Autore: Matteo Alberti

Sommario

Identificazione attraverso l’individuazione di sottospazi 2

Approssimazioni Matriciali per la riduzione. 10

Casi di applicazione base: Decomposizione in Valori Singolari (SVD). 11

Norme Matriciali 11

Norme vettoriali 13

Norme indotte. 13

Norme di Schatten. 13

Norma di Frobenius. 13

Casi di applicazione base: Analisi dei Cluster. 16

Definizione di metrica. 16

Distanze di Minkowski (Manhattan, Euclidea, Lagrange). 16

Lo scopo di questo primo tutorial è di introdurre le nozioni base di riduzione della dimensionalità dal punto di vista matematico (spazi, sottospazi, mappe lineari) e di riprendere gli elementi necessari di algebra lineare (norme, isometria, isomorfismo…) per ogni algoritmo di machine learning.

Metodi lineari per la riduzione:

Andiamo dunque ad introdurre con termini generali la logica dei processi di riduzione lineare della dimensionalità andando in prima fase ad identificare sottospazi “ottimali”

Identificazione attraverso l’individuazione di sottospazi

Abbiamo un insieme di vettori k-dimensionali $x_1$ ,…, $x_n$ (n unità statistiche su k covariante) dove vogliamo individuare un sottospazio p-dimensionale $V_p$ in $R^k$ ed un mappa lineare $\varphi\left ( . \right )$ da $R^k$ a $V_p$ tale per cui le relative immagini $\varphi(x_i)$ approssimino in maniera sufficiente i nostri vettori k-dimensionali di input (in riferimento a qualche metrica che andremo a definire)

Riscriviamo come:

$\varphi: R^k\mapsto V_p$

$: x_i \mapsto\varphi\(x_i )$

Elementi di algebra:

Spazio vettoriale

Si definisce spazio vettoriale su R un insieme V, i cui elementi sono detti vettori con le seguenti proprietà:

Esiste in V un’operazione definita Addizione vettoriale che associa ad ogni

il vettore $x+y$ $\epsilon$ $V$

Addizione vettoriale è commutativa, associativa
Esiste in V un vettore, indicato con 0 e definito origine
Ogni vettore $x$ $\epsilon$ $V$ ha un suo opposto, indicato con –x t.c. $x + (-x) =0$

Esiste in V un’operazione definita moltiplicazione per gli scalari che associa ad ogni $x$ $\epsilon$ $V$ ed ad ogni $\alpha$ $\epsilon$ $V$ il vettore $\alpha$ $x$ $\epsilon$ $V$ in modo che:

Moltiplicazione fra scalari è associativa
$1x=x$ $\forall x$ $\epsilon$ $V$

Inoltre vale anche:

Moltiplicazione scalare è distributiva rispetto all’addizione vettoriale

Sottospazio vettoriale

Si definisce S un insieme non vuoto dello sottospazio di V se per ogni: $x-x=0$ $\epsilon$ $S$ ed ogni loro combinazione lineare $\alpha x +\beta x$ $\epsilon$ $S$

Nucleo ed immagine

Siano V e W due spazi vettoriali e sia $L$ : $V$ $\mapsto W$ un’ applicazione lineare.

Si dice nucleo di L l’insieme dei vettori di V la cui immagine è il vettore nullo di W.

Tale insieme si indica con ker L.

$ker(L)$ = $\left \{ v \epsilon V | L(v) = 0 \right \}$

Si dice immagine di L l’insieme dei vettori di W che sono immagini di qualche vettore appartenente al dominio V, cioè:

$Im(L)$ = $\left \{ w \epsilon W | w = L(v) , v \epsilon V \right \}$

Mappa Lineare

Una mappa (o applicazione) lineare $f$ : $V$ $\rightarrow W$ fra spazi vettoriali reali è una funzione per cui valgano le proprietà:

per ogni :

Andiamo a definire solo i casi di principale rilevanza:

Sia $f$ $: V$ $\mapsto W$ una mappa lineare. Allora f è detta:

un monomorfismo se è iniettiva
un epimorfismo se è suriettiva
un isomorfismo se è biiettiva (iniettiva + suriettiva)
un endomorfismo se V = W
un automorfismo se V = W ed è biettiva.
di rango r se r = dim f(V).

Supponiamo a questo punto di aver individuato un sottospazio (specificato successivamente) $V_p$ che risulti sufficientemente “approssimante” e sia $b_1$ ,…, $b_p$ una base di $V_p$ (Nota: la base è formata da vettori k-dimensionali in quanto $V_p$ è sottospazio di $R^k$ )

La mappa lineare $\varphi\left ( . \right )$ associa all’input $x_i$ l’elemento $\varphi$ $\left ( x_i \right )$ di $V_p$ , avente le seguente forma:

$a_i_j$ scelti opportunamente.

L’errore di approssimazione da $R^k \rightarrow V_p$ quindi da $x_1 .. x_n ..a..\varphi\left ( x_i \right )...\varphi\left ( x_n \right )$

consisterà nell’opportuna norma vettoriale:

Fissata la nostra base $b_1$ ,…, $b_p$ i nostri vettori $\varphi\left ( x_1 \right )$ possono essere trovati direttamente dalle coordinate $a_i_j$ .

Data la mappa $\varphi\left ( . \right )$ che associa al generico vettore il suo vettore $\varphi\left ( x_i \right )$ di coordinate $a_i_j$ e componiamo con la mappa $\varphi\left ( . \right )$ otteniamo una mappa che associa ai vettori di input le coordinate delle loro immagini in $V_p\div \theta\left ( . \right )$ = $\left ( \varphi \circ \varphi \right )$ $\left ( . \right )$

Attraverso la nostra mappa i vettori k-dimensionali di input vengono rappresentati in vettori di p-dimensionali ossia come elementi di $R^p$ .

A questo punto risulta immediato che si può procedere con ulteriori analisi in $R^p$ .

Andiamo dunque ad indagare in che modo questa riduzione della dimensionalità va a mantenere ed a perdere in particolare:

Naturalmente passare da k a p dimensioni $p \lt k$ con comporta una perdita di informazioni ed una deformazioni della geometria originaria del dato. Di particolare rilevanza è che qualunque mappa lineare non potrà essere un isomorfismo né un’isometria.

Ciò comporta che tutte le norme, prodotti scalari e distanze non vengono preservate

Esempio:

$V_p$ sottospazio dimensionale
$V_p^\bot$ complemento ortogonale di $R^k$

Ogni vettore $x\in R^k$ può esser decomposto in una somma di vettori ( $x\in V_p$ e di un vettore $x \in V_p^\bot$ )

In generale, presi i due vettori $u,v \in R^k$ abbiamo:

Come si può constatare il prodotto scalare non è conservato.

Elementi di algebra:

complemento ortogonale

Sia $S \subseteq V$ un sottospazio di V, definiamo complemento ortogonale di D in V indicandolo con $S^\bot$ il sottoinsieme di V definito da:

Ossia un sottoinsieme di tutti i vettori di V ortogonali a tutti i vettori di S

$V_p\rightarrow R^p$

La mappa lineare $\varphi\left ( . \right )$ è un isomorfismo gli spazi vettoriali $V_p$ e $R^p$ , ciò comporta che non vi sarà alcuna perdita di informazioni .

Volendo chiarire ulteriormente questo concetto:

consideriamo il prodotto euclideo e supponiamo che la base $b_1 ... b_p$ sia ortonormale e siano $h , w$ due vettori di $V_p$ con i relativi vettori di coordinate: $a^h$ = $\left \{ a^h_i \right \}$ e $a^w$ = $\left \{ a^w_i \right \}$ allora risulta vera la seguente condizione:

Significa che il prodotto scalare tra h,w è identico al prodotto scalare dei rispettivi vettori di coordinate iniziali (giusto specificare che i due prodotti scalari sono definiti in spazi differenti sebbene siano stati scritti allo stesso modo)

Se la base $\left ( b_i, b_j \right )$ non fosse ortonormale i fattori non si ridurrebbero a 0.

Nel primo caso il prodotto scalare fra i vettori di coordinate è dato da:

mentre che nel secondo caso sarebbe dato da : $\left [a^h \right ]$ $^t$ $G a^w$ , con G matrice di Gram ne consegue quindi che matrici costruite nel secondo modo ed associate a basi differenti sono fra loro diverse (dovendo riadattare il calcolo dei prodotti scalari, norme, distanze indotte …)

Elementi di algebra:

ortonormale:

Una base si definisce ortonormale quando è composta da vettori di norma unitaria e fra loro ortogonali

Approssimazioni Matriciali per la riduzione

Vogliamo dare una seconda visione sulla riduzione alla dimensionalità basata sull’approssimazione matriciale (ciò che verrà utilizzata in pratica in ogni linguaggio di programmazione)

Data:

Matrice $A_n_x_p$ di rango p che abbia per righe i vettori di coordinate $a_i$ con $i= 1..n$
Matrice $B_p_x_q$ di rango p con i vettori di coordinate $b_i$ con $i = 1 .... p$
Matrice $\theta_n_x_k$ di rango p con i vettori di coordinate $\varphi \left ( x_1 \right )$ con $i= 1....n$
Matrice $x$ matrice di rango k che ha come righe i vettori $x_i$ con $i= 1..n$

Allora possiamo riscriverlo come:

$X\approx \theta = A\cdot B$

Le righe di $\theta$ sono date dalle combinazioni lineari delle righe di B ossia dalla nostra base, con i coefficienti dati dalle righe di A, le coordinate sulla base scelta.

Il nostro problema di riduzione della dimensionalità corrisponde quindi ad individuare un sottospazio vettoriale di dimensione p (p<k) la nostra base scelta (B) e delle relative coordinate date dalla matrice A.

Nell’analisi dei dati, dove il nostro punto di partenza è la matrice dei dati, le diverse tecniche di riduzione si differenziano in base al tipo di approssimazione, decomposizione e scelta fra le tante basi possibili.

Casi di applicazione base: Decomposizione in Valori Singolari (SVD)

Andiamo ad implementare in Python una semplice decomposizione in valori singolari (SVD) ossia andiamo a suddividere la nostra matrice X di partenza nelle due matrici A e B viste in precedenza:

import numpy as np

X = np.array([3,2,4],[3,6,7],[2,1,4])

autoval, autovett = np.linalg.eig(X)

Metodi lineari per la riduzione:

Identificazione attraverso l’individuazione di sottospazi

Approssimazioni Matriciali per la riduzione

Casi di applicazione base: Decomposizione in Valori Singolari (SVD)

Potrebbero interessarti