Jak duży system jest uzasadniony, aby spróbować regresji liniowej?Co to jest BigO regresji liniowej?
Konkretnie: Posiadam system z ~ 300 000 punktów pomiarowych i ~ 1200 liniowymi terminami. Czy to możliwe obliczeniowo?
można wyrazić jako równanie macierzowe:
gdzie macierz 
jest 300K 1200 wierszy i kolumn, wektor współczynnika 
jest 1200x1, a RHS wektor 
jest 1200x1.
Jeśli pomnożysz obie strony przez transponowanie macierzy 
, masz układ równań dla nieznanych, który wynosi 1200x1200. Możesz użyć dekompozycji LU lub dowolnego innego algorytmu, który chcesz rozwiązać dla współczynników. (To właśnie robi najmniejsze kwadraty).
Tak więc zachowanie Big-O jest podobne do O (m m n), gdzie m = 300K i n = 1200. Miałbyś odpowiedzialność za transpozycję, mnożenie macierzy, dekompozycja LU i zastępowanie w przód, aby uzyskać współczynniki.
Tak więc, jeśli czytam to poprawnie (i IIRC), generowanie A będzie O (n * m) ~ = O (m^2) (w moim przypadku 'n/m = C') i mnożenie będzie być O (n * n * m) ~ = O (n^3), a inwersja będzie O (n^3) Teraz tylko, aby obliczyć stały termin. – BCS
Regresja liniowa jest obliczana jako (X'X)^- 1 X'Y.
Jeżeli X jest (nxk) matrix
(X”X) wykonuje O (N * K^2) razem i tworzy (kxk) matrycę
inwersja macierzy grupy (kxk) matrycy odbywa o (K^3) czas
(X”Y) wykonuje o (n * K^2) razem i tworzy (kxk) matrycę
końcowe mnożenie macierzy z dwóch (k x k) macierzy zabierają O (k^3) czas
Tak więc czas działania Big-O wynosi O (k^2 * (n + k)).
Zobacz także: http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra
Jeśli masz fantazyjne wygląda można uzyskać czas w dół do O (k^2 * (n + k^0,376)) z algorytmem Coppersmith-Winograda.
Algorytm Coppersmith-Winograd nie jest praktycznie użyteczny, ponieważ współczynnik jest tak duży, że wymaga tak dużej matrycy, aby zacząć dostrzegać korzyści z asymptotycznej efektywności, jest nierealistyczny: https://en.m.wikipedia.org/wiki/ Coppersmith-Winograd_algorithm – JStrahl
regresji liniowej zamkniętej formie modelu jest obliczana jak następuje: pochodną
RSS (W) = -2^t (r-HW)
Tak więc, rozwiązania dla
-2H^t (HW) y = 0
Następnie wartość W jest
W = (H^T H)^- 1 H^2 y
gdzie: W: jest wektorem o oczekiwanej masie H: jest cechy matrycy N * D, gdzie N oznacza liczbę obserwacji, a d jest liczbą cech y: czy wartość rzeczywista
następnie complexit y
H^T H jest nD^2
Złożoność transponowania D^3
więc Złożoność
(H^t H)^-1 is n * D^2 + D^3
Czy to nie tylko złożoność tej implementacji? Czy istnieje dowód na to, że jest to najszybsza implementacja? – BCS
Który algorytm? Najmniej kwadraty? –
Tak, najmniejszych kwadratów. Nie wiedziałem, że jest jakakolwiek inna. – BCS