Alai

Nel 2004, Microsoft Research e il team Web Search di Microsoft hanno iniziato uno sforzo congiunto per migliorare la rilevanza dei nostri risultati di ricerca web. Ne è seguito uno sforzo sostenuto che, nel corso degli anni successivi, ha portato alla spedizione di tre generazioni di algoritmi di ranking per la ricerca sul web, culminando negli insiemi di alberi potenziati che Bing utilizza oggi. Abbiamo chiamato il primo di questi algoritmi di ranking RankNet. Recentemente l’articolo RankNet, che è stato pubblicato nella International Conference on Machine Learning (ICML) nel 2005, ha vinto il premio “Test of Time” della ICML, un premio dato ogni anno a quel singolo articolo presentato alla conferenza dieci anni prima che è stato giudicato avere il più alto impatto accademico complessivo negli anni successivi. Questo è un grande onore e anche un’opportunità per dare uno sguardo indietro e valutare i nostri progressi negli ultimi dieci anni. In questo articolo, vorrei raccontare questa storia.

La ricerca sul web funziona essenzialmente prendendo la richiesta dell’utente e valutando la pertinenza di ogni documento indicizzato ad essa. Non tutte le pagine web sono nell’indice, ma l’indice contiene comunque centinaia di miliardi di documenti, memorizzati in una speciale struttura di dati per rendere veloce la ricerca. Poiché i risultati migliori devono essere presentati all’utente in poche centinaia di millisecondi, questo richiede un processo di filtraggio e classificazione estremamente efficiente. I classificatori qui descritti lavorano su un (ancora grande) sottoinsieme di documenti, scelti usando questo veloce processo di filtraggio iniziale. Fondamentalmente, un classificatore funziona prendendo una lista di numeri, ognuno dei quali misura la qualità di una particolare corrispondenza query/documento in un modo particolare (per esempio, un numero binario che rappresenta se la query contiene o meno una parola nel titolo del documento). Il classificatore quindi mappa quella lista di numeri in una singola misura di rilevanza, che viene poi usata per ordinare tutti i documenti per quella query. L’elenco ordinato di numeri che il classificatore mappa in un singolo punteggio è chiamato vettore di caratteristiche.

Quindi quando viene utilizzato in fase di esecuzione, per una data query, il classificatore prende il vettore di caratteristiche per ogni coppia query/documento e lo mappa in un numero che cattura la rilevanza di quel documento per la query. RankNet è un modello di rete neurale feedforward. Prima che possa essere utilizzato, i suoi parametri devono essere appresi utilizzando una grande quantità di dati etichettati, chiamati set di allenamento. L’insieme di allenamento consiste in un gran numero di coppie query/documento, dove per ogni coppia, un numero che valuta la qualità della rilevanza del documento per quella query è assegnato da esperti umani. Sebbene l’etichettatura dei dati sia un compito lento e ad alta intensità umana, l’addestramento della rete, dati i dati etichettati, è completamente automatico e abbastanza veloce. Il sistema usato da Microsoft nel 2004 per l’addestramento del classificatore era chiamato The Flying Dutchman. Abbiamo scoperto che, mentre The Flying Dutchman ha impiegato diversi giorni e un cluster per produrre un modello addestrato, RankNet è stato in grado di produrre un modello di classificazione in solo un paio d’ore usando una sola macchina. RankNet ha anche dato una rilevanza significativamente migliorata rispetto al classificatore precedentemente utilizzato, poiché le reti neurali possono modellare una gamma molto ampia di possibili mappature, mentre il sistema precedente era limitato solo alle mappature lineari.

Fin qui tutto bene, ma avremmo potuto fare meglio? La risposta è sì, ma per capire perché, devo spiegare un po’ come viene addestrato RankNet. Per ogni query nel set di allenamento, per ogni coppia di documenti da classificare per quella query, a RankNet vengono mostrati i due vettori di caratteristiche e poi aggiusta un po’ i suoi parametri, usando un metodo chiamato Stochastic Gradient Descent (SGD), in modo che i punteggi di output aggiustati per le due caratteristiche si muovano nella giusta direzione – cioè, il punteggio per il documento più rilevante aumenta, e quello per quello meno, diminuisce. Ma questo significa che RankNet lavorerà duramente per aumentare i documenti altamente rilevanti che sono molto in basso nella classifica, e anche per abbassare i documenti ad alto punteggio ma meno rilevanti. Spendendo le sue risorse in questo modo, non presta tanta attenzione quanto dovrebbe solo ai primi pochi link che vengono mostrati all’utente. In effetti, all’epoca, la nostra metrica di valutazione era un punteggio chiamato NDCG, che dà un singolo numero che valuta la qualità complessiva del ranking, con un’enfasi molto maggiore sui primi risultati che vengono mostrati all’utente. NDCG è quindi una misura più naturale per la ricerca web rispetto all’errore a coppie. Questo ci ha presentato una sfida: SGD si riduce a una ricerca in uno spazio continuo, ma NDCG è fondamentalmente una misura discreta, in quanto il suo valore cambia solo quando almeno due documenti cambiano posizione nella lista classificata. Cambiamenti sufficientemente piccoli nei punteggi del modello non danno alcun cambiamento in NDCG, e poiché SGD funziona esplorando piccoli cambiamenti nei punteggi, è difficile vedere come ottimizzare NDCG usando SGD.

Abbiamo trovato una risposta a questo enigma, che abbiamo chiamato LambdaRank. Il trucco è stato quello di notare che l’intera procedura di addestramento di una rete neurale ha bisogno solo dei gradienti della funzione di costo, non della funzione di costo stessa. Potete pensare a questi gradienti come a piccole frecce attaccate ad ogni documento nella lista classificata, indicando in quale direzione vorremmo che quei documenti si muovessero. LambdaRank ha semplicemente preso i gradienti RankNet, che sapevamo funzionare bene, e li ha scalati per il cambiamento in NDCG trovato scambiando ogni coppia di documenti. Abbiamo scoperto che questo addestramento ha generato modelli con una rilevanza significativamente migliorata (come misurato da NDCG) e ha avuto un ulteriore bonus di scoprire un ulteriore trucco che ha migliorato la velocità complessiva di addestramento (sia per RankNet che per LambdaRank). Inoltre, sorprendentemente, abbiamo trovato prove empiriche (vedi anche questo articolo) che la procedura di addestramento ottimizza effettivamente NDCG, anche se il metodo, sebbene intuitivo e sensato, non ha tale garanzia.

Fin qui tutto bene, ma di nuovo, avremmo potuto fare meglio? La risposta è stata di nuovo Sì. Sapevamo di una classe di modelli chiamati insiemi di alberi potenziati che erano noti per fare classificatori multiclasse molto forti. Cosa succede se si tratta il problema del ranking come un problema di classificazione multiclasse, con una classe per ciascuno dei cinque livelli di rilevanza identificati nel set di allenamento? Abbiamo scoperto che questo dà risultati migliori rispetto a LambdaRank (in particolare una versione chiamata classificazione multiclasse ordinale). Gli alberi potenziati hanno l’ulteriore vantaggio di poter gestire facilmente caratteristiche categoriali e altri tipi di caratteristiche discrete, che sono meno adatte alle reti neurali. Abbiamo creduto che questi risultati fossero dovuti alla migliore idoneità di questa classe di modelli ai nostri dati, e quindi la domanda naturale è stata: possiamo combinare i modelli ad albero potenziati con l’idea del LambdaRank per ottenere il meglio dei due mondi? L’addestramento di un modello ad albero potenziato può anche essere visto come una forma di SGD, e quindi la risposta era sì, sotto forma di un modello che abbiamo chiamato LambdaMART. LambdaMART aveva un ulteriore vantaggio: l’addestramento dei modelli ad albero può essere accelerato in modo molto significativo rispetto all’equivalente a rete neurale (questo lavoro, condotto da O. Dekel, non è ancora pubblicato). Questo ci permette di allenarci con insiemi di dati molto più grandi, il che dà ancora una volta una migliore accuratezza delle classifiche.

Come sono i nostri classificatori rispetto ad altri nel settore? Nel 2010, Yahoo! ha organizzato una sfida di apprendimento per classificare, una traccia della quale era progettata per vedere chi aveva il miglior algoritmo di classificazione della ricerca web. 1.055 squadre si sono registrate per la sfida. Il nostro team ha vinto la sfida, usando un insieme di modelli LambdaMART.

Guardando indietro nell’ultimo decennio, forse la lezione tecnica più saliente è l’importanza della velocità di formazione. Un addestramento più veloce permette sia una maggiore sperimentazione che l’uso di set di dati più grandi. Credo che questi due fattori siano alla fine più importanti degli algoritmi sottostanti utilizzati, purché questi ultimi siano modelli sufficientemente espressivi per il compito da svolgere. L’altra “lezione di vita” che traggo da questa esperienza è l’importanza di essere persistenti, ma soprattutto, dell’importanza del dono di poter lavorare con colleghi meravigliosi, nei gruppi di prodotto, in Microsoft Research, e nel mondo accademico.

Chris Burges è un Principal Researcher e Research Manager in Microsoft Research, dove si trova dal 2000. Prima ha lavorato alla AT&T Bell Labs, dove è entrato nel 1986. Prima di questo è stato un borsista post-dottorato presso il Dipartimento di Fisica Teorica del MIT, dove è entrato dopo aver conseguito il dottorato in Fisica alla Brandeis, dopo una laurea con lode in Fisica e Matematica a Oxford. I suoi interessi hanno spaziato dall’ingegneria dei sistemi di grandi reti di comunicazione (AT&T usa ancora i suoi algoritmi per instradare diverse reti chiave), alle reti neurali per il riconoscimento della scrittura e della stampa automatica (ha lavorato su un sistema ora usato per leggere milioni di assegni al giorno, e in effetti la sua lunga discesa nell’apprendimento automatico è stata innescata da una dimostrazione particolarmente interessante di una rete neurale che riconosceva cifre scritte a mano nei primi anni 90), macchine vettoriali di supporto (ha avuto la fortuna di lavorare con Vladimir Vapnik, il co-creatore di SVM, nei primi giorni, e ha scritto un tutorial che è piaciuto ad alcune persone), fingerprinting audio (il suo lavoro è attualmente utilizzato in Xbox e Windows Media Player per identificare la musica), verifica degli altoparlanti, recupero delle informazioni, e classifica (il suo algoritmo di classifica è attualmente utilizzato da Bing per la ricerca web). L’attuale passione di Chris è lo sviluppo di nuovi approcci alla comprensione automatica scalabile e azionabile del testo, che, anche se dichiaratamente molto ambizioso, è ancora in grado di insegnarci qualcosa, a meno che non smettiamo di provarci. Chris è stato co-presidente del programma del Neural Information Processing Systems 2012 e co-presidente generale del NIPS 2013.

Per altre notizie sulla ricerca informatica, visita ResearchNews.com.