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

Материал из MachineLearning.

(Различия между версиями)

Текущая версия

Статья написана с использованием LLM Gemini 3.1 Pro и проверена участником Vsevolod Peretiatko 23:43, 16 июня 2026 (MSD)

Ранжирование (или обучение ранжированию, англ. Learning to rank, LTR) — класс задач обучения с учителем, нацеленный на построение прогнозных моделей, способных оптимально упорядочивать (сортировать) подмножества объектов из некоторого пространства. В отличие от классических задач сортировки, где критерий сравнения элементов детерминирован и задан транзитивным отношением порядка (например, числовое неравенство), в задачах ранжирования решающее правило выводится автоматически на основе анализа многомерных признаковых описаний объектов и обучающей выборки, содержащей экспертные или поведенческие суждения о «правильном» порядке.

Рис. 1. Схема многоэтапного каскада обработки данных в современных поисковых системах: отсечение нерелевантного индекса на этапе Retrieval и точечное переранжирование нейросетями в топе выдачи.

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

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

Математическая постановка задачи

В классической терминологии информационного поиска задача формулируется в терминах запросов (англ. queries) и документов (англ. documents).

Пусть задано множество запросов $Q$ и множество документов $D$ . Для каждого обучающего запроса $q_i \in Q \ (i = 1, \dots, m)$ существует набор из $n_i$ документов $D_i = \{d_{i,1}, d_{i,2}, \dots, d_{i,n_i}\}$ , которые были отобраны поисковым движком (на этапе retrieval) для данного запроса.

Каждой паре «запрос — документ» $(q_i, d_{i,j})$ сопоставляется вектор признаков $\mathbf{x}_{i,j} = \Psi(q_i, d_{i,j}) \in \mathbb{R}^k$ . Признаки традиционно классифицируют на три макрогруппы:

Эндогенные признаки документа (англ. document-based features): не зависят от запроса, отражают внутренние свойства объекта (например, PageRank, статическая авторитетность веб-узла, длина документа, свежесть, индекс цитируемости).
Эндогенные признаки запроса (англ. query-based features): не зависят от документов, характеризуют контекст пользователя (например, длина запроса в словах, геопозиция, тип устройства, коммерческий интент запроса).
Признаки соответствия (англ. query-document features): вычисляют степень релевантности документа телу запроса (например, классические меры TF-IDF, BM25, косинусное расстояние между семантическими эмбеддингами запроса и документа, количество точных вхождений токенов в заголовки).

Также для каждой пары $(q_i, d_{i,j})$ задана истинная метка релевантности $y_{i,j}$ (англ. relevance label), отражающая степень полезности документа для данного запроса. Источником меток выступает экспертная разметка асессоров либо агрегированные логи пользовательского поведения (клики, время удержания внимания, конверсии). Оценки релевантности могут быть:

Бинарными: $y_{i,j} \in \{0, 1\}$ (релевантен / не релевантен).
Градуированными (многоуровневыми дискретными): $y_{i,j} \in \{0, 1, \dots, K\}$ , где $0$ — «абсолютно нерелевантно», а $K$ — «идеальный ответ» (англ. perfect match).

Обучающая выборка представляет собой множество кортежей $S = \left\{ (q_i, D_i, Y_i) \right\}_{i=1}^m$ , где $Y_i = \{y_{i,1}, y_{i,2}, \dots, y_{i,n_i}\}$ — вектор истинных меток релевантности для документов из подмножества $D_i$ .

Цель обучения ранжированию — найти такую вещественнозначную функцию ранжирования (англ. scoring function) $f(\mathbf{x}) = f(\Psi(q, d))$ , которая для любого нового запроса и ассоциированного с ним множества документов формирует такие оценки $\hat{y} = f(\mathbf{x}) \in \mathbb{R}$ , что сортировка документов по убыванию этих оценок максимально близко воспроизводит порядок, задаваемый вектором истинных меток $Y_i$ .

Подходы к обучению ранжированию

Рис. 2. Математическое различие подходов к обучению ранжированию: независимое предсказание оценок (Pointwise), оптимизация относительного порядка внутри комбинаторных пар (Pairwise) и структурная минимизация ошибки на всей группе документов (Listwise).

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

Поточечный подход (Pointwise approach)

Поточечный подход полностью игнорирует групповую структуру данных и сводит LTR к стандартным задачам обучения с учителем. Каждая пара «запрос — документ» рассматривается как независимый изолированный объект обучающей выборки.

В зависимости от природы меток $y_{i,j}$ , задача ставится как:

Регрессия: минимизируется среднеквадратичная ошибка (MSE): $\mathcal{L}(f) = \sum_{i=1}^m \sum_{j=1}^{n_i} (f(\mathbf{x}_{i,j}) - y_{i,j})^2$
Классификация: если метки дискретны, то минимизируется, например, многоклассовая кросс-энтропия, где модель предсказывает вероятность принадлежности объекта к каждому классу релевантности.

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

Недостатки: подход концептуально неоптимален. Модель не учитывает, что документы сгруппированы по запросам. Ошибка на нерелевантном документе в запросе, где вообще нет хороших ответов, штрафуется так же, как ошибка в топе критически важной выдачи. Кроме того, абсолютные значения оценок асессоров могут смещаться от запроса к запросу, что запутывает поточечную модель.

Попарный подход (Pairwise approach)

В попарном подходе минимизируется количество инверсий — пар документов для одного и того же запроса, порядок которых модель предсказала неверно. Объект обучения здесь — пара документов $(d_{i,j}, d_{i,k})$ при условии, что их истинные релевантности различны: $y_{i,j} \neq y_{i,k}$ .

Часто задача формулируется как бинарная классификация пар. Пусть $y_{i,j} > y_{i,k}$ (документ $j$ лучше документа $k$ ). Тогда модель должна выдать оценки, удовлетворяющие неравенству $f(\mathbf{x}_{i,j}) > f(\mathbf{x}_{i,k})$ . Вероятность того, что документ $j$ должен быть ранжирован выше документа $k$ , аппроксимируется сигмоидной функцией от разности их скоров: $P(j \succ k) = \sigma\left(f(\mathbf{x}_{i,j}) - f(\mathbf{x}_{i,k})\right) = \frac{1}{1 + \exp\left(-\left(f(\mathbf{x}_{i,j}) - f(\mathbf{x}_{i,k})\right)\right)}$

Функция потерь для всей выборки (например, в алгоритме RankNet) представляет собой кросс-энтропию: $\mathcal{L}(f) = - \sum_{i=1}^m \sum_{j, k: y_{i,j} > y_{i,k}} \ln P(j \succ k)$

Достоинства: более адекватное соответствие сути ранжирования (оптимизируется относительный порядок).

Недостатки: 1) Комбинаторный рост вычислительной сложности: количество пар в рамках запроса растёт квадратично $O(n_i^2)$ . 2) Проблема баланса: все пары штрафуются одинаково. Однако ошибка в перестановке документов на 1-м и 2-м местах в поисковой выдаче экспоненциально критичнее для пользователя, чем перестановка документов на 99-м и 100-м местах.

Посписочный подход (Listwise approach)

Посписочный подход работает непосредственно со всем списком документов $D_i$ для запроса $q_i$ как с единым многомерным объектом. Главная сложность здесь заключается в том, что целевые метрики ранжирования (NDCG, ERR) зависят от функции ранга (позиции элемента), которая является кусочно-постоянной (ступенчатой). Это делает применение классического метода градиентного спуска напрямую невозможным, так как градиент везде либо равен нулю, либо не существует.

Для решения проблемы гладкой оптимизации выделяют два пути:

Вероятностный подход (суррогатные функции) (например, ListNet): преобразует вектор оценок модели и вектор истинных релевантностей в распределения вероятностей на перестановках элементов списка с помощью многомерного обобщения Softmax, после чего минимизирует расстояние Кульбака — Лейблера между ними.
Прямая аппроксимация метрик (например, LambdaRank, LambdaMART): эти методы используют «виртуальные градиенты» ( $\lambda$ -градиенты). Вес градиента для попарной ошибки динамически масштабируется на величину изменения целевой метрики (например, $\Delta\text{NDCG}$ ), которое произойдет, если поменять эти два документа местами в текущей выдаче.

Достоинства: наивысшая точность, прямая оптимизация бизнес-метрик, фокус на корректности заполнения верхних позиций списка (топ выдачи).

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

Метрики качества ранжирования

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

Пусть для запроса модель отсортировала документы по убыванию $f(\mathbf{x})$ . Обозначим документ, оказавшийся на позиции $i$ , как $d_{(i)}$ , а его истинную релевантность — как $y_{(i)}$ .

MRR (Mean Reciprocal Rank)

Средний обратный ранг используется в задачах с бинарной релевантностью ( $y \in \{0, 1\}$ ), когда пользователя интересует исключительно один первый корректный ответ (например, навигационные запросы). $\text{RR}(q) = \frac{1}{\min \{ i \mid y_{(i)} = 1 \}}, \quad \text{MRR} = \frac{1}{|Q|} \sum_{q \in Q} \text{RR}(q)$

MAP (Mean Average Precision)

Средняя средняя точность оценивает качество всего возвращённого списка документов для бинарной разметки. Для начала вычисляется средняя точность ( $\text{Average Precision}, \text{AP}$ ) для одного запроса: $\text{AP}(q) = \frac{\sum_{i=1}^{n_i} \text{P@i} \cdot y_{(i)}}{\sum_{i=1}^{n_i} y_{(i)}}$ , где $\text{P@i}$ (Precision at $i$ ) — точность на срезе топ- $i$ элементов: $\text{P@i} = \frac{1}{i} \sum_{k=1}^i y_{(k)}$ Итоговая метрика $\text{MAP}$ является усреднением $\text{AP}(q)$ по всем запросам.

NDCG (Normalized Discounted Cumulative Gain)

Нормированный дисконтированный суммарный выигрыш — индустриальный стандарт оценки. Рассчитан на многоуровневые дискретные оценки $y_{(i)}$ и учитывает затухание внимания пользователя с помощью логарифмического дисконтирования. Расчёт для фиксированного среза длины $p$ (например, $p=10$ ):

CG (Cumulative Gain): $\text{CG}_p = \sum_{i=1}^p y_{(i)}$
DCG (Discounted Cumulative Gain): введение штрафа за низкую позицию. Наиболее популярна формула: $\text{DCG}_p = \sum_{i=1}^p \frac{2^{y_{(i)}} - 1}{\log_2(i + 1)}$
NDCG (Normalized DCG): деление на максимально возможное идеальное значение метрики ( $\text{IDCG}_p$ ), получаемое при идеальной сортировке: $\text{NDCG}_p = \frac{\text{DCG}_p}{\text{IDCG}_p} \in [0, 1]$

ERR (Expected Reciprocal Rank)

Ожидаемый обратный ранг базируется на каскадной модели поведения пользователя, который сканирует выдачу сверху вниз и останавливается с вероятностью, зависящей от релевантности текущего документа. Вероятность удовлетворения документом на позиции $i$ : $R_i = \frac{2^{y_{(i)}} - 1}{2^{y_{\max}}}$ Тогда математическое ожидание обратного ранга: $\mathrm{ERR} = \sum_{i=1}^p \frac{1}{i} P_i = \sum_{i=1}^p \frac{1}{i} R_i \prod_{k=1}^{i-1} (1 - R_k)$

Классические алгоритмы

Эволюция классических алгоритмов обучения ранжированию развивалась параллельно с тремя фундаментальными подходами (pointwise, pairwise, listwise). Ключевым технологическим драйвером в этой области стали исследования подразделения Microsoft Research, преодолевшие дискретность поисковых метрик, а также адаптация классических статистических методов.

RankSVM (Pairwise)

Исторически один из первых успешных алгоритмов попарного подхода, предложенный Торстеном Йоахимсом (Thorsten Joachims) в 2002 году. Алгоритм сводит задачу ранжирования к оптимизации разделяющей гиперплоскости в методе опорных векторов (SVM).

Идея: Для каждого запроса $q_i$ и пары документов $(d_{i,j}, d_{i,k})$ , такой что $y_{i,j} > y_{i,k}$ , максимизируется зазор (margin) между проекциями векторов признаков на искомый вектор весов $\mathbf{w}$ . Задача оптимизации формулируется через разности признаковых описаний:

$\frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i,j,k} \xi_{ijk} \to \min_{\mathbf{w}, \xi}$

при условии $\mathbf{w}^T (\mathbf{x}_{i,j} - \mathbf{x}_{i,k}) \ge 1 - \xi_{ijk}, \quad \xi_{ijk} \ge 0$

где $\xi_{ijk}$ — ослабляющие переменные (slack variables), штрафующие модель за нарушение порядка в паре.

Ограничения: Квадратичный рост числа пар ограничил применение RankSVM на больших выборках. Кроме того, линейное ядро плохо моделирует сложные нелинейные зависимости, а переход к ядерному SVM драматически повышает вычислительную сложность на этапе предсказания.

RankNet (Pairwise)

Разработанный Кристофером Берджесом (Christopher J.C. Burges) в 2005 году, RankNet заменил жесткие ограничения RankSVM на гладкую вероятностную функцию потерь, что позволило использовать нейронные сети и алгоритм обратного распространения ошибки.

Математическая модель: Модель предсказывает вещественные оценки (скоры) $s_j = f(\mathbf{x}_{i,j})$ . Вероятность того, что документ $j$ должен стоять выше документа $k$ , аппроксимируется логистической функцией:

$P_{jk} \equiv P(j \succ k) = \frac{1}{1 + \exp(-\alpha (s_j - s_k))}$

где $\alpha$ — гиперпараметр масштабирования. В качестве лосса для пары используется бинарная кросс-энтропия с истинным распределением $\bar{P}_{jk} \in \{0, 1, 0.5\}$ :

$\mathcal{L}_{jk} = - \bar{P}_{jk} \ln P_{jk} - (1 - \bar{P}_{jk}) \ln (1 - P_{jk})$

Оптимизация: Градиент лосса по скору $s_j$ (обозначаемый как $\lambda_{jk}$ ) равен:

$\lambda_{jk} = \frac{\partial \mathcal{L}_{jk}}{\partial s_j} = -\alpha \left( \bar{P}_{jk} - P_{jk} \right)$

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

LambdaRank (Pairwise / Суррогатный Listwise)

LambdaRank (2006 г.) решил фундаментальную проблему RankNet — одинаковый вес ошибки для инверсий в начале списка (топ выдачи) и в его конце. Поскольку целевые метрики (например, NDCG) дискретны, их нельзя дифференцировать напрямую.

Идея: Вместо поиска явной аналитической формы функции потерь, Берджес предложил сразу переопределить её градиент (названный $\lambda$ -градиентом). Физический смысл $\lambda_j$ — это результирующая сила, толкающая документ $j$ вверх или вниз по списку выдачи.
Формула градиента: Попарный градиент RankNet динамически масштабируется на абсолютную величину изменения целевой метрики $|\Delta\text{Metric}|$ (например, $|\Delta\text{NDCG}|$ ), которое произошло бы, если бы документы $j$ и $k$ поменялись местами в текущем промежуточном ранжировании:

$\lambda_{jk} = -\frac{\alpha}{1 + \exp(\alpha(s_j - s_k))} \cdot |\Delta\text{NDCG}|$

Рис. 3. Действие виртуальных сил ( $\lambda$ -градиентов) на документы промежуточной выдачи: релевантные объекты выталкиваются вверх, а нерелевантные — смещаются вниз.

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

ListNet (Listwise)

Предложенный в 2007 году алгоритм ListNet перенес фокус с пар на оптимизацию всего списка документов целиком через вероятностные модели перестановок (модель Плакетта-Люса).

Математическая модель: Для подмножества документов запроса $D_i$ вычисляется распределение вероятностей top-1. Вероятность того, что документ $j$ окажется на первом месте при векторе скоров модели $\mathbf{s}$ , задается как многомерный Softmax:

$P_{f}(d_{i,j}) = \frac{\exp(f(\mathbf{x}_{i,j}))}{\sum_{l=1}^{n_i} \exp(f(\mathbf{x}_{i,l}))}$

Аналогичным образом из истинных экспертных меток релевантности $Y_i$ формируется целевое распределение $P_{y}(d_{i,j})$ .

Функция потерь: Минимизируется расстояние Кульбака — Лейблера (KL-divergence) между модельным и истинным распределениями:

$\mathcal{L}(f) = \sum_{i=1}^m \sum_{j=1}^{n_i} P_{y}(d_{i,j}) \ln \frac{P_{y}(d_{i,j})}{P_{f}(d_{i,j})}$

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

LambdaMART (Listwise)

Вершина развития классического LTR (2010 г.), объединившая концепцию виртуальных $\lambda$ -градиентов LambdaRank и ансамблирование с помощью градиентного бустинга над решающими деревьями (GBDT).

Алгоритм: Вместо весов нейронной сети оптимизируется композиция базовых алгоритмов (деревьев регрессии). На каждой итерации бустинга для каждого документа рассчитывается суммарный псевдоотклик (сдвиг):

$\lambda_j = \sum_{k: y_{i,j} > y_{i,k}} \lambda_{jk} - \sum_{k: y_{i,k} > y_{i,j}} \lambda_{kj}$

Эти значения $\lambda_j$ выступают в качестве антиградиента (целевого вектора), под который подгоняется новое решающее дерево с помощью метода наименьших квадратов.

Вычисление значений в листьях: После построения структуры дерева значения в терминальных вершинах (листьях) пересчитываются с помощью одного шага метода Ньютона-Рафсона, что требует аппроксимации второй производной (Гессиана) суррогатного лосса. Благодаря стабильности деревьев к мультиколлинеарности и выбросам, LambdaMART стал основой библиотек LightGBM, XGBoost и CatBoost.

Современные нейросетевые архитектуры

Эра глубокого обучения (Deep Learning) сместила парадигму LTR от ручного конструирования признаков (feature engineering) к сквозному обучению (end-to-end), где модель одновременно учится извлекать семантические представления из сырого текста или графовых топологий и оптимально упорядочивать их.

Двухбашенные модели и DSSM

Историческим фундаментом глубокого семантического ранжирования стала архитектура DSSM (Deep Structured Semantic Model), разработанная Microsoft в 2013 году для борьбы с «лексическим разрывом» (когда запрос и релевантный документ написаны разными синонимами).

Рис. 4. Архитектура нейросети DSSM: независимое отображение текстовых пространств запроса и документа в векторное пространство признаков одинаковой размерности с последующим расчетом косинусного расстояния.

Архитектура: Модель представляет собой "две башни" (Two-Tower architecture) — независимые многослойные перцептроны (позже — CNN или LSTM). Первая башня преобразует текстовое тело запроса $q$ в низкоразмерный вектор $\mathbf{y}_q$ , вторая — документ $d$ в вектор $\mathbf{y}_d$ .
Word Hashing: Для преодоления огромной размерности словаря сырой текст разбивается на символьные n-граммы (например, слово «cat» преобразуется в триграммы #ca, cat, at#). Это сжимает размерность входного пространства с миллионов токенов до фиксированных нескольких тысяч и делает модель устойчивой к опечаткам.
Оптимизация: Сходство вычисляется как косинусное расстояние $R(q,d) = \text{cosine}(\mathbf{y}_q, \mathbf{y}_d)$ . Модель минимизирует попарный контрастивный лосс (или cross-entropy по подмножеству документов), максимизируя схожесть запроса с кликнутым документом и минимизируя со случайными негативными примерами (negative sampling).

Трансформеры: Bi-Encoders и Cross-Encoders

Появление архитектуры Трансформер и предобученных языковых моделей (BERT) разделило современные нейросетевые ранжировщики по вычислительной сложности и глубине извлечения признаков.

Bi-Encoders (Двухкодировщики):

Развивают идеи двухбашенных моделей. Запрос и документ кодируются отдельными трансформерами независимо: $\mathbf{e}_q = \text{BERT}_Q(q)$ и $\mathbf{e}_d = \text{BERT}_D(d)$ . Итоговый скор — это скалярное произведение или косинусная близость.

Достоинства: Эмбеддинги документов можно рассчитать заранее, сохранить в векторный индекс и осуществлять мгновенный поиск кандидатов с помощью алгоритмов приближенного поиска ближайших соседей (ANN, например, HNSW).

Продвинутые варианты (ColBERT): Используют стратегию позднего взаимодействия (late interaction). Вместо сжатия текста в один вектор, ColBERT сохраняет эмбеддинги всех токенов и вычисляет финальный скор через оператор MaxSim: $\sum_{t \in q} \max_{t' \in d} (\mathbf{e}_t \cdot \mathbf{e}_{t'})$ , что сохраняет токенизированную структуру и резко повышает точность.

Cross-Encoders (Перекрестные кодировщики):

Запрос и документ подаются в один трансформер одновременно в виде единой последовательности, разделенной специальным токеном: `[CLS] query [SEP] document [SEP]`. Механизм внутреннего внимания (Self-Attention) вычисляет перекрестные веса между каждым словом запроса и каждым словом документа на всех слоях нейросети.

Достоинства: Наивысшее качество ранжирования (State-of-the-Art), улавливание тонкого контекста, отрицаний и синтаксических связей.
Недостатки: Экстремально высокая вычислительная сложность. Невозможность предрасчета векторов документов вынуждает прогонять тяжелую нейросеть через трансформер в режиме реального времени.

По этой причине в современных поисковых системах применяется каскадная схема: быстрый Bi-Encoder отбирает топ-100 кандидатов (этап retrieval), а тяжелый Cross-Encoder осуществляет финальное точечное переранжирование (re-ranking).

Рис. 5. Топология современных ранжировщиков на базе Трансформеров. Сверху: вычислительно легкий Bi-Encoder для быстрого ANN-поиска. В центре: Cross-Encoder с полным механизмом Self-Attention для финального отбора. Снизу: схема ColBERT (Late Interaction).

Графовые нейронные сети (GNN) в ранжировании

В рекомендательных системах (e-commerce, социальные сети) ранжирование усложняется тем, что объекты и пользователи связаны сетью интеракций. Задача формулируется как ранжирование на двудольном графе «пользователь — товар» (User-Item Graph).

Пространственный подход (Spatial Message Passing):

Архитектуры вроде PinSage (разработка Pinterest на базе GraphSAGE) агрегируют информацию от локального окружения узла. Эмбеддинг товара формируется путем свертки признаков его соседей — пользователей, которые с ним взаимодействовали, и других товаров из их сессий.

Рис. 6. Формирование вектора целевого товара в GNN через Message Passing.

Спектральный анализ и лапласиан графа:

Для выявления глобальной топологии графа задействуется его спектральный анализ. Графовый лапласиан $L = D - A$ (где $D$ — матрица степеней узлов, $A$ — матрица смежности) позволяет разложить структуру графа в базис собственных векторов. Это эквивалентно переходу в частотную область (преобразование Фурье на графах), помогая модели ранжирования улавливать макро-сообщества (spectral clustering) и глобальные тренды схожести, недоступные локальным сверткам.

Масштабирование через Random Walks:

Поскольку вычисление честного спектра на миллиардных графах невозможно, алгоритмы (PinSage) аппроксимируют его. Используются случайные блуждания (Random Walks): важность соседа определяется частотой попадания в него при случайном блуждании из целевой вершины. Эмбеддинги, полученные на выходе GNN, подаются в финальный слой с Max-Margin лоссом, обучающим модель ранжировать релевантные пользователю товары выше случайных.

См. также

Информационный поиск — предметная область, изучающая методы поиска, извлечения и ранжирования текстовой и мультимедийной информации.
Рекомендательная система — класс алгоритмов, предсказывающих предпочтения пользователей и ранжирующих объекты в условиях отсутствия явного поискового запроса.
Градиентный бустинг — метод построения композиций слабых моделей (обычно решающих деревьев), являющийся математическим фундаментом алгоритма LambdaMART.
Обучение с учителем — общая парадигма машинного обучения, подмножеством которой является обучение ранжированию (LTR).
Архитектура Трансформер — нейросетевая архитектура, основанная на механизме Self-Attention и доминирующая в современных задачах семантического ранжирования.
Метод опорных векторов — алгоритм бинарной классификации, линейное расширение которого легло в основу попарного метода RankSVM.
Расстояние Кульбака — Лейблера — статистическая метрика расхождения распределений, используемая в качестве функции потерь в посписочном алгоритме ListNet.

Литература

Joachims T. Optimizing search engines using clickthrough data // Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. — 2002. — С. 133–142.
Cao Z., Qin T., Liu T.-Y., Tsai M.-F., Li H. Learning to rank using listwise approach // Proceedings of the 24th international conference on Machine learning. — 2007. — С. 129–136.
Liu T.-Y. Learning to Rank for Information Retrieval // Foundations and Trends® in Information Retrieval. — 2009. — Т. Vol. 3, no. 3. — С. 225–331.
Burges C. J. C. From RankNet to LambdaRank to LambdaMART: An Overview // Microsoft Research Technical Report MSR-TR-2010-82. — 2010.
Huang P.-S., He X., Gao J., Deng L., Acero A., Heck L. Learning deep structured semantic models for web search using clickthrough data // Proceedings of the 22nd ACM international conference on Information & Knowledge Management (CIKM). — 2013. — С. 2333–2338.
Ying R., He R., Chen K., Eksombatchai P., Hamilton W. L., Leskovec J. Graph convolutional neural networks for web-scale recommender systems (PinSage) // Proceedings of the 24th ACM SIGKDD International Conference. — 2018. — С. 974-983.
Nogueira R., Cho K. Passage Re-ranking with BERT // arXiv preprint arXiv:1901.04085. — 2019.
Khattab O., Zaharia M. ColBERT: Efficient and effective passage search via contextualized late interaction over BERT // Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. — 2020. — С. 39–48.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%BD%D0%B6%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5»

Категории: Машинное обучение | Ранжирование

@@ Строка 2: / Строка 2: @@
 '''Ранжирование''' (или ''обучение ранжированию'', англ. ''Learning to rank'', LTR) — класс задач [[Обучение с учителем|обучения с учителем]], нацеленный на построение прогнозных моделей, способных оптимально упорядочивать (сортировать) подмножества объектов из некоторого пространства. В отличие от классических задач [[Алгоритм сортировки|сортировки]], где критерий сравнения элементов детерминирован и задан транзитивным отношением порядка (например, числовое неравенство), в задачах ранжирования решающее правило выводится автоматически на основе анализа многомерных признаковых описаний объектов и [[Обучающая выборка|обучающей выборки]], содержащей экспертные или поведенческие суждения о «правильном» порядке.
+[[Изображение:Multi stage search ranking cascade pipeline.svg|thumb|500px|Рис. 1. Схема многоэтапного каскада обработки данных в современных поисковых системах: отсечение нерелевантного индекса на этапе Retrieval и точечное переранжирование нейросетями в топе выдачи.]]
 Наиболее важное применение методы ранжирования находят в архитектуре современных систем [[Информационный поиск|информационного поиска]] (формирование поисковой выдачи по текстовым запросам), [[Рекомендательная система|рекомендательных системах]] (ранжирование лент новостей, товаров или медиаконтента), а также в задачах подбора персонала, фильтрации спама и вычислительной биологии.
@@ Строка 28: / Строка 30: @@
 == Подходы к обучению ранжированию ==
+[[Изображение:Pointwise pairwise listwise approaches.svg|thumb|400px|Рис. 2. Математическое различие подходов к обучению ранжированию: независимое предсказание оценок (Pointwise), оптимизация относительного порядка внутри комбинаторных пар (Pairwise) и структурная минимизация ошибки на всей группе документов (Listwise).]]
 В зависимости от способа декомпозиции выборки и структуры конструируемой функции потерь, выделяют три фундаментальные парадигмы обучения ранжированию.
@@ Строка 122: / Строка 126: @@
 * '''Формула градиента''': Попарный градиент RankNet динамически масштабируется на абсолютную величину изменения целевой метрики <tex>|\Delta\text{Metric}|</tex> (например, <tex>|\Delta\text{NDCG}|</tex>), которое произошло бы, если бы документы <tex>j</tex> и <tex>k</tex> поменялись местами в текущем промежуточном ранжировании:
 :<tex>\lambda_{jk} = -\frac{\alpha}{1 + \exp(\alpha(s_j - s_k))} \cdot |\Delta\text{NDCG}|</tex>
+[[Изображение:Lambdarank gradient forces.svg|thumb|center|650px|Рис. 3. Действие виртуальных сил (<tex>\lambda</tex>-градиентов) на документы промежуточной выдачи: релевантные объекты выталкиваются вверх, а нерелевантные — смещаются вниз.]]
 Теоретически доказано, что такая эвристическая модификация градиента гарантирует локальную оптимизацию негладкой исходной метрики.
@@ Строка 146: / Строка 153: @@
 === Двухбашенные модели и DSSM ===
 Историческим фундаментом глубокого семантического ранжирования стала архитектура '''DSSM''' (Deep Structured Semantic Model), разработанная Microsoft в 2013 году для борьбы с «лексическим разрывом» (когда запрос и релевантный документ написаны разными синонимами).
+[[Изображение:Dssm two tower architecture.svg|thumb|center|450px|Рис. 4. Архитектура нейросети DSSM: независимое отображение текстовых пространств запроса и документа в векторное пространство признаков одинаковой размерности с последующим расчетом косинусного расстояния.]]
 * '''Архитектура''': Модель представляет собой "две башни" (Two-Tower architecture) — независимые многослойные перцептроны (позже — CNN или LSTM). Первая башня преобразует текстовое тело запроса <tex>q</tex> в низкоразмерный вектор <tex>\mathbf{y}_q</tex>, вторая — документ <tex>d</tex> в вектор <tex>\mathbf{y}_d</tex>.
 * '''Word Hashing''': Для преодоления огромной размерности словаря сырой текст разбивается на символьные n-граммы (например, слово «cat» преобразуется в триграммы #ca, cat, at#). Это сжимает размерность входного пространства с миллионов токенов до фиксированных нескольких тысяч и делает модель устойчивой к опечаткам.
@@ Строка 151: / Строка 161: @@
 === Трансформеры: Bi-Encoders и Cross-Encoders ===
 Появление архитектуры [[Трансформер|Трансформер]] и [[BERT|предобученных языковых моделей (BERT)]] разделило современные нейросетевые ранжировщики по вычислительной сложности и глубине извлечения признаков.
@@ Строка 157: / Строка 168: @@
 :'''Достоинства''': Эмбеддинги документов можно рассчитать заранее, сохранить в [[Векторная база данных|векторный индекс]] и осуществлять мгновенный поиск кандидатов с помощью [[Приближённый поиск ближайших соседей|алгоритмов приближенного поиска ближайших соседей]] (ANN, например, HNSW).
 :'''Продвинутые варианты (ColBERT)''': Используют стратегию позднего взаимодействия (late interaction). Вместо сжатия текста в один вектор, ColBERT сохраняет эмбеддинги всех токенов и вычисляет финальный скор через оператор MaxSim: <tex>\sum_{t \in q} \max_{t' \in d} (\mathbf{e}_t \cdot \mathbf{e}_{t'})</tex>, что сохраняет токенизированную структуру и резко повышает точность.
 * '''Cross-Encoders (Перекрестные кодировщики)''':
 Запрос и документ подаются в один трансформер одновременно в виде единой последовательности, разделенной специальным токеном: `[CLS] query [SEP] document [SEP]`. Механизм [[Модель внимания|внутреннего внимания (Self-Attention)]] вычисляет перекрестные веса между каждым словом запроса и каждым словом документа на всех слоях нейросети.
@@ Строка 163: / Строка 173: @@
 :* '''Недостатки''': Экстремально высокая вычислительная сложность. Невозможность предрасчета векторов документов вынуждает прогонять тяжелую нейросеть через трансформер в режиме реального времени.
 По этой причине в современных поисковых системах применяется каскадная схема: быстрый Bi-Encoder отбирает топ-100 кандидатов (этап retrieval), а тяжелый Cross-Encoder осуществляет финальное точечное переранжирование (re-ranking).
+[[Изображение:Transformer ranking architectures.svg|thumb|center|850px|Рис. 5. Топология современных ранжировщиков на базе Трансформеров. Сверху: вычислительно легкий Bi-Encoder для быстрого ANN-поиска. В центре: Cross-Encoder с полным механизмом Self-Attention для финального отбора. Снизу: схема ColBERT (Late Interaction).]]
 === [[Графовые нейронные сети]] (GNN) в ранжировании ===
@@ Строка 169: / Строка 181: @@
 * '''Пространственный подход (Spatial Message Passing)''':
 Архитектуры вроде [[PinSage]] (разработка Pinterest на базе GraphSAGE) агрегируют информацию от локального окружения узла. Эмбеддинг товара формируется путем свертки признаков его соседей — пользователей, которые с ним взаимодействовали, и других товаров из их сессий.
+[[Изображение:User item bipartite graph gnn.svg|thumb|center|460px|Рис. 6. Формирование вектора целевого товара в GNN через Message Passing.]]
 * '''Спектральный анализ и лапласиан графа''':
 Для выявления глобальной топологии графа задействуется его [[Спектральный анализ|спектральный анализ]]. [[Графовый лапласиан]] <tex>L = D - A</tex> (где <tex>D</tex> — матрица степеней узлов, <tex>A</tex> — матрица смежности) позволяет разложить структуру графа в базис собственных векторов. Это эквивалентно переходу в частотную область ([[Преобразование Фурье|преобразование Фурье]] на графах), помогая модели ранжирования улавливать макро-сообщества (spectral clustering) и глобальные тренды схожести, недоступные локальным сверткам.