44
правки
Изменения
Нет описания правки
'''Ранжирование''' (англ. ''learning to rank'') {{---}} это класс задач [[Общие понятия|машинного обучения с учителем]], заключающихся в автоматическом подборе ранжирующей модели по обучающей выборке, состоящей из множества списков и заданных частичных порядков на элементах внутри каждого списка. Частичный порядок обычно задаётся путём указания оценки для каждого элемента (например, «релевантен» или «не релевантен»). Цель ранжирующей модели — наилучшим образом приблизить и обобщить способ ранжирования в обучающей выборке на новые данные.
==Постановка задачи==
<tex>X</tex> {{---}} множество объектов. <tex>X^l = \{x_1 , \ldots , x_l\}</tex> – {{---}} обучающая выборка, состоящая из . <tex>i \prec j</tex> {{---}} правильный частичный порядок на парах <tex>(i, j) \in \{1, \ldots, l\}^2</tex> элементов. Она состоит из объектов"Правильность" зависит от постановки задачи, а именно запись <tex>i \prec j</tex> может означать, что объект <tex>i</tex> имеет ранг выше, имеющих признаковое описаниечем объект <tex>j</tex>, как так и в задачах регрессии наоборот. '''Задача:''' Построить ранжирующую функцию <tex>a : X \to \mathbb{R}</tex> такую, что: <tex> i \prec j \Rightarrow a(x_i) < a(x_j)</tex>. '''Линейная модель ранжирования:''' <tex>a(x; w) = \langle x, w \rangle</tex>, где <tex>x \mapsto (f_1(x), \ldots, f_n(x)) \in \mathbb{R}^n</tex> {{---}} вектор признаков объекта <tex>x</tex>. ==Примеры приложения=====Задача ранжирования поисковой выдачи===<tex>D</tex> {{---}} коллекция текстовых документов. <tex>Q</tex> {{---}} множество запросов. <tex>D_q \subseteq D</tex> {{---}} множество документов, найденных по запросу <tex>q</tex>. <tex>X = Q \times D</tex> {{---}} объектами являются пары (запрос, документ): <tex>x \equiv (q, d), q \in Q, d \in D_q</tex>. <tex>Y</tex> {{---}} упорядоченное множество рейтингов. <tex>y: X \to Y</tex> {{---}} оценки релевантности, поставленные асессорами(экспертами): чем выше оценка <tex>y(q, d)</tex>, тем релевантнее документ <tex>d</tex> по запросу <tex>q</tex>. ''Правильный порядок'' определен только между документами, найденными по одному и классификациитому же запросу <tex>q</tex>: <tex> (q, d) \prec (q, d') \Leftrightarrow y(q, d) < y(q, d')</tex>.
==Метрики качества ранжирования==
===Точность ранжирования===
В самой простой постановке задачи ранжирования целевая переменная принимает два значения, документ
либо релевантен запросу, либо нет:
<tex>y(q, d) \in \{0, 1\}, </tex> где <tex>y</tex> – целевая переменная, <tex>q</tex> – запрос, <tex>d</tex> – документ.
как доля релевантных документов среди первых <tex>k</tex>, полученных с помощью модели:
<tex>Precision@k(q) = {{1}\over{k}} \sum_{i = 1}^{k} y(q, d_{q}^{(i)})</tex>.
при <tex>k = 10</tex> среди первых <tex>k</tex> документов есть <tex>5</tex> релевантных, то неважно, где они находятся: среди первых
или последних <tex>5</tex> документов. Обычно же хочется, чтобы релевантные документы располагались как можно
выше.
Описанную проблему можно решить, модифицировав метрику, и определить среднюю точность (англ. averageprecision, <tex>AP</tex>). Данная метрика тоже измеряется на уровне <tex>k</tex> и вычисляется следующим образом:
<tex>AP@k(q) = {\large {{\sum_{i = 1}^{k} y(q, d_{q}^{(i)}) Precision@i(q)}\over{\sum_{i = 1}^{k} y(q, d_{q}^{(i)})}}}</tex>.
Данная величина уже зависит от порядка. Она достигает максимума, если все релевантные документы находятся вверху ранжированного списка. Если они смещаются ниже, значение метрики уменьшается.
И точность, и средняя точность вычисляются для конкретного запроса <tex>q</tex>. Если выборка большая и размечена для многих запросов, то значения метрик усредняются по всем запросам:
<tex>MAP@k = {{1}\over{|Q|}} \sum_{q \in Q} AP@k(q)</tex>.
===DCG===
Второй подход к измерению качества ранжирования — это метрика DCG дисконтированный совокупный доход (англ. discounted cumulative gain)или DCG. Онаиспользуется в более сложной ситуации, когда оценки релевантности <tex>y</tex> могут быть вещественными: <tex>y(q, d) \in \mathbb{R}</tex>.
То есть для каждого документа теперь существует градация между релевантностью и нерелевантностью.
Остальные обозначения остаются теми же, что и для предыдущей метрики. Формула для вычисления DCG:
Метрика — это сумма дробей. Чем более релевантен документ, тем больше числитель в дроби. Знаменатель
штраф будет маленьким. Таким образом, метрика DCG учитывает и релевантность, и позицию документа.
Она достигает максимума, если все релевантные документы находятся в топе списка, причём отсортированные
по значению <tex>y</tex>.Данную метрику принято нормировать: <tex>nDCG@k(q) = {\large {DCG@k(q)} \over {{\large max DCG@k(q)}}}</tex>, где <tex>max DCG@k(q)</tex> — значение DCG при идеальном ранжировании. После нормировки метрика принимаетзначения от 0 до 1. '''Пример вычисления DCG и nDCG:''' Дано множество документов, где каждый документ оценивается от <tex>3</tex> до <tex>0</tex>, где <tex>3</tex> {{---}} очень релевантен, а <tex>0</tex> {{---}} не релевантен. Пусть таким множеством будет <tex>S = \{ D_1, D_2, D_3, D_4, D_5, D_6\}</tex>, где оценка релевантности по опросу пользователей задается(в том же порядке) множеством <tex>R = \{3, 2, 3, 0, 1, 2\}</tex>. Тогда <tex>DCG@6 = \sum_{i = 1}^{6} {{rel_i} \over {log(i+1)}} = 3 + 1.262 + 1.5 + 0 + 0.387 + 0.712 = 6.861</tex>
Идеальный порядок оценок релевантности <tex>nDCG@k(q) Ideal = \{3, 3, 2, 2, 1, 0\large {}</tex>. DCGдля данного множества будет следующим: <tex>maxDCG@k(q)6 = \sum_{i = 1}^{6} {{rel_i} \over {{\large max DCG@klog(qi+1)}}}= 3 + 1.893 + 1 + 0.861 + 0.387 + 0 = 7.141</tex>.
==Методы ранжирования==
Всего выделяют три подхода к решению задачи ранжирования: поточечный (англ. pointwise (поточечный), попарный (англ. pairwise (попарный), списочный (англ. listwise (списочный). Далее будут приведены по одному методу из каждого подхода, чтобы можно былосоставить представления об их различиях и особенностях.
===Поточечный подход===
