Word Embedding e operazioni sullo Spazio Vettoriale

Abbiamo visto come attraverso modelli di Latent Semantic Analysis , iterativi/deep learning (Word2Vec) o ibridi (GloVe), possiamo ricavare una rappresentazione delle parole presenti in un corpus mediante word embedding, ovvero vettori \({\bf x} \in \Bbb R^n \)  le cui componenti sono intrinsecamente portatrici di specifici significati.
Ciò ci permette di operare sugli embedding con gli strumenti propri dell'algebra vettoriale per ottenere risultati semanticamente rilevanti in ambito di analogie, similitudini e in tutti quegli ambiti dove sia utile sfruttare le relazioni tra le parole in termini di significato.

Vediamo nell'esempio che per semplicità utilizza degli embedding in 2 dimensioni, come possiamo utilizzare le relazioni tra rappresentazioni di parole note per estrarre componenti di significato ed individuare altre parole correlate.

\(\bf regalità=x_{re}-x_{uomo}\)   individua una componente che rappresenta il concetto di regalità. 
Applicando questa componente alla rappresentazione nota di "donna"  otterremo un nuovo embedding che ci attendiamo essere molto vicino a quello di "regina"
\(\bf x_{regina} \approx x_{donna} + regalità\)     

Procedendo analogamente possiamo estrarre la componente di genere \(\bf genere=x_{donna}-x_{uomo}\)   ed applicarla alla rappresentazione di "re" per ottenere un embedding che ci attendiamo essere (il più) vicino a quello di  \(\bf x_{regina} \approx x_{re} + genere\)

Operando linearmente sullo spazio vettoriale degli embedding è ad esempio possibile strutturare semplici sistemi di Q&A sfruttando  analogie e similitudini.
Un esempio classico è l'individuazione delle capitali, partendo dalle rappresentazioni note di una nazione e della relativa capitale: 
\(\bf capitale=x_{Roma}-x_{Italia}\)   rappresenterà la componente "capitale" che applicata ad una qualsiasi nazione potrà approssimare al meglio la della relativa capitale.
Quindi se calcoliamo \(\bf y = x_{Francia} + capitale \)   e ricerchiamo tra gli embedding del nostro dizionario \(V \) quello con distanza minore da \(\bf y\) , otterremo auspicabilmente \(\bf x_{Parigi}\)   
E' importante rimarcare che non andremo ad operare in termini esatti, in quanto la determinazione stessa degli embedding è un processo di modellizzazione che tende verso la migliore rappresentazione in relazione al metodo adottato, alla dimensione degli embedding e alle caratteristiche qualitative/quantitative del corpus di training.

Traduzione come Trasformazione lineare tra Spazi Vettoriali

Immaginiamo di avere due differenti insiemi di word embedding, uno per la lingua A dove ogni parola nel corpus è rappresentata da un vettore   \({\bf x} \in \Bbb R^n\) ,  e uno per la lingua B dove ogni parola nel corpus è rappresentata da un vettore \({\bf y} \in \Bbb R^m\) .

Visto che gli word embedding sono una rappresentazione semantica delle parole, risulta corretto attenderci che le relazioni lineari già viste tra parole che rappresentano lo stesso significato nelle due lingue rimangano valide in entrambi gli spazi. Riprendendo l'esempio e considerando per comodità di visualizzazione \(n=m=2\) 

Vediamo che, a prescindere dalle componenti dei singoli vettori, nelle 2 lingue continueranno a valere le relazioni tra i termini corrispondenti e quindi:

\(\bf x_{regina} \approx x_{re}-x_{uomo}+x_{donna} \\ y_{queen} \approx y_{king}-y_{man}+y_{woman} \)

Pertanto, tale linearità deve preservarsi nell'operazione di traduzione, che consisterà nell'associare ad un vettore \({\bf x} \in \Bbb R^n\) nella lingua A un vettore \({\bf \hat y} \in \Bbb R^m\) il più possibile vicino alla esatta traduzione \({\bf y} \in \Bbb R^m\) .  
E' immediato verificare, considerando i vettori riga per comodità, che tale operazione è soddisfatta da una trasformazione lineare attraverso la moltiplicazione per una opportuna matrice \({\bf R}_{(n \times m)}\)   .
Ipotizzando di avere già individuato una matrice \(\bf R\) ottimale tale che \(\bf x_{re}R \approx y_{king} \ , \ x_{uomo}R \approx y_{man} \ , \ x_{donna}R \approx y_{woman}\)  , otteniamo dalle relazioni cui sopra:

\(\bf x_{regina}R \approx (x_{re}-x_{uomo}+x_{donna})R \\ x_{regina}R \approx x_{re}R-x_{uomo}R+x_{donna}R \\ x_{regina}R \approx y_{king}-y_{man}+y_{woman}\)       

pertanto dalle relazioni di partenza  \(\bf y_{queen} \approx x_{regina} R\)   , ovvero siamo in grado di individuare l'embedding \({\bf y} \in \Bbb R^m\)  che rappresenta la migliore corrispondenza nella lingua di destinazione dell'embedding \({\bf x} \in \Bbb R^n\) nella lingua di partenza, il tutto attraverso una matrice \({\bf R}_{(n \times m)}\)  costruita in modo da meglio approssimare la trasformazione tra un certo numero di embedding noti nelle due lingue.

Calcolo della matrice R

Per calcolare la matrice R è necessario disporre di \(k\) parole nella lingua A di cui sia nota la traduzione nella lingua B, ovviamente con i relativi embedding  \(\bf x_1 \cdots x_k \) e  i corrispondenti \(\bf y_1 \cdots y_k \)
La matrice \({\bf R}_{(n \times m)}\) dovrà essere calcolata in modo da minimizzare complessivamente l'errore tra i vari  \(\bf x_i R\) e \(\bf y_i\) .  Disponendo i vettori in 2 matrici:

\({\bf X} = \begin{bmatrix} - {\bf x}_1- \\ \vdots \\ - {\bf x}_k- \end{bmatrix}_{(k\times n)} \ \ , \ \ {\bf Y} = \begin{bmatrix} - {\bf y}_1- \\ \vdots \\ - {\bf y}_k- \end{bmatrix}_{(k\times m)} \)     e pertanto possiamo definire il problema come \(\bf XR\approx Y\)

Una delle metriche più utilizzate per il calcolo di distanze tra matrici è la norma di Frobenius \(|| {\bf A} ||_F=\sqrt{\sum_i \sum_j a_{ij}^2}\)  che ci permette di impostare il problema come

\(\arg \underset{\bf R}{\min}{||{\bf XR-Y}||}_F^2 \)   , ovvero come ricerca del minimo della funzione di costo rispetto all'incognita \(\bf R\) 

Il metodo storicamente più utilizzato per la risoluzione numerica di problemi di minimo è l'algoritmo della discesa del gradiente : dopo aver inizializzato la matrice \(\bf R\) a \(\bf 0\) o con valori casuali, si procede ad applicare le regole del calcolo differenziale matriciale e calcolare il gradiente rispetto alla matrice R come  \({\bf dR} = 2 \bf X^\top(XR-Y) \)    

A questo punto si procederà ad aggiornare la nostra matrice \(\bf R=R- \alpha \ dR\)  utilizzando un opportuno coefficiente di apprendimento \(\alpha\) .
Ripeteremo iterativamente il calcolo del gradiente e l'aggiornamento della matrice, sino a quando il valore della funzione di costo si assesterà attorno a quello che identificheremo come un minimo.

In alternativa alla risoluzione per via numerica è ovviamente possibile anche la risoluzione analitica del problema di minimo ponendo il gradiente \(\bf X^\top(XR-Y) =0\)  , da cui   \(\bf X^\top XR = X^\top Y\)  e infine \(\bf R = (X^\top X)^{-1}X^\top Y\)
Sebbene il calcolo di una matrice inversa di dimensione \(n \times n\) possa rilevarsi rilevante al crescere di \(n\) , per le attuali capacità computazionali e le dimensioni degli embedding correntemente utilizzate inferiori a 1000 componenti, si ritiene generalmente preferibile procedere direttamente con questa soluzione esatta.

A questo punto avremo individuato la nostra migliore matrice di traduzione \(\bf R\) che potremo utilizzare per ottenere un vettore  \(\bf \hat y=Rx\) a partire dall'embedding \(\bf x \) di una qualunque parola nella lingua A,  e successivamente individuare l'embedding più vicino \(\bf y \approx \hat y\) nella lingua B corrispondente alla traduzione più probabile della parola.

Distanza e hashing degli embedding

L'individuazione nel nostro dizionario dell'embedding più vicino al vettore \({\bf \hat y}\in \Bbb R^m\)  può essere computazionalmente onerosa, a seconda della dimensione \(|V|\) del dizionario stesso, potenzialmente nell'ordine dei 10⁵~10⁶ elementi.

La metrica generalmente più efficace in queste applicazioni non è quella della distanza euclidea ma il coseno di similarità:
\(\displaystyle d({\bf v},{\bf w})=\cos(\widehat{\bf v w})=\frac{{\bf v}\cdot{\bf w}}{||{\bf v}|| \ ||{\bf w}||}\)    , che quindi attribuisce rilevanza alla direzione e verso degli embedding e non al modulo, meno significativo ai fini del contributo semantico, specie in spazi ad alta dimensionalità come quelli degli embedding.

Una tecnica utilizzata frequentemente per ottimizzare i tempi di ricerca è quella dell'hashing degli embedding, che nel caso della distanza vista può essere realizzata dividendo lo spazio \(\Bbb R^m\) in \(2^p\)  parti attraverso \(p\) iperpiani orientati di dimensione \(m-1\) passanti per l'origine, identificati dai loro vettori normali \({\bf n}_i \in \Bbb R^m\) .
La generazione dei vettori normali può essere casuale, pseudocasuale o seguire algoritmi precisi in relazione alla conoscenza dell'insieme degli embedding - possiamo assumere una generazione casuale senza perdere di generalità. 

L'attribuzione di un vettore \(\bf v\) alla una delle parti dello spazio separate da un iperpiano con normale \(\bf n\) può essere codificata come 0 od 1  ponendo  \(h_i=\min (0,\text{sign}({\bf v} \cdot {\bf n}_i))\) .

E' quindi possibile generare un hash \(h=\sum_{i=1}^{p} h_i \ 2^{i-1}\)  che identifichi univocamente la zona di appartenza del vettore nello spazio partizionato dagli iperpiani.

Pertanto, per trovare l'embedding più vicino ad un dato vettore, sarà opportuno misurarne la distanza dagli embedding che hanno stesso hash, senza confrontarlo con l'intero insieme degli embedding.

Tuttavia si evidenzia che questo non è un metodo esatto, non assicurando che l'embedding più vicino a \(\bf v\) nel relativo bucket sia l'embedding più vicino in assoluto: il vettore \(\bf v \) potrebbe ad esempio trovarsi vicino alla frontiera delimitata da un iperpiano oltre il quale si trova un embedding ancora più vicino.
Per ovviare a questo si procede solitamente a generare \(k\) insiemi distinti di \(p\) iperpiani, e quindi \(k\) hash per ogni embedding. 
Si andrà quindi a confrontare la distanza tra il vettore e tutti gli embedding nei \(k\) bucket,  aumentando sensibilmente la probabilità di individuare l'embedding più vicino in assoluto. 

Limiti e osservazioni

L'osservazione preliminare è che il metodo esposto opera in uno scenario ideale e circoscritto di una traduzione parola per parola, nel quale si cerca di associare una parola della lingua B ad una parola nella lingua A, alla stregua di un dizionario.
Sebbene sia possibile con alcuni accorgimenti utilizzare anche embedding composti da più parole per rappresentare contesti più articolati, l'utilizzo di questo approccio per la traduzione di intere frasi risulta scarsamente efficiente.
E' inoltre di limitata efficacia per la traduzione di parole che presentano molteplici significati a seconda del contesto, o tra lingue con costruzioni concettuali/semantiche estremamente diverse tra loro. Pertanto la facilità di training del sistema va valutata alla luce dello specifico obiettivo che si vuole ottenere e dell'accuratezza reputata accettabile.

E' bene ricordare che è sempre rilevante, in ogni applicazione che faccia uso di più embedding per traduzioni e mappature, utilizzare per quanto possibile degli embedding addestrati con un metodo uniforme e ricavati da corpus omogenei per estensione, tematiche, contesti (es: pagine di wikipedia , news, etc.) , in modo da avere una ragionevole confidenza nel fatto che siano rappresentati quantitativamente e qualitativamente embedding riconducibili allo stesso universo. 

E' infine opportuno fornire al modello quanti più embedding di corrispondenze note per costruire le matrici \(\bf X\) e \(\bf Y\), in modo da imporre più punti di riferimento ed ottenere una matrice \(\bf R\) efficace in grado di trasporre al meglio tutte le varie componenti di significato,  considerando anche le consuete dimensioni \(m,n >200\) dei vettori in gioco.