Was ist der Bigo der linearen Regression?

Question

Wie groß ist es vernünftig, zu versuchen, eine lineare Regression aufzunehmen?

Insbesondere: Ich habe ein System mit ~ 300.000 Beispielpunkten und ~ 1200 linearen Begriffen. Ist das rechnerisch machbar?

Answer 1

Sie können dies als Matrixgleichung ausdrücken:

wo die Matrix IS 300K Zeilen und 1200 Spalten, der Koeffizientenvektor ist 1200x1 und der RHS -Vektor ist 1200x1.

Wenn Sie beide Seiten mit der Transponierung der Matrix multiplizieren , Sie haben ein Gleichungssystem für die Unbekannten, die 1200 x 1200 sind. Sie können die LU -Zerlegung oder einen anderen Algorithmus verwenden, den Sie für die Koeffizienten lösen möchten. (Dies ist das, was die geringsten Quadrate tun.)

Das Big-O-Verhalten ist also so etwas wie o (m)mn), wobei M = 300K und n = 1200. Sie für die Transponierung, die Matrixmultiplikation, die LU-Zersetzung und die Vorwärts-Rücken-Substitution berücksichtigen würden, um die Koeffizienten zu erhalten.

Answer 2

Die lineare Regression wird als (x'x)^-1 x'y berechnet.

Wenn x eine (NXK) Matrix ist:

1. (X 'x) nimmt o (n*k^2) Zeit und erzeugt eine (kxk) Matrix

2. Die Matrixinversion einer (kxk) Matrix dauert die Zeit

3. (X 'y) nimmt o (n*k^2) Zeit und erzeugt eine (kxk) Matrix

4. Die endgültige Matrixmultiplikation von zwei (KXK) Matrizen dauert die Zeit

Die Big-O-Laufzeit ist also o (k^2*(n + k)).

Siehe auch: http://en.wikipedia.org/wiki/computational_complexity_of_mathematical_operations#matrix_algebra

Wenn Sie Lust bekommen, sieht es so aus, als ob Sie die Zeit bis O (k^2*(n+k^0,376)) mit dem Coppersmith -Winograd -Algorithmus bekommen können.

Answer 3

Die lineare Regression des Modells geschlossene Form wird wie folgt berechnet: Ableitung von

RSS (W) = -2H^T (y -HW)

Also lösen wir für

-2H^t (y-hw) = 0

Dann ist der W -Wert

W = (h^t h)^-1 H^2 y

wo:W: Ist der Vektor der erwarteten GewichteH: Ist die Merkmale Matrix N*D, wobei n die Anzahl der Beobachtungen ist und D die Anzahl der Merkmale isty: Ist der tatsächliche Wert

Dann die Komplexität von

H^t H ist n d^2

Die Komplexität der Transponierung ist d^3

Also die Komplexität von

(H^t H)^-1 is n * D^2 + D^3