Soutenance mémoire
Contexte
La Recherche d’Information (RI), née en 1950, s’attache à définir des modèles et des systèmes dont le but est de faciliter l’accès à un ensemble de documents sous forme électronique (corpus de documents), afin de permettre à des utilisateurs de retrouver les documents dont le contenu répond à leur besoin d’information. La RI est donc centrée sur la notion de pertinence qui est définie par le degré de corrélation entre la requête utilisateur et les réponses retrouvées. Les modèles de RI sont construits autour du triplet document, besoin d’information et fonction de correspondance. Ces modèles constituent encore aujourd’hui la base sur laquelle sont développés les systèmes de recherche d’information (SRI), dont les moteurs de recherche sur le Web. Ainsi, un SRI est un système qui indexe un corpus de document et qui évalue un ensemble de documents pertinents en réponse à une requête formulée par un utilisateur. Les systèmes de recherche d’information sont composés essentiellement de deux modules : un module d’indexation et un module d’interrogation. Le module d’indexation construit des abstractions des contenus de documents appelées index. Le module d’interrogation construit des abstractions des besoins d’information utilisateurs appelées requêtes et les compare à l’index grâce à une fonction de correspondance, laquelle permet de calculer une pertinence entre la requête et l’index. Cette fonction de correspondance est un composant très important dans tout SRI. Dans le cas de la recherche d’information sur le Web, son importance devient critique vu la taille du Web, qui atteint des milliards de documents. Il est donc impératif d’avoir de bonnes fonctions de correspondance afin de mieux répondre aux besoins d’information utilisateurs exprimés à travers les requêtes.
La qualité d’un système doit être mesurée en comparant les réponses du système avec les réponses idéales que l’utilisateur espère recevoir. Plus les réponses du système correspondent à celles que l’utilisateur espère, meilleur est le système. La démarche de validation en recherche d’information repose sur l’évaluation expérimentale des performances des modèles ou des systèmes proposés. Cette évaluation peut porter sur plusieurs critères : le temps de réponse, la pertinence, la qualité et la présentation des résultats, etc. Le critère le plus important est celui qui mesure la capacité du système à satisfaire le besoin d’information d’un utilisateur, c’est à dire la pertinence qui est une une notion complexe. Deux facteurs permettent d’évaluer ce critère. Le premier est le rappel, il mesure la capacité du système à sélectionner tous les documents pertinents. Le second est la précision, il mesure la capacité du système à ne sélectionner que les documents pertinents ou à rejeter tous les documents non pertinents. Les mesures de précision et de rappel sont très utilisées sur des corpus textuels lorsqu’on connaît l’ensemble des éléments du corpus analysé. Cependant, ces mesures sont difficilement applicables dans le cas d’un moteur de recherche car il est difficile d’avoir une idée précise de l’ensemble des documents visibles sur le Web.
Modèles d’analyse de liens en recherche d’information
Afin de mettre l’apport proposé dans ce mémoire dans la perspective des travaux publiés sur le même sujet, nous consacrons ce chapitre à une présentation des approches les plus similaires à la nôtre. Le nombre très important de publications relatives à l’utilisation des liens en recherche d’information rend impossible une présentation exhaustive de toutes ces méthodes. Nous insistons plus particulièrement sur les travaux les plus connus qui portent sur la propagation de valeurs (pertinence ou popularité) à travers le graphe du Web. Nous portons une attention particulière aux approches que nous utilisons dans nos experimentations afin d’évaluer notre système par rapport à ces approches, en insistant sur les avantages et les limites de chaque approche.
Les modèles d’analyse de liens que nous présentons dans les sections qui suivent sont inspirés des travaux de recherche issus de la bibliométrie. On distingue deux méthodes de citation des articles scientifiques utilisées en bibliométrie : la co-citations (Marshakova [Mar73] et Small [Sma73]) et le couplage bibliographique (Kessler [Kes63]). Nous avons classé ces modèles en trois grandes familles selon leur mode de fonctionnement 2.1, à savoir : la propagation de popularité, la propagation de pertinence et la propagation d’information. Il existe plusieurs travaux de recherche qui portent sur l’analyse des graphes du Web afin d’améliorer les performances de la recherche d’information. Par definition, le graphe du Web est constitué de plusieurs nœuds qui représentent les documents et de liens qui relient ces nœuds. Nous distinguons deux types de liens dans le Web : les liens hypertextes et les liens de structure physique des sites Web (chemin d’accès à un document ou URLs). Il existe aussi plusieurs types de document : pages Web, blocs, chemins de lecture, groupes de pages Web (ex. un site). Dans les algorithmes d’analyse de liens, la propagation de popularité, de pertinence ou d’information à travers les liens du graphe permettent d’accorder une certaine importance aux nœuds du graphe qui jouent un rôle particulier (portail, page d’accueil, document de référence, etc.), dans le but d’enrichir sémantiquement le contenu de ces nœuds et d’augmenter leur pertinence par rapport à un besoin utilisateur. La propagation d’information porte sur le contenu des nœuds citant le nœud courant (par exemple associer le texte ancre des liens, les mots clés et les titres de la page source du lien à la page destinataire du lien). Tandis que la propagation de popularité et la propagation de pertinence consistent à assigner une nouvelle valeur de qualité au nœud courant en fonction des valeurs de qualité des nœuds citant ou cités par ce nœud courant.
Propagation de popularité
La propagation de popularité est une approche dérivée des méthodes d’analyse de citations et de co-citations utilisées en bibliométrie (Kessler [Kes63], White et al. [WM89]) qui consiste à privilégier les documents populaires qui jouent un rôle particulier dans le graphe de liens. Typiquement, il s’agit de la notion de popularité : « une page référencée par un grand nombre de pages est une bonne page ». Différentes études ont suggéré de tenir compte de la popularité des documents afin d’améliorer les performance de la recherche d’information. Le PageRank [BP98] de Google et le HITS [Kle99] de Kleinberg sont deux algorithmes fondamentaux qui utilisent les liens hypertextes pour classer les résultats d’une requête. Un certain nombre d’extension de ces deux algorithmes ont été proposés, comme Lempel [LM00], Haveliwala [Hav02], Kamvar et al. [KHMG03], Cai et al. [CYWM04], Jiang et al. [JXS+04] et Jeh et all [JW03]. Généralement, ces algorithmes fonctionnent en deux temps. Dans une première étape, un moteur de recherche classique retourne une liste de documents répondant à la requête posée, en fonction des termes de la requête et des termes d’indexation des documents. Dans une seconde étape, ces systèmes tiennent compte des liens hypertextes pour classer ces documents. Les scores accordés aux documents avant la propagation sont identiques. L’utilisation d’un algorithme d’analyse de liens permet en sorte de calculer une valeur de la popularité de chaque document répondant à la requête utilisateur. Nous distinguons deux catégories d’algorithmes d’analyse de liens : la première catégorie regroupe tous les algorithmes qui calculent une valeur de popularité unique à l’étape d’indexation, c’est le cas du PageRank [BP98] qui calcule une valeur de popularité pour l’ensemble des pages Web en appliquant l’algorithme de PageRank sur le graphe du Web en entier. La deuxième catégorie regroupe les algorithmes d’analyse des liens appliqués à un sous-ensemble de pages Web répondant totalement ou partiellement à la requête utilisateur.
Propagation de popularité sur l’ensemble d’une collection
Dans les systèmes de propagation de popularité appliquée à l’ensemble des documents de la collection, le contenu des documents et la structure des liens ont été utilisés séparément . C’est le cas des approches comme Hawking [Haw00], Craswell et al. [CHWW03] et Craswell et al. [CH04] qui utilisent le modèle vectoriel [SWY75] pour calculer un degré de pertinence reposant sur le contenu du document et les liens hypertextes pour calculer un indice de popularité indépendant de la requête (exemple PageRank [BP98]). Ensuite, ces deux scores sont combinés pour classer les documents retrouvés. Ces méthodes sont avérées en pratique moins efficaces par rapport aux méthodes utilisant uniquement le contenu seul des documents.
|
Table des matières
1 Introduction
1.1 Contexte
1.2 Problématique
1.3 Objectifs et contributions de la thèse
1.4 Plan de la thèse
2 Modèles d’analyse de liens en recherche d’information
2.1 Introduction
2.2 Propagation de popularité
2.2.1 Propagation de popularité sur l’ensemble d’une collection
2.2.2 Propagation de popularité sur les résultats d’une requête
2.3 Propagation de pertinence
2.3.1 Propagation d’une fraction du score de pertinence
2.3.2 Modèle général de propagation de pertinence
2.3.3 Propagation de pertinence probabiliste
2.3.4 Discussion sur les modèles de propagation de pertinence
2.4 Analyse des liens au niveau blocs thématiques
2.4.1 Segmentation linéaire du texte brut par cohésion lexicale
2.4.2 Segmentation structurelle de pages Web
2.4.3 Utilisation de liens au niveau blocs
2.5 Conclusion
3 Modélisation du nouveau système
3.1 Introduction
3.2 Modèle de propagation de pertinence
3.2.1 Représentation des documents
3.2.2 Représentation des requêtes
3.2.3 Indexation
3.2.4 Fonction de correspondance
3.3 Architecture du système en trois couches
3.3.1 Niveau page
3.3.2 Niveau site
3.3.3 Niveau bloc
3.4 Algorithme de segmentation
3.4.1 Algorithmes génétiques
3.4.2 Principe de notre algorithme
3.4.3 Processus de segmentation thématique à critères visuels
3.4.4 Les inconvénients de la méthode de segmentation
3.4.5 Complexité de l’algorithme de segmentation
3.5 Conclusion
4 Expérimentations sur les collections TREC et GOV
4.1 Métriques d’évaluation
4.2 Expérimentations au niveau page
4.3 Expérimentations au niveau bloc thématique
4.4 Expérimentations des liens au niveau bloc
5 Conclusion et perspectives
