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=UMAx+b+e

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

Idealmente:

  • Eu gostaria de um algoritmo com maior complexidade de espaço e tempo O(NM) por atualização, em que N é a dimensionalidade da variável independente ( x ) e M é a dimensionalidade da variável dependente ( 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.
Mikera
fonte
2
Procure (1) regressão linear flexível, (2) filtros Kalman.
Jase

Respostas:

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 T por meio de uma transformação ortogonal Q, de modo que Q X = ( T , 0 ) . (É rápido e fácil obter os resultados da regressão a partir de uma matriz triangular.) Ao juntar uma nova linha v abaixo de X , você efetivamente estende ( T , 0 )XTQQX=(T,0)vX Por uma linha diferente de zero, diga t . A tarefa é zerar esta linha enquanto mantém as entradas na posição de T. diagonal. Uma sequência de rotações de Givens faz isso: a rotação com a primeira linha de T zeros, o primeiro elemento de t ; então a rotação com a segunda linha de T zeros o segundo elemento e assim por diante. O efeito é pré-multiplicar Q por uma série de rotações, o que não altera sua ortogonalidade.(T,0)tTTtTQ

Quando a matriz de projeto possui colunas (que é o caso ao regredir nas variáveis p mais uma constante), o número de rotações necessárias não excede p + 1 e cada rotação altera dois vetores p + 1 . O armazenamento necessário para T é O ( ( p + 1 ) 2 ) . Portanto, esse algoritmo tem um custo computacional de O ( ( p + 1 ) 2 ) no tempo e no espaço.p+1 1pp+1 1p+1 1TO((p+1 1)2)O((p+1 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 k . Parece que 1 / k seria o análogo do parâmetro de influência.O(k(p+1 1))k1/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 W . Basta pegar o gradiente, mas não use a solução de formulário fechado, mas apenas a direção da pesquisa.EW

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

WjWj+αE(Eu;W)Wj

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

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β)
eu(β)=-2Xt(y-Xβ)
2eu(β)=XtX

βxneW,yneW

euneW(β)=-2xneW(yneW-xneWTβ)

2euneW=xneWxneWT

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

βneW=βoeud+(2eu)-1 1euneW

E você terminou.

ryu576
fonte
11
euneWp,O(p3)
O(p3)p(Eu-UMA)-1 1=Eu+UMA+UMA2+...
2

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

β=(XTX)-1 1XTY

β

XTXXTYM2+Mβ

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

β=Eu=1 1NxEuyEuEu=1 1NxEu2

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.

XTXXTY(1 1-λ)λ

Mark Higgins
fonte
2
β
XTXXTY
6
XX
11
C-1 1xCxzt+1 1=zt+x-CztzC-1 1xt
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