Alai

En 2004, Microsoft Research et l’équipe de recherche Web de Microsoft ont commencé un effort conjoint pour améliorer la pertinence de nos résultats de recherche Web. Il s’en est suivi un effort soutenu qui, au cours des années suivantes, a abouti à l’expédition de trois générations d’algorithmes de classement de recherche sur le Web, pour aboutir aux ensembles d’arbres boostés que Bing utilise aujourd’hui. Nous avons appelé le premier de ces algorithmes de classement RankNet. Récemment, l’article sur RankNet, publié dans la conférence internationale sur l’apprentissage automatique (ICML) en 2005, a remporté le prix « Test of Time » de l’ICML, un prix décerné chaque année à un seul article présenté à la conférence dix ans plus tôt et jugé comme ayant eu le plus grand impact académique global au cours des années intermédiaires. C’est un grand honneur, mais aussi l’occasion de jeter un coup d’œil en arrière et d’évaluer nos progrès au cours de la dernière décennie. Dans cet article, je voudrais raconter cette histoire.

La recherche sur le Web fonctionne essentiellement en prenant la requête de l’utilisateur et en évaluant la pertinence de chaque document indexé par rapport à celle-ci. Toutes les pages web ne sont pas dans l’index, mais celui-ci contient néanmoins des centaines de milliards de documents, stockés dans une structure de données spéciale pour rendre la recherche rapide. Comme les meilleurs résultats doivent être présentés à l’utilisateur en quelques centaines de millisecondes, cela nécessite un processus de filtrage et de classement extrêmement efficace. Les classeurs décrits ici travaillent sur un sous-ensemble (encore important) de documents, choisis à l’aide de ce processus de filtrage initial rapide. Fondamentalement, un classeur fonctionne en prenant une liste de nombres, dont chacun mesure la qualité d’une correspondance requête/document particulière d’une manière particulière (par exemple, un nombre binaire représentant si la requête contient ou non un mot dans le titre du document). Le classeur convertit ensuite cette liste de chiffres en une mesure unique de la pertinence, qui est ensuite utilisée pour classer tous les documents correspondant à cette requête. La liste ordonnée de nombres que le classeur associe à un score unique est appelée vecteur de caractéristiques.

Donc, lorsqu’il est utilisé au moment de l’exécution, pour une requête donnée, le classeur prend le vecteur de caractéristiques pour chaque paire requête/document et l’associe à un nombre qui capture la pertinence de ce document pour la requête. RankNet est un modèle de réseau neuronal à action directe. Avant de pouvoir être utilisé, ses paramètres doivent être appris à l’aide d’une grande quantité de données étiquetées, appelées ensemble d’apprentissage. L’ensemble d’apprentissage consiste en un grand nombre de paires requête/document, où pour chaque paire, un nombre évaluant la qualité de la pertinence du document pour cette requête est attribué par des experts humains. Bien que l’étiquetage des données soit une tâche lente et à forte intensité humaine, l’entraînement du réseau, à partir des données étiquetées, est entièrement automatique et assez rapide. Le système utilisé par Microsoft en 2004 pour former le classificateur s’appelait The Flying Dutchman. Nous avons constaté que, alors que The Flying Dutchman a pris plusieurs jours et un cluster pour produire un modèle entraîné, RankNet a été capable de produire un modèle de classement en seulement quelques heures en utilisant une seule machine. RankNet a également donné une pertinence significativement améliorée par rapport au ranker utilisé précédemment, car les réseaux neuronaux peuvent modéliser un très large éventail de mappings possibles, alors que le système précédent était limité aux seuls mappings linéaires.

Pour l’instant, tout va bien, mais aurions-nous pu faire mieux ? La réponse est Oui, mais pour voir pourquoi, je dois expliquer un peu comment RankNet est formé. Pour chaque requête de l’ensemble d’entraînement, pour chaque paire de documents à classer pour cette requête, on montre à RankNet les deux vecteurs de caractéristiques et il ajuste ensuite un peu ses paramètres, en utilisant une méthode appelée Stochastic Gradient Descent (SGD), de sorte que les scores de sortie ajustés pour les deux caractéristiques évoluent dans la bonne direction – c’est-à-dire que le score du document le plus pertinent augmente, et celui du moins pertinent, diminue. Mais cela signifie que RankNet s’efforcera de faire remonter les documents très pertinents qui sont très bas dans le classement, et aussi de faire descendre les documents à haut score mais moins pertinents. En dépensant ses ressources de cette manière, il ne prête pas autant d’attention qu’il le devrait aux quelques premiers liens qui sont montrés à l’utilisateur. En fait, à l’époque, notre mesure d’évaluation était un score appelé NDCG, qui donne un chiffre unique évaluant la qualité globale du classement, en accordant une importance bien plus grande aux quelques premiers résultats affichés à l’utilisateur. Le NDCG est donc une mesure plus naturelle pour la recherche sur le Web que l’erreur par paire. Cela nous a posé un défi : le SGD se résume à une recherche dans un espace continu, mais le NDCG est fondamentalement une mesure discrète, en ce sens que sa valeur ne change que lorsqu’au moins deux documents changent de position dans la liste classée. Des changements suffisamment petits dans les scores du modèle ne donnent aucun changement dans NDCG, et puisque SGD fonctionne en explorant de petits changements dans les scores, il est difficile de voir comment optimiser NDCG en utilisant SGD.

Nous avons trouvé une réponse à ce puzzle, que nous avons appelé LambdaRank. L’astuce consistait à remarquer que toute la procédure de formation d’un réseau neuronal n’a besoin que des gradients de la fonction de coût, et non de la fonction de coût elle-même. Vous pouvez considérer ces gradients comme de petites flèches attachées à chaque document de la liste classée, indiquant la direction dans laquelle nous aimerions que ces documents se déplacent. LambdaRank a simplement pris les gradients de RankNet, dont nous savions qu’ils fonctionnaient bien, et les a mis à l’échelle par le changement de NDCG trouvé en échangeant chaque paire de documents. Nous avons constaté que cet entraînement générait des modèles dont la pertinence (mesurée par le NDCG) était nettement améliorée et que, en prime, nous avions découvert une autre astuce qui améliorait la vitesse d’entraînement globale (à la fois pour RankNet et LambdaRank). En outre, de manière surprenante, nous avons trouvé des preuves empiriques (voir également cet article) que la procédure de formation optimise effectivement le NDCG, même si la méthode, bien qu’intuitive et sensée, ne présente aucune garantie de ce type.

Pour l’instant, tout va bien, mais encore une fois, aurions-nous pu faire mieux ? La réponse était à nouveau Oui. Nous connaissions une classe de modèles appelés ensembles d’arbres boostés qui étaient connus pour faire des classificateurs multiclasses très forts. Que se passe-t-il si l’on traite le problème du classement comme un problème de classification multiclasse, avec une classe pour chacun des cinq niveaux de pertinence identifiés dans l’ensemble d’apprentissage ? Nous avons constaté que cela donnait de meilleurs résultats que LambdaRank (en particulier une variante appelée classification multiclasse ordinale). Les arbres boostés ont l’avantage supplémentaire de pouvoir traiter facilement des caractéristiques catégorielles et d’autres types de caractéristiques discrètes, qui sont moins bien adaptées aux réseaux neuronaux. Nous pensions que ces résultats étaient dus à la meilleure adéquation de cette classe de modèles à nos données, et la question naturelle était donc de savoir si nous pouvions combiner les modèles d’arbres boostés avec l’idée du LambdaRank pour obtenir le meilleur des deux mondes. L’entraînement d’un modèle d’arbre boosté peut également être considéré comme une forme de SGD, et la réponse était donc oui, sous la forme d’un modèle que nous avons appelé LambdaMART. LambdaMART présentait un avantage supplémentaire : l’entraînement des modèles d’ensemble d’arbres peut être très nettement accéléré par rapport à l’équivalent en réseau de neurones (ce travail, dirigé par O. Dekel, n’est pas encore publié). Cela nous permet de nous entraîner avec des ensembles de données beaucoup plus importants, ce qui donne à nouveau une meilleure précision de classement.

Comment nos classeurs se comparent-ils aux autres dans l’industrie ? En 2010, Yahoo ! a organisé un défi d’apprentissage du classement, dont l’une des pistes visait à déterminer qui avait le meilleur algorithme de classement des recherches sur le Web. 1 055 équipes se sont inscrites à ce défi. Notre équipe a remporté le défi, en utilisant un ensemble de modèles LambdaMART.

En regardant en arrière sur la dernière décennie, peut-être la leçon technique la plus saillante est l’importance de la vitesse de formation. Une formation plus rapide permet à la fois plus d’expérimentation et l’utilisation de plus grands ensembles de données. Je pense que ces deux facteurs sont finalement plus importants que les algorithmes sous-jacents utilisés, pour autant que ces derniers soient des modèles suffisamment expressifs pour la tâche à accomplir. L’autre « leçon de vie » que je tire de cette expérience est l’importance de la persévérance, mais surtout du don de pouvoir travailler avec de merveilleux collègues, dans les groupes de produits, chez Microsoft Research et dans le milieu universitaire.

Chris Burges est chercheur principal et directeur de recherche chez Microsoft Research, où il travaille depuis 2000. Avant cela, il a travaillé chez AT&T Bell Labs, qu’il a rejoint en 1986. Avant cela, il était chercheur postdoctoral au département de physique théorique du MIT, qu’il a rejoint après avoir obtenu son doctorat en physique à Brandeis, après avoir obtenu un diplôme avec mention très bien en physique et en mathématiques à Oxford. Il s’est intéressé à l’ingénierie des systèmes de grands réseaux de communication (AT&T utilise toujours ses algorithmes pour acheminer plusieurs réseaux clés), aux réseaux neuronaux pour la reconnaissance de l’écriture manuscrite et des caractères d’imprimerie (il a travaillé sur un système utilisé aujourd’hui pour lire des millions de chèques par jour, et en fait, sa longue descente vers l’apprentissage automatique a été déclenchée par une démonstration particulièrement cool d’un réseau neuronal reconnaissant des chiffres manuscrits au début des années 90), les machines à vecteurs de support (il a eu la chance de travailler avec Vladimir Vapnik, le co-créateur des SVM, dans les premiers temps, et il a écrit un tutoriel que certains ont apprécié), l’empreinte audio (son travail est actuellement utilisé dans Xbox et Windows Media Player pour identifier la musique), la vérification du locuteur, la recherche d’informations et le classement (son algorithme de classement est actuellement utilisé par Bing pour la recherche sur le web). Chris se passionne actuellement pour le développement de nouvelles approches de la compréhension automatique du texte, qui, bien que très ambitieuse, est susceptible de nous apprendre quelque chose, à moins que nous n’arrêtions d’essayer. Chris était coprésident du programme de Neural Information Processing Systems 2012 et coprésident général de NIPS 2013.

Pour plus de nouvelles sur la recherche en informatique, visitez ResearchNews.com.

.