Soutenance mémoire
La Recherche d’Information (RI) est un problème qui, malgré son ancienneté, continue à s’imposer comme un besoin essentiel à la plupart des utilisateurs. En effet, le besoin d’avoir de l’information pertinente est crucial d’autant plus que les systèmes de partage de contenus évoluent et prennent plusieurs formes qui, dans la plupart des cas cohabitent ensemble. L’information est disponible sous forme de grands volumes sur des serveurs centralisés, décentralisés, dans les blogs, chez des utilisateurs, chez des communautés, etc [add online 2009, Informatica 2010]. Les concepts de base de la recherche d’information sont toujours adoptés mais selon le système de partage d’information et le volume de données, de nouvelles contraintes affectant toutes les phases d’un processus de recherche d’information apparaissent et les techniques de recherche sont appelées à évoluer. Dans ce chapitre, nous présentons les concepts de base d’un système de Recherche d’Information. Nous décrivons les principes de base de la Recherche d’Information, puis nous détaillons les phases de la Recherche d’Information Distribuée pour arriver à la fin aux problèmes spécifiques aux systèmes de Recherche d’Information largement distribués tels que les systèmes Pair-à-pair [Defude 2007]. Nous évoquons de même, le défi de l’intégration de la sémantique, en vue d’améliorer les processus de recherche, dans les systèmes Pair-à-Pair.
Les Systèmes de Recherche d’Information Centralisés
La Recherche d’Information (RI) documentaire est un concept qui remonte aux années 50 lorsque Mooers [Mooers 1950] a inventé ce terme pour la première fois. Mooers définit un Système de Recherche d’Information (SRI) comme un système d’information permettant, à une personne exprimant un besoin, d’extraire, à partir d’une collection documentaire, les documents qui correspondent à son besoin. Cette définition met en évidence deux éléments essentiels dans un processus de Recherche d’Information : une requête et un ensemble d’informations appelé collection, à partir duquel le système délivre des ressources pertinentes à la requête utilisateur.
De manière formelle, et en référence au modèle de [Baeza-Yates 1999], un SRI peut être défini comme un quadruplet M = (D, Q, F, S(qi , dj )), tel que :
– D : représente un ensemble de vues logiques pour des documents dans une collection.
– Q : est un ensemble de vues logiques pour des requêtes utilisateurs.
– F : ensemble de modèles de représentation de documents ou de requêtes.
– S(dj , qi) : fonction de classement ou plus précisément de similarité du document dj par rapport à la requête qi .
Processus de recherche d’information centralisé
Les SRIs sont largement utilisés dans différents domaines d’activités [Andrieu 2011]. Les systèmes « historiques » les plus connus, sont Smart dans les années 80 [Salton 1989] et Medline, qui se présente parmi les systèmes commerciaux, actuellement accessible depuis [PubMedline 2012]. Le concept de SRI a été popularisé avec l’avènement du web sous la forme des moteurs de recherche dont les plus connus sont notamment, le leader Google [Page 1998] ou « son equivalent » Bing de Microsoft [center 2012] . La Figure 1.1 représente les briques de base d’un SRI centralisé. Un SRI doit être en mesure d’indexer, d’une part les documents présents dans son corpus documentaire et d’autre part, les besoins en information exprimés par les utilisateurs, puis de rechercher les documents les plus pertinents par rapport à une requête utilisateur et de les ordonner. Compte tenu des éléments du quadruplet M, un processus de recherche d’information centralisé comporte au moins trois modules de base : le module d’indexation, le module d’interrogation et le module d’appariement.
Module d’indexation
Le module d’indexation consiste à représenter l’ensemble de documents présents dans un corpus documentaire, sous forme d’un ensemble de vues logiques [Baeza-Yates 1999], visant à repérer les contenus de ces documents, afin d’en faciliter la recherche et l’accès. L’indexation concerne également les requêtes afin de les écrire dans un langage Q qui est l’ensemble de vues logiques représentant une requête (ce qui correspond au deuxième élément du quadruplet M) comparable à celui des documents (D). Souvent, la même méthode d’indexation est utilisée pour indexer aussi bien les documents que les requêtes. Ainsi, pour rechercher une information à partir d’une collection de données, un SRI doit accéder à ces informations d’une façon unique en comparant une requête à un ensemble de clés formant l’index de la collection. La façon par laquelle on représente les documents ou les requêtes dépend d’un modèle de représentation F. Plusieurs modèles de représentation de contenus existent [Salton 1975, Ponte 1998, Baeza-Yates 1999, Savoy 2001].
Le module d’appariement ou de filtrage
Ce module constitue le cœur de tout le processus de Recherche d’Information. En effet, c’est au cours de la phase d’appariement qu’un Système de Recherche d’Information produit les réponses jugées adéquates satisfaisant le mieux possible le besoin de l’utilisateur. Ceci passe par l’utilisation d’une fonction d’estimation de la similarité (ou fonction de scoring) S(di , qj ) entre le document di et la requête qj . Faisant référence au score calculé par la fonction de similarité, un SRI procède généralement au tri des réponses qu’il retourne à l’utilisateur (voir Figure 1.1). La pertinence des réponses retournées par un SRI et leur ordre dépendent d’une procédure d’évaluation qui vise à réduire la distance entre les réponses du système (ou pertinence système) et les intensions de l’utilisateur (ou pertinence utilisateur). La fonction de similarité utilisée est très différente d’un SRI à un autre et dépend du modèle de RI adopté par le système. Les Systèmes de Recherche d’Information intègrent différents algorithmes pour mesurer la similarité d’une représentation d’un document relativement à celle d’une requête et pour évaluer par conséquent la pertinence du document relativement à la requête. Par exemple, Les fonctions cosinus, dice, jaccard et overlap [Egghe 2010] constituent une famille de fonctions de similarités largement utilisées dans le modèle vectoriel [Salton 1989] (voir plus loin dans ce chapitre). Le modèle probabiliste utilise un autre ensemble de fonctions de correspondance, telle que la fonction okapi BM25 [Robertson 1995]. Des fonctions de similarité sémantiques existent également, comme par exemple, la similarité de Salton [Salton 1989].
Les méthodes d’appariement utilisent des logiques différentes pour classer les documents par rapport à une requête. De ce fait, elles peuvent diverger nettement dans l’ordre qu’elles affectent à leurs réponses même s’il s’agit de classer les mêmes réponses retournées. Cette divergence de classement peut être remarquée pour une même famille de méthodes d’appariement. Ainsi, une fonction cosinus peut donner un ordre différent de celui donné par dice pour la réponse à une requête q. Ceci pose le problème de l’estimation de l’efficacité des modèles de RI et rend essentiel le recours à leurs évaluations.
Google : une solution centralisée pour de très gros volumes
Pour la grande communauté des utilisateurs d’Internet, la Recherche d’Information est une opération facile et quotidienne qui se compose de 3 phases : (i) taper un ensemble de mots clé dans le moteur de recherche Google [Page 1998] ; (ii) récupérer les réponses sur quelques dizaines de pages ; et, (iii) consulter les meilleures réponses généralement sur les 10 premières réponses retournées. Google étant le moteur de recherche le plus présent sur le web, ceci explique pourquoi le concept de Recherche d’Information s’est fortement ancré chez le grand public avec le moteur de recherche Google [Dean 2009]. Pour l’indexation, Google utilise des robots logiciels (les spiders) qui, à partir de quelques points d’entrée, vont explorer en profondeur et ce récursivement, toutes les pages qui leur sont liées. Chaque page explorée est envoyée sur le site central de Google où elle va être indexée et contribuer à la construction d’un gigantesque index (termes – documents).
La recherche consiste, quant à elle, à rechercher dans cet index toutes les pages incluant les termes de la requête utilisateur, ce qui permet de retrouver en général un très grand nombre de résultats. L’avancée principale de Google est sa capacité à indexer des milliards de pages et à traiter en simultané des milliers de requêtes utilisateurs. Ceci est possible par le recours à des dizaines de gros clusters de serveurs gérant cette charge en parallèle (cela représente aujourd’hui plusieurs dizaines de milliers de serveurs). En ce qui concerne le classement des pages, Google intègre plusieurs critères de décision dont le plus important est le « PageRank » [Brin 1998] ou popularité d’une page. L’algorithme pageRank consiste à mesurer l’importance d’une page en fonction du nombre de liens externes qui mènent vers cette page. D’autres critères considèrent les relations de synonymies, l’importance des termes de la requête dans les pages sélectionnées et leurs fréquences [Andrieu 2011]. Google a réussi à avoir un bon compromis entre le nombre de documents indexés, la fraîcheur des index et le traitement des requêtes par seconde [Dean 2009]. En effet, la réponse à une requête ne dépasse pas aujourd’hui 0.5s avec des taux de mise à jour très importants (les pages les plus dynamiques selon le log du moteur d’index sont mises à jour quotidiennement et même plusieurs fois par jour alors qu’auparavant les mises à jour se faisaient mensuellement) [Dean 2009].
Google propose également des produits de recherche spécialisés tels que Google scholar pour la recherche scientifique, Google Maps pour la recherche géographique, Google Books pour l’exploration des livres, etc. Malgré l’investissement énorme rendu nécessaire pour mettre en place et maintenir l’infrastructure de dizaines de milliers de serveurs, Google offre cependant, des performances limitées. En effet, le principe d’exploration des robots ne garantit pas l’exhaustivité de l’indexation et des pans entiers de l’Internet ne sont pas indexés par Google. On peut citer notamment tout ce qui est qualifié de web caché (the hidden web) et de web profond [Bergman 2001] (the deep web), c’est-à-dire les informations présentes derrière des formulaires web ou bien qui nécessitent une identification préalable. L’autre limite porte sur la qualité de la RI proposée par Google. Google utilise une approche purement statistique applicable sur un corpus énorme et très hétérogène (taille, structure, langues, etc).
Enfin, pour des raisons économiques (les grands coûts dépensés par Google), il n’a pas de place pour un autre Google, ce qui rend la mise en place de nouveaux systèmes centralisés à l’échelle du web impossibles (même si on vise des sous ensembles restreints à une langue ou une spécialité, par exemple). Ceci laisse la place à d’autres approches basées sur une vision décentralisée moins coûteuse à mettre en place.
Avant de s’attaquer à la vision distribuée de recherche, nous proposons une revue de l’histoire de l’evolution de la RI. Dans ce qui suit, nous tenons à retracer les principaux événements qui ont impacté le monde de la RI et ses principales évolutions. Les événements concernent le côté matériel, le volume de données et les principales innovations.
|
Table des matières
Introduction Générale
1 De la Recherche d’Information centralisée à la Recherche d’Information à Large Échelle
1.1 Introduction
1.2 Les Systèmes de Recherche d’Information Centralisés
1.2.1 Revue de quelques modèles de Recherche d’Information
1.2.2 Google : une solution centralisée pour de très gros volumes
1.3 Evolution de la Recherche d’Information
1.4 Principe de Recherche d’Informations Distribuée
1.5 Les systèmes de Recherche d’Information en Pair-à-Pair RIP2P
1.5.1 Revue sur les systèmes P2P
1.5.2 La Recherche d’Information dans les systèmes P2P
1.5.3 P2P sémantique
1.6 Conclusion
2 Agrégation de résultats dans un système de recherche distribué à large échelle
2.1 Introduction
2.2 Agrégation : Origines et concepts
2.2.1 Agrégation vs Fusion
2.2.2 Fusion de données vs fusion de collections
2.3 Problème d’agrégation dans les systèmes à large échelle : cas des systèmes de RIP2P
2.3.1 Définition du problème d’agrégation
2.3.2 Propriétés requises d’un modèle d’agrégation en RIP2P
2.4 Catégorisation des principaux modèles d’agrégation
2.4.1 Modèles à base de scores
2.4.2 Modèle à base de rangs
2.4.3 Les Modèles à base d’apprentissage
2.4.4 Discussion
2.5 Conclusion
3 Modèle d’agrégation hybride à base de profils
3.1 Introduction
3.2 Architecture du modèle d’agrégation
3.3 Modèle de profils utilisateurs
3.3.1 Définition du profil utilisateur
3.3.2 Acquisition des profils
3.3.3 Représentation du profil
3.3.4 Intégration de profils utilisateurs dans un processus d’agrégation de résultats à large échelle
3.4 Agrégation hybride à base de profils
3.4.1 Score d’agrégation hybride
3.4.2 Algorithme d’agrégation à base de profils
3.4.3 Complexité algorithmique
3.4.4 Exemple illustratif
3.5 Conclusion
4 Démarche d’Evaluation
4.1 Introduction
4.2 Métriques d’évaluation pour les systèmes largement distribués
4.2.1 Mesures d’efficacité
4.2.2 Étude de la performance d’un système de RID
4.3 Baseline
4.4 Collections de test
4.4.1 Modèles de distribution
4.4.2 Modèles de réplication
4.5 Environnement
4.5.1 Choix de la plate-forme d’évaluation
4.5.2 Simulateur Peersim-Rare
4.5.3 Simulateur d’agrégation : PeerSim-RARE +
4.5.4 Scénarii de simulation
4.6 Conclusion
Conclusion
Télécharger le rapport complet
