Indexation et recherche d'information
Vincent Labatut
1 QCM chaque séance, "c'est pour vérifier que vous travaillez régulièrement"
utilisateur : a besoin d'une information
collection : de documents (= tout fichier qui contient de l'information = données non structurées)
besoin (de l'utilisateur) : les documents recherchés sont ceux qui correspondent au besoin
pour résoudre ce problème général, il faut résoudre les 4 sous-problèmes : représentation, stockage, organisation, accès
"il existe beaucoup de moyens, on va en voir 3" :
la recherche d'information est plus ancienne que l'informatique, mais depuis que l'informatique existe, on distingue 2 approches (complémentaires) de RI : humaine/machine
besoin informationnel (𝑏) : le renseignement que l'utilisateur désire, implicite (langage naturel)
corpus (𝐶) : collection des documents (𝑑)
lexique : ensemble des mots qui composent le corpus
requête (𝑞) : formulation explicite et non ambiguë du 𝑏 (langage formel)
résultat (𝑅) : sous-ensemble 𝑅 ⊂ 𝐶, ou séquence (quand le sous-ensemble est trié)
pour évaluer un moteur de recherche on peut soit s'intéresser aux documents qu'il oublie de renvoyer (faux négatifs, ou FN), soit aux documents qu'il renvoie en trop (faux positifs FP)
pertinence de la requête : les résultats pertinents pour la requête "livre python" ne sont pas les mêmes pour un programmeur ou un biologiste
"on veut un moteur de recherche qui nous renvoie tous les documents pertinents (rappel), et seulement les documents pertinents (précision)"
greping : approche naïve
Matrice d'incidence 𝑇 × 𝐷 : "on va parcourir tous les textes une seule fois"
soit 𝓣 l'ensemble des termes 𝑡 du corpus
dans le modèle "bag-of-words", 𝑑 correspond à 𝓣 (𝑑 = {𝑡𝑗1, ..., 𝑡𝑗𝑀})
tables de vérité :
| & (∧) | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| &! (∧¬ ) | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
exemple : Brutus ∧ (et) Caesar ∧¬ (n'est pas) Calpurnia
"cette méthode va très vite, mais elle est gourmande en mémoire" : une meilleure représentation est possible
DocID : "c'est le même principe qu'une clé étrangère"
fichier inversé : on liste tous les postings 𝓁 (= les DocID) de chaque terme 𝑡
"ça prend beaucoup moins de place en mémoire, mais le traitement est moins direct"
exemples :
"à présent, j'aimerais rentrer dans les détails linguistiques : la tokénisation, les mots vides, et la formalisation"
"la première étape, c'est la constitution du corpus" : l'index comportera toutes les informations dont on a besoin pour la recherche
cette tâche dépend énormément du format des données à indexer, "le web va nécessiter d'effectuer un crawl par exemple", le PDF peut nécessiter de l'OCR, etc.
"écrire du code qui sait lire tous les encodages, ça pose beaucoup de problèmes en informatique"
un document = un fichier ? "c'est pas si évident"
tokénisation : "dans cet exemple, l'algo considère que les virgules ne sont pas des mots, dans les langues latines c'est presque toujours le cas"
unité sémantique : "on recherche toujours la plus petite valeur qui a du sens"
la position permet de distinguer les tokens : "friends à la 1ère position n'est pas le même token que friends à la 8e position" (mais ils sont du même type)
un terme n'est pas forcément un mot du dictionnaire : par ex. index sémantique ("voiture" et "automobile" sont regroupés dans un seul terme), "on ne va pas en parler dans ce cours"
"et le plus souvent, on va exclure certains mots des termes car ils ne sont pas assez discriminants, ils ne permettent de distinguer un document à eux seuls" (pronoms, stop words)
racinisation = stemming (confond les flexions et les dérivations)
lemmatisation = exclut les dérivations et ne traite que les flexions
contrairement aux flexions, les dérivations ne vont changer ni le genre, ni le nombre, ni le temps, ni la voix... mais juste la sémantique
| - | d1 | d2 | d3 |
|---|---|---|---|
| bon | 0 | 1 | 0 |
| chat | 1 | 1 | 1 |
| chien | 0 | 1 | 1 |
| courir | 1 | 1 | 1 |
| etre | 0 | 1 | 0 |
| faire | 0 | 1 | 1 |
| jardin | 0 | 1 | 1 |
| laisser | 0 | 1 | 0 |
| piege | 1 | 0 | 0 |
| pierre | 0 | 1 | 1 |
| preparer | 1 | 0 | 0 |
| savoir | 1 | 1 | 0 |
| souris | 1 | 0 | 0 |
| tour | 0 | 1 | 1 |
| voisin | 0 | 1 | 1 |
"Le ∧ chien ∧ court" = chien ∧ courir = 011 & 111 = 011
| terme | 𝑑𝑓(𝑡) | postings |
|---|---|---|
| bon | 1 | d2 |
| chat | 3 | d1, d2, d3 |
| chien | 2 | d2, d3 |
| courir | 3 | d1, d2, d3 |
| etre | 1 | d1 |
| faire | 2 | d2, d3 |
| jardin | 2 | d2, d3 |
| piege | 1 | d1 |
| pierre | 2 | d2, d3 |
| preparer | 1 | d1 |
| savoir | 2 | d1, d2 |
| souris | 1 | d1 |
| tour | 2 | d2, d3 |
| voisin | 2 | d2, d3 |
Si 𝑑𝑓(𝑡) est faible et 𝑡𝑓(𝑑,𝑡) est élevé, la recherche sera plus pertinente, mais les scores se comportent de façon opposée
il faut donc transformer 𝑑𝑓(𝑡) pour inverser son comportement :
GET /festival_cannes_2015/_search
{
"query": {
"match": {"from_user": "BSidelhadj"}
}
}
GET /festival_cannes_2015/_search
{
"query": {
"match": {"from_user": "dandy_cannes"}
}
}
Le nombre de résultats est indiqué dans "hits" : { "total" : {"value" : 8592,
GET /festival_cannes_2015/_search
{
"query": {
"match": {"from_user": "dandy_cannes BSidelhadj"}
}
}
La requête ci-dessus renvoie 8596 résultats (8592 + 4)
match va donc renvoyer les résultats pour chaque terme (équivalent du booléen OU)
GET /festival_cannes_2015/_search
{
"query": {
"term": {"from_user": "dandy_cannes"}
}
}
même requête mais avec "term": {"from_user": "BSidelhadj"} : 0 résultat
même requête sans majuscules ("term": {"from_user": "bsidelhadj"}) : on retrouve bien les 4 résultats
term ne cherche que la valeur exacte indexée : les majuscules étant supprimées par la normalisation des champs texte, BSidelhadj devient donc bsidelhadj lors de l'indexation
GET /festival_cannes_2015/_search
{
"query": {
"match": {"content": "beau temps Cannes"}
}
}
Renvoie exactement 10000 "hits"
GET /festival_cannes_2015/_search
{
"query": {
"match": {
"content": {
"query" : "beau temps Cannes",
"operator" : "and"
}
}
}
}
Renvoie 628 résultats
GET _search
{
"query": {
"match_phrase": {"content": "beau temps Cannes"}
}
}
Seulement 2 résultats : les mots exacts sont recherchés
avec "beau temps a cannes" : 456 résultats, le mot "#cannes" est normalisé en "cannes"
avec "beau temps à cannes" : 0 résultats (le "à" n'est donc pas normalisé)
GET _search
{
"query": {
"bool": {
"must": [
{"match": {"content": "beau"}},
{"match": {"content" : "temps"}},
{"match": {"content" : "cannes"}}
],
"must_not": {
"match_phrase": {"content": "beau temps cannes"}
}
}
}
}
GET _search
{
"query": {
"multi_match": {
"query" : "codeurs",
"fields" : ["from_user", "content"]
}
}
}
GET _search
{
"query": {
"range": {
"created_at" : {"gte": "2016-10-01", "lte" : "2016-10-03"}
}
}
}
GET _search
{ "query":
{ "bool":
{"must" :
[
{"match" :
{"content" : "Sicario"}
},
{"match" :
{"iso_langage_code" : "fr"}
}
],
"filter" :
{"range" :
{"created_at" :
{"gte" : "2015-05-13"}
}
}
}
}
}
Avec un must_not à la place du filter :
GET _search
{ "query":
{ "bool":
{"must" :
[
{"match" :
{"content" : "Sicario"}
},
{"match" :
{"iso_langage_code" : "fr"}
}
],
"must_not":
{"range" :
{"created_at" :
{"lt" : "2015-05-13"}
}
}
}
}
}
En favorisant les tweets mentionnant Emily Blunt :
GET _search
{ "query":
{ "bool":
{"must" :
[
{"match" :
{"content" : "sicario"}
},
{"match" :
{"iso_langage_code" : "fr"}
}
],
"must_not":
{"range" :
{"created_at" :
{"lt" : "2015-05-13"}
}
},
"should":
{"match" :
{"content" : "emily blunt"}
}
}
}
}
GET _search
{ "size" : 0,
"aggs" :
{ "my_aggs" :
{ "filters" :
{ "filters" :
{ "english" :
{ "match" :
{"iso_langage_code" : "en"}
},
"portugese" :
{ "match" :
{"iso_langage_code" : "pt"}
},
"spanish" :
{ "match" :
{"iso_langage_code" : "es"}
}
}
}
}
}
}
L'espagnol est plus utilisé que le portugais
GET _search
{ "size" : 0,
"aggs" :
{ "languages" :
{ "filters" :
{"other_bucket_key": "other_languages",
"filters" :
{ "english" :
{ "match" :
{"iso_langage_code" : "en"}
},
"portugese" :
{ "match" :
{"iso_langage_code" : "pt"}
},
"spanish" :
{ "match" :
{"iso_langage_code" : "es"}
}
}
}
}
}
}
GET _search
{ "size" : 0,
"aggs" :
{ "size" :
{ "avg":
{ "field": "display_text_range"}
}
}
}
si 100% des documents sont des TP ou des TN, il n'y a aucun faux = le rapport est de 1
si il n'y a que des erreurs, le rapport sera de 0
"c'est la mesure de base utilisée en classification, par contre elle n'est pas tellement adaptée aux problèmes que l'on traite en recherche d'information" : "les classes seront déséquilibrées en faveur des documents non pertinents"
Précision :
Rappel :
𝐹-mesure élevée = scores de précision et rappel élevés
𝐹-mesure intermédiaire = un des 2 scores est plus faible
𝐹-mesure faible = les 2 scores sont faibles
"vous devriez pouvoir calculer ça à l'examen"
"on a l'impression que les moteurs de recherche en entreprise vous renvoient des résultats moins pertinents que ceux de Google, pourtant les technologies sont les mêmes"
"je suis responsable de master, en ce moment j'ai 600 dossiers Monmaster à traiter, y'a des étudiants qui m'ont envoyé leur relevé de notes pris en photo, parfois c'est illisible, c'est comme s'ils n'avaient pas envoyé leur relevé en fait"