Метрики в задачах ранжирования и матчинга

План лекции
метрики качества с точки зрения классификации
особенности метрик качества для матчинга
метрики качества с точки зрения ранжирования

Матчинг с точки зрения ML
Learning to rank (LTR) - ранжирование
Картинки взята из times.cs.uiuc.edu/course/598f14/l2r.pdf

Что измерять в ранжировании?
Качество / Точность – насколько аккуратна система ранжирования?
Измеряем возможности системы ранжировать релевантные документы выше нерелевантных
Эффективность – насколько быстро выдается ответ? Сколько ресурсов нужно для формирования ответа?
Измеряем затраты на память и время формирования ответа
Удобство использования – насколько полезна система для решения задач?
Пользовательские ощущения, UX

Оценка качества ранжирования
Методология оценки Кранфилда (Cranfield Evaluation Methodology):
Зафиксированный набор документов
Зафиксированный набор запросов
Оценки релевантности пар (в идеале оценки даются пользователями системы)
Наборы должны быть репрезентативными

Оценка качества ранжирования
Запросы
Q40
Q2
Q1
Документы
D1
D3
D15
D42
D2
Оценки релевантности
Q1 D1 +
Q1 D2 +
Q1 D3 -
Q1 D4 -
…
Q2 D1 -
Q2 D2 +
…
Q40 D42 +

Оценка качества ранжирования
Запросы
Q40
Q2
Q1
Документы
D1
D3
D15
D42
D2
Оценки релевантности
Q1 D1 +
Q1 D2 +
Q1 D3 -
Q1 D4 -
…
Q2 D1 -
Q2 D2 +
…
Q40 D42 +
Модель 1
Модель 2
D1 +
D2 +
D3 -
Для Q1:
D1 +
D3 -
D4 +
D5 -
D6 +
D7 -

Оценка качества ранжирования
Запросы
Q40
Q2
Q1
Документы
D1
D3
D15
D42
D2
Оценки релевантности
Q1 D1 +
Q1 D2 +
Q1 D3 -
Q1 D4 -
…
Q2 D1 -
Q2 D2 +
…
Q40 D42 +
Модель 1
Модель 2
D1 +
D2 +
D3 -
Для Q1:
D1 +
D3 -
D4 +
D5 -
D6 +
D7 -
Precision: 2/3
Precision: 3/6

Оценка качества ранжирования
Запросы
Q40
Q2
Q1
Документы
D1
D3
D15
D42
D2
Оценки релевантности
Q1 D1 +
Q1 D2 +
Q1 D3 -
Q1 D4 -
…
Q2 D1 -
Q2 D2 +
…
Q40 D42 +
Модель 1
Модель 2
D1 +
D2 +
D3 -
Для Q1:
D1 +
D3 -
D4 +
D5 -
D6 +
D7 -
Всего релевантных 10
Precision: 2/3
Recall: 2/10
Precision: 3/6
Recall: 3/10

Оценка качества ранжирования
Доля правильных ответов (accuracy)
Точность, полнота (Precision, Recall)
Картинка взята из en.wikipedia.org/wiki/Precision_and_recall
Ограничение на расчет в Top-K (@K), Precision@5

Оценка качества ранжирования
F1, Fb-меры
Картинка взята из en.wikipedia.org/wiki/Precision_and_recall
Почему просто не брать 0.5*P + 0.5*R?

Оценка качества ранжирования
PR-auc
Сортируем предсказания по убыванию релевантности
Считаем значение точности и полноты по первой паре
Понижаем значение порога, чтобы выше порога было две пары
Повторяем до тех пор, пока не добавим все элементы
Опционально применить отсечение (Recall@Precision=N)

Оценка качества ранжирования
PR-auc
PR-auc @N

Оценка качества ранжирования
Average Precision (AP) – насколько много релевантных объектов сконцентрировано среди самых высокооцененных

Оценка качества ранжирования
Average Precision (AP) – насколько много релевантных объектов сконцентрировано среди самых высокооцененных
Всего релевантных нашли
1
1
2
3
3
4
4
4

Оценка качества ранжирования
Average Precision (AP) – насколько много релевантных объектов сконцентрировано среди самых высокооцененных
Всего релевантных нашли
Скользящая сумма
0 + 1/1 = 1
1
1 + 2/3 = 1.67
1.67 + 3/4 = 2.42
2.42
2.42 + 4/6 = 3.08
3.08
3.08
3.08 / 4 = 0.77
1
1
2
3
3
4
4
4
(Кол-во корректных предсказаний) / k

Оценка качества ранжирования
Average Precision (AP) – насколько много релевантных объектов сконцентрировано среди самых высокооцененных

Оценка качества ранжирования
Переход от бинарной задачи релевантно/не релевантно к многоуровневой
Уровень релевантности:
Не релевантно
В целом релевантно
Очень релевантно, точное соответствие

Оценка качества ранжирования
Переход от бинарной задачи релевантно/не релевантно к многоуровневой
Уровень релевантности:
Не релевантно
В целом релевантно
Очень релевантно, точное соответствие
“Gain”
D1 3
D2 2
D3 1
D4 1
D5 3
D6 1
D7 2

Оценка качества ранжирования
Переход от бинарной задачи релевантно/не релевантно к многоуровневой
Уровень релевантности:
Не релевантно
В целом релевантно
Очень релевантно, точное соответствие
“Gain”
D1 3
D2 2
D3 1
D4 1
D5 3
D6 1
D7 2
Cumulative Gain
3
3+2
3+2+1
3+2+1+1
3+2+1+1+3
3+2+1+1+3+1
3+2+1+1+3+1+2

Оценка качества ранжирования
Переход от бинарной задачи релевантно/не релевантно к многоуровневой
Уровень релевантности:
Не релевантно
В целом релевантно
Очень релевантно, точное соответствие
“Gain”
D1 3
D2 2
D3 1
D4 1
D5 3
D6 1
D7 2
Cumulative Gain
3
3+2
3+2+1
3+2+1+1
3+2+1+1+3
3+2+1+1+3+1
3+2+1+1+3+1+2
Discounted Cumulative Gain
3
3 + 2/log(3)
3 + 2/log(3) + 1/log(4)
3 + 2/log(3) + 1/log(4) + 1/log(5)
…
DCG@7 = 3 + 2/log(3) + … + 2/log(8)
log2(k+1)

Оценка качества ранжирования
Переход от бинарной задачи релевантно/не релевантно к многоуровневой
Уровень релевантности:
Не релевантно
В целом релевантно
Очень релевантно, точное соответствие
“Gain”
D1 3
D2 2
D3 1
D4 1
D5 3
D6 1
D7 2
Discounted Cumulative Gain
3
3 + 2/log(3)
3 + 2/log(3) + 1/log(4)
3 + 2/log(3) + 1/log(4) + 1/log(5)
…
DCG@7 = 3 + 2/log(3) + … + 2/log(8) ~ 7.38

Оценка качества ранжирования
Переход от бинарной задачи релевантно/не релевантно к многоуровневой
Уровень релевантности:
Не релевантно
В целом релевантно
Очень релевантно, точное соответствие
“Gain”
D1 3
D2 2
D3 1
D4 1
D5 3
D6 1
D7 2
Discounted Cumulative Gain
IdealDCG@7 = 3 + 3/log(3) + … + 1/log(8) ~ 7.83
3
3 + 2/log(3)
3 + 2/log(3) + 1/log(4)
3 + 2/log(3) + 1/log(4) + 1/log(5)
…
DCG@7 = 3 + 2/log(3) + … + 2/log(8) ~ 7.38

Оценка качества ранжирования
Переход от бинарной задачи релевантно/не релевантно к многоуровневой
Уровень релевантности:
Не релевантно
В целом релевантно
Очень релевантно, точное соответствие
“Gain”
D1 3
D2 2
D3 1
D4 1
D5 3
D6 1
D7 2
Discounted Cumulative Gain
DCG@7 = 3 + 2/log(3) + … + 2/log(8) ~ 7.38
IdealDCG@7 = 3 + 3/log(3) + … + 1/log(8) ~ 7.83
DCG@K
IdealDCG@K
nDCG@K =
= 0.942
3
3 + 2/log(3)
3 + 2/log(3) + 1/log(4)
3 + 2/log(3) + 1/log(4) + 1/log(5)
…

Оценка качества ранжирования
PFound (Yandex):
Значение метрики будет оценкой вероятности найти релевантный результат в выдаче модели
pLook[i] – вероятность просмотреть i-й документ из списка
pRel[i] – вероятность того, что i-й документ окажется релевантным (например, 0%, 50%, 100% для шкалы с тремя уровнями)
Картинка взята из romip.ru/romip2009/15_yandex.pdf

Оценка качества ранжирования
PFound (Yandex):
Значение метрики будет оценкой вероятности найти релевантный результат в выдаче модели
pLook[i] – вероятность просмотреть i-й документ из списка
pRel[i] – вероятность того, что i-й документ окажется релевантным (например, 0%, 50%, 100% для шкалы с тремя уровнями)
Для расчета pLook[i] используется два предположения:
результаты ранжирования отсматриваются сверху вниз
процесс прекращается в случае нахождения релевантного результата либо без каких-то определенных причин («надоело»)
Картинка взята из romip.ru/romip2009/15_yandex.pdf

Оценка качества ранжирования
pLook[i] – вероятность просмотреть i-й документ из списка
pRel[i] – вероятность того, что i-й документ окажется релевантным (например, 0%, 50%, 100% для шкалы с тремя уровнями)
Для расчета pLook[i] используется два предположения:
результаты ранжирования отсматриваются сверху вниз
процесс прекращается в случае нахождения релевантного результата либо без каких-то определенных причин («надоело»)
Картинка взята из romip.ru/romip2009/15_yandex.pdf

Историчесские метрики
Среднеобратный ранг (Mean reciprocal rank, MRR)
Среднее гармоническое между рангами
(1/3 + 1/2 + 1) / 3 = 11/18 ~ 0.61

Историчесские метрики
Kendall rank correlation coefficient (Kendall’s τ)
- Биномиальный коэффициент
Часто используется в статистике для оценки ранговых корреляций