¿Por qué la norma L1 para modelos escasos

Question

Estoy leyendo los libros sobre regresión lineal. Hay algunas frases sobre la norma L1 y L2. Las conozco, pero no entiendo por qué la norma L1 para modelos escasos. ¿Alguien puede dar una explicación simple?

Gracias

Answer 1

Considere el vector $ \vec {x}=(1, \varepsilon ) \in\mathbb {R}^2$ donde $ \varepsilon >0$ es pequeño. El $l_1$ y $l_2$ normas de $ \vec {x}$ respectivamente, están dadas por

$$|| \vec {x}||_1 = 1+ \varepsilon ,\ \ || \vec {x}||_2^2 = 1+ \varepsilon ^2$$

Ahora digamos que, como parte de algún procedimiento de regularización, vamos a reducir la magnitud de uno de los elementos de $ \vec {x}$ por $ \delta\leq\varepsilon $ . Si cambiamos $x_1$ a $1- \delta $ las normas resultantes son

$$|| \vec {x}-( \delta ,0)||_1 = 1- \delta + \varepsilon ,\ \ || \vec {x}-( \delta ,0)||_2^2 = 1-2 \delta + \delta ^2+ \varepsilon ^2$$

Por otro lado, reducir $x_2$ por $ \delta $ da normas

$$|| \vec {x}-(0, \delta )||_1 = 1- \delta + \varepsilon ,\ \ || \vec {x}-(0, \delta )||_2^2 = 1-2 \varepsilon\delta + \delta ^2+ \varepsilon ^2$$

Lo que hay que notar aquí es que, para un $l_2$ pena, regularizando el término más amplio $x_1$ resulta en una reducción mucho mayor de la norma que hacerlo al término más pequeño $x_2 \approx 0$ . Para el $l_1$ Sin embargo, la reducción es la misma. Así, cuando se penaliza a un modelo que utiliza el $l_2$ es altamente improbable que algo se ponga a cero, ya que la reducción de la norma al pasar de $ \varepsilon $ a $0$ es casi inexistente cuando $ \varepsilon $ es pequeño. Por otro lado, la reducción de $l_1$ La norma es siempre igual a $ \delta $ independientemente de la cantidad que se penalice.

Otra forma de verlo: no es tanto que $l_1$ las penalizaciones fomentan la escasez, pero eso $l_2$ las penas en algún sentido desalentar la escasez al producir rendimientos decrecientes a medida que los elementos se acercan a cero.

Answer 2

Con un modelo disperso, pensamos en un modelo en el que muchos de los pesos son 0. Por lo tanto, razonemos sobre cómo es más probable que la regularización L1 cree pesos 0.

Considere un modelo que consiste en los pesos $(w_1, w_2, \dots , w_m)$ .

Con la regularización L1, se penaliza al modelo con una función de pérdida $L_1(w)$ = $ \Sigma_i |w_i|$ .

Con la regularización L2, se penaliza al modelo con una función de pérdida $L_2(w)$ = $ \frac {1}{2} \Sigma_i w_i^2$

Si se utiliza el descenso de gradiente, hará que los pesos cambien iterativamente en la dirección opuesta al gradiente con un tamaño de paso $ \eta $ . Veamos los gradientes:

$ \frac {dL_1(w)}{dw} = sign(w)$ donde $sign(w) = ( \frac {w_1}{|w_1|}, \frac {w_1}{|w_1|}, \dots , \frac {w_1}{|w_m|})$

$ \frac {dL_2(w)}{dw} = w$

Si trazamos la función de pérdida y es derivada para un modelo que consiste en un solo parámetro, se ve así para L1:

Y así para la L2:

Fíjese que para $L_1$ el gradiente es 1 o -1, excepto cuando $w_1 = 0$ . Eso significa que la regularización L1 moverá cualquier peso hacia 0 con el mismo tamaño de paso, sin importar el valor del peso. En contraste, puedes ver que el $L_2$ El gradiente disminuye linealmente hacia 0 a medida que el peso se acerca a 0. Por lo tanto, la regularización de L2 también moverá cualquier peso hacia 0, pero tomará pasos cada vez más pequeños a medida que el peso se acerque a 0.

Intenta imaginar que empiezas con una modelo con $w_1 = 5$ y usando $ \eta = \frac {1}{2}$ . En la siguiente imagen, se puede ver cómo el descenso del gradiente usando la regularización L1 hace que 10 de las actualizaciones $w_1 := w_1 - \eta \cdot \frac {dL_1(w)}{dw} = w_1 - 0.5 \cdot 1$ hasta llegar a un modelo con $w_1 = 0$ :

En contraste, con la regularización L2 donde $ \eta = \frac {1}{2}$ el gradiente es $w_1$ causando que cada paso sea sólo la mitad del camino hacia el 0. Es decir, hacemos la actualización $w_1 := w_1 - \eta \cdot \frac {dL_1(w)}{dw} = w_1 - 0.5 \cdot w_1$ Por lo tanto, el modelo nunca alcanza un peso de 0, independientemente de cuántos pasos demos:

Obsérvese que la regularización de L2 puede hacer que un peso llegue a cero si el tamaño del paso $ \eta $ es tan alta que llega a cero o más allá en un solo paso. Sin embargo, la función de pérdida también consistirá en un término que mide el error del modelo con respecto a los pesos dados, y ese término también afectará al gradiente y por lo tanto al cambio de los pesos. Sin embargo, lo que se muestra en este ejemplo es cómo los dos tipos de regularización contribuyen a un cambio en los pesos.

Answer 3

Echa un vistazo a la figura 3.11 (página 71) de Los elementos del aprendizaje estadístico . Muestra la posición de un $ \hat \beta $ que minimiza la función de error al cuadrado, las elipses que muestran los niveles de la función de error al cuadrado, y donde están las $ \hat \beta $ sujeto a restricciones $ \ell_1 ( \hat \beta ) < t$ y $ \ell_2 ( \hat \beta ) < t$ .

Esto le permitirá entender muy geométricamente que sujeto a la $ \ell_1 $ de la restricción, obtienes algunos componentes nulos. Esto es básicamente porque la $ \ell_1 $ pelota $\{ x : \ell_1 (x) \le 1\}$ tiene "bordes" en los ejes.

En general, este libro es una buena referencia sobre este tema: riguroso y bien ilustrado, grandes explicaciones.

Answer 4

Básicamente, la escasez es inducida por los bordes afilados que se encuentran en el eje de una isosuperficie. La mejor explicación gráfica que he encontrado hasta ahora está en este vídeo:

https://www.youtube.com/watch?v=sO4ZirJh9ds