Le système SMART

Le système SMART est un système de RI expérimental. Il utilise le modèle vectoriel. Ce système a été construit entre 1968 et 1970 (la première version). Dans les années 1980, il a été réécrit et réorganisé. Cette nouvelle version est accessible gratuitement pour les recherches à l'adresse suivante: ftp://ftp.cs.cornell.edu/pub/smart/

Les travaux sur SMART ont été dirigés par Prof. G. Salton. Vous pouvez aussi trouver plus de descriptions sur ce système dans le livre suivant:

G. Salton, The SMART Retrieval System: Experiments in Automatic Document Processing, 1971, Prentice-Hall, (Z699.4 S2 S25)

Dans ce système, on peut remarquer les faits suivants:

Beaucoup de système de RI actuels ont grandement bénéficié de SMART. Certain ont repris les mêmes idées, certains d'autres sont développés directement à partir de SMART (en utilisant les codes de SMART). Si on analyse les moteurs de recherche disponibles sur l'Internet, on peut affirmer que SMART se compare très bien à ces moteurs, et dans beaucoup de cas, il fonctionne mieux (donne de meilleures réponses).

Le but de présenter ici le système SMART est de vous montrer un système de RI concret. Vous pouvez ainsi avoir une idée sur comment faire un système de RI concrètement. C'est aussi un cadre idéal pour vous montrer comment les techniques qu'on a présentées jusqu'à là peuvent s'enchaîner pour faire la RI.

Nous allons séparer les traitements en différents volets: indexation de document, indexation de requête, évaluation d'une requête, évaluation du système.

1. Indexation

Un document textuel peut contenir différents champs (appelés section dans SMART). Par exemple, dans un document, on peut distinguer le titre, l'auteur, la date, … et le corps. SMART offre la possibilité de traiter ces champs de façon différente. Par exemple, on peut indexer les noms d'auteur d'une manière différente qu'un texte dans la partie corps. La même chose pour la date. Dans une requête, on peut aussi avoir différents champs (sections).

L'indexation de document et de requête est illustrée dans la figure suivante:

La partie gauche correspond à l'indexation de document, et à droite, l'indexation de requête. Les deux traitements sont très similaires, à quelques détails près.

L'indexation de document

Reconnaissance de sections: Pour chaque document, le premier traitement est la séparation de champs (ou la reconnaissance de section). Cela se fait par des marqueurs qui annoncent le début de différentes sections. Par exemple, on peut avoir le marqueur <Title> pour annoncer que les lignes suivantes (jusqu'au prochain marqueur) correspondent au titre. <Date> marque une date, <Body> marque le début du corps du document - un plein-texte. Dans Smart, on peut définir un ensemble de marqueurs, et les actions d'indexation correspondantes. Par exemple, pour <Author>, on peut choisir une transformation spéciale pour les noms propres (transformer "Marc Gingras" en "Gingras, M.").

Tokenisation: Pour chaque section que SMART doit indexer, on doit d'abord la couper en mots. Cela consiste à reconnaître les séparateurs de mots, comme ",", ";", l'espace, etc. Le résultat de ce traitement est une suite de "tokens" ou mots (dans un sens large).

Stoplist: Les mots trouvés se compare avec la stoplist qui contient l'ensemble de mots qu'on ne veut pas garder comme index. Les autres mots sont soumis aux traitements suivants. Ce traitement est facultatif. On peut très bien décider que tous les mots sont significatifs, et doivent être gardés.

Lemmatisation: Ce traitement consiste à transformer une forme de mot en une certaine forme standard. Trois options sont offertes dans SMART: aucune lemmatisation, enlever le "s" à la fin, ou utiliser un arbre trie pour enlever la terminaison.

Après la lemmatisation, la forme standard obtenue est comparée avec un dictionnaire. Dans ce dictionnaire, on stocke tous les index, et à chaque index, on attribue un numéro d'identification. Ainsi, on a la structure suivante pour le dictionnaire:

<no_mot, nature, mot>

où no_mot est le numéro d'identification, mot est le mot correspondant, et nature désigne la nature de ce mot (par exemple, un chiffre, un mot normal, un nom propre, ou un mot vide).

La comparaison du résultat de la lemmatisation a pour le but d'obtenir le no_mot pour le mot. Si ce mot a été déjà rencontré (et donc stocké dans le dictionnaire), on reprend simplement son no_mot; sinon, le système crée un numéro automatiquement pour lui, et on ajoute une entrée dans le dictionnaire pour ce nouveau mot.

Statistique: Pour chaque mot, on doit faire la statistique de sa fréquence d'occurrence dans le document. Ainsi, à chaque occurrence d'un mot, on ajoute 1 dans sa fréquence.

Itérations: Dans la figure, il y a 3 itérations dans l'indexation de document: itération pour traiter chaque mot, itération pour chaque section, et itération pour chaque document.

Résultat: Le résultat d'indexation pour un document est un ensemble de <no_doc, ctype, no_mot, fréq>. Si le document contient 100 mot significatifs distincts, alors il y a 100 entrées colle cela.

Conversion du résultat: La conversion se fait seulement quand tous les documents ont été indexés. On peut faire deux sortes de conversions: convertir des vecteurs en fichier inversé, ou convertir les poids de termes. La première conversion consiste à trier à nouveau les résultats de l'indexation. Initialement, ils sont triés dans l'ordre croissant de no_doc. Dans un fichier inversé, ce sera trié dans l'ordre croissant de no_mot.

La seconde conversion consiste à transformer le poids a chaque terme dans chaque document en un nouveau poids. La conversion dans SMART se fait en 3 étapes:

  1. transformation de tf: on peut garder la fréquence obtenue comme la tf, ou bien on peut choisir à la normaliser en la divisant par la fréquence maximale dans le document, ou bien on peut la convertir en une valeur binaire (0 ou 1).
  2. La tf obtenue est de l'étape 1 est multiplié par idf. À ce stade, on peut choisir différentes façons de calculer idf. Par exemple, log(N/n), ou bien 1/n, etc.
  3. La troisième étape est la normalisation. On peut normaliser le poids obtenu en le divisant par la valeur maximale, ou bien par la formule Cosinus (c'est-à-dire 1/(S i pi2) 1/2).

À chaque étape, il y a de multiples choix. Pour en connaître plus, vous pouvez lire le fichier suivant:

http://www.iro.umontreal.ca/~nie/IFT6255/Doc_smart/howto/weight

Indexation de requête

Consultation du dictionnaire: Nous soulignons ici seulement la différence avec l'indexation de document.

Après la lemmatisation, le mot obtenu est comparé avec le dictionnaire pour connaître no_mot. Si ce mot n'existe pas dans le dictionnaire, on n'ajoute pas une nouvelle entrée dans le dictionnaire pour ce mot. Le mot est considéré "inconnu" par le système. En effet, il ne sert à rien d'ajouter ce mot inconnu dans le dictionnaire puisqu'il ne correspond à aucun document. On peut donc l'ignorer dans le modèle vectoriel. (Note: Dans le modèle boooléen, la traitement de mot inconnu doit être différent. Pourquoi?)

Conversion: On n'a pas à convertir une requête en forme de fichier inversé. La seule conversion utile pour une requête est la conversion de poids. Ici, on utilise la même méthode que pour le document. Si on utilise idf dans la second étape, les n et N sont aussi celles des documents. Donc, on utilise la même idf que pour les documents.

Itération: Dans la figure, on n'a pas inclus une itération pour traiter différentes requêtes. Cela est possible dans SMART. Par exemple, si on utilise SMART sur un corpus de test qui contient un ensemble de requ^etes, on peut très bien indexer toutes les requêtes. Mais dans une situation plus réelle, on traite généralement une requête à la fois.

2. évaluation d'une requête

L'évaluation d'une requête utilise le fichier inversé des documents et le résultat d'indexation de la requête qui est une suite de no_mot et de son poids. SMART utilise le produit interne comme similarité, c'est-à-dire:

Sim(d, q) = S i (pi * qi)

où pi et qi sont les poids d'un mot dans le document d et dans la requête q.

SMART implante un calcul global pour tous les document à la fois. L'algorithme est comme suit:

Initialiser Sim(dj, q) à 0 pour tout dj;

Pour chaque mot (no_moti) dans la requête q (avec poids qi) faire;

Trouver dans le fichier inversé tous les documents dj incluant ce mot, avec le poids pi;

Pour chaque dj dans cet ensemble faire:

Sim(dj, q) = Sim(dj, q) + pi * qi

À la fin de cet algorithme, on obtient la valeur de Sim pour chaque document. Cette méthode dévaluation globale est plus efficace qu'une évaluation séquentielle. Dans la méthode séquentielle, on doit comparer chaque document séparément avec la requête, et utiliser la formule théorique de Sim pour calculer la similarité. Le plus grand désavantage est qu'on doit considérer tous les documents, même ceux qui ne contiennent aucun mot de la requête. Dans l'évaluation globale utilisant le fichier inversé, on ne considère que les documents qui contiennent au moins un mot de la requête. Le nombre de documents à considérer est beaucoup réduit.

Dans SMART, il est cependant possible de choisir l'évaluation séquentielle, si on veut. Dans des cas normaux, cela ne fait aucune différence dans les réponses.

  • Évaluation du système
  • Pour évaluer la qualité d'un système, on doit tester ce système avec des corpus de test. Rappelons qu'un corpus de test contient 3 éléments: un ensemble de documents, un ensemble de requêtes, et le jugement de pertinence par un expert pour chaque requête (c'est-à-dire d'indiquer les documents du corpus qui sont pertinents à chaque requête).

    Le système à tester doit indexer les documents, les requêtes, et produire une liste de documents comme réponses pour chaque requête. On compare ensuite les réponses du système avec celle de l'expert pour évaluer la précision et le rappel.

    Plus souvent, on s'intéresse à connaître l'effet d'une technique (par exemple, la lemmatisation). Dans ce cas, on peut faire un système 1 sans cette technique et un autre système 2 avec cette technique. Les autres composantes des systèmes restent les mêmes. Si système 2 fonctionne mieux que Système 1, on peut alors conclure que la technique a un effet positive. En général, pour conclure que la technique a toujours un effet positive, il faut tester cela avec plusieurs corpus de test différents.

    On a déjà décrit la méthode utilisée pour obtenir les valeurs de précision-rappel. Elle consiste à avancer 1 à 1dans la liste de réponses du système, et on considère à chaque étape que les documents précédant ce point constituent la réponse du système. On évalue la précision et le rappel. Ainsi, on obtient un point de précision-rappel à chaque étape. Finalement, on obtient une courbe. La courbe moyenne est calculée sur toutes les requêtes du corpus de test. On peut aussi calculer la précision moyenne sur 11 points de rappel (0.0, 0.1, …, 1.0).

    SMART contient un ensemble de fonctions qui permettent d'évaluer la courbe précision-rappel pour un ou plusieurs systèmes et de les comparer. L'amélioration du Système 2 par rapport au Système 1 se calcule de la façon suivante:

    Amélioration = (P2 - P1) / P1

    où P1 et P2 sont les performances des systèmes 1 et 2 (qui peut être une précision, un rappel, ou la précision moyenne).

     

  • Rétroaction de la pertinence (Relevance feedback)
  • Cette technique a été inventé par Roccio, un membre dans l'équipe SMART. L'idée de la rétroaction est qu'après une première évaluation du système, l'utilisateur, en lisant les réponses, peut indiquer ceux qui sont pertinents, et ceux qui ne sont pas. Avec ces indications, le système peut reformuler la requête. La nouvelle requête peut devenir plus proche des documents pertinents et plus loin des documents non-pertinents.

    Pour mieux comprendre l'effet de la rétroaction, il faut mentionner que la requête d'un usager souvent ne décrit pas très bien son besoin d'information. Par exemple, un usager peut utiliser la requête "bases de données et gestion" pour décrire son besoin sur "l'utilisation de bases de données dans la gestion". Or, la requête donnée ne donne pas autant de précision. En effet, on peut très bien interpréter la requête comme "gestion de bases de données". A part l'interprétation ambiguë, on trouve plus souvent des requêtes dans lesquelles les concepts importants sont manquants. Ainsi, l'idée de la rétroaction est d'essayer de saisir plus précisément le besoin de l'usager à travers les documents qu'il a jugés. La nouvelle requête tente de se modifier pour devenir plus similaire aux documents pertinents, et moins similaires aux documents non-pertinents.

    La formule générale de réformulation de Roccio est la suivante:

    q' = a * q + b * Doc_Pert - g * Doc_Npert.

    où q et q' sont les vecteurs de l'ancienne et la nouvelle requêtes, Doc_Pert et Doc_Npert sont les centroïdes des documents pertinents et non-pertinents, a ,b et g sont les 3 paramètres qui règlent l'importance de chaque élément dans la nouvelle requête. Ces 3 paramètres sont fixes.

    Pour obtenir la nouvelle requête q', on doit d'abord calculer les deux centroïdes. Ce sont les vecteurs moyens de tous les documents pertinents et non-pertinents jugés par l'usager. Ensuite, pour chaque terme (dimension dans l'espace vectoriel), le nouveau poids du terme est

    p' = a * p + b * ppert - g * pnpert

    En pratique, on n'a pas besoin de calculer cela pour tous les termes de l'espace vectoriel, mais seulement les termes concernés (qui apparaissent dans q, Doc_Pert ou Doc_Npert).

    Par exemple, soit un espace vectoriel à 5 dimensions. La requête initiale est la suivante:

    t1 t2 t3 t4 t5

    q = <1, 2, 0, 1, 0>

    Les 2 document pertinents que l'usager a jugés sont:

    dp1= <2, 0, 1, 1, 0>

    dp2= <1, 1, 1, 0, 0>

    et les document non-pertinents:

    dn1= <0, 1, 0, 1, 1>

    dn2= <0, 1, 0, 2, 0>

    Les vecteurs centroïdes sont:

    dp= <1.5, 0.5, 1, 0.5, 0>

    dn= <0, 1, 0, 1.5, 0.5>

    Soit a =1, b =0.5, g =0.5, la nouvelle requête est la suivante:

    q' = <1.75, 1.75, 0.5, 0.5, -0.25>

    Si on compare q' avec q, on voit que le poids de t1 a beaucoup augmenté. La raison est que dans les deux documents pertinents, t1 a un poids fort; tandis que dans les documents non-pertinents, ses poids sont nuls. Donc, on peut croire que les documents pertinents pour l'usager doit avoir un poids fort sur t1. Par contre, le poids de t4 a diminué de 1 à 0.5. C'est parce que t4 apparaît plus dans les documents non-pertinents que dans les documents pertinents. Ainsi, son apparition est vue plutôt comme un signe de non-pertinence. Donc, son poids dans la nouvelle requête est diminué. Il y a aussi un poids négatif dans q'. Ceci signifie que l'apparition de t5 est un signe totalement négatif. Donc, quand il apparaît dans un document, on diminue la similarité du document.

    Globalement, on peut voir le changement dans la nouvelle requête comme le changement dans la direction des documents non-pertinents vers les documents pertinents. On peut illustrer cela comme la figure suivante:

    Dans cette figure, q et q' correspond à tous les documents que q et q' permettent de retrouver comme réponse. Les points noirs corresponds aux centroïdes des documents pertinents et non-pertinents jugés par l'usager. La flèche entre eux illustre la direction de changement qu'on apporte à la requête. Ainsi, la nouvelle requête est changée de l'ancienne requête dans cette direction. L'effet est donc de s'approcher plus aux documents pertinents et de s'éloigner des documents non-pertinents.

    Ici, on fait l'hypothèse que les documents pertinents seront similaires à ceux jugés par l'usager, ainsi que pour les documents non-pertinents. Dans ce cas, on peut espérer retrouver plus de documents pertinents et moins de documents non-pertinents avec la nouvelle requête. Dans le cas ou il n'y a pas cette similarité, l'effet sera imprévisible. En pratique, il existe une certaine similarité au sein des documents pertinents même si on ne peut pas en dire autant pour les documents non-pertinents. Ainsi, certains suggèrent de définir g =0 pour ne pas utiliser les documents nopn-pertinents comme contre-exemples.

    La définition des 3 paramètres dépende du corpus et de la précision de la requête de l'usager. En général, on définit un a plus grand que b .

    Il n'est pas nécessaire non plus de tenir compte de tous les termes dans les documents pertinents et non-pertinents. En effet, beaucoup de termes peuvent apparaître dans ces documents par hasard. Ainsi, on utilise généralement les termes les plus forts de ces documents pour réformuler la requête (par exemple, 100 termes les plus forts).

     

  • Illustration de fonctionnement de SMART par des exemples
  • Ces exemples sont obtenus avec le corpus de test CACM.

    1. Exemple de document (1er document)

    .I 1

    .T

    Preliminary Report-International Algebraic Language

    .B

    CACM December, 1958

    .A

    Perlis, A. J.

    Samelson,K.

    .N

    CA581203 JB March 22, 1978 8:28 PM

    .X

    100 5 1

    123 5 1

    164 5 1

    1 5 1

    1 5 1

    1 5 1

    205 5 1

    210 5 1

    214 5 1

    1982 5 1

    398 5 1

    642 5 1

    669 5 1

    1 6 1

    1 6 1

    1 6 1

    1 6 1

    1 6 1

    1 6 1

    1 6 1

    1 6 1

    1 6 1

    1 6 1

    165 6 1

    196 6 1

    196 6 1

    1273 6 1

    1883 6 1

    324 6 1

    43 6 1

    53 6 1

    91 6 1

    410 6 1

    3184 6 1

     

    2. Une partie de trace d'exécution d'indexation des documents:

    ...

    Commentaire

    Trace: entering index_coll

    On commence l'indexation

    Trace: entering next_vecid

    Générer le prochain no_doc

    1

     

    Trace: leaving next_vecid

     

    Trace: entering pp_generic

    Reconnaissance des sections

    .- --- 1 /home/vautour3/nie/Smart/colls/cacm/ cacm.all 0 401

    L'endroit du doc. original

     

    *** d'ici

    .t 0 53

    Première section - titre

       

    Preliminary Report-International Algebraic Language

     
       

    .a 53 80

    Deuxième section - auteur

       

    Perlis, A. J.

     

    Samelson,K.

    *** jusqu'à là = document orig.

    Trace: leaving pp_generic

     

    Trace: entering add_textloc

    Ajouter le texte original dans une BD

    Doc textloc 1

     

    Title 'Preliminary Report-International Algebraic Language '

     

    File '/home/vautour3/nie/Smart/colls/cacm/cacm.all'

     

    0 401 0

     

    Trace: leaving add_textloc

     

    Trace: entering index_pp

     

    Trace: entering token_sect

    Tokenisation des sections

    2 '

     

    ' -6

     

    2 'Preliminary' -2

     

    2 ' ' -5

     

    2 'Report' -2

     

    2 '-' -4

     

    2 'International' -2

    Les mots reconnus

    2 ' ' -5

     

    2 'Algebraic' -2

     

    2 ' ' -5

     

    2 'Language' -2

     

    2 '

     

    ' -6

     

    Trace: leaving token_sect

     

    Trace: entering full_all_parse

     

    Trace: entering stop_dict

    Filtrage de stoplist

    0

     

    Trace: leaving stop_dict

     

    Trace: entering remove_s

    Lemmatisation (enlever "s")

    preliminary

    Le mot

    Trace: leaving remove_s

     

    Trace: entering tokcon_dict

     

    13644

    Le no_mot

    Trace: leaving tokcon_dict

     

    … Continuer sur les autres mots

    Trace: leaving tokcon_dict

     

    13644 0 0 0 1 0.000000

     

    4975 0 0 0 3 0.000000

    résultat

    10955 0 0 0 5 0.000000

     

    9280 0 0 0 7 0.000000

     

    15587 0 0 0 9 0.000000

     

    Trace: leaving full_all_parse

     

    Trace: entering token_sect

    Traitements pour la 2ième section

    0 '

     

    ' -6

     

    0 'Perlis' -2

     

    0 ',' -4

     

    0 ' ' -5

     

    0 'A' -2

     

    0 '.' -4

     

    0 ' ' -5

     

    0 'J' -2

     

    0 '.' -4

     

    0 '

     

    ' -6

     

    0 'Samelson' -2

     

    0 ',' -4

     

    0 'K' -2

     

    0 '.' -4

     

    0 '

     

    ' -6

     

    Trace: leaving token_sect

     

    Trace: entering name_parse

     

    Perlis , A J

     

    perlis, a

     

    Trace: entering tokcon_dict

     

    15679

     

    Trace: leaving tokcon_dict

     

    Samelson , K

     

    samelson, k

     

    Trace: entering tokcon_dict

     

    4691

     

    Trace: leaving tokcon_dict

     

    15679 0 0 0 9 0.000000

     

    4691 0 0 1 14 0.000000

     

    Trace: leaving name_parse

     

    Trace: entering makevec

    construire le vecteur du doc.

    1 0 4691 1.000000

     

    1 0 4975 1.000000

     

    1 0 9280 1.000000

     

    1 0 10955 1.000000

     

    1 0 13644 1.000000

     

    1 0 15587 1.000000

     

    1 0 15679 1.000000

     

    Trace: leaving makevec

     

    Trace: entering weight_tri

    On peut éventuellement

    1 0 4691 1.000000

    Transformer les poids

    1 0 4975 1.000000

    (n'est pas faite ici)

    1 0 9280 1.000000

     

    1 0 10955 1.000000

     

    1 0 13644 1.000000

     

    1 0 15587 1.000000

     

    1 0 15679 1.000000

     

    Trace: leaving weight_tri

     

    1 0 4691 1.000000

     

    1 0 4975 1.000000

     

    1 0 9280 1.000000

     

    1 0 10955 1.000000

     

    1 0 13644 1.000000

     

    1 0 15587 1.000000

     

    1 0 15679 1.000000

     

    Trace: leaving index_pp

     

    Trace: entering store_vec_aux

     

    Trace: entering vec_inv

     

    Trace: leaving vec_inv

     

    Trace: leaving store_vec_aux

     

    Trace: entering next_vecid

    On continue sur le 2ième doc.

    2

     

    Trace: leaving next_vecid

    Trace: entering pp_generic

     

    .- --- 2 /home/vautour3/nie/Smart/colls/cacm/ cacm.all 401 572

     

     

    3. Le dictionnaire créé:

    No_mot    Nature   	Mot		
    0       -1      NOT-a-TOKEN
    1       1       written
    2       2       derivable
    3       3       conveying
    4       0       dow, j
    5       5       inv
    6       6       avint
    7       7       usec
    8       8       154
    9       0       lee, y
    10      10      noncomputational
    11      11      475
    12      12      accurate
    14      14      a440
    15      15      tagged
    19      19      add
    20      0       robinson, h
    25      25      inferior
    27      0       blair, c
    28      28      extracted
    29      29      incorporate
    30      30      stage2
    

    4. Résultat de l'indexation des documents:

    no_doc, ctype  no_mot      fréq      mot (*non stocké dans le vecteur)
    1       0       4691     1.00000        samelson, k
    1       0       4975     1.00000        report
    1       0       9280     1.00000        algebraic
    1       0       10955    1.00000        international
    1       0       13644    1.00000        preliminary
    1       0       15587    1.00000        language
    1       0       15679    1.00000        perlis, a
    2       0       304      1.00000        root
    2       0       1811     1.00000        computer
    2       0       4448     1.00000        repeated
    2       0       5083     1.00000        digital
    2       0       6845     1.00000        sugai, i
    2       0       16216    1.00000        subtraction
    2       0       17345    1.00000        extraction
    3       0       2426     1.00000        matrix
    3       0       5152     1.00000        program
    3       0       6450     1.00000        scheme
    3       0       11219    1.00000        department
    3       0       12180    1.00000        technique
    3       0       13137    1.00000        friedman, m
    4       0       1811     1.00000        computer
    4       0       2303     1.00000        terminology
    4       0       4696     1.00000        glossary
    4       0       5376     1.00000        programming
    4       0       12786    1.00000        engineering
    

    5. Fichier inversé

    no_doc  ctype  no_mot    fréq		
    282     0       1       1.000000
    282     0       1       1.000000
    282     0       1       1.000000
    321     0       1       1.000000
    321     0       1       1.000000
    321     0       1       1.000000
    597     0       1       1.000000
    597     0       1       1.000000
    597     0       1       1.000000
    728     0       1       1.000000
    728     0       1       1.000000
    728     0       1       1.000000
    847     0       1       1.000000
    847     0       1       1.000000
    847     0       1       1.000000
    942     0       1       1.000000
    942     0       1       1.000000
    942     0       1       1.000000
    971     0       1       1.000000
    971     0       1       1.000000
    971     0       1       1.000000
    1117    0       1       1.000000
    ...
    1768    0       2       1.000000
    1768    0       2       1.000000
    1768    0       2       1.000000
    ...
    

    6. Conversion de poids (convertir en ltc- une variante de tf*idf)

    1       0       4691     0.52487        samelson, k
    1       0       4975     0.26250        report
    1       0       9280     0.30023        algebraic
    1       0       10955    0.45385        international
    1       0       13644    0.38392        preliminary
    1       0       15587    0.12003        language
    1       0       15679    0.44462        perlis, a
    2       0       304      0.26528        root
    2       0       1811     0.06574        computer
    2       0       4448     0.44893        repeated
    2       0       5083     0.21378        digital
    2       0       6845     0.59289        sugai, i
    2       0       16216    0.40789        subtraction
    2       0       17345    0.40023        extraction
    3       0       2426     0.25753        matrix
    3       0       5152     0.11481        program
    3       0       6450     0.30950        scheme
    3       0       11219    0.50649        department
    3       0       12180    0.16664        technique
    3       0       13137    0.73512        friedman, m
    4       0       1811     0.09906        computer
    4       0       2303     0.54341        terminology
    4       0       4696     0.65775        glossary
    4       0       5376     0.16239        programming
    4       0       12786    0.48568        engineering
    

    7. Indexation de requête

    Requêtes originales:

    .I 1

    .W

    What articles exist which deal with TSS (Time Sharing System), an

    operating system for IBM computers?

    .N

    1. Richard Alexander, Comp Serv, Langmuir Lab (TSS)

    .I 2

    .W

    I am interested in articles written either by Prieve or Udo Pooch

    .A

    Prieve, B.

    Pooch, U.

    .N

    2. Richard Alexander, Comp Serv, Langmuir Lab (author = Pooch or Prieve)

    Résultats:

    1 0 1089 1.00000 time

    1 0 1811 1.00000 computer

    1 0 2997 1.00000 sharing

    1 0 4682 1.00000 tss

    1 0 5328 1.00000 deal

    1 0 7034 1.00000 ibm

    1 0 10177 1.00000 exist

    1 0 15858 1.00000 article

    1 0 17201 1.00000 operating

    1 0 17338 2.00000 system

    2 0 1 1.00000 written

    2 0 6055 1.00000 prieve, b

    2 0 9914 1.00000 interested

    2 0 13926 1.00000 pooch, u

    2 0 15858 1.00000 article

     

    8. Évaluation des requêtes

    On demande à SMART de trouver les meilleur 20 documents comme réponse. Si on utilise la fréquence comme poids dans les documents et les requêtes, les réponses sont:

    no_req no_doc rang pert. sim

    1 1844 1 0 0 0 147.0000

    1 1680 2 0 0 0 102.0000

    1 1938 3 0 0 0 99.0000

    1 1591 4 0 0 0 96.0000

    1 1747 5 0 0 0 90.0000

    1 2344 6 0 0 0 84.0000

    1 2319 7 0 0 0 84.0000

    1 2535 8 0 0 0 78.0000

    1 2188 9 0 0 0 78.0000

    1 1719 10 0 0 0 78.0000

    1 2951 11 0 0 0 75.0000

    1 1827 12 0 0 0 75.0000

    1 2812 13 0 0 0 72.0000

    1 2629 14 0 0 0 72.0000

    1 2379 15 0 0 0 72.0000

    1 2151 16 0 0 0 72.0000

    1 2740 17 0 0 0 69.0000

    1 1908 18 0 0 0 69.0000

    1 1572 19 1 0 0 69.0000

    1 2542 20 0 0 0 63.0000

    Si on utilise le poids converti en ltc:

    1 1410 1 1 0 0 0.1714

    1 1938 2 0 0 0 0.1652

    1 2574 3 0 0 0 0.1417

    1 2319 4 0 0 0 0.1349

    1 2371 5 0 0 0 0.1084

    1 1657 6 0 0 0 0.1068

    1 1333 7 0 0 0 0.1050

    1 1461 8 0 0 0 0.1042

    1 1280 9 0 0 0 0.1027

    1 1071 10 0 0 0 0.1011

    1 1572 11 1 0 0 0.0983

    1 1827 12 0 0 0 0.0920

    1 1752 13 0 0 0 0.0891

    1 2069 14 0 0 0 0.0858

    1 971 15 0 0 0 0.0845

    1 3069 16 0 0 0 0.0826

    1 2036 17 0 0 0 0.0811

    1 2340 18 0 0 0 0.0798

    1 2317 19 0 0 0 0.0791

    1 2151 20 0 0 0 0.0777

    Si on compare juste ces deux résultats, on voit qu'avec ltc, la performance est meilleur. Avec la fr"equence, on ne trouve qu'un seul document pertinent au 19ième rang. Avec ltc, on obtient deux: au 1er rang et au 11ième rang.

     

    9. Évaluation du système

    Les données ci-dessus donnent les performances des systèmes utilisant la fréquence et ltc comme poids:

    1. /home/vautour3/nie/Smart/indexed_colls/cacm/tr.nnn
    2. /home/vautour3/nie/Smart/indexed_colls/cacm/tr.ltc
    
    Run number:          1        2    
    Num_queries:         52       52
    Total number of documents over all queries
        Retrieved:     1040     1040
        Relevant:       796      796
    Rel_ret:        140      259
        Trunc_ret:      993      945
    Recall - Precision Averages:
        at 0.00       0.4755   0.7126 
        at 0.10       0.3232   0.6487 
        at 0.20       0.2019   0.4920 
        at 0.30       0.1677   0.3894 
        at 0.40       0.0905   0.2919 
        at 0.50       0.0810   0.2010 
        at 0.60       0.0542   0.1717 
        at 0.70       0.0365   0.1289 
        at 0.80       0.0365   0.1015 
        at 0.90       0.0288   0.0823 
        at 1.00       0.0288   0.0823 
    Average precision for all points
       11-pt Avg:     0.1386   0.3002 
        % Change:              116.6 
    Average precision for 3 intermediate points (0.20, 0.50, 0.80)
        3-pt Avg:     0.1065   0.2649 
        % Change:              148.8 
    
    Recall:
        Exact:        0.2734   0.4486
        at  5 docs:   0.1250   0.2485
        at 10 docs:   0.1904   0.3378
        at 15 docs:   0.2310   0.4065
        at 30 docs:   0.2734   0.4486
    Precision:
        Exact:        0.1346   0.2490
        At  5 docs:   0.2000   0.4154
        At 10 docs:   0.1635   0.3423
        At 15 docs:   0.1474   0.2821
        At 30 docs:   0.0897   0.1660
    Truncated Precision:
        Exact:        0.1596   0.3140
        At  5 docs:   0.2163   0.4538
        At 10 docs:   0.1846   0.3938
        At 15 docs:   0.1712   0.3419
        At 30 docs:   0.1160   0.2368
    

    Cette comparaison montre que le poids ltc fonctionne beaucoup mieux que la fréquence (une amélioration de 118.1% sur la précision moyenne).

    Dans les courbes précision-rappel, on remarque qu'entre rappel 0.20 et 0.30 pour le système 1, et entre 0.30 et 0.40 pour le système 2, la précision diminue beaucoup. Cela est du à la limite de 20 documents par requête qu'on a imposée. Si on allonge cette limite, soit ce saut important viendra plus tard, soit il disparaît (presque).

     

    10. Rétroaction de pertinence

    On peut simuler l'effet de rétroaction dans SMART. Cela se fait en deux étapes:

    1. trouver un ensembles de documents et les considère comme les documents que l'usager aurait jugé (pertinent ou non-pertinent).
    2. Lancer une recherche en mode feedback qui crée d'abord une nouvelle requête, puis l'évalue.

    Comme exemple, on montre ici le feedback suivant:

    On utilise les 10 premiers documents de la première recherche avec les requêtes originales comme des documents jugés par l'usager. On ne tient compte que des documents pertinents. Parmi les documents pertinents, on retient juste les 5 termes les plus forts. Les paramètres: a =1.0, b =0.5 (et g =0).

    La comparaison entre le système sans feedback et avec feedback:

    1. /home/vautour3/nie/Smart/indexed_colls/cacm/tr.ltc
    2. /home/vautour3/nie/Smart/indexed_colls/cacm/tr.fdbk.ltc
    
    Run number:          1        2    
    Num_queries:         52       52
    Total number of documents over all queries
        Retrieved:     1040     1040
        Relevant:       796      796
        Rel_ret:        259      298
        Trunc_ret:      945      941
    Recall - Precision Averages:
        at 0.00       0.7126   0.9097 
        at 0.10       0.6487   0.8286 
        at 0.20       0.4920   0.6316 
        at 0.30       0.3894   0.4815 
        at 0.40       0.2919   0.3591 
        at 0.50       0.2010   0.2293 
        at 0.60       0.1717   0.1873 
        at 0.70       0.1289   0.1582 
        at 0.80       0.1015   0.1303 
        at 0.90       0.0823   0.0848 
        at 1.00       0.0823   0.0848 
    Average precision for all points
       11-pt Avg:     0.3002   0.3714 
        % Change:               23.7 
    Average precision for 3 intermediate points (0.20, 0.50, 0.80)
        3-pt Avg:     0.2649   0.3304 
        % Change:               24.7 
    
    Recall:
        Exact:        0.4486   0.4955
        at  5 docs:   0.2485   0.2808
        at 10 docs:   0.3378   0.3742
        at 15 docs:   0.4065   0.4377
        at 30 docs:   0.4486   0.4955
    Precision:
        Exact:        0.2490   0.2865
        At  5 docs:   0.4154   0.5115
        At 10 docs:   0.3423   0.3885
        At 15 docs:   0.2821   0.3179
        At 30 docs:   0.1660   0.1910
    Truncated Precision:
        Exact:        0.3140   0.3540
        At  5 docs:   0.4538   0.5500
        At 10 docs:   0.3938   0.4419
        At 15 docs:   0.3419   0.3804
        At 30 docs:   0.2368   0.2643