Qual é a grande regressão linear?
-
21-09-2019 - |
Pergunta
Qual é o tamanho do sistema, é razoável tentar fazer uma regressão linear?
Especificamente: eu tenho um sistema com ~ 300 mil pontos de amostra e ~ 1200 termos lineares. Isso é computacionalmente viável?
Solução
Você pode expressar isso como uma equação da matriz:
onde a matriz são 300k linhas e 1200 colunas, o vetor de coeficiente é 1200x1 e o vetor RHS é 1200x1.
Se você multiplicar os dois lados pela transposição da matriz , você tem um sistema de equações para as incógnitas que são 1200x1200. Você pode usar a Decomposição da LU ou qualquer outro algoritmo que deseja resolver para os coeficientes. (É isso que os mínimos quadrados estão fazendo.)
Então, o comportamento Big-O é algo como O (Mmn), onde m = 300k e n = 1200. Você explicaria a transposição, a multiplicação da matriz, a decomposição da LU e a substituição de adiante para obter os coeficientes.
Outras dicas
A regressão linear é calculada como (x'x)^-1 x'y.
Se x é uma matriz (nxk):
(X 'x) leva o tempo o (n*k^2) e produz uma matriz (kxk)
A inversão da matriz de uma matriz (kxk) leva o tempo (k^3)
(X 'y) leva o tempo o (n*k^2) e produz uma matriz (kxk)
A multiplicação final da matriz de duas matrizes (KXK) leva o tempo (k^3)
Portanto, o tempo de corrida Big-O é O (K^2*(n + k)).
Veja também: http://en.wikipedia.org/wiki/computational_complexity_of_mathematical_operations#matrix_algebra
Se você se sentir sofisticado, parece que você pode ter um tempo para O (k^2*(n+k^0,376)) com o algoritmo Coppersmith -Winograd.
A regressão linear do modelo de forma fechada é calculada da seguinte forma: derivado de
Rss (w) = -2h^t (y -hw)
Então, resolvemos para
-2h^t (y-hw) = 0
Então, o valor W é
W = (h^t h)^-1 h^2 y
Onde:C: é o vetor dos pesos esperadosH: é a matriz de recursos n*d onde n é o número de observações e d é o número de recursosy: é o valor real
Então, a complexidade de
H^t h é n d^2
A complexidade da transposição é d^3
Então, a complexidade de
(H^t H)^-1 is n * D^2 + D^3