В процессе подготовки задачи для вступительного испытания на летнюю школу 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:



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


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


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


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

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


Discounted Cumulative Gain at K


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


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


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


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:


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


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


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


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


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


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


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


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


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


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

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


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


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

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


Expected reciprocal rank


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


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


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


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





PFound


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


где

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




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

Написано с использованием StackEdit.
Большое спасибо пользователю SeptiM за восхитительный habratex.
Поделиться с друзьями
-->

Комментарии (3)


  1. tumbler
    16.06.2016 19:09

    А наши пользователи вводят "конкретная имевшаяся ввиду рыба", потом пролистывают выдачу, на первом месте которой эта самая "конкретная имевшаяся ввиду рыба", эдак, страницы до пятой, и смотрят один ролик. Как объяснить это поведение, кроме как эффектом от подстановки автокомплита (которую пользователь не заметил), мы не придумали.


    1. obus
      16.06.2016 19:27

      Логика есть, главное ее найти. Может дело в многозначности значений?
      А так, во всех метриках в этой статье подразумевается их усреднение по пользователям, за счет чего влияние небольшого числа «нелогичных» пользователей мало заметно.
      P.S. Сервис — tumblr? :)


      1. tumbler
        17.06.2016 15:05

        Возможно, Вы правы. Мы только начали собирать метрики с поиска, так что "усреднение" пока не работает — зато как раз этих "сумасшедших" заметили. Зато, судя по MAP20, качество выдачи тем больше, чем популярнее конкретный запрос. 10% запросов у нас в логах пришли больше чем от 20 уников, и по ним метрика максимальная, а к "уникальным" запросам качество заметно просаживается.
        image
        X — минимальное число уников, спросивших одно и то же; Y — MAP20


        Отсюда встает еще один поведенческий вопрос: а не будет ли определение качества по кликам/покупкам просто следствием того, что переход с 1 на 2 страницу имеет вероятность 50%, с первой на третью — 25%, и т.д? Кстати, а это нормировать как-то можно?


        PS. Нет, не tumblr.