Jaki jest najmniejszy

Zdefiniuj oszacowanie lasso gdzie i ^ {th} wiersz x_i \ in \ mathbb {R} ^ p macierzy projektowej X \ in \ mathbb {R} ^ {n \ times p} jest wektorem zmiennych towarzyszących dla wyjaśnienia odpowiedzi stochastycznej y_i (dla i = 1, \ kropki n ).

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

Wiemy, że dla $\lambda \geq \frac{1}{n} \|X^T y\|_\infty$ szacunek lasso $\hat\beta^\lambda = 0$ . (Zobacz na przykład zakres parametrów dostrajania Lasso i Ridge'a ). W innej notacji oznacza to, że $\lambda_\max = \frac{1}{n} \|X^T y\|_\infty$ . Zauważ, że $\lambda_\mathrm{max} = \sup_{\hat\beta^\lambda \ne 0} \lambda.$Widzimy to wizualnie z następującym obrazem przedstawiającym ścieżkę rozwiązania lasso:

Zauważ, że na daleko po prawej stronie działki, wszystkie współczynniki są równe zero. Dzieje się tak w punkcie $\lambda_\mathrm{max}$ opisanym powyżej.

Od tej działce, możemy również zauważyć, że na daleko po lewej stronie, wszystkie współczynnika są niezerowe: jaka jest wartość , w którym każdy element jest początkowo zerowa? To znaczy, co jest równa, jako funkcja i ? Interesuje mnie rozwiązanie w formie zamkniętej. W szczególności nie interesuje mnie rozwiązanie algorytmiczne, takie jak na przykład sugerowanie, że LARS może znaleźć węzeł poprzez obliczenia.beta X X min = minut ∃ $\lambda$$\hat\beta^\lambda$X

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

Mimo moich zainteresowań wydaje się, że może nie być dostępna w formie zamkniętej, ponieważ w przeciwnym razie pakiety obliczeniowe lasso prawdopodobnie skorzystałyby z niej podczas określania głębokości parametru strojenia podczas sprawdzania poprawności krzyżowej. W związku z tym interesuje mnie wszystko, co można teoretycznie pokazać na temat i (nadal) szczególnie interesuje się formą zamkniętą. λ m i $\lambda_\mathrm{min}$$\lambda_\mathrm{min}$

Oszacowanie lasso opisane w pytaniu jest odpowiednikiem mnożnika lagrange'a następującego problemu optymalizacji:

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

Ta optymalizacja ma geometryczną reprezentację znalezienia punktu styku między sferą wielowymiarową a polytopem (rozpiętym przez wektory X). Powierzchnia polytopu reprezentuje . Kwadrat promienia kuli reprezentuje funkcję i jest minimalizowany, gdy powierzchnie stykają się.$g(\beta)$$f(\beta)$

Poniższe obrazy przedstawiają objaśnienie graficzne. W obrazach wykorzystano następujący prosty problem z wektorami o długości 3 (dla uproszczenia, aby móc wykonać rysunek):

$$\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}$$ a my minimalizujemy z ograniczeniem$\epsilon_1^2+\epsilon_2^2+\epsilon_3^2$$abs(\beta_1)+abs(\beta_2)+abs(\beta_3) \leq t$

Obrazy pokazują:

• Czerwona powierzchnia przedstawia ograniczenie, polytop o rozpiętości X.
• Zielona powierzchnia przedstawia zminimalizowaną powierzchnię - kulę.
• Niebieska linia pokazuje ścieżkę lasso, rozwiązania, które znajdujemy, gdy zmieniamy lub .$t$$\lambda$
• Zielony wektor pokazuje rozwiązanie OLS (które wybrano jako lub .$\hat{y}$$\beta_1=\beta_2=\beta_3=1$ y =x1+x2+x3$\hat{y} = x_1 + x_2 + x_3$
• Trzy czarne wektory to , , i .$x_1 = (0.8,0.6,0)$$x_2 = (0,0.6,0.8)$$x_3 = (0.6,0.64,-0.48)$

Wyświetlamy trzy obrazy:

1. Na pierwszym zdjęciu tylko punkt polytopu dotyka kuli . Ten obraz pokazuje bardzo dobrze, dlaczego rozwiązanie lasso nie jest tylko wielokrotnością rozwiązania OLS. Kierunek rozwiązania OLS zwiększa sumy . W tym przypadku tylko pojedynczy jest niezerowy.$\vert \beta \vert_1$$\beta_i$
2. Na drugim zdjęciu grzbiet polytopa dotyka kuli (w wyższych wymiarach otrzymujemy analogi o wyższych wymiarach). W tym przypadku wiele jest niezerowych.$\beta_i$
3. Na trzecim zdjęciu aspekt polytopu dotyka kuli . W tym przypadku wszystkie są niezerowe$\beta_i$ .

Zakres lub dla którego mamy pierwszy i trzeci przypadek, można łatwo obliczyć dzięki ich prostej reprezentacji geometrycznej.$t$$\lambda$

Przypadek 1: Tylko jeden niezerowy$\beta_i$

Niezerowa to ta, dla której skojarzony wektor ma najwyższą bezwzględną wartość kowariancji z (jest to punkt paralallelotopu najbliższy rozwiązaniu OLS). Możemy obliczyć mnożnik Lagrange'a poniżej którego mamy co najmniej niezerową , biorąc pochodną z (znak w zależności od tego, czy zwiększymy w kierunku ujemnym czy dodatnim):$\beta_i$$x_i$$\hat{y}$$\lambda_{max}$$\beta$$\pm\beta_i$$\beta_i$

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

który prowadzi do

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

co równa się wspomnianej w komentarzach.$\vert \vert X^Ty \vert \vert_\infty$

gdzie powinniśmy zauważyć, że jest to prawdą tylko w szczególnym przypadku, w którym czubek polytopu dotyka kuli ( więc nie jest to ogólne rozwiązanie , chociaż uogólnienie jest proste).

Przypadek 3: Wszystkie są niezerowe.$\beta_i$

W tym przypadku aspekt polytopu dotyka kuli. Wtedy kierunek zmiany ścieżki lassa jest normalny do powierzchni konkretnego aspektu.

Polytop ma wiele aspektów, z dodatnim i ujemnym udziałem . W przypadku ostatniego kroku lasso, gdy rozwiązanie lasso jest zbliżone do rozwiązania ols, wówczas wkład musi być określony znakiem rozwiązania OLS. Normalna ścianka może być zdefiniowana przez przyjęcie gradientu funkcji , wartości sumy beta w punkcie , która wynosi:$x_i$$x_i$$\vert \vert \beta(r) \vert \vert_1$$r$

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

a równoważna zmiana wersji beta dla tego kierunku to:

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

który po niektórych sztuczkach algebraicznych z przesunięciem transpozycji ( ) i rozkładem nawiasów staje się$A^TB^T = [BA]^T$

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

normalizujemy ten kierunek:

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

Aby znaleźć poniżej której wszystkie współczynniki są niezerowe. Musimy tylko przeliczyć z rozwiązania OLS z powrotem do punktu, w którym jeden ze współczynników wynosi zero,$\lambda_{min}$

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

, i w tym momencie oceniamy pochodną (jak poprzednio, gdy obliczamy ). Używamy tego dla funkcji kwadratowej mamy :$\lambda_{max}$$q'(x) = 2 q(1) x$

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

Zdjęcia

punkt dotyka kuli, pojedynczy jest niezerowy:$\beta_i$

grzbiet (lub różny w wielu wymiarach) dotyka kuli, wiele jest niezerowych:$\beta_i$

aspekt dotyka kuli, wszystkie są niezerowe:$\beta_i$

Przykład kodu:

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

Uwaga: najważniejsze są te trzy ostatnie linie

> 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

---

Napisane przez StackExchangeStrike