Accéder à la page principale du cours

Skip-Gram with Negative Sampling as Matrix Factorization

Adrien Guille, Université Lyon 2

Le modèle Skip-Gram with Negative Sampling (consulter la page dédiée) apprend les représentations vectorielles des mots en résolvant un problème de classification supervisée binaire. En 2014, Levy et Goldberg ont exposé une vision différente, lors de la conférence NIPS (consulter l'article). Ils expliquent comment formuler Skip-Gram with Negative Sampling comme un problème de factorisation de matrice : .

Ré-écriture de la fonction objectif de SGNS

Soit la fréquence absolue de la paire de mots dans le multi-ensemble , et la nombre de paires dont l'un des deux mots est . On peut ré-écrire l'objectif de Skip-Gram avec échantillonnage négatif, en factorisant les éléments répétés de la somme :

La partie droite ne dépendant pas de , on peut simplifier :

On écrit explicitement le terme d'espérance, en prenant :

Étude de l'objectif pour une paire de mots

Soit , la partie de la somme correspondant à la paire de mots . On note et on cherche à résoudre en pour déterminer pour quelle valeur de ce produit scalaire est maximal. D'abord, on calcule la dérivée partielle de en :

On simplifie l'écriture de la constante en facteur de , en notant , et on résoud en :

On introduit l'expression de :

On remplace par son expression :

On obtient alors :

Lien avec la mesure d'information mutuelle ponctuelle

L'information mutuelle ponctuelle des mots et , notée , quantifie l'intensité de l'association entre ces deux mots. Plus sa valeur est grande, plus l'association est forte :

Avec , et . On a donc :

On en conclue que Skip-Gram with Negative Sampling tente d'apprendre des représentations vectorielles des mots, de telle sorte que le produit scalaire approche la mesure d'information mutuelle des mots et , diminuée de .

Formulation de Skip-Gram with Negative Sampling comme une factorisation de matrice

Il s'agit donc de déterminer les matrices et , telles que approche la matrice qui décrit la mesure d'information mutuelle entre toute paire de mots , :

Cette formulation présente plusieurs défauts. Premièrement, en vertue de la loi de Zipf, la plupart des mots ne coccurrent jamais, ce qui conduit à observer souvent . Or, la mesure de PMI n'est pas définie dans ce cas, du fait du logarithme. Deuxièmement, lorsque le ratio est inférieur à 1, est inférieur à 0. Toujours en vertue de la loi de Zipf, ce cas est également fréquent.

Levy et Goldberg suggèrent donc un problème alternatif, en remplaçant la PMI par la mesure d'information mutuelle diminuée positive, :

Il s'agit alors de factoriser une matrice creuse, :

Estimation des paramètres

Une manière d'estimer et consiste à définir une fonction de coût selon l'erreur de reconstruction de la matrice par , et à la minimiser par descente de rgadient stochastique, c'est par exemple ce que fait GloVe (consulter la page dédiée).

Décomposition spectrale

Une autre approche, consiste à estimer et par décomposition spectrale. Pour cela, on calcule la décomposition en valeur singulières tronquée à l'ordre de la matrice :

Par définition, et sont des matrices réelles denses qui décrivent les premiers vecteurs singuliers, à gauche et à droite, tandis que est une matrice diagonale qui décrit les premières valeurs signulières. On définit et de la sorte :

Cette approche a notamment pour avantage d'être simple à implémenter, la décomposition en valeur singulière tronquée de matrices creuses étant déjà implémentée de manière très efficace dans la plupart des librairie d'algèbre linéaire.