Оптимізація «жадібних» функцій – навчання ранжування (matrixnet)
Пропонуємо ознайомитися з документом, посилання на який представники Яндекса виклали у своєму блозі тут (переробка архітектури ранжирування), при анонсі нового алгоритму ранжування під назвою "Сніжинськ"
Оптимізація «жадібних» функцій – навчання ранжування
«Жадібна» апроксимація функції та посилені алгоритми добре підходять для вирішення практичних завдань машинного навчання. Ми опишемо широко відомі посилені алгоритми та їх модифікації, які використовуються для вирішення завдань ранжування.
Зміст
Ранжування в пошукових системах
Характеристична модель ранжування
Навчання ранжування. Завдання оптимізації (обліковий, точковий, парний підходи).
Точковий підхід. Апроксимування посилених алгоритмів та «жадібної» функції.
Обліковий підхід. Апроксимування комплексних критеріїв оцінки (DCG, nDCG).
Ранжування пошукової системи.
Основна мета : ранжування документів за рівнем відповідності пошуковому запиту.
Як здійснити ранжування?
Безліч документів, що відповідають кожній із умов q Є Q .
Оцінки релевантності кожної пари (запит, документ) – у нашій моделі це речові числа rel ( q , d ) Є [0, 1]
Критерії оцінки
Оцінка для ранжування буде середнім значенням критеріїв оцінки по безлічі пошукових запитів Q:
Точність-10 – відсоток документів з оцінкою релевантності понад нуль у топ-10
MAP – середня точність
де k – кількість документів з позитивною оцінкою релевантності, що відповідає запиту q, n r (i) – позиція i-го документа з оцінкою релевантності вище за нуль.
DCG – дисконтований приріст
де N q – сумарна кількість документів у списку, що ранжується, rel j – оцінка релевантності для документа на позиції j .
nDCG – нормалізований дисконтований приріст
Кожна пара (запит, документ) описується як вектор ознак (характеристик):
Пошукове ранжування - сортування позначення «функції релевантності». Функція релевантності - це комбінація ознак (характеристик):
fr(q , d) = 3.14 log 7 (f 9 (q, d)) + e f 66 (q,d) +…
Завдання оптимізації
Як отримати хорошу функцію релевантності?
Створитирозпізнавальне (навчається?) безліч прикладів P l - безліч пар (q, d) з оцінкою релевантності rel (q, d).
Використовуйте навчання (накопичення дослідів, упізнання?) для створення методів ранжування для отримання fr .
Завдання оптимізації (обліковий підхід)
Потрібно вирішити пряме завдання оптимізації:
де F - безліч можливих ранжуючих функцій,
Q l – безліч різних запитів у розпізнавальній множині P l
Складність рішення: більшість методів оцінки – не безперервні функції.
Завдання оптимізації (точковий підхід)
Спростити задачу оптимізації до завдання регресії та мінімізувати суму функцій втрат:
де L (fr (q, d), rel (q, d)) - функції втрат,
F – безліч можливих функцій ранжирування.
Приклади функцій втрат:
Завдання оптимізації (парний підхід)
Спробуємо використати широко відомі алгоритми навчання машин для вирішення наступної задачі класифікації:
Посилені алгоритми та апроксимація «жадібної» функції
Ми вирішимо наступне завдання регресії:
Шукатимемо функцію релевантності в наступному вигляді:
Функція релевантності буде лінійноюкомбінацією функцій h k (q, d), функції h k (q, d) належать простій сім'ї H (родині слабкого навчання).
Сконструюємо фінальну функцію ітерації. На кожній ітерації ми додаватимемо до нашої функції релевантності додаткове обмеження? k h k (q, d):
Значення параметрів? k і слабкого учня h k (q, d) можуть бути вирішенням природного завдання оптимізації:
Завдання може бути вирішене безпосередньо для квадратичної функції втрат і простого класу H, але вирішити це для інших функцій втрат може бути складно.
Градієнтна апроксимація. Вважати релевантну функцію fr як вектор значень, проіндексованих розпізнавальними прикладами. Взяти градієнт для функції помилок:
Вибір слабкого навчання (з точністю до константи). Знайти функцію h k (q, d), що найбільше корелює з функцією g рішенням наступної оптимізаційної задачі:
Вибір ?k. Знайти значення? k з однопараметричної оптимізаційної задачі:
Вибір слабкого навчання
Нехай клас слабкого навчання H буде безліччю функцій-дерев прийняття рішень:
Це приклад потрійної функції-дерева прийняття рішень. Функція поділяє простір ознак на 3 вершини за умовами у формі f j (q, d) & gt; ? (f j – простір ознак, ? – межа поділу). Вона має постійне значення для вектора ознак на одній вершині.
Вибір слабкого навчання (значення функції)
Сім'я слабкого навчання буде шестирною (наприклад, const-рівневий) функцією-деревом прийняття рішень. Постараємось вирішити наступне:
Припустимо, що ми знаємо деревоподібну структуру слабкого навчання h (q, d) - знаємо умови поділу та рівні. Ми маємо знайти «константні значення рівнів».Оптимізаційна задача звужується до звичайної регресійної задачі:
Вибір слабкого навчання (деревоподібна структура)
Вибір «жадібного» дерева:
bestTree = функція-константа (одновершинне дерево),
«Жадібний» поділ. Постаратися, розділяючи вершини betsTree , знайти найкращий поділ:
Припустимо, ми маємо безліч констант можливих меж поділу. Число можливих поділів обмежене значенням:
Повторити попередній крок.
MatrixNet (мережа матриць)
Багато слабких навчань – повні дерева прийняття рішень із глибиною k та кількістю вершин 2 k .
Константна кількість вершин (константна глибина).
Однакові умови поділу на одному рівні:
Немає потреби у складній структурі: глибина важливіша.