Qual algoritmo é usado na regressão linear?

42

Eu costumo ouvir sobre "mínimos quadrados comuns". Esse é o algoritmo mais usado para regressão linear? Existem motivos para usar um diferente?

Belmont
fonte
@hxd, exceto por qualquer estrutura especial na matriz de projeto, todos esses são algoritmos , diferindo apenas no fator constante. A abordagem decompositiva é um bom hábito herdado da tradição da álgebra linear numérica. O(mn2)
JM não é um estatístico
@ hxd, e é por isso que minha resposta foi adaptada para ser uma exposição dos algoritmos envolvidos. Se você tiver perguntas não abordadas neste tópico, considere fazer uma nova pergunta.
JM não é um estatístico

Respostas:

32

Em relação à pergunta no título, sobre qual é o algoritmo usado:

Em uma perspectiva de álgebra linear, o algoritmo de regressão linear é a maneira de resolver um sistema linear com mais equações que incógnitas. Na maioria dos casos, não há solução para esse problema. E isso ocorre porque o vetor não pertence ao espaço da coluna de , .b A C ( A )Ax=bbAC(A)

O best straight lineé o que faz com que o erro global tão pequeno quanto for preciso. E é conveniente pensar que o tamanho do quadrado é pequeno, , porque não é negativo e só é igual a 0 quando b \ em C (\ mathbf {A}) .e=Axb b C ( A )e2bC(A)

Projetar (ortogonalmente) o vetor para o ponto mais próximo no espaço da coluna de fornece o vetor que resolve o sistema (seus componentes estão na melhor linha reta) com o erro mínimo.A b bAb

ATAx^=ATbx^=(ATA)1ATb

e o vetor projetado é dado por:b

b=Ax^=A(ATA)1ATb

Talvez o método dos mínimos quadrados não seja usado exclusivamente porque isso squaring compensa demais os valores extremos.

Deixe-me dar um exemplo simples em R, que resolve o problema de regressão usando este algoritmo:

library(fBasics)

reg.data <- read.table(textConnection("
   b      x
  12      0
  10      1
   8      2
  11      3
   6      4
   7      5
   2      6
   3      7
   3      8 "), header = T)

attach(reg.data)

A <- model.matrix(b~x)

# intercept and slope
inv(t(A) %*% A) %*% t(A) %*% b

# fitted values - the projected vector b in the C(A)
A %*% inv(t(A) %*%A ) %*% t(A) %*% b

# The projection is easier if the orthogonal matrix Q is used, 
# because t(Q)%*%Q = I
Q <- qr.Q(qr(A))
R <- qr.R(qr(A))

# intercept and slope 
best.line <- inv(R) %*% t(Q) %*% b

# fitted values 
Q %*% t(Q) %*% b

plot(x,b,pch=16)
abline(best.line[1],best.line[2])
George Dontas
fonte
Eu recebo um erro could not find inv?!
hhh
1
Carregue o pacote fBasics. finzi.psych.upenn.edu/R/library/fBasics/html/matrix-inv.html
George Dontas
5
Existe uma razão para usar inv do fBasics quando é apenas um sinônimo para resolver? Não seria melhor para a resposta não exigir uma dependência de pacotes externos, se for desnecessário?
Dason
@ George Eu amo a resposta clara, no entanto, acho que a pergunta original estava pedindo algoritmos, e o QR é apenas uma delas. Que tal decomposição de LU, SVD e Cholesky? Além disso, em R, o método para lmé QR, há razões para isso, você poderia explicar por quê?
Haitao Du
@GeorgeDontas Note que pode ser que não seja invertível. Conforme explicado nesta resposta , uma maneira de lidar com isso é remover das colunas que são combinações lineares de outras colunas. AATAA
Oren Milman
70

Para responder à letra da pergunta, "mínimos quadrados comuns" não é um algoritmo; ao contrário, é um tipo de problema na álgebra linear computacional, da qual a regressão linear é um exemplo. Geralmente dados e uma função experimental ("modelo") para ajustar os dados, na forma . Os são chamados de "funções " e podem ser de monômeros a funções trigonométricas (por exemplo, , ) e funções exponenciais ( ). O termo "linear" em "regressão linear" aqui não se refere às funções básicas,{(x1,y1),,(xm,ym)}f(x)=c1f1(x)++cnfn(x)fj(x)xjsin(jx)cos(jx)exp(jx)cj, em que a derivada parcial do modelo em relação a qualquer um dos fornece o fator multiplicador de ; isto é, .cjcjfj(x)

Agora, matriz retangular ("matriz de design") que (geralmente) possui mais linhas do que colunas, e cada entrada possui o formato , sendo o índice de linha e sendo o índice da coluna. O OLS agora é a tarefa de encontrar o vetor que minimiza a quantidade (na notação da matriz, ; aqui, é geralmente chamado de "vetor de resposta").m×nAfj(xi)ijc=(c1cn)j=1m(yjf(xj))2Acy2y=(y1ym)

Existem pelo menos três métodos usados ​​na prática para calcular soluções de mínimos quadrados: as equações normais, decomposição QR e decomposição de valor singular. Em resumo, são maneiras de transformar a matriz em um produto de matrizes que são facilmente manipuladas para resolver o vetor .Ac

George já mostrou o método das equações normais em sua resposta; basta resolver o conjunto de equações linearesn×n

AAc=Ay

para . Devido ao fato de a matriz ser simétrica positiva (semi) definida, o método usual usado para isso é a decomposição de Cholesky, que fatores no formato , com uma matriz triangular inferior. O problema com essa abordagem, apesar da vantagem de ser capaz de compactar os matriz de projeto em uma (geralmente) muito menores matriz, é que esta operação é propenso a perda de algarismos significativos (isso tem algo a faça com o "número da condição" da matriz de design).cAAAAGGGm×nn×n

Uma maneira um pouco melhor é a decomposição do QR, que trabalha diretamente com a matriz de design. É factores como , onde é uma matriz ortogonal (multiplicando uma tal matriz, com a sua transposta dá uma matriz de identidade) e é triangular superior. é posteriormente computado como . Por razões que não abordarei (basta ver qualquer texto de álgebra linear numérica decente, como este ), ele possui melhores propriedades numéricas do que o método das equações normais.AA=QRQRcR1Qy

Uma variação no uso da decomposição QR é o método de equações seminormais . Resumidamente, se alguém tiver a decomposição , o sistema linear a ser resolvido assume a formaA=QR

RRc=Ay

Efetivamente, alguém está usando a decomposição QR para formar o triângulo de Cholesky de nessa abordagem. Isso é útil no caso em que é escasso, e o armazenamento explícito e / ou a formação de (ou uma versão fatorada) é indesejável ou impraticável.AAAQ

Finalmente, a maneira mais cara, porém mais segura, de resolver o OLS é a decomposição de valor singular (SVD). Desta vez, é fatorado como , onde e são ortogonais eA = U Σ VU V ΣAA=UΣVUVΣé uma matriz diagonal, cujas entradas diagonais são denominadas "valores singulares". O poder dessa decomposição reside na capacidade de diagnóstico concedida a você pelos valores singulares, pois se alguém vê um ou mais valores singulares minúsculos, é provável que você tenha escolhido um conjunto de bases não totalmente independente, necessitando, assim, de uma reformulação seu modelo. (O "número da condição" mencionado anteriormente está de fato relacionado à razão entre o maior valor singular e o menor; é claro que a razão se torna enorme (e a matriz está, portanto, mal condicionada) se o menor valor singular for "minúsculo" .)

Este é apenas um esboço desses três algoritmos; qualquer bom livro sobre estatística computacional e álgebra linear numérica deve fornecer detalhes mais relevantes.

JM não é estatístico
fonte
3
Boa explicação!
Mike Spivey
Como você calcula R^{-1} Q^T yse A não é quadrado? Você deixa cair as zero linhas em R?
bhan
1
@bhan, estou assumindo a variante "econômica" (ou "fina") da decomposição QR, onde é quadrado e tem as mesmas dimensões que a matriz de design. Algo para você fazer: procure a diferença entre "QR completo" e "QR fino". QRQ
JM não é um estatístico
@JM alguma recomendação sobre "bom livro sobre estatística computacional e álgebra linear numérica"? realmente quer aprender mais.
Haitao Du
1
@hxd, de cabeça para baixo: Monahan para estatística computacional e Golub / van Loan para álgebra linear numérica.
JM não é um estatístico
6

O link do wiki: Métodos de estimativa para regressão linear fornece uma lista bastante abrangente de métodos de estimativa, incluindo OLS e os contextos nos quais métodos alternativos de estimativa são usados.

user603
fonte
1
Não aborda a questão (a página nem sequer menciona QR)
user603
4

É fácil se confundir entre definições e terminologia. Ambos os termos são usados, às vezes de forma intercambiável. Uma rápida pesquisa na Wikipedia deve ajudar:

Mínimos Quadrados Ordinários (OLS) é um método usado para ajustar modelos de regressão linear. Devido à consistência e eficiência demonstráveis ​​(sob premissas suplementares) do método OLS, é a abordagem dominante. Veja os artigos para obter mais pistas.

Dirk Eddelbuettel
fonte
Certo, é por isso que eu considero OLS ser um "algoritmo" usada na regressão linear ...
Belmont
3
Os mínimos quadrados comuns são um estimador. Há uma variedade de algoritmos para calcular a estimativa: geralmente é usado algum tipo de decomposição da matriz ortogonal, como o QR. Veja en.wikipedia.org/wiki/…
Simon Byrne
4

Costumo pensar em 'mínimos quadrados' como um critério para definir a linha de regressão mais adequada (ou seja, aquela que torna a soma dos resíduos 'quadrados' menores '') e o 'algoritmo' nesse contexto como o conjunto de etapas usadas determinar os coeficientes de regressão que atendem a esse critério. Essa distinção sugere que é possível ter algoritmos diferentes que satisfizessem o mesmo critério.

Eu ficaria curioso para saber se outros fazem essa distinção e que terminologia eles usam.

Jeromy Anglim
fonte
Por algoritmo, quero dizer aproximadamente a implementação de software usada para ajustar uma linha para modelar a média de uma distribuição.
Belmont
3

Um livro antigo, no entanto, ao qual me pego repetidamente, é

Lawson, CL e Hanson, RJ Resolvendo problemas dos mínimos quadrados , Prentice-Hall, 1974.

Ele contém uma discussão detalhada e muito legível de alguns dos algoritmos mencionados pelas respostas anteriores. Você pode querer olhar para ele.

F. Tusell
fonte
1
Se você leu este livro antigo, também deveria examinar os Métodos Numéricos de Åke Björck para Problemas dos Mínimos Quadrados , que têm coisas que não foram discutidas em Lawson / Hanson. As rotinas incluídas no livro Lawson / Hanson estão disponíveis no Netlib .
JM não é estatístico