Recherche d'Information Traitement Automatique des Langues Xavier Tannier [email protected] Recherche d'Information Indexation (modèle de document) Collections dynamiques vs. statiques Modèle de recherche Évaluation Requête Traitement de l'information sur le Web Recherche d'Information Xavier Tannier 2 Diversité des besoins d'information (1/2) • Recherche d’un élément connu – L’utilisateur sait exactement quels éléments il recherche. Il sait reconnaître les éléments désirés s’il les voit. – Exemple : recherche d'une citation bibliographique précise. Bases de données (SQL, XQuery, etc.) • Recherche d’une information générale – L’utilisateur recherche une information sur un sujet en général. Il existe de nombreuses façons de décrire le sujet. – Il est possible que l’information pertinente ne soit pas reconnue – Cette information peut ne satisfaire l’utilisateur que de façon partielle. – Exemple : Les réformes de la recherche en France Recherche d’information « traditionnelle » Traitement Automatique des Langues Recherche d'Information Xavier Tannier 3 Diversité des besoins d'information (2/2) • Recherche d’une information précise – L’utilisateur recherche une information spécifique mais ignore sous quelle forme elle se présente. – Réponse partielle impossible – Exemple : À quelle date le président Kennedy a-t-il été assassiné ? Extraction d'information et systèmes de question-réponse • Exploration – Le but n’est pas de répondre à une question en particulier, mais de parcourir l’ensemble des données pour découvrir quels types d’informations concernant un sujet ou un domaine sont présents. Navigation Traitement Automatique des Langues Recherche d'Information Xavier Tannier 4 Grandes évolutions de la RI • Précédemment : – Bases documentaires structurés et de petite taille – Accès par des métadonnées et rarement par le texte intégral – Utilisation de langages documentaires (contraints) par les spécialistes • Aujourd'hui – Documents multimédia sous forme électronique – Nombreux formats de représentation (texte brut, HTML, XML, PDF, RTF, formats propriétaires...) – De plus en plus de données non structurées – Une masse d'information gigantesque (Web...) Traitement Automatique des Langues Recherche d'Information Xavier Tannier 5 1. Crawling et Indexation "Prétraitement" L'exploration des sites (crawling) • Des robots (ou crawlers, spiders, ...) "parcourent" les sites et indexent leur contenu – Ils partent d'une liste d'adresses et suivent les liens dans les pages – Une page peut demander au robot de ne pas l'indexer ou de ne pas suivre les liens (robots.txt, lien "nofollow")… • La fréquence de passage dépend des moteurs et des pages – Les ressources nécessaires sont énormes – Les robots passent plus souvent dans les pages souvent modifiées • Le crawler est un acteur primordial pour l'efficacité d'un moteur de recherche Traitement Automatique des Langues Recherche d'Information Xavier Tannier 7 Indexation : pourquoi ? • Le parcours complet de l'ensemble des documents avec les termes d'une requête est impossible : trop de documents et temps de réponse prohibitif. • On passe par un traitement préalable : l'indexation • Le but de l'indexation automatique : "transformer des documents en substituts capables de représenter le contenu de ces documents" (Salton et McGill, 1983) • Les difficultés de l'indexation sont pour beaucoup celles inhérentes à la langue des documents. • Les index peuvent prendre plusieurs formes : mots simples, termes complexes, syntagmes, entrées de thésaurus... Traitement Automatique des Langues Recherche d'Information Xavier Tannier 8 Indexation : le fichier inverse Traitement de l'information sur le Web Recherche d'Information Xavier Tannier 9 Indexation : le fichier inverse • Notion "classique" de l'index • Un fichier inverse associe des index aux documents qui les contiennent : – – – – – – – – a à abaissa abaissable abandon abandonna abasourdi … ▸ ▸ ▸ ▸ ▸ ▸ ▸ d1, d2, d3, d4, d5... d1, d2, d3, d4, d5... d3, d4... d5 d1, d5 d2 d1 Traitement Automatique des Langues Recherche d'Information Xavier Tannier 10 Indexation libre et contrôlée • Indexation libre : – Mots, termes des documents • Indexation contrôlée – Listes de termes prédéfinie – Vocabulaire contrôlé (évite polysémie, synonymie et problèmes de granularité) – Thésaurus exemple : thésaurus UMLS Traitement Automatique des Langues Recherche d'Information Xavier Tannier 11 Chaîne d'indexation Segmentation Documents à indexer • Généralement en mots • Termes complexes Normalisation • Lemmatisation • Stemming •… Fichiers d'indexation Indexation • Pondération • Positions • Casse, police, … Traitement de l'information sur le Web Recherche d'Information Xavier Tannier 12 Constitution des fichiers inverses Normalisation • Lemmatisation – Du mot à son lemme (entrée du dictionnaire) • Racinisation (stemming) – Du mot à sa racine • Non conservation de certaines formes – Liste de mots vides (stop list) – Environ 30 mots représentent environ 30 % des occurrences de termes dans les textes écrits – Éliminer les 150 termes les plus fréquents réduit l'espace d'environ 25 % Quel impact pour la recherche d'information ? Traitement Automatique des Langues Recherche d'Information Xavier Tannier Pondération • Dans une requête comme dans un document, les termes n'ont pas tous la même importance • Intuition #1 : plus un document contient d'occurrences d'un terme, plus il est "à propos" de ce terme (plus il sera pertinent par rapport à une requête contenant ce terme) • C'est le modèle "sac de mots" – On raisonne en termes de fréquence et on oublie l'ordre des mots – Pour conserver l'ordre des mots, il faut mémoriser la position de chaque occurrence dans les index • Les longs documents sont favorisés car ils sont susceptibles de contenir davantage d'occurrences Traitement Automatique des Langues Recherche d'Information Xavier Tannier 15 Pondération : le td.idf • Intuition #2 : des termes très fréquents dans tous les documents ne sont pas si importants (ils sont moins discriminants) • On compense donc la fréquence des termes dans les documents (tf) en prenant en compte leur fréquence dans la collection (df) 1 dfi – Mesure simple : wi , d tfi , d – En pratique : wi , d tfi , d log n dfi • Le poids d'un terme dans un document D augmente avec sa fréquence dans D et avec sa rareté dans la collection. Traitement Automatique des Langues Recherche d'Information Xavier Tannier 16 Pondération : le td.idf tf seul tf.idf Sur le Web • Dépend du type de document (texte brut, HTML, PDF, fichiers Office, etc.) • Conversion des documents en hits comprenant notamment : – Le mot et la position dans le document – La taille relative de la fonte, la casse du mot • Les robots n'indexent que les pages qu'on leur demande et les liens qui en partent, et pas le "Web profond" : – Les sites "non-liés" (Web opaque) – Le contenu à accès limité – La plupart des pages dynamiques La majeure partie du Web n'est pas indexée (Web profond = 500 fois le Web de surface selon BrightPlanet 2001) Protocole sitemap de Google Traitement Automatique des Langues Recherche d'Information Xavier Tannier 18 Sur le Web : le PageRank • Mesure de l'importance relative objective d'une page Web : – Indice de popularité ; notion de confiance collaborative – Utilisation de la structure des liens du Web : • Les liens sortants (forward links) • Les liens entrants (backlinks) • Justification intuitive : – Le nombre de liens entrants d'une page est révélateur d'une certaine importance (analogie : spéculation des futurs Prix Nobel par des comptages de citations) – Une page ayant un lien entrant provenant d'un site lui-même important (journal en ligne, grand site, portail, etc.) est plus importante qu'une page ayant des liens entrant provenant de sites peu importants : notion récursive de l'importance d'une page • On voit le Web comme un graphe Traitement Automatique des Langues Recherche d'Information Xavier Tannier 19 PageRank • La probabilité pour qu'un utilisateur cliquant au hasard arrive sur une page. • Obtenir un fort PageRank pour une page qui a de nombreux liens entrants et/ou des liens entrants provenant de pages elles-mêmes importantes : 1 PR (v ) PR (u) d (1 d ) N v Bu C ( v ) – Bu : ensemble des pages ayant un lien entrant sur la page u – C(v) : nombre de liens sortant de la page v (chaque page diffuse son vote de façon égale sur tous ses liens sortants) – d : facteur d'amortissement ; d vaut 0.85, donc une page n'ayant aucun lien entrant aura un PageRank de 0.15 – Le PR moyen est 1 (avec 1/N, la somme des PR est 1) Traitement Automatique des Langues Recherche d'Information Xavier Tannier 20 Calcul du PageRank • Le PageRank d'une page dépend des PageRanks des pages qui pointent vers elle : – Calcul des PageRanks sans connaître la valeur finale de tous les PageRanks impliqués – Itérations qui approchent des valeurs finales jusqu'à convergence – La valeur initiale n'affecte pas les valeurs finales mais le nombre d'itérations pour atteindre la convergence (ex : prendre des valeurs initiales correspondant à la fréquentation des pages) – Le coût pour le calcul des PageRanks est très faible relativement au temps de construction d'un index complet Traitement Automatique des Langues Recherche d'Information Xavier Tannier 21 Calcul du PageRank Traitement de l'information sur le Web Recherche d'Information Xavier Tannier 22 Calcul du PageRank A B C Valeurs relatives des PageRanks des pages ? D Traitement de l'information sur le Web Recherche d'Information Xavier Tannier 23 Calcul du PageRank A B 1,49 C PR moyen = 1 1,58 0,78 D • (20 itérations sont nécessaires pour la convergence) • La page D a une valeur minimale du PageRank (aucun lien entrant) • La page C a de nombreux liens entrants • La page A bénéficie du lien entrant provenant de la page C 0,15 Traitement de l'information sur le Web Recherche d'Information Xavier Tannier 24 PageRank : cas simple Contact 0,41 0,39 Home Produit 0,92 0,85 0,41 0,39 Liens 0,41 0,39 Lien externe E 0,19 Lien externe G 0,19 Lien externe F 0,19 Lien externe A 0,19 0,22 Lien externe B 0,22 0,19 Lien externe C 0,22 0,19 Lien externe D 0,22 0,19 Lien externe H 0,19 Traitement de l'information sur le Web Recherche d'Information Xavier Tannier 25 PageRank : cas simple • Rétroaction des valeurs des PageRanks pour la page Home • Plus le nombre de liens sortant de la page Links est important, plus le partage du PageRank est diffus • Plus le nombre de pages augmente, plus des pages sans nouveaux liens entrant perdent de l'importance • Avoir un lien vers une page importante n'augmente pas le PR (!) Traitement Automatique des Langues Recherche d'Information Xavier Tannier 26 PageRank : la tentation du spam Page A 331,0 Page B Spam 1 Spam 2 281,6 0,39 0,39 …………………… Spam 1000 0,39 • Le nombre de pages d'un site n'augmente pas le PR moyen • Une certaine organisation hiérarchique d'un site peut fortement concentrer le PR sur la page principale • Maintenant décelable par les robots (ex : Googlebot) qui pénalisent le site Traitement Automatique des Langues Recherche d'Information Xavier Tannier 27 2. Modèles de recherche "en ligne" Langages de requête • Tous très similaires : – Un langage "de base" avec mots-clés, guillemets, "+" et "-" : • "+" : mot-clé important et graphie exacte (accents, flexion, ...) • "-" : mot qui invalide un document ("java -langage -informatique") – Une recherche avancée : • • • • • • • • filetype:pdf allinurl: britney allintitle: brad site:fr.wikipedia.org define: ordinateur Jules OR Jim Jazz 1920..1930 135 * 23 • 125 euros en monnaie de la République Tchèque (Google) Traitement Automatique des Langues Recherche d'Information Xavier Tannier 29 Modèles de recherche : les trois courants • Modèles fondés sur la théorie des ensembles ► Modèle booléen • Modèles algébriques ► Modèle vectoriel • Modèles probabilistes ► Modélisation de la notion de "pertinence" • Courants fondés à l'aube de la discipline (années 60, 70) • Passage à l'échelle : des bases documentaires "jouets" au téraoctet de TREC et au Web Traitement Automatique des Langues Recherche d'Information Xavier Tannier 30 Modèle booléen • Le premier et le plus simple des modèles • Basé sur la théorie des ensembles et l'algèbre de Boole • Les termes de la requête sont soit présents soit absents – Poids binaire des termes, 0 ou 1 • Un document est soit pertinent soit non pertinent – Pertinence binaire, et jamais partielle (modèle exact) • La requête s'exprime avec des opérateurs logiques – AND, OR, NOT – (cyclisme OR natation) AND NOT dopage – le document est pertinent si et seulement si son contenu respecte la formule logique demandée Traitement Automatique des Langues Recherche d'Information Xavier Tannier 31 Modèle booléen : exemple Requête Q : (cyclisme OR natation) AND NOT dopage Le document contient cyclisme natation cyclisme OR natation dopage NOT dopage Pertinence du document 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 0 Traitement de l'information sur le Web Recherche d'Information Xavier Tannier 32 Modèle booléen : avantages et inconvénients • Avantages : – Le modèle est transparent et simple à comprendre pour l'utilisateur : • Pas de paramètres "cachés" • Raison de sélection d'un document claire : il répond à une formule logique – Adapté pour les spécialistes (vocabulaire contraint) • Inconvénients : – Il est difficile d'exprimer des requêtes longues sous forme booléenne – Le critère binaire peu efficace • Il est admis que la pondération des termes améliore les résultats • cf. modèle booléen étendu – Il est impossible d'ordonner les résultats • Tous les documents retournés sont sur le même plan • L'utilisateur préfère un classement lorsque la liste est grande Traitement Automatique des Langues Recherche d'Information Xavier Tannier 33 Modèle vectoriel • Modèle statistique : – Aspect quantitatif des termes et des documents – Degré de similarité entre une requête et un document Liste ordonnée de résultats selon cette similarité • Mesure de similarité : Plus deux représentations contiennent les mêmes éléments, plus la probabilité qu’elles représentent la même information est élevée. • Documents et requête sont représentés par un vecteur – Les coordonnées du vecteur sont exprimées dans un espace euclidien à n dimensions (n : nombre de termes) – La longueur du vecteur (i.e. de sa projection sur chacun des axes/termes) est proportionnelle au poids des termes. – La pertinence du document correspond au degré de similarité entre le vecteur de la requête et celui du document Traitement Automatique des Langues Recherche d'Information Xavier Tannier 34 Modèle vectoriel t3 Requête Q : t1 t2 t3 Document D : 0.80 D Q … t1 … t3 … Poids wD,t1 = 0.45 t1 0.45 Poids wD,t3 = 0.80 t2 Traitement de l'information sur le Web Recherche d'Information Xavier Tannier 35 Modèle vectoriel : mesures de similarité • Mesure de l'angle entre les vecteurs de Q et de D – Produit scalaire n sim(Q, D ) Q D wiQ wiD i 1 n – Cosinus sim(Q, D ) Q D Q D wiQ wiD i 1 2 wiQ 2 wiD – Distance euclidienne, mesures de Jaccard et Dice... • Normalisation telle que la norme du vecteur soit unitaire – Permet de gommer les différences de taille des documents • Contribution d'un terme isolé : – S'il est présent dans le document et la requête, il augmente le score – S'il est présent dans un des deux seulement, il diminue le score Traitement Automatique des Langues Recherche d'Information Xavier Tannier 36 Modèle vectoriel : avantages et inconvénients • Avantages : – – – – Le langage de requête est plus simple (liste de mot-clés) Les performances sont meilleures grâce à la pondération des termes Le renvoi de documents à pertinence partielle est possible La fonction d'appariement permet de trier les documents • Inconvénients : – Le modèle considère que tous les termes sont indépendants (inconvénient théorique) – Le langage de requête est moins expressif – L'utilisateur voit moins pourquoi un document lui est renvoyé Le modèle vectoriel est le plus populaire en RI Traitement Automatique des Langues Recherche d'Information Xavier Tannier 37 Modèle probabiliste • Estimation de la probabilité de pertinence d'un document par rapport à une requête • Probability Ranking Principle (Robertson 77) variables indépendantes, • R : D est pertinent pour Q deux ensembles de documents séparés • ¬R : D n'est pas pertinent pour Q • Le but : estimer – P(R/D ) : probabilité pour le document D de faire partie des documents pertinents pour Q – P(¬R/D ) P( R / D ) P( R / D ) si 1 ou si log P( R / D ) P( R / D ) 0 alors D est pertinent Traitement Automatique des Langues Recherche d'Information Xavier Tannier 38 Modèle probabiliste • Rappel du théorème de Bayes : P( A / B ) P( B / A) P( A) P( B ) • On ne sait pas calculer P(R/D), mais on peut calculer P(D /R) Probabilité d'obtenir D en connaissant les pertinents P( R / D ) Probabilité d'obtenir un document pertinent en piochant au hasard P( D / R ) P( R ) P( D ) Probabilité de piocher D au hasard Traitement Automatique des Langues Recherche d'Information Xavier Tannier 39 Modèle probabiliste • En utilisant l'hypothèse d'indépendance des termes : n P( D / R ) P(ti D / R) i 1 • Pour estimer les probabilités sur les termes, on peut utiliser des requêtes déjà résolues (apprentissage) puis des pondérations • Exemple (système Okapi) : – le tf.idf – la longueur du document – la longueur moyenne des documents Traitement Automatique des Langues Recherche d'Information Xavier Tannier 40 Et la recherche multimédia ? • Texte et/ou image et/ou audio et/ou vidéo... • Des collections très volumineuses ! • Utilisation : – des métadonnées – du texte "environnant" les images (légende, point de référence...) – Finalement peu des caractéristiques propres des documents autres que le texte : • Analyse d'image • Speech-to-text • ... Traitement Automatique des Langues Recherche d'Information Xavier Tannier 41 2. Évaluation Qu'évalue-t-on ? • Vitesse, espace disque, mémoire, certes… • …Mais surtout, la pertinence des réponses ! • La pertinence est jugée par un être humain (subjectif et versatile, souvenez-vous…) • On évalue donc en général les documents renvoyés : – – – – Sans définition réellement objective de la pertinence Indépendamment les uns des autres De façon binaire En estimant l'accord inter-annotateurs Traitement Automatique des Langues Recherche d'Information Xavier Tannier 43 Évaluation : précision et rappel Documents renvoyés ET pertinents Documents pertinents P bruit Retour du système S silence Précision Rappel P S S P S P Silence 1 - Rappel Bruit 1 - Précision Traitement de l'information sur le Web Recherche d'Information Xavier Tannier 44 Évaluation : courbes rappel/précision • Le rappel augmente bien sûr avec le nombre de réponses • La précision diminue • On utilise la courbe rappel/précision pour caractériser les systèmes de recherche d'information 1 0,8 0,6 0,4 0,2 0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 1 Traitement Automatique des Langues Recherche d'Information Xavier Tannier 45 Évaluation : F-mesure • Pour obtenir une valeur unique entre 0 et 1, on utilise la F-mesure (moyenne harmonique) F 1 1 p (1 ( 1 ) R 2 1) P R 2 P R avec 1 2 1 • Pour donner autant d'importance à la précision qu'au rappel, on choisit = 1 F • < 1 favorise la précision, 2 P.R P R > 1 favorise le rappel Traitement Automatique des Langues Recherche d'Information Xavier Tannier 46 Évaluation : autres mesures • MAP (Mean Average Precision) : aire sous la courbe R/P • P@5, P@10 : précision après 10 documents retrouvés favorise la haute/très haute précision • P@100, ... • Taux d'erreur = (faux positifs + faux négatifs) / pertinents • et de nombreuses autres... MAP Traitement Automatique des Langues Recherche d'Information Xavier Tannier 47 Quelques outils • • • • • • • • • • smart mg (version 1.3g) lucy/zettair cheshire dataparksearch engine lemur lucene terrier wumpus xapian ftp://ftp.cs.cornell.edu/pub/smart/ http://www.nzdl.org/html/mg.html http://www.seg.rmit.edu.au/zettair/ http://cheshire.lib.berkeley.edu/ http://www.dataparksearch.org/ http://www.lemurproject.org/ http://jakarta.apache.org/lucene/docs/ http://ir.dcs.gla.ac.uk/terrier/ http://www.wumpus-search.org/ http://www.xapian.org/ liste et liens sur http://www.emse.fr/~mbeig/IR/tools.html Traitement Automatique des Langues Recherche d'Information Xavier Tannier 48
© Copyright 2024 ExpyDoc
