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

Постановка задачи

[math]x_1 \ldots x_l[/math] – выборка, состоящая из [math]l[/math] элементов. Она состоит из объектов, имеющих признаковое описание, как и в задачах регрессии и классификации.

Ключевое отличие ранжирования заключается в целевой переменной. Если ранее в задачах обучения с учителем каждому объекту соответствовал свой ответ, то теперь ответы — это пары вида: [math]\{ (i, j) : x_i \lt x_j\} [/math]. Набор таких пар и есть целевая переменная.

Основная задача – построить ранжирующую модель [math]a(x)[/math], такую, что: [math]\{ x_i \lt x_j \Rightarrow a(x_i) \lt a(x_j) \}[/math]

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

Ранжирование поисковой выдачи

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

В качестве объектов выступают пары [math](запрос, документ)[/math]. Запрос – ключевые слова, введенные пользователем, документ – один из всех документов, имеющихся в поисковой выдаче: [math]({запрос}, {документ}_1) \lt ({запрос}, {документ}_2) [/math]

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

Точность ранжирования

В самой простой постановке задачи ранжирования целевая переменная принимает два значения, документ либо релевантен запросу, либо нет:

[math]y(q, d) \in \{0, 1\}, [/math] где [math]y[/math] – целевая переменная, [math]q[/math] – запрос, [math]d[/math] – документ.

Пусть также есть некоторая модель [math]a(q, d)[/math], оценивающая релевантность документа запросу. По значениям, полученным с помощью этой модели, можно отранжировать документы. [math]d^{(i)}_{q}[/math] будет обозначать [math]i[/math]-й по релевантности документ для запроса [math]q[/math].

После того как введены обозначения, можно задать простейшую метрику ранжирования. Это [math]Precision@k[/math], точность среди первых [math]k[/math] документов ([math]k[/math] — параметр метрики). Если ранжируется поисковая выдача, и на первой странице показываются 10 документов, то разумно выбирать [math]k = 10[/math]. Данная метрика определяется как доля релевантных документов среди первых [math]k[/math], полученных с помощью модели:

[math]Precision@k(q) = {{1}\over{k}} \sum_{i = 1}^{k} y(q, d_{q}^{(i)})[/math]

Это полезная метрика, потому что обычно важно иметь релевантные документы среди первых [math]k[/math]. Однако у неё есть серьёзный недостаток: позиции релевантных документов никак не учитываются. Например, если при [math]k = 10[/math] среди первых [math]k[/math] документов есть [math]5[/math] релевантных, то неважно, где они находятся: среди первых или последних [math]5[/math] документов. Обычно же хочется, чтобы релевантные документы располагались как можно выше.

Описанную проблему можно решить, модифицировав метрику, и определить среднюю точность (average precision, [math]AP[/math]). Данная метрика тоже измеряется на уровне [math]k[/math] и вычисляется следующим образом:

[math]AP@k(q) = {{\sum_{i = 1}^{k} y(q, d_{q}^{(i)}) Precision@i(q)}\over{\sum_{i = 1}^{k} y(q, d_{q}^{(i)})}}[/math]

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

И точность, и средняя точность вычисляются для конкретного запроса [math]q[/math]. Если выборка большая и размечена для многих запросов, то значения метрик усредняются по всем запросам:

[math]MAP@k = {{1}\over{|Q|}} \sum_{q \in Q} AP@k(q)[/math]