Cours RI Latiri 2024 Ing Compressed

Cours
Systèmes de Recherche d'Information

M2 DSIR
2023-2024
Chiraz Latiri
[email protected]
Autour de trois parties :
I. Introduction à la RI
II. Fondements de la RI
III. RI et Web
Chiraz Latiri
[email protected]
Partie I : Introduction à la RI
Chiraz Latiri
[email protected]
Recherche d’Information (RI) / Information Retrieval (IR)
Recherche d’Information
Ensemble des méthodes et techniques pour
l’acquisition, l’organisation, le stockage, la recherche
et la sélection d’information pertinente pour
un utilisateur
Chiraz Latiri 5
Recherche d'Information
Chiraz Latiri 6
Les acteurs de la Recherche d'Information
Collection :
un ensemble de
documents
Utilisateur : Système de RI : l'outil qui doit

un besoin retrouver les documents
d'information pertinents pour le besoin
et/ou une tâche de l'utilisateur
à accomplir
Chiraz Latiri 7
RI: définitions
IR is finding material (usually documents) of an
unstructured nature (usually text) that satisfies an
information need from within large collections (usually
stored on computers).
Information retrieval deals with the representation,

storage, organization of, and access to information items
such as documents, Web pages, online catalogs, structured
and semi-structured records, multimedia objects. The
representation and organization of the information items
should be such as to provide the users with easy access to
information of their interest.
IR: The techniques of storing and recovering and often

disseminating recorded data especially through the use of a
computerized system.
Chiraz Latiri 8
RI: définitions
• Information retrieval (IR)
• is the science of searching for documents, for information within
documents, and for metadata about documents, as well as that of
searching relational databases and the World Wide Web.
• IR is interdisciplinary,
• based on computer science, mathematics, library science,
information science, information architecture, cognitive
psychology, linguistics, statistics, and physics.
• are used to reduce what has been called "information overload".
• Many universities and public libraries use IR systems to provide
access to books, journals and other documents. Web search
engines are the most visible IR applications.
Chiraz Latiri 9
RI : une requête classique
Chiraz Latiri 10
RI: qu’est ce qu’on cherche?
• 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 Latiri 11

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)
• La connaissance est la sélection, l'appropriation et
l'interprétation des informations, souvent implicite et utile
pour l’utilisateur.

Données-Informations-Connaissances
Système de gestion de Système de Recherche
Base de données d’information
Données
Information :
Signification
Chaîne de caractères/valeurs
(explication/description) des
associées à des objets, des
personnes et des événements (42) données, données intelligible (42° C
- relevé à 18 h, sous abri, à Tozeur le
Select .. From … where
2 mai)
Connaissance :
Information découverte, comprise
et partagée par une communauté
(étant donné qu'on est au sud
Tunisien, 42°C en mai c’est plutôt
très chaud) (Data mining, fouille de
données)

L’information est partout sous de gros volumes
KiloOctets 103
MegaOctets 106
GigaOctets 109
TeraOctets 1012
PetaOctets 1015
ExaOctets 1018
ZettaOctets 1021
Big Growth Forecasted for Big Data
DC says 175 ZB will be created by 2025

(Image courtesy IDC)

Informations hétérogènes
Origines de l’information numérique….diverses et
nombreuses
Twitter (2015)
• Les tweets contenant une photo sont deux fois
plus partagés que la moyenne.
• 500 millions de tweets sont envoyés chaque jour.
• 300 milliards de tweets ont été envoyés depuis le
21 mars 2006.
Facebook (2015)
•Facebook (2015) Statuts partagés chaque

seconde : 4100
• Likes distribués chaque minute : 1,8 million
• Likes distribués chaque jour : 4,5 milliards
• Contenus partagés chaque jour : 4,75 milliards
• Messages envoyés chaque jour : 10 milliards
• Données échangées chaque minute : 350
gigaoctets

…et multi-sources

Premier Bilan
Le problème n’est pas la disponibilité de

l’information (Bases de données, Fichiers annotés,
Corpus de textes, Pages Web, Vidéos annotées, images,….)
Sa sélection, son identification
Arriver à trouver au bon

moment l’information utile et
pertinente
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 (Livre de Eric
Gaussier sur la RI).
• 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 l’enseignement secondaire en Tunisie

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 heure Chokri Belaid 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

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.

Verrous de la RI
• Rechercher une information a un coût
– « On» passe (en moyenne) 35% de son temps à rechercher des
informations
– Les managers y consacrent 17% de leur temps
– Les 1000 grandes entreprises (US) perdent jusqu’à $2.5 milliards
par an en raison de leur incapacité à récupérer les bonnes
informations
• Nécessité de développer des systèmes automatisés efficaces

permettant
– Collecter, Organiser, Rechercher, Sélectionner

Diversité des Tâches de RI (1/4)
• Recherche adhoc
– Je cherche des infos (pages web) sur un sujet donné
• Je soumets une requête à retour liste de résultats
• Requête «recherche d’info»à SRI à renvoie une liste de
documents traitant de la « recherche d’information »
– Plusieurs types de RI adhoc
• Recherche adhoc (tâches spécifiques)
– Domaine spécifique (médical, légal, chimie, …)
– Recherche d’opinions (Opinion retrieval) (sentiment analysis)
– Recherche d’événements
– Recherche de personnes (expert)

• Classification-Catégorisation/Clustering
(partitionnement)
– Regrouper les informations (documents) selon un
ou plusieurs critères
• Question-réponses (Query answering)

– Chercher des réponses à des questions
– par exemple
• « Qui est averroes ? »
• « Quelle la hauteur du Bouguarnine? »

• Filtrage d’information/ recommandation
(filtering/recommendation)
– Recommandation
– Dissémination sélective d’information
– Système d’alerte
– Push
– Profilage (profiling

• Résumé automatique (document summarization)
• Recherche agrégée (Aggregated search)

– Agréger des moteurs : interroger les résultats de
plusieurs moteurs (méta-moteurs)
– Agréger des résultats : interroger plusieurs sources
(vertical search)
– Agréger des contenus : former un résultat à partir de
plusieurs contenus

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.
Moteurs de recherche
• Distinguer d’abord :
– Outils propres au web : moteurs de recherche, métamoteurs, moteurs
de blogs…(Google, yahoo les plus populaires).
– Outils accessibles par le web : bases de données, catalogues…
• Deux critères essentiels :
– Offre des ressources : outil généraliste / spécialisé
– Mode d’indexation : outil humain / automatisé
• Moteurs généralistes : Google, Yahoo, Ask, Bing…
• Moteurs spécialisés : géographique : Google.tn, selon le contenu des
ressources indexées (Google Scholar), presse (Google News), disciplinaire
SciencesDirect en Sciences exactes, par domaine (PubMed), forums
(Google Groups), listes de diffusion (info-IC) ; blogs , selon les supports :
images, vidéos (Google ou Yahoo), fichiers son.

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"

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)

Caractère implicite de la langue
• Connaissance du langage et des conventions langagières
Q : Le voisin est-il chez lui ?
R : Sa voiture est devant le portail (implicature conversationnelle)
• Connaissance du contexte
C'est la deuxième fois qu'il reçoit un carton (Sport ? Courrier ? Accident ?)
• Connaissance du monde
La Nouvelle-Zélande va tailler la France en pièces. (métonymie + langage figuré +
actualité du rugby)
• Déduction (présupposition)
Ravaillac a assassiné Henri IV en 1610.
Ä Henri IV est mort en 1610.

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

Caractère ambigu de la langue
• Les homonymes sont des mots qui ont une même graphie mais des
sens différents
Chiraz Latiri 32
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

Partie II : Fondements de la RI
Chiraz Latiri
[email protected]
Problématique de la RI
Besoin en information ou Collections dynamiques ou
requête statiques
SRI
Résultat
Ici s’évalue la pertinence du
résultat
Sélectionner dans une collection
– Résultats: les informations ( documents, images, vidéos...)
– … pertinentes répondant aux
– … besoins en information des utilisateurs (Requêtes)

Besoin en information ou
requête
Besoin en information?...Requête (1/2)
• Formes
– Texte, images, sons, vidéo, graphiques, etc.
– Exemples texte : web pages, email, livres, journaux, publications, blog,
Word™, Powerpoint™, PDF, forum postings, brevets, etc.
• Hétérogénéité
– langage (multilingues)
– media (multimédia - transmédia)
– Social (réseaux sociaux, micrblogs)
– Comprendre le contenu vs. l’interptérer àAmbiguïté du langage naturel

(polysémie, synonymie, …)
– Définir la granularité respectivement au besoin (document, paragraphe,
phrase, titre, unité linguistique...)

Besoin en information?...Requête (2/2)
• Besoin en information est une expression mentale d’un utilisateur
• Requête : Ensemble de mots-clés
à Une représentation possible du besoin en information
Comment capturer le
besoin de l’utilisateur ?

Besoin d’information : Intention de la requête
• Besoin = requête
• Exemple : Apple

Résumé des notions clés de la RI
• Au cœur de tout système de RI (SRI)
– Relation entre le document et … la requête ou le besoin de
l’utilisateur (Besoin en information)?
• Plusieurs facteurs influencent la décision de l’utilisateur, tâche, le

contexte, nouveauté, style, compréhension, temps, …
• Pertinence par document

– Goffman, 1969: ‘…the relevance of the information from one document
depends upon what is already known about the subject, and in turn affects
the relevance of other documents subsequently examined.’

Notion de pertinence en RI
Pertinence: notion clé de la RI (1/2)
Rappel : Un système de recherche d’information doit satisfaire un besoin
d’information d’un utilisateur
• Pertinence : capacité d’un système à répondre exactement à la requête

demandée par l’utilisateur
• pertinence utilisateur vs pertinence système

• Pertinence utilisateur : satisfaction de l’utilisateur
• Pertinence système : estimation du système
Pertinence utilisateur : représente la façon dont l’utilisateur évalue les
documents retrouvés par le SRI en fonction de son besoin d’information (on
parle de jugements de pertinence).
ü C’est une évaluation subjective : dépend de l’utilisateur et varie au cours du temps,
ü Pas possible de la mesurer de manière automatique

Pertinence: notion clé de la RI (2/2)
Pertinence système : mesurée automatiquement par les SRI en comparant les
représentations des documents et celles des requêtes
diffère d’un SRI à un autre en fonction des méthodes utilisées pour
comparer les documents et la requête.
Attention : un document considéré comme pertinent par le système ne l’est pas
nécessairement par l’utilisateur (et inversement).
• L’enjeu de la RI : rapprocher tant que possible la pertinence système de la

pertinence utilisateur.
• Plusieurs pertinences système
– Thématique (topical): relation entre le sujet exprimé dans la requête et le
sujet couvert dans le document.
– Contextuelle (Situation) : relation entre la tâche, le problème posé par
l’utilisateur, la situation de l’utilisateur et l’information retrouvée.
– Cognitive : relation entre l’état de la connaissance de l’utilisateur et
l’information sélectionné

requête Processus RI
Requête
SRI
Langage de Traitement Traitement =
Indexation
requêtes Indexation
Appariement Index (mots clés) et
Liste de mots
Ranking organisation
physique
Fichier
inverse
Visualisation
Modèles de RI :
Vectoriel, probabiliste
Recherche d'Information Ranking dans le web Chiraz Latiri 44
SRI et modèle de RI

Pour récapituler…(1/2)
Représentation (indexation) du document
Comment construire une représentation à partir du document ?
Quelle organisation physique pour ces index?
Représentation des besoins
Comment capturer le besoin de l’utilisateur ?
Comment exprimer le besoin (langage de requêtes) ?
Comparaison/ranking document-requête (des
représentations)
Comment mesurer (décider) la pertinence d’un document ?
Évaluation des performances
Comment comparer les SRI ?
Quelle démarche (empirique/ analytique) ?
Quelles métriques ?

Pour récapituler…(2/2)
• 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 Latiri

Métriques de base d’évaluation
en RI
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.

Collections de test
• Pour arriver à une telle évaluation, on doit connaître

d'abord les réponses idéales de l'utilisateur.
• Une collection 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.

Démarche d’évaluation en RI (1/2)
• Démarche Analytique (formelle) :
– Difficile pour les SRI, car plusieurs facteurs : pertinence, distribution
des termes, etc. sont difficiles à formaliser mathématiquement
• Démarche Expérimentale (lab-based evaluation) (Cranfield

Paradigm)
– « benchmarking » : collection de test.
– Evaluation effectuée sur des collections de tests
– Collection de test : un ensemble de documents, un ensemble de
requêtes et des pertinences (réponses positives pour chaque requête)

Démarche d’évaluation en RI (2/2)
Documents de Requêtes de
tests test
1 9 7
q1
3 q2
4 6 5
Système à
évaluer
Liste 0,9
documents 5 0,8
9 0,7 Syst A
7 0,6
Précision
0,5
0,4
0,3
Liste de bonnes Evaluation 0,2
réponses Précision
0,1
0
q1 1, 9
et rappel 0,1 0,2 0,3 0,4 0,5 0,6
Rappel
0,7 0,8 0,9 1
q2 4

Qu’est ce
Evaluation d’un SRI qu’un
modèle RI?
• Comparer les SRI de manière théorique (via leur modèle) est un
problème non-résolu, on passe donc par des évaluations de type
«boîte noire » en testant les résultats d’un système par rapport aux
réponses idéales attendues.
• Objectif : Rapprocher pertinence système et utilisateur

Rappel vs Précision (1/3)
Les critères essentiels sont :
• Le rappel : capacité du système à fournir en réponse tous les
documents pertinents
• La précision : capacité du système à ne fournir que des
documents pertinents en réponse.
Ces deux critères sont antagonistes dans la réalité

• Le rappel est le rapport du nombre de documents trouvés par le
système et convenant à l’utilisateur au nombre total de documents
convenant à l’utilisateur.
• La précision est le rapport du nombre de documents trouvés par le

système et convenant à l’utilisateur au nombre de documents
retrouvés par le système.

Pour une requête et un système : 2 valeurs réelles
Exemple : un système retourne 5 documents, parmi lesquels 3 sont
pertinents, sachant qu’il y a 10 documents pertinents dans le
corpus, soit :
Rappel = 3 / 10
Précision = 3 / 5
Il faut des analyses plus fines
des résultats :
Courbes de rappel/précision

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).

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%.

Courbe rappel/Précision
Représente l’évolution de la précision et du rappel avec
des résultats triés.
Méthode :
Pour chaque document retrouvé, on calcule la précision et
le rappel obtenus en considérant seulement le premier
document comme réponse, puis les deux premiers, puis les
trois premiers etc., jusqu'à la réponse totale du système.

Exemple courbe Rappel/précision
Doc P(O/N) Rap Préc Un SRI retourne 12 documents, parmi
lesquels 7 sont pertinents, sachant qu’il y a
D23 Oui 1/15=0,06 1/1=1
15 documents pertinents dans le corpus.
D12 Non 0.06 ½=0,5
D55 Oui 2/15=0,12 2/3=0,66 Précision/Rappel

D67 Non 0,12 2/4=0,5 1
0,9
D14 Oui 3/15=0,2 3/5=0,6 0,8
0,7
D22 Non 3/15=0,2 3/6=0,5 0,6
0,5
D40 Oui 4/15=0,26 4/7=0,57
0,4
D11 Oui 5/15=0,33 =5/8=0,62 0,3
0,2
D9 Non 5/15=0,33 = 5/9 0,1
=0,55 0
0,06 0,06 0,12 0,12 0,2 0,2 0,26 0,33 0,33 0,33 0,4 0,46
D44 Non 5/15=0,33 =5/10=
Préc
0,5
D87 Oui 6/15=0,4 =
6/11=0,54
D18 Oui 7/15=0,46 =
7/12=0,58

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).

Courbe rappel/Précision (1/2)
Pour traiter l’évaluation sur plusieurs requêtes, on calcule la
moyenne aux points de rappels standards.
Précision moyenne à x documents (P@x)
• Il est également courant de calculer le taux de précision
après un nombre de documents fixés pour une requête, puis
de faire la moyenne sur toutes les requêtes.
• Il existe des programmes qui génèrent les tableaux pour les
courbes de rappel/précision et les précision moyennes à 5,
10, 20, 50 et 100 documents (Terrier, Lucene et TrecEval).

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 en tant Gain comme suit :
æ Perf ( SRI 2) - Perf ( SRI1) ö

Gain = çç ÷÷
è Perf ( SRI1) ø
Chiraz Latiri 63
Campagnes d’évaluation
• TREC - Text REtrieval Conference
– Évaluation des approches RI (beaucoup de tâches sont évaluées
dans cette campagne)
• CLEF - Cross Language Evaluation Forum

– Évaluation des approches de croisement de langues
(multilinguisme)
• INEX - Initiative for the Evaluation of XML Retrieval

– Évaluation de la RI sur des documents de type XML
• NTCIR- NII Testbeds and community for information access

Research
• SEMEval
• DEFT
Autres métriques en RI
• R-Précision,
• MAP,
• P@X,
• RR (Reciprocal Rank)
• NDGC,
• BPREF,
• F-mesure,
• Coverage,
• Novelty.

Indexation en RI
Indexation

Indexation: exemple

Indexation: exemple
• Décomposer le texte (Parsing) <Title>: Information retrieval
(Corps du texte> : Information
retrieval (IR) is the activity of
• Décomposer les mots (Tockenizing) obtaining information resources…
Information, retrieval, information,
• Supprimer les mots communs (Stop retrieval, IR, is, the activity, of
,obtaining, information …
word removal)
– Basé sur une “short list” “the”, Information, retrieval, information,
“and”, “or” retrieval, IR, activity, obtaining,
Information, retrieval, information,

• Raciniser les mots (Stemming) retrieval, IR, activity, obtain
Information 2, retrieval 2, IR 1,
• Regrouper les mots activity1, obtain 1
Un sac de
mots (BOW)
Indexation : pourquoi ?
• L’idée principale du moteur de recherche est de retrouver les
documents qui « parlent de » la requête.
• On utilise ce qu’on a sous la main : les mots
– Qu’est-ce qu’un mot ?
– Que faire lorsqu’un mot est « proche » d’un mot de la requête ?
• 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)

Indexation
ü Processus permettant de construire un ensemble d’éléments
«clés» permettant de caractériser le contenu d’un document /
retrouver ce document en réponse à une requête
ü Approches
– Guidée par un vocabulaire contrôlé vs. Libre
– Statistique (distribution des mots) et/ou TALN
(compréhension du texte)
– Approche courante est plutôt statistique avec des
hypothèses simples
• Redondance d’un mot marque son importance
• Cooccurrence des mots marque le sujet d’un document

Indexation libre et contrôlée
• Indexation libre :
– Mots, termes des documents
• Indexation contrôlée
– Listes de termes prédéfinies
– Vocabulaire contrôlé (évite
– polysémie, synonymie et problèmes
de granularité)
– Thésaurus
exemple : thésaurus UMLS

Approche générale de construction d’index
Prétraitements linguistiques Utilisation
d’une stop
Collections words liste
de Sélection
documents des termes
Normalisation
Corpus de
des termes
textes
Construction
de l’index
Segmentation
Chiraz Latiri 73
Dans quels documents cherche-t-on ?
• Formats
– HTML (menus, tableaux, publicité, rendu)
– Texte brut (structure ?)
– pdf (problèmes d’encodage, rendu)
– Word (format propriétaire, structure)
– Excel (gestion des tableaux)
– OpenOffice (XML)
– …
• Il est assez simple de détecter le type d’un document
• Des heuristiques spécifiques à chaque format pour extraire
le texte
• Les moteurs de recherche utilisent très rarement la
structure des documents

• Langues
– Identification de langues, un problème difficile
– Des documents multilingues
– De la recherche d’information multilingue
• Encodages
– Des erreurs dans la gestion de l’encodage peuvent
conduire à des résultats erronés
« président du Pérou »

• « Unité » document
– Un fichier ?
– Un e-mail ?
• Avec ses entêtes ?
• Avec ses attachements ?
– Un groupe de fichiers ?
• Site Web
• Document en plusieurs
fichiers
– Etc.

Prétraitements linguistiques
Collections
de Sélection
Normalisation
Corpus de
des termes
textes
Construction
de l’index
Segmentation
Chiraz Latiri 77
La segmentation (Tokenisation)
• Identification des unités élémentaires
(phonèmes, morphèmes, mots, etc.).
Pour l'écrit, des mots et des phrases.
• Un problème très complexe dans certaines
langues (chinois...)
• L’étape initiale indispensable pour tout travail sur le texte
• On obtient des mots, ou des termes, ou des tokens
• Ces unités seront les candidats à l’indexation et à la recherche

dans une requête

La segmentation
• Dans les langues « latines" :
– Les délimiteurs de mots et de phrases peuvent être ambigus
• etc. T.A.L. 21.3 www.sncf.com
• l'illusion aujourd'hui jusqu'à
• Jean-Louis donne-t-il 1914-1918 06-13-23-33-12
– Les mots (noms propres en particulier) peuvent avoir des variantes :
• Etats-Unis États-Unis
• France Inter France-Inter

La segmentation
• Dans les langues "européennes" :
– Les nombres, les dates
• 14/07/1789 Mardi 12 mars
• B-52
• (+33) 6 45 65 13 95
• Les anciens systèmes de RI retiraient tout simplement les nombres
• Toujours source de beaucoup d’erreurs dans les systèmes de RI modernes

La segmentation
• En Japonais, Chinois, etc. il n’y a pas d’espace entre les mots
– 學而不思則罔，思而不學則殆。
– La segmentation n’est pas toujours unique
• En Japonais, Coréen, on manipule plusieurs types d’alphabets !

東京、マドリード、イスタンブール（トルコ）が争う２０２０年夏季五輪の開催
地は７日（日本時間８日）、ブエノスアイレスでの国際オリンピック委員会（Ｉ
ＯＣ）総会で、ＩＯＣ委員約１００人の投票で決まる。
• En Arabe ou en Hébreu, on écrit de droite à gauche, mais

certains éléments sont écrits de gauche à droite
‫ وﺣدة ﺳﻛﻧﯾﺔ ﺟدﯾدة ﻣوﺟﮭﺔ ﻻﻣﺗﺻﺎص اﻟﺳﻛن اﻟﮭش ﻋﺑر وﻻﯾﺔ‬3026 ‫ﯾرﺗﻘب ﺗوزﯾﻊ ﻣﺎ ﻣﺟﻣوﻋﮫ‬
2013 ‫ﻋﻧﺎﺑﺔ وذﻟك ﻗﺑل ﻧﮭﺎﯾﺔ اﻟﺳﻧﺔ اﻟﺟﺎرﯾﺔ‬

Filtrage
Collections
de Sélection
Normalisation
Corpus de
des termes
textes
Construction
de l’index
Segmentation
Chiraz Latiri 82
Filtrage des mots vides (Stopword list)
• Les mots « outils » n’apportent pas de sens au texte
déterminants : « le », « la », pronoms : « je », « nous », prépositions :
« sur », « contre », …
• Ce sont les mots les plus fréquents de la langue
– Les 30 mots les plus fréquents représentent 30 % des occurrences de
mots
– Les supprimer permet d’économiser beaucoup de place dans l’index
• Mais :
– On en a besoin pour des requêtes multi-termes
« pomme de terre », « les Chevaliers du Zodiaque »
– Ils sont parfois porteurs de sens dans des cas particuliers
« Let it be », « The Who », « ça », « être ou ne pas être »
– La compression permet finalement de conserver les mots vides dans peu
d’espace
Antidictionnaire (Stopword list) Smart (571)
a all and are
a's allow another aren't
able allows any around
about almost anybody as
above alone anyhow aside
according along anyone ask
accordingly already anything asking
across also anyway associated
actually although anyways at
after always anywhere available
afterwards am apart away
again among appear awfully
against amongst appreciate
ain't an appropriate

Filtrage
Collections
de Sélection
Normalisation
Normalisation
Corpus de
des termes
textes
Construction
de l’index
Segmentation
Chiraz Latiri 85
Normalisation textuelle (1)
• Dans les documents comme dans la requête
• On veut par exemple normaliser :
– « U.S.A. » et « USA » à USA
– « morpho-syntaxe » et « morphosyntaxe » à morphosyntaxe
– « Tuebingen », « Tübingen » et « Tubingen » à Tubingen
– « Gorbatchov » et « Gorbatchev » à Gorbatchev
• Mais pas :
– « sur » et « sûr »,
– « pêche » et « péché »
– En allemand, « mit » (avec) et « MIT »
– En anglais, « C.A.T. » (Caterpillar) et « cat »
• Sans oublier les fautes de frappe / d’orthographe

Normalisation textuelle (2)
• Les règles communiément utilisées :
• Les ponctuations :
– Enlever les points et les traits d’union apparaissant dans les mots.
• La casse :
– Réduction de certaines lettres en minuscules.
– L’heuristique la plus souvent utilisée : convertir les 1ères lettres des
mots se trouvant au début de chaque phrase.
• Les accents :
ambiguë à ambigue; forêt à foret,
• Les dates et les valeurs monétaires : année/mois/jour ou
mois/jour/année
Chiraz Latiri 87
Normalisation linguistique
• Ramener un mot fléchi sous sa forme

canonique.
• 3 types de normalisation linguistique:
• La lemmatisation
• La racinisation
• L’étiquetage
Chiraz Latiri 88
Lemmatisation
• Obtention de la forme canonique (le lemme) à partir du mot :
– Pour un verbe : sa forme à l'infinitif (sans les flexions)
montrer, montreras, montraient à montrer
am, are, is à be
– Pour un nom, adjectif, article, ... : sa forme au masculin singulier

vert, vertes, verts à vert
computing à compute
car, cars, car's, cars' à car
• La lemmatisation demande des ressources et un traitement
linguistique
– En particulier pour les nombreuses exceptions
– Long et donc difficile à mettre en œuvre pour des grandes collections
– Dépendant de la langue

Racinisation (stemming)
• Obtention de la racine, une forme tronquée du mot, commune
à toutes les variantes morphologiques (troncature)
– Suppression des flexions
– Suppression des suffixes
– Ex : cheval, chevaux, chevalier, chevalerie, chevaucher
>> "cheva"(mais pas "cavalier")
– automate(s), automatic, automation >> automat
• La racinisation est généralement à base de règles
– Rapide
– Dépendant de la langue
• Elle agrège beaucoup plus que la lemmatisation
– Index plus petit

Racinisation : algorithme de Porter
• 5 phases de réduction par règles (pour l’anglais, adapté
ensuite au français)
• Si deux règles de réduction s’appliquent, on choisit celle qui
supprime le plus long suffixe
• sses à ss
• ies à i
• ational à ate
• tional à tion
• Si m > 1 alors cement à ""
replacement à replac
cement à cement

Algorithme de Porter
(Porter, M.F., 1980, An algorithm for suffix stripping, Program, 14(3) :130-137)
• Step 1: pluriels et participes passés
– SSES -> SS caresses -> caress
– (*v*) ING -> motoring -> motor
• Step 2: adj->n, n->v, n->adj, …
– (m>0) OUSNESS -> OUS callousness -> callous
– (m>0) ATIONAL -> ATE relational -> relate
• Step 3:
– (m>0) ICATE -> IC triplicate -> triplic
• Step 4:
– (m>1) AL -> retrieval -> retrieiv
– (m>1) ANCE -> allowance -> allow
• Step 5:
– (m>1) E -> probate -> probat
– (m > 1 and *d and *L) -> single letter controll -> control

Autres stemmers
• Lovins stemmer
http://www.comp.lancs.ac.uk/computing/research/stemming/general/lovins.htm
• Krovetz stemmer (R. Krovetz, 1993: "Viewing morphology as an

inference process," in R. Korfhage et al., Proc. 16th ACM SIGIR Conference,
Pittsburgh, June 27-July 1, 1993; pp. 191-202.)

Exemples d’outils TALN
http://www.atala.org/-Outils-pour-le-TAL-#type
ESSENTIAL (Résumeur de texte
Étiquetage, Traitement de corpus, Gestion de lexique, Autre (préciser)
MULTILINGUE en ligne en 20 langues)
Humanistique Étiquetage, Traitement de corpus, Gestion de lexique
DOSLoX & WinLoX Traitement de corpus, Extraction de termes
CooLoX Traitement de corpus
SIAC Autre (préciser)
LIA_PHON Étiquetage, Autre (préciser)
SyntEtiq Étiquetage, Analyse syntaxique
LEXTER Analyse syntaxique, Extraction de termes
MultAna Étiquetage
XLFG Analyse syntaxique
Lexed Gestion de lexique
TerminologyExtractor Extraction de termes
ACABIT Extraction de termes
DyALog Analyse syntaxique, Autre (préciser)
Sémiographe : fonctions syntaxiques Étiquetage, Analyse syntaxique, Autre (préciser)
Sémiographe : fonctions sémantiques Autre (préciser)
ANA Extraction de termes
Class4U Étiquetage, Traitement de corpus
Analyseur syntaxique du GREYC Analyse syntaxique, Traitement de corpus
CorTeCs Étiquetage
FASTER Extraction de termes
CORDIAL Universités ou Cordial Analyseur Étiquetage, Analyse syntaxique, Traitement de corpus, Extraction de termes

Exemple (tiré du livre de Croft et al.,)
• Originale
Document will describe marketing strategies carried out by U.S.
companies for their agricultural chemicals, …
• Porter
document describ market strategi carri compani agricultur chemic …
• Krovetz
document describe marcketing strategy carry company agriculture
chemical …

Étiquetage
• Associer aux mots leur catégorie morphosyntaxique
(nom, verbe, adjectif, etc.)
• Peut être utile en recherche d'information pour :

– Supprimer les mots inutiles
– Opérer des regroupements en termes complexes
– Rechercher des mots ambigus avec plus de précision
(vers, or, pouvoir…)
• L’outil le plus populaire
– TreeTagger : analyseur morpho-syntaxique
– http://txm.sourceforge.net/installtreetagger_fr.html

Récapitulation : La normalisation
• Des analyses différentes pour des besoins différents :
– Lemmatisation : pour rechercher/extraire de l'information, accéder au
sens d'un lemme en faisant abstraction des flexions.
– Racinisation (stemming) : pour agréger les dérivations morphologiques à
peu de frais, sans souci de la perte du sens et des lemmes initiaux.
– Étiquetage : pour appliquer des techniques de TAL sur les catégories
grammaticales plutôt que sur les mots eux-mêmes.
– Types de flexions, de dérivations : pour appliquer des traitements plus
fins en vue d'une analyse syntaxique et/ou sémantique.
• Des techniques assez bien maîtrisées : un pourcentage d'erreurs

faible mais difficilement compressible.

Collections Comment
de Sélection représenter
documents des termes l’index?
Normalisation
Corpus de
des termes
textes
Construction
de l’index
Chiraz Latiri 98
Construction de l’index : le fichier inverse
• Notion "classique" de l'index
• Un fichier inverse associe des index aux documents qui les
contiennent. Chaque document possède un identifiant unique.
– a ▸ d1, d2, d3, d4, d5...
– à ▸ d1, d2, d3, d4, d5...
– abaissa ▸ d3, d4...
– abaissable ▸ d5
– abandon ▸ d1, d5
– abandonna ▸ d2
– abasourdi ▸ d1
– …

Sac de mots
• Modèles « sac de mots » pour l’indexation et la recherche :
– On oublie l’ordre des mots
(« Jean est plus rapide que Marie » = « Marie est plus rapide que Jean »)
– On raisonne en termes de présence / absence des termes dans un
document, ou en terme de fréquence de ces termes

Index inversé
• Pour chaque terme T, on doit stocker la liste de tous les
documents qui contiennent T.
• Que doit-on utiliser: un tableau ou une liste?
Brutus 2 4 8 16 32 64 128
Calpurnia 1 2 3 5 8 13 21 34
Caesar 13 16

Index inversé
Les listes chainées sont généralement plus utilisées que les
tableaux :
– Allocation dynamique de l’espace mémoire
Brutus 2 4 8 16 32 64 128
Calpurnia 1 2 3 5 8 13 21 34
Caesar 13 16
Documents
Dictionnaire

Index inversé: Term
I
Doc #
1
1/ Extraire les mots de chaque document did

enact
1
1
julius 1
caesar 1
• Extraire les termes de chaque document dans un I 1
was 1
fichier (1 fichier par document) ou un fichier pour killed 1
plusieurs documents) i'
the
1
1
capitol 1
brutus 1
Ici un fichier pour les deux documents killed 1
me 1
so 2
Doc 1 Doc 2 let
it
2
2
be 2
I did enact Julius So let it be with with 2
Caesar I was killed Caesar. The noble

caesar
the
2
2
i' the Capitol; Brutus hath told you noble
brutus
2
2
Brutus killed me. Caesar was ambitious hath 2
told 2
you 2
caesar 2
was 2
ambitious 2
Chiraz Latiri 103
Index Inversé: Term Doc #
2/ Trier le fichier termes-documents ambitious

be
2
2
Term Doc #
brutus 1
I 1 brutus 2
did 1 capitol 1
enact 1 caesar 1
julius 1 caesar 2
Trier le fichier par caesar
I
1
1
caesar
did
2
1
ordre alphabétique des

was 1
enact 1
killed 1
hath 1
i' 1
I 1
termes et par document
the 1
capitol 1 I 1
brutus 1 i' 1
killed 1 it 2
me 1 julius 1
so 2 killed 1
let 2 killed 1
it 2
let 2
be 2
with 2
me 1
caesar 2 noble 2
the 2 so 2
noble 2 the 1
brutus 2 the 2
hath 2 told 2
told 2 you 2
you 2
was 1
caesar 2
was 2
was 2
ambitious 2 with 2
Chiraz Latiri 104
Index Inversé:
3/ Trier le fichier termes-documents
Term Doc #
Term Doc # Freq
ambitious 2 ambitious 2 1
be 2 be 2 1
• Pour chaque terme, brutus 1 brutus 1 1
brutus 2 brutus 2 1
– on dispose de la liste de capitol
caesar
1
1
capitol 1 1
documents qui le caesar

caesar
2
2
caesar
caesar
1
2
1
2
contient did
enact
1
1
did
enact
1
1
1
1
– Le nombre de documents hath
I
1
1
hath
I
2
1
1
2
comportant ce terme I
i'
1
1
i' 1 1
it 2 it 2 1
julius 1 julius 1 1
killed 1 killed 1 2
killed 1 let 2 1
let 2 me 1 1
me 1
noble 2 1
noble 2
so 2
so 2 1
the 1 the 1 1
the 2 the 2 1
told 2 told 2 1
you 2 you 2 1
was 1
was 1 1
was 2
was 2 1
with 2
with 2 1
Chiraz Latiri 105

Construction de l’index
Terme Fréquence Liste
Terme Id. Doc
Fichier inverse
(dictionnaire)
En RI,
"fréquence" =
….. ….. "nb d’occurrences"
Chiraz Latiri 106

Construction de l’index
Terme Fréquence Liste Term
ambitious
Doc #
2
Term Doc # Freq
ambitious 2 1
be 2 be 2 1
brutus 1 brutus 1 1
brutus 2 brutus 2 1
capitol 1 capitol 1 1
caesar 1 caesar 1 1
caesar 2 caesar 2 2
caesar 2 did 1 1
did 1 enact 1 1
enact 1 hath 2 1
hath 1 I 1 2
I 1 i' 1 1
I 1 it 2 1
i' 1 julius 1 1
it 2 killed 1 2
julius 1 let 2 1
killed 1 me 1 1
killed 1 noble 2 1
let 2 so 2 1
me 1
the 1 1
noble 2
the 2 1
so 2
told 2 1
the 1
you 2 1
the 2
was 1 1
told 2
was 2 1
you 2
with 2 1
was 1
was 2
with 2
Chiraz Latiri 107

Index Inversé: Fichier
documents
4/ Construire le dictionnaire et le « posting »
Term Doc # Freq
ambitious 2 1 Doc # Freq
be 2 1 Term N docs Tot Freq 2 1
brutus 1 1 ambitious 1 1 2 1
be 1 1 1 1
brutus 2 1
brutus 2 2 2 1
capitol 1 1
capitol 1 1 1 1
caesar 1 1
caesar 2 3 1 1
caesar 2 2
did 1 1 2 2
did 1 1 enact 1 1 1 1
enact 1 1 hath 1 1 1 1
hath 2 1 I 1 2 2 1
I 1 2 i' 1 1 1 2
i' 1 1 it 1 1 1 1
it 2 1 julius 1 1
2 1
julius 1 1 killed 1 2
1 1
killed 1 2 let 1 1
1 2
let 2 1 me 1 1
2 1
me 1 1 noble 1 1
1 1
noble 2 1 so 1 1
the 2 2 2 1
so 2 1
told 1 1 2 1
the 1 1
you 1 1 1 1
the 2 1
was 2 2 2 1
told 2 1
with 1 1 2 1
you 2 1
2 1
was 1 1 1 1
was 2 1 2 1
with 2 1 2 1
Chiraz Latiri 108

Recherche de groupes de mots
• Recherche sur Nicolas Sarkozy.
• On veut obtenir des textes contenant « Nicolas Sarkozy », et
non par exemple :
« Nicolas Bedos après son sketch sur DSK et Carla Bruni-Sarkozy. »
• De nombreuses requêtes sont implicitement des recherches de

groupes de mots, au moins en partie :
« Nicolas Sarkozy » Disneyland
• Nos index inversés <terme : documents> ne suffisent plus

La notion de n-grammes
• n-gramme : une sous-séquence de n éléments extraite d’une
séquence donnée. (cf. modèles de Markov)
Ici, n-grammes de mots
• uni-gramme : tous les mots
• bi-gramme : une sous-séquence de 2 éléments
• etc.
• Différent du groupe de mots d’un point de vue linguistique
• Pour la génération des n-grammes à partir d’un corpus de

textes, on utilise des outils de modélisation statistique de
langage tel que SRILM le plus utilisé
(http://www.speech.sri.com/projects/srilm/)

Index de bi-grammes (1/4)
• Indexer (en plus des mots simples) toutes les paires de termes
du texte.
Rien ne sert de Rien ne ne sert sert de de courir
courir il faut courir il il faut faut partir
partir à point partir à à point
Comment éviter d’indexer toutes les paires ?

• On considère donc chaque bi-gramme comme un terme du
dictionnaire
• Une requête sur un bi-gramme est immédiate

• Les requêtes plus longues (n-grammes, n > 2)
« pommes de terre »
Ä « pommes de » AND « de terre »

et ainsi de suite pour des requêtes encore plus longues…
Risque de faux positifs, pourquoi ?

• Autre solution plus économique, on supprime les « mots vides »
dans l’index et dans la requête
« pommes de terre »
Ä « pommes terre »
Encore un risque de faux positifs, pourquoi ?
• Ça ne suffit pas pour

« Université Paris-Sud 11 » ou
« Centre National de la Recherche Scientifique »

• Conduit à des faux positifs
• Dictionnaire beaucoup plus gros et index vite ingérable
• Impraticable pour n > 2
• si on a 200 000 termes uniques

• et si on considère les n-grammes de n = 1 à 5
• on obtient un dictionnaire de 3,2 × 1026
entrées !
• On peut utiliser des index bi-grammes dans certaines situations
ou pour certains groupes de mots, mais ce n’est pas la solution
standard pour la recherche de groupes de mots.
ð Index de positions

Deux lois statistiques au cœur
de la RI
Les statistiques au coeur de la RI
Chiraz Latiri 116

Loi de zipf : fréquence des termes
•Constat intuitif : Beaucoup de mots fréquents, et peu de mots
rares.
Loi de Zipf : la fréquence d’occurrence fc(m) d’un mot m dans
une collection de documents est inversement proportionnelle à
son rang.
•Le rang est obtenu lorsque l’on trie par ordre décroissant des
fréquences les mots de la collection.
Rappel,
"fréquence" =
µ "nb d’occurrences"
fréquence des termes fc(m) =
rang (m)
Termes Paramètre
triviaux rang des termes dépendant
du corpus
Termes
marginaux Chiraz Latiri 117
Tf : term frequency
• tf (fréquence des termes) : La fréquence d’un terme t est
un indicateur de son importance
• Intuitivement, plus un document contient d’occurrences
d’un terme t, plus il sera pertinent pour une requête
contenant ce terme t.
• Nombre d’occurrences du terme t dans le document d
= 1 + 𝑙𝑜 𝑔( 𝑓𝑟𝑒𝑞 𝑡, 𝑑 )
𝑓𝑟𝑒𝑞(𝑡, 𝑑)
=
𝑡𝑓 = 𝑓𝑟𝑒𝑞 𝑡, 𝑑 = 𝑚𝑎𝑥∀ " !∈$%&'( (𝑡 ) , 𝑑)
𝑓𝑟𝑒𝑞(𝑡, 𝑑)
=
∑∀ " !∈$𝑓𝑟𝑒𝑞(𝑡 ) , 𝑑)
Chiraz Latiri 118

Idf : inverse document frequency
• idf (Inverse Document Frequency) la fréquence inverse du terme
dans la collection, plus un terme est fréquent moins il est
discriminant.
• Les 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)
æ N = Nb _docs _dans _la_ collection ö æ N ö

ç
idf (t ) = logç ÷
÷ = logçç ÷÷
è df (t ) = Nb_ docs _contenant _t ø è df (t ) ø
Chiraz Latiri 119

Pondération tf×idf : poids d’un terme
• Le poids wi,j d’un terme ti dans un document dj est la
combinaison de ces deux métriques (tf×idf) pour
rendre compte du caractère discriminant d’un terme
dans un document.
• Le poids wi,j d’un terme ti dans un document dj :
– augmente avec sa fréquence dans le document
– augmente avec sa rareté dans la collection
wi , j = tf (ti , d j ) ´ idf (ti , d j )

Loi de Heaps pour la caractérisation du vocabulaire
• La taille du vocabulaire (V), appelé aussi Lexique, croît
exponentiellement en fonction du nombre de mots présents dans
un corpus (M).
• Loi de Heaps : Caractérise le nombre de mots distincts dans un

corpus
V = K x Mβ avec 0<β<1
• β dépend de la langue de M
• et K dépend des prétraitements appliqués à M pour extraire les
termes.

Modèles de RI
requête Processus RI
Requête
SRI
Langage de Traitement Traitement =
Indexation
requêtes Indexation
Appariement Index (mots clés) et
Liste de mots
Ranking organisation
physique
Fichier
inverse
Visualisation
Modèles de RI :
Vectoriel, probabiliste
Ranking dans le web
Modèle de RI : au cœur du SRI

Taxonomie des modèles en RI (1/2)

Taxonomie des modèles en RI (2/2)

Modèle Booléen

Le modèle booléen (1/2)
• 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

• Modèle de connaissances : T = {ti}, i ∈ [1, .. N]
–Termes ti qui indexent les documents
•Le modèle de documents (contenu) est une expression
booléenne dans la logique des propositions avec les ti
considérés comme des propositions :
•Un document D1 est représenté par une formule D1:
Une requête Q est représentée par une formule logique Q:

– Document D = Conjonction logique de termes (non
pondérés)
– Requête Q = expression booléenne de termes
– R(D, Q) = D ⊃ Q
Exemple
D1 = t1∧t2∧t3 (les 3 termes apparaissent dans D)
D2 = t2∧t3∧t4∧t5
Q = (t1∧t2)∨(t3∧t4)
D1 ⊃Q,
/ alors R(D1, Q) = 1.
mais D2 ⊃ Q, alors R(D2, Q) = 0.

La fonction de correspondance est basée sur l’implication logique
en logique des propositions :
Un document D répond à une requête Q si et seulement si
D⊃Q
Utilisation de déduction par :
Permet l’expression de requêtes complexes

Le modèle booléen : exemple
– D = t1∧t3
– Q = t1 ∨ t 4
Déduction :
x: t1∧t3 ⊃ t1 (équivalent à D ⊃ t1)
MP(x) : t1
y: t1 ⊃ t1 ∧t4 (équivalent à t1 ⊃ Q)
MP(y) : Q
Conclusion
Q est dérivable à partir de D donc le document D
répond à la requête.
Modèle booléen : exemple
Requête Q : (cyclisme OR natation) AND NOT dopage
Le document contient Pertinence
cyclisme natation cyclisme OR dopage NOT dopage du
natation 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
Chiraz Latiri 133

Remarques sur le modèle booléen
• Correspondance stricte : Oui/Non
– Q = t1 ⋀ t3 ⋀ t4
– D1 = t1 ⋀ t4 ,
Q ⊃ D1
– Le document D1 (représenté par D1) n’est pas pertinent pour la
requête Q (représentée par Q) d’après le modèle, alors qu’il contient
une description « proche » de la requête.
• Pas de distinction entre les documents pertinents

– Q = t1 ⋀ t4
– D2 = t1 ⋀ t4 ,
– D3 = t1 ⋀ t3 ⋀ t4 ⋀ t5 ⋀ t6 ⋀ t7
D1 ⊃ Q et D3 ⊃ Q
–Le document D2 (représenté par D2) est-il plus ou moins pertinent que D3 (représenté
par D3) pour la requête D (représentée par Q) ?

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

Modèle booléen étendu
• Idée : permettre l'utilisation des opérateurs logiques tout en
proposant une pertinence graduée
• Combinaison des modèles booléen et vectoriel
• Utilisation de la pondération des termes dans un document (tf.idf)
• Comme dans le modèle vectoriel, positionnement des documents
dans un espace euclidien dont les axes sont les termes de la
requête
• Calcul de la distance entre les coordonnées du document et :

– les coordonnées idéales (requête ET)
– les coordonnées nulles (requête OU)

Modèle booléen étendu : exemple (1/2)
Requête Q : t1 AND/OR t2 t (1,1)

2
Document D1 : ... t1 ... t2 ... 1
poids wD1,t1 = 0.75 y1 0,65

y2 0,5 D2 D1
poids wD1,t2 = 0.65
Document D2 : ... t1 ... t2 ... t

(0,0) 0,25 0,75 1 1
poids wD2,t1 = 0.25 x2 x1
poids wD2,t2 = 0.50
Chiraz Latiri 137

Modèle booléen étendu : exemple (2/2)
t1 OR t2 t1 AND t2
t (1,1) t (1,1)
2 2
1 1
y1 0,65 y1 0,65
D2 D2
y2 0,5 D1 y2 0,5 D1
x2 x1 x2 x1
t t
(0,0) 0,25 0,75 1 1
(0,0) 0,25 0,75 1 1
𝑥! + 𝑦! 1−𝑥 ! + 1−𝑦 !
𝑅𝑆𝑉 D, Q OR = 𝑅𝑆𝑉 D, Q AND = 1 −
2 2
Chiraz Latiri 138

Modèle booléen étendu : formule finale
'
!
∑!"#..% 𝑐&
𝑅𝑆𝑉 D, Q OR =
𝑚
'
!
∑!"#..% 1 − 𝑐 &
𝑅𝑆𝑉 D, Q AND = 1 −
𝑚
avec :
• c les coordonnées des mots
• m le nombre de termes
de la requête
p = 1 modèle booléen classique
•1≤p≤∞ p = 2 exemple précédent
Chiraz Latiri 139

Le modèle booléen pondéré : Bilan
o Extension du modèle booléen en intégrant des
pondérations (dénotant la représentativité d’un terme
pour un document).
o Modèle de connaissances : T = {ti}, i ∈[1, .. N]
Termes ti qui indexent les documents
oUn document D est représenté par :
• Une formule logique D (idem modèle booléen)
• Une fonction WD : T ⟶[0,1], qui pour chaque terme de T donne le
poids de ce terme dans D. Le poids vaut 0 pour un terme non présent
dans le document.
• Fonction de correspondance non binaire basée sur une similarité
inspiré de la logique floue
•Limitation : on ne tient pas compte dans la réponse de tous les termes
de la requête.

Modèles algébriques

Modèle vectoriel (1/4)
–Modèle de connaissances : V = {ti}, i ∈ [1, .. N]
–Tous les documents sont décrits suivant ce vocabulaire V
–Un document Di est représenté par un vecteur décrit dans
l’espace vectoriel IRN défini par V:

Di = wi ,1 , wi , 2 ,..., wi , j ,..., wi , N
avec wi,j le poids d’un terme dans un document
Une requête Q est représentée par un vecteur décrit dans
l’espace vectoriel IRN défini par V:

Q = wQ ,1 , wQ , 2 ,..., wQ , j ,..., wQ , N

Plus les vecteurs représentant les documents sont « proches »,

plus les documents sont similaires :
Plus l’angle est petit et

plus le document
correspond à la requête

Comment trouver les poids des termes

pour les documents ?
•Un document
–« Un violon est issu de bois précieux comme l’érable, palissandre,
l’ébène... »
•Pour indexer, la première idée est de compter
les mots les plus fréquents excepté les termes
non significatifs comme « de », « avec », «
comme »…
–« Un violon est composé de bois précieux comme l’érable, le
palissandre, l’ébène... »
–Les termes en rouge sont ceux qui sont sélectionnés

On tient compte du corpus (base de documents) entier,
un terme qui apparaît beaucoup ne discrimine pas
nécessairement les documents :
Terme fréquent dans tout le corpus Terme fréquent dans un seul document

Représentation
t3
Requête Q : t1 t2 t3 D
0.80
Q
Document D : … t1 … t3 …
Poids wD,t1 = 0.45

t1
0.45
Poids wD,t3 = 0.80
t2
Chiraz Latiri 146

Quelle mesure de similarité ? (1/2)
t2
D1
Cosinus
Q
𝑄:𝐷 ∑(!"# 𝑤!,* × 𝑤!,+
sim 𝑄, 𝐷 = =
𝑄×𝐷 ∑ 𝑤²!,* × ∑ 𝑤²!,+
D3 D2
D4
(Le produit scalaire avec

t1 normalisation de la longueur
des vecteurs)

Quelle mesure de similarité ? (2/2)
• Autres mesures :
– Dice 2 ∑ 𝑤!, ×𝑤!- 2∣𝐴∩𝐵 ∣
𝑅𝑆𝑉 Q, D = ∣ 𝐴 ∣+∣ 𝐵 ∣
∑ 𝑤!, + ∑ 𝑤!-
– Jaccard ∑ 𝑤!, ×𝑤!- ∣𝐴∩𝐵 ∣

𝑅𝑆𝑉 Q, D = ∣𝐴∪𝐵 ∣
∑ 𝑤!, + ∑ 𝑤!- − ∑ 𝑤!, ×𝑤!-
– Overlap ∑ 𝑤!, ×𝑤!- ∣𝐴∩𝐵 ∣

𝑅𝑆𝑉 Q, D = 𝑚𝑖𝑛 ∣ 𝐴 ∣, ∣ 𝐵 ∣
𝑚𝑖𝑛 ∑ 𝑤!- , ∑ 𝑤!,

Modèle vectoriel : Bilan
• On représente la requête comme un vecteur (quelle

pondération ?)
• On représente chaque document comme un vecteur
pondéré
• On calcule la similarité (cosinus par exemple) entre
chaque vecteur document et le vecteur requête
• On ordonne les résultats dans l’ordre inverse des scores
obtenus
• On fournit les k premiers résultats à l’utilisateur
Chiraz Latiri 149

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

Cours RI Latiri 2024 Ing Compressed

Transféré par

Droits d'auteur :

Formats disponibles

Cours RI Latiri 2024 Ing Compressed

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours RI Latiri 2024 Ing Compressed

Transféré par

Droits d'auteur :

Formats disponibles

Cours

Systèmes de Recherche d'Information

Utilisateur : Système de RI : l'outil qui doit

Information retrieval deals with the representation,

IR: The techniques of storing and recovering and often

Recherche d'Information Chiraz Latiri 11

• L'information, en revanche, est un ensemble de données

Recherche d'Information Chiraz Latiri 12

Recherche d'Information Chiraz Latiri 13

Big Growth Forecasted for Big Data

DC says 175 ZB will be created by 2025

Recherche d'Information Chiraz Latiri 14

•Facebook (2015) Statuts partagés chaque

Recherche d'Information Chiraz Latiri 15

Recherche d'Information Chiraz Latiri 16

Le problème n’est pas la disponibilité de

Sa sélection, son identification

Arriver à trouver au bon

Recherche d'Information Chiraz Latiri 18

• Recherche d’une information précise

Recherche d'Information Chiraz Latiri 19

Recherche d'Information Chiraz Latiri 20

• Nécessité de développer des systèmes automatisés efficaces

Recherche d'Information Chiraz Latiri 21

Recherche d'Information Chiraz Latiri 22

• Question-réponses (Query answering)

Recherche d'Information Chiraz Latiri 23

Recherche d'Information Chiraz Latiri 24

• Recherche agrégée (Aggregated search)

Recherche d'Information Chiraz Latiri 25

Recherche d'Information Chiraz Latiri 27

• Il ne peut pas exister de système de recherche d'information

• L'évaluation d'un système dépasse les aspects

Recherche d'Information Chiraz Latiri 28

• La recherche d'information est encore compliquée par le fait que :

Ø Il est compliqué de formuler son besoin d’information

Recherche d'Information Chiraz Latiri 29

Recherche d'Information Chiraz Latiri 30

Recherche d'Information Chiraz Latiri 31

Recherche d'Information Chiraz Latiri 33

Recherche d'Information Chiraz Latiri 35

– Comprendre le contenu vs. l’interptérer àAmbiguïté du langage naturel

Recherche d'Information Chiraz Latiri 37

Recherche d'Information Chiraz Latiri 38

Recherche d'Information Chiraz Latiri 39

• Plusieurs facteurs influencent la décision de l’utilisateur, tâche, le

• Pertinence par document

Recherche d'Information Chiraz Latiri 40

• Pertinence : capacité d’un système à répondre exactement à la requête

• pertinence utilisateur vs pertinence système

Recherche d'Information Chiraz Latiri 42

• L’enjeu de la RI : rapprocher tant que possible la pertinence système de la

Recherche d'Information Chiraz Latiri 43

Recherche d'Information Chiraz Latiri 45

Recherche d'Information Chiraz Latiri 46

• Un bon système de RI doit donner une évaluation de

Recherche d'Information Chiraz Latiri

Recherche d'Information Chiraz Latiri

• Pour arriver à une telle évaluation, on doit connaître