ML - 31 - Singular Value Decomposition

Consideriamo adesso la matrice \(\mathbf{A} = \mathbf{W}^T \mathbf{W} \in \mathbb{R}^{m \times m}\). È possibile dimostrare le seguenti cose:

• \(A\) è simmetrica.

• \(A\) è semidefinita positiva.

• Tutti gli autovalori di \(A\) sono reali.

• Gli autovettori di \(A\) che corrispondono ad autovalori diversi sono ortonormali tra loro.

• Deve esistere un insieme di autovettori di \(A\) che formano una base ortonormale.

• Tutti gli autovettori di\(A\) sono maggiori di \(0\).

Complessivamente abbiamo che \(\mathbf{A} = \mathbf{W}^T \mathbf{W} \in \mathbb{R}^{m \times m}\) ha \(r\) reali e positivi autovalori \(\lambda_1, \ldots, \lambda_r\), con i corrispondenti autovettori \(v_1, \ldots, v_r\) ortonormali tra loro con

\[\mathbf{A} v_i = (\mathbf{W}^T \mathbf{W}) v_i = \lambda_i v_i\]

Se definiamo adesso gli \(r\) valori singolari come le radici degli autovalori

\[\sigma_i = \sqrt{\lambda_i} \;\;\;\;,\;\;\; i = 1,\ldots,r\]

e consideriamo il seguente insieme di vettori

\[\mathbf{u}_i = \frac{1}{\sigma_i} \mathbf{W} v_i \;\;\;\;,\;\;\; i = 1,\ldots,r\]

È possibile osservare che

1. \(u_1, \ldots, u_r\) sono ortogornali.

2. \(u_1, \ldots, u_r\) hanno norma unitaria.

A questo punto possiamo considerare le tre matrici seguenti

• La matrice \(\mathbf{V} \in \mathbb{R}^{m \times r}\) che ha i vettori \(v_1, \ldots, v_r\) come colonne

• La matrice \(\mathbf{U} \in \mathbb{R}^{n \times r}\) che ha i vettori \(u_1, \ldots, u_r\) come colonne

• La matrice \(\mathbf{\Sigma} \in \mathbb{R}^{r \times r}\) che è una matrice diagonale avente i valori singolari sulla diagonale.

A questo punto è possibile osservare che

\[\mathbf{W} \mathbf{V} = \mathbf{U} \mathbf{\Sigma}\]

e quindi, dato che \(\mathbf{V}\) è ortogonale, ovvero \(\mathbf{V}^{-1} = \mathbf{V}^T\), otteniamo che

\[\mathbf{W} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^-1 = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^T\]

L'approccio LSA (Latent Semantic Analysis) si basa su tre ipotesi:

• La matrice \(\mathbf{V}, \mathbf{D}\) contiene dei dati da cui possono essere estratte delle informazioni semanticamente significative.

• Per derivare queste informazioni siamo interessati ad effettuare della dimensionality reduction.

• "termini" e "documenti" possono essere modellati tramite punti (vettori) in uno spazio euclideo.

Gli elementi a nostra dispozione sono i seguenti:

• Un dizionario \(\mathbf{V}\) di \(V = |\mathbf{V}|\) termini \(t_1, \ldots, t_V\).

• Un corpus \(\mathbf{D}\) di \(D = | \mathbf{D}|\) documenti \(d_1, \ldots, d_D\).

• Ogni documento \(d_i\) è una sequenza di \(N_i\) occorrenze di termini da \(\mathbf{V}\).

L'idea è quella di considerare ogni documento \(d_i\) come un multiset di \(N_i\) termini di \(\mathbf{V}\) (questa ipotesi è detta bag of words).

Abbiamo poi una corrispondenza tra \(\mathbf{V}\), \(\mathbf{D}\) e uno spazio vettoriale \(\mathcal{S}\). Ad ogni termine \(t_i\) associamo un vettore \(u_i\) e ad ogni documento \(d_j\) associato un vettore \(v_j \in \mathcal{S}\).

Per rappresentare la relazione tra termini e documenti utilizziamo una occurence matrix (matrice di occorrenza) \(\mathbf{W} \in \mathbb{R}^{V \times D}\), dove \(\mathbf{W}(i, j)\) contiene l'occorrenza del termine \(t_i\) nel documento \(d_j\), e tale valore è ottenuto tramite delle funzioni predefinite (tipicamente tf-idf, o entropy related).

Il modello appena descritto presenta vari problemi, tra cui troviamo:

• I valori di \(V\) e \(D\) tipicamente sono molto grandi.

• I vettori per \(t_i\) e \(d_j\) sono molto sparsi.

• Gli spazi vettoriali per termini e documenti sono diversi.

Per risolvere questi problemi si applica una SVD alla matrice delle occorrenze \(\mathbf{W} \in \mathbb{R}^{n \times m}\).

La SVD infatti ci dice che dato il rango \(d \leq \min{(n, m)}\) con \(n > m\), allora esiste una decomposizione della forma

\[\mathbf{W} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^T\]

con,

• \(\mathbf{U} \in \mathbb{R}^{n \times d}\) ortonormale.

• \(\mathbf{V} \in \mathbb{R}^{m \times d}\) ortonormale.

• \(\mathbf{Z} \in \mathbb{R}^{d \times d}\) diagonale.

Graficamente,

Andando ad interpretare le righe di \(\mathbf{W}\) come termini e le colonne di \(\mathbf{W}\) come documenti otteniamo che tramite la SVD siamo in grado di rappresentare sia i termini che i documenti in un sottospazio vettoriale di dimensione minore.

Anche se tecnicamente non conosciamo il valore di \(d\), l'idea è quello di fissarlo in modo arbitrario. Così facendo otteniamo una matrice approssimata

\[\mathbf{W} \approx \overline{\mathbf{W}} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^T\]

Notiamo però che vale la seguente proprietà

\[\underset{A: \text{rank}(A) =d}{\min} || \mathbf{A}||_2 = || \mathbf{W} - \overline{\mathbf{W}} ||_2\]

e quindi la matrice \(\overline{\mathbf{W}}\) è la migliore approssimazione possibile di \(\mathbf{W}\) rispetto a tutte le matrici di rango \(d\) secondo la norma di Frobenius

\[||\mathbf{A}||_2 = \sqrt{\sum\limits_{i = 1}^m \sum\limits_{j = 1}^n | a_{i,j} | ^2}\]

La SVD definisce quindi una trasformazione tra due spazi vettoriali \(\mathcal{V} \in \mathbb{Z}^D\) e \(\mathcal{D} \in \mathbb{Z}^V\) in uno spazio vettoriale continuo della stessa dimensione \(\mathcal{T} \in \mathbb{R}^d\).

La dimensione di \(\mathcal{T}\) è minore o uguale al rank (sconosciuto) della matrice di occorrenza \(\mathbf{W}\), ed è legata alla quantità di distorsione accettabile nella proiezione.

L'idea è che \(\tilde{\mathbf{W}}\) cattura la maggior parte delle associazioni tra termini e documenti in \(\mathbf{W}\), andando a non considerare le relazioni meno significative. In particolare:

• Ogni termine viene rappresentato come una combinazione lineare di concetti invisibili, che corrispondono alle colonne di \(\mathbf{V}\).

• Ogni documento viene rappresentato come una combinazione lineare di topics invisibibli, corrispondendti alle colonne di \(\mathbf{U}\).