Как Google интерпретирует клики и поведение пользователей как «парные сравнения» для обучения моделей ранжирования и персонализации

Описание

Какую задачу решает

Патент решает фундаментальную проблему в машинном обучении и поиске (Information Retrieval): вычислительную сложность обучения статистических моделей предпочтений (в частности, Mallows models), когда данные пользователей представлены в виде произвольных парных сравнений (arbitrary pairwise comparisons), например, «А предпочтительнее Б». Традиционные методы требовали полных рейтингов, которые трудно получить. Этот патент критически важен для интерпретации неявной обратной связи, такой как клики в веб-поиске, где выбор одного результата над другим является парным сравнением.

Что запатентовано

Запатентована система и вычислительный фреймворк для изучения моделей предпочтений (Mallows models и их смесей) на основе данных парных сравнений. Ядром изобретения являются новые алгоритмы сэмплирования — Generalized Repeated Insertion Model (GRIM) и его аппроксимации (AMP, MMP). Эти методы делают обучение вычислительно возможным, поскольку точное вычисление является неразрешимым (#P-hard).

Как это работает

Система предполагает, что существует базовый «эталонный рейтинг» (Reference Ranking), и индивидуальные предпочтения являются случайными отклонениями от него. Для обучения параметров модели на основе частичных данных (кликов) используется алгоритм Expectation-Maximization (EM). Ключевая сложность заключается в E-шаге, который требует сэмплирования полных рейтингов, соответствующих наблюдаемым частичным данным. Патент вводит GRIM и AMP для эффективного выполнения этого сэмплирования, позволяя системе оценить либо единый объективный рейтинг (релевантность), либо несколько кластеров предпочтений (персонализация).

Актуальность для SEO

Высокая. Интерпретация поведения пользователей (клики, выборы) остается центральной задачей для современных поисковых систем (Learning-to-Rank) и рекомендательных сервисов. Этот патент описывает базовую статистическую машинерию, необходимую для преобразования этих зашумленных, частичных сигналов в надежные модели релевантности и предпочтений в большом масштабе.

Важность для SEO

Патент имеет высокое значение (8.5/10) для понимания того, как Google интерпретирует поведенческие факторы. Он описывает не конкретный сигнал ранжирования, а статистический инструментарий, который позволяет системам изучать «объективную релевантность» или «персональные предпочтения» на основе зашумленной обратной связи от пользователей (кликов). Это подчеркивает критическую важность удовлетворения интента пользователя для генерации положительных сигналов вовлеченности.

Детальный разбор

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

Mallows Model (Модель Маллоуза)

Статистическая модель распределения вероятностей над пространством ранжирований. Параметризуется эталонным рейтингом (σ) и параметром дисперсии (φ). Вероятность конкретного рейтинга уменьшается по мере увеличения его расстояния от эталонного.

Pairwise Comparisons (Парные сравнения)

Частичная информация о предпочтениях в форме «Элемент А предпочтительнее элемента Б». Являются основными строительными блоками для большинства данных о предпочтениях, включая клики в поиске.

Reference Ranking (σ, Эталонный рейтинг)

Центральный или модальный рейтинг в модели Маллоуза. Представляет собой «среднее предпочтение» популяции или «объективную релевантность».

Dispersion Parameter (φ, Параметр дисперсии)

Параметр в модели Маллоуза, контролирующий вариативность предпочтений вокруг эталонного рейтинга. Низкое значение означает сильную концентрацию вокруг σ.

Mixture Model (Смешанная модель)

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

Kendall-tau distance (Расстояние Кендалла-тау)

Метрика расстояния между двумя рейтингами, равная количеству пар элементов, порядок которых не совпадает в этих двух рейтингах.

GRIM (Generalized Repeated Insertion Model, Обобщенная модель повторной вставки)

Ключевое нововведение патента. Метод, позволяющий сэмплировать из произвольного распределения рейтингов, включая модели Маллоуза, обусловленные наблюдаемыми парными сравнениями.

AMP (Approximate Mallows Posterior)

Эффективный алгоритм аппроксимации для сэмплирования из апостериорного распределения Маллоуза, используемый, когда точное вычисление GRIM невозможно.

MMP (Metropolis Mallows Posterior)

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

EM Algorithm (Expectation-Maximization)

Итеративный алгоритм машинного обучения для нахождения оценок максимального правдоподобия параметров статистических моделей при наличии скрытых переменных.

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

Патент является высокотехничным и фокусируется на вычислительных методах машинного обучения.

Claim 1 (Независимый пункт): Описывает общий метод идентификации и ранжирования предпочтений.

1. Получение эталонного ранжирования на основе информации о предпочтениях, включая частичную информацию в виде набора pairwise comparisons (парных сравнений) выбранных и невыбранных элементов.
2. Анализ парных сравнений, включающий итеративное переупорядочивание эталонных ранжирований на основе различных векторов вставки (insertion vectors) для генерации распределения. (Это описание процесса, реализуемого через GRIM).
3. Использование этого распределения для обучения статистических моделей.
4. Генерация рекомендации (или ранжирования) на основе этих моделей.

Ядром изобретения является способность системы обучаться на основе неполных парных данных, что ранее было вычислительно сложной задачей.

Claim 7 (Зависимый от 1): Уточняет, что статистическая модель включает Mallows model.

Claim 8 (Зависимый от 7): Уточняет, что модель Маллоуза определяется средним рейтингом (mean ranking) и параметром дисперсии (dispersion parameter).

Это указывает на конкретный статистический подход: система предполагает наличие центрального «правильного» ранжирования и рассматривает действия пользователей как зашумленные отклонения от него.

Claim 3 (Зависимый от 1): Упоминает использование смесей моделей (mixtures of statistical models), что позволяет формировать кластеры пользователей с разными предпочтениями (персонализация).

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

Это изобретение относится к инфраструктуре машинного обучения, используемой для анализа данных и обучения моделей, которые затем применяются в ранжировании.

CRAWLING / INDEXING (Сбор данных)
На этом этапе система собирает данные о взаимодействии пользователей (клики, выбор продуктов, рейтинги). Эти данные преобразуются в pairwise comparisons.

RANKING (Обучение моделей – Офлайн)
Основное применение патента. Алгоритмы (EM с использованием GRIM/AMP) выполняются в офлайн-режиме для анализа исторических данных о взаимодействии. Это может быть использовано для:

• Обучения объективной релевантности: Изучение единой модели Маллоуза, где Reference Ranking представляет собой идеальный порядок результатов поиска для запроса.
• Обучения предпочтений пользователей: Изучение смеси моделей (mixture models) для кластеризации пользователей по типам предпочтений (персонализация).

RANKING / RERANKING (Применение моделей – Онлайн)
Изученные модели (параметры σ и φ) используются алгоритмами ранжирования для оценки документов на основе изученной релевантности (RANKING) или для адаптации выдачи к предпочтениям пользователя на этапе RERANKING.

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

• Наборы парных сравнений (V), полученные из поведения пользователей.

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

• Оптимизированные параметры модели (эталонные рейтинги σ, параметры дисперсии φ, коэффициенты смешивания π).

На что влияет

• Интерпретация поведенческих сигналов: Основное влияние заключается в том, как система интерпретирует клики и другие действия пользователей. Они рассматриваются не как прямые голоса, а как статистические данные для сложных моделей (Learning-to-Rank).
• Специфические запросы и ниши: Влияет на области, где предпочтения пользователей разнообразны (e-commerce, рекомендации контента, неоднозначные запросы), или где объективная истина должна быть выведена из зашумленных сигналов (общая релевантность веб-поиска).

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

• Временные рамки: Алгоритмы обучения (EM) применяются в офлайн-режиме во время фазы обучения (training phase) моделей ранжирования. Это периодический процесс переобучения.
• Условия: Применяется, когда необходимо изучить распределение предпочтений или объективную релевантность на основе большого объема частичных (парных) данных.

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

Описан процесс обучения смеси моделей Маллоуза с использованием Monte Carlo EM (Expectation-Maximization).

1. Инициализация: Инициализация параметров смеси моделей Маллоуза: коэффициентов смешивания (π), эталонных рейтингов (σ) и параметров дисперсии (φ) для K компонентов.
2. E-Step (Expectation / Оценка ожиданий): Оценка апостериорного распределения скрытых переменных (полных рейтингов пользователей и их принадлежности к компонентам). Поскольку точное вычисление невозможно (#P-hard), используется сэмплирование:
   • Для каждого пользователя генерируются образцы (samples) полных рейтингов, которые согласуются с его наблюдаемыми частичными данными.
   • Для этого используются эффективные аппроксимации на базе GRIM (например, AMP или MMP).
3. M-Step (Maximization / Максимизация): Обновление параметров модели (π, σ, φ) для максимизации ожидаемого логарифмического правдоподобия (Log Likelihood), рассчитанного на основе образцов из E-шага.
   • Оптимизация σ: Поиск нового эталонного рейтинга для каждого компонента (задача Kemeny consensus, часто решается приближенно).
   • Оптимизация φ: Настройка параметров дисперсии (например, с помощью градиентного подъема).
4. Итерация и Сходимость: Повторение E-шага и M-шага до тех пор, пока параметры модели не стабилизируются.

Какие данные и как использует

Данные на входе

Патент фокусируется исключительно на обработке одного типа данных:

• Поведенческие факторы: Основные входные данные — это pairwise comparisons. Патент указывает, что эти данные могут быть получены неявно из действий пользователя, таких как выбор продукта, взаимодействие в социальных сетях или клики по веб-ссылкам (например, по разным результатам поиска или рекламе). В контексте поиска клик на один результат при пропуске другого интерпретируется как парное сравнение.

Какие метрики используются и как они считаются

• Kendall-tau distance (d(r, σ)): Ключевая метрика для определения вероятности рейтинга в модели Маллоуза. Измеряет количество парных разногласий между рейтингом r и эталонным рейтингом σ.
• Dispersion Parameter (φ): Параметр модели, который оценивается в процессе обучения.
• Log Likelihood (Логарифмическое правдоподобие): Метрика, используемая для оценки того, насколько хорошо модель соответствует наблюдаемым данным. Ее максимизация является целью алгоритма EM.

Методы вычислений и анализа:

• Алгоритмы машинного обучения: Monte Carlo Expectation-Maximization (MCEM).
• Статистические методы: Сэмплирование Гиббса (Gibbs Sampling), Алгоритм Метрополиса (Metropolis Algorithm), Importance Sampling.
• Методы оптимизации: Градиентный подъем (Gradient Ascent), Локальная Кеменизация (Local Kemenization).

Выводы

1. Фундамент для интерпретации поведенческих сигналов: Патент предоставляет надежную статистическую основу для интерпретации кликов как сигналов предпочтений. Клики рассматриваются не как абсолютные голоса, а как зашумленные pairwise comparisons.
2. Сложность моделирования предпочтений (LTR): Патент демонстрирует, что Google использует сложные статистические модели (смеси Маллоуза) и продвинутые вычислительные методы (Monte Carlo EM, GRIM, AMP) для анализа поведения. Это не просто подсчет CTR; это основа для систем Learning-to-Rank.
3. Поддержка как объективного, так и персонализированного ранжирования: Описанные методы могут использоваться как для изучения «объективного ранжирования» (поиск общей релевантности), так и для сегментации пользователей и персонализации (изучение различных предпочтений разных групп через Mixture Models).
4. Устойчивость к шуму и манипуляциям: Модель Маллоуза по своей природе предполагает, что наблюдаемые данные являются зашумленными отклонениями от эталона. Система стремится найти центральную тенденцию (истинную релевантность) и устойчива к случайным кликам или простым манипуляциям.
5. Вычислительная эффективность на неполных данных: Ключевая ценность изобретения в том, что оно делает анализ частичных данных (типичных для веба) вычислительно эффективным с помощью GRIM и его аппроксимаций.

Практика

Best practices (это мы делаем)

• Фокус на комплексном удовлетворении интента: Поскольку входными данными для этих моделей являются поведенческие сигналы (pairwise comparisons), ключевая стратегия — максимизировать вероятность того, что пользователь выберет ваш результат и будет им удовлетворен («последний клик»). Это генерирует положительные парные сравнения в вашу пользу.
• Оптимизация сниппетов для релевантных кликов: Сниппеты должны точно отражать содержание страницы, чтобы привлекать пользователей, ищущих именно эту информацию. Это гарантирует, что полученный клик будет сигналом истинного предпочтения, а не шумом.
• Создание объективно лучшего контента: Если система использует эти методы для изучения «объективного ранжирования», цель SEO — соответствовать этому эталону. Это достигается за счет создания наиболее полного, авторитетного и полезного контента по теме.
• Анализ разнообразия интентов: Понимайте, что по одному запросу могут существовать разные кластеры пользователей (Mixture Models). Убедитесь, что ваш контент четко нацелен на один из основных кластеров или учитывает разнообразие предпочтений.

Worst practices (это делать не надо)

• Кликбейт и обман ожиданий: Привлечение кликов с помощью вводящих в заблуждение заголовков, за которым следует быстрый возврат в выдачу (pogo-sticking). Это генерирует отрицательные сигналы предпочтений (пользователь предпочел другие результаты вашему после его изучения).
• Манипуляции поведенческими факторами (накрутки): Попытки искусственно симулировать клики. Модели Маллоуза предназначены для поиска центральной тенденции (Reference Ranking) среди шума. Систематические манипуляции могут быть идентифицированы как выбросы или шум относительно истинных предпочтений популяции.

Стратегическое значение

Патент подтверждает стратегический сдвиг к динамическим, ориентированным на пользователя метрикам. Поведенческие сигналы — это не просто «бонус»; они являются обучающими данными для основных моделей Learning-to-Rank. Google интерпретирует поведение вероятностно и на очень гранулярном уровне. Стратегия SEO должна быть направлена на то, чтобы контент генерировал сигналы, которые убеждают статистическую модель в его высокой объективной релевантности и полезности.

Практические примеры

Сценарий: Интерпретация кликов для неоднозначного запроса и персонализация

1. Запрос: Пользователь вводит неоднозначный запрос (например, «Ягуар»).
2. Сбор данных: Google собирает данные о кликах (pairwise preferences). Некоторые пользователи кликают на результаты об автомобилях, другие — о животных.
3. Обучение модели (Офлайн): Система применяет EM и GRIM/AMP для анализа этих данных. Она идентифицирует смесь моделей Маллоуза (Mixture Model) с двумя основными кластерами (Автолюбители и Любители природы).
4. Результат обучения: Для каждого кластера определяется свой Reference Ranking (например, у автолюбителей сайты про машины выше).
5. Применение (Ранжирование/Переранжирование): Если новый пользователь кликает на результат об автомобиле (создавая pairwise preference), система классифицирует его как принадлежащего к кластеру Автолюбителей и переранжирует (RERANKING) последующие результаты или будущие запросы в соответствии с Reference Ranking этого кластера.

Вопросы и ответы