Regularización que induce a la dispersión para matrices estocásticas

Question

Es bien sabido (por ejemplo, en el campo de la detección por compresión) que el $L_1$ es "inductora de escasez", en el sentido de que si minimizamos la función (para una matriz fija $A$ y el vector $\vec{b}$ ) $$f_{A,\vec{b}}(\vec{x})=\|A\vec{x}-\vec{b}\|_2^2+\lambda\|\vec{x}\|_1$$ para que sea lo suficientemente grande $\lambda>0$ , es probable que tengamos muchas opciones de $A$ , $\vec{b}$ y $\lambda$ para tener muchas entradas exactamente nulas en el $\vec{x}$ .

Pero si minimizamos $f_{A,\vec{b}}$ con la condición de que las entradas de $\vec{x}$ son positivos y suman $1$ entonces el $L_1$ no tiene ningún efecto (porque $\|\vec{x}\|_1=1$ por decreto). ¿Existe un análogo $L_1$ -regularizador que funciona en este caso para fomentar que la $\vec{x}$ ¿es escaso?

Answer 1

Un método general para crear soluciones dispersas es a través de la estimación MAP con una media normal cero a priori con una varianza desconocida.

$$p(x_i|\sigma_i^2)\sim N(0,\sigma_i^2)$$

Si a continuación se asigna un prior a $\sigma_i^2$ que tiene un modo en cero, entonces el modo posterior suele ser escaso. El $L_1$ surge de este enfoque tomando una distribución de mezcla exponencial.

$$p(\sigma_i^2|\lambda)\sim Expo\left(\frac{\lambda^2}{2}\right)$$

Entonces usted obtiene

$$\log[p(x_i|\lambda)]=-\lambda | x_i|+\log\left[\frac{\lambda}{2}\right]$$

Algunas alternativas son el doble pareto generalizado, el medio cauchy, el beta invertido. En cierto sentido son mejores que el lazo porque no reducen los valores grandes. De hecho, estoy bastante seguro de que el pareto doble generalizado puede escribirse como una mezcla de exponenciales. Es decir, escribimos $\lambda=\lambda_i$ y luego colocar una gamma previa $p(\lambda_i|\alpha\beta)$ . Lo conseguimos:

$$p(x_i|\alpha\beta)=\frac{\alpha}{2\beta}\left(1+\frac{|x_i|}{\beta}\right)^{-(\alpha+1)}$$

Tenga en cuenta que he incluido constantes de normalización, ya que ayudan a elegir buenos parámetros globales. Ahora, si aplicamos la restricción de rango, tenemos un problema más complicado, ya que tenemos que renormalizar sobre el simplex.

Otra característica genérica de las penalizaciones que inducen a la dispersión es que no son diferenciables en cero. Normalmente esto se debe a que los límites izquierdo y derecho son de signo contrario.

Esto se basa en el brillante trabajo de Nicolas Polson y James Scott sobre las representaciones de mezclas de varianzas que utilizan para desarrollar TIRLS - una extensión masiva de los mínimos cuadrados a una clase muy grande de combinaciones de pérdidas-penalidades.

Como alternativa se podría utilizar una prioridad definida en el simplex, pero que tenga las modas de las distribuciones marginales en cero. Un ejemplo es la distribución dirichlet con todos los parámetros entre 0 y 1. La penalización implícita sería así:

$$-\sum_{i=1}^{n-1}(a_i-1)\log(x_i) - (a_n-1)\log(1-\sum_{i=1}^{n-1}x_i)$$

Dónde $0<a_i<1$ . Sin embargo, habría que tener cuidado al optimizar numéricamente, ya que la penalización presenta singularidades. Un proceso de estimación más robusto es utilizar la media posterior. Aunque se pierda la dispersión exacta, se obtendrán muchas medias posteriores cercanas a cero.

Answer 2

La premisa de la pregunta es correcta sólo en parte. Si bien es cierto que el $L_1$ -norma es sólo una constante bajo la restricción, el problema de optimización de la restricción podría muy bien tener una solución dispersa.

Sin embargo, la solución no se ve afectada por la elección de $\lambda$ por lo que o bien hay una solución dispersa o no. Otra cuestión es cómo encontrar realmente la solución. Por supuesto, se puede utilizar un optimizador cuadrático estándar con restricciones lineales, pero los algoritmos populares de descenso de coordenadas no se pueden utilizar sin más.

Una sugerencia podría ser optimizar bajo una restricción de positividad solamente, para diferentes $\lambda$ y luego renormalizar la solución para tener $L_1$ -norma 1. Un algoritmo de descenso de coordenadas debería, creo, ser fácilmente modificable para calcular la solución bajo una restricción de positividad.

Answer 3

Dos opciones:

1. Utilice un $L_0$ pena de $\vec x$ . El inconveniente obvio es que esto no es convexo y por lo tanto es difícil de optimizar.
2. Reparametrizar, $x_i = \frac{\exp(w_i)}{\sum_j \exp(w_j)}$ y utilizar una penalización sobre el nuevo vector de parámetros (natural), $\|\vec w\|$ . Esto fomentará que los eventos sean igualmente probables, a menos que haya una buena razón para que no lo sean.

Answer 4

Se me ocurren tres métodos.

• Método bayesiano: introducir una distribución a priori de media cero y utilizar la verosimilitud de tipo II para estimar los parámetros y los hiperparámetros.

• Utilice $\Vert\cdot\Vert_{\infty}$ como regularización. Sin embargo, esto no es diferenciable. Se puede utilizar una norma de alto orden para aproximarla.

• Utilice $-\sum_{i=1}\log x_i$ .

De hecho, el primer y el tercer método son el mismo.