Aprendizaje automático online
En las ciencias de la computación, el aprendizaje automático online es un método de aprendizaje automático en el que los datos están disponibles en un orden secuencial y se utilizan para actualizar el mejor predictor para datos futuros en cada paso, a diferencia de las técnicas de aprendizaje por lotes, que generan el mejor predictor aprendiendo sobre todo el conjunto de datos de entrenamiento a la vez. El aprendizaje online es una técnica comúnmente utilizada en áreas del aprendizaje automático en las que es inviable desde el punto de vista computacional entrenar sobre todo el conjunto de datos, lo que requiere la necesidad de algoritmos de memoria externa. También se utiliza en situaciones en las que es necesario que el algoritmo se adapte dinámicamente a nuevos patrones en los datos, o cuando los propios datos se generan en función del tiempo, por ejemplo, la predicción del precio de las acciones. Los algoritmos de aprendizaje online pueden ser propensos a sufrir interferencias catastróficas, un problema que puede resolverse mediante enfoques de aprendizaje incremental.
Introducción
En el entorno del aprendizaje supervisado, una función de será aprendida, en el que es considerado como un espacio de entradas y como un espacio de salidas que predice bien sobre instancias que se extraen de una distribución de probabilidad conjunta en . En realidad, el aprendiz nunca conoce la distribución verdadera , sobre instancias. En su lugar, el aprendiz suele tener acceso a un conjunto de ejemplos de entrenamiento . En este caso, la función de pérdida es la siguiente , de modo que mide la diferencia entre el valor predicho y el valor real . El objetivo ideal es seleccionar una función , en elq ue es un espacio de funciones llamado espacio de hipótesis, de modo que se minimiza alguna noción de pérdida total. Dependiendo del tipo de modelo (estadístico o adversarial), se pueden concebir diferentes nociones de pérdida, que conducen a diferentes algoritmos de aprendizaje.
Visión estadística del aprendizaje online
En los modelos de aprendizaje estadístico, las muestras de entrenamiento se asumen que han sido extraídas de la distribución verdadera y el objetivo es minimizar el "riesgo" esperado
Un paradigma común en esta situación es estimar una función mediante la minimización empírica del riesgo o la minimización empírica regularizada del riesgo (normalmente la regularización de Tikhonov). La elección de la función de pérdida aquí da lugar a varios algoritmos de aprendizaje bien conocidos, como los mínimos cuadrados regularizados y las máquinas de vectores de soporte. Un modelo puramente online de esta categoría aprendería basándose sólo en la nueva entrada , el mejor predictor actual y alguna información adicional almacenada (que normalmente se espera que tenga requisitos de almacenamiento independientes del tamaño de los datos de entrenamiento). Para muchas formulaciones, por ejemplo los métodos kernel no lineales, el verdadero aprendizaje online no es posible, aunque puede utilizarse una forma de aprendizaje online híbrido con algoritmos recursivos donde puede depender de y todos los puntos de datos anteriores . En este caso, ya no se garantiza que los requisitos de espacio sean constantes, ya que requiere almacenar todos los puntos de datos anteriores, pero la solución puede tardar menos en calcularse con la adición de un nuevo punto de datos, en comparación con las técnicas de aprendizaje por lotes.
Una estrategia común para superar los problemas anteriores es aprender utilizando minilotes, que procesan un pequeño lote de puntos de datos a la vez, esto puede considerarse como pseudoaprendizaje online para mucho menor que el número total de puntos de entrenamiento. Las técnicas de minilotes se utilizan con pasadas repetidas sobre los datos de entrenamiento para obtener versiones optimizadas de memoria externa de algoritmos de aprendizaje automático, por ejemplo, el descenso de gradiente estocástico. Cuando se combina con la retropropagación, éste es actualmente el método de entrenamiento de facto para entrenar redes neuronales artificiales.
Ejemplo: mínimos cuadrados lineales
El sencillo ejemplo de los mínimos cuadrados lineales se utiliza para explicar diversas ideas del aprendizaje online. Las ideas son lo suficientemente generales como para aplicarse a otros entornos, por ejemplo, con otras funciones de pérdida convexas.
Aprendizaje por lotes
También llamado como "batch learning" (en inglés). Consideremos el aprendizaje supervisado con una función lineal que debe aprenderse:
donde es un vector de entradas (puntos de datos) y es un vector de filtro lineal. El objetivo es calcular el vector de filtro . Para ello, una función de pérdida cuadrada
se utiliza para calcular el vector que minimiza la pérdida empírica
donde
.
Sea la matriz de datos y es el vector columna de valores objetivo tras la llegada de los primeros puntos de datos . Suponiendo que la matriz de covarianza es invertible (en caso contrario es preferible proceder de forma similar con la regularización de Tikhonov), la mejor solución al problema lineal de mínimos cuadrados viene dado por
Ahora, calculando la matriz de covarianza requiere tiempo , invirtiendo la matriz requiere tiempo , mientras que el resto de la multiplicación requiere el tiempo , lo que da un tiempo total de . Cuando hay puntos totales en el conjunto de datos, para volver a calcular la solución tras la llegada de cada punto de datos , el enfoque ingenuo tendrá una complejidad total . Obsérvese que al almacenar la matriz , para actualizarla en cada paso sólo es necesario añadir , que requiere tiempo, reduciendo el tiempo total a , pero con un espacio de almacenamiento adicional de para almacenar .[1]
Aprendizaje online: mínimos cuadrados recursivos
El algoritmo de mínimos cuadrados recursivos (en inglés: recursive least squares, RLS) considera un enfoque online al problema de mínimos cuadrados. Se puede demostrar que inicializando y , la solución del problema lineal de mínimos cuadrados dado en la sección anterior puede calcularse mediante la siguiente iteración:
El algoritmo de iteración anterior puede demostrarse mediante inducción sobre .[2] La prueba también muestra que . También se puede considerar el RLS en el contexto de los filtros adaptativos (véase RLS).
La complejidad para pasos de este algoritmo es , que es un orden de magnitud más rápido que la complejidad del aprendizaje por lotes correspondiente. Los requisitos de almacenamiento en cada paso son almacenar la matriz , que es constante en . Para el caso en que no es invertible, consideremos la versión regularizada de la función de pérdida del problema . Entonces, es fácil demostrar que el mismo algoritmo funciona con , y las iteraciones proceden para dar .[1]
Descenso de gradiente estocástico
Cuando
es reemplazado por
o por , se convierte en el algoritmo de descenso de gradiente estocástico. En este caso, la complejidad para pasos de este algoritmo se reduce a . Las necesidades de almacenamiento en cada paso son constantes en .
Sin embargo, el step size debe elegirse cuidadosamente para resolver el problema de minimización del riesgo esperado, como se ha detallado anteriormente. Al elegir un step size decreciente se puede demostrar la convergencia de la iterada media . Este escenario es un caso especial de optimización estocástica, un problema bien conocido en optimización.[1]
Descenso de gradiente estocástico incremental
En la práctica, se pueden realizar múltiples pasadas de gradiente estocástico (también llamadas ciclos o épocas) sobre los datos. El algoritmo así obtenido se denomina método de gradiente incremental y corresponde a una iteración
La principal diferencia con el método del gradiente estocástico es que aquí una secuencia se elige para decidir qué punto de entrenamiento se visita en la secuencia -n paso. Esta secuencia puede ser estocástica o determinista. El número de iteraciones se desacopla del número de puntos (cada punto puede considerarse más de una vez). Se puede demostrar que el método del gradiente incremental proporciona un minimizador del riesgo empírico.[3] Las técnicas incrementales pueden ser ventajosas cuando se consideran funciones objetivo compuestas por una suma de muchos términos, por ejemplo, un error empírico correspondiente a un conjunto de datos muy grande.[1]
Métodos kernel
Los kernels pueden utilizarse para ampliar los algoritmos anteriores a modelos no paramétricos (o modelos en los que los parámetros forman un espacio dimensional infinito). El procedimiento correspondiente ya no será verdaderamente online e implicará el almacenamiento de todos los puntos de datos, pero sigue siendo más rápido que el método de fuerza bruta. Esta discusión se limita al caso de la pérdida cuadrada, aunque puede extenderse a cualquier pérdida convexa. Se puede demostrar mediante una fácil inducción[1] que si es la matriz de datos y es la salida después de pasos del algoritmo SGD, entonces,
donde y la secuencia satisface la recursión
y
.
Observe que aquí es simplemente el Kernel estándar en y el predictor es de la forma
.
Ahora bien, si en su lugar se introduce un kernel general y dejamos que el predictor sea
entonces la misma prueba mostrará también que el predictor que minimiza la pérdida por mínimos cuadrados se obtiene cambiando la recursión anterior por
La expresión anterior requiere almacenar todos los datos para actualizar . La complejidad de tiempo total para la recursión cuando se evalúa para el -n punto de datos es , donde es el coste de evaluar el kernel en un único par de puntos.[1] Así, el uso del kernel ha permitido pasar de un espacio de parámetros de dimensión finita a una característica de dimensión posiblemente infinita representada por el kernel , realizando en su lugar la recursión en el espacio de parámetros , cuya dimensión es igual al tamaño del conjunto de datos de entrenamiento. En general, esto es una consecuencia del teorema del representador.[1]
Optimización convexa online
La optimización convexa online (en inglés: online convex optimization, OCO)[4] es un marco general para la toma de decisiones que aprovecha la optimización convexa para permitir algoritmos eficientes. El marco es el de un juego repetido:
Para
- El aprendiz recibe la entrada
- El aprendiz emite a partir de un conjunto convexo fijo
- La naturaleza devuelve una función de pérdida convexa .
- El aprendiz sufre una pérdida y actualiza su modelo
El objetivo es minimizar el arrepentimiento, o la diferencia entre la pérdida acumulada y la pérdida del mejor punto fijo en retrospectiva. Como ejemplo, consideremos el caso de la regresión lineal por mínimos cuadrados online. Aquí, los vectores de peso provienen del conjunto convexo y la naturaleza devuelve la función de pérdida convexa . Nótese aquí que se envía implícitamente con .
Sin embargo, algunos problemas de predicción online no encajan en el marco de OCO. Por ejemplo, en la clasificación online, el dominio de predicción y las funciones de pérdida no son convexas. En estos casos, se utilizan dos técnicas sencillas de convexificación: la aleatorización y las funciones de pérdida sustitutas.
Algunos algoritmos sencillos de optimización convexa online son:
Seguir al líder (FTL)
La regla de aprendizaje más sencilla que se puede probar es seleccionar (en el paso actual) la hipótesis que tenga la menor pérdida en todas las rondas pasadas. A este algoritmo se le llama Seguir al líder (en inglés: Follow the leader, FTL), y simplemente se le da la ronda por:
Este método puede considerarse un algoritmo voraz. Para el caso de la optimización cuadrática online (donde la función de pérdida es ), se puede mostrar un límite de arrepentimiento que crece como . Sin embargo, no se pueden obtener límites similares para el algoritmo FTL para otras familias importantes de modelos como la optimización lineal online. Para ello, se modifica el FTL añadiendo regularización.
Seguir al líder regularizado (FTRL)
Seguir al líder regularizado (en inglés: follow the regularised leader, FTRL) es una modificación natural del FTL que se utiliza para estabilizar las soluciones FTL y obtener mejores límites de arrepentimiento. Una función de regularización , y el aprendizaje se realiza en la ronda de la siguiente manera:
Como ejemplo especial, considérese el caso de una optimización linear online, en otras palabras, cuando la naturaleza devuelve las funciones de pérdida de la forma . Además, déjese . Supongamos que la función de regularización se elige para algún número positivo . Entonces, se puede demostrar que la iteración que minimiza el arrepentimiento se convierte en
Nótese que esto puede ser reescrito como , que se parece exactamente a un descenso de gradiente online.
Si en cambio es algún subespacio convexo de , tendría que ser proyectado, lo que lleva a la regla de actualización modificada
Este algoritmo se conoce como proyección perezosa, ya que el vector acumula los gradientes. También se conoce como algoritmo de promedio dual de Nesterov. En este escenario de funciones de pérdida lineales y regularización cuadrática, el arrepentimiento está limitado por y, por tanto, el arrepentimiento medio se reduce a , tal y como se desea.
Descenso por subgradiente online (OSD)
Lo anterior demostró un límite de arrepentimiento para funciones de pérdida lineales . Para generalizar el algoritmo a cualquier función de pérdida convexa, el subgradiente de se utiliza como aproximación lineal a cerca de , dando lugar al algoritmo de descenso subgradiente online:
Inicializar el parámetro
Para
- Predecir utilizando , recibir de la naturaleza.
- Elija
- Si , actualizar como
- Si , proyectar los gradientes acumulativos sobre , es decir,
Se puede utilizar el algoritmo OSD para obtener límites de arrepentimiento para la versión online de las SVM de clasificación, que utilizan la pérdida de bisagra
Otros algoritmos
Los algoritmos FTRL regularizados cuadráticamente conducen a algoritmos de gradiente perezosamente proyectado como los descritos anteriormente. Para utilizar lo anterior para funciones convexas y regularizadores arbitrarios, se utiliza el descenso de espejo online. La regularización óptima en retrospectiva puede derivarse para funciones de pérdida lineales, lo que conduce al algoritmo AdaGrad. Para la regularización euclidiana, se puede mostrar un límite de arrepentimiento de que puede mejorarse hasta un valor de para funciones de pérdida fuertemente convexas y expocóncavas.
Aprendizaje continuo
El aprendizaje continuo significa mejorar constantemente el modelo aprendido procesando flujos continuos de información.[5] Las capacidades de aprendizaje continuo son esenciales para los sistemas de software y los agentes autónomos que interactúan en un mundo real en constante cambio. Sin embargo, el aprendizaje continuo es un reto para el aprendizaje automático y los modelos de redes neuronales, ya que la adquisición continua de información disponible de forma incremental a partir de distribuciones de datos no estacionarias suele conducir a un olvido catastrófico.
Interpretaciones del aprendizaje en línea
El paradigma del aprendizaje online tiene diferentes interpretaciones dependiendo de la elección del modelo de aprendizaje, cada una de las cuales tiene implicaciones distintas sobre la calidad predictiva de la secuencia de funciones . Para esta discusión se utiliza el algoritmo de descenso de gradiente estocástico prototípico. Como se ha señalado anteriormente, su recursión viene dada por
La primera interpretación considera el método de descenso de gradiente estocástico aplicado al problema de minimización del riesgo esperado definido anteriormente.[6] En efecto, en el caso de un flujo infinito de datos, puesto que los ejemplos se suponen extraídos i.i.d. de la distribución , la secuencia de gradientes de en la iteración anterior son una muestra i.i.d. de estimaciones estocásticas del gradiente del riesgo esperado y, por lo tanto, se pueden aplicar los resultados de complejidad del método de descenso de gradiente estocástico para acotar la desviación , donde es el minimizador de .[7] Esta interpretación también es válida en el caso de un conjunto de entrenamiento finito; aunque con múltiples pasadas por los datos los gradientes ya no son independientes, aún pueden obtenerse resultados de complejidad en casos especiales.
La segunda interpretación se aplica al caso de un conjunto de entrenamiento finito y considera el algoritmo SGD como una instancia del método de descenso de gradiente incremental.[3] En este caso, se considera el riesgo empírico:
Dado que los gradientes de en las iteraciones de descenso de gradiente incremental son también estimaciones estocásticas del gradiente de . Esta interpretación también está relacionada con el método de descenso de gradiente estocástico, pero aplicado para minimizar el riesgo empírico en lugar del riesgo esperado. Dado que esta interpretación se refiere al riesgo empírico y no al riesgo esperado, se permiten fácilmente múltiples pasadas a través de los datos y, de hecho, conducen a límites más estrictos en las desviaciones , donde es el minimizador de .
Implementaciones
- Vowpal Wabbit: sistema de aprendizaje online rápido de memoria externa de código abierto que destaca por admitir varias reducciones de aprendizaje automático, ponderación de importancia y una selección de diferentes funciones de pérdida y algoritmos de optimización. Utiliza el hashing trick para limitar el tamaño del conjunto de características independientemente de la cantidad de datos de entrenamiento.
- scikit-learn: Proporciona implementaciones fuera del núcleo de algoritmos para
- Clasificación: Perceptrón, clasificador SGD, clasificador bayesiano ingenuo.
- Regresión: Regresor SGD, Regresor agresivo pasivo.
- Agrupación: Minilote k-medias.
- Extracción de características: Aprendizaje de diccionario en mini lotes, PCA incremental.
Véase también
Paradigmas del aprendizaje automático
- Aprendizaje activo
- Aprendizaje por imitación
- Aprendizaje por refuerzo
- Aprendizaje supervisado
- Aprendizaje vago
- Bandido multibrazo
Algoritmos generales
Modelos de aprendizaje
Referencias
- ↑ a b c d e f g Rosasco, L.; Poggio, T. (2015). «Machine Learning: a Regularization Approach, MIT-9.520 Lectures Notes, Manuscript, Dec. 2015.». Chapter 7 - Online Learning.
- ↑ Yin, Harold J. Kushner, G. George (2003). New York, ed. Stochastic approximation and recursive algorithms and applications (2 edición). Springer. pp. 8–12. ISBN 978-0-387-21769-7.
- ↑ a b Bertsekas, D. P. (2011). «Incremental gradient, subgradient, and proximal methods for convex optimization: a survey.». Optimization for Machine Learning: 85.
- ↑ Hazan, Elad (2015). Introduction to Online Convex Optimization. Foundations and Trends in Optimization.
- ↑ Parisi, German I.; Kemker, Ronald; Part, Jose L.; Kanan, Christopher; Wermter, Stefan (2019). «Continual lifelong learning with neural networks: A review». Neural Networks 113: 54-71. ISSN 0893-6080. doi:10.1016/j.neunet.2019.01.012.
- ↑ Bottou, Léon (1998). «Online Algorithms and Stochastic Approximations». Online Learning and Neural Networks. Cambridge University Press. ISBN 978-0-521-65263-6.
- ↑ Kushner, Harold J.; Yin, G. George (2003). «Stochastic Approximation and Recursive Algorithms and Applications». Stochastic Approximation Algorithms and Applications (2 edición). New York: Springer-Verlag. ISBN 0-387-00894-2.
Enlaces externos
- Alexander Rakhlin. 6.883: Online Methods in Machine Learning: Theory and Applications. MIT (en inglés)