Pode haver várias soluções ótimas locais quando resolvemos uma regressão linear?

19

Li esta afirmação em um antigo exame verdadeiro / falso:

Podemos obter várias soluções ótimas locais se resolvermos um problema de regressão linear, minimizando a soma dos erros ao quadrado usando a descida do gradiente.

Solução: Falso

Minha pergunta é: qual parte dessa pergunta está errada? Por que essa afirmação é falsa?

Anjela Minoeu
fonte

Respostas:

8

Essa questão é interessante na medida em que expõe algumas conexões entre teoria da otimização, métodos de otimização e métodos estatísticos que qualquer usuário capaz de estatística precisa entender. Embora essas conexões sejam simples e fáceis de aprender, elas são sutis e muitas vezes esquecidas.

Para resumir algumas idéias dos comentários a outras respostas, gostaria de salientar que há pelo menos duas maneiras pelas quais a "regressão linear" pode produzir soluções não exclusivas - não apenas teoricamente, mas na prática.

Falta de identificação

A primeira é quando o modelo não é identificável. Isso cria uma função objetiva convexa, mas não estritamente convexa, com várias soluções.

Considere-se, por exemplo, regredindo contra e (com uma intercepção) para o de dados . Uma solução é . Outra é . Para ver que deve haver várias soluções, parametrize o modelo com três parâmetros reais e um termo de erro no formatox y ( x , y , z ) ( 1 , - 1 , 0 ) , ( 2 , - 2 , - 1 ) , ( 3 , - 3 , - 2 ) z = 1 + y z = 1 - x ( λ , μ , ν ) εzxy(x,y,z)(1,1,0),(2,2,1),(3,3,2)z^=1+yz^=1x(λ,μ,ν)ε

z=1+μ+(λ+ν1)x+(λν)y+ε.

A soma dos quadrados dos resíduos simplifica para

SSR=3μ2+24μν+56ν2.

(Este é um caso limitante de funções objetivas que surgem na prática, como o discutido em Pode o hessian empírico de um estimador M ser indefinido?, Onde você pode ler análises detalhadas e visualizar gráficos da função.)

Como os coeficientes dos quadrados ( e ) são positivos e o determinante é positivo, essa é uma forma quadrática semidefinida positiva em . É minimizado quando , mas pode ter qualquer valor. Como a função objetivo não depende de , seu gradiente (ou quaisquer outros derivados) também não. Portanto, qualquer algoritmo de descida de gradiente - se ele não fizer algumas mudanças arbitrárias de direção - definirá o valor da solução de como o valor inicial.56 3 × 56 - ( 24 / 2 ) 2 = 24 ( μ , ν , λ ) μ = ν = 0 λ SSR λ λ3563×56(24/2)2=24(μ,ν,λ)μ=ν=0λSSRλλ

Mesmo quando a descida do gradiente não é usada, a solução pode variar. Por Rexemplo, existem duas maneiras fáceis e equivalentes de especificar esse modelo: como z ~ x + you z ~ y + x. O primeiro produz mas o segundo fornece . z =1+yz^=1xz^=1+y

> x <- 1:3
> y <- -x
> z <- y+1

> lm(z ~ x + y)
Coefficients:
(Intercept)            x            y  
          1           -1           NA  


> lm(z ~ y + x)
Coefficients:
(Intercept)            y            x  
          1            1           NA 

(Os NAvalores devem ser interpretados como zeros, mas com um aviso de que existem várias soluções. O aviso foi possível devido a análises preliminares realizadas Rindependentemente do método de solução. Um método de descida de gradiente provavelmente não detectaria a possibilidade de várias soluções, embora uma boa advertisse você de alguma incerteza de que havia chegado ao ideal.)

Restrições de parâmetro

A convexidade estrita garante um ótimo global único, desde que o domínio dos parâmetros seja convexo. As restrições de parâmetro podem criar domínios não convexos, levando a várias soluções globais.

Um exemplo muito simples é fornecido pelo problema de estimar uma "média" para os dados sujeitos à restrição . Isso modela uma situação que é exatamente o oposto de métodos de regularização como Ridge Regression, Lasso ou Elastic Net: está insistindo que um parâmetro de modelo não se torne muito pequeno. (Várias perguntas apareceram neste site perguntando como resolver problemas de regressão com tais restrições de parâmetros, mostrando que elas surgem na prática.)- 1 , 1 | u | 1 / 2μ1,1|μ|1/2

Existem duas soluções de mínimos quadrados para este exemplo, ambas igualmente boas. Eles são encontrados minimizando sujeito à restrição . As duas soluções são . Mais de uma solução pode surgir porque a restrição de parâmetro torna o domínio não-convexo:(1μ)2+(1μ)2|μ|1/2μ=±1/2μ(,1/2][1/2,)

Parcela da soma dos quadrados contra $ \ mu $

A parábola é o gráfico de uma função (estritamente) convexa. A parte vermelha grossa é a parte restrita ao domínio : possui dois pontos mais baixos em , onde a soma dos quadrados é . O restante da parábola (mostrado pontilhado) é removido pela restrição, eliminando assim seu mínimo exclusivo de consideração.μμ=±1/25/2

Um método de descida de gradiente, a menos que esteja disposto a dar grandes saltos, provavelmente encontrará a solução "única" ao iniciar com um valor positivo e, caso contrário, encontraria a solução "única" ao iniciar com um valor negativo.μ=1/2μ=1/2

A mesma situação pode ocorrer com conjuntos de dados maiores e em dimensões mais altas (ou seja, com mais parâmetros de regressão para ajustar).

whuber
fonte
1
Um exemplo muito simples de uma função convexa que não é estritamente convexa e tem infinitos mínimos é . Qualquer ponto na linha é um ponto mínimo. f(x,y)=(xy)2y=x
b Kjetil Halvorsen
1
@ Kjetil Obrigado, é verdade. O truque aqui é mostrar como essas funções realmente surgem em situações de regressão. Sua função é precisamente a inspiração para o primeiro exemplo que ofereci.
whuber
Um exemplo visual stats.stackexchange.com/a/151351/171583 .
ayorgo
2

Receio que não haja resposta binária para sua pergunta. Se a regressão linear for estritamente convexa (sem restrições de coeficientes, regularizador etc.), a descida do gradiente terá uma solução única e será ótima global. A descida de gradiente pode e retornará várias soluções se você tiver um problema não convexo.

Embora o OP solicite uma regressão linear, o exemplo abaixo mostra uma minimização mínima quadrada, embora não linear (versus a regressão linear que o OP deseja) possa ter várias soluções e a descida do gradiente possa retornar uma solução diferente.

Eu posso mostrar empiricamente usando um exemplo simples que

  1. A soma dos erros ao quadrado pode, em algum momento, não ser convexa, portanto, ter várias soluções
  2. O método de descida de gradiente pode fornecer várias soluções.

Considere o exemplo em que você está tentando minimizar o mínimo de quadrados para o seguinte problema:

insira a descrição da imagem aqui

onde você está tentando resolver minimizando a função objetiva. A função acima, embora diferenciável, não é convexa e pode ter várias soluções. Substituindo valores reais para veja abaixo.wa

a12=9,a13=1/9,a23=9,a31=1/9

minimize (9w1w2)2+(19w1w3)2+(19w2w1)2+(9w2w3)2+(9w3w1)2+(19w3w2)2

O problema acima tem 3 soluções diferentes e são as seguintes:

w=(0.670,0.242,0.080),obj=165.2

w=(0.080,0.242,0.670),obj=165.2

w=(0.242,0.670,0.080),obj=165.2

Como mostrado acima, o problema dos mínimos quadrados pode não ser convexo e pode ter várias soluções. Em seguida, o problema acima pode ser resolvido usando o método gradiente de descida, como o Microsoft Excel Solver, e toda vez que executamos, acabamos recebendo uma solução diferente. Como a descida do gradiente é um otimizador local e pode ficar travada na solução local, precisamos usar diferentes valores iniciais para obter ótimas otimizações globais. Um problema como esse depende dos valores iniciais.

previsor
fonte
2
Eu não acho que isso responda à pergunta do OP porque ele pergunta especificamente sobre regressão linear , não otimização em geral.
Sycorax diz Restabelecer Monica
1
Não, não, mas apenas tentando fazer um ponto sobre problemas com otimiza, irá atualizar com ressalvas
meteorologista
@ user777 você está certo. Esta é uma pergunta muito válida no exame antigo do MIT. Tenho certeza de que a resposta é falsa, graças ao Forecastet.
Anjela Minoeu
então você tem certeza que estou certo?
Anjela Minoeu
@AnjelaMinoeu, atualizei minha resposta.
forecaster
1

Isso ocorre porque a função objetivo que você está minimizando é convexa, há apenas um mínimo / máximo. Portanto, o ideal local também é o ideal global. A descida do gradiente encontrará a solução eventualmente.

Por que essa função objetivo é convexa? Essa é a beleza de usar o erro quadrático para minimização. A derivação e a igualdade para zero mostrarão muito bem por que esse é o caso. É um problema bastante comum e é abordado em quase todos os lugares.

Vladislavs Dovgalecs
fonte
4
A convexidade não implica um mínimo único. Normalmente, você precisa apelar à estrita convexidade de uma função objetiva definida em um domínio convexo. Também é um problema aqui os critérios de terminação para descida de gradiente usando aritmética de ponto flutuante: mesmo quando a função objetivo é estritamente convexa, é provável que o algoritmo encontre soluções diferentes (dependendo dos valores iniciais) quando a função estiver quase plana perto de seu mínimo.
whuber
@whuber você poderia simplificar e tornar mais claro para mim?
Anjela Minoeu
@ Whuber Acho que a primeira questão é o uso de terminologia. Segundo, a convexidade implica um mínimo único. Não vejo uma função côncava diferenciável que não tenha um único mínimo / máximo. Veja a prova aqui: planetmath.org/localminimumofconvexfunctionis necessariamente global
Vladislavs Dovgalecs
3
Não me preocupei em ler a prova, porque ela deve invocar uma convexidade estrita para estar correta. Um problema de mínimos quadrados com coeficientes não identificáveis ​​será convexo, mas não estritamente convexo e, portanto, terá (infinitamente) muitas soluções. Mas isso não é completamente relevante para a descida do gradiente, que tem seus próprios problemas - alguns dos quais são claramente discutidos no artigo da Wikipedia . Assim, nos sentidos teórico e prático, a resposta correta para a pergunta é verdadeira : a descida do gradiente pode - e vai - dar várias soluções.
whuber
@whuber Sim, a prova apela à estrita convexidade.
Vladislavs Dovgalecs