¿Pueden haber múltiples soluciones óptimas locales cuando resolvemos una regresión lineal?

Question

Leí esta afirmación en un viejo examen de verdadero/falso:

Podemos obtener múltiples soluciones óptimas locales si resolvemos un problema de regresión lineal minimizando la suma de errores al cuadrado utilizando el descenso de gradiente.

Solución: Falso

Mi pregunta es, ¿cuál parte de esta afirmación es incorrecta? ¿Por qué es falsa?

Answer 1

Esta pregunta es interesante en la medida en que expone algunas conexiones entre la teoría de optimización, los métodos de optimización y los métodos estadísticos que cualquier usuario capaz de estadísticas necesita entender. Aunque estas conexiones son simples y fáciles de aprender, son sutiles y a menudo pasan desapercibidas.

Para resumir algunas ideas de los comentarios a otras respuestas, me gustaría señalar que hay al menos dos formas en que la "regresión lineal" puede producir soluciones no únicas, no solo teóricamente, sino también en la práctica.

Falta de identificabilidad

La primera es cuando el modelo no es identificable. Esto crea una función objetivo convexa pero no estrictamente convexa que tiene múltiples soluciones.

Considere, por ejemplo, hacer una regresión de $z$ contra $x$ e $y$ (con una intersección) para los datos $(x,y,z)$ $(1,-1,0),(2,-2,-1),(3,-3,-2)$. Una solución es $\hat z = 1 + y$. Otra es $\hat z = 1-x$. Para ver que debe haber múltiples soluciones, parametrize el modelo con tres parámetros reales $(\lambda,\mu,\nu)$ y un término de error $\varepsilon$ en la forma

$$z = 1+\mu + (\lambda + \nu - 1)x + (\lambda -\nu)y + \varepsilon.$$

La suma de los cuadrados de los residuos se simplifica a

$$\operatorname{SSR} = 3\mu^2 + 24 \mu\nu + 56 \nu^2.$$

(Este es un caso límite de funciones objetivo que surgen en la práctica, como la discutida en ¿Puede la hessiana empírica de un estimador M ser indefinida?, donde puede leer análisis detallados y ver gráficos de la función.)

Debido a que los coeficientes de los cuadrados ($3$ y $56$) son positivos y el determinante $3\times 56 - (24/2)^2 = 24$ es positivo, esta es una forma cuadrática positiva-semidefinida en $(\mu,\nu,\lambda)$. Se minimiza cuando $\mu=\nu=0$, pero $\lambda$ puede tener cualquier valor. Dado que la función objetivo $\operatorname{SSR}$ no depende de $\lambda$, tampoco lo hace su gradiente (ni ninguna otra derivada). Por lo tanto, cualquier algoritmo de descenso de gradiente, si no realiza algunos cambios arbitrarios de dirección, establecerá el valor de la solución de $\lambda$ en lo que sea que fuera el valor inicial.

Incluso cuando no se utiliza el descenso de gradiente, la solución puede variar. En R, por ejemplo, hay dos formas fáciles y equivalentes de especificar este modelo: como z ~ x + y o z ~ y + x. El primero da $\hat z = 1 - x$ pero el segundo da $\hat z = 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 

(Los valores de NA deben interpretarse como ceros, pero con una advertencia de que existen múltiples soluciones. La advertencia fue posible debido a análisis preliminares realizados en R que son independientes de su método de solución. Un método de descenso de gradiente probablemente no detectaría la posibilidad de múltiples soluciones, aunque uno bueno te advertiría de cierta incertidumbre de que haya llegado al óptimo.)

Restricciones de parámetros

La convexidad estricta garantiza un óptimo global único, siempre que el dominio de los parámetros sea convexo. Las restricciones de los parámetros pueden crear dominios no convexas, lo que lleva a múltiples soluciones globales.

Un ejemplo muy simple se ofrece con el problema de estimar una "media" $\mu$ para los datos $-1, 1$ sujeto a la restricción $|\mu| \ge 1/2$. Esto modela una situación que es algo así como lo opuesto a métodos de regularización como Regresión Ridge, LASSO o Elastic Net: está insistiendo en que un parámetro del modelo no se vuelva demasiado pequeño. (Han aparecido varias preguntas en este sitio preguntando cómo resolver problemas de regresión con tales restricciones de parámetros, mostrando que surgen en la práctica.)

Hay dos soluciones de mínimos cuadrados para este ejemplo, ambas igualmente buenas. Se encuentran minimizando $(1-\mu)^2 + (-1-\mu)^2$ sujeto a la restricción $|\mu| \ge 1/2$. Las dos soluciones son $\mu=\pm 1/2$. Pueden surgir más de una solución porque la restricción del parámetro hace que el dominio $\mu \in (-\infty, -1/2]\cup [1/2, \infty)$ sea no convexo:

La parábola es el gráfico de una función (estrictamente) convexa. La parte roja gruesa es la porción restringida al dominio de $\mu$: tiene dos puntos más bajos en $\mu=\pm 1/2$, donde la suma de cuadrados es $5/2$. El resto de la parábola (mostrada punteada) es eliminada por la restricción, eliminando así su mínimo único de consideración.

Un método de descenso de gradiente, a menos que esté dispuesto a dar grandes saltos, probablemente encontraría la solución "única" $\mu=1/2$ al comenzar con un valor positivo y de lo contrario encontraría la solución "única" $\mu=-1/2$ al comenzar con un valor negativo.

La misma situación puede ocurrir con conjuntos de datos más grandes y en dimensiones más altas (es decir, con más parámetros de regresión para ajustar).

Answer 2

Me temo que no hay una respuesta binaria a tu pregunta. Si la regresión lineal es estrictamente convexa (sin restricciones en los coeficientes, sin regularizador, etc.), entonces el descenso de gradiente tendrá una solución única y será el óptimo global. El descenso de gradiente puede y devolverá múltiples soluciones si se tiene un problema no convexo.

Aunque el OP pide una regresión lineal, el ejemplo a continuación muestra la minimización de mínimos cuadrados aunque no lineal (en lugar de la regresión lineal que el OP desea) puede tener múltiples soluciones y el descenso de gradiente puede devolver diferentes soluciones.

Puedo mostrar empíricamente usando un ejemplo sencillo que

1. La suma de errores cuadrados a veces puede no ser convexa, por lo tanto, tener múltiples soluciones
2. El método del descenso de gradiente puede proporcionar múltiples soluciones.

Considera el ejemplo en el que intentas minimizar los cuadrados para el siguiente problema:

donde intentas resolver para $w$ minimizando la función objetivo. La función anterior, aunque diferenciable, no es convexa y puede tener múltiples soluciones. Sustituyendo los valores reales para $a$, ver abajo.

$a_{12} =9,a_{13} = 1/9,a_{23}=9,a_{31}=1/9$

$$minimizar$$ $${(9-\frac{w_1}{w_2})^2+(\frac{1}{9}-\frac{w_1}{w_3})^2+(\frac{1}{9}-\frac{w_2}{w_1})^2+(9-\frac{w_2}{w_3})^2+(9-\frac{w_3}{w_1})^2+(\frac{1}{9}-\frac{w_3}{w_2})^2}$$

El problema anterior tiene 3 soluciones diferentes y son las siguientes:

$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 se muestra arriba, el problema de mínimos cuadrados puede no ser convexo y puede tener múltiples soluciones. Luego, el problema anterior se puede resolver utilizando un método de descenso de gradiente como el solver de Microsoft Excel y cada vez que lo ejecutamos terminamos obteniendo diferentes soluciones. Dado que el descenso de gradiente es un optimizador local y puede quedarse atascado en una solución local, es necesario usar diferentes valores iniciales para obtener el verdadero óptimo global. Un problema como este depende de los valores iniciales.

Answer 3

Esto se debe a que la función objetivo que estás minimizando es convexa, solo hay un mínimo/máximo. Por lo tanto, el óptimo local también es un óptimo global. El descenso de gradiente encontrará la solución eventualmente.

¿Por qué esta función objetivo es convexa? Esta es la belleza de usar el error cuadrático para minimización. La derivación y la igualdad a cero mostrarán claramente por qué esto es así. Es un problema bastante clásico y está cubierto casi en todas partes.