Regressão linear online eficiente

53

Estou analisando alguns dados nos quais gostaria de executar uma regressão linear comum, mas isso não é possível, pois estou lidando com uma configuração on-line com um fluxo contínuo de dados de entrada (que rapidamente se tornará muito grande para memória) e precisa para atualizar estimativas de parâmetros enquanto isso estiver sendo consumido. ou seja, não posso simplesmente carregar tudo na memória e executar regressão linear em todo o conjunto de dados.

Estou assumindo um modelo de regressão multivariada linear simples, ou seja

y = UMA x + b + e

$\mathbf y = \mathbf A\mathbf x + \mathbf b + \mathbf e$

Qual é o melhor algoritmo para criar uma estimativa de atualização contínua dos parâmetros de regressão linear $\mathbf A$ e $\mathbf b$ ?

Idealmente:

Eu gostaria de um algoritmo com maior complexidade de espaço e tempo $\mathcal O(N\cdot M)$ por atualização, em que $N$ é a dimensionalidade da variável independente ( $\mathbf x$ ) e $M$ é a dimensionalidade da variável dependente ( $\mathbf y$ ).
Gostaria de poder especificar algum parâmetro para determinar quanto os parâmetros são atualizados por cada nova amostra, por exemplo, 0,000001 significaria que a próxima amostra forneceria um milionésimo da estimativa de parâmetro. Isso daria algum tipo de decaimento exponencial para o efeito de amostras no passado distante.

time-series regression algorithms real-time Mikera
fonte

2

Procure (1) regressão linear flexível, (2) filtros Kalman.

Jase

31

Maindonald descreve um método seqüencial baseado nas rotações de Givens . (Uma rotação de Givens é uma transformação ortogonal de dois vetores que zera uma determinada entrada em um dos vetores.) Na etapa anterior, você decompôs a matriz de design em uma matriz triangular por meio de uma transformação ortogonal modo que . (É rápido e fácil obter os resultados da regressão a partir de uma matriz triangular.) Ao juntar uma nova linha abaixo de , você efetivamente estende $\mathbf{X}$ $\mathbf{T}$ $\mathbf{Q}$ $\mathbf{Q}\mathbf{X} = (\mathbf{T}, \mathbf{0})'$ $v$ $\mathbf{X}$ Por uma linha diferente de zero, diga . A tarefa é zerar esta linha enquanto mantém as entradas na posição de diagonal. Uma sequência de rotações de Givens faz isso: a rotação com a primeira linha de zeros, o primeiro elemento de ; então a rotação com a segunda linha de zeros o segundo elemento e assim por diante. O efeito é pré-multiplicar por uma série de rotações, o que não altera sua ortogonalidade. $(\mathbf{T}, \mathbf{0})'$ $t$ $\mathbf{T}$ $\mathbf{T}$ $t$ $\mathbf{T}$ $\mathbf{Q}$

Quando a matriz de projeto possui colunas (que é o caso ao regredir nas variáveis mais uma constante), o número de rotações necessárias não excede e cada rotação altera dois vetores . O armazenamento necessário para é . Portanto, esse algoritmo tem um custo computacional de no tempo e no espaço. $p+1$ $p$ $p+1$ $p+1$ $\mathbf{T}$ $O((p+1)^2)$ $O((p+1)^2)$

Uma abordagem semelhante permite determinar o efeito na regressão da exclusão de uma linha. Maindonald dá fórmulas; assim como Belsley, Kuh e Welsh . Portanto, se você estiver procurando por uma janela em movimento para regressão, poderá reter os dados da janela em um buffer circular, adjacente ao novo dado e descartando o antigo a cada atualização. Isso dobra o tempo de atualização e requer armazenamento adicional de para uma janela de largura . Parece que seria o análogo do parâmetro de influência. $O(k (p+1))$ $k$ $1/k$

Para decaimento exponencial, acho (especulativamente) que você pode adaptar essa abordagem a mínimos quadrados ponderados, atribuindo a cada novo valor um peso maior que 1. Não deve haver necessidade de manter um buffer de valores anteriores ou excluir dados antigos.

Referências

JH Maindonald, computação estatística. J. Wiley & Sons, 1984. Capítulo 4.

DA Belsley, E. Kuh, RE Welsch, Regression Diagnostics: Identifying Influential Data and Sources of Collinearity. J. Wiley & Sons, 1980.

whuber
fonte

11

O método descrito por Maindonald está relacionado ou é o mesmo que o algoritmo de Gentleman? jstor.org/stable/2347147

onestop

6

Nesse caso, veja também as extensões de Alan Miller jstor.org/stable/2347583 . Um arquivo do site de software Fortran está agora em jblevins.org/mirror/amiller

onestop

5

Um algoritmo explícito aparece na parte inferior de p. 4 de saba.kntu.ac.ir/eecd/people/aliyari/NN%20%20files/rls.pdf . Isso pode ser encontrado no Google "mínimos quadrados recursivos". Não parece uma melhoria na abordagem de Gentleman / Maindonald, mas pelo menos é descrita de forma clara e explícita.

whuber

2

O último link se parece com o método que eu ia sugerir. A identidade matricial que eles usam é conhecida em outros lugares como a identidade Sherman-Morrison-Woodbury. Também é numericamente eficiente de implementar, mas pode não ser tão estável quanto uma rotação do Givens.

cardeal

2

@suncoolsu Hmm ... O livro de Maindonald foi publicado recentemente quando comecei a usá-lo :-).

whuber

8

Eu acho que reformular seu modelo de regressão linear em um modelo de espaço de estado fornecerá o que você procura. Se você usa R, convém usar o pacote dlm e dar uma olhada no livro complementar de Petris et al.

F. Tusell
fonte

talvez eu esteja confuso, mas isso parece se referir a um modelo de série temporal? meu modelo é realmente mais simples em que as amostras não são uma série temporal (efetivamente eles estão x-> y) amostras (independentes, eles estão apenas acumulados em grandes volumes ao longo do tempo)

mikera

11

Sim, no caso geral, isso é usado para séries temporais com observações não independentes; mas você sempre pode assumir incorrelação entre observações sucessivas, o que fornece um caso especial de interesse para você.

F. Tusell

7

Você sempre pode apenas executar gradiente descendente sobre a soma dos quadrados custam wrt os parâmetros do seu modelo . Basta pegar o gradiente, mas não use a solução de formulário fechado, mas apenas a direção da pesquisa. $E$ $W$

Deixe- ser o custo da amostra formação i'ésima dados os parâmetros . Sua atualização para o parâmetro j'th é então $E(i; W)$ $W$

W_{j} \leftarrow W_{j} + α \frac{\partial E (Eu; W)}{\partial W_{j}}

$W_{j} \leftarrow W_j + \alpha \frac{\partial{E(i; W)}}{\partial{W_j}}$

onde é uma taxa escalonada, que você deve escolher por meio de validação cruzada ou boa medida. $\alpha$

Isso é muito eficiente e a maneira como as redes neurais são normalmente treinadas. Você pode processar até muitas amostras em paralelo (digamos, mais ou menos 100) com eficiência.

É claro que algoritmos de otimização mais sofisticados (momento, gradiente conjugado, ...) podem ser aplicados.

bayerj
fonte

Parece muito semelhante a este artigo eprints.pascal-network.org/archive/00002147/01/… . Foi implementado em um projeto de código aberto chamado jubatus.

sacarina

3

Surpreendido, ninguém mais tocou nisso até agora. A regressão linear tem uma função objetiva quadrática. Portanto, um passo de Newton Raphson a partir de qualquer ponto de partida leva você diretamente ao ótimo. Agora, digamos que você já fez sua regressão linear. A função objetivo é:

eu (β) = (y - X β)^{t} (y - X β)

$L(\beta) = (y - X \beta)^t (y - X \beta)$

\nabla eu (β) = - 2 X^{t} (y - X β)

$\nabla L (\beta) = -2 X^t (y - X \beta)$

\nabla^{2} eu (β) = X^{t} X

$\nabla^2 L (\beta) = X^t X$

$\beta$ $x_{new}, y_{new}$

\nabla {eu}_{n e W} (β) = - 2 x_{n e W} (y_{n e W} - x_{n e W}^{T} β)

$\nabla L_{new}(\beta) = -2 x_{new} (y_{new}-x_{new}^T \beta)$

\nabla^{2} {eu}_{n e W} = x_{n e W} x_{n e W}^{T}

$\nabla^2 L_{new} = x_{new}x_{new}^T$

Adicione isso ao antigo hessian dado acima. Então, basta dar um passo em Newton Raphson.

β_{n e W} = β_{o eu d} + (\nabla^{2} eu)^{- 1 1} \nabla {eu}_{n e W}

$\beta_{new} = \beta_{old} + (\nabla^2L)^{-1} \nabla L_{new}$

E você terminou.

ryu576
fonte

11

\nabla L_{n e w}

$\nabla L_{new}$

p,

$p,$

O (p^{3})

$O(p^3)$

O (p^{3})

$O(p^3)$

p

$p$

(I - A)^{- 1} = I + A + A^{2} + \dots

$(I-A)^{-1}=I+A+A^2+ \dots$

2

O ajuste padrão dos mínimos quadrados fornece coeficientes de regressão

$\beta = ( X^T X )^{-1} X^T Y$

$\beta$

$X^T X$ $X^T Y$ $M^2+M$ $\beta$

Por exemplo, se M = 1, então o coeficiente é

$\beta = \frac{\sum_{i=1}^N{x_i y_i}}{\sum_{i=1}^N{x_i^2}}$

portanto, toda vez que você obtém um novo ponto de dados, atualiza as duas somas, calcula a proporção e obtém o coeficiente atualizado.

$X^T X$ $X^T Y$ $(1-\lambda)$ $\lambda$

Mark Higgins
fonte

2

β

$\beta$

X^{T} X

$X^T X$

X^{T} Y

$X^T Y$

6

X^{'} X

$X'X$

11

C^{- 1} x

$C^{-1}x$

C

$C$

x

$x$

z_{t + 1} = z_{t} + x - C z_{t}

$z_{t+1}=z_t + x - Cz_t$

z \to C^{- 1} x

$z\to C^{-1}x$

t \to \infty

$t\to\infty$

1

O problema é resolvido mais facilmente quando você reescreve as coisas um pouco:

Y = y

X = [x, 1]

então

Y = A * X

Uma solução única é encontrada calculando-se

V = X '* X

e

C = X '* Y

observe que o V deve ter tamanho N por N e C um tamanho N por M. Os parâmetros que você procura são dados por:

A = inv (V) * C

Como V e C são calculados somando seus dados, você pode calcular A em cada nova amostra. Isso tem uma complexidade de tempo de O (N ^ 3), no entanto.

Como V é quadrado e positivo semi-definido, existe uma decomposição de LU, o que torna a inversão de V numericamente mais estável. Existem algoritmos para executar atualizações de nível 1 no inverso de uma matriz. Encontre-os e você terá a implementação eficiente que procura.

Os algoritmos de atualização de nível 1 podem ser encontrados em "Computações em matriz" por Golub e van Loan. É um material resistente, mas possui uma visão abrangente de tais algoritmos.

Nota: O método acima fornece uma estimativa do quadrado mínimo em cada etapa. Você pode adicionar pesos facilmente às atualizações de X e Y. Quando os valores de X e Y aumentam muito, eles podem ser dimensionados por um único escalar, sem afetar o resultado.

Sr. White
fonte

Regressão linear online eficiente

Respostas:

Referências