44
правки
Изменения
Новая страница: «==Постановка задачи== <tex>x_1 \ldots x_l</tex> – выборка, состоящая из <tex>l</tex> элементов. Она состоит…»
==Постановка задачи==
<tex>x_1 \ldots x_l</tex> – выборка, состоящая из <tex>l</tex> элементов. Она состоит из объектов, имеющих признаковое описание, как и в задачах регрессии и классификации.
Ключевое отличие ранжирования заключается в целевой переменной. Если ранее в задачах обучения с учителем каждому объекту соответствовал свой ответ, то теперь ответы — это пары вида: <tex>\{ (i, j) : x_i \lt x_j\} </tex>. Набор таких пар и есть целевая переменная.
Основная задача – построить ранжирующую модель <tex>a(x)</tex>, такую, что: <tex>\{ x_i \lt x_j \Rightarrow a(x_i) \lt a(x_j) \}</tex>
Таким образом, по выходам необходимо восстановить порядок, а величина ответов не имеет значения. В этом
заключается главное отличие ранжирования от остальных задач машинного обучения.
==Ранжирование поисковой выдачи==
Классическим примером для задачи ранжирования считается ранжирование поисковой выдачи. Далее для понимания материала везде будет рассматриваться данный пример, но все рассуждения хорошо обобщаются и для других применений.
В качестве объектов выступают пары <tex>(запрос, документ)</tex>. Запрос – ключевые слова, введенные пользователем, документ – один из всех документов, имеющихся в поисковой выдаче: <tex>({запрос}, {документ}_1) \lt ({запрос}, {документ}_2) </tex>
==Метрики качества ранжирования==
===Точность ранжирования===
В самой простой постановке задачи ранжирования целевая переменная принимает два значения, документ
либо релевантен запросу, либо нет:
<tex>y(q, d) \in \{0, 1\}, </tex> где <tex>y</tex> – целевая переменная, <tex>q</tex> – запрос, <tex>d</tex> – документ.
Пусть также есть некоторая модель <tex>a(q, d)</tex>, оценивающая релевантность документа запросу. По значениям, полученным с помощью этой модели, можно отранжировать документы. <tex>d^{(i)}_{q}</tex> будет обозначать <tex>i</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</tex>. Однако
у неё есть серьёзный недостаток: позиции релевантных документов никак не учитываются. Например, если
при <tex>k = 10</tex> среди первых <tex>k</tex> документов есть <tex>5</tex> релевантных, то неважно, где они находятся: среди первых
или последних <tex>5</tex> документов. Обычно же хочется, чтобы релевантные документы располагались как можно
выше.
Описанную проблему можно решить, модифицировав метрику, и определить среднюю точность (average
precision, <tex>AP</tex>). Данная метрика тоже измеряется на уровне <tex>k</tex> и вычисляется следующим образом:
<tex>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)})}}</tex>
Данная величина уже зависит от порядка. Она достигает максимума, если все релевантные документы находятся вверху ранжированного списка. Если они смещаются ниже, значение метрики уменьшается.
И точность, и средняя точность вычисляются для конкретного запроса <tex>q</tex>. Если выборка большая и размечена для многих запросов, то значения метрик усредняются по всем запросам:
<tex>MAP@k = {{1}\over{|Q|}} \sum_{q \in Q} AP@k(q)</tex>
<tex>x_1 \ldots x_l</tex> – выборка, состоящая из <tex>l</tex> элементов. Она состоит из объектов, имеющих признаковое описание, как и в задачах регрессии и классификации.
Ключевое отличие ранжирования заключается в целевой переменной. Если ранее в задачах обучения с учителем каждому объекту соответствовал свой ответ, то теперь ответы — это пары вида: <tex>\{ (i, j) : x_i \lt x_j\} </tex>. Набор таких пар и есть целевая переменная.
Основная задача – построить ранжирующую модель <tex>a(x)</tex>, такую, что: <tex>\{ x_i \lt x_j \Rightarrow a(x_i) \lt a(x_j) \}</tex>
Таким образом, по выходам необходимо восстановить порядок, а величина ответов не имеет значения. В этом
заключается главное отличие ранжирования от остальных задач машинного обучения.
==Ранжирование поисковой выдачи==
Классическим примером для задачи ранжирования считается ранжирование поисковой выдачи. Далее для понимания материала везде будет рассматриваться данный пример, но все рассуждения хорошо обобщаются и для других применений.
В качестве объектов выступают пары <tex>(запрос, документ)</tex>. Запрос – ключевые слова, введенные пользователем, документ – один из всех документов, имеющихся в поисковой выдаче: <tex>({запрос}, {документ}_1) \lt ({запрос}, {документ}_2) </tex>
==Метрики качества ранжирования==
===Точность ранжирования===
В самой простой постановке задачи ранжирования целевая переменная принимает два значения, документ
либо релевантен запросу, либо нет:
<tex>y(q, d) \in \{0, 1\}, </tex> где <tex>y</tex> – целевая переменная, <tex>q</tex> – запрос, <tex>d</tex> – документ.
Пусть также есть некоторая модель <tex>a(q, d)</tex>, оценивающая релевантность документа запросу. По значениям, полученным с помощью этой модели, можно отранжировать документы. <tex>d^{(i)}_{q}</tex> будет обозначать <tex>i</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</tex>. Однако
у неё есть серьёзный недостаток: позиции релевантных документов никак не учитываются. Например, если
при <tex>k = 10</tex> среди первых <tex>k</tex> документов есть <tex>5</tex> релевантных, то неважно, где они находятся: среди первых
или последних <tex>5</tex> документов. Обычно же хочется, чтобы релевантные документы располагались как можно
выше.
Описанную проблему можно решить, модифицировав метрику, и определить среднюю точность (average
precision, <tex>AP</tex>). Данная метрика тоже измеряется на уровне <tex>k</tex> и вычисляется следующим образом:
<tex>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)})}}</tex>
Данная величина уже зависит от порядка. Она достигает максимума, если все релевантные документы находятся вверху ранжированного списка. Если они смещаются ниже, значение метрики уменьшается.
И точность, и средняя точность вычисляются для конкретного запроса <tex>q</tex>. Если выборка большая и размечена для многих запросов, то значения метрик усредняются по всем запросам:
<tex>MAP@k = {{1}\over{|Q|}} \sum_{q \in Q} AP@k(q)</tex>
