¿Cuál es el más pequeño que da un componente 0 en el lazo?

La estimación del lazo descrita en la pregunta es el equivalente multiplicador lagrange del siguiente problema de optimización:

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

Esta optimización tiene una representación geométrica de encontrar el punto de contacto entre una esfera multidimensional y un politopo (abarcado por los vectores de X). La superficie del politopo representa . El cuadrado del radio de la esfera representa la función y se minimiza cuando las superficies entran en contacto. $g(\beta)$ $f(\beta)$

Las imágenes a continuación proporcionan una explicación gráfica. Las imágenes utilizaron el siguiente problema simple con vectores de longitud 3 (por simplicidad para poder hacer un dibujo):

[\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}$ y minimizamos con la restricción

ϵ_{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$

Las imágenes muestran:

La superficie roja representa la restricción, un politopo atravesado por X.
Y la superficie verde representa la superficie minimalizada, una esfera.
La línea azul muestra el camino del lazo, las soluciones que encontramos a medida que cambiamos o . $t$ $\lambda$
El vector verde muestra la solución OLS (que se eligió como o . $\hat{y}$ $\beta_1=\beta_2=\beta_3=1$ $\hat{y} = x_1 + x_2 + x_3$
Los tres vectores negros son , y . $x_1 = (0.8,0.6,0)$ $x_2 = (0,0.6,0.8)$ $x_3 = (0.6,0.64,-0.48)$

Te mostramos tres imágenes:

En la primera imagen, solo un punto del politopo toca la esfera . Esta imagen demuestra muy bien por qué la solución de lazo no es solo un múltiplo de la solución OLS. La dirección de la solución OLS agrega más fuerza a la suma . En este caso, solo un no es cero. $\vert \beta \vert_1$ $\beta_i$
En la segunda imagen, una cresta del politopo toca la esfera (en dimensiones más altas obtenemos análogos dimensionales más altos). En este caso, múltiples no son cero. $\beta_i$
En la tercera imagen, una faceta del politopo está tocando la esfera . En este caso, todos los son distintos de cero $\beta_i$ .

El rango de o para el que tenemos el primer y el tercer caso se puede calcular fácilmente debido a su representación geométrica simple. $t$ $\lambda$

Caso 1: solo un distinto de cero $\beta_i$

El distinto de cero es aquel para el que el vector asociado tiene el valor absoluto más alto de la covarianza con (este es el punto del paralelelopopo más cercano a la solución OLS). Podemos calcular el multiplicador de Lagrange debajo del cual tenemos al menos un distinto de cero tomando la derivada con (el signo depende de si aumentamos el en dirección negativa o positiva): $\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$

lo que lleva a

λ_{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$

que es igual a mencionado en los comentarios. $\vert \vert X^Ty \vert \vert_\infty$

donde deberíamos notar que esto solo es cierto para el caso especial en el que la punta del politopo está tocando la esfera ( por lo que esta no es una solución general , aunque la generalización es sencilla).

Caso 3: Todos no son cero. $\beta_i$

En este caso, una faceta del politopo está tocando la esfera. Entonces, la dirección de cambio de la ruta del lazo es normal a la superficie de la faceta particular.

El politopo tiene muchas facetas, con contribuciones positivas y negativas de . En el caso del último paso del lazo, cuando la solución del lazo está cerca de la solución ols, entonces las contribuciones de deben definirse mediante el signo de la solución OLS. La normalidad de la faceta se puede definir tomando el gradiente de la función , el valor de la suma de beta en el punto , que es: $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$

y el cambio equivalente de beta para esta dirección es:

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

que después de algunos trucos algebraicos con el desplazamiento de las transposiciones ( ) y la distribución de paréntesis se convierte en $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})$

normalizamos esta dirección:

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

Para encontrar el por debajo del cual todos los coeficientes son distintos de cero. Solo tenemos que volver a calcular desde la solución OLS hasta el punto donde uno de los coeficientes es cero, $\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$

, y en este punto evaluamos la derivada (como antes cuando calculamos ). Usamos eso para una función cuadrática tenemos : $\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$

Imágenes

un punto del politopo toca la esfera, un solo no es cero: $\beta_i$

una cresta (o diferencia en varias dimensiones) del politopo está tocando la esfera, muchos no son cero: $\beta_i$

una faceta del politopo está tocando la esfera, todos no son cero: $\beta_i$

Ejemplo 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: esas tres últimas líneas son las más 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

Sexto empírico
fuente

Gracias por incluir las ediciones! Hasta ahora en mi lectura, estoy atrapado más allá de la subsección "caso 1". El resultado para derivado allí es incorrecto ya que no incluye un valor absoluto o un máximo. Sabemos además que hay un error ya que en la derivación, hay un error de signo, un lugar donde se supone erróneamente la diferenciabilidad, una "elección arbitraria" de para diferenciar con respecto a, y una derivada evaluada incorrectamente. Para ser sincero, no hay un signo " " que sea válido.

λ_{max}

$\lambda_\max$

i

$i$

=

$=$

user795305

Lo he corregido con un signo más menos. El cambio de la beta puede ser positivo o negativo. Con respecto al máximo y "elección arbitraria" ... "para el cual el vector asociado tiene la covarianza más alta con " $x_i$ $\hat{y}$

Sextus Empiricus

¡Gracias por la actualización! Sin embargo, todavía hay problemas. Por ejemplo, se evalúa incorrectamente.

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

$\frac{\partial}{\partial \beta_i} \|y - X \beta\|_2^2$

usuario795305

Si entonces esta correlación entra en la ecuación porque, si s = 0, entonces solo el cambio de tangente a está cambiando la longitud del vector

β = 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

Ah, está bien, ¡hay un límite involucrado en tu argumento! (Está utilizando tanto como que un coeficiente es distinto de cero). Además, la segunda igualdad en la línea con es engañosa ya que el signo podría cambiar debido a la diferenciación del valor absoluto.

β = 0

$\beta = 0$

λ_{max}