Appunti completi del corso di Machine Learning

X

2 2

∥v ∥ = v

i i

i=1

CAPITOLO 2. MODELLI LINEARI 15

T T T

e nell’ultimo passaggio abbiamo applicato il risultato (2.5) agli scalari Y Xw e w X Y .

Notiamo ancora una volta che l’empirical risk coincide con una forma quadratica e per-

tanto la sua minimizzazione ammette un risultato in forma chiusa.

1

Calcoliamone quindi il gradiente 2

2 T T

∇ − X Y + X Xw

L (w) =

w S m m

∇

e ponendolo L (w) pari a zero, otteniamo facilmente l’equazione

w S T T

X X w = X Y

T T ×

dove X Y è un vettore colonna di dimensione d, X X è una matrice quadrata d d e

T

w è il consueto vettore colonna di dimensione d. Assumendo che la matrice X X sia

invertibile, l’empirical risk minimizer del problema di regressione lineare risulta

−1

T T

ŵ = X X X Y (2.10)

S

Questa soluzione è del tutto equivalente con la precedente (2.8), infatti

• il primo termine corrisponde a 

 T

x m

1

. X Ti

T ..

x . . . x = x x

X X = 



1 m i



 Tm i=1

x

• il secondo, invece  

y 1 m

... X

T

x . . . x

X Y = = x y

 

1 m i i

  i=1

y m

2.1.2 Considerazioni sull’invertibilità

Come anticipato in precedenza, nella pratica non è sempre possibile richiedere che la

T

matrice X X sia invertibile, molto spesso, infatti, capita di lavorare con matrici rettan-

golari contenenti dei dati e, come ben noto, tali matrici non soddisfano questa proprietà.

Studiamo ora nel dettaglio come approcciarci a questo problema, nello specifico vogliamo

T

capire cosa succede se X X è non-invertibile e se esiste un modo per calcolarne l’inversa

in modo tale da poter risolvere il problema di minimizzazione precedentemente esposto.

A tal proposito, consideriamo il sistema lineare precedentemente incontrato

T T

⇔

X X w = X Y Aw = b

T T

×

dove abbiamo chiamato A = X X la matrice quadrata di dimensioni d d e b = X Y

il vettore colonna di dimensioni d, rispettivamente. Affermare che A non è invertibile

d

⊂

equivale a dire che A non ha rango pieno, ovvero Im(A) con dim (Im A) < d.

R

1 T T

Il secondo addendo è stato ottenuto tenendo conto del fatto che w X Xw è una forma quadratica e,

∂

T T T

secondo il risultato (85) del Matrix Cookbook, la sua derivata coincide con w X Xw = 2X Xw.

∂w

16 2.1. REGRESSIONE LINEARE

# 1: Esiste almeno una soluzione del sistema?

Domanda ∈

Sappiamo che un generico sistema lineare ammette almeno una soluzione se b Im(A).

Nel nostro caso abbiamo che T T

⇒ ∈

b = X Y b Im(X ) (2.11)

Inoltre T

Im(A) = Im(X ) (2.12)

Dimostriamo questo fatto. T m

∈ ∃u ∈

Dimostrazione: Prendiamo un vettore v Im(X ). Questo vuol dire che tale

R

T

che v = X u. Dunque, se applichiamo A a v otteniamo

T T T T T

Av = X Xv = X X(X u) = X (XX u)

T T

∈ ⊆

il che significa Av Im(X ) e quindi Im(A) Im(X ). T

∈

Dimostriamo ora che vale anche l’inclusione inversa. Prendiamo un vettore w Im X

ovvero T m

∈

w = X z per qualche z R

Dobbiamo trovare un y tale che Ay = w. Possiamo scrivere

T T

w = X z = X (Xy) = Ay

T T

∈ ⊆

ovvero w Im X Im A. Ciò dimostra che Im(A) = Im(X ).

Combinando i risultati (2.11) e (2.12) concludiamo che

T

∈

b Im(X ) = Im(A) T T

e pertanto esiste sempre almeno una soluzione del sistema (X X)w = X Y .

# 2: Quante soluzioni esistono?

Domanda

Dimostreremo ora che esistono infinite soluzioni.

∗ ∗

T T

Dimostrazione: Sia w una soluzione del precedente sistema, i.e. (X X)w = X Y .

T

∈

Consideriamo ora w̃ ker(X X): una tale soluzione esiste sempre in quanto la matri-

ce non ha rango pieno e pertanto almeno una delle soluzioni deve trovarsi nel nucleo.

Consideriamo ora le soluzioni dell’equazione

∗ ∗ ∗

T T T T

X X (w + w̃) = X Xw + X X w̃ = X Xw = b

∗

Poichè abbiamo considerato una generica soluzione w e abbiamo ottenuto b, ciò dimostra

che esistono infinite soluzioni.

CAPITOLO 2. MODELLI LINEARI 17

# 3: Come troviamo tali soluzioni?

Domanda

Dobbiamo introdurre uno strumento di algebra lineare, chiamato SVD di una generica

m×n

∈

matrice rettangolare A .

R

2.1.3 Singular Value Decomposition - SVD

La decomposizione ai valori singolari di una matrice A è la fattorizzazione di A nel pro-

T

dotto di tre matrici A = U SV dove le colonne di U e V sono ortonormali e la matrice S

è diagonale con elementi reali positivi. Tale decomposizione è definita per tutte le tipo-

logie di matrici (rettangolari o quadrate). Le colonne di V , chiamate vettori singolari

destri di A, formano un insieme ortogonale senza alcuna ipotesi su A. Le colonne della

matrice U sono chiamate vettori singolari sinistri di A e anch’essi formano un insieme

ortogonale. Infine, gli elementi della matrice diagonale S sono i valori singolari di A.

Ricordiamo la definizione di matrici ortonormali. m×m

∈

Definizione 2.1.3 Una matrice U è detta orto-

(Matrice Ortonormale) R

normale se soddisfa le seguenti proprietà

T T

U U = U U = I (2.13)

n

Ciò vuol dire che le colonne di U formano un insieme di vettori ortonormali, (ortogonali

2 Ti

∥u ∥ ⟨u ⟩ ∀i ̸

con norma unitaria). In altre parole e u u = , u = 0 = j.

i j i j

La precedente definizione suggerisce che m

∈

u u . . . u

U = , u R

1 2 m i

 

u 



1 T

T u

u . . . u

u m

1 1

1

u

  ... ..

2 .

T ..

u u . . . u

U U = = 

  

.. .

1 2 m

  



. T T

  u u . . . u u

1 m

m m

u m

dove 2 Ti

∥u ∥ ⟨u ⟩ ∀i ̸

= 1 e u u = , u = 0 = j

i j i j m×n

∈

Teorema 2.1.1 Per ogni matrice A di

(Singular Value Decomposition) R

m×m n×n

∈ ∈

rango k = rank(A), esistono delle matrici ortonormali U e V , e una

R R

m×n

∈

matrice S diagonale rettangolare

R  

σ

1 ...

 

 

σ

 

k

S =  

0

 

 

. ..

 

 

0

≤ ≤ ≤

con 0 < σ . . . σ σ , tali che

k 2 1 T

A = U SV (2.14)

18 2.1. REGRESSIONE LINEARE

Si noti che il teorema non fa alcuna assunzione sul rango della matrice A. Infatti, tale

decomposizione viene principalmente utilizzata nella pratica quando A non è invertibile

≤ −

e cioè k = rank(A) min(m, n) (dim(ker(A)) = n k).

2.1.4 Costruzione geometrica della SVD

m×n m n

∈ → →

Data una trasformazione lineare A tale che A : : v Av, utilizziamo

R R R

la seguente procedura per costruire la decomposizione ai valori singolari di A. Questo

metodo può essere visto come un modo per trovare il vettore singolare principale itera-

tivamente, ovvero quello associato al massimo valore singolare di A, sfruttando l’idea di

massimizzare la norma del prodotto tra A e v.

Passo 1 n

∈

Consideriamo l’applicazione di un vettore v a norma unitaria alla mappa definita

R

da A. Vogliamo individuare la direzione di v corrispondente alla direzione di massima

amplificazione operata da A, ovvero 2

∥Av∥

v = arg max (2.15)

1 n

v∈R :∥v∥=1

Il vettore v è il vettore unitario (nella dimensione dello spazio delle colonne di A) che

1 ∥Av∥,

massimizza la norma ovvero il massimo allungamento applicato da A. Questo

T

problema si riduce quindi a trovare l’autovettore principale di A A, corrispondente al

T

massimo autovalore di A A. Può essere espresso in maniera equivalente secondo

2

∥Av∥ v 1

v = arg max , v =

1 1

2

∥v∥ ∥v ∥

n

v∈R 1

Una volta trovato v , il massimo valore singolare al quale è associata l’amplificazione

1

massima (la quantità di allungamento che A applica a v ) è

1

∥Av ∥

σ = (2.16)

1 1

Il primo vettore singolare sinistro u è ottenuto proiettando v tramite A e normalizzando

1 1

il risultato Av Av

1 1

u = = (2.17)

1 ∥Av ∥ σ

1 1

Passo 2

Ripetiamo la procedura, aggiungendo il vincolo di ortongonalità fra il vettore v e il

1

generico vettore v poichè vogliamo che i vettori singolari nelle la matrici V ed U siano

fra loro ortonormali 2

∥Av∥

v = arg max (2.18)

2 n

v∈R :∥v∥=1

v⊥v 1

Una volta ricavato il secondo vettore singolare destro, v , la rispettiva amplificazione è

2

∥Av ∥ ≤

σ = σ (2.19)

2 2 1

Notiamo che in questo caso l’amplificazione σ dovrà per forza essere minore della pre-

2

cedente σ poichè stiamo risolvendo lo stesso problema di prima ma con un vincolo

1

CAPITOLO 2. MODELLI LINEARI 19

aggiuntivo, i.e. stiamo risolvendo lo stesso problema di ottimizzazione in uno spazio più

piccolo. Infine, il vettore a norma unitaria u corrisponde a

2 Av

Av 2

2 = (2.20)

u =

2 ∥Av ∥ σ

2 2

Passo k

Ripetiamo la procedura per un numero pari a rank(A) = k volte, aggiungendo il vincolo

che ogni vettore v trovato dalla soluzione di arg max debba essere ortogonale a tutti gli

i

altri vettori v 2

∥Av∥ (2.21)

v = arg max

k n

v∈R :∥v∥=1

v⊥v i

−

con i = 1, . . . , k 1. Una volta trovata la k-esima direzione di massima amplificazione

v , ovvero la minima, il rispettivo valore singolare è

k ∥Av ∥ ≤ ≤

σ = . . . σ (2.22)

k k 1

Essa dev’essere minore delle precedenti σ per le ragioni esposte in precedenza. Infine,

k−1

il vettore a norma unitaria u corrisponde a

k Av

Av k

k = (2.23)

u =

k ∥Av ∥ σ

k k ≤ −

Questo algoritmo deve essere ripetuto fintanto che la condizione dim(ker(A)) n k

è soddisfatta. Infatti, il numero di valori singolari σ che è possibile trovare, coincide

k

−

con il rango della matrice A. Gli eventuali n k vettori singolari dovranno per forza

trovarsi all’interno del nucleo di A. In altre parole, se volessimo trovare σ , esso sarebbe

k+1

necessariamente pari a zero e ciò accadrebbe per tutti i successivi σ , . . . , σ .

k+2 n

Grazie ai k = rank(A) vettori singolari