Icone color1 02

Introduzione ai Metodi di riduzione della Dimensionalità ed elementi di Algebra lineare [Parte 1]

Autore: Matteo Alberti

 

Sommario

Metodi lineari per la riduzione: 2

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  \alphax \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è:

 

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  fV \rightarrow W  fra spazi vettoriali reali è una funzione per cui valgano le proprietà:

 

ecuacion de recta

per ogni :

Ecuacion 2

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:

 

Formula 2

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:

Formula 3

 

 

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 )

formula 4

 

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:

IMAGEN5

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:

formula 7

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:

ecucion 9

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:

formula 9

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:

x

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

d.p

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)