Узнайте, как поисковая система Google ранжирует документы на основе их структуры ссылок.

Ранжирование — важная проблема в машинном обучении. Учитывая набор документов, цель состоит в том, чтобы отсортировать их в определенном порядке на основе определенных критериев. Ранжирование широко используется в информационно-поисковых системах для сортировки результатов поиска или в рекомендательных системах для фильтрации контента, потенциально интересного конкретному пользователю.

На основе данной проблемы и цели существует множество алгоритмов ранжирования. Тот, который мы собираемся изучить в этой статье, называется PageRank. Его основная цель — ранжировать набор документов (веб-страниц), используя информацию об их связности. Ранг, присвоенный каждой веб-странице, указывает на ее важность: чем выше ранг, тем выше важность. Алгоритм основан на двух предположениях, которые мы рассмотрим в следующем разделе.

Предположения

Мы можем определить термин «важность» веб-страницы, сделав два предположения.

Важность веб-страницы высока, если на нее указывает много других веб-страниц.

Представьте, что у нас есть популярная исследовательская работа и множество других статей, на которые ссылаются цитаты или результаты из нее. В первую очередь имеет смысл придать этой статье большое значение. С другой стороны, если есть неизвестная веб-страница, на которую нет ссылок с других ресурсов, логично присвоить этой странице низкую важность.

На самом деле, мы также должны заботиться о качестве входящих ссылок.

Важность веб-страницы пропорциональна важности веб-страниц, указывающих на нее.

Если страница изначально цитируется качественной статьей в Википедии, то такая ссылка должна иметь больший вес. И наоборот, когда абсолютно неизвестный ресурс указывает на другую веб-страницу, обычно это не должно иметь большого значения.

Формальное определение

Допустим, важность узла равна сумме весов входящих ссылок.

Представьте себе узел i с важностью rᵢ, имеющий k исходящих ссылок. Как мы можем определить вес каждой ссылки? Самый простой подход — взять важность узла и разделить ее поровну между всеми исходящими ссылками. Таким образом, каждая исходящая ссылка получит вес rᵢ / k.

Имея граф из n веб-страниц, мы можем создать систему из n линейных уравнений, чтобы найти веса графа. Однако такая система может иметь бесконечное число решений. Вот почему мы должны добавить еще одно ограничение, которое наложит уникальное решение. Кстати, PageRank добавляет нормализованное условие, что сумма важности всех узлов равна 1.

Мы придумали решение, но оно не масштабируемо. Даже при исключении Гаусса мы получаем сложность O(n³). Учитывая, что количество проанализированных веб-страниц n может достигать миллиардов, нам необходимо придумать более эффективный подход.

Прежде всего, упростим обозначения. Для этого введем квадратную матрицу смежности G, которая будет содержать веса ссылок для каждой пары связанных веб-страниц (если две веб-страницы не связаны, мы поместим 0 в соответствующий элемент матрицы). Более формально:

Матрица G называется стохастической, поскольку сумма всех ее столбцов равна 1.

Затем мы определяем вектор рангов r, элемент i которого равен рангу (важности) страницы i. Сумма всех элементов этого вектора также равна 1. Наша конечная цель — найти значения этого вектора r.

Уравнение PageRank

Посмотрим, что произойдет, если мы умножим матрицу G на вектор r. Основываясь на примере с графиком из раздела выше, мы видим, что он приводит к тому же вектору r!

Почему это происходит? Это просто совпадение? Помните, что i-я строка матрицы G содержит веса всех входных ссылок на страницу i. Когда мы умножаем j-й элемент i-й строки на r[j], мы фактически получаем компонент r j / d[j]out — важность, которая перетекает из узла j в i. Если между узлами i и j нет связи, то соответствующий компонент устанавливается равным 0. Логически конечный результат умножения i em>-я строка по вектору r будет равна сумме всех значимостей, которые перетекают из любой связной вершины графа в вершину i. По определению это значение равно рангу узла i. В общем случае мы можем написать следующее уравнение:

Поэтому наша цель — найти такой вектор r, который при умножении на входную матрицу G останется прежним.

Собственные векторы

Мы можем найти решение приведенного выше уравнения, пересмотрев теорию собственных векторов из линейной алгебры. Для матрицы A вектор v называется собственным вектором, если существует такое число α, которое удовлетворяет следующее уравнение:

Число α называется собственным значением. Мы можем заметить, что уравнение PageRank соответствует уравнению собственных значений, где A = G, v = r и α = 1. Обычно любая квадратная матрица имеет несколько собственных значений и собственных векторов, но поскольку наша матрица G является стохастической, теория утверждает, что ее наибольшее собственное значение равно 1.

Мощная итерация

Одним из самых популярных способов нахождения собственных векторов матрицы является метод степенной итерации. Он состоит из инициализации исходного вектора r некоторыми значениями (мы будем использовать 1 / n, где n — количество веб-страниц), затем постоянно вычисляя значение G * r и снова присваивая это значение r. Если на какой-либо итерации расстояние между векторами r и G * r меньше некоторого порога ε, останавливаем алгоритм, так как он сошёлся успешно.

В приведенном выше примере мы видим, что при установке εв0,0005 алгоритм корректно сходится всего за 9 итераций:

Очевидно, что это всего лишь игрушечный пример, но на практике этот метод очень хорошо работает и для большего числа переменных.

Случайная прогулка

Представьте серфера (ходока), который находится в любом узле графа в момент времени t. Обозначим через p(t) вектор, i-я компонента которого равна вероятности того, что в момент времени t серфер находится в узле я. Затем серфер случайным образом (с равными вероятностями) выбирает другой связанный узел с текущим и перемещается туда в момент времени t + 1. В конечном итоге мы хотим найти вектор распределения p(t + 1) в момент времени t + 1.

Мы можем заметить, что вероятность появления серфера в узле i в момент t + 1 представляет собой сумму вероятностей (по всем связанным узлам до i), что пользователь ранее находился в соседнем узле j, умноженной на вероятность перемещения из узла j в i.

  • Мы уже знаем вероятность появления серфера в узле j в момент t: p(t)[j].
  • Вероятность перехода из узла j в i равна G[j][i].

Суммируя эти вероятности, мы получаем значение для p(t + 1)[i]. Чтобы найти значение p(t + 1) для всех узлов графа, мы можем написать одно и то же уравнение в матричной форме:

Это уравнение имеет абсолютно такой же вид, как то, что мы получили для PageRank раньше! Это означает, что эти две проблемы имеют одинаковое решение и интерпретацию.

В какой-то момент вектор распределения p(t) сойдется: p(t + 1) = M * p(t) = p(t). Сходящийся вектор p(t) в таком случае называется стационарным распределением. Во все последующие моменты времени вероятность пребывания в любом заданном узле не меняется.

Показатель PageRank узла равен вероятности того, что посетитель окажется в этом узле в будущем, случайно прогуливаясь по графу.

Конвергенция

Описанный процесс обхода графа часто называют «цепями Маркова». В теории цепей Маркова существует теорема, которая утверждает, что:

При определенных условиях на структуру графа стационарное распределение уникально и может быть достигнуто при любом начальном распределении вероятностей в момент t = 0.

В следующем разделе мы более подробно рассмотрим условия, которые необходимо выполнить для однозначной сходимости. Оказывается, не для всех графов можно добиться однозначной сходимости.

В принципе, существует 2 типа случаев, которых мы хотим избежать любой ценой.

Тупики

Узлы, не имеющие исходящих связей, называются тупиками. Проблема с такими узлами заключается в том, что из-за них общая значимость утекает из сети. Вот пример:

Ловушка для пауков

Группа узлов образует ловушку для пауков, если у них нет исходящих ссылок на другие узлы за пределами этой группы. По сути, оказавшись там, невозможно выбраться за пределы этой группы узлов. Ловушки для пауков приводят к двум следующим проблемам:

  • Алгоритм никогда не сходится.
  • Группа узлов, образующих ловушку для пауков, поглощает всю важность графа. В результате эти узлы имеют очень высокую важность, в то время как другие узлы имеют важность, равную 0.

Первая проблема показана на рисунке ниже:

Поглощение важности показано на следующем рисунке. Хотя в игрушечном примере ниже это может показаться несерьезной проблемой, представьте себе веб-сеть с миллионами веб-страниц, некоторые из которых образуют ловушку для пауков. Как следствие, эти несколько страниц будут распределять всю доступную важность, в то время как важность всех других веб-страниц будет установлена ​​на 0. Очевидно, что это не то, чего мы обычно хотим в реальной жизни.

Телепорты

Одним из решений, предложенных Google, является добавление следующего условия перед каждым движением серфера:

  • С вероятностью β перейти к другому связанному узлу.
  • С вероятностью (1 — β) переместиться в случайный узел (через телепорт).

Параметр β называется фактором демпинга. Авторы исходного алгоритма PageRank рекомендуют выбирать значение для β = 0,85, что означает, что в среднем после 5 переходов серфер случайным образом перейдет к другому узлу. Идея состоит в том, что если серфер попадет в паучью ловушку, то через какое-то время он в итоге выберется оттуда через телепорт.

На диаграмме ниже показано, как телепорты могут помочь справиться с проблемой ловушек для пауков. Если серфер войдет в узел c, он останется там навсегда. Внедрение телепортов (синие линии) помогает устранить эту проблему, гарантируя, что через некоторое время серферу придется идти к другому случайному узлу.

Однако для тупиковых узлов нужно немного изменить подход. Из одного из приведенных выше примеров мы знаем, что тупики приводят к утечке важности в графе. Это явление можно наблюдать при методе степенных итераций, когда вектор рангов становится заполненным нулями из-за соответствующего нулевого столбца в исходной матрице G. В конечном итоге мы можем сделать следующее:

Всякий раз, когда серфер попадает на тупиковый узел, он должен немедленно перейти к случайному узлу (с равной вероятностью) графа.

На самом деле мы можем изменить исходную матрицу G, чтобы удовлетворить этому утверждению: нам просто нужно заменить нули на 1/n вместо всех элементов столбцов всех тупиковые узлы матрицы G. Пример ниже демонстрирует этот принцип.

Узел c является тупиковым узлом с соответствующим столбцом нулей в матрице G. Добавление n = 3 телепортов из c во все узлы графа приводит к равной вероятности p = 1 / 3 перемещения из c к любому узлу. Чтобы учесть это, мы заполняем столбец матрицы G, соответствующий узлу c, значениями 1 / 3.

Мы можем заметить, что после добавления телепортов сумма всех столбцов матрицы теперь равна 1. Другими словами, матрица G становится стохастической. Это существенное свойство, которое мы будем использовать позже.

Условия сходимости

Существует ключевая теорема теории цепей Маркова, определяющая условие сходимости.

Для любого начального вектора матрица перехода G сходится к единственному положительному стационарному вектору распределения r, если цепь, соответствующая G, является стохастической, апериодической и неприводимой.

Напомним последние три свойства этой теоремы и проверим, решают ли введенные телепорты поставленные выше задачи.

Цепь G называется стохастической, если сумма каждого ее столбца равна 1.

Как мы заметили выше, добавление телепортов в тупиковые узлы устраняет нулевые столбцы в матрице и делает сумму всех ее столбцов равной 1. Условие уже выполнено.

Цепь G называется периодической, если существует такое число k > 1, что длина пути между любой парой узлов всегда кратна k. В противном случае цепь называется апериодической.

Это условие означает, что любой возврат в одно и то же состояние должен происходить кратно k раз. В случае апериодичности возврат происходит нерегулярно. По сути, это состояние относится к проблеме с ловушкой для пауков. Поскольку мы уже разобрались с ловушками для пауков, добавив телепорты, цепочка G является апериодической.

Цепь G называется неприводимой, если вероятность перехода из любого узла в любой другой узел всегда больше 0.

Это условие подразумевает, что между любыми двумя узлами всегда существует связь, поэтому невозможно застрять ни на одном узле. Другими словами, матрица G должна состоять из всех ненулевых элементов. В следующем разделе ниже мы увидим, как это условие будет удовлетворено, если соединить все узлы графа.

Изменение алгоритма

Алгоритм PageRank, предложенный Google, берет исходную матрицу G и корректирует ее, добавляя телепорты из тупиков в другие узлы. Это обеспечивает стохастичность. Затем, чтобы гарантировать апериодичность и неприводимость, к каждому узлу добавляется условие, описанное ранее:

  • С вероятностью β перейти к другому связанному узлу.
  • С вероятностью (1 — β) перейти к случайному узлу.

Математически это приводит к следующему ранговому уравнению для каждого узла:

Это уравнение можно преобразовать в матричную форму:

Нарисуем модифицированный граф и соответствующую матрицу перехода R из одного из приведенных выше примеров:

Повышение эффективности

Остается только одна проблема: как хранить матрицу перехода R. Помните, что R — это квадратная матрица размера n x n, где n — количество веб-страниц. В настоящее время у Google более 25 миллиардов веб-страниц! Матрица R не имеет нулей, поэтому она плотная, что означает, что мы должны хранить ее полностью. Предположим, что для хранения каждого элемента матрицы требуется 4 байта. Общий объем памяти, необходимый для хранения матрицы R, равен (25 * 10⁹)² * 4(байт)~ 3 * 10²¹(байт) . Это гигантский объем памяти! Нужно придумать другой подход, чтобы уменьшить хотя бы на несколько порядков.

Во-первых, мы можем просто заметить, что добавление телепортов эквивалентно уменьшению исходных элементов матрицы G на (1 — β)% и их равномерному распределению по каждому узлу. Имея это в виду, мы можем преобразовать матричное уравнение PageRank в другой формат:

Посмотрим на последнее полученное уравнение. G — исходная матрица ссылок, большинство элементов которой равны 0. Почему это так? В действительности, если вы возьмете любую веб-страницу, она, вероятно, будет содержать не более нескольких десятков ссылок на другие веб-страницы. Имея в виду, что это более 25 миллиардов веб-страниц, мы получаем, что относительное количество общих ссылок по сравнению с количеством веб-страниц чрезвычайно мало. Следовательно, в G много нулей, поэтому G является разреженным.

Для хранения разреженных матриц требуется гораздо меньше памяти, чем для плотных. Предположим, что каждая веб-страница ссылается в среднем на 40 других страниц. Общее количество байтов, необходимых для хранения матрицы G, теперь равно 25 * 10⁹ * 40(байт)= 10¹²(байт)= 1 ( ТБ). Оказывается, нам нужен всего 1 терабайт для хранения G. По сравнению с тем, что было раньше, это потрясающее улучшение!

Фактически на каждой итерации нам нужно только вычислить произведение матрицы G на вектор r, умножить его на β и добавить константу (1 — β) / n к каждому элементу результирующего вектора.

Также имейте в виду, что если исходная цепочка G содержит тупиковые узлы, то сумма вектора r на каждой итерации будет меньше 1. Чтобы справиться с этим, достаточно его перенормировать, чтобы сумма всех компонент вектора равнялась 1.

Полный алгоритм

На рисунке ниже мы видим полную версию алгоритма PageRank. На каждой итерации обновление рангов происходит в 2 этапа. Первый этап включает только обновление по исходной матрице G. Затем мы суммируем компоненты вектора рангов в переменной s. Таким образом, значение (1 — s) — это значение, на которое был уменьшен общий входной ранг одного узла. Чтобы компенсировать это, на втором этапе мы учитываем телепорты и добавляем их от узла ко всем узлам с равным значением (1 — s) / n.

Заключение

В этой статье мы рассмотрели различные формулировки алгоритма PageRank, чтобы в конечном итоге прийти к его оптимизированной версии. Несмотря на существование и эволюцию других методов ранжирования результатов поиска, PageRank остается самым эффективным алгоритмом среди других, которые работают под капотом поисковой системы Google.

Рекомендации

Логическая структура этой статьи основана на лекции Стэнфордского университета о больших графах.

Все изображения, если не указано иное, принадлежат автору