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}$.