\section{LARS}
\subsection{L'algoritmo}
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 $\beta$ 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 $\widehat{\mathbf{\mu}}=X \widehat{\mathbf{\beta}}$ in una successione di passi, aggiungendo ad ogni passaggio una covarianza del modello, in maniera che dopo $k$ passi il vettore $\widehat{\beta}_j$ abbia $k$ componenti non nulle.

\begin{figure}[htbp] 
	\centering 
	\includegraphics[scale=0.4]{figure/lars1.eps} 
	\caption{}
	\label{lars1}
\end{figure}

In figura \ref{lars1} viene illustrato il caso con due covarianze $\mathbf{X} = (\mathbf{x}_1 , \mathbf{x}_2)$                       cioè con m=2. In questo caso la correlazione corrente diventa:

\begin{equation}
	\mathbf{c}(\hat{\mathbf{\mu}})=X'(\mathbf{y}-\hat{\mathbf{\mu}})=X'(\mathbf{\bar{y}_2}-\hat{\mathbf{\mu}})
\end{equation}

dimostrando una dipendenza solo da $\bar{\mathbf{y}}_2$ nello spazio lineare $\mathcal{L}(X)$ generato da $\mathbf{x}_1$ e $\mathbf{x}_2$. Come precedentemente spiegato si parte con $\hat{\mu}_0=\mathbf{0}$. In figura \ref{lars1} si ha che $ \bar{\mathbf{y}}_2-\hat{\mathbf{\mu}}_0$ produce un angolo più piccolo con $\mathbf{x}_1$ che con $\mathbf{x}_2$ ovvero si ha $c_1(\hat{\mathbf{\mu}}_0)>c_2(\hat{\mathbf{\mu}}_0)$; per cui il LARS aumenta $\widehat{\mathbf{\mu}}_0$ nella direzione di $\mathbf{x}_1$ ottenendo: 

\begin{equation}
	\mathbf{\hat{\mu}_1}=\mathbf{\hat{\mu}_0}+\widehat{\gamma}_1\mathbf{x}_1.
\end{equation}

A questo punto l'algoritmo Stagewise sceglierebbe $\widehat{\gamma}_1$ uguale ad un qualche valore $\epsilon$ (molto piccolo) per poi ripetere il processo molte volte. Il classico Forward Selection  prenderebbe invece $\widehat{\gamma}_1$ sufficientemente grande per rendere $\hat{\mathbf{\mu}}_1$ equivalente a $\bar{\mathbf{y}}_1$, la proiezione di $\mathbf{y}$ su $\mathcal{L}(\mathbf{x}_1)$. Invece LARS usa un valore intermedio di $\widehat{\gamma}_1$, il valore che rende $\bar{\mathbf{y}}_2-\hat{\mathbf{\mu}}$ ugualmente correlato con $\mathbf{x}_1$ e $\mathbf{x}_2$, in maniera che $ \bar{\mathbf{y}}_2-\hat{\mathbf{\mu}}_1$ sia la retta secante l'angolo compreso fra $\mathbf{x}_1$ e $\mathbf{x}_2$, ottenendo $c_1(\hat{\mathbf{\mu}}_1)=c_2(\hat{\mathbf{\mu}}_1)$.

Sia $\mathbf{u}_2$  il versore della bisettrice, il nuovo passo del LARS sarà:

\begin{equation}
	\mathbf{\hat{\mu}_2}=\mathbf{\hat{\mu}_1}+\widehat{\gamma}_2\mathbf{u}_2,
\end{equation}

con $\widehat{\gamma}_2$ scelta per rendere $\widehat{\mathbf{\mu}}_2=\bar{\mathbf{y}}_2$ nel caso di m=2. Si noti che con più di 2 covarianze $\widehat{\gamma}_2$ sarebbe più piccola in conformità con un altro cambio di direzione come illustrato in figura \ref{lars2}. 

\begin{figure}[htbp] 
	\centering 
	\includegraphics[scale=0.4]{figure/lars2.eps} 
	\caption{}
	\label{lars2}
\end{figure}

Da questo processo si evince che il calcolo teorico di $\widehat{\gamma}_1$, $\widehat{\gamma}_2$, $\ldots$, $\widehat{\gamma}_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 $\mathbf{x}_1$, $\mathbf{x}_2$, $\ldots$ $\mathbf{x}_m$ linearmente indipendenti. Per $\mathcal{A}$, un sottoinsieme degli indici $\{1,2, \ldots ,m\}$, si definisce la matrice:

\begin{equation}
	\mathbf{X_{\mathcal{A}}}=( \ldots  s_j \mathbf{x}_j \ldots )_{j \in \mathcal{A}} 
	\end{equation}
	
	dove la variabile segno $s_j$ può assumere i valori $\pm 1$. Si prende

\begin{equation}
	\mathbf{\mathcal{G}_{\mathcal{A}}}=X_{\mathcal{A}}'X_{\mathcal{A}}
\quad \text{con} \quad
\mathbf{\mathcal{A}_{\mathcal{A}}}=(1_{\mathcal{A}}' \mathbf{\mathcal{G}_{\mathcal{A}}}  1_{\mathcal{A}})^{-\frac{1}{2}}
\end{equation}

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

Sia 
\begin{equation}
  \mathbf{u}_{\mathcal{A}}=X_{\mathcal{A}}w_{\mathcal{A}} \quad \text{con} \quad w_{\mathcal{A}}=\mathcal{A_A} \mathcal{G_A}^{-1} 1_{\mathcal{A}}
\end{equation}

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

\begin{equation}
X_{\mathcal{A}}'\mathbf{u}_{\mathcal{A}}=\mathcal{A_A} 1_\mathcal{A} \quad \text{e} \quad ||\mathbf{u}_{\mathcal{A}}||^2=1.
\label{XAuA}
\end{equation}
 
 Si descrivono ora i passi seguiti dall'algoritmo LARS. Come in Stagewise si parte con $\widehat{\mathbf{\mu}}_0=\mathbf{0}$ e si costruisce $\widehat{\mathbf{\mu}}$ iterativamente, cercando però di percorrere passi più grandi. Supponendo che $\widehat{\mathbf{\mu}}_\mathcal{A}$ sia la stima corrente con
 
\begin{equation}
\hat{\mathbf{c}}=X'(\mathbf{y}-\hat{\mathbf{\mu}}_\mathcal{A})
\end{equation}

il vettore delle correlazioni correnti come definito dalla generica $\widehat{\mathbf{c}}=\mathbf{c}(\widehat{\mu})=X'(\mathbf{y}-\widehat{\mu})$. L'insieme attivo $\mathcal{A}$ è composto dagli indici delle covarianze che hanno la più grande correlazione corrente in valore assoluto, ovvero

\begin{equation}
\widehat{C}=\max_j{|\hat{c}_j|} \quad \text{e} \quad \mathcal{A}=\{j:|\widehat{c}_j|=\widehat{C}\}.
\label{ccap}
\end{equation}

 Prendendo

\begin{equation}
s_j=sign\{\widehat{c}_j\} \quad \text{con} \quad j \in \mathcal{A}
\end{equation}

si calcola $X_\mathcal{A}$, $A_\mathcal{A}$ ed $\mathbf{u}_\mathcal{A}$, e si calcola il prodotto interno

\begin{equation}
\mathbf{a} \equiv X'\mathbf{u}_{\mathcal{A}}.
\end{equation}

Al passo successivo l'algoritmo LARS aggiorna $\widehat{\mu}_{\mathcal{A}}$, definita come

\begin{equation}
\widehat{\mu}_{\mathcal{A_+}}=\widehat{\mu}_{\mathcal{A}} + \widehat{\gamma} \mathbf{u}_{\mathcal{A}}
\label{mu}
\end{equation}

dove

\begin{equation}
\widehat{\gamma}=\min^{+}_{j \in \mathcal{A}^c} \{ \frac{ \widehat{C} - \widehat{c}_j} {A_\mathcal{A}-a_j} , \frac{ \widehat{C} + \widehat{c}_j } { A_\mathcal{A}+a_j } \} 
\label{min}
\end{equation}

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

\begin{equation}
\mathbf{\mu}(\gamma)=\widehat{\mu}_\mathcal{A}+\gamma \mathbf{u}_\mathcal{A}
\end{equation}

con $\gamma>0$, in maniera che la correlazione corrente sia


\begin{equation}
c_j(\gamma)=\mathbf{x}_j'(\mathbf{y}-\mathbf{\mu}(\gamma))=\widehat{c}_j-\gamma a_j.
\label{cj}
\end{equation}

Per $j \in  \mathcal{A}$ usando \ref{XAuA} \ref{ccap}

\begin{equation}
|c_j(\gamma)|=\widehat{C}-\gamma A_\mathcal{A}
\label{cjmod}
\end{equation}

il che mostra come tutte le correlazioni correnti declinino nella stessa maniera.
Per $j \in \mathcal{A}^c$ uguagliando l'equazione \ref{cj} con la \ref{cjmod}, si ottiene che $c_j(\gamma)$ è uguale al massimo valore di $\gamma=(\widehat{C}_j-\widehat{c}_j)/(A_\mathcal{A}-a_j)$; alla stessa maniera per $-c_j(\gamma)$ la correlazione corrente per la covarianza inversa $-\mathbf{x}_j$ raggiunge il massimo per $(\widehat{C}_j+\widehat{c}_j)/(A_\mathcal{A}+a_j)$.

Quindi la $\widehat{\gamma}$ in \ref{min} è il più piccolo valore positivo di $\gamma$  tale che il nuovo indice $\widehat{j}$ venga aggiunto all'insieme attivo degli indici; $\widehat{j}$ è indice che minimizza la \ref{min}, 

\subsection{L'estensione a gruppi}

Quando tutti i fattori ( $Y=\sum_{j=1}^{J} X_j \beta_j + \varepsilon$ ) hanno lo stesso numero di variabili di input $(p_1= \ldots =p_j)$ una naturale estensione del LARS per la selezione dei coefficienti è la sua estensione a gruppi che mantiene la proprietà di linearità a tratti del percorso di soluzione. Si parte definendo l'angolo $\theta(r,X)$, definito come l'angolo compreso tra r (vettore di $n$ elementi) ed il fattore rappresentato da $X_j$, che acquista il senso dell'angolo tra il vettore r e lo spazio generato dalle colonne di $X_j$, ovviamente è di più facile comprensione interpretare l'angolo $\theta(r,X)$ come l'angolo tra $r$ e la sua proiezione $r_{X_j}$ sullo spazio generato da $X_j$ come illustrato in Figura \ref{span}.

\begin{figure}[htbp] 
	\centering 
	\includegraphics[scale=0.4]{figure/span.eps} 
	\caption{}
	\label{span}
\end{figure}

Dunque il $\cos^2 \{ \theta (r,X) \}$ è proporzionale alla somma dei quadrati delle variazioni in $r$ (è proporzionale alla proiezione $r_{X_j}$), che è motivato dalla regressione di $X_j$.
Finché $X_j$ è ortonormale si ha che

\begin{equation}
\cos^2( \theta (r,X) )=||X_j'r||^2/||r||^2.
\end{equation}

Iniziando  con tutti i coefficienti vettoriali posti a zero, group LARS trova il primo fattore (che chiameremo $X_{j1}$) che è l'angolo più piccolo con $Y$ e si procede nella direzione della proiezione di $Y$ finché un nuovo fattore (che chiameremo $X_{j2}$) ha un angolo più piccolo con il residuo, cioè ci si ferma quando

\begin{equation}
||X_{j1}'r||^2=||X_{j2}'r||^2
\end{equation}

dove $r$ è il residuo corrente. A questo punto la proiezione del residuo corrente nello spazio generato dalle colonne di  $X_{j1}$ e di $X_{j2}$ ha lo stesso angolo con i due fattori ed il group LARS procede in questa direzione. Groups LARS continua in questa direzione finché il residuo con $X_{j3}$ è il più correlato. Group LARS continua come per il LARS ad avanzare finché non trova uno spazio maggiormente correlato e a questo punto aggiorna la sua direzione. Il lettore avrà capito che invece di cercare il vettore maggiormente correlato nel caso dell'algoritmo a gruppi si cerca lo spazio maggiormente correlato, in questa maniera la sparsità non sarà sui singoli coefficienti ma sugli stessi ingressi, i cui coefficienti sono stati raggruppati in un unico spazio.


Per riassumere, la  versione implementata a gruppi dell'algoritmo LARS si procede nella seguente maniera:

\begin{itemize}
	\item Passo 1: si inizia con $\beta^{[0]}=0$, $k=1$ e $r^{[0]}=Y$.
	\item Passo 2: si calcola il vettore maggiormente correlato
	
	\begin{equation}
			\mathcal{A}_1=\arg \max_{j} ||X_j' r{[k-1]}||^2/p_j.
	\end{equation}
	
\item Passo 3: si calcola la direzione corrente $\gamma$ come $p=\sum p_j$	vettore di dimensione con $\gamma \mathcal{A}^{c}_{k}=0$
	\begin{equation}
		\gamma_{\mathcal{A}_k}=(X'_{\mathcal{A}_k} X_{\mathcal{A}_k})X'_{\mathcal{A}_k} r^{[k-1]}		
	\end{equation}
	dove $X_{\mathcal{A}_k}$ denota la matrice che comprende le colonne di $X$ corrispondenti a $\mathcal{A}_k$.
	\item Passo 4:
		\begin{equation}
		||X'_j(r^{[k-1]}-\alpha_j X \gamma)||^2/p_j=||X'_{j'}(r^{[k-1]}-\alpha_{j'} X \gamma)||^2/p_{j'}
		\label{XP}
	\end{equation}
	dove $j'$ è arbitrariamente scelto da $\mathcal{A}_k$.
	\item Passo 5: se $\mathcal{A}_k \neq \{1, \ldots , J \} $, si prende $\alpha= \min_{j \notin \mathcal{A}_k}(\alpha_j)\equiv \alpha_{j^*}$ e si aggiorna $\mathcal{A}_{k+1}=\mathcal{A}\cup \{j^* \}$; altrimenti si imposta $\alpha=1$.
	\item Passo 6: si aggiorna $\beta^{[k]}=\beta^{[k-1]}+ \alpha \gamma$, $r^{[k]}=Y-X \beta^{[k]}$ e $k=k+1$. Si torna al passo 3 finché non si ottiene $\alpha=1$.
\end{itemize}

L'equazione \ref{XP} è una equazione quadratica di $\alpha_j$ che può essere risolta facilmente. Nel caso in cui $\alpha_j=0$, $j'$ è il vettore maggiormente correlato e la parte sinistra dell'equazione è minore rispetto alla parte destra . Comunque in accordo con la definizione di $\gamma$ , il lato destro dell'equazione \ref{XP} è zero quando $\alpha_j=1$. Per cui all'ultima iterazione la soluzione di \ref{XP} deve essere compresa tra 0 e 1. In altre parole $\alpha_j$ al passo 4 è sempre ben definita. L'algoritmo si ferma solo al raggiungimento di $\alpha_j=1$, a quel punto il residuo sarà ortogonale con tutte le colonne di $X$ perciò la soluzione dopo l'ultimo passo è la stima ai minimi quadrati, con probabilità 1 che viene raggiunta in J passi.

%Il vantaggio di questo algoritmo è una selezione a posteriori dei sensori, cosa che potrebbe essere utile nel caso in cui si pensi di creare una rete fissa di sensori di sensori in un edificio e si voglia tramite una serie di nodi mobili trovare il modello che lega la temperatura del nodo mobile rispetto ai dati raccolti dalla rete. Questo permetterebbe la creazione di una propria rete di punti virtuali in cui si ricava la misura utilizzando il modello identificato. La sparsità permette di ottenere dei modelli di ordine limitato, sapendo che proprio i sensori più significativi sono stati scelti come ingressi del modello.


 

