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

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

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

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

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


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

Формально, рассмотрим 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:

p%40K%20%3D%20%5Cfrac%7B%5Csum_%7Bk%3D1%

Замечание: под 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:

ap%40K%20%3D%20%5Cfrac%7B1%7D%7BK%7D%5Cs


Так, если из трех элементов мы релевантным оказался только находящийся на последнем месте, то 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 для каждого объекта и усреднить:

map%40K%20%3D%20%5Cfrac%7B1%7D%7BN%7D%5C


Замечание: идея эта вполне логична, если предположить, что все пользователи одинаково нужны и одинаково важны. Если же это не так, то вместо простого усреднения можно использовать взвешенное, домножив 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) — базовая метрика ранжирования, которая использует простую идею: чем релевантные элементы в этом топе, тем лучше:

%20CG%40K%20%3D%20%20%5Csum%5Climits_%7B


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

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

Discounted Cumulative Gain at K


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

%20DCG%40K%20%3D%20%20%5Csum%5Climits_%7


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

%20DCG%40K%20%3D%20%20%5Csum%5Climits_%7


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

%5Cfrac%7B1%7D%7B%5Clog_2%281%2B1%29%7D%


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:

%20nDCG%40K%20%3D%20%20%20%5Cfrac%7BDCG%


где 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) — еще одна часто используемая метрика качества ранжирования. Задается она следующей формулой:

MRR%40K%20%3D%20%5Cfrac%7B1%7D%7BN%7D%5C


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

RR%40K%20%3D%20%5Cfrac%7B1%7D%7B%5Cmin%5


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

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


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

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


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

%5Ctau%20%3D%20%20%5Cfrac%7B%28%5Ctext%7


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


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

%20r_%7BS%7D%20%3D%20%5Crho%28%5Cpi%2C%2


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

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

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


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

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

Expected reciprocal rank


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

ERR%40K%20%3D%20%5Cfrac%7B1%7D%7BK%7D%5C


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

P%28%5Ctext%7B%D0%BE%D0%B1%D1%8A%D0%B5%D


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

p_k%20%3D%20r%5E%7Btrue%7D%28%5Cpi%5E%7B


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

p_k%20%3D%20%5Cfrac%7B2%5E%7Br%5E%7Btrue

PFound


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

PFound%40K%20%3D%20%5Csum%20%5Climits_%7


где

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


В заключении приведем несколько полезных ссылок по теме:
— Статьи на википедии по: обучению ранжированию, MRR, MAP и nDCG.
— Официальный список метрик используемых на РОМИП 2010.
— Описание метрик MAP и nDCG на kaggle.com.
— Оригинальные статьи по каскадной модели, ERR и PFound.

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

© Habrahabr.ru