Naučit se hodnotit - Learning to rank

Learning to rank nebo strojově naučené hodnocení ( MLR ) je aplikace strojového učení , typicky supervizovaného , semi-supervidovaného nebo posilovacího učení , při konstrukci modelů hodnocení pro systémy získávání informací . Údaje o školení se skládají ze seznamů položek s určitým dílčím pořadím určeným mezi položkami v každém seznamu. Toto pořadí je obvykle vyvoláno číselným nebo pořadovým skóre nebo binárním úsudkem (např. „Relevantní“ nebo „nerelevantní“) pro každou položku. Model hodnocení má za cíl řadit, tj. Vytvářet permutaci položek v nových, neviditelných seznamech podobným způsobem jako hodnocení v tréninkových datech.

Aplikace

Při získávání informací

Možná architektura strojově naučeného vyhledávače.

Hodnocení je ústřední součástí mnoha problémů s vyhledáváním informací , jako je načítání dokumentů , společné filtrování , analýza sentimentu a online reklama .

Možná architektura strojově naučeného vyhledávače je znázorněna na přiloženém obrázku.

Tréninkové údaje se skládají z dotazů a dokumentů, které je shodují s mírou relevance každé shody. Může to být připraveno ručně lidskými hodnotiteli (nebo hodnotiteli , jak jim říká Google ), kteří zkontrolují výsledky u některých dotazů a určí relevantnost každého výsledku. Není možné kontrolovat relevanci všech dokumentů, a proto se obvykle používá technika nazývaná sdružování - kontroluje se pouze několik nejlepších dokumentů, které byly získány některými existujícími hodnotícími modely. Alternativně lze tréninková data odvodit automaticky analýzou protokolů prokliku (tj. Výsledků vyhledávání, na které uživatelé klikli), řetězců dotazů nebo funkcí takových vyhledávačů, jako je Google SearchWiki .

Tréninková data jsou používána výukovým algoritmem k vytvoření hodnotícího modelu, který vypočítává relevanci dokumentů pro skutečné dotazy.

Uživatelé obvykle očekávají dokončení vyhledávacího dotazu v krátké době (například několik stovek milisekund pro vyhledávání na webu), což znemožňuje vyhodnotit komplexní model hodnocení pro každý dokument v korpusu, a proto je dvoufázové schéma použitý. Nejprve je identifikován malý počet potenciálně relevantních dokumentů pomocí jednodušších vyhledávacích modelů, které umožňují rychlé vyhodnocení dotazů, jako je vektorový prostorový model , booleovský model , vážený AND nebo BM25 . Tato fáze se nazývá vyhledávání špičkových dokumentů ${\ displaystyle k}$ a v literatuře bylo navrženo mnoho heuristiky, aby se urychlila, například pomocí skóre statické kvality dokumentu a stupňovitých indexů. Ve druhé fázi je k přeřazení těchto dokumentů použit přesnější, ale výpočetně nákladnější strojově naučený model.

V jiných oblastech

Algoritmy učení se zařazování byly použity v jiných oblastech, než je získávání informací:

Ve strojovém překladu pro hodnocení sady hypotetických překladů;
Ve výpočetní biologii pro klasifikaci kandidátských 3-D struktur v problému predikce proteinové struktury.
V systémech doporučení pro identifikaci seřazeného seznamu souvisejících zpravodajských článků, které lze doporučit uživateli poté, co si přečetl aktuální zpravodajský článek.
V softwarovém inženýrství byly pro lokalizaci chyb použity metody učení se pořadí.

Vektory funkcí

Pro usnadnění algoritmů MLR jsou páry dotazů a dokumentů obvykle reprezentovány numerickými vektory, které se nazývají vektory funkcí . Takový přístup se někdy nazývá pytel funkcí a je analogický modelu modelů slov a vektorového vesmírného modelu používaného při získávání informací pro reprezentaci dokumentů.

Komponenty takových vektorů se nazývají vlastnosti , faktory nebo hodnotící signály . Mohou být rozděleny do tří skupin (funkce z načítání dokumentů jsou uvedeny jako příklady):

Query-independent or static features-those features, which depending only on the document, but not on the query. Například PageRank nebo délka dokumentu. Takové funkce lze během indexování předpočítat v režimu offline. Mohou být použity k výpočtu statického skóre kvality (nebo statického hodnocení ) dokumentu, které se často používá k urychlení hodnocení vyhledávacích dotazů.
Dynamické nebo závislé funkce na dotazu- takové funkce, které závisí na obsahu dokumentu i na dotazu, například skóre TF-IDF nebo jiné funkce hodnocení, které nejsou strojově naučeny.
Funkce na úrovni dotazu nebo funkce dotazu , které závisí pouze na dotazu. Například počet slov v dotazu.

Některé příklady funkcí, které byly použity ve známé datové sadě LETOR :

TF, TF-IDF , BM25 a skóre modelování zón dokumentu (název, tělo, text kotvy, URL) pro daný dotaz;
Délky a součty IDF zón dokumentu;
PageRank dokumentu , pozice HITS a jejich varianty.

Výběr a navrhování dobrých funkcí je důležitou oblastí ve strojovém učení, kterému se říká inženýrství funkcí .

Hodnotící opatření

Existuje několik opatření (metrik), která se běžně používají k posouzení, jak dobře si algoritmus vede s tréninkovými daty, a ke srovnání výkonu různých algoritmů MLR. Problém s hodnocením pořadí je často přeformulován jako problém optimalizace s ohledem na jednu z těchto metrik.

Příklady hodnocení kvality hodnocení:

Průměrná průměrná přesnost (MAP);
DCG a NDCG ;
Precision @ n , NDCG@ n , kde „@ n “ označuje, že metriky jsou vyhodnoceny pouze na prvních n dokumentech;
Průměrná vzájemná hodnost ;
Kendall's tau ;
Spearman's rho .

DCG a jeho normalizovaná varianta NDCG jsou obvykle upřednostňovány v akademickém výzkumu, když se používá více úrovní relevance. Další metriky, jako je MAP, MRR a přesnost, jsou definovány pouze pro binární úsudky.

Nedávno bylo navrženo několik nových metrik hodnocení, které tvrdí, že modelují spokojenost uživatelů s výsledky vyhledávání lépe než metrika DCG:

Očekávaná reciproční hodnost (ERR);
Yandex 's pfound.

Obě tyto metriky jsou založeny na předpokladu, že uživatel s větší pravděpodobností přestane prohlížet výsledky vyhledávání po prozkoumání relevantnějšího dokumentu než po méně relevantním dokumentu.

Přístupy

Tie-Yan Liu z Microsoft Research Asia analyzoval ve své knize Learning to Rank for Information Retrieval stávající algoritmy pro učení se klasifikovat problémy . Zařadil je do tří skupin podle jejich vstupních prostorů, výstupních prostorů, prostorů hypotéz (základní funkce modelu) a ztrátových funkcí : bodový, párový a listový přístup. V praxi seznamové přístupy často překonávají párové přístupy a bodové přístupy. Toto tvrzení bylo dále podpořeno rozsáhlým experimentem o výkonu různých metod učení se řadit na velkou sbírku srovnávacích datových sad.

V této části bez dalšího upozornění označuje objekt, který má být hodnocen, například dokument nebo obrázek, označuje hypotézu s jednou hodnotou, označuje funkci s dvěma variacemi nebo s více variacemi a funkci ztráty. ${\ displaystyle x}$ ${\ displaystyle f (x)}$ ${\ displaystyle h (\ cdot)}$ ${\ Displaystyle L (\ cdot)}$

Bodový přístup

V tomto případě se předpokládá, že každá dvojice dotaz-dokument v tréninkových datech má číselné nebo pořadové skóre. Potom lze problém učení-pořadí ohodnotit regresním problémem-vzhledem k jediné dvojici dotaz-dokument předvídejte jeho skóre. Formálně řečeno, bodový přístup má za cíl naučit se funkci předpovídající skutečnou hodnotu nebo pořadové skóre dokumentu pomocí funkce ztráty . ${\ displaystyle f (x)}$ ${\ displaystyle x}$ ${\ Displaystyle L (f, x_ {j}, y_ {j})}$

K tomuto účelu lze snadno použít řadu stávajících algoritmů strojového učení pod dohledem . Algoritmy řadové regrese a klasifikace lze také použít v bodovém přístupu, když se používají k predikci skóre jednoho páru dotaz-dokument, a to vyžaduje malý, konečný počet hodnot.

Párový přístup

V tomto případě je problém učení se řadit aproximován problémem klasifikace-učením se binárního klasifikátoru, který dokáže určit, který dokument je v dané dvojici dokumentů lepší. Klasifikátor vezme jako vstup dva obrázky a cílem je minimalizovat ztrátovou funkci . Funkce ztráty může odrážet průměrný počet inverzí v pořadí. ${\ displaystyle h (x_ {u}, x_ {v})}$ ${\ Displaystyle L (h; x_ {u}, x_ {v}, y_ {u, v})}$

V mnoha případech je binární klasifikátor implementován s funkcí bodování . RankNet jako příklad přizpůsobuje model pravděpodobnosti a definuje , že odhadovaná pravděpodobnost dokumentu má vyšší kvalitu než : ${\ 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) = {\ text {CDF}} (f (x_ {u})-f (x_ {v})),}

kde je kumulativní distribuční funkce , například standardní logistický CDF , tzn ${\ displaystyle {\ text {CDF}} (\ cdot)}$

{\ displaystyle {\ text {CDF}} (x) = {\ frac {1} {1+ \ exp \ left [-x \ right]}}.}

Seznamový přístup

Tyto algoritmy se pokoušejí přímo optimalizovat hodnotu jednoho z výše uvedených hodnotících opatření, zprůměrovaných ze všech dotazů v tréninkových datech. To je obtížné, protože většina hodnotících opatření nepředstavuje spojité funkce s ohledem na parametry hodnotícího modelu, a proto je třeba používat spojité aproximace nebo meze hodnotících opatření.

Seznam metod

Částečný seznam publikovaných algoritmů pořadí učení je uveden níže s roky prvního zveřejnění každé metody:

Rok	název	Typ	Poznámky
1989	OPRF	2 bodově	Polynomiální regrese (namísto strojového učení se tato práce týká rozpoznávání vzorů, ale myšlenka je stejná)
1992	SLR	2 bodově	Fázová logistická regrese
1994	NMOpt	2 listwise	Nemetrická optimalizace
1999	MART (více aditivních regresních stromů)	2 po párech
2000	Žebříček SVM (RankSVM)	2 po párech	Je k dispozici novější expozice, která popisuje hodnocení aplikace pomocí protokolů prokliku.
2002	Žert	1 bodově	Obyčejná regrese.
2003	RankBoost	2 po párech
2005	RankNet	2 po párech
2006	IR-SVM	2 po párech	Hodnocení SVM s normalizací na úrovni dotazu ve ztrátové funkci.
2006	LambdaRank	po páru/seznamu	RankNet, ve kterém je funkce párové ztráty vynásobena změnou IR metriky způsobenou swapem.
2007	AdaRank	3 listwise
2007	Upřímný	2 po párech	Na základě RankNet používá jinou ztrátovou funkci - ztrátu věrnosti.
2007	GBRank	2 po párech
2007	ListNet	3 listwise
2007	McRank	1 bodově
2007	QBRank	2 po párech
2007	RankCosine	3 listwise
2007	RankGP	3 listwise
2007	PořadíRLS	2 po párech	Regulované pořadí založené na nejmenších čtvercích. Práce je rozšířena o učení se hodnotit z obecných preferenčních grafů.
2007	^Mapa SVM	3 listwise
2008	LambdaSMART/LambdaMART	po páru/seznamu	Vítězný příspěvek v nedávné soutěži Yahoo Learning to Rank využil soubor modelů LambdaMART. Na základě MART (1999) „LambdaSMART“, pro Lambda-submodel-MART, nebo LambdaMART pro případ bez submodelu (https://www.microsoft.com/en-us/research/wp-content/uploads/2016/ 02/tr-2008-109.pdf ).
2008	ListMLE	3 listwise	Na základě ListNet.
2008	PermuRank	3 listwise
2008	SoftRank	3 listwise
2008	Upřesnění hodnocení	2 po párech	Semi-dohlížený přístup k učení se hodnotit, který používá Boosting.
2008	SSRankBoost	2 po párech	Rozšíření RankBoost pro učení s částečně označenými daty (semi-supervised learning to rank)
2008	SortNet	2 po párech	SortNet, adaptivní algoritmus hodnocení, který objednává objekty pomocí neurální sítě jako komparátoru.
2009	MPBoost	2 po párech	Varianta RankBoost zachovávající velikost. Myšlenka je taková, že čím nerovnější jsou štítky dvojice dokumentů, tím těžší by se měl algoritmus pokusit je ohodnotit.
2009	BoltzRank	3 listwise	Na rozdíl od dřívějších metod BoltzRank vytváří hodnotící model, který během dotazu hledí nejen na jeden dokument, ale také na páry dokumentů.
2009	BayesRank	3 listwise	Metoda kombinuje model Plackett-Luce a neuronovou síť, aby minimalizovala očekávané Bayesovo riziko související s NDCG z hlediska rozhodování.
2010	NDCG Boost	3 listwise	Posilující přístup k optimalizaci NDCG.
2010	GBlend	2 po párech	Rozšiřuje GBRank na problém učení se míchat při společném řešení více problémů s hodnocením učení s některými sdílenými funkcemi.
2010	IntervalRank	2 po párech a po seznamu
2010	CRR	2 bodově & párově	Kombinovaná regrese a hodnocení. Používá stochastický gradientový sestup k optimalizaci lineární kombinace bodové kvadratické ztráty a párových ztrát závěsu z Ranking SVM.
2014	LCR	2 po párech	Předpoklad nízké nízké hodnosti při hodnocení spolupráce. Na WWW'14 obdržel cenu za nejlepší studentský papír.
2015	FaceNet	po párech	Hodnocuje obrázky tváří s metrikou tripletů prostřednictvím hluboké konvoluční sítě.
2016	XGBoost	po párech	Podporuje různé cíle hodnocení a metriky hodnocení.
2017	Hodnocení ES	listwise	Evoluční strategie Naučte se hodnotit techniku se 7 metrikami hodnocení fitness
2018	PolyRank	po párech	Učí se současně hodnocení a podkladový generativní model z párových srovnání.
2018	FATE-Net/FETA-Net	listwise	Konstruovatelné architektury typu end-to-end, které explicitně zohledňují všechny položky při modelování kontextových efektů.
2019	FastAP	listwise	Optimalizuje průměrnou přesnost, aby se naučil hluboké vložení
2019	Moruše	listwise & hybridní	Naučí se zásady hodnocení maximalizující více metrik v celé datové sadě
2019	DirectRanker	po párech	Zobecnění architektury RankNet
2020	PRM	po párech	Transformátorová síť kódující jak závislosti mezi položkami, tak interakce mezi uživatelem a položkami

Poznámka: Jelikož většinu algoritmů učení pod dohledem lze aplikovat na bodové případy, výše jsou uvedeny pouze ty metody, které jsou speciálně navrženy s ohledem na hodnocení.

Dějiny

Norbert Fuhr představil obecnou myšlenku MLR v roce 1992, popisující učební přístupy při získávání informací jako zobecnění odhadu parametrů; konkrétní variantu tohoto přístupu (pomocí polynomické regrese ) zveřejnil o tři roky dříve. Bill Cooper navrhl logistickou regresi pro stejný účel v roce 1992 a použil ji se svou výzkumnou skupinou v Berkeley k výcviku úspěšné funkce hodnocení pro TREC . Manning a kol. naznačují, že tyto rané práce dosáhly ve své době omezených výsledků kvůli málo dostupným údajům o školení a špatným technikám strojového učení.

Několik konferencí, jako NIPS , SIGIR a ICML, mělo od poloviny dvacátých let (desetiletí) workshopy věnované problému učení se hodnosti.

Praktické využití vyhledávači

Komerční webové vyhledávače začaly používat strojově naučené systémy hodnocení od roku 2000 (desetiletí). Jedním z prvních vyhledávačů, který jej začal používat, byl AltaVista (později jeho technologii získala Overture a poté Yahoo ), která v dubnu 2003 spustila funkci posilování gradientu -vyškolené.

Bing je hledání je řekl, aby byl poháněn RankNet algoritmus, který byl vynalezen v Microsoft Research v roce 2005.

V listopadu 2009 ruský vyhledávač Yandex oznámil, že výrazně zvýšil kvalitu vyhledávání díky nasazení nového patentovaného algoritmu MatrixNet , což je varianta metody zesílení gradientu, která využívá zapomnětlivé rozhodovací stromy. Nedávno také sponzorovali strojově naučenou žebříčkovou soutěž „Internetová matematika 2009“ na základě produkčních dat vlastního vyhledávače. Společnost Yahoo vyhlásila podobnou soutěž v roce 2010.

Od roku 2008, Google ‚s Peter Norvig popíral, že jejich vyhledávač spoléhá výhradně na strojově naučili pořadí. CEO společnosti Cuil , Tom Costello, navrhuje, aby upřednostňovali ručně vyráběné modely, protože mohou překonat strojově naučené modely, pokud jsou měřeny metrikami, jako je míra prokliku nebo čas na vstupní stránce, protože strojově naučené modely „zjistí, co lidé říkají, že se jim líbí, ne to, co se lidem skutečně líbí “.

V lednu 2017 byla tato technologie zahrnuta do open source vyhledávače Apache Solr ™, díky čemuž je strojově naučená vyhledávací pozice široce dostupná i pro podnikové vyhledávání.

Zranitelnosti

Podobně jako rozpoznávací aplikace v počítačovém vidění se také ukázalo, že nedávné algoritmy hodnocení založené na neuronových sítích jsou náchylné k skrytým nepřátelským útokům , a to jak na kandidáty, tak na dotazy. S malými poruchami nepostřehnutelnými pro lidské bytosti lze pořadí pořadí libovolně měnit. Kromě toho se ukázalo, že jsou možné modelové agnostické přenositelné kontradiktorní příklady, což umožňuje kontroverzní útoky black-boxu na systémy s hlubokým hodnocením bez nutnosti přístupu k jejich podkladovým implementacím.

Robustnost těchto systémů hodnocení lze naopak zlepšit pomocí kontradiktorní obrany, jako je Madryova obrana.

Languages

In other projects