Velocidad, gastos computacionales de PCA, LASSO, red elástica

Estoy tratando de comparar la complejidad computacional / velocidad de estimación de tres grupos de métodos para la regresión lineal como se distingue en Hastie et al. "Elementos del aprendizaje estadístico" (2ª ed.), Capítulo 3:

Selección de subconjunto
Métodos de contracción
Métodos que utilizan direcciones de entrada derivadas (PCR, PLS)

La comparación puede ser muy aproximada, solo para dar una idea. Entiendo que las respuestas pueden depender de la dimensión del problema y de cómo se ajusta a la arquitectura de la computadora, por lo que para un ejemplo concreto se puede considerar un tamaño de muestra de 500 y 50 regresores candidatos. Estoy interesado principalmente en la motivación detrás de la complejidad computacional / velocidad de estimación, pero no en cuánto tiempo tomaría cierto procesador para el ejemplo dado.

machine-learning estimation feature-selection algorithms time-complexity Richard Hardy
fuente

Cuando se usa PCR o PLS, el número de componentes es un parámetro de ajuste (similar a

λ

$\lambda$ en la regresión de cresta). Por lo tanto, estos métodos también necesitarán una validación cruzada para encontrar el número óptimo de componentes. LASSO también tiene un parámetro de regularización, pero la red elástica tiene dos (red elástica = cresta + LASSO), por lo que la validación cruzada es más costosa. Además de eso, LASSO es probablemente más lento que todos los demás modelos, ya que no tiene una solución de forma cerrada.

ameba dice Reinstate Monica

¡Gracias! Su comentario sería una buena respuesta si incluyera dos detalles más: (1) qué tan costosa es una iteración de PCR y PLS en comparación con una ejecución OLS de la regresión regular; (2) cuantifique la velocidad de LASSO con mayor precisión para que sea comparable a la velocidad de la regresión regular (es polinomial, exponencial o linealmente más costosa, y por qué).

Richard Hardy

Desafortunadamente, no tengo una respuesta lista para esto, especialmente para (2). Por eso solo dejé un comentario. +1, por cierto, ¡y felicidades con 5k rep!

ameba dice Reinstate Monica

@amoeba, gracias! No podría haber esperado alcanzar los 5k cuando comencé (muy lentamente) el año pasado. ¡Pero es muy emocionante y gratificante ser un miembro activo aquí en Cross Validated!

Richard Hardy

@amoeba, creo que obtuve la complejidad de LASSO si se usa el algoritmo LARS; Actualicé mi publicación en consecuencia. Pero no leí el documento LARS con atención, por lo que no estoy completamente seguro de que sea correcto ...

Richard Hardy

Respuestas:

Grupo 1 :
La complejidad / velocidad del grupo 1. no parece demasiado difícil de determinar si se utilizan algoritmos de fuerza bruta (aunque puede haber alternativas más eficientes como el algoritmo de "saltos y límites"). Por ejemplo, la selección completa de un subconjunto requerirá regresiones para ajustarse dado un conjunto de características candidatas. Un ajuste OLS de una regresión lineal tiene la complejidad de (según esta publicación ) donde es el tamaño de la muestra. Por lo tanto, la complejidad total de la selección del subconjunto completo de fuerza bruta debe ser $2^K$ $K$ $\mathcal{O}(K^2 n)$ $n$ . $\mathcal{O}(2^K K^2 n)$

Grupo 2 :
La complejidad / velocidad del grupo 2. se discute en las secciones 3.8 y 3.9 del libro. Por ejemplo, la regresión de cresta con una penalización dada tiene la misma complejidad computacional que una regresión regular. Dado que se necesita encontrar mediante la validación cruzada, la carga computacional aumenta linealmente en el número de divisiones de datos utilizadas en la validación cruzada (por ejemplo, ). Si la cuadrícula tiene puntos, la complejidad total de la regresión de cresta con el ajuste del parámetro será . $\lambda$ $\lambda$ $S$ $\lambda$ $L$ $\lambda$ $\mathcal{O}(LSK^2 n)$
$\lambda$ $\lambda$ $\mathcal{O}(LSK^2 n)$
$\mathcal{O}(ALSK^2 n)$ $A$ $\alpha$

Grupo 3 :
I todavía echo cualquier nota de la complejidad / velocidad para el grupo 3. que consiste de principal de regresión componentes (PCR) y mínimos cuadrados parciales (PLS).

Richard Hardy
fuente

Es solo para una parte de la pregunta 2 del grupo 3 anterior (es decir, PLS), pero puede ser informativo: Srinivasan et al (2010, informe técnico; consulte https://www.umiacs.umd.edu/~balajiv/Papers/ UMD_CS_TR_Pls_Gpu.pdf ) realizó algunas mediciones en PLS utilizando el algoritmo NIPALS, indicando que la complejidad de tiempo (y espacio) de este algoritmo sería O (dN), para la extracción e incluyéndolas en diferentes modelos para a) detección de humanos en imágenes, y b ) Reconocimiento facial. Las mediciones se realizaron utilizando su propia implementación basada en GPU.

jf1
fuente