Como derivar a solução de regressão de crista?

40

Estou tendo alguns problemas com a derivação da solução para regressão de crista.

Conheço a solução de regressão sem o termo de regularização:

β=(XTX)1XTy.

Porém, após adicionar o termo L2 à função cost, como é que a solução se tornaλβ22

β=(XTX+λI)1XTy.
user34790
fonte

Respostas:

23

Basta modificar a função de perda adicionando a penalidade. Em termos matriciais, a função de perda quadrática inicial se torna

(YXβ)T(YXβ)+λβTβ.
A derivação em relação a β leva à equação normal
XTY=(XTX+λI)β
que leva ao estimador de Ridge.
johnny
fonte
11
Como é que a derivada de é igual aλβTβλIβ
user34790
4
@ user34790 Não é. É igual a . Mas o 2 cancela com 2 semelhantes nos outros termos. Obviamente, o fator é como um fator 1 na álgebra "regular", você pode multiplicá-lo onde quiser, sem alterar nada. 2λβI
Bill
4
@ Bill: aqui você precisa a para obter uma matriz de dimensão correta para a adição trabalha com : é apenas um escalarIXTXλ
Henry
47

Vamos desenvolver o que sabemos, que sempre que a matriz do modelo é , a resposta vetor é e o parâmetro vetor é , a função objetivon×pXnypβ

f(β)=(yXβ)(yXβ)

(que é a soma dos quadrados dos resíduos) é minimizada quando resolve as equações normaisβ

(XX)β=Xy.

A regressão de Ridge adiciona outro termo à função objetivo (geralmente depois de padronizar todas as variáveis ​​para colocá-las em pé de igualdade), pedindo para minimizar

(yXβ)(yXβ)+λββ

para alguma constante não negativa . É a soma dos quadrados dos resíduos mais um múltiplo da soma dos quadrados dos próprios coeficientes (tornando óbvio que ele tem um mínimo global). Como , ele possui uma raiz quadrada positiva .λλ0ν2=λ

Considere a matriz aumentada com linhas correspondentes a vezes a matriz de identidade :Xνp×pI

X=(XνI)

Quando o vetor é similarmente estendido com zeros no final para , o produto da matriz na função objetivo adiciona termos adicionais da forma ao objetivo original. Assim sendoypyp(0νβi)2=λβi2

(yXβ)(yXβ)=(yXβ)(yXβ)+λββ.

A partir da forma da expressão da mão esquerda, é imediato que as equações normais sejam

(XX)β=Xy.

Como juntamos zeros no final de , o lado direito é o mesmo que . No lado esquerdo, é adicionado ao . Portanto, as novas equações normais simplificam parayXyν2I=λIXX

(XX+λI)β=Xy.

Além de ser conceitualmente econômico - nenhuma nova manipulação é necessária para obter esse resultado - também é computacionalmente econômico: seu software para fazer mínimos quadrados comuns também fará regressão de crista sem qualquer alteração. (No entanto, pode ser útil em grandes problemas usar software projetado para essa finalidade, porque ele explorará a estrutura especial de para obter resultados eficientemente para um intervalo densamente espaçado de , permitindo que você explore como as respostas variam com .)Xλλ

Outra beleza dessa maneira de ver as coisas é como ela pode nos ajudar a entender a regressão da crista. Quando queremos realmente entender a regressão, quase sempre ajuda pensar nela geometricamente: as colunas de constituem vetores em um espaço vetorial real da dimensão . Ao unir a , prolongando-os de vetores para vetores, estamos incorporando em um espaço maior incluindo direções "imaginárias", mutuamente ortogonais. A primeira coluna deXpnνIXnn+pRnRn+ppXrecebe um pequeno componente imaginário de tamanho , prolongando-o e movendo-o para fora do espaço gerado pelas colunas originais . A segunda, terceira, ..., colunas são igualmente alongadas e movidas para fora do espaço original pela mesma quantidade - mas todas em novas direções diferentes. Consequentemente, qualquer colinearidade presente nas colunas originais será resolvida imediatamente . Além disso, quanto maior o número de , mais esses novos vetores se aproximam doνppthννpdireções imaginárias: elas se tornam cada vez mais ortonormais. Conseqüentemente, a solução das equações normais se tornará possível imediatamente e se tornará numericamente estável à medida que aumenta de .ν0

Essa descrição do processo sugere algumas abordagens inovadoras e criativas para solucionar os problemas que a Regressão de Ridge foi projetada para lidar. Por exemplo, usando qualquer meio (como a decomposição de variância descrita por Belsley, Kuh e Welsch em seu livro de 1980 sobre Regression Diagnostics , capítulo 3), você poderá identificar subgrupos de colunas quase colineares de , em que cada subgrupo é quase ortogonal a qualquer outro. Você só precisa contíguo tantas linhas para (e zeros para ) como existem elementos no maior grupo, dedicando uma nova dimensão "imaginária" para deslocar cada elemento de um grupo longe de seus irmãos: você não precisa imaginário dimensões para fazer isso.XXyp

whuber
fonte
2
O último autor do livro é galês, não galês.
Mark L. Stone
11
Uau, isso só me impressionou. Existe alguma discussão sobre o que acontece quando isso é generalizado fora dos modelos lineares, isto é, dos glm's? A penalidade não deve ser igual à regressão de crista ... mas essa interpretação implica que ainda seria um estimador útil em potencial!
Cliff AB
2
@ Cliff Essa é uma sugestão muito interessante. Como, no entanto, as estimativas GLM dependem de maneira mais complicada de e seus estimadores geralmente não podem ser fatorados na forma como são para OLS (onde e ), pode ser difícil estabelecer uma relação útil entre impor uma função de penalidade e modificando as colunas de . Em particular, não está claro como os valores em precisariam ser aumentados para que isso funcionasse. X
β^=g(X)h(y)
g(X)=(XX)1Xh(y)=yXy
whuber
11
Sim, seria preciso pensar um pouco para estabelecer qual é a penalidade, mas não estou tão preocupado com isso. A idéia de que usar geralmente também não é fácil ... exceto talvez no caso de regressão logística, onde poderíamos adicionar dois 's; um dos 0 e um dos 1. Esse aumento seria então uma versão mais geral do "estimador binomial +2" (existe um nome mais apropriado para esse estimador em que estou apagando, que é basicamente quando você está estimando partir de uma distribuição binomial usando a média posterior como a estimativa com um uniforme anterior em ). y ypp
Cliff AB
@ Mark Obrigado pela correção. Você pode dizer que eu estava saindo da memória ... :-).
whuber
20

A derivação inclui cálculo de matriz, que pode ser bastante entediante. Gostaríamos de resolver o seguinte problema:

minβ(YβTX)T(YβTX)+λβTβ

Agora observe que e Juntos, chegamos à condição de primeira ordem Isolar gera a solução:

(YβTX)T(YβTX)β=2XT(YβTX)
λβTββ=2λβ.
XTY=XTXβ+λβ.
β
β=(XTX+λI)1XTY.
pthesling
fonte
9

Recentemente, deparei com a mesma pergunta no contexto de P-Splines e, como o conceito é o mesmo, quero dar uma resposta mais detalhada sobre a derivação do estimador de crista.

Começamos com uma função de critério penalizado que difere da função clássica de critério OLS pelo seu termo de penalização no último somatório:

CriterionRidge=i=1n(yixiTβ)2+λj=1pβj2

Onde

  • p= quantidade de covariáveis ​​usadas no modelo
  • xiTβ= seu preditor linear padrão
  • o primeiro summand representa o MSE (divergência ao quadrado da previsão em relação ao valor real) que queremos minimizar como de costume
  • o segundo somatório representa a penalização que aplicamos aos coeficientes. Aqui estamos no contexto de Ridge, que implica uma medida de distância euclidiana e, portanto, o grau de 2 no termo da penalização. No caso de uma penalização por laço, aplicaríamos um grau 1 e produziríamos um estimador totalmente diferente.

Podemos reescrever esse critério na notação matricial e detalhá-lo:

CriterionRidge=(yXβ)T(yXβ)+λβTβ

=yTyβTXTyyTXβ+βTxTXβ+λβTβ

=yTyβTXTyβTXTy+βTXTXβ+βTλIβ sendo a matriz de identidadeI

=yTy2βTXTy+βT(XTX+λI)β

Agora, pesquisamos o que minimiza nosso critério. Entre outros, usamos a regra de diferenciação de matrizes que podemos aplique aqui como : βxTAxx=(A+AT)x=A symmetric2Ax(XTX+λI)Rn×n

CriterionRidgeβ=2XTy+2(XTX+λI)β=!0

(XTX+λI)β=XTy

et voilàβ^=(XTX+λI)1XTy

Jann Goschenhofer
fonte
@ Jahn, você pode explicar como se tornou ? Eu acho que você acabou de aplicar a transposição, certo. Mas você não pode simplesmente aplicar transposição em um termo sem aplicá-lo em todas as equações. O que estou perdendo aqui?
yTXβ
βTXTy
theateist
11
@ theateist Um escalar transposto é o mesmo escalar.
Konstantin
2

Há algumas coisas importantes que estão faltando nas respostas dadas.

  1. A solução para é derivada da condição necessária de primeira ordem: que gera . Mas isso é suficiente? Ou seja, a solução é um mínimo global somente se for estritamente convexo. Isso pode ser mostrado como verdadeiro.βfridge(β,λ)β=0β=(XTX+λI)1XTYfridge(β,λ)

  2. Outra maneira de analisar o problema é ver a equivalência entre e restrito a . OLS significa Mínimos Quadrados Ordinários. Nesta perspectiva, é apenas a função lagrangiana usada para encontrar os mínimos globais da função objetivo convexa restringida pela função convexa .fridge(β,λ)fOLS(β)=(YβTX)T(YβTX)||β||22tfridge(β,λ)fOLS(β)||β||22

Uma boa explicação para esses pontos e a derivação de podem ser encontradas nessas notas de aula: http://math.bu.edu/people/cgineste/classes/ma575/p/w14_1.pdfβ

Davor Josipovic
fonte