Apprendimento di ranking
Nell'apprendimento automatico, l'apprendimento di ranking, detto comunemente learning to rank[1] (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[2]. 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
modificaGli 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 [1] 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. [3]
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
modificaIn 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
modificaIn 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 [4] 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
modificaQuesti 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 [5]. LambdaMART è un algoritmo a coppie che, empiricamente, si è dimostrato capace di approssimare funzioni obiettivo a liste.[6]
Misure di valutazione
modificaEsistono 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 [7]. 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:
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
modifica- ^ a b (EN) Tie-Yan Liu, Learning to Rank for Information Retrieval, in Foundations and Trends® in Information Retrieval, vol. 3, n. 3, 2007, pp. 225–331, DOI:10.1561/1500000016.
- ^ Mehryar Mohri, Afshin Rostamizadeh e Ameet Talwalkar, Foundations of machine learning, collana Adaptive computation and machine learning, The MIT Press, 2012, ISBN 978-0-262-01825-8.
- ^ Niek Tax, Sander Bockting e Djoerd Hiemstra, A cross-benchmark comparison of 87 learning to rank methods, in Information Processing & Management, vol. 51, n. 6, 1º novembre 2015, pp. 757–772, DOI:10.1016/j.ipm.2015.07.002.
- ^ Chris Burges, Tal Shaked e Erin Renshaw, Learning to rank using gradient descent, in Proceedings of the 22nd international conference on Machine learning, Association for Computing Machinery, 7 agosto 2005, pp. 89–96, DOI:10.1145/1102351.1102363.
- ^ Michael Taylor, John Guiver e Stephen Robertson, SoftRank: optimizing non-smooth rank metrics, in Proceedings of the 2008 International Conference on Web Search and Data Mining, Association for Computing Machinery, 11 febbraio 2008, pp. 77–86, DOI:10.1145/1341531.1341544.
- ^ C. Burges, From RankNet to LambdaRank to LambdaMART: An Overview (PDF), 23 giugno 2010. URL consultato il 29 settembre 2025.
- ^ (EN) Christopher Manning e Prabhakar Raghavan, Learning to Rank (lecture 15) (PPT), su Wayback machine. URL consultato il 30 settembre 2025 (archiviato dall'url originale il 4 gennaio 2011).
- ^ (EN) Olivier Chapelle, Donald Metlzer e Ya Zhang, Expected reciprocal rank for graded relevance, ACM, 2 novembre 2009, pp. 621–630, DOI:10.1145/1645953.1646033.
- ^ (RU) Gulin A.; Karpovich P.; Raskovalov D.; Segalovich I., Yandex at ROMIP'2009: optimization of ranking algorithms by machine learning methods, in Proceedings of ROMIP'09, 2009, pp. 163-168 (archiviato dall'originale il 22 novembre 2009) .