Изменения

<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> { (i{---}} множество документов, j) : x_i \lt x_j\} найденных по запросу <tex>q</tex>. Набор таких пар и есть целевая переменная.

Основная задача – построить ранжирующую модель <tex>a(x)X = Q \times D</tex>{{---}} объектами являются пары (запрос, такую, чтодокумент): <tex>x \{ x_i \lt x_j \Rightarrow aequiv (x_iq, d) , q \lt a(x_j) 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>U</tex> {запрос{---}}пользователи. <tex>I</tex> {{---}} предметы (фильмы, книги и т.д.). <tex>X = U \times I</tex> {{документ---}}_1объектами являются пары (пользователь, предмет). ''Правильный порядок'' определён между предметами, которые выбирал или рейтинговал один и тот же пользователь: <tex>(u, i) \prec (u, i') \lt Leftrightarrow y(u, i) < y(u, i')</tex>. Рекомендация пользователю <tex>u</tex> {{запрос---}} это список предметов <tex>i</tex>, {документ}_2упорядоченный с помощью функции ранжирования <tex>a(u, i) </tex>.

либо релевантен запросу, либо нет:

После того как введены обозначения, можно задать простейшую метрику ранжирования. Это <tex>Precision@k</tex>,

<tex>Precision@k(q) = {{1}\over{k}} \sum_{i = 1}^{k} y(q, d_{q}^{(i)})</tex>.

Это полезная метрика, потому что обычно важно иметь релевантные документы среди первых <tex>k</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>MAP@k = {{1}\over{|Q|}} \sum_{q \in Q} AP@k(q)</tex>. ===Дисконтированный совокупный доход===Второй подход к измерению качества ранжирования — дисконтированный совокупный доход (англ. discounted cumulative gain) или DCG. Ониспользуется в более сложной ситуации, когда оценки релевантности <tex>y</tex> могут быть вещественными: <tex>y(q, d) \in \mathbb{R}</tex>. То есть для каждого документа теперь существует градация между релевантностью и нерелевантностью.Остальные обозначения остаются теми же, что и для предыдущей метрики. Формула для вычисления DCG: <tex>DCG@k(q)= \sum_{i = 1}^{k} {\large {{2^{y(q, d_{q}^{(i)})} - 1} \over {log(i+1)}}}</tex>. Метрика — это сумма дробей. Чем более релевантен документ, тем больше числитель в дроби. Знаменательзависит от позиции документа, он штрафует за то, где находится документ. Если документ очень релевантен,но занимает низкую позицию, то штраф будет большим, если документ релевантен и находится вверху списка,штраф будет маленьким. Таким образом, метрика 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> |} Идеальный порядок оценок релевантности <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>. {| 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>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> |} Итого <tex>nDCG@6 = {{DCG@6} \over {maxDCG@6}} = {{6.861} \over {7.141}} = 0.961</tex>. ==Методы ранжирования== Всего выделяют три подхода к решению задачи ранжирования: поточечный (англ. pointwise), попарный (англ. pairwise), списочный (англ. listwise). Выбор метода зависит от качества ранжирования данных. Теоретически, списочный подход считается наилучшим, однако, на практике, например в Яндексе, лучше всего работает попарный подход. ===Поточечный подход=== Самый простой подход — это поточечный. В нём игнорируется тот факт, что целевая переменная <tex>y(q, d) \in \mathbb{R}</tex> задаётся на парах объектов, и оценка релевантности <tex>a(d, q)</tex> считается для каждого объекта. Если речь идёт о задаче ранжирования поисковой выдачи, то пусть асессор поставил какую-то оценку <tex>y</tex> каждой паре (запрос, документ). Эта оценка и будет предсказываться. При этом никак не учитывается, что нужно предсказать порядок объектов, а не оценки. Этот подход является простым в том смысле, что в нёмиспользуются уже известные методы. Например, можно предсказывать оценки с использованием линейнойрегрессии и квадратичной ошибки: <tex>\sum_{i = 1}^{l} (a(q_i, d_i) - y(q_i, d_i))^2 \rightarrow min</tex> Известно, как решать такую задачу, и таким образом будет получена релевантность. Далее по выходам моделиможно ранжировать объекты. ===Попарный подход=== В попарном подходе используются знания об устройстве целевой переменной. Модель строится сведением к минимуму количества дефектных пар, то есть таких, в которых моделью был предсказан неправильный порядок: <tex>\sum_{x_i < x_j} [a(x_j) - a(x_i) < 0] \rightarrow min</tex> К сожалению, этот функционал дискретный (в него входят индикаторы), поэтому невозможно его минимизировать. Однако можно действовать так же, как и с классификаторами: оценить функционалсверху. Можно считать, что разница между объектами <tex>a(x_j) − a(x_i)</tex> — это отступ <tex>M</tex>, и задать некоторую гладкуюфункцию <tex>L(M)</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. Затем можно решать задачу, например, с помощью [[Стохастический градиентный спуск|стохастического градиентного спуска]]. ===Списочный подход=== В методе RankNet шаг стохастического градиентного спуска для линейной модели выглядит следующимобразом: <tex>\omega := \omega + \eta {{\large 1} \over {\large 1 + exp(\langle \omega, x_j - x_i \rangle)}} (x_j - x_i)</tex> Заметим, что данная формула зависит от одной пары объектов, а также не учитываются зависимости между различными парами. Возникает вопрос, можно ли модифицировать данный метод (а именно формулу шага) так, чтобы минимизировался не исходный функционал, оценивающий долю дефектных пар, а DCG. Действительно, можно домножить градиент исходного функционала на то, насколько изменится nDCG, если поменять местами <tex>x_i</tex> и <tex>x_j</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> Данный метод называется LambdaRank<ref>[https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/MSR-TR-2010-82.pdf From RankNet to LambdaRank {{---}} Christopher J.C. Burges]</ref>.  Оказывается, что при выполнении градиентного спуска с помощью данных шагов оптимизируется nDCG. Существуют и другие подходы к оптимизации nDCG, однако в них предпринимается попытка работы сфункционалом, что гораздо сложнее. == См. также ==* [[Общие понятия|Общие понятия]]* [[Стохастический градиентный спуск|Стохастический градиентный спуск]]* [[Рекомендательные системы|Рекомендательные системы]]^{[на 17.03.19 не создан]} == Примечания ==<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) Курс лекций по машинному обучению] {{---}} Воронцов К.В. [[Категория: Машинное обучение]]