PCA

La Principal Component Analysis, o trasformazione discreta di Karhunen-Loeve KLT, è una tecnica che ha due importanti applicazioni nell'analisi dei dati:

• permette di “ordinare” in una distribuzione vettoriale dei dati in modo da massimizzarne la varianza e, attraverso questa informazione, ridurre le dimensioni del problema: si tratta pertanto di una tecnica di compressione dei dati a perdita, o altrimenti una tecnica per rappresentare con meno dati la medesima quantità di informazione;
• trasforma i dati in ingresso in modo che la matrice di covarianza dei dati in uscita sia diagonale e pertanto le componenti dei dati siano tra loro scorrelate.

Allo stesso modo esistono due formulazioni della definizione di PCA:

• proietta i dati su uno spazio a dimensione inferiore tale che la varianza dei dati proiettati sia massima;
• proietta i dati su uno spazio a dimensione inferiore tale che la distanza tra il punto e la sua proiezione sia minima.

Un esempio pratico di riduzione delle dimensioni di un problema è l'equazione di un iperpiano in $d$ dimensioni: esiste una base dello spazio che trasforma l'equazione del piano riducendola a $d-1$ dimensioni senza perdere informazione, facendo risparmiare così una dimensione al problema.

Figura 2.2: Componenti Principali.

sere memorizzati nelle righe^2.2 della matrice $\mathbf{X}$ di dimensioni $n \times d$, matrice pertanto che memorizza $n$ vettori aleatori di dimensionalità $d$ e con $n > d$.

Ogni riga corrisponde a una diversa osservazione $\mathbf{x}_i$ e la distribuzione di questi esperimenti deve avere media, quantomeno quella empirica, nulla.

Assumendo che i punti abbiano media zero (cosa che si può sempre ottenere con la semplice sottrazione del centroide), la matrice di covarianza delle osservazioni è data da

$$\boldsymbol\Sigma = E(\mathbf{x}\mathbf{x}^{\top}) \approx \frac{1}{n} \mathbf{X}^{\top}\mathbf{X}$$ (2.69)

Se i dati in ingresso $\mathbf {x}$ sono correlati, la matrice di covarianza $\boldsymbol\Sigma$ non è una matrice diagonale.

L'obiettivo di PCA è trovare una trasformazione $\mathbf{V}$ ottima che trasformi i dati da correlati a decorrelati

$$\mathbf{y} = \mathbf{V}^{\top}\mathbf{x}$$ (2.70)

ed ordinati in base al loro contenuto informativo in maniera tale che, se preso un sottoinsieme delle basi, possa tale approccio ridurre la dimensione del problema.

Se esiste una base ortonormale $\mathbf{V}$ tale che la matrice di covarianza $\boldsymbol\Sigma$ espressa in questa base sia diagonale, allora gli assi di questa nuova base si chiamano componenti principali di $\boldsymbol\Sigma$ (o della distribuzione di $\mathbf {x}$). Quando si ottiene una matrice di covarianza dove tutti gli elementi sono nulli tranne quelli sulla diagonale, significa che sotto questa nuova base gli eventi sono tra loro scorrelati.

Questa trasformazione può essere trovata risolvendo un problema agli autovalori: si può infatti dimostrare che gli elementi della matrice diagonale sono gli autovalori di $\boldsymbol\Sigma$ e che le varianze delle proiezioni del vettore $\mathbf {x}$ sulle componenti principali coincidono con tali autovalori:

$$\boldsymbol\Sigma \mathbf{V} = \mathbf{V}\boldsymbol\Delta$$ (2.71)

dove $\mathbf{V}$ è la matrice degli autovettori (matrice ortogonale tale che $\mathbf{V}\mathbf{V}^{\top}=\mathbf{I}$) e $\boldsymbol\Delta$ è la matrice diagonale degli autovalori ordinati $\lambda_1 \ge \ldots \ge \lambda_d$.

Per ottenere questo risultato esistono due approcci.

Siccome $\boldsymbol\Sigma$ è una matrice simmetrica reale semidefinita positiva, può essere scomposta come

$$\boldsymbol\Sigma = \mathbf{V}\boldsymbol\Delta\mathbf{V}^{\top}$$ (2.72)

chiamata decomposizione spettrale, con $\mathbf{V}$ matrice ortonormale degli autovettori e $\boldsymbol\Delta$ matrice diagonale degli autovalori. Siccome la matrice $\boldsymbol\Sigma$ è semidefinita positiva, tutti gli autovalori sono non negativi.

Tale tecnica tuttavia richiede il calcolo esplicito di $\boldsymbol\Sigma$.

Data una matrice rettangolare $\mathbf{X}$, la decomposizione ai valori singolari (SVD) permette di ottenere in modo numericamente stabile gli autovettori di $\mathbf{X}^{\top}\mathbf{X}$ e, attraverso il quadrato dei valori singolari, i corrispondenti autovalori. La SVD costituisce pertanto la tecnica di riferimento per il calcolo delle componenti principali.

Attraverso la SVD è possibile decomporre la matrice degli eventi $\mathbf{X}$ come

$$\mathbf{X} = \mathbf{U}\mathbf{S}\mathbf{V}^{\top}$$

usando la rappresentazione Economy/Compact SVD, dove $\mathbf{U}$ contiene i vettori singolari sinistri (left singular vectors), $\mathbf{S}$ contiene i valori singolari di $\mathbf{X}$ e $\mathbf{V}$ contiene i vettori singolari destri.

È da notare che usando la SVD non è necessario calcolare esplicitamente la matrice di covarianza $\boldsymbol\Sigma$. Tale matrice può essere ricavata in un secondo momento attraverso

$$\boldsymbol\Sigma = \frac{1}{n}\mathbf{X}^{\top}\mathbf{X} = \frac{1}{n}\mathbf{V}\mathbf{S}^{2}\mathbf{V}^{\top}$$ (2.73)

Confrontando questa relazione con l'equazione (2.72) si ottiene

$$\boldsymbol\Delta = \frac{1}{n}\mathbf{S}^{2}.$$ (2.74)

Vanno ricordate le proprietà degli autovalori e dei valori singolari:

• Le matrici $\mathbf{X}\mathbf{X}^{\top}$ e $\mathbf{X}^{\top}\mathbf{X}$ condividono gli stessi autovalori non nulli.
• I valori singolari $\sigma_i$ della matrice $\mathbf{X}$ sono le radici quadrate degli autovalori di $\mathbf{X}^{\top}\mathbf{X}$:
  
  $$\sigma_i = \sqrt{\lambda_i(\mathbf{X}^{\top}\mathbf{X})}.$$
  
  

• Gli autovalori maggiori della matrice di covarianza sono associati alle direzioni di massima varianza dei dati.

Va inoltre ricordata una importante proprietà della SVD:

$$\mathbf{X}^{(l)} = \sum_{i=1}^{l} \sigma_i \mathbf{u}_i \mathbf{v}_i^{\top}$$ (2.75)

che rappresenta la migliore approssimazione di rango $l$ della matrice $\mathbf{X}$ nel senso della norma di Frobenius. Questo fatto, unito alla caratteristica della SVD di restituire i valori singolari ordinati dal maggiore al minore, permette di approssimare una matrice con una di rango inferiore.

Selezionando gli autovettori associati agli autovalori maggiori è possibile costruire una matrice

$$\tilde{\mathbf V} \in \mathbb{R}^{d\times m}$$

le cui colonne formano una base ortonormale dello spazio ridotto. La proiezione di un vettore

$$\mathbf x \in \mathbb{R}^{d}$$

su tale sottospazio è

$$\mathbf y = \tilde{\mathbf V}^{\top}\mathbf x$$

con

$$\mathbf y \in \mathbb{R}^{m}.$$

Il vettore $\mathbf y$ rappresenta una descrizione a dimensionalità ridotta dei dati che preserva la maggior parte della varianza presente nel sistema.

Figura 2.3: Esempio dei primi 10 autovettori $24 \times 48$ estratti dal dataset di pedoni Daimler-DB

Footnotes

...righe^2.2

In questo documento si è scelta la convenzione per righe: in letteratura si trova in ugual maniera la rappresentazione per riga o per colonna dei dati e di conseguenza la nomenclatura potrebbe essere differente e far riferimento a $\mathbf{U}$ invece che a $\mathbf{V}$ e viceversa.