Recherche d'Information
-
Introduction
Chiraz Trabelsi
[email protected]
1
Ce qui vous intéresse
• Cours
– Introduction
– Représentation et Indexation
– Modèles de recherche
– Recherche d'information sur le Web
– Etc.
• Notation :
1. Note de contrôle continu + Note de DS
2. Note finale : Examen écrit (avec questions de cours)
Recherche d'Information
Chiraz Trabelsi 2
Ä Introduction
2
Qu'est-ce que la Recherche
d'Information ?
(brainstorming)
Les acteurs de la Recherche d'Information
Collection :
un ensemble de
documents
Les systèmes de RI
Utilisateur : doivent pouvoir traiter :
• De grandes masses
un besoin d'information
d'information • En langage naturel (et créée
et/ou une tâche pour des humains)
à accomplir • De façon rapide et pertinente
Recherche d'Information
Chiraz Trabelsi 4
Ä Introduction
4
Recherche d'Information
Google
Web
Recherche d'Information
Chiraz Trabelsi 5
Ä Introduction
Recherche d'Information
• Où se trouve la librairie la plus proche de chez moi ?
• Qui est actuellement en tête du Top 14 de rugby ?
• Quels sont les titres mentionnés à la une du journal Le Monde d’aujourd’hui ?
• Que rapporte la une du Monde d’aujourd’hui sur les candidats à l’élection présidentielle ?
• Quels sont les films qui passent ce soir sur la TNT ?
• Dans quels films Jean Rochefort et Philippe Noiret ont-ils joué ensemble ?
• Quels sont les logiciels d’installation de logiciels sous Linux/Debian ?
• Comment peut-on installer des logiciels sous Linux/Debian ?
• Quelle est la traduction du mot anglais “ice” en français ?
• Qui était Claude Bernard ?
Questions
• Quelle est la nature des résultats attendus ?
• Comment évalue-t-on la pertinence des résultats ?
• Sous quelle forme doit-on formuler ses requêtes ?
•…
Recherche d'Information
Chiraz Trabelsi 6
Ä Introduction
6
Information vs. données
• "Les données sont reçues, stockées et retrouvées par un
endosystème. Les données sont impersonnelles ; elles sont
disponibles pour tout utilisateur du système.
• L'information, en revanche, est un ensemble de données qui
correspond à un besoin particulier.
• Le concept d'information a des composantes personnelles et
temporelles absentes du concept de donnée."
(R. R. Korfhage, 1997)
Recherche d'Information
Chiraz Trabelsi 7
Ä Introduction
Connaissance
•Une quantité Q du produit P est vendue en région R
•Les familles de profil F utilisent M% de P durant la période N
Information
•X habite la région R
•Y a A ans
•Z dépense son argent dans la ville V de la région R
Données
•Consommateurs
•Magasins
•Ventes
•Démographie
•Géographie Recherche d'Information 8
Chiraz Trabelsi oct.-23
Ä Introduction
8
Information
Informations visibles
• 14èmes Journées Francophones "Extraction et Gestion des
Connaissances"
• Du 28 au 31 janvier 2014
• Rennes, France
• Président d'honneur : Jim Hendler, Rensselaer Polytechnic Institute,
USA
Recherche d'Information
Chiraz Trabelsi 10
Ä Introduction
10
Ce qu'une machine voit…
• 14èmes Journées Francophones
"Extraction et Gestion des
Connaissances"
• Du 28 au 31 janvier 2014
• Rennes, France
• Président d'honneur : Jim
Hendler, Rensselaer Polytechnic
Institute, USA
Recherche d'Information
Chiraz Trabelsi 11
Ä Introduction
11
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.
• 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 Tunisie
Recherche d'Information
Chiraz Trabelsi 12
Ä Introduction
12
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é ?
• 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
Recherche d'Information
Chiraz Trabelsi 13
Ä Introduction
13
Diversité des sources d'information
• Emplacement des informations
– Ressources locales ou distantes
– Problèmes : disponibilité, identification, répartition sur plusieurs sources,
variabilité des formats (encodage des caractères et description du contenu)
• Nature des fichiers de ressources
– Bases de données : formats bien décrits, langages d’interrogation non
ambigus (ex : SQL pour les bases de données relationnelles)
– Fichiers annotés : formats plus ou moins bien décrits, annotations de
présentation et/ou de description sémantique du contenu, langages
d’interrogation (ex : XSLT/XPath pour les fichiers XML)
– Fichiers textes : formats très peu ou pas décrits, langue(s) connue(s) ou non,
– Pages Web : fichiers écrits en HTML,..
– Vidéos annotées,….
Recherche d'Information
Chiraz Trabelsi 14
Ä Introduction
14
Diversité des problèmes
• Difficultés d'accès, couverture, temps de traitement
– Les sources d’information sont très grandes, réparties sur de
nombreux sites dans des localisations différentes.
• Difficultés de définition de la pertinence
– Comment un document remplit-il le besoin informationnel d'une personne
donnée ?
– Quelle est sa pertinence ? Comment la mesure-t-on ?
• Difficulté d'exploitation
– Les documents pertinents ne sont pas nécessairement dans la langue de la
requête.
– L'information recherchée n'est pas nécessairement
clairement identifiable dans un document.
Recherche d'Information
Chiraz Trabelsi 15
Ä Introduction
15
Grandes évolutions de la RI
• Précédemment :
– Bases documentaires structurées 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...)
Recherche d'Information
Chiraz Trabelsi 16
Ä Introduction
16
Recherche d'information sur le Web
• Sur Internet : utilisation massive par des utilisateurs non experts
– Domaine d'une importance économique majeure
– La requête typique est constituée d’au plus quelques mots clés
– Les utilisateurs s’adaptent aux outils
• Une partie du web n’est pas directement accessible (web invisible,
dont pages à accès restreint et pages dynamiques)
• L’information présente est fortement multilingue : les documents
répondant aux requêtes peuvent être dans des langues différentes
• L’information présente n’est pas toujours fiable
• La visualisation de l’information est particulièrement importante :
classement des résultats, présentation d’extraits, extraction de
segments pertinents, etc.
Recherche d'Information
Chiraz Trabelsi 17
Ä Introduction
17
Recherche d'Information
Indexation
Collections dynamiques (modèle de document)
vs. statiques
Modèle de
recherche Évaluation
Requête
Recherche d'Information
Chiraz Trabelsi 18
Ä Introduction
18
Les difficultés de la RI : le facteur humain
• Le besoin d'information de l'utilisateur est parfois vague et toujours
subjectif.
– La perte d'information entre la réalité du besoin d'information et son
expression peut être importante.
– La pertinence d'un document pour une requête est une notion variable et
très complexe à définir.
Ø Il ne peut pas exister de système de recherche d'information parfait
Ø L'évaluation d'un système dépasse les aspects
habituels de performance informatique
• L'humain est subjectif, versatile, et il utilise un langage "naturel" !
Recherche d'Information
Chiraz Trabelsi 19
Ä Introduction
19
Les difficultés de la RI : le facteur "langage"
• À la différence des langages artificiels, le langage "naturel" est :
– Implicite : tout n'est pas dit dans les textes et leur compréhension requiert
une importance connaissance sur le contexte et sur le monde
– Redondant : la langue offre de nombreuses façons de
formuler le même contenu
– Ambigu : un même énoncé peut souvent être interprété
de différentes façons
• La recherche d'information est encore compliquée par le fait que :
– Les mots peuvent jouer des rôles différents dans les textes
– Les atomes de sens peuvent être des mots ou des groupes de mots (termes)
Ø Il est compliqué de formuler son besoin d’information
(perte d’information entre besoin et requête)
Recherche d'Information
Chiraz Trabelsi 20
Ä Introduction
20
Caractère redondant de la langue
• Au niveau lexical
– Synonymie : vélo et bicyclette
– Hyperonymie et hyponymie : véhicule / vélo / VTT
– Méronymie et holonymie : pédale / pédalier / vélo
• Abréviations et sigles
– S'il-vous-plaît et SVP, VTT et Vélo Tout Terrain
• Entre mots et expressions
– Périphrases : lave-vaisselle et machine à laver la vaisselle
– Définitions : selle et petit siège, le plus souvent de cuir, d'un cycle ou d'un
véhicule à deux roues à moteur
• Glissements de sens (synonymie contextuelle)
– Il a écrit un papier/article sur la recherche d'information
Recherche d'Information
Chiraz Trabelsi 21
Ä Introduction
21
Caractère ambigu de la langue
• Les homonymes sont des mots qui ont une même graphie mais des
sens différents
Recherche d'Information
Chiraz Trabelsi 22
Ä Introduction
22
Mots composés
• Les mots composés sont beaucoup moins polysémiques
• Les rechercher ensemble dans les textes est bénéfique
(mais compliqué)
• Ils ont un sens qui n'est pas la composition des sens des atomes
– Homme-grenouille
– Pomme de terre
– Traitement de texte
ã M. Heinrich, J. Negra
Recherche d'Information
Chiraz Trabelsi 23
Ä Introduction
23
Recherche d'Information
• Elle permet de traiter de grandes masses d'informations.
• Elle s'applique à du texte en langue naturelle, ne demande pas
d'intervention des concepteurs des sites, ni de représentation
particulière pour les connaissances manipulées.
• Les machines ne comprennent rien au sens des informations
traitées.
• Un moteur de recherche ne permet aucune inférence, aucun
recoupement d'information.
Recherche d'Information
Chiraz Trabelsi 24
Ä Introduction
24
Accès au contenu sémantique
Avec l'aide de Brigitte Safar
25
Information partiellement structurée
• Premières applications: dans les bibliothèques :
spécification d’un livre
ISBN: 0-201-12227-8
Auteur: Salton, Gerard
Titre: Automatic text processing: the transformation,
analysis, and retrieval of information by computer
Editeur: Addison-Wesley
Date: 1989
Contenu: <Text du livre>
• Chercher un livre par :
– Attributs externes (ISBN, Auteur., etc) = recherche en BD
– Attributs internes (contenu) = RI: recherche par le contenu
Recherche d'Information
Chiraz Trabelsi 26
Ä Introduction
26
Approches possibles
1. Approche minimaliste :
Considérer la requête comme chaîne de caractère, et un document
pertinent comme celui qui contient cette chaîne.
– Balayer les documents séquentiellement, en les comparant avec la chaîne de
caractère qui est la requête, si on trouve la même chaîne dans un document,
alors il est retourné comme réponse.
– Approche très simple mais :
• Vitesse : très lente (convient pour des petites collections),
• Pouvoir d’expression d’une requête
Recherche d'Information
Chiraz Trabelsi 27
Ä Introduction
27
Approches possibles:
Indexation
2. Approche basée sur l’indexation :
Effectuer un pré-traitement sur les documents et sur les requêtes:
Þ Construire une structure d’index qui permet de retrouver rapidement les
documents incluant les termes demandés:
terme--> {D1, D2,…Dn} : chaque terme est mis en
correspondance avec les documents qui le contiennent
• La requête peut être une expression incluant des
opérateurs logiques (ET, OU,..) ou d’autre types
d’opérateurs.
Recherche d'Information
Chiraz Trabelsi
Ä Introduction
28
Avantages de l’indexation
• Par rapport à l'approche minimaliste, cette approche a
les avantages suivants:
– Elle est plus rapide. En effet, on n'a plus besoin du parcours séquentiel.
Avec la structure d'index, on peut directement savoir quels documents
contiennent tel ou tel mot.
– L'expression des requêtes peut être très complexe, exprimant des besoins
d'information complexes.
Recherche d'Information
Chiraz Trabelsi
Ä Introduction
29
Le prix à payer…
• Besoin de l'espace de stockage supplémentaire pour la
structure d'index.
• 40% à 200% de la taille de la collection de documents, selon la
complexité de l'indexation.
• Le besoin d'espace pose de moins en moins de problème
maintenant.
Recherche d'Information
Chiraz Trabelsi
Ä Introduction
30
Problèmes majeurs en RI
• Indexation du Document (D) et de la Requête (Q)
– Quelle est la meilleure représentation?
• Évaluation de la Q (ou processus de la recherche ou
correspondance)
– Comment D est pertinent par rapport à Q (mesures)?
• Évaluation du SRI
– Performances du SRI?
– Les document trouvés sont-ils pertinents? (précision)
– Tous les documents pertinents sont retrouvés? (rappel)
Recherche d'Information
Chiraz Trabelsi 31
Ä Introduction
31
Utilisateur Besoin Documents
d’information Pertinence de pertinents
l’utilisateur
Requête Document
Pertinence du système
indexation indexation
Représentation Représentation
(mots clés) (mots clés)
Correspondance
Recherche d'Information
Chiraz Trabelsi
Ä Introduction
32
Notions de correspondance et d’évaluation
• Déterminer si la représentation d'un document
correspond à celle de la requête => développer un
processus d'évaluation.
• Un bon système de RI doit donner une évaluation de
correspondance qui reflète bien la pertinence du
système, qui à son tour, correspond bien au jugement
de pertinence de l'utilisateur.
Recherche d'Information
Chiraz Trabelsi
Ä Introduction
33
Evaluation d'un SRI
• Le but de la RI est de trouver des documents pertinents à
une requête, et donc utiles pour l'utilisateur.
• 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 correspond à celles que
l'utilisateur espère, mieux est le système.
Recherche d'Information
Chiraz Trabelsi
Ä Introduction
34
Corpus de test (références)
• Pour arriver à une telle évaluation, on doit connaître d'abord
les réponses idéales de l'utilisateur.
• Un corpus de test (ou de référence) :
– un ensemble de documents;
– un ensemble de requêtes;
– la liste de documents pertinents pour chaque requête.
Recherche d'Information
Chiraz Trabelsi
Ä Introduction
35
Taille d’un corpus
• Pour qu'un corpus de test soit significatif, il faut qu'il
possède un nombre de documents assez élevé.
• Les premiers corpus de test développés dans les
années 1970 renferment quelques milliers de
documents.
• Les corpus de test plus récents (par exemple, ceux
de TREC) contiennent en général plus 100 000
documents (considérés maintenant comme un
corpus de taille moyenne), voir des millions de
documents (corpus de grande taille).
Recherche d'Information
Chiraz Trabelsi
Ä Introduction
36
Précision et rappel
• La comparaison des réponses d'un système pour une requête
avec les réponses idéales nous permet d'évaluer les deux
métriques suivantes:
– Précision
– Rappel
Recherche d'Information
Chiraz Trabelsi
Ä Introduction
37
Précision
• Précision: La précision mesure la proportion de document
pertinents retrouvés parmi tous les documents retrouvés par
le système.
Précision = # de documents pertinents retournés par le SRI
# de documents retournés le SRI
Recherche d'Information
Chiraz Trabelsi
Ä Introduction
38
Rappel
• Rappel : Le rappel mesure la proportion de document
pertinents retrouvés parmi tous les documents pertinents dans
la base (collection de test).
Rappel = # de documents pertinents retournés par le SRI
# de documents pertinents dans la collection de test
Recherche d'Information
Chiraz Trabelsi
Ä Introduction
39
Idéalement…
• Idéalement, on voudrait qu'un système donne de bons taux de
précision et de rappel en même temps. Un système qui aurait
100% pour la précision et pour le rappel signifie qu'il trouve
tous les documents pertinents, et rien que les documents
pertinents.
Þ les réponses du système à chaque requête sont constituées de
tous et seulement les documents idéaux que l'utilisateur a
identifiés.
• En pratique, cette situation n'arrive pas. On peut obtenir un
taux de précision et de rappel aux alentours de 30%.
Recherche d'Information
Chiraz Trabelsi
Ä Introduction
40
Relation entre Rappel et Précision
• Les deux métriques :
– Ne sont pas indépendantes : quand l'une augmente, l'autre diminue.
– Ne sont pas statiques : un système n'a pas qu'une mesure de précision et
de rappel.
• Le comportement d'un système peut varier en faveur de
précision ou en faveur de rappel (en détriment de l'autre
métrique).
Recherche d'Information
Chiraz Trabelsi
Ä Introduction
41
Comparaison de systèmes et Précision moyenne
• Pour comparer deux systèmes de RI, il faut les tester avec le
même corpus de test (ou plusieurs corpus de test) :
– On utilise la précision moyenne comme une mesure de performance.
La précision moyenne est une moyenne de précision sur un ensemble
de points de rappel.
– L’amélioration relative qui est calculée comme suit :
Amélioration du SRI 2 par rapport au SRI 1 =
(performance du SRI 2 – performance du SRI 1)
performance du SRI 1.
Recherche d'Information
Chiraz Trabelsi 42
Ä Introduction
42
Bref historique de la RI
• Années 1940-50s
– Automatisation des bibliothèques
– Notion de pertinence
– Calvin N. Mooers introduit en 1948 le terme « recherche
d'information » (information retrieval)
– La première conférence sur le thème a lieu en 1958
(International Conference on Scientific Information)
– Luhn décrit un modèle statistique pour la recherche
d'information (KWIC)
Recherche d'Information
Chiraz Trabelsi 43
Ä Introduction
43
Bref historique de la RI
• Années 1960-70s
– Maron et Kuhns définissent un modèle de recherche
d'information probabiliste
– Le projet d'évaluation CRANFIELD définit les mesures
d'évaluation
– Premier livre de Gerard Salton sur le système SMART
– Développement des modèles booléens et vectoriels pour la
recherche d'information
Recherche d'Information
Chiraz Trabelsi 44
Ä Introduction
44
Bref historique de la RI
• Années 1980s
– Grandes bases de données de documents
– Intégration des techniques de l’IA en RI : systèmes experts etc.,
• Années 1990s
– baisse du coût des disques => stockage d'information
– WESTLAW premier système de recherche d'information à grande
échelle qui utilise un modèle de recherche probabiliste
– Recherche sur des fichiers sur Internet
– Evaluations TREC
– Systèmes de recommandations
– Catégorisation et classification de textes
– Essor des modèles probabilistes (Okapi)
– Introduction des modèles de langues à la fin des années 90s
Recherche d'Information
Chiraz Trabelsi
Ä Introduction
45
Bref historique de la RI
• Années 2000s
– Analyse de liens pour la recherche d'informations sur le web (google)
– Extraction d'information
– Réponses à des questions (TREC QA track)
– Indexation et recherche d'informations multimedia (image, video,
audio et musique)
– Recherche d'information multilingue (CLEF, NTCIR, DARPA, Tides)
– Résumé automatique de documents
➔ la recherche d'information comme un pré-traitement
Recherche d'Information
Chiraz Trabelsi
Ä Introduction
46
Conclusion de l'introduction
• Les humains préfèrent les documents textuels dans leur langue
naturelle.
• Les machines préfèrent des données structurées et sans surprise.
• Il est difficile de construire des documents appropriés à la fois pour
les machines et pour les humains.
Ä Recherche d'information et web sémantique sont complémentaires.
Recherche d'Information
Chiraz Trabelsi 47
Ä Introduction
47
Pendant ce module
• En cours
– Au programme :
• Introduction
• Indexation
• Modèle de Recherche
• Évaluation
• Passage à l’échelle
• RI sur le Web
Recherche d'Information
Chiraz Trabelsi 48
Ä Introduction
48
