Изменения

Перейти к: навигация, поиск

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

1693 байта добавлено, 14 март
Нет описания правки
'''Ранжирование''' (англ. ''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>\{ (i, j) : x_i \lt x_j\} </tex>. Набор таких пар и есть целевая переменная.'''
Основная задача – построить ранжирующую модель <tex>a(x; w)= \langle x, w \rangle</tex>, такую, что: где <tex>x \{ x_i \lt x_j \Rightarrow amapsto (f_1(x_ix) , \lt aldots, f_n(x_jx) ) \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>U</tex> {запрос{---}} пользователи. <tex>I</tex> {{---}}предметы (фильмы, книги и т.д.). <tex>X = U \times I</tex> {{документ---}}_1объектами являются пары (пользователь, предмет). ''Правильный порядок'' определён между предметами, которые выбирал или рейтинговал один и тот же пользователь: <tex>(u, i) \lt prec (u, i') \Leftrightarrow y(u, i) < y(u, i')</tex>. Рекомендация пользователю <tex>u</tex> {{запрос---}}это список предметов <tex>i</tex>, {документ}_2упорядоченный с помощью функции ранжирования <tex>a(u, i) </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</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:
<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>nDCG@k(q) = {\large {DCG@k(q)} \over {{\large max DCG@k(q)}}}</tex>, где <tex>max DCG@k(q)</tex> — значение DCG при идеальном ранжировании. После нормировки метрика принимает
значения от 0 до 1.
44
правки

Навигация