Alai

În 2004, Microsoft Research și echipa Microsoft’s Web Search au început un efort comun pentru a îmbunătăți relevanța rezultatelor căutărilor noastre pe web. A urmat un efort susținut care, în următorii câțiva ani, a dus la expedierea a trei generații de algoritmi de clasificare a căutărilor web, culminând cu ansamblurile de arbori potențați pe care Bing le utilizează în prezent. Pe primul dintre acești algoritmi de clasificare l-am numit RankNet. Recent, articolul RankNet, care a fost publicat în Conferința internațională privind învățarea mașinilor (ICML) în 2005, a câștigat premiul „Test of Time” al ICML, un premiu acordat în fiecare an acelui articol prezentat la conferință cu zece ani mai devreme, despre care s-a considerat că a avut cel mai mare impact academic global în anii care au trecut. Aceasta este o mare onoare și, de asemenea, o oportunitate de a arunca o privire retrospectivă și de a evalua progresul nostru din ultimul deceniu. În acest articol, aș dori să spun această poveste.

Cercetarea web funcționează, în esență, luând interogarea utilizatorului și evaluând relevanța fiecărui document indexat pentru aceasta. Nu toate paginile web se află în index, dar indexul conține totuși sute de miliarde de documente, stocate într-o structură de date specială pentru a face căutarea rapidă. Deoarece rezultatele de top trebuie să fie prezentate utilizatorului în câteva sute de milisecunde, acest lucru necesită un proces de filtrare și clasificare extrem de eficient. Clasificatorii descriși aici lucrează pe un subset (încă mare) de documente, ales cu ajutorul acestui proces inițial de filtrare rapidă. Practic, un clasificator funcționează prin luarea unei liste de numere, fiecare dintre acestea măsurând calitatea unei anumite corespondențe între o anumită interogare și un anumit document într-un anumit mod (de exemplu, un număr binar care reprezintă dacă interogarea conține sau nu un cuvânt în titlul documentului). Clasificatorul face apoi legătura între această listă de numere și o singură măsură a relevanței, care este apoi utilizată pentru a clasifica toate documentele pentru interogarea respectivă. Lista ordonată de numere pe care ierarhizatorul o mapează la un singur scor se numește vector de caracteristici.

Atunci, atunci când este utilizat în timpul execuției, pentru o anumită interogare, ierarhizatorul ia vectorul de caracteristici pentru fiecare pereche interogare/document și îl mapează la un număr care surprinde relevanța acelui document pentru interogare. RankNet este un model de rețea neuronală de tip feedforward. Înainte de a putea fi utilizat, parametrii săi trebuie să fie învățați folosind o cantitate mare de date etichetate, numite set de antrenament. Setul de antrenament este format dintr-un număr mare de perechi interogare/document, unde, pentru fiecare pereche, experții umani atribuie un număr care evaluează calitatea relevanței documentului pentru interogarea respectivă. Deși etichetarea datelor este o sarcină lentă și intensivă pentru oameni, formarea rețelei, având în vedere datele etichetate, este complet automată și destul de rapidă. Sistemul utilizat de Microsoft în 2004 pentru a antrena clasificatorul a fost numit The Flying Dutchman. Am constatat că, în timp ce The Flying Dutchman a avut nevoie de mai multe zile și de un cluster pentru a produce un model antrenat, RankNet a fost capabil să producă un model de clasificare în doar câteva ore, folosind doar o singură mașină. RankNet a oferit, de asemenea, o relevanță semnificativ îmbunătățită față de clasificatorul utilizat anterior, deoarece rețelele neuronale pot modela o gamă foarte largă de corespondențe posibile, în timp ce sistemul anterior era limitat doar la corespondențe liniare.

Până aici totul bine, dar am fi putut face mai bine? Răspunsul este Da, dar pentru a vedea de ce, trebuie să explic puțin despre cum este antrenat RankNet. Pentru fiecare interogare din setul de instruire, pentru fiecare pereche de documente care urmează să fie clasificate pentru acea interogare, lui RankNet i se arată cei doi vectori de caracteristici și apoi își ajustează puțin parametrii, folosind o metodă numită Stochastic Gradient Descent (SGD), astfel încât scorurile de ieșire ajustate pentru cele două caracteristici să se deplaseze în direcția corectă – adică, scorul pentru documentul mai relevant crește, iar cel pentru documentul mai puțin relevant, scade. Dar acest lucru înseamnă că RankNet va depune eforturi pentru a ridica documentele foarte relevante care se află foarte jos în clasament și, de asemenea, pentru a coborî documentele cu punctaj ridicat, dar mai puțin relevante. Cheltuindu-și resursele în acest mod, nu acordă atât de multă atenție pe cât ar trebui doar primelor câteva linkuri care sunt afișate utilizatorului. De fapt, la momentul respectiv, criteriul nostru de evaluare era un scor numit NDCG, care oferă un singur număr care evaluează calitatea generală a clasamentului, punând un accent mult mai mare pe primele câteva rezultate care sunt afișate utilizatorului. Astfel, NDCG este o măsură mai naturală pentru căutarea pe internet decât eroarea pe perechi. Acest lucru ne-a pus în fața unei provocări: SGD se reduce la o căutare într-un spațiu continuu, dar NDCG este în mod fundamental o măsură discretă, în sensul că valoarea sa se modifică doar atunci când cel puțin două documente își schimbă poziția în lista de clasament. Modificări suficient de mici în scorurile modelului nu produc nicio schimbare în NDCG și, din moment ce SGD funcționează prin explorarea schimbărilor mici în scoruri, este greu de înțeles cum să optimizăm NDCG folosind SGD.

Am găsit un răspuns la această enigmă, pe care l-am numit LambdaRank. Trucul a fost să observăm că întreaga procedură de instruire pentru o rețea neuronală are nevoie doar de gradienții funcției de cost, nu de funcția de cost în sine. Vă puteți gândi la aceste gradiente ca la niște săgeți mici atașate la fiecare document din lista clasată, indicând direcția în care am dori ca aceste documente să se deplaseze. LambdaRank a luat pur și simplu gradienții RankNet, despre care știam că funcționează bine, și i-a scalat în funcție de modificarea NDCG constatată prin schimbarea fiecărei perechi de documente. Am constatat că această instruire a generat modele cu o relevanță semnificativ îmbunătățită (măsurată prin NDCG) și a avut ca bonus suplimentar descoperirea unui alt truc care a îmbunătățit viteza generală de instruire (atât pentru RankNet, cât și pentru LambdaRank). Mai mult decât atât, în mod surprinzător, am găsit dovezi empirice (a se vedea, de asemenea, această lucrare) că procedura de instruire optimizează de fapt NDCG, chiar dacă metoda, deși intuitivă și sensibilă, nu are o astfel de garanție.

Atât de bine până acum, dar din nou, am fi putut face mai bine? Răspunsul a fost din nou Da. Cunoșteam o clasă de modele numite „boosted tree ensembles” despre care se știa că fac clasificatoare multiclasă foarte puternice. Ce se întâmplă dacă tratăm problema de clasificare ca pe o problemă de clasificare multiclasă, cu câte o clasă pentru fiecare dintre cele cinci niveluri de relevanță identificate în setul de instruire? Am constatat că acest lucru a dat rezultate mai bune decât LambdaRank (în special o variantă numită clasificare multiclasă ordinală). Arborele de amplificare are și avantajul suplimentar că poate gestiona cu ușurință caracteristici categorice și alte tipuri de caracteristici discrete, care sunt mai puțin potrivite pentru rețelele neuronale. Am crezut că aceste rezultate se datorează unei mai bune adaptări a acestei clase de modele la datele noastre și, prin urmare, întrebarea firească a fost dacă putem combina modelele boosted tree cu ideea LambdaRank, pentru a obține ce e mai bun din ambele lumi. Antrenarea unui model de arbore cu creștere poate fi privită, de asemenea, ca o formă de SGD, astfel încât răspunsul a fost da, sub forma unui model pe care l-am numit LambdaMART. LambdaMART a avut un avantaj suplimentar: antrenarea modelelor de ansamblu de arbori poate fi accelerată în mod semnificativ față de echivalentul rețelelor neuronale (această lucrare, condusă de O. Dekel, nu este încă publicată). Acest lucru ne permite să ne antrenăm cu seturi de date mult mai mari, ceea ce oferă, din nou, o precizie îmbunătățită a clasificării.

Cum se compară clasificatorii noștri cu alții din industrie? În 2010, Yahoo! a organizat o provocare de învățare a clasificării, una dintre pistele căreia a fost concepută pentru a vedea cine avea cel mai bun algoritm de clasificare a căutărilor pe internet. 1.055 de echipe s-au înscris la această provocare. Echipa noastră a câștigat provocarea, folosind un ansamblu de modele LambdaMART.

Cu o privire retrospectivă asupra ultimului deceniu, poate că cea mai evidentă lecție tehnică este importanța vitezei de instruire. O instruire mai rapidă permite atât mai multe experimente, cât și utilizarea unor seturi de date mai mari. Cred că acești doi factori sunt în cele din urmă mai importanți decât algoritmii de bază utilizați, atâta timp cât aceștia din urmă sunt modele suficient de expresive pentru sarcina în cauză. Cealaltă „lecție de viață” pe care o trag din această experiență este importanța de a fi perseverent, dar mai ales importanța darului de a putea lucra cu colegi minunați, în grupurile de produse, în Microsoft Research și în mediul academic.

Chris Burges este cercetător principal și manager de cercetare la Microsoft Research, unde se află din anul 2000. Înainte de aceasta, a lucrat la AT&T Bell Labs, la care s-a alăturat în 1986. Înainte de aceasta, a fost bursier postdoctoral la Departamentul de Fizică Teoretică de la MIT, la care s-a alăturat după ce și-a obținut doctoratul în fizică la Brandeis, în urma unei diplome cu onoruri de primă clasă în fizică și matematică la Oxford. Interesele sale s-au extins de la ingineria sistemelor de rețele mari de comunicații (AT&T încă folosește algoritmii săi pentru a direcționa mai multe rețele cheie), la rețele neuronale pentru recunoașterea scrisului de mână și a amprentelor (a lucrat la un sistem folosit acum pentru a citi zilnic milioane de cecuri și, de fapt, lunga sa coborâre în domeniul învățării automate a fost declanșată de o demonstrație deosebit de interesantă a unei rețele neuronale care recunoștea cifrele scrise de mână la începutul anilor ’90), mașinile cu suport vectorial (a avut norocul de a lucra cu Vladimir Vapnik, co-creatorul SVM, în primele zile, și a scris un tutorial pe care unii l-au apreciat), amprentarea audio (munca sa este utilizată în prezent în Xbox și Windows Media Player pentru a identifica muzica), verificarea vorbitorilor, recuperarea informațiilor și clasificarea (algoritmul său de clasificare este utilizat în prezent de Bing pentru căutarea pe internet). În prezent, pasiunea lui Chris se concentrează pe dezvoltarea de noi abordări pentru înțelegerea automată a textului la scară largă, care, deși este adevărat că este extrem de ambițioasă, este posibil să ne învețe ceva, dacă nu vom înceta să încercăm. Chris a fost copreședinte al programului Neural Information Processing Systems 2012 și copreședinte general al NIPS 2013.

Pentru mai multe știri despre cercetarea în domeniul informaticii, vizitați ResearchNews.com.

.