¿Qué algoritmo se utiliza en la regresión lineal?

Question

Suelo oír hablar de los "mínimos cuadrados ordinarios". ¿Es ese el algoritmo más utilizado para la regresión lineal? ¿Hay razones para utilizar uno diferente?

Answer 1

Para responder a la letra de la pregunta, los "mínimos cuadrados ordinarios" no son un algoritmo, sino un tipo de problema de álgebra lineal computacional, del que la regresión lineal es un ejemplo. Normalmente se tienen datos $\{(x_1,y_1),\dots,(x_m,y_m)\}$ y una función tentativa ("modelo") para ajustar los datos, de la forma $f(x)=c_1 f_1(x)+\dots+c_n f_n(x)$ . El $f_j(x)$ se denominan "funciones base" y pueden ser cualquier cosa, desde monomios $x^j$ a las funciones trigonométricas (por ejemplo $\sin(jx)$ , $\cos(jx)$ ) y las funciones exponenciales ( $\exp(-jx)$ ). El término "lineal" en "regresión lineal" no se refiere aquí a las funciones de base, sino a los coeficientes $c_j$ en el sentido de que al tomar la derivada parcial del modelo con respecto a cualquiera de los $c_j$ le da el factor que multiplica $c_j$ eso es, $f_j(x)$ .

Uno de ellos tiene ahora un $m\times n$ matriz rectangular $\mathbf A$ ("matriz de diseño") que (normalmente) tiene más filas que columnas, y cada entrada es de la forma $f_j(x_i)$ , $i$ siendo el índice de la fila y $j$ siendo el índice de la columna. OLS es ahora la tarea de encontrar el vector $\mathbf c=(c_1\,\dots\,c_n)^\top$ que minimiza la cantidad $\sqrt{\sum\limits_{j=1}^{m}\left(y_j-f(x_j)\right)^2}$ (en notación matricial, $\|\mathbf{A}\mathbf{c}-\mathbf{y}\|_2$ ; aquí, $\mathbf{y}=(y_1\,\dots\,y_m)^\top$ suele llamarse "vector de respuesta").

Existen al menos tres métodos utilizados en la práctica para calcular las soluciones por mínimos cuadrados: las ecuaciones normales, la descomposición QR y la descomposición del valor singular. En resumen, son formas de transformar la matriz $\mathbf{A}$ en un producto de matrices que se manipulan fácilmente para resolver el vector $\mathbf{c}$ .

George ya mostró el método de las ecuaciones normales en su respuesta; uno sólo resuelve la $n\times n$ conjunto de ecuaciones lineales

$\mathbf{A}^\top\mathbf{A}\mathbf{c}=\mathbf{A}^\top\mathbf{y}$

para $\mathbf{c}$ . Debido a que la matriz $\mathbf{A}^\top\mathbf{A}$ es simétrica positiva (semi)definida, el método habitual utilizado para ello es la descomposición de Cholesky, que factoriza $\mathbf{A}^\top\mathbf{A}$ en la forma $\mathbf{G}\mathbf{G}^\top$ con $\mathbf{G}$ una matriz triangular inferior. El problema de este enfoque, a pesar de la ventaja de poder comprimir la $m\times n$ matriz de diseño en una (normalmente) mucho más pequeña $n\times n$ es que esta operación es propensa a la pérdida de cifras significativas (esto tiene algo que ver con el "número de condición" de la matriz de diseño).

Una forma ligeramente mejor es la descomposición QR, que trabaja directamente con la matriz de diseño. Factoriza $\mathbf{A}$ como $\mathbf{A}=\mathbf{Q}\mathbf{R}$ , donde $\mathbf{Q}$ es una matriz ortogonal (al multiplicar una matriz de este tipo por su transpuesta se obtiene una matriz identidad) y $\mathbf{R}$ es triangular superior. $\mathbf{c}$ se calcula posteriormente como $\mathbf{R}^{-1}\mathbf{Q}^\top\mathbf{y}$ . Por razones en las que no voy a entrar (basta con ver cualquier texto de álgebra lineal numérica decente, como este ), éste tiene mejores propiedades numéricas que el método de las ecuaciones normales.

Una variación en el uso de la descomposición QR es la método de las ecuaciones seminormales . Brevemente, si se tiene la descomposición $\mathbf{A}=\mathbf{Q}\mathbf{R}$ el sistema lineal a resolver tiene la forma

$$\mathbf{R}^\top\mathbf{R}\mathbf{c}=\mathbf{A}^\top\mathbf{y}$$

En efecto, se utiliza la descomposición QR para formar el triángulo de Cholesky de $\mathbf{A}^\top\mathbf{A}$ en este enfoque. Esto es útil para el caso en que $\mathbf{A}$ es escaso, y el almacenamiento explícito y/o la formación de $\mathbf{Q}$ (o una versión factorizada de la misma) es indeseable o poco práctica.

Por último, la forma más cara, aunque más segura, de resolver OLS es la descomposición del valor singular (SVD). Esta vez, $\mathbf{A}$ se factoriza como $\mathbf{A}=\mathbf{U}\mathbf \Sigma\mathbf{V}^\top$ , donde $\mathbf{U}$ y $\mathbf{V}$ son ambos ortogonales, y $\mathbf{\Sigma}$ es una matriz diagonal, cuyas entradas diagonales se denominan "valores singulares". El poder de esta descomposición radica en la capacidad de diagnóstico que le otorgan los valores singulares, en el sentido de que si uno ve uno o más valores singulares diminutos, entonces es probable que haya elegido un conjunto de bases no del todo independiente, lo que hace necesaria una reformulación de su modelo. (El "número de condición" mencionado anteriormente está, de hecho, relacionado con la relación entre el valor singular más grande y el más pequeño; la relación, por supuesto, se vuelve enorme (y la matriz está, por tanto, mal condicionada) si el valor singular más pequeño es "diminuto").

Esto es sólo un esbozo de estos tres algoritmos; cualquier buen libro de estadística computacional y álgebra lineal numérica debería poder ofrecerle más detalles relevantes.

Answer 2

Respecto a la pregunta del título, sobre cuál es el algoritmo que se utiliza:

Desde la perspectiva del álgebra lineal, el algoritmo de regresión lineal es la forma de resolver un sistema lineal $\mathbf{A}x=b$ con más ecuaciones que incógnitas. En la mayoría de los casos no hay solución a este problema. Y esto se debe a que el vector $b$ no pertenece al espacio de columnas de $\mathbf{A}$ , $C(\mathbf{A})$ .

El best straight line es el que comete el error global $e=\mathbf{A}x-b$ tan pequeño como sea necesario. Y es conveniente pensar que lo pequeño es la longitud al cuadrado, $\lVert e \rVert^2$ porque no es negativo, y es igual a 0 sólo cuando $b\in C(\mathbf{A})$ .

Proyectando (ortogonalmente) el vector $b$ al punto más cercano en el espacio de la columna de $\mathbf{A}$ da el vector $b^*$ que resuelve el sistema (sus componentes se encuentran en la mejor línea recta) con el mínimo error.

$\mathbf{A}^T\mathbf{A}\hat{x}=\mathbf{A}^Tb \Rightarrow \hat{x}=(\mathbf{A}^T\mathbf{A})^{-1}\mathbf{A}^Tb$

y el vector proyectado $b^*$ está dada por:

$b^*=\mathbf{A}\hat{x}=\mathbf{A}(\mathbf{A}^T\mathbf{A})^{-1}\mathbf{A}^Tb$

Quizás el método de mínimos cuadrados no sea exclusivamente utilizado porque eso squaring compensa en exceso los valores atípicos.

Permítanme dar un ejemplo simple en R, que resuelve el problema de regresión utilizando este algoritmo:

library(fBasics)

reg.data <- read.table(textConnection("
   b      x
  12      0
  10      1
   8      2
  11      3
   6      4
   7      5
   2      6
   3      7
   3      8 "), header = T)

attach(reg.data)

A <- model.matrix(b~x)

# intercept and slope
inv(t(A) %*% A) %*% t(A) %*% b

# fitted values - the projected vector b in the C(A)
A %*% inv(t(A) %*%A ) %*% t(A) %*% b

# The projection is easier if the orthogonal matrix Q is used, 
# because t(Q)%*%Q = I
Q <- qr.Q(qr(A))
R <- qr.R(qr(A))

# intercept and slope 
best.line <- inv(R) %*% t(Q) %*% b

# fitted values 
Q %*% t(Q) %*% b

plot(x,b,pch=16)
abline(best.line[1],best.line[2])

Answer 3

El enlace de la wiki: Métodos de estimación de la regresión lineal ofrece una lista bastante completa de los métodos de estimación, incluido el método OLS, y los contextos en los que se utilizan métodos de estimación alternativos.

Answer 4

Es fácil confundirse entre las definiciones y la terminología. Ambos términos se utilizan, a veces indistintamente. Una búsqueda rápida en Wikipedia debería ayudar:

• mínimos cuadrados ordinarios
• Regresión cercana

Los mínimos cuadrados ordinarios (MCO) son un método utilizado para ajustar modelos de regresión lineal. Debido a la coherencia y eficacia demostrables (bajo supuestos complementarios) del método MCO, es el enfoque dominante. Consulte los artículos para obtener más pistas.

Answer 5

Suelo pensar en los "mínimos cuadrados" como un criterio para definir la línea de regresión que mejor se ajusta (es decir, la que hace que la suma de los residuos "al cuadrado" sea "menor") y el "algoritmo" en este contexto como el conjunto de pasos utilizados para determinar los coeficientes de regresión que satisfacen ese criterio. Esta distinción sugiere que es posible tener diferentes algoritmos que satisfagan el mismo criterio.

Me gustaría saber si otros hacen esta distinción y qué terminología utilizan.