La recherche de documents

Comment retrouver une information ?

• Étiquetage: par mots clés (vocabulaire contrôlé)
• Classification: catégories et sous-catégories
• Recherche plein texte (full-text)

Recherche plein texte

• Texte libre
• Porte sur le contenu textuel
• /!\ uniquement sur le contenu textuel

Les cousins germains

• Le tri-routage veille concurrentielle, alertes, filtrage, classification automatique
• Analyse sémantique catégorisation de contenu, repérage d'entités nommées, analyse de sentiments

Moteur de recherche

• Service permettant de trouver/retrouver des documents
• À partir d'une requête en texte libre

Objectif

Trouver les documents pertinents qui correspondent à la requête

Première étape

Trouver les documents

L'index inversé

cette brique technique injustement méconnue

Pourquoi inversé

• Pas inversé: du document vers les éléments qui le composent Doc1 → mot1, mot2, mot3, ... Doc2 → mot2, mot4, mot5, ...
• Inversé: de l'élément vers les documents qui le contiennent Mot1 → Doc1, Doc45, Doc76, ... Mot2 → Doc1, Doc2, Doc18, ...

Mise en application

Recherche dans une base de 2 documents

Recherchons dans l'index inversé

• chat
• Félix le chat
• miauler granges
• felix

Recherche dans une base de 2 documents (2)

Normalisation du texte: minuscule sans accent

Recherchons dans l'index inversé

• chat
• Félix le chat
• miauler granges
• felix

Recherche dans une base de 2 documents (3)

minuscule sans accent + lemmatisation (lemme = forme canonique, «neutre»)

• chat
• chattes
• miauler granges
• avoir grange

Résumé de la mise en pratique

• Un index inversé
• Un pré-traitement de normalisation (textuel ou linguistique) sur les mots
• Mais des problèmes et difficultés: choix des prétraitements - pertinence - niveau de normalisation

Calculer la page de résultat

Qu'est-ce qu'un résultat?

Calculer un résultat

Ensembles & algèbre booléenne

1 terme = 1 ensemble de documents Le résultat est l'intersection des ensembles

Calcul de score

1 terme = 1 ensemble de documents On attribue un total de scores à chaque document Le résultat est la liste des documents triés par leur score

Évaluer les résultats

interlude mathématique

Contexte documentaire

Évaluer la qualité

La précision

Calcul le taux de faux positifs (documents non-pertinents retournés)

Le rappel (recall)

Calcul le taux de faux négatifs (documents pertinents ratés)

Impact des pré-traitements

Normalisation «légère»

minuscule, effacement des diacritiques, lemmatisation

→ Bonne précision, rappel bas

Normalisation «agressive»

normalisation phonétique, racinisation

→ Précision basse, bon rappel

Traitements du texte

Chaine de traitement

Chaine de traitement (2)

Document brut

Demain, les élèves mangeront des frites.

Tokens

Demain les élèves mangeront des frites

Normalisation (casse + diacritiques + lemmatisation)

demain un eleve manger un frite

Exemple historique

Soundex

• Algorithme de normalisation phonétique, breveté en 1918, utilisé par l'administration US
• Destiné à effacer les variances de prononciation et d'écriture
• Algorithme dans wikipédia

Exemple

Type de normalisations et pré-traitements

• Normalisations textuelles: casse, effacement des diacritiques
• Normalisations linguistiques: lemmatisation, racinisation
• Normalisation phonétiques: Soundex, métaphone, double-métaphone, Snowball, etc
• Filtrage: stop words
• Normalisation mathématiques: bi-grams

Lemmatisation

• Transformation en forme canonique infirmières → infirmier des/une → un
• Ambiguités homographiques tu jumelles (→ jumeler) vs (des jumelles → jumelle)
• Sensibles aux erreurs typographiques
• bonne précision

Racinisation

• Ou stemming en anglais
• Transformation vers la racine morphologique supposée mang ← manger+flexions, mangeur mens ← mentir+flexions, menteur, mensonge
• Ambiguités sémantiques et morphologiques général - généraliser - généralement
• Par algorithmes ou par dictionnaires

Stop words

• Technique permettant d'éviter les faux négatifs
• Élimination des mots trop communs pour être discriminants
• Pronom, déterminants, adverbes
• Verbes faibles (auxilliaires et verbes support ou sémantiquement faibles) do, give, have, make, take
• De moins en moins utilisés

Multiplions les index

Multiplions les index

Pourquoi faire ?

• Améliorer les résultats
• Un index par type de normalisation
• Pondérer les index/les normalisations
• Répercuter dans les scores des documents
• → #WIN

Multiplions les index

Exemple

Requêtes

seau - sot - sceau regardons ce gavage il me gave

Multiplions les index

Créons notre algorithme !

Tous les index que l'on veut !

• texte exact
• casse
• diacritiques
• casse+diacritiques

• lemmatisation
• racinisation
• n-grams
• phonétique

Multiplions les index

Pondérons

• texte exact 1.0
• casse 0.9
• diacritiques 0.9
• casse+diacritiques 0.8

• lemmatisation 0.6
• racinisation 0.3
• n-grams 0.6
• phonétique 0.5

Utilisation

• Chaque index, suivant sa normalisation, offre un niveau de pertinence différent
• Le calcul de score peut utiliser un ou plusieurs index

Elements de l'algorithme

Modifieurs lexicaux possible

• Index utilisés
• Fréquence de l'unite lexicale dans le document
• Le nombre d'unités lexicales dans le document
• La fréquence du mot dans la langue
• Fréquence dans des champs spécifiques

Modifieurs contextuels

• Langue utilisée
• Colocation des termes (n-grams)
• Classification sémantique du document
• « PageRank» du site, nombre de pointeurs vers le doc
• Date de publication
• clic sur résultat, pays, centres d'intérêt, sexe, ...

etc etc

Résumé

L'algorithme

Une function heuristique pondérant une grande variétés de paramètres

Difficultés d'un moteur de recherche

• Trouver les documents qui correspondent à la requête Trouver les documents qui correspondent à ce que cherche l'utilisateur
• Les difficultés de la langue ni sémantique, ni énonciation
• La course au positionnement
• L'évaluation des améliorations
• Les temps de réponse

The end