Regresión lineal eficiente en línea

Question

Estoy analizando algunos datos en los que me gustaría realizar una regresión lineal ordinaria, sin embargo, esto no es posible ya que estoy tratando con una configuración en línea con un flujo continuo de datos de entrada (que rápidamente será demasiado grande para la memoria) y necesito actualizar las estimaciones de los parámetros mientras esto se consume, es decir, no puedo simplemente cargar todo en la memoria y realizar la regresión lineal en todo el conjunto de datos.

Estoy asumiendo un modelo de regresión lineal multivariante simple, es decir

$$\mathbf y = \mathbf A\mathbf x + \mathbf b + \mathbf e$$

¿Cuál es el mejor algoritmo para crear una estimación continuamente actualizada de los parámetros de regresión lineal $\mathbf A$ y $\mathbf b$ ?

Lo ideal sería:

• Me gustaría un algoritmo que sea lo más $\mathcal O(N\cdot M)$ la complejidad espacial y temporal de cada actualización, donde $N$ es la dimensionalidad de la variable independiente ( $\mathbf x$ ) y $M$ es la dimensionalidad de la variable dependiente ( $\mathbf y$ ).
• Me gustaría poder especificar algún parámetro para determinar cuánto se actualizan los parámetros por cada nueva muestra, por ejemplo, 0,000001 significaría que la siguiente muestra proporcionaría una millonésima parte de la estimación de los parámetros. Esto daría algún tipo de decaimiento exponencial para el efecto de las muestras en el pasado.

Answer 1

Maindonald describe un método secuencial basado en Rotaciones Givens . (Una rotación Givens es una transformación ortogonal de dos vectores que pone a cero una entrada determinada de uno de los vectores). En el paso anterior has descompuesto el matriz de diseño $\mathbf{X}$ en una matriz triangular $\mathbf{T}$ mediante una transformación ortogonal $\mathbf{Q}$ para que $\mathbf{Q}\mathbf{X} = (\mathbf{T}, \mathbf{0})'$ . (Es rápido y fácil obtener los resultados de la regresión de una matriz triangular.) Al adjuntar una nueva fila $v$ debajo de $\mathbf{X}$ , usted amplía de forma efectiva $(\mathbf{T}, \mathbf{0})'$ por una fila no nula, también, digamos $t$ . La tarea consiste en poner a cero esta fila manteniendo las entradas en la posición de $\mathbf{T}$ diagonal. Una secuencia de rotaciones Givens hace esto: la rotación con la primera fila de $\mathbf{T}$ pone a cero el primer elemento de $t$ y luego la rotación con la segunda fila de $\mathbf{T}$ pone a cero el segundo elemento, y así sucesivamente. El efecto es premultiplicar $\mathbf{Q}$ por una serie de rotaciones, lo que no cambia su ortogonalidad.

Cuando la matriz de diseño tiene $p+1$ columnas (que es el caso cuando se hace una regresión sobre $p$ variables más una constante), el número de rotaciones necesarias no supera $p+1$ y cada rotación cambia dos $p+1$ -vectores. El almacenamiento necesario para $\mathbf{T}$ es $O((p+1)^2)$ . Así, este algoritmo tiene un coste computacional de $O((p+1)^2)$ tanto en el tiempo como en el espacio.

Un enfoque similar le permite determinar el efecto en la regresión de la eliminación de una fila. Maindonald da fórmulas; también lo hace Belsley, Kuh y Welsh . Por lo tanto, si se busca una ventana móvil para la regresión, se pueden retener los datos de la ventana dentro de un búfer circular, adyacente al nuevo dato y dejando caer el antiguo con cada actualización. Esto duplica el tiempo de actualización y requiere $O(k (p+1))$ almacenamiento para una ventana de ancho $k$ . Parece que $1/k$ sería el análogo del parámetro de influencia.

Para el decaimiento exponencial, creo (especulando) que se podría adaptar este enfoque a los mínimos cuadrados ponderados, dando a cada nuevo valor un peso mayor que 1. No debería haber ninguna necesidad de mantener un buffer de valores anteriores ni de borrar ningún dato antiguo.

Referencias

J. H. Maindonald, Cálculo estadístico. J. Wiley & Sons, 1984. Capítulo 4.

D. A. Belsley, E. Kuh, R. E. Welsch, Diagnóstico de regresión: Identificación de datos influyentes y fuentes de colinealidad. J. Wiley & Sons, 1980.

Answer 2

Creo que la refundición de su modelo de regresión lineal en un modelo de espacio de estado le dará lo que busca. Si utiliza R, puede utilizar el paquete dlm y echa un vistazo a la libro de acompañamiento por Petris et al.

Answer 3

Siempre se puede realizar el descenso por gradiente sobre la suma de los cuadrados del coste $E$ en cuanto a los parámetros de su modelo $W$ . Sólo hay que tomar el gradiente de la misma pero no ir a por la solución de forma cerrada sino sólo a por la dirección de búsqueda.

Dejemos que $E(i; W)$ sea el coste de la muestra de entrenamiento i's dados los parámetros $W$ . Su actualización para el parámetro j's es entonces

$$W_{j} \leftarrow W_j + \alpha \frac{\partial{E(i; W)}}{\partial{W_j}}$$

donde $\alpha$ es una tasa de paso, que debe elegir mediante validación cruzada o una buena medida.

Esto es muy eficiente y es la forma en que las redes neuronales suelen ser entrenadas. Se pueden procesar incluso muchas muestras en paralelo (por ejemplo, unas 100) de forma eficiente.

Por supuesto, se pueden aplicar algoritmos de optimización más sofisticados (impulso, gradiente conjugado, ...).

Answer 4

Me sorprende que nadie haya tocado este tema hasta ahora. La regresión lineal tiene una función objetivo cuadrática. Por lo tanto, un paso de Newton Raphson desde cualquier punto de partida te lleva directamente al óptimo. Ahora, digamos que usted ya hizo su regresión lineal. La función objetivo es:

$$ L(\beta) = (y - X \beta)^t (y - X \beta) $$ El gradiente se convierte en $$ \nabla L (\beta) = -2 X^t (y - X \beta)$$ Y la arpillera: $$ \nabla^2 L (\beta) = X^t X$$

Ahora, tienes algunos datos pasados e hiciste una regresión lineal y estás sentado con tus parámetros ( $\beta$ ). El gradiente en este punto es cero por definición. La hessiana es la indicada anteriormente. Un nuevo punto de datos ( $x_{new}, y_{new}$ ) llega. Sólo hay que calcular el gradiente para el nuevo punto a través de:

$$\nabla L_{new}(\beta) = -2 x_{new} (y_{new}-x_{new}^T \beta)$$ y eso se convertirá en tu gradiente global (ya que el gradiente de los datos existentes era cero). El hessian para el nuevo punto de datos es:

$$\nabla^2 L_{new} = x_{new}x_{new}^T $$ .

Añade esto a la vieja arpillera dada anteriormente. A continuación, sólo tomar un paso de Newton Raphson.

$$\beta_{new} = \beta_{old} + (\nabla^2L)^{-1} \nabla L_{new}$$

Y ya está.

Answer 5

El ajuste estándar por mínimos cuadrados da los coeficientes de regresión

$ \beta = ( X^T X )^{-1} X^T Y $

donde X es una matriz de M valores para cada uno de los N puntos de datos, y tiene un tamaño NXM. Y es una matriz NX1 de salidas. $\beta$ por supuesto es una matriz de coeficientes MX1. (Si quieres un intercepto sólo tienes que hacer que un conjunto de x sea siempre igual a 1).

Para hacer esto en línea presumiblemente sólo tienes que llevar un registro de $X^T X$ y $X^T Y$ por lo que una matriz MXM y una matriz MX1. Cada vez que se obtiene un nuevo punto de datos se actualizan esos $M^2+M$ elementos, y luego calcular $\beta$ de nuevo, lo que le cuesta una inversión de la matriz MXM y la multiplicación de la matriz MXM y la matriz MX1.

Por ejemplo, si M=1, el coeficiente único es

$ \beta = \frac{\sum_{i=1}^N{x_i y_i}}{\sum_{i=1}^N{x_i^2}} $

por lo que cada vez que se obtiene un nuevo punto de datos se actualizan ambas sumas y se calcula la relación y se obtiene el coeficiente actualizado.

Si se quiere amortiguar geométricamente las estimaciones anteriores, supongo que se podría ponderar $X^T X$ y $X^T Y$ por $(1-\lambda)$ cada vez antes de añadir el nuevo término, donde $\lambda$ es un número pequeño.