WordToVector

Table of Contents

1 Word2Vector – Un point d'étape

1.1 Introduction

L'objectif de ce document est de faire un point sur la représentation vectorielle de mots (aussi appelée embedding) pour réfléchir à ce que devra contenir un logiciel permettant de créer des représentations vectorielles de mots à partir de corpus. Tout ce qui suit concerne la langue anglaise. Il sera donc nécessaire de réfléchir ensuite au cas du français et, éventuellement, au cas multi-langues.

On part d'un corpus de textes, on définit un vocabulaire de mots \(V_w\) et un vocabulaire de contextes \(V_c\). L'objectif est de représenter tout mot \(w\) par un vecteur \(\vec{w}\). Les vecteurs \(\vec{w}\) (resp. \(\vec{c}\)) sont les lignes d'une matrice W de dimension \(|V_w| \times d\) représentant les mots. Certaines méthodes permettent également de représenter tout contexte \(c\) par un vecteur \(\vec{c}\) donnant une matrice \(C\) de dimension \(|V_c| \times d\). Nous allons étudier trois types de méthodes :

  • les méthodes à base de compte (count methods) où on définit explicitement la matrice \(W\) avec en ligne les mots et en colonne les contextes et on remplit la matrice avec un calcul basé sur les fréquences d'apparition des mots dans les contextes.
  • les méthodes à base de compte avec réduction de dimension où on définit une matrice \(M\) comme précédemment à laquelle on applique une méthode de réduction de dimension pour produire une matrice \(W\) représentant les mots et une matrice \(C\) représentant les contextes.
  • les méthodes prédictives (ou par apprentissage) où on apprend explicitement une matrice \(W\) en choisissant un critère d'apprentissage.

Dans une première partie, nous allons parcourir ces méthodes et revoir la littérature sur les comparaisons entre ces méthodes. Mais il faut d'abord être fixé sur la façon d'évaluer les choix. Nous allons donc, dans un premier temps, décrire les tâches ayant servi à l'évaluation des représentations. Nous présentons ensuite les corpus de référence et les pré-traitements sur les textes. Nous présentons ensuite les principales propositions de la littérature pour chacun des trois types de méthodes. Nous terminons par une comparaison et une conclusion.

Dans une seconde partie, nous spécifions les attendus du système de création de représentations vectorielles en prenant en compte les conclusions de la première partie et nos objectifs de recherche et d'utilisation dans des projets collaboratifs appliqués.

1.2 L'évaluation des représentations

1.2.1 Les distances

Tout d'abord, les représentations vectorielles des mots vont être principalement utilisés pour comparer des mots dans le but de voir si les résultats de la comparaison sont pertinents relativement au problème cible. On peut choisir distance ou similarité mais la plupart des travaux se basent sur des distances. Il est intéressant de noter que, si les choix de distances sont discutés en terme de performances, ils ne le sont pas toujours en terme d'adéquation en terme de représentation. Par exemple, on peut utiliser une Cosine similarité sur un vecteur de probabilités. Les principales distances utilisées sont :

  • distance euclidienne \(d(x,y)=\sqrt{\sum(x_i-y_i)^2}\)
  • distance de Manhattan (City Block) \(d(x,y)=\sum{|x_i-y_i|}\)
  • Cosine distance \(d(x,y)=1-cos(x,y)\)

Si les vecteurs sont des vecteurs probabilistes (composantes entre 0 et 1 de somme 1), alors on peut aussi utiliser les distances :

  • distance de Hellinger \(d(x,y) = \sum (\sqrt{x_i}-\sqrt{y_i})^2\)
  • distance de Kullback-Leibler \(d(x,y) = \sum(x_i log(\frac{x_i}{y_i}))\)
  • distance de Bhattacharya \(d(x,y) = - \log(\sum(\sqrt{x_i}\sqrt{y_i}))\)

Si ces distances sont les principales utilisées, la liste est bien sur non limitative et on pourrait également penser à utiliser des similarités. Je n'ai pas vu considérer de noyaux.

1.2.2 Les tâches

Les surveys s'intéressent, en général, à plusieurs tâches. On distinguera la période avant l'introduction de la tâche "Analogy" en 2013 de la période qui suit. En effet, les résultats et constats sont différents selon qu'on considère cette tâche ou pas. On notera également que le risque de spécialisation existe car des choix pertinents pour une tâche ne se généralisent pas toujours. On notera également que pour les tâches de calcul de topic d'un document ou de calcul de sens des mots (cf exposé Tim), les résultats et les choix diffèrent également. Les tâches considérées ici sont :

  • TOEFL – Synonym Detection (LandauerDumais'97) : 80 questions à choix multiples avec 4 candidats. Par exemple : levied – imposed (correct), believed, requested, correlated. Le système choisit un synonyme en utilisant les représentations vectorielles et une similarité (souvent Cosine) et on mesure le taux de correction.
  • Similarity Judgments (BullinariaLevy'07'12). 200 paires de mots jugés reliés sémantiquement comme king et queen, concept et thought, cut et slice, … On compare la distance entre une cible, le mot relié et 10 mots tirés au hasard.
  • Semantic Categorization (BullinariaLevy'07'12). On considère 53 catégories sémantiques comme cities, flowers, … On mesure si la représentation vectorielle d'un mot est plus proche de sa catégorie sémantique que des autres catégories en supposant que la représentation vectorielle d'une catégorie est la moyenne des représentations des mots de la catégorie.
  • Syntactic Categorization (BullinariaLevy'07'12). Idem avec 12 catégories syntaxiques. Fait pour tester si on capture aussi des informations syntaxiques dans la représentation vectorielle.
  • Clustering Purity (BullinariaLevy'07'12). 60 noms répartis en catégories. On utilise la représentation vectorielle pour faire un clustering et on mesure la pureté du clustering obtenu wrt le clustering cible.
  • Semantic Relatedness (RubensteinGoodenough'65 – Baronietal'14). 65 paires de noms avec une similarité évaluée par des humains qui est comparée à une similarité calculée avec les représentations vectorielles.
  • Analogy (Mikolovetal'13 – Baronietal'14). L'objectif est de trouver le quatrième élément d'un quadruplet (\(x\) - \(y\), \(z\) - ?). On calcule le ? en calculant le mot dont la représentation vectorielle est la plus proche pour la Cosine distance de \(\vec{x} - \vec{y} + \vec{z}\). On mesure le taux de correction du système. Il est important de noter que les performances doivent être étudiées pour les deux cas (syntaxique et sémantique) car les résultats sont très différents. Il est également important de noter que la méthode utilisée pour calculer l'analogie n'est pas la meilleure. Goldberg et Levy propose le ? qui maximise \(\frac{cos(y,?).cos(?,z)}{cos(?,x)+\epsilon}\) avec \(\epsilon\) petit (0.001). Ils montrent que cette règle est toujours meilleure que la précédente. Il y a deux datasets : Google's analogy dataset constitué de 19 544 analogies dont 8869 syntaxiques comme (work-works, speak-speaks) et 10675 sémantiques comme (brother-sister, grandson-granddaughter) ; et MSR's analogy dataset qui contient 8000 analogies morpho-syntaxiques comme (good-best, smart-smartest).

1.3 Les préalables à la construction de représentations vectorielles

1.3.1 Les corpus

Comme dit dans l'introduction, les corpus sont des corpus en langue anglaise. Les principaux corpus utilisés sont :

  • BNC British National Corpus 90% de texte écrit et 10% de texte parlé. La taille approximative est de 100 million de mots. Il est annoté au besoin avec part-of-speech et désambiguisation.
  • English Wikipedia
  • ukWaC est tiré du The Web-As-Corpus Kool Yinitiative. C'est un corpus de 2 milliards de mots obtenu en crawlant le Web du domaine uk en utilisant comme graines les mots de fréquence moyenne du BNC corpus. On notera qu'il existe aussi le frWaC sur ce site construit sur le même principe à partir du Web français.

Les travaux utilisent un corpus ou une combinaison de ces 3 corpus dans les expériences.

1.3.2 Les pré-traitements

Les corpus sont nettoyés pour obtenir des séquences de mots. Les traitements sont peu détaillés mais on peut penser qu'ils prennent tout ce qui est considéré comme mot par le programme de segmentation utilisé, donc les nombres et noms propres. La casse n'est pas considérée en général et les mots sont réduits à des chaînes de minuscules. Le traitement de fin de phrase n'est pas non plus précisé.

Le stemming (garder la racine) et la lemmatisation sont étudiés dans BullinariaLevy12. Il est montré expérimentalement que le stemming ne permet pas d'améliorer les performances (sur les tâches citées plus haut). La lemmatisation permet parfois d'améliorer les performances mais jamais de façon significative. Leur conclusion est de dire que la lemmatisation peut être utilisée si on veut jouer les derniers pourcents sur une tâche particulière.

Les prétraitements considérés et les conclusions concernent la langue anglaise. La langue française pourrait amener à d'autres conclusions. Par exemple, la morphologie riche de la langue française pourrait donner une importance plus grande à la lemmatisation. Il nous faut garder en mémoire que nous aurons à considérer d'autres pré-traitements pour traiter d'autres langues et pour considérer des contextes plus riches que les mots autour du mot.

1.4 Les méthodes basées sur les comptes

On suppose choisis un corpus, un dictionnaire de mots et une notion de contexte. J'appelle \(w\) un mot et \(c\) un contexte et on construit une matrice avec en ligne les mots et en colonnes les contextes. Les différents comptes considérés sont (voir petit exemple en R):

  • Matrice des comptes \(\#(w,c)\) contenant le nombre d'apparitions du mot \(w\) dans le contexte \(c\) dans le corpus
  • Matrice des probabilités \(P(w,c)\) contenant la probabilité de trouver le couple mot \(w\) et contexte \(c\) dans le corpus
  • Matrice des probabilités \(P(c|w)\) contenant la probabilité de trouver le contexte \(c\) sachant le mot \(w\). Ceci revient à faire une normalisation linéaire en ligne de la matrice des comptes
  • Matrice des ratios \(\frac{P(c|w)}{P(c)}\) entre probabilité de l'événement c sachant w et la probabilité de l'événement c. Note : \(\frac{P(c|w)}{P(c)} = \frac{P(w|c)}{P(w)} = \frac{P(w,c)}{P(w)P(c)}\)
  • Matrice PMI (Pointwise Mutual Information) \(\log(\frac{P(c|w)}{P(c)})\). Cette quantité est nulle lorsque \(P(c|w)=P(c)\) ou encore lorsque \(P(w|c)=P(w)\) càd lorsque l'apparition de \(c\) est indépendante de la connaissance de \(w\). Lorsqu'une paire \((w,c)\) n'apparaît jamais alors \(PMI(w,c)=\log(0)=-\infty\) mais une approche commune est de poser \(PMI(w,c)=0\) dans ce cas. Cette quantité est positive lorsque \(P(c|w)>P(c)\) càd \(w\) apporte de l'information sur l'apparition de \(c\). Cette quantité est négative sinon. Pour se faire une idée de la sémantique, on peut regarder un classement pour des paires de mots calculés sur la déclaration d'indépendance. On trouve des scores élevés pour "Great Britain" (7.22), "United States" (6.8) et des scores négatifs pour "and the" (-0.14) et "of and" (-0.75). Note : les mots rares ont tendance à avoir une PMI élevée et c'est pour cette raison qu'il est courant de limiter le vocabulaire aux mots avec une fréquence supérieure à un seuil.
  • Variantes de la matrice PMI
    • PPMI où on seuille à 0 la matrice PMI, i.e. \(max(0,\log(\frac{P(c|w)}{P(c)}))\). Ceci permet de ne pas tenir compte des paires \((w,c)\) telles que \(\#(w,c)=0\) ou \(P(c|w)<P(c)\)
    • La shifted PPMI \(SPPMI(w,c)=max(PMI(w,c)-\log(k);0)\) avec un paramètre \(k>1\).
    • La smoothed PMI avec un paramètre \(\alpha\) et définie par \(PMI_{\alpha}(w,c) = \log(\frac{P(w,c)}{P(w)P^{\alpha}(c)})\) où \(P^{\alpha}(c)=\frac{\#(c)^{\alpha}}{\sum_c \#(c)^{\alpha}}\), souvent \(\alpha=0.75\).
  • Matrice tf-idf où tf(w,c) peut être le compte #(w,c) ou la proba P(c|w) et idf(w) = log((#contextes)/(#contextescontenantw))

Il existe d'autres formules de calcul à base de comptes. Note : certains travaux avec des contextes de type fenêtre utilisent une matrice indicée en ligne et en colonne par les mots. Dans ce cas, la composante d'indice \((w,w')\) concerne le compte correspondant à présence de \(w\) et \(w'\) dans la même fenêtre. Par exemple, \(PMI(w,w') = \log(\frac{P(w,w')}{P(w)P(w')})\) où \(P(w,w')\) est la probabilité dans le corpus que \(w\) et \(w'\) se trouvent dans la même fenêtre.

BullinariaLevy07 montre de façon empirique sur les quatre premières tâches précitées que

  1. sans prétraitement, ni posttraitement, Positive PMI avec Cosine similarity l'emporte sur toutes les tâches
  2. bon comportement statistique des mesures en faisant varier taille du vocabulaire et des corpus
  3. BullinariaLevy12 montre une amélioration des performances par taille croissante de corpus. Ils montrent aussi que avec BNC et un extrait de ukWaC de même taille que BNC, on obtient de meilleurs résultats avec BNC. Et que, par contre, en augmentant la taille de ukWaC on arrive à dépasser les résultats obtenus avec BNC.

Ils étudient également l'influence du choix des contextes de type fenêtres de mots. Les contextes considérés sont x mots à gauche, x mots à droite, centrés avec x mots à gauche et x mots à droite (notés x-x). On considère également le cas où on considère les deux contextes gauche et droit (notés x&x) mais il faut adapter les mesures de compte ce que je n'ai pas vu. BullinariaLevy07 montre de façon empirique sur les quatre premières tâches précitées que

  1. si on fait varier la forme de la fenêtre, sa taille, l'importance des mots dans la fenêtre. Avec la positive PMI et la Cosine similarity, on obtient toujours les meilleurs résultats avec 1-1 et 1&1. Pour les autres distances, les résultats peuvent varier selon la fenêtre.
  2. si on se restreint aux contextes les plus fréquents (par fréquence des contextes ou des mots dans les contextes), pour PPMI et Cosine, les résultats s'améliorent si on augmente le nombre de contextes conservés. Pour PPMI et Euclidienne, on a une cloche et donc une dégradation des performances si on garde trop de contextes, en particulier si on les garde tous.

Une conclusion de BullinariaLevy07 est que la taille de fenêtres ne semble pas influer grandement et les meilleurs résultats sont souvent obtenus avec 1-1. Cependant, ces résultats ont été remis en question par des études plus récentes. En effet, sur la tâche Analogy, la fenêtre 1-1 ne donne pas les meilleurs résultats car elle peine à capturer des relations sémantiques indépendants de la proximité immédiate. Les meilleurs résultats sont obtenus avec 5-5 voire 10-10 selon que l'on considère les analogies syntaxiques ou sémantiques.

Une autre conclusion de BullinariaLevy07 est qu'il semble intéressant de se limiter aux contextes de fréquence supérieure à un seuil, c'est-à-dire aux contextes les plus fréquents. Des études récentes reviennent également sur cette conclusion. Par exemple, LebretCollobert15 montre que, sur toutes les tâches (dont Analogy), les résultats avec tous les mots, les 10 000 mots les plus fréquents, les mots de fréquence supérieure à 10^-6 sont proches. Un autre axe est de limiter l'influence des mots trop fréquents. Par exemple, LebretCollobert15 résultats sont meilleurs si on élimine les mots les plus fréquents et donc de considérer les mots de fréquence inférieure à 10^-5 ou les mots de fréquence entre 10^-6 et 10^-5. Goldberg et Levy étudient aussi dans le cadre de la PPMI le retrait des mots trop fréquents pour le calcul des contextes avec des résultats non convaicants (amélioration dans 50\% des cas).

1.5 Les méthodes avec réduction de dimension non supervisée

On suppose choisi un corpus, un dictionnaire de mots et une notion de contexte. On construit une matrice \(M\) avec en ligne les mots et en colonne les contextes pour une mesure de compte choisie. Nous examinons ici l'effet de la réduction de dimension de la matrice M sur les performances.

On peut noter que pour la LSA (Latent Semantic analysis) qui produit des concepts à partir de documents, la réduction de dimension de la matrice des comptes de fréquence a été démontrée comme pertinente. La situation est moins claire sur des tâches sémantiques sur les mots car les matrices de compte comme PPMI avec Cosine donnent déjà d'excellents résultats. BullinariaLevy12 se propose d'étudier l'influence de la réduction de dimension dans ce cadre.

Les méthodes de dimension de réduction principalement considérées utilisent la PCA de la matrice \(M^tM\) ou la SVD de \(M\). Les deux méthodes vont fournir une matrice \(M_d\) de rang d qui minimise la distance de reconstruction selon la norme de Frobenius. Noter que Collobert font la même chose sur \(\sqrt{M}\) et on obtient alors une matrice qui minimise la distance de reconstruction selon la distance de Hellinger. Noter aussi que LebretCollobert propose la stochastic low rank approximation (SLRA) comme méthode de réduction de dimension. La factorisation SVD de \(M\) est \(M=U \Sigma V^t\) permet, pour une dimension \(d\) choisie, de définir les matrices \(W=U_d \Sigma_d\) et \(C=V_d\) pour représenter mots et contextes. Mais ce choix est remis en question dans le point 2 ci-après et dans le papier de Goldberg et Levy.

On peut noter aussi que pour la recherche de sens des mots, on utilise aussi des méthodes de factorisation de matrices non négatives (NMF) qui semblent mieux adaptées pour trouver le sens des mots. Ces méthodes sont non supervisées (ou sans apprentissage) et on les considère comme une amélioration des méthodes de compte.

BullinariaLevy12 étudie l'apport de la SVD et leurs résultats empiriques principaux sont :

  1. On fait varier la taille de la matrice M (50000, 25000, 12500 dimensions), on ordonne les contextes par fréquence croissante. On compare les performnaces avec une matrice réduite aux N premières compsantes avec une matrice réduite de dimension N obtenue par SVD. On montre que pour N petit (moins de mille), la SVD améliore les résultats. pour quelques milliers de dimensions, les deux matrices ont des performances très proches.
  2. Une autre étude basée sur un constat issu de travaux précédents (Caron01) porte sur l'influence des premières valeurs singulières. si on remplace \(\Sigma\) (la matrice diagonale des singular values) par \(\Sigma^{0.25}\) (cad on diminue l'importance des valeurs singulières les plus grandes), on gagne dans tous les cas et on améliore le standard pour plusieurs milliers de dimensions. On a également de bons résultats en enlevant les 100 premières valeurs singulières. Si on fait varier l'exposant, on montre amélioration avec exposant <1 et un pic à 0.25. Pour la méthode d'exclusion, le nombre à exclure est dépendant de la tâche mais exclure des premières composantes améliore.
  3. On teste la validité statistique des résultats en faisant varier la taille du corpus. Plus le corpus est grand moins la validité statistique des différences constatées (choix de l'exposant, nombre de composantes à exclure) est significatif. Sur le TOEFL, on arrive avec des bons choix de paramètres à atteindre les 100% mais avec un comportement différent des autres tâches. Il faut donc être très prudent sur les résultats et sur la généralisation de résultats d'une tâche à l'autre.
  4. Le papier se termine par une tentative d'interprétation du phénomène d'exclusion. Les premières composantes contiennent de l'information utile. Cependant les enlever et garder quelques milliers de composantes améliore les résultats. L'interprétation proposée est que les premières composantes contiennent de l'information syntaxique et sémantique, que l'information sémantique est répartie sur toutes les valeurs et que, par conséquent, supprimer ou diminuer l'influence des premières valeurs enlèverait du bruit sur la sémantique. Ils font des expériences en ajoutant du bruit, en utilisant les méthodes d'exclusion sur BNC, en regardant ce qui se passe sur les premières composantes. Ces expériences ne donnent pas de conclusion claire si ce n'est de constater que : "highest variance dimensions tend not to contribute the most useful information about semantics and have a large "noise" component that is best removed or reduced".

Ils concluent que la réduction de dimension améliore les performances avec un phénomène d'exclusion des plus grandes valeurs. L'espace des choix possibles est très grand et donc trouver les meilleurs paramètres est difficile avec un comportement statistique non démontré. Il faut être très attentif à ne pas se limiter à une seule tâche car les comportements peuvent être différents et que les résultats ne se généralisent pas nécessairement. Note : l'étude ne porte que sur la représentation avec contexte 1-1, PPMI et évaluation avec Cosine et ne se généralise pas nécessairement à d'autres choix.

LebretCollobert15 font l'étude de la réduction de dimension avec la matrice des P(c|t), les contextes 5-5 et 10-10, la distance de Hellinger, l'utilisation de la PCA dans les cas 10 000 mots les plus fréquents et 24 000 mots de fréquence entre 10^-6 et 10^-5. Ils trouvent également un pic de performance pour les tâches sémantiques simples, ce pic est autour de 1000 dimensions avec une équivalence entre 5-5 et 10-10. Par contre, pour les taches Analogy syntaxique et sémantique, les performances augmentent avec le nombre de dimension et 10-10 donne de meilleurs résultats que 5-5. Ils terminent sur une remarque sur l'inférence ou la compositionnalité. LebretCollobert15 défendent les méthodes à base de compte en considérant le cas des phrases ou des expressions. Soit une expression comme "Chicago Bulls" ou "New York City", on peut pour résoudre une tâche, utiliser un corpus pour construire une représentation vectorielle des mots, puis calculer avec le corpus le vecteur de contexte de cette expression, réduire le vecteur dans le cas d'une méthode avec réduction de dimension, et enfin l'utiliser pour trouver les mots proches. Par exemple, ils trouvent que "Chicago Bulls" est proche de Celtics, Lakers, … et "New York City" de Chicago, Brooklyn, NYC, … Ceci ne pouvant pas être réalisé par les méthodes prédictives étudiées ci-après sauf à assumer un mode de composition des vecteurs pour les expressions ou à introduire dans le vocabulaire les expressions avant apprentissage.

Nous reviendrons sur la SVD dans l'étude du papier de Goldberg et Levy

1.6 Les méthodes prédictives

Nous allons considérer ici des méthodes qui vont construire une représentation vectorielle de dimension réduite en utilisant un objectif supervisé. Nous allons principalement considérer les méthodes à base de réseaux de neurones de Mikolovetal13 et nous utilisons Baronietal14 pour comparer les méthodes prédictives et les méthodes à base de comptes (avec et sans réduction de dimension).

Comme les méthodes précédentes, ces approches ne sont pas récentes mais sont revenues en force essentiellement par les possibilités de passage à l'échelle pour la taille du dictionnaire, la taille de la fenêtre, la dimension choisie et le problème d'apprentissage modélisé. Les architectures de Mikolov sont des simplifications de l'architecture neural net language model (NNLM) proposée par Bengioetal03. Pour ce dernier, l'objectif est de prédire le mot courant connaissant les N mots précédents. NNLM est une architecture ayant une couche d'entrée avec indice des mots, une première couche dite de projection contenant les représentations vectorielles des mots, une couche cachée de calcul d'une fonction des N mots actifs et une couche de sortie qui calcule la probabilité du mot i sachant le contexte (on a une sortie par mot du vocabulaire). Pour donner un ordre de grandeur, le dictionnaire a une taille de l'ordre de 20 000 mots, N au maximum 6. Les calculs sont parallélisés, on utilise un ensemble d'apprentissage, de validation (model selection, weight decay, early stopping) et de test.

Mikolovetal13abcx propose une architecture simplifiée dans laquelle on partage la représentation des mots (toutes les représentations des mots considérés sont moyennées et envoyées à la même position) et on supprime la couche cachée de calcul. On simplifie la couche de sortie : au lieu d'une sortie par mot, on utilise une sortie codée avec un arbre de Huffman. Pour le modèle continuous bag of words (CBOW), on considère des fenêtres symétriques et l'objectif de l'apprentissage est de bien prédire le mot du milieu. Pour le modèle continuous skip-gram (SKIP-GRAM), l'architecture est similaire mais l'objectif est de prédire à partir du mot d'entrée un mot de son environnement proche. On tire aléatoirement le mot à prédire dans une fenêtre avec une proba décroissante en fonction de la distance au mot d'entrée. On apprend à le discriminer de mots tirés aléatoirement (negative sampling).

Dans les expériences, le vocabulaire est limité à 1 million de mots, la dimension de l'espace varie entre 50 et 600, la taille de l'échantillon d'apprentissage de 24 millions à 783 millions de mots. Les résultats montrent une évolution des performances avec dimension et taille de l'échantillon d'apprentissage croissantes. Une autre expérience compare les architectures avec 640 dimensions et une fenêtre 4-4, les deux architectures l'emportent sur l'état de l'art et CBOW l'emporte sur les analogies syntaxiques, SKIP-GRAM l'emporte nettement sur les analogies sémantiques. CBOW rattrape son retard avec plus de dimensions et plus d'exemples en utilisant un apprentissage distribué. Une première amélioration ultérieure porte sur l'utilisation d'une méthode de subsampling des mots les plus fréquents pendant l'apprentissage. Une seconde amélioration concerne la couche de sortie ou plutôt que d'estimer la probabilité d'un mot on cherche à le distinguer de mots tirés aléatoirement selon une distribution de bruit.

Baronietal14 compare les méthodes compte avec les méthodes prédictives. Pour les méthodes de compte, il considère la PPMI et le loglikelihood ratio et pour la réduction de dimension la SVD et une méthode de factorisation de matrices avec des dimensions réduites de 200 à 500, des fenêtres 2-2 et 5-5. Pour les méthodes prédictives, ils considèrent la méthode CBOW de Mikolovetal13 avec codage hiérarchique des sorties ou avec negative sampling (tirage d'exemples négatifs), un paramètre de sous-échantillonage des mots fréquents, des fenêtres 2-2 et 5-5, des dimensions de 200 à 500. Leur constat est que, bien que les modèles de compte se comportent bien sur les tâches choisies (une variation de celles de Bullinarietal12 avec Analogy en plus), les méthodes prédictives l'emportent. Les méthodes prédictives semblent assez robustes aux choix des paramètres avec des dégradations de performance en général peu importantes. Le modèle de compte pouvant être mauvais surtout pour un mauvais choix de fenêtre, comme la fenêtre 2-2 pour les analogies sémantiques. Mais, le plus mauvais modèle prédictif n'est pas très performant non plus dans ce cas. Pour les modèles de compte, ils retrouvent que PPMI et SVD sont des bons choix. Pour les modèles prédictifs, les deux méthodes à base de sampling (pour la prédiction et pour la sélection des exemples) améliorent les performances. On peut noter que les représentations de Collobert sont pas top. LebretCollobert15 se vengent avec un papier pour réhabiliter les méthodes de compte ! Ils montrent que pour les méthodes de compte, il faut considérer des fenêtres larges (normal si on veut traiter les analogies), il faut éliminer les mots fréquents. Ils obtiennent des performances un peu moins bonnes que les méthodes prédictives (non tunées). Note : le raw a le meilleur résultat, souvent nettement, sur les analogies sémantiques !

Une méthode prédictive alternative est la méthode GloVe proposée par Manning et al (Glove: Global Vectors for Word Representation, EMNLP 2014). Ce papier est intéressant car il définit un problème d'apprentissage en partant du problème. Un premier point est l'importance des rapports \(P(c|w)/P(c|w')\). Un second point est l'additivité car sur Analogy par exemple on compare des sommes. Un troisième point est la facilité de calcul d'où l'introduction de fonction exp ou log. Ils arrivent à une formulation de la forme : pour tout \(w\) et tout \(c\), trouver les matrices \(W\) et \(C\) et les vecteurs de biais tels que \(\log(\#(w,c)) \simeq \vec{w}.\vec{c} + b_w + b_c\) où \(\vec{w}\) est le vecteur représentant \(w\), \(\vec{c}\) est le vecteur représentant \(c\), \(b_w\) et \(b_c\) les composantes des vecteurs de biais correspondant à \(w\) et \(c\). Cette formulation correspond à une factorisation de la matrice PMI shiftée. De plus, plutôt que de factoriser (avec SVD ou autre) la méthode se propose d'apprendre la factorisation en formulant l'équivalence précédente comme une somme d'écarts quadratiques pondérée par la fréquence des paires \((w,c)\). Les expériences montrent que Glove est la meilleure méthode sur toutes les tâches. Constatation que personne n'a pu retrouver !

1.7 Une comparaison des méthodes par Levy et Goldberg

On peut lire avec profit le blog du développeur de Gensim pour une discussion sur la comparaison des méthodes. Je discute ici le papier de Omer Levy et Goldberg (Improving Distributional Similarity with Lessons Learned from Word Embeddings, TACL 2015) qui est une étude qui reprend de nombreux points des études précédentes (donc du présent document), compare les méthodes et montre que les méthodes sont relativement proches tant en terme de performances qu'en terme d'objectif (sauf CBOW) mais diffèrent par le choix des hyper-paramètres.

On définit un vocabulaire de mots et un vocabulaire de contextes. L'objectif est de représenter tout mot \(w\) (resp. contexte \(c\)) par un vecteur \(\vec{w}\) (resp. \(\vec{c}\)). Les vecteurs \(\vec{w}\) (resp. \(\vec{c}\)) sont les lignes d'une matrice W (resp. \(C\)) de dimension \(|V_w| \times d\) (resp. \(|V_c| \times d\)). Ils considèrent les méthodes suivantes :

  • PPMI, \(W_{PPMI}=M^{PPMI}\) constituée des valeurs de PPMI pour tout \((w,c)\). La matrice \(C_{PPMI}\) est la transposée de \(W_{PPMI}\). Partant des études sur les méthodes prédictives, on considère également deux variantes. La shifted PPMI (avec k=1, 5, 15) motivée par Glove et les vecteurs de biais. La smoothed PMI (avec \(\alpha=0.75\)) motivée par le tirage des exemples dans le négative sampling qui décroit la probabilité de tirer des mots du contexte éloignés du mot central.
  • SVD, avec construction d'une matrice à base de comptes \(M\) (PPMI, shifted PPMI ou smoothed PMI) et sa factorisation SVD \(M=U \Sigma V^t\) qui permet de définir les matrices \(W_{SVD}=U_d \Sigma_d\) et \(C_{SVD}=V_d\) pour une dimension \(d\) choisie. Mais ce choix justifié théoriquement est remis en question par la pratique dans la génération de représentations vectorielles comme montré dans Caron01. Pour cela, ils considèrent également les choix \(W_{SVD}=U_d \Sigma_d^p\) avec p=1 (classique), p=0.5 et p=0. Noter que p=0.25 avait été montré un bon choix dans Bullinariaetal12.
  • SGNS (Skip-Gram with Negative Sampling) est une des méthodes proposée par Mikolov. L'objectif est de produire des représentations vectorielles \(\vec{w}\) et \(\vec{c}\) de dimension \(d\) de tout mot \(w\) et de tout contexte \(c\). Le critère d'apprentissage est de maximiser une fonction du produit \(\vec{w}.\vec{c}\) pour les paires \((w,c)\) rencontrées dans le corpus et de minimiser cette même fonction pour des exemples négatifs. Le "negative sampling" consiste à produire les exemples négatifs en tirant, pour chaque paire \((w,c)\), des paires \((w,nc)\) en tirant les contextes \(nc\) selon leur probabilité d'apparition dans le corpus et une probabilité décroissante selon l'éloignement à \(w\). Il a été démontré par Goldberg et Levy que ceci revient à factoriser la matrice PMI shiftée d'une constante \(\log(k)\) avec un coût de factorisation qui n'est pas en norme \(L_2\) (coût pour la SVD) mais une fonction sigmoide pondérée moins sensible aux valeurs extrêmes.
  • Glove comme exposée ci-avant.

Pour étudier et comparer les algorithmes, on peut jouer sur les paramètres suivants :

  • win (tous) : la taille de la fenêtre : 2, 5, 10
  • dyn (tous) : pondérer l'importance des mots selon distance au centre
  • sub (tous) : sous échantillonner les mots fréquents (avant ou après)
  • del (tous) : supprimer les mots rares (avant)
  • neg (tous sauf Glove) : shifter la PMI : \(k=\) 1, 5, 15
  • cds (tous sauf Glove) : lisser la PMI
  • w+c (tous sauf PPMI) – postprocessing : ajouter \(\vec{w}\) avec \(\vec{c}\)
  • eig (SVD) : diminuer l'influence de \(\Sigma\) avec exposant \(p =\) 0, 0.5, 1
  • nrm (tous) : normalisation \(L_2\) des lignes pour utiliser Cosine

Le corpus est English Wikipedia (dump 2013), les mots de fréquence inférieure à 100 sont enlevés, ce qui donne un dictionnaire de 189,533 mots.Les jeux d'évaluation sont WordSim, Analogy (sans les questions avec des mots apparaissant moins de 100 fois dans Wikipedia). Glove et SGNS sont entraînés à partir de paires \((w,c)\) préalablement extraites (prog de Goldberg et Levy). Au total ils ont comparé 672 configurations. Les résultats principaux sont les suivants :

  • la normalisation \(L_2\) des lignes donne de bons résultats
  • dans un premier set d'expériences, ils comparent les méthodes avec divers paramétrages par défaut et recherche du meilleur paramétrage. Ils concluent qu'aucune méthode ne semble meilleure mais que c'est le bon choix des hyperparamètres pour la tache qui est essentiel. La recherche de ces paramètres faites sur un ensemble de train permet d'améliorer les performnaces et d'approcher l'optimal de la méthode.
  • Un deuxième set d'expériences étudie le passage à l'échelle et la question de savoir si il faut augmenter le jeu de données ou rechercher le meilleur paramétrage. La conclusion est que SGNS est le meilleur pour passer à l'échelle, que augmenter les données améliore souvent les résultats.
  • "Are predicting methods superior to count methods ? " Leur réponse est non (contrairement à Baronietal14). SVD l'emporte sur les taches de similarité. SGNS et Glove l'emportent relativement à PPMI sur Analogy mais de façon légère. Ils expliquent les différences par l'amélioration de PPMI apportée par le shift et de SVD apportée par la diminution de l'influence de \(\Sigma\).
  • "Is Glove superior to SGNS ? ". Leur réponse est non contrairement à ce qui est annoncé dans le papier sur Glove.
  • Le cas de CBOW. Cet algorithme ne peut être explicité comme une méthode de factorisation de matrice car un vecteur de contexte est représenté par la somme des vecteurs des mots constituant le contexte. CBOW est meilleure sur Analogy syntaxique mais pas sur les autres tâches. La piste de capturer les contextes joints doit être poursuivie selon les auteurs.
  • Ils tirent ensuite un certain nombre de "règles de bonne conduite dans le choix des paramètres"
    • Utiliser des petites fenêtres pour PPMI et SVD
    • Pour la SVD, il est conseillé de ne pas shifter la PPMI, il est essentiel de considérer la version "incorrecte" avec \(p=0\) ou \(p=0.5\) et pas la "correcte" avec p=1
    • Pour la PPMI, SVD et SGNS, utiliser la smoothed PMI avec \(\alpha=0.75\) comme matrice résultat (pour PPMI) ou initiale (pour SVD et SGNS)
    • Utiliser du negative sampling pour SGNS
    • SGNS est un bon baseline qui passe bien à l'échelle
    • Pour SGNS et Glove, penser à tester la variante w+c qui permet d'améliorer dans certains cas

1.8 Conclusion

Pour un ensemble de tâches d'école comme la similarité et l'analogie, la question du choix de la méthode reste entière. On dispose avec SGNS et CBOW de baseline avec de très bons résultats sur la plupart des tâches et la possibilité de passer à l'échelle. Cependant les méthodes à base de compte peuvent être très compétitives en terme de résultats mais pas en terme de passage à l'échelle. Il semble que l'étude des méthodes a fait progresser la compréhension des méthodes de représentation vectorielle mais que bien des progrès restent à réaliser sur la théorie. Cependant l'objectif étant "bien résoudre des tâches syntaxique et sémantique", on ne voit pas trop comment avancer dans ce sens. Rappelons que, pour la création de sens, d'autres méthodes comme la NMF sont privilégiées. Il semble qu'il reste de la place à d'autres approches. Pour résoudre une tâche spécifique ou un problème réel, le choix de la méthode reste posé.

Date: 2016-05-31T10:37+0200

Author: Rémi Gilleron

Org version 7.9.3f with Emacs version 24

Validate XHTML 1.0