четверг, 12 марта 2009 г.

Развитие PageRank

С того момента, когда PageRank был впервые представлен в 1998 году, было потрачено немало усилий, чтобы улучшить его качество и скорость вычисления. В этой обзорной и достаточно популярной статье я опишу основные направления исследований вокруг PageRank и варианты алгоритма.

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

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

На следующей картинке схематически представлены основные направления исследований, окруживших PageRank. Каждому овалу на схеме будет соответствовать отдельная глава статьи.



PageRank с математической стороны


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

PageRank страницы – это вероятность того, что блуждающий «пользователь» находится на данной странице.

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

Пронумеруем web-страницы целыми числами от 1 до N.

Сформируем матрицу переходов P, содержащую вероятность перехода «пользователя» с одной страницы на другую. Пусть deg(i) – количество исходящих ссылок на странице i. В таком случае, вероятность перехода со страницы i на страницу j равна:

P[i, j] = 1 / deg(i), если i ссылается на j
P[i, j] = 0, если i не ссылается на j

Пусть p(k) – это вектор, содержащий для каждой страницы вероятность того, что в момент k на ней находится «пользователь». Этот вектор – распределение вероятностей местоположения «пользователя».

Предположим, что «пользователь» может начать своё бесцельное блуждание с любой страницы. То есть, начальное распределение вероятностей равномерно.

Зная распределение вероятностей в момент k, мы можем узнать распределение вероятностей в момент k+1 по следующей формуле:



В основе этой формулы не более чем правила сложения и умножения вероятностей.

Математически мы пришли к цепи Маркова с матрицей переходов P, где каждая web-страница представляет собой одно из состояний цепи.

Но нам нужно знать вероятность нахождения «пользователя» на странице независимо от того, сколько шагов k он сделал от точки начала блуждания.

Мы берём начальное распределение вероятностей p(0). Считаем по представленной выше формуле распределение p(1). Затем по той же формуле считаем p(2), затем p(3) и т.д. до тех пор, пока некие p(k-1) и p(k) не будут отличаться лишь незначительно (полное равенство будет достигнуто при k стремящемся к бесконечности).

Таким образом, последовательность p(1), p(2), p(3) … сойдётся к некому вектору p = p(k). Интересно, что вектор p на самом деле не зависит от начального распределения (т.е. от того, с какой страницы начал своё блуждание воображаемый «пользователь»).

Вектор p таков, что в любой момент (начиная с некоторого момента k), вероятность того, что «пользователь» находится на странице i, равна p[i]. Это и есть искомый PageRank.

Этот алгоритм называется методом степеней (power method). Он сойдётся только в том случае, если выполняются два условия: граф страниц должен быть сильно связным и апериодическим. Как достигается выполнение первого условия, будет рассмотрено далее. Второе же без дополнительных усилий справедливо для структуры web.

Примечание


При выполнении условий сильной связности и апериодичности, согласно эргодической теореме, цепь Маркова с матрицей перехода P имеет единственное стационарное распределение p:



PageRank и является стационарным распределением цепи Маркова.

Также это выражение представляет собой собственную систему, а вектор p — собственный вектор матрицы A. Поэтому и применяется метод степеней — численный метод для поиска собственных векторов.

Висячие узлы (dangling nodes)


Висячие узлы – это страницы, которые не имеют исходящих ссылок. Страница может не иметь исходящих ссылок просто потому, что у неё их нет, либо потому, что она не была прокраулена (crawled) – т.е. страница попала в базу, т.к. на неё ссылаются другие прокрауленные страницы, но сама прокраулена не была, и о её исходящих ссылках ничего не известно.

Для вычисления PageRank в графе страниц не должно быть висячих узлов. Сумма каждого ряда матрицы переходов должна быть равна единице (row-stochastic), для висячих же узлов она окажется равной 0 – входные данные алгоритма будут некорректными.

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

Метод удаления


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

Кроме того, удаление висячих узлов, может создать новые висячие узлы. Таким образом, требуется проделать несколько итераций удаления (обычно 5 или что-то около того).

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

Считать связанными со всеми другими страницами


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

Можно считать вероятность попадания «пользователя» на страницу из висячего узла в результате такого перескока распределённой равномерно среди всех страниц сети. Но можно и не считать её таковой. Например, можно исключить попадание из висячего узла на другой висячий узел. Или распределить вероятность между страницами по аналогии с аристократическим вектором телепортации, о котором будет рассказано ниже в главе Телепортация.

Матрица переходов модифицируется следующим образом:



d[i] = 1, если i – висячий узел, и 0 в противном случае
v[j] – вероятность попадания «пользователя» на страницу j из висячего узла

Шаг назад (step back)


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

Петля (self-link)


Упомяну кратко ещё один способ. Каждому висячему узлу можно добавить ссылку на самого себя – это приведёт в порядок матрицу переходов. Но после вычисления PageRank, результат придётся определённым образом скорректировать. Подробности описаны в G. Jeh and J.Widom “Scaling Personalized Web Search.”

Телепортация


Решение проблемы висячих узлов ещё не даёт сильную связность графа. Поэтому вводится телепортация.

В модели случайного блуждания это выглядит так: «пользователь», находясь на некоторой странице, с вероятностью c переходит по одной из её ссылок и с вероятностью (1 – c) * v[j] перескакивает (телепортируется) на страницу j. Стохастический вектор v описывает вероятность телепортации на ту или иную страницу и называется вектором телепортации.

c как правило выбирается в диапазоне 0.85 – 0.9. Большие значения дают более точные результаты, но более медленную сходимость. Меньшие значения – быструю сходимость, но менее точные результаты.

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

Существует два способа выбора вектора телепортации: демократический и аристократический. Демократический вектор содержит одинаковые значения вероятности для всех страниц. Это стандартный вариант. Аристократический содержит низкую вероятность для обычных страниц и более высокую для избранных достоверно качественных неспамерских страниц. Последний способ явно поощряет избранные страницы в ущерб остальным, зато более устойчив к поисковому спаму.

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

Значение v[j] не должно быть равно 0. Иначе может оказаться, что j недосягаема из некой другой страницы, что означает нарушение сильной связности.

Телепортация модифицирует матрицу переходов следующим образом:



v – вектор телепортации

Мы ещё вернёмся к вектору телепортации, когда будем обсуждать персонализацию PageRank.

Ускорение метода степеней


Многие исследователи пытались ускорить сходимость метода степеней. Посмотрим на самые удачные способы.

Для удобства повторю формулу, которую мы используем на каждой итерации. Назовём её формулой А:



Метод Гаусса-Зейделя (Gauss-Seidel method)


На каждой итерации в методе степеней мы используем значения элементов вектора p(k) чтобы рассчитать вектор p(k+1). Отличие метода Гаусса-Зейделя в том, что мы сразу используем значения вычисленных элементов вектора p(k+1) для вычисления его остальных элементов.

В методе Гаусса-Зейделя мы последовательно элемент за элементом вычисляем вектор p(k+1). При это там где, согласно формуле А, нам нужно использовать значение p(k)[i] мы используем p(k+1)[i], если этот элемент вектора уже был вычислен.

Согласно экспериментам этот метод способен сократить необходимое количество итераций на 40%. Его недостаток в том, что его достаточно сложно вычислять параллельно.

Методы экстраполяции (Extrapolation methods)


В этой группе методов мы проделываем некоторое количество d обычных итераций метода степеней. Затем на основе результатов этих итераций строим аппроксимацию решения и используем её вместо p(k) для следующей итерации. Через следующие d итераций повторяем трюк. И так далее пока алгоритм не сойдётся.

Исследователям удавалось достичь сокращения необходимого количества итераций на 30%.

Адаптивный метод (Adaptive method)


Этот метод основан на наблюдении, что значительная часть элементов вектора p сходится гораздо быстрее остальных и затем почти не меняется. Ускорение в этом методе достигается за счёт того, что мы не пересчитываем значения таких элементов.

Если в какой-то момент k для некоторого элемента i обнаруживается что p(k+1)[i] - p(k)[i] меньше определённого порога, мы считаем, что значение PageRank для страницы i найдено и более не пересчитываем i-тый элемент вектора p.

Исследователям удавалось достичь сокращения времени работы метода степеней на 20% при помощи этого трюка.

Однако данный метод требует периодически переупорядочивать данные, чтобы избежать вычисления тех элементов, значения которых считаются уже найденными. Поэтому адаптивный метод плохо подходит для больших графов – переупорядочить огромный объём данных становится слишком дорогой задачей.

Метод блочной структуры (Block Structure Method)


Web имеет блочную структуру. Это открытие столь интересно, что я намерен посвятить ему отдельный пост. Там же и обсудим этот метод.

UPD: пост о блочной структуре web.

Численные методы


Вычисляя значение PageRank, мы ищем такой вектор p, что



Это выражение является так называемой собственной системой, а p – собственный вектор матрицы A. Задача поиска собственного вектора может быть представлена системой линейных уравнений. В нашем случае это будет огромная, но всё же обычная система, которая может быть решена при помощи численных методов линейной алгебры.

Тем не менее, вычисление PageRank численными методами ещё находится в экспериментальной области. Каковы будут характеристики и свойства этих методов на реальных графах web пока не понятно.

Стоит отметить, что существуют уже готовые решения для параллельного вычисления крупных линейных систем.

Параллелизация


Вычисление PageRank параллельно на нескольких машинах позволяет существенно ускорить работу.

По сути методы параллелизации можно разделит на два типа.

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

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

UPD: пост о блочной структуре web.

Оптимизация ввода-вывода


Это довольно интересная тема, которую я приберегу для одного из следующих постов. Я представлю три алгоритма, которые будут интересны не только с точки зрения вычисления PageRank, но и вообще с точки зрения обработки больших объёмов информации.

Эволюция графа


Довольно естественной кажется идея не пересчитывать PageRank для всех страниц целиком, а найти способ обновлять его по мере эволюции графа страниц (по мере эволюции web).

В «Incremental Page Rank Computation on Evolving Graphs» Prasanna Desikan и др. предлагают следующий способ.

Сперва выделить часть графа, состоящую из страниц, до которых не существует путей от новых страниц, исчезнувших страниц, либо страниц, ссылки которых были изменены. Удалить эту часть графа, оставив только граничные узлы (т.к. они влияют на PageRank оставшихся страниц). Посчитать PageRank для оставшегося графа. Затем отмасштабировать значения PageRank с учётом общего количества страниц – т.к. количество страниц влияет на часть PageRank, получаемую за счёт телепортации.

Замечу, что полученный в результате PageRank не является точным, а всё же некой аппроксимацией.

По различным данным от 25% до 40% ссылок между web-страницами меняются в интернет в течение недели. Такая скорость изменения, на мой взгляд, оправдывает полный пересчёт PageRank всех страниц.

Персонализация


Представление о важности той или ной страницы во многом субъективно. То, что покажется одному отбросом, другой сочтёт изумрудом. Пусть есть очень качественная страница об игре керлинг, но я совершенно не хочу, чтобы она вылезала лично мне в топ. Чтобы учитывать в ранжировании интересы конкретного человека был придуман персонализированный PageRank.

Выбирается какое-то количество категорий, по которым можно классифицировать тематику тех или иных страниц (или сайтов). Например: культура, спорт, политика и т.п.

Пусть T[j] – множество страниц, принадлежащих к категории j (или расположенных на сайте, принадлежащем к данной категории).

Для каждой категории формируется особый вектор телепортации v (см. главу Телепортация).

v[i] очень мало, если страница i не принадлежит T[j], и значительно больше если принадлежит.

Для каждого тематического вектора телепортации вычисляется тематический PageRank pj. Вычислить сто тематических PageRank для ста категорий вполне реально.

Допустим, у нас есть вектор k, сумма элементов которого равна единице. Значение k[j] отражает степень заинтересованности пользователя (реального, а не того из модели блуждания) в категории j.

Степень заинтересованности пользователя может быть указана явно, или она может быть сохранена в его профиле. Или она может быть выведена исходя из того, какие слова входят в запрос. Например, если запрос содержит слово fairtrade то можно вывести, что пользователь заинтересован на 0.4 в теме общество, на 0.4 в теме экономика и на 0.2 в теме политика.

Во время ранжирования результатов запроса пользователя для страниц используется следующее итоговое значение PageRank:

k[0] * p0 + k[1] * p1 + … + k[n] * pn , где n – количество категорий

Таким образом, рейтинг страницы будет зависеть от того, что реально интересно пользователю.

Темы, которые будут рассмотрены в следующих постах


Оптимизация ввода-вывода


Это довольно интересная тема, которую я приберегу для одного из следующих постов. Я представлю три алгоритма, которые будут интересны не только с точки зрения вычисления PageRank, но и вообще с точки зрения обработки больших объёмов информации.

Siterank


UPD: Эта тема освещена в посте о блочной структуре web.

8 комментариев:

Ujin комментирует...

Довольно толково и интересно всё описано! Спасибо!

Eugenijus комментирует...

Спасибоб супер!

Анонимный комментирует...

Огромное человеческое спасбо!

Крутой сайт! Все полезно сделано.

Анонимный комментирует...

хороший пост!

Анонимный комментирует...

Понравился пост))). спасибо

Анонимный комментирует...

Many thanks for an explanation, now I will not commit such error.
[url=http://www.livejournali.com]It is remarkable, rather useful idea[/url]

Анонимный комментирует...

Spasibo. Informacia prigoditsya

Unknown комментирует...

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

Разрешите задать Вам пару вопросов.
Скажите, было ли у Вас так, что при удалении висячих узлов в исходной матрице способами Self-Link и Step Back наибольшее собственное значение марковской матрицы P получалось отличным от числа Фробениуса λ=1? И если да, то почему и как Вы с этим справлялись? Ведь по следствию из теоремы Фробениуса гарантией неразложимости марковской матрицы P является только наличие наибольшего собственного значения λ=1 (т.е. числа Фробениуса) этой матрицы P. В свою очередь, сходимость степенного метода вычисления собственного вектора с рангами может быть гарантирована только в случае, если λ=1 и матрица P неразложимая. Но если наибольшее собственное число матрицы P после преобразований Self-Link или Step Back не равно 1, а в некоторых случаях даже комплексное, то как тогда быть и где искать ошибку? Или нужно в таком случае просто искать наибольшее собственное число и соответствующий ему вектор с искомыми рангами, не обращая внимания на его несоответствие числу Фробениуса λ=1?
Буду очень благодарен за пояснение, если Вас не затруднит это. Если здесь писать не удобно, то можете написать на hackcatt@gmail.com.

И ещё вопрос: каким способом вы получили иллюстрации с графиками распределения связанности страниц в web?
Заранее огромное спасибо.