Wie groß ist ein System, um eine lineare Regression zu versuchen?Was ist der BigO der linearen Regression?
Konkret: Ich habe ein System mit ~ 300K Sample Points und ~ 1200 linearen Begriffen. Ist das rechnerisch machbar?
Sie können dies als eine Matrixgleichung ausdrücken:
wobei die Matrix 
300K Zeilen und 1200 Spalten ist, der Koeffizientenvektor 
1200x1 ist und der RHS-Vektor 
ist 1200x1.
Wenn Sie beide Seiten mit der Transponierten der Matrix 
multiplizieren, haben Sie ein System von Gleichungen für die Unbekannten, die 1200x1200 ist. Sie können die LU-Zerlegung oder einen anderen Algorithmus verwenden, den Sie für die Koeffizienten lösen möchten. (Dies ist, was die kleinsten Quadrate tut.)
So ist das Big-O-Verhalten so etwas wie O (m m n), wo m = 300K und n = 1200. Sie würden für die transponieren, die Matrixmultiplikation, die LU-Zerlegung und die Forward-Back-Substitution, um die Koeffizienten zu erhalten.
Also, wenn ich das richtig lese (und IIRC), wird die Erzeugung von A O (n * m) ~ = O (m^2) sein (in meinem Fall 'n/m = C') und die Multiplikation wird Sei O (n * n * m) ~ = O (n^3) und die Inversion wird O (n^3) sein, nur um den konstanten Term herauszufinden. – BCS
Die lineare Regression wird berechnet als (X'X)^- 1 X'Y.
Wenn X eine (n × k) -Matrix ist:
(X‘X) nimmt O (n * k^2) Zeit und erzeugt eine (kxk) -Matrix
die Matrix Inversion ein (kxk) -Matrix O (k^3) Zeit
(X‘Y) nimmt O (n * k^2) Zeit und erzeugt ein (kxk) -Matrix
Die endgültige Matrixmultiplikation braucht von zwei (k x k) Matrizen O nehmen (k^3) Zeit
So ist das Big-O Zeit läuft, ist O (k^2 * (n + k)).
Siehe auch: http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra
Wenn Sie Lust bekommen es sieht aus wie Sie die Zeit bis zu O (k^2 * (n + k^0,376)) mit dem Kupferschmied-Winograd-Algorithmus erhalten.
Der Coppersmith-Winograd-Algorithmus ist praktisch nicht anwendbar, da der Koeffizient so groß ist, dass er eine Matrix benötigt, die so groß ist, dass man den Nutzen der asymptotischen Effizienz sehen kann, was unrealistisch ist: https://en.m.wikipedia.org/wiki/ Coppersmith-Winograd_algorithm – JStrahl
Die lineare Regression von geschlossener Form-Modell wird wie folgt berechnet: Derivat von
RSS (W) = -2H^t (y-HW)
So wir lösen für
-2H^t (y-HW) = 0
Dann wird der W-Wert
W = (H^t H)^- 1 H^2 y
wobei: W: der Vektor der erwarteten Gewichte H: ist die Merkmale Matrix N * D, wobei N die Anzahl von Beobachtungen ist, und D ist die Anzahl der Funktionen y: ist der Istwert
Dann wird die complexit y von
H^t H ist, n D^2
Die Komplexität der Transponierten ist D^3
So ist die Komplexität der
(H^t H)^-1 is n * D^2 + D^3
Ist das nicht nur die Komplexität dieser Implementierung? Gibt es einen Beweis dafür, dass dies die schnellste Implementierung ist? – BCS
Welcher Algorithmus? Kleinsten Quadrate? –
Ja, kleinste Quadrate. Mir war nicht bewusst, dass da noch etwas anderes war. – BCS