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

Autore: Matteo Alberti

 

 

  1. Metodi lineari per la riduzione: Parte 1
    1. Identificazione attraverso l’individuazione di sottospazi
    2. Approssimazioni Matriciali per la riduzione
    3. Casi di applicazione base: Decomposizione in Valori Singolari (SVD)
  2. Norme Matriciali: Parte 2
    1. Norme vettoriali
    2. Norme indotte
    3. Norme di Schatten
    4. Norma di Frobenius
  3. Casi di applicazione base: Analisi dei Cluster
    1. Definizione di metrica
    2. Distanze di Minkowski (Manhattan, Euclidea, Lagrange)

 

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 covariate) dove vogliamo individuare un sottospazio p-dimensionale \(V_p\) in \( R^k \) ed una mappa lineare \( φ(·) \) da \( R^k \) a \( V_p \) tale per cui le relative immagini \( φ(x_i) \) approssimino in maniera sufficiente i nostri vettori k-dimensionali di input (in riferimento a qualche metrica che andremo a definire)
Riscriviamo come:

\( φ∶ R^k→V_p \)
\(∶ x_i→ φ(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 \( x,y ∈V \) il vettore \( x+y ∈V \)

  • Addizione vettoriale è commutativa, associativa
  • Esiste in V un vettore, indicato con 0 e definito origine
  • Ogni vettore \( x ∈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 ∈V \) ed ad ogni \( α ∈V \) il vettore \( αx∈V \) in modo che:

  • Moltiplicazione fra scalari è associativa
  • 1x=x,∀x ∈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 ∈S \) ed ogni loro combinazione lineare \( αx+ βy ∈S \)

 

Nucleo ed immagine
Siano V e W due spazi vettoriali e sia L∶ V → 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) = {v ∈ V | L(v) = 0 }. \)
Si dice immagine di L l’insieme dei vettori di W che sono immagini di qualche vettore appartenente al dominio V, cioè:
\( Im(L) = {w ∈ W | w = L(v), v ∈ V } \)

Mappa Lineare
Una mappa (o applicazione) lineare\(  f∶ V -> W \) fra spazi vettoriali reali è una funzione per cui valgano le proprietà:
\( f( u ⃗ + v ⃗ ) = f( u ⃗) + f( v ⃗ ) \)
\( f(λ · u ⃗) = λ · f( u ⃗) \)

per ogni \( u ⃗,v ⃗ ∈ V \) e \(λ ∈ R \)
Andiamo a definire solo i casi di principale rilevanza:
Sia \(f∶ V -> 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 \( φ(∙) \) associa all’input x_i l’elemento \( φ(x_i) \) di \( V_p \), avente le seguente forma:
\(φ(x_i )= ∑_(j=1)^p▒〖α_ij b_j 〗\)
\( α_ij \) scelti opportunatamente.
L’errore di approssimazione da \(  R^k→V_p \) quindi da \( x_1..x_n \) a \( φ(x_1 )..φ(x_n) \) consisterà nell’opportuna norma vettoriale:
\(Errore= ∑_(i=1)^n▒‖x_i- φ(x_i) ‖ \)

Fissata la nostra base \( b_1,…,b_p \) i nostri vettori \( φ(x_i) \) possono essere trovati direttamente dalle coordinate \( α_ij \)
Data la mappa \( φ(∙) \) che associa al generico vettore \( φ(x_i) \) il suo vettore di coordinate \( α_ij \) e componiamo con la mappa \( φ(∙) \) otteniamo una mappa che associa ai vettori di input le coordinate delle loro immagini in \( V_p: ϑ(∙)=(φ∘φ)(∙) \)

\( ϑ∶R^k→R^p \)
\( ∶x_i→ ϑ(x_i )= α_ij \)

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:
Da \( R^k→V_p \)
Da \( V_p→R^p \)

\( R^k→V_p \)
Naturalmente passare da k a p dimensioni con p Ciò comporta che tutte le norme, prodotti scalari e distanze non vengono preservate

Esempio:
\( V_p \) sottospazio dimensionale
\( V_p^⊥ \) complemento ortogonale di \( R^k \)
Ogni vettore \( x ∈R^k \) può esser decomposto in una somma di vettori (\( x ∈V_p \) e di un vettore \( x ∈ V_p^⊥ \))
In generale, presi i due vettori u,v ∈R^k abbiamo:
\( 〈u,v〉= 〈u ̂+ u ̂^⊥,v ̂+ v^⊥ 〉≠ 〈u ̂ ,v ̂ 〉 \)
Come si può constatare il prodotto scalare non è conservato.

 

Elementi di algebra:
complemento ortogonale
Sia \( S ⊆V \) un sottospazio di V, definiamo complemento ortogonale di D in V indicandolo con \( S^⊥ \) il sottoinsieme di V definito da:
\( S^⊥ ∶={v ∈V t.c v ∙s=0 ∀s∈S} \)
Ossia un sottoinsieme di tutti i vettori di V ortogonali a tutti i vettori di S

\( V_p→R^p \)

La mappa lineare \( φ(·)  \) è 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={a_i^h} \) e \( a^w={a_i^w} \) allora risulta vera la seguente condizione:
\( 〈u,v〉= ∑_(i,j=1)^p▒〖a_i^h a_j^w 〈b_i,b_j 〉 〗= \) \(  ∑_(i=1)^p▒〖a_i^h a_i^w=〈a^h,a^w 〉 〗\)
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 \( 〈b_i,b_j 〉 \) non si ridurrebbero a 0.
Nel primo caso il prodotto scalare fra i vettori di coordinate è dato da: \( [a^h ]^T I a^w \) mentre nel secondo caso sarebbe data da \( [a^h ]^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_nxp \) di rango p che abbia per righe i vettori di coordinate a_i con i=1…n
Matrice \( B_pxk \) di rango p con i vettori di coordinate \( b_i \) con i=1…p
Matrice \( θ_nxk \) di rango p con i vettori di coordinate \( φ(x_i ) \) 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 ≈ θ=A ∙B \)

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)
0 commenti

Lascia un Commento

Vuoi partecipare alla discussione?
Fornisci il tuo contributo!

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *