Алгоритм Google PageRank, который является центром поиска Google, основан на цепях Маркова, вот его объяснение (для базовой версии).
С 1 миллиардом сайтов в Интернете невозможно проанализировать их содержание. Однако Интернет — это не набор самостоятельных текстов, а огромный гипертекст: страницы цитируют друг друга. Рассматривая сеть как график и, принимая во внимание связи между страницами, мы можем делать интересные вещи. Первыми, кто выступил с этой точкой зрения, были Ларри Пейдж и Сергей Брин, основатели Google, с их алгоритм PageRank.
С момента своего создания в 1998 году Google доминирует на рынке поисковых систем в Интернете. 17 лет спустя их методы уже сильно развились, полученные результаты поиск становится все более и более актуальным, но основная идея по-прежнему основана на алгоритме ранжирования PageRank. В этой статье мы подробно рассмотрим этот алгоритм и связь с цепь маркова.
PageRank использует функцию, которая присваивает значение каждой странице в Интернете. Чем выше значение, тем важнее страница.
PageRank — это алгоритм, который не зависит от запроса и контента. Независимость от запросов означает, что ранжирование сайтов выполняется в автономном режиме. Действительно, каждые 30 дней Google загружает, индексирует и ранжирует все сайты. Поэтому ранжирование результатов не зависит от запроса. Независимость содержания совершенно ясна, поскольку она обсуждается в части Введение : алгоритм PageRank использует не контент, а ссылки на страницы ранжирования.
Большинство из них ранжируют результаты в зависимости от того, как часто искомое слово используется на каждом сайте. Это быстро выявило проблемы: если сайт хочет привлечь посетителей, вам просто нужно спамить ключевые слова, и поисковая система поверит, что это действительно релевантный результат.
Методы обмана поисковых систем, подобные этому, называются «спамом терминов». Чтобы избежать мошенничества, Ларри Пейдж и Сергей Брин создали PageRank с двумя новшествами:
— PageRank имитирует случайную прогулку посетителя, который случайным образом выбирает ссылку на текущей странице для перехода на следующую страницу. Этот процесс повторяется несколько раз, и авторы считают, что страницы, на которых пользователь проводит больше времени, более важны, чем те, которые он посещает редко.
— Важность страницы зависит от важности страниц, которые
привести к этому. Таким образом, даже если кто-то создал 1000 поддельных страниц, содержащих ссылки на главную страницу, PageRank этой главной страницы не сильно улучшится, потому что эти 1000 поддельных страниц не являются «важными».
В настоящее время Пейдж и Брин еще не обращались к термину «марков» в своей статье, но можно легко заметить, что моделированием случайного блуждания является цепь Маркова. Еще более интересно то, что стационарная вероятность цепи Маркова дает нам представление о доле времени, которую Xn проведет в каждом состоянии в долгосрочной перспективе.
Тогда, если цепочка сходится к своей стационарной вероятности, ее предельная вероятность действительно является искомым PageRank. Другими словами, алгоритм PageRank вычисляет рейтинг каждого сайта, находя уникальную стационарную вероятность цепи Маркова.
Но жизнь не так проста. Мы не можем гарантировать, что наша цепь Маркова сходится или существует единственная стационарная вероятность. Это часто имеет место для интернет-модели. Например, очень маловероятно, что сайты, посвященные математике, имеют ссылки на сайты, посвященные спорту (да, потому что гики не занимаются спортом…), поэтому наша цепь Маркова имеет 2 конечных класса, следовательно, 2 стационарных вероятности.
Чтобы решить эту проблему, Пейдж и Брин пытаются построить цепь Маркова. эргодический, что обеспечит существование единственной стационарной вероятности, которая и станет вектором PageRank.
Пример
Пусть Xn будет страницей, которую пользователь посещает на шаге n. Xn может быть смоделирован цепью Маркова, потому что выбор пользователя зависит только от текущей страницы.
Предположим, что наш «Интернет» состоит из 7 страниц, которые представлены в виде 7 узлов. Края представляют собой связи между страницами. Находясь на странице, посетитель случайным образом выбирает ссылку для перехода на другую страницу, поэтому вероятности перехода с одной страницы на другие равны.
Матрица перехода:
Заметим, что имеется 2 поглощающих состояния: 4 и 7. Цепь не эргодична, имеет 2 стационарные вероятности и поэтому не сходится к одной вероятности.
Чтобы избежать этой ситуации, Пейдж и Брин сделали предположение:
Как только посетитель попадает на «конечную» страницу (т. е. без ссылки для выхода), он переходит к адресной строке и вводит адрес случайного сайта.
В терминах матрицы переходов заменим столбец поглощающего состояния вектором:
Таким образом, матрица перехода T принимает вид:
С этим изменением T неприводим и апериодичен, следовательно, эргодичен. Однако это не всегда так, на примере сайтов Math и Sport мы можем получить матрицу перехода T:
Он не имеет поглощающих состояний, но не является неприводимым и, следовательно, не эргодичным. Нам нужно сделать еще одно предположение:
Предположим, что посетитель находится на странице, мы говорим, что с вероятностью p он выберет одну из ссылок на этой странице, а с вероятностью 1 − p он перейдет в адресную строку и наберет адрес случайного веб-сайта.
Таким образом, новая матрица перехода:
G = рТ + (р - 1)К
с K матрицей, каждый столбец которой является вектором:
Матрица G называется матрицей Google. G эргодична. Google часто использует p = 0,85.
Применяя к нашему примеру, получаем:
Решая Gπ = π, находим:
Таким образом, порядок ранжирования в нашем примере: 3,2,6,5,1,4,7. Таким образом, если искомое слово появляется на страницах 1,2,5, порядок результатов будет 2,5,1.
Сломать систему
Если значение PageRank (которое также является стационарной вероятностью) страницы равно p, время возврата этой страницы равно 1/p. Таким образом, мы можем эффективно увеличить значение PageRank за счет сокращения времени возврата, что возможно, если мы создадим очень короткие циклы или, в идеале, циклы.
Конкретно, для страницы x мы удаляем все ссылки на ней (то есть без выхода), мы создаем другую страницу, y, только с двумя ребрами x → y и y → x. Значение PageRank страницы x увеличивается, потому что каждый раз, когда посетитель попадает на эту страницу, он не может с нее выйти. Как мы обсуждали в части 3 (на примере математики и спорта), алгоритм PageRank может избежать эффекта этой стратегии, увеличив значение p, вероятность того, что посетитель перейдет на адрес бара d и наберет адрес случайный сайт.
Другая стратегия состоит в том, чтобы создать множество страниц, у которых есть только одно ребро на странице x. Этот метод использует вероятность повторного начала обхода. Если у нас очень большое количество фальшивых страниц, очень вероятно, что после повторного запуска мы наткнемся на страницу x, и, следовательно, значение PageRank увеличится. Чтобы избежать этой ситуации, необходимо уменьшить значение p.
Благодаря этим двум ситуациям мы ясно видим, что выбор p чрезвычайно важен для предотвращения спама. Если p слишком велико, спамерам просто необходимо создать миллионы поддельных страниц, ведущих на их главные страницы. С другой стороны, при очень маленьком p они могут создавать петли своими страницами.
То, что мы обсудили, является лишь основами поисковой системы Google. Методы уже сильно развились, чтобы давать наиболее релевантные результаты. Вопрос вычислений тоже очень интересен. Поскольку истинная матрица Google имеет размер 8 миллиардов x 8 миллиардов, метод исключения Гаусса непрактичен. Для нахождения собственных векторов используются более мощные алгоритмы, в частности степенной метод.
RU 
FR 
EN 
ES