Uno dei primi approcci alla rappresentazione di significato delle parole nel NLP, con molti limiti e di fatto oggi poco utilizzato, è quello dell'utilizzo della matrice di co-occorrenza tra le parole del corpus, basata su una finestra di  \(\pm m\) parole adiacenti.

Questa matrice simmetrica in sostanza conta quante volte una determinata parola appare nella finestra di un'altra all'interno del corpus. Il concetto alla base di questa costruzione è che parole con significati simili dovrebbero avere un utilzzo simile all'interno del corpus, con una similitudine riflessa nella corrispondente riga/colonna della matrice.

Ipotizziamo un corpus  costituito da 3 frasi semplici con una finestra di \(\pm 1 \) parole, senza tenere conto della punteggiatura, ed inseriamo nel conteggio anche i marker <INIZIO> e <FINE> delle frasi.

<INIZIO> Io ho caldo <FINE>
<INIZIO> Io sono stanco <FINE>
<INIZIO> Io amo studiare <FINE>

Iterando su tutte le parole del corpus otteniamo una matrice di co-occorrenza conteggiando le parole che compaiono nella rispettiva finestra:

\(X=\begin{array}{c|cc} & \text{<INIZIO>} & \text{Io} & \text{ho} & \text{sono} & \text{amo} & \text{caldo} & \text{stanco} & \text{studiare} & \text{<FINE>} \\ \hline \text{<INIZIO>} & 0 & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \text{Io} & 3 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \text{ho} & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \text{sono} & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \text{amo} & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \text{caldo} & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ \text{stanco} & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ \text{studiare} & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ \text{<FINE>} & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\ \end{array}\)

Comprendiamo subito che la gestione di una matrice di questo tipo, su un corpus reale che si appoggia su un dizionario di almeno 50k-100k parole diventa estremamente grande e difficilmente gestibile. Inoltre siamo di fronte a una matrice estremamente sparsa, visto che relativamente "poche" parole compariranno nella finestra di una determinata parola, lasciandoci con una matrice composta in gran parte da zeri.

Riduzione della dimensionalità con SVD

Al fine di rendere concretamente utilizzabile questo modello, è quindi necessario ridurre la dimensionalità dei nostri vettori associati ad ogni parola, cercando di perdere la minore quantità possibile di informazione.

Utilizziamo a questo fine la decomposizione ai valori singolari (SVD) che ci permette nella sua forma ridotta di decomporre una matrice nella forma  \(\bf A=UDV^\top \)   , dove 

\({\bf A} \in\Bbb R^{n \times d}\) è la nostra matrice di partenza di rango \(r\) ,  

\({\bf D} \in\Bbb R^{r \times r}\) è una matrice diagonale, sulla quale sono collocati i valori singolari di A, disposti sulla diagonale in ordine decrescente  \(\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r \)

\({\bf U} \in\Bbb R^{n \times r}\) è una matrice ortogonale (\(\bf UU^\top=I\)),  le cui colonne formano una base ortornormale per lo spazio generato dalle colonne di \({\bf A}\)

\({\bf V} \in\Bbb R^{d \times r}\) è una matrice ortogonale (\(\bf VV^\top=I\)),  le cui colonne formano una base ortornormale per lo spazio generato dalle righe di \({\bf A}\)

A questo punto è possibile scegliere una nuova dimensione ridotta \(k<r\) per i nostri vettori e considerare la sottomatrice \({\bf U}_{1:n,1:k}\) di dimensione \(n \times k\) come nostro nuovo word embedding - troncando quindi a \(k\) le dimensioni \(r\) nelle varie matrici della scomposizione.

In questo modo è dimostrabileche il nuovo embedding cattura comunque una parte \(\frac{\sum_{i=1}^k \sigma_i}{\sum_{i=1}^r \sigma_i}\) rilevante della varianza dell'embedding originale.

Applicazione alla matrice di Co-occorrenza

Nel caso specifico della matrice di co-occorrenza abbiamo, indicando con \(|V|\) la dimensione del nostro dizionario, una scomposizione

\(X_{(|V| \times |V|)}={\bf UDV^\top}= \begin{bmatrix} | & & | \\ \boldsymbol u_1 & \cdots & \boldsymbol u_{|V|} \\ | & & | \end{bmatrix}_{(|V| \times |V|)} \begin{bmatrix} \sigma_1 & & {\bf 0} \\ & \ddots & \\ {\bf 0} & & \sigma_{|V|} \end{bmatrix}_{(|V| \times |V|)} \begin{bmatrix} - &\boldsymbol v_1 & - \\ & \vdots & \\ - & \boldsymbol v_{|V|} & - \end{bmatrix}_{(|V| \times |V|)} \)

che ci permetterà di ridurre la dimensione del ns. embedding troncando le matrici ad una arbitraria dimensione \(k\) con l'introduzione dell'errore di varianza sopra indicato. Avremo quindi:

\(\hat X_{(|V| \times |V|)}= \begin{bmatrix} | & & | \\ \boldsymbol u_1 & \cdots & \boldsymbol u_k \\ | & & | \end{bmatrix}_{(|V| \times k)} \begin{bmatrix} \sigma_1 & & {\bf 0} \\ & \ddots & \\ {\bf 0} & & \sigma_k \end{bmatrix}_{(k \times k)} \begin{bmatrix} - &\boldsymbol v_1 & - \\ & \vdots & \\ - & \boldsymbol v_k & - \end{bmatrix}_{(k \times |V|)} \)

Riusciamo in questo modo a passare da vettori (word embedding) di decine di migliaia di componenti, a vettori di un centinaio di componenti, mantenendo buona parte dell'informazione codificata e permettendoci di lavorare con vettori gestibili per effettuare confronti, similitudini, analogie e altre operazioni lineari svolte normalmente sugli word embedding.

Limiti del modello e rimedi

Come abbiamo visto questo modello ha dei limiti legati innanzitutto alla alta dimensionalità della matrice di partenza e alla sua sparsità, parzialmente risolvibili attraverso la SVD. Tuttavia la decomposizione SVD necessita di un tempo quadratico.

Soprattutto c'è il problema che l'aggiunta di nuove parole nel corpus comporta la modifica della intera matrice di co-occorrenza.

Inoltre c'è un tema di squilibrio tra le frequenze di parole comuni e non che richiede spesso dei correttivi e/o l'eliminazione delle parole più comuni che apportano poco significato (articoli, congiunzioni , etc).

Nei fatti oggi è un modello poco utilizzato per la generazione di word embedding, se non in casi estramamente circoscritti.