Nauka rankingu - Learning to rank
Część serii na |
Uczenie maszynowe i eksploracja danych |
---|
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 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.
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 .
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.
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ż :
gdzie jest dystrybuantą skumulowaną , np. standardowy logistyczny CDF , tj
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 Regresja wielomianowa (zamiast uczenia maszynowego ta praca dotyczy rozpoznawania wzorców, ale idea jest taka sama) 1992 Lustrzanka Etapowa regresja logistyczna 1994 NMOpt Optymalizacja niemetryczna 1999 MART (Drzewa regresji wielu addytywnych) 2000 Ranking SVM (RankSVM) Nowsza ekspozycja znajduje się w opisie aplikacji do rankingu za pomocą dzienników kliknięć. 2002 Dowcipy Regresja porządkowa. 2003 RangaBoost 2005 RankingNet 2006 IR-SVM 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 2007 Szczery W oparciu o RankNet wykorzystuje inną funkcję straty - utratę wierności. 2007 GBRank 2007 ListNet 2007 McRank 2007 QBRrank 2007 RangaCosine 2007 RankingGP 2007 RankRLS Uregulowany ranking oparty na najmniejszych kwadratach. Praca jest rozszerzona na naukę rangowania na podstawie ogólnych wykresów preferencji.
2007 Mapa SVM 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 Na podstawie ListNet. 2008 PermuRank 2008 Miękki ranking 2008 Udoskonalenie rankingu Częściowo nadzorowane podejście do nauki rangowania, które wykorzystuje Boosting. 2008 SSRankBoost Rozszerzenie RankBoost do nauki z częściowo oznaczonymi danymi (częściowo nadzorowane uczenie się do rangi) 2008 SortNet SortNet, adaptacyjny algorytm rankingowy, który porządkuje obiekty za pomocą sieci neuronowej jako komparatora. 2009 MPBoost 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 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 Metoda łączy Model Placketta-Luce'a i sieć neuronową, aby zminimalizować oczekiwane ryzyko Bayesa, związane z NDCG, od strony decyzyjnej. 2010 Wzmocnienie NDCG Wzmacniające podejście do optymalizacji NDCG. 2010 GBlen 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 2010 CRR 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 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