¿Existen algoritmos para calcular los parámetros de regresión lineal o logística "en marcha"?

Question

Un documento "Calculando con precisión la varianza en funcionamiento" en http://www.johndcook.com/standard_deviation.html muestra cómo calcular la media, la varianza y las desviaciones estándar.

¿Existen algoritmos en los que los parámetros de un modelo de regresión lineal o logística puedan actualizarse de forma similar "dinámicamente" a medida que se proporciona cada nuevo registro de entrenamiento?

Answer 1

Los coeficientes de regresión lineal de $y = ax + b$ son $a = cov(x,y)/var(x)$ y $b = mean(y) - a \cdot mean(x)$ .

Así que todo lo que necesitas es un método incremental para calcular $cov(x,y)$ . A partir de este valor y de la varianza de $x$ y la media de ambos $y$ y $x$ puede calcular los parámetros $a$ y $b$ . Como se puede ver en el pseudocódigo dado a continuación, el cálculo incremental de $cov(x,y)$ es muy similar al cálculo incremental de $var(x)$ . Esto no debería ser una sorpresa porque $var(x) = cov(x,x)$ .

Aquí está el pseudocódigo que probablemente esté buscando:

init(): meanX = 0, meanY = 0, varX = 0, covXY = 0, n = 0

update(x,y):
n += 1
dx = x - meanX
dy = y - meanY
varX += (((n-1)/n)*dx*dx - varX)/n
covXY += (((n-1)/n)*dx*dy - covXY)/n
meanX += dx/n
meanY += dy/n

getA(): return covXY/varX
getB(): return meanY - getA()*meanX

Encontré esta pregunta mientras buscaba un algoritmo equivalente que calculara incrementalmente una regresión multivariada como $R = (X'X)^{-1}X'Y $ para que $ XR = Y+\epsilon $

Answer 2

Para sus dos ejemplos concretos:

Regresión lineal El papel "Regresión lineal en línea y su aplicación al aprendizaje por refuerzo basado en modelos" de Alexander Strehl y Michael Littman describe un algoritmo llamado "KWIK Linear Regression" (ver algoritmo 1) que proporciona una aproximación a la solución de regresión lineal utilizando actualizaciones incrementales. Obsérvese que se trata de no regularizado (es decir, no es una regresión Ridge). Estoy bastante seguro de que el método de Strehl & Littman no puede extenderse a esa configuración.

Regresión logística

Este hilo arroja algo de luz sobre el asunto. Cita:

Incluso sin una restricción de regularización, la regresión logística es un problema de optimización no lineal. Ya esto no tiene una solución analítica, que suele ser un requisito previo para derivar una solución de actualización. Con una restricción de regularización, se convierte en un problema de optimización restringida. Esto introduce todo un nuevo conjunto de complicaciones no analíticas además de las que ya tenía el problema no restringido.

No obstante, existen otros métodos en línea (o incrementales) para la regresión que quizá desee consultar, por ejemplo Regresión de proyección ponderada localmente (LWPR)

Answer 3

Como principio general:

0) se mantienen las estadísticas suficientes y las estimaciones actuales de ML

1) cuando obtenga nuevos datos, actualice las estadísticas suficientes y las estimaciones

2) Cuando no tenga suficientes estadísticas, tendrá que utilizar todos los datos.

3) Normalmente no tienes soluciones de forma cerrada; utiliza los MLEs anteriores como punto de partida, utiliza algún método de optimización conveniente para encontrar el nuevo óptimo a partir de ahí. Es posible que tenga que experimentar un poco para encontrar qué enfoques hacen las mejores compensaciones para sus tipos particulares de casos de problemas.

Si tu problema tiene una estructura especial, probablemente puedas explotarla.

Un par de referencias potenciales que pueden tener algún valor o no:

McMahan, H. B. y M. Streeter (2012),
Problema abierto: mejores límites para la regresión logística en línea ,
JMLR: Actas de talleres y conferencias , vol. 23, 44,1-44,3

Penny, W.D. y S.J. Roberts (1999),
Regresión logística dinámica ,
Actas IJCNN '99

Answer 4

Añadiendo a la respuesta de tdc, no hay métodos conocidos para calcular estimaciones exactas de los coeficientes en cualquier punto del tiempo con sólo un tiempo constante por iteración. Sin embargo, hay algunas alternativas que son razonables e interesantes.

El primer modelo que hay que ver es el aprendizaje en línea ajuste. En este escenario, el mundo anuncia primero un valor de x, su algoritmo predice un valor para y, el mundo anuncia el valor verdadero y', y su algoritmo sufre una pérdida l(y,y'). Para este escenario se sabe que los algoritmos simples (descenso de gradiente y gradiente exponencial, entre otros) logran un arrepentimiento sublineal. Esto significa que, a medida que se ven más ejemplos, el número de errores adicionales que comete el algoritmo (en comparación con el mejor predictor lineal posible) no crece con el número de ejemplos. Esto funciona incluso en entornos adversariales. Existe una buen papel explicando una estrategia popular para probar estos límites de arrepentimiento. La obra de Shai Shalev-Schwartz notas de clase también son útiles.

Existe una extensión de la configuración de aprendizaje en línea llamada configuración de bandido, en la que su algoritmo sólo recibe un número que representa lo equivocado que estaba (y ningún indicador de la respuesta correcta). Es impresionante que muchos de los resultados del aprendizaje en línea se trasladen a este escenario, salvo que aquí uno se ve obligado a explorar además de explotar, lo que lleva a todo tipo de retos interesantes.

Answer 5

Puedes utilizar algún paquete estándar de Filtro de Kalman en R para esto - sspir, dlm, kfas, etc. Creo que el KF es un área mucho más desarrollada que el aprendizaje en línea, por lo que puede ser más práctico. Usted puede utilizar un modelo $$y_t = \beta_t\cdot x_t + \varepsilon_t, \\ \beta_t = \beta_{t-1}+ \eta_t$$ para permitir que sus coeficientes de regresión varíen lentamente con el tiempo y KF los reestimará en cada paso (con un coste de tiempo constante) basándose en los datos más recientes. Alternativamente, puede establecerlos como constantes $$\beta_t = \beta_{t-1}$$ y KF seguirá reestimándolos en cada paso, pero esta vez asumiendo que son constantes y sólo incorporando nuevos datos observados para producir estimaciones cada vez mejores de los mismos valores de los coeficientes.

Se puede formular un modelo similar para la regresión logística, $$y_t = logit(\beta_t\cdot x_t + \varepsilon_t), \\ \beta_t = \beta_{t-1}+ \eta_t$$ como será no lineal, tendrá que utilizar el método de filtrado no lineal de los paquetes anteriores - EKF o UKF.