174
правки
Изменения
м
Ключевое отличие ранжирования заключается в целевой переменной. Если ранее в задачах обучения с учителем каждому объекту соответствовал свой ответ, то теперь ответы — это пары вида: ===Коллаборативная фильтрация===<tex>\{ (i, j) : x_i \lt x_j\} U</tex>. Набор таких пар и есть целевая переменная{{---}} пользователи.
Основная задача – построить ранжирующую модель <tex>a(x)I</tex>, такую, что: <tex>\{ x_i \lt x_j \Rightarrow a{---}} предметы (x_iфильмы, книги и т.д.) \lt a(x_j) \}</tex>.
Таким образом<tex>X = U \times I</tex> {{---}} объектами являются пары (пользователь, по выходам необходимо восстановить порядок, а величина ответов не имеет значения. В этомзаключается главное отличие ранжирования от остальных задач машинного обученияпредмет).
==Ранжирование поисковой выдачи==Классическим примером для задачи ранжирования считается ранжирование поисковой выдачи. Далее для понимания материала везде будет рассматриваться данный пример''Правильный порядок'' определён между предметами, но все рассуждения хорошо обобщаются которые выбирал или рейтинговал один и для других примененийтот же пользователь: <tex>(u, i) \prec (u, i') \Leftrightarrow y(u, i) < y(u, i')</tex>.
В качестве объектов выступают пары Рекомендация пользователю <tex>(запрос, документ)u</tex> {{---}} это список предметов <tex>i</tex>. Запрос – ключевые слова, введенные пользователем, документ – один из всех документов, имеющихся в поисковой выдаче: упорядоченный с помощью функции ранжирования <tex>a({запрос}, {документ}_1) \lt ({запрос}u, {документ}_2i) </tex>.
Это полезная метрика, потому что обычно важно иметь релевантные документы среди первых <tex>k</tex>. Однакоу неё есть серьёзный недостаток: позиции релевантных документов никак не учитываются. Например, если
Формула для вычисления DCG: <tex>DCG@k(q)= \sum_{i = 1}^{k} {\large {{2^{y(q, d_{q}^{(i)})} - 1} \over {log(i+1)}}}</tex>.
Данную метрику принято нормироватьИдеальный порядок оценок релевантности <tex>Ideal = \{3, 3, 2, 2, 1, 0\}</tex>. DCG для данного множества будет следующим:<tex>maxDCG@6 = \sum_{i = 1}^{6} {{rel_i} \over {log(i+1)}} = 3 + 1.893 + 1 + 0.861 + 0.387 + 0 = 7.141</tex>.
где Итого <tex>max nDCG@6 = {{DCG@k(q)6} \over {maxDCG@6}} = {{6.861} \over {7.141}} = 0.961</tex> — значение DCG при идеальном ранжировании. После нормировки метрика принимаетзначения от 0 до 1.
Это не очень сложная Заметим, что данная формула, она зависит от одной пары объектов, а также не учитываются зависимости между различными парами. Возникает вопрос, можно ли модифицировать данный метод (а именно формулу шага) так, чтобы минимизировался не исходный функционал,оценивающий долю дефектных пар, а DCG.
Ответ на этот вопрос положительный. Можно Действительно, можно домножить градиент исходного функционала на то, насколько изменится nDCG, если поменять местами <tex>x_i</tex> и <tex>x_j</tex> :
Оказывается, что при выполнении градиентного спуска с помощью данных шагов оптимизируется NDCGДанный метод называется LambdaRank<ref>[https://www.Это эмпирический факт, и он не доказанmicrosoft. Но на практике NDCG действительно улучшается при решениизадачи данным методомcom/en-us/research/wp-content/uploads/2016/02/MSR-TR-2010-82.pdf From RankNet to LambdaRank {{---}} Christopher J.C. Burges]</ref>.
→Методы ранжирования
'''Ранжирование''' (англ. ''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>q</tex> {{---}} это список документов <tex>d</tex>, упорядоченных с помощью функции ранжирования <tex>a(q, d)</tex>.
==Метрики качества ранжирования==
===Точность ранжирования===
В самой простой постановке задачи ранжирования целевая переменная принимает два значения, документ
либо релевантен запросу, либо нет:
<tex>y(q, d) \in \{0, 1\}, </tex> где <tex>y</tex> – целевая переменная, <tex>q</tex> – запрос, <tex>d</tex> – документ.
релевантности документ для запроса <tex>q</tex>.
После того как введены обозначения, можно задать простейшую метрику ранжирования. Это <tex>Precision@k</tex>,
точность среди первых <tex>k</tex> документов (<tex>k</tex> — параметр метрики). Если ранжируется поисковая выдача, и на
первой странице показываются 10 документов, то разумно выбирать <tex>k = 10</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). Онаиспользуется в более сложной ситуации, когда оценки релевантности <tex>y</tex> могут быть вещественными:
===Дисконтированный совокупный доход===Второй подход к измерению качества ранжирования — дисконтированный совокупный доход (англ. 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>. {| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+|-align="center"! '''i''' || <tex>rel_i</tex> || <tex>log(i+1)</tex> || <tex>{rel_i}\over{log(i+1)}</tex>|-align="center"| <tex>1</tex> || <tex>3</tex> || <tex>1</tex> || <tex>3</tex>|-align="center"| <tex>2</tex> || <tex>2</tex> || <tex>1.585</tex> || <tex>1.262</tex>|-align="center"| <tex>3</tex> || <tex>3</tex> || <tex>2</tex> || <tex>1.5</tex> |-align="center"| <tex>4</tex> || <tex>0</tex> || <tex>2.322</tex> || <tex>0</tex> |-align="center"| <tex>5</tex> || <tex>1</tex> || <tex>2.585</tex> || <tex>0.387</tex>|-align="center"| <tex>6</tex> || <tex>2</tex> || <tex>2.807</tex> || <tex>0.712</tex> |}
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+|-align="center"! '''i''' || <tex>rel_i</tex> || <tex>nDCG@klog(qi+1) = {\large </tex> || <tex>{DCG@k(q)rel_i} \over {{\large max DCG@klog(qi+1)}}}</tex>|-align="center"| <tex>1</tex> || <tex>3</tex> || <tex>1</tex> || <tex>3</tex>|-align="center"| <tex>2</tex> || <tex>3</tex> || <tex>1.585</tex> || <tex>1.893</tex>|-align="center"| <tex>3</tex> || <tex>2</tex> || <tex>2</tex> || <tex>1</tex> |-align="center"| <tex>4</tex> || <tex>2</tex> || <tex>2.322</tex> || <tex>0.861</tex> |-align="center"| <tex>5</tex> || <tex>1</tex> || <tex>2.585</tex> || <tex>0.387</tex>|-align="center"| <tex>6</tex> || <tex>0</tex> || <tex>2.807</tex> || <tex>0</tex> |}
==Методы ранжирования==
Всего выделяют три подхода к решению задачи ранжирования: поточечный (англ. pointwise (поточечный), попарный (англ. pairwise (попарный), списочный (англ. listwise (списочный). Далее будут приведены по одному методу из каждого подходаВыбор метода зависит от качества ранжирования данных. Теоретически, чтобы можно былосоставить представления об их различиях и особенностяхсписочный подход считается наилучшим, однако, на практике, например в Яндексе, лучше всего работает попарный подход.
===Поточечный подход===
Самый простой подход — это поточечный. В нём игнорируется тот факт, что целевая переменная <tex>y(q, d) \in \mathbb{R}</tex> задаётся на парах объектов, и оценка релевантности <tex>a(d, q)</tex> оценивается непосредственно считается для каждого объекта.
Если речь идёт о задаче ранжированияпоисковой выдачи, то пусть асессор поставил какую-то оценку <tex>y</tex> каждой паре (запрос, документ). Эта оценка и будет предсказываться. При этом никак не учитывается, что на самом деленужно предсказать порядок объектов, а не оценки. Этот подход является простым в том смысле, что в нём
используются уже известные методы. Например, можно предсказывать оценки с использованием линейной
регрессии и квадратичной ошибки:
===Попарный подход===
В попарном подходе используются знания об устройстве целевой переменной. Модель строится минимизацией сведением к минимуму количества дефектных пар, то есть таких, в которых моделью был предсказан неправильный порядок:
<tex>\sum_{x_i < x_j} [a(x_j) - a(x_i) < 0] \rightarrow min</tex>
К сожалению, этот функционал дискретный (в него входят индикаторы), поэтому не получится невозможно его минимизировать непосредственно его. Однако можно действовать так же, как и с классификаторами: оценить функционал
сверху.
<tex>\sum_{x_i < x_j} L(a(x_j) - a(x_i)) \rightarrow min</tex>
Если использовать функцию как в логистической регрессии <tex>L(M) = log(1 + e^{−M})</tex>, то полученный метод называется RankNet. Затем можно решать задачу, например, с помощью [[Стохастический градиентный спуск|стохастического градиентного спуска]].
===Listwise-Списочный подход===
В методе RankNet шаг стохастического градиентного спуска для линейной модели выглядит следующим
<tex>\omega := \omega + \eta {{\large 1} \over {\large 1 + exp(\langle \omega, x_j - x_i \rangle)}} (x_j - x_i)</tex>
<tex>\omega := \omega + \eta {{\large 1} \over {\large 1 + exp(\langle \omega, x_j - x_i \rangle)}} (x_j - x_i) |\Delta nDCG_{ij}| (x_j - x_i)</tex>
Оказывается, что при выполнении градиентного спуска с помощью данных шагов оптимизируется nDCG. Существуют и другие подходы к оптимизации nDCG, однако в них предпринимается попытка работы сфункционалом, что гораздо сложнее. Выше описан самый простой подход, он называется LambdaRank == См. также ==* [[Общие понятия|Общие понятия]]* [[Стохастический градиентный спуск|Стохастический градиентный спуск]]* [[Рекомендательные системы|Рекомендательные системы]]<sup>[на 17.03.19 не создан]</sup> == Примечания ==<references/>
== Источники информации ==
# [http://www.machinelearning.ru/wiki/images/8/89/Voron-ML-Ranking-slides.pdf?title=Rank Обучение ранжировнию] {{---}} статья на machinelearning.ru
# [https://www.coursera.org/lecture/text-retrieval/lesson-6-1-learning-to-rank-part-1-mFYTD Learning to rank] {{---}} презентация на coursera.org
# [http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_(%D0%BA%D1%83%D1%80%D1%81_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D0%B9%2C_%D0%9A.%D0%92.%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D1%86%D0%BE%D0%B2) Курс лекций по машинному обучению] {{---}} Воронцов К.В.
[[Категория: Машинное обучение]]
