Accéder à la page principale du cours

Skip-Gram with Negative Sampling

Adrien Guille, Université Lyon 2

Skip-Gram with Negative Sampling (SGNS) est probablement la méthode la plus connue et la plus utilisée pour apprendre des représentations vectorielles des mots. Elle a été présentée en 2013 par Mikolov et al. lors de la conférence NIPS (consulter l'article).

Notations

Modèle

On modélise la probabilité conditionnelle d'observer le mot , sachant que le mot apparaît à moins de mots de distance. Cette probabilité est paramétrée par les représentations vectorielles des mots :

On reconnaît la fonction sigmoïde, , appliquée au produit scalaire du vecteur cible du mot avec le vecteur contexte du mot :

fonction sigmoide

La fonction sigmoïde étant strictement croissante, plus le produit scalaire des représentations de deux mots est grand (ce qui signifie que les deux vecteurs sont similaires), plus la probabilité conditionnelle est importante.

Estimation des paramètres

Dans le but de déterminer les paramètres, c'est-à-dire les matrices et , les représentations des mots, on met en œuvre la démarche suivante :

  1. À partir du corpus , on construit un jeu de données, qui consiste en un multi-ensemble de paires de mots ;
  2. On définit un problème d'optimisation, sous l'hypothèse , basé sur ce jeu de données ;
  3. On calcule les représentations des mots ce problème par la méthode du gradient stochastique.

1. Construction du jeu de données

Le jeu de données consiste en un multi-ensemble de paires de mots, chaque paire étant composée d'un mot cible et d'un mot contexte : . Pour construire ce multi-ensemble, on fait glisser une fenêtre sur le corpus . La fenêtre est une séquence de tokens, en 3 parties :

Pour chaque fenêtre, on crée une paire pour chaque mot contexte , étant le mot cible, au centre de la fenêtre.

2. Définition du problème

On définit un problème de maximisation de la vraisemblance du jeu de données sous l'hypothèse :

Le logarithme étant une fonction strictement monotone croissante, maximiser la fonction de vraisemblance est équivalent à maximiser le log de cette fonction :

On remarque que ce problème admet une solution triviale. En effet, il suffit de choisir et comme deux matrices dont les coefficients sont tous fixés à une constante de sorte à obtenir pour toute paire de mots un produit scalaire élevé et donc une probabilité conditionnelle proche de 1. Par exemple, en choisissant 1 pour constante, le produit scalaire vaudra .

Échantillonnage négatif

Pour éviter cette solution triviale, on introduit un terme d'échantillonnage négatif :

La fonction sigmoïde étant symétrique, on peut légèrement simplifier l'écriture :

Il s'agit donc de maximiser pour les paires de mots tirées du corpus (les paires "positives"), et de maximiser pour des paires "négatives" de mots, où le mot contexte est tiré aléatoirement selon (c'est-à-dire la fréquence d'occurrence dans , lissée). La valeur de , un hyper-paramètre, contrôle le ratio entre le nombre de paires positives et le nombre de paires négatives. En pratique, on choisit entre 1 et 15.

On peut donc formuler ce problème comme un problème de classification supervisée binaire, où il s'agit de distinguer des paires de mots positives de paires de mots négatives. Soit le jeu de données étiqueté , composé de triplets , où indique si la paire de mots est positive ou négative. On construit selon la procédure suivante. Pour chaque paire , on ajoute à le triplet et on ajoute triplets , les étant tirés aléatoirement selon . Enfin, on exprime la log-vraisemblance de ce jeu de données :

3. Calcul des vecteurs selon la méthode du gradient stochastique

La fonction à maximiser étant définie par une somme, on applique la méthode du gradient stochastique. Le principe est le suivant :

  1. On initialise aléatoirement les matrices et .
  2. On parcourt la somme sur , et pour chaque terme, on modifie les vecteurs et dans la direction du gradient de cet élément, respectivement, en et en .

Gradients

Soit un élément de la somme qui définit la log-vraisemblance. Le gradient de en est le vecteur , qui décrit les dérivées partielles de en chaque composante de :

La dérivée partielle de en , une composante quelconque de , est :

Similairement, la dérivée partielle de en une composante quelconque de est :

Algorithme

En pratique, on réalise plusieurs itérations, c'est-à-dire qu'on parcourt plusieurs fois la somme. Le plus simple est de fixer un nombre d'itérations, . On limite également la magnitude de la modification à l'aide d'un pas d'apprentissage. Là encore, le plus simple est de fixer une valeur, . L'algorithme est le suivant :

  1. Construire le jeu de données

  2. Initialiser aléatoirement et

  3. Répéter fois

    1. Mélanger aléatoirement

    2. Pour chaque triplet , mettre à jour les vecteurs selon les formules :

Dans l'implémentation originale (consulter le code), les valeurs par défaut de , , et sont :