Latent Semantic Indexing |
 |
Le modèle Latent Semantic Indexing
Qu’est-ce que le sens d’un mot ? Comment déterminer que deux mots ont le même sens ? Une façon d’y arriver est de voir comment les mots sont utilisés. Deux mots qui sont interchangeables dans des textes sont des synonymes. Très souvent, par exemple, les mots bouquin et livre sont interchangeables. Si deux termes sont vraiment interchangeables, il vaudrait mieux que le moteur de recherche les traite comme un seul et même terme. On s’attend à une meilleure qualité de recherche si les termes synonymes sont regroupés.
Une autre forme de redondance intéressante se présente lorsque deux mots sont systématiquement utilisés ensemble. Par exemple, l’expression latine sine qua non est assez courante, mais on utilise peu les mots sine ou qua hors de ce contexte. Cela signifie que la matrice d’occurrences aura la particularité que le vecteur correspondant au terme sine sera identique au vecteur correspondant qua. La matrice d’occurrences pourra prendre la forme que voici :
| Terme | Document 1 | Document 2 | Document 3 | ... |
| sine | 2 | 0 | 1 | ... |
| qua | 2 | 0 | 1 | ... |
Cette forme de redondance est nuisible tant pour la rapidité de traitement que pour la précision du système : l’expression sine qua devrait compter comme un seul terme et non deux.
Le livre de référence du cours introduit le modèle du Latent Semantic Indexing (indexation sémantique latente) qui peut s’expliquer ainsi : on peut simplifier la matrice d’occurrences par la décomposition en valeurs singulières [1]. Le modèle Latent Semantic Indexing nous invite à « regrouper les mots » ayant le même « sens ».
Rappelez-vous que vous pouvez calculer la décomposition en valeur singulière d’une matrice en utilisant une librairie comme JAMA.
Dans le langage Python, on peut calculer la décomposition en valeurs singulières de la matrice d’occurrences de notre exemple en utilisant la librairie Numerical Python.
from LinearAlgebra import *
from Numeric import *
U,S,V=singular_value_decomposition( array([[0.6,0.6,0], [0,0,1.6], [3.2,0,0], [0,1.6,0], [0.6,0,0.6]]))Notre matrice peut alors se décomposer de la manière suivante [2] :
$\begin{eqnarray*}\left [ \begin{array}{ccc} -0.19 & 0.25 & 0.23 \\ -0.02 & -0.66 & 0.66 \\ -0.96 & 0.0 & -0.12 \\ -0.02 & 0.66 & 0.66 \\ -0.19 & -0.25 & 0.23 \end{array} \right ] \left [ \begin{array}{ccc} 3.32 & 0 & 0 \\ 0 & 1.71 & 0 \\ 0 & 0 & 1.70 \end{array} \right ] \left [ \begin{array}{ccc} -1 & -0.045 & -0.045 \\ 0 & 0.7071 & -0.7071 \\ -0.06 & 0.7057 & 0.7057 \end{array} \right ] =\\ \left [ \begin{array}{ccc} 0.6 & 0.6 &0 \\ 0 &0& 1.6\\ 3.2 & 0 & 0\\ 0 & 1.6 & 0\\ 0.6 & 0 & 0.6 \end{array} \right ] \end{eqnarray*} $
Observez que la première matrice nous donne trois vecteurs orthogonaux : un des vecteurs (la première colonne) peut être compris comme étant
« -0.19 pour Jean, -0.02 pour ferme, -0.96 pour usine, -0.02 pour pommes, -0.19 pour Pierre ». Chacun des trois vecteurs représente une façon de regrouper les 5 termes. On peut regrouper ces 5 termes en 3 groupes de termes pondérés « orthogonaux ».
Dans ce cas particulier, la décomposition en valeurs singulières n’est pas d’une utilité évidente parce que la matrice diagonale n’a pas de valeur nettement proche de zéro sur sa diagonale (3.32, 1.71, 1.70), même si l’une des trois valeurs est plus importante que les trois autres.
Si on calcule une matrice réduite par la méthode de la décomposition en valeurs singulières, on obtient [3] :
$\begin{eqnarray*}\left [ \begin{array}{ccc} -0.19 & 0.25 & 0.23 \\ -0.02 & -0.66 & 0.66 \\ -0.96 & 0.0 & -0.12 \\ -0.02 & 0.66 & 0.66 \\ -0.19 & -0.25 & 0.23 \end{array} \right ] \left [ \begin{array}{ccc} 3.32 & 0 & 0 \\ 0 & 1.71 & 0 \\ 0 & 0 & 0 \end{array} \right ] \left [ \begin{array}{ccc} -1 & -0.045 & -0.045 \\ 0 & 0.7071 & -0.7071 \\ -0.06 & 0.7057 & 0.7057 \end{array} \right ] \approx\\ \left [ \begin{array}{ccc} 0.62 & 0.33 &-0.27 \\ 0.071 &-0.80 & 0.80\\ 3.19 & 0.14 & 0.14\\ 0.071 & 0.80 & -0.80\\ 0.62 & -0.27 & 0.32 \end{array} \right ] \end{eqnarray*} $
Cette nouvelle matrice est une approximation de notre matrice d’occurrences, mais « simplifiée » ou « débruitée ». Elle équivaut à faire disparaître le dernier des trois vecteurs orthogonaux de la première matrice. En somme, au lieu de dire qu’on peut regrouper les 5 termes en 3 groupes de termes pondérés, on dit maintenant qu’on peut « approximativement » les regrouper en seulement 2 groupes. En pratique, avec des matrices d’occurrences importantes, ce type d’analyse mène à des systèmes plus robustes qui peuvent traiter, en partie, les problèmes de polysémie et de synomymie en travaillant avec des groupes de termes pondérés au lieu de termes individuels.
Lors d’une requête d’un utilisateur, on procédera de la même façon qu’avec l’ancienne matrice d’occurrences pour déterminer le bon document à recommander, c’est-à-dire qu’on calculera le cosinus avec les vecteurs-colonnes. La nouvelle matrice simplifiée peut donner de meilleurs résultats.
Le calcul de la décomposition en valeurs singulières prend un temps $O(n^3)$. Néanmoins, le modèle Latent Semantic Indexing est une norme utile en recherche d’informations et constitue le sujet de beaucoup de travaux de recherche.
Référence
Deerwester, S., Dumais, S.T., Furnas, G.W., Landauer, T.K., and Harshman, R., Indexing by latent semantic analysis, Journal of the American Society for Information Science, 41 (6), 1990, p. 391-407.
[1] Voir l’article sur les vecteurs et matrices, présenté dans la première semaine.
[2] Le produit de ces trois matrices est égal à notre matrice d’occurrences. Cette vérification est un exercice.
[3] Observez que la matrice diagonale a une composante en moins !
