Qual é o menor

Defina a estimativa do laço onde a i ^ {th} linha x_i \ in \ mathbb {R} ^ p da matriz de design X \ in \ mathbb {R} ^ {n \ times p} é um vetor de covariáveis ​​para explicar a resposta estocástica y_i (para i = 1, \ pontos 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$

Sabemos que para $\lambda \geq \frac{1}{n} \|X^T y\|_\infty$ , a estimativa do laço $\hat\beta^\lambda = 0$ . (Veja, por exemplo, o escopo do parâmetro de ajuste Lasso e Ridge .) Em outra notação, isso está expressando que $\lambda_\max = \frac{1}{n} \|X^T y\|_\infty$ . Observe que $\lambda_\mathrm{max} = \sup_{\hat\beta^\lambda \ne 0} \lambda.$Podemos ver isso visualmente com a seguinte imagem exibindo o caminho da solução do laço:

Observe que no distante lado direito da trama, todos os coeficientes são zero. Isso acontece no ponto $\lambda_\mathrm{max}$ descrito acima.

A partir deste enredo, nós também notar que na distante lado esquerdo, todos do coeficiente são diferentes de zero: o que é o valor de em que qualquer componente de é inicialmente zero? Ou seja, o que igual a, como uma função de e ? Estou interessado em uma solução de formulário fechado. Em particular, não estou interessado em uma solução algorítmica, como, por exemplo, sugerir que o LARS poderia encontrar o nó através da computação.p X X min = min ∃ $\lambda$$\hat\beta^\lambda$X

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

Apesar dos meus interesses, parece que pode não estar disponível em formato fechado, pois, caso contrário, os pacotes computacionais do laço provavelmente tirariam vantagem disso ao determinar a profundidade do parâmetro de ajuste durante a validação cruzada. À luz disso, estou interessado em qualquer coisa que possa ser teoricamente mostrada sobre e (ainda) particularmente interessada em um formulário fechado. λ m i $\lambda_\mathrm{min}$$\lambda_\mathrm{min}$

A estimativa do laço descrita na pergunta é o equivalente multiplicador de lagrange do seguinte problema de otimização:

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

Essa otimização tem uma representação geométrica de encontrar o ponto de contato entre uma esfera multidimensional e um politopo (estendido pelos vetores de X). A superfície do politopo representa . O quadrado do raio da esfera representa a função e é minimizado quando as superfícies entram em contato.$g(\beta)$$f(\beta)$

As imagens abaixo fornecem uma explicação gráfica. As imagens utilizaram o seguinte problema simples com vetores de comprimento 3 (para simplificar, a fim de poder fazer um desenho):

$$\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}$$ e minimizamos com a restrição$\epsilon_1^2+\epsilon_2^2+\epsilon_3^2$$abs(\beta_1)+abs(\beta_2)+abs(\beta_3) \leq t$

As imagens mostram:

• A superfície vermelha representa a restrição, um politopo estendido por X.
• E a superfície verde representa a superfície minimalizada, uma esfera.
• A linha azul mostra o caminho do laço, as soluções que encontramos quando mudamos ou .$t$$\lambda$
• O vetor verde mostra a solução OLS (que foi escolhida como ou .$\hat{y}$$\beta_1=\beta_2=\beta_3=1$ y =x1+x2+x3$\hat{y} = x_1 + x_2 + x_3$
• Os três vetores pretos são , e .$x_1 = (0.8,0.6,0)$$x_2 = (0,0.6,0.8)$$x_3 = (0.6,0.64,-0.48)$

Mostramos três imagens:

1. Na primeira imagem, apenas um ponto do politopo está tocando a esfera . Esta imagem demonstra muito bem por que a solução laço não é apenas um múltiplo da solução OLS. A direção da solução OLS é mais forte na soma . Nesse caso, apenas um único é diferente de zero.$\vert \beta \vert_1$$\beta_i$
2. Na segunda imagem, uma crista do politopo está tocando a esfera (em dimensões mais altas, obtemos análogos dimensionais mais altos). Nesse caso, vários são diferentes de zero.$\beta_i$
3. Na terceira imagem, uma faceta do politopo está tocando a esfera . Nesse caso, todos os são diferentes de zero$\beta_i$ .

O intervalo de ou para o qual temos o primeiro e o terceiro casos pode ser facilmente calculado devido à sua representação geométrica simples.$t$$\lambda$

Caso 1: apenas um único diferente de zero$\beta_i$

O diferente de zero é aquele para o qual o vetor associado tem o valor absoluto mais alto da covariância com (este é o ponto do paralelotopo mais próximo da solução OLS). Podemos calcular o multiplicador de Lagrange abaixo do qual temos pelo menos um diferente de zero usando a derivada com$\beta_i$$x_i$y λ m um x β ± β i β i$\hat{y}$$\lambda_{max}$$\beta$$\pm\beta_i$ (o sinal depende se aumentamos o na direção negativa ou positiva):$\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$$

o que leva a

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

que é igual a$\vert \vert X^Ty \vert \vert_\infty$ mencionado nos comentários.

onde devemos notar que isso só é verdade para o caso especial em que a ponta do politopo está tocando a esfera ( portanto, essa não é uma solução geral , embora a generalização seja direta).

Caso 3: Todos os são diferentes de zero.$\beta_i$

Nesse caso, uma faceta do politopo está tocando a esfera. Então a direção da mudança do caminho do laço é normal para a superfície da faceta específica.

O politopo tem muitas facetas, com contribuições positivas e negativas do . No caso da última etapa do laço, quando a solução do laço estiver próxima da solução ols, as contribuições do deverão ser definidas pelo sinal da solução OLS. O normal da faceta pode ser definido tomando o gradiente da função , o valor da soma de beta no ponto$x_i$$x_i$$\vert \vert \beta(r) \vert \vert_1$$r$ , que é:

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

e a mudança equivalente de beta para essa direção é:

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

que depois de alguns truques algébricos com a mudança das transposições ($A^TB^T = [BA]^T$ ) e a distribuição de colchetes se torna

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

normalizamos esta direção:

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

Para encontrar o$\lambda_{min}$ abaixo do qual todos os coeficientes são diferentes de zero. Só precisamos calcular novamente a partir da solução OLS até o ponto em que um dos coeficientes é 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$$

, e neste momento avaliamos a derivada (como antes, quando calculamos ). Usamos que, para uma função quadrática, temos :$\lambda_{max}$$q'(x) = 2 q(1) x$

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

Imagens

um ponto do politopo está tocando a esfera, um único é diferente de zero:$\beta_i$

uma crista (ou difere em várias dimensões) do pólipo está tocando a esfera, muitos são diferentes de zero:$\beta_i$

uma faceta do politopo está tocando a esfera, todos são diferentes de zero:$\beta_i$

Exemplo de código:

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

nota: essas últimas três linhas são as mais importantes

> 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

---

Escrito por StackExchangeStrike