Information Retrieval

Ce matériel couvre les principes fondamentaux de la recherche d'information (RI) et son évaluation. Il s'adresse aux étudiants de niveau master en sciences des données et informatique, souhaitant comprendre les modèles, les collections de test, les mesures d'évaluation et les campagnes internationales d'évaluation en RI.

Modèle de Recherche d'Information (RI)

La recherche d'information repose sur un corpus de documents indexés, une base d'index, des requêtes formulées par l'utilisateur et une fonction de mise en correspondance f(q, δi) qui évalue la pertinence des documents δi par rapport à la requête q. L'utilisateur soumet une requête, le système retourne une liste de documents classés selon leur pertinence estimée.

Modèle TREC de la Recherche d'Information

Le modèle TREC (Text Retrieval Conference) est une référence pour l'évaluation des systèmes de RI. Il comprend :

• Un corpus de documents (➊)
• Un filtre pour sélectionner les documents pertinents (➋)
• Une base d'index construite à partir des documents (➌)
• Des besoins d'information exprimés sous forme de requêtes (➍ et ➎)
• Une fonction de mise en correspondance (➏)
• Une liste de résultats retournée par le système (➐)
• Des jugements de pertinence (➑)
• Une évaluation basée sur des mesures telles que la précision et le rappel (➒)

Exemple de document et requête dans la collection adi

Un document extrait de la collection adi contient des métadonnées et un texte décrivant des problèmes liés à la récupération documentaire, par exemple :

.I 17
.T
document recovery
.A
R. L. BIRCG
.W
the naming of journals and organizations : implications for
names are chosen for technical journals for societies often
incorporating factors which needlessly complicate filing and
recovery...

Une requête associée pourrait être :

.I 1
.W
What problems and concerns are there in making up descriptive titles?
What difficulties are involved in automatically retrieving articles from approximate titles?
What is the usual relevance of the content of articles to their titles?

Jugements de pertinence et expérimentations

Les jugements de pertinence indiquent quels documents sont pertinents pour chaque requête. Par exemple :

# qid docid relevance
1    17    1
1    46    1
1    62    1
2    12    1
2    71    1

Trois expérimentations sur la collection adi ont été réalisées avec différents systèmes (smart.nnn.nnn, smart.lic.ann, zettair), produisant des listes de documents classés avec des scores associés.

Évaluation d’un système de recherche d’information (SRI)

L’évaluation d’un SRI suppose que :

• La pertinence est binaire (un document est pertinent ou non)
• Le système est une boîte noire, sans interaction utilisateur

On évalue la capacité du système :

• À retourner les documents pertinents
• À ne pas retourner les documents non pertinents

Précision et rappel

Ces deux mesures fondamentales sont définies par :

Recall = |Rel ∩ Retr| / |Rel|

Precision = |Rel ∩ Retr| / |Retr|

où :

• Rel est l'ensemble des documents pertinents
• Retr est l'ensemble des documents récupérés

Mesure F (F-mesure)

La F-mesure est la moyenne harmonique pondérée de la précision P et du rappel R :

F = 1 / (α / P + (1 - α) / R)

ou, avec β² = (1 - α) / α :

F = (β² + 1) P R / (β² P + R)

En particulier, la F1-mesure (β = 1) est :

F1 = 2 P R / (P + R)

Courbes précision-rappel

Dans une liste de documents classés, la précision et le rappel sont calculés à chaque rang en considérant tous les documents récupérés jusqu’à ce rang.

Exemple de calcul pour une requête

Pour la requête 27, avec 33 documents pertinents et 66 documents récupérés classés par score décroissant, la précision et le rappel sont calculés à chaque rang :

• Rappel initial : 0/33 = 0%
• Précision après 2 documents : 2/3 = 66,7%
• Précision après 10 documents : 6/10 = 60%
• Rappel après 13 documents : 7/33 = 21,2%

Ces valeurs permettent de tracer la courbe précision-rappel.

Interpolation et extrapolation

Pour comparer plusieurs requêtes, on interpole les valeurs de précision entre les points de rappel observés et on extrapole jusqu’à 0% de rappel. On utilise généralement 11 points standards de rappel allant de 0% à 100% par pas de 10%.

Moyenne sur plusieurs requêtes

Les courbes précision-rappel peuvent être moyennées sur plusieurs requêtes pour évaluer globalement un système.

Outils et mesures d’évaluation

trec_eval est l'outil standard pour l’évaluation des systèmes de RI. Il fournit de nombreuses mesures :

• Précision à 5, 10, ..., 1000 documents
• R-Précision : précision au rang R, où R est le nombre de documents pertinents pour la requête
• bpref (mesure adaptée aux jugements incomplets)
• Reciprocal rank

Mean Average Precision (MAP)

La moyenne de la précision moyenne (MAP) est définie par :

AP(q) = (1 / |Relq|) ∑_{k=1}^{|Relq|} P(R_{qk})

MAP(Q) = (1 / |Q|) ∑_{q ∈ Q} AP(q)

où P(R_{qk}) est la précision au rang du k-ième document pertinent récupéré pour la requête q.

Collections de test historiques

Plusieurs collections de documents sont utilisées pour la recherche d'information :

• adi.all : 82 résumés d’articles de l’American Documentation Institute (domaine sciences de l’information)
• cacm.all.Z : 3204 documents avec titres et citations (informatique)
• cisi.all.Z : domaine sciences de l’information
• med.all.Z : domaine médical
• npl.dat.Z : électronique, informatique, physique
• time/doc.text.Z : actualités

Conférence TREC et campagnes d’évaluation

TREC est la campagne annuelle la plus connue pour l’évaluation des systèmes de RI depuis 1992. Le cycle comprend :

• Proposition de tâches et fourniture des documents et topics par le NIST
• Exécution des systèmes par les participants et production d’une liste de résultats (RUN)
• Évaluation des résultats par le NIST
• Atelier de restitution en novembre

Exemples de pistes TREC

• Adhoc (1992–1999), Robust (2003–2005)
• Interactive (1994–2005)
• Routing (1992–1997), Filtering (1995–2002), Spam (depuis 2005)
• Langues spécifiques : espagnol, chinois, multilingue
• Domaines spécialisés : légal, web, chimie, médical, courrier électronique
• Supports variés : OCR, parole, vidéo (VidTREC)

Questions liées aux collections de test

• Quels critères pour choisir les documents ?
• Représentativité des tâches
• Diversité des sujets et du vocabulaire
• Type de données : texte intégral, résumé, hyperliens, données sociales
• Nombre de topics nécessaires (au moins 25, idéalement 50)
• Identification des documents pertinents pour chaque topic

Caractéristiques des collections TREC

• Documents de journaux : AP Newswire, Wall Street Journal, Ziff-Davis Publishing, Federal Register, DOE abstracts
• Documents web : VLC, WT2G, WT10G, .GOV, W3C
• Collection Medline

Les tailles varient de quelques milliers à plusieurs millions de documents, avec des tailles de corpus allant de quelques gigaoctets à plusieurs téraoctets.

Exemple de document TREC

<DOC>
<DOCNO> WSJ870324-0001 </DOCNO>
<HL> John Blair Is Near Accord To Sell Unit, Sources Say </HL>
<DD> 03/24/87</DD>
<SO> WALL STREET JOURNAL (J) </SO>
<IN> REL TENDER OFFERS, MERGERS, ACQUISITIONS (TNM)
MARKETING, ADVERTISING (MKT) TELECOMMUNICATIONS,
BROADCASTING, TELEPHONE, TELEGRAPH (TEL) </IN>
<DATELINE> NEW YORK </DATELINE>
<TEXT>
John Blair & Co. is close to an agreement to sell its TV station
advertising representation operation and program production unit to an
investor group led by James H. Rosenfield, a former CBS Inc.
executive, industry sources said. Industry sources put the value of the
proposed acquisition at more than $100 million. ...
</TEXT>
</DOC>

Définition d’un topic

Un topic décrit un besoin d’information et donne des indications sur la pertinence. Il est construit par un évaluateur (assessor) qui identifie les documents pertinents pour ce topic.

<top>
<num> Number: 451
<title> What is a Bengals cat?
<desc> Description:
Provide information on the Bengal cat breed.
<narr> Narrative:
Item should include any information on the Bengal cat breed,
including description, origin, characteristics, breeding program,
names of breeders and catteries carrying bengals.
References which discuss bengal clubs only are not relevant.
Discussions of bengal tigers are not relevant.
</top>

La requête doit être construite à partir du topic.

Jugements de pertinence

Le jugement de pertinence est un processus long et coûteux. Par exemple, juger 800 000 documents à raison de 30 secondes par document nécessiterait plus de 900 jours ouvrés. TREC utilise la méthode de pooling pour limiter ce travail.

Questions importantes :

• Consistance : la pertinence est subjective et dépend de l’évaluateur
• Complétude : certains documents pertinents ne sont pas jugés et sont considérés comme non pertinents, ce qui peut pénaliser certains systèmes

Mesure bpref

La mesure bpref est conçue pour gérer les jugements incomplets :

bpref(q) = (1 / R) ∑_r (1 - |n classés avant r| / min(R, N))

où :

• R est le nombre de documents pertinents jugés
• N est le nombre de documents non pertinents jugés
• r est un document pertinent récupéré
• n est un document non pertinent parmi les premiers R documents non pertinents

Autres initiatives d’évaluation

• NTCIR (depuis 1997) pour les langues asiatiques
• CLEF (depuis 2000) pour l’évaluation multilingue et multidomaine
• INEX (depuis 2002) pour la RI structurée (documents XML), maintenant partie de CLEF
• FIRE (depuis 2008) pour les langues d’Asie du Sud

Glossaire des termes clés

• Corpus : ensemble de documents utilisés pour la recherche d’information.
• Indexation : processus de création d’une base d’index à partir des documents.
• Requête (query) : expression du besoin d’information par l’utilisateur.
• Base d’index : structure de données permettant d’accéder rapidement aux documents pertinents.
• Fonction de mise en correspondance f(q, δi) : fonction évaluant la pertinence d’un document δi par rapport à une requête q.
• Jugements de pertinence : annotations indiquant si un document est pertinent ou non pour une requête donnée.
• Précision : proportion de documents récupérés qui sont pertinents.
• Rappel : proportion de documents pertinents qui ont été récupérés.
• F-mesure : moyenne harmonique pondérée de la précision et du rappel.
• MAP (Mean Average Precision) : moyenne des précisions moyennes sur un ensemble de requêtes.
• Pooling : méthode pour sélectionner un sous-ensemble de documents à juger en combinant les résultats de plusieurs systèmes.
• bpref : mesure d’évaluation adaptée aux jugements incomplets.
• TREC : campagne annuelle d’évaluation des systèmes de recherche d’information.
• Topic : description formelle d’un besoin d’information utilisée pour l’évaluation.

Points clés à retenir

• La recherche d’information repose sur l’indexation, la formulation de requêtes et la mise en correspondance entre requêtes et documents.
• La campagne TREC fournit un cadre standardisé pour l’évaluation des systèmes de RI.
• Les mesures principales sont la précision, le rappel et la F-mesure, calculées sur des documents classés.
• La MAP est une mesure globale qui moyenne la précision moyenne sur plusieurs requêtes.
• Les jugements de pertinence sont coûteux et incomplets, ce qui nécessite des mesures adaptées comme bpref.
• Les collections de test historiques et les topics sont essentiels pour comparer les systèmes de manière objective.
• Des initiatives internationales complètent TREC pour des langues et domaines variés.