Si p > n, el lazo selecciona como máximo n variables

Question

Una de las motivaciones de la red elástica fue la siguiente limitación de LASSO:

En el $p > n$ el lazo selecciona como máximo n variables satura, debido a la naturaleza del problema de optimización convexo. Esto parece ser una característica limitante para un método de selección de variables. Además, el lazo no está bien definido a menos que el límite de la L1 de los coeficientes sea inferior a un valor determinado.

( http://onlinelibrary.wiley.com/doi/10.1111/j.1467-9868.2005.00503.x/full )

Tengo entendido que LASSO es un problema de programación cuadrática, pero que también puede resolverse mediante LARS o descenso de gradiente por elementos. Pero no entiendo donde en estos algoritmos me encuentro con un problema si $p > n$ donde $p$ es el número de predictores y $n$ es el tamaño de la muestra. ¿Y por qué este problema se resuelve utilizando red elástica donde aumento el problema a $p+n$ variables que supera claramente $p$ .

Answer 1

Como se ha dicho, esto no es una propiedad de un algoritmo, sino del problema de optimización. Las condiciones KKT dan básicamente que para el coeficiente $\beta_j$ para ser distinto de cero debe corresponder a una correlación fija con el residuo $|X_j^t(y-X\beta)| = \lambda$ ( $\lambda$ es el parámetro de regularización).

Tras resolver las diversas complicaciones con el valor absoluto, etc., nos queda una ecuación lineal para cada coeficiente distinto de cero. Dado que el rango de la matriz $X$ es como máximo $n$ cuando $p>n$ , éste es el número de ecuaciones que se pueden resolver y, por tanto, hay como máximo n no ceros (a menos que haya redundancias).

Por cierto, esto es cierto para cualquier función de pérdida, no sólo el lazo estándar con $L_2$ pérdida. Así que, de hecho, es una propiedad de la penalización del lazo. Hay muchos trabajos que muestran este punto de vista KKT y las conclusiones resultantes, puedo señalar nuestro trabajo: Rosset y Zhu, Piecewise Linear Regularized Solutions Paths, Annals of Stats 2007 y sus referencias.

Answer 2

Otra explicación es la siguiente: si $n < p$ el rango de la matriz de datos $X$ es como máximo $n$ por lo que la dimensión de su espacio nulo (derecho) es al menos $p - n$ . Escribe cualquier vector en este espacio nulo como $z$ . Entonces, en cualquier punto factible $\beta$ uno siempre puede moverse en este $p - n$ -espacio nulo hacia los ejes de coordenadas del $p$ -espacio ambiental dimensional, para llegar a un $\beta+z$ donde (como máximo) $n$ $\beta_j$ s son distintos de cero, y la función objetivo LASSO

$$ \|y-X(\beta+z)\|_2^2 + \lambda \|\beta+z\|_1 = \|y-X\beta\|_2^2 + \lambda \|\beta+z\|_1 < \|y-X\beta\|_2^2 + \lambda \|\beta\|_1 $$

ha disminuido.