Webschool Tours
S08E05
Démystifions les moteurs de recherche
http(s)://reyesr.github.io/webschool-tours-S08E05-moteurs-de-recherche
Votre speaker
Rodrigo Reyes
- Linguiste
- Informaticien
- CTO Orthomatique
À propos
Sujets traités
- La recherche de documents textuels
- Les traitements linguistiques qui améliorent les résultats
Sujets non-traités
- « l'algorithme de Google »
- Ni rien sur comment améliorer son positionnement SEO
Présentation destinée à l'édification personnelle
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
| Doc1 | Le, chat, a, miaulé, dans, la, grange |
| Doc2 | Félix, le, chat, repartira, demain |
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
| Doc1 | le, chat, a, miaule, dans, la, grange |
| Doc2 | felix, le, chat, repartira, demain |
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»)
| Doc1 | le, chat, avoir, miauler, dans, le, grange |
| Doc2 | felix, le, chat, repartir, demain |
- 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)
| Précision = | Nombre de résultats pertinents retournés |
| Nombre total de résultats retournés |
Le rappel (recall)
Calcul le taux de faux négatifs (documents pertinents ratés)
| Rappel = | Nombre de résultats pertinents retournés |
| Nombre total de résultats pertinents dans la base |
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
- Tokenisation: découpages en unités lexicales
Spécifique à chaque langue
mots multiples: compte rendu, aujourd'hui, donne-moi vs couvre-feu
patterns particuliers: (800) 123-4567, 11/02/2016 -
Normalisation: transformer chaque unité lexicale
Également spécifique à chaque langue
Grande variété de normalisations -
Stockage: chaque unité lexicale pointe sur un ensemble de documents
Pondération contextuelle (titre, corps de page, annexes)
Nombre d'occurrences, colocations,
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
| Doc1 | Regarde, ces seaux débordent
[casse+diac] regarde ces seaux debordent [stemming] regard un seau debord [phonet.] røgard ce so debɔrd |
| Doc2 | Ce sot me gave
[casse+diac] ce sot me gave [stemming.] ce sot m gav [phonet.] cø so mø gav |
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 !
|
|
Multiplions les index
Pondérons
|
|
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