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?

regression lasso regularization ridge-regression lagrange-multipliers jeza
fonte

2

en.wikipedia.org/wiki/…

Taylor

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

19

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

\arg min_{x} \frac{1}{2} {‖ x - y ‖}_{2}^{2} + λ {‖ x ‖}_{2}^{2}

$\arg \min_{x} \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{2}^{2}$

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

\begin{aligned} \arg min_{x} & \frac{1}{2} {‖ x - y ‖}_{2}^{2} \\ subject to & {‖ x ‖}_{2}^{2} \leq t \end{aligned}

$\begin{align*} \arg \min_{x} \quad & \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} \\ \text{subject to} \quad & {\left\| x \right\|}_{2}^{2} \leq t \end{align*}$

Vamos definir como a solução ideal do primeiro problema e como a solução ideal do segundo problema. $\hat{x}$ $\tilde{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. $\forall t, \: \exists \lambda \geq 0 : \hat{x} = \tilde{x}$
$t$ $\lambda \geq 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:

\hat{x} - y + 2 λ \hat{x} = 0

$\hat{x} - y + 2 \lambda \hat{x} = 0$

As condições KKT do segundo problema afirmam:

\tilde{x} - y + 2 μ \tilde{x} = 0

$\tilde{x} - y + 2 \mu \tilde{x} = 0$

e

μ ({‖ \tilde{x} ‖}_{2}^{2} - t) = 0

$\mu \left( {\left\| \tilde{x} \right\|}_{2}^{2} - t \right) = 0$

A última equação sugere que ou . $\mu = 0$ ${\left\| \tilde{x} \right\|}_{2}^{2} = 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. $\hat{x} = \tilde{x}$ $\mu = \lambda$

Então isso significa que no caso deve-se definir que significa que, por suficientemente grande para que ambos sejam equivalentes, deve-se definir . ${\left\| y \right\|}_{2}^{2} \leq t$ $\mu = 0$ $t$ $\lambda = 0$

No outro caso, deve-se encontrar onde: $\mu$

y^{t} {(I + 2 μ I)}^{- 1} {(I + 2 μ I)}^{- 1} y = t

${y}^{t} \left( I + 2 \mu I \right)^{-1} \left( I + 2 \mu I \right)^{-1} y = t$

Isso é basicamente quando ${\left\| \tilde{x} \right\|}_{2}^{2} = t$

Depois de descobrir que as soluções colidirão. $\mu$

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. ${L}_{1}$

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

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 de $x$ $y$
$x = y$ ${L}_{2}$
${L}_{2}$ $x$ $\lambda$ $x$
$x$ $y$ até 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$
$t$ $y$ $\lambda$ $y$

Recursos

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

Dureza de aproximação para uma classe de problemas de otimização esparsa .

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

$t$

λ \geq 0

$\lambda \geq 0$

t

$t$

t

$t$

y

$y$

Royi 28/05

3

@ jeza, ambos

&

são essencialmente parâmetros livres aqui. Depois de especificar, digamos,

, isso produz uma solução ótima específica. Mas

continua sendo um parâmetro livre. Portanto, neste ponto, a alegação é que pode haver algum valor de

que produziria a mesma solução ótima. Existem, essencialmente, há restrições sobre o que isso

deve ser; não é como se tivesse que ser alguma função fixa de

, como

ou algo assim.

λ

$\lambda$

t

$t$

λ

$\lambda$

t

$t$

t

$t$

t

$t$

λ

$\lambda$

t = λ / 2

$t=\lambda/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

(depende dos dados).

λ

$\lambda$

λ

$\lambda$

y

$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 é 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 que é constante em relação à minimização e pode ser ignorado). $x$ $x$ $\beta$ $-\lambda 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 e , temos: $f(x,y)$ $\hat{x}$ $\hat{y}$

min_{x} f (x, \hat{y}) \leq f (\hat{x}, \hat{y}) \leq max_{y} f (\hat{x}, y)

$\min_x f(x, \hat{y}) \leq f(\hat{x}, \hat{y}) \leq \max_y f(\hat{x}, y)$

Desde que vale para qualquer e ele também afirma que: $\hat{x}$ $\hat{y}$

max_{y} min_{x} f (x, y) \leq min_{x} max_{y} f (x, y)

$\max_y \min_x f(x, y) \leq \min_x \max_y f(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 ):

max_{y} min_{x} f (x, y) = min_{x} max_{y} f (x, y)

$\max_y \min_x f(x, y) = \min_x \max_y f(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: $\mathcal{L}$

L (b, λ) = \sum_{i = 1}^{n} (y - x_{i} \cdot b)^{2} + λ (\sum_{j = 1}^{p} b_{j}^{2} - t)

$\mathcal{L}(\mathbf{b}, \lambda) = \sum_{i=1}^n (y - \mathbf{x}_i \cdot \mathbf{b})^2 + \lambda \left( \sum_{j=1}^p b_j^2 - t \right)$

A interpretação min-max do Lagrangiano

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

min_{b} max_{λ \geq 0} L (b, λ)

$\min_\mathbf{b} \max_{\lambda \geq 0} \mathcal{L}(\mathbf{b}, \lambda)$

Você escolhe para minimizar o objetivo, cientes de que após é escolhido, o seu adversário irá definir ao infinito se você escolheu tal que . $\mathbf{b}$ $\mathbf{b}$ $\lambda$ $\mathbf{b}$ $\sum_{j=1}^p b_j^2 > 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_{λ \geq 0} min_{b} L (b, λ)

$\max_{\lambda \geq 0} \min_\mathbf{b} \mathcal{L}(\mathbf{b}, \lambda)$

Aqui, seu oponente escolhe primeiro ! Você escolhe para minimizar o objetivo, já sabendo a escolha de . A parte (considerada como dada) é equivalente à segunda forma do seu problema de regressão de cume. $\lambda$ $\mathbf{b}$ $\lambda$ $\min_\mathbf{b} \mathcal{L}(\mathbf{b}, \lambda)$ $\lambda$

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

\begin{matrix} (1) & min_{b} \sum_{i = 1}^{n} (y - x_{i}^{'} \cdot b)^{2} s . t . \sum_{j = 1}^{p} b_{j}^{2} \leq t, b = (b_{1}, . . ., b_{p}) \end{matrix}

$\min_{\mathbf b} \sum_{i=1}^n (y - \mathbf{x}'_i \cdot \mathbf{b})^2\\ s.t. \sum_{j=1}^p b_j^2 \leq t,\;\;\; \mathbf b = (b_1,...,b_p) \tag{1}$

resolvemos minimizando sobre o correspondente lagrangeano $\mathbf b$

\begin{matrix} (2) & Λ = \sum_{i = 1}^{n} (y - x_{i}^{'} \cdot b)^{2} + λ (\sum_{j = 1}^{p} b_{j}^{2} - t) \end{matrix}

$\Lambda = \sum_{i=1}^n (y - \mathbf{x}'_i \cdot \mathbf{b})^2 + \lambda \left( \sum_{j=1}^p b_j^2 - t \right) \tag{2}$

Aqui, é um limite dado exogenamente, é 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$ $\lambda \geq 0$ $\lambda$ $t$

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

\begin{matrix} (3) & min_{b} {Λ + λ t} \end{matrix}

$\min_{\mathbf b}\{\Lambda + \lambda t\} \tag{3}$

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 , parece que de fato as duas abordagens são equivalentes ... $(3)$ $\mathbf b$

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

\sum_{j = 1}^{p} (b_{j, r i d g e}^{*})^{2} = t

$\sum_{j=1}^p (b^*_{j,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 ( ) e o estimador de Ridge ( ). $\lambda = 0$ $\lambda ^*=0$ $\lambda^* >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

λ \geq 0

$\lambda \geq 0$

λ > 0

$\lambda > 0$

t < ‖ β^{O L S} ‖_{2}^{2}

$t < \Vert \beta^{OLS} \Vert^2_2$

λ = 0

$\lambda=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

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

Respostas:

Recursos

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

Lagrangiano para regressão de cume restrito

A interpretação min-max do Lagrangiano

Referências