Nauka rankingu - Learning to rank

Część serii na
Uczenie maszynowe i eksploracja danych
Problemy Klasyfikacja Grupowanie Regresja Wykrywanie anomalii Czyszczenie danych AutoML Zasady stowarzyszenia Nauka wzmacniania Prognoza strukturalna Inżynieria funkcji Nauka funkcji Nauka online Nauka częściowo nadzorowana Nauka nienadzorowana Nauka rangi Indukcja gramatyczna
Uczenie nadzorowane ( klasyfikacja  • regresja ) Drzewa decyzyjne Zespoły Parcianka Wzmacnianie Losowy las k -NN Regresja liniowa Naiwny Bayes Sztuczne sieci neuronowe Regresja logistyczna Perceptron Maszyna wektorów trafności (RVM) Maszyna wektorów pomocniczych (SVM)
Grupowanie BRZOZOWY LECZYĆ Hierarchiczny k -oznacza Oczekiwanie – maksymalizacja (EM) DBSCAN OPTYKA Średnia zmiana
Redukcja wymiarowości Analiza czynników CCA ICA LDA NMF PCA PGD t-SNE
Prognoza strukturalna Modele graficzne Sieć Bayesa Warunkowe pole losowe Ukryty Markow
Wykrywanie anomalii k -NN Lokalny czynnik odstający
Sztuczna sieć neuronowa Autokoder Obliczenia kognitywne Głęboka nauka DeepDream Perceptron wielowarstwowy RNN LSTM GRU ESN Ograniczona maszyna Boltzmanna GAN SOM Konwolucyjna sieć neuronowa U-Net Transformator Wzrastająca sieć neuronowa Memtranzystor Elektrochemiczna pamięć RAM (ECRAM)
Nauka wzmacniania Q-learning SARSA Różnica czasowa (TD)
Teoria Kompromis między odchyleniami a wariancją Teoria uczenia się komputerowego Minimalizacja ryzyka empirycznego Nauka Occam Nauka PAC Nauka statystyczna Teoria VC
Miejsca uczenia maszynowego NeuroIPS ICML ML JMLR ArXiv:cs.LG
Powiązane artykuły Słowniczek sztucznej inteligencji Lista zbiorów danych do badań nad uczeniem maszynowym Zarys uczenia maszynowego
v T mi

Nauka rangowania lub rankingu nauczonego maszynowo ( MLR ) to zastosowanie uczenia maszynowego , zazwyczaj nadzorowanego , częściowo nadzorowanego lub uczenia wzmacniającego , w konstruowaniu modeli rankingowych dla systemów wyszukiwania informacji . Dane uczące składają się z list pozycji z pewną częściową kolejnością określoną pomiędzy pozycjami na każdej liście. Ta kolejność jest zazwyczaj indukowana przez podanie wyniku liczbowego lub porządkowego lub oceny binarnej (np. „istotne” lub „nieistotne”) dla każdej pozycji. Model rankingu ma na celu uszeregowanie, tj. tworzenie permutacji pozycji w nowych, niewidocznych listach w sposób podobny do rankingów w danych uczących.

Aplikacje

W wyszukiwaniu informacji

Ranking jest centralną częścią wielu problemów związanych z wyszukiwaniem informacji , takich jak wyszukiwanie dokumentów , wspólne filtrowanie , analiza sentymentu i reklama online .

Możliwą architekturę wyszukiwarki uczącej się maszynowo pokazano na załączonym rysunku.

Dane treningowe składają się z zapytań i dokumentów dopasowujących je wraz ze stopniem trafności każdego dopasowania. Może on być przygotowany ręcznie przez człowieka asesorów (lub oceniających , jak Google nazywa je), który sprawdzeniu wyników dla niektórych zapytań i określić przydatność każdego wyniku. Nie jest możliwe sprawdzenie trafności wszystkich dokumentów, dlatego zazwyczaj stosuje się technikę zwaną łączeniem — sprawdzanych jest tylko kilka pierwszych dokumentów pobranych przez niektóre istniejące modele rankingowe. Ewentualnie dane szkoleniowe mogą być uzyskiwane automatycznie poprzez analizę dzienników klikalności (tj. wyników wyszukiwania, które uzyskały kliknięcia od użytkowników), łańcuchów zapytań lub takich funkcji wyszukiwarek, jak SearchWiki Google .

Dane uczące są używane przez algorytm uczący do stworzenia modelu rankingu, który oblicza istotność dokumentów dla rzeczywistych zapytań.

Zazwyczaj użytkownicy oczekują, że zapytanie wyszukiwania zakończy się w krótkim czasie (na przykład kilkaset milisekund w przypadku wyszukiwania w sieci), co uniemożliwia ocenę złożonego modelu rankingu dla każdego dokumentu w korpusie, a zatem schemat dwufazowy jest używany. Po pierwsze, mała ilość potencjalnie odpowiednich dokumentów zostaną zidentyfikowane przy prostszych pobierania modeli, które umożliwiają szybką ocenę zapytań, takich jak modelu przestrzeni wektorowej , logicznego modelu , ważone, a czy BM25 . Ta faza nazywana jest grzałka górna odzyskiwania dokumentów${\displaystyle k}$ i wielu heurystyki zostały zaproponowane w literaturze, aby go przyspieszyć, takich jak korzystanie z dokumentu jakości statyczny wynik i warstwowych indeksów. W drugiej fazie do zmiany rankingu tych dokumentów wykorzystywany jest dokładniejszy, ale kosztowny obliczeniowo model uczący się maszynowo.

W innych obszarach

Uczenie się algorytmów rangowania zostało zastosowane w obszarach innych niż wyszukiwanie informacji:

• W tłumaczeniu maszynowym do rankingu zestawu hipotetycznych tłumaczeń;
• W biologii obliczeniowej do rankingu kandydujących struktur 3-D w problemie przewidywania struktury białek.
• W systemach rekomendacji służących do identyfikowania rankingowej listy powiązanych artykułów z wiadomościami, które można polecić użytkownikowi po przeczytaniu bieżącego artykułu z wiadomościami.
• W inżynierii oprogramowania do lokalizacji błędów stosowano metody uczenia się do rangowania.

Wektory cech

Dla wygody algorytmów MLR pary zapytanie-dokument są zwykle reprezentowane przez wektory numeryczne, zwane wektorami cech . Takie podejście jest czasami nazywane workiem cech i jest analogiczne do modelu worka słów i modelu przestrzeni wektorowej używanego w wyszukiwaniu informacji do reprezentacji dokumentów.

Składniki takich wektorów nazywane są cechami , czynnikami lub sygnałami rankingowymi . Można je podzielić na trzy grupy (funkcje z pobierania dokumentów przedstawiono jako przykłady):

• Funkcje niezależne od zapytania lub statyczne — te funkcje, które zależą tylko od dokumentu, ale nie od zapytania. Na przykład PageRank lub długość dokumentu. Takie cechy mogą być wstępnie obliczone w trybie off-line podczas indeksowania. Mogą być używane do obliczania statycznego wyniku jakości dokumentu (lub statycznej rangi ), który jest często używany do przyspieszenia oceny zapytań wyszukiwania.
• Funkcje zależne od zapytania lub dynamiczne — te funkcje, które zależą zarówno od zawartości dokumentu, jak i od zapytania, takie jak wynik TF-IDF lub inne funkcje rankingowe nieuczone maszynowo.
• Funkcje na poziomie zapytania lub funkcje zapytania , które zależą tylko od zapytania. Na przykład liczba słów w zapytaniu.

Kilka przykładów funkcji, które zostały użyte w dobrze znanym zbiorze danych LETOR :

• TF, TF-IDF , BM25 i wyniki modelowania języka stref dokumentu (tytuł, treść, tekst kotwicy, adres URL) dla danego zapytania;
• Długości i sumy IDF stref dokumentu;
• Dokumentu PageRank , HITS szeregi i ich warianty.

Wybór i projektowanie dobrych funkcji to ważny obszar uczenia maszynowego, który nazywa się inżynierią funkcji .

Środki ewaluacyjne

Istnieje kilka miar (metryk), które są powszechnie używane do oceny, jak dobrze algorytm radzi sobie z danymi uczącymi i do porównywania wydajności różnych algorytmów MLR. Często problem uczenia się do rangowania jest przeformułowywany jako problem optymalizacji w odniesieniu do jednej z tych metryk.

Przykłady miar jakości rankingu:

• Średnia średnia precyzja (MAP);
• DCG i NDCG ;
• Precyzja @ n , NDCG@ n , gdzie „@ n ” oznacza, że ​​metryki są oceniane tylko w n pierwszych dokumentach;
• Średnia wzajemna ranga ;
• tau Kendalla ;
• Rho Spearmana .

DCG i jego znormalizowany wariant NDCG są zwykle preferowane w badaniach akademickich, gdy stosuje się wiele poziomów istotności. Inne metryki, takie jak MAP, MRR i precyzja, są zdefiniowane tylko dla ocen binarnych.

Ostatnio zaproponowano kilka nowych metryk oceny, które twierdzą, że lepiej modelują zadowolenie użytkownika z wyników wyszukiwania niż metryka DCG:

• Oczekiwana wzajemna ranga (ERR);
• Yandex pfound „s.

Oba te wskaźniki opierają się na założeniu, że użytkownik z większym prawdopodobieństwem przestanie patrzeć na wyniki wyszukiwania po zbadaniu bardziej trafnego dokumentu niż po mniej trafnym dokumencie.

Podejścia

Tie-Yan Liu z Microsoft Research Asia w swojej książce Learning to Rank for Information Retrieval przeanalizował istniejące algorytmy uczenia się rangowania problemów . Podzielił je na trzy grupy według ich przestrzeni wejściowych, przestrzeni wyjściowych, przestrzeni hipotez (funkcja rdzenia modelu) i funkcji straty : podejście punktowe, parami i listowe. W praktyce podejścia listowe często przewyższają podejścia parami i podejścia punktowe. Stwierdzenie to zostało dodatkowo poparte zakrojonym na szeroką skalę eksperymentem dotyczącym skuteczności różnych metod uczenia się w celu uszeregowania na dużym zbiorze zestawów danych porównawczych.

W tej sekcji, bez dalszego powiadomienia, oznacza obiekt do oceny, na przykład dokument lub obraz, oznacza hipotezę jednowartościową, oznacza funkcję funkcji dwuwymiarowej lub wielowymiarowej oraz oznacza funkcję straty. ${\displaystyle x}$${\displaystyle f(x)}$${\displaystyle h(\cdot)}$${\displaystyle L(\cdot)}$

Podejście punktowe

W tym przypadku zakłada się, że każda para zapytanie-dokument w danych uczących ma wynik liczbowy lub porządkowy. Następnie problem uczenia się do rangowania można przybliżyć za pomocą problemu regresji — biorąc pod uwagę pojedynczą parę zapytanie-dokument, przewidzieć jej wynik. Formalnie rzecz biorąc, podejście punktowe ma na celu poznanie funkcji przewidującej wartość rzeczywistą lub wynik porządkowy dokumentu za pomocą funkcji straty . ${\displaystyle f(x)}$${\displaystyle x}$${\ Displaystyle L (f, x_ {j}, y_ {j})}$

W tym celu można z łatwością wykorzystać szereg istniejących nadzorowanych algorytmów uczenia maszynowego. Algorytmy regresji porządkowej i klasyfikacji mogą być również stosowane w podejściu punktowym, gdy są używane do przewidywania wyniku pojedynczej pary zapytanie-dokument i wymagają małej, skończonej liczby wartości.

Podejście parami

W tym przypadku problem uczenia się do rangowania jest przybliżony przez problem klasyfikacji — uczenie klasyfikatora binarnego, który może powiedzieć, który dokument jest lepszy w danej parze dokumentów. Klasyfikator powinien wziąć dwa obrazy jako dane wejściowe, a celem jest zminimalizowanie funkcji strat . Funkcja straty może odzwierciedlać średnią liczbę inwersji w rankingu. ${\ Displaystyle h (x_ {u}, x_ {v})}$${\ Displaystyle L (h; x_ {u}, x_ {v}, y_ {u, v})}$

W wielu przypadkach klasyfikator binarny jest zaimplementowany z funkcją oceniania . Jako przykład, RankNet dostosowuje model prawdopodobieństwa i określa, że oszacowane prawdopodobieństwo dokumentu ma wyższą jakość niż : ${\ Displaystyle h (x_ {u}, x_ {v})}$${\displaystyle f(x)}$${\ Displaystyle h (x_ {u}, x_ {v})}$${\displaystyle x_{u}}$${\displaystyle x_{v}}$

${\ Displaystyle P_ {u, v} (f) = {\ tekst {CDF}} (f (x_ {u}) -f (x_ {v})),}$

gdzie jest dystrybuantą skumulowaną , np. standardowy logistyczny CDF , tj ${\ Displaystyle {\ tekst {CDF}} (\ cdot )}$

${\ Displaystyle {\ tekst {CDF}} (x) = {\ Frac {1} {1+ \ exp \ lewo [-x \ prawo]}}.}$

Podejście listowe

Algorytmy te próbują bezpośrednio zoptymalizować wartość jednej z powyższych miar oceny, uśrednioną dla wszystkich zapytań w danych uczących. Jest to trudne, ponieważ większość miar ewaluacyjnych nie jest funkcjami ciągłymi w odniesieniu do parametrów modelu rankingowego, a zatem muszą być stosowane ciągłe przybliżenia lub ograniczenia miar ewaluacyjnych.

Lista metod

Poniżej przedstawiono częściową listę opublikowanych algorytmów uczenia się do rankingu wraz z latami pierwszej publikacji każdej metody:

Rok	Nazwa	Rodzaj	Uwagi
1989	OPRF	2 punktowo	Regresja wielomianowa (zamiast uczenia maszynowego ta praca dotyczy rozpoznawania wzorców, ale idea jest taka sama)
1992	Lustrzanka	2 punktowo	Etapowa regresja logistyczna
1994	NMOpt	2 skrępowany	Optymalizacja niemetryczna
1999	MART (Drzewa regresji wielu addytywnych)	2 parami
2000	Ranking SVM (RankSVM)	2 parami	Nowsza ekspozycja znajduje się w opisie aplikacji do rankingu za pomocą dzienników kliknięć.
2002	Dowcipy	1 punktowo	Regresja porządkowa.
2003	RangaBoost	2 parami
2005	RankingNet	2 parami
2006	IR-SVM	2 parami	Ranking SVM z normalizacją na poziomie zapytania w funkcji straty.
2006	LambdaRank	parami/listwisem	RankNet, w którym funkcja straty parami jest mnożona przez zmianę metryki IR spowodowaną swapem.
2007	AdaRank	3 skrępowany
2007	Szczery	2 parami	W oparciu o RankNet wykorzystuje inną funkcję straty - utratę wierności.
2007	GBRank	2 parami
2007	ListNet	3 skrępowany
2007	McRank	1 punktowo
2007	QBRrank	2 parami
2007	RangaCosine	3 skrępowany
2007	RankingGP	3 skrępowany
2007	RankRLS	2 parami	Uregulowany ranking oparty na najmniejszych kwadratach. Praca jest rozszerzona na naukę rangowania na podstawie ogólnych wykresów preferencji.
2007	Mapa SVM	3 skrępowany
2008	LambdaSMART/LambdaMART	parami/listwisem	Zwycięska pozycja w niedawnym konkursie Yahoo Learning to Rank wykorzystała zestaw modeli LambdaMART. Na podstawie MART (1999) „LambdaSMART” dla Lambda-submodel-MART lub LambdaMART dla przypadku bez podmodelu (https://www.microsoft.com/en-us/research/wp-content/uploads/2016/ 02/tr-2008-109.pdf ).
2008	ListaMLE	3 skrępowany	Na podstawie ListNet.
2008	PermuRank	3 skrępowany
2008	Miękki ranking	3 skrępowany
2008	Udoskonalenie rankingu	2 parami	Częściowo nadzorowane podejście do nauki rangowania, które wykorzystuje Boosting.
2008	SSRankBoost	2 parami	Rozszerzenie RankBoost do nauki z częściowo oznaczonymi danymi (częściowo nadzorowane uczenie się do rangi)
2008	SortNet	2 parami	SortNet, adaptacyjny algorytm rankingowy, który porządkuje obiekty za pomocą sieci neuronowej jako komparatora.
2009	MPBoost	2 parami	Zachowujący wielkość wariant RankBoost. Chodzi o to, że im bardziej nierówne są etykiety pary dokumentów, tym trudniej algorytm powinien uszeregować je.
2009	Ranking Boltz	3 skrępowany	W przeciwieństwie do wcześniejszych metod, BoltzRank tworzy model rankingu, który w czasie zapytania uwzględnia nie tylko pojedynczy dokument, ale także pary dokumentów.
2009	BayesRank	3 skrępowany	Metoda łączy Model Placketta-Luce'a i sieć neuronową, aby zminimalizować oczekiwane ryzyko Bayesa, związane z NDCG, od strony decyzyjnej.
2010	Wzmocnienie NDCG	3 skrępowany	Wzmacniające podejście do optymalizacji NDCG.
2010	GBlen	2 parami	Rozszerza GBRank o problem uczenia się do łączenia polegający na wspólnym rozwiązywaniu wielu problemów związanych z uczeniem się do rankingu z niektórymi wspólnymi funkcjami.
2010	InterwałRanga	2 parami i listwisem
2010	CRR	2 punktowo i parami	Połączona regresja i ranking. Wykorzystuje stochastyczne opadanie gradientowe, aby zoptymalizować liniową kombinację punktowej straty kwadratowej i pary zawiasowej straty z rankingu SVM.
2014	LCR	2 parami	Zastosowano lokalne założenie niskiej rangi w rankingu opartym na współpracy. Otrzymał nagrodę za najlepszą pracę studencką na WWW'14.
2015	FaceNet	parami	Klasyfikuje obrazy twarzy za pomocą metryki trypletowej za pomocą głębokiej sieci konwolucyjnej.
2016	XGBoost	parami	Obsługuje różne cele rankingowe i wskaźniki oceny.
2017	ES-Rank	skrępowany	Strategia ewolucyjna Uczenie się techniki rangowania z 7 wskaźnikami oceny sprawności
2018	PolyRank	parami	Uczy się jednocześnie rankingu i bazowego modelu generatywnego z porównań parami.
2018	FATE-Net/FETA-Net	skrępowany	Kompleksowe architektury z możliwością uczenia się od końca do końca, które jawnie uwzględniają wszystkie elementy w modelowaniu efektów kontekstowych.
2019	FastAP	skrępowany	Optymalizuje średnią precyzję, aby uczyć się głębokich osadzeń
2019	Morwa	listwise i hybryda	Poznaje zasady rankingowe maksymalizujące wiele metryk w całym zbiorze danych
2019	DirectRanker	parami	Uogólnienie architektury RankNet
2020	PRM	parami	Sieć transformatorowa kodująca zarówno zależności między elementami, jak i interakcje między użytkownikiem a przedmiotami

Uwaga: ponieważ większość nadzorowanych algorytmów uczenia się można zastosować w przypadku punktowym, powyżej przedstawiono tylko te metody, które zostały zaprojektowane specjalnie z myślą o rankingu.

Historia

Norbert Fuhr przedstawił ogólną ideę MLR w 1992 roku, opisując podejścia do uczenia się w wyszukiwaniu informacji jako uogólnienie estymacji parametrów; specyficzny wariant tego podejścia (wykorzystujący regresję wielomianową ) opublikował trzy lata wcześniej. Bill Cooper zaproponował regresję logistyczną w tym samym celu w 1992 roku i wykorzystał ją wraz ze swoją grupą badawczą z Berkeley , aby wyszkolić skuteczną funkcję rankingową dla TREC . Manning i in. sugerują, że te wczesne prace przyniosły ograniczone wyniki w swoim czasie z powodu małej ilości dostępnych danych szkoleniowych i słabych technik uczenia maszynowego.

Kilka konferencji, takich jak NIPS , SIGIR i ICML, od połowy lat 2000 (dekady) organizowało warsztaty poświęcone problemowi uczenia się do rangi.

Praktyczne wykorzystanie przez wyszukiwarki

Komercyjne wyszukiwarki internetowe zaczęły używać systemów rankingowych uczenia maszynowego od 2000 roku (dekady). Jedną z pierwszych wyszukiwarek, które zaczęły z niej korzystać, była AltaVista (później jej technologię przejęli Overture , a następnie Yahoo ), która w kwietniu 2003 r. uruchomiła funkcję rankingową wyszkoloną w zakresie gradientu .

Mówi się, że wyszukiwanie Bing jest oparte na algorytmie RankNet , który został wynaleziony w Microsoft Research w 2005 roku.

W listopadzie 2009 r. rosyjska wyszukiwarka Yandex ogłosiła, że ​​znacznie poprawiła jakość wyszukiwania dzięki wdrożeniu nowego, zastrzeżonego algorytmu MatrixNet , wariantu metody zwiększania gradientu , która wykorzystuje nieświadome drzewa decyzyjne. Niedawno sponsorowali także konkurs rankingowy oparty na wiedzy maszynowej „Internet Mathematics 2009” na podstawie danych produkcyjnych własnej wyszukiwarki. Yahoo ogłosiło podobny konkurs w 2010 roku.

W 2008 roku Google „s Peter Norvig zaprzeczyć, że ich wyszukiwarka opiera się wyłącznie na ranking maszynowego nauczyć. Dyrektor generalny Cuil , Tom Costello, sugeruje, że preferują modele ręcznie budowane, ponieważ mogą one przewyższać modele uczące się maszynowo, gdy mierzy się je takimi wskaźnikami, jak współczynnik klikalności lub czas na stronie docelowej, ponieważ modele uczone maszynowo „uczą się, czego ludzie powiedz, że lubią, a nie to, co ludzie naprawdę lubią”.

W styczniu 2017 r. technologia została włączona do otwartej wyszukiwarki Apache Solr ™, dzięki czemu ranking wyszukiwania maszynowego stał się szeroko dostępny również w przypadku wyszukiwania korporacyjnego.

Luki

Podobnie jak w przypadku aplikacji rozpoznawania w wizji komputerowej , najnowsze algorytmy rankingowe oparte na sieciach neuronowych są również podatne na ukryte ataki przeciwnika , zarówno na kandydatów, jak i zapytania. Przy niewielkich perturbacjach niedostrzegalnych dla ludzi kolejność rankingu może być dowolnie zmieniana. Ponadto okazuje się, że możliwe są możliwe do przeniesienia przykłady kontradyktoryjności niezależne od modelu, co umożliwia ataki kontradyktoryjne typu „czarna skrzynka” na systemy o głębokim rankingu bez konieczności dostępu do ich podstawowych implementacji.

I odwrotnie, solidność takich systemów rankingowych można poprawić dzięki obronie przeciwnika, takiej jak obrona Madry.

Zobacz też

• Pobieranie obrazów na podstawie treści
• Pobieranie informacji multimedialnych
• Pobieranie obrazu
• Strata trojaczków

Bibliografia

Zewnętrzne linki

Konkursy i publiczne zbiory danych

• LETOR: Zbiór wzorców dla badań nad nauką oceniania w celu wyszukiwania informacji
• Matematyka internetowa Yandex 2009
• Wieśniak! Nauka rangowania wyzwania
• Microsoft Learning do rankingu zbiorów danych

Kod Open Source

• Równoległa implementacja C++/MPI drzew regresji wzmocnionej gradientem do rankingu, opublikowana we wrześniu 2011 r.
• Implementacja C++ drzew regresji wzmocnionej gradientem i lasów losowych do rankingu
• Narzędzia C++ i Python do korzystania z algorytmu SVM-Rank
• Implementacja Java w wyszukiwarce Apache Solr