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

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

Background Probability (Фоновая вероятность)

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

Co-occurrence (Совместное появление)

Факт появления двух или более сущностей в одном списке или коллекции.

List (Список)

Коллекция или набор одной или более сущностей. Может быть списком на веб-странице (HTML UL/OL), социальным кругом (Social Circle), таблицей и т.д.

List Score (Оценка списка)

Числовое значение, присваиваемое списку, отражающее его полезность для идентификации связанных сущностей. Зависит от количества seeds, длины списка и Background Probability его элементов.

Negative Class Component (Компонент негативного класса)

Часть расчета List Score в вероятностной модели, основанная на предположении, что список нерелевантен. Обычно базируется на Background Probability.

Non-independent Data (Несамостоятельные данные)

Данные в списке, которые являются результатом копирования из другого источника. Система стремится понизить вес таких данных.

Positive Class Component (Компонент позитивного класса)

Часть расчета List Score, основанная на предположении, что список релевантен. Базируется на вероятностях seeds и модифицированных вероятностях других элементов.

Reciprocal Connections (Взаимные связи)

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

Seed Entities / Seed Items (Исходные сущности / Семена)

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

Set Expansion (Расширение набора)

Процесс поиска дополнительных элементов, принадлежащих к тому же концептуальному классу, что и исходный набор примеров.

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

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

1. Система идентифицирует связи между сущностями и получает исходные сущности (seeds).
2. Генерируется набор списков на основе этих связей.
3. Вычисляется Background Probability для каждой сущности (частота появления в наборе списков).
4. Вычисляется List Score для каждого списка. Эта оценка базируется на двух факторах: (а) количестве seeds в списке и (б) Background Probabilities сущностей в этом списке.
5. Идентифицируется подмножество списков на основе их оценок.
6. Вычисленная List Score присваивается сущностям в этом подмножестве с учетом их Background Probabilities.
7. Сущности ранжируются на основе присвоенных оценок для идентификации связанных сущностей.

Claim 12 (Зависимый от 11 и 1): Детализирует расчет List Score с использованием вероятностной модели.

1. Вычисляется Positive Class Component оценки списка на основе вероятностной модели.
2. Вычисляется Negative Class Component оценки списка на основе модели и Background Probabilities сущностей в списке.
3. List Score вычисляется на основе этих двух компонентов.

Claim 13 (Зависимый от 12): Вводит корректировку оценок на основе реципрокных (взаимных) связей в социальном контексте.

Система определяет наличие взаимных связей (Reciprocal Connections) между сущностями и владельцем списка. Компоненты Positive и Negative Class корректируются так, чтобы придать больший вес спискам, содержащим сущности с взаимными связями.

Claim 15 (Зависимый от 12): Описывает корректировку для борьбы со скопированными списками.

Система определяет наличие Non-independent Data в списке (на основе популярности частей списка). Компоненты Positive и Negative Class корректируются, чтобы придать меньший вес спискам, включающим такие данные, предотвращая искажения от массового копирования.

Claim 16 (Зависимый от 12): Вводит корректировку оценок на основе фактора популярности (popularity factor).

Система определяет фактор популярности для сущностей. Компоненты Positive и Negative Class корректируются так, чтобы присвоить меньший вес спискам, включающим сущности с высоким фактором популярности.

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

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

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

• Извлечение списков: Система должна извлекать и индексировать списки из различных источников (веб-страницы, структурированные данные, социальные графы). Упоминаются HTML-теги <UL>, <OL>, <DL>, таблицы.
• Расчет Background Probability: Глобальная популярность сущностей (Background Probability) должна быть предварительно рассчитана в ходе индексации или в рамках офлайн-процессов анализа данных (например, при построении Knowledge Graph).

RANKING / RERANKING (в рамках конкретных функций или вертикалей)

• Алгоритм применяется для ранжирования сущностей в ответ на запрос на расширение набора (например, запрос на предложение друзей в социальной сети, запрос на поиск связанных тем или запросов). Это самостоятельный процесс ранжирования сущностей, который использует данные из индекса.

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

• Набор исходных сущностей (Seed Entities).
• Обширная коллекция списков (Set of Lists).
• Предварительно рассчитанные Background Probabilities для всех сущностей в коллекции.

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

• Отранжированный список сущностей, которые считаются связанными с Seed Entities, с их финальными оценками.

На что влияет

• Сущности (Entities): Основной объект анализа. Алгоритм влияет на то, как система понимает связи между любыми типами сущностей (люди, места, концепции, продукты).
• Структурированные данные и списки: Влияет на интерпретацию данных, представленных в виде списков (HTML-списки, таблицы, разметка Schema.org).
• Тематические кластеры: Может использоваться для определения границ тематических кластеров и идентификации центральных и периферийных сущностей в них.

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

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

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

Этап 1: Подготовка данных (Офлайн / Индексация)

1. Сбор списков: Идентификация и сбор коллекции списков из различных источников.
2. Расчет Background Probability: Для каждой уникальной сущности в коллекции вычисляется ее фоновая вероятность (например, отношение числа списков, где она встречается, к общему числу списков).

Этап 2: Обработка запроса на расширение (Онлайн)

1. Получение ввода: Система получает набор исходных сущностей (Seed Entities).
2. Инициализация: Каждой seed сущности присваивается начальная вероятность (например, по формуле