Как Google использует модифицированный PageRank (Personalized PageRank) для персонализации выдачи на основе истории и предпочтений пользователя

Термины и определения

Point-of-View (POV) (Точка зрения)

Контекст, в рамках которого выполняется поиск. Определяет предпочтения пользователя или тематические ограничения.

POV Data (Данные точки зрения)

Информация, определяющая POV. Включает историю просмотров пользователя (browsing history), закладки (bookmarks/favorites), ключевые слова, категории, On-topic URLs и Off-topic URLs.

On-topic URLs (Тематические URL)

Набор URL, служащих положительными примерами для POV. Являются основой для смещения ранжирования.

PageRank™

Алгоритм ранжирования, основанный на анализе ссылок. В патенте используется его модифицированная версия (Personalized PageRank).

Reset Probability (Вероятность сброса / Вектор телепортации)

В алгоритме PageRank — вероятность того, что пользователь совершит случайный переход ("телепортацию") на страницу. Модификация этого вектора является ядром изобретения.

Co-citation (Совместное цитирование)

Ситуация, когда один документ ссылается на два других. Используется как метод расширения набора POV Data.

Ключевые утверждения (Анализ Claims)

Claim 1 (Независимый пункт): Описывает основной метод персонализированного поиска.

1. Получение поискового запроса.
2. Хранение POV data до получения запроса. POV data включает набор URL, связанных с документами, ранее посещенными пользователем.
3. Генерация списка документов на основе запроса.
4. Фильтрация списка документов на основе POV data.
5. Представление отфильтрованного списка.

Ключевой аспект — использование истории посещений пользователя как основы для фильтрации текущего поиска (персонализация).

Claim 13 и 14 (Зависимые от 1): Детализируют технический механизм фильтрации (Personalized PageRank).

1. Установка Reset Probability для URL в наборе POV data (On-topic URLs) в значение $1/k$ (где k — количество URL в наборе). (Claim 13)
2. Установка Reset Probability для всех остальных URL (не входящих в POV data) в ноль (0). (Claim 14)
3. Присвоение оценок документам с использованием метода ранжирования (PageRank), основанного на этих установленных вероятностях.

Это описывает ключевую инновацию: вектор телепортации полностью концентрируется на наборе POV. Авторитет (Rank) в этой модели распространяется исключительно из этого набора, меняя PageRank с глобальной оценки на персонализированную или тематическую.

Claims 4-8 (Зависимые): Описывают методы расширения исходного набора POV data. Включают поиск по ключевым словам, извлеченным из POV data (Claim 5), и добавление URL, которые совместно цитируются (co-cited) с URL из исходного набора (Claim 8).

Claim 34 (Независимый пункт): Расширяет определение источников POV Data, включая адреса, связанные с документом, текущим или недавно просмотренным пользователем, или находящимся в списке избранного (favorites list).

Где и как применяется

Изобретение затрагивает несколько этапов поиска, интегрируя контекст и данные пользователя в процесс ранжирования.

CRAWLING & INDEXING – Сканирование, Индексирование
На этом этапе строится глобальный граф ссылок, необходимый для расчетов PageRank. Также должна существовать инфраструктура для сбора и хранения персональных данных пользователя (POV Data).

QUNDERSTANDING – Понимание Запросов (и Контекста)
Система извлекает POV Data пользователя для определения контекста. В некоторых вариантах (Claim 27) POV Data может использоваться для дополнения (augmentation) исходного запроса (например, добавление уточняющих слов на основе истории пользователя).

RANKING / RERANKING – Ранжирование и Переранжирование
Основное применение патента. После генерации базового набора релевантных документов система применяет фильтрацию. Рассчитывается Personalized PageRank для документов-кандидатов с использованием POV Data пользователя в качестве вектора Reset Probability. Результаты переупорядочиваются на основе этих персонализированных оценок.

Входные данные:

• Поисковый запрос пользователя.
• POV Data пользователя (история, закладки, категории, указанные URL).
• Глобальный граф ссылок.

Выходные данные:

• Список результатов поиска, смещенный в сторону POV и отсортированный с учетом модифицированного PageRank.

На что влияет

• Персонализация поиска: Результаты адаптируются под интересы пользователя на основе его предыдущего поведения. Особенно сильно влияет на неоднозначные запросы (например, "Ягуар").
• Тематический поиск: Позволяет ограничить поиск определенной областью (например, поиском внутри категории каталога или среди набора доверенных сайтов), используя тематические URL как POV Data.

Когда применяется

Алгоритм применяется при выполнении одного из условий:

• Автоматически (Персонализация): Когда у системы есть достаточный объем POV Data для пользователя (история просмотров, закладки) для осмысленного смещения результатов.
• Явный запрос пользователя: Пользователь предоставляет примеры URL или выбирает категорию для ограничения поиска (как показано в патенте на примере интерфейса Advanced Search).

Пошаговый алгоритм

Процесс реализации Personalized PageRank на основе POV Data.

1. Получение запроса и POV Data: Система получает запрос и извлекает набор URL-адресов (K штук), составляющих POV Data пользователя (например, из истории посещений).
2. Генерация первичных результатов: Система выполняет стандартный поиск и формирует список релевантных документов.
3. Инициализация вектора персонализации (Reset Probability):
   • Для каждого URL в наборе POV Data устанавливается Reset Probability равная $1/K$ (или взвешенное значение w(A)).
   • Для всех остальных URL в вебе Reset Probability устанавливается равной 0.
4. Расчет Personalized PageRank: Система рассчитывает оценки PageRank, используя модифицированный вектор Reset Probability. Расчет производится по формуле: