Después de tanto batallar ya encontramos el arreglo de esta pregunta que tantos lectores de nuestro sitio web tienen. Si quieres compartir algún detalle no dejes de aportar tu comentario.
Solución:
Me tomó una hora ayer para finalmente entender esto. Escribí un blog muy detallado para explicarlo.
https://medium.com/@shiyan/l1-norm-regularization-and-sparsity-explained-for-dummies-5b0e4be3938a#.nhy58osj5
Estoy publicando una versión simple aquí.
Ayer, cuando pensé por primera vez en esto, usé dos vectores de ejemplo [0.1, 0.1] y [1000, 0]. El primer vector obviamente no es disperso, pero tiene la norma L1 más pequeña. Es por eso que estaba confundido, porque mirar solo la norma L1 no hará que esta idea sea comprensible. Tengo que considerar toda la función de pérdida como un todo.
cuando está resolviendo un gran vector x con menos datos de entrenamiento. Las soluciones a x podrían ser muchas.
Aquí A es una matriz que contiene todos los datos de entrenamiento. x es el vector solución que está buscando. b es el vector etiqueta.
Cuando los datos no son suficientes y el tamaño de los parámetros de su modelo es grande, su matriz A no será lo suficientemente “alta” y su x es muy larga. Así que la ecuación anterior se verá así:
Usemos un ejemplo simple y concreto. Supongamos que queremos encontrar una línea que coincida con un conjunto de puntos en el espacio 2D. Todos sabemos que necesitas al menos 2 puntos para arreglar una línea. Pero, ¿y si los datos de entrenamiento tienen un solo punto? Entonces tendrás infinitas soluciones: cada línea que pasa por el punto es una solución. Supongamos que el punto está en [10, 5], y una línea se define como una función y = a * x + b. Entonces el problema es encontrar una solución a esta ecuación:
Dado que b = 5 – 10 * a, todos los puntos en esta línea siguiente b = 5 – 10 * a deberían ser una solución:
Pero, ¿cómo encontrar el escaso con la norma L1?
La norma L1 se define como la suma de los valores absolutos de todos los componentes de un vector. Por ejemplo, si un vector es [x, y], su norma L1 es |x| + |y|.
Ahora, si dibujamos todos los puntos que tienen una norma L1 igual a una constante c, esos puntos deberían formar algo (en rojo) como esto:
Esta forma parece un cuadrado inclinado. En el espacio de alta dimensión, será un octaedro. Observe que en esta forma roja, no todos los puntos son escasos. Solo en las puntas, los puntos son escasos. Es decir, el componente x o y de un punto es cero. Ahora, la forma de encontrar una solución dispersa es agrandar esta forma roja desde el origen dando una c cada vez mayor para “tocar” la línea de solución azul. La intuición es que lo más probable es que el punto de contacto esté en la punta de la forma. Dado que la punta es un punto disperso, la solución definida por el punto de contacto también es una solución dispersa.
Como ejemplo, en este gráfico, la forma roja crece 3 veces hasta que toca la línea azul b = 5–10 * a. El punto de contacto, como puede ver, está en la punta de la forma roja. el punto de contacto [0.5, 0] es un vector disperso. Por lo tanto, decimos que al encontrar el punto de solución con la norma L1 más pequeña (0.5) de todas las soluciones posibles (puntos en la línea azul), encontramos una solución escasa [0.5, 0] a nuestro problema. En el punto de contacto, la constante c es la norma L1 más pequeña que podría encontrar dentro de todas las soluciones posibles.
La intuición de usar la norma L1 es que la forma formada por todos los puntos cuya norma L1 es igual a una constante c tiene muchas puntas (picos) que resultan ser escasas (se encuentra en uno de los ejes del sistema de coordenadas). Ahora hacemos crecer esta forma para tocar las soluciones que encontramos para nuestro problema (generalmente una superficie o una sección transversal en gran dimensión). La probabilidad de que el punto de contacto de las 2 formas esté en una de las “puntas” o “picos” de la forma normalizada L1 es muy alta. Es por eso que desea poner la norma L1 en la fórmula de su función de pérdida, para que pueda seguir buscando una solución con una c más pequeña (en la punta “escasa” de la norma L1). (Entonces, en el caso de la función de pérdida real, esencialmente está reduciendo la forma roja para encontrar un punto de contacto, no agrandándola desde el origen).
¿La norma L1 siempre toca la solución en una punta y nos encuentra una solución escasa? No necesariamente. Supongamos que todavía queremos encontrar una línea a partir de puntos 2D, pero esta vez, los únicos datos de entrenamiento son un punto [1, 1000]. En este caso, la línea de solución b = 1000 -a es paralela a uno de los bordes de la forma norma L1:
Eventualmente se tocan en un borde, no por una punta. No solo no puede tener una solución única esta vez, sino que la mayoría de sus soluciones regularizadas aún no son escasas (aparte de los dos puntos de punta).
Pero, de nuevo, la probabilidad de tocar una punta es muy alta. Supongo que esto es aún más true para problemas del mundo real de gran dimensión. Como cuando su sistema de coordenadas tiene más ejes, su forma de norma L1 debería tener más picos o puntas. ¡Debe parecer un cactus o un erizo! no puedo imaginar
Pero, ¿es la norma L1 el mejor tipo de norma para encontrar una solución escasa? Bueno, resulta que la norma Lp cuando 0 <= p < 1 da el mejor resultado. Esto se puede explicar observando las formas de las diferentes normas:
Como puede ver, cuando p < 1, la forma es más "aterradora", con picos más afilados y emergentes. Mientras que cuando p = 2, la forma se convierte en una bola suave y no amenazante. Entonces, ¿por qué no dejar que p < 1? Eso es porque cuando p < 1, hay dificultades de cálculo.
Quizás esto esté discutiendo una situación en la que los posibles valores de los parámetros son un conjunto discreto. Si cada parámetro distinto de cero tiene un valor absoluto de al menos $epsilon$, el número de parámetros distintos de cero es como máximo $1/epsilon$ veces la norma $ell^1$ del vector de parámetros.
Reseñas y calificaciones
Puedes añadir valor a nuestra información tributando tu veteranía en las críticas.