Introduction à la Recherche
d’Information : les
principes
1
1
1/31
Plan du cours
1 Qu’est-ce que la recherche d’information ? Exemple
de Recherche d’information Évaluation d’un
moteur de recherche
2
2
2/31
Information Retrieval, définition
Une définition
La Recherche d’Information (Information Retrieval, IR) consiste à trouver des
documents peu ou faiblement structurés, dans une grande collection, en fonction d’un
besoin d’information.
Recherche sur le Web. Utilisée quotidiennement par des milliards
d’utilisateurs.
Recherche dans votre boîte mail.
Recherche sur votre ordinateur
(Spotlight).
Recherche dans une base documentaire, publique ou privée.
3
3
31
Information Retrieval, définition
Recherche plein texte : on cherche à examiner tous les mots de chaque
document enregistré et à essayer de les faire correspondre à ceux fournis par
l’utilisateur
À bien distinguer d’une recherche type “base de données” : requête
structurée, données structurées, réponse «exacte».
Contrairement à une base de données (SQL), le résultat dépend de l’interprétation d’un
besoin. On ne peut jamais dire qu’un résultat est totalement exact (ou totalement faux).
4
4
Un moteur de recherche bien connu
5
5
6/31
Fonctionnalités avancées
6
6
7/31
Wikipédia : recherche avancée
7
7
8/31
ECommerce : recherche à facettes
8
8
Évaluation d’un moteur de recherche
9
9
Évaluation d’un moteur de recherche
10
10
10/31
Évaluation d’un moteur de recherche
Deux notions importantes
Faux positifs : ce sont les documents non pertinents inclus dans le résultat; ils
ont été sélectionnés à tort.
Faux négatifs : ce sont les documents pertinents qui ne sont pas inclus dans
le résultat.
La recherche plein texte est susceptible de récupérer beaucoup de faux positifs.
La récupération de documents non pertinents est souvent provoquée par
l’ambiguïté inhérente au langage naturel ;
En général, chercher à réduire les faux positifs entraîne l’augmentation des
faux négatifs, et réciproquement.
11
11
11/31
Évaluation de la pertinence : précision et rappel
La précision mesure la fraction des vrais positifs dans le résultat r.
Si on note tp (r) et fp (r) le nombre de vrais et de faux positifs dans r, alors
tp(r) tp(r)
précision = =
t p (r)+fp (r) |r|
Le rappel mesure la fraction de faux
négatifs.
tp
rappel=
tp +fn
L’évaluation d’un système de RI est difficile : implique des tests rigoureux avec
des utilisateurs sur un échantillon.
12
12
12/31
Illustration des faux-positifs et négatifs
13
13
13/31
Performances
On peut améliorer les performances des moteurs de recherche à l’aide de plusieurs
techniques :
des requêtes plus structurées
requêtes booléennes,
expressions rationnelles,
proximité,
recherche d’expression
des résultats classés
modèle vectoriel
PageRank
analyse sémantique latente
14
14
13/31
Plan du cours
2 Intégration de moteurs dans le SI
15
15
14/31
Moteurs de recherche
Moteurs libres
Apache Solr (Lucene)
ElasticSearch
(Lucene) Sphinx
Xapian Moteurs
commerciaux
Google Search Appliance
Exalead, Qwant
Amazon
CloudSearch
Microsoft Azure Search,
Bing
16
16
15/31
Bases documentaires et moteur de recherche
17
17
16/31
Bases documentaires et moteur de recherche
Un scénario typique :
une recherche par mot-clé dans un site
Les données du site sont gérées classiquement par une base documentaire
(MySQL, Postgres, MongoDB)
On extrait de la base tous les textes à indexer et on en fait des documents
ES/Solr, à qui on les confie
Ce dernier se charge alors de répondre quand un utilisateur emploie un champ
de recherche.
18
18
17/31
Bases documentaires et moteur de recherche
Un moteur de recherche comme ElasticSearch ou Solr s’appuie sur un index
Pourquoi ne pas utiliser directement le moteur de recherche comme gestionnaire
des documents ?
ElasticSearch permet des recherches puissantes, efficaces, ainsi que le
stockage et l’accès aux documents.
19
19
18/31
Bases documentaires et moteur de recherche
Mais, comme ElasticSearch est entièrement consacré à la recherche, c’est-à-
dire la lecture la plus efficace possible de documents.
il s’appuie pour cela sur des structures compactes, compressées, optimisées (les
index inversés)
ce n’est pas un très bon outil pour les autres fonctionnalités d’une base de
données :
Le stockage par exemple n’est ni aussi robuste ni aussi stable.
Pour des raisons qui tiennent à la structure de ces index, les mises à jour sont difficiles
et s’effectuent difficilement en temps réel
20
20
19/31
Plan du cours
3 Index (ou liste) inversés
Modèle
Opération de recherche avec liste
inversée
21
21
20/31
Exemple de base
Un ensemble (modeste) de documents nous servira de guide.
d1 Le loup est dans la bergerie.
d2 Le loup et le trois petits cochons.
d3 Les moutons sont dans la bergerie.
d4 Spider Cochon, Spider Cochon, il peut marcher au plafond.
d5 Un loup a mangé un mouton, les autres loups sont restés dans la bergerie.
d6 Il y a trois moutons dans le pré, et un mouton dans la gueule du loup. d7
Le cochon est à 12€ le Kg, le mouton à 10€/Kg.
d8 Les trois petits loups et le grand méchant cochon.
22
22
21/31
Le besoin et la solution
Besoin
On veut chercher tous les documents parlant de loups, de moutons mais pas de
bergerie.
Parcourir tous les documents ?
(Grep) potentiellement long;
critère ”pas de bergerie” n’est pas facile à traiter;
autres types de recherche (”le mot ’loup’ doit être près du mot ’mouton’”) sont
difficiles;
comment classer par pertinence les documents trouvés ?
Structure spécialisée : la matrice d’incidence et surtout soninversion.
23
23
22/31
Matrice avec documents en ligne
On sélectionne un ensemble de mots (ou termes), constituant notre vocabulaire
(ou dictionnaire).
Documents en ligne, termes en colonnes. Dans chaque cellule : 1 si le terme est dans
le document, 0 sinon.
24
24
23/31
Pour effectuer la recherche
(loup, mouton, et pas bergerie) On prend les vecteurs binaires des termes (les colonnes).
Loup : 11001101
Mouton : 00101110
Bergerie : 01010011
Puis :
ET logique sur les vecteurs de Loup et Mouton, on obtient 00001100.
ET logique avec le complément du vecteur de Bergerie (01010111)
On obtient 00000100, d’où on déduit que la réponse est limitée au document d6.
Opération binaires très efficace, mais...
25
25
27/31
Index inversé
La structure utilisée dans tous les moteurs de recherche.
Un répertoire contient tous les termes.
Une liste (inversée) est associée à chaque terme, triée par
docId. Chaque élément de la liste est appelé une entrée.
Concept : la notion de terme (token en anglais) est différente de celle de “mot”.
Vocabulaire : le répertoire est parfois appelé dictionnaire ; les listes sont des posting list
en anglais; les entrées sont des postings.
Efficacité : le répertoire devrait toujours être en mémoire ; les listes, autant que possible
en mémoire, sinon fichiers contigus sur le disque.
26
26