Как Google использует сущности, онтологии и векторные представления для кластеризации и организации поисковой выдачи

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

Balance Score (Оценка баланса)

Метрика, измеряющая, насколько равномерно распределены популярные результаты (например, по объему конверсий) между кластерами. Рассчитывается как энтропия распределения конверсий. Высокий балл означает равномерное распределение.

Cluster Score (Оценка кластера)

Итоговая метрика качества кластера. Рассчитывается как регрессия (взвешенная комбинация) из пяти метрик: Coverage, Balance, Overlap, Silhouette Score и Silhouette Ratio.

Coverage Score (Оценка покрытия)

Метрика, измеряющая процент топовых или популярных результатов поиска, которые покрываются кластерами.

Embedding Space (Векторное пространство / Пространство представлений)

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

Embedding Similarity (Векторная близость)

Мера близости между двумя объектами в Embedding Space, часто рассчитываемая как косинусное сходство (cosine similarity).

Entity (Сущность)

Объект из Базы Знаний (Knowledge Base), представляющий человека, место, предмет, идею, тему и т.д.

Entity Ontology (Онтология сущностей)

Набор отношений, связывающих сущности как синонимы (synonyms) или как родитель-потомок (parent-child/hypernyms). Также включает отношения братьев/сестер (co-hypernyms).

First-level Clusters (Первичные кластеры)

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

Hierarchical Clustering (Иерархическая кластеризация)

Метод кластерного анализа (например, агломеративный), который строит иерархию кластеров, часто основанный на дистанции (distance-based).

Overlap Score (Оценка пересечения)

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

Silhouette Ratio (Коэффициент силуэта)

Метрика качества всего набора кластеров. Представляет собой процент кластеров, у которых Silhouette Score выше определенного порога.

Silhouette Score (Оценка силуэта)

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

Trained Embedding Model (Обученная модель векторных представлений)

Модель машинного обучения (например, WALS), используемая для генерации Embedding Space на основе привязок результатов поиска к сущностям.

Two-Step Clustering (Двухэтапная кластеризация)

Метод, где на первом этапе кластеры объединяются строго на основе онтологии, а на втором этапе применяется стандартная иерархическая кластеризация.

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

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

1. Определение результатов, релевантных запросу.
2. Генерация первичных кластеров (first-level clusters) на основе привязки результатов к сущностям.
3. Расчет Cluster Score для каждого первичного кластера. Ключевое требование: эта оценка основана на Silhouette Score и Silhouette Ratio.
4. Объединение первичных кластеров на основе Entity Ontology И рассчитанных оценок. Условие объединения: оценка объединенного кластера должна быть лучше, чем оценки исходных кластеров.
5. Применение иерархической кластеризации (hierarchical clustering) к объединенным кластерам для получения финальных кластеров, максимизируя их оценки качества.
6. Предоставление результатов поиска, организованных по финальным кластерам.

Claim 2 и 3 (Зависимые от 1): Детализируют стратегию объединения на основе схожести.

Система предпочитает объединять онтологически связанные кластеры, которые имеют наивысшую схожесть (определяемую через Embedding Similarity – Claim 3), при условии, что качество (Cluster Score) улучшается.

Claim 4 (Зависимый от 1): Детализирует альтернативную стратегию объединения на основе размера.

Система предпочитает объединять онтологически связанные кластеры, начиная с самых маленьких, при условии, что качество (Cluster Score) улучшается.

Claim 6 (Зависимый от 1): Определяет состав Cluster Score.

Оценка кластера рассчитывается как регрессия пяти метрик: Silhouette Score, Silhouette Ratio, Coverage Score, Balance Score и Overlap Score.

Claim 9 (Независимый пункт): Фокусируется на деталях механизма оценки качества кластеров.

Этот пункт защищает сам метод расчета Cluster Score как регрессии пяти метрик. Он определяет Silhouette Ratio как долю кластеров с Silhouette Score выше порога. Далее этот скоринг используется для итеративного улучшения кластеров, гарантируя, что новые кластеры имеют лучшую оценку.

Claim 14 (Независимый пункт): Описывает метод, комбинирующий онтологию и векторные представления для кластеризации.

Этот пункт акцентирует внимание на использовании как Entity Ontology, так и Embedding Space (сгенерированного из Embedding Model) для объединения кластеров, при этом также требуя использования Silhouette Score и Silhouette Ratio для валидации качества объединения.

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

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

INDEXING – Индексирование и извлечение признаков

• Привязка к сущностям: Система привязывает результаты поиска (search items) к сущностям в Knowledge Base на основе анализа контента или метаданных.
• Генерация онтологии: Система (Entity Ontology Engine) генерирует или обновляет Entity Ontology (офлайн-процесс).
• Обучение модели представлений: Система обучает Trained Embedding Model (например, WALS), создавая Embedding Space для сущностей и результатов поиска.

RANKING – Ранжирование

• Определяются релевантные результаты и рассчитываются их базовые оценки популярности/релевантности (используемые позже в метрике Coverage).

METASEARCH – Метапоиск и Смешивание / RERANKING – Переранжирование

Основное применение патента происходит на этапе формирования SERP.

• Кластеризация и оптимизация: Clustering Engine получает набор результатов и применяет фреймворк оптимизации: генерирует первичные кластеры, запускает параллельные алгоритмы кластеризации и оценивает их качество с помощью Cluster Score.
• Формирование SERP: Result Engine выбирает наилучший вариант кластеризации и организует финальную выдачу в виде сгруппированных блоков (например, каруселей).

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

• Набор релевантных результатов поиска с их оценками популярности.
• Привязки результатов поиска к сущностям.
• Entity Ontology.
• Trained Embedding Model.

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

• Организованная страница результатов поиска (SERP), где результаты сгруппированы по финальным кластерам с наивысшим качеством.

На что влияет

• Специфические запросы: Наибольшее влияние на широкие, общие запросы (например, "игры", "инструменты", "рецепты"), где требуется разнообразие и структурирование выдачи.
• Конкретные типы контента и вертикали: Патент явно упоминает поиск мобильных приложений, но технология применима к товарам в маркетплейсах, песням, изображениям, видео и веб-документам.
• Форматы SERP: Влияет на формирование структурированной выдачи, каруселей, групп результатов вместо плоского списка.

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

• Триггеры активации: Алгоритм активируется, когда стандартный ранжированный список может быть недостаточно разнообразным (insufficiently diverse) или когда требуется предоставить логическую структуру для большого пространства результатов.
• Условия работы: Требуется наличие достаточного количества релевантных результатов, которые можно привязать к сущностям, а также наличие онтологии и обученной модели векторных представлений для этих сущностей.

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

Описание процесса оптимизации кластеризации (Optimization-based framework).

1. Определение релевантных результатов: Система определяет набор результатов поиска, отвечающих запросу.
2. Генерация и оценка первичных кластеров: Формируются first-level clusters на основе сущностей. Для них рассчитывается Cluster Score (см. Процесс Оценки).
3. Параллельное выполнение алгоритмов кластеризации: Система запускает несколько методов для генерации кандидатов.
   • Метод 1 (Двухэтапный, Схожесть):
     • Этап 1: Объединение кластеров, связанных онтологически, начиная с самых похожих (по Embedding Similarity).
     • Этап 2: Применение иерархической кластеризации.
   • Метод 2 (Двухэтапный, Размер):
     • Этап 1: Объединение кластеров, связанных онтологически, начиная с самых маленьких.
     • Этап 2: Применение иерархической кластеризации.
   • Метод 3 (Иерархический с онтологией): Иерархическая кластеризация, где Embedding Similarity усиливается (boost) для онтологически связанных пар.
   • Метод 4 (Иерархический стандартный): Иерархическая кластеризация только на основе Embedding Similarity.
   Примечание: В каждом методе объединение происходит, только если Cluster Score улучшается.
4. Выбор лучшего кандидата: Система сравнивает итоговое качество (например, средний Cluster Score или Silhouette Ratio) для всех методов.
5. Генерация SERP: Выбирается набор кластеров с наивысшей оценкой для отображения пользователю.

Процесс Оценки (Cluster Scoring):

1. Расчет Coverage Score: Определение процента популярных/топовых элементов.
2. Расчет Balance Score: Оценка равномерности распределения популярности (энтропия).
3. Расчет Overlap Score: Определение количества дубликатов между кластерами.
4. Расчет Silhouette Score: Оценка когерентности кластера и его отличия от соседей (используя Embedding Similarity).
5. Расчет Silhouette Ratio: Определение процента кластеров с Silhouette Score выше порога.
6. Расчет Cluster Score: Вычисление взвешенной линейной комбинации (регрессии) этих пяти метрик.

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

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

• Семантические факторы (NLP/Entities): Привязки результатов поиска к сущностям (Entities) в Knowledge Base. Основаны на анализе текста, метаданных или аннотаций.
• Структурные факторы (Ontology): Entity Ontology, определяющая отношения между сущностями (синонимы, иерархии).
• Векторные данные (Embeddings): Trained Embedding Model, позволяющий проецировать сущности и результаты поиска в единое Embedding Space.
• Поведенческие/Ранговые факторы (Popularity/Relevance): Данные о популярности или конверсии результатов (клики, покупки, установки). Используются для расчета метрики Coverage.

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

Система использует пять ключевых метрик для оценки качества кластеров:

1. Coverage Score: Процент популярных элементов, попавших в кластеры.
2. Balance Score: Энтропия распределения популярных элементов по кластерам.
3. Overlap Score: Количество дубликатов элементов между кластерами.
4. Silhouette Score: Мера когерентности кластера и его отличия от ближайшего соседа. Рассчитывается с использованием Embedding Similarity.
5. Silhouette Ratio: Процент кластеров с Silhouette Score выше порога.

Итоговая метрика:

• Cluster Score: Рассчитывается как регрессия (взвешенная линейная комбинация) пяти вышеуказанных метрик.