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

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

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

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

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

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

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

Существует два основных способа получения :

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

2. На основе экспертной оценки. Например, в задаче поиска, для каждого запроса можно привлечь команду асессоров, которые вручную оценят релевантности документов запросу.

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

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

Mean average precision

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

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

Precision at K

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

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

Average precision at K

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

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

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

Теперь и 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

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

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

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

Discounted Cumulative Gain at K

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

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

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

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

Normalized Discounted Cumulative Gain at K

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

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

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

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

Mean reciprocal rank

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Expected reciprocal rank

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

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

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

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

В общем же случае чаще всего используют следующую формулу:

PFound

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

где

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

В заключении приведем несколько полезных ссылок по теме:

— Статьи на википедии по: обучению ранжированию, MRR, MAP и nDCG.

— Официальный список метрик используемых на РОМИП 2010.

— Описание метрик MAP и nDCG на kaggle. com.

— Оригинальные статьи по каскадной модели, ERR и PFound.

Написано с использованием StackEdit.

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

«поиск» в продукте, часть третья — Сервисы на vc.ru

Привет! Я Женя Гурьянов, Chief Product Officer в компании DocDoc. В своих статьях я рассказываю, как внедрять и развивать «поиск» в продуктах. В этой статье я расскажу о метриках поисковой выдачи, а также о том, как можно проверить, что вы не придумали ерунды: офлайн- и онлайн-оценки поисковой выдачи.

6254
просмотров

В первой статье я рассказывал про то, как наполнять бэклог развития «поиска» в продукте и как приоритизировать поисковые задачи.

• Что такое релевантность?
• Как построить поиск книг в электронной библиотеке?
• Как построить поиск объявлений в онлайн-классифайде?

Итак, теперь к статье.

Метрики поисковой выдачи

Допустим, у вас уже есть поисковая выдача. Вы хотите понимать, ведут ли изменения алгоритма ранжирования к успеху или только ухудшают ситуацию?

Давайте разобьём метрики на две группы: поисковые и бизнесовые (разделение больше формальное).

Поисковые, кликовые метрики

[email protected] — это отношениеколичества выдач, в которых был хотя бы один клик в первые N позиций в выдаче, к количеству всех выдач. Измеряется в процентах.

Давайте поясню формулой для [email protected]

Чем выше CTR, тем лучше

Average Highest Click (AHC)

Средняя позиция клика в выдаче (если пользователь сделал несколько кликов в конкретной выдаче, то выбирается наивысший клик).

Пример: у вас три кликнутых выдачи, клики были на второй, шестой и первой позициях. Подсчёт: AHC = (2 + 6 + 1) / 3 = 3.

То есть средняя позиция наивысшего клика в нашем примере — третья. Очевидно, что кейс идеальной выдачи, это когда пользователи кликают на первую позицию в выдаче (AHC = 1).

Важно: чем меньше Average Highest Click, тем лучше.

Доля кликнутых выдач

Отношение количества всех выдач, в которых был хотя бы один клик на сниппет, к количеству всех выдач.

Также важно учитывать две следующие метрики:

1. Доля нулевых выдач: отношение количества выдач, в которых не было ни одного найденного документа, к количеству всех выдач.
2. Доля малых выдач: если вам важно давать пользователю большой ассортимент товаров, услуг или предоставлять большой выбор поставщиков, полезно будет смотреть на данную метрику. Для различных продуктов малая выдача может определяться по-разному. Давайте для примера определим её как выдачу, в которой найдено не более пяти документов.

Формула расчёта доли

Бизнес-метрики

Скорее всего, вы работаете над поисковой выдачей не просто в отрыве от бизнеса, а для достижения конкретных целей. Понятно, что финальной целью функционирования бизнеса будут деньги. Но не всегда можно напрямую завязаться на деньги. Рассмотрим пару примеров бизнес-метрик.

Классифайды: «Юла», Avito

Если не принимать в расчёт рекламу на сайтах, то основные деньги приносят продавцы (они платят за поднятия объявлений, премиум-размещения), но поисковая выдача напрямую влияет на покупателей.

Поэтому сложно привязать рост выручки непосредственно к изменению алгоритма работы поисковой выдачи (особенно в A/B- тесте). И поэтому вполне нормальным было бы привязать успех к количеству контактов или количеству покупателей в продукте.

Логика следующая: становится больше покупателей (можно проверять в разрезах: все объявления, платные объявления) → становится больше сделок → продавцы более мотивированы размещать товары и платить за рекламу.

Социальные сети: Facebook, «ВКонтакте», Linkedin и другие

Обычно на вершине иерархии метрик для соцсетей стоит время, в среднем проводимое пользователем в соцсети за день (timespent).

Далее метрики каскадируются. Давайте поговорим, например, про поиск людей или друзей. Как оценивать работу поисковой выдачи? Вполне резонный ответ — по количеству добавленных в друзья.

Логика следующая: чем больше у пользователя друзей в соцсети, тем больше он зависит от неё и больше проводит там времени. Рост количества друзей → рост timespent-показателя.

DocDoc

Деньги DocDoc приносит запись к врачу. До записи есть ещё заявка на запись. Поэтому, казалось бы, для измерения «хорошести» алгоритма поисковой выдачи можно использовать метрику «количество заявок или записей». Но не тут то было.

В реальности всё сложнее: разные клиники могут предоставлять разный чек для записи к разным врачам. Соответственно, даже при увеличении количества записей выручка может уменьшиться. В этом случае завязывать успех надо на выручку.

Ловушки метрик ускорения поиска пользователя

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

• Количество шагов до целевого действия.
• Время до целевого действия.

Кажется, что при уменьшении этих метрик счастье пользователя должно расти. На самом деле не всегда. Рассмотрим это на примере классифайда.

Целевым действием пользователя считаем первый контакт в день в конкретной категории (собственно, тогда можно считать пользователя покупателем в конкретной категории). Мы пытаемся сократить время или количество действий до первого контакта.

В одной из статей, написанной ранее, я предлагал потенциальную доработку в Avito и «Юле» — пробрасывать пользователя при конкретном запросе марки и модели авто в нужную ему категорию. В примере был запрос «шевроле траверс».

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

• Если проброса нет, пользователь после текстового поиска видит объявления, выданные ему по всем категориям. Он не провалился в категорию «Автомобили», соответственно не видит фильтры (цена, тип автомобиля, год выпуска). Пользователь вынужден выбирать из предложенных объявлений и, чтобы уточнить информацию, входит внутрь объявлений и по некоторым из них делает контакты.

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

Время до первого контакта растёт, число действий также растёт (пользователь прокликивает фильтры). Итого: пользователь ищет дольше. Но больше пользователей делают контакт, и контактов на пользователя становится больше.

То есть в примере замедление совершения первого целевого действия не снижает счастье пользователя, а напротив, увеличивает его.

Ну и не забываем про скорость работы поисковой выдачи

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

Важно следить не только за метриками, которые были описаны выше, но и за скоростью работы выдачи.

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

Вы можете проверить, насколько скорость отображения выдачи влияет на метрики продукта, просто проведя ухудшающий А/B-тест (искусственно замедлив выдачу в тестовой группе). При этом важно понимать, что функция влияния скорости отображения выдачи на продуктовые метрики может отличаться в различных диапазонах скорости выдачи.

Как понять, что вы не придумали ерунду

Теперь перейдём к более подробному ответу на вопрос, как оценивать эффективность работы алгоритма поисковой выдачи и как сравнивать два алгоритма между собой.

Есть офлайн- и онлайн-оценка работы алгоритмов.

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

Офлайн-оценка поисковой выдачи

Документы

Вы фиксируете набор документов(слепок документов), на которых будете обучать и оценивать ваш алгоритм ранжирования.

• В задаче поиска книг в электронной библиотеке — список книг в конкретный момент времени (со всей доступной по ним информацией).
• В задаче для классифайда (Avito, «Юла») — набор объявлений на конкретную дату.
• В задаче ранжирования докторов на сайте DocDoc — данные об анкетах врачей.

Запросы

На каких запросах оценивать качество работы поиска. Очевидно, что не на всех, которые вбивали пользователи за последние два года.

Нужна выборка запросов для оценки. Для начала я советую не париться и выбрать запросы для оценки из базы случайно. Например, вынуть из всей базы с запросами пользователей 1000 запросов для оценки. В них будет представлена голова и хвост.

Хороший вопрос — за какой период выбирать запросы?

Ответ зависит от продукта:

• С одной стороны, для получения самых актуальных данных надо выбирать запросы за последнее время (например, за месяц).
• С другой стороны, для учёта сезонности хорошо бы выбрать запросы за весь год: люди ищут разные вещи, например, зимой и летом (тогда и слепок базы надо будет подгонять под сезонность).

Поэтому если в поиске продукта нет сезонности или она слабая, можно брать наиболее актуальные данные — за месяц.

Если в продукте есть сезонность (например, классифайд), то в идеале её стоит учитывать. В выборку могут попасть такие сезонные запросы, как «дома под ключ», «лыжи», «детские самокаты».

Оценщики или асессоры

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

Откуда взять этих асессоров?

Во-первых, те люди, которые работают над улучшением поиска, должны понимать, как и что ищут пользователи (в первую очередь понимание должно быть у продакт-менеджера).

Во-вторых, при работе над поисковыми алгоритмами вам понадобится оценить огромное количество документов по различным запросам, поэтому на помощь приходит «Яндекс.Толока». В неё вы сможете загрузить свои задания и подобрать асессоров, которые быстро дадут вам столь необходимые данные.

Далее я хочу рассмотреть два подхода к офлайн-оценке: поточечный (pointwise approach) и попарный (pairwise approach).

Поточечный подход

Оценки

В данном подходе каждой паре «запрос пользователя — выданный документ» поставлена в соответствие числовая оценка. Один из подходов к варианту оценки:

• 0 — этот документ для меня не релевантен (это не то, чего я хотел).
• 1 — релевантный документ (более-менее ОК).
• 2 — очень релевантный документ (прямо в точку!).

Как только мы определились с оценками, запросами и корпусом документов, на котором будем оценивать релевантность, можно делать первые подходы к получению оценок.

Чтобы стало ещё понятнее, давайте разберём на примере «Юлы». Пользователь ищет услуги ремонта для смартфона. Есть вероятность, что у него что-то с экраном телефона (но это не точно).

Вводим запрос «ремонт samsung galaxy s5»

Предположим, наш алгоритм выбрал и отранжировал из базы объявлений следующие:

Привожу пример объявлений с прода

Я немного поработал асессором и проставил оценки (красным цветом). К сожалению, я посчитал, что в выдаче не было ни одной «двойки», но и такое бывает.

Надеюсь, стало понятнее, что означают оценки и как они расставляются. Допустим, вы получили оценки для всех пар «запрос — документы». Идём дальше.

Офлайн — метрики качества ранжирования

Есть несколько метрик качества ранжирования. Перечислю для наиболее пытливых читателей: DCG, NDCG, MAP, [email protected], [email protected], pFound (подробнее в статье на «Википедии»).

Для общего понимания я бы остановился на NDCG (Normalized Discounted Cumulative Gain.). Да и то с целью качественно пояснить, как работает и рассчитывается данная метрика.

Допустим, что на запрос X алгоритм вернул выдачу, результаты которой оценены асессорами следующим образом:

• Первый документ — 0 (не релевантен).
• Второй документ — 2 (прямо в точку).
• Третий документ — 0 (не релевантен).
• Четвёртый документ — 1 (более-менее релевантен).
• Пятый документ — 1 (более-менее релевантен).
• Шестой документ — 2 (прямо в точку).
• Седьмой документ — 0 (не релевантен).
• Восьмой документ — 0 (не релевантен).
• Девятый документ — 1 (более-менее релевантен).
• Десятый документ — 0 (не релевантен).

Для примера рассмотрим десять первых результатов. Будем рассчитывать [email protected]

Очевидно, что идеальный порядок тех же документов в выдаче выглядит следующим образом (чем релевантнее, тем выше). Это идеальная выдача:

• Второй документ — 2 (прямо в точку).
• Шестой документ — 2 (прямо в точку).
• Четвёртый документ — 1 (более-менее релевантен).
• Пятый документ — 1 (более-менее релевантен).
• Девятый документ — 1 (более-менее релевантен).
• Оставшиеся пять нерелевантных документов.

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

Для этого я вас проведу по вычислениям cumulative gain (CG), discounted cumulative gain (DCG) и [email protected]

Первый показатель — просто сумма всех десяти оценок ([email protected] = 0 + 2 + 0 + 1 + 1 + 2 + 0 + 0 + 1 + 0 = 7)

При последующем подсчёте учитывается принцип «пользователи просматривают документы сверху вниз».

Также пользователи зачастую нетерпеливые и могут не дойти до документов в нижней части выдачи. Поэтому вводятся веса для учёта положения документа в выдаче. Чем ниже релевантный документ в выдаче, тем ниже у него вес. Итак, чем выше сниппет, тем лучше.

Таким образом подсчитываем то, что называется DCG.

Для нашего примера [email protected] равен 3,093

Для идеальной выдачи DCG равен 4,579

Тогда [email protected] равен 0,675 (3,093 ÷ 4,579).

Очевидно, что максимально достижимый nDCG равен единице (если бы наша выдача совпадала с идеальной). Поэтому тот nDCG, который мы получили, — некая мера того, насколько мы приблизились к идеальной выдаче.

На этом мы закончили рассмотрение поточечного подхода к оценке нашей выдачи. Перейдём к краткому рассмотрению попарного подхода.

Попарный подход

В поточечном подходе каждому документу в выдаче мы выставляли одну из трёх цифр для оценки (0, 1, 2). Но в таком подходе есть две проблемы:

1. Сложно понять «правильную» позицию документа в выдаче по отношению к другим документам с той же оценкой (как должны располагаться два документа с «единичной» оценкой относительно друг друга?).
2. Асессорам сложно проставлять какую-то абсолютную оценку (например, в некоторых случаях сложно выбрать между единицей и двойкой).

Для более точного оценивания и решения вышеописанных проблем используется попарный подход к оценке.

Пример задания для попарного сравнения сниппетов по запросу «дерматолог» в DocDoc.  Сравнивается именно желание записаться на приём к конкретному дерматологу (правому или левому).

После достаточно большого количества попарных сравнений можно определить точнее идеальный порядок врачей в выдаче.

Нюансы работы с асессорами

В наш самый первый подход к «Толоке» мы не стали заморачиваться на долгой подготовке инструкции и контрольных заданий (golden dataset) для асессоров. Мы запустили небольшую порцию заданий на асессоров и затем руками проверили качество ответов (некое MVP). Результат оказался печальным. Зато задания были выполнены практически мгновенно 🙂

Почему это происходит? Мы сталкивались с двумя проблемами:

1. Асессоры не понимают задание, которое необходимо выполнить.
2. Некоторые асессоры могут обманывать, намеренно прокликивать случайные ответы в тесте.

Нам пришлось провести ещё пару итераций работы над системой контроля качества, чтобы добиться необходимого уровня качества ответов.

Над чем я рекомендую поработать:

• Обязательно подготовьте инструкцию и обучающий пулзаданий. Для начала мы тестировали эти артефакты на коллегах (скажем, из бухгалтерии). Был создан некий цикл: прохождение обучения, сбор фидбэка, доработка, затем опять прохождение обучения и по кругу.
• Разработайте пул контрольных заданий. Пример контрольного вопроса для выдачи классифайда — запрос «samsung galaxy s8», а на сниппете — iPhone 8. Если асессор отвечает, что объявление релевантно, тут явно что-то не то. Наличие подобных контрольных вопросов поможет вам сильно сократить асессорский фрод.
• Запускайте выполнение заданий с перекрытием. Например, вы можете задать следующее условие: на каждое задание нужно получить ответ от пяти асессоров. Правильным можете считать, например, мнение большинства (то есть одинаковый ответ как минимум от трёх асессоров в случае с пятикратным перекрытием).

Если вы решите работать для оценки заданий с «Толокой», то подробнее про настройку работы с качеством можно почитать в разделе «Контроль качества».

Онлайн-оценка поисковой выдачи

Допустим, что мы протестировали наш новый алгоритм в офлайне и теперь готовы тестировать на реальных пользователях.

Как измерить результат вашей работы в онлайне? Тут нам помогут старые-добрые А/B-тесты. Разбиваем пользователей на две группы:

1. Контрольная группа видит результаты работы старого алгоритма.
2. Тестовая — нового (тестируемого).

В одном из предыдущих разделов я рассказывал про метрики поисковой выдачи.

При онлайн-оценке поиска прежде всего нужно смотреть на бизнес-метрики.

Они могут могут отличаться у разных продуктов.

Примеры:

• Классифайды(«Юла», Avito) — количество контактов, сделок.
• Социальные сети (поиск друзей) — количество пользователей, добавленных в друзья.
• DocDoc(поиск врачей) — выручка, количество записей.

Далее смотрим на кликовые метрики: [email protected], [email protected], Average Highest Click, долю кликнутых выдач, долю нулевых выдач.

Вместе с аналитиками делаем выводы и не забываем про проверку статистической значимости результатов.

Бонус: пользователи не всегда знают, чего хотят

Есть нюанс, который сложно проверить при офлайн-оценке качества работы алгоритма: реальные люди часто не знают, чего именно хотят и на что готовы согласиться, если им предложат. Умение видеть такие моменты в выдаче приходит с опытом, а также выявляется на пользовательских интервью. Тестируется же на реальных пользователях.

Например. Пользователь ищет на «Юле» «чёрный iPhone 8». Вдруг среди чёрных iPhone в выдаче пользователь видит белый iPhone 8, но дешёвый, в хорошем состоянии да ещё и в соседнем доме. Пользователь заходит в объявление и покупает товар.

С одной стороны, объявление формально было нерелевантно запросу и асессоры бы отсекли его из выдачи, но в реальности такие вкрапления могут быть очень полезны для пользователей.

Как находить такие вкрапления

Смотрим на то, какие факторы влияют на выбор товара пользователем, смотрим на товары субституты. Например:

• Тип, вид, марка, модель товара. Пользователь, который ищет одну марку и модель авто, потенциально готов рассмотреть марку или модель того же класса, но в том же диапазоне цен.
• Цвет товара.
• Состояние товара — новый или почти новый.
• Геопозиция.
• Стоимость товара.

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

В своей следующей статье я опишу работу над формированием поисковой выдачи врачей в DocDoc. Мы пройдём весь продуктовый путь — от приоритизации доработки до проверки придуманного нами решения!

Метрики оценки ранжирования для рекомендательных систем | by Benjamin Wang

Для оценки эффективности рекомендателя используются различные показатели.

Мы сосредоточимся в основном на показателях, связанных с ранжированием, включая HR (коэффициент попаданий), MRR (средний взаимный ранг), MAP (средняя средняя точность), NDCG (нормализованный дисконтированный кумулятивный прирост).

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

В настройках рекомендателя коэффициент попаданий — это просто доля пользователей, для которых правильный ответ включен в рекомендательный список длиной L.

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

MRR — это сокращение от среднего обратного ранга. Он также известен как средний взаимный коэффициент попаданий (ARHR).

Обратите внимание, что существуют различные варианты или упрощения для расчета RR(u) . Для неявного набора данных показатель релевантности равен 0 или 1 для элементов, которые не были куплены или куплены (не нажаты или не нажаты и т. д.).

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

Можно утверждать, что коэффициент попаданий на самом деле является частным случаем MRR, когда RR(u) является двоичным, так как становится равным 1, если в списке есть соответствующий элемент, и 0 в противном случае.

Давайте сначала освежим нашу память о точности и отзыве, особенно в области информационного поиска.

Что такое точность и полнота?

Короче говоря, точность — это доля релевантных элементов во всех извлеченных элементах. Он используется для ответа на вопрос, сколько пунктов среди всех рекомендаций верны.

А отзыв — это доля релевантных элементов во всех соответствующих элементах. Это должно ответить на вопрос охвата, среди всех тех элементов, которые считаются релевантными, сколько отражено в рекомендациях.

Точность из ВикипедииОтзыв из Википедии

Что такое точность@k?

Опираясь на него, мы также можем определить precison@k и Recall@k аналогичным образом. Precision@k будет долей релевантных элементов в топ-k рекомендаций, а отзыв@k будет охватом релевантных моментов времени в топ-k.

Что такое средняя средняя точность?

Теперь вернемся к карте.

MAP — это среднее значение средней точности. Если у нас есть точка доступа для каждого пользователя, достаточно просто усреднить ее по всем пользователям для расчета MAP.

Вычисляя точность и полноту в каждой позиции ранжированной последовательности документов, можно построить кривую точность-полнота, отображающую точность p(r) как функцию полноты r . Средняя точность вычисляет среднее значение p(r) в интервале от 0 до 1.

Это важная область под кривой точности-отзыва. Дискретным способом его можно рассчитать следующим образом:

Наконец, мы можем рассчитать MAP, который представляет собой просто среднее значение AP для всех пользователей.

NDCG означает нормализованную дисконтированную совокупную прибыль. Мы построим эту концепцию в обратном порядке, отвечая на следующие вопросы:

• Что такое усиление?
• Что такое кумулятивный выигрыш?
• Как сделать скидку?
• Как нормализовать?

Прирост для элемента, по сути, такой же, как показатель релевантности, который может быть числовым рейтингом, как результаты поиска в Google, которые могут быть оценены по шкале от 1 до 5, или двоичным в случае неявных данных, о которых мы знаем только если пользователь потреблял определенный элемент или нет.

Естественно кумулятивный прирост определяется как сумма прироста до позиции k в списке рекомендаций

Одним из очевидных недостатков CG является то, что он не учитывает заказ . Поменяв относительный порядок любых двух элементов, компьютерная графика не пострадает. Это проблематично, когда важен порядок ранжирования. Например, в результатах поиска Google вы, очевидно, не хотели бы размещать наиболее релевантную веб-страницу внизу.

Чтобы наказать наиболее релевантные элементы, помещаемые внизу, мы вводим DCG

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

У оценки DCG все еще есть недостаток. Это то, что оценка DCG складывается с длиной списка рекомендаций. Таким образом, мы не можем постоянно сравнивать оценку DCG для системы, рекомендующей 5 лучших и 10 лучших элементов, потому что последний будет иметь более высокий балл не из-за качества рекомендации, а из-за чистой длины.

Мы решили эту проблему, представив IDCG (идеальный DCG). IDCG — это оценка DCG для наиболее идеального рейтинга, который ранжирует элементы сверху вниз в соответствии с их релевантностью до позиции 9.0009 к .

И NDCG просто нормализует показатель DCG с помощью IDCG, чтобы его значение всегда было между 0 и 1, независимо от длины.

1. Википедия по NDCG довольно хороша: https://en.wikipedia.org/wiki/Discounted_cumulative_gain
2. В Википедии есть очень хороший список показателей оценки, используемых в IR: https://en.wikipedia.org/w/ index.php?title=Information_retrieval&oldid=793358396#Average_precision
3. В этой статье очень хорошо объясняется MAP как в ИК, так и в обнаружении объектов: https://towardsdatascience.com/breaking-down-mean-average-precision-map-ae462f623a52

20 популярных показателей машинного обучения. Часть 2: Рейтинг и статистические показатели | Шервин Минаи

Краткое введение в наиболее важные метрики, используемые в машинном обучении для оценки классификации, регрессии, ранжирования, статистики, видения, НЛП и моделей глубокого обучения

Фото Дэна Фримена на Unsplash

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

• Mean reciprocal rank (MRR)
• Precision at k
• DCG and NDCG (normalized discounted cumulative gain)
• Pearson correlation coefficient
• Coefficient of determination (R²)

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

• Рекомендация фильма (как в Netflix , и YouTube ),
• Рейтинг страницы на Google ,
• Рейтинг E-Commerce Products на Amazon ,
• Query Auto-Com-Com-Com-Com-COMO-COMO-COMO-COMO-COMO-COMO-COMO-COMO-COMO-CORY-CORY-COMO-COMOM. на vimeo ,
• Поиск отеля на Expedia / Бронирование .

При обучении задаче ранжирования модель пытается предсказать ранг (или относительный порядок) списка элементов для данной задачи¹. Алгоритмы для задачи ранжирования можно разделить на:

• Точечные модели: , которые пытаются предсказать (совпадающую) оценку для каждой пары запрос-документ в наборе данных и используют ее для ранжирования элементов.
• Парные модели : которые пытаются изучить двоичный классификатор, который может сказать, какой документ более релевантен запросу, учитывая пару документов.
• Списковые модели : которые пытаются напрямую оптимизировать значение одной из вышеуказанных мер оценки, усредненное по всем запросам в обучающих данных.

Во время оценки, учитывая истинный порядок списка элементов для нескольких запросов, мы хотим знать, насколько хорош предсказанный порядок этих элементов списка.

There are various metrics proposed for evaluating ranking problems, such as:

• MRR
• Precision@ K
• DCG & NDCG
• MAP
• Kendall’s tau
• Spearman’s rho

In this post, we focus on первые 3 метрики выше, которые являются наиболее популярными метриками для проблемы ранжирования.

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

11- MRR

Средний взаимный ранг (MRR) — один из самых простых показателей для оценки моделей ранжирования. По сути, MRR представляет собой среднее обратных рангов «первого релевантного элемента» для набора запросов Q и определяется как:

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

MRR этой системы можно найти как:

MRR= 1/3*(1/2+1/3+1/1)= 11/18

Одним из ограничений MRR является то, что он принимает во внимание только ранг одного из элементов (наиболее релевантного) и игнорирует другие элементы (например, средства массовой информации, поскольку форма множественного числа среды игнорируется). Это может быть плохой метрикой для случаев, когда мы хотим просмотреть список связанных элементов.

12- Точность при k

Точность при k (P@k) — еще одна популярная метрика, которая определяется как «количество релевантных документов среди k лучших документов»:

Например, если вы ищете в Google «дезинфицирующее средство для рук» и на первой странице 8 из 10 ссылок относятся к дезинфицирующему средству для рук, то P@10 для этого запроса будет равен 0,8.

Теперь, чтобы найти точность при k для набора запросов Q, вы можете найти среднее значение P@k для всех запросов в Q.

P@k имеет несколько ограничений. Самое главное, что он не учитывает позиции соответствующих документов среди k лучших. Кроме того, в этом случае легко оценить модель вручную, поскольку необходимо проверить только первые k результатов, чтобы определить, релевантны они или нет.

Обратите внимание, что еще одна популярная метрика — Recall@k, которую можно определить очень похожим образом.

13- DCG и NDCG

Нормализованный дисконтированный кумулятивный выигрыш (NDCG), пожалуй, самый популярный показатель для оценки обучения системам ранжирования. В отличие от предыдущих показателей, NDCG принимает во внимание порядок и относительную важность документов, а также ценит высокорелевантные документы, помещая их на первое место в рекомендуемых списках.

Прежде чем дать официальное определение NDCG, давайте сначала представим два соответствующих показателя: кумулятивный прирост (CG) и дисконтированный кумулятивный прирост (DCG).

Совокупный выигрыш (CG) набора извлеченных документов представляет собой сумму оценок их релевантности запросу и определяется, как показано ниже.

Здесь мы предполагаем, что оценка релевантности каждого документа запросу задана (в противном случае она обычно устанавливается на постоянное значение)

Дисконтированная совокупная прибыль (DCG) Понижающий коэффициент используется для дисконтирования оценок релевантности пропорционально положению результатов. Это полезно, так как на практике мы хотим дать более высокий приоритет первым нескольким элементам (чем более поздним) при анализе производительности системы. DCG определяется как:

Существует также другая версия

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

, где IDCG — это «идеальный дисконтированный кумулятивный прирост», определяемый следующим образом:

NDCG — популярный показатель, но он также имеет свои ограничения. Одно из его основных ограничений заключается в том, что он не наказывает результат за плохие документы. Это может быть неприемлемо для измерения производительности запросов, которые часто могут иметь несколько одинаково хороших результатов (особенно верно, когда нас в основном интересуют первые несколько результатов, как это делается на практике).

Хотя можно думать о машинном обучении как о прикладной статистике и, следовательно, считать все показатели ML как своего рода статистические показатели, есть несколько показателей, которые в основном используются статистиками для оценки производительности статистических моделей. Некоторые из популярных метрик здесь включают: коэффициент корреляции Пирсона, коэффициент детерминации (R²), коэффициент ранговой корреляции Спирмена, p-значение и другие². Здесь мы кратко вводим коэффициент корреляции и R-квадрат.

14- Коэффициент корреляции Пирсона

Коэффициент корреляции Пирсона, пожалуй, один из самых популярных показателей во всей области статистики и машинного обучения. Его применение настолько широко, что используется практически во всех аспектах статистического моделирования, от выбора признаков и уменьшения размерности до регуляризации и оценки модели и т. д.³.

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

Коэффициент линейной корреляции двух случайных величин X и Y определяется следующим образом:

Здесь \mu и \sigma обозначают среднее и стандартное отклонение каждой переменной соответственно.

В большинстве случаев лежащее в основе статистическое распределение переменных неизвестно, и все, что у нас есть, — это выборка N этой случайной величины (вы можете думать об этом как о N-мерном векторе). В этих случаях мы можем использовать коэффициент корреляции Sample двух N-мерных векторов X и Y, как показано ниже:

Коэффициент корреляции двух переменных всегда представляет собой значение в [-1,1] .
Известно, что две переменные независимы тогда и только тогда, когда их корреляция равна 0 .

15- Коэффициент детерминации (R²)

Коэффициент детерминации или R² формально определяется как доля дисперсии зависимой переменной, которую можно предсказать по независимой(ым) переменной(ям).

Чтобы лучше понять, что это значит, предположим, что в наборе данных есть N выборок с соответствующими целевыми значениями y_1, y_2, …, y_N. Предположим, что соответствующие предсказанные значения этих выборок нашей моделью имеют значения f_1, f_2, …, f_N.

Теперь мы можем определить следующие термины, которые будут использоваться для расчета R²:

• среднее значение наблюдаемых данных :

• общая сумма квадратов (пропорциональная дисперсии данных) :

• Сумма квадратов остатков, также называемая суммой квадратов остатков :

Тогда наиболее общее определение R² можно записать следующим образом:

В лучшем случае смоделированные значения точно совпадают наблюдаемые значения, что приводит к R²=1 .

This entry was posted in Популярное