¿Qué tan grande es un sistema razonable para intentar hacer una regresión lineal?¿Cuál es el BigO de la regresión lineal?
Específicamente: Tengo un sistema con ~ 300K puntos de muestra y ~ 1200 términos lineales. ¿Es esto computacionalmente factible?
Usted puede expresar esto como una ecuación matricial:
donde la matriz 
es 300K filas y 1200 columnas, el vector de coeficiente de 
es 1200x1, y el RHS vector 
es 1200x1.
Si multiplicas ambos lados por la transposición de la matriz 
, tienes un sistema de ecuaciones para las incógnitas de 1200x1200. Puede usar la descomposición de LU o cualquier otro algoritmo que quiera resolver para los coeficientes. (Esto es lo que está haciendo mínimos cuadrados.)
lo tanto, el comportamiento de Big-O es algo así como O (m m n), donde m = n = 300 K y 1200. Se podría dar cuenta de la transposición, la la multiplicación de matrices, la descomposición de LU y la sustitución hacia atrás para obtener los coeficientes.
Entonces, si estoy leyendo eso correctamente (y IIRC), generar A será O (n * m) ~ = O (m^2) (en mi caso 'n/m = C') y la multiplicación ser O (n * n * m) ~ = O (n^3) y la inversión será O (n^3) Ahora solo para calcular el término constante. – BCS
La regresión lineal se calcula como (X'X)^- 1 X'Y.
Si X es un (nxk) matriz:
(X X') realiza (* 2 n k ^) Tiempo de O y produce un (kxk) matriz
La inversión de la matriz de un (kxk) matriz toma O (k^3) tiempo
(X' y) toma (2 n * k ^) tiempo de O y produce un (kxk) matriz
La multiplicación matriz final de dos (k x k) matrices toma O (3) tiempo k^
Así que el Big-O tiempo de ejecución es O (k^2 * (n + k)).
Consulte también: http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra
Si conseguir la suposición parece que se puede obtener el tiempo de inactividad a O (k^2 * (n + k^0.376)) con el algoritmo Calderero-Winograd.
El algoritmo de Coppersmith-Winograd no es utilizable en la práctica, ya que el coeficiente es tan grande que requiere una matriz tan grande para comenzar a ver el beneficio de la eficiencia asintótica que no es realista: https://en.m.wikipedia.org/wiki/ Coppersmith-Winograd_algorithm – JStrahl
La regresión lineal de forma cerrada modelo se calcula como sigue: derivado de
RSS (W) = -2H^T (Y-HW)
Así, resolvemos para
-2H^T (Y-HW) = 0
A continuación, el valor de W es
W = (H^t H)^- 1 H^2 y
donde: W: es el vector de pesos esperados H: es la características matriz de N * D donde N es el número de observaciones, y D es el número de características y: es el valor real
Entonces, el complexit y de
H^t H es n D^2
La complejidad de la transpuesta es D^3
Así, la complejidad de
(H^t H)^-1 is n * D^2 + D^3
¿No es solo la complejidad de esa implementación? ¿Hay alguna prueba de que esa es la implementación más rápida? – BCS
¿Qué algoritmo? Mínimos cuadrados? –
Sí, mínimos cuadrados. No sabía que había otro. – BCS