Con il paper GloVe - Global Vectors for Word Representation (C.D.Manning, R.Socher, J.Pennington. 2014) viene presentato un modello di word embedding con i benefici sia dei metodi Latent Semantic Analysis basati su matrici statistiche globali di co-occorrenza, particolarmente efficaci nel cogliere la similarità tra parole, sia dei modelli iterativi in ottica deep-learning come Word2Vec (CBoW/Skip-Gram) basati sulla capacità di predizione della parola/contesto, efficaci nel cogliere analogie e strutture complesse.

Rapporto tra probabilità, Modello bilineare logaritmico e funzione obiettivo di GloVe

Dato un corpus testuale, dalla definizione di matrice di co-occorrenza \(X\) , l'elemento \(X_{ij}\) rappresenta il numero di volte che la parola \(j\) appare nel contesto della parola \(i\).
Di conseguenza \(\displaystyle X_i=\sum_{k \in corpus} X_{ik} \)  rappresenta il numero di volte che una qualsiasi parola appare nel contesto di \(i\).
\(\displaystyle P_{ij}=(w_j|w_i)= \frac{X_{ij}}{X_i} \) è quindi la probabilità che la parola \(j\) appaia nel contesto di \(i\).

Gli autori del paper hanno osservato, come dall'esempio a seguire, che il rapporto tra probabilità di co-occorrenza può essere utilizzato proficuamente per rilevare componenti e "direttrici" di significato rilevanti:

\(\displaystyle \begin{array}{|c|c|c|c|c|} \hline & x=\text{solido} & x=\text{gas} & x=\text{acqua} & x=\text{moda} \\ \hline P(x|\text{ghiaccio}) & \color{red}{1.9 \times 10^{-4}} & \color{blue}{6.6 \times 10^{-5}} & \color{red}{3.0 \times 10^{-3}} & \color{blue}{1.7 \times 10^{-5}} \\ \hline P(x|\text{vapore}) & \color{blue}{2.2 \times 10^{-5}} & \color{red}{7.8 \times 10^{-4}} & \color{red}{2.2 \times 10^{-3}} & \color{blue}{1.8 \times 10^{-5}} \\ \hline \frac{P(x|\text{ghiaccio})}{P(x|\text{vapore})} & \color{red}{\mathbf {8.9}} & \color{blue}{\mathbf {8.5 \times 10^{-2}}} & \color{grey}{\mathbf {1.36}} & \color{grey}{\mathbf {0.96}} \\ \hline \end{array}\)

In questo esempio si rileva che "acqua" e "moda" sono due parole non discriminative in questo contesto rispetto alle parole "ghiaccio" e "vapore", avendo un rapporto tra probabilità di co-occorrenza vicino ad 1.
Invece la parola "solido", con un rapporto molto maggiore di 1, è correlabile con proprietà specifiche di "ghiaccio", mentre la parola "gas" con un rapporto molto minore di 1, è correlabile con proprietà specifiche di "vapore".
Da questo tipo di considerazione, nasce l'esigenza di strutturare un modello di embedding in grado di cogliere il significato contenuto nel rapporto di probabilità.
La soluzione individuata è quella di scegliere un modello bilineare-logaritmico tale che \(w_i \cdot \tilde w_j=\log P(i|j)\)

A questo punto si verifica che il rapporto di probabilità è riportato a una differenza di vettori  \(\displaystyle w_x \cdot (\tilde w_a - \tilde w_b)=\log \frac{P(x|a)}{P(x|b)}\) che ben riflette il significato ricercato - intuitivamente, ad esempio nel caso di "moda" o "acqua", avremo degli embedding pressochè ortogonali alla direttrice degli embedding "ghiaccio"-"vapore", e quindi a prodotto scalare tendenzialmente nullo (che corrisponde ad un rapporto di probabilità unitario).

A partire da questa relazione cerchiamo di capire la struttura di una funzione di costo che ci consenta di ottimizzare i vettori. 
Partendo da  \(w_i^\top \tilde w_j=\log P(i|j)=\log \frac{X_{ij}}{X_i}=\log X_{ij} - \log X_i \)     otteniamo che

\(w_i^\top \tilde w_j + \log X_i =\log X_{ij} \)  e considerando che \(X_i \) non dipende dalla parola j può essere ricompreso in uno scalare di bias \(b_i\) da apprendere. Aggiungeremo inoltre, per salvaguardare la simmetria, un ulteriore scalare di bias \(\tilde b_j\) da apprendere relativo a \(\tilde w_j\).

Otterremo quindi una relazione  \(w_i^\top \tilde w_j + b_i + \tilde b_j=\log X_{ij} \)  che cercheremo di ottimizzare complessivamente per ogni i,j .
In via generale dovremmo tenere conto del caso in cui l'occorrenza \(X_{ij}\) sia nulla - evenienza molto frequente, considerando la sparsità della matrice di co-occorrenza - considerando eventualmente \(X_{ij} + 1\)
Il problema è comunque superato proprio dalla scelta della funzione obiettivo di GloVe, per la quale si utilizza il metodo dei minimi quadrati e moderata da una funzione di ponderazione \(f(X_{ij})\) nulla per \(X_{ij}=0\), 

\(\displaystyle \bbox[5px,border:2px solid red] {J=\sum_{i,j=1}^V f(X_{ij})( w_i^\top \tilde w_j + b_i + \tilde b_j - \log X_{ij} )^2} \)

Nel dettaglio la \(f(X_{ij})\) sarà scelta monotona crescente con \(f(0)=0\) e relativamente contenuta per valori elevati dell'argomento , in modo da non dare eccessivo peso a co-occorrenze particolarmente frequenti.
Nel paper originale è stata utilizzata con buoni risultati la funzione
\(f(x)=\begin{cases} (x/x_\text{max})^\alpha & \text{se} \ \ x<x_\text{max} \\ 1 & \text{altrimenti} \end{cases}\)   con un \(\alpha=3/4\) e un un cutoff \(x_\text{max}=100\)  per non attribuire eccessivo peso a occorrenze comuni

 

Da Word2Vec a GloVe: denormalizzazione della funzione di costo e minimi quadrati

Vediamo come un risultato analogo può essere riscontrato partendo invece dal modello Word2Vec e introducendo la matrice di co-occorrenza per integrare e modificare le relazioni e la funzione di costo.
Riprendendo le considerazioni sugli word embedding del modello Word2Vec / Skipgram, la probabilità che una parola \(j \) compaia nel contesto della parola \(i\) viene definita come \(Q_{ij}=\frac{e^{u_j^T v_i}}{\sum_{w=1}^W e^{u_w^T v_i}}\)

In questo caso la funzione di costo globale in accordo alla cross entropy è \(\displaystyle J=-\sum_{i \in corpus}\sum_{j \in context(i)} \log Q_{ij}\)  

Utilizzando convenientemente la matrice di co-occorrenza otteniamo \(J=- \sum_{i=1}^W \sum_{j=1}^W X_{ij} \log Q_{ij}\)

che può essere espresso come \(J=- \sum_{i=1}^W X_i \sum_{j=1}^W P_{ij} \log Q_{ij}=- \sum_{i=1}^W X_i H(P_i,Q_j)\)  ovvero una sommatoria pesata della cross entropy tra le distribuzioni di probabilità degli word embedding e quella della matrice di co-occorrenza.

Uno dei problemi operativi legati all'utilizzo della cross entropy è il fatto che ogni distribuzione Q deve essere normalizzata sull'intero dizionario. L'approccio di GloVe è quello di utilizzare invece una funzione di costo basata invece sul modello dei minimi quadrati, senza la normalizzazione delle distribuzioni P e Q. Abbiamo quindi:

\(\displaystyle \hat{J}=\sum_{i=1}^W \sum_{j=1}^W X_i(\hat{P}_{ij}-\hat{Q}_{ij})^2\)  dove \(\hat P_{ij}=\hat X_{ij} \ \ , \ \ \hat Q_{ij}=e^{u_j^\top v_i}\)  sono valori non normalizzati.  Per ridurre il rischio di valori esponenzialmente alti nella funzione di costo, si preferisce ottimizzare il quadrato della differenza dei logaritmi, ovvero:

\(\displaystyle \hat{J}=\sum_{i=1}^W \sum_{j=1}^W X_i(\log\hat{P}_{ij}-\log \hat{Q}_{ij})^2=\sum_{i=1}^W \sum_{j=1}^W X_i(u_j^\top v_i -\log X_{ij})^2\)

Infine, come già visto sopra, è dimostrato che si ottengono migliori risultati utilizzano un fattore di peso più articolato che il semplice \(X_i\) , utilizzando una funzione \(f(X_{ij})\) che tiene in considerazione anche la parola di contesto, e aggiungendo un parametro di bias \(b_i \) per la parola centrale ed uno \(\tilde b_j \) per la parola di contesto. Nella sua forma finale la funzione di costo, riprendendo sia i termini di bias che la funzione di ponderazione, è proprio nella forma già vista

\(\displaystyle \hat{J}=\sum_{i=1}^W \sum_{j=1}^W f(X_{ij})(u_j^\top v_i + b_i + \tilde b_j -\log X_{ij})^2\)
 

Considerazioni finali: efficienza nel training e risultati

I benefici del modello GloVe si ritrovano, oltre che nelle performance generalmente superiori nei task usuali (similitudini, analogie, NER) riportate nel paper ufficiale, in un training più efficiente dei parametri del modello legato ad una funzione obiettivo più agevole da ottimizzare.
La funzione è difatti condizionata da una matrice di co-occorrenza ad alta sparsità, con una computazione più snella e mirata rispetto a Word2Vec nel quale l'utilizzo di softmax prevedeva un esubero computazionale per la normalizzazione - tale da necessitare nella pratica di varianti quali il Negative Sampling per efficientare il calcolo.
 

__________________________________________

Riferimenti

http://nlp.stanford.edu/pubs/glove.pdf 

http://web.stanford.edu/class/cs224n/readings/cs224n-2019-notes02-wordvecs2.pdf