- PVSM.RU - https://www.pvsm.ru -

Метрики качества ранжирования

В процессе подготовки задачи для вступительного испытания на летнюю школу GoTo [1], мы обнаружили, что на русском языке практически отсутствует качественное описание основных метрик ранжирования (задача касалась частного случая задачи ранжирования — построения рекомендательного алгоритма). Мы в E-Contenta [2] активно используем различные метрики ранжирования, поэтому решили исправить это недоразуменее, написав эту статью.

Метрики качества ранжирования

Задача ранжирования сейчас возникает повсюду: сортировка веб-страниц согласно заданному поисковому запросу, персонализация новостной ленты, рекомендации видео, товаров, музыки… Одним словом, тема горячая. Есть даже специальное направление в машинном обучении, которое занимается изучением алгоритмов ранжирования способных самообучаться — обучение ранжированию (learning to rank [3]). Чтобы выбрать из всего многообразия алгоритмов и подходов наилучший, необходимо уметь оценивать их качество количественно. О наиболее распространенных метриках качества ранжирования и пойдет речь далее.

Кратко о задаче ранжирования

Ранжирование — задача сортировки набора элементов из соображения их релевантности. Чаще всего релевантность понимается по отношению к некому объекту. Например, в задаче информационного поиска объект — это запрос, элементы — всевозможные документы (ссылки на них), а релевантность — соответствие документа запросу, в задаче рекомендаций же объект — это пользователь, элементы — тот или иной рекомендуемый контент (товары, видео, музыка), а релевантность — вероятность того, что пользователь воспользуется (купит/лайкнет/просмотрит) данным контентом.

Формально, рассмотрим N объектов inline_formula и M элементов inline_formula. Реузальтат работы алгоритма ранжирования элементов inline_formula для объекта inline_formula — это отображение inline_formula, которое сопоставляет каждому элементу inline_formula вес inline_formula, характеризующей степень релевантности элемента объекту (чем больше вес, тем релевантнее объект). При этом, набор весов inline_formula задает перестановку inline_formula на наборе элементов элементов inline_formula (считаем, что множество элементов упорядоченное) исходя из их сортировки по убыванию веса inline_formula.

Чтобы оценить качество ранжирования, необходимо иметь некоторый «эталон», с которым можно было бы сравнить результаты алгоритма. Рассмотрим inline_formula — эталонную функцию релевантности, характеризующую «настоящую» релевантность элементов для данного объекта (inline_formula — элемент идеально подходит, inline_formula — полностью нерелевантен), а так же соответствующую ей перестановку inline_formula (по убыванию inline_formula).

Существует два основных способа получения inline_formula:
1. На основе исторических данных. Например, в случае рекомендаций контента, можно взять просмотры (лайки, покупки) пользователя и присвоить просмотренным весам соответствующих элементов 1 (inline_formula ), а всем остальным — 0.
2. На основе экспертной оценки. Например, в задаче поиска, для каждого запроса можно привлечь команду асессоров, которые вручную оценят релевантности документов запросу.

Стоит отметить, что когда inline_formula принимает только экстремальные значения: 0 и 1, то престановку inline_formula обычно не рассматривют и учитывают лишь множество релевантных элементов, для которых inline_formula.

Цель метрики качества ранжирования — определить, насколько полученные алгоритмом оценки релевантности inline_formula и соответствующая им перестановка inline_formula соответствуют истинным значениям релевантности inline_formula. Рассмотрим основные метрики.

Mean average precision

Mean average precision at K (map@K) — одна из наиболее часто используемых метрик качества ранжирования. Чтобы разобраться в том, как она работает начнем с «основ».

Замечание: "*precision" метрики используется в бинарных задачах, где inline_formula принимает только два значения: 0 и 1.

Precision at K

Precision at K (p@K) — точность на K элементах — базовая метрика качества ранжирования для одного объекта. Допустим, наш алгоритм ранжирования выдал оценки релевантности для каждого элемента inline_formula. Отобрав среди них первые inline_formula элементов с наибольшим inline_formula можно посчитать долю релевантных. Именно это и делает precision at K:

Метрики качества ранжирования - 30

Замечание: под inline_formula понимается элемент inline_formula, который в результате перестановки inline_formula оказался на inline_formula-ой позиции. Так, inline_formula — элемент с наибольшим inline_formula, inline_formula — элемент со вторым по величине inline_formula и так далее.

Average precision at K

Precision at K — метрика простая для понимания и реализации, но имеет важный недостаток — она не учитывает порядок элементов в «топе». Так, если из десяти элементов мы угадали только один, то не важно на каком месте он был: на первом, или на последнем, — в любом случае inline_formula. При этом очевидно, что первый вариант гораздо лучше.

Этот недостаток нивелирует метрика ранжирования average precision at K (ap@K), которая равна сумме p@k по индексам k от 1 до K только для релевантных элементов, деленому на K:

Метрики качества ранжирования - 40

Так, если из трех элементов мы релевантным оказался только находящийся на последнем месте, то inline_formula, если угадали лишь тот, что был на первом месте, то inline_formula, а если угаданы были все, то inline_formula.

Теперь и map@K нам по зубами.

Mean average precision at K

Mean average precision at K (map@K) — одна из наиболее часто используемых метрик качества ранжирования. В p@K и ap@K качество ранжирования оценивается для отдельно взятого объекта (пользователя, поискового запроса). На практике объектов множество: мы имеем дело с сотнями тысяч пользователей, миллионами поисковых запросов и т.д. Идея map@K заключается в том, чтобы посчитать ap@K для каждого объекта и усреднить:

Метрики качества ранжирования - 44

Замечание: идея эта вполне логична, если предположить, что все пользователи одинаково нужны и одинаково важны. Если же это не так, то вместо простого усреднения можно использовать взвешенное, домножив ap@K каждого объекта на соответствующий его «важности» вес.

Normalized Discounted Cumulative Gain

Normalized discounted cumulative gain (nDCG) — еще одна распространенная метрика качества ранжирования. Как и в случае с map@K, начнем с основ.

Cumulative Gain at K

Вновь рассмотрим один объект и inline_formula элементов с наибольшим inline_formula. Cumulative gain at K (CG@K) — базовая метрика ранжирования, которая использует простую идею: чем релевантные элементы в этом топе, тем лучше:

Метрики качества ранжирования - 47

Эта метрика обладает очевидными недостатками: она не нормализована и не учитывает позицию релевантных элементов.

Заметим, что в отличии от p@K, CG@K может использоваться и в случае небинарных значений эталонной релевантности inline_formula.

Discounted Cumulative Gain at K

Discounted cumulative gain at K (DCG@K) — модификация cumulative gain at K, учитывающая порядок элементов в списке путем домножения релевантности элемента на вес равный обратному логарифму номера позиции:

Метрики качества ранжирования - 49

Замечание: если inline_formula принимает только значения 0 и 1, то inline_formula, и формула принимает более простой вид:

Метрики качества ранжирования - 52

Использование логарифма как функции дисконтирования можно объяснить следующими интуитивными соображениями: с точки зрения ранжирования позиции в начале списка отличаются гораздо сильнее, чем позиции в его конце. Так, в случае поискового движка между позициями 1 и 11 целая пропасть (лишь в нескольких случаях из ста пользователь заходит дальшей первой страницы поисковой выдачи), а между позициями 101 и 111 особой разницы нет — до них мало кто доходит. Эти субъективные соображения прекрасно выражаются с помощью логарифма:

Метрики качества ранжирования - 53

Discounted cumulative gain решает проблему учета позиции релевантных элементов, но лишь усугубляет проблему с отсутствием нормировки: если inline_formula варьируется в пределах inline_formula, то inline_formula уже принимает значения на не совсем понятно отрезке. Решить эту проблему призвана следующая метрика

Normalized Discounted Cumulative Gain at K

Как можно догадаться из названия, normalized discounted cumulative gain at K (nDCG@K) — не что иное, как нормализованная версия DCG@K:

Метрики качества ранжирования - 57

где inline_formula — это максимальное (I — ideal) значение inline_formula. Так как мы договорились, что inline_formula принимает значения в inline_formula, то inline_formula.

Таким образом, inline_formula наследует от inline_formula учет позиции элементов в списке и, при этом принимает значения в диапазоне от 0 до 1.

Замечание: по аналогии с map@K можно посчитать inline_formula, усредненный по всем объектам.

Mean reciprocal rank

Mean reciprocal rank (MRR) — еще одна часто используемая метрика качества ранжирования. Задается она следующей формулой:

Метрики качества ранжирования - 66

где inline_formulareciproсal rank для inline_formula-го объекта — очень простая по своей сути величина, равная обратному ранку первого правильно угаданного элемента.

Метрики качества ранжирования - 69

Mean reciprocal rank изменяется в диапазоне [0,1] и учитывает позицию элементов. К сожалению он делает это только для одного элемента — 1-го верно предсказанного, не обращая внимания на все последующие.

Метрики на основе ранговой корреляции

Отдельно стоит выделить метрики качества ранжирования, основанные на одном из коэффициентов ранговой корреляции. В статистике, ранговый коэффициент корреляции — это коэффициент корреляции [4], который учитывает не сами значения, а лишь их ранг (порядок). Рассмотрим два наиболее распространенных ранговых коэффициента корреляции: коэффициенты Спирмена и Кендэлла.

Ранговый коэффициент корреляции Кендэлла

Первый из них — коэффициент корреляции Кендэлла, который основан на подсчете согласованных
(и несогласованных) пар у перестановок — пар элементов, котором перестановки присвоили одинаковый (разный) порядок:

Метрики качества ранжирования - 70

Ранговый коэффициент корреляции Спирмена

Второй — ранговый коэффициент корреляции Спирмена — по сути является ни чем иным как корреляции Пирсона, посчитанной на значениях рангов. Есть достаточно удобная формула, выражающая его из рангов напрямую:

Метрики качества ранжирования - 71

где inline_formula — коэффициент корреляции Пирсона.

Метрики на основе ранговой корреляции обладают уже известными нам недостатком: они не учитывают позицию элементов (еще хуже чем p@K, т.к. корреляция считается по всем элементам, а не по K элементам с наибольшим рангом). Поэтому на практике используются крайне редко.

Метрики на основе каскадной модели поведения

До этого момента мы не углублялись в то, как пользователь (далее мы рассмотрим частный случай объекта — пользователь) изучает предложенные ему элементы. На самом деле, неявно нами было сделано предположение, что просмотр каждого элемента независим от просмотров других элементов — своего рода «наивность». На практике же, элементы зачастую просматриваются пользователем поочередно, и то, просмотрит ли пользователь следующий элемент, зависит от его удовлетворенности предыдущими. Рассмотрим пример: в ответ на поисковый запрос алгоритм ранжирования предложил пользователю несколько документов. Если документы на позиции 1 и 2 оказались крайне релевантны, то вероятность того, что пользователь просмотрит документ на позиции 3 мала, т.к. он будет вполне удовлетворен первыми двумя.

Подобные модели поведения пользователя, где изучение предложенных ему элементов происходит последовательно и вероятность просмотра элемента зависит от релевантности предыдущих называются каскадными.

Expected reciprocal rank

Expected reciprocal rank (ERR) — пример метрики качества ранжирования, основанной на каскадной модели. Задается она следующей формулой:

Метрики качества ранжирования - 73

где ранг понимается по порядку убывания inline_formula. Самое интересное в этой метрике — вероятности. При их расчете используются предположения каскадной модели:

Метрики качества ранжирования - 75

где inline_formula — вероятность того, что пользователь будет удовлетворен объектом с рангом inline_formula. Эти вероятности считаются на основе значений inline_formula. Так как в нашем случае inline_formula, то можем рассмотреть простой вариант:

Метрики качества ранжирования - 80

который можно прочесть, как: истинная релевантность элемента оказавшегося на позиции inline_formula после сортировки по убыванию inline_formula.
В общем же случае чаще всего используют следующую формулу:

Метрики качества ранжирования - 83

PFound

PFound — метрика качества ранжирования, предложенная нашими соотечественниками [5] и использующая похожую на каскадную модель:

Метрики качества ранжирования - 84

где

  • inline_formula,
  • inline_formula, если inline_formula и 0 иначе,
  • inline_formula — вероятность того, что пользователь прекратит просмотр по внешним причинам.


В заключении приведем несколько полезных ссылок по теме:
— Статьи на википедии по: обучению ранжированию [3], MRR [6], MAP [7] и nDCG [8].
Официальный список метрик [9] используемых на РОМИП 2010.
— Описание метрик MAP [10] и nDCG [11] на kaggle.com.
— Оригинальные статьи по каскадной модели [12], ERR [13] и PFound [5].

Написано с использованием StackEdit [14].
Большое спасибо пользователю SeptiM [15] за восхитительный habratex [16].

Автор: E-Contenta

Источник [17]


Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/matematika/135338

Ссылки в тексте:

[1] летнюю школу GoTo: http://goto.msk.ru/school/

[2] E-Contenta: https://e-contenta.com/ru/

[3] learning to rank: https://en.wikipedia.org/wiki/Learning_to_rank

[4] коэффициент корреляции: https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D1%80%D1%80%D0%B5%D0%BB%D1%8F%D1%86%D0%B8%D1%8F

[5] предложенная нашими соотечественниками: http://romip.ru/romip2009/15_yandex.pdf

[6] MRR: https://en.wikipedia.org/wiki/Mean_reciprocal_rank

[7] MAP: https://en.wikipedia.org/wiki/Information_retrieval#Mean_average_precision

[8] nDCG: https://en.wikipedia.org/wiki/Discounted_cumulative_gain

[9] Официальный список метрик: http://romip.ru/romip2010/20_appendix_a_metrics.pdf

[10] MAP: https://www.kaggle.com/wiki/MeanAveragePrecision

[11] nDCG: https://www.kaggle.com/wiki/NormalizedDiscountedCumulativeGain

[12] каскадной модели: http://www.wsdm2009.org/wsdm2008.org/WSDM2008-papers/p87.pdf

[13] ERR: http://doi.acm.org/10.1145/1645953.1646033

[14] StackEdit: https://stackedit.io/

[15] SeptiM: https://habrahabr.ru/users/SeptiM/

[16] habratex: https://habrahabr.ru/post/263213/

[17] Источник: https://habrahabr.ru/post/303458/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best