Quel est le plus petit

$$\hat\beta^\lambda = \arg\min_{\beta \in \mathbb{R}^p} \frac{1}{2n} \|y - X \beta\|_2^2 + \lambda \|\beta\|_1,$$ $i^{th}$$x_i \in \mathbb{R}^p$$X \in \mathbb{R}^{n \times p}$$y_i$$i=1, \dots n$

Nous savons que pour $\lambda \geq \frac{1}{n} \|X^T y\|_\infty$ , l'estimation au lasso $\hat\beta^\lambda = 0$ . (Voir, par exemple, la portée du paramètre de réglage Lasso et Ridge .) Dans une autre notation, cela exprime que $\lambda_\max = \frac{1}{n} \|X^T y\|_\infty$ . Notez que $\lambda_\mathrm{max} = \sup_{\hat\beta^\lambda \ne 0} \lambda.$Nous pouvons voir cela visuellement avec l'image suivante affichant le chemin de la solution de lasso:

Notez qu'à l' extrême droite du graphique, tous les coefficients sont nuls. Cela se produit au point $\lambda_\mathrm{max}$ décrit ci-dessus.

À partir de ce graphique, nous remarquons également qu'à l' extrême gauche, tous les coefficients sont différents de zéro: quelle est la valeur de à laquelle tout composant de est initialement nul? Autrement dit, quelle est égal, en fonction de et ? Je suis intéressé par une solution de formulaire fermé. En particulier, je ne suis pas intéressé par une solution algorithmique, comme, par exemple, suggérant que LARS pourrait trouver le nœud grâce au calcul.$\lambda$$\hat\beta^\lambda$

$$\lambda_\textrm{min} = \min_{\exists j \, \mathrm{ s.t. } \, \hat\beta_j = 0} \lambda$$ $X$$y$

Malgré mes intérêts, il semble que ne soit pas disponible sous forme fermée, car sinon, les packages de calcul au lasso en profiteraient probablement lors de la détermination de la profondeur du paramètre de réglage lors de la validation croisée. À la lumière de cela, je suis intéressé par tout ce qui peut être théoriquement montré sur et (encore) particulièrement intéressé par une forme fermée.$\lambda_\mathrm{min}$$\lambda_\mathrm{min}$

L'estimation au lasso décrite dans la question est l'équivalent multiplicateur de lagrange du problème d'optimisation suivant:

$${\text{minimize } f(\beta) \text{ subject to } g(\beta) \leq t}$$

$$\begin{align} f(\beta) &= \frac{1}{2n} \vert\vert y-X\beta \vert\vert_2^2 \\ g(\beta) &= \vert\vert \beta \vert\vert_1 \end{align}$$

Cette optimisation a une représentation géométrique de la recherche du point de contact entre une sphère multidimensionnelle et un polytope (enjambé par les vecteurs de X). La surface du polytope représente $g(\beta)$ . Le carré du rayon de la sphère représente la fonction $f(\beta)$ et est minimisé lorsque les surfaces entrent en contact.

Les images ci-dessous fournissent une explication graphique. Les images ont utilisé le problème simple suivant avec des vecteurs de longueur 3 (pour plus de simplicité afin de pouvoir faire un dessin):

$$\begin{bmatrix} y_1 \\ y_2 \\ y_3\\ \end{bmatrix} = \begin{bmatrix} 1.4 \\ 1.84 \\ 0.32\\ \end{bmatrix} = \beta_1 \begin{bmatrix} 0.8 \\ 0.6 \\ 0\\ \end{bmatrix} +\beta_2 \begin{bmatrix} 0 \\ 0.6 \\ 0.8\\ \end{bmatrix} +\beta_3 \begin{bmatrix} 0.6 \\ 0.64 \\ -0.48\\ \end{bmatrix} + \begin{bmatrix} \epsilon_1 \\ \epsilon_2 \\ \epsilon_3\\ \end{bmatrix}$$ et nous minimiser$\epsilon_1^2+\epsilon_2^2+\epsilon_3^2$ avec la contrainte$abs(\beta_1)+abs(\beta_2)+abs(\beta_3) \leq t$

Les images montrent:

• La surface rouge représente la contrainte, un polytope enjambé par X.
• Et la surface verte représente la surface minimisée, une sphère.
• La ligne bleue montre le chemin du lasso, les solutions que nous trouvons en changeant $t$ ou $\lambda$ .
• Le vecteur vert indique la solution OLS y (qui a été choisi en tant que β 1 = β 2 = β 3 = 1 ou y = x 1 + x 2 + x 3 .$\hat{y}$$\beta_1=\beta_2=\beta_3=1$$\hat{y} = x_1 + x_2 + x_3$
• Les trois vecteurs noirs sont $x_1 = (0.8,0.6,0)$ , $x_2 = (0,0.6,0.8)$ et $x_3 = (0.6,0.64,-0.48)$ .

Nous montrons trois images:

1. Dans la première image, seul un point du polytope touche la sphère . Cette image montre très bien pourquoi la solution de lasso n'est pas seulement un multiple de la solution OLS. La direction de la solution OLS ajoute plus fort à la somme $\vert \beta \vert_1$ . Dans ce cas, un seul $\beta_i$ est non nul.
2. Dans la deuxième image, une crête du polytope touche la sphère (dans des dimensions supérieures, nous obtenons des analogues de dimension supérieure). Dans ce cas, les multiples $\beta_i$ sont non nuls.
3. Dans la troisième image, une facette du polytope touche la sphère . Dans ce cas, tous les $\beta_i$ sont non nuls .

La plage de $t$ ou $\lambda$ pour laquelle nous avons les premier et troisième cas peut être facilement calculée en raison de leur représentation géométrique simple.

Cas 1: Un seul $\beta_i$ non nul

Le non nul $\beta_i$ est celle pour laquelle le vecteur associé $x_i$ a la plus grande valeur absolue de la covariance avec $\hat{y}$ (ce qui est le point de la parrallelotope qui le plus proche de la solution de SLO). On peut calculer le multiplicateur de Lagrange $\lambda_{max}$ dessous duquel on a au moins un $\beta$ non nul en prenant la dérivée avec $\pm\beta_i$ (le signe selon qu'on augmente le $\beta_i$ en sens négatif ou positif):

$$\frac{\partial ( \frac{1}{2n} \vert \vert y - X\beta \vert \vert_2^2 - \lambda \vert \vert \beta \vert \vert_1 )}{\pm \partial \beta_i} = 0$$

qui conduit à

$$\lambda_{max} = \frac{ \left( \frac{1}{2n}\frac{\partial ( \vert \vert y - X\beta \vert \vert_2^2}{\pm \partial \beta_i} \right) }{ \left( \frac{ \vert \vert \beta \vert \vert_1 )}{\pm \partial \beta_i}\right)} = \pm \frac{\partial ( \frac{1}{2n} \vert \vert y - X\beta \vert \vert_2^2}{\partial \beta_i} = \pm \frac{1}{n} x_i \cdot y$$

ce qui équivaut à $\vert \vert X^Ty \vert \vert_\infty$ mentionné dans les commentaires.

où nous devons remarquer que cela n'est vrai que pour le cas spécial où la pointe du polytope touche la sphère ( ce n'est donc pas une solution générale , bien que la généralisation soit simple).

Cas 3: Tous les $\beta_i$ sont non nuls.

Dans ce cas, une facette du polytope touche la sphère. Ensuite, la direction de changement de la trajectoire du lasso est normale à la surface de la facette particulière.

The polytope has many facets, with positive and negative contributions of the $x_i$. In the case of the last lasso step, when the lasso solution is close to the ols solution, then the contributions of the $x_i$ must be defined by the sign of the OLS solution. The normal of the facet can be defined by taking the gradient of the function $\vert \vert \beta(r) \vert \vert_1$, the value of the sum of beta at the point $r$, which is:

$$n = - \nabla_r ( \vert \vert \beta(r) \vert \vert_1) = -\nabla_r ( \text{sign} (\hat{\beta}) \cdot (X^TX)^{-1}X^Tr ) = -\text{sign} (\hat{\beta}) \cdot (X^TX)^{-1}X^T$$

and the equivalent change of beta for this direction is:

$$\vec{\beta}_{last} = (X^TX)^{-1}X n = -(X^TX)^{-1}X^T [\text{sign} (\hat{\beta}) \cdot (X^TX)^{-1}X^T]$$

which after some algebraic tricks with shifting the transposes ($A^TB^T = [BA]^T$) and distribution of brackets becomes

$$\vec{\beta}_{last} = - (X^TX)^{-1} \text{sign} (\hat{\beta})$$

we normalize this direction:

$$\vec{\beta}_{last,normalized} = \frac{\vec{\beta}_{last}}{\sum \vec{\beta}_{last} \cdot sign(\hat{\beta})}$$

To find the $\lambda_{min}$ below which all coefficients are non-zero. We only have to calculate back from the OLS solution back to the point where one of the coefficients is zero,

$$d = min \left( \frac{\hat{\beta}}{\vec{\beta}_{last,normalized}} \right)\qquad \text{with the condition that } \frac{\hat{\beta}}{\vec{\beta}_{last,normalized}} >0$$

,and at this point we evaluate the derivative (as before when we calculate $\lambda_{max}$). We use that for a quadratic function we have $q'(x) = 2 q(1) x$:

$$\lambda_{min} = \frac{d}{n} \vert \vert X \vec{\beta}_{last,normalized} \vert \vert_2^2$$

Images

a point of the polytope is touching the sphere, a single $\beta_i$ is non-zero:

a ridge (or differen in multiple dimensions) of the polytope is touching the sphere, many $\beta_i$ are non-zero:

a facet of the polytope is touching the sphere, all $\beta_i$ are non-zero:

Code example:

library(lars)    
data(diabetes)
y <- diabetes$y - mean(diabetes$y)
x <- diabetes$x

# models
lmc <- coef(lm(y~0+x))
modl <- lars(diabetes$x, diabetes$y, type="lasso")

# matrix equation
d_x <- matrix(rep(x[,1],9),length(x[,1])) %*% diag(sign(lmc[-c(1)]/lmc[1]))
x_c = x[,-1]-d_x
y_c = -x[,1]

# solving equation
cof <- coefficients(lm(y_c~0+x_c))
cof <- c(1-sum(cof*sign(lmc[-c(1)]/lmc[1])),cof)

# alternatively the last direction of change in coefficients is found by:
solve(t(x) %*% x) %*% sign(lmc)

# solution by lars package
cof_m <-(coefficients(modl)[13,]-coefficients(modl)[12,])

# last step
dist <- x %*% (cof/sum(cof*sign(lmc[])))
#dist_m <- x %*% (cof_m/sum(cof_m*sign(lmc[]))) #for comparison

# calculate back to zero
shrinking_set <- which(-lmc[]/cof>0)  #only the positive values
step_last <- min((-lmc/cof)[shrinking_set])

d_err_d_beta <- step_last*sum(dist^2)

# compare
modl[4] #all computed lambda
d_err_d_beta  # lambda last change
max(t(x) %*% y) # lambda first change
enter code here

note: those last three lines are the most important

> modl[4]            # all computed lambda by algorithm
$lambda
 [1] 949.435260 889.315991 452.900969 316.074053 130.130851  88.782430  68.965221  19.981255   5.477473   5.089179
[11]   2.182250   1.310435

> d_err_d_beta       # lambda last change by calculating only last step
    xhdl 
1.310435 
> max(t(x) %*% y)    # lambda first change by max(x^T y)
[1] 949.4353

---

Écrit par StackExchangeStrike