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
Casi di applicazione base: Analisi dei Cluster. 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 ,…,
(n unità statistiche su k covariante) dove vogliamo individuare un sottospazio p-dimensionale
in
ed un mappa lineare
da
a
tale per cui le relative immagini
approssimino in maniera sufficiente i nostri vettori k-dimensionali di input (in riferimento a qualche metrica che andremo a definire)
Riscriviamo come:
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
- Addizione vettoriale è commutativa, associativa
- Esiste in V un vettore, indicato con 0 e definito origine
- Ogni vettore
ha un suo opposto, indicato con –x t.c.
Esiste in V un’operazione definita moltiplicazione per gli scalari che associa ad ogni
ed ad ogni
il vettore
in modo che:
- Moltiplicazione fra scalari è associativa
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:
ed ogni loro combinazione lineare
Nucleo ed immagine
Siano V e W due spazi vettoriali e sia :
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.
=
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è:
=
Mappa Lineare
Una mappa (o applicazione) lineare :
fra spazi vettoriali reali è una funzione per cui valgano le proprietà:
per ogni :
Andiamo a definire solo i casi di principale rilevanza:
Sia
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) che risulti sufficientemente “approssimante” e sia
,…,
una base di
(Nota: la base è formata da vettori k-dimensionali in quanto
è sottospazio di
)
La mappa lineare associa all’input
l’elemento
di
, avente le seguente forma:
scelti opportunamente.
L’errore di approssimazione da quindi da
consisterà nell’opportuna norma vettoriale:
Fissata la nostra base ,…,
i nostri vettori
possono essere trovati direttamente dalle coordinate
.
Data la mappa che associa al generico vettore il suo vettore
di coordinate
e componiamo con la mappa
otteniamo una mappa che associa ai vettori di input le coordinate delle loro immagini in
=
Attraverso la nostra mappa i vettori k-dimensionali di input vengono rappresentati in vettori di p-dimensionali ossia come elementi di .
A questo punto risulta immediato che si può procedere con ulteriori analisi in .
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 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:
sottospazio dimensionale
complemento ortogonale di
Ogni vettore può esser decomposto in una somma di vettori (
e di un vettore
)
In generale, presi i due vettori abbiamo:

Come si può constatare il prodotto scalare non è conservato.
Elementi di algebra:
complemento ortogonale
Sia un sottospazio di V, definiamo complemento ortogonale di D in V indicandolo con
il sottoinsieme di V definito da:
Ossia un sottoinsieme di tutti i vettori di V ortogonali a tutti i vettori di S
La mappa lineare è un isomorfismo gli spazi vettoriali
e
, ciò comporta che non vi sarà alcuna perdita di informazioni .
Volendo chiarire ulteriormente questo concetto:
consideriamo il prodotto euclideo e supponiamo che la base sia ortonormale e siano
due vettori di
con i relativi vettori di coordinate:
=
e
=
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 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 :
, 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
di rango p che abbia per righe i vettori di coordinate
con
- Matrice
di rango p con i vettori di coordinate
con
- Matrice
di rango p con i vettori di coordinate
con
- Matrice
matrice di rango k che ha come righe i vettori
con
Allora possiamo riscriverlo come:
Le righe di 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)