он показывает, почему метод работает независимо от того, какие числа мы выберем, – в соответствии с третьим критерием нашего определения хорошего алгоритма.
Алгоритмы так распространились в наше время, потому что они идеально подходят для компьютеров. Алгоритм приводит нас к ответу задачи, опираясь на схему, лежащую в основе нашего метода ее решения. Компьютеру не нужно думать. Он просто снова и снова следует инструкциям, заложенным в алгоритм, и как будто по волшебству выдает нужный нам ответ.
Один из самых замечательных алгоритмов нашего времени – это алгоритм, ежедневно помогающий миллионам людей путешествовать по интернету. Если бы я оказался на необитаемом острове и мог взять с собой только один алгоритм, я, вероятно, выбрал бы тот, который управляет поисковой системой Google (хотя толку от него было бы мало, так как у меня, скорее всего, не было бы подключения к интернету).
На заре интернета (я говорю о начале 1990-х) существовал каталог, в котором были перечислены все имеющиеся веб-сайты. В 1994 году их было всего 3000. Интернет был настолько мал, что было достаточно легко пролистать этот перечень и найти в нем то, что нужно. С тех пор ситуация сильно изменилась. Когда я начинал писать этот абзац, в интернете был 1 267 084 131 активный вебсайт. Спустя несколько предложений это число возросло до 1 267 085 440 (текущее состояние можно проверить по адресу http://www.internetlivestats.com).
Как же Google решает, какой именно из миллиардов сайтов рекомендовать? Мэри Эшвуд, 86-летняя бабушка из города Уигана[22], всегда тщательно вставляла в свои поисковые запросы вежливые «пожалуйста» и «спасибо», возможно представляя себе, что обращается к группе энергичных практикантов, которые просеивают бесконечные запросы вручную. Когда ее внук Бен открыл ее лэптоп и увидел запрос «пожалуйста переведите римское число mcmxcviii спасибо», он не смог устоять перед искушением рассказать всему миру о заблуждениях своей бабушки через твиттер. Каково же было его удивление, когда кто-то из сотрудников Google ответил на его сообщение:
Дорогая бабушка Бена,
как вы поживаете?
Вы порадовали нас в мире миллиардов поисковых запросов.
Кстати, ответ – 1998.
Спасибо ВАМ
В этом случае бабушка Бена достучалась до человеческой части Google, но компания, разумеется, никак не может лично отвечать на все те запросы, которые поступают в систему Google – по миллиону каждые 15 секунд. Но, если в Google нет волшебных эльфов, прочесывающих интернет, как же поисковой системе удается столь поразительно эффективно находить ответы, нужные пользователю?
Причина всего этого – в мощности и красоте алгоритма, который Ларри Пейдж и Сергей Брин сочинили в стэнфордском студенческом общежитии в 1996 году. Сначала они собирались назвать свой алгоритм Backrub[23], но в конце концов остановились на имени Google, от принятого в математике названия числа, равного единице со ста нулями, – «гугол» (англ. googol). Их целью было ранжировать страницы интернета, что должно было помочь в ориентировании в этой постоянно растущей базе данных, так что название огромного числа казалось вполне уместным.
Не то чтобы не существовало других алгоритмов, которые использовались с той же целью, но их концепции были весьма примитивны. Например, для человека, желающего найти дополнительную информацию по теме «вежливая бабушка и Google», существовавшие алгоритмы отыскали бы все страницы, содержащие эти слова, и расположили их в определенном порядке: те сайты, на которых термины запроса встречаются наибольшее количество раз, попали бы в верхнюю часть списка.
Такой метод вполне работоспособен, но его очень легко обмануть: любой хозяин цветочного магазина может тысячу раз вписать в метаданные своего сайта выражение «Цветы к Дню матери» и моментально окажется на первом месте в результатах поиска всех любящих сыновей и дочерей. Нужна поисковая система, которой хитрым веб-дизайнерам было бы не так просто помыкать. Как же можно получить неискаженную меру важности веб-сайта? И как выяснить, на какие сайты можно не обращать внимания?
У Пейджа и Брина возникла следующая светлая мысль: если на некий веб-сайт ведет много ссылок, значит, те сайты, с которых они ведут, сигнализируют, что его стоит посетить. То есть можно демократизировать меру ценности веб-сайта, позволив другим веб-сайтам голосовать за те сайты, которые они считают важными. Однако и этот алгоритм можно было обмануть. Нужно было всего лишь создать тысячу искусственных сайтов со ссылками на сайт цветочного магазина, и он снова оказывался вверху списка выдачи. Чтобы предотвратить такое положение дел, разработчики алгоритма решили придавать больший вес голосам сайтов, которые сами пользуются уважением.
Но и тогда один вопрос по-прежнему оставался без ответа: как ранжировать сайты по относительной важности? Рассмотрим, например, миниатюрную сеть, изображенную на схеме:
Сначала присвоим всем сайтам равные веса. Представим себе, что каждый веб-сайт – это корзина; положим в каждую корзину по восемь шаров, что означает, что все они имеют одинаковый ранг. После этого веб-сайты должны отдать свои шары тем сайтам, на которые они ссылаются. Если они содержат ссылки не на один, а на несколько сайтов, то они отдают каждому из них равное число шаров. Поскольку веб-сайт А содержит ссылки на оба сайта – В и С, он отдает каждому из них по 4 шара. Однако на сайте В есть ссылка только на сайт С, и все его восемь шаров переходят в корзину веб-сайта С (см. следующую схему).
После первого перераспределения веб-сайт С кажется очень сильным. Но эту процедуру нужно повторять, потому что веб-сайт А усилится благодаря ссылке на него, которая имеется на сайте С, получившем теперь высокий рейтинг. В следующей таблице показаны изменения количества шаров в итерациях этого процесса.
Пока что этот алгоритм не выглядит особенно удачным. По-видимому, он не стабилизируется и работает довольно неэффективно, что нарушает два из наших четырех условий идеального алгоритма. Великая идея Пейджа и Брина заключалась в том, что они поняли: принцип распределения шаров нужно определить исходя из связности сети. Так совпало, что в университетском курсе математики их научили одному хитрому приему, который позволял получать правильное распределение всего за один шаг.
Для его применения прежде всего нужно построить матрицу, отражающую перераспределение шаров между веб-сайтами. В первом столбце матрицы записывается доля шаров, передаваемых от веб-сайта А другим сайтам. В данном случае 0,5 общего числа шаров переходит сайту В, а еще 0,5 – вебсайту С. Тогда матрица перераспределения выглядит следующим образом:
Задача состоит в нахождении собственного вектора этой матрицы с собственным значением, равным 1. Это вектор-столбец, который не изменяется при умножении на саму матрицу[24]. Нахождению таких собственных векторов, или точек устойчивости, мы учим своих студентов в начале их университетского курса. В случае нашей сети оказывается, что матрицу перераспределения стабилизирует следующий вектор-столбец:
Это означает, что если мы разделим шары в пропорции 2:1:2, то полученное распределение весов будет стабильным. При раздаче шаров по тем правилам, которые мы использовали до этого, получается то же распределение по сайтам – 2:1:2.
Собственные векторы матриц – невероятно могущественный инструмент математики и точных наук вообще. Именно они позволяют определить энергетические уровни частиц в квантовой физике. Они могут рассказать об устойчивости вращающейся текучей среды – например, вращающейся звезды – или о скорости размножения вируса. Возможно, они даже послужат ключом к пониманию распределения простых чисел среди чисел вообще.
Рассчитав собственный вектор связности сети, мы видим, что веб-сайтам А и С должен быть присвоен один и тот же ранг. Хотя ссылка на сайт А имеется только на одном сайте (С), тот факт, что веб-сайт С высоко ценится и содержит ссылку только на сайт А, означает, что эта ссылка придает сайту А высокую ценность.
Таков основной принцип алгоритма. В нем есть еще несколько дополнительных тонкостей, которые потребовалось ввести, чтобы алгоритм заработал в полную силу. Например, он должен учитывать аномалии – например, веб-сайты, не содержащие никаких ссылок на другие сайты и становящиеся поэтому тупиковыми складами перераспределяемых шаров. Но в основе алгоритма лежит именно эта простая идея.
Информация об основном устройстве поисковой системы общедоступна, но внутри алгоритма есть параметры, которые держатся в тайне и изменяются со временем, что несколько затрудняет взлом алгоритма. Но замечательнее всего устойчивость алгоритма Google и его неуязвимость к попыткам его обмануть. Веб-сайту очень трудно сделать у себя что-либо, что повысило бы его рейтинг. Его положение могут усилить только другие сайты. Если вы посмотрите на веб-сайты, которым алгоритм ранжирования страниц Google присваивает высокий рейтинг, вы увидите среди них сайты многих крупных новостных агентств и университетов, например Оксфорда и Гарварда. Это связано с тем, что многие сторонние сайты размещают ссылки на данные и мнения, опубликованные на сайтах университетов, потому что многие люди по всему миру высоко оценивают исследования, которыми мы занимаемся.
Интересно отметить одно следствие такого положения вещей: когда владелец веб-сайта, входящего в оксфордскую сеть, размещает у себя ссылку на какой-нибудь сторонний сайт, это приводит к повышению ранга этого стороннего сайта, потому что сайт Оксфорда отдает ему малую часть своего огромного престижа (или запаса шаров). Поэтому меня часто просят разместить на моем сайте на математическом факультете Оксфорда ссылки на сторонние веб-сайты. Такие ссылки повышают ранг этих сайтов и, как знать, даже могут позволить им осуществить заветную мечту всех вебсайтов – появиться на первой странице результатов поиска в Google.