Accéder à la page principale du cours

GloVe: Global Vectors for Word Representation

Adrien Guille, Université Lyon 2

L'alternative la plus connue à la méthode Skip-Gram with Negative Sampling est le modèle GloVe. Il a été présenté en 2014 par Pennington et al. lors de la conférence EMNLP (consulter l'article).

Notations

Modèle

Contrairement à SGNS, qui détermine les représentations vectorielles en résolvant une tâche de classification supervisée binaire, GloVe formule un problème de régression. On modélise le logarithme de la fréquence de co-occurrence des mots et , , de la sorte :

Ainsi, plus la fréquence de co-occurrence est élevée, plus leurs représentations doivent être similaires -- en vertue de l'hypothèse distributionnelle -- et donc plus leur produit scalaire doit être grand. Le logarithme permet de compresser les fréquences et de limiter la norme des vecteurs. Les biais quant à eux permettent d'absorber en partie l'erreur, notamment pour les paires de mots où l'un ou l'autre des mots co-occurrent fréquemment avec beaucoup de mots différents, e.g. un mot vide, sans pour autant qu'il soit sémantiquement proche.

Estimation des paramètres

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

  1. À partir du corpus , on construit une matrice décrivant les co-occurrences entre mots ;
  2. On définit un problème de factorisation de matrice ;
  3. On calcule les représentations des mots et les biais par une méthode de gradient stochastique adaptif.

1. Construction de la matrice de co-occurrence

Pour construire cette matrice, , on fait glisser une fenêtre sur le corpus . La fenêtre est une séquence de tokens, en 3 parties :

Pour chaque mot contexte , on incrémente de 1.

2. Définition du problème

On définit un problème de factorisation de matrice, avec une fonction de coût de type moindres carrés pondérés :

Avec :

fonction f

La fonction joue plusieurs rôle. Premièrement, elle permet de diminuer l'importance des co-occurrences rares en leur attribuant un poids faible. Deuxièmement, elle limite l'importance des co-occurrences sur-représentées en bornant leur poids à 1 (le seuil est fixé à 100 dans expérimentations présentées par les auteurs). Enfin, elle exclue les coefficients nuls de , ce qui permet de réduire drastiquement la complexité temporelle de l'estimation des paramètres (et accessoirement, permet de gommer le problème du logarithme non défini en 0).

En effet, en pratique, la taille du vocabulaire, , oscille autour de . Par conséquent, la matrice comporte de l'ordre de coefficients. Or, par nature, environ 95% de ces coefficients sont nuls, la plupart des mots ne co-occurrant jamais avec la vaste majorité des mots.

3. Calcul des vecteurs selon une méthode de gradient stochastique adaptif

La fonction à minimiser é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 les indices de la matrice , et pour chaque paire telle que , on modifie les vecteurs et dans la direction opposée du gradient de cet élément, respectivement, en et en ; on modifie les biais et dans la direction opposée de la dérivée partielle de cet élément, respectivement, en et en .

Gradients et dérivées partielles

Soit un élément de la somme qui définit le coût de reconstruction. Le gradient de en est le vecteur :

Similairement, la gradient de en est :

La dérivée partielle de en est le scalaire :

Similairement, la dériviée partielle de en est le scalaire :

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 choisit un pas d'apprentissage initial, , puis on le régule, par paramètre, en fonction de la somme de la norme des gradients passés. Cette technique s'appelle AdaGrad (consulter l'article). L'algorithme est le suivant :

  1. Construire la matrice

  2. Initialiser aléatoirement , , et

  3. Instancier deux matrices nulles, et , de même dimensions que et , et deux vecteurs nuls, et , de même dimensions que et

  4. Répéter fois :

    1. Mélanger aléatoirement la liste des coefficients non nuls

    2. Pour chaque :

      1. Calculer , , et

      2. Mettre à jour les paramètres selon :

      3. Mettre à jour les historiques des gradients :

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