En un problema de regresión lineal con restricción de sparsity, $P = (P_1, \cdots, P_N)^{T}$ es el vector columna de las salidas, y $D = (d_{j, k})$ es el $(N \times M)$ - matriz dimensional de entradas. La función objetivo es
$$\text{argmin}_{c \in \Bbb R^{M}} (\Vert P - Dc \Vert_2^2 + \lambda \Vert c \Vert_0)$$
en el que $\Vert c \Vert_0 = \# \{j: c_j \neq 0\}$
He aprendido que este problema es NP-difícil, pero no entiendo por qué.
Lo que pienso:
En total hay $N$ casos que debemos considerar
$$N = C(M, 1) + C(M, 2) + \cdots + C(M, M)$$ en el que $M$ es la dimensión del vector de coeficientes $c$ . $C(M, n) = \begin{pmatrix} M\\ n \end{pmatrix} = \frac{M!}{(M-n)!n!} $ .
Para cada tupla de características seleccionadas, realizamos OLS (sin tener en cuenta el regularizador) y registramos la pérdida: $$L = RMSE + \lambda \Vert c \Vert_0$$
Después de hacer $N$ de estos cálculos, podemos elegir la tupla de características que produzca el menor $L$ .
Sin embargo, no sé si el resultado obtenido es realmente la solución a la función objetivo original, ya que en primer lugar no tenemos en cuenta el efecto del regularizador.
O este algoritmo no tiene sentido, en lugar de comparar $L = RMSE + \lambda \Vert c \Vert_0$ entre tuplas de diferentes tamaños, sólo podemos comparar la $RMSE$ del conjunto de tuplas de características del mismo tamaño.
0 votos
No tengo la respuesta a tu pregunta principal, pero ten en cuenta que en el algoritmo que propones, no querrías comparar las soluciones en función de su RMSE, porque entonces siempre ganaría la solución sin coeficientes cero (es decir, con todas las variables incluidas en el modelo). Lo que quiere es compararlas en función de su coste total tal y como lo definió en la primera ecuación, es decir, incluyendo los $l_0$ pena.
0 votos
@ Ruben van Bergen ¡Gracias por señalarlo! Me preguntaba dónde está el efecto del regularizador en este algoritmo.