L'apprentissage par classement ou classement appris par machine (MLR) est l'application de l'apprentissage automatique – typiquement supervisé, semi-supervisé ou apprentissage par renforcement – dans la construction de fonction de classements pour les systèmes de recherche d'informationMehryar Mohri, Afshin Rostamizadeh, Ameet Talwalkar (2012) Foundations of Machine Learning, The MIT Press .. Les données d'entraînement se composent, par exemple, de listes d'éléments pour lesquelles un ordre partiel est spécifié entre les éléments de chaque liste. Cet ordre s'obtient typiquement en attribuant à chaque élément un score numérique ou ordinal, ou un jugement binaire (ex. « pertinent » ou « non pertinent »). L'objectif de construire le modèle de classement est de classer de nouvelles listes, non encore vues, d'une manière similaire aux classements figurant dans les données d'entraînement.

Applications

En recherche d'information 250px|thumb|Une architecture possible d'un moteur de recherche utilisant l'apprentissage par classement Le classement constitue un élément central de nombreux problèmes de recherche d'information, tels que la récupération de documents, le filtrage collaboratif, l'analyse de sentiments et la publicité en ligne.

Une architecture possible d'un moteur de recherche utilisant l'apprentissage par classement est présentée sur la figure ci-contre.

Les données d'entraînement se composent de requêtes et de documents associés, avec pour chacun un degré de pertinence. Ces données peuvent être préparées manuellement par des évaluateurs humains (ou « évaluateurs », comme Google les désigne), qui examinent les résultats pour certaines requêtes et déterminent la pertinence de chaque résultat. Il n'est pas réaliste de vérifier la pertinence de tous les documents, et une technique appelée « pooling » s'emploie typiquement – seuls les quelques premiers documents, récupérés par certains modèles de classement existants, sont vérifiés. Cette technique peut introduire un biais de sélection. Alternativement, les données d'entraînement se dérivent automatiquement par l'analyse des « clickthrough logs » (c'est-à-dire les résultats ayant fait l'objet de clics par les utilisateurs), chaînes de requêtes, ou par des fonctionnalités telles que SearchWiki de Google (désormais remplacé). Les clickthrough logs se montrent biaisés par la tendance des utilisateurs à cliquer sur les premiers résultats, supposés déjà bien classés.

Les données d'entraînement s'emploient ensuite par un algorithme d'apprentissage pour produire un modèle de classement qui calcule la pertinence des documents pour de réelles requêtes.

Typiquement, les utilisateurs attendent qu'une requête se termine en quelques centaines de millisecondes (comme dans la recherche sur le web), ce qui rend impossible l'évaluation d'un modèle de classement complexe sur chaque document du corpus. On emploie donc une procédure en deux phases. La première phase consiste à identifier un petit nombre de documents potentiellement pertinents à l'aide de modèles de recherche plus simples permettant une évaluation rapide des requêtes, tels que le modèle vectoriel, le modèle booléen ou le weighted AND, ou le BM25. Cette phase s'appelle « récupération des k meilleurs documents » et de nombreuses heuristiques ont été proposées dans la littérature pour l'accélérer, par exemple en utilisant le score de qualité statique d'un document et des index hiérarchisés. Dans la seconde phase, un modèle appris par machine, plus précis mais coûteux en calcul, se charge de reclasser ces documents.

Dans d'autres domaines Les algorithmes d'apprentissage par classement s'appliquent également en dehors de la recherche d'information : En traduction automatique pour classer un ensemble d'hypothétiques traductions; En biologie computationnelle pour classer les structures 3‑D candidates dans les problèmes de prédiction de la structure des protéines; Dans les système de recommandations pour identifier une liste classée d'articles d'actualité à recommander à un utilisateur après la lecture d'un article en coursYuanhua Lv, Taesup Moon, Pranam Kolari, Zhaohui Zheng, Xuanhui Wang, and Yi Chang, Learning to Model Relatedness for News Recommendation , in International Conference on World Wide Web (WWW), 2011..

Vecteurs de caractéristiques Pour la commodité des algorithmes MLR, les paires requête–document se représentent généralement sous forme de vecteurs numériques, appelés vecteur de caractéristiques. Une telle approche est parfois qualifiée de « sac de caractéristiques » et s'apparente au modèle sac de mots et au modèle vectoriel utilisés en recherche d'information pour la représentation des documents.

Les composantes de ces vecteurs s'appellent des caractéristiques, « facteurs » ou « signaux de classement ». On peut les diviser en trois groupes (des exemples de caractéristiques issues de la récupération de documents sont indiqués) : Caractéristiques indépendantes de la requête ou statiques – celles qui dépendent uniquement du document et non de la requête. Par exemple, PageRank ou la longueur d'un document. Ces caractéristiques se pré-calculent en mode hors ligne lors de l'indexation. Elles servent à calculer le « score de qualité statique » (ou « rang statique ») du document, souvent utilisé pour accélérer l'évaluation d'une requête de recherche. Caractéristiques dépendantes de la requête ou dynamiques – celles qui dépendent à la fois du contenu du document et de la requête, telles que le score TF-IDF ou d'autres fonctions de classement non apprises par machine. Caractéristique de requêtes (QLF), qui dépendent uniquement de la requête. Par exemple, le nombre de mots dans une requête.

Quelques exemples de caractéristiques utilisés dans le célèbre jeu de données LETOR : TF, TF-IDF, BM25 et les scores issus de la modélisation du langage appliqués aux zones d'un document (titre, corps, texte des ancres, URL) pour une requête donnée ; Longueurs et sommes d'IDF des zones d'un document ; Le PageRank, les classements HITS et leurs variantes.

La sélection et la conception de bonnes caractéristiques constituent un domaine important en apprentissage automatique, appelé ingénierie des caractéristiques.

Mesures d'évaluation

Plusieurs mesures (métriques) s'emploient couramment pour juger de la performance d'un algorithme sur les données d'entraînement et pour comparer les performances de différents algorithmes MLR. Souvent, un problème d'apprentissage par classement se reformule comme un problème d'optimisation par rapport à l'une de ces métriques.

Exemples de mesures de qualité de classement : Précision moyenne DCG et NDCG Précision@n, NDCG@n, où « @n » indique que les métriques s'évaluent uniquement sur les n premiers documents ; Rang réciproque moyen Tau de Kendall Corrélation de Spearman

Le DCG et sa variante normalisée NDCG sont généralement privilégiés dans la recherche académique lorsque plusieurs niveaux de pertinence s'emploient. D'autres métriques telles que MAP, MRR et la précision se définissent uniquement pour des jugements binaires.

Récemment, plusieurs nouvelles métriques d'évaluation apparaissent, prétendant modéliser la satisfaction de l'utilisateur par rapport aux résultats de recherche mieux que la métrique DCG : Expected reciprocal rank (ERR); Le pfound de Yandex. Ces deux métriques reposent sur l'hypothèse que l'utilisateur est plus susceptible d'arrêter de consulter les résultats de recherche après avoir examiné un document plus pertinent que lorsqu'il en examine un moins pertinent.

Approches Les approches d'apprentissage par classement se répartissent souvent en trois catégories : l'approche par point (où les documents individuels se classent), l'approche par paire (où des paires de documents se classent par ordre relatif) et l'approche par liste (où une liste entière de documents se met en ordre).

Tie-Yan Liu de Microsoft Research Asia analyse les algorithmes existants pour les problèmes d'apprentissage par classement dans son ouvrage Learning to Rank for Information Retrieval. Il les classe en trois groupes selon leurs espaces d'entrée, espaces de sortie, espaces d'hypothèses (la fonction cœur du modèle) et fonctions de perte : l'approche par point, par paire et par liste. En pratique, l'approche par liste surpasse souvent les approches par paire et par point.

Dans cette section, sans autre précision, désigne un objet à évaluer (par exemple, un document ou une image), désigne une hypothèse à valeur unique, désigne une fonction bivariée ou multivariée et désigne la fonction de perte.

Approche par point Dans ce cas, on suppose que chaque paire requête–document dans les données d'entraînement dispose d'un score numérique ou ordinal. Le problème d'apprentissage par classement se rapproche alors d'un problème de régression – pour une paire requête–document donnée, on prédit son score. Formellement, l'approche par point vise à apprendre une fonction qui prédit le score réel ou ordinal d'un document en utilisant la fonction de perte .

Un certain nombre d'algorithmes d'apprentissage supervisé existants s'emploient aisément à cet effet. Les algorithmes de régression ordinale et de classification s'emploient également dans l'approche par point lorsqu'ils prédisent le score d'une paire requête–document unique, lequel prend un nombre fini et restreint de valeurs.

Approche par paire Dans ce cas, le problème d'apprentissage par classement se rapproche d'un problème de classification – apprendre un classifieur binaire capable de déterminer quel document est supérieur dans une paire donnée. Le classifieur reçoit deux documents en entrée et l'objectif est de minimiser une fonction de perte . Cette fonction de perte reflète généralement le nombre et l'ampleur des inversions dans le classement induit.

Dans de nombreux cas, le classifieur binaire s'implémente à l'aide d'une fonction de notation . Par exemple, RankNet. adapte un modèle probabiliste et définit comme la probabilité estimée que le document ait une qualité supérieure à :

où est une fonction de répartition cumulée, par exemple, la CDF logistique standard, c'est-à-dire

Approche par liste Ces algorithmes essaient d'optimiser directement la valeur d'une des mesures d'évaluation ci-dessus, moyennée sur l'ensemble des requêtes des données d'entraînement. Cela s'avère souvent difficile en pratique, car la plupart des mesures d'évaluation ne sont pas des fonctions continues par rapport aux paramètres du modèle de classement, et il faut alors utiliser des approximations continues ou des bornes sur ces mesures. Par exemple, l'algorithme SoftRankTaylor, M.J., Guiver, J., Robertson, S.E., & Minka, T.P. (2008). SoftRank: optimizing non-smooth rank metrics. Web Search and Data Mining.. LambdaMART est un algorithme par paire qui s'est montré empiriquement capable d'approcher des fonctions objectifs par liste..

Liste des méthodes Une liste partielle des algorithmes d'apprentissage par classement publiés est présentée ci-dessous avec l'année de première publication de chaque méthode : {|class="wikitable sortable" ! Année !! Nom !! Type !! Remarques |- | 1989 || OPRF || 2par point || Régression polynomiale (au lieu de l'apprentissage automatique, ce travail se réfère à la reconnaissance de formes, mais l'idée est la même). |- | 1992 || SLR || 2par point || Régression logistique par étapes. |- | 1994 || NMOpt || 2par liste || Optimisation non métrique. |- | 1999 || MART (Arbres de régression additives multiples)|| 2par paire || |- | 2000 || Ranking SVM (RankSVM) || 2par paire || Une présentation plus récente se trouve dans, qui décrit une application au classement utilisant les clics. |- | 2001 || Pranking|| 1par point || Régression ordinale. |- | 2003 || RankBoost || 2par paire || |- | 2005 || RankNet || 2par paire || |- | 2006 || IR-SVM|| 2par paire || SVM de classement avec normalisation au niveau de la requête dans la fonction de perte. |-