Jaki jest najmniejszy

Zdefiniuj oszacowanie lasso gdzie wiersz macierzy projektowej jest wektorem zmiennych towarzyszących dla wyjaśnienia odpowiedzi stochastycznej (dla ).

{\hat{β}}^{λ} = \arg min_{β \in R^{p}} \frac{1}{2 n} ‖ y - X β ‖_{2}^{2} + λ ‖ β ‖_{1},

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

i^{t h}

$i^{th}$

x_{i} \in R^{p}

$x_i \in \mathbb{R}^p$

X \in R^{n \times p}

$X \in \mathbb{R}^{n \times p}$

y_{i}

$y_i$

i = 1, \dots n

$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. $\lambda$ $\hat\beta^\lambda$

λ_{min} = min_{\exists j s . t . {\hat{β}}_{j} = 0} λ

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

X

$X$

y

$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ą. $\lambda_\mathrm{min}$ $\lambda_\mathrm{min}$

lasso regularization

— użytkownik795305
źródło

Jest to stwierdzone i udowodnione w dokumencie glmnet

— Matthew Drury

@MatthewDrury Dziękujemy za udostępnienie tego! Jednak ten artykuł nie wydaje się dzielić tego, co sugerujesz, że oni robią. W szczególności zwróć uwagę, że mój jest ich .

λ_{max}

$\lambda_\max$

λ_{min}

$\lambda_\min$

— user795305

Czy na pewno potrzebujesz tagu [tuning-parameter]?

— ameba mówi Przywróć Monikę

masz rację, zamknięta forma rozwiązania lasso zasadniczo nie istnieje (patrz stats.stackexchange.com/questions/174003/... ). jednak lars przynajmniej mówi ci, co się dzieje i pod jakimi warunkami / w którym momencie możesz dodać / usunąć zmienną. myślę, że coś takiego jest najlepsze, co możesz dostać.

— chRrr

@chRrr Nie jestem pewien, czy to w pełni uczciwe powiedzieć: wiemy, że dla . Oznacza to, że w skrajnym przypadku rozwiązania 0, mamy formę zamkniętą. Pytam, czy podobnie jest w skrajnym przypadku, gdy oszacowanie lasso jest gęste (tj. Bez zer). Rzeczywiście, nie jestem nawet zainteresowany dokładnymi wpisami --- tylko czy są one zerowe czy nie.

{\hat{β}}^{λ} = 0

$\hat\beta^\lambda = 0$

λ \geq \frac{1}{n} ‖ X^{t} y ‖_{\infty}

$\lambda \geq \frac{1}{n} \|X^t y\|_\infty$

{\hat{β}}_{λ}

$\hat\beta_\lambda$

— user795305

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

minimize f (β) subject to g (β) \leq t

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

\begin{aligned} f (β) & = \frac{1}{2 n} | | y - X β | |_{2}^{2} \\ g (β) & = | | β | |_{1} \end{aligned}

$\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{matrix} y_{1} \\ y_{2} \\ y_{3} \end{matrix}] = [\begin{matrix} 1.4 \\ 1.84 \\ 0.32 \end{matrix}] = β_{1} [\begin{matrix} 0.8 \\ 0.6 \\ 0 \end{matrix}] + β_{2} [\begin{matrix} 0 \\ 0.6 \\ 0.8 \end{matrix}] + β_{3} [\begin{matrix} 0.6 \\ 0.64 \\ - 0.48 \end{matrix}] + [\begin{matrix} ϵ_{1} \\ ϵ_{2} \\ ϵ_{3} \end{matrix}]

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

ϵ_{1}^{2} + ϵ_{2}^{2} + ϵ_{3}^{2}

$\epsilon_1^2+\epsilon_2^2+\epsilon_3^2$

a b s (β_{1}) + a b s (β_{2}) + a b s (β_{3}) \leq t

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

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$
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$
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}{2 n} | | y - X β | |_{2}^{2} - λ | | β | |_{1})}{\pm \partial β_{i}} = 0

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

λ_{m a x} = \frac{(\frac{1}{2 n} \frac{\partial (| | y - X β | |_{2}^{2}}{\pm \partial β_{i}})}{(\frac{| | β | |_{1})}{\pm \partial β_{i}})} = \pm \frac{\partial (\frac{1}{2 n} | | y - X β | |_{2}^{2}}{\partial β_{i}} = \pm \frac{1}{n} x_{i} \cdot y

$\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} (| | β (r) | |_{1}) = - \nabla_{r} (sign (\hat{β}) \cdot (X^{T} X)^{- 1} X^{T} r) = - sign (\hat{β}) \cdot (X^{T} X)^{- 1} X^{T}

$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{β}}_{l a s t} = (X^{T} X)^{- 1} X n = - (X^{T} X)^{- 1} X^{T} [sign (\hat{β}) \cdot (X^{T} X)^{- 1} X^{T}]

$\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{β}}_{l a s t} = - (X^{T} X)^{- 1} sign (\hat{β})

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

normalizujemy ten kierunek:

{\vec{β}}_{l a s t, n o r m a l i z e d} = \frac{{\vec{β}}_{l a s t}}{\sum {\vec{β}}_{l a s t} \cdot s i g n (\hat{β})}

$\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 = m i n (\frac{\hat{β}}{{\vec{β}}_{l a s t, n o r m a l i z e d}}) with the condition that \frac{\hat{β}}{{\vec{β}}_{l a s t, n o r m a l i z e d}} > 0

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

λ_{m i n} = \frac{d}{n} | | X {\vec{β}}_{l a s t, n o r m a l i z e d} | |_{2}^{2}

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

— Sextus Empiricus
źródło

Dziękujemy za uwzględnienie zmian! Jak dotąd czytając, utknąłem tuż obok podrozdziału „przypadek 1”. Wynik dla wyprowadzony tam jest niepoprawny, ponieważ nie zawiera wartości bezwzględnej ani maksymalnej. Wiemy ponadto, że istnieje błąd, ponieważ w derywacji występuje błąd znaku, miejsce, w którym błędnie zakłada się różniczkowość, „arbitralny wybór” do rozróżnienia w odniesieniu do, oraz niepoprawnie oszacowana pochodna. Szczerze mówiąc, nie ma jednego poprawnego znaku „ ”.

λ_{max}

$\lambda_\max$

i

$i$

=

$=$

— user795305

Poprawiłem to za pomocą znaku plus minus. Zmiana wersji beta może być dodatnia lub ujemna. W odniesieniu do maksymalnego i „arbitralnego wyboru” ... ”, dla którego powiązany wektor ma najwyższą kowariancję z $x_i$ $\hat{y}$ ”

— Sextus Empiricus

Dziękuję za aktualizację! Nadal jednak występują problemy. Na przykład,

\frac{\partial}{\partial β_{i}} ‖ y - X β ‖_{2}^{2}

$\frac{\partial}{\partial \beta_i} \|y - X \beta\|_2^2$ jest oceniany nieprawidłowo.

— user795305

Jeśli to korelacja ta wchodzi w równanie, ponieważ: jeśli s = 0, to tylko zmiana stycznej na zmienia długość wektora

β = 0

$\beta=0$

\frac{\partial}{\partial β_{i}} | | y - X β | |_{2}^{2}

$\frac{\partial}{\partial\beta_i} \vert \vert y - X\beta \vert \vert_2^2$

= \frac{\partial | | y - X β | |_{2}}{\partial β_{i}} 2 | | y - X β | |_{2}

$= \frac{\partial \vert \vert y - X\beta \vert \vert_2}{\partial\beta_i} 2 \vert \vert y - X\beta \vert \vert_2$

= \frac{\partial | | y - s x_{i} | |_{2}}{\partial s} 2 | | y - X β | |_{2}

$= \frac{\partial \vert \vert y - s x_i \vert \vert_2}{\partial s} 2 \vert \vert y - X\beta \vert \vert_2$

= 2 c o r (x_{i}, y) | | x_{i} | |_{2} | | y | |_{2}

$= 2 cor(x_i,y) \vert \vert x_i \vert \vert_2 \vert \vert y \vert \vert_2$

= 2 x_{i} \cdot y

$= 2 x_i \cdot y$

s x_{i}

$s x_i$

y

$y$

y - s x_{i}

$y - s x_i$

— Sextus Empiricus

Ach, okej, więc w twoim sporze jest granica! (Używasz zarówno

β = 0

$\beta = 0$ i tego, że współczynnik jest niezerowy.) Ponadto druga równość w linii z jest myląca, ponieważ znak może się zmienić z powodu różnicowania wartości bezwzględnej.

λ_{max}

$\lambda_\max$

— user795305

Jaki jest najmniejszy

Przypadek 1: Tylko jeden niezerowyβiβi\beta_i

Przypadek 3: Wszystkie są niezerowe.βiβi\beta_i

Zdjęcia

Przykład kodu:

Przypadek 1: Tylko jeden niezerowy $\beta_i$

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