Удовольствие от X. Увлекательная экскурсия в мир математики от одного из лучших преподавателей в мире

Алгоритмы на основе анализа ссылок решили проблему, проникнув в суть парадокса, подобного коанам дзен: в результате поиска в интернете должны были отображаться лучшие страницы. А что же, кузнечик[132], делает страницу лучшей? Когда на нее ссылаются другие не менее хорошие страницы.

Звучит подобно рассуждениям про замкнутый круг.[133] Так и есть. Именно поэтому все настолько сложно. Ухватившись за эту идею и превратив ее в преимущество, алгоритм анализа ссылок дает решение поиска в сети в стиле джиу-джитсу.

Этот подход построен на идеях, взятых из линейной алгебры[134], изучения векторов и матриц. Если вы хотите выявить закономерности в огромном скоплении данных или выполнить гигантские вычисления с миллионами переменных, линейная алгебра предоставит для этого все необходимые инструменты[135]. С ее помощью был построен фундамент для алгоритма PageRank[136], положенного в основу Google. Она также помогает ученым классифицировать человеческие лица[137], провести анализ голосования в Верховном суде[138], а также выиграть приз Netflix[139] (вручаемый команде, сумевшей улучшить более чем на 10 % систему Netflix, на основе которой составляются рекомендации для просмотра лучших фильмов).

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

Стрелки указывают, что страница X содержит ссылку на страницу Y, однако Y не отвечает ей взаимностью. Наоборот, Y ссылается на Z. Тем временем X и Z ссылаются друг на друга, сцепившись между собой цифровыми лапками.

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

Подход, придуманный Ларри Пейджем и Сергеем Брином, аспирантами университета и основателями Google, состоял в том, чтобы позволить страницам самим ранжироваться в определенном порядке, голосуя ссылками. В приведенном выше примере страницы X и Y ссылаются на Z, благодаря чему Z становится единственной страницей с двумя входящими ссылками. Следовательно, она и будет самой популярной страницей в данной среде. Однако если ссылки поступают со страниц сомнительного качества, они станут работать против себя. Популярность сама по себе ничего не значит. Главное — иметь ссылки с хороших страниц.

И здесь мы снова оказывается в замкнутом круге. Страница считается хорошей, если на нее ссылаются хорошие страницы, но кто изначально решает, какие из них хорошие?

Это решает сеть. Вот как все происходит. (Далее я буду пропускать некоторые подробности, изложенные в примечании[140].)

Алгоритм Google назначает для каждой страницы дробное число от 0 до 1. Это численное значение называется PageRank и измеряет «важность» страницы по отношению к другим, высчитывая относительное количество времени, которое гипотетический пользователь потратит на ее посещение. Хотя пользователь может выбирать более чем из одной исходящей ссылки, он выбирает ее случайно с равной вероятностью. При таком подходе страницы считаются более авторитетными, если они чаще посещаются.

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

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

Изначально алгоритм задает равные доли, что позволяет каждой странице получить одинаковое количество PageRank. В нашем примере три страницы, и каждая из них начинает движение по алгоритму со счетом 1/3.

Начальные значения PageRank