Показатели MAP и MRR кажутся интуитивно понятными, но они незаметно искажают оценку рейтинга. Вот почему эти метрики вводят в заблуждение — и как лучшие альтернативы это исправляют.
Делиться
Специалисты по ранжированию в поисковой выдаче часто используют средний обратный ранг (MRR) и среднюю точность (MAP) для оценки качества своих позиций. В этой статье мы обсудим, почему MAP и MRR плохо соответствуют современному поведению пользователей в поисковой выдаче. Затем мы рассмотрим две метрики, которые являются лучшими альтернативами MRR и MAP.
Что такое MRR и MAP?
Средний обратный ранг (MRR)
Средний обратный ранг ((MRR)) — это средний ранг, в котором встречается первый релевантный элемент.
$$mathrm{RR} = frac{1}{text{ранг первого релевантного элемента}}$$
В электронной коммерции первым релевантным рейтингом может быть рейтинг первого товара, на который кликнули в ответ на поисковый запрос.
В приведенном выше примере предположим, что соответствующий элемент — это второй элемент. Это означает:
$$mathrm{Взаимный ранг} = frac{1}{2}$$
Обратный ранг рассчитывается для всех запросов в оценочном наборе. Чтобы получить единую метрику для всех запросов, мы берем среднее значение обратных рангов, чтобы получить средний обратный ранг.
$$mathrm{Средний обратный ранг} = frac{1}{N}sum_{i=1}^N {frac{1}{text{Ранг первого релевантного элемента}}}$$
где (N) — количество запросов. Из этого определения видно, что (MRR) фокусируется на получении одного релевантного результата на раннем этапе. Он не измеряет, что происходит после получения первого релевантного результата.
Средняя точность (MAP)
Средняя точность (MAP) измеряет, насколько хорошо система извлекает релевантные элементы и как рано они отображаются. Для начала мы вычисляем среднюю точность (AP) для каждого запроса. Мы определяем AP как
$$mathrm{AP} = frac{1}{|R|}sum_{k=1}^{K}mathrm{Precision@}k cdot mathbf{1}[text{элемент на } k text{ имеет отношение к делу}]$$
где (|R|) — количество релевантных элементов для запроса.
(mathrm{MAP}) — это среднее значение (mathrm{AP}) по всем запросам.
Приведенное выше уравнение выглядит сложным, но на самом деле оно простое. Давайте рассмотрим пример, чтобы разобрать его. Предположим, запрос содержит 3 релевантных элемента, и наша модель предсказывает следующий порядок:
Ранг: 1 2 3 4 5 Предмет: RNRNR
(R = актуально, N = не актуально)
Для вычисления (MAP) мы вычисляем AP в каждой соответствующей позиции :
- @1: Точность = 1/1 = 1,0
- @3: Точность = 2/3 ≈ 0,667
- @5: Точность = 3/5 = 0,6
$$mathrm{AP} = frac{1}{3}(1,0 + 0,667 + 0,6) = 0,756$$
Мы вычисляем вышеуказанное для всех запросов и усредняем их, чтобы получить (MAP). Формула AP состоит из двух важных компонентов:
- Precision@k: Поскольку мы используем Precision, раннее извлечение релевантных элементов приводит к более высоким значениям точности. Если модель ранжирует релевантные элементы позже, Precision@k снижается из-за большего значения k.
- Усреднение точности: Мы усредняем точность по общему количеству релевантных элементов. Если система никогда не извлекает элемент или извлекает его после порогового значения, элемент не вносит никакого вклада в числитель, но продолжает учитываться в знаменателе, что уменьшает (AP) и (MAP).
Почему MAP и MRR вредны для ранжирования в поисковой выдаче
Теперь, когда мы рассмотрели определения, давайте разберемся, почему (MAP) и (MRR) не используются для ранжирования результатов поиска.
Релевантность оценивается по шкале, а не является бинарной.
При вычислении (MRR) мы берем ранг первого релевантного элемента. В (MRR) мы рассматриваем все релевантные элементы одинаково. Не имеет значения, если первым появляется другой релевантный элемент. В действительности, разные элементы, как правило, имеют разную релевантность.
Аналогично, в (MAP) мы используем бинарную релевантность — мы просто ищем следующий релевантный элемент. Опять же, (MAP) не делает различий в оценке релевантности элементов. В реальных случаях релевантность оценивается по шкале, а не является бинарной.
Пункт: 1 2 3 Релевантность: 3 1 0
Методы (MAP) и (MRR) игнорируют качество соответствующего элемента. Они не позволяют количественно оценить релевантность.
Пользователи просматривают несколько результатов.
Это относится, в частности, к (MRR). При вычислении (MRR) мы записываем ранг первого релевантного элемента и игнорируем все, что идет после него. Это может быть хорошо для поиска, вопросов и ответов и т. д. Но это плохо для рекомендаций, поиска товаров и т. д.
В процессе поиска пользователи не останавливаются на первом релевантном результате (за исключением случаев, когда есть только один правильный ответ). Пользователи просматривают множество результатов, которые вносят вклад в общую релевантность поиска.
MAP чрезмерно акцентирует внимание на запоминании.
(MAP) вычисляет
$$mathrm{AP} = frac{1}{|R|}sum_{k=1}^{K}mathrm{Precision@}k cdot mathbf{1}[text{элемент на } k text{ имеет отношение к делу}]$$
В результате каждый релевантный элемент вносит свой вклад в оценку. Отсутствие любого релевантного элемента снижает оценку. Когда пользователи выполняют поиск, они не заинтересованы в поиске всех релевантных элементов. Их интересует поиск нескольких лучших вариантов. Оптимизация (MAP) заставляет модель изучать длинный хвост релевантных элементов, даже если вклад релевантности невелик, и пользователи никогда не прокручивают страницу так далеко. Следовательно, (MAP) чрезмерно акцентирует внимание на полноте.
MAP распадается линейно
Рассмотрим пример ниже. Мы размещаем соответствующий предмет в трех разных местах и вычисляем AP.
| Классифицировать | Precision@k | АП |
|---|---|---|
| 1 | 1/1 = 1,0 | 1.0 |
| 3 | 1/3 ≈ 0,33 | 0,33 |
| 30 | 1/30 ≈ 0,033 | 0,033 |
Результаты AP на 30-м месте выглядят хуже, чем на 3-м, а на 3-м — хуже, чем на 1-м. Оценка AP снижается линейно с повышением ранга. В действительности, разница между 3-м и 30-м местами составляет более чем 10 раз. Это скорее сравнение «видел» и «не видел».
Функция (MAP) чувствительна к позиции, но лишь в незначительной степени . Она не отражает, как поведение пользователя меняется в зависимости от позиции. Функция (MAP) чувствительна к позиции благодаря Precision@k, где снижение с рангом происходит линейно. Это не отражает, как снижается внимание пользователя к результатам поиска.
NDCG и ERR — лучший выбор.
Для ранжирования результатов поиска лучше использовать (NDCG) и (ERR). Они устраняют проблемы, от которых страдают (MRR) и (MAP).
Ожидаемый обратный ранг (ERR)
Ожидаемый обратный ранг ((ERR)) предполагает каскадную модель поведения пользователя, в которой пользователь выполняет следующие действия.
- Просматривает список сверху вниз.
- На каждом ранге (i),
- С вероятностью (R_i) пользователь доволен и прекращает использование сервиса.
- С вероятностью (1- R_i) пользователь продолжает смотреть вперед
Функция (ERR) вычисляет ожидаемый обратный ранг этой позиции остановки , в которой пользователь удовлетворен:
$$mathrm{ERR} = sum_{r=1}^n frac{1}{r} cdot {R}_r cdot prod_{i=1}^{r-1}{1-{R}_i}$$
где (R_i) равно (R_i = frac{2^{l_i}-1}{2^{l_m}}), а (l_m) — максимально возможное значение метки.
Давайте разберемся, чем (ERR) отличается от (MRR).
- В функции (ERR) используется (R_i = frac{2^{l_i}-1}{2^{l_m}}), что представляет собой градуированную релевантность, поэтому результат может частично удовлетворить пользователя.
- Функция (ERR) позволяет нескольким релевантным элементам вносить свой вклад . Ранние высококачественные элементы уменьшают вклад более поздних элементов.
Пример 1
Рассмотрим простой пример, чтобы понять, чем отличаются (ERR) и (MRR).
Рейтинг: 1 2 3 Релевантность: 2 3 0
- (MRR) = 1 (соответствующий элемент находится на первом месте)
- (ERR) =
- (R_1 = {(2^2 – 1)}/{2^3} = {3}/{8})
- (R_2 ={(2^3 – 1)}/{2^3} = {7}/{8})
- (R_3 ={(2^0 – 1)}/{2^3} = 0)
- (ERR = (1/1) cdot R_1 + (1/2) cdot R_2 + (1/3) cdot R_3 = 0.648)
- (MRR) означает идеальный рейтинг . (ERR) означает неидеальный рейтинг , поскольку позже появляется элемент с более высокой релевантностью.
Пример 2
Рассмотрим еще один пример, чтобы увидеть, как изменение ранжирования влияет на вклад элемента в показатель (ERR). Мы разместим очень релевантный элемент на разных позициях в списке и вычислим вклад этого элемента в показатель (ERR). Рассмотрим приведенные ниже случаи.
- Рейтинг 1: ([8, 4, 4, 4, 4])
- Рейтинг 2: ([4, 4, 4, 4, 8])
Давайте вычислим
| Релевантность l | 2^l − 1 | Р(л) |
|---|---|---|
| 4 | 15 | 0,0586 |
| 8 | 255 | 0.9961 |
Используя это для вычисления полной ошибки (ERR) для обоих рейтингов, получаем:
- Рейтинг 1: (ERR) ≈ 0,99
- Рейтинг 2: (ERR) ≈ 0,27
Если мы рассмотрим вклад элемента с показателем релевантности 8, то увидим, что снижение вклада этого термина составляет 6,36x . Если бы штраф был линейным, снижение составило бы 5x.
| Сценарий | Вклад релевантности — 8 пунктов |
|---|---|
| Ранг 1 | 0.9961 |
| 5-й ранг | 0.1565 |
| Коэффициент падения | 6,36x |
Нормализованный дисконтированный кумулятивный выигрыш (NDCG)
Нормализованный дисконтированный кумулятивный прирост (NDCG) — ещё один отличный вариант, хорошо подходящий для ранжирования результатов поиска. NDCG основан на двух основных идеях.
- Выгода: Элементы с более высоким показателем релевантности имеют гораздо большую ценность.
- Скидка: товары, появляющиеся позже, стоят значительно меньше, поскольку пользователи уделяют меньше внимания товарам, появляющимся позже.
NDCG объединяет идеи выигрыша и скидки для создания оценки. Кроме того, он также нормализует оценку, что позволяет сравнивать различные запросы. Формально выигрыш и скидка определяются следующим образом:
- (mathrm{Gain} = 2^{l_r}-1)
- (mathrm{Discount} = log_2(1+r))
где (l) — метка релевантности элемента в позиции (r), а (r) — позиция, в которой он находится.
Прирост имеет экспоненциальную форму, которая вознаграждает более высокую релевантность. Это гарантирует, что элементы с более высоким показателем релевантности вносят гораздо больший вклад . Логарифмическая скидка наказывает за более позднее ранжирование релевантных элементов. Применительно ко всему ранжированному списку мы получаем дисконтированный кумулятивный прирост:
$$mathrm{DCG@K} = sum_{r=1}^{K} frac{2^{l_r}-1}{mathrm{log_2(1+r)}}$$
Для заданного ранжированного списка (l_1, l_2, l_3, …l_k) вычисление (DCG@K) полезно, но масштаб меток релевантности может варьироваться в зависимости от запроса, что делает сравнение (DCG@K) несправедливым. Поэтому нам нужен способ нормализации значений (DCG@K).
Мы делаем это, вычисляя (IDCG@K), что представляет собой идеальный дисконтированный кумулятивный прирост. (IDCG) — это максимально возможный (DCG) для одних и тех же элементов, полученный путем их сортировки по релевантности в порядке убывания.
$$mathrm{DCG@K} = sum_{r=1}^{K} frac{2^{l^*_r}-1}{mathrm{log_2(1+r)}}$$
(IDCG) представляет собой идеальный рейтинг. Для нормализации (DCG@K) мы вычисляем
$$mathrm{NDCG@K} = frac{mathrm{DCG@K}}{mathrm{IDCG@K}}$$
(NDCG@K) обладает следующими свойствами
- Находится в диапазоне от 0 до 1.
- Сравнимо по всем запросам
- 1 — идеальный порядок
Пример: Хороший и немного худший порядок
В этом примере мы возьмем два разных рейтинга одного и того же списка и сравним их значения (NDCG). Предположим, у нас есть элементы с метками релевантности по шкале от 0 до 3.
Рейтинг А
Рейтинг: 1 2 3 Релевантность: 3 2 1
Рейтинг B
Рейтинг: 1 2 3 Релевантность: 2 1 3
Вычислив компоненты (NDCG), получаем:
| Классифицировать | Прирост (2^l − 1) | Дисконт log₂(1 + r) | Вклад | Вклад |
|---|---|---|---|---|
| 1 | 7 | 1.00 | 7.00 | 3.00 |
| 2 | 3 | 1.58 | 1.89 | 4.42 |
| 3 | 1 | 2.00 | 0,50 | 0,50 |
- DCG(A) = 9,39
- DCG(B) = 7,92
- IDCG = 9,39
- NDCG(A) = 9,39 / 9,39 = 1,0
- NDCG(B) = 7,92 / 9,39 = 0,84
Таким образом, перемещение соответствующего элемента с первого места в рейтинге приводит к значительному падению.
NDCG: Дополнительное обсуждение
Скидка, составляющая знаменатель вычисления (DCG), имеет логарифмическую природу. Она увеличивается гораздо медленнее, чем линейно.
$$mathrm{discount(r)}=frac{1}{mathrm{log2(1+r)}}$$
Давайте сравним это с линейным распадом:
| Классифицировать (р) | Линейный (1/р) | логарифмический (1 / log₂(1 + r)) |
|---|---|---|
| 1 | 1.00 | 1.00 |
| 2 | 0,50 | 0,63 |
| 5 | 0.20 | 0,39 |
| 10 | 0.10 | 0,29 |
| 50 | 0,02 | 0,18 |
- (1/r) убывает быстрее
- (1/log(1+r)) убывает медленнее
Логарифмическая скидка наказывает более поздние ранги менее агрессивно, чем линейная скидка . Разница между рангом 1 → 2 больше, но разница между рангом 10 → 50 невелика.
Логарифмическая скидка имеет уменьшающуюся предельную величину снижения штрафных санкций для более поздних рангов из-за своей вогнутой формы. Это предотвращает превращение (NDCG) в метрику с преобладанием рангов 1-3, где ранги доминируют в оценке. Линейный штраф игнорировал бы разумные варианты выбора на более низких уровнях.
Логарифмическая скидка также отражает тот факт, что внимание пользователей резко падает в верхней части списка, а затем выравнивается, а не снижается линейно с повышением рейтинга.
Заключение
MAP и MRR — полезные метрики для поиска информации, но они плохо подходят для современных систем ранжирования результатов поиска. В то время как MAP фокусируется на поиске всех релевантных документов, MRR рассматривает задачу ранжирования как метрику одной позиции. И MAP, и MRR игнорируют градуированную релевантность элементов в поиске и рассматривают их как бинарные: релевантные и нерелевантные.
Показатели (NDCG) и (ERR) лучше отражают реальное поведение пользователей, учитывая несколько позиций, позволяя элементам иметь небинарные оценки, и придавая большее значение верхним позициям. Для систем ранжирования результатов поиска эти чувствительные к положению метрики — не просто лучший выбор, они необходимы.
Дополнительная литература
- LambdaMART (хорошее объяснение)
- Учимся занимать высокие позиции в поисковой выдаче (настоятельно рекомендую прочитать эту книгу. Она длинная и подробная, а также послужила источником вдохновения для этой статьи!).
Источник: towardsdatascience.com
