Машинне навчання та добування даних |
---|
![]() |
Задачі
|
Кероване навчання (класифікація • регресія)
|
Кластерування
|
Зниження розмірності
|
Структурове передбачування
|
Виявлення аномалій
|
Нейронні мережі
|
Навчання з підкріпленням
|
Теорія
|
Місця машинного навчання
|
Навчання ранжуванню (англ. learning to rank) або машине-навчання ранжуванню (МНР, англ. machine-learned ranking) є застосуванням машинного навчання, як правило, навчання з учителем, напівавтоматичного навчанням або навчання з підкріпленням, при побудові моделей ранжування для інформаційно-пошукових систем. Навчальні набори даних складаються зі списків елементів з деяким частковим порядком, заданим між елементами в кожному списку. Цей порядок, як правило, відповідає числовим або порядковим балам або бінарним рішенням (наприклад, «відповідає» або «не відповідає») для кожного елемента. Метою моделі ранжування є присвоєння рангу, тобто, у проведенні перестановки елементів з метою створення нових списків, які «подібні» до рейтингів у навчальних даних в певному сенсі.
Ранжування є центральною складовою багатьох інформаційно-пошукових задач, наприклад, пошуку документів [en] , колаборативної фільтрації, аналізу тональності тексту, і онлайн-реклами.
Навчальні дані складаються з запитів та документів, приписуючи кожній такій парі степінь відповідності. Створення навчального набору можливе вручну людьми з потрібною кваліфікацією (англ. assessors або raters, як їх називає Гугл). Вони перевіряють результати для деяких запитів і визначити релевантність кожного результату. Очевидно, що не можливо перевірити релевантність всіх документів, і тому зазвичай використовується метод, званий пулінгом — перевіряють тільки кілька документів вгорі списку, отриманих за допомогою деяких існуючих моделей ранжування. Крім того, навчальні дані можуть бути отримані автоматично шляхом аналізу журналів логування переходів (наприклад, результати пошуку, які отримали кліки від користувачів), ланцюжки запитів, або такі характеристики пошукової системи як Google SearchWiki [en] .
Навчальні дані використовуються алгоритмом навчання для отримання моделі ранжування, яка обчислює релевантність документів для фактичних запитів.
Зазвичай користувачі очікують, що пошуковий запит буде виконано за короткий час (наприклад, кілька сотень мілісекунд для веб-пошуку), що унеможливлює оцінку складної моделі ранжування на кожному документі в корпусі, тому використовують двохкрокову схему. Спочатку невелика кількість потенційно релевантних документів ідентифікується з використанням більш простих моделей пошуку, які дозволяють швидко оцінювати запити, такі як модель векторного простору, булева модель [en] , зважений AND, або BM25 [en] . Цей етап називається запитом верхніх документів, у літературі було запропоновано багато евристичних підходів для прискорення цього кроку, наприклад, використання статичного показника якості документа та багаторівневих індексів. На другому етапі використовується більш точна обчислювальна машина, яка споживає більше ресурсів, і виконує переоцінку цих документів.
Алгоритми навчання ранжируванню були застосовані в інших областях, окрім пошуку інформації:
Для зручності алгоритмів МНР пари запит-документ зазвичай представлені числовими векторами, які називаються векторами ознак. Такий підхід іноді називають торбою ознак аналогічно моделі «торба слів» і моделі векторного простору, що використовується при інформаційному пошуку для представлення документів.
Компоненти таких векторів називаються ознаками, факторами або сигналами рангу. Вони можуть бути розділені на три групи (ознаки з пошуку документів [en] показані як приклади):
Деякі приклади ознак, які використовувалися у відомому наборі даних LETOR :
Вибір і розробка хороших ознак є важливою областю в машинному навчанні, що називається проектуванням ознак .
Існує декілька метрик (мір), які зазвичай використовуються для того, щоб оцінити, наскільки добре алгоритм працює на навчальних даних і порівнювати продуктивність різних алгоритмів МНР. Часто завдання «навчання рангу» переформулюється як задача оптимізації відносно однієї з цих метрик.
Приклади метрик оцінки рейтингів:
Дисконтованому сукупному приросту і його нормалізованому варіанту зазвичай застосовуються в академічних дослідженнях, коли використовуються кілька рівнів релевантності. Інші метрики, такі як середня усереднена точність, середній взаємний ранг і точність, визначаються тільки для бінарних суджень.
Нещодавно було запропоновано кілька нових метрик оцінки, які стверджують, що модель задоволення користувачів результатами пошуку краще, ніж метрика дисконтованого сукупного приросту:
Обидві ці метрики базуються на припущенні, що користувач, скоріше за все, перестане переглядати результати пошукового запиту після того, як зустріне більш відповідний документ, ніж після менш релевантного документа.
Тай-Янь Ліу (англ. Tie-Yan Liu) з Microsoft Research Asia [en] проаналізував наявні алгоритми навчання ранжуванню у своїй роботі «Навчання ранжуванню для пошуку інформації». Він класифікував їх за трьома групами відповідно до їх вхідного представлення і функції втрат: точковий, попарний і списковий підхід. На практиці спискові підходи часто перевершують попарні та точкові підходи. Це твердження було додатково підтверджено великомасштабним експериментом щодо оцінки різних методів навчання ранжуванню на великій колекції еталонних наборів даних.
У цьому випадку передбачається, що кожна пара запит-документ у навчальних даних має числову або порядкову оцінку. Тоді завдання навчання ранжуванню можна наблизити задачею регресії — для заданої пари запит-документ, передбачити її оцінку.
Ряд існуючих алгоритмів машинного навчання з учителем може бути легко використаний для цієї мети. Порядкові алгоритми регресії і класифікації також можуть бути використані в точковому підході, коли вони використовуються для прогнозування однієї пари запит-документ, і вона приймає невелике, скінченне число значень.
У цьому випадку проблема навчання ранжуванню апроксимується проблемою класифікації — вивчення бінарного класифікатора, який може визначити, який документ краще в даній парі документів. Мета полягає в мінімізації середньої кількості перестановок в рейтингу.
Ці алгоритми намагаються безпосередньо оптимізувати значення однієї з наведених вище метрик оцінювання, усереднених по всіх запитах в навчальних даних. Це важко, оскільки більшість метрик оцінювання не є неперервними функціями від параметрів моделі ранжирування, і тому необхідно застосовувати гладкі наближення або слід використовувати обмеження метрик оцінювання.
Частковий список алгоритмів навчання ранжирування наведено нижче. Вказано роки першої публікації кожного методу:
Рік | Назва | Тип | Примітки |
---|---|---|---|
1989 | OPRF | точковий | Поліноміальна регресія (замість машинного навчання ця робота відноситься до розпізнавання образів, але ідея та ж сама) |
1992 | SLR | точковий | Поетапна логістична регресія |
1999 | MART (Multiple Additive Regression Trees) | попарний | |
2000 | Ranking SVM (RankSVM) | попарний | Подальші пояснення є в, де описано застосування ранжування через використання журналювання кліків. |
2002 | Pranking | точковий | Порядкова регресія. |
2003 | RankBoost | попарний | |
2005 | RankNet | попарний | |
2006 | IR-SVM | попарний | Ранжування за допомогою SVM з нормалізацією на рівні запитів у функції втрат. |
2006 | LambdaRank | попарний/списковий | RankNet в якому попарна функція втрат множиться на зміни в IR метриці спричинені перестановкою. |
2007 | AdaRank | списковий | |
2007 | FRank | попарний | Ґрунтується на RankNet, використовує відмінну функцію втрат — точні втрати. |
2007 | GBRank | попарний | |
2007 | ListNet | списковий | |
2007 | McRank | точковий | |
2007 | QBRank | попарний | |
2007 | RankCosine | списковий | |
2007 | RankGP | списковий | |
2007 | RankRLS | попарний |
Регуляризоване ранжування на основі найменших квадратів. Робота розширена в навчанню ранжування по графам загальних преференцій. |
2007 | SVMmap | списковий | |
2008 | LambdaSMART/LambdaMART | попарний/списковий | Переможець у конкурсі Yahoo Learning to Rank. Використано ансамбль моделей LambdaMART. Ґрунтується на MART (1999) «LambdaSMART», для Lambda-submodel-MART, або LambdaMART у випадку без підмоделей (https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2008-109.pdf). |
2008 | ListMLE | списковий | Ґрунтується на ListNet. |
2008 | PermuRank | списковий | |
2008 | SoftRank | списковий | |
2008 | Ranking Refinement | попарний | Підхід з напіватоматичним навчанням ранжуванню з використанням бустингу. |
2008 | SSRankBoost | попарний | Розширення RankBoost для навчання з частково позначеними даними (напіватоматичне навчання ранжуванню). |
2008 | SortNet | попарний | SortNet, алгоритм адаптивного ранжування, який упорядковує об'єкти за допомогою нейронної мережі, яка порівнює об'єкти. |
2009 | MPBoost | попарний | Варіація RankBoost зі збереженням значимості. Ідея полягає в тому, що чим більш відрізняються мітки пари документів, тим складніше алгоритму намагатись їх класифікувати. |
2009 | BoltzRank | списковий | На відміну від попередніх методів, BoltzRank створює модель ранжування, яка проглядає під час запиту не тільки окремий документ, але і пари документів. |
2009 | BayesRank | списковий | Метод об'єднує модель Plackett-Luce та нейронну мережу для мінімізації очікуваного ризику Байєса, пов'язаного з нормалізованим дисконтованим сукупним приростом (NDCG), з точки зору прийняття рішень. |
2010 | NDCG Boost | списковий | Бустинговий підхід до оптимізації нормалізованого дисконтованого сукупного прирісту (NDCG). |
2010 | GBlend | попарний | Розширений GBRank навчання задачам спільного вирішення декількох завдань навчання ранжування з деякими спільними ознаками. |
2010 | IntervalRank | попарний & списковий | |
2010 | CRR | точковий & попарний | Комбіновані регресія і ранжування. Використовується стохастичний градієнтний спуск для оптимізації лінійної суми квадратів точкових втрат та попарних завісних втрат SVM-ранжування. |
2017 | ES-Rank | списковий | Еволюційна стратегія навчання методу ранжирування з підгонкою по 7 метрикам. |
Примітка: оскільки більшість алгоритмів навчання з учителем можна застосувати до точкових випадків, вище показані тільки ті методи, які спеціально розроблені з метою ранжування.
Норберт Фур [en] представив загальну ідею МНР у 1992 році, описавши підходи до навчання у інформаційному пошуку як узагальнення оцінки параметрів; конкретний варіант цього підходу (з використанням поліноміальної регресії [en] ) був опублікований ним за три роки до того. Білл Купер запропонував логістичну регресію для тієї ж мети в 1992 році і використав її з дослідницькою групою у Берклі для підготовки успішної функції ранжування для TREC [en] . Manning et al. припускають, що ці ранні роботи досягли обмежених результатів у свій час через невелику кількість доступних навчальних даних і слабкий розвиток методів машинного навчання.
Кілька конференцій, таких як NIPS [en] , Special Interest Group on Information Retrieval [en] і ICML [en] мали семінари, присвячені проблемі навчання ранжування, починаючи з середини першого десятиліття 2000-х років.
Комерційні веб-пошукові системи почали використовувати системи машинного навчання ранжування з першого десятиліття 2000-х років. Одна з перших пошукових систем, яка почала це використовувати була AltaVista (пізніше технологія була придбана Overture [en] , а потім Yahoo), яка почала навчати функції ранжування методом градієнтного підсилювання [en] в квітні 2003 року.
Пошукова система Bing, як повідомляється, працює за алгоритмом RankNet, який був винайдений дослідженні Microsoft у 2005 році.
У листопаді 2009 року російський пошуковий сервіс Яндекс оголосив, що значно збільшив якість пошуку за рахунок розгортання нового власного алгоритму MatrixNet [en] , варіанту методу градієнтного підсилювання [en] , який використовує невідомі дерева рішень. 2009 року вони також виступили спонсором конкурсу МНР «Internet Mathematics 2009» на основі власних даних їх пошукової системи. Yahoo оголошувала аналогічний конкурс у 2010 році.
У 2008 році Пітер Норвіг з Google заперечував, що їх пошукова система спирається виключно на МНР. Генеральний директор Cuil, Том Костелло, припускає, що вони віддають перевагу моделям, створеним вручну, тому що вони можуть перевершувати моделі отримані за допомогою машинного навчання, якщо вимірюються за показниками такими, як частота переходів або час на проведений цільовій сторінці, що є причиною того, що алгоритми МНР «дізнаються, що люди кажуть, що їм подобається, а не те, що людям подобається насправді».
У січні 2017 року ця технологія була включена в пошуковий рушій з відкритим вихідним кодом Apache Solr™, тим самим, МНР став широко доступним.