PageRank: линейная алгебра съедает веб

Задача

К 1996 году поисковые машины ранжировали страницы по тексту: чем чаще встречается слово запроса, тем выше страница. Способ ломался тривиально — достаточно было написать нужное слово тысячу раз белым по белому.

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

Идея

Ларри Пейдж и Сергей Брин, сентябрь 2003 годаEhud Kenan · CC BY 2.0

Сергей Брин и Ларри Пейдж, аспиранты Стэнфорда, предложили определение, которое выглядит порочным кругом:

Страница важна, если на неё ссылаются важные страницы.

Круг разрывается тем, что это не определение, а уравнение. Пусть $r_j$ — важность страницы $j$, а $d_j$ — число исходящих с неё ссылок. Тогда

$$r_i=\sum_{j\to i}\frac{r_j}{d_j},$$

то есть каждая страница делит свою важность поровну между теми, на кого ссылается. В матричной записи $r=Mr$: искомый вектор — собственный вектор матрицы ссылок с собственным значением 1.

Посчитаем на трёх страницах. Пусть $A$ ссылается на $B$ и $C$, $B$ — на $C$, $C$ — на $A$. Тогда

$$r_A=r_C,\qquad r_B=\tfrac{r_A}{2},\qquad r_C=\tfrac{r_A}{2}+r_B .$$

Из первых двух: $r_C=\tfrac{r_A}{2}+\tfrac{r_A}{2}=r_A$ — третье уравнение выполняется само. Нормируем суммой в единицу: $r_A+\tfrac{r_A}{2}+r_A=1$, откуда

$$r_A=0{,}4,\qquad r_B=0{,}2,\qquad r_C=0{,}4 .$$

Страница $B$, на которую ссылается только одна страница, и то поделив внимание пополам, оказалась вдвое менее важной, чем остальные.

Случайный сёрфер

У той же формулы есть вероятностное чтение, и оно объясняет, почему всё работает.

Представим человека, который ходит по вебу наугад: на каждой странице выбирает случайную ссылку и переходит по ней. Это цепь Маркова — та самая конструкция, которую Андрей Андреевич Марков в 1913 году придумал, пересчитывая гласные и согласные в «Евгении Онегине», чтобы показать, что закон больших чисел работает и для зависимых величин.

Важность страницы — это доля времени, которую случайный сёрфер на ней проводит, то есть стационарное распределение цепи.

Но у настоящего веба две беды. Есть страницы без исходящих ссылок — сёрфер на них застревает. И есть замкнутые группы страниц, из которых нет выхода наружу, — они собирают на себя всю важность.

Лечение простое и с точки зрения математики решающее: демпфирование. С вероятностью $d=0{,}85$ сёрфер идёт по ссылке, а с вероятностью $0{,}15$ прыгает на случайную страницу веба:

$$r=\frac{1-d}{N}\,\mathbf{1}+d\,Mr .$$

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

Перрон и Фробениус

Именно здесь работает теорема, которой на тот момент было девяносто лет.

Теорема Перрона — Фробениуса. У матрицы с положительными элементами наибольшее по модулю собственное значение вещественно, положительно, просто, и соответствующий ему собственный вектор можно выбрать с положительными координатами.

Оскар Перрон доказал это в 1907 году для положительных матриц, Фробениус в 1912-м обобщил на неотрицательные неразложимые. Оба занимались чистой алгеброй и ни о каких приложениях не думали.

Демпфирование делает матрицу положительной — значит, стационарное распределение существует, единственно и положительно. Ранжирование определено однозначно.

Как это считают

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

$$r^{(k+1)}=\frac{1-d}{N}\mathbf{1}+d\,M r^{(k)} .$$

Важность страниц найдена степенным методом: показаны первые шаги и пределMathLocus · построено для этого сайта

Скорость сходимости определяется отношением второго собственного значения к первому, и здесь есть красивый факт: для матрицы PageRank второе собственное значение в точности равно коэффициенту демпфирования $d$ (это доказали Хавеливала и Камвар в 2003 году). Значит, каждая итерация уменьшает ошибку в $1/0{,}85\approx1{,}18$ раза, и для приличной точности хватает 50–100 умножений матрицы на вектор.

Отсюда, кстати, видно, почему $d$ выбрано равным 0,85, а не 0,99: чем ближе $d$ к единице, тем ранжирование «честнее» — тем меньше искусственных прыжков, — но тем медленнее сходимость. Число 0,85 — компромисс, а не константа природы.

Рядом

Почти одновременно и независимо Джон Клейнберг в IBM Almaden предложил HITS: каждой странице приписываются две величины — «авторитетность» (на неё ссылаются) и «посредничество» (она ссылается на авторитетные). Это тоже собственные векторы, только двух связанных матриц. Клейнберг получил за эти работы премию Неванлинны в 2006 году.

Разница оказалась инженерной: PageRank считается один раз для всего веба и не зависит от запроса, HITS — для подграфа, найденного по запросу. Первое масштабируется, второе нет.

Замыкание круга

Здесь наша линия кончается, и стоит оглянуться.

Она началась с зарубок на кости: человек ставит метки, чтобы сосчитать предметы. Она кончается умножением матрицы порядка $10^{11}$ на вектор, и это по-прежнему счёт — только объекты другие.

Главный её герой — перебор, и оба его лица видны на одном экране. Поисковая выдача считается быстро потому, что задача оказалась не переборной: важность — это собственный вектор, а не наилучший из вариантов. Замочек рядом с адресом страницы держится ровно на обратном: на предположении, что перебор устранить нельзя. Один вопрос, два ответа — и на них стоит вся ежедневная работа сети.

Что происходит в линии сейчас, уже за пределами наших точек:

Экспандеры. Помните, что Эрдёш умел доказать существование, не умея предъявить? В 1973 году Марк Пинскер показал, что случайный граф почти наверняка является экспандером — графом, который при малом числе рёбер связан так хорошо, как это вообще возможно; и в том же 1973-м Григорий Маргулис в Москве построил явный пример. Разрыв между существованием и построением был закрыт в одной конкретной задаче — и именно из этих явных конструкций выросли современные коды, генераторы псевдослучайности и дерандомизация.
Теорема PCP (1992). Всякое доказательство можно переписать так, что для проверки достаточно взглянуть на константное число случайно выбранных битов. Прямое продолжение вопроса Гёделя и Карпа — и из неё следует, что для многих задач трудно не только найти точный ответ, но и приблизиться к нему.
Полиномиальный метод. В 2008–2010 годах несколько задач, стоявших десятилетиями (проблема Какейи над конечными полями, задача Эрдёша о различных расстояниях 1946 года), пали от одного приёма: построить многочлен, обращающийся в нуль на конфигурации, и воспользоваться тем, что у многочлена мало корней. Комбинаторика взяла инструмент у алгебры.
Возвращённый долг. В 2004 году Бен Грин и Теренс Тао доказали, что в простых числах есть арифметические прогрессии любой длины. Средства — комбинаторные: теорема Семереди и её эргодические и гиперграфовые варианты. Дискретная математика, три века бравшая у теории чисел, вернула ей одну из красивейших теорем века.

И последнее. Во вводной этой линии сказано, что дискретная математика моложе всех и старше всех сразу. Двадцать тысяч лет назад человек в Ишанго нарезал на кости группы по одиннадцать, тринадцать, семнадцать и девятнадцать. Мы до сих пор не знаем, что он имел в виду, — но точно знаем, чем занимался: он считал конечные предметы и записывал результат. Ровно этим занята и последняя точка линии, и разница только в том, что предметов стало $10^{11}$, а записывает их машина.

Задача. Найдите PageRank трёх страниц из примера выше с демпфированием $d=0{,}85$.
(Ответ: система $a=0{,}05+0{,}85c$, $b=0{,}05+0{,}425a$, $c=0{,}05+0{,}85\left(\tfrac{a}{2}+b\right)$ при $a+b+c=1$. Из последнего $c=0{,}95-1{,}425a$; подставляя в первое, $a=0{,}05+0{,}85(0{,}95-1{,}425a)$, откуда $2{,}21125\,a=0{,}8575$ и $a\approx0{,}388$. Дальше $b\approx0{,}215$, $c\approx0{,}397$. Заметьте, что $C$ обошла $A$: без демпфирования они были равны, а случайные прыжки достаются всем поровну и потому чуть выравнивают картину в пользу той страницы, у которой входящих ссылок больше.)

Соседние точки: Фробениус (1896) → Марков (1913) → PageRank (1998) → скетчи.