¿Qué algoritmo se usa en regresión lineal?

Usualmente escucho sobre "mínimos cuadrados ordinarios". ¿Es ese el algoritmo más utilizado para la regresión lineal? ¿Hay razones para usar una diferente?

Con respecto a la pregunta en el título, sobre cuál es el algoritmo que se utiliza:

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

El best straight linees el que hace que el error general tan pequeño como sea necesario. Y es conveniente pensar que la longitud al cuadrado es tan pequeña, , porque no es negativa, y es igual a 0 solo cuando b \ en C (\ mathbf {A}) .$e=\mathbf{A}x-b$$\lVert e \rVert^2$$b\in C(\mathbf{A})$

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

$\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 viene dado por:$b^*$

$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 se usa exclusivamente porque squaring compensa en exceso los valores atípicos.

Permítanme dar un ejemplo simple en R, que resuelve el problema de regresión usando 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])

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

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

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

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

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

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

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

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

Efectivamente, uno está utilizando la descomposición QR para formar el triángulo Cholesky de en este enfoque. Esto es útil para el caso donde es escaso, y el almacenamiento explícito y / o la formación de (o una versión factorizada de este) no es deseable o poco práctico.$\mathbf{A}^\top\mathbf{A}$$\mathbf{A}$$\mathbf{Q}$

Finalmente, la forma más costosa, pero más segura, de resolver OLS es la descomposición de valores singulares (SVD). Esta vez, se factoriza como , donde y son ortogonales y$\mathbf{A}$$\mathbf{A}=\mathbf{U}\mathbf \Sigma\mathbf{V}^\top$$\mathbf{U}$$\mathbf{V}$$\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 minúsculos, es probable que haya elegido un conjunto de bases no completamente independiente, por lo que necesita una reformulación de tu modelo (El "número de condición" mencionado anteriormente está de hecho relacionado con la relación del valor singular más grande al más pequeño; la relación, por supuesto, se vuelve enorme (y la matriz está mal condicionada) si el valor singular más pequeño es "pequeño" .)

Esto es simplemente un bosquejo de estos tres algoritmos; cualquier buen libro sobre estadística computacional y álgebra lineal numérica debería poder brindarle detalles más relevantes.

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

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

• mínimos cuadrados ordinarios
• regresión cercana

Mínimos cuadrados ordinarios (MCO) es un método utilizado para ajustar modelos de regresión lineal. Debido a la consistencia y eficiencia demostrables (bajo supuestos suplementarios) del método MCO, es el enfoque dominante. Ver los artículos para más clientes potenciales.

Tiendo a 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 "cuadrados" residuales 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 usan.

Un libro viejo, pero uno al que me encuentro recurriendo repetidamente, es

Lawson, CL y Hanson, RJ Solucionando problemas de mínimos cuadrados , Prentice-Hall, 1974.

Contiene una discusión detallada y muy legible de algunos de los algoritmos que las respuestas anteriores han mencionado. Es posible que desee verlo.