CAIRN.INFO : Matières à réflexion

1 – Introduction

1Au cours des dernières années, un grand nombre de moteurs de recherche d’information géoréférencés ont émergé sur Internet. Ces moteurs proposent aux internautes de rechercher des lieux qui sont classés suivant un grand nombre de critères : l’adéquation avec la requête, la proximité du lieu à la position de l’utilisateur, l’adéquation entre le lieu et les goûts de l’utilisateur ou de son réseau social ou encore l’e-réputation du lieu. L’e-réputation correspond à la réputation d’un établissement sur Internet, au travers des commentaires laissés par les internautes sur des forums, des réseaux sociaux ou d’autres sites de partage. Pour les utilisateurs, ces moteurs peuvent représenter des outils attractifs. Les résultats correspondent non seulement à leurs besoins, mais encore ils ont été jugés par l’ensemble des internautes et par leur réseau social, ce qui constitue un gage de confiance. Par ailleurs, la recherche personnalisée semble leur garantir des recommandations au plus près de leurs goûts et de leurs attentes. Pour les établissements, ces moteurs constituent une opportunité d’être plus visibles, d’augmenter ou de mieux cibler leur clientèle ou encore de contrôler leur e-réputation. Ainsi, le moteur de recherche géoréférencé Nomao propose aux propriétaires des lieux des outils stratégiques d’aide au référencement et de suivi de leur réputation sur Internet. Plus généralement, la connaissance des mécanismes de référencement et surtout des critères et algorithmes de classement des résultats peuvent être des outils puissants pour la veille stratégique.

2Les moteurs de recherche utilisent des algorithmes d’ordonnancement qui leur permettent de classer les résultats suivant leur pertinence à une requête. A l’aide de jeux de données constitués de paires requête-document pour lesquelles la pertinence est connue, les algorithmes apprennent une fonction dite d’ordonnancement permettant de prédire la pertinence et l’ordre des documents. Un grand nombre d’approches et d’algorithmes ont été développés dans ce but au cours de la dernière décennie. Si ces algorithmes sont performants, ils présentent néanmoins des limites. Notamment, ils n’utilisent qu’une seule fonction d’ordonnancement pour l’ensemble des requêtes. Ils considèrent ainsi que les critères de tris sont identiques quels que soient la requête et l’utilisateur. Par ailleurs, la plupart de ces algorithmes ont été développés dans le cadre de moteurs généralistes. Leur utilisation sur des moteurs spécialistes, comme par exemple les moteurs géoréférencés, peut ne pas être adaptée. Il est donc nécessaire de proposer de nouvelles méthodes permettant de mieux prendre en compte les spécificités des requêtes et des utilisateurs, utilisables sur des moteurs généralistes ou spécialistes.

3Cet article constitue une version plus détaillée du travail présenté au séminaire VSST’12 (Laporte, 2012). Il est structuré en trois parties. Dans la section 2, nous introduisons brièvement la recherche d’information (RI), puis nous présentons le principe de l’optimisation de l’ordonnancement des résultats sur les moteurs de recherche. Nous détaillons également les différentes approches proposées au cours de la dernière décennie que nous illustrons par les algorithmes de référence correspondants. Nous mettons en évidence deux enjeux en apprentissage d’ordonnancement : la création de jeux de données représentatifs et l’adaptation de l’ordonnancement aux différents types de requêtes. Dans la section 3, nous nous concentrons sur le premier enjeu, i.e. la création de jeux de données représentatifs. Nous proposons un état de l’art des méthodes existantes et mettons en évidence leurs limites. Nous présentons une de nos propositions afin de résoudre ce problème. Enfin dans la section 4, nous nous intéressons à la problématique de l’adaptation de l’ordonnancement aux types de requêtes. Nous présentons un état de l’art de l’existant et nous proposons des pistes d’amélioration.

2 – Apprentissage d’ordonnancement en RI

4La RI est le domaine de la recherche qui s’intéresse à "la représentation, à l’organisation, au stockage et à la sélection de l’information" (Salton, 1968). Une des tâches centrales en RI est la restitution de documents pertinents vis-à-vis d’une requête au sein d’un corpus. En RI, requêtes et documents sont généralement représentés sous forme de vecteurs des occurrences des termes présents dans la requête et le document respectivement. Des mesures représentant la similarité entre la requête et le document sont calculées à partir de ces vecteurs. Elles sont ensuite utilisées pour sélectionner les documents qui sont restitués par le système. Des fonctions d’ordonnancement permettent ensuite de déterminer l’ordre des résultats. Un système de RI (SRI) est alors évalué sur sa capacité à restituer l’ensemble des documents pertinents et à les classer de façon optimale. L’optimisation automatique des fonctions d’ordonnancement, donc du classement des résultats de recherche, est l’objectif de l’apprentissage d’ordonnancement (learning to rank) en RI. Nous présentons dans un premier temps les mesures de RI utilisées pour évaluer les SRI. Dans un second, nous introduisons le principe général de l’optimisation automatique des fonctions d’ordonnancement. Nous détaillons également les différentes approches utilisées dans les algorithmes d’apprentissage d’ordonnancement.

2.1 – Mesures d’évaluation en recherche d’information

5La performance d’un SRI est évaluée sur sa capacité à sélectionner les documents pertinents. Deux critères sont étudiés : le rappel et la précision. Le rappel traduit la capacité d’un SRI à restituer l’ensemble des documents pertinents. Il est défini de la façon suivante :

6

equation im1

7La précision traduit la capacité d’un système à ne sélectionner que des documents pertinents. Elle est définie de la façon suivante :

8

equation im2

9La performance des systèmes est généralement évaluée à partir de la précision à la position k pour une requête q notée Pq@k, de la précision moyenne notée APq et de la moyenne de la précision moyenne sur l’ensemble des requêtes notée MAP, définies de la façon suivante (Baccini et al., 2012) :

10

equation im3

11La MAP permet d’évaluer les systèmes quand il existe deux niveaux de pertinence pour les documents (typiquement, pertinent vs non pertinent). Dans le cas de classes multiples de pertinence (non pertinent, peu moyennement pertinent, très pertinent) une autre mesure peut être utilisée : le NDCG (Normalized Discounted Cumulative Gain). Elle est définie à partir du Discounted Cumulative Gain (DCG) :

12

equation im4

13Le DCG peut avoir des valeurs supérieures à 1. Le NDCG est alors obtenu en normalisant par Zk, la plus grande valeur du DCG@k, pour ramener les valeurs entre 0 et 1 :

14

equation im5

15Certains algorithmes optimisent directement ces mesures pour apprendre les fonctions d’ordonnancement.

2.2 – Principes et approches en apprentissage d’ordonnancement

16Dans le domaine de l’apprentissage d’ordonnancement, chaque couple requête-document (qi, dj) est représenté par un vecteur de variables equation im6[1] qui traduisent la similarité entre la requête et le document (par exemple le nombre de termes qu’ils ont en commun), ainsi que certaines caractéristiques propres à la requête (nombre de termes, …) ou propres au document (confiance accordée à la source, …). Des jugements de pertinence sont associés à ces couples. Il peut s’agir (1) de scores, de classes de pertinence (très pertinent, peu pertinent, non pertinent par exemple) ou de relation d’ordre (document 1 plus pertinent que le document 2) déterminés par des experts humains, ou (2) de scores, de relation d’ordre ou de probabilités de pertinence estimées à partir des clics des utilisateurs sur les documents. L’objectif des algorithmes d’apprentissage d’ordonnancement est de prédire correctement ces jugements connaissant les valeurs du vecteur des variables. Le processus d’apprentissage d’ordonnancement se décompose en deux phases : une phase d’apprentissage et une phase de test. Dans la phase d’apprentissage, les jeux de données sont utilisés par les algorithmes pour apprendre automatiquement les fonctions d’ordonnancement qui servent de modèles pour la prédiction des jugements de pertinence. Dans la phase de test, ces fonctions sont ensuite utilisées pour ordonner les documents restitués par le SRI lorsque de nouvelles requêtes ont été soumises. Ce principe est illustré à la figure 1.

Figure 1

Les différentes étapes du processus d’ordonnancement

Figure 1

Les différentes étapes du processus d’ordonnancement

17Au cours de la dernière décennie, de nombreux algorithmes ont été proposés pour optimiser l’ordonnancement des résultats de recherche. Ils sont généralement répartis en trois grandes catégories : par point, par paire et par liste. Ces approches diffèrent sur trois éléments : leur façon de considérer les données en entrée du système d’apprentissage, le type de variable ou jugement de pertinence à prédire et la modélisation mathématique du problème d’apprentissage.

2.2.1 – Approche par point

18Dans l’approche par point (de l’anglais pointwise), chaque document xi est considéré séparément en entrée du système d’apprentissage. Le jugement de pertinence peut être un score entier ou réel, une classe de pertinence non ordonnée (non pertinent, pertinent) ou une classe de pertinence ordonnée (pertinence de niveau 1 < pertinence de niveau 2 <…). Le jugement de pertinence est ici une variable à prédire, dont la valeur permet d’ordonner les documents. Lorsque le jugement de pertinence est un score entier ou réel, le problème d’apprentissage est généralement considéré comme un problème de régression linéaire. La relation qui lie la variable quantitative à expliquer aux variables explicatives est supposée linéaire. Cossock et Zhang (2006) ont ainsi proposé un algorithme minimisant une variante de l’erreur de moindres carrés (c’est-à-dire le carré de la différence entre le jugement de pertinence de référence et le jugement prédit) pour optimiser le classement des premiers résultats d’une liste.

19Dans le cas où l’on considère des classes de pertinence, le problème d’apprentissage pourra être vu comme un problème de classification ou de régression logistique ordinale, selon que l’on considère ou non une relation d’ordre entre les classes de pertinence. Dans le cas de la classification, les algorithmes ne prennent pas en compte les éventuelles relations d’ordre pouvant exister entre les classes de pertinence. La littérature distingue des algorithmes traitant des pertinences binaires (le document est pertinent vs non pertinent) et des algorithmes traitant des classes de pertinence multiples (pertinent, moyennement pertinent, non pertinent). Ces algorithmes utilisent des techniques de classification connues en apprentissage automatique. Nallapati (2004) a ainsi utilisé les machines à support de vecteurs (SVM) pour prédire les classes de pertinence dans le cas de pertinence binaire. Il s’agit ici d’une application directe des SVM proposé par Vapnik (1999). Ceux-ci cherchent à calculer l’hyperplan permettant de séparer correctement les données tout en étant le plus loin possible de chaque observation. Li et al. (2007) ont montré que le problème de classification multiple pouvait être résolu par une application directe des méthodes de boosting (Freund, Schapire, 1997). Contrairement aux algorithmes de classification, les algorithmes basés sur la régression ordinale prennent en compte les relations d’ordre existant entre les classes dans le processus d’apprentissage. Considérant k catégories, l’objectif est de trouver les seuils bk tels que b1 < b2 < ??? < bK–1 qui délimitent les classes et la fonction f qui répartit correctement les prédictions dans chaque classe ainsi délimitée. L’algorithme Prank (Crammer, Singer, 2001) est un algorithme itératif dédié à cette tâche. Considérant un vecteur de poids w et des seuils initiaux bk, la quantité yi = argmink{wT xibk < 0} est calculée à chaque itération. Elle est alors comparée à la référence. Si l’algorithme a fait une erreur, le vecteur w et le seuil sont modifiés.

20Le processus est itéré jusqu’à ce que l’algorithme converge.

2.2.2 – Approche par paires

21Dans l’approche par paires (de l’anglais pairwise), des paires de documents (xi; xj) sont considérées en entrée du système d’apprentissage. A chaque paire de documents est associé un jugement de préférence yi;j à valeur dans –1; 1. Si, yi;j = 1, alors le document xi est préféré au document xi : il doit être classé au dessus de xj dans la liste de résultat. La préférence est notée xi ? xj. Au contraire, si yi;j = –1, alors le document xj est préféré au document xi et on note xi ? xj. Le problème d’apprentissage est ici un problème de classification, dans le cas particulier de paires d’instances. Par conséquent, la plupart des algorithmes de cette approche utilisent des adaptations de classifieurs existants. Ainsi, Burges et al. (2005) ont proposé RankNet, un algorithme basé sur les réseaux de neurones. Freund et al. (2003) ont développé l’algorithme RankBoost, une adaptation d’Adaboost (Freund, Schapire, 1997) pour les paires de documents. Enfin, différents algorithmes basés sur les SVM ont été développés, notamment RankSVM-Struct proposé par Joachims (2002) et RankSVM-Primal, proposé par Chapelle et Keerthi (2010), qui résolvent différemment le problème d’optimisation associé aux SVM.

2.2.3 – Approche par liste

22Dans l’approche par liste (de l’anglais listwise), la liste complète et ordonnée des documents est considérée en entrée du système d’apprentissage. Les algorithmes fournissent en sortie la liste ordonnée des documents ou la liste de leurs scores de pertinence. Les algorithmes sont répartis en deux sous-catégories au sein de cette approche : ceux minimisant une fonction d’erreur définie à partir d’une mesure de RI comme la MAP ou le NDCG et ceux minimisant une fonction de perte non liée à une mesure de RI. Les travaux de la première catégorie suivent la logique suivante : puisque la performance des algorithmes est évaluée à partir de mesures de RI, les algorithmes doivent apprendre les fonctions en maximisant ces mesures. Considérant une mesure m, les algorithmes cherchent ainsi à minimiser soit une approximation de la quantité 1 – m (Taylor et al., 2008 ; Zoeter et al., 2008), soit une approximation de la borne supérieure de la quantité 1 – m (Xu, Li, 2007 ; Yue et al., 2007). Les travaux de la deuxième catégorie cherchent quant à eux à minimiser le nombre de permutations entre la liste de référence et la liste restituée par l’algorithme. De nombreuses fonctions de perte ont été proposées dans ce but (Cao et al., 2007 ; Xia et al., 2008).

2.3 – Deux enjeux : la création de collections d’apprentissage et l’adaptation aux types de requêtes

23Plusieurs enjeux ont émergé au cours des dernières années dans le domaine de l’apprentissage d’ordonnancement. Dans cet article, nous nous intéressons à deux problèmes principaux : la création automatique de jeux de données représentatifs et l’adaptation des fonctions d’ordonnancement aux requêtes.

2.3.1 – Création automatique de jeux de données représentatifs

24Les algorithmes d’apprentissage d’ordonnancement sont évalués sur leur capacité à restituer les documents pertinents en haut de la liste, via différentes mesures de RI (MAP, NDCG). L’algorithme le plus performant sera celui pour lequel la valeur de la mesure est la plus grande. Généralement, la performance est mesurée sur les collections d’apprentissage de référence LETOR 3.0 ou LETOR 4.0 (T.-Y. Liu, 2011 ; Qin et al., 2010). Ces collections ont été développées spécifiquement pour l’évaluation des algorithmes d’ordonnancement. Les requêtes et documents utilisés sont extraits de deux autres collections de référence en RI : Ohsumed, constituée d’articles médicaux et TREC 2003 et 2004, constitué des pages web du domaine.gov. Pour les collections LETOR, l’ensemble des similarités pour chaque couple requête-document est pré-calculé et les jugements de pertinence sont donnés par des experts humains. Si ces collections présentent l’avantage de permettre une évaluation et une comparaison aisées des différents algorithmes dans le cadre de moteurs généralistes, elles peuvent ne pas être adaptées lorsque l’on considère certains éléments du contexte, comme par exemple la nouveauté des résultats proposés. Elles sont par ailleurs longues et coûteuses à obtenir. D’autres méthodes de construction de collections d’apprentissage, basées sur l’utilisation des connexions de recherche, ont ainsi été développées.

25Les fichiers de connexion stockent chaque jour l’ensemble des actions réalisées par les utilisateurs sur les moteurs de recherche, notamment les requêtes soumises, les documents restitués et les résultats cliqués. Les clics peuvent être considérés comme des indicateurs implicites de la pertinence. En effet, un utilisateur cliquera sur un résultat s’il est intéressé et si celui-ci répond a priori à son besoin. Le fait que le résultat soit cliqué traduit donc une certaine forme de pertinence. De nombreuses approches ont proposé d’utiliser les clics comme jugements de pertinence pour la création de collection d’apprentissage.

26Nous nous intéressons plus particulièrement à cette problématique dans la section 3. Nous proposons dans un premier temps un état de l’art des méthodes d’évaluation de clics. Dans un second temps, nous montrons que ces méthodes présentent des limites, notamment pour des moteurs de recherche autorisant l’utilisateur à effectuer différentes actions sur un même résultat de recherche. Enfin, nous présentons l’une de nos contributions : un modèle d’évaluation implicite de la pertinence à partir des clics utilisateurs, dédié aux moteurs à clics multiples.

2.3.2 – Adaptation des fonctions d’ordonnancement aux requêtes

27Les algorithmes d’apprentissage d’ordonnancement présentés apprennent une fonction d’ordonnancement unique pour l’ensemble des requêtes. Ils supposent donc que toutes les requêtes peuvent être traitées de la même manière. Or les requêtes peuvent grandement différer à plusieurs niveaux. Elles peuvent utiliser des sémantiques différentes, être longues ou courtes, fréquentes ou rares, avoir ou non une dimension géographique, être plus ou moins ambiguës ou encore traduire des buts utilisateurs distincts. Dans le cadre des moteurs de recherche géoréférencés, le type d’usage et le type de lieu recherché peuvent également influencer le traitement de la requête. Ainsi, la proximité géographique est souvent plus importante lors d’une recherche sur un appareil mobile que lors d’une recherche sur un ordinateur fixe. En effet, l’utilisateur d’un mobile est généralement en mouvement et désire trouver dans l’instant un lieu à proximité de sa position actuelle, ce qui n’est pas nécessairement vrai dans le cadre d’une utilisation d’un appareil fixe. L’utilisateur peut dans ce cas rechercher un lieu dans le cadre d’un futur déplacement ou voyage.

28Des méthodes ont été développées afin de regrouper les requêtes similaires et apprendre des fonctions d’ordonnancement spécifiques. Nous nous intéressons à cette problématique en section 4. Dans un premier temps, nous proposons un état de l’art des méthodes d’adaptation aux requêtes dont nous présentons les limites. Dans un second temps, nous introduisons les méthodes de sélection de variables comme possibilité d’amélioration de l’adaptation aux requêtes. Enfin, nous proposons une méthodologie d’adaptation de l’ordonnancement aux requêtes utilisant la sélection de variables. Des résultats préliminaires d’évaluation de cette méthodologie sont présentés.

3 – Création automatique de jeux de données représentatifs

29Dans cette section, nous abordons le problème de la création automatique de jeux de données représentatifs. Nous nous intéressons aux modèles de clics, qui permettent d’évaluer la pertinence d’un document vis-à-vis d’une requête à partir des clics des utilisateurs, de façon automatique, sans recours à des experts humains. Nous montrons que les modèles actuels ne peuvent pas prendre en compte les spécificités de certains moteurs. Nous présentons une autre approche permettant de pallier ce problème et de créer des jeux de données représentatifs de ces moteurs.

3.1 – Les modèles existants pour l’évaluation de la pertinence

30Les clics des utilisateurs sont considérés comme de bons indicateurs de la pertinence d’un document vis-à-vis d’une requête. De nombreux travaux de recherche se sont intéressés à cette problématique et diverses stratégies ou modèles ont ainsi été proposés.

31A notre connaissance, Joachims (2002) a été le premier à proposer une stratégie d’extraction de préférences à partir des clics dans le cadre d’algorithmes. Joachims et al. (2005) ont poursuivi ces travaux en testant différentes stratégies d’extraction de préférences dans le cadre d’algorithmes. Parmi celles-ci, la plus connue, car la plus performante, est la stratégie SkipAbove. Elle stipule que, considérant un ensemble de résultats restitués par le système et l’ensemble de résultats cliqués correspondants, le document cliqué de rang le plus faible est préféré à l’ensemble des documents non cliqués de meilleur rang. Ainsi, si (d1, d2, d3, d4, d5) est la liste des documents restitués et si (d1, d4) est la liste des documents cliqués, nous obtenons les préférences suivantes : d4 ? d2 et d4 ? d3. Ces préférences sont directement utilisables par les algorithmes basés sur l’approche par paires. Radlinski et Joachims (2005) ont étendu ces stratégies dans le cadre de chaînes de requêtes, c’est-à-dire des successions de requêtes traduisant le même besoin mais tour à tour reformulées, généralisées ou spécialisées. La stratégie SkipEarlierQuery considère qu’un document cliqué est préféré à l’ensemble des documents non cliqués à la requête précédente, dans la même chaîne de requêtes. Dans le cas où aucun document n’avait été cliqué pour la première requête, les auteurs considèrent qu’un document cliqué est préféré aux deux premiers documents de la requête précédente (stratégie TopTwoEarlierQuery).

32Les approches basées sur les clics peuvent être biaisées par la présentation initiale des résultats. En effet, les utilisateurs sont généralement plus influencés par la position des résultats de recherche que par leur pertinence. Ainsi, ils ont tendance à cliquer sur les premiers résultats restitués par le système et à délaisser des documents situés plus bas dans la liste, même si ceux-ci sont les plus pertinents. Des approches ont été proposées afin de prendre en compte ce biais de position dans la modélisation des clics. La pertinence est alors inférée à partir de l’ensemble des sessions utilisateurs. Les premiers modèles proposés ont été le modèle de position et le modèle en cascade (Craswell et al., 2008).

33Le modèle de position (Position Model) considère que l’utilisateur clique sur un seul document qui est alors le document pertinent. La probabilité qu’un document soit cliqué dépend uniquement de sa position dans la liste de résultats et diminue avec celle-ci.

34Le modèle en cascade (Cascade Model) suppose que l’utilisateur regarde les résultats du haut vers le bas de la liste. Pour chaque résultat, il choisit de cliquer sur le document qui est alors le seul document pertinent ou de passer au résultat suivant. L’utilisateur clique ainsi sur un seul document qui lui paraît pertinent compte tenu des résultats précédents.

35Il est important de noter que ces deux modèles postulent qu’il n’y a qu’un seul document pertinent, donc un seul clic, par session de recherche. Or, en pratique, les utilisateurs cliquent généralement sur plusieurs résultats au cours d’une même session. D’autres modèles ont ainsi été développés pour généraliser le modèle en cascade aux sessions pour lesquelles plusieurs résultats sont cliqués.

36Le modèle de clics dépendants (Dependent click model) considère que l’utilisateur consulte les résultats du haut vers le bas de la liste. Comme pour le modèle en cascade, l’utilisateur choisit à chaque étape de cliquer sur le document ou de passer au résultat suivant. Mais, contrairement au modèle en cascade où il s’arrête une fois le premier document cliqué, l’utilisateur peut revenir sur la liste de résultat et consulter d’autres documents. La probabilité qu’un clic ait lieu sur le document di à la position i est notée equation im8 et est définie de la façon suivante (Guo et al., 2009) :

37

equation im9

38equation im10 est la pertinence du document di par rapport à la requête observée et ? est un paramètre qui traduit la tendance des utilisateurs à revenir sur la liste des résultats après avoir consulté un document. Ces deux quantités sont alors estimées de la façon suivante :

39

equation im11

40Le modèle bayésien dynamique (Dynamic Bayesian Model) (Chapelle, Zhang, 2009) généralise également le modèle en cascade aux sessions à clics multiples et apporte une nouvelle contribution en définissant les notions de pertinence perçue et de pertinence effective. La pertinence perçue au correspond à la probabilité que le document soit cliqué. Elle traduit le fait que l’utilisateur ait été attiré par le résultat avant consultation du contenu du document. La pertinence effective su traduit la satisfaction de l’utilisateur après consultation du contenu du document. Soient les évènements Ei : le résultat est vu dans la liste, Ci : le résultat est cliqué, Ai : l’utilisateur est attiré par le résultat et Si : l’utilisateur est satisfait par le document, le modèle est alors défini (Chapelle, Zhang, 2009) par les équations présentées au tableau 1.

Tableau 1

Modèle bayésien dynamique

Tableau 1
Un résultat est cliqué Ei = 1,Ai = 1 ? Ci = 1 si et seulement si l’utilisateur a vu le résultat et a été attiré par celui-ci P(Ai = 1) = au La pertinence perçue est égale à la probabilité que l’utilisateur soit attiré par le document La pertinence effective est P(Si = 1|Ci = 1) = su la probabilité que l’utilisateur soit satisfait sachant qu’il a cliqué sur le document Si = 1 ? Ei+1 = 0 Si un utilisateur est satisfait par un document alors il arrête sa recherche Ci = 0 ? Si = 0 Si le document n’a pas été cliqué alors l’utilisateur ne peut pas être satisfait P(Ei+1|Ei, Si = 0) = ? L’utilisateur retourne sur la liste de résultats avec la probabilité ? s’il n’est pas satisfait par le document Ei = 0 ? Ei+1 = 0 L’utilisateur ne regarde le résultat suivant que s’il a traité le résultat en cours

Modèle bayésien dynamique

41La pertinence globale du document est alors définie comme le produit de la pertinence perçue et de la pertinence effective ausu. Elle est utilisée pour la construction des échantillons d’apprentissage. C. Liu et al. (2009) ont également proposé un modèle bayésien, spécialement adapté à l’apprentissage de préférences dans les algorithmes d’ordonnancement de paires d’instances.

3.2 – Des collections d’apprentissage non représentatives

42Les modèles présentés à la section précédente sont performants pour prédire correctement les clics et donc la pertinence. Néanmoins, ils restent limités à une utilisation sur des moteurs de recherche généralistes. Nous entendons par généralistes des moteurs qui traitent des documents non spécifiques et qui présentent leurs résultats sous forme de liste d’URL. L’utilisateur qui souhaite consulter un résultat clique sur le lien vers le document. Un seul clic est possible pour chaque référence. Or, de plus en plus de moteurs proposent de visualiser les résultats sous forme de fiches comportant plusieurs éléments cliquables. Plusieurs actions sont alors possibles pour un même résultat et chaque clic peut avoir une importance différente concernant la pertinence. Nous parlerons dans ce cas de moteurs de recherche à actions multiples. Nous pouvons citer, par exemple, le moteur géolocalisé Nomao [2], qui présente des lieux sous forme de fiches pour lesquelles le nom, le numéro de téléphone ou encore la position sur la carte sont cliquables. Néanmoins, les moteurs de recherche à actions multiples ne se limitent pas aux moteurs géoréférencés. Ainsi, le moteur de recherche du site The European Library[3] permet de consulter les collections des bibliothèques nationales européennes. Chaque résultat est présenté sous la forme d’une fiche bibliographique comportant plusieurs liens cliquables permettant l’accès au document complet en ligne, l’accès au document au format pdf ou encore le téléchargement du document. L’utilisateur peut réaliser plusieurs actions sur un même résultat et ces actions peuvent refléter des degrés distincts d’intérêt de l’utilisateur. Ainsi, nous pourrions considérer qu’un document qui a été affiché au format pdf puis téléchargé est plus pertinent qu’un document seulement affiché. Les modèles de clics actuels ne sont pas conçus pour prendre en compte ces nuances. Ils ne sont donc pas adaptés pour ce genre de moteurs et ne permettent pas la construction des jeux de données. Dans la section suivante, nous présentons brièvement des travaux que nous avons menés afin d’évaluer la pertinence sur les moteurs de recherche à actions multiples.

3.3 – Une proposition d’évaluation de la pertinence sur les moteurs à actions multiples

43Les travaux que nous exposons ici ont fait l’objet d’un article présenté à la conférence INFORSID’12 (Laporte et al., 2012). Nous nous intéressons à l’évaluation de la pertinence dans le cadre de moteurs à actions multiples. Chaque action correspond à un type de clic différent effectué par l’utilisateur sur le résultat de recherche. Dans le cadre de moteurs de recherche géoréférencés, il peut s’agir d’un clic sur le nom d’un lieu, sur son numéro de téléphone ou sur le lien vers son site internet. Nous supposons que chacune de ces actions traduit un degré différent de satisfaction (ou de pertinence) de la part de l’utilisateur. Ainsi, nous définissons la pertinence rl,q du lieu l pour la requête q comme la somme pondérée du nombre de clics ci,d,q correspondant à l’action i pour la requête q et le document d telle que :

equation im13
?i ? 0, 1 est le poids associé à l’action i. Les poids ?i permettent de modéliser le fait que des actions ont plus d’impact sur la pertinence que d’autres. Les expérimentations menées ont montré que le modèle donnait de bons résultats dans le cas équipondéré et qu’un ordre d’importance entre les actions pouvait être déduit. D’autres analyses doivent être menées afin de proposer une méthodologie permettant d’estimer automatiquement les poids de chaque action.

4 – Adaptation des fonctions d’ordonnancement aux requêtes

44Les algorithmes d’apprentissage apprennent une fonction d’ordonnancement unique pour l’ensemble des requêtes. Or, les critères d’ordonnancement peuvent varier suivant le contexte d’usage ou le type de la requête. Dans cette section, nous nous intéressons aux différentes approches existantes permettant d’apprendre des fonctions d’ordonnancement adaptées à un type ou un groupe de requêtes. Nous présentons un état de l’art de ces méthodes ainsi que leurs limites. Nous introduisons alors les méthodes de sélection de variables afin de pallier aux limitations des méthodes existantes. Puis, nous formalisons une méthodologie pour l’adaptation de l’ordonnancement aux requêtes basée sur la sélection de variables. Enfin, nous présentons quelques résultats préliminaires obtenus.

4.1 – Les méthodes existantes d’apprentissage adapté aux requêtes

45La problématique de l’adaptation des fonctions d’ordonnancement aux types de requêtes soulève deux questions :

  1. Comment définir des groupes/types de requêtes ?
  2. Comment apprendre des fonctions d’ordonnancement efficaces propres à chaque catégorie de requêtes ?
La première problématique dépasse le simple cadre de l’apprentissage d’ordonnancement et a été largement étudiée. La deuxième problématique n’a, à notre connaissance, donné lieu qu’à un faible nombre de publications, qui se contentent généralement d’appliquer des algorithmes existants sur des groupes de requêtes préalablement définis. La section suivante regroupe des travaux traitant de ces deux problématiques.

4.1.1 – Les approches de classification des requêtes

46Parmi l’ensemble des travaux dédiés à la classification de requêtes, nous pouvons distinguer ceux consacrés à la compréhension ou à la modélisation du besoin de l’utilisateur, de ceux dédiés au développement de méthodes d’apprentissage d’ordonnancement adaptées aux types de requêtes ou dépendant des requêtes. La plupart des travaux de la première catégorie s’est consacrée à la création de typologies qui peuvent être basées sur le but supposé de l’utilisateur ou encore consacrées à un type d’information particulier, comme les informations géoréférencées.

47Les typologies basées sur le but supposé de l’utilisateur constituent une première approche pour la classification des requêtes. Broder (2002) a ainsi proposé une typologie regroupant les requêtes en trois grandes catégories : navigationnelles, informationnelles et transactionnelles. Les requêtes navigationnelles correspondent à la recherche d’un site internet spécifique. Par exemple, un utilisateur qui soumet la requête "air france" cherche probablement la page d’accueil du site www.airfrance.fr de la compagnie aérienne française. L’utilisateur attend a priori un seul résultat. Les requêtes informationnelles correspondent quant à elles à la recherche d’une information pouvant être présente sur une ou plusieurs pages web. Par exemple, l’utilisateur qui soumet la requête "sites touristiques Dordogne" peut être uniquement intéressé par le site du comité départemental du tourisme de Dordogne ou par l’ensemble des sites des offices de tourisme de Dordogne. Enfin, les requêtes transactionnelles traduisent que l’utilisateur recherche un site Internet dans le but d’y effectuer une transaction ultérieure, par exemple un achat, un téléchargement ou une réservation. Ainsi, la requête "billet de train Toulouse Sarlat" semble indiquer que l’utilisateur cherche un site internet pour acheter un billet de train. Il s’agit donc d’une requête transactionnelle. Rose et Levinson (2004) puis Jansen et al. (2008) ont également proposé des typologies de requêtes reprenant les trois grandes catégories de Broder. Néanmoins, certains travaux ont mis en évidence que ces typologies peuvent ne pas être représentatives des requêtes sur des moteurs spécialisés, par exemple des moteurs de recherche de blogs (Mishne, De Rijke, 2006).

48Les typologies propres aux informations géoréférencées se sont plus particulièrement intéressées aux requêtes portant sur des informations géoréférencées. Notamment, Gan et al. (2008) ont mené une analyse des requêtes géographiques extraites des logs du moteur de recherche AOL et ont proposé de regrouper les requêtes géographiques en 23 catégories combinant le but utilisateur et le thème de la recherche. Ils ont également évalué des méthodes permettant de séparer les requêtes géographiques des requêtes non géographiques d’une part, et de séparer les requêtes géographiques navigationnelles des requêtes géographiques informationnelles d’autre part.

49Les travaux de la deuxième catégorie utilisent des typologies ou des méthodes de classification non supervisée pour créer des groupes de requêtes, mais vont plus loin en les intégrant dans le processus d’ordonnancement. L’apprentissage de fonctions d’ordonnancement dépendantes des requêtes ou de catégories de requêtes est ainsi vu comme un moyen d’améliorer le classement des résultats restitués par le système (Qin et al., 2010 ; T.-Y. Liu, 2011). Parmi les travaux basés sur l’utilisation des typologies, nous pouvons citer Kang et Kim (2003) qui ont classifié les requêtes en s’inspirant de la typologie de Broder et utilisé des fonctions distinctes créées manuellement pour classer les documents. Ils ont montré que cette approche permettait d’améliorer le classement.

50Parmi les travaux utilisant les méthodes de classification non supervisées, nous pouvons citer Geng et al. (2008) qui ont proposé une approche basée sur l’algorithme des k plus proches voisins pour regrouper les requêtes et apprendre des fonctions spécifiques. Pour chaque requête de l’échantillon d’apprentissage, ils sélectionnent les k plus proches requêtes présentes dans l’échantillon. Un modèle est automatiquement appris grâce à l’algorithme Ranking SVM sur le sous-ensemble de données ainsi constitué. Lorsqu’une nouvelle requête est soumise au système, ses k plus proches voisines sont sélectionnées. Ce groupe de requêtes est alors comparé à chaque sous-ensemble précalculé afin de déterminer celui qui contient le plus de requêtes communes. La fonction d’ordonnancement correspondante est alors utilisée pour classer les résultats.

4.1.2 – Limites des approches

51Ces approches donnent de bons résultats pour la classification des requêtes, mais présentent à nos yeux deux limites majeures.

52D’une part, ces approches n’ont pas suffisamment été évaluées dans le cadre de l’apprentissage d’ordonnancement pour connaître leur impact réel sur l’optimisation des résultats. En effet, parmi les travaux précédemment cités, seuls ceux de Kang et Kim (2003) et Geng et al. (2008) ont intégré les classes de requêtes dans un système d’ordonnancement. Par ailleurs, les méthodes intégrées à un système d’ordonnancement se sont limitées à certains types de requêtes et de moteurs. Leur apport dans le cadre de moteurs plus spécifiques, comme les moteurs géoréférencés, n’est donc pas connu.

53D’autre part, les méthodes d’apprentissage dépendant des requêtes nous semblent limitées du fait de la méthodologie utilisée. Celle-ci peut être décomposée en deux étapes :

  1. Définition de groupe de requêtes via une méthodologie ou une méthode de classification non supervisée.
  2. Apprentissage de fonctions d’ordonnancement sur chaque groupe de requêtes avec l’ensemble des caractéristiques.
Cette méthodologie présente l’inconvénient de conserver l’ensemble des caractéristiques, ou critères d’ordonnancement, pour l’ensemble des requêtes. L’adaptation aux types de requêtes se réduit donc à une simple repondération des différents critères. Des caractéristiques non pertinentes ou inutiles sont ainsi conservées, ce qui peut nuire à la qualité de la prédiction.

54Dans la section suivante, nous introduisons la sélection de variables, qui permet de ne conserver en apprentissage que les variables réellement pertinentes et qui pourrait donc pallier la limite évoquée. Nous en présentons les principes généraux et introduisons les travaux existants en apprentissage d’ordonnancement.

4.2 – Les méthodes existantes de sélection de variables en apprentissage d’ordonnancement

55La faiblesse principale des méthodes existantes est d’utiliser l’ensemble des variables pour apprendre le modèle spécifique aux types de requêtes, au risque de conserver des caractéristiques non pertinentes, inutiles ou susceptibles d’introduire du bruit. Des méthodes de sélection de variables peuvent être utilisées afin de résoudre ce problème.

4.2.1 – Les approches en sélection de variables

56Dans le cadre général de la classification, nous distinguons trois grands types de méthodes de classification de variables : les méthodes filter, les méthodes wrapper et les méthodes embedded. L’article de Guyon et Elisseeff (2003) propose une introduction complète à la sélection de variables. Les méthodes filter constituent une étape prétraitement au cours de laquelle un sous-ensemble de caractéristiques est sélectionné à l’aide d’un certain critère, indépendamment du prédicteur utilisé pour l’apprentissage. Les méthodes wrapper utilisent l’algorithme d’apprentissage comme une boîte noire pour assigner un score à différents sous-ensembles de caractéristiques. Le sousensemble présentant le score le plus élevé est alors sélectionné comme l’ensemble optimal de caractéristiques. Le modèle est ensuite appris sur ce sous-ensemble. Les méthodes embedded intègrent la sélection de variables à l’algorithme d’apprentissage. Ces méthodes sont donc généralement spécifiques à un algorithme donné.

4.2.2 – Les méthodes existantes en apprentissage d’ordonnancement

57Récemment, des méthodes de sélection de variables spécifiques à l’apprentissage d’ordonnancement ont été développées. Ces méthodes peuvent être classées suivant le même formalisme que dans le cadre de la classification (filter, wrapper et embedded).

58Les méthodes filter. À notre connaissance, la première méthode de sélection de variables dédiée à l’apprentissage d’ordonnancement a été une approche de type filter. Il s’agit de l’algorithme GAS (pour Greedy search Algorithm for feature Selection) proposé par Geng et al. (2007). Les auteurs définissent un score d’importance propre à chaque caractéristique qui traduit sa qualité en tant que prédicteur et un score de similarité entre deux caractéristiques qui traduit la ressemblance entre deux caractéristiques. L’objectif est de sélectionner les variables ayant le plus grand score d’importance et les plus faibles scores de similarité, ce qui revient à résoudre un problème d’optimisation qui maximise les scores d’importance tout en minimisant les scores de similarité. Hua et al. (2010) utilise des scores de similarité afin de déterminer des groupes de caractéristiques par une méthode de type k-means. La variable la plus représentative de chaque groupe est alors sélectionnée et ajoutée à l’ensemble des caractéristiques utilisées pour apprendre le modèle. Enfin, Yu et al. (2009) ont également proposé RankFilter, une méthode filter dans le cadre de classes de pertinence multiples basé sur les algorithmes Relief (Sikonja, Igor, 2003), une classe d’algorithmes qui modifient itérativement les poids des caractéristiques en fonction de leur importance.

59Les méthodes wrapper. Plus récemment, des méthodes wrapper pour la sélection de variables ont été développées. Pan et al. (2009) ont ainsi proposé une méthode utilisant sur les Boosted Regression Trees (BRT), qui sont des algorithmes proposés par Friedman (2000) basés sur les arbres de décision et le boosting. Les auteurs utilisent le score d’importance relative des BRT (Friedman, 2000) ainsi qu’un score de similarité entre caractéristiques pour résoudre trois problèmes d’optimisation : (a) maximisation du score d’importance, (b) minimisation du score de similarité et (c) maximisation du score d’importance et minimisation simultanée du score de similarité. Ils montrent que les ensembles de caractéristiques sélectionnées par la première approche donnent les meilleurs résultats. La même année, Yu et al. (2009) proposent RankWrapper, basé comme RankFilter sur les algorithmes Relief, mais qui utilisent des jugements de pertinence ordonnés relativement et non des classes de pertinence. Dang et Croft (2010) et Pahikkala et al. (2010) ont proposé deux méthodes wrapper basés sur des algorithmes existants : l’algorithme de recherche best-first (Kohavi, John, 1997) pour les premiers et l’algorithme d’apprentissage d’ordonnancement RankRLS (Pahikkala et al., 2010) pour les seconds. Ils ont montré que chacune des deux approches permettait d’obtenir des résultats équivalents en utilisant un nombre plus faible de caractéristiques.

60Les méthodes embedded. Les méthodes embedded considérées en apprentissage d’ordonnancement apprennent des modèles linéaires parcimonieux. En pratique, la sélection de variables est réalisée par l’introduction d’un terme de régularisation en norme ?1, qui est connu pour introduire de la parcimonie dans les modèles (Lal et al., 2006). Sun et al. (2009) ont ainsi proposé une méthode parcimonieuse en norme ?1 nommée RSRank utilisant un algorithme de descente de gradient tronqué pour la résolution du problème d’optimisation. Très récemment, Lai et al. (2012) ont proposé une méthode utilisant les Support Vector Machine (SVM) en norme ?1. Les SVM sont des algorithmes utilisés en classification et basés sur la recherche d’un hyperplan séparateur optimal. Les auteurs ont montré que cette approche surpassait, du point de vue de la qualité de l’ordonnancement, des approches sans sélection de variables, mais également, l’approche RSRank.

61Ces méthodes sont efficaces pour sélectionner les variables en apprentissage d’ordonnancement. Néanmoins, elles ont principalement été proposées dans l’optique de réduire le nombre de variables pour des considérations de temps d’exécution ou qualité d’apprentissage. A notre connaissance, leur utilisation dans le cadre d’un apprentissage adapté aux requêtes n’a pas été formalisé. Dans la section suivante, nous proposons une méthodologie d’adaptation de l’ordonnancement aux types de requêtes basés sur la sélection de variables.

4.3 – Proposition d’une méthodologie pour l’apprentissage adaptatif basé sur la sélection de variables

62Dans cette section, nous proposons dans un premier temps une méthodologie d’ordonnancement adaptatif basé sur la sélection de variables. Dans un second temps, nous présentons des résultats préliminaires d’évaluation d’un algorithme de sélection de variables que nous souhaitons appliquer dans le cadre de la méthodologie utilisée.

4.3.1 – Méthodologie d’ordonnancement adaptatif basé sur la sélection de variables

63Nous proposons d’utiliser les méthodes de sélection de variables afin d’apprendre des fonctions d’ordonnancement spécifiques les plus parcimonieuses possibles. La méthodologie se décompose ainsi en deux étapes principales, résumées à la figure 2 : une étape de classification des requêtes et une étape d’apprentissage des fonctions d’ordonnancement adaptées aux groupes de requêtes précédemment déterminés. Il est important de noter que, dans le cadre des approches filter et wrapper, la deuxième étape se décomposent en deux sous-étapes : la sélection du sous-ensemble de caractéristiques puis l’apprentissage des fonctions d’ordonnancement à proprement dit. Ce n’est pas le cas des méthodes de type embedded, puisque la sélection et l’apprentissage sont effectués simultanément par les algorithmes. Nous proposons ainsi de ne considérer que des approches de type embedded, pour deux raisons principales :

  1. La sélection de caractéristiques est intégrée directement à l’apprentissage, ce qui permet d’une part d’économiser une étape de calcul comparativement aux méthodes filter ou wrapper et d’autre part, de ne pas poser d’hypothèses supplémentaires pour effectuer la sélection de variables (pas de définitions de score d’importance ou de similarité notamment). La sélection s’effectue grâce aux propriétés mathématiques de la norme utilisée et ne dépend donc pas de la définition des différents scores.
  2. En classification, des études empiriques (John et al., 1994 ; Aha, Bankert, 1995) ont montré que les méthodes wrapper étaient plus performantes que les méthodes filter du point de vue de la qualité de classification. Par ailleurs, Guyon et Elisseeff (2003) précisent que les approches embedded surpassent elles-mêmes les approches wrapper, notamment concernant les temps de calcul et la robustesse au sur-apprentissage. Les méthodes embedded seraient donc globalement plus performantes. Il est logique de supposer que ces bonnes propriétés sont conservées en sélection de variables pour l’apprentissage d’ordonnancement.
Nous proposons d’appliquer notre méthodologie dans le cadre de méthodes de sélection de variables de type embedded. La technologie de regroupement de requêtes, par typologies ou par classification non supervisée, sera adaptée suivant le cadre d’application et les données. De nouveaux algorithmes de sélection de variables utilisant les Support Vector Machines (SVM) seront développés. Les SVM présentent le double avantage d’être aisément adaptables dans le cadre de méthodes embedded et de permettre de bonnes performances en apprentissage d’ordonnancement. Dans la suite de cette section, nous présentons les résultats préliminaires de travaux menés dans ce cadre.

Figure 2

Méthodologie d’apprentissage des fonctions d’ordonnancement adaptées aux requêtes

Figure 2

Méthodologie d’apprentissage des fonctions d’ordonnancement adaptées aux requêtes

4.3.2 – Un algorithme de sélection de variables embarquée : résultats préliminaires

64Nous avons débuté une étude sur l’utilisation d’algorithmes de sélection de variables de type embedded pour la sélection de variables adaptative. Nous avons considéré un algorithme parcimonieux en norme ?1 basé sur les SVM et les méthodes proximales pour effectuer la sélection de variables. Nous nommons cet algorithme RankSVM-Lasso. Les SVM en norme ?1 sont connus pour introduire de la parcimonie dans les modèles. Les méthodes proximales (Beck, Teboulle, 2009) permettent quant à elles de résoudre efficacement le problème d’optimisation associé aux SVM en norme ?1.

65L’étude a été menée sur les jeux de données HP2004, NP2004 et TD2004 issus de la collection Letor 3.0. Trois expérimentations ont été considérées : évaluation de la capacité de l’algorithme à ordonner correctement les résultats, évaluation de la capacité de l’algorithme à sélectionner uniquement les variables pertinentes et à supprimer les autres et évaluation de la capacité de l’algorithme à apprendre des fonctions adaptées à un contexte donné.

66Expérience 1 : évaluation de la capacité de l’algorithme à ordonner correctement les résultats.

67L’algorithme évalué est comparé à 5 algorithmes non parcimonieux de l’état de l’art (RankSVM-Primal, RankBoost, ListNet, AdaRank-MAP, AdaRank-NDCG), à l’aide de la MAP et du NDCG@10. La figure 3 montre que l’algorithme parcimonieux donne des résultats comparables ou significativement meilleurs par rapport aux autres algorithmes sur les différents jeux de données. Plus particulièrement, l’algorithme proposé est significativement meilleur que RankBoost sur les jeux de données HP2004 et NP2004, que l’on considère la MAP ou le NDCG@10. Sur NP2004, RankSVM-Lasso est significativement meilleur que les deux algorithmes de l’état de l’art AdaRank-MAP et AdaRank-NDCG lorsque le NDCG@10 est considéré. Sur TD2004, il est significativement meilleur que l’algorithme AdaRank-NDCG selon la MAP. Sur ce même jeu de données, nous observons que l’algorithme parcimonieux est significativement moins bon que RankBoost, que l’on considère la MAP ou le NDCG. En pratique, RankBoost est significativement meilleur que l’ensemble des algorithmes de l’état de l’art sur ce jeu de données. Globalement, l’algorithme parcimonieux proposé obtient donc des résultats compétitifs par rapport à l’état de l’art.

Figure 3

Comparaison des résultats entre RankSVM-Lasso et les algorithmes non parcimonieux selon la MAP (haut) et le NDCG@10 (bas). Une * indique que RankSVM-Lasso est significativement meilleur au seuil de 5 % (Test de Student apparié unilatéral) tandis qu’un - indique qu’il est significativement moins bon au seuil de 5 % (Test de Student apparié unilatéral)

Figure 3

Comparaison des résultats entre RankSVM-Lasso et les algorithmes non parcimonieux selon la MAP (haut) et le NDCG@10 (bas). Une * indique que RankSVM-Lasso est significativement meilleur au seuil de 5 % (Test de Student apparié unilatéral) tandis qu’un - indique qu’il est significativement moins bon au seuil de 5 % (Test de Student apparié unilatéral)

68Expérience 2 : évaluation de la capacité de l’algorithme à sélectionner uniquement les variables pertinentes et à supprimer les autres.

69Pour évaluer la capacité de l’algorithme à sélectionner les variables, nous nous intéressons aux ratio de parcimonie pour chaque jeu de données. Le ratio de parcimonie est défini comme le pourcentage de variables conservées par l’algorithme à la fin de la phase d’apprentissage. Le tableau 2 montre que l’algorithme considéré est capable d’apprendre des fonctions d’ordonnancement utilisant uniquement 43 à 50 % des variables initiales, sans dégradation de la qualité de l’ordonnancement. L’approche proposée obtient donc des résultats comparables selon la MAP et le NDCG@10 tout en utilisant moins de 50 % des variables initiales. Elle est particulièrement efficace en matière de sélection de variables.

Tableau 2

Ratio de parcimonie de RankSVM-Lasso

Tableau 2
HP2004 Ratio de parcimonie 0.43 NP2004 TD2004 0.49 0.50

Ratio de parcimonie de RankSVM-Lasso

70Expérience 3 : évaluation de la capacité de l’algorithme à apprendre des fonctions adaptées à un contexte donné.

71Dans cette première approche, nous avons défini le contexte comme étant le jeu de données considéré. Chacun des jeux de données correspond à une tâche TREC spécifique. L’objectif est d’apprendre une fonction d’ordonnancement adaptée pour chaque jeu de données donc pour chaque tâche. L’hypothèse sous-jacente est que l’algorithme doit être capable de sélectionner un noyau de variables communes à l’ensemble des tâches et un ensemble de variables spécifiques pour chaque tâche.

72L’algorithme parcimonieux parvient à sélectionner 4 variables communes aux trois jeux de données. Une variable de type modèle de langue est sélectionnée sur les deux jeux de données HP2004 et NP2004, tandis que la variable HostRank est sélectionnée sur TD2004 et HP2004. L’algorithme est donc capable d’adapter la sélection de variables à la tâche considérée en sélectionnant à la fois des variables communes et des variables spécifiques.

73Les expériences menées ont mis en évidence des résultats encourageants. L’approche proposée permet d’apprendre des fonctions dont la qualité d’ordonnancement est comparable voire meilleure que celle des méthodes de l’état de l’art, tout en utilisant moins de la moitié des variables initiales. Par ailleurs, l’expérience d’adaptation au contexte a permis d’isoler un sous-ensemble de variables communes à l’ensemble des tâches, tout en sélectionnant des variables spécifiques aux tâches. Une analyse plus détaillée doit maintenant être menée pour l’évaluation de l’adaptation, non plus au niveau de la tâche, mais au niveau de la requête.

5 – Conclusion

74Nous avons présenté le principe général de l’ordonnancement des résultats sur les moteurs de recherche. Nous avons également introduit les principales approches et algorithmes existant dans la littérature. Nous avons constaté que les approches actuelles étaient limitées car elles ne peuvent pas être généralisées aux moteurs spécialisés. En effet, elles ne prennent pas en compte les spécificités des moteurs, des utilisateurs et des requêtes. Nous proposons des pistes d’adaptation et d’amélioration basées sur une meilleure connaissance des comportements des utilisateurs et sur la détermination de critères propres à différents scénari de requêtes. Des expériences préliminaires pour l’évaluation de l’approche ont donné des résultats très encourageants. Nous proposons d’appliquer ces méthodes dans le cadre des moteurs géoréférencés. Plus particulièrement, nous pourrons les adapter dans le cadre spécifique du moteur de recherche géoréférencé Nomao. En améliorant l’ordonnancement des résultats par l’utilisation de critères spécifiques aux catégories de requêtes, des études devraient permettre d’augmenter la performance du moteur et la satisfaction utilisateur. Elles pourront aussi fournir des indications importantes pour les entreprises afin d’améliorer leur compréhension des processus de choix des utilisateurs. Notre étude sur les différents types de clics permettra ainsi de mieux appréhender ces mécanismes utilisateurs et surtout, de créer des jeux de données d’apprentissage adaptés à chaque moteur. L’application de ces méthodes devrait ainsi conduire à la création d’une base d’apprentissage dédiée aux moteurs géoréférencés, qui pourra être ouverte à la communauté scientifique.

Remerciements

Nous remercions la Région Midi-Pyrénées qui soutient ces travaux via le financement numéro 10009108. Les travaux sont effectués dans le cadre d’une thèse codirigée par Sébastien Déjean (Institut de Mathématiques de Toulouse) et Josiane Mothe (Institut de Recherche en Informatique de Toulouse) et co-encadrée dans l’entreprise Nomao par Estelle Delpech.

Notes

  • [1]
    Dans la suite de l’article, nous ferons abstraction de la requête et nous noterons xi le vecteur représentant le couple requête-document (qj, di).
  • [2]
    www.nomao.com.
  • [3]
Français

Les moteurs de recherche géoréférencés utilisent des algorithmes d’ordonnancement complexes, prenant en compte le contexte d’utilisation, l’e-reputation et les réseaux sociaux, pour classer pertinemment les lieux vis-à-vis d’une requête. Or, comprendre les critères de sélection des utilisateurs et d’ordonnancement des moteurs est crucial pour les entreprises. Nous présentons le principe de l’optimisation de l’ordonnancement sur les moteurs de recherche et les approches et algorithmes existants. Nous montrons qu’ils sont limités et non adaptés au géoréférencement. Nous proposons une amélioration de l’évaluation de la pertinence et une méthodologie d’adaptation aux requêtes utilisant la sélection de variables embarquée.

Mots-clés

  • recherche d’information
  • ordonnancement
  • apprentissage automatique
  • adaptation aux requêtes
  • sélection de variables
  • modèles de pertinence
English

Local search engines use complex learning to rank algorithms to rank places according to a query by taking into account the user environment, the places e-reputation and social networks information. In parallel, the understanding of how users search or which criteria are used to rank results become a key issue for companies. In this paper, we present an overview of existing learning to rank approaches and algorithms. We show that these approaches may not be accurate when dealing with local data. We propose new methods to evaluate relevance and to adapt ranking to queries by using an embedded feature selection algorithm.

Keywords

  • information retrieval
  • learning to rank
  • machine learning
  • query-dependent ranking
  • feature selection
  • relevance models
  1. 1 - Introduction
  2. 2 - Apprentissage d’ordonnancement en RI
    1. 2.1 - Mesures d’évaluation en recherche d’information
    2. 2.2 - Principes et approches en apprentissage d’ordonnancement
      1. 2.2.1 - Approche par point
      2. 2.2.2 - Approche par paires
      3. 2.2.3 - Approche par liste
    3. 2.3 - Deux enjeux : la création de collections d’apprentissage et l’adaptation aux types de requêtes
      1. 2.3.1 - Création automatique de jeux de données représentatifs
      2. 2.3.2 - Adaptation des fonctions d’ordonnancement aux requêtes
  3. 3 - Création automatique de jeux de données représentatifs
    1. 3.1 - Les modèles existants pour l’évaluation de la pertinence
    2. 3.2 - Des collections d’apprentissage non représentatives
    3. 3.3 - Une proposition d’évaluation de la pertinence sur les moteurs à actions multiples
  4. 4 - Adaptation des fonctions d’ordonnancement aux requêtes
    1. 4.1 - Les méthodes existantes d’apprentissage adapté aux requêtes
      1. 4.1.1 - Les approches de classification des requêtes
      2. 4.1.2 - Limites des approches
    2. 4.2 - Les méthodes existantes de sélection de variables en apprentissage d’ordonnancement
      1. 4.2.1 - Les approches en sélection de variables
      2. 4.2.2 - Les méthodes existantes en apprentissage d’ordonnancement
    3. 4.3 - Proposition d’une méthodologie pour l’apprentissage adaptatif basé sur la sélection de variables
      1. 4.3.1 - Méthodologie d’ordonnancement adaptatif basé sur la sélection de variables
      2. 4.3.2 - Un algorithme de sélection de variables embarquée : résultats préliminaires
  5. 5 - Conclusion

Bibliographie

  • Aha D., Bankert R. (1995). A comparative evaluation of sequential feature selection algorithms. Learning from Data : Artificial Intelligence and Statistics V.
  • En ligneBaccini A., Déjean S., Lafage L., Mothe J. (2012, february). How many performance measures to evaluate information retrieval systems? Knowledge and Information Systems, vol. 30, n° 3, p. 693–713.
  • En ligneBeck A., Teboulle M. (2009, mars). A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, vol. 2, n° 1, p. 183–202.
  • En ligneBroder A. (2002, septembre). A taxonomy of web search. SIGIR Forum, vol. 36, n° 2, p. 3–10.
  • Burges C., Shaked T., Renshaw E., Lazier A., Deeds M., Hamilton N. (2005). Learning to rank using gradient descent. In Proceedings of the 22nd international conference on machine learning, p. 89–96.
  • Cao Z., Qin T., Liu T.-Y., Tsai M.-F., Li H. (2007). Learning to rank: from pairwise approach to listwise approach. In Proceedings of the 24th international conference on machine learning, p. 129–136. ACM.
  • En ligneChapelle O., Keerthi S. S. (2010, juin). Efficient algorithms for ranking with svms. Information Retrieval, vol. 13, n° 3, p. 201–215.
  • Chapelle O., Zhang Y. (2009). A dynamic bayesian network click model for web search ranking. In Proceedings of the 18th international conference on world wide web, p. 1–10. New York, NY, USA, ACM.
  • En ligneCossock D., Zhang T. (2006). Subset ranking using regression. In Proceedings of the 19th annual conference on learning theory, p. 605–619. Berlin, Heidelberg, Springer-Verlag.
  • Crammer K., Singer Y. (2001). Pranking with ranking. In Nips’01, p. 641-647.
  • Craswell N., Zoeter O., Taylor M., Ramsey B. (2008). An experimental comparison of click position-bias models. In Proceedings of the international conference on web search and web data mining, p. 87–94. New York, NY, USA, ACM.
  • Dang V., Croft B. (2010). Feature selection for document ranking using best first search and coordinate ascent. In Sigir workshop on feature generation and selection for information retrieval.
  • Freund Y., Iyer R., Schapire R. E., Singer Y. (2003, décembre). An efficient boosting algorithm for combining preferences. J. Mach. Learn. Res., vol. 4, p. 933–969.
  • En ligneFreund Y., Schapire R. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, vol. 55, n° 1, p. 119– 139.
  • En ligneFriedman J. H. (2000). Greedy function approximation: A gradient boosting machine. Annals of Statistics, vol. 29, p. 1189–1232.
  • Gan Q., Attenberg J., Markowetz A., Suel T. (2008). Analysis of geographic queries in a search engine log. In Proceedings of the first international workshop on location and the web, p. 49-56. New York, NY, USA, ACM.
  • Geng X., Liu T.-Y., Qin T., Arnold A., Li H., Shum H.-Y. (2008). Query dependent ranking using k-nearest neighbor. In Proceedings of the 31st annual international acm sigir conference on research and development in information retrieval, p. 115–122. New York, NY, USA, ACM.
  • Geng X., Liu T.-Y., Qin T., Li H. (2007). Feature selection for ranking. In Proceedings of the 30th annual international acm sigir conference on research and development in information retrieval, p. 407–414. New York, NY, USA, ACM.
  • Guo F., Liu C., Wang Y. M. (2009). Efficient multiple-click models in web search. In Proceedings of the second acm international conference on web search and data mining, p. 124-131. New York, NY, USA, ACM.
  • Guyon I., Elisseeff A. (2003, mars). An introduction to variable and feature selection. J. Mach. Learn. Res., vol. 3, p. 1157–1182.
  • Hua G., Zhang M., Liu Y., Ma S., Ru L. (2010). Hierarchical feature selection for ranking. In Proceedings of the 19th international conference on world wide web, p. 1113–1114. New York, NY, USA, ACM.
  • En ligneJansen B. J., Booth D. L., Spink A. (2008). Determining the informational, navigational, and transactional intent of web queries. Information Processing and Management, vol. 44, n° 3, p. 1251 - 1266.
  • Joachims T. (2002). Optimizing search engines using clickthrough data. In Proceedings of the eighth acm sigkdd international conference on knowledge discovery and data mining, p. 133–142. New York, NY, USA, ACM.
  • Joachims T., Granka L., Pan B., Hembrooke H., Gay G. (2005). Accurately interpreting clickthrough data as implicit feedback. In Proceedings of the 28th annual international acm sigir conference on research and development in information retrieval, p. 154–161. New York, NY, USA, ACM.
  • En ligneJohn G. H., Kohavi R., Pfleger K. (1994). Irrelevant features and the subset selection problem. In Proceedings of the eleventh international conference on machine learning, p. 121–129. Morgan Kaufmann.
  • Kang I.-H., Kim G. (2003). Query type classification for web document retrieval. In Proceedings of the 26th annual international acm sigir conference on research and development in informaion retrieval, p. 64–71. New York, NY, USA, ACM.
  • En ligneKohavi R., John G. H. (1997). Wrappers for feature subset selection. Artificial Intelligence, vol. 97, n° 1, p. 273–324.
  • Lai H., Pan Y., Liu C., Lin L.,Wu J. (2012). Sparse learning-to-rank via an efficient primal-dual algorithm. IEEE Transactions on Computers, vol. 99, n° PrePrints.
  • En ligneLal T., Chapelle O., Weston J., Elisseeff A. (2006). Embedded methods. In I. Guyon, M. Nikravesh, S. Gunn, L. Zadeh (Eds.), Feature extraction, vol. 207, p. 137-165. Springer Berlin / Heidelberg.
  • Laporte L. (2012, mai). Ordonnancement des résultats sur les moteurs de recherche : principes, limites et applications au géoréférencement (short paper). In Séminaire Veille Stratégique Scientifique et Technologique (Séminaire VSST), Ajaccio, 23/05/12-25/05/12, p. (en ligne). Veille Stratégique Scientifique et Technologique(VSST).
  • Laporte L., Candillier L., Déjean S., Mothe J. (2012, mai). Modélisation de la pertinence dans les moteurs de recherche géoréférencés (regular paper). In INFormatique des Organisations et Systemes d’Information et de Decision (INFORSID), Montpellier, 29/05/2012-31/05/2012, p. 281–297. Association INFORSID.
  • Li P., Burges C. J. C., Wu Q. (2007). Mcrank: Learning to rank using multiple classification and gradient boosting. In J. C. Platt, D. Koller, Y. Singer, S. T. Roweis (Eds.), Nips. Curran Associates, Inc.
  • Liu C., Guo F., Faloutsos C. (2009). Bbm: bayesian browsing model from petabyte-scale data. In Proceedings of the 15th acm sigkdd international conference on knowledge discovery and data mining, p. 537–546. New York, NY, USA, ACM.
  • Liu T.-Y. (2011). Learning to rank for information retrieval. Springer.
  • En ligneMishne G., De Rijke M. (2006). A study of blog search. Advances in information retrieval, p. 289–301.
  • Nallapati R. (2004). Discriminative models for information retrieval. In Proceedings of the 27th annual international acm sigir conference on research and development in information retrieval, p. 64–71. New York, NY, USA, ACM.
  • Pahikkala T., Airola A., Naula P., Salakoski T. (2010). Greedy rankrls: a linear time algorithm for learning sparse ranking models. In E. Gabrilovich, A. J. Smola, N. Tishby (Eds.), Sigir 2010 workshop on feature generation and selection for information retrieval, p. 11-18. ACM.
  • Pan F., Converse T., Ahn D., Salvetti F., Donato G. (2009). Feature selection for ranking using boosted trees. In Proceedings of the 18th acm conference on information and knowledge management, p. 2025–2028. New York, NY, USA, ACM.
  • En ligneQin T., Liu T., Xu J., Li H. (2010). Letor: A benchmark collection for research on learning to rank for information retrieval. Information Retrieval, vol. 13, n° 4, p. 346–374.
  • Radlinski F., Joachims T. (2005). Query chains: learning to rank from implicit feedback. In Proceedings of the eleventh acm sigkdd international conference on knowledge discovery in data mining, p. 239–248.
  • En ligneRose D., Levinson D. (2004). Understanding user goals in web search. In Proceedings of the 13th international conference on world wide web, p. 13–19.
  • Salton G. (1968). Automatic information organization and retrieval. McGraw Hill Text.
  • En ligneSikonja M. R., Igor K. (2003). Theoretical and empirical analysis of relieff and rrelieff. Machine Learning, vol. 53, n° 1-2, p. 23–69.
  • Sun Z., Qin T., Tao Q., Wang J. (2009). Robust sparse rank learning for non-smooth ranking measures. In Proceedings of the 32nd international acm sigir conference on research and development in information retrieval, p. 259–266. New York, NY, USA, ACM.
  • En ligneTaylor M., Guiver J., Robertson S., Minka T. (2008). Softrank: optimizing non-smooth rank metrics. In Proceedings of the international conference on web search and web data mining, p. 77–86.
  • Vapnik V. (1999). The nature of statistical learning theory. springer.
  • Xia F., Liu T.-Y.,Wang J., ZhangW., Li H. (2008). Listwise approach to learning to rank: theory and algorithm. In Proceedings of the 25th international conference on machine learning, p. 1192-1199. New York, NY, USA, ACM.
  • Xu J., Li H. (2007). Adarank: a boosting algorithm for information retrieval. In Proceedings of the 30th annual international acm sigir conference on research and development in information retrieval, p. 391–398. New York, NY, USA, ACM.
  • Yu H., Oh J., Han W.-S. (2009). Efficient feature weighting methods for ranking. In Proceedings of the 18th acm conference on information and knowledge management, p. 1157– 1166. New York, NY, USA, ACM.
  • Yue Y., Finley T., Radlinski F., Joachims T. (2007). A support vector method for optimizing average precision. In Proceedings of the 30th annual international acm sigir conference on research and development in information retrieval, p. 271–278. New York, NY, USA, ACM.
  • Zoeter O., Taylor M., Snelson E., Guiver J., Craswell N., Szummer M. (2008). A decision theoretic framework for ranking using implicit feedback. In Sigir 2008 workshop on learning to rank for information retrieval.
Léa Laporte
Institut de Recherche en Informatique de Toulouse, UMR 5505, CNRS, Université Paul Sabatier, 118 Route de Narbonne
31062 Toulouse Cedex 9, France
Nomao SA, 1 avenue Jean Rieux
31500 Toulouse, France
Dernière publication diffusée sur Cairn.info ou sur un portail partenaire
Mis en ligne sur Cairn.info le 15/05/2013
https://doi.org/10.3166/DN.16.1.97-121
Pour citer cet article
Distribution électronique Cairn.info pour Lavoisier © Lavoisier. Tous droits réservés pour tous pays. Il est interdit, sauf accord préalable et écrit de l’éditeur, de reproduire (notamment par photocopie) partiellement ou totalement le présent article, de le stocker dans une banque de données ou de le communiquer au public sous quelque forme et de quelque manière que ce soit.
keyboard_arrow_up
Chargement
Chargement en cours.
Veuillez patienter...