Обучение за класиране

Обучение за класиране(англ. learning to rank илиmachine-learned ranking, MLR) [1] е клас от проблеми с контролирано машинно обучение, които се състоят в автоматично избиране на модел за класиране от набор за обучение, състоящ се от набор от списъци и дадени частични поръчки на елементи във всеки списък. Частичният ред обикновено се уточнява чрез посочване на оценка за всеки елемент (напр. „уместно“ или „неуместно“; възможни са повече от две степени). Целта на модела за класиране е най-добре (в известен смисъл) да приближи и обобщи метода за класиране в набора за обучение към нови данни.

Обучението за класиране е все още доста млада, бързо развиваща се област на изследване, която възниква през 2000-те години с появата на интерес в областта на извличането на информация при прилагането на методи за машинно обучение към проблеми с класирането.

Съдържание

Във връзка с търсачките всеки списък е набор от документи, които отговарят на някаква заявка за търсене.

Обучителната извадка се състои от извадка от заявки за търсене, подмножество от документи, които им съответстват, и оценки за уместността на всеки документ спрямо заявката. Те могат да бъдат изготвени или ръчно от специално обучени хора (оценители на качеството на търсенето илиоценители), или автоматично, въз основа на анализ на потребителски кликвания [2] или инструменти на търсачката като системата SearchWiki на търсачката Google.

Функции за класиране

По време на обучението на модела за класиране и по време на неговата работа, всяка двойка документ-заявка се превежда в числен вектор от характеристики за класиране (наричани също фактори за класиране или сигнали), които характеризират свойствата на документа, заявката и тяхната връзка. Такива знацимогат да бъдат разделени на три групи:

  • Независими от заявкатаилистатичнифункции - зависи само от документа, не от заявката. Например PageRank или дължина на документа. Такива характеристики обикновено се изчисляват на етапа на индексиране на документи и често се използват за конструиране на статичен резултат за качество на документа, който се използва за подобряване на производителността на търсачките. [3][4]
  • Функции, които зависят само от заявката. Например „заявка за порно или не“.
  • Зависещи от заявкатаилидинамичнифункции - зависи както от документа, така и от заявката. Например мярката TF-IDF за съответствие на документа със заявка.

Следват някои примери за функции за класиране, използвани в добре известния набор от данни LETOR в тази област на изследване: [5]

  • Стойности на мерките TF, TF-IDF, BM25 и езиковия модел за съвпадение на заявката на различни зони на документа (заглавие, URL, основен текст, текст на връзка);
  • Дължини и IDF суми на документни зони;
  • Класиране на документи, получено чрез различни вариации на алгоритми за класиране на връзки като PageRank и HITS.

Има няколко показателя, които оценяват и сравняват ефективността на алгоритмите за класиране върху извадка с партньорски проверки. Често параметрите на модела за класиране са склонни да бъдат коригирани по такъв начин, че да се увеличи максимално стойността на един от тези показатели.

  • DCG и NDCG;
  • Точност@n, NDCG@n(@nозначава, че метричната стойност се взема предвид само заnнай-добри документи за издаване);
  • КАРТА;
  • среден обратен ранг;
  • pfound е разработен от Yandex. [6]

В своята статия „Learning to Rank for Information Retrieval“ [1] и изказвания натематични конференции, Тай-Ян Лиу от Microsoft Research Asia анализира съществуващите тогава методи за решаване на проблема с обучението за класиране и предложи тяхната класификация в три подхода, в зависимост от използваното представяне на входните данни и наказателната функция:

Точков подход

При поточковия подход се приема, че на всяка двойка заявка-документ се присвоява числова оценка. Задачата да се научите да класирате се свежда до изграждане на регресия: за всяка отделна двойка заявка-документ е необходимо да се предвиди нейният резултат.

В рамките на този подход много алгоритми за машинно обучение могат да бъдат приложени към регресионни проблеми. Когато резултатите могат да приемат само няколко стойности, могат да се използват и алгоритми за ординална регресия и класификация.

Подход по двойки

При подход по двойки, обучението за класиране се свежда до изграждане на двоичен класификатор, който получава два документа, съответстващи на една и съща заявка като вход, и се изисква да се определи кой е по-добър.

Примери за алгоритми: [1] RankNet, FRank, RankBoost, RankSVM, IR-SVM.

Списъчен подход

Списъчният подход (англ. listwise approach) е да се изгради модел, на входа на който незабавно се получават всички документи, които отговарят на заявката, а на изхода е тяхната пермутация. Напасването на параметрите на модела се извършва за директно максимизиране на един от горните показатели за класиране. Но това често е трудно, тъй като показателите за класиране обикновено не са непрекъснати и недиференцируеми по отношение на параметрите на модела за класиране, така че те прибягват до максимизиране на някои от техните приближения или по-ниски оценки.

Примери за алгоритми: [1] SoftRank, SVM карта, AdaRank,RankGP, ListNet, ListMLE.

В основните търсачки

Търсачките на много съвременни интернет търсачки, включително Yandex, Yahoo [7] и Bing, използват модели за класиране, изградени чрез методи за машинно обучение. Търсенето на Bing използва алгоритъма RankNet. [8] Най-новият алгоритъм за машинно обучение за класиране, разработен и използван в търсачката Yandex, се нарича MatrixNet; [9] Самият Yandex наскоро спонсорира състезанието Internet Mathematics 2009 [10] за изграждане на алгоритъм за класиране въз основа на собствен набор от данни.

В интервю в началото на 2008 г. Питър Норвиг, директор по изследванията в Google, заяви, че тяхната търсачка все още не е готова да повери изцяло класирането на алгоритми за машинно обучение, твърдейки, че, първо, автоматично генерираните модели могат да се държат непредсказуемо при нови класове заявки, които не изглеждат като заявки от набора за обучение, в сравнение с моделите, създадени от човешки експерти. Второ, създателите на настоящия алгоритъм за класиране на Google са уверени, че техният модел също е в състояние да решава проблеми по-ефективно от машинното обучение. [11] Първата причина е от много по-голям интерес за нас, тъй като тя не само се връща към така добре познатия проблем в индуктивната логика, формулиран от немския математик К.Г. Хемпел и противоречи на интуицията (изявлението "всички гарвани са черни" е логически еквивалентно на "всички не-черни обекти не са гарвани"), но също така ни кара да се върнем към редица нерешени проблеми на Ф. Розенблат, който създаде първата в света невронна мрежа, способна да възприема и да формира отговор на възприемания стимул - еднослоен перцептрон. [12] Надграждане на критиката на елементарния перцептронРозенблат, можем да разберем уязвимостта на този модел за оценка, за който ни разказват експертите на Google: способни ли са изкуствените системи да обобщят своя индивидуален опит в широк клас ситуации, за които отговорът не им е бил предоставен предварително? Не, индивидуалният опит на изкуствените системи на практика винаги е ограничен и никога пълен. По един или друг начин инструментите за машинно обучение ви позволяват да разрешите проблема с спамдексинга с доста висока степен на ефективност. [13]