A prova de fórmulas equivalentes de regressão de crista

15

Eu li os livros mais populares da aprendizagem estatística

1- Os elementos da aprendizagem estatística.

2- Uma introdução à aprendizagem estatística .

Ambos mencionam que a regressão de crista tem duas fórmulas equivalentes. Existe uma prova matemática compreensível desse resultado?

Também passei pelo Cross Validated , mas não consigo encontrar uma prova definitiva lá.

Além disso, o LASSO desfrutará do mesmo tipo de prova?

insira a descrição da imagem aqui

jeza
fonte
1
O laço não é uma forma de regressão de crista.
Xian
@ jeza, você poderia explicar o que está faltando na minha resposta? Realmente deriva que tudo pode ser derivado sobre a conexão.
Royi 30/05
@ jeza, você poderia ser específico? A menos que você conheça o conceito lagrangiano de problema restrito, é difícil dar uma resposta concisa.
Royi 31/05/19
1
@jeza, um problema de otimização restrito pode ser convertido em otimização da função Lagrangiana / condições KKT (conforme explicado nas respostas atuais). Este princípio já tem muitas explicações simples e diferentes em toda a Internet. Em que direção é necessária mais explicação da prova? Explicação / prova do multiplicador / função Lagrangiana, explicação / prova Como esse problema é um caso de otimização relacionado ao método de Lagrange, diferença KKT / Lagrange, explicação do princípio da regularização, etc.?
Sextus Empiricus

Respostas:

19

A clássica regressão de cume ( regularização de Tikhonov ) é dada por:

argminx12xy22+λx22

A alegação acima é que o seguinte problema é equivalente:

argminx12xy22subject tox22t

Vamos definir como a solução ideal do primeiro problema e como a solução ideal do segundo problema. x^x~

A reivindicação de equivalência significa que . Ou seja, você pode ter sempre um par de e tal a solução do problema é o mesmo.t,λ0:x^=x~ t X 0
tλ0

Como poderíamos encontrar um par?
Bem, resolvendo os problemas e observando as propriedades da solução.
Ambos os problemas são convexos e suaves, tornando as coisas mais simples.

A solução para o primeiro problema é dada no ponto em que o gradiente desaparece, o que significa:

x^y+2λx^=0

As condições KKT do segundo problema afirmam:

x~y+2μx~=0

e

μ(x~22t)=0

A última equação sugere que ou .μ=0x~22=t

Preste atenção que as 2 equações básicas são equivalentes.
Ou seja, se e ambas as equações são válidas. x^=x~μ=λ

Então isso significa que no caso deve-se definir que significa que, por suficientemente grande para que ambos sejam equivalentes, deve-se definir .y22tμ=0tλ=0

No outro caso, deve-se encontrar onde:μ

yt(I+2μI)1(I+2μI)1y=t

Isso é basicamente quandox~22=t

Depois de descobrir que as soluções colidirão.μ

Em relação ao caso (LASSO), bem, ele funciona com a mesma idéia. A única diferença é que não fechamos a solução, portanto, a conexão é mais complicada.L1

Dê uma olhada na minha resposta no StackExchange Q291962 cruzado validado e no StackExchange Signal Processing Q21730 - significância de na busca de baseλ .

Observação
O que realmente está acontecendo?
Nos dois problemas, tenta estar o mais próximo possível de . No primeiro caso, desaparecerá o primeiro termo (a distância ) e, no segundo caso, fará a função objetivo desaparecer. A diferença é que, no primeiro caso, é preciso equilibrar Norma de . À medida que aumenta, o saldo significa que você deve reduzir . No segundo caso, há uma parede, você aproxima cada vez mais dexy
x=yL2
L2xλx
xyaté você atingir a parede, que é a restrição de sua norma (por ). Se a parede estiver longe o suficiente (valor alto de ) e o suficiente depender da norma de então eu não terá significado , assim como é relevante apenas do seu valor multiplicado pela norma de começa a ser significativo. A conexão exata é pelo Lagrangiano indicado acima.t
tyλy

Recursos

Encontrei este artigo hoje (03/04/2019):

Royi
fonte
O equivalente significa que \ lambda e \ t devem ser iguais. Porque eu não posso ver isso na prova. graças
jeza
@ jeza, como escrevi acima, para qualquer existe (não necessariamente igual a mas uma função de dados ), de modo que as soluções das duas formas sejam as mesmas. tλ0tty
Royi 28/05
3
@ jeza, ambos & t são essencialmente parâmetros livres aqui. Depois de especificar, digamos, λ , isso produz uma solução ótima específica. Mas t continua sendo um parâmetro livre. Portanto, neste ponto, a alegação é que pode haver algum valor de t que produziria a mesma solução ótima. Existem, essencialmente, há restrições sobre o que isso t deve ser; não é como se tivesse que ser alguma função fixa de λ , como t = λ / 2 ou algo assim. λtλtttλt=λ/2
gung - Restabelece Monica
@ Royi, eu gostaria de saber 1 - por que sua fórmula tem (1/2), enquanto as fórmulas em questão não? 2- estão usando KKT para mostrar a equivalência das duas fórmulas? 3- se sim, ainda não consigo ver essa equivalência. Não tenho certeza, mas o que espero ver é essa prova para mostrar que a fórmula um = fórmula dois.
jeza
1. Simplesmente mais fácil quando você diferencia o termo LS. Você pode mover do meu para o OP λ por fator de dois. 2. Eu usei KKT para o 2º caso. O primeiro caso não possui restrições; portanto, você pode resolvê-lo. 3. Não existe uma equação de forma fechada entre eles. Eu mostrei a lógica e como você pode criar um gráfico conectando-os. Mas, como escrevi, ele mudará para cada y (depende dos dados). λλy
Royi 01/04/19
9

Uma abordagem menos rigorosa matematicamente, mas possivelmente mais intuitiva, para entender o que está acontecendo é começar com a versão de restrição (equação 3.42 na pergunta) e resolvê-la usando os métodos do "Multiplicador de Lagrange" ( https: //en.wikipedia .org / wiki / Lagrange_multiplier ou seu texto de cálculo multivariável favorito). Lembre-se de que no cálculo é o vetor de variáveis, mas no nosso caso x é constante e β é o vetor variável. Depois de aplicar a técnica de multiplicador de Lagrange você acabar com a primeira equação (3.41) (depois jogando fora extra - λ t que é constante em relação à minimização e pode ser ignorado).xxβλt

Isso também mostra que isso funciona para laço e outras restrições.

Greg Snow
fonte
8

Talvez valha a pena ler sobre a dualidade lagrangiana e uma relação mais ampla (às vezes equivalência) entre:

  • otimização sujeita a restrições rígidas (ou seja, invioláveis)
  • otimização com multas por violar restrições.

Introdução rápida à dualidade fraca e dualidade forte

Suponha que temos alguma função de duas variáveis. Para qualquer x e y , temos:f(x,y)x^y^

minxf(x,y^)f(x^,y^)maxyf(x^,y)

Desde que vale para qualquer x e y ele também afirma que:x^y^

maxyminxf(x,y)minxmaxyf(x,y)

Isso é conhecido como dualidade fraca . Em certas circunstâncias, você também tem forte dualidade (também conhecida como propriedade do ponto de sela ):

maxyminxf(x,y)=minxmaxyf(x,y)

Quando uma forte dualidade se mantém, resolver o problema duplo também resolve o problema primordial. Em certo sentido, eles são o mesmo problema!

Lagrangiano para regressão de cume restrito

Deixe-me definir a função como:L

L(b,λ)=i=1n(yxib)2+λ(j=1pbj2t)

A interpretação min-max do Lagrangiano

O problema de regressão de Ridge sujeito a restrições rígidas é:

minbmaxλ0L(b,λ)

Você escolhe para minimizar o objetivo, cientes de que após b é escolhido, o seu adversário irá definir λ ao infinito se você escolheu b tal que Σ p j = 1 b 2 j > t .bbλbj=1pbj2>t

Se uma forte dualidade se mantiver (o que ocorre aqui porque a condição de Slater é satisfeita para ), você obtém o mesmo resultado revertendo a ordem:t>0

maxλ0minbL(b,λ)

Aqui, seu oponente escolhe primeiro ! Você escolhe b para minimizar o objetivo, já sabendo a escolha de λ . A parte min b L ( b , λ ) (considerada λ como dada) é equivalente à segunda forma do seu problema de regressão de cume.λ bλminbL(b,λ)λ

Como você pode ver, esse não é um resultado específico da regressão de Ridge. É um conceito mais amplo.

Referências

(Comecei este post após uma exposição que li de Rockafellar.)

Rockafellar, RT, Análise Convexa

Você também pode examinar as aulas 7 e 8 do curso do professor Stephen Boyd sobre otimização convexa.

Matthew Gunn
fonte
note que sua resposta pode ser estendida a qualquer função convexa.
81235 08/07/19
6

Eles não são equivalentes .

Para um problema de minimização restrito

(1)minbi=1n(yxib)2s.t.j=1pbj2t,b=(b1,...,bp)

resolvemos minimizando sobre o correspondente lagrangeanob

(2)Λ=i=1n(yxib)2+λ(j=1pbj2t)

Aqui, é um limite dado exogenamente, λ 0 é um multiplicador de Karush-Kuhn-Tucker não-negativo, e tanto o vector beta e λ são para ser determinadas de forma óptima através do procedimento de minimização dado t . tλ0 λ t

Comparando e eq ( 3,41 ) no posto do OP, parece que o estimador de Ridge pode ser obtido como a solução para (2)(3.41)

(3)minb{Λ+λt}

Como em a função a ser minimizada parece ser o Lagrangeano do problema de minimização restrita mais um termo que não envolve b , parece que de fato as duas abordagens são equivalentes ...(3)b

Mas isso não está correto, porque na regressão de Ridge minimizamos o excesso de dado λ > 0 . Mas, na lente do problema de minimização restrita, assumindo λ > 0 impõe a condição de que a restrição é vinculativa , ou seja, queb λ>0λ>0

j=1p(bj,ridge)2=t

O problema geral de minimização com restrições também permite , e essencialmente é uma formulação que inclui como casos especiais o estimador básico de mínimos quadrados ( λ = 0 ) e o estimador de Ridge ( λ > 0 ).λ=0λ=0λ>0

Portanto, as duas formulações não são equivalentes. No entanto, o post de Matthew Gunn mostra de uma maneira muito intuitiva como os dois estão intimamente ligados. Mas dualidade não é equivalência.

Alecos Papadopoulos
fonte
@MartijnWeterings Obrigado pelo comentário, reformulei minha resposta.
Alecos Papadopoulos
@MartijnWeterings Não vejo o que é confuso, pois a expressão escrita em seu comentário é exatamente a que escrevi em minha postagem reformulada.
Alecos Papadopoulos
1
λ0λ>0t<βOLS22λ=0
@MartijnWeterings Quando A é um caso especial de B, A não pode ser equivalente a B. E a regressão de cume é um caso especial do problema geral de minimização restrita, ou seja, uma situação à qual chegamos se restringirmos ainda mais o problema geral (como você faz no seu último comentário).
Alecos Papadopoulos
Certamente você pode definir algum problema de minimização restrito que é mais geral do que a regressão de cumeeira (como você também pode definir algum problema de regularização que é mais geral que a regressão de cumeeira, por exemplo, regressão de cumeeira negativa), mas a não equivalência se deve à maneira como você define o problema e não devido à transformação da representação restrita em representação lagrangiana. As duas formas podem ser vistas como equivalentes na formulação / definição restrita (não geral) que são úteis para a regressão da crista.
Sextus Empiricus