# Apprentissage par classement

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'information. 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

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 cours.

## 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, $x$ désigne un objet à évaluer (par exemple, un document ou une image), $f(x)$ désigne une hypothèse à valeur unique, $h$ désigne une fonction bivariée ou multivariée et $L$ 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 $f(x)$ qui prédit le score réel ou ordinal d'un document $x$ en utilisant la fonction de perte $L(f;x_{j},y_{j})$.
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 $h(x_{u},x_{v})$ 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 $L(h;x_{u},x_{v},y_{u,v})$. 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 $h(x_{u},x_{v})$ s'implémente à l'aide d'une fonction de notation $f(x)$. Par exemple, RankNet adapte un modèle probabiliste et définit $h(x_{u},x_{v})$ comme la probabilité estimée que le document $x_{u}$ ait une qualité supérieure à $x_{v}$ :
    $P_{u,v}(f)={\text{CDF}}{\biglf(x_{u})-f(x_{v}){\bigr )},$
où ${\text{CDF}}(\cdot )$ est une fonction de répartition cumulée, par exemple, la CDF logistique standard, c'est-à-dire
    ${\text{CDF}}(x)={\frac {1}{1+\exp {\bigl-x{\bigr )}}}.$

### 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 SoftRank. 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 :
    AnnéeNomTypeRemarques 1989OPRF2par pointRé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). 1992SLR2par pointRégression logistique par étapes. 1994NMOpt2par listeOptimisation non métrique. 1999MART (Arbres de régression additives multiples)2par paire 2000Ranking SVM (RankSVM)2par paireUne présentation plus récente se trouve dans, qui décrit une application au classement utilisant les clics. 2001Pranking1par pointRégression ordinale. 2003RankBoost2par paire 2005RankNet2par paire 2006IR-SVM2par paireSVM de classement avec normalisation au niveau de la requête dans la fonction de perte. 2006LambdaRankpar paire/par listeRankNet dans lequel la fonction de perte par paire est multipliée par la variation de la métrique de recherche d'information causée par un échange. 2007AdaRank3par liste 2007FRank2par paireBasé sur RankNet, utilise une fonction de perte différente – la perte de fidélité. 2007GBRank2par paire 2007ListNet3par liste 2007McRank1par point 2007QBRank2par paire 2007RankCosine3par liste 2007RankGP3par liste 2007RankRLS2par paireClassement basé sur les moindres carrés régularisés. Le travail s'étend à l'apprentissage par classement à partir de graphes de préférences. 2007SVM$^{map}$3par liste 2008LambdaSMART/LambdaMARTpar paire/par listeEntrée gagnante lors de la compétition Yahoo Learning to Rank en 2010, utilisant un ensemble de modèles LambdaMART. Basé sur MART (1999) « LambdaSMART », pour le sous-modèle LambdaMART, ou LambdaMART dans le cas sans sous-modèle. 2008ListMLE3par listeBasé sur ListNet. 2008PermuRank3par liste 2008SoftRank3par liste 2008Ranking Refinement2par paireUne approche semi-supervisée pour l'apprentissage par classement qui utilise le Boosting. 2008SSRankBoost2par paireUne extension de RankBoost pour apprendre avec des données partiellement étiquetées (apprentissage semi-supervisé du classement). 2008SortNet2par paireSortNet, un algorithme de classement adaptatif qui ordonne les objets en utilisant un réseau de neurones comme comparateur. 2009MPBoost2par paireVariante de RankBoost préservant la magnitude. L'idée est que plus les étiquettes d'une paire de documents sont inégales, plus l'algorithme doit s'efforcer de les classer. 2009BoltzRank3par listeContrairement aux méthodes antérieures, BoltzRank produit un modèle de classement qui, lors de l'exécution de la requête, examine non seulement un document unique, mais aussi des paires de documents. 2009BayesRank3par listeUne méthode qui combine le modèle Plackett–Luce et un réseau de neurones pour minimiser le risque Bayésien attendu, lié au NDCG, du point de vue décisionnel. 2010NDCG Boost3par listeUne approche de boosting pour optimiser le NDCG. 2010GBlend2par paireÉtend GBRank au problème d'apprentissage de fusion consistant à résoudre conjointement plusieurs problèmes d'apprentissage par classement avec certaines caractéristiques partagées. 2010IntervalRank2par paire & par liste 2010CRR2par point & par paireRégression et classement combinés. Utilise la descente de gradient stochastique pour optimiser une combinaison linéaire d'une perte quadratique par point et d'une perte de type hinge par paire issue du Ranking SVM. 2014LCR2par paireApplique l'hypothèse de faible rang local sur le classement collaboratif. A reçu le prix du meilleur article étudiant à WWW'14. 2015FaceNetpar paireClasse les images de visages avec la métrique de triplet via un réseau de neurones convolutionnel profond. 2016XGBoostpar paireSupporte divers objectifs de classement et mesures d'évaluation. 2017ES-Rankpar listeTechnique d'apprentissage par classement par stratégie évolutive avec 7 mesures d'évaluation de la fitness. 2018DLCM2par listeUne fonction de classement multivariée qui encode plusieurs éléments d'une liste initiale classée (contexte local) à l'aide d'un réseau de neurones récurrent, puis crée un classement des résultats en conséquence. 2018PolyRankpar paireApprend simultanément le classement et le modèle génératif sous-jacent à partir de comparaisons par paires. 2018FATE-Net/FETA-Netpar listeArchitectures entièrement entraînables, prenant explicitement en compte tous les éléments pour modéliser les effets de contexte. 2019FastAPpar listeOptimise la précision moyenne pour apprendre des embeddings profonds. 2019Mulberrypar liste & hybrideApprend des politiques de classement maximisant plusieurs métriques sur l'ensemble du jeu de données. 2019DirectRankerpar paireGénéralisation de l'architecture RankNet. 2019GSF2par listeUne fonction de classement multivariée invariante par permutation qui encode et classe les éléments avec des fonctions de notation groupées construites à l'aide de réseaux de neurones profonds. 2020RaMBOpar listeOptimise les métriques basées sur le classement en utilisant la rétropropagation en boîte noire 2020PRMpar paireRéseau transformeur encodant à la fois les dépendances entre les éléments et les interactions entre l'utilisateur et ces derniers. 2020SetRank2par listeUne fonction de classement multivariée invariante par permutation qui encode et classe les éléments avec des réseaux à auto-attention. 2021PiRankpar listeDes substituts différentiables pour le classement, capables de retrouver exactement les métriques souhaitées et de bien se scaler pour de grandes tailles de liste, améliorant significativement les benchmarks à l'échelle d'Internet. 2022SAS-Rank par listeCombine le recuit simulé avec la stratégie évolutive pour l'apprentissage par classement implicite et explicite à partir d'étiquettes de pertinence. 2022VNS-Rank par listeRecherche de voisinage variable dans 2 nouvelles méthodologies en IA pour l'apprentissage par classement. 2022VNA-Rank par listeCombine le recuit simulé avec la recherche de voisinage variable pour l'apprentissage par classement. 2023GVN-Rank par listeCombine l'ascension de gradient avec la recherche de voisinage variable pour l'apprentissage par classement.
Note : Comme la plupart des algorithmes supervisés d'apprentissage par classement s'appliquent aux cas par point, par paire et par liste, seules les méthodes spécifiquement conçues pour le classement sont présentées ci-dessus.

## Histoire

Norbert Fuhr introduit l'idée générale du MLR en 1992, décrivant les approches d'apprentissage en recherche d'information comme une généralisation de l'estimation de paramètres ; une variante spécifique de cette approche (utilisant la régression polynomiale) est publiée par lui trois ans plus tôt. Bill Cooper propose la régression logistique pour le même objectif en 1992 et l'utilise avec son groupe de recherche de Berkeley pour entraîner une fonction de classement performante pour le TREC. Manning et al..
Plusieurs conférences, telles que NeurIPS, SIGIR et ICML organisent depuis le milieu des années 2000 des ateliers consacrés au problème de l'apprentissage par classement.

### Utilisation pratique par les moteurs de recherche

Les moteurs de recherche commerciaux commencent à utiliser des systèmes de classement appris par machine depuis les années 2000. L'un des premiers moteurs de recherche à l'adopter est AltaVista (plus tard sa technologie est acquise par Overture, puis par Yahoo), qui lance une fonction de classement entraînée par gradient boosting en avril 2003$^,$.
On dit que la recherche sur Bing s'appuie sur l'algorithme RankNet, inventé chez Microsoft Research en 2005.
En novembre 2009, le moteur de recherche russe Yandex annonce qu'il augmente significativement la qualité de sa recherche grâce au déploiement d'un nouvel algorithme propriétaire MatrixNet, une variante de la méthode de gradient boosting qui utilise des arbres de décision oblivieux. Récemment, ils sponsorisent également une compétition d'apprentissage par classement automatique « Internet Mathematics 2009 » basée sur les données de production de leur propre moteur de recherche. Yahoo annonce une compétition similaire en 2010.
En 2008, Google et Peter Norvig déclarent que leur moteur de recherche ne repose pas exclusivement sur l'apprentissage automatique du classement ; le PDG de Cuil, Tom Costello, suggère qu'ils préfèrent des modèles construits manuellement, car ceux-ci surpassent les modèles appris automatiquement lorsqu'on les mesure à l'aide d'indicateurs tels que le taux de clics ou le temps passé sur la page d'atterrissage – parce que les modèles appris « apprennent ce que les gens disent aimer, et non ce qu'ils aiment réellement ».
En janvier 2017, la technologie est intégrée dans le moteur de recherche open source Apache Solr. Elle est également disponible dans OpenSearch open source et dans Elasticsearch en mode source-disponible$^,$. Ces implémentations rendent l'apprentissage par classement largement accessible pour la recherche en entreprise.

## Vulnérabilités

À l'instar des applications de reconnaissance en vision par ordinateur, les algorithmes récents de classement basés sur les réseaux de neurones se révèlent également vulnérables aux attaques adversariales, aussi bien sur les candidats que sur les requêtes. Avec de petites perturbations imperceptibles à l'œil humain, l'ordre de classement peut être modifié arbitrairement. De plus, des exemples adversariaux transférables, indépendants du modèle, apparaissent possibles, permettant des attaques adversariales en boîte noire sur des systèmes de classement profonds sans nécessiter l'accès à leurs implémentations sous-jacentes$^,$.
Inversement, la robustesse de tels systèmes de classement peut être améliorée grâce à des défenses adversariales telles que la défense Madry.