Recherche approchée

Supports complémentaires:

• Un cours complet en ligne (en anglais) et accompagné d’un ouvrage de référence : http://www-nlp.stanford.edu/IR-book/. Certaines parties du cours empruntent des exemples à ce livre.

S1: introduction à la recherche d’information

Supports complémentaires:

• Présentation: Introduction à la recherche d’information

• Vidéo de la session Introduction RI - principes

Qu’est ce que la recherche d’information

La Recherche d’Information (RI, Information Retrieval, IR en anglais) consiste à trouver des documents peu ou faiblement structurés, dans une grande collection, en fonction d’un besoin d’information. Le domaine d’application le plus connu est celui de la recherche « plein texte ». Étant donné une collection de documents constitués essentiellement de texte, comment trouver les plus pertinents en fonction d’un besoin exprimé par quelques mots-clés? La RI développe des modèles pour interpréter les documents d’une part, le besoin d’information d’autre part, en vue de faire correspondre les deux, mais aussi des techniques pour calculer des réponses rapidement même en présence de collections très volumineuses. Enfin, des systèmes (appelés « moteurs de recherches ») fournissent des solutions sophistiquées prêtes à l’emploi.

La RI a pris une très grande importance, en raison notamment de l’émergence de vastes sources de documents que l’on peut agréger et exploiter (le Web bien sûr, mais aussi les systèmes d’information d’entreprise). Les techniques utilisées ont également beaucoup progressé, avec des résultats spectaculaires. La RI est maintenant omniprésente dans beaucoup d’environnements informatiques, et notamment:

• La recherche sur le Web, utilisée quotidiennement par des milliards d’utilisateurs,

• La recherche de messages dans votre boîte mail,

• La recherche de fichiers sur votre ordinateur (Spotlight),

• La recherche de documents dans une base documentaire, publique ou privée,

Ce chapitre introduit ces différents aspects en se concentrant sur la recherche d’information appliquée à des collections de documents structurés, comprenant des parties textuelles importantes.

Précision et rappel

Comme le montre la définition assez imprécise donnée en préambule, la recherche d’information se donne un objectif à la fois ambitieux et relativement vague. Cela s’explique en partie par le contexte d’utilisation de ces systèmes. Avec une base de données classique, on connaît le schéma des données, leur organisation générale, avec des contraintes qui garantissent qu’elles ont une certaine régularité. En RI, les données, ou « documents », sont souvent hétérogènes, de provenances diverses, présentent des irrégularités et des variations dues à l’absence de contrainte et de validation au moment de leur création. De plus, un système de RI est souvent utilisé par des utilisateurs non-experts. À la difficulté d’interpréter le contenu des documents et de le décrire s’ajoute celle de comprendre le « besoin », exprimé souvent de manière très partielle.

D’une certaine manière, la RI vise essentiellement à prendre en compte ces difficultés pour proposer des réponses les plus pertinentes possibles. La notion de pertinence est centrale ici: un document est pertinent s’il satisfait le besoin exprimé. Quand on utilise SQL, on considère que la réponse est toujours exacte car définie de manière mathématique (en fonction de l’état de la base). En RI, on ne peut jamais considérer qu’un résultat, constitué d’un ensemble de documents, est exact, mais on mesure son degré de pertinence (c’est-à-dire les erreurs du système de recherche) en distinguant:

• les faux positifs: ce sont les documents non pertinents inclus dans le résultat; ils ont été sélectionnés à tort. En anglais, on parle de false positive.

• les faux négatifs: ce sont les documents pertinents qui ne sont pas inclus dans le résultat. En anglais, on parle de false negative.

Les documents pertinents inclus dans le résultat sont appelés les vrais positifs, les documents non pertinents non inclus dans le résultat sont appelés les vrais négatifs. On le voit à ce qui vient d’être dit : on emploie le terme positif pour désigner ce qui a été ramené dans le résultat de recherche. À l’inverse, les documents qui sont négatifs ont été laissés de côté par le moteur de recherche au moment de faire correspondre des documents avec un besoin d’information. Et l’on désigne par vrai ce qui a été bien classé (dans le résultat ou hors du résultat).

Deux indicateurs formels, basés sur ces notions, sont couramment employés pour mesurer la qualité d’un système de RI.

La précision

La précision mesure la proportion des vrais positifs dans le résultat r. Si on note respectivement \(t_p(r)\) et \(f_p(r)\) le nombre de vrais et de faux positifs dans r (de taille \(|r|\)), alors

\[\text{précision} = \frac{t_p(r)}{t_p(r) + f_p(r)} = \frac{t_p(r)}{|r|}\]

Une précision de 1 correspond à l’absence totale de faux positifs. Une précision nulle indique un résultat ne contenant aucun document pertinent.

Le rappel

Le rappel mesure la proportion des documents pertinents qui sont inclus dans le résultat. Si on note \(f_n(r)\) le nombre de documents faussement négatifs, alors le rappel est:

\[\frac{t_p(r)}{t_p(r) + f_n(r)}\]

Un rappel de 1 signifie que tous les documents pertinents apparaissent dans le résultat. Un rappel de 0 signifie qu’il n’y a aucun document pertinent dans le résultat.

La truefalsepositivenegative illustre (en anglais) ces concepts pour bien distinguer les ensembles dont on parle pour chaque requête de recherche et les mesures associées.

Vrai, faux, positifs, négatifs.

Ces deux indicateurs sont très difficiles à optimiser simultanément. Pour augmenter le rappel, il suffit d’ajouter plus de documents dans le résultat, au détriment de la précision. À l’extrême, un résultat qui contient toute la collection interrogée a un rappel de 1, et une précision qui tend vers 0. Inversement, si on fait le choix de ne garder dans le résultat que les documents dont on est sûr de la pertinence, la précision s’améliore mais on augmente le risque de faux négatifs (c’est-à-dire de ne pas garder des documents pertinents), et donc d’un rappel dégradé.

L’évaluation d’un système de RI est un tâche complexe et fragile car elle repose sur des enquêtes impliquant des utilisateurs. Reportez-vous à l’ouvrage de référence cité au début du chapitre (et au matériel de cours associé) pour en savoir plus.

La recherche plein texte

Commençons par étudier une méthode simple de recherche pour trouver des documents répondant à une recherche dite « plein texte » constituée d’un ensemble de mots-clés. On va donner à cette recherche une définition assez restrictive pour l’instant: il s’agit de trouver tous les documents contenant tous les mots-clés. Prenons pour exemple l’ensemble (modeste) de documents ci-dessous.

• \(d_1\): Le loup est dans la bergerie.

• \(d_2\): Le loup et le trois petits cochons

• \(d_3\): Les moutons sont dans la bergerie.

• \(d_4\): Spider Cochon, Spider Cochon, il peut marcher au plafond.

• \(d_5\): Un loup a mangé un mouton, les autres loups sont restés dans la bergerie.

• \(d_6\): Il y a trois moutons dans le pré, et un mouton dans la gueule du loup.

• \(d_7\): Le cochon est à 12 le Kg, le mouton à  10 E/Kg

• \(d_8\): Les trois petits loups et le grand méchant cochon

Et ainsi de suite. Supposons que l’on recherche tous les documents parlant de loups, de moutons mais pas de bergerie (c’est le besoin). Une solution simple consiste à parcourir tous les documents et à tester la présence des mots-clés. Ce n’est pas très satisfaisant car:

• c’est potentiellement long, pas sur notre exemple bien sûr, mais en présence d’un ensemble volumineux de documents;

• le critère « pas de bergerie » n’est pas facile à traiter;

• les autres types de recherche (« le mot “loup” doit être près du mot “mouton” ») sont difficiles;

• quid si je veux classer par pertinence les documents trouvés?

On peut faire mieux en créant une structure compacte sur laquelle peuvent s’effectuer les opérations de recherche. Les données sont organisées dans une matrice (dite d’incidence) qui représente l’occurrence (ou non) de chaque mot dans chaque document. On peut, au choix, représenter les mots en colonnes et les documents en ligne, ou l’inverse. La première solution semble plus naturelle (chaque fois que j’insère un nouveau document, j’ajoute une ligne dans la matrice). Nous verrons plus loin que la seconde représentation, appelée matrice inversée, est en fait beaucoup plus appropriée pour une recherche efficace.

Terme, vocabulaire.

Nous utilisons progressivement la notion de terme (token en anglais) qui est un peu différente de celle de « mot ». Le vocabulaire, parfois appelé dictionnaire, est l’ensemble des termes sur lesquels on peut poser une requête. Ces notions seront développées plus loin.

Commençons par montrer une matrice d’incidence avec les documents en ligne. On se limite au vocabulaire suivant: {« loup », « mouton », « cochon », « bergerie », « pré », « gueule »}.

La matrice d’incidence

	loup	mouton	cochon	bergerie	pré	gueule
\(d_1\)	1	0	0	1	0	0
\(d_2\)	1	0	1	0	0	0
\(d_3\)	0	1	0	1	0	0
\(d_4\)	0	0	1	0	0	0
\(d_5\)	1	1	0	1	0	0
\(d_6\)	1	1	0	0	1	1
\(d_7\)	0	1	1	0	0	0
\(d_8\)	1	0	1	0	0	0

Cette structure est parfois utilisée dans les bases de données sous le nom d’index bitmap. Elle permet de répondre à notre besoin de la manière suivante :

• On prend les vecteurs d’incidence de chaque terme contenu dans la requête, soit les colonnes dans notre représentation :

  • Loup: 11001101

  • Mouton: 00101110

  • Bergerie: 01010011

• On fait un et (logique) sur les vecteurs de Loup et Mouton et on obtient 00001100

• Puis on fait un et du résultat avec le complément du vecteur de Bergerie (01010111)

• On obtient 00000100, d’où on déduit que la réponse est limitée au document \(d_6\), puisque la 6e position est la seule où il y a un “1”.

Les index inversés

Si on imagine maintenant des données à grande échelle, on s’aperçoit que cette approche un peu naïve soulève quelques problèmes. Posons par exemple les hypothèses suivantes:

• Un million de documents, mille mots chacun en moyenne (ordre de grandeur d’une encyclopédie en ligne bien connue)

• Disons 6 octets par mot, soit 6 Go (pas très gros en fait!)

• Disons 500 000 termes distincts (ordre de grandeur du nombre de mots dans une langue comme l’anglais)

La matrice a 1 000 000 de lignes, 500 000 colonnes, donc \(500 \times 10^9\) bits, soit 62 GO. Elle ne tient pas en mémoire de nombreuses machines, ce qui va beaucoup compliquer les choses…. Comment faire mieux?

Une première remarque est que nous avons besoin des vecteurs pour les termes (mots) pour effectuer des opérations logiques (and, or, not) et il est donc préférable d’inverser la matrice pour disposer les termes en ligne (la représentation est une question de convention: ce qui est important c’est qu’au niveau de la structure de données, le vecteur d’incidence associé à un terme soit stocké contigument en mémoire et donc accessible simplement et rapidement). On obtient la structure de la inverted-index-bool pour notre petit ensemble de documents.

Inversion de la matrice

Seconde remarque: la matrice d’incidence est creuse. En effet, sur chaque ligne, il y a au plus 1000 « 1 » (cas extrême où tous les termes du document sont distincts). Donc, dans l’ensemble de la matrice, il n’y a au plus que \(10^9\) positions avec des 1, soit un sur 500. Il est donc tout à fait inutile de représenter les cellules avec des 0. On obtient une structure appelée index inversé qui est essentiellement l’ensemble des lignes de la matrice d’incidence, dans laquelle on ne représente que les cellules correspondant à au moins une occurrence du terme (en ligne) dans le document (en colonne).

Important

Comme on ne représente plus l’ensemble des colonnes pour chaque ligne, il faut indiquer, pour chaque cellule, à quelle colonne elle correspond. Pour cela, on place dans les cellules l’identifiant du document (docId). De plus chaque liste est triée sur l’identifiant du document.

La inverted-index montre un exemple d’index inversé pour trois termes, pour une collection importante de documents consacrés à nos animaux familiers. À chaque terme est associé une liste inverse.

Un index inversé

On parle donc de cochon dans les documents 2, 31, 54 et 101 (notez que les documents sont ordonnés — très important). Il est clair que la taille des listes inverses varie en fonction de la fréquence d’un terme dans la collection.

La structure d’index inversé est utilisée dans tous les moteurs de recherche. Elle présente d’excellentes propriétés pour une recherche efficace, avec en particulier des possibilités importantes de compression des listes associées à chaque terme.

Vocabulaire

Le dictionnaire (dictionary) est l’ensemble des termes de l’index inversé; le répertoire est la structure qui associe chaque terme à l’adresse de la liste inversée (posting list) associée au terme. Enfin on ne parle plus de cellule (la matrice a disparu) mais d’entrée pour désigner un élément d’une liste inverse.

En principe, le répertoire est toujours en mémoire, ce qui permet de trouver très rapidement les listes impliquées dans la recherche. Les listes inverses sont, autant que possible, en mémoire, sinon elles sont compressées et stockées dans des fichiers (contigus) sur le disque.

Opérations de recherche

Étant donné cette structure, recherchons les documents parlant de loup et de mouton. On ne peut plus faire un et sur des tableaux de bits de taille fixe puisque nous avons maintenant des listes de taille variable. L’algorithme employé est une fusion (« merge ») de liste triées. C’est une technique très efficace qui consiste à parcourir en parallèle et séquentiellement des listes, en une seule fois. Le parcours unique est permis par le tri des listes sur un même critère (l’identifiant du document).

La loup-et-mouton-full montre comment on traite la requête loup et mouton. On maintient deux curseurs, positionnés au départ au début de chaque liste. L’algorithme compare les valeurs des docId contenues dans les cellules pointées par les deux curseurs. On compare ces deux valeurs, puis:

• (choix A) si elles sont égales, on a trouvé un document: on place son identifiant dans le résultat, à gauche; on avance les deux curseurs d’un cran

• (choix B) sinon, on avance le curseur pointant sur la cellule dont la valeur est la plus petite, jusqu’à atteindre ou dépasser la valeur la plus grande.

Parcours linéaire pour la fusion de listes triées

La loup-et-mouton-full se lit de gauche à droite, de haut en bas. On applique tout d’abord deux fois le choix A: les documents 1 et 2 parlent de loup et de mouton. À la troisième étape, le curseur du haut (loup) pointe sur le document 3, le pointeur du bas (mouton) sur le document 4. On applique le choix B en déplaçant le curseur du haut jusqu’à la valeur 4.

Et ainsi de suite. Il est clair qu’un seul parcours suffit. La recherche est linéaire, et l’efficacité est garantie par un parcours séquentiel d’une structure (la liste) très compacte. De plus, il n’est pas nécessaire d’attendre la fin du parcours de toutes les listes pour commencer à obtenir le résultat. L’algorithme est résumé ci-dessous.

// Fusion de deux listes l1 et l2
function Intersect($l1, $l2)
{
  $résultat = [];
  // Début de la fusion des listes
  while ($l1 != null and $l2 != null) {
    if ($l1.docId == $l2.docId) {
      // On a trouvé un document contenant les deux termes
      $résultat += $l1.docId;
      // Avançons sur les deux listes
      $l1 = $l1.next; $l2 = $l2.next;
    }
    else if ($l1.docId < $l2.docId) {
      // Avançons sur l1
      $l1 = $l1.next;
    }
    else {
       // Avançons sur l2
      $l2 = $l2.next;
    }
  }
}

C’est l’algorithme de base de la recherche d’information. Dans la version présentée ici, on satisfait des requêtes dites booléennes: l’appartenance d’un document au résultat est binaire, et il n’y a aucun classement par pertinence.

À partir de cette technique élémentaire, on peut commencer à raffiner, pour aboutir aux techniques sophistiquées visant à capturer au mieux le besoin de l’utilisateur, à trouver les documents qui satisfont ce besoin et à les classer par pertinence. Pour en arriver là, tout un ensemble d’étapes que nous avons ignorées dans la présentation abrégée qui précède sont nécessaires. Nous les reprenons dans ce qui suit.

Quiz

Cherchez l’erreur! Quelle propriété parmi les suivantes ne vous semble pas s’appliquer à la recherche d’information?

1. On évalue la proximité entre le besoin exprimé et les documents du système

2. On cherche des documents de structure similaire à celui donné par la requête

3. On cherche des documents de contenu similaire à celui donné par la requête

4. On cherche les paires de documents proches les uns des autres

Quel est le rappel si la recherche ramène tous les documents?

1. Le rappel est maximal, donc 1

2. Le rappel est minimal, donc 0

3. Le rappel est le rapport entre le nombre de documents pertinents et la taille de la collection

Quelle est la précision si la recherche ramène tous les documents?

1. La précision est maximale, donc 1

2. La précision est minimale, donc 0

3. La précision est le rapport entre le nombre de documents pertinents et la taille de la collection

Quel est le rappel si la recherche ne ramène aucun document?

1. Le rappel est maximal, donc 1

2. Le rappel est minimal, donc 0

3. Le rappel est le rapport entre le nombre de documents pertinents et la taille de la collection

Quelle est la précision si la recherche ne ramène aucun document?

1. La précision est maximale, donc 1

2. La précision est minimale, donc 0

3. La précision est indéfinie

Si je souhaite minimiser le nombre de faux positifs dans ma réponse, je dois favoriser

1. Le rappel

2. La précision

3. Le rapport rappel / précision

4. Le rapport précision / rappel

Si je souhaite minimiser le nombre de faux négatifs dans ma réponse, je dois favoriser

1. Le rappel

2. La précision

Qu’est-ce qu’une matrice (ou un index) inversé?

1. C’est une structure dans laquelle on a remplacé les 0 par des 1 et réciproquement, pour faciliter les calculs

2. C’est une structure où les documents sont en ligne et les token en colonne

3. C’est une structure où les documents sont en colonne et les token en ligne

Qu’est-ce que le répertoire dans un index inversé?

1. C’est l’espace où l’on stocke les listes inversées

2. C’est la liste des termes indexés

3. C’est un tableau qui associe un terme et une liste

Quel est le coût d’une recherche avec un index inversé?

1. Proportionnel à la taille de la collection

2. Proportionnel à la taille des listes correspondant aux mots cherchés

3. Proportionnel au nombre de termes de la requête

Par rapport à la définition de la recherche d’information, quel énoncé ci-dessous sur la recherche booléenne vous semble correct ?

1. Ce n’est pas de la RI car on traite des documents structurés

2. Ce n’est pas de la RI car il n’y a pas d’estimation de la pertinence

3. Ce n’est pas de la RI car il n’y a ni faux négatif ni faux positif.

S2: L’analyse de documents

Supports complémentaires:

• Présentation: Recherche d’information - analyse de documents

• Vidéo : Pré-traitement des documents textuels

En présence d’un document textuel un tant soit peu complexe, on ne peut pas se contenter de découper plus ou moins arbitrairement en mots sans se poser quelques questions et appliquer un pré-traitement du texte. Les effets de ce pré-traitement doivent être compris et maîtrisés: ils influent directement sur la précision et le rappel. Quelques exemples simples pour s’en convaincre:

• si on cherche les documents contenant le mot « loup », on s’attend généralement à trouver ceux contenant « loups », « Loup », « louve »; il faut donc, quand on conserve un document dans Elasticsearch, qu’il soit en mesure de mettre ces différentes formes dans le même index inversé;

• si on ne normalise pas (on conserve les majuscules et les pluriels), on va dégrader le rappel, puisqu’un utilisateur saisissant le mot-clef « loup » ne trouvera pas les documents dans lesquels ce terme apparaît seulement sous la forme « Loup » ou « loups »;

• on le comprend immédiatement avec le cas de « loup / louve », il faut une connaissance experte de la langue pour décider que « louve » et « loup » doivent être associés, ce qui requiert une transformation qui dépend de la langue et nécessite une analyse approfondie du contenu;

• inversement, si on normalise (retrait des accents, par exemple) « cote », « côte », « côté », on va unifier des mots dont le sens est différent, et on va diminuer la précision.

En fonction des caractéristiques des documents traités, des utilisateurs de notre système de recherche, il faudra trouver un bon équilibre, aucune solution n’étant parfaite. C’est de l’art et du réglage…

L’analyse se compose de plusieurs phases:

• Tokenization: découpage du texte en « termes ».

• Normalisation: identification de toutes les variantes d’écritures d’un même terme et choix d’une règle de normalisation (que faire des majuscules? acronymes? apostrophes? accents?).

• Stemming (« racinisation »): rendre la racine des mots pour éviter le biais des variations autour d’un même sens (auditer, auditeur, audition, etc.)

• Stop words (« mots vides »), comment éliminer les mots très courants qui ne rendent pas compte de la signification propre du document?

Ce qui suit est une brève introduction, essentiellement destinée à comprendre les outils prêts à l’emploi que nous utiliserons ensuite. Remarquons en particulier que les étapes ci-dessus sont parfois décomposées en sous-étapes plus fines avec des algorithmes spécifiques (par exemple, un pour les accents, un autre pour les majuscules). L’ordre que nous donnons ci-dessus est un exemple, il peut y avoir de légères variations. Enfin, notez bien que le texte transformé dans une étape sert de texte d’entrée à la transformation suivante (nous y reviendrons dans la partie pratique).

Tokenisation et normalisation

Un tokenizer prend en entrée un texte (une chaîne de caractères) et produit une séquence de tokens. Il effectue donc un traitement purement lexical, consistant typiquement à éliminer les espaces blancs, la ponctuation, les liaisons, etc., et à identifier les « mots ». Des transformations peuvent également intervenir (suppression des accents par exemple, ou normalisation des acronymes - U.S.A. devient USA).

La tokenization est très fortement dépendante de la langue. La première chose à faire est d’identifier cette dernière. En première approche on peut examiner le jeu de caractères (characters).

Quelques jeux de caractères … exotiques

Il s’agit respectivement du: Coréen, Japonais, Maldives, Malte, Islandais. Ce n’est évidemment pas suffisant pour distinguer des langues utilisant le même jeu de caractères. Une extension simple est d’identifier les séquences de caractères fréquents, (n-grams). Des bibliothèques fonctionnelles font ça très bien (e.g., Tika, http://tika.apache.org)

Une fois la langue identifiée, on divise le texte en tokens (« mots »). Ce n’est pas du tout aussi facile qu’on le dirait!

• Dans certaines langues (Chinois, Japonais), les mots ne sont pas séparés par des espaces.

• Certaines langues s’écrivent de droite à gauche, de haut en bas.

• Que faire (et de manière cohérente) des acronymes, élisions, nombres, unités, URL, email, etc.

• Que faire des mots composés: les séparer en tokens ou les regrouper en un seul? Par exemple:

  • Anglais: hostname, host-name et host name, …

  • Français: Le Mans, aujourd’hui, pomme de terre, …

  • Allemand: Levensversicherungsgesellschaftsangestellter (employé d’une société d’assurance vie).

Pour les majuscules et la ponctuation, une solution simple est de normaliser systématiquement (minuscules, pas de ponctuation). Ce qui donnerait le résultat suivant pour notre petit jeu de données.

• \(d_1\): le loup est dans la bergerie

• \(d_2\): le loup et les trois petits cochons

• \(d_3\): les moutons sont dans la bergerie

• \(d_4\): spider cochon spider cochon il peut marcher au plafond

• \(d_5\): un loup a mangé un mouton les autres loups sont restés dans la bergerie

• \(d_6\): il y a trois moutons dans le pré et un mouton dans la gueule du loup

• \(d_7\): le cochon est à 12 euros le kilo le mouton à  10 euros kilo

• \(d_8\): les trois petits loups et le grand méchant cochon

Stemming (racine), lemmatisation

La racinisation consiste à confondre toutes les formes d’un même mot, ou de mots apparentés, en une seule racine. Le stemming morphologique retire les pluriels, marque de genre, conjugaisons, modes, etc. Le stemming lexical fond les termes proches lexicalement: « politique, politicien, police (?) » ou « université, universel, univers (?) ». Ici, le choix influe clairement sur la précision et le rappel (plus d’unification favorise le rappel au détriment de la précision).

La racinisation est très dépendante de la langue et peut nécessiter une analyse linguistique complexe. En anglais, geese est le pluriel de goose, mice de mouse; les formes masculin / féminin en français n’ont parfois rien à voir (« loup / louve ») mais aussi (« cheval / jument »: parle-t-on de la même chose?) Quelques exemples célèbres montrent les difficultés d’interprétation:

• « Les poules du couvent couvent »: où est le verbe, où est le substantif?

• « La petite brise la glace »: idem.

Voici un résultat possible de la racinisation pour nos documents.

• \(d_1\): le loup etre dans la bergerie

• \(d_2\): le loup et les trois petit cochon

• \(d_3\): les mouton etre dans la bergerie

• \(d_4\): spider cochon spider cochon il pouvoir marcher au plafond

• \(d_5\): un loup avoir manger un mouton les autre loup etre rester dans la bergerie

• \(d_6\): il y avoir trois mouton dans le pre et un mouton dans la gueule du loup

• \(d_7\): le cochon etre a 12 euro le kilo le mouton a 10 euro kilo

• \(d_8\): les trois petit loup et le grand mechant cochon

Il existe des procédures spécialisées pour chaque langue. En anglais, l’algorithme Snowball de Martin Porter fait référence et est toujours développé aujourd’hui. Il a connu des déclinaisons dans de nombreuses langues, dont le français, par un travail collaboratif.

Mots vides et autres filtres

Un des filtres les plus courants consiste à retire les mots porteurs d’une information faible (« stop words » ou « mots vides ») afin de limiter le stockage.

• Les articles: le, le, ce, etc.

• Les verbes « fonctionnels »: être, avoir, faire, etc.

• Les conjonctions: et, ou, etc.

• et ainsi de suite.

Le choix est délicat car, d’une part, ne pas supprimer les mots vides augmente l’espace de stockage nécessaire (et ce d’autant plus que la liste associée à un mot très fréquent est très longue), d’autre part les éliminer peut diminuer la pertinence des recherches (« pomme de terre », « Let it be », « Stade de France »).

Parmi les autres filtres, citons en vrac:

• Majuscules / minuscules. On peut tout mettre en minuscules, mais on perd alors la distinction nom propre / nom commu,, par exemple Lyonnaise des Eaux, Société Générale, Windows, etc.

• Acronymes. CAT = cat ou Caterpillar Inc.? M.A.A.F ou MAAF ou Mutuelle … ?

• Dates, chiffres. Monday 24, August, 1572 – 24/08/1572 – 24 août 1572; 10000 ou 10,000.00 ou 10,000.00

Dans tous les cas, les même règles de transformation s’appliquent aux documents ET à la requête. Voici, au final, pour chaque document la liste des tokens après application de quelques règles simples.

• \(d_1\): loup etre bergerie

• \(d_2\): loup trois petit cochon

• \(d_3\): mouton etre bergerie

• \(d_4\): spider cochon spider cochon pouvoir marcher plafond

• \(d_5\): loup avoir manger  mouton autre loup etre rester bergerie

• \(d_6\): avoir trois mouton pre mouton gueule loup

• \(d_7\): cochon etre douze euro kilo mouton dix euro kilo

• \(d_8\): trois petit loup grand mechant cochon

Quiz

Qu’est-ce que la tokenisation?

1. C’est l’élimination de toute ponctuation

2. C’est le découpage d’un texte en unités lexicales

3. C’est l’extraction des termes d’un dictionnaire présents dans un texte

Quelle opération ci-dessous ne relèvent pas de la stemmisation?

1. Rassembler tous les synonymes en un seul terme

2. Supprimer toutes les formes plurielles

3. Ramener tous les verbes à la forme infinitive

S1: recherche avec classement

Supports complémentaires:

• Présentation: Recherche avec classement

• Vidéo de la session « Principes de la recherche avec classement »

Le mode d’interrogation classique en base de données consiste à exprimer des critères de recherche et à produire en sortie les données qui satisfont exactement ces critères. En d’autres termes, dans le cas d’une base documentaire, on peut déterminer qu’un document est ou n’est pas dans le résultat. Cette décision univoque correspond au modèle de requêtes Booléennes présenté précécemment.

Notions de base: espace métrique, distance et similarité

Dans le cas typique d’un document textuel, il est illusoire de vouloir effectuer une recherche exacte en tentant de produire comme critère la chaîne de caractères complète du document, voire même une sous-chaîne. La même remarque s’applique à des objets complexes ou multimédia (images, vidéos, etc.). La logique est alors plutôt d’interpréter la requête comme un besoin, et d’identifier les documents les plus « proches » du besoin. En recherche d’information (RI), on raisonne donc plutôt en terme de pertinence pour décider si un document fait ou non partie du résultat d’une recherche. La formalisation de ces notions de besoin et de pertinence est au centre des méthodes de RI.

En particulier, la formalisation de la pertinence consiste à en donner une expression quantitative. Pour cela, l’approche classique consiste

• à définir un espace métrique E doté d’une fonction de distance \(m_E\),

• à définir une fonction \(f\) de l’espace des documents vers E; cette fonction s’applique également à la requête q, vue comme un document;

• enfin, on mesure la pertinence (ou similarité) entre deux documents \(d_1\) et \(d_2\) comme l’inverse de la distance entre \(f(d_1)\) et \(f(d_2)\).

  \[sim(d, q) = \frac{1}{m_E(f(d_1), f(d_2))}\]

On obtient une mesure de la similarité, ou score, mesurant la proximité de deux documents (ou, plus précisément, des vecteurs représentant ces documents). Il reste à interpréter la requête \(q\) comme un document et à évaluer \(sim(f(d), f(q))\) pour chaque document d afin d’évaluer la pertinence d’un document vis-à-vis du besoin exprimé par la requête.

Avec cette approche, contrairement aux requêtes Booléennes, on ne peut souvent plus dire de manière stricte qu’un document d n’appartient pas au résultat d’une recherche. Il est plus correct de dire que d est plus ou moins pertinent. Cela rend les résultats beaucoup plus riches, et offre à l’utilisateur la possibilité d’éviter le « tout ou rien » de l’approche Booléenne.

Note

Reportez-vous au chapitre Recherche approchée pour une discussion introductive sur les notions de faux et vrais positifs, de rappel et de précision.

La contrepartie de cette flexibilité est l’abondance des candidats potentiels et la nécessité de les classer en fonction de leur pertinence/score. Le rôle d’un moteur de recherche consiste donc (conceptuellement), pour chaque requête q, à calculer le score \(s_i = sim(q, d_i)\) pour chaque document \(d_i\) de la collection, à trier tous les documents par ordre décroissant des scores et à présenter ce classement à l’utilisateur.

Important

Il faut ajouter une contrainte de temps: le résultat doit être disponible en quelques dizièmes de secondes, même dans le cas de collections comprenant des millions, des centaines de millions ou des milliards de documents (cas du Web). La performance de la recherche s’appuie sur les structures d’index inversés et des optimisations fines qui dépassent le cadre de ce cours: reportez-vous, par exemple, au livre en ligne mentionné en début de chapitre.

En pratique, le calcul du score pour tous les documents n’est bien sûr pas faisable (ni souhaitable d’ailleurs), et le moteur de recherche dispose de structures de données qui vont lui permettre de déterminer rapidement les documents ayant le meilleur score. Ces documents (disons les 10 ou 20 premiers, typiquement) sont présentés à l’utilisateur, et le reste de la liste est calculé à la demande si besoin est. Dans le cas d’une interface interactive (et si le classement est réellement pertinent vis-à-vis du besoin), il est rare qu’un utilisateur aille au-delà de la seconde, voire même de la première page.

Vocabulaire. En résumé, voici les points à retenir.

1. on effectue des calculs dans un espace métrique, le plus souvent un espace vectoriel;

2. pour chaque document, on produit un objet de l’espace métrique, appelé descripteur, qui a le plus souvent la forme d’un vecteur (features vector);

3. on applique le même traitement à la requête q pour obtenir un descripteur \(v_q\);

4. le score est une mesure de la pertinence d’un document \(d_i\) par rapport au besoin exprimé par la requête q;

5. le calcul du score s’appuie sur la mesure de la distance entre le descripteur de \(d_i\) et celui de q.

Ces principes étant posés, voyons une application concrète (quoique simplifiée pour l’instant, et peu satisfaisante en pratique) au cas de la recherche plein texte.

Application à la recherche plein texte

Important

La méthode présentée ci-dessous n’est qu’une première approche, à la fois très simplifiée et présentant de sévères défauts par rapport à la méthode générale que nous présenterons ensuite.

Pour commencer, on suppose connu l’ensemble \(V=\{t_1, t_2, \cdots, t_n\}\) de tous les termes utilisables pour la rédaction d’un document et on définit E comme l’espace de tous les vecteurs constitués de n coordonnées valant soit 0, soit 1 (soit, en notation mathématique, \(E = \{0, 1\}^{n}\)). Ce sont nos descripteurs.

Par exemple, on considère que le vocabulaire est {« papa », « maman », « gateau », « chocolat », « haut », « bas »}. Nos vecteurs sont donc constitués de 6 coordonnées valant soit 0, soit 1. Il faut alors définir la fonction \(f\) qui associe un document d à son descripteur (vecteur) \(v = f(d)\). Voici cette définition:

\[\begin{split}v[i] = \left\{ \begin{array}{ll} 1 \text{ si $d$ contient le terme $t_i$}\\ 0 \text{ sinon} \end{array} \right.\end{split}\]

C’est exactement la représentation que nous avons adoptée jusqu’à présent. À chaque document on associe une séquence (un vecteur) de 1 ou de 0 selon que le terme \(t_i\) est présent ou non dans le document.

Prenons un premier exemple. Le document \(d_{maman}\):

"maman est en haut, qui fait du gateau"

sera représenté par le descripteur/vecteur \([0, 1, 1, 0, 1, 0]\). Je vous laisse calculer le vecteur de ce second document \(d_{papa}\):

"papa est en bas, qui fait du chocolat"

Note

Remarquez que l’on choisit délibérément d’ignorer certains mots considérés comme peu représentatifs du contenu du document. Ce sont les stop words (mots inutiles) comme « est », « en », « qui », « fait », etc.

Note

Remarquez également que l’ordre des mots dans le document est ignoré par cette représentation qui considère un texte comme un « sac de mots » (bag of words). Si on prend un document contenant les deux phrases ci-dessus, on ne sait plus distinguer si papa est en haut ou en bas, ou si maman fait du gateau ou du chocolat.

Maintenant, contrairement à la recherche Booléenne dans laquelle on vérifiait que, pour chaque terme requis, la position correspondante dans le vecteur d’un document était à 1, on va appliquer une fonction de distance sur les vecteurs afin d’obtenir une valeur entre 0 et 1 mesurant la pertinence. Un candidat naturel est la distance Euclidienne dont nous rappelons la définition, pour deux vecteurs \(v_1\) et \(v_2\).

\[E(v_1, v_2) = \sqrt{(v_1^1 - v^1_2)^2 + (v^2_1 - v^2_2)^2 + \cdots + (v_1^n - v^n_2)^2}\]

Et la similarité est l’inverse de la distance.

\[\begin{split}sim(v_1, v_2) = \left\{ \begin{array}{ll} \infty \text{ si $v^i_1=v^i_2$ pour tout $i$ }\\ \frac{1}{E(v_1, v_2)} \text{ sinon} \end{array} \right.\end{split}\]

On obtient une mesure de la similarité, ou score, mesurant la proximité de deux documents (ou, plus précisément, des vecteurs représentant ces documents).

Il reste à interpréter la requête comme un document et à évaluer \(sim(f(d), f(q))\) pour chaque document d et la requête q pour évaluer la pertinence d’un document vis-à-vis du besoin exprimé par la requête. La requête q par exemple:

"maman haut chocolat"

est donc transformée en un vecteur \(v_q = [0, 1, 0, 1, 1, 0]\). Pour le document \(d_{maman}\), on obtient un score de \(sim (v_q, d_{maman}) = \frac{1}{\sqrt{2}}\). À vous de calculer \(sim (v_q, d_{papa})\) et de vérifier que ce score est moins elevé, ce qui correspond à notre intuition. Notez quand même:

• que « chocolat », un des mots-clés de q, n’apparaît pas dans le document \(d_{maman}\), malgré tout classé en tête;

• qu’un seul terme est commun entre \(d_{papa}\) et q, et que le document est quand même (bien) classé;

• qu’un document comme « bébé mange sa soupe » obtiendrait un score non nul (lequel?) et serait donc lui aussi classé (si on ne met pas de borne à la valeur du score).

Une différence concrète très sensible (illustrée ci-dessus) avec les requêtes Booléennes est qu’il n’est pas nécessaire qu’un document contienne tous les termes de la requête pour que son score soit différent de 0.

Les limites de l’approche présentée jusqu’ici sont explorées dans des exercices. La méthode beaucoup plus robuste détaillée dans la prochaine section montrera aussi, par contraste, coment des facteurs comme la taille des documents, la taille du vocabulaire, le nombre d’occurrences d’un terme dans un document et la rareté de ce terme influent sur la précision du classement.

Quiz

Quelle est la différence entre un espace métrique (EM) et un espace vectoriel (EV)?

1. Les données d’un EM sont ordonnées, contraitrement aux vecteurs

2. Il existe une fonction de distance dans un EM, et pas dans un EV

3. Un EV est un type particulier d’espace métrique

Laquelle de ces propriétés n’est pas nécessaire pour une distance

1. La symétrie

2. L’inégalité triangulaire

3. La valeur est comprise entre 0 et 1

4. La distance est nulle ssi les deux objets sont les mêmes

Quelle explication de la notion de « bag of words » vous semble la bonne.

1. Chaque texte est représenté par un sous-ensemble de ses mots, c’est le « sac »

2. Le texte est considéré comme un ensemble de mots sans ordre, comme s’ils étaient dans un « sac »

3. Les textes sont projetés dans un espace vectoriel appelé « sac de mots ».

Pourquoi est-il plus correct de parler de distance entre les représentations des documents que de distance entre les documents eux-mêmes?

1. Parce qu’il peut y avoir plusieurs représentations possibles d’un même document, ce qui peut influer sur la distance

2. Parce que la distance naturelle entre deux documents textuels est trop coûteuse à calculer

3. Parce que cela permet d’appliquer une même distance à des documents multimédia quelconques: images, vidéos, etc.

Comment est interprétée une requête q ?

1. C’est une séquence d’opérations à appliquer à la collection

2. C’est une spécification de critères de recherche filtrant la collection

3. C’est un document de même type que ceux de la collection

4. C’est une sous-chaîne des documents textuels de la collection

Qu’est-ce qui détermine le classement du résultat?

1. On calcule toutes les distances entre chaque paire de documents, et on trie.

2. On calcule la distance par rapport à un document de référence: la requête

3. Les documents qui contiennent le plus de termes sont classés en premier

Qu’est-ce qu’un stop word

1. On exclut les documents qui contiennent ce mot

2. C’est un mot courant qui n’informe pas sur le document

3. C’est un mot qui déclenche l’arrêt de la recherche quand il est rencontré

Un document doit contenir tous les mots de la requête pour être pertinent

1. Vrai

2. Faux

Quelle propriété de la distance euclidienne est vraie?

1. On ne prend en compte que les 1

2. On ne prend en compte que les 0

3. On prend en compte toutes les coordonnées des vecteurs

4. On prend en compte les coordonnées du vecteur décrivant la requête

S2: recherche plein texte

Supports complémentaires:

• Présentation: Recherche plein texte

• Vidéo de la session classement dans la recherche plein texte

Nous reprenons maintenant un approche plus solide pour la recherche plein texte, qui pour l’essentiel s’appuie sur les principes précédents, mais corrige les gros inconvénients que vous avez dû découvrir en complétant les exercices.

La méthode présentée dans ce qui suit est maintenant bien établie et utilisée, à quelques raffinements près, comme approche de base par tous les moteurs de recherche. Résumons (une nouvelle fois):

• les documents (textuels) sont vus comme des sacs de mots, l’ordre entre les mots étant ignoré; on ne fera pas de différence entre un document qui dit que le mouton est dans la gueule du loup et un autre qui prétend que le loup est dans la gueule du mouton (?);

• quand on parle de « mots », il faut bien comprendre: les termes obtenus par application d’un processus de simplification / normalisation lexicale déjà étudié;

• un descripteur est associé à chaque document, dans un espace doté d’une fonction de distance qui permet d’estimer la similarité entre deux documents;

• enfin, la requête elle-même est vue comme un document, et placée donc dans le même espace; on considère donc ici les requêtes exprimées comme une liste de mots, sans aucune construction syntaxique complémentaire.

Ceci posé, nous nous concentrons sur la fonction de similarité.

Note

« mot » et « terme » sont utilisés comme des synonymes à partir de maintenant.

Le poids des mots

Dans l’approche très simplifiée présentée ci-dessus, nous avons traité les mots uniformément, selon une approche Booléenne: 1 si le mot est présent dans le document, 0 sinon.

Pour obtenir des résultats de meilleure qualité, on va prendre en compte les degrés de pertinence et d’information portés par un terme, selon deux principes:

1. plus un terme est présent dans un document, plus il est représentatif du contenu du document;

2. moins un terme est présent dans une collection, et plus une occurrence de terme est significative.

De plus, on va tenter d’éliminer le biais lié à la longueur variable des documents. Il est clair que plus un document est long, et plus il contiendra de mots et de répétitions d’un même mot. Si on n’introduit pas un élément correctif, la longueur des documents a donc un impact fort sur le résultat d’une recherche et d’un classement, ce qui n’est pas forcément souhaitable.

En tenant compte de ces facteurs, on aboutit à affecter un poids à chaque mot dans un document, et à représenter ce dernier comme un vecteur de paires (mot, poids), ce qui peut être considéré comme une représentation compacte du contenu du document. La méthode devenue classique pour déterminer le poids est de combiner la fréquence des termes et la fréquence inverse (des termes) dans les documents, ce que l’on abrège par tf (term frequency) et idf (inverse document frequency).

La fréquence des termes

La fréquence d’un terme t dans un document d est le nombre d’occurrences de t dans d.

\[\mathrm{tf}(t,d)= n_{t,d}\]

où \(n_{t,d}\) est le nombre d’occurrences de t” dans d. On représente donc un document par la liste des termes associés à leur fréquence. Si on prend une collection de documents, dans laquelle certains termes apparaissent dans plusieurs documents (ce qui est le cas normal), on peut représenter les tf par une matrice semblable à la matrice d’incidence déjà vue dans la cas Booléen. Celle ci-dessous correspond à une collection de trois documents, avec un vocabulaire constitué de 4 termes.

terme	d1	d2	d3
voiture	27	15	24
marais	3	20	0
serpent	0	25	29
baleine	14	0	17
total	44	60	70

Normalisation des tf

Il y a donc 44 termes dans le document d1, 60 dans le d2 et 70 dans le d3. Il est clair qu’il est difficile de comparer dans l’absolu des fréquences de terme pour des documents de longueur très différentes, car la probabilité qu’un terme apparaisse souvent augment avec la taille du document.

Pour s’affranchir de l’effet induit par la taille (qui amènerait à classer systématiquement en tête les documents longs), on normalise donc les valeurs des tf. Une méthode simple est, par exemple, de diviser chaque tf par le nombre total de termes dans le document, ce qui donnerait la matrice suivante:

terme	d1	d2	d3
voiture	27/44	15/60	24/70
marais	3/44	20/60	0
serpent	0	25/60	29/70
baleine	14/44	0	17/70

Un calcul un peu plus sophistiqué consiste à considérer l’ensemble une colonne de la matrice d’incidence comme un vecteur dans un espace multidimensionel. Dans notre exemple l’espace est de dimension 4, chaque axe correspondant à l’un des termes. Le vecteur de d1 est (27, 3, 0, 14), celui de d2 (15,20, 25,0), etc. Pour normaliser ces vecteurs, on va diviser leurs coordonnées par leur norme euclidienne. Rappel: la norme d’un vecteur \(v = (x_1, x_2, \cdots, x_n)\) est

\[||v|| = \sqrt{x_1^2 + x_2^2 + \cdots + x_n^2}\]

La norme du vecteur d1 est donc:

\[\sqrt{27^2 + 3^2 + 14^2} = 30,56\]

Celle de d2:

\[\sqrt{15^2 + 20^2 + 25^2} = 35,35\]

Celle de d3:

\[\sqrt{24^2 + 29^2 + 17^2} = 41,3\]

On voit que le résultat est assez différent de la simple somme des tf. L’interprétation des descripteurs de documents comme des vecteurs est à la base d’un calcul de similarité basé sur les cosinus, que nous détaillons ci-dessous.

La fréquence inverse dans les documents

La fréquence inverse d’un terme dans les documents (inverse document frequency, ou idf) mesure l’importance d’un terme par rapport à une collection D de documents. Un terme qui apparaît rarement peut être considéré comme plus caractéristique d’un document qu’un autre, très commun. On retrouve l’idée des mots inutiles, avec un raffinement consistant à mesurer le degré d’utilité.

L’idf d’un terme t est obtenu en divisant le nombre total de documents par le nombre de documents contenant au moins une occurrence de t. De plus, on prend le logarithme de cette fraction pour conserver cette valeur dans un intervalle comparable à celui du tf.

\[\mathrm{idf}(t)=\log\frac{|D|}{\left|\left\{d' \in D\,|\,n_{t,d'}>0\right\}\right|}\]

Notez que si on ne prenait pas le logarithme, la valeur de l’idf pourrait devenir très grande, et rendrait négligeable l’autre composante du poids d’un terme. La base du logarithme est 10 en général, mais quelle que soit la base, vous noterez que l’idf est nul dans le cas d’un terme apparaissant dans tous les documents (c’est clair? sinon réfléchissez!).

Reprenons notre matrice ci-dessus en supposant que la collection se limite aux trois documents. Alors

• l’idf de « voiture » est 0, car il apparaît dans tous les documents. Intuitivement, « voiture » est (pour la collection étudiée) tellement courant qu’il n’apporte rien comme critère de recherche.

• l’idf de « marais », « serpent » et « baleine » est \(log(3/2)\)

Dans un cas plus réaliste, un terme qui apparaît 100 fois dans une collection d’un million de documents aura un idf de \(log_{10}(1000000/100) = log_{10}(10000) = 4\) (en base 10). Un terme qui n’apparaît que 10 fois aura un idf de \(log_{10}(1000000/10) = log_{10}(100000) = 5\). Une valeur d’idf plus élevée indique le terme est relativement plus important car plus rare.

Le poids tf.idf

On peut combiner le tf (normalisé ou non) et l’idf pour obtenir le poids tf.idf d’un terme t dans un document. C’est simplement le produit des deux valeurs précédentes:

\[\mathop{\mathrm{tf{.}idf}}(t,d)= n_{t,d}\cdot \log\frac{|D|}{\left|\left\{d'\in D\,|\,n_{t,d'}>0\right\}\right|}\]

À chaque document d nous associons un vecteur \(v_d\) dont chaque composante \(v_d[i]\) contient le tf.idf du terme \(t_i\) pour d.

Si le tf n’est pas normalisé, les valeurs des tf.idf seront d’autant plus élevées que le document est long. En terme de stockage (et pour anticiper un peu sur la structure des index inversés), il est préférable de stocker

• l’idf à part, dans une structure indexée par le terme,

• la norme des vecteurs à part, dans une structure indexéee par les documents

• et enfin de placer dans chaque cellule la valeur du tf.

On peut alors effectuer le produit tf.idf et la division par la norme au moment du calcul de la distance.

La similarité cosinus

Nous avons donc des vecteurs représentant les documents. La requête est elle aussi représentée par un vecteur dans lequel les coefficients des mots sont à 1. Comment calculer la distance entre ces vecteurs? Si on prend comme mesure la norme de la différence entre deux vecteurs comme nous l’avons fait initialement, des anomalies sévères apparaissent car deux documents peuvent avoir des contenus semblables mais des tailles très différentes. La distance Euclidienne n’est donc pas un bon candidat.

On pourrait mesure la distance euclidienne entre les vecteurs normalisés. Une mesure plus adaptée en pratique est la similarité cosinus. Commençons par quelques rappels, en commençant par la formule du produit scalaire de deux vecteurs.

\[v_1 . v_2 = ||v_1|| \times ||v_2|| \times cos \theta = \sum_{i=1}^n v_1[i] \times v_2[i]\]

où \(\theta\) désigne l’angle entre les deux vecteurs et \(||v||\) la norme d’un vecteur v (sa longueur Euclidienne).

On en déduit donc que le cosinus de l’angle entre deux vecteurs satisfait:

\[cos { } \theta = \frac{\sum_{i=1}^n v_1[i] \times v_2[i]}{||v_1|| \times ||v_2||}\]

Quel est l’intérêt de prendre ce cosinus comme mesure de similarité? L’idée est que l’on compare la direction de deux vecteurs, indépendamment de leurs longueurs. La CosineSim montre la représentation des vecteurs pour nos documents de l’exercice Ex-S1-1. Les vecteurs en ligne pleine sont les vecteurs unitaires, normalisés, les lignes pointillées montrant les vecteurs complets. Pour des raisons d’illustration, l’espace est réduit à deux dimensions correspondant aux deux termes, « loup » et « bergerie ». Il faut imaginer un espace vectoriel de dimension n, n étant le nombre de termes dans la collection, et donc potentiellement très grand.

Illustration de la similarité cosinus

Les documents (B) et (D) contiennent respectivement une occurrence de « bergerie » et une de « loup »: ils sont alignés avec les axes respectifs.

Le document (A) contient une occurrence de « loup » et une de « bergerie » et fait donc un angle de 45 degrés avec l’abcisse: le cosinus de cet angle, égal à \(\sqrt{2}/2\), représente la similarité entre A et B.

En ce qui concerne C, « loup » est mentionné deux fois et « bergerie » une, d’où un angle plus important avec l’abcisse.

Le fait d’avoir comme dénominateur dans la formule le produit des normes revient à normaliser le calcul en ne considérant que des vecteurs de longueur unitaire. La mesure satisfait aussi des conditions satisfaisantes intuitivement:

• l’angle entre deux vecteurs de même direction est 0, le cosinus vaut 1;

• l’angle entre deux vecteurs orthogonaux, donc « indépendants » (aucun terme en commun), est 90 degrés, le cosinus vaut 0;

• toutes les autres valeurs possibles (dans la mesure où les coefficients de nos vecteurs sont positifs) varient continuement entre 0 et 1 avec la variation de l’angle entre 0 et 90 degrés.

Dernier atout: la similarité cosinus est très simple à calculer, et très rapide pour des vecteurs comprenant de nombreuses composantes à 0, ce qui est le cas pour la représentation des documents.

Note

La similarité cosinus n’est pas une distance au sens strict du terme (l’inégalité triangulaire n’est pas respectée), mais ses propriétés en font un excellent candidat.

Passons à la pratique sur notre exemple de trois documents représentés par la matrice donnée précédemment. On va ignorer l’idf pour faire simple, et se contenter de prendre en compte le tf.

Commençons par une requête simplissime: « voiture ». Cette requête est représentée dans l’espace de dimension 4 de notre vocabulaire par le vecteur (1, 0, 0, 0), dont la norme est 1. On pourrait croire qu’il suffit de prendre le classement des tf du terme concerné, sans se lancer dans des calculs compliqués, auquel cas d1 arriverait en tête juste devant d3. Erreur! Ce qui compte ce n’est pas la fréquence d’un terme, mais sa proportion par rapport aux autres. Il faut appliquer le calcul cosinus rigoureusement.

Calculons donc les cosinus. Pour d1, le cosinus vaut est le produit scalaire des vecteurs (27, 3, 0, 14) et (1, 0, 0, 0), divisé par le produit de la norme de ces deux vecteurs:

\[\frac{27 \times 1 + 3 \times 0 + 0 \times 0 + 14 \times 0}{1 \times 30,56} = 0,88\]

Pour les autres documents:

• Pour d2, le cosinus vaut : \(\frac{15 + 0 + 0 + 0}{1 \times 35,35} = 0,424\)

• Pour d3, le cosinus vaut : \(\frac{24 + 0 +0 +0}{1,41 \times 41,3} = 0,58\)

Le classement est d1, d3, d2, et on voit que d1 l’emporte assez nettement sur d3 alors que le nombre d’occurrences du terme « voiture » est à peu près le même dans les deux cas. Explication: d1 parle essentiellement de voiture, le second terme le plus important, « baleine », ayant moins d’occurrences. Dans d3 au contraire, « serpent » est le terme principal, « voiture » arrivant en second. Le document d1 est donc plus pertinent pour la requête et doit être classé en premier.

Prenons un second exemple, « voiture » et « baleine ». Remarquons d’abord que les coefficients de la requête sont (1, 0, 0, 1) et sa norme \(\sqrt{1+1} = 1,41\). Voici les calculs cosinus:

• Pour d1, le cosinus vaut : \(\frac{27 + 14}{1,41 \times 30,56} = 0,95\)

• Pour d2, le cosinus vaut : \(\frac{15 + 0}{1,41 \times 35,35} = 0,30\)

• Pour d3, le cosinus vaut : \(\frac{24 + 17}{1,41 \times 41,3} = 0,70\)

L’ordre est donc d1, d3, d2. Le document d3 présente un meilleur équilibre entre les composantes voiture et baleine, mais, contrairement à d1, il a une autre composante forte pour serpent ce qui diminue sa similarité.

Quiz

Pourquoi un terme est-il considéré comme important pour un document?

1. Parce qu’il est rare dans le document

2. Parce qu’il est rare dans la collection

3. Parce qu’il est fréquent dans la collection et rare dans le document

4. Parce qu’il est rare dans la collection et fréquent dans le document

Je soumets une requête \(t_1 t_2 \cdots t_n\). Quel est le tf de chaque terme dans le vecteur représentant cette requête?

1. \(\frac{1}{n}\)

2. 1

3. \(\frac{1}{\sqrt{n}}\)

La normalisation de ce vecteur-requête est elle importante pour le classement ?

1. Non puisque cela revient à multiplier tous les rangs par une constante positive, et ne change donc pas l’ordre.

2. Oui car c’est la condition pour permettre le calcul du cosinus

3. Non car la normalisation n’a de sens que pour les documents, pas pour la requête

Dans la figure euclidiandistance, qu’obtient-on en projetant un vecteur sur l’axe d’un terme t ?

1. La norme du vecteur multipliée par le cosinus

2. L’idf du terme t

3. Le tf du terme t

4. Le tf.idf du terme t

Vecteurs dans un espace Euclidien

On exprime une requête avec un seul terme. Est-ce que l’idf du terme a une importance pour le classement?

1. Non puisque cela ne change pas la direction du vecteur

2. Oui car cela change sa norme

3. Non car son idf est forcément égal à 1 dans ce cas

Quel est le but de la normalisation ?

1. Unifier la taille des vecteurs décrivant les documents

2. Effacer les écarts entre les fréquences de termes dans un document

3. Utiliser une même représentation pour tous les documents

Comment caractériser un mot qui n’a aucun intérêt pour une recherche?

1. C’est un mot dont l’idf vaut 1

2. C’est un mot dont l’idf vaut 0

3. C’est un mot qui n’apparaît que dans un seul document

Quelle propriété est vraie pour le calcul de la similarité cosinus entre deux documents

1. On doit prendre en compte toutes les coordonnées des vecteurs

2. On ne prend en compte que les paires de coordonnées (1,1)

3. On ne prend en compte que les paires dont une coordonnée est non nulle

4. On ne prend en compte que les paires de coordonnées (0,0)

Deux documents de même longueur contiennent tous les deux le même nombre d’occurrences d’un terme t. Que peut-on en déduire sur le classement de ces documents si je fais une recherche avec l’unique terme t?

1. Ils seront tous les deux classés en tête avec une valeur cosinus de 1

2. Leur classement sera le même, mais pas forcément en tête

3. Leur classement dépend, pour chacun, des co-occurrences avec d’autres termes différents de t

Je soumets une requête composée de deux termes: \(t_1\) et \(t_2\), qui ont le même idf. Chaque document contient soit \(t_1\), soit \(t_2\), une seule fois, et jamais les deux ensemble. Quel sera le résultat?

1. Ils seront tous les deux classés en tête avec une valeur cosinus de 1

2. Leur classement sera le même, mais pas forcément en tête

3. Les documents sont classés selon leur taille

Exercices

Exercice Ex-S1-1: précision et rappel, calculons

Voici une matrice donnant les faux positifs et faux négatifs, vrais positifs et vrais négatifs pour une recherche.

Table de contingence

	Pertinent	Non pertinent
Ramené (positif)	50	10
Non ramené (négatif)	30	120

Quelques questions:

• Donnez la précision et le rappel.

• Quelle méthode stupide donne toujours un rappel maximal?

• Quelles sont les valeurs possibles pour la précision si je tire un seul document au hasard?

• Si j’effectue un tirage aléatoire, que penser de l’évolution de la précision et du rappel en fonction de la taille du tirage ?

Exercice Ex-S1-2: précision et rappel, réfléchissons.

Soit un système qui affiche systématiquement 20 documents, ni plus ni moins, pour toutes les recherches. Indiquez quel est la précision et le rappel dans les cas suivants:

• Mon besoin de recherche correspond à un document unique de la collection, il est affiché parmi les 20.

• Ma base contient 100 documents, je veux tous les obtenir, le système m’en renvoie 20.

• Je fais une recherche dont je sais qu’elle devrait me ramener 30 documents. Parmi les 20 que renvoie le système, je n’en retrouve que 10 parmi ceux attendus.

Exercice Ex-S1-3: proposons une autre mesure

Voici une autre mesure de qualité, que nous appellerons exactitude comme traduction de accuracy (exactitude). Elle se définit comme la fraction du résultat qui est correcte (en comptant les vrais positifs et vrais négatifs comme corrects). Donc,

\[accuracy = \frac{t_n + t_p}{t_n + t_p + f_n + f_p}.\]

Où p et n désignent les négatifs et positifs, t et f les vrais et faux, respectivement.

Cette mesure ne convient pas en recherche d’information. Pourquoi? Imaginez un système où seule une infime partie des documents sont pertinents, quelle que soit la recherche.

• Quelle serait l’exactitude dans ce cas?

• Quelle méthode simple et stupide donnerait une exactitude proche de la perfection?

Exercice Ex-S1-4: matrice d’incidence

Faire un fichier Excel (ou l’équivalent) qui calcule la taille d’une collection, la taille de la matrice d’incidence, et la densité de 1 dans cette matrice, en fonction des paramètres suivants :

• n, le nombre de documents,

• d, le nombre de termes distincts,

• m, le nombre moyen de mots dans un document,

• w, la taille moyenne d’un mot (en octets).

Exercice Ex-S1-5: algorithme de négation

On sait faire une fusion pour une recherche de type ET. La recherche de type OU est évidente (?). Montrer qu’un algorithme similaire existe pour une recherche de type NOT (« les documents qui parlent de loup mais pas de mouton »).

Exercice Ex-S1-6: recherches

Exprimez les recherches suivantes sur votre base de données

• les films dans lesquels on parle d’un « meurtrier »;

• même critère, mais en ajoutant le mot-clé « féroce »;

• films avec Kate Winslett et Leonardo di Caprio;

• films qui sont soit des drames, soit du fantastique;

• films avec le mot-clé « France »; obtient-on les films produits en France? Sinon pourquoi? Que faudrait-il faire?

• on recherche le film « Sleepy Hollow »; effectuez une recherche sur le titre (« Sleepy », « Hollow », « Sleepy Hollow ») puis sur le résumé.

• films satisfaisant une combinaison de critères: parus entre 1990 et 2000 et aux USA, ou contenant les mots-clés « Michael » et « Sonny »;

• etc.

Vous êtes invités à effectuer les recherches avec ou sans majuscules, à chercher des phrases comme « féroce et meurtrier », à indiquer ou non des noms de champs, et à interpréter les résultats (ou l’absence de résultat) obtenus.