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

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 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 rechercheModèle:,.
• 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}(f(x_u)-f(x_v)),$

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 (-x)}.$

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é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.
2006	LambdaRank	par paire/par liste	RankNet 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.
2007	AdaRank	3par liste
2007	FRank	2par paire	Basé sur RankNet, utilise une fonction de perte différente – la perte de fidélité.
2007	GBRank	2par paire
2007	ListNet	3par liste
2007	McRank	1par point
2007	QBRank	2par paire
2007	RankCosine	3par liste
2007	RankGP	3par liste
2007	RankRLS	2par paire	Classement basé sur les moindres carrés régularisés. Le travail s'étend à l'apprentissage par classement à partir de graphes de préférences.
2007	SVMmap	3par liste
2008	LambdaSMART/LambdaMART	par paire/par liste	Entré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.
2008	ListMLE	3par liste	Basé sur ListNet.
2008	PermuRank	3par liste
2008	SoftRank	3par liste
2008	Ranking Refinement	2par paire	Une approche semi-supervisée pour l'apprentissage par classement qui utilise le Boosting.
2008	SSRankBoost	2par paire	Une extension de RankBoost pour apprendre avec des données partiellement étiquetées (apprentissage semi-supervisé du classement).
2008	SortNet	2par paire	SortNet, un algorithme de classement adaptatif qui ordonne les objets en utilisant un réseau de neurones comme comparateur.
2009	MPBoost	2par paire	Variante 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.
2009	BoltzRank	3par liste	Contrairement 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.
2009	BayesRank	3par liste	Une 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.
2010	NDCG Boost	3par liste	Une approche de boosting pour optimiser le NDCG.
2010	GBlend	2par 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.
2010	IntervalRank	2par paire & par liste
2010	CRR	2par point & par paire	Ré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.
2014	LCR	2par paire	Applique l'hypothèse de faible rang local sur le classement collaboratif. A reçu le prix du meilleur article étudiant à WWW'14.
2015	FaceNet	par paire	Classe les images de visages avec la métrique de triplet via un réseau de neurones convolutionnel profond.
2016	XGBoost	par paire	Supporte divers objectifs de classement et mesures d'évaluation.
2017	ES-Rank	par liste	Technique d'apprentissage par classement par stratégie évolutive avec 7 mesures d'évaluation de la fitness.
2018	DLCM	2par liste	Une 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.
2018	PolyRank	par paire	Apprend simultanément le classement et le modèle génératif sous-jacent à partir de comparaisons par paires.
2018	FATE-Net/FETA-Net	par liste	Architectures entièrement entraînables, prenant explicitement en compte tous les éléments pour modéliser les effets de contexte.
2019	FastAP	par liste	Optimise la précision moyenne pour apprendre des embeddings profonds.
2019	Mulberry	par liste & hybride	Apprend des politiques de classement maximisant plusieurs métriques sur l'ensemble du jeu de données.
2019	DirectRanker	par paire	Généralisation de l'architecture RankNet.
2019	GSF	2par liste	Une 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.
2020	RaMBO	par liste	Optimise les métriques basées sur le classement en utilisant la rétropropagation en boîte noire
2020	PRM	par paire	Réseau transformeur encodant à la fois les dépendances entre les éléments et les interactions entre l'utilisateur et ces derniers.
2020	SetRank	2par liste	Une fonction de classement multivariée invariante par permutation qui encode et classe les éléments avec des réseaux à auto-attention.
2021	PiRank	par liste	Des 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.
2022	SAS-Rank	par liste	Combine le recuit simulé avec la stratégie évolutive pour l'apprentissage par classement implicite et explicite à partir d'étiquettes de pertinence.
2022	VNS-Rank	par liste	Recherche de voisinage variable dans 2 nouvelles méthodologies en IA pour l'apprentissage par classement.
2022	VNA-Rank	par liste	Combine le recuit simulé avec la recherche de voisinage variable pour l'apprentissage par classement.
2023	GVN-Rank	par liste	Combine 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 2003Modèle:,.

On dit que la recherche sur Bing s'appuie sur l'algorithme RankNetModèle:Quand, 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-disponibleModèle:,. 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-jacentesModèle:,.

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.

Voir aussi

• Recherche d'image par le contenu
• Fonction de coût par triplet

Liens externes

Compétitions et jeux de données publics

• LETOR : Une collection de référence pour la recherche sur l'apprentissage par classement pour la recherche d'information
• Les Mathématiques sur Internet de Yandex 2009
• Challenge Yahoo! Learning to Rank
• Jeux de données Microsoft Learning to Rank