Regresión lineal en línea eficiente

53

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 para actualizar las estimaciones de los parámetros mientras se consume. es decir, no puedo cargarlo todo en la memoria y realizar una regresión lineal en todo el conjunto de datos.

Asumo un modelo de regresión lineal multivariado simple, es decir

y = UNA X + si + mi

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

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

Idealmente:

Me gustaría un algoritmo que sea la mayor parte de la complejidad de espacio y tiempo por actualización, donde es la dimensionalidad de la variable independiente ( ) y es la dimensionalidad de la variable dependiente ( ). $\mathcal O(N\cdot M)$ $N$ $\mathbf x$ $M$ $\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 del parámetro. Esto daría algún tipo de disminución exponencial para el efecto de las muestras en el pasado distante.

time-series regression algorithms real-time mikera
fuente

2

Busque (1) Regresión lineal flexible, (2) Filtros de Kalman.

Jase

31

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

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

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

Para la disminución exponencial, creo (especulativamente) que podría adaptar este enfoque a los mínimos cuadrados ponderados, dando a cada nuevo valor un peso mayor que 1. No debería ser necesario mantener un búfer de valores anteriores o eliminar datos antiguos.

Referencias

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

DA Belsley, E. Kuh, RE Welsch, Diagnóstico de regresión: identificación de datos influyentes y fuentes de colinealidad. J. Wiley & Sons, 1980.

whuber
fuente

1

¿El método que describe Maindonald está relacionado o es igual al algoritmo de Gentleman? jstor.org/stable/2347147

onestop

66

En ese caso, vea también las extensiones de Alan Miller jstor.org/stable/2347583 . Un archivo de su sitio de software Fortran se encuentra ahora en jblevins.org/mirror/amiller

onestop

55

Aparece un algoritmo explícito en la parte inferior de la p. 4 de saba.kntu.ac.ir/eecd/people/aliyari/NN%20%20files/rls.pdf . Esto se puede encontrar buscando en Google "mínimos cuadrados recursivos". No parece una mejora en el enfoque Gentleman / Maindonald, pero al menos se describe de manera clara y explícita.

whuber

2

El último enlace se parece al método que iba a sugerir. La identidad matricial que utilizan se conoce en otros lugares como la identidad Sherman - Morrison - Woodbury. También es bastante eficiente desde el punto de vista numérico, pero puede no ser tan estable como una rotación de Givens.

cardenal

2

@suncoolsu Hmm ... El libro de Maindonald se publicó recientemente cuando comencé a usarlo :-).

whuber

8

Creo que reestructurar su modelo de regresión lineal en un modelo de espacio de estado le dará lo que busca. Si usa R, es posible que desee usar el paquete dlm y eche un vistazo al libro complementario de Petris et al.

F. Tusell
fuente

tal vez estoy confundido pero esto parece referirse a un modelo de serie temporal? mi modelo es en realidad más simple en que las muestras no son una serie de tiempo (la eficacia con que se x-> y) muestras (independientes, no son más que acumulan en grandes cantidades a través del tiempo)

mikera

1

Sí, en el caso general esto se usa para series de tiempo con observaciones no independientes; pero siempre puede suponer una correlación incorrecta entre observaciones sucesivas, lo que le da un caso especial de interés.

F. Tusell

7

Usted siempre puede realizar descenso de gradiente sobre la suma de los cuadrados costó WRT los parámetros de su modelo . Simplemente tome el gradiente de él, pero no busque la solución de formulario cerrado, sino solo la dirección de búsqueda. $E$ $W$

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

W_{j} \leftarrow W_{j} + α \frac{\partial mi (yo; W)}{\partial W_{j}}

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

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

Esto es muy eficiente y la forma en que se entrenan las redes neuronales. Puede procesar incluso muchas muestras en paralelo (por ejemplo, unas 100 o más) de manera eficiente.

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

bayerj
fuente

Parece muy similar a este documento eprints.pascal-network.org/archive/00002147/01/… . Se implementó en un proyecto de código abierto llamado jubatus.

sacarina

3

Sorprendido, nadie más tocó esto hasta ahora. La regresión lineal tiene una función objetivo cuadrática. Entonces, un paso de Newton Raphson desde cualquier punto de partida lo lleva directamente a la optima. Ahora, digamos que ya hiciste tu regresión lineal. La función objetivo es:

L (β) = (y - X β)^{t} (y - X β)

$L(\beta) = (y - X \beta)^t (y - X \beta)$ El gradiente se convierte en

\nabla L (β) = - 2 X^{t} (y - X β)

$\nabla L (\beta) = -2 X^t (y - X \beta)$ Y la arpillera:

\nabla^{2} L (β) = X^{t} X

$\nabla^2 L (\beta) = X^t X$

Ahora, obtuvo algunos datos pasados e hizo una regresión lineal y está sentado con sus parámetros ( $\beta$ ). El gradiente en este punto es cero por definición. El hessian es como se dio anteriormente. Llega un nuevo punto de datos ( $x_{new}, y_{new}$ ). Simplemente calcule el gradiente para el nuevo punto mediante:

\nabla L_{n e w} (β) = - 2 x_{n e w} (y_{n e w} - x_{n e w}^{T} β)

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

\nabla^{2} L_{n e w} = x_{n e w} x_{n e w}^{T}

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

Agregue esto al viejo hessian dado anteriormente. Luego, solo da un paso de Newton Raphson.

β_{n e w} = β_{o l d} + (\nabla^{2} L)^{- 1} \nabla L_{n e w}

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

Y tu estas listo.

ryu576
fuente

1

\nabla L_{n e w}

$\nabla L_{new}$

p,

$p,$

O (p^{3})

$O(p^3)$

O (p^{3})

$O(p^3)$

p

$p$

(I - A)^{- 1} = I + A + A^{2} + \dots

$(I-A)^{-1}=I+A+A^2+ \dots$

2

El ajuste estándar de mínimos cuadrados proporciona coeficientes de regresión

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

$\beta$

$X^T X$ $X^T Y$ $M^2+M$ $\beta$

Por ejemplo, si M = 1, entonces el coeficiente uno es

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

así que cada vez que obtienes un nuevo punto de datos actualizas ambas sumas y calculas la relación y obtienes el coeficiente actualizado.

$X^T X$ $X^T Y$ $(1-\lambda)$ $\lambda$

Mark Higgins
fuente

2

β

$\beta$

X^{T} X

$X^T X$

X^{T} Y

$X^T Y$

66

X^{'} X

$X'X$

1

C^{- 1} x

$C^{-1}x$

C

$C$

x

$x$

z_{t + 1} = z_{t} + x - C z_{t}

$z_{t+1}=z_t + x - Cz_t$

z \to C^{- 1} x

$z\to C^{-1}x$

t \to \infty

$t\to\infty$

1

El problema se resuelve más fácilmente cuando reescribe un poco las cosas:

Y = y

X = [x, 1]

entonces

Y = A * X

Se encuentra una solución única calculando

V = X '* X

y

C = X '* Y

tenga en cuenta que la V debe tener un tamaño N-por-N y C un tamaño de N-por-M. Los parámetros que está buscando vienen dados por:

A = inv (V) * C

Dado que tanto V como C se calculan sumando sus datos, puede calcular A en cada nueva muestra. Sin embargo, esto tiene una complejidad temporal de O (N ^ 3).

Como V es cuadrado y positivo semi-definido, existe una descomposición LU, que hace que la inversión de V sea numéricamente más estable. Existen algoritmos para realizar actualizaciones de rango 1 al inverso de una matriz. Encuéntralos y tendrás la implementación eficiente que estás buscando.

Los algoritmos de actualización de rango 1 se pueden encontrar en "Cálculos matriciales" de Golub y van Loan. Es un material resistente, pero tiene una visión general completa de tales algoritmos.

Nota: El método anterior proporciona una estimación de mínimos cuadrados en cada paso. Puede agregar fácilmente pesos a las actualizaciones de X e Y. Cuando los valores de X e Y crecen demasiado, puede escalarlos un solo escalar, sin afectar el resultado.

Señor White
fuente

Regresión lineal en línea eficiente

Respuestas:

Referencias