Berapakah

Tentukan perkiraan lasso ß λ = arg min ß ∈ R p 1

$$\hat\beta^\lambda = \arg\min_{\beta \in \mathbb{R}^p} \frac{1}{2n} \|y - X \beta\|_2^2 + \lambda \|\beta\|_1,$$ mana$i^{th}$baris$x_i \in \mathbb{R}^p$dari matriks desain$X \in \mathbb{R}^{n \times p}$adalah vektor kovariat untuk menjelaskan respons stokastik$y_i$(untuk$i=1, \dots n$).

Kita tahu bahwa untuk $\lambda \geq \frac{1}{n} \|X^T y\|_\infty$, laso estimasi ß λ=0. (Lihat, misalnya,ruang lingkup parameter tuning Lasso dan Ridge.) Dalam notasi lain, ini menyatakan bahwaλmaks=1$\hat\beta^\lambda = 0$$\lambda_\max = \frac{1}{n} \|X^T y\|_\infty$. Perhatikan bahwa$\lambda_\mathrm{max} = \sup_{\hat\beta^\lambda \ne 0} \lambda.$Kita dapat melihat ini secara visual dengan gambar berikut ini menampilkan jalur solusi laso:

Perhatikan bahwa pada jauh sisi kanan plot, semua koefisien adalah nol. Hal ini terjadi pada titik dijelaskan di atas.$\lambda_\mathrm{max}$

Dari plot ini, kami juga melihat bahwa di jauh sisi kiri, semua koefisien adalah nol: apa nilai di mana setiap komponen ß λ awalnya nol? Yaitu, apa itu λ min = min ∃ $\lambda$$\hat\beta^\lambda$sama untuk, sebagai fungsi dariXdany? Saya tertarik pada solusi formulir tertutup. Secara khusus, saya tidak tertarik pada solusi algoritmik, seperti, misalnya, menyarankan bahwa LARS dapat menemukan simpul melalui perhitungan.

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

Terlepas dari minat saya, sepertinya mungkin tidak tersedia dalam bentuk tertutup, karena, jika tidak, paket komputasi laso kemungkinan akan memanfaatkannya ketika menentukan kedalaman parameter tuning selama validasi silang. Mengingat hal ini, saya tertarik pada apa pun yang secara teoritis dapat ditampilkan tentang λ m i n dan (masih) sangat tertarik pada bentuk tertutup.$\lambda_\mathrm{min}$$\lambda_\mathrm{min}$

Perkiraan laso yang dijelaskan dalam pertanyaan adalah persamaan pengali lagrange dari masalah optimisasi berikut:

$${\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}$$

Optimizazion ini memiliki representasi geometris untuk menemukan titik kontak antara bola multidimensi dan polytope (direntang oleh vektor X). Permukaan polytope mewakili $g(\beta)$ . Kuadrat jari-jari bola mewakili fungsi $f(\beta)$ dan diminimalkan ketika permukaan kontak.

Gambar di bawah ini memberikan penjelasan grafis. Gambar memanfaatkan masalah sederhana berikut dengan vektor dengan panjang 3 (untuk kesederhanaan agar dapat membuat gambar):

$$\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}$$ dan kami kecilkan$\epsilon_1^2+\epsilon_2^2+\epsilon_3^2$ dengan batasan$abs(\beta_1)+abs(\beta_2)+abs(\beta_3) \leq t$

Gambar menunjukkan:

• Permukaan merah menggambarkan kendala, sebuah polytope membentang oleh X.
• Dan permukaan hijau menggambarkan permukaan yang diminimalkan, sebuah bola.
• Garis biru menunjukkan jalur laso, solusi yang kami temukan saat kami mengubah $t$ atau $\lambda$ .
• Menunjukkan vektor hijau solusi OLS y (yang dipilih sebagai β 1 = β 2 = β 3 = 1 atau y = x 1 + x 2 + x 3$\hat{y}$$\beta_1=\beta_2=\beta_3=1$$\hat{y} = x_1 + x_2 + x_3$ .
• Tiga vektor hitam adalah $x_1 = (0.8,0.6,0)$ , $x_2 = (0,0.6,0.8)$ dan $x_3 = (0.6,0.64,-0.48)$ .

Kami menampilkan tiga gambar:

1. Pada gambar pertama hanya satu titik dari polytope yang menyentuh bola . Gambar ini menunjukkan dengan sangat baik mengapa solusi laso bukan hanya kelipatan dari solusi OLS. Arah solusi OLS menambah kuat jumlah $\vert \beta \vert_1$ . Dalam hal ini hanya $\beta_i$ tunggal yang bukan nol.
2. Pada gambar kedua punggungan dari polytope menyentuh bola (dalam dimensi yang lebih tinggi kita mendapatkan analog dimensi yang lebih tinggi). Dalam hal ini beberapa $\beta_i$ tidak nol.
3. Pada gambar ketiga sisi polytope menyentuh bola . Dalam hal ini semua $\beta_i$ adalah nol .

Kisaran $t$ atau $\lambda$ yang kita miliki memiliki kasus pertama dan ketiga dapat dengan mudah dihitung karena representasi geometrisnya yang sederhana.

Kasus 1: Hanya $\beta_i$ tunggal yang bukan nol

The non-nol $\beta_i$ adalah salah satu yang vektor terkait $x_i$ memiliki nilai absolut tertinggi dari kovarians dengan $\hat{y}$ adalah titik parrallelotope yang paling dekat dengan solusi OLS). Kita dapat menghitung pengali Lagrange $\lambda_{max}$ bawah ini yang kita miliki setidaknya $\beta$ nol dengan mengambil turunan dengan $\pm\beta_i$ (tanda tergantung pada apakah kita meningkatkan $\beta_i$ dalam arah negatif atau 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$$

yang mengarah ke

$$\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$$

which equals the $\vert \vert X^Ty \vert \vert_\infty$ mentioned in the comments.

where we should notice that this is only true for the special case in which the tip of the polytope is touching the sphere (so this is not a general solution, although generalization is straightforward).

Case 3: All $\beta_i$ are non-zero.

In this case that a facet of the polytope is touching the sphere. Then the direction of change of the lasso path is normal to the surface of the particular facet.

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

---

Written by StackExchangeStrike