Peut-il y avoir plusieurs solutions optimales locales lorsque nous résolvons une régression linéaire?

19

J'ai lu cette déclaration sur un ancien vrai / faux examen:

Nous pouvons obtenir plusieurs solutions optimales locales si nous résolvons un problème de régression linéaire en minimisant la somme des erreurs quadratiques en utilisant la descente de gradient.

Solution: faux

Ma question est, quelle partie de cette question est fausse? Pourquoi cette affirmation est-elle fausse?

Anjela Minoeu
la source

Réponses:

8

Cette question est intéressante dans la mesure où elle expose certains liens entre la théorie de l'optimisation, les méthodes d'optimisation et les méthodes statistiques que tout utilisateur capable de statistiques doit comprendre. Bien que ces connexions soient simples et faciles à apprendre, elles sont subtiles et souvent négligées.

Pour résumer quelques idées tirées des commentaires des autres réponses, je voudrais souligner qu'il existe au moins deux façons dont la "régression linéaire" peut produire des solutions non uniques - pas seulement en théorie, mais en pratique.

Manque d'identifiabilité

Le premier est lorsque le modèle n'est pas identifiable. Cela crée une fonction objective convexe mais pas strictement convexe qui a plusieurs solutions.

Considérons, par exemple, régressant contre x et y (avec une ordonnée à l' origine) pour le ( x , y , z ) des données ( 1 , - 1 , 0 ) , ( 2 , - 2 , - 1 ) , ( 3 , - 3 , - 2 ) . Une solution est z = 1 + y . Une autre est zzxy(x,y,z)(1,1,0),(2,2,1),(3,3,2)z^=1+y . Pour voir qu'il doit y avoir plusieurs solutions, paramétrez le modèle avec trois paramètres réels ( λ , μ , ν ) et un terme d'erreur ε sous la formez^=1x(λ,μ,ν)ε

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

La somme des carrés des résidus se simplifie pour

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

(Il s'agit d'un cas limitatif de fonctions objectives qui se posent dans la pratique, comme celui discuté à Est-ce que la toile de jute empirique d'un estimateur M peut être indéfinie?, Où vous pouvez lire des analyses détaillées et afficher des graphiques de la fonction.)

Du fait que les coefficients des carrés ( et 56 ) sont positifs et le déterminant 3 × 56 - ( 24 / 2 ) 2 = 24 est positif, ceci est une forme quadratique positive semi - définie en ( μ , ν , λ ) . Elle est minimisée lorsque μ = ν = 0 , mais λ peut avoir n'importe quelle valeur. Puisque la fonction objectif SSR ne dépend pas de λ3563×56(24/2)2=24(μ,ν,λ)μ=ν=0λSSRλ, ni son gradient (ni aucun autre dérivé). Par conséquent, tout algorithme de descente de gradient - s'il n'apporte pas de changements de direction arbitraires - définira la valeur de de la solution quelle que soit la valeur de départ.λ

Même lorsque la descente de gradient n'est pas utilisée, la solution peut varier. Dans R, par exemple, il existe deux façons simples et équivalentes de spécifier ce modèle: as z ~ x + yor z ~ y + x. Le premier rendement z = 1 - x , mais la seconde donne z = 1 + y . z^=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 

(Les NAvaleurs doivent être interprétées comme des zéros, mais avec un avertissement indiquant l'existence de plusieurs solutions. L'avertissement a été possible en raison d'analyses préliminaires effectuées Rindépendamment de sa méthode de solution. Une méthode de descente en gradient ne détecterait probablement pas la possibilité de plusieurs solutions, même si un bon vous avertirait d'une certaine incertitude qu'il était arrivé à l'optimum.)

Contraintes de paramètres

Une convexité stricte garantit un optimum global unique, à condition que le domaine des paramètres soit convexe. Les restrictions de paramètres peuvent créer des domaines non convexes, conduisant à plusieurs solutions globales.

Un exemple très simple est fourni par le problème de l'estimation d'une "moyenne" pour les données - 1 , 1 soumises à la restriction | μ | 1 / deux . Cela modélise une situation qui est un peu à l'opposé des méthodes de régularisation comme Ridge Regression, le Lasso ou Elastic Net: il insiste pour qu'un paramètre de modèle ne devienne pas trop petit. (Diverses questions sont apparues sur ce site pour savoir comment résoudre les problèmes de régression avec de telles contraintes de paramètres, montrant qu'ils se posent en pratique.)μ1,1|μ|1/2

Il existe deux solutions des moindres carrés à cet exemple, toutes deux également bonnes. On les trouve en minimisant soumis à la contrainte | μ | 1 / deux . Les deux solutions sont μ = ± 1 / 2 . Plus d'une solution peut se produire parce que la restriction des paramètres rend le domaine u ( - , - 1 / 2 ] (1μ)2+(1μ)2|μ|1/2μ=±1/2 non convexe:μ(,1/2][1/2,)

Tracé de la somme des carrés contre $ \ mu $

La parabole est le graphe d'une fonction (strictement) convexe. La partie rouge épaisse est la partie restreinte au domaine de : il a deux points les plus bas à μ = ± 1 / deux , où la somme des carrés est cinq / deux . Le reste de la parabole (représentée en pointillés) est supprimée par la contrainte, éliminant ainsi son minimum unique de la considération.μμ=±1/25/2

Une méthode de descente de gradient, à moins qu'il était prêt à prendre de grands sauts, trouverait probablement la solution « unique » en commençant par une valeur positive et sinon , il trouverait la solution « unique » μ = - 1 / 2 lorsque en commençant par une valeur négative.μ=1/2μ=1/2

La même situation peut se produire avec des ensembles de données plus grands et dans des dimensions plus élevées (c'est-à-dire avec plus de paramètres de régression à ajuster).

whuber
la source
1
Un exemple très simple d'une fonction convexe qui n'est pas strictement convexe et qui a une infinité de minima est . Tout point sur la ligne y = x est un point minimum. f(x,y)=(xy)2y=x
kjetil b halvorsen
1
@Kjetil Merci, c'est vrai. L'astuce ici est de montrer comment ces fonctions se produisent réellement dans des situations de régression. Votre fonction est précisément l'inspiration du premier exemple que j'ai proposé.
whuber
Un exemple visuel stats.stackexchange.com/a/151351/171583 .
ayorgo
2

J'ai bien peur qu'il n'y ait pas de réponse binaire à votre question. Si la régression linéaire est strictement convexe (pas de contraintes sur les coefficients, pas de régularisateur, etc.), alors la descente de gradient aura une solution unique et ce sera l'optimum global. La descente en pente peut et renverra plusieurs solutions si vous avez un problème non convexe.

Bien que OP demande une régression linéaire, l'exemple ci-dessous montre la minimisation des moindres carrés bien que non linéaire (par rapport à la régression linéaire souhaitée par OP) peut avoir plusieurs solutions et la descente de gradient peut retourner une solution différente.

Je peux montrer empiriquement en utilisant un exemple simple

  1. La somme des erreurs quadratiques peut parfois être non convexe, donc avoir plusieurs solutions
  2. La méthode de descente en gradient peut fournir plusieurs solutions.

Considérez l'exemple où vous essayez de minimiser les moindres carrés pour le problème suivant:

entrez la description de l'image ici

wa

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

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

Le problème ci-dessus a 3 solutions différentes et elles sont les suivantes:

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

Comme indiqué ci-dessus, le problème des moindres carrés peut être non convexe et peut avoir plusieurs solutions. Ensuite, le problème ci-dessus peut être résolu en utilisant une méthode de descente de gradient telle que le solveur Microsoft Excel et chaque fois que nous exécutons, nous obtenons une solution différente. comme la descente de gradient est un optimiseur local et peut rester bloqué dans la solution locale, nous devons utiliser différentes valeurs de départ pour obtenir de vrais optima globaux. Un problème comme celui-ci dépend des valeurs de départ.

prévisionniste
la source
2
Je ne pense pas que cela réponde à la question d'OP parce qu'OP pose spécifiquement des questions sur la régression linéaire , pas sur l'optimisation en général.
Sycorax dit Réintégrer Monica
1
Non, ce n'est pas le cas, mais juste essayer de faire un point sur les problèmes d'optimisation, mettra à jour avec des mises en garde
prévisionniste
@ user777 vous avez raison. c'est une question très valable sur l'ancien examen du MIT. Je suis sûr que la réponse est fausse grâce à Forecastet.
Anjela Minoeu
alors tu es sûr que j'ai raison?
Anjela Minoeu
@AnjelaMinoeu, j'ai mis à jour ma réponse.
prévisionniste
1

C'est parce que la fonction objectif que vous minimisez est convexe, il n'y a qu'un seul minimum / maximum. Par conséquent, l'optimum local est également un optimum global. Une descente en pente trouvera éventuellement la solution.

Pourquoi cette fonction objective est convexe? C'est la beauté de l'utilisation de l'erreur quadratique pour la minimisation. La dérivation et l'égalité à zéro montreront bien pourquoi c'est le cas. C'est assez un problème de manuel et est couvert presque partout.

Vladislavs Dovgalecs
la source
4
La convexité n'implique pas un minimum unique. En général, vous devez faire appel à la convexité stricte d'une fonction objective définie sur un domaine convexe. Les critères de terminaison de la descente de gradient utilisant l'arithmétique à virgule flottante posent également problème: même lorsque la fonction objectif est strictement convexe, l'algorithme est susceptible de trouver des solutions différentes (selon les valeurs de départ) lorsque la fonction est presque plate près de son minimum.
whuber
@whuber voudriez-vous s'il vous plaît le rendre plus simple et clair pour moi?
Anjela Minoeu
@whuber Je pense que le premier problème est l'utilisation de la terminologie. Deuxièmement, la convexité implique un minimum unique. Je ne vois pas de fonction concave différenciable qui n'a pas de minimum / maximum unique. Voir la preuve ici: planetmath.org/localminimumofconvexfunctionisnecessatelyglobal
Vladislavs Dovgalecs
3
Je n'ai pas pris la peine de lire la preuve, car elle doit invoquer une convexité stricte pour être correcte. Un problème des moindres carrés avec des coefficients non identifiables sera convexe mais pas strictement convexe, et aura donc (infiniment) de nombreuses solutions. Mais ce n'est pas complètement pertinent pour la descente de gradient, qui a ses propres problèmes - dont certains sont clairement discutés dans l'article Wikipedia . Ainsi, dans les deux sens théoriques et pratiques, la bonne réponse à la question est vraie : la descente de gradient peut - et donnera - plusieurs solutions.
whuber
@whuber Oui, la preuve fait appel à la stricte convexité.
Vladislavs Dovgalecs