H2PTM (2007) Chibane

Evaluation d’un modèle de propagation de pertinence dépendant des termes de la requête sur les collections WT10g et Gov

---

 
 

Titre Evaluation d’un modèle de propagation de pertinence dépendant des termes de la requête sur les collections WT10g et Gov Auteurs Idir Chibane(i), Bich-Liên Doan(i) Affiliations (i)SUPELEC, plateau de Moulon, 3 rue Joliot Curie 91192 Gif sur Yvette, France Idir.Chibane@supelec.fr Bich-Lien.Doan@supelec.fr Dans actes du colloque H2PTM 2007 Hammamet publié dans H²PTM07 : Collaborer, échanger, inventer

Résumé

Nous proposons de modéliser la fonction de correspondance d’un système de recherche d’information en prenant en compte à la fois le contenu d’une page et le voisinage de cette page. Ce voisinage est calculé dynamiquement en pondérant les liens hypertextes reliant les pages en fonction des termes de la requête contenus dans ces pages. Nous avons expérimenté notre système sur deux collections de test WT10g et GOV. Nous concluons que notre fonction réalise de bons résultats par rapport à l’algorithme classique reposant sur le contenu seul de la page et celui de pagerank reposant sur la popularité de la page indépendamment des termes de la requête.

Mots-clés 

recherche d’information, système hypertextes, analyse des liens, web, propagation de pertinence, collection de test

English description

Abstract 

We propose to model a matching function for an information retrieval system using both the content and the neighbourhood of a web page. The neighbourhood of a web page is dynamically computed with the terms of the query the pages are composed of. We experienced our system over the two test collections WT10g and GOV. We conclude that our function provides better results in comparison with the baseline based on text content only and the pagerank algorithm which gives a popularity of a page independently from the query term.

Keywords

information retrieval, hypertext systems, link analysis, web, relevance propagation, test collection

 

Introduction

Dans la recherche d’information traditionnelle, il est évident que la pertinence d’un document par rapport à la requête utilisateur réside dans son contenu. Par conséquence, les documents répondant à une requête utilisateur sont classés selon un degré de pertinence estimé pour chaque document et calculé en fonction du son contenu textuel. Cependant, dans le cadre de corpus de documents hypertextes, par exemple le web, l’information peut résider au-delà du contenu textuel du document. C’est le cas de la structure du Web considéré comme un graphe. La structure de graphe est utilisée pour accroître l’estimation de la pertinence accordée au document. Or, les hyperliens sont beaucoup plus nombreux que les documents web et donc représentent une source d’information très importante. De ce fait, de nombreux travaux de recherche utilisant des techniques de recherche reposent sur l’analyse des liens hypertextes ont été proposés (Brin, 1998), (Kleinberg, 1998), etc. L’utilisation des hyperliens pour améliorer les performances de la recherche d’information repose sur l’idée suivante : « les hyperliens relient des documents relatifs et donc ils peuvent fournir des informations additionnelles à la recherche ». En conséquence, les approches de recherche d’information reposant sur les liens dans les systèmes hypertextes utilisent plusieurs méthodes pour affiner le contenu local des documents par l’information provenant de leur voisinage (contenu des documents pointés ou pointant vers ces documents). En général, les approches de recherche d’information reposant sur les liens sont inspirées des travaux d’analyse des citations issus du domaine de la bibliométrie. Deux mesures de similarité entre documents reposant sur la citation ont été proposées dans la bibliométrie (White, 1989) : le couplage bibliographique (Kessler, 1963) qui est le nombre de documents cités par les deux documents p et q, et la co-citation (Small, 1973), qui est le nombre de documents qui citent les deux documents p et q. Dans le contexte de collection de documents hypertextes homogènes traitant d’un seul thème, le contenu informationnel de voisinage introduit par les hyperliens tend à être de grande qualité et d’utilité. Cependant, dans le cadre du web où les hyperliens pointent des documents hétérogènes de contenus différents, l’enrichissement des documents via les hyperliens peut parfois présenter du bruit et en effet, dégrader les performances de la recherche. Dans cet article, nous proposons une technique de propagation de pertinence qui tient compte du voisinage des pages en pondérant dynamiquement les liens qui relient ces pages en fonction du nombre de termes de la requête contenus dans ces pages. Nous avons expérimenté notre modèle de recherche d’information sur deux collections de tests WT10g et GOV. Cet article est composé de plusieurs sections. D’abord, nous présentons quelques travaux d’utilisation des liens dans la recherche d’information. Puis nous détaillons notre modèle avec la fonction de correspondance reposant sur le voisinage de la page que nous proposons. Nous présentons aussi les expériences effectuées sur les deux collections de test TREC et GOV et nous terminons par une conclusion et des perspectives.

Utilisation des liens dans la recherche d’information

Au début de la recherche d’information reposant sur l’analyse des liens, le contenu des documents et la structure des liens ont été utilisés séparément. C’est le cas des approches (Hawking, 2000), (Craswell, 2003), (Craswell, 2004) qui utilisent d’une part le modèle vectoriel (Salton, 1975) pour calculer un degré de pertinence reposant sur le contenu seul du document et d’autre part, les liens hypertextes pour calculer un indice de popularité indépendant de la requête (exemple PageRank (Brin, 1998). Ensuite, ces deux scores sont combinés pour classer les documents retrouvés. Ces dernières années, plusieurs méthodes qui tiennent compte d’une certaine dépendance entre le contenu des documents et la structure des liens ont été développées. (Qin, 2005) distinguent deux catégories de techniques d’analyse des liens. La première catégorie est la propagation de popularité (Kleinberg, 1998),(Lempel, 2000) (Haveliwala, 2002). Dans un premier lieu, un ensemble de documents qui contiennent les termes de la requête est retourné par un moteur de recherche, puis des algorithmes d’analyse de liens issues des études de graphes sont appliqués pour classer ces documents. La deuxième catégorie est la propagation de pertinence (Mcbryan, 1994), (Song, 2004), (Shakery, 2003). Ces méthodes propagent une portion des scores des documents à travers la structure du web composé par des liens hypertextes et les urls (structure hiérarchique des sites). Pour la première catégorie, HITS (Kleinberg, 1998) et topic-sensitive PageRank (Haveliwala, 2002) sont deux algorithmes représentatifs. HITS construit d’abord un sous graphe associé à la requête utilisateur et composé de documents contenant les termes de la requête. Puis, il calcule un poids pivot et un poids autorité pour chaque document. Cependant, Topic-sensitive PageRank calcule un ensemble de vecteur PageRank pour chaque document : le PageRank global et plusieurs PageRank biaisés correspondant à chaque topique préfinis. Généralement, ces méthodes appliquent les techniques d’analyse des liens sur un sous graphe plus petit que le graphe entier du web. Pour la deuxième catégorie, plusieurs méthodes de propagation de pertinence ont été proposées pour enrichir le contenu du document web en propageant des informations sur le contenu des documents voisins à travers la structure des liens. Par exemple, (Mcbryan, 1994), (Brin, 1998) propagent le texte ancre, (Shakery, 2003) propagent une fraction du score de pertinence à travers le graphe des liens et (Song, 2004) propagent les fréquences de termes de la requête à travers la structure hiérarchique d’un site web. (Shakery, 2006) propage des scores de probabilités calculés à partir d’un modèle de surfer aléatoire en utilisant de multiples ensembles de voisinages.

Méthodes de propagation de pertinence

Nombreux travaux sur la propagation de pertinence à travers la structure du Web ont été proposés pour améliorer les performances de la recherche d’information. (Shakery, 2003) ont proposé un cadre général pour les algorithmes de propagation de pertinence à travers la structure des liens. Ils distinguent deux facteurs importants pour calculer la pertinence d’un document par rapport un besoin utilisateur : le score de pertinence du document lui-même et les scores de pertinence des documents voisins. Motivé par cette observation, (Shakery, 2003) propagent le score de pertinence d’un document à travers le graphe des liens. Ils ont définis un degré de pertinence « hyper-pertinent » pour chaque document comme une fonction de trois variables : la similarité entre le contenu du document et la requête, la somme des scores de pertinence des documents qui pointent ce document et la somme des scores de pertinence de documents pointés par ce document. Formellement, le modèle de propagation de pertinence peut être décrit comme suit :

Où hk(d,q) est le score «hyper-pertinent» du document d à l’étape k du calcul, S(d,q) est la similarité entre le contenu du document d et la requête q et wI et wO sont deux poids de pondération associés aux liens entrants et sortants respectivement. Ces poids sont calculés à partir du graphe des liens indépendamment des termes de la requête. En principe, le choix de la fonction f est aléatoire. Un choix précieux de f est la combinaison linéaire des variables. Les scores de pertinence peuvent être calculés itérativement jusqu'à ce que l’algorithme converge vers une limite qui n’est autre que le score final des documents à classer. Dans la pratique, (Shakery, 2003) distinguent trois cas simplifiés du modèle spécifique de propagation de pertinence. Chaque cas correspond à un certain comportement de l'utilisateur pendant sa recherche.

Tableau 1. Différents modèles spécifiques de propagation de pertinence

Tableau 1. Différents modèles spécifiques de propagation de pertinence (Song, 2004) ont proposé une méthode de propagation de fréquence des termes de la requête à travers la structure hiérarchique d’un site Web. Pour décrire un site web, la page index est la mieux placée par rapport à une page feuille dans la structure du site. En effet, une page index contient des informations globales sur le site et des liens vers les pages qui constituent le site. Donc, il vaut mieux retournée une page index plutôt qu’une page feuille de la structure hiérarchique du site en réponse à une requête utilisateur. Le fait de propager les fréquences des termes à travers la structure hiérarchique d’un site web va augmenter le degré de pertinence de la page index par rapport à la requête. La fréquence d’occurrence d’un terme t dans ce modèle de propagation de frequence est décrite comme suit :

Où et sont les fréquences d'occurrence du terme t dans la page p avant et après la propagation des fréquences des termes. Après avoir propagé les fréquences de termes à travers la structure du site, n’importe quel algorithme de calcul de pertinence des documents peut être utilisé pour classer ces documents. (Qin, 2005) ont proposé un cadre général de propagation dont plusieurs méthodes se sont des dérivées de ce modèle.

Nouveau modèle de propagation de pertinence

Notre système est composé de deux modules : le module d’indexation qui représente les documents et le module d’interrogation qui représente les requêtes. La fonction de correspondance qui permet de calculer le degré d’appariement entre les termes de la requête et les termes d’indexation des documents afin d’évaluer la pertinence des documents par rapport à la requête utilisateur repose sur le contenu et le voisinage de la page en fonction des termes de la requête. Ce voisinage est calculé dynamiquement en pondérant les liens hypertextes reliant les pages en fonction des termes de la requête contenus dans ces pages.

Fonction de correspondance

La nouveauté dans notre modèle est l’utilisation d’une fonction de correspondance qui dépend en plus du contenu textuel des pages, de leurs voisinages. Cette dépendance permet une meilleure adéquation des résultats retrouvés par un modèle classique de recherche d’information avec un besoin utilisateur. Notre fonction de correspondance repose sur deux mesures : l’une est classique et utilisée dans les systèmes actuels. C'est la mesure OKAPI BM25. Et l'autre repose sur le calcul d'un score de voisinage dynamiquement en pondérant les liens hypertextes reliant les pages en fonction des termes de la requête contenus dans ces pages. La combinaison de ces deux scores est décrite comme suit :

Avec α un paramètre compris entre 0 et 1. Il nous permet de voir l'impact de notre fonction de voisinage sur celle reposant sur le contenu seul de la page. On note S(Pi,Q) le score global de la page Pi par rapport à la requête Q, SV(Pi,Q) le score de voisinage de la page Pi par rapport à la requête et SD(Pi,Q) le score associé à la page Pi reposant sur son contenu textuel. Nous détaillons la fonction de voisinage ainsi que la pondération des liens dans la section suivante.

Fonction de voisinage

La fonction de voisinage que nous avons proposée tient compte de la structure du Web composée des liens hypertextes. L'hypothèse que repose notre modèle est décrite comme suit : "On considère qu'une page Web est bien connue pour un terme T de la requête Q si celle-ci contient beaucoup de liens entrants émis à partir des pages qui elles aussi contiennent le terme T de la requête" (Doan, 2005). Cette mesure tient compte du nombre de termes de la requête contenus dans les pages Web. L'idée principale de notre mesure de voisinage est de pondérer les liens entrants selon le nombre de termes contenu dans la page source du lien. L'hypothèse qu'on a fixée au départ stimule que le poids d'un lien émis par un document contenant k termes de la requête Q est deux fois plus important que le poids d'un lien contenant k-1 termes de la requête Q. Supposons une requête Q contenant nbtQ termes et une page P retournée par un système traditionnel de recherche d'information. Soit nbtQ(P) le nombre de termes de la requête Q appartenant à la page P. Notons EP le nombre de liens entrants de la page P. La fonction de voisinage est décrite de la manière suivante :

Avec Wl(Pi,P,Q) est la pondération du lien entre la page Pi et la page P en fonction du nombre de termes de la requête Q appartenant à la page source du lien(i.e. Pi). Plus la page Pi contient de termes de la requête Q, plus le poids du lien entre Pi et P est grand et plus le score de pertinence de la page P est grand. Ce poids est défini comme suit :

β est un paramètre compris entre 0 et 1 et vérifie que la distribution de probabilité sur les différents types de liens selon le nombre de termes de la requête appartenant à la source du lien vaut 1. Par exemple, pour une requête composée de deux termes, nous avons deux types de liens : Type 1 : Liens partant de pages contenant un seul terme. Type 2 : Liens partant de pages contenant les deux termes.

Plus la requête contient de termes, moins sera la valeur de β. Le rôle de β est de réduire la contribution de voisinage en fonction du nombre de termes de la requête car dans le cas d’une requête contenant beaucoup de termes, le voisinage d’une page peut induire du bruit. En remplaçant ¦β¦ par sa valeur dans la fonction de voisinage, nous obtiendrons la fonction suivante que nous employons dans nos expérimentations.¶

Expérimentations sur les collections TREC et GOV

Tableau 2. Caractéristiques des collections de test TREC et GOV

Dans le cadre de nos expérimentations, nous avons choisi comme collection de tests la collection WT10g et la collection GOV issue du corpus de la conférence TREC ayant eu lieu en 2000 et 2002 respectivement. Nous les avons choisies en raison de la notoriété des collections issues de TREC et par conséquent, leur statut de collections standard dans le domaine de la recherche d’information. Nous voulons connaître à partir de ces expérimentations l’impact de notre fonction de voisinage sur le classement des résultats. Afin d’évaluer notre système, nous avons exécuté 50 requêtes sur des systèmes différents selon la fonction de correspondance utilisée. Les requêtes exécutées sur les deux collections TREC et GOV sont différentes. Chaque collection est définie par un ensemble de 50 besoins d’information et un ensemble de jugements de pertinence des documents par rapport à chaque requête. Le tableau 2 montre les caractéristiques de chacune des deux collections.

Figure 1. La précision moyenne aux 11 niveaux standard du rappel pour les différentes fonctions de correspondance utilisées (contenu seul, popularité et combinaison du contenu et du voisinage)

La figure 1 montre les résultants expérimentaux obtenus sur les deux collections TREC et GOV en utilisant trois fonctions de correspondance différentes. La première fonction repose sur le contenu textuel seul de la page. Elle représente l’algorithme de base de nos évaluations. La deuxième fonction repose sur la popularité d’une page indépendamment des termes de la requête. En fait, nous avons utilisé l’algorithme de pagerank (Brin, 1998) qui classe les pages retrouvées par leurs popularités. La dernière fonction est une combinaison d’une mesure de contenu textuel d’une page et de son voisinage que nous avons proposée, avec le paramètre α optimal (0,15 pour la collection TREC et 0.25 pour la collection GOV). D’après la figure 1, on peut constater que l’algorithme pagerank réalise de mauvais résultats par rapport aux deux autres algorithmes sur les deux collection TREC et GOV. Avec cet algorithme, une page a le même score (un indice d’importance indépendant de la requête) pour chaque requête exécutée sur le système. C’est pour cette raison que les résultats obtenus sont mauvais. La combinaison entre une mesure reposant sur le contenu d’une page et son voisinage immédiat montre de meilleurs résultats par rapport à l’algorithme de base qui n’est autre que la fonction basée sur le contenu seul de la page et sur les deux collections TREC et GOV. Ceci signifie que le voisinage d’une page que nous avons proposé apporte plus de précision dans les résultats retournés par un moteur de recherche.

Tableau 3. Comparaison entre différentes fonctions de correspondance (Contenu seul, popularité et voisinage) en fonction de la P@5, P@10 et S@5 sur les deux collections TREC et GOV

Le tableau 3 montre les résultats obtenus sur les deux collections TREC et GOV en comparant les différents algorithmes testés par rapport à la précision moyenne à 5 et 10 documents retrouvés (P@5 et P10) et Succès@5 respectivement. D’après ce tableau, les performances de notre système restent toujours au-dessus de l’algorithme de base avec les deux mesures d’évaluation. Cela signifie qu’avec notre fonction de voisinage, il y a plus de documents pertinents au top du classement et il y a plus de requêtes qui ont au moins une répons pertinente parmi les cinq premiers documents du classement par rapport à l’algorithme de base.

Conclusion et des perspectives

Dans cet article, nous avons proposé un modèle de propagation de pertinence. La nouveauté dans notre modèle est l’utilisation d’une fonction de correspondance qui tient compte à la fois le contenu et le voisinage d’une page. Ce voisinage est calculé dynamiquement en pondérant les liens hypertextes reliant les pages en fonction du nombre de termes de la requête contenus dans ces pages. Nous avons expérimenté notre système sur les deux collections de test WT10g et GOV. Les résultats obtenus avec la combinaison du contenu et le voisinage d’une page dans la fonction de correspondance montrent de meilleurs résultats par rapport à ceux qui reposent sur le contenu seul ou sur les liens indépendamment de la requête. Nous constatons que les résultats obtenus par notre système avec la collection GOV sont comparables à ceux obtenu dans le cadre d’expérimentation sur WT10g. Nous poursuivons actuellement un travail pour intégrer une mesure sur la propagation des scores à travers un graphe de blocs thématiques pour améliorer les performances de notre système. Nous allons découper les pages Web en plusieurs blocs thématiques en utilisant une fonction de segmentation reposant sur des critères visuels et de présentation de document en utilisant deux mesures :la cohérence des termes constituant le bloc et la distance entre deux blocs adjacents.

Bibliographie

[Brin, 1998] ↑ Brin S. et Page L., « The anatomy of a large-scale hyper textual Web search engine », In Proceeding of WWW7, 1998.

[Craswell, 2003] ↑ Craswell N. et Hawking D., « Overview of the TREC 2003 Web Track », in 12th TREC, 2003.

[Craswell, 2004] ↑ Craswell N. et Hawking D., « Overview of the TREC 2004 Web Track », in 13th TREC, 2004.

[Doan, 2005] ↑ Doan B-L. et Chibane I., « Expérimentations sur un modèle de recherche d’information utilisant les liens hypertextes des pages Web », Revue des Nouvelles Technologies de l'Information (EGC’2005), pp.257-262, 2005.

[Hawking, 2000] ↑ Hawking D., « Overview of the TREC-9 Web Track », in the 9th TREC, 2000.

[Kessler, 1963] ↑ Kessler M.M., « Bibliographic coupling between scientific papers », American Documentation, p. 10-25, 1963.

[Lempel, 2000] ↑ Lempel R. et Moran S., « The stochastic approach for link-structure analysis (SALSA) and the TKC effect », In Proceeding of 9th International World Wide Web Conference, 2000.

[Mcbryan, 1994] ↑ Mcbryan O., « GENVL and WWW: Tools for Taming the Web », In Proceedings of the 1st WWW, 1994.

[Qin, 2005] ↑ Qin T., Liu T.Y., Zhang X.D., Chen Z. et Ma W.Y., « A Study of Relevance Propagation for Web Search », The 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 2005.

[Small, 1973] ↑ Small H., « Co-Citation in the Scientific Literature: A New Measure of the Relationship between Two Documents », Journal of the American Society for Information Science, p. 265-269, 1973.

[Salton, 1975] ↑ Salton G., Yang C.S. et Yu C.T., « A theory of term importance in automatic text analysis », Journal of the American Society for Information Science and Technology, 1975.

[Shakery, 2003] ↑ Shakery A. et Zhai C.X., « Relevance Propagation for Topic Distillation UIUC TREC 2003 Web Track Experiments », in the 12th TREC, 2003.

[Shakery, 2006] ↑ Shakery A. et Zhai C.X., « A probabilistic relevance propagation model for hypertext retrieval », CIKM '06: Proceedings of the 15th ACM international conference on Information and knowledge management, P.550-558, 2006.

[Song, 2004] ↑ Song R., Wen J.R., Shi S.M., Xin G.M., Liu T.Y. et Qin T., « Microsoft Research Asia at Web Track and Terabyte Track of TREC 2004 », in the 13th TREC, 2004

[White, 1989] ↑ White H.D. et McCain K.W., « Bibliometrics », Annual Review of Information Science and Technology, p. 119-186, 1989Annual Review of Information Science and Technology, p. 119-186, 1989Annual Review of Information Science and Technology, p. 119-186, 1989