Навчання ранжуванню () Слайди доповіді Тай-Янь Ліу на конференції 2009 доступні онлайн або машине-навчання ранжуванню (МНР, ) є застосуванням машинного навчання, як правило, керованого навчання, напівкерованого навчання або навчання з підкріпленням, при побудові моделей ранжування для інформаційно-пошукових систем.Mehryar Mohri, Afshin Rostamizadeh, Ameet Talwalkar (2012) Foundations of Machine Learning, The MIT Press . Навчальні набори даних складаються зі списків елементів з деяким частковим порядком, заданим між елементами в кожному списку. Цей порядок, як правило, відповідає числовим або порядковим балам або бінарним рішенням (наприклад, «відповідає» або «не відповідає») для кожного елемента. Метою моделі ранжування є присвоєння рангу, тобто, у проведенні перестановки елементів з метою створення нових списків, які «подібні» до рейтингів у навчальних даних в певному сенсі.
Застосування
В інформаційному пошуку
Ранжування є центральною складовою багатьох інформаційно-пошукових задач, наприклад, , колаборативної фільтрації, аналізу тональності тексту, і онлайн-реклами.
Навчальні дані складаються з запитів та документів, приписуючи кожній такій парі степінь відповідності. Створення навчального набору можливе вручну людьми з потрібною кваліфікацією ( або raters, як їх називає Гугл). Вони перевіряють результати для деяких запитів і визначити релевантність кожного результату. Очевидно, що не можливо перевірити релевантність всіх документів, і тому зазвичай використовується метод, званий пулінгом — перевіряють тільки кілька документів вгорі списку, отриманих за допомогою деяких існуючих моделей ранжування. Крім того, навчальні дані можуть бути отримані автоматично шляхом аналізу журналів логування переходів (наприклад, результати пошуку, які отримали кліки від користувачів), ланцюжки запитів, або такі характеристики пошукової системи як .
Навчальні дані використовуються алгоритмом навчання для отримання моделі ранжування, яка обчислює релевантність документів для фактичних запитів.
Зазвичай користувачі очікують, що пошуковий запит буде виконано за короткий час (наприклад, кілька сотень мілісекунд для вебпошуку), що унеможливлює оцінку складної моделі ранжування на кожному документі в корпусі, тому використовують двохкрокову схему. Спочатку невелика кількість потенційно релевантних документів ідентифікується з використанням більш простих моделей пошуку, які дозволяють швидко оцінювати запити, такі як модель векторного простору, , зважений AND, або BM25. Цей етап називається запитом верхніх документів, у літературі було запропоновано багато евристичних підходів для прискорення цього кроку, наприклад, використання статичного показника якості документа та багаторівневих індексів.. Section 7.1 На другому етапі використовується точніша обчислювальна машина, яка споживає більше ресурсів, і виконує переоцінку цих документів.
В інших областях Алгоритми навчання ранжируванню були застосовані в інших областях, окрім пошуку інформації:
В машинного перекладу для ранжування множини гіпотетичних перекладів; В обчислювальної біології для ранжування кандидатів 3-D структур білків у задачі прогнозування структури. В рекомендаційних систем для виявлення ранжованого списку пов'язаних новин, яку будуть рекомендуватись користувачеві після перегляду поточної новини.Yuanhua Lv, Taesup Moon, Pranam Kolari, Zhaohui Zheng, Xuanhui Wang, and Yi Chang, Learning to Model Relatedness for News Recommendation , in International Conference on World Wide Web (WWW), 2011. В області розробки програмного забезпечення, методи навчання ранжуванню були використані для локалізації несправності.
Вектори ознак Для зручності алгоритмів МНР пари запит-документ зазвичай представлені числовими векторами, які називаються векторами ознак. Такий підхід іноді називають торбою ознак аналогічно моделі «торба слів» і моделі векторного простору, що використовується при інформаційному пошуку для представлення документів.
Компоненти таких векторів називаються ознаками, факторами або сигналами рангу. Вони можуть бути розділені на три групи (ознаки з показані як приклади):
Незалежні від запиту або статичні ознаки — ті ознаки, які залежать тільки від документа, а не від запиту. Наприклад, PageRank або довжина документа. Такі ознаки можна підраховувати офлайн під час індексації. Вони можуть бути використані для розрахунку статичного показника якості документа (або статичного рангу), який часто використовується для прискорення оцінки пошукових запитів. Залежні від запиту або динамічні ознаки — ті ознаки, які залежать як від вмісту документа, так і від запиту, наприклад, результату TF-IDF або інших функцій ранжування, які не є алгоритмами МНР. Ознаки рівня запитів або ознаки запитів, які залежать тільки від запиту. Наприклад, кількість слів у запиті. Див. .
Деякі приклади ознак, які використовувалися у відомому наборі даних :
TF, TF-IDF, BM25, і мовні оцінки моделей зон документа (назва, тіло, текст якоря, URL) для цього запиту; Довжини та суми IDF зон документа; PageRank документу, ранги та їх варіанти.
Вибір і розробка хороших ознак є важливою областю в машинному навчанні, що називається конструюванням ознак.
Метрики оцінювання
Існує декілька метрик (мір), які зазвичай використовуються для того, щоб оцінити, наскільки добре алгоритм працює на навчальних даних і порівнювати продуктивність різних алгоритмів МНР. Часто завдання «навчання рангу» переформулюється як задача оптимізації відносно однієї з цих метрик.
Приклади метрик оцінки рейтингів:
(); () і нормалізований дисконтований сукупний приріст; Влучність@n, NDCG@n, де «@n» означає, що метрики оцінюються тільки на верхніх n документах; (); Кендалла; Спірмена.
Дисконтованому сукупному приросту і його нормалізованому варіанту зазвичай застосовуються в академічних дослідженнях, коли використовуються кілька рівнів релевантності. Інші метрики, такі як середня усереднена влучність, середній взаємний ранг і влучність, визначаються тільки для бінарних суджень.
Нещодавно було запропоновано кілька нових метрик оцінки, які стверджують, що модель задоволення користувачів результатами пошуку краще, ніж метрика дисконтованого сукупного приросту:
Очікуваний взаємний рейтинг (); Pfound від Yandex. ()
Обидві ці метрики базуються на припущенні, що користувач, найімовірніше, перестане переглядати результати пошукового запиту після того, як зустріне більш відповідний документ, ніж після менш релевантного документа.
Підходи Тай-Янь Ліу () з Microsoft Research Asia проаналізував наявні алгоритми навчання ранжуванню у своїй роботі «Навчання ранжуванню для пошуку інформації». Він класифікував їх за трьома групами відповідно до їх вхідного представлення і функції втрат: точковий, попарний і списковий підхід. На практиці спискові підходи часто перевершують попарні та точкові підходи. Це твердження було додатково підтверджено великомасштабним експериментом щодо оцінки різних методів навчання ранжуванню на великій колекції еталонних наборів даних.
Точковий підхід У цьому випадку передбачається, що кожна пара запит-документ у навчальних даних має числову або порядкову оцінку. Тоді завдання навчання ранжуванню можна наблизити задачею регресії — для заданої пари запит-документ, передбачити її оцінку.
Ряд існуючих алгоритмів машинного керованого навчання може бути легко використаний для цієї мети. Порядкові алгоритми регресії і класифікації також можуть бути використані в точковому підході, коли вони використовуються для прогнозування однієї пари запит-документ, і вона приймає невелике, скінченне число значень.
Попарний підхід У цьому випадку проблема навчання ранжуванню апроксимується проблемою класифікації — вивчення бінарного класифікатора, який може визначити, який документ краще в даній парі документів. Мета полягає в мінімізації середньої кількості перестановок в рейтингу.
Списковий підхід Ці алгоритми намагаються безпосередньо оптимізувати значення однієї з наведених вище метрик оцінювання, усереднених по всіх запитах в навчальних даних. Це важко, оскільки більшість метрик оцінювання не є неперервними функціями від параметрів моделі ранжирування, і тому необхідно застосовувати гладкі наближення або слід використовувати обмеження метрик оцінювання.
Список методів Частковий список алгоритмів навчання ранжирування наведено нижче. Вказано роки першої публікації кожного методу: {|class="wikitable sortable" ! Рік || Назва || Тип || Примітки |- | 1989 || OPRF || 2 точковий || Поліноміальна регресія (замість машинного навчання ця робота належить до розпізнавання образів, але ідея та ж сама) |- | 1992 || SLR || 2 точковий || Поетапна логістична регресія |- | 1999 || MART (Multiple Additive Regression Trees) || 2 попарний || |- | 2000 || Ranking SVM (RankSVM) || 2 попарний || Подальші пояснення є в, де описано застосування ранжування через використання журналювання кліків. |- | 2002 || Pranking || 1 точковий || Порядкова регресія. |- | 2003 || RankBoost || 2 попарний || |- | 2005 || RankNet || 2 попарний || |- | 2006 || IR-SVM || 2 попарний || Ранжування за допомогою SVM з нормалізацією на рівні запитів у функції втрат. |- | 2006 || LambdaRank || попарний/списковий || RankNet в якому попарна функція втрат множиться на зміни в IR метриці спричинені перестановкою. |- | 2007 || AdaRank || 3 списковий || |- | 2007 || FRank || 2 попарний || Ґрунтується на RankNet, використовує відмінну функцію втрат — точні втрати. |- | 2007 || GBRank || 2 попарний || |- | 2007 || ListNet || 3 списковий || |- | 2007 || McRank || 1 точковий || |- | 2007 || QBRank || 2 попарний || |- | 2007 || RankCosine || 3 списковий || |- | 2007 || RankGP || 3 списковий || |- | 2007 || RankRLS || 2 попарний || Регуляризоване ранжування на основі найменших квадратів. Робота розширена в навчанню ранжування по графам загальних преференцій. |- | 2007 || SVMmap || 3 списковий || |- | 2008 || LambdaSMART/LambdaMART || попарний/списковий || Переможець у конкурсі Yahoo Learning to Rank. Використано ансамбль моделей LambdaMART. Ґрунтується на MART (1999)C. Burges. (2010). From RankNet to LambdaRank to LambdaMART: An Overview . «LambdaSMART», для Lambda-submodel-MART, або LambdaMART у випадку без підмоделей (https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2008-109.pdf ). |- | 2008 || ListMLE || 3 списковий || Ґрунтується на ListNet. |- | 2008 || PermuRank || 3 списковий || |- | 2008 || SoftRank || 3 списковий || |- | 2008 || Ranking Refinement Rong Jin, Hamed Valizadegan, Hang Li, Ranking Refinement and Its Application for Information Retrieval , in International Conference on World Wide Web (WWW), 2008. || 2 попарний || Підхід з напівавтоматичним навчанням ранжуванню з використанням бустингу. |- | 2008 || SSRankBoostMassih-Reza Amini, Vinh Truong, Cyril Goutte, A Boosting Algorithm for Learning Bipartite Ranking Functions with Partially Labeled Data , International ACM SIGIR conference, 2008. Код доступний для дослідницьких цілей. || 2 попарний|| Розширення RankBoost для навчання з частково позначеними даними (напівавтоматичне навчання ранжуванню). |- | 2008 || SortNet Leonardo Rigutini, Tiziano Papini, Marco Maggini, Franco Scarselli, «SortNet: learning to rank by a neural-based sorting algorithm» , SIGIR 2008 workshop: Learning to Rank for Information Retrieval, 2008 || 2 попарний|| SortNet, алгоритм адаптивного ранжування, який упорядковує об'єкти за допомогою нейронної мережі, яка порівнює об'єкти. |- | 2009 || MPBoost || 2 попарний || Варіація RankBoost зі збереженням значущості. Ідея полягає в тому, що чим більш відрізняються мітки пари документів, тим складніше алгоритму намагатись їх класифікувати. |- | 2009 || BoltzRank || 3 списковий || На відміну від попередніх методів, BoltzRank створює модель ранжування, яка проглядає під час запиту не тільки окремий документ, але і пари документів. |-