Sommaire

• Introduction
• Au croisement de la statistique et de la sémantique…
• Latent Semantic Analysis (LSA)
• Le mot de la fin

Introduction

On entend assez souvent parler dans les domaines du TAL de méthodes statistiques pour analyser la sémantique des mots d’un texte. Ce billet est le premier d’une liste de billets visant à expliciter le lien existant entre les statistiques et la sémantique des mots en présentant quelques méthodes parmi les plus connues dans le domaine. Ce premier billet de la série est consacrée à la très célèbre méthode Latent Semantic Analysis (LSA).

• Statistiques et sémantique des mots
• Latent Semantic Analysis (LSA)
• Hyperspace Analogue To Language (HAL)

Mais commençons d’abord par le commencement…

Au croisement de la statistique et de la sémantique…

C’est quoi une méthode statistique?
Une méthode statistique désigne une méthode qui s’appuie sur les probabilités d’un événement et plus généralement sur la probabilité d’occurrence conjointe de plusieurs événements pour en déduire des corrélations entre les événements.

C’est quoi le lien avec la sémantique?
Les méthodes statistiques sont utilisées dans l’analyse des mots d’un texte ou d’un corpus de textes pour détecter automatiquement leur sémantique par leur probabilité d’apparition dans un texte donné du corpus ou en voisinage avec d’autres termes.

Entrons maintenant dans le vif du sujet avec la méthode du jour qu’est LSA….

Latent Semantic Analysis (LSA)

Connaissances utiles pour implémenter la méthode :

• Connaissances sur les matrices et le produit matriciel
• Connaissance de la méthode de pondération TF.IDF
• Connaissance de la méthodes de la mesure de distance du cosinus entre deux vecteurs

Référence de la méthode :
DEERWESTER S., DUMAIS S., FURNAS G., LANDAUER T. & HARSHMAN R. (1990). Indexing by latent semantic analysis. Journal of the American society for information science, 41(6), 391–407 (si le serveur est surchargé, je vous propose un lien alternatif).

La méthode date de 1990 pour sa publication mais fut brevetée en 1988 aux États-Unis.

Elle sert à quoi?
Elle sert à découvrir de manière statistique la sémantique cachée et sous-jacente (latente) de mots dans un corpus de documents. Cela va notamment permettre de mettre en relation des requêtes et des documents relevants de celle ci présents au sein d’un corpus. Pour cela, on va calculer une matrice d’occurrence des termes dans les documents de taille t×d où t est le nombre de termes dans le corpus et d le nombre de documents.

Quelles sont les étapes principales?
On en dénombre quatre :

• 1- La construction de la matrice des occurrences X
• 2- La décomposition de la matrice X en deux matrices orthogonales T0 et D0 et en une matrice diagonale de valeurs singulières S0
• 3- La réduction des matrices S0, T0 et D0 au rang k
• 4- Le calcul de la matrice X^, matrice approchée au rang k de la matrice X

1- Construction de la matrice des occurrences X
La première étape consiste donc à construire une matrice des occurrences des termes dans les documents de taille t×d. Chaque ligne de la matrice représente un terme et chaque colonne représente un document. L’intersection de chaque ligne et de chaque colonne représente l’importance du terme représenté par la ligne dans le document représenté par la colonne. Cette importance est souvent normalisée par un nombre compris entre 0 (aucune importance) et 1 (extrêmement important). Des méthodes telles que le TF.IDF sont souvent employées pour calculer l’importance d’un terme pour un document. Par ailleurs, il est courant de ne pas tenir compte des mots les moins pertinents tels que les déterminants, les pronoms,… On appelle ces mots des mots creux.

Voyons ce que cela peut donner sur un exemple très minimaliste.

Prenons quatre documents :
Doc1 : “Sarkozy débute la campagne présidentielle UMP”
Doc2 : “Sarkozy affronte Hollande”
Doc3 : “Hollande a été désigné pour la présidentielle PS”
Doc4 : “Il y a des tracteurs en campagne”

Il sont constitués de l’ensemble des mots suivants {Sarkozy, débute, campagne, présidentielle, UMP, affronte, Hollande, désigné, PS, tracteurs} après retrait de l’ensemble des mots creux {la, a, été, pour, il, y, des, en}.

Nous pouvons alors représenter l’occurrence simple des termes dans les documents par la matrice X suivante :

	Doc1	Doc2	Doc3	Doc4
Sarkozy	1	1
débute	1
campagne	1			1
présidentielle	1		1
UMP	1
affronte		1
Hollande		1	1
désigné			1
PS			1
tracteurs				1

Nous allons utiliser un logiciel permettant de réaliser des calculs numériques. Vous connaissez peut être le logiciel MATLAB qui est assez réputé dans le domaine. Je vous propose cependant d’utiliser pour cet exemple un logiciel libre : Scilab

Nous commençons donc par saisir la matrice X dans ce logiciel :

2- Décomposition de la matrice par des valeurs singulières
La deuxième étape consiste à identifier les valeurs singulières de la matrice X afin de pouvoir la décomposer en trois matrices T0, S0, D0 distinctes dont la multiplication donne la matrice X.
X = T0 . S0 . D0
où S0 est une matrice diagonale de taille m×m de valeurs singulières et T0 et D0, deux matrices orthogonales de taille t×m et m×d

Demandons à scilab de réaliser la décomposition en valeurs singulières (SVD) de notre matrice X normée :

Attention! Scilab ne donne pas les matrices T0, S0 et tD0 telles que X/norm(X) = T0*S0*tD0 mais telles que X/norm(X) = T0*S0*tD0′ (tD0′ correspondant à la matrice transposée de tD0 et donc à D0) comme on peut facilement le vérifier…

Nous avons donc quatre valeurs singulières pour notre exemple : 1 / 0.7605876 / 0.6094909 / 0.5046700

3- Réduction des matrices au rang k
La troisième étape consiste à réduire la matrice diagonale S0 de taille m×m à une matrice diagonale S de taille k×k avec k ≤ m.
Pour cela, on effectue une permutation des colonnes de S0 afin de les classer dans l'ordre décroissant des valeurs singulières. Les permutations sont reportées sur les colonnes de T0 et D0 afin de conserver l'égalité de la multiplication des trois matrices avec la matrice X de départ.
On effectue ensuite une réduction au rang k en ne gardant que les k plus grandes valeurs singulières de la matrice S0 et en considérant comme nulles les autres valeurs singulières. Cela a comme impact de pouvoir supprimer les m-k dernières lignes et colonnes de la matrice S0, les m-k dernières colonnes de T0 et les m-k dernières lignes de D0. On appelle S, T et D les matrices ainsi obtenus de tailles respectives k×k, t×k et k×d.

La réduction au rang k des matrices va permettre de se concentrer sur les plus fortes valeurs singulières. Si l’on considère la matrice X comme la matrice représentant les t×d liens existants entre les documents et les termes par l’intermédiaire d’un espace de concepts de taille m×m, cela revient à se concentrer uniquement sur les liens t×d existants entre les documents et les termes si l’on réduit l’espace de concepts à ses k dimensions les plus influentes sur l’espace des documents et des termes. Le gain espéré est dans les ressources nécessaires aux calculs puisque la réduction de l’espace intermédiaire aura comme conséquence une simplification des liens existants. En contrepartie, les finalités induites par les m-k dimensions abandonnées de l’espace intermédiaire seront perdues. L’astuce est donc dans le bon choix du rang k pour obtenir le meilleur rapport simplicité / pertinence. De plus, le passage par un espace intermédiaire de concepts permet à la méthode de prendre du recul sur les liens unissant les documents et les termes permettant par là l’apprentissage et l’exploitation de liens non triviaux de prime abord.

Supposons que nous voulions faire une réduction au rang 3 de notre matrice X/norm(X) (et donc annuler la plus petite valeur singulière à savoir 0.5046700).

Nous réduisons donc les rangs des matrices T0, S0 et D0 pour obtenir les matrices T, S et D à l’aide de Scilab :

4- Calcul de la matrice X^
La dernière étape consiste à en déduire la matrice X^ de taille t×d, approximation au rang k de la matrice X.
X^ = T . S . D

Ce que Scilab peut nous faire facilement pour la matrice X^ de notre exemple :

Et comment on l’utilise ce résultat?
La matrice X^ ainsi obtenu est une matrice approchée (et donc simplifiée) de la matrice initiale X ne contenant que la sémantique des mots la plus importante d’un point de vue statistique pour le corpus (la sémantique latente des mots dans le corpus). On peut donc utiliser classiquement cette matrice pour déterminer des distances entre deux objets qu’il s’agisse de documents ou de termes.

Traditionnellement, la distance du cosinus des vecteurs constituants les lignes de la matrice (dans le cas des termes) ou de ceux constituants les colonnes de la matrice (dans le cas des documents) est utilisée. Soit ti, le vecteur de la ième ligne (resp di, la ième colonne) de la matrice X^ représentative du ième terme (resp. document) et tj, le vecteur de la jème ligne (resp dj, la jème colonne) de la matrice X^ représentative du jème terme (resp. document). On a alors :
distance(ti,tj) = Cos(ti,tj)
distance(di,dj) = Cos(di,dj)

De manière plus poussée, si l’on a une requête, on peut former un nouveau vecteur ri similaire à un vecteur di de la matrice X tel que les composantes de ce nouveau vecteur soit le centroid des termes de la requêtes. On a alors pour chaque document di du corpus d’origine :
distance(di,ri) = Cos(di,ri)

Bon me direz vous, et sur notre exemple qu’est ce que cela change concrétement? Un premier constat que l’on peut faire est que la matrice X^ est moins creuse que la matrice X (elle ne comporte plus aucune valeur nulle alors que la matrice originale en comporte 26 sur 40). Cette matrice semble donc dans un premier constat nous fournir des liens plus subtils entre les termes et les documents que la matrice originale.

Intéressons nous particulièrement au dernier document. Celui-ci est ce que l’on pourrait considérer comme un intrus puisqu’il n’aborde pas la même thématique que les autres (à savoir la politique). Si l’on observe la matrice d’origine, l’exotérisme de ce document (la 4ème colonne de la matrice) n’est pas flagrant. Par contre, dans la matrice approchée X^, on constate que la dernière colonne contient des valeurs beaucoup plus faibles que les trois autres. En outre, la valeur la plus forte de cette colonne est 0.19 contre 0.47, 0.408 et 0.403 pour les trois autres. La méthode LSA en se concentrant sur les liens principaux entre les termes et les documents parvient à faire ressortir l’exotérisme du dernier document.

La deuxième subtilité du corpus réside dans le piège linguistique du mot “campagne” évoqué dans ces deux principaux contextes sémantiques. La matrice originale X nous donne pour ce terme (3ème ligne de la matrice) une correspondance équivalente à 1 pour les documents 1 et 4 l’évoquant respectivement dans le contexte politique et dans celui de la ruralité. De ce fait, une requête menée sur ce corpus concernant le terme “campagne” ne pourrait pas faire le choix entre les deux contextes pourtant inégalitaire en terme de représentation (3 documents contre 1 en faveur de la politique). Il apparaît donc comme évident qu’une telle requête devrait privilégier le contexte dominant qu’est la politique. Là encore, la LSA parvient grâce à la transition par l’espace intermédiaire des concepts à privilégier le premier contexte au second. Ainsi, l’intersection entre le terme campagne et le document 1 (le sens politique du terme) est gratifié d’un 0.47 contre un 0.19 pour l’intersection avec le document 4 (le sens rural du terme).

Cet exemple assez minimaliste mais comportant déjà des résultats intéressants montre l’intérêt de la méthode LSA dans le domaine assez vaste de la recherche d’informations et en particulier dans la fouille de texte (text mining) où elle permet d’indexer les textes non pas uniquement en fonction des mots qu’ils comportent mais en fonction de la sémantique latente qu’ils contiennent.

Le mot de la fin

C’est fini pour aujourd’hui. Dans le prochain volet, nous parlerons de la méthode Hyperspace Analogue to Language (HAL).

Mots clefs : décomposition de valeurs singulières, Latent Semantic Analysis, LSA, matrice de valeurs singulières, Scilab, sémantique, sémantique cachée, sémantique sous-jacente, sémantique statistique, SVD avec Scilab, TAL

Cette entrée a été publiée le Vendredi 27 janvier 2012 à 11 h 35 min, et rangée dans Statistiques, TAL. Vous pouvez suivre les réponses à cette entrée via son flux RSS 2.0. Vous pouvez laisser un commentaire, ou faire un rétrolien depuis votre site.