Découplage fond-forme dans Maximal Marginal Relevance

 Cette section est organisée en deux sous-parties. Tout d’abord, la formulation de Maximal Marginal Relevance est subdivisée en paramètres dépendants du besoin de l’utilisateur (le fond) et de ceux qui peuvent être calculés par avance (la forme). Ensuite, une projection des phrases dans un espace pseudo-sémantique est proposée pour modéliser le fond.

Algorithme de sélection de phrases représentatives

 La méthode générale de sélection de phrases pour le résumé par extraction est de partitionner l’espace informatif en groupes de phrases sur un thème, ou un événement important, puis de sélectionner une phrase représentative par groupe. Le résumé sera constitué de la juxtaposition des phrases représentant chaque groupe. Des contraintes d’interaction avec l’utilisateur dirigent néanmoins le choix vers une méthode hybride réalisant le partitionnement de l’espace informatif en même temps que la sélection des phrases représentatives. Cette méthode, dénommée Maximal Marginal Relevance (MMR), a été proposée par Goldstein et al. (2000) pour déterminer la sélection de phrases candidates dans un résumé par extraction.Dans les formulations suivantes, un résumé est constitué à partir d’un ensemble de documents thématiquement cohérents et d’un besoin utilisateur. Les documents sont découpés en phrases qui représentent la matière première de l’algorithme de résumé. À ce niveau, les phrases sont considérées comme indépendantes les unes des autres : leur origine et leur ordre sont ignorés. Une phrase est dénotée (si ) pour la différencier d’une autre phrase (sj ). Pour l’instant, aucune hypothèse n’est faite sur le contenu des phrases, il est juste important de pouvoir les comparer deux à deux. Le besoin utilisateur est noté (b). La seule hypothèse nécessaire réside dans la possibilité d’évaluer une phrase en fonction de sa réponse au besoin. MMR est une approximation gloutonne de la résolution du problème d’optimisation consistant à maximiser l’information tout en minimisant la redondance de l’ensemble de phrases sélectionnées pour le résumé. À chaque itération, l’algorithme détermine la phrase (sˆk ) la plus proche de l’expression du besoin utilisateur (b) tout en étant la plus éloignée des phrases (sj ) sélectionnées auparavant. Cette phrase est ajoutée à la sélection et l’algorithme s’arrête lorsqu’une condition est remplie comme par exemple lorsqu’un nombre de phrases K, un nombre de mots ou un ratio de compression est atteint. La figure 5.3 illustre ce fonctionnement. Si n est le nombre de phrases à l’origine.

Projection des phrases dans un espace pseudo-sémantique

 La similarité dans l’espace sémantique utilisée par MMR peut être fondée sur la plupart des méthodes de recherche d’information détaillées dans la section 2.1. Nous nous sommes concentrés sur cosine(·), mais afin d’outrepasser les limitations du modèle vectoriel classique (VSM), la base de l’espace sémantique est construite par Latent Semantic Analysis (LSA). Nous détaillons cette méthode dans les paragraphes suivants. L’objectif de LSA est d’obtenir un espace modélisant les affinités contextuelles des mots comme approximation de leurs relations sémantiques. Contrairement à la formulation classique qui projette les requêtes (phrases) dans un espace réduit construit à partir des documents, nous suivons les travaux de Widdows et Peters (2003) et calculons une base unique sur un corpus de grande taille pour pouvoir projeter de nouveaux documents sans avoir à recalculer la base. Cette approche s’apparente au modèle vectoriel généralisé (GVSM). Ainsi, le vecteur représentant une phrase est la somme des vecteurs représentant les mots la composant dans l’espace LSA. La construction de l’espace LSA demande tout d’abord la création d’une matrice de cooccurrence entre les mots. Chaque ligne et chaque colonne de cette matrice représentent un mot et la cellule à l’intersection d’une ligne i et d’une colonne j contient le nombre de fois que les mots i et j se sont retrouvés ensemble dans un contexte donné (équation 5.3). wj ↓ w T i →    x1,1 … x1,n . . . . . . . . . xm,1 … xm,n    (5.3) La portée de la cooccurrence peut être la phrase, le document, ou un contexte de taille fixe. Par exemple, le tableau de contingence des bi-grammes est construit en limitant le contexte au mot précédent. Généralement, afin de s’affranchir de la nécessité de frontières fixes, une fenêtre glissante de n mots représente le contexte. Bien que la matrice de cooccurrences soit symétrique et creuse, elle demande quand-même une quantité de mémoire en O(n 2 ), ce qui devient vite exorbitant lorsque le vocabulaire traité est grand. Pour réduire cet effet, il est courant de limiter le nombre de mots observés aux N mots les plus fréquents et de calculer leurs cooccurrences avec non pas l’ensemble du vocabulaire, mais une petite quantité de mots très fréquents et bien choisis, comme les entités nommées, afin de représenter des domaines sémantiques. Dans la suite, le rang de cette matrice va être réduit pour trois principales raisons : 1. la matrice est de trop grande taille pour assurer une faible complexité de calcul dans les traitements de grandes masses de données ; 2. l’estimation des cooccurrences n’est pas fiable par rapport à la distribution réelle (à cause de l’utilisation de synonymes, par exemple) ; 3. les erreurs de transcription bruitent cette matrice (dans le cas où des données textuelles ne sont pas disponibles pour en améliorer l’estimation). La réduction du rang de la matrice se fait par décomposition en valeurs singulières (Singular Value Decomposition, SVD). Le principe est qu’une matrice réelle X peut être factorisée en 3 matrices U,Σ et V avec Σ une matrice diagonale positive, et U et V des matrices orthogonales (équation 5.4). X = UΣV T (5.4) Σ contient les valeurs singulières σi de X, et U et V contiennent les vecteurs singuliers respectifs. Si les σi sont ordonnés de façon décroissante, le rang de la matrice Σ peut être réduit à k en annulant les valeurs singulières de rang supérieur à k. Cette réduction correspond à une approximation de X minimisant l’erreur au sens de moindres carrés (équation 5.5). La décomposition en valeurs singulières correspond à la minimisation de la corrélation entre les vecteurs singuliers. La base créée est souvent qualifiée de base « thématique » dans laquelle chaque vecteur représente un thème détecté automatiquement. Les mots sont exprimés dans cette base comme un vecteur de poids des différents thèmes auxquels ils participent. Dans la pratique, il est difficile d’interpréter les thèmes détectés, mais l’espace créé représente bien les affinités lexicales des mots. Xˆ = UΣkV T (5.5) La base de vecteurs singuliers U est utilisée pour exprimer un contexte d (requête, phrase, paragraphe, document…) en fonction des mots qui le composent. Dans l’équation 5.6, d est un vecteur sur l’ensemble du vocabulaire, fonction de la fréquence des mots dans le contexte observé et ˆd est la projection de ce vecteur dans l’espace sémantique. d = (w0, · · · , wn) T ˆd = Σ −1 k U T d (5.6) Cette approche a pour principal intérêt de représenter chaque unité informative par un vecteur dans un espace de dimension réduite. Ceci diminue le coût de calcul d’une similarité entre deux éléments. L’espace est considéré comme un modèle du monde (de tout ce qui peut y être instancié) et peut être généré à partir de données externes, disponibles en grande masse. Par contre, par rapport au modèle vectoriel simple utilisé en recherche documentaire, il n’est pas possible de créer un index inversé accélérant — par exemple — le calcul pour trouver l’élément le plus proche d’un élément donné (tous les éléments doivent être parcourus). Comme dans de nombreuses approches, la similarité cosine est utilisée pour comparer deux éléments ; ce n’est autre que le cosinus de l’angle entre les deux vecteurs représentant ces éléments : cosine(a, b) = a · b |a||b| , = ∑i q aibi ∑i a 2 i q ∑i b 2 i . Suivant des travaux de Murray et al. (2005), l’espace sémantique ainsi créé est utilisé pour calculer la similarité entre deux phrases dans l’algorithme de résumé automatique présenté en 5.3.1, sous le nom de MMR-LSA.