Cours SRI - GI5, 2024-2025 PDF

Systèmes de RI Pr. S Bouzid Génie informatique – 5ème année Année universitaire 2024 - 2025 1 SRI & Big Data  Plan Introduction: Définitions autour de la RI...

Systèmes de RI Pr. S Bouzid Génie informatique – 5ème année Année universitaire 2024 - 2025 1 SRI & Big Data  Plan Introduction: Définitions autour de la RI Domaines de la RI Historique Problématique de la RI L’indexation Les modèles de RI L’évaluation d’un SRI La RI sur le web 2 SRI & Big Data  Introduction 3 SRI & Big Data  Introduction Le domaine de la recherche d’information remonte au début des années 1950 : explosion des informations après la seconde guerre mondiale avènement de l’informatique (et de l’utilisation des ordinateurs) popularisation de l’internet Les pionniers de l’époque étaient enthousiastes à utiliser l’ordinateur pour automatiser la recherche d’information, dépassant la capacité humaine Les informations étaient principalement contenues dans des documents textuels Problématique abordée: comment rechercher des informations dans une base de documents volumineuse de 4 manière rapide et efficace SRI & Big Data  Définition - RI Définition de la RI: La recherche d’information (RI) est une branche de l’informatique qui s’intéresse a l’acquisition, l’organisation, le stockage, la recherche et la sélection d’information [salton, 1968] Terminologies utilisées: Recherche d’information (RI) - Information Retrieval (IR) Recherche de document – Document Retrieval Finalité: Sélectionner dans une collection (de documents) les informations pertinentes répondant à un besoin précis 5 SRI & Big Data  Définition - RI Trois notions clés se dégagent : Document (quels documents) Requête (comment correspondre la requête et les documents) Pertinence (comment évaluer le résultat) La notion de document en RI: Document textuel Page web (fichiers web , mail, …) Images, Vidéos Mélange de types (textes, images, …) dans un format précis => On appelle « document » dans la RI toute ressource d’information qui peut constituer une réponse à une requête d‘un utilisateur 6 SRI & Big Data  Définition - RI Remarques: Dans la RI: l’information recherchée est textuelle, mais peut être retrouvée dans différents formats de documents / fichiers Pour les images et les vidéos (ou tout autre fichier multimédia), leurs métadonnées sont utilisées en premier Il existe une autre branche de la RI (recherche d’image - image retrieval) qui se focalise sur la recherche d’image à partir d’une requête sous forme d’image (comparaison d’images…). Il ne s’agit pas d’une recherche textuelle (hors sujet de ce cours). 7 SRI & Big Data  Domaines de la RI Domaines d’applications: GED (gestion électroniques de documents) Recherche sur le web Réseaux sociaux Bibliothèques numériques Monde de l’entreprise (toute activité métier produisant des documents) Recherche scientifique Nos propres ordinateurs (bureautique et autre) … 8 SRI & Big Data  Domaines de la RI Domaines d’application connexes : Classification / catégorisation (clustering) Web sémantique (semantic web) Systèmes de Questions-réponses (Query Answering) Systèmes de Recommandation (Recommendation systems) L’IA (intelligence artificielle) Fouille de textes (Text mining) Gestion des connaissances (knowledge management) … 9 SRI & Big Data  Définition - SRI Un système de recherche d'information (SRI) est un système qui permet de retrouver les « documents pertinents » à une requête utilisateur (textuelle) Exemples de SRI: Moteur de recherche Web (google, bing, …) Systèmes de RI documentaires (tels que pour la recherche d’articles scientifiques) Systèmes de RI dans les logiciels de GED Systèmes de RI spécifiques à une base de documents d’une entreprise 10 SRI & Big Data  Définition - SRI Remarque: Il ne faut pas confondre systèmes de bases de données et systèmes de RI Les SRI se focalisent sur la recherche d’informations textuelles dans des ressources telles que des documents La recherche (requêtage) dans des BD (relationnelles ou non relationnelles) ne relève pas du domaine de la RI, car : ces BD contiennent des données (et pas des informations) organisées suivant un certain schéma (modèle) de stockage (les données ont un modèle de conception métier) le résultat renvoie des données (table, liste de données) et pas des documents 11 SRI & Big Data  Historique La RI date des années 1940, dès la naissance des ordinateurs. Le nom de « recherche d’information » (information retrieval) fut donné par Calvin N. Mooers en 1948 [MOO 48] pour la première fois quand il travaillait sur son mémoire de maîtrise Au début, la RI se concentrait sur les applications dans des bibliothèques (on utilisait le nom "automatisation de bibliothèques") Dans les années 1950, on commençait de petites expérimentations en utilisant des petites collections de documents (références bibliographiques). Le modèle utilisé est le modèle booléen 12 SRI & Big Data  Historique La première conférence dédiée au thème de la RI – International Conference on Scientific Information - s’est tenue en 1958 à Washington Les premiers problèmes qui intéressaient les chercheurs portaient sur comment retrouver les documents (avec quels mots, quels termes) => la notion d’index est devenue au centre des recherches Dans les années 1960 et 1970, des expérimentations plus larges ont été menées, et des méthodologie pour évaluer les systèmes de RI ont vue le jour. Des corpus de test (e.g. CACM) ont été conçus pour évaluer des systèmes différents de RI. Ces corpus de test ont beaucoup contribué à l'avancement de la RI 13 SRI & Big Data  Historique Parmi les projets d’expérimentation menés sur la RI : Projet Cranfield (dirigé par Cyril Cleverdon, 1957-1967) [CLE 67]: on visait à tester l’efficacité de différentes façons d’indexer et de rechercher des documents. C’est dans ce projet que les mesures précision et rappel (precision and recall) on été inventées. Ces mesures sont encore utilisées aujourd’hui pour évaluer la pertinence des résultats obtenus par rapport aux résultats souhaités Projet MEDLARS – MEDical Literature Analysis and Retrieval System (F. Wilfrid Lancaster, complete en 1968) [LAN 68]: il s’agit d’expérimentation de la RI dans le domaine biomédical. Les documents sont indexés manuellement, avec un vocabulaire contrôlé (choisi). Les résultats évalués (avec précision et rappel) ont montré que l’utilisation d’un vocabulaire contrôlé avec l’indexation manuelle est efficace mais restreint la pertinence des résultats. 14 SRI & Big Data  Historique SMART (Gerard Salton, 1ière version 1961-1965) [SAL 71] : celui qui a eu le plus d’impact sur la RI est le système SMART, développé entre les années 1960 et début des années 1970. Les travaux sur ce système ont été dirigés par G. Salton, professeur à Cornell university (NY). De nouvelles techniques ont été implémentées et expérimentées pour la première fois dans ce système telles que: l’utilisation du modèle vectoriel, la technique de « relevance feedback », le regroupement de documents / clustering, …). Le système SMART fut réécrit dans les années 1970 et 1980 par E. Fox et C. Buckley. Ce système a été, et est encore aujourd’hui, utilisé par de nombreux chercheurs pour des expérimentations en RI. 15 SRI & Big Data  Historique Les années 1980 ont été influencées par le développement de l'intelligence artificielle. Ainsi, on tentait d'intégrer des techniques de l'IA dans la RI (par exemple, système expert pour la RI, etc.). Les années 1990 (surtout à partir de 1995) sont les années de l’avènement de l'Internet. Cela a eu pour effet de propulser la RI en avant et sur sur le web (apparition des moteurs de recherche web). La problématique de la RI a été élargie à d’autres types de documents/fichiers tels que le multimédia (et encore plus aujourd’hui avec les réseaux sociaux). Les techniques de base utilisées dans les moteurs de recherche web sont celles connues de la RI. Des améliorations et des spécificités liées au web ont été apportées par la suite. 16 SRI & Big Data  Problématique de la RI 17 SRI & Big Data  Problématique de la RI Besoin d’information How? Sources d’information Input Matching Requête utilisateur … Documents textuels, images, vidéos, … Output 18 SRI & Big Data  Problématique de la RI Besoin d’information Sources d’information Input Matching Requête utilisateur … Documents textuels, images, vidéos, … Output 19 SRI & Big Data  Problématique de la RI Besoin d’information : Il s’agit d’une expression mentale de l’utilisateur Le même besoin peut être exprimé de différentes manières, selon l’utilisateur… Requête utilisateur: Est une représentation possible du besoin de l’utilisateur Peut prendre les formes suivantes : Texte libre, texte avec operateurs (AND, OR, NOT,…) Liste de mots clés (vocabulaire contrôlé) Images, sons Par navigation dans une collection Hashtag (cas des réseaux sociaux) … 20 SRI & Big Data  Problématique de la RI Problématique du besoin : Une requête idéale doit comporter toutes les informations que l’utilisateur recherche, la similarité serait alors optimale (et maximale) Or, l’utilisateur recherche une information qu’il ne connait pas a priori, il ne peut donc pas l’exprimer (décrire) de maniere précise (ideale) Le besoin est donc exprimé de manière approximative Le besoin est subjectif car dépend de l’utilisateur qui l’exprime 21 SRI & Big Data  Problématique de la RI Besoin d’information Sources d’information Input Matching Requête utilisateur … Documents textuels, images, vidéos, … Output 22 SRI & Big Data  Problématique de la RI Sources d’information : Ressources d’information (documents / fichiers) Formes des ressources : Texte images, sons, vidéo, graphiques, etc. Propriétés des ressources : Non structurée : texte brut (plain text) Structurée ou semi structurée (XML, HTML, …) Hétérogénéité Langage (contenu multilingue) Format connu (documents, images, vidéos,…) Format spécifique (issue d’applications métier…) 23 SRI & Big Data  Problématique de la RI Exemple semi-structuré: livre numérique (métadonnées + texte brut): 24 SRI & Big Data  Problématique de la RI Deux classes d’information: Méta-information, métadonnées (données/informations à propos du document) Attributs : titre, auteur, date de création, etc. Structure (organisation du contenu) : structure logique, liens,... Contenu : Contenu brut : texte du document Contenu sémantique : texte ayant du sens (information) extrait à partir du contenu brut 25 SRI & Big Data  Problématique de la RI Problématique des sources d’information : Beaucoup de formes et d’hétérogénéités dans les documents Quantité importante d’informations L’utilisateur ne connait pas les sources d’information à l’avance (pas nécessairement). L’information recherchée est noyée dans d’autres informations => Comment peut-on parcourir autant de sources d’information et en sélectionner les plus pertinentes par rapport à un besoin utilisateur ? 26 SRI & Big Data  Problématique de la RI Besoin d’information Sources d’information Input Matching Requête utilisateur … Documents textuels, images, vidéos, … Output 27 SRI & Big Data  Problématique de la RI Matching (mise en correspondance) : => Deux approches possibles: Approche simple de la RI : Correspondance mot à mot Trouver les documents ayant X Y Z les mêmes mots que la requête La requête et les documents sont des listes de mots clés (texte) On parcourt séquentiellement les textes des documents en recherchant les occurrences de chaque mot-clé de la requête On sélectionne les documents et classe les résultats : les documents qui contiennent le plus de mots de la requête sont présentés en premier 28 SRI & Big Data  Problématique de la RI Critique de l’approche simple: Efficace pour des bases de textes de petite taille : le temps de calcul est linéaire dans la taille de la base Pas de prétraitement de la requête ni des textes : caractères spécifiques (accents,...), mots de même famille => risque de passer à côté de certains documents Problème de Vitesse: L'opération de recherche est très lente. Pour chaque requête, on doit parcourir tous les documents dans la base. Dans la pratique, il y en a des centaines de milliers, voire des millions. Il n'est donc envisageable d'utiliser cette approche que sur des collections très petites (avec un contenu textuel pas très chargé) 29 SRI & Big Data  Problématique de la RI Exemples de SRI avec l’approche simple : Recherche de fichiers de code dans les Frameworks de développement informatique Recherche dans les e-mails (outlook, gmail, …) Fonctionnalité de recherche dans l’historique de navigation dans un navigateur web 30 SRI & Big Data  Problématique de la RI Approche par indexation : Correspondance Correspondance entre les X Y Z mots de la requête et les Index index (représentations des documents) Représentations Principe : On ne peut pas parcourir les documents à chaque requête => On va donc prétraiter les documents pour identifier de manière rapide dans quel document apparaît chaque mot recherché Technique : => L’indexation Prétraiter les documents (sélectionner les termes clés qui les représentent) Constituer une liste de termes pour chaque document Construire une structure de données associant termes et documents => 31 Base d’index SRI & Big Data  Problématique de la RI Critique de l’approche par indexation: Elle est plus rapide car plus besoin du parcours séquentiel. Avec la structure d'index, on peut directement savoir quels sont les documents qui contiennent tel ou tel mot L’expression des requêtes peut être intelligente (avec des opérateurs de logique ente les mots), exprimant des besoins d'information complexes Le prix à payer pour ces avantages est le besoin d’espace de stockage supplémentaire pour la structure d'indexes. En général, cet espace peut aller de 40% jusqu’à 200% de la taille de la collection de documents, selon la complexité de l'indexation 32 SRI & Big Data  Problématique de la RI Exemples de SRI avec l’approche par indexation: Tous les moteurs de recherche web, Certains moteurs intégré dans les logiciels du marché (logiciels professionnel de gestion, ERP, CRM,…), Outils de GED, Moteur de recherche des réseaux sociaux, … 33 SRI & Big Data  Problématique de la RI Besoin d’information Sources d’information Input Matching Requête utilisateur … Documents textuels, images, vidéos, … Output 34 SRI & Big Data  Problématique de la RI Pertinence des résultats : La pertinence est le degré de correspondance entre une requête et la liste des documents retournés en résultats Côté utilisateur humain, la pertinence est subjective: les résultats peuvent paraitre pertinents pour un utilisateur et pas assez pertinents pour un autre (pour une même requête) Côté système, la pertinence est algorithmique : termes de la requête dans un document (grâce aux index) = document pertinent Le but de rechercher l’information dans un SRI est de trouver seulement les documents pertinents à une requête, et pertinents pour la majorité des utilisateurs du système Aucun système de RI n’est parfait. L’objectif final est de trouver le bon rapport entre requête/résultat 35 SRI & Big Data  Synthèse de la problématique Caractéristiques d’un SRI : Le système doit être simple à utiliser (expression facile de la requête, possibilité d’exprimer des requêtes logiques,…) Le système doit conjuguer avec les différents formats et contenus des documents / sources d’information Le système doit fournir les meilleures réponses possibles, et ces réponses doivent être « pertinentes » pour l’utilisateur Le système doit fournir un nombre raisonnable de réponses Le système doit fournir des réponses rapides (délai raisonnable) => Comment essayer de satisfaire toutes ces caractéristiques à la fois? Solution = Indexation + Modèle de RI 36 SRI & Big Data  L’indexation 37 SRI & Big Data  L’indexation Sources d’information Besoin d’information Input … Documents textuels, images, vidéos, … Matching Requête utilisateur Index Index Index Output 38 SRI & Big Data  L’indexation C’est quoi l’indexation? Processus permettant de construire un ensemble de termes clés (« index ») permettant de représenter le contenu de chaque document L’index peut représenter : Un mot simple: « pomme » Un groupe de mots : « pomme de terre » L’indexation peut être : Manuelle (experts des documents) Automatique (ordinateur) Semi-automatique (combinaison des deux) Basée sur : Un langage libre (éléments pris directement des documents) Un langage contrôlé (lexique, thesaurus, ontologie/réseau sémantique,…) 39 SRI & Big Data  Vocabulaire contrôlé Types de vocabulaires contrôlés: Lexique : Liste de mots dans un domaine Liste hiérarchique (taxonomie) : de concepts, de notations,… Thésaurus : Liste de mots dans un domaine + relation de synonymie entre les mots Ontologie / réseau sémantique : Liste de concepts + relations (sémantiques) entre les concepts Dictionnaire de mots : Exemple : WordNet (pour l’anglais) 40 SRI & Big Data  Vocabulaire contrôlé WordNet est un dictionnaire (gratuit) de mots anglais créé par des chercheurs à l’université de Princeton Contenu de WordNet : Mots en anglais organisés en synsets : ensembles de mots synonymes Les synsets ont des définitions et des relations entre elles Un mot peut appartenir à plusieurs synsets Relations sémantiques entre synsets : Hyperonymie/hyponymie(généralisation/spécialisation) : is-a Antonymie (opposé à) 41 SRI & Big Data  Exemple : « City » dans WordNet 42 SRI & Big Data  Types d’indexation Manuelle Automatique Semi-automatique 43 SRI & Big Data  L’indexation manuelle Idée de l’Indexation manuelle : On identifie pour chaque document les termes clés qui les représentent On enrichie manuellement la base d’indexes (Terme / Documents). Les termes peuvent être issus d’un langage contrôlé (recommandé) L’indexation manuelle se fait par le biais d’une interface d’indexation telle un formulaire (pas besoin d’être un informaticien) Précondition: Nécessité d’être un expert des documents concernés par l’indexation (bien connaître les documents et leur contenu) 44 SRI & Big Data  L’indexation manuelle Exemple : 45 SRI & Big Data  L’indexation manuelle Cas d’application : Souvent utilisées pour l’indexation des livres dans les bibliothèques et les centres de documentation Indexation de fichiers multimédias (images, vidéos, sons/ enregistrements vocaux, …) Indexation de fichiers spécifiques d’applications (cas où il est difficile d’en extraire du texte, ou le texte n’a pas de sens) 46 SRI & Big Data  L’indexation manuelle Avantages : Permet l’indexation de tous documents/fichiers sans se soucier de leurs formats et contenus Cas d’utilisation d’un vocabulaire contrôlé : Fournit une terminologie standard pour indexer et rechercher les documents Permet la classification (regroupement) de documents (par sujets, thème,…) Permet facilement une recherche par navigation dans les concepts et terminologies 47 SRI & Big Data  L’indexation manuelle Inconvénients : Indexation très coûteuse: pour construire le vocabulaire pour affecter les concepts (termes) aux documents Difficile à maintenir: La terminologie évolue, plusieurs termes sont rajoutés tous les jours Processus humain donc subjectif : Des termes différents peuvent être affectés à un même document par des indexeurs (humains) différents Les utilisateurs ne connaissent pas forcément le vocabulaire utilisé par les indexeurs 48 SRI & Big Data  Types d’indexation Manuelle Automatique Semi-automatique 49 SRI & Big Data  L’indexation automatique Idée de l’indexation automatique : Le système (programme) informatique se charge de parcourir chaque document et d’en extraire les termes qui serviront à l’indexation Approche : L’approche courante est statistique avec les hypothèses suivantes: La redondance d’un mot marque son importance La cooccurrence des mots marque le sujet d’un document Autre critère pouvant être pris en compte: la position du terme dans le document (important dans le cas où la requête est une expression) 50 SRI & Big Data  L’indexation automatique : les étapes Démarche générale de l’indexation automatique : Etape 1 : Extraction des termes Etape 2 : Normalisation des mots / lemmatisation (regroupement des variantes d’un mot ) Etape 3 : Pondération (discrimination entre les termes clés/importants/significatifs et les autres) 51 SRI & Big Data  L’indexation automatique : les étapes Etape 1 : Extraction des termes Extraction de termes = tokenization Terme (tocken) : mot (simple/compose), mots clés, concepts Mot : suite de caractères séparés par des séparateurs (espace, signe de ponctuation, caractères spéciaux, retour à la ligne, tabulation,…), Nombres Les termes retenus seront les index utilisés pour la recherche Il faut prendre en compte les spécificités des langues : Langue française : Pomme de terre : 1, 2 ou 3 termes? Langue Allemande les mots composés ne sont pas segmentés: Lebensversicherungsgesellschaftsangestellter = "life insurance company employee" 52 SRI & Big Data  Etape 1 : Extraction de termes Pas d’espaces en chinois et en japonais Ne garantit pas l’extraction d’un terme de manière unique Le Japonais encore plus compliqué avec différents alphabets La langue arabe s’écrit de droite à gauche avec certains termes écrits de gauche à droite (ex : les chiffres) 53 SRI & Big Data  Etape 1 : Extraction de termes Suppression des mots « vides » (stoplist / Common Words removal) : Il s’agit de mots trop fréquents et pas utiles (à supprimer lors de la tockenisation) Il peut s’agir d’articles, de pronoms, de mots de liaison… (le choix des stopwords dépendent de la langue et du contexte) Exemples : Anglais : the, or, a, you, I, us, to, … Français : le , la, de, des, je, tu, à, aux, … Il faut faire attention à certaines exceptions: Certaines abréviations font référence à autre chose qu’aux stopwords Exemple: “US” pour dire ”USA” 54 SRI & Big Data  L’indexation automatique : les étapes Etape 2 : Normalisation Il s’agit de Lemmatisation (radicalisation, racinisation) / (stemming en anglais) : Processus consistant à regrouper les variantes d’un mot (mot de même famille) pour lui donner la forme neutre (canonique) qu'il a (forme proche du radical / racine). cette forme canonique est appelée lemme. Exemples : grand, grande, grands, grandes, grandement => grand La forme canonique de tous ces mots dont le sens premier exprime une taille importante est grand. Pour l’anglais : retrieve, retrieving, retrieval, retrieved, retrieves => retriev est le lemme de tous ces mots 55 SRI & Big Data  Etape 2 : Normalisation Techniques de normalisation: Approche algorithmique de transformation de mots en lemme : ces algorithmes appliquent des règles de désuffixation (suppression des suffixes). Soit le suffixe est supprimé, soit il est transformé selon des règles pour avoir la forme canonique du mot. Les algorithmes les plus connus : Algorithme de Porter pour l’anglais Algorithme de Carry pour le français Algorithme de Paice/Husk Approche par dictionnaire : Lemmatisation avec un lexique / dictionnaire : suppression de suffixes puis recherche de la racine correspondante dans le dictionnaire Technique de Troncatures: couper jusqu’à X caractères 56 SRI & Big Data  Approche algorithmique L’algorithme de Porter : Permet la désuffixation de mots anglais (enlever les suffixes) à commencer par la transformation du pluriel au singulier. Les règles de transformation sont classées en sept phases successives (traitement des pluriels et verbes conjugués, traitement des adverbes...) Il comprend cinq groupes de règles de contexte, qui indiquent les conditions dans lesquelles un suffixe devra être supprimé. La terminaison en -ing, par exemple, ne sera enlevée que si le radical comporte au moins une voyelle. Exemple : "troubling" deviendra "troubl", mais "sing" restera "sing". Les mots à analyser passent par toutes les étapes de désuffixation, et, dans le cas où plusieurs règles pourraient leur être appliquées, c'est toujours celle comprenant le suffixe le plus long qui est choisie. La racinisation (désuffixation) est accompagnée à chaque étape de règles de recodage 57 SRI & Big Data  L’algorithme de Porter Exemples : Règles Exemples en anglais SSES → SS caresses → caress SS → SS caress → caress S→ cats → cat ATIONAL → ATE relational → relate TIONAL → TION conditional → condition ATIVE → formative → form ALIZE → AL formalize → formal Exemples de transformation du mot : Generalizations étape1: Generalization étape 2: Generalize étape 3: General 58 étape 4: Gener SRI & Big Data  L’algorithme de Porter Aperçu des étapes: 59 SRI & Big Data  L’algorithme de Porter Implémentation de l’algorithme de porter (disponible en plusieurs langages de programmation) : https://tartarus.org/martin/PorterStemmer/index.html 60 SRI & Big Data  Approche algorithmique Pour la langue française : Les lemmes de la langue française peuvent avoir plusieurs formes en fonction : du genre (masculin ou féminin), de leur nombre (un ou plusieurs), de leur personne (moi, toi, eux…), de leur mode (indicatif, impératif,…) L’algorithme Carry fonctionne sur le même principe que l’algorithme de porter, et est téléchargeable gratuitement sur le site du projet GALILEI http://www.otlet-institute.org/GALILEI_Platform_fr.html 61 SRI & Big Data  Approche avec lexique Approche avec utilisation d’un lexique : L’outil TreeTagger https://www.cis.lmu.de/~schmid/tools/TreeTagger/ Version online: https://cental.uclouvain.be/treetagger/ Il s’agit d’un outil de lemmatisation et d’annotation de texte, créé par Helmut Schmid à l’université de Stuttgart Prend en compte plusieurs langues (français, anglais, allemand, italien, espagnol, portugais, russe, …) et peut être adapté à de nouvelles langues (si le lexique est fourni + un corpus entrainé ) De manière générale on y applique les règles suivantes: Pour un verbe conjugué: on prend sa forme à l'infinitif Pour un nom, adjectif, article,... : sa forme au masculin singulier L’outil peut être utilisé dans un cadre d’études / recherche / enseignement, mais est interdit d’usage commercial 62 SRI & Big Data  Exemple avec TreeTagger Phrase à lemmatiser : « Il s’agit d’un cours d’informatique sur la recherche d’information » Résultat : 63 SRI & Big Data  Etape 2 : Normalisation Utilisation de Troncature : Il s’agit de couper un mot au Xème caractère pour supprimer éventuellement des suffixes Valeur optimale de X pour le français : 7 caractères Exemple de troncature à 7 caractères économiquement : écomoni Quelques limites : Le nombre de caractère dépend de la langue. Certaines langues ne peuvent pas supporter cette technique Pas suffisant pour trouver une racine : certains mots, notamment les verbes, changent complètement de forme Exemple : verbe être : est, fut, soit Certains mots ont des sens différents mais deviennent le même lemme à la troncature. Exemple : Informatique et information => informa 64 SRI & Big Data  Etape 2 : Normalisation Autre technique : méthode des n-gram : Un n-gram est une succession de n lettres n = 1, 2, 3 Exemple : retrieval 1-gram : r, e, t, r, i, e, v, a, l 2-gram : re, et, tr, ri, ie, ev, va, al 3- gram : ret, etr, tri, rie, iev, eva, val Utile pour la racinisation pour certaines langues complexes, où il est difficile de trouver des règles de désuffixations 65 SRI & Big Data  Méthode des n-gram Hypothèse retenue: si les n-gram de deux mots ont une forte similitude alors ils ont de fortes chances d’être de la même famille Exemple : Comparaison de retrieve et retrieval avec 3-gram: A=retrieve : ret, etr, tri, rie, iev, eve B=retrieval ret, etr, tri, rie, iev, eva, val On calcule leur similitude avec la formule : Sim (A,B)=2*nb_comm/(nb_A +nb_B) Sim(A,B) = 0.76 Plus le rapport est proche de 1, plus la similitude est forte (il faut pour cela déterminer un seuil au delà duquel on accepte la similitude) 66 SRI & Big Data  Etape 2 : Normalisation Avantages de la normalisation : Permet d’avoir un terme commun qui fait référence à tous les termes d’une même famille Augmente les chances de répondre efficacement à une requête (quelque soit la technique de matching appliquée…) Permet de réduire la taille de la base d’index (c’est surtout pour cette raison qu’on utilise la normalisation) 67 SRI & Big Data  Etape 2 : Normalisation Limites de la normalisation : peut conduire à une normalisation « agressive » Exemples : avec l’algorithme de Porter: policy/police, university/universe, organization/organ avec troncature: Internet/Interne oubli de quelques normalisations intéressantes: Exemples : matrices/matrix, machine/machinery ne sont pas normalisés avec Porter peut produire des mots difficiles à interpréter : Exemples : avec Porter: “iteration” produit “iter”, “general” produit “gener” 68 SRI & Big Data  L’indexation automatique : les étapes Etape 3 : Pondération Comment caractériser l’importance des termes dans un document ? Associer un (ou plusieurs) poids a un terme Idée sous jacente : Les termes importants doivent avoir un poids fort Approche la plus répandue : TF.IDF (du « Modèle vectoriel ») Enregistrer la position du terme dans le document (pour identifier les expressions et mots composés fréquents) Exemple: pomme de terre 69 SRI & Big Data  Types d’indexation Manuelle Automatique Semi-automatique 70 SRI & Big Data  L’indexation semi-automatique L’indexation semi-automatique est la combinaison des deux techniques manuelles et automatiques Exemple : Dans le cas de documents contenant du texte : On automatise d’abord l’extraction des termes des documents (suppression de stopwords, lemmatisation, pondération éventuellement …) Les termes sélectionnés vont être proposés à l’utilisateur (expert de l’indexation manuelle) pour correction / validation et/ou pour l’ajout de nouveaux termes 71 SRI & Big Data  L’indexation : Synthèse Sources d’information Processus … d’indexation Documents textuels, images, vidéos, … (manuel, auto, semi-auto) Index Index Index A quoi ressemble une base d’index ? 72 SRI & Big Data  Structure de la base d’index Quelque soit la méthode et techniques d’indexation choisies, la rapidité et l’efficacité de la recherche dans la base d’index dépend de sa structure L’indexation permet d’obtenir (par défaut) une liste de termes décrivant chaque document : Le problème de cette forme de structure est que la recherche d’un terme est lente : on recherche le terme séquentiellement dans chaque document ⟹ La structure d’index la plus communément utilisée dans les moteurs de recherche est de forme : inverted index (fichier inversé) 73 SRI & Big Data  Structure de la base d’index Structure inverted index : Terme → {doc1, Doc2, …} Une structure inverted index contient chaque terme sélectionné dans les documents comme index, avec pour chaque index la référence à tous les documents qui le contiennent Cette structure peut être enrichie par: la fréquence du terme dans chaque document et la position 74 SRI & Big Data  Structure de la base d’index Exemple 1: Les documents D1, D2 et D3 contiennent les textes suivants: Pour chaque document des termes seront sélectionnés (après traitement), on parle de bag of words (sac de mot ) Pour D1 = c’ , est, ce, que Pour D2 = c’, est, ceci Pour D3 = ceci, est, une, banane Ces mots seront utilisés comme index 75 SRI & Big Data  Structure de la base d’index La structure inverted index résultante : N.B: chaque index dans une structure d’index est unique 76 SRI & Big Data  Structure de la base d’index Il existe deux types de structure d’index inversé : Record-Level Inverted Index : Le fichier d'index inversé contient une liste de références aux documents pour chaque terme utilisé comme index Word-Level Inverted Index : Le fichier d'index inversé contient non seulement la liste de références aux documents, mais également les positions de chaque mot dans un document. Cette dernière forme offre plus de fonctionnalités mais nécessite plus de puissance de traitement et plus d'espace pour être stockée. Un autre critère est aussi pris en compte pour les deux types de structures: la fréquence du mot dans le document. La fréquence d’un mot permet de connaître son importance dans le document pour: décider de le sélectionner ou pas (cas de collections importantes) de savoir où le classer dans la liste des résultats 77 SRI & Big Data  Structure de la base d’index Exemple 2: fréquence DocId [positions] Dictionary Postings list 78 Inverted Index SRI & Big Data  Structure de la base d’index Avantages: Recherche efficace : les index inversés permettent une recherche efficace de grands volumes de données textuelles. En indexant chaque terme de chaque document, l'index peut identifier rapidement tous les documents contenant un terme ou une expression de recherche donnée, réduisant ainsi considérablement le temps de recherche. Mises à jour rapides : les index inversés peuvent être mis à jour rapidement et efficacement à mesure que du nouveau contenu est ajouté au système. Cela permet une indexation et une recherche de nouveau contenu en temps quasi réel. Compression : les index inversés peuvent être compressés pour réduire les besoins de stockage. Diverses techniques telles que le delta encoding, gamma encoding, variable byte encoding, etc. peuvent être utilisées pour compresser efficacement. 79 SRI & Big Data  Structure de la base d’index Prise en charge de plusieurs langues : les index inversés peuvent prendre en charge plusieurs langues, permettant aux utilisateurs de rechercher du contenu dans différentes langues en utilisant le même système. 80 SRI & Big Data  Structure de la base d’index Comment rechercher dans une base d’index: Recherche séquentielle : temps linéaire dans la taille du vocabulaire indexé (Utile pour une petite base d’index uniquement). Recherche dichotomique : les index doivent être triés. on regarde le mot du milieu, on cherche sur le même principe dans la première ou seconde moitié (Temps logarithmique dans la taille du vocabulaire). Recherche avec un arbre de recherche : arbre dont les feuilles donnent accès à la ligne et les noeuds disent quelle branche suivre (Temps logarithmique dans la taille du vocabulaire). Recherche avec une fonction de hachage : fonction qui calcule le numéro de ligne à partir du mot. (Temps constant). 81 SRI & Big Data  Structure de la base d’index Remarque : Le stockage d’une structure d’index peut s’avérer très couteux en espace de stockage mais également en recherche. Dans le cas de très larges collections il faut penser à un système distribué pour les tâches d’indexation. L’un des modèles connus pour cela est le modèle du MapReduce de Google. 82 SRI & Big Data  Conclusion sur l’indexation L’indexation est une phase complexe qui nécessite des choix à faire à plusieurs niveaux (indexation manuelle ou automatique ou les deux, techniques d’extraction, de normalisation, structure de la base d’index,…). Ces choix dépendent aussi de : La taille de la collection La nature des ressources (documents/ fichiers) concernées par la RI Les techniques de RI utilisées pour le matching requête/documents Remarque : Pour déterminer si la représentation d'un document correspond à celle de la requête, on doit développer un processus de matching (avec évaluation des résultats pour vérifier son efficacité) Différents modèles ont été développés en relation avec la représentation des documents et des requêtes. C'est cet ensemble de représentations et la technique de mise en correspondance et de sélection des résultats qu'on appelle un modèle de RI. 83 SRI & Big Data  Les modèles de RI 84 SRI & Big Data  Les modèles de RI Notion de modèle dans le processus de RI : X Y Z Représentation des documents Représentation matching de la requête Index Un modèle de RI spécifie comment est la représentation d’une requête, comment est la représentation d’un document et comment faire la mise en correspondance (matching) entre les deux représentations 85 SRI & Big Data  Les modèles de RI Il existe deux formes de matching (mise en correspondance / appariement) dans la RI : exact matching / best matching Exact matching: On spécifie dans la requête les termes recherchés de manière précise L’ensemble des documents respectant exactement la requête sont sélectionnés (mais pas ordonnés) Best matching : On spécifie dans la requête les termes recherchés Les documents sont sélectionnés selon un degré de pertinence (similarité/ probabilité ) vis-à-vis de la requête et sont ordonnés (par degré de correspondance) 86 SRI & Big Data  Les modèles de RI Plusieurs modèles de RI existent : Modèle booléen (1950) Modèle vectoriel (1970) Modèle probabiliste (1976) (basé sur le théorème de Bayes) Modèle inférentiel (1992) (basé sur les statistiques inférentielles) Modèle LSI (Latent Semantic Indexing) (1994) Modèles Word embeddings (à partir de 2002) (modèle de langue) 87 SRI & Big Data  Modèle Booléen Il s’agit du premier modèle de RI (modèle booléen strict) Caractéristiques : Représentation d’un document: un document est représenté par un ensemble de termes (qui indexent le document) : D = (𝑡1 , 𝑡2 , …, 𝑡𝑖 ) avec i ∈ [1, … , 𝑁] Représentation de la requête : une requête est une expression logique de termes avec des opérateurs booléens: AND (ᴧ) OR (ᴠ) NOT (¬) Exemple : Q = (𝑡1 ᴧ 𝑡2 ) ᴠ (𝑡3 ᴧ ¬ 𝑡4 ) Technique d’appariement « Exact match » : présence des termes de la requête dans la représentation d’un document → document sélectionné 88 SRI & Big Data  Modèle Booléen Exemple : D1 = (𝑡1 , 𝑡3 , 𝑡4 ) D2 = (𝑡2 , 𝑡4 ) D3 = (𝑡1 , 𝑡2 , 𝑡4 , 𝑡5 ) D4 = (𝑡1 , 𝑡4 ) Q1= (𝑡2 ᴧ 𝑡4 ) Q2 = 𝑡5 ᴠ (𝑡1 ᴧ ¬ 𝑡3 ) ⟹ D2 et D3 répondent à la requête Q1 ⟹ D3 et D4 répondent à la requête Q2 89 SRI & Big Data  Modèle Booléen Limites du modèles : Formulation de la requête avec les opérateurs de logique pas évidente (voire difficile) pour beaucoup d’utilisateur Sélection des documents sur décision binaire (soit le document répond à la requête, soit il n’y répond pas) Pas de classement des documents sélectionnés (pas de degré de pertinence car les termes ne sont pas pondérés) Pour les collections volumineuses : risque de sélection de beaucoup trop de documents en résultat (surtout à cause de l’opérateur OR) 90 SRI & Big Data  Modèle Booléen pondéré Extension du modèles : Modèle booléen pondéré On intègre des pondérations dénotant la représentativité de tous les termes T d’une requête pour un document La fonction de pondération 𝑊𝐷 pour un document est: 𝑊𝐷 : T → [0,1]. Pour chaque terme de la requête, le poids de ce terme dans D vaut : 0 pour un terme non présent dans le document 1 pour un terme présent dans le document La fonction de correspondance entre les termes de la requête et des documents, notée Sim, est basée sur un calcul de similarité selon l’opérateur logique (AND, OR, NOT) 91 SRI & Big Data  Modèle Booléen pondéré Cas de l’opérateur NOT: 𝑺𝒊𝒎 𝑫, ¬𝒂 = 𝟏 − 𝑾𝑫 (a) Cas des opérateurs AND et OR : Formules 1 inspirées de la logique floue (ne tenant pas compte de tous les termes de la requête) 𝑺𝒊𝒎 𝑫, 𝒂 ᴠ 𝒃 = 𝑴𝒂𝒙 [𝑾𝑫 (a), 𝑾𝑫 (b)] (a, b les termes d’une requête) 𝑺𝒊𝒎 𝑫, 𝒂 ᴧ 𝒃 = 𝑴𝒊𝒏 [𝑾𝑫 (a), 𝑾𝑫 (b)] Formules 2 avec prise en compte de tous les termes de la requête 𝑾𝑫 𝒂 2 + 𝑾𝑫 𝒃 2 𝑺𝒊𝒎 𝑫, 𝒂 ᴠ 𝒃 = 𝟐 𝟏−𝑾𝑫 𝒂 𝟐 + 𝟏−𝑾𝑫 𝒃 𝟐 𝑺𝒊𝒎 𝑫, 𝒂 ᴧ 𝒃 = 𝟏 − 𝟐 92 SRI & Big Data  Modèle Booléen pondéré Exemple : on considère A et B les termes d’une requête Modèle pondéré Documents A B (A ᴠ B) (A ᴧ B) (A ᴠ B) (A ᴧ B) (formule 2) (formule 2) D1 1 1 1 1 1 1 D2 1 0 1 0 0,7 0,29 D3 0 1 1 0 0,7 0,29 La pondération permet ici de classer les documents Exemple: Pour la requête (A ᴠ B) avec le modèle pondéré, D1 sera classé en 1er, suivi de D2 et D3 dans le même ordre. 93 SRI & Big Data  Modèle Vectoriel Modèle créé au début des années 70 par Gerard Salton, appliqué pour la RI avec le système SMART (System for the Mechanical Analysis and Retrieval of Text) Caractéristiques : Modèle best-match le plus commun Requête en texte libre (un ou plusieurs termes) Documents ordonnés dans les résultats : on tient compte du poids des termes de la requête dans les documents pour pouvoir les classer (on parle de pondération) Les documents et la requête sont représentés comme des vecteurs dans un espace vectoriel : il s’agit de vecteur de poids Document : dj= (w1j, w2j, …, wNj) avec : Wij poids du terme ti dans le document dj 94 Requête : q= (w1q, w2q, …, wNq) Wiq : poids du terme ti dans la requête q SRI & Big Data  Modèle Vectoriel Illustration : représentations des documents et d’une requête dans un espace vectoriel de termes ti Plus les vecteurs représentant les documents sont proches, plus les documents sont similaires Plus l’angle entre la requête est le document est petit, plus le document répond à la requête On calcule la similarité vectorielle entre l’angle d’un document et d’une requête en utilisant le poids des termes (la mesure de 95 similarité la plus utilisée est la formule du cosinus) SRI & Big Data  Modèle Vectoriel Notion de pondération : Pondérer les termes permet de connaître leur importance dans la recherche pour sélectionner les documents les plus pertinents et les classer La pondération des termes pour une requête est simple : fréquence du terme dans la requête (term frequency) La pondération pour les documents est une notion plus complexe. Elle tient compte de : l'importance du terme dans le document (pondération locale) l'importance du terme dans la collection (pondération globale) La mesure la plus connue pour la pondération des termes pour un document est : tf.idf 96 SRI & Big Data  Modèle Vectoriel Les mesures: tf = Term Frequency est la fréquence du terme dans le document df = Document Frequency est le nombre de documents dans la collection (corpus entier) contenant le terme recherché on utilise la mesure df inversée, notée idf (Inverted Document Frequency) 97 SRI & Big Data  Modèle Vectoriel Formules : tf : (term frequency) Formule simple du tf: est la fréquence du terme ti dans le document dj (nombre d’occurrences) tfi,j = freq(ti, dj) Variante du tf: fréquence normalisée logarithmiquement tfi,i = log(1+freq(ti, dj)) idf : (inverted document frequency) Formule simple : idfj = 1 / dfj avec dfj nombre de documents où apparait le terme tj Formule normalisée logarithmiquement : idfj = log(N / dfj) avec N le nombre de documents du corpus Le poids de chaque terme ti dans un document dj est calculé: 98 Wi,j = tfi,j.idfj SRI & Big Data  Modèle Vectoriel Exemple de calcul de pondération : On considère la structure inverted index suivante : Terme DocId Freq Pomme d1 1 d2 3 d3 2 Poire d1 1 d3 2 d4 1 99 SRI & Big Data  Modèle Vectoriel → Pondération pour le terme t1 = pomme avec formule simple : Wt1,d1 = 1 x (1/3) = 0,33 Wt1,d2 = 3 x (1/3) = 1 Wt1,d3 = 2 x (1/3) = 0,67 → Pondération pour le terme t1 avec formule logarithmique : Wt1,d1 = (log(1+1)) x (log(4/3)) = 0,037 Wt1,d2 = (log(1+3)) x (log(4/3)) = 0,075 Wt1,d3 = (log(1+2)) x (log(4/3)) = 0,059 N.B : d4 n’est pas indexé avec le terme pomme, il ne sera donc pas pris en compte dans le calcul des poids 100 SRI & Big Data  Modèle Vectoriel Fonction de matching: La similarité entre les représentations d’une requête Q et d’un document D est notée Sim(Q,D) et est calculée grâce à la formule du cosinus (cosine similarity): 𝑆𝑖𝑚 (𝑄, 𝐷) = cos(𝑄, 𝐷) = avec : Wi Q : poids des termes dans la requête (tf) Wi D : poids des termes dans le document (tf.idf) N.B: La similarité est comprise entre 0 et 1: résultat proche de 1 si les termes sont similaires, proche de 0 sinon. Dans le cas de larges collections, il est possible de choisir un seuil de 101 pertinence ou les k-best scores à afficher SRI & Big Data  Modèle Vectoriel Remarque 1 : D’autres mesures de calcul de similarité textuelle existent, telles que: Coefficient de Dice : Mesure de Jaccard : qi : poids du terme ti dans la requête di : poids du terme ti dans le document 102 SRI & Big Data  Modèle Vectoriel Remarque 2 : Quand la représentation de documents est sous forme d’une liste de termes: on parle de Bag of Words (BoW) : Le modèle BoW est un modèle de texte qui utilise une représentation basée sur une collection non ordonnée de mots ( « sac de mots ») Il est utilisé dans le traitement du langage naturel et la recherche d'informations (RI). Il ne tient pas compte de l'ordre des mots dans la requête ou les documents, mais prend en compte la multiplicité 103 SRI & Big Data  Modèle Vectoriel Avantages: Le langage de requête est simple (liste de mots) La pondération améliore les résultats de recherche La mesure de similarité permet d’ordonner les documents selon leur pertinence vis à vis de la requête Limites : Le modèle considère les termes indépendants, alors que ce n’est pas forcément le cas. Exemple: « pomme » et « pomme de terre » sont deux notions différentes. Si la structure d’index contient la position des termes, il est souhaitable d’en tenir compte (par exemple, inclure une condition dans l’algorithme de recherche qui vérifie les positions des termes) Il n'y a pas de schéma de pondération optimal (dépend du corpus et de la requête) 104 SRI & Big Data  Modèle LSI (ou LSA) LSI (Latent Semantic Indexing) : Appelé également LSA (Latent Semantic Analysis) Il s’agit d’une extension du modèle vectoriel L’idée est de réduire l’espace vectoriel construit à partir des termes de la requête et des documents (peut être aussi appliquée aux termes des documents uniquement) Principe: Une matrice n x m est construite : n représente les termes de la requête, m représente les documents (ou n représente les termes des documents et m les documents) une technique de réduction de dimension est appliquée sur les valeurs de la matrice. La plus connue et utilisée est SVD (Single Value Decomposition) : réduit le nombre de lignes tout en préservant le nombre de colonnes Les vecteurs résultants des termes de la requêtes et des documents sont ensuite comparés grâce à une formule de calcul de similarité (Cosine similarity par exemple) Ce processus permet de trouver une relation sémantique latente entre les termes en regroupant des termes qui coexistent souvent dans des contextes similaires dans les documents. 105 SRI & Big Data  Modèle LSI Illustration : 106 SRI & Big Data  Modèles word embeddings Word embeddings: technique de NLP (Natural Language Processing) permettant une représentation « riche » de mots (termes) dans un espace vectoriel (on parle de représentation dense ou dense vectors) Il s’agit d’une représentation contextualisée des vecteurs de termes où de nouveaux termes s’ajoutent aux termes des requêtes et des documents dans leurs vecteurs respectifs (les termes ajoutés peuvent être des synonymes, des termes connexes, etc.) Des techniques d’apprentissage (machine learning et deep learning) sont appliquées sur des corpus de textes pour permettre au système d’apprendre les relations sémantiques entre les mots Les modèles les plus connus sont basés sur les réseaux de neurones et les architectures de Transformers. Exemples : Word2Vec, GloVe, ELMo, BERT. 107 SRI & Big Data  Word2Vec Word2Vec est un groupe de modèles de langue inventé par Google en 2013 Ces modèles sont basés sur des réseaux neuronaux superficiels (shallow neural network) à deux couches, formés pour reconstruire les contextes linguistiques des mots Word2vec prend en entrée un grand corpus de texte et produit un espace vectoriel (de plusieurs centaines de dimensions) chaque mot unique du corpus étant associé à un vecteur correspondant dans l'espace 108 SRI & Big Data  Word2Vec Il existe deux principaux modèles d’architecture Word2Vec : CBOW (Continuous Bag of Words) : Principe: Étant donné un contexte (des mots environnants / surrounding words), le modèle prédit le mot cible Exemple: Pour la phrase «he likes to eat», le mot cible est « likes » et les mots de contexte sont «he », « to » et « eat » Context window: le nombre de mots environnants recommandé par les auteurs du modèle est de 5 mots (avant et après) Skip-Gram : Principe: Étant donné un mot cible, le modèle prédit les mots de contexte (surrounding words) Exemple: en reprenant l’exemple précédent, pour le mot «likes », le modèle prédit les mots de contexte «he », « to » et « eat » Context window: le nombre de mots environnants recommandé par les auteurs du modèle est de 10 mots 109 SRI & Big Data  Word2Vec Illustration : CBOW vs Skip-gram 110 SRI & Big Data  Word2Vec Entrainement (Training process) : Input : un grand corpus de texte est utilisé en entrée Représentation des mots : chaque mot est représenté sous la forme d'un vecteur codé one-hot (one-hot encoded vector) Architecture du réseau neuronal : un réseau neuronal superficiel (généralement avec une couche cachée) est formé pour apprendre les relations entre les mots en fonction de leurs modèles de cooccurrence Optimisation : le modèle est formé pour minimiser l'erreur de prédiction à l'aide de techniques telles que la SGD (stochastic gradient descent) Output : après l’entrainement, chaque mot du vocabulaire est associé à un vecteur de taille fixe (word embedding) qui code les informations sémantiques en fonction de son contexte dans le corpus d’entrainement 111 SRI & Big Data  Word2Vec Implémentations de Word2Vec: https://radimrehurek.com/gensim/models/word2vec.html https://www.tensorflow.org/text/tutorials/word2vec 112 SRI & Big Data  BERT BERT (Bidirectional Encoder Representations from Transformers) : est un modèle de langage basé sur l'architecture des transformers*, développé par Google en 2018. Il est conçu pour des tâches de compréhension du langage naturel, comme le « question answering », l’analyse de sentiments, la classification de textes, et plus récemment la RI. Caractéristiques : Contexte bidirectionnel : BERT est bidirectionnel, cela signifie qu’il prend en compte les mots de gauche à droite et de droite à gauche (dans une phrase) pour comprendre le contexte complet Transformers : BERT est basé sur l'architecture Transformer, qui utilise des mécanismes d'attention pour pondérer l'importance des différents mots dans une phrase, ce qui aide le modèle à capturer les relations complexes entre les mots Pré-entraînement : BERT est pré-entraîné sur un large corpus de textes (par exemple, Wikipédia, BooksCorpus, …) en utilisant des méthodes non supervisées. Après cette phase de pré-entraînement, il peut être affiné pour des tâches de NLP spécifiques avec des données annotées (technique du NER). 113 *Transformers: il s’agit d’un modèle d’architecture deep learning (créé par Google), basé sur un mechanism d’attention multi-head SRI & Big Data  BERT Principe de fonctionnement : BERT repose sur l'architecture du Transformer, en utilisant uniquement sa partie "encodeur". Il comprend une première couche d'embeddings lexicaux qui représente les mots sous forme de vecteurs. Ces embeddings sont ensuite donnés en entrée à des blocs de Transformers successifs. Le modèle se termine par une couche, appelée "tête", qui aligne les vecteurs issus du dernier bloc du Transformer avec le vocabulaire du modèle, permettant ainsi d'obtenir une distribution de probabilité sur le lexique pour prédire un mot manquant. 12 blocs « encodeurs » de Transformer avec 12 têtes d’attention Trois types d’embeddings sont utilisés : position, segment et token 114 SRI & Big Data  BERT Input du model: Une séquence de tokens est fournie à l'encodeur du Transformer. Ces tokens sont incorporés avec d’autres informations dans des vecteurs (embeddings lexicaux), puis traités dans le réseau de neurones. Output du model : une séquence de vecteurs, chacun correspondant à un token d'entrée, fournissant des représentations contextualisées. Training process: deux stratégies sont utilisées: Masked Language Model (MLM) : Modèle de Langage Masqué Next Sentence Prediction (NSP) : Prediction de la phrase suivante 115 SRI & Big Data  BERT Masked Language Model (MLM): Dans le processus de pré-entraînement de BERT, une partie des mots dans chaque séquence d'entrée est masquée, et le modèle est entraîné à prédire les valeurs originales de ces mots masqués en se basant sur le contexte fourni par les mots environnants : Masquer les mots : Avant que BERT n’apprenne à partir des phrases, il cache certains mots (environ 15%) et les remplace par [MASK] Deviner les mots cachés : Le travail de BERT consiste à deviner quels sont ces mots cachés en se basant sur les mots qui les entourent. C'est comme un jeu de devinettes où certains mots manquent, et BERT essaie de combler les blancs. Comment BERT apprend : BERT ajoute une couche spéciale (couche de classification) au-dessus de la sortie de l'encodeur. Cette couche est essentielle pour prédire les mots masqués. Il vérifie ensuite à quel point ses prédictions sont proches des mots cachés réels. Il le fait en convertissant ses prédictions en probabilités. La probabilité de chaque mot dans le vocabulaire est calculée à l'aide de la fonction d'activation SoftMax (SoftMax Activation function). Cette étape génère une distribution de probabilité sur l'ensemble du vocabulaire pour chaque position masquée. 116 SRI & Big Data  BERT Les vecteurs de sortie de la couche de classification sont multipliés par la matrice d’embeddings, les transformant ainsi dans la dimension du vocabulaire. Cette étape aide à aligner les représentations prédites avec le vocabulaire. BERT utilise une fonction de perte (function loss) pendant l'entraînement. Elle ne prend en compte que la prédiction des valeurs masquées. Le modèle est pénalisé pour l'écart entre ses prédictions et les valeurs réelles des mots masqués. 117 SRI & Big Data  BERT Next Sentence Prediction (NSP): Lors du processus d'entraînement, BERT apprend à comprendre la relation entre les paires de phrases, en prédisant si la deuxième phrase suit la première dans le document d'origine. 50 % des paires d'entrée contiennent la deuxième phrase comme la phrase suivante dans le document d'origine, et les autres 50 % ont une phrase choisie aléatoirement. Pour aider le modèle à distinguer les paires de phrases connectées et déconnectées, l’input est traité comme suit: Un token [CLS] est inséré au début de la première phrase, et un token [SEP] est ajouté à la fin de chaque phrase. Un embedding de phrase indiquant la Phrase A ou la Phrase B est ajouté à chaque token. Un embedding positionnel indique la position de chaque token dans la séquence. BERT prédit si la deuxième phrase est connectée à la première. Cela se fait en transformant la sortie du token [CLS] en un vecteur de forme 2×1 à l'aide d'une couche de classification, puis en calculant la probabilité que la deuxième phrase suive la première en utilisant la fonction SoftMax. 118 SRI & Big Data  BERT Remarques sur les deux modèles : Pendant l'entraînement du modèle BERT, les modèles MLM et NSP sont entraînés ensemble. Le modèle vise à minimiser la fonction de perte combinée du MLM et de NSP, ce qui conduit à un modèle de langage robuste avec des capacités importantes de compréhension du contexte au sein des phrases et des relations entre les phrases. Le MLM aide BERT à comprendre le contexte au sein d'une phrase, tandis que la NSP aide BERT à saisir la connexion ou la relation entre des paires de phrases. Ainsi, l'entraînement simultané des deux stratégies garantit que BERT acquiert une compréhension large et complète du langage, capturant à la fois des détails entre les phrases et le sense à l'intérieur des phrases. 119 SRI & Big Data  BERT BERT dans la RI: BERT est de plus en plus utilisé dans la RI pour améliorer la pertinence et la précision des résultats de recherche. Sa capacité à comprendre le contexte des mots de manière bidirectionnelle le rend particulièrement efficace pour interpréter les requêtes des utilisateurs et les associer aux documents pertinents Avantages : Matching requête/documents contextualisé (semantic search) : les représentations vectorielles des requêtes et des documents sont contextualisées et le sens des mots est déchiffré grâce au modèle BERT (s’il est assez pré-entrainé sur des corpus adéquats) Compréhension des phrases comme requêtes de recherche: BERT est utile et approprié pour comprendre les phrases et les textes longs comme requêtes de recherche Classement contextuel des résultats : BERT peut être utilisé dans les moteurs de recherche pour classifier les résultats de recherche (par thématique par exemple) Exemple dans Google Search: BERT est intégré dans l’algorithme de recherche de Google. Il est surtout utilisé pour comprendre le contexte et les nuances des requêtes, en particulier pour les requêtes conversationnelles (écrites sous forme de phrases) 120 SRI & Big Data  Amélioration des résultats de RI Quelque soit le modèle de RI utilisé, il existe des techniques pour améliorer les résultats retournés par un SRI (après l’affichage des résultats) La plus connues est la technique du Relevance feedback :il s’agit de reformuler la requête à partir des résultats et grâce au retour de l’utilisateur Principe du Relevance feedback: On estime que la première requête de l’utilisateur est souvent naïve et spontanée On permet à l’utilisateur de donner son avis (feedback) sur les résultats (sous une forme précise) La requête originale est reformulée (étendue avec de nouveaux termes) et re-pondérée 121 SRI & Big Data  Relevance feedback Illustration : Résultats : Ensemble de documents ordonné + Feedback utilisateur Nouvelle requête étendue Exemple de feedback : L’utilisateurs examine les k meilleurs documents et les étiquettes avec des valeurs [1,0] L’utilisateur classe les k meilleurs résultats par ordre de pertinence 122 selon son point de vue SRI & Big Data  Conclusion sur les modèles de RI Remarque 1: Les modèles de RI ont été inventés avant l’apparition de la technique de lemmatisation des mots dans l’indexation automatique. Les lemmes qui servent d’index peuvent être légèrement différents des termes de la requête et donc peuvent poser problème lors de la recherche. Exemple: on saisit le terme «économique» dans la requête mais c’est « économi » qui est enregistré dans la base. Il est conseillé dans ce cas d’appliquer les mêmes techniques de normalisation sur les termes des requêtes durant le processus de matching Il est possible de vérifier la similarité entre deux termes en utilisant des mesures de calcul de similarité (edit-distance). Parmi les plus connues: Levenshtein distance Damerau- Levenshtein distance Jaro-Winkler distance … 123 SRI & Big Data  Conclusion sur les modèles de RI Remarque 2 : Le stockage d’une structure d’index peut s’avérer très couteux en espace de stockage mais également en recherche. Dans le cas de très larges collections il faut penser à un système distribué pour les tâches d’indexation. L’un des modèles connus pour cela est le modèle du MapReduce de Google. 124 SRI & Big Data  Evaluation des SRI 125 SRI & Big Data  Evaluation des SRI Notion de pertinence des résultats : La pertinence est: la correspondance entre un document et une requête, le degré de relation (chevauchement, relativité, …) entre le document et la requête; le degré de la surprise qu'apporte un document, qui a un rapport avec le besoin de l'utilisateur; une mesure d'utilité du document pour l'utilisateur; … Les utilisateurs d'un système de RI ont des besoins très variés. Ils ont aussi des critères très différents pour juger si un document est pertinent ou pas. 126 SRI & Big Data  Evaluation des SRI Certains paramètres entrent en compte dans la pertinence des résultats d’un SRI (surtout pour les moteurs web): Profil de l’utilisateur Un besoin d’information exprimé par deux personnes de la même manière ne fournit pas forcément les mêmes réponses (prise en compte du profil de l’utilisateur quand il est connecté par exemple) Expérience de l’utilisateur à chaque même requête (relevance feedback) Contexte « externe » du besoin d’information Temporel : Un besoin d’information exprimé à différents moments n’a pas le même sens Géographique : Un besoin d’information exprimé à différents endroits n’a pas le même sens) (« restaurant » à Marrakech ne nécessite pas forcément de réponses de restaurants dans d’autres 127 villes ou pays) SRI & Big Data  Evaluation des SRI De manière générale, le but de la RI est de trouver seulement les documents pertinents à une requête, et donc utiles pour l'utilisateur Document pertinent = document où l'utilisateur doit pouvoir trouver les informations dont il a besoin. La qualité d'un système doit être mesurée en comparant les réponses du système avec les réponses idéales que l'utilisateur espère recevoir. Plus les réponses du système correspondent à celles que l'utilisateur espère, mieux est le système Pour arriver à une telle évaluation, on doit d'abord connaître les réponses idéales de l'utilisateur. L'évaluation d'un système se fait ensuite avec : un corpus de test 128 et des métriques connues en RI : Précision et Rappel. SRI & Big Data  Evaluation des SRI Dans un corpus de test, il y a: un ensemble de documents un ensemble de requêtes la liste de documents pertinents pour chaque requête (d’un point de vue utilisateur) Prérequis (pour des résultats assez objectifs): Les requêtes doivent traiter des sujets variés Il faut une collection assez variée contenant les documents pertinents (qui répondent aux requêtes) et d’autres moins pertinents Il faut des utilisateurs experts qui savent juger la pertinence d’un document (pour chaque requête, quelles sont les résultats attendus) 129 SRI & Big Data  Evaluation des SRI On compare les résultats obtenus par le système avec les résultats établis par les experts Les métriques utilisées en RI: Précision : proportion de documents pertinents retrouvés parmi tous les documents retrouvés par le système Rappel : proportion de documents pertinents retrouvés parmi tous les documents pertinents dans la collection 130 SRI & Big Data  Evaluation des SRI Illustration : Résultats obtenus Pas obtenus (sélectionnés par le SRI) False True False True Negative Positive Positive Negative (FN) (TP) (FP) (TN) Pertinents Non pertinents 131 SRI & Big Data  Evaluation des SRI Ces mesures permettent d’améliorer : la qualité des index la formulation des requêtes la technique de matching entre les deux Il n’y a pas de bons taux de précision et de rappel. Ces deux mesures sont fortement liées: quand l’une augmente, l’autre diminue. L’objectif est de trouver le bon rapport entre la précision et le rappel: on parle de moyenne harmonique La moyenne harmonique entre précision et rappel est nommée: F-mesure (ou F-score ou F1) : 132 SRI & Big Data  Evaluation des SRI Exemple : (pour 1 requête) Nombre de docs dans la collection : 100 Nombre de docs pertinents dans la collection : 60 Nombre de docs sélectionnés : 30 dont 10 non pertinents Matrice de confusion Selected (confusion matrix) TP = 20 FP = 10 Predicted FN = 40 TN = 30 Precision = 20/(20+10) = 0,67 Rappel = 20/(20+40) = 0,33 F1-score = 0,44 133 SRI & Big Data  Exemples d’implémentations Frameworks et moteurs de RI connus: Lucene : est une bibliothèque d’indexation et de recherche d’information textuelle, écrite en Java (existe aussi en: C++, C#, Perl, Python,…), disponible sous licence Apache. Le processus d’indexation et de recherche est traité de manière générale. Beaucoup de classes sont abstraites et doivent être spécialisée (par exemple, pour l’extraction automatique des termes pour les index, il y a une classe abstraite Analyzer, pour la recherche, une classe abstraite Query proposant différentes méthodes abstraites pour des requêtes booléennes, requêtes avec préfixe, …). Moteurs et applications de RI basées sur Lucene: Elastic seach, Solr, Nutch (web crawler) Xapian : moteur open source écrit en C++ offrant des fonctions d’indexation et de recherche (licence GPL). Il met en œuvre l’approche probabilistique de la RI et des opérateurs booléens pour la recherche 134 SRI & Big Data  Notion de métamoteur Un métamoteur (ou méta-chercheur) est un moteur de recherche qui puise ses informations d’autres moteurs de recherche connus : Le métamoteur interroge plusieurs moteurs de recherche (Google, Bing, Ask, Yahoo!,…) et retourne les résultats de chacun d'eux. Il n’y a pas de redondance dans les résultats puisque les résultats similaires sont éliminés (par exemple: si les moteurs Google et Yahoo! renvoient quelques mêmes liens, le métamoteur ne va les afficher qu'une seule fois dans la liste des résultats). Certains métamoteurs indiquent de quels moteurs de recherche provient chaque résultat Exemples : Moteurs généralistes: DogPile, Yippy, StartPage, Metacrawler Moteurs spécialisés: CiteSeerX, GoogleScholar, CCSearch, Indeed 135 SRI & Big Data  La RI sur le web 136 SRI & Big Data  La RI sur le web Caractéristiques du web : Taille : très grand nombre de documents (milliards et plus) Hétérogénéité : très grande variété de documents Répartition : documents répartis sur Internet Structure du Web : documents interconnectés par des hyperliens ⟹ Environnement complexe : Il faut parcourir le web tous les jours, toutes les heures … pour indexer la nouveauté La recherche doit être rapide et les résultats assez pertinents pour le plus d’utilisateurs possibles (sinon le moteur ne sera pas utilisé) Les moteurs de recherche web se basent sur les fondamentaux de la RI (indexation avec inverted index, recherche avec pondération, classement,…), mais ont leur propre techniques pour indexer et rechercher 137 SRI & Big Data  La RI sur le web Côté indexation : Les moteurs web utilise des web crawler (robots d’indexation ou collecteur) Un web crawler parcourt le web, visite le contenu des ressources trouvées (page web, documents,…) et extrait le maximum d’informations (pour ensuite en faire des index) Il procède en suivant récursivement les hyperliens trouvés à partir d'une page De manière générale un robot d'indexation se charge des questions suivantes : quelles pages télécharger quand vérifier s'il y a des changements dans les pages comment éviter les surcharges de pages Web (délais en général) comment coordonner les tâches de manière distribuée (parallélisme) 138 SRI & Big Data  La RI sur le web Les index sont extraits à partir de plusieurs éléments des ressources web : le contenu textel des pages et toute ressource du site la structure du titre : titres de niveau 1, de niveau 2,… les méta