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

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

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



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

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

Формально, розглянемо N об'єктів inline_formulaM елементів 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_formulainline_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_formulainline_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_formulainline_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.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.