Uno dei task più classici dell'NLP è il Part of Speech Tagging, ovvero l'analisi grammaticale di un testo con attribuzione ad ogni parola della relativa caratteristica lessicale (Nome, Verbo, Aggettivo, Pronome, etc...). 
Tale caratteristica lessicale dipende, oltre che dalla parola, dalla sua collocazione nel contesto della frase: un rilevante numero di parole può assumere una caratteristica diversa a seconda dell'utilizzo; ad esempio "la" può essere articolo, pronome, o nome.

L'approccio con il modello di Markov a stati nascosti è una soluzione classica che permette di ottenere risultati di accuratezza apprezzabili senza utilizzare word embedding.

Modello di Markov a Stati Nascosti (Hidden Markov Model)

Nel modello di Markov a Stati Nascosti andiamo a rappresentare attraverso un grafo orientato ai cui rami sono associate delle probabilità, poi tradotto poi in 2 matrici, la conoscenza desunta da un corpus di training testuale al quale sono già state associate le caratteristiche lessicali.

Stati

Gli Stati nel nostro problema corrispondono alle caratteristiche lessicali - nell'esempio a seguire per semplicità consideriamo solo "Nome", "Verbo", "Articolo".
Parliamo di stati nascosti perchè, quando analizziamo una frase, non conosciamo a priori la sequenza dei corrispondenti Stati - che anzi, è nostro obiettivo determinare nella configurazione più probabile per la frase in esame - ma stiamo osservando gli "Eventi", ovvero le parole della frase che costituiscono l'emissione degli stati corrispondenti.
Nel modello aggiungiamo anche uno stato \(\pi\)  che corrisponde al delimitatore della frase, quindi rappresentando sia l'inizio che la fine - è pertanto l'unico stato noto a priori.

Transizioni e Matrice di Transizione

Alle possibili Transizioni tra i vari stati vengono associate le probabilità calcolate sul corpus di training:  partendo da un qualsiasi stato \(S_i\) la parola successiva quindi sarà riconducibile ad un determinato stato \(S_j\)con una certa probabilità \(\displaystyle P(S_j | S_i) = \frac{C(S_i, S_j) + \varepsilon }{C(S_i) +\varepsilon \cdot N}\) , dove  \(C(S_i, S_j)\) è il conteggio nel corpus delle occorrenze della sequenza \(S_i\) \(S_j\) ,    \(C(S_i)\) è il conteggio nel corpus delle occorrenze di \(S_i\) ,  una piccola costante di smoothing \(\varepsilon \) evita che vi siano transizioni a probabilità nulla ed \(N\)  è il numero degli stati; 
Tutte le probabilità \(P(S_j | S_i)\) saranno collocate in una matrice \({\bf A}_{(N \times N)}\)  detta Matrice di transizione.

Emissioni, Dizionario e Matrice di Emissione

Alle possibili Emissioni dei vari stati, nel nostro caso le parole che possono essere manifestazione di un particolare Stato, vengono associale le rispettive probabilità calcolate sul corpus di training:  per un determinato stato \(S_i\)  e per ogni parola \(w_j\)nel dizionario ricavato dal corpus, avremo che \(\displaystyle P(w_j | S_i) = \frac{C(S_i, w_j) + \varepsilon }{C(S_i) +\varepsilon \cdot |V|}\), dove  \(C(S_i, w_j)\) è il conteggio nel corpus delle occorrenze della parola \(w_j\) quando compare con stato \(S_i\) ,    \(C(S_i)\) è il conteggio nel corpus delle occorrenze di \(S_i\) ,  una piccola costante di smoothing \(\varepsilon \) evita che vi siano emissioni a probabilità nulla e \(|V|\)  è il numero di parole nel nostro dizionario.

Il dizionario \(V\) , specie per corpus rilevanti, è costruito utilizzando non tutte le parole del corpus, ma solo quelle che presentano un frequenza maggiore di un certo valore \(k\) (tipicamente 1 o 2) , e aggiungendovi una parola speciale \(unk\)  a rappresentare una generica corrispondenza non presente nel vocabolario (eventualmente possono essere aggiunte delle parole specializzate \(unk\_nom\) , \(unk\_ver\) , etc. dove siano implementate regole o un'analisi euristica del suffisso per determinare la possibile appartenenza di una parola sconosciuta a uno specifico Stato).
In fase di training e applicazione del modello, quando viene incontrata una parola non presente nel dizionario viene considerata come \(unk\)  (oppure, applicando alla parola le opportune analisi euristiche per la possibile associazione a uno Dtato, verrà considerata come  \(unk\_Stato\) ).

Ciò permetterà di addestrare e utilizzare il modello con buoni risultati anche per parole non presenti nel set di training.
 
Tutte le probabilità \(P(S_j | S_i)\) saranno collocate in una matrice \({\bf B}_{(N \times |V|)}\)  detta Matrice di emissione.

Esempio di calcolo delle matrici di transizione ed emissione

Ipotizziamo uno scenario semplificato con un corpus di training composto da sole 3 frasi e con i 3 stati N (nome), V(verbo), A(articolo):

\(\underset{A}{\text{il}} \ \underset{N}{\text{gatto}} \ \underset{V}{\text{cerca}} \ \underset{A}{\text{la}} \ \underset{N}{\text{mamma}} \\ \underset{N}{\text{Mario}} \ \underset{V}{\text{suona}} \ \underset{A}{\text{un}} \ \underset{N}{\text{la}} \\ \underset{A}{\text{la}} \ \underset{N}{\text{mamma}} \ \underset{V}{\text{guarda}} \ \underset{A}{\text{il}} \ \underset{N}{\text{gatto}} \\\)   

e procediamo al conteggio delle transizioni e degli stati

\(\begin{array} {r|r|r|r|r|r} \color{red}{C(S_i,S_j)} & \pi & A & N & V & \color{red}{C(S_i)}\\ \hline \pi & 0 & 2 & 1 & 0 & \color{red}{3}\\ \hline A & 0 & 0 & 5 & 0 & \color{red}{5}\\ \hline N & 3 & 0 & 0 & 3 & \color{red}{6}\\ \hline V & 0 & 3 & 0 & 0 & \color{red}{3}\\ \hline \end{array}\)     

e al conteggio delle emissioni, ipotizzando di adottare un dizionario con tutte le parole del corpus.

\(\begin{array} {r|c|c|c|c|c|c|c|c|c|c|c|} \color{red}{C(S_i,w_j)} & \text{il} & \text{gatto} & \text{cerca} & \text{la} & \text{mamma} & \text{Mario} & \text{suona} & \text{un} & \text{guarda} & -unk- & -del- \\ \hline \pi & 0 & 0 & 0 & 0 & 0 &0 &0 &0&0&0 &4 \\ \hline A & 2 & 0 & 0 & 2 & 0 &0 &0 &1&0&0 &0\\ \hline N & 0 &2 &0&1&2&1&0&0&0&0&0 \\ \hline V & 0 & 0 & 1 & 0&0&0&1&0&1&0&0 \\ \hline \end{array}\)

Procediamo ora al calcolo della matrice di transizione A, utilizzando un coefficiente di smoothing \(\varepsilon=0,01\)  (che non applichiamo alla transizione \(P(\pi|\pi)\) considerata di fatto impossibile, corrispondendo ad una frase nulla)

\(\begin{array} {r|r|r|r|r|} \color{red}{P(S_j|S_i)} & \pi & A & N & V \\ \hline \pi & 0 & 0,663 & 0,333 & 0,003 \\ \hline A & 0,002 & 0,002 & 0,994 & 0,002 \\ \hline N & 0,498 & 0,002 & 0,002 & 0,498 \\ \hline V & 0,003 & 0,990 & 0,003 & 0,003 \\ \hline \end{array}\)

e al calcolo della matrice di emissione B, utilizzando un coefficiente di smoothing \(\varepsilon=0,01\)   (per lo stato \(\pi\) le emissioni sono sempre certe e verso il delimitatore \(-del-\), senza necessità di considerare nello smoothing la ripettiva riga e la rispettiva colonna)

\(\begin{array} {r|c|c|c|c|c|c|c|c|c|c|c|} \color{red}{P(w_j|S_i)} & \text{il} & \text{gatto} & \text{cerca} & \text{la} & \text{mamma} & \text{Mario} & \text{suona} & \text{un} & \text{guarda} & -unk- & -del- \\ \hline \pi & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &0&1 \\ \hline A & 0,394 & 0,002 & 0,002 & 0,394 & 0,002 &0,002 &0,002 &0,198&0,002&0,002&0 \\ \hline N & 0,002 &0,330 &0,002&0,166&0,330&0,166&0,002&0,002&0,002&0,002&0 \\ \hline V & 0,003 & 0,003 & 0,326 & 0,003&0,003&0,003&0,326&0,003&0,326&0,003&0 \\ \hline \end{array}\)

Rileviamo facilmente che il prodotto delle matrici \(\bf AB\) conterrà le probabilità \(P(w^{(t+1)}_j|S^{(t)}_i)\) che la parola successiva allo stato \(S^{(t)}_i\) sia \(w^{(t+1)}_j\)

Algoritmo di Viterbi

Data una frase arbitraria da analizzare, dobbiamo trovare la sequenza di stati da associare ad ogni parola, tale da massimizzare la probabilità risultante della frase, calcolata sulla base delle matrici di transizione ed emissione.

Ci viene in aiuto in ciò l'algoritmo di Viterbi , che con un approccio di programmazione dinamica, permette di analizzare i percorsi tra stati sul grafo a partire dallo stato iniziale attraversando gli stati successivi individuando il miglior percorso in relazione alle emissioni date (le \(k\) parole della frase \(\bf w\)).

L'algoritmo prevede la costruzione iterativa per colonne di due matrici  \({\bf C}_{(N \times k)}\)  , contenente le probabilità dei migliori percorsi attraversati, e \({\bf D}_{(N \times k)}\) con la traccia degli stati attraversati.

La prima colonna della matrice \({\bf C}_{(N \times k)}\) viene inizializzata ponendo \(c_{i,1}=a_{1,i} \cdot b_{i,indice(w_1)}\)  , ovvero le probabilità di emettere la prima parola \(w_1\) attraverso la transizione dallo stato iniziale verso un primo stato \(S_i\).

La prima colonna della La prima colonna della matrice \({\bf D}_{(N \times k)}\) viene inizializzata ponendo \(d_{i,1}=0\)  in quanto non abbiamo ancora parti precedenti del percorso da tracciare.

Le successive  colonne della matrice \({\bf C}_{(N \times k)}\) vengono iterativamente calcolate come \(c_{i,j}=\underset{k}{\max} c_{k,j-1} \cdot a_{k,i}\cdot b_{i,indice(w_j)}\)   , scegliendo in pratica di raggiungere lo stato \(S_i\) dallo stato precedente \(S_k\) che massimizza la probabilità del percorso parziale.
Di conseguenza nella matrice \({\bf D}_{(N \times k)}\) andremo ad inserire proprio tale \(k \) calcolato come \(d_{i,j}=\underset{k}{\arg \max} \ c_{k,j-1} \cdot a_{k,i}\cdot b_{i,indice(w_j)}\)

Una volta calcolate le due matrici, avremo che il massimo valore presente nella colonna \(k\)  della matrice \(\bf C\)  rappresenta la probabilità della sequenza di stati più probabile.  In particolare il suo indice  \(s_k=\underset{i}{\arg \max} \ c_{i,k} \)  ci indicherà lo stato della sequenza più probabile associato all'ultima parola \(w_k\) .

Per trovare gli Stati associati alle parole precedenti, itereremo nella matrice \(\bf D\) popolata con gli indici delgli stati di provenienza dei vari percorsi, ponendo \(s_{j-1}=d_{s_{j},j}\)   ,  ottenendo infine l'intera sequenza desiderata degli stati   \(S_{s_1}S_{s_2}\cdots S_{s_k} \)

Esempio di analisi di una frase con algoritmo di Viterbi

Supponiamo, a partire dalle matrici di transizione ed emissione già calcolate, di voler analizzare la frase  Il gatto mangia un topo

Rileviamo subito che abbiamo 2 parole sconosciute per il nostro dizionario che quindi sostituiremo con -unk- al fine dell'analisi.

Inizializziamo le matrici secondo le formule indicate, partendo dallo stato di inizio frase:

\(\begin{array} {r|c|c|c|c|c|} \color{red}{\bf C} & \text{un} & \text{gatto} & \text{mangia} & \text{il} & \text{topo} \\ \hline A & 1,313 \cdot 10^{-1} & & & & \\ \hline N & 6,660 \cdot 10^{-4} & & & & \\ \hline V & 9,000 \cdot 10^{-6}& & & & \\ \hline \end{array}\)   \(\begin{array} {r|c|c|c|c|c|} \color{red}{\bf D} & \text{un} & \text{gatto} & \text{mangia} & \text{il} & \text{topo} \\ \hline A & 0 & & & & \\ \hline N & 0 & & & & \\ \hline V & 0 & & & & \\ \hline \end{array}\)
 

e proseguiamo iterativamente a riempire le successive colonne secondo le formule sopra indicate:

\(\begin{array} {r|c|c|c|c|c|} \color{red}{\bf C} & \text{un} & \text{gatto} & \text{mangia} & \text{il} & \text{topo} \\ \hline A & 1,313 \cdot 10^{-1} & 5,251 \cdot 10^{-7} & 1,722 \cdot 10^{-7} & 1,261 \cdot 10^{-5} & 5,044 \cdot 10^{-11} \\ \hline N & 6,660 \cdot 10^{-4} & 4,306 \cdot 10^{-2} & 1,722 \cdot 10^{-7} & 3,860 \cdot 10^{-10} & \color{red}{2,507 \cdot 10^{-8}} \\ \hline V & 9,000 \cdot 10^{-6} & 9,950 \cdot 10^{-7} & 6,433 \cdot 10^{-5} & 5,790 \cdot 10^{-10} & 7,566 \cdot 10^{-11} \\ \hline \end{array}\)       \(\begin{array} {r|c|c|c|c|c|} \color{red}{\bf D} & \text{un} & \text{gatto} & \text{mangia} & \text{il} & \text{topo} \\ \hline A & 0 & 1 & 2& 3& 1\\ \hline N & 0 & 1 & 2& 3& \color{red}{1}\\ \hline V & 0 & 2 & 2&3 &1 \\ \hline \end{array}\)  

e ripercorrendo a ritroso, colonna per colonna, gli indici degli stati nella tabella D a partire dall'indice indicato in rosso, otteniamo 

\(s_5=2 \rightarrow S_{\text{topo}}=N \\ s_4=1 \rightarrow S_{\text{il}}=A \\ s_3=3 \rightarrow S_{\text{mangia}}=V \\ s_2=2 \rightarrow S_{\text{gatto}}=N \\ s_1=1 \rightarrow S_{\text{un}}=A \\\)

che costituisce la sequenza di stati attribuiti alle frase con massima la probabilità secondo il modello di Markov presentato - ed è effettivamente la corretta analisi grammaticale della frase, nonostante presenza di due parole estranee al dizionario.

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 105~10elementi.

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.