Soutenance mémoire
Télécharger le fichier pdf d’un mémoire de fin d’études
Moteurs de recherche thématiques
Les moteurs de recherche thématiques, moteurs de recherche spécia-lisés (dans un domaine ou un thème), parfois nommés portails de re-cherche (verticaux) ou « vortails », existent depuis les débuts du Web. À titre d’exemple, le moteur de recherche Google proposait dès 1999 des moteurs de recherche thématiques sur des thèmes aussi divers que les systèmes d’exploitation (google.com/linux, google.com/mac, . . . ) ou les informations gouvernementales américaines (google.com/unclesam). En complément de ces exemples, plusieurs moteurs de recherche thématiques en langues française et anglaise sont présentés au Tableau 1.1.
De même, dans le milieu académique, les campagnes d’évaluation témoi-gnent d’un passé de recherche de plus de dix ans en recherche d’informa-tion spécialisée. La campagne d’évaluation CLEF (Conference and Labs of the Evaluation Forum 5) a ainsi proposé une tâche dédiée à la recherche d’information spécialisée (domain-specific IR) entre 2000 et 2009 (Kluck et Gey, 2001; Kluck, 2004). La campagne d’évaluation TREC (Text REtrieval Conference), bien que n’ayant pas proposé de tâche de recherche d’infor-mation spécialisée, a encapsulé un certain nombre de tâches sur des do-maines spécialisés tels que la chimie (TREC Chemistry IR, 2009-2011), la bio-informatique (TREC Genomics, 2003-2007), la santé (TREC Medical Re-cords, 2011-2012) ou la justice (TREC Legal, 2006-2012).
Exploration orientée
Comme nous l’avons vu au chapitre précédent, utiliser un moteur de recherche comme point d’entrée au Web offre plusieurs avantages :
– Simple : ne nécessite qu’un ordinateur personnel et un accès à Internet.
– Efficace : collecte rapide.
– Prétraité : documents indésirables (spam) préfiltrés.
– Couverture : index du Web.
En contrepartie, l’utilisation d’un moteur de recherche Web impose les limites suivantes :
– Éléments inconnus : critères de filtrage, critères de tri des résultats.
– Limites : nombre de résultats renvoyés, nombre de requêtes soumises par jour, langues disponibles.
– Maintien à long terme : fermeture possible des API d’accès aux mo-teurs de recherche 3.
– Expressivité : spécification du besoin basée uniquement sur des re-quêtes de type « mots-clés ». Le crawling orienté a un coût plus important et nécessite de répliquer les traitements réalisés par les moteurs de recherche Web (spam, qualité des pages, crawling distribué). Néanmoins, il permet un plus grand contrôle du processus de collecte.
Exploration
Les crawlers font partie intégrante des moteurs de recherche Web et sont dédiés à la collecte et à l’indexation des documents Web. Ils sont également utilisés dans un but d’archivage 7, d’extraction d’information (pour trouver des adresses e-mail ou des pages de produits par exemple) et de constitu-tion de corpus à la demande (Baroni et Ueyama, 2006), entre autres.
Un processus de crawl (Figure 2.3, adaptée de (Castillo, 2005)) démarre à partir d’URL amorces (seed URL). Les pages Web correspondant à ces URL sont téléchargées et les hyperliens présents sur ces dernières sont extraits et ajoutés à un ensemble d’URL à visiter, également appelé la frontière de crawl. Le nombre d’URL peuplant la frontière de crawl augmentant très ra-pidement, un critère permettant de prioriser le téléchargement de certaines pages est généralement appliqué. Tour à tour, les URL les mieux classées parmi la frontière de crawl sont téléchargées et de nouveaux liens en sont extraits. Ce processus, en apparence simple, amène néanmoins un certain nombre de défis techniques : comment ordonner la frontière de crawl, com-ment maximiser l’utilisation de la bande passante, comment esquiver les pièges tendus aux crawlers (pages Web de spam, boucles de liens infinis), ou encore comment éviter de surcharger les serveurs Web. Castillo (2005) a défini le comportement d’un crawler Web comme une combinaison de quatre principes :
– Un principe de politesse qui définit comment éviter de surcharger les serveurs Web.
– Un principe de parallélisation qui définit comment coordonner les robots d’indexation distribués.
– Un principe de sélection qui définit quelles pages télécharger.
– Un principe de revisite qui définit quand vérifier si les pages ont été mises à jour.
Le principe de politesse est un composant obligatoire d’un crawler qui spécifie de quelle manière il doit se comporter face à un serveur Web. Des règles explicites (robots.txt) et des règles implicites régulent la fréquence à laquelle il est possible de télécharger les documents issus d’un même ser-veur. Le principe de parallélisation a pour objectif de maximiser la vitesse de téléchargement tout en minimisant le surcoût dû à la parallélisation du téléchargement et en évitant de télécharger la même page plusieurs fois. Cho et Garcia-Molina (2002) mentionnent deux approches : l’approche dy-namique qui consiste à allouer de nouvelles URL aux crawlers dynamique-ment, et l’approche statique qui consiste à définir comment répartir les URL avant le crawl. Le principe de revisite est discuté en section 2.5.
Nous allons nous intéresser plus particulièrement aux crawlers orientés visant à télécharger un nombre restreint de pages répondant à un besoin en un minimum de temps. Dans ce cadre, le problème d’ordonnancement de la frontière de crawl est certainement le plus important (principe de sé-lection). Contrairement aux crawlers généralistes, qui utilisent des mesures de l’importance des pages telles que le degré entrant (Cho et coll., 1998), le PageRank (Cho et coll., 1998), la taille du site Internet (Baeza-Yates et coll., 2005) ou l’impact sur le moteur de recherche (Pandey et Olston, 2008), les crawlers orientés font au contraire usage de critères spécifiques au besoin, pour sélectionner les URL à télécharger en priorité.
Revisite
Afin de maintenir leur index à jour, les moteurs de recherche doivent surveiller continuellement si les documents qu’ils ont collectés ont été mis à jour. C’est ce que l’on nomme le re-crawling ou la revisite. Plusieurs tra-vaux se sont intéressés à cette problématique dans le cadre de moteurs de recherche généralistes et peuvent être directement appliqués aux moteurs de recherche spécialisés, c’est pourquoi nous ne ferons qu’un rapide sur-vol des travaux existant à ce sujet. L’un des objectifs du principe de re-crawling est de maximiser la fraî-cheur de l’index en estimant la fréquence de changement des pages de l’index du moteur de recherche pour planifier une nouvelle visite de ces dernières au moment opportun. Le re-crawling dépend de deux facteurs : un estimateur de la fréquence de changement des pages et une stratégie de synchronisation (ou téléchargement) des pages.
De nombreuses expériences (Coffman et coll., 1997; Brewington et Cy-benko, 2000; Cho et Garcia-Molina, 2003b) ont montré qu’une loi de Pois-son modélisait correctement les mises à jour aléatoires et indépendantes des pages Web. Cet estimateur peut être basé sur plusieurs mesures de fraîcheur (Cho et Garcia-Molina, 2003a) : une mesure binaire (freshness) où la fraîcheur d’une page vaut 1 si elle est fraîche et 0 sinon. Et une mesure continue (âge) où la fraîcheur d’une page est négativement proportionnelle à la dernière date de visite. En marge de ces mesures, Pandey et Olston (2008) ont proposé un modèle directement fondé sur les modifications des pages et non sur l’âge de la page (information longevity).
Cho et Garcia-Molina (2003a) ont également proposé plusieurs modèles pour déterminer la stratégie de synchronisation optimale. Un premier mo-dèle opère une mise à jour de toutes les pages avec une même fréquence alors qu’un second modèle opère cette mise à jour avec une fréquence de changement différente pour chaque page. La première stratégie a éton-namment été montrée comme supérieure. De plus, Cho et Garcia-Molina ont montré qu’il est plus avantageux d’exclure les pages qui sont mises à jour trop souvent afin de libérer de la bande passante pour mettre à jour plus de pages. Edwards et coll. (2001) ont, quant à eux, proposé de clas-ser les pages en groupe de pages de fréquence de changement similaire et d’utiliser cette information pour améliorer la stratégie de re-crawling.
Synthèse
Dans ce chapitre, nous nous sommes intéressés à deux approches de constitution d’index spécialisés : l’utilisation d’un moteur de recherche Web et le crawling orienté.
La première approche a été relativement peu étudiée dans un but de création de moteurs de recherche spécialisés. Les requêtes formulées aux moteurs de recherche Web sont typiquement des combinaisons de termes du domaine fournis par un utilisateur ou extraits automatiquement à par-tir de petites collections documentaires existantes. Ces travaux se fondent sur l’hypothèse que la combinaison de mots-clés d’un domaine permet de désambiguïser le thème de la requête et d’obtenir une majorité de docu-ments du thème. Toutefois, la validité de cette hypothèse n’a jamais été confirmée rigoureusement et dépend de plusieurs paramètres tels que le nombre de termes utilisés, le caractère discriminant des termes choisis, ou encore l’ambiguïté de la terminologie du domaine. C’est pourquoi une étape de validation manuelle des documents est généralement appliquée.
Les travaux en crawling orienté ont, eux, été beaucoup plus nombreux. Nous constatons que les travaux récents sur ce domaine font usage de mé-thodes d’apprentissage pour mieux ordonner la frontière de crawl ou tenter d’augmenter le rappel du crawler. Les méthodes utilisées dans ce domaine sont par ailleurs analogues à celles appliquées en recherche d’information : la requête utilisateur est remplacée par un thème, mais l’objectif du craw-ler orienté est bien de trouver l’ensemble de documents les plus pertinents possible pour le thème formulé.
Enfin, nous avons proposé une vue d’ensemble des méthodes de revisite. Bien que ces méthodes ne soient pas spécifiques aux moteurs de recherche spécialisés, la revisite est un élément clé de ces moteurs qui doivent of-frir une fraîcheur exemplaire pour concurrencer les moteurs de recherche généralistes.
Sélection des termes amorces
Nous nous intéressons à présent à la sélection des termes amorces qui vont servir à créer les requêtes spécialisées. Nous nous appuyons sur les descriptions des sites internet entrées manuellement par les éditeurs de l’OpenDirectory. Pour chaque catégorie, nous agrégeons les descriptions des sites qui la composent en un seul texte afin de générer une description de catégorie (ou topic description (Srinivasan et coll., 2005)). Nous modélisons ensuite chaqu description de catégorie en un sac de mots et appliquons une mesure de Spécificité (TermHood (Kageura et Umino, 1996)), en l’occurrence, le tfidf (Salton et Buckley, 1988), pour trouver les termes les plus importants pour cette catégorie. La mesure du tfidf est elle-même composée de deux mesures : le tf, pour term frequency, qui mesure l’importance locale d’un terme dans un document (ici, une catégorie), et le df, pour document frequency, qui mesure l’importance globale d’un terme dans une collection (ici, l’ensemble des catégories).
Nous utilisons la variante ntc (Manning et coll., 2008, chap. 6, p. 128) du tfidf qui est définie comme suit : tfidft,d = tft,d log idft idft = N dft. avec tft,d le nombre d’occurrences du terme t dans le document d, dft le nombre de documents où apparaît le terme t et N le nombre total de documents dans la collection.
Nous présentons au Tableau 3.3 les 10 meilleurs termes obtenus via cette mesure pour quelques catégories choisies manuellement.
Performances en fonction de la taille des tuples
Nous étudions tout d’abord l’influence de la taille des tuples sur la qualité des documents collectés. Pour ce faire, nous réalisons, pour chaque catégorie, toutes les combinaisons possibles à partir des 10 termes ayant le plus fort tfidf. Puis nous mesurons la précision (à 10) et le rappel des documents renvoyés pour chaque requête. Nous considérons qu’un document est pertinent si sa catégorie dans l’OpenDirectory est la même que celle qui a servi à générer les termes de la requête. Nous calculons enfin une micro moyenne de ces résultats.
Nous présentons au Tableau 3.5 les micro moyennes des précisions et rappels obtenues pour l’ensemble des requêtes. Nous observons clairement un écart important entre les requêtes composées d’un seul terme, trop ambiguës, et les requêtes composées de 2 termes et plus. Nous constatons que la précision augmente avec le nombre de termes par requête : l’ajout de termes contraint l’ensemble de documents en sortie et valide le thème des documents. Cependant, le gain obtenu en augmentant la taille des requêtes décroît rapidement (+0, 001 en précision entre des requêtes de 3 et 4 termes). Ce dernier résultat semble indiquer que l’augmentation de la taille des requêtes ne permet pas d’améliorer la précision substantiellement au-delà de quelques termes. Force est de constater qu’une valeur de précision de 0, 46 est relativement faible. Nous pensons que les performances que nous obtenons représentent une borne inférieure aux performances que nous pouvons obteniravec un moteur de recherche Web. En effet, d’une part le modèle vectoriel tfidf employé par Lucene est inférieur à l’état de l’art actuel (He et Ounis, 2005). D’autre part, les moteurs de recherche Web font usages de nombreuses données (traces des utilisateurs par exemple) qui leurs permettent d’améliorer leur fonction d’ordonnancement. En l’état, ce résultat laisse une marge d’amélioration intéressante. L’application d’un filtre a posteriori, manuelle ou automatique, semble inévitable.
Les mesures que nous avons présentées ne sont pas suffisantes pour sélectionner une taille de requête optimale. Ces résultats ne tiennent pas compte du recouvrement entre les différentes requêtes d’une même catégorie.
En effet, nous nous attendons à un recouvrement plus fort entre requêtes de grande taille (4 termes par exemple) que pour des requêtes de taille inférieure. Nous étudions dès lors la précision et le rappel, non plus pour chaque requête, mais pour l’ensemble des requêtes d’une catégorie.
Notons qu’il ne s’agit pas simplement de la macro moyenne des mesures mentionnées précédemment, mais de mesures différentes en raison du recouvrement entre les documents ramenés par les requêtes d’une même catégorie. Comme précédemment, nous partons des 10 meilleurs termes pour une catégorie et générons toutes les combinaisons de ces termes de manière exhaustive. Puis, nous évaluons la précision et le rappel de l’union des documents ramenés par toutes les requêtes d’une catégorie.
Performances en fonction des catégories
Nous profitons de ce corpus pour évaluer la difficulté de collecte en fonction des catégories. Nous mesurons la précision des collections créées pour chaque catégorie.
Le résultat, présenté à la Figure 3.3, ne fait pas apparaître de groupes de catégories plus simples ou plus difficiles à construire. De même, la Figure 3.4 montre la macro moyenne par catégorie de premier niveau de la précision des catégories de second niveau. Nous constatons que la précision sur ces catégories peut varier de plus ou moins 0, 2. Toutefois, les catégories de second niveau à l’intérieur de ces catégories ont une précision qui varie également beaucoup (symbolisée par les barres d’erreurs).
Une étude plus approfondie des résultats montre que les mauvaises performances obtenues sur certaines de ces catégories peuvent être dues à plusieurs facteurs, tels que :
1. Des mot-clés mal choisis (tfidf ) .
2. Des catégories similaires existantes (Arts/Video, Arts/Movies/ Filmmaking et Arts/Movies/Education, par exemple).
Bilan
Dans ce chapitre, nous nous sommes intéressé à une approche standard de recherche orientée. Dans ce cadre, nous avons proposé une méthode d’évaluation rigoureuse, claire et facilement reproductible pour mesurer les performances de ces systèmes de collecte. Cette méthode se fonde sur l’indexation d’un sous-ensemble annoté du Web (l’OpenDirectory) dans un moteur de recherche (Lucene). Nous avons ensuite appliqué notre méthode pour évaluer les performances d’une approche simple pour la collecte de documents thématiques via un moteur de recherche : l’approche par combinaison de termes. Nous avons observé des résultats variables groupes thématiques de catégories. Nous avons constaté que la création de triplets de termes offre la meilleure F1-mesure sur nos données. Cependant, même la précision maximale, obtenue pour des requêtes composées de quatre termes, reste moyenne (0, 373) et le gain pouvant être obtenu en augmentant la taille des requêtes semble limité.
Ces résultats laissent la porte ouverte à d’intéressantes améliorations au niveau de la formulation du besoin thématique (termes composant la requête) mais également du filtrage des documents rapatriés.
Pertinence d’un terme pour un thème
Nous formulons notre problématique comme suit : considérant un lexique thématique LT composé de N termes, LT = (t1, t2, . . . , tN), nous voulons calculer un vecteur de poids wLT = (w1,w2, . . . ,wN) où chaque poids wi mesure la pertinence du terme ti pour le thème T.
Recueil de connaissances exogènes
Nous collectons, pour chaque terme ti, un corpus Ci correspondant aux Mmeilleurs résultats renvoyés par un moteur de recherche pour la requête ne contenant que ce mot (“< ti >”). La valeur deMdoit être suffisamment grande pour réduire le biais du moteur de recherche, tout en restant raisonnable afin d’éviter un temps de traitement trop long.
Nous considérons deux unités d’information : la page Web et le snippet. Prendre en compte les pages Web entières permet de bénéficier d’un contexte plus large et plus riche. Toutefois, télécharger les documents renvoyés par le moteur de recherche rallonge considérablement le temps de calcul et nécessite une méthode de nettoyage des pages Web (suppression des menus, publicités et balises HTML). D’autre part, le caractère local des snippets peut permettre de réduire le bruit pouvant apparaître dans les pages Web.
Critère de cohésion thématique
Considérant un ensemble de documents (virtuellement infini) contenant le terme ti, nous faisons l’hypothèse que la pertinence du terme ti pour le thème T est fonction de la proportion de documents appartenant au thème T. Ainsi, le terme « mercury », par exemple, qui peut faire référence à un astre, à un dieu de la mythologie romaine, à un élément chimique ou à un célèbre chanteur, est relativement ambigu et devrait être discriminé.
Au contraire, le terme « telescope », peu ambigu et menant très majoritairement à des documents traitant d’astronomie devrait obtenir un score important pour ce thème.
Cependant, nous ne disposons pas d’information quant au caractère thématique des documents. Une solution serait d’utiliser un catégoriseur thématique, à l’instar de Song et coll. (2007), mais là encore nous ne disposons pas d’un tel outil. Nous proposons plutôt d’estimer le caractère thématique des documents en fonction de l’apparition des termes du lexique dans le document. Par conséquent, nous proposons une première définition de notre critère comme suit : le poids wi d’un terme ti est égal au nombre de termes du lexique (ti exclu) cooccurrant avec ti dans le corpus Ci. Plus formellement, le poids wi d’un terme ti est défini par : wi = X tj2LyT ntj,Ci (4.1).
Évaluation du critère pour la sélection de requêtes
Après nous être intéressés à l’influence des paramètres du critère sur des lexiques non bruités, nous souhaitons évaluer l’apport du critère pour la sélection de requêtes. Ainsi, nous appliquons notre mesure pour réordonner les termes amorces précédemment extraits des descriptions de catégories de l’OpenDirectory (déjà utilisés § 3.2, p. 40). En accord avec nos dernières conclusions, nous sélectionnons les 200 termes ayant le meilleur tfidf pour les repondérer ensuite à l’aide de notre critère. Pour chaque requête, nous téléchargeons les 200 premiers snippets renvoyés par le moteur de recherche. Nous nous appuyons sur deux moteurs de recherche : le moteur de recherche Web Blekko et le moteur de recherche que nous utilisons pour la recherche orientée Lucene. Dans les deux cas, nous utilisons des snippets de longueur similaires (250 caractères). Nous faisons l’hypothèse qu’utiliser le même moteur de recherche pour la prédiction de performances et la collecte de documents spécialisés devrait amener de meilleures performances. Malgré cela, il nous semble intéressant d’évaluer le biais dû à l’utilisation d’un autre moteur de recherche, qui pourrait être installé localement et offrir ainsi un temps de traitement plus faible.
Tout d’abord, nous évaluons la validité de notre critère de cohésion thématique pour la prédiction de performances d’un unique terme. Puis, nous poursuivons cette évaluation en appliquant notre critère pour la prédiction de performances d’une requête. Nous envisageons deux méthodes : (i) sélectionner les 10 meilleurs termes amorces à l’aide de notre critère et réaliser toutes les combinaisons de ces termes ; (ii) combiner les scores prédits pour chaque terme afin de fournir une prédiction de performances pour chaque requête
|
Table des matières
1 moteurs de recherche web
1.1 Web
1.2 Recherche d’information
1.3 Moteurs de recherche verticaux
1.4 Moteurs de recherche thématiques
2 collecte thématique de documents
2.1 Présentation
2.2 Recherche orientée
2.3 Exploration orientée
2.3.1 Exploration
2.3.2 Exploration orientée
2.4 Revisite
2.5 Synthèse
3 construction de bases documentaires via un moteur de recherche
3.1 Données
3.2 Sélection des termes amorces
3.3 Protocole expérimental
3.4 Évaluations
3.4.1 Performances en fonction de la taille des tuples
3.4.2 Performances en fonction des catégories
3.5 Bilan
4 prédiction des performances des requêtes thématiques sur le web
4.1 Travaux liés
4.2 Pertinence d’un terme pour un thème
4.2.1 Recueil de connaissances exogènes
4.2.2 Critère de cohésion thématique
4.3 Évaluations
4.3.1 Évaluation de l’influence des paramètres du critère .
4.3.2 Évaluation du critère pour la sélection de requêtes .
4.4 Bilan
5 grawltcq : graphes hétérogènes et marches aléatoires pour la collecte spécialisée
5.1 Travaux liés
5.2 Modèle de graphe
5.3 Marches aléatoires
5.4 Évaluation brute sur l’OpenDirectory
5.4.1 Évaluation de l’ordre des documents
5.4.2 Évaluation de la sélection de termes amorces
5.5 Évaluation sur un corpus de l’Agence France Presse
5.6 Bilan
6 exploration orientée du web
6.1 Babouk : exploration orientée du Web
6.1.1 Implémentation pour un passage à l’échelle
6.1.2 Synthèse
6.2 Apprendre à ordonner la frontière de crawl
6.2.1 Apprentissage de fonctions d’ordonnancement à partir de données de crawl annotées
6.2.2 Évaluations
6.3 Bilan
Conclusion
bibliographie
Télécharger le rapport complet
