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

Leí esta declaración en un antiguo examen verdadero / falso:

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

Solución: falso

Mi pregunta es, ¿qué parte de esta pregunta está mal? ¿Por qué es falsa esta afirmación?

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 comprender. Aunque estas conexiones son simples y fáciles de aprender, son sutiles y a menudo se pasan por alto.

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 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.

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

La suma de los cuadrados de los residuos se simplifica a

(Este es un caso limitante de funciones objetivas que surgen en la práctica, como el discutido en ¿Puede el hessiano empírico de un estimador M ser indefinido ? , donde puede leer análisis detallados y ver gráficas de la función).

Debido a que los coeficientes de los cuadrados ( y ) son positivos y el determinante es positivo, esta es una forma cuadrática semidefinida positiva en . Se minimiza cuando , pero puede tener cualquier valor. Como la función objetivo no depende de , 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 en el valor inicial.$3$3 × 56 - ( 24 / 2 ) 2 = 24 ( μ , ν , λ ) μ = ν = 0 λ SSR λ $56$$3\times 56 - (24/2)^2 = 24$$(\mu,\nu,\lambda)$$\mu=\nu=0$$\lambda$$\operatorname{SSR}$$\lambda$$\lambda$

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 + yo z ~ y + x. El primero produce pero el segundo da . z =1+$\hat z = 1 - x$$\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 NAvalores deben interpretarse como ceros, pero con una advertencia de que existen múltiples soluciones. La advertencia fue posible debido a los análisis preliminares realizados Rque 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 una buena le advertiría de cierta incertidumbre de que había llegado a lo ó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 parámetros pueden crear dominios no convexos, lo que lleva a múltiples soluciones globales.

Un ejemplo muy simple es el problema de estimar una "media" para los datos sujetos a la restricción . Esto modela una situación que es algo opuesta a los métodos de regularización como la regresión de cresta, el lazo o la red elástica: insiste en que un parámetro del modelo no sea demasiado pequeño. (En este sitio han aparecido varias preguntas sobre cómo resolver problemas de regresión con tales restricciones de parámetros, lo que demuestra que surgen en la práctica).- 1 , 1 | μ | ≥ 1 /$\mu$$-1, 1$$|\mu| \ge 1/2$

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

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 : tiene dos puntos más bajos en , donde la suma de los cuadrados es . El resto de la parábola (que se muestra punteada) se elimina por la restricción, eliminando así su mínimo único de consideración.mu = ± 1 / 2 5 /$\mu$$\mu=\pm 1/2$$5/2$

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

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 ajustarse).

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

Aunque OP solicita una regresión lineal, el siguiente ejemplo muestra la minimización de mínimos cuadrados, aunque no lineal (frente a la regresión lineal que OP quiere) puede tener múltiples soluciones y el descenso del gradiente puede devolver una solución diferente.

Puedo mostrar empíricamente usando un ejemplo simple que

1. La suma de los errores al cuadrado puede ser no convexa, por lo tanto, tener múltiples soluciones
2. El método de descenso de gradiente puede proporcionar múltiples soluciones.

Considere el ejemplo en el que está tratando de minimizar los mínimos cuadrados para el siguiente problema:

$w$$a$

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

$minimize$ ${(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 ser no convexo y puede tener una solución múltiple. Luego, el problema anterior se puede resolver utilizando el método de descenso de gradiente, como el solucionador de Microsoft Excel, y cada vez que ejecutamos, obtenemos una solución diferente. Dado que el descenso de gradiente es un optimizador local y puede atascarse en una solución local, necesitamos usar diferentes valores iniciales para obtener un óptimo global óptimo. Un problema como este depende de los valores iniciales.

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

¿Por qué esta función objetivo es convexa? Esta es la belleza de usar el error al cuadrado para la minimización. La derivación y la igualdad a cero mostrarán muy bien por qué este es el caso. Es un problema bastante de libros de texto y está cubierto en casi todas partes.