Existem algoritmos para calcular parâmetros de regressão linear ou logística “em execução”?

32

Um artigo "Computando com precisão a variação de execução" em http://www.johndcook.com/standard_deviation.html mostra como calcular a média de execução, a variação e os desvios padrão.

Existem algoritmos nos quais os parâmetros de um modelo de regressão linear ou logística podem ser similarmente "atualizados dinamicamente" à medida que cada novo registro de treinamento é fornecido?

chl
fonte
1
Com um grande conjunto de treinamento ou um fluxo contínuo de dados de entrada, você pode usar algoritmos iterativos como Descentral Estocástico de Gradiente e capturar a entrada em pequenos lotes à medida que avança. Era isso que você estava perguntando?
9602 Andreister
1
Pesquisa algoritmo RLS e suas variantes. pt.wikipedia.org/wiki/Recursive_least_squares_filter
Memorando 9/09/16

Respostas:

20

Os coeficientes de regressão linear de y=ax+b é a=cov(x,y)/var(x) e b=mean(y)amean(x) .

Então, tudo que você realmente precisa é de um método incremental para calcular cov(x,y) . A partir desse valor e da variação de x e a média de y e x é possível calcular os parâmetros a e b . Como você verá no pseudo-código fornecido abaixo, o cálculo incremental de cov(x,y) é muito semelhante ao cálculo incremental de var(x) . Isso não deveria ser uma surpresa, porque var(x)=cov(x,x) .

Aqui está o pseudo-código que você provavelmente está procurando:

init(): meanX = 0, meanY = 0, varX = 0, covXY = 0, n = 0

update(x,y):
n += 1
dx = x - meanX
dy = y - meanY
varX += (((n-1)/n)*dx*dx - varX)/n
covXY += (((n-1)/n)*dx*dy - covXY)/n
meanX += dx/n
meanY += dy/n

getA(): return covXY/varX
getB(): return meanY - getA()*meanX

Eu encontrei essa pergunta ao procurar um algoritmo equivalente calculando incrementalmente uma regressão multi-variável como R=(XX)1XY modo que XR=Y+ϵ

chmike
fonte
4
Obrigado pela sua contribuição! A parte da pergunta sobre regressão linear, na verdade, é uma duplicata de stats.stackexchange.com/questions/6920/… cujas respostas mostram como atualizar um modelo de regressão linear múltipla. É permitido que o segmento atual permaneça porque a parte da regressão logística da pergunta é independentemente de interesse. Na verdade, até a parte logística foi duplicada em stats.stackexchange.com/questions/59174/… .
whuber
1
Eu pensei que essa resposta seria útil considerando o texto de referência fornecido na pergunta. Obrigado pelo link. No entanto, não é o que estou procurando. Meu caso de uso é aparentemente particular.
chmike
3
Eu acredito que pode ser útil e é único na oferta de código funcional.
whuber
Posso perguntar por que você deixou dx * dy vezes (n-1) / n?
FavorMylikes
Você pode melhorar o código para calcular o valor-p?
26418 Nathan
12

Para seus dois exemplos específicos:

Regressão linear O artigo "Regressão linear on-line e sua aplicação ao aprendizado por reforço baseado em modelo" de Alexander Strehl e Michael Littman descreve um algoritmo chamado "Regressão linear KWIK" (consulte o algoritmo 1) que fornece uma aproximação à solução de regressão linear usando atualizações incrementais . Observe que isso não é regularizado (ou seja, não é regressão de cume). Tenho certeza de que o método de Strehl & Littman não pode se estender a essa configuração.

Regressão logística

Este tópico lança alguma luz sobre o assunto. Citação:

Mesmo sem uma restrição de regularização, a regressão logística é um problema de otimização não linear. Já isso não tem uma solução analítica, que geralmente é um pré-requisito para derivar uma solução de atualização. Com uma restrição de regularização, torna-se um problema de otimização restrito. Isso introduz um novo conjunto de complicações não analíticas, além daquelas que o problema irrestrito já apresentava.

No entanto, existem outros métodos on-line (ou incrementais) de regressão que você pode querer examinar, por exemplo, Regressão de projeção ponderada localmente (LWPR)

tdc
fonte
Sobre a regressão logística, acho que você é desnecessariamente pessimista. A regressão logística é equivalente a calcular probabilidades de classe posterior para um problema de duas classes com cada classe gaussiana distribuída, com diferentes meios e uma covariância compartilhada. O MLE para a covariância é apenas uma soma ponderada das covariâncias por classe; portanto, as estatísticas suficientes são apenas a contagem por classe, a soma e a soma dos quadrados. Obviamente, é fácil conseguir uma atualização exata usando as estatísticas suficientes.
Robert Dodier
3
@RobertDodier Você descreveu a análise discriminante linear, não a regressão logística. O último parágrafo da seção introdutória aqui esclarece o relacionamento.
ahfoss 3/09/16
@ahfoss Mesmo que os dados por classe não sejam normalmente distribuídos, ainda é possível construir um modelo equivalente à regressão logística por meio de covariâncias por classe.
Robert Dodier
1
@RobertDodier Qual é o modelo equivalente? Você parece sugerir que existe uma solução óbvia para um problema substancialmente difícil. Sua solução é mais brilhante do que você imagina, ou muito menos.
ahfoss 5/09/16
11

Como princípio geral:

0) você mantém estatísticas suficientes e as estimativas atuais de ML

1) ao obter novos dados, atualize as estatísticas e as estimativas suficientes

2) Quando você não possui estatísticas suficientes, precisará usar todos os dados.

3) Normalmente você não tem soluções em formato fechado; use os MLEs anteriores como ponto de partida, use algum método conveniente de otimização para encontrar o novo ideal a partir daí. Pode ser necessário experimentar um pouco para descobrir quais abordagens fazem as melhores compensações para seus tipos específicos de instâncias de problemas.

Se o seu problema tiver uma estrutura especial, você provavelmente poderá explorá-lo.

Algumas referências em potencial que podem ou não ter algum valor:

McMahan, HB e M. Streeter (2012),
Problema em aberto: limites melhores para a regressão logística on-line ,
JMLR: Procedimentos de oficinas e conferências , vol 23, 44.1–44.3

Penny, WD e SJ Roberts (1999),
Regressão Logística Dinâmica ,
Procedimentos IJCNN '99

Glen_b -Reinstate Monica
fonte
Concordo com a idéia de manter estatísticas suficientes (se elas existirem para o problema), mas a presença de estatísticas suficientes não torna as outras coisas desnecessárias? Se você tiver estatísticas suficientes, poderá calcular os parâmetros atualizados exatamente como se tivesse usado todo o conjunto de dados. Não há necessidade de levar em consideração os parâmetros atuais e não há necessidade de experimentar métodos de otimização.
Robert Dodier
2
É importante notar que ter estatísticas suficientes não implica que você tenha uma solução para as equações.
Glen_b -Reinstar Monica
8

Adicionando à resposta do tdc, não há métodos conhecidos para calcular estimativas exatas dos coeficientes a qualquer momento, apenas com tempo constante por iteração. No entanto, existem algumas alternativas razoáveis ​​e interessantes.

O primeiro modelo a ser observado é a configuração de aprendizado on - line . Nesse cenário, o mundo anuncia primeiro um valor de x, seu algoritmo prediz um valor para y, o mundo anuncia o valor verdadeiro y 'e seu algoritmo sofre uma perda l (y, y'). Para esta configuração, sabe-se que algoritmos simples (descida de gradiente e gradiente exponenciado, entre outros) atingem arrependimento sublinear. Isso significa que, conforme você vê mais exemplos, o número de erros extras cometidos por seu algoritmo (quando comparado ao melhor preditor linear possível) não aumenta com o número de exemplos. Isso funciona mesmo em ambientes contraditórios. Existe um bom artigo explicando uma estratégia popular para provar esses limites do arrependimento. As anotações de Shai Shalev-Schwartz também são úteis.

Há uma extensão da configuração de aprendizado on-line chamada configuração de bandido, na qual seu algoritmo recebe apenas um número que representa o quão errado ele estava (e nenhum ponteiro para a resposta correta). De maneira impressionante, muitos resultados do aprendizado on-line são transferidos para essa configuração, exceto aqui um é forçado a explorar e a explorar, o que leva a todos os tipos de desafios interessantes.

Alexandre Passos
fonte
6

Outras respostas apontaram para o mundo do aprendizado de máquina, e esse é certamente um lugar onde esse problema foi abordado.

No entanto, outra abordagem que pode ser mais adequada às suas necessidades é o uso da fatoração QR com atualizações de baixa classificação. As abordagens para fazer isso e usá-lo para resolver problemas de mínimos quadrados são fornecidas em:

Atualizando a fatoração QR e o problema dos mínimos quadrados de Hammerling e Lucas.


fonte
5

yt=βtxt+εt,βt=βt1+ηt
βt=βt1

yt=logit(βtxt+εt),βt=βt1+ηt
Kochede
fonte
2

Isso é para adicionar à resposta @chmike.

O método parece ser semelhante ao algoritmo on-line da BP Welford para desvio padrão, que também calcula a média. John Cook dá uma boa explicação aqui . Tony Finch em 2009 fornece um método para uma média móvel exponencial e desvio padrão:

diff := x – mean 
incr := alpha * diff 
mean := mean + incr 
variance := (1 - alpha) * (variance + diff * incr)

Examinando a resposta postada anteriormente e expandindo-a para incluir uma janela móvel exponencial:

init(): 
    meanX = 0, meanY = 0, varX = 0, covXY = 0, n = 0,
    meanXY = 0, varY = 0, desiredAlpha=0.01 #additional variables for correlation

update(x,y):
    n += 1
    alpha=max(desiredAlpha,1/n) #to handle initial conditions

    dx = x - meanX
    dy = y - meanY
    dxy = (x*y) - meanXY #needed for cor

    varX += ((1-alpha)*dx*dx - varX)*alpha
    varY += ((1-alpha)*dy*dy - varY)*alpha #needed for corXY
    covXY += ((1-alpha)*dx*dy - covXY)*alpha

    #alternate method: varX = (1-alpha)*(varX+dx*dx*alpha)
    #alternate method: varY = (1-alpha)*(varY+dy*dy*alpha) #needed for corXY
    #alternate method: covXY = (1-alpha)*(covXY+dx*dy*alpha)

    meanX += dx * alpha
    meanY += dy * alpha
    meanXY += dxy  * alpha

getA(): return covXY/varX
getB(): return meanY - getA()*meanX
corXY(): return (meanXY - meanX * meanY) / ( sqrt(varX) * sqrt(varY) )

No "código" acima, o alfa desejado pode ser definido como 0 e, nesse caso, o código funcionaria sem ponderação exponencial. Pode-se sugerir definir o alfa desejado como 1 / o tamanho desejado da janela, conforme sugerido por Modified_moving_average para um tamanho de janela em movimento.

Pergunta secundária: dos cálculos alternativos acima, algum comentário sobre o que é melhor do ponto de vista de precisão?

Referências:

chmike (2013) https://stats.stackexchange.com/a/79845/70282

Cook, John (nd) Computando com precisão a variação de execução http://www.johndcook.com/blog/standard_deviation/

Finch, Tony. (2009) Cálculo incremental da média ponderada e variância. https://fanf2.user.srcf.net/hermes/doc/antiforgery/stats.pdf

Wikipedia. (nd) Algoritmo on-line de Welford https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Online_algorithm

Chris
fonte