¿Cuál es el menor $\lambda$ que da un componente 0 en el lazo?

Question

Definir la estimación del lazo $$\hat\beta^\lambda = \arg\min_{\beta \in \mathbb{R}^p} \frac{1}{2n} \|y - X \beta\|_2^2 + \lambda \|\beta\|_1,$$ donde el $i^{th}$ fila $x_i \in \mathbb{R}^p$ de la matriz de diseño $X \in \mathbb{R}^{n \times p}$ es un vector de covariables para explicar la respuesta estocástica $y_i$ (para $i=1, \dots n$ ).

Sabemos que para $\lambda \geq \frac{1}{n} \|X^T y\|_\infty$ la estimación del lazo $\hat\beta^\lambda = 0$ . (Véase, por ejemplo, Alcance de los parámetros de ajuste de Lasso y Ridge .) En otra notación, esto es expresar que $\lambda_\max = \frac{1}{n} \|X^T y\|_\infty$ . Observe que $\lambda_\mathrm{max} = \sup_{\hat\beta^\lambda \ne 0} \lambda.$ Podemos ver esto visualmente con la siguiente imagen que muestra la trayectoria de la solución del lazo:

Observe que en el lejos derecha del gráfico, todos los coeficientes son cero. Esto ocurre en el punto $\lambda_\mathrm{max}$ descrito anteriormente.

En este gráfico, también observamos que en el lejos lado izquierdo, todos los coeficientes son distintos de cero: ¿cuál es el valor de $\lambda$ en el que cualquier componente de $\hat\beta^\lambda$ es inicialmente cero? Es decir, ¿qué es $$\lambda_\textrm{min} = \min_{\exists j \, \mathrm{ s.t. } \, \hat\beta_j = 0} \lambda$$ igual a, en función de $X$ y $y$ ? Estoy interesado en una solución de forma cerrada. En particular, no estoy interesado en una solución algorítmica, como, por ejemplo, sugiriendo que LARS podría encontrar el nudo a través de la computación.

A pesar de mis intereses, parece que $\lambda_\mathrm{min}$ puede no estar disponible en forma cerrada, ya que, de lo contrario, los paquetes computacionales del lazo probablemente lo aprovecharían al determinar la profundidad del parámetro de ajuste durante la validación cruzada. A la luz de esto, estoy interesado en cualquier cosa que se pueda demostrar teóricamente sobre $\lambda_\mathrm{min}$ y (todavía) especialmente interesado en una forma cerrada.

Answer 1

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

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

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

Las imágenes siguientes ofrecen una explicación gráfica. En las imágenes se ha utilizado el siguiente problema sencillo con vectores de longitud 3 (por simplicidad para poder hacer un dibujo):

$$\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 $\epsilon_1^2+\epsilon_2^2+\epsilon_3^2$ con la restricción $abs(\beta_1)+abs(\beta_2)+abs(\beta_3) \leq t$

Las imágenes lo muestran:

• La superficie roja representa la restricción, un politopo abarcado por X.
• Y la superficie verde representa la superficie minimizada, una esfera.
• La línea azul muestra la trayectoria del lazo, las soluciones que encontramos al cambiar $t$ o $\lambda$ .
• El vector verde muestra la solución OLS $\hat{y}$ (que fue elegido como $\beta_1=\beta_2=\beta_3=1$ o $\hat{y} = x_1 + x_2 + x_3$ .
• Los tres vectores negros son $x_1 = (0.8,0.6,0)$ , $x_2 = (0,0.6,0.8)$ y $x_3 = (0.6,0.64,-0.48)$ .

Mostramos tres imágenes:

1. En la primera imagen sólo un punto del politopo toca la esfera . Esta imagen demuestra muy bien por qué la solución del lazo no es sólo un múltiplo de la solución OLS. La dirección de la solución OLS se suma más fuerte a la suma $\vert \beta \vert_1$ . En este caso, sólo un $\beta_i$ es distinto de cero.
2. En la segunda imagen una cresta del politopo está tocando la esfera (en dimensiones superiores obtenemos análogos de mayor dimensión). En este caso, múltiples $\beta_i$ son distintos de cero.
3. En la tercera imagen una faceta del politopo toca la esfera . En este caso todo el $\beta_i$ son distintos de cero .

La gama de $t$ o $\lambda$ para los que tenemos el primer y tercer caso se pueden calcular fácilmente debido a su sencilla representación geométrica.

Caso 1: Sólo un $\beta_i$ no cero

La parte no nula $\beta_i$ es aquella para la que el vector asociado $x_i$ tiene el mayor valor absoluto de la covarianza con $\hat{y}$ (este es el punto del paralelótopo que más se acerca a la solución OLS). Podemos calcular el multiplicador de Lagrange $\lambda_{max}$ por debajo de la cual tenemos al menos un $\beta$ tomando la derivada con $\pm\beta_i$ (el signo depende de si aumentamos el $\beta_i$ en sentido negativo o positivo ):

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

$$\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 la $\vert \vert X^Ty \vert \vert_\infty$ mencionado en los comentarios.

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

Caso 3: Todos $\beta_i$ son distintos de cero.

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

El politopo tiene muchas facetas, con contribuciones positivas y negativas del $x_i$ . En el caso del último paso del lazo, cuando la solución del lazo se acerca a la solución del ols, entonces las contribuciones del $x_i$ debe ser definido por el signo de la solución OLS. La normal de la faceta puede definirse tomando el gradiente de la función $\vert \vert \beta(r) \vert \vert_1 $ el valor de la suma de beta en el punto $r$ que es:

$$ 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{\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 ( $A^TB^T = [BA]^T$ ) y la distribución de paréntesis se convierte en

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

normalizamos esta dirección:

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

Para encontrar el $\lambda_{min}$ por debajo del cual todos los coeficientes son distintos de cero. Sólo tenemos que calcular desde la solución OLS hasta el punto en el que uno de los coeficientes es cero,

$$ 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 $\lambda_{max}$ ). Utilizamos que para una función cuadrática tenemos $q'(x) = 2 q(1) x$ :

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

Imágenes

un punto del politopo está tocando la esfera, un solo $\beta_i$ es distinto de cero:

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

una faceta del politopo está tocando la esfera, todas $\beta_i$ son distintos de cero:

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: estas 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

(aviso de edición: esta respuesta se ha editado mucho. He borrado partes antiguas. Pero dejé esta respuesta del 14 de julio que contiene una buena explicación de la separación de $y$ , $\epsilon$ y $\hat{y}$ . Los problemas que se planteaban en esta respuesta inicial se han resuelto. El paso final del algoritmo LARS es fácil de encontrar, es la normal del politopo definido por el signo del $\hat{\beta}$ ) #RESPUESTA JULIO 14 2017#

para $\lambda < \lambda_{max}$ tenemos al menos un coeficiente distinto de cero (y sobre todo son cero)

para $\lambda < \lambda_{min}$ tenemos todo coeficientes no nulos (y por encima al menos un coeficiente es cero)

encontrar $\lambda_{max}$

Puede utilizar los siguientes pasos para determinar $\lambda_{max}$ (y esta técnica también ayudará para $\lambda_{min}$ aunque un poco más difícil). Para $\lambda>\lambda_{max}$ tenemos $\hat{\beta}^\lambda$ = 0, ya que la penalización en el término $\lambda \vert \vert \beta \vert \vert_1$ será demasiado grande, y un aumento de $\beta$ no reduce $(1/2n) \vert \vert y-X \beta \vert \vert ^2_2$ suficientemente para optimizar la siguiente expresión

(1) \begin{equation}\frac{1}{2n} \vert \vert y-X \beta \vert \vert ^2_2 + \lambda \vert \vert \beta \vert \vert_1 \end{equation}

La idea básica es que en algún nivel de $\lambda$ el aumento de $\vert \vert \beta \vert \vert_1$ hará que el término $(1/2n) \vert \vert y-X \beta \vert \vert ^2_2$ a disminuciones más que el término $\lambda \vert \vert \beta \vert \vert_1$ aumenta. Este punto en el que los términos son iguales se puede calcular exactamente y en este punto la expresión (1) puede ser optimizada por un aumento de $\beta$ y este es el punto por debajo del cual algunos términos de $\beta$ son distintos de cero.

• Determinar el ángulo, o vector unitario $\beta_0$ a lo largo de la cual la suma $(y - X\beta)^2$ disminuiría más. (de la misma manera que el primer paso del algoritmo LARS explicado en el muy buen artículo referenciado por chRrr) Esto se relacionaría con la(s) variable(s) $x_i$ que más se correlaciona con $y$ .
• Calcule la tasa de cambio a la que cambia la suma de cuadrados del error si aumenta la longitud del vector predicho $\hat{y}$

$r_1= \frac{1}{2n} \frac{\partial\sum{(y - X\beta_0\cdot s)^2}}{\partial s}$

esto está relacionado con el ángulo entre $\vec{\beta_0}$ y $\vec{y}$ . El cambio del cuadrado de la longitud del término de error $y_{err}$ será igual a

$\frac{\partial y_{err}^2}{\partial \vert \vert \beta_0 \vert \vert _1} = 2 y_{err} \frac{\partial y_{err}}{\partial \vert \vert \beta_0 \vert \vert _1} = 2 \vert \vert y \vert \vert _2 \vert \vert X\beta_0 \vert \vert _2 cor(\beta_0,y)$

El término $\vert \vert X\beta_0 \vert \vert _2 cor(\beta_0,y)$ es lo que la longitud $y_{err}$ cambia según el coeficiente $\beta_0$ cambios y esto incluye una multiplicación con $X$ (ya que el mayor $X$ mayor será el cambio al cambiar el coeficiente) y una multiplicación con la correlación (ya que sólo la parte de la proyección reduce la longitud del vector de error).

---

Entonces $\lambda_{max}$ es igual a esta tasa de cambio y $\lambda_{max} = \frac{1}{2n} \frac{\partial\sum{(y - X\beta_0\cdot s)^2}}{\partial s} = \frac{1}{2n} 2 \vert \vert y \vert \vert _2 \vert \vert x \vert \vert _2 corr(\beta_0,y) = \frac{1}{n} \vert \vert X\beta_0 \cdot y \vert \vert _2 $

Donde $\beta_0$ es el vector unitario que corresponde al ángulo en el primer paso del algoritmo LARS.

Si $k$ es el número de vectores que comparten la máxima correlación entonces tenemos

$\lambda_{max} = \frac{\sqrt{k}}{n} \vert \vert X^T y\vert \vert_\infty $

---

En otras palabras. LARS le da la disminución inicial de la SSE a medida que aumenta la longitud del vector $\beta$ y esto es entonces igual a su $\lambda_{max}$

---

Ejemplo gráfico

La siguiente imagen explica el concepto de cómo el algoritmo LARS puede ayudar a encontrar $\lambda_{max}$ . (y también pistas de cómo podemos encontrar $\lambda_{min}$ )

• En la imagen vemos esquemáticamente el ajuste del vector $y$ por los vectores $x_1$ y $x_2$ .
• Los vectores grises punteados representan la solución OLS con $y_{\perp}$ el parte de $y$ que es perpendicular (el error) al tramo de los vectores $x_1$ y $x_2$ (y el vector perpendicular es la distancia más corta y la menor suma de cuadrados)
• las líneas grises son isolíneas para las que $\vert \vert \beta \vert \vert_1$ es constante
• Los vectores $\beta_0$ y $\beta_1$ representan el camino que se sigue en una regresión LARS.
• las líneas azules y verdes son los vectores que representan el término de error al seguir el algoritmo de regresión LARS. la longitud de estas líneas es el SSE y cuando alcanzan el vector perpendicular $y_{\perp}$ tiene la menor suma de cuadrados

Ahora, inicialmente la trayectoria se sigue a lo largo del vector $x_i$ que tiene la mayor correlación con $y$ . Para este vector el cambio del $\sqrt{SSE}$ en función del cambio de $\vert \vert \beta \vert \vert$ es mayor (es decir, igual a la correlación de ese vector $x_i$ y $y$ ). Mientras sigues el camino este cambio de $\sqrt{SSE}$ / $\vert \vert \beta \vert \vert$ disminuye hasta que un camino a lo largo de una combinación de dos vectores se vuelve más eficiente, y así sucesivamente. Obsérvese que la relación del cambio $\sqrt{SSE}$ y cambiar $\vert \vert \beta \vert \vert$ es una función monótonamente decreciente. Por lo tanto, la solución para $\lambda_{max}$ debe estar en el origen.

encontrar $\lambda_{min} $

La ilustración anterior también muestra cómo podemos encontrar $\lambda_{min}$ el punto en el que todos los coeficientes son distintos de cero. Esto ocurre en el último paso del procedimiento LARS.

Podemos encontrar estos puntos con pasos similares. Podemos determinar el ángulo del último escalón y del anteúltimo y determinar el punto en el que estos escalones pasan de uno a otro. Este punto se utiliza entonces para calcular $\lambda_{min}$ .

La expresión es un poco más complicada ya que no se calcula partiendo de cero. En realidad, la solución puede no existir. El vector a lo largo del cual se realiza el último paso está en la dirección de $X^T \cdot sign$ en el que $sign$ es un vector con 1's y -1's dependiendo de la dirección del cambio del coeficiente en el último paso. Esta dirección se puede calcular si se conoce el resultado del anteúltimo paso (y se podría conseguir iterando hacia el primer paso, pero un cálculo tan grande no parece ser lo que queremos). No encuentro si podemos ver directamente cual es el signo del cambio de los coeficientes en el último paso.

Obsérvese que podemos determinar más fácilmente el punto $\lambda_{opt}$ para lo cual $\beta^\lambda$ es igual a la solución OLS. En la imagen esto está relacionado con el cambio del vector $y_{\perp}$ a medida que avanzamos por la pendiente $\hat{\beta_n}$ (esto podría ser más práctico de calcular)

problemas con los cambios de signo

La solución LARS se acerca a la solución LASSO. La diferencia está en el número de pasos. En el método anterior se averiguaría la dirección del último cambio y se volvería a partir de la solución OLS hasta que un coeficiente se hiciera cero. Se produce un problema si este punto no es un punto en el que se añade un coeficiente al conjunto de coeficientes activos. También podría ser un cambio de signo y las soluciones LASSO y LARS podrían diferir en estos puntos.

Answer 2

El lazo es especialmente útil cuando $p>n$ es decir, más parámetros que el tamaño de la muestra.

Si $p>n$ y $X$ tiene distribuciones continuas, la estimación por mínimos cuadrados $\hat\beta^{LS}$ que minimiza $\min_{b\in R^p} \|y-Xb\|^2$ no es único (el subespacio afín de soluciones por mínimos cuadrados es exactamente $\hat\beta^{LS}_0 + \ker(X)$ para cualquier solución específica $\hat\beta^{LS}_0$ y $\ker(X)$ tiene una dimensión mínima de $p-n$ ).

Además, existe una solución de mínimos cuadrados con un máximo de $n$ coordenadas no nulas y al menos $p-n$ coordenadas cero. Para ver esto, escriba $X$ por bloque como $[X_n|X_{p-n}]$ donde $X_n$ es un cuadrado $n\times n$ matriz. Si $X$ tiene una distribución continua, entonces $X_n$ es invertible con probabilidad uno y $\hat b$ en $R^p$ definido por $X_n^{-1}y$ en la primera $n$ coordenadas y 0 en la última $(p-n)$ coordenadas es una solución de mínimos cuadrados con al menos $p-n$ cero entradas.

Así que con probabilidad uno, cuando $p>n$ , su $\lambda_{min}$ es igual a 0.