Quanto è ragionevole un sistema per tentare di eseguire una regressione lineare?Qual è il BigO della regressione lineare?
In particolare: ho un sistema con ~ 300K punti campione e ~ 1200 termini lineari. Questo è computazionalmente fattibile?
È possibile esprimere questo come un'equazione matriciale:
dove la matrice è 
300K righe e 1200 colonne, il coefficiente vettore 
è 1200x1, e RHS vettore 
è 1200x1.
Se si moltiplicano entrambi i lati per la trasposizione della matrice 
, si dispone di un sistema di equazioni per gli incogniti che è 1200x1200. Puoi utilizzare la decomposizione LU o qualsiasi altro algoritmo che desideri risolvere per i coefficienti. (Questo è ciò che sta facendo il minimo dei quadrati.)
Quindi il comportamento del Big-O è qualcosa come O (m m n), dove m = 300K e n = 1200. Sarai responsabile della trasposizione, il moltiplicazione della matrice, la decomposizione della LU e la sostituzione del forward-back per ottenere i coefficienti.
Quindi, se sto leggendo correttamente (e IIRC), la generazione di A sarà O (n * m) ~ = O (m^2) (nel mio caso 'n/m = C') e la moltiplicazione essere O (n * n * m) ~ = O (n^3) e l'inversione sarà O (n^3) Ora solo per capire il termine costante. – BCS
La regressione lineare è calcolata come (X'X)^- 1 X'Y.
Se X è un (nxk) matrice:
(X' X) richiederà O (n * k^2) tempo e produce un (kxk) matrice
L'inversione della matrice di un (kxk) matrice richiede O (k^3) tempo
(X' Y) richiederà O (n * k^2) tempo e produce un (kxk) matrice
La moltiplicazione matrice finale di due (k x k) prende matrici O (k^3) Tempo
Così il Big-O tempo di esecuzione è O (k^2 * (n + k)).
Consulta anche: http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra
Se si ottiene fantasia sembra che è possibile ottenere il tempo fino a O (k^2 * (n + k^0,376)) con l'algoritmo Coppersmith-Winograd.
L'algoritmo di Coppersmith-Winograd non è praticamente utilizzabile, poiché il coefficiente è così grande che richiede una matrice così grande da iniziare a vedere il beneficio dell'efficienza asintotica che non è realistico: https://en.m.wikipedia.org/wiki/ Coppersmith-Winograd_algorithm – JStrahl
La regressione lineare del modello forma chiusa viene calcolata come segue: derivato di
RSS (W) = -2H^t (y-HW)
Così, abbiamo risolvere per
-2H^t (y-HW) = 0
Quindi, il valore di W è
W = (H^t H)^- 1 H^2 y
dove: W: è il vettore dei pesi attesi H: è la matrice caratteristiche N * D dove N è il numero di osservazioni, e D è il numero di funzioni y: è il valore reale
Poi, il complexit y di
H^t H è n D^2
La complessità della trasposizione è D^3
Quindi, la complessità di
(H^t H)^-1 is n * D^2 + D^3
Non è solo la complessità di questa implementazione? C'è qualche prova che quella sia l'implementazione più veloce? – BCS
Quale algoritmo? Minimi quadrati? –
Sì, minimi quadrati. Ero inconsapevole che ce n'era un altro. – BCS