Nell'apprendimento automatico, l'apprendimento di ranking, detto comunemente learning to rank (LTR) o machine-learned ranking (MLR), consiste nell'applicazione di tecniche di apprendimento, spesso supervisionato, semi-supervisionato o per rinforzo, per la costruzione di modelli di ranking utili in compiti di ritrovamento di informazioni o nei sistemi di raccomandazione. I dati di addestramento possono consistere, ad esempio, in una lista di elementi assieme alla specifica di un ordinamento parziale fra coppie di elementi. Tale ordinamento viene tipicamente indotto da punteggi numerici od ordinali oppure da un giudizio binario (ad es. "rilevante" o "non rilevante") per ciascun elemento. L'obiettivo della costruzione di un modello di ranking è quello di stabilire la posizione in graduatoria di nuovi elementi non considerati in fase di addestramento, in maniera simile alla classificazione dei dati di addestramento.
Approcci Gli approcci all'apprendimento di ordinamenti vengono spesso classificati utilizzando le tre seguenti categorie: puntuale (in cui vengono classificati i singoli oggetti), a coppie (in cui vengono classificate coppie di elementi in un ordine relativo) e per lista (in cui viene ordinato l'intero elenco di oggetti).
Gli algoritmi esistenti per problemi LTR sono stati cosi categorizzati in base ai loro spazi di input, spazi di output, spazi di ipotesi (la funzione principale del modello) e alle funzioni di perdita adottate. Nella pratica, gli approcci per lista spesso superano gli approcci a coppie e puntuali. Ciò stata ulteriormente confermato da un esperimento su vasta scala volto a misurare le prestazioni di diversi metodi LTR su un'ampia raccolta di dataset di riferimento.
In questa sezione, a meno di diversa indicazione, indica un oggetto da valutare, ad esempio un documento o un'immagine, indica un'ipotesi a valore singolo, indica una funzione bivariata o multivariata e indica la funzione di perdita (loss).
Approccio puntuale In questo caso, si presume che ogni coppia query-risultato nei dati di addestramento riceva un punteggio numerico o ordinale. Quindi il problema LTR può essere approssimato attraverso un problema di regressione: data una singola coppia query-risultato, prevederne il punteggio. Formalmente, l'approccio puntuale mira ad apprendere una funzione che di predizione dei punteggio reale od ordinale di un oggetto utilizzando la funzione di perdita .
A tal fine è possibile utilizzare una serie di algoritmi di apprendimento supervisionato disponibili. Nell'approccio puntuale possono essere utilizzati anche algoritmi di regressione ordinale e di classificazione utili a prevedere il punteggio di una singola coppia query-risultato richiedendo un numero di valori limitato e finito.
Approccio a coppie In tal caso, il problema LTR viene approssimato come problema di classificazione: l'apprendimento di un classificatore binario in grado di stabilire quale di due oggetti sia migliore in una data coppia. Il classificatore deve prendere in input due oggetti e l'obiettivo è minimizzare una loss . Tale funzione riflette tipicamente il numero e la grandezza delle inversioni nell'ordinamento indotto.
In molti casi, il classificatore binario viene implementato con una funzione di valutazione (scoring) . Ad esempio, RankNet adatta un modello probabilistico e definisce come stima della probabilità che l'elemento sia qualitativamente superiore a :
dove è una funzione di distribuzione cumulativa, ad esempio la CDF logistica standard, ovvero
Approccio per lista Questi algoritmi cercano di ottimizzare direttamente il valore di una delle misure di valutazione sopra indicate, calcolando la media di tutte le query sui dati di addestramento. Ciò è spesso difficile nella pratica perché la maggior parte delle misure di valutazione non sono funzioni continue rispetto ai parametri del modello di classificazione e quindi è necessario ricorrere ad approssimazioni continue o limiti sulle misure di valutazione come avviene, ad esempio, nell'algoritmo SoftRank . LambdaMART è un algoritmo a coppie che, empiricamente, si è dimostrato capace di approssimare funzioni obiettivo a liste.
Misure di valutazione Esistono diverse misure (metriche) comunemente utilizzate per valutare l'efficacia di un algoritmo sui dati di addestramento e per confrontare le prestazioni di diversi algoritmi LTR. Spesso un problema LTR viene riformulato come problema di ottimizzazione rispetto a una di queste metriche.
Esempi di misure di qualità del ranking:
Mean average precision (MAP); DCG e NDCG; Precisione@n, NDCG@n dove "@n" denota il fatto che le metriche siano valutate solo sui primi n elementi; Mean reciprocal rank; tau di Kendall; rho di Spearman.
La DCG e la sua variante normalizzata NDCG sono solitamente preferite nella ricerca accademica quando vengono impiegati più livelli di rilevanza . Altre metriche, come MAP, MRR e precisione, sono definite solo per giudizi binari. Recentemente sono stati proposti diversi nuovi parametri di valutazione che sostengono di modellare la soddisfazione degli utenti relativamente ai risultati di ricerca in modo migliore rispetto alla DCG:
Expected reciprocal rank (ERR) ; pfound di Yandex .
Entrambe le metriche si basano sul presupposto che l'utente sia più propenso a smettere di guardare i risultati di ricerca dopo aver esaminato un documento più pertinente piuttosto che dopo averne esaminato uno meno pertinente.
Note
Categoria:Apprendimento automatico Categoria:Recupero dell'informazione