ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 3, с. 355-371
УДК 519.62
ОБ ЭФФЕКТИВНЫХ РАНДОМИЗИРОВАННЫХ АЛГОРИТМАХ ПОИСКА ВЕКТОРА PAGERANK1
© 2015 г. А. В. Гасников, Д. Ю. Дмитриев
(141000Долгопрудный, М.о., Институтский пер., 9, МФТИ, ИППИРАН) e-mail:gasnikov@yandex.ru, dmitden@gmail.com Поступила в редакцию 03.09.2014 г.
В работе рассматриваются два рандомизированных способа поиска вектора PageRank, т.е. решения системы p1 = pTP, со стохастической матрицей P размера n х n (решение ищется в классе распределений вероятностей), где n ~ 107—109, с точностью s: s n—1, таким образом исключается возможность "честного" умножения матрицы P на столбец, если рассматривать не разреженные объекты. Первый способ базируется на идее Markov chain Monte Carlo. Этот
подход эффективен в случае "быстрого" выхода итерационного процесса pj +1 = pJP на стационар, и учитывает также другую специфику матрицы P — равенство отличных от нуля вне диагональных элементов матрицы P по строчкам (это используется при организации случайного блуждания по графу с матрицей P). На основе современных неравенств концентрации меры в работе приводятся новые оценки времени работы такого метода, учитывающие специфику матрицы P. В основе второго способа лежит идея сведения поиска ранжирующего вектора к поиску равновесия в антагонистической матричной игре:
min max (u, (PT -1) p),
P e Sn( 1) u e Sn(1)
где ¿*n(1) — единичный симплекс в Rn, а I — единичная матрица. Возникшая задача решается с помощью небольшой модификации алгоритма Григориадиса—Хачияна (1995). Этот метод, также как метод Назина—Поляка (2009), является рандомизированным вариантом метода зеркального спуска А.С. Немировского. Отличие заключается в том, что у Григориадиса—Ха-чияна рандомизация осуществляется на этапе проектирования на симплекс, а не на этапе вычисления стохастического градиента. Для разреженных матриц P предложенный нами метод показывает заметно лучшие результаты. Библ. 67.
Ключевые слова: метод зеркального спуска, Markov chain Monte Carlo, стохастическая оптимизация, рандомизация, PageRank.
DOI: 10.7868/S0044466915030060
1. ВВЕДЕНИЕ
Известно, что поисковая система Google была создана в качестве учебного проекта студентов Стэнфордского университета (см. [1]). В 1996 году они работали над поисковой системой BackRub, а в 1998 году на ее основе создали новую поисковую систему Google (см. [2], [3]). В [1] был предложен определенный способ ранжирования web-страниц. Этот способ, также как и довольно большой класс задач ранжирования, возникающих, например, при вычислении индексов цитирования ученых или журналов (см. [4]), сводится (см. [5]) к нахождению левого соб-
Zn
pk = 1), отвечающего собственному зна-
k = 1
чению 1, некоторой стохастической (по строкам) матрицы P = 1 : p1 = pxP.
Замечание 1. К поиску такого вектора, который иногда называют вектором Фробениуса—Перрона, сводится (например, в модели де Гроота) задача поиска консенсуса. Подробнее об этом, и в целом о моделях консенсуса, написано в обзоре [6].
Работа выполнена при финансовой поддержке РФФИ (код проекта 14-01-00722-а); Лаборатории структурных методов анализа данных в предсказательном моделировании ФУПМ МФТИ; гранта Президента РФ № МК-5285.2013.9, исследование метода МСМС выполнено за счет гранта РНФ (проект № 14-50-00150).
Замечание 2. Решение рт = ртР всегда существует по теореме Брауера (непрерывный (ограниченный) оператор Р отображает выпуклый компакт (симплекс) в себя), и единственно в классе распределений вероятностей тогда и только тогда, когда имеется всего "один класс сообщающихся (существенных) состояний" при возможном наличии "несущественных состояний" (см. [7]). Другими словами, если мы поставим в соответствие матрице Р такой ориентированный граф, что и вершины I иу соединены ребром тогда и только тогда, когдар у > 0, то в таком графе любая вершина может принадлежать только одному из двух типов: несущественная, когда стартуя из этой вершины и двигаясь по ребрам с учетом их ориентации, мы всегда можем забрести в такую вершину, из которой обратно никогда не вернемся; существенная, когда стартуя из любой такой вершины, мы можем добраться в любую другую существенную вершину (в частности, вернуться в исходную).
Приведем, следуя [5], обоснование такому способу. Пусть имеется ориентированный граф О = (V, Е) сети Интернет (вершины — web-страницы, ребра — ссылки: запись (/, у) е Е означает, что на 1-й странице имеется ссылка нау-ю страницу), N — число пользователей сети (это число не меняется со временем). Пусть п((?) — число посетителей web-страницы I в момент времени За один такт времени каждый посетитель этой web-страницы независимо ни от чего с вероятностью ру переходит по ссылке на web-страницуу. Считаем стохастическую матрицу Р неразложимой и апериодической (см. [7]). Ниже приведен результат из [5] (обоснование будет приведено в разд. 4), позволяющий по-другому интерпретировать вектор р (PageRank), согласно которому и происходит ранжирование web-страниц:
3^099 > 0, Т> 0: Vt > Т,
P
иОО N
<
0.99
JN-
> 0.99,
где рт = ртР (решение единственно в классе распределений вероятностей в виду неразложимости).
В ряде случаев считают, что
Р = (1 - 5) I + 5Р, где 5 е (0, 1], I = diag{1, ..., 1} — единичная матрица,
~п = [|{к : (I,])е Е}|-1, Iф], "ч | Л
10 иначе.
Такая специфика матрицы P нами будет использоваться в разд. 4. Отметим также, что вместо I часто берут стохастическую матрицу с одинаковыми элементами — матрицу телепортации (см. [2]). Это сразу дает оценку снизу 5 на спектральную щель матрицы P.
Опишем вкратце структуру статьи. В разд. 2 приводится обзор наиболее популярных известных ранее способов численного поиска вектора PageRank. Новизна заключается в том, что этот обзор делается одновременно с декларированием двух новых способов поиска вектора PageRank: на основе Markov chain Monte Carlo (MCMC) и на основе алгоритма Григориадиса—Хачияна. В разд. 3, также носящем обзорный характер, кратко описываются основные необходимые в дальнейшем факты о методе MCMC. Новых результатов в этом пункте нет. Тем не менее, интерес может представлять обзор литературы. В разд. 4 метод MCMC применяется для поиска вектора PageRank. Новыми здесь являются оценки скорости сходимости такого метода, а также оценки общего числа затраченных арифметических операций. Подчеркнем, что в отличие от общего случая, мы ограничиваемся в данной статье изучением эффективности метода MCMC на специальном классе задач. За счет этого удается получить существенно лучшие оценки, чем можно было бы ожидать в общем случае. Новизна метода также заключается в том, как организуются случайные блуждания. Отметим, что предложена хорошо параллелизуемая версия метода MCMC. Описанный выше метод MCMC будет хорошо работать, если спектральная щель матрицы P достаточно велика. В разд. 5 предложен новый способ поиска вектора PageRank, не требующий ограничений на спектральную щель. Этот способ сводит поиск ранжирующего вектора к поиску равновесия Нэша в антагонистической матричной игре. Для поиска равновесия мы используем метод Григориадиса—Хачияна, который позволяет учитывать разреженность матрицы P и хорошо распараллеливается.
2. ОБЗОР И ОБСУЖДЕНИЕ ИЗВЕСТНЫХ РАНЕЕ И НОВЫХ СПОСОБОВ ЧИСЛЕННОГО ПОИСКА ВЕКТОРА PageRank
В работах [8]—[15] предложены различные способы численного поиска вектора PageRank p.
Замечание 3. Строго говоря, в [11] и [12] решались другие задачи, но несложно перенести алгоритмы этих работ на задачу поиска вектора PageRank: в случае [11] это делается тривиально, а вот в случае [12] потребуется немного более точное исследование сходимости — поправка ln(a—1) появляется из-за того, что мы избавляется от математического ожидания в критерии качества (цели).
Приведем краткое резюме сложностных оценок алгоритмов работ [8]—[15] и алгоритмов, предложенных в этой статье. "Сложность" понимается как количество арифметических операций типа умножения двух чисел, которые достаточно осуществить, чтобы с вероятностью не меньше 1 — а достичь точности решения б по "целевому" функционалу.
Поясним основные сокращения:
♦ G-условие — наличие такой web-страницы (например, страницы, отвечающей самой поисковой системе Google), на которую можно перейти из любой другой web-страницы с вероятностью не меньшей, чем а > cn—1, не ограничивая общности, будем считать, что вершина, отвечающая этой web-странице, имеет номер 1 (см. алгоритм MCMC);
♦ S-условие — из каждой web-страницы выходит не более s < n ссылок на другие, т.е. имеет место разреженность матрицы P (Sparsity); если из каждой web-страницы одновременно выходит и
входит не более s < n ссылок, то будем говорить об S условии;
Замечание 4. В ряде случаев (например, для метода из [14]) можно релаксировать S-условие: "выходит в среднем".
♦ SG-условие — спектральная щель а (Spectral Gap) матрицы Pудовлетворяет условию а > n~2, где а — расстояние между максимальным по величине модуля собственным значением (числом Фробениуса—Перрона) матрицы P (равным 1) и модулем следующего (по величине модуля) собственного значения. Если выполняется G-условие, то выполняется и SG-условие с а не меньшим, чем в G-условии (см. [2], [15]).
Отметим, что приведенная таблица немного огрубляет результаты процитированных работ, в частности, работ [9], [10]. Это сделано для большей наглядности. Отметим также, что приведенная здесь оценка сложности алгоритмов из [9], [10] сильно завышена. На практике эти алгоритмы работают заметно лучше. Алгоритм же из [8], напротив, на практике работает не очень быстро из-за большой константы в O(). Отчасти похожая ситуация и с алгоритмами из [11], [12], они также работают не так быстро, как можно было бы ожидать. Связано это также и с тем, что в стандартных пакетах (использовался MatLab) довольно не эффективно реализована возможность работы со случайностью в огромных размерностях. Алгоритмы из [13], [14] и MCMC работают в точности по приведенным оценкам. Заметно лучше приведенной оценки на практике работает алгоритм из [15], причем речь идет не о константе в
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.