\underline{1. LARS 1}

1 LARS

Il LARS ( Least Angle Regression ) è una versione semplificata della procedura Stagewise la quale usa una semplice formula matematica per accelerare il calcolo computazionale. In soli m passi si giunge all’insieme delle soluzioni, dove m è il numero delle covarianze. Come nel più classico algoritmo Forward Selection si parte con tutti i coefficienti della stima β uguali a zero e si trova il predittore x_{j_{1}} maggiormente correlato con la risposta. Una volta trovato la direzione scelta è quella di x_{j_{1}} e viene mantenuta finchè non subentra un altro predittore x_{j_{2}} che ha maggior correlazione con il residuo. Da qui in poi il LARS procede lungo una nuova direzione equiangolare rispetto a x_{j_{1}} e x_{j_{2}}. Si percorre tale direzione finché un nuovo predittore x_{j3} diventa il più correlato, a questo punto la direzione che viene presa è equiangolare rispetto a x_{j_{1}}, x_{j_{2}} e x_{j_{3}}. Ovviamente si procede con questa iterazione di k passi di volta in volta avanzando lungo una direzione equiangolare ai predittori precedentemente individuati e aggiornando la direzione nel momento in cui si trova un predittore maggiormente correlato con il residuo. Si dà ora una veloce descrizione geometrica di questo processo. Con il LARS si cerca di dare una stima di μ̂ = Xβ̂ in una successione di passi, aggiungendo ad ogni passaggio una covarianza del modello, in maniera che dopo k passi il vettore β̂_{j} abbia k componenti non nulle.

In figura 1 viene illustrato il caso con due covarianze X = (x_{1}, x_{2}) cioè con m=2. In questo caso la correlazione corrente diventa:

c(μ̂) = X′(y − μ̂) = X′(ȳ_{2} − μ̂)  (1.1)

dimostrando una dipendenza solo da ȳ_{2} nello spazio lineare L(X) generato da x_{1} e x_{2}. Come precedentemente spiegato si parte con μ̂_{0} = 0. In figura 1 si ha che ȳ_{2} − μ̂_{0} produce un angolo più piccolo con x_{1} che con x_{2} ovvero si ha c_{1}(μ̂_{0}) > c_{2}(μ̂_{0}); per cui il LARS aumenta μ̂_{0} nella direzione di x_{1} ottenendo:

μ̂_{1} = μ̂_{0} + γ̂_{1}x_{1}.  (1.2)

A questo punto l’algoritmo Stagewise sceglierebbe γ̂_{1} uguale ad un qualche valore ϵ (molto piccolo) per poi ripetere il processo molte volte. Il classico Forward Selection prenderebbe \underline{2 1. LARS}

invece γ̂_{1} sufficientemente grande per rendere μ̂_{1} equivalente a ȳ_{1}, la proiezione di y su L(x_{1}). Invece LARS usa un valore intermedio di γ̂_{1}, il valore che rende ȳ_{2} − μ̂ ugualmente correlato con x_{1} e x_{2}, in maniera che ȳ_{2} −μ̂_{1} sia la retta secante l’angolo compreso fra x_{1} e x_{2}, ottenendo c_{1}(μ̂_{1}) = c_{2}(μ̂_{1}). Sia u_{2} il versore della bisettrice, il nuovo passo del LARS sarà:

μ̂_{2} = μ̂_{1} + γ̂_{2}u_{2},  (1.3)

con γ̂_{2} scelta per rendere μ̂_{2} = ȳ_{2} nel caso di m=2. Si noti che con più di 2 covarianze γ̂_{2} sarebbe più piccola in conformità con un altro cambio di direzione come illustrato in figura 1.1.

Figura 1.1: Sc

Da questo processo si evince che il calcolo teorico di γ̂_{1}, γ̂_{2}, …, γ̂_{m} sia molto più veloce per il LARS rispetto al calcolo con l’algoritmo Stagewise che avanza solo per piccoli passi. Si presume ora di assumere i vettori covarianze x_{1}, x_{2}, … x_{m} linearmente indipendenti. Per A, un sottoinsieme degli indici {1, 2, …, m}, si definisce la matrice:

X_{A} = (… s_{j}x_{j} …)_{j∈A}  (1.4)

dove la variabile segno s_{j} può assumere i valori ±1. Si prende

G_{A} = X′_{A}X_{A} con A_{A} = (1′_{A}G_{A}1_{A})^{− \frac{1}{2}}  (1.5)

dove 1_{A} è un vettore con elementi unitari con lunghezza pari |A|, la dimensione di A. Sia

u_{A} = X_{A}w_{A} con w_{A} = A_{A}G_{A}^{−1}1_{A}  (1.6)

il vettore equiangolare ovvero il vettore unitario che rende gli angoli (minori di 90°) con le colonne della matrice A tutti uguali,

X′_{A}u_{A} = A_{A}1_{A} e ||u_{A}||^{2} = 1.  (1.7)

Si descrivono ora i passi seguiti dall’algoritmo LARS. Come in Stagewise si parte con μ̂_{0} = 0 e si costruisce μ̂ iterativamente, cercando però di percorrere passi più grandi. Supponendo che μ̂_{A} sia la stima corrente con

ĉ = X′(y − μ̂_{A})  (1.8)

il vettore delle correlazioni correnti come definito dalla generica ĉ = c(μ̂) = X′(y−μ̂). L’insieme attivo A è composto dagli indici delle covarianze che hanno la più grande correlazione corrente in valore assoluto, ovvero

Ĉ = max_{j} |ĉ_{j}| e A = {j : |ĉ_{j}| = Ĉ}.  (1.9)

Prendendo

s_{j} = sign{ĉ_{j}} con j ∈ A  (1.10)

si calcola X_{A}, A_{A} ed u_{A}, e si calcola il prodotto interno

a ≡ X′u_{A}.  (1.11)

Al passo successivo l’algoritmo LARS aggiorna μ̂_{A}, definita come

μ̂_{A_{+}} = μ̂_{A} + γ̂u_{A}  (1.12)

dove

γ̂ = min_{j∈A^{c}}^{+}\{\frac{Ĉ − ĉ_{j}}{A_{A} − a_{j}} , \frac{Ĉ + ĉ_{j}}{A_{A} + a_{j}} \}  (1.13)

con = min^{+} che indica che il minimo viene preso solo tra i componenti positivi delle scelte j in 1.13. Usando le formule 1.12 e 1.13 si definisce

μ(γ) = μ̂_{A} + γu_{A}  (1.14)

con γ > 0, in maniera che la correlazione corrente sia

c_{j}(γ) = x′_{j}(y − μ(γ)) = ĉ_{j} − γa_{j}.  (1.15)

Per j ∈ A usando 1.7 1.9

|c_{j}(γ)| = Ĉ − γA_{A}  (1.16)

il che mostra come tutte le correlazioni correnti declinino nella stessa maniera. Per j ∈ A^{c} uguagliando l’equazione 1.15 con la 1.16, si ottiene che c_{j}(γ) è uguale al massimo valore di γ = (Ĉ_{j} −ĉ_{j})/(A_{A}−a_{j}); alla stessa maniera per −c_{j}(γ) la correlazione corrente per la covarianza inversa −x_{j} raggiunge il massimo per (Ĉ_{j} + ĉ_{j})/(A_{A} + a_{j}). Quindi la γ̂ in 1.13 è il più piccolo valore positivo di γ tale che il nuovo indice ĵ venga aggiunto all’insieme attivo degli indici; ĵ è indice che minimizza la 1.13,