¿Por qué la selección hacia adelante solo requiere $O(p^2)$ llamadas al algoritmo de aprendizaje?

Question

En http://cs229.stanford.edu/notes/cs229-notes-all/cs229-notes5.pdf pg 5, se indica que la búsqueda hacia adelante toma $O(p^2)$ (nota que las notas utilizan $n$ en lugar de $p$ para el número de variables independientes).

¿No es en realidad el número de llamadas $O(2^p \cdot k)$? Se consideran todos los posibles subconjuntos de variables independientes en la búsqueda hacia adelante, de los cuales hay $2^p$. Para cada subconjunto se realiza una validación k-fold, por lo que $k$ llamadas de aprendizaje para cada subconjunto.

¿Cómo es que es cuadrático en lugar de exponencial?

Answer 1

En el procedimiento de selección hacia adelante descrito, las características se dividen en conjuntos seleccionados y candidatos. Al principio, el conjunto seleccionado está vacío y todas las $p$ características son candidatos. En cada etapa, cada característica candidata se agrega provisionalmente como una característica de prueba adicional, y se elige la mejor para mantenerla.

Por lo tanto, 1 nueva característica se elimina del conjunto de candidatos después de cada iteración. Esto significa que la primera iteración prueba $p$ candidatos, la segunda $p-1$, etc. Y $p + (p-1) + \ldots + 2 + 1 = O[p^2]$.

Una vez que una característica se agrega al conjunto seleccionado, nunca se elimina en iteraciones posteriores. Por lo tanto, el procedimiento no explora todos los subconjuntos de características. Más bien, es una heurística ávida, sin garantías de optimalidad. (Creo que por eso técnicas como LASSO se han vuelto más populares para la selección de características.)