En informática , el aprendizaje automático en línea 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 de datos futuros en cada paso, en contraposición a las técnicas de aprendizaje por lotes que generan el mejor predictor mediante el aprendizaje. en todo el conjunto de datos de entrenamiento a la vez. El aprendizaje en línea es una técnica común que se usa en áreas de aprendizaje automático donde no es factible computacionalmente entrenar sobre todo el conjunto de datos, lo que requiere la necesidad de algoritmos fuera del núcleo . 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 datos en sí se generan en función del tiempo, por ejemplo, predicción del precio de las acciones.. Los algoritmos de aprendizaje en línea pueden ser propensos a interferencias catastróficas , un problema que puede abordarse mediante enfoques de aprendizaje incremental .
Introducción
En el ámbito del aprendizaje supervisado , una función de es para aprender, donde se piensa como un espacio de entradas y como un espacio de salidas, que predice bien en instancias que se extraen de una distribución de probabilidad conjunta en . En realidad, el alumno nunca conoce la verdadera distribuciónsobre instancias. En cambio, el alumno suele tener acceso a un conjunto de ejemplos de formación.. En esta configuración, la función de pérdida se da como, tal que mide la diferencia entre el valor predicho y el verdadero valor . El objetivo ideal es seleccionar una función, dónde 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 contradictorio), se pueden idear diferentes nociones de pérdida, que conducen a diferentes algoritmos de aprendizaje.
Vista estadística del aprendizaje en línea
En modelos estadísticos de aprendizaje, la muestra de entrenamiento se supone que se han extraído de la distribución real 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 del riesgo empírico o la minimización del riesgo empírico regularizado (generalmente 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 mínimos cuadrados regularizados y máquinas de vectores de soporte . Un modelo puramente en línea en esta categoría aprendería basándose solo en la nueva entrada, el mejor predictor actual y algo de 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 de kernel no lineales , el verdadero aprendizaje en línea no es posible, aunque se puede utilizar una forma de aprendizaje híbrido en línea con algoritmos recursivos donde se permite 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 a usar mini lotes, que procesan un pequeño lote de puntos de datos a la vez, esto puede considerarse como aprendizaje pseudo-en línea para mucho menor que el número total de puntos de entrenamiento. Las técnicas de mini lotes se utilizan con el paso repetido de los datos de entrenamiento para obtener versiones optimizadas fuera del núcleo [ aclaración necesaria ] de los algoritmos de aprendizaje automático, por ejemplo, descenso de gradiente estocástico . Cuando se combina con la retropropagación , este es actualmente el método de entrenamiento de facto para entrenar redes neuronales artificiales .
Ejemplo: mínimos cuadrados lineales
El ejemplo simple de mínimos cuadrados lineales se utiliza para explicar una variedad de ideas en el aprendizaje en línea. Las ideas son lo suficientemente generales como para aplicarse a otros entornos, por ejemplo, con otras funciones de pérdida convexa.
Aprendizaje por lotes
Considere el entorno del aprendizaje supervisado con siendo una función lineal a aprender:
dónde es un vector de entradas (puntos de datos) y es un vector de filtro lineal. El objetivo es calcular el vector de filtro. Con este fin, una función de pérdida cuadrada
se usa para calcular el vector que minimiza la pérdida empírica
dónde
- .
Dejar ser el matriz de datos y es el vector de columna de valores objetivo después de la llegada del primer puntos de datos. Suponiendo que la matriz de covarianza es invertible (de lo contrario, es preferible proceder de manera similar con la regularización de Tikhonov), la mejor solución al problema de mínimos cuadrados lineales está dado por
- .
Ahora, calculando la matriz de covarianza requiere tiempo , invirtiendo el la matriz lleva tiempo , mientras que el resto de la multiplicación lleva tiempo , dando un tiempo total de . Cuando hay puntos totales en el conjunto de datos, para volver a calcular la solución después de la llegada de cada punto de datos , el enfoque ingenuo tendrá una complejidad total . Tenga en cuenta que al almacenar la matriz, luego actualizarlo en cada paso solo necesita agregar , el cual toma tiempo, reduciendo el tiempo total para , pero con un espacio de almacenamiento adicional de para almacenar . [1]
Aprendizaje en línea: mínimos cuadrados recursivos
El algoritmo de mínimos cuadrados recursivos (RLS) considera un enfoque en línea para el problema de mínimos cuadrados. Se puede demostrar que al inicializar y , la solución del problema de mínimos cuadrados lineales dada en la sección anterior se puede calcular mediante la siguiente iteración:
El algoritmo de iteración anterior se puede probar usando inducción en . [2] La prueba también muestra que. También se puede observar el RLS en el contexto de los filtros adaptativos (ver RLS ).
La complejidad de Los pasos de este algoritmo son , que es un orden de magnitud más rápido que la correspondiente complejidad de aprendizaje por lotes. Los requisitos de almacenamiento en cada paso aquí están para almacenar la matriz , que es constante en . Para el caso cuando no es invertible, considere 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 a dar . [1]
Descenso de gradiente estocástico
Cuando esto
es reemplazado por
o por , esto se convierte en el algoritmo de descenso de gradiente estocástico. En este caso, la complejidad de pasos de este algoritmo se reduce a . Los requisitos de almacenamiento en cada paso son constantes en .
Sin embargo, el tamaño del paso debe elegirse cuidadosamente para resolver el problema de minimización de riesgos esperado, como se detalla anteriormente. Al elegir un tamaño de paso en descomposición se puede probar la convergencia de la iteración promedio . Esta configuración es un caso especial de optimización estocástica , un problema de optimización bien conocido. [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 de gradiente estocástico es que aquí una secuencia se elige para decidir qué punto de entrenamiento se visita en el -ésimo paso. Tal secuencia puede ser estocástica o determinista. El número de iteraciones se desacopla luego al número de puntos (cada punto puede considerarse más de una vez). Se puede demostrar que el método de gradiente incremental proporciona un minimizador del riesgo empírico. [3] Las técnicas incrementales pueden ser ventajosas cuando se consideran funciones objetivas 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 de kernel
Los núcleos se pueden utilizar para extender los algoritmos anteriores a modelos no paramétricos (o modelos donde los parámetros forman un espacio dimensional infinito). El procedimiento correspondiente ya no estará realmente en línea y, en cambio, implicará el almacenamiento de todos los puntos de datos, pero seguirá 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 inducción sencilla [1] que si es la matriz de datos y es la salida después de pasos del algoritmo SGD, entonces,
dónde y la secuencia satisface la recursividad:
- y
Fíjate que aquí es solo el Kernel estándar en , y el predictor tiene la forma
- .
Ahora, si un kernel general se introduce en su lugar y deja que el predictor sea
entonces la misma prueba también mostrará que el predictor que minimiza la pérdida por mínimos cuadrados se obtiene cambiando la recursividad anterior a
La expresión anterior requiere almacenar todos los datos para actualizar . La complejidad de tiempo total para la recursividad al evaluar la-th datapoint es , dónde es el costo de evaluar el kernel en un solo par de puntos. [1] Por lo tanto, el uso del kernel ha permitido el movimiento desde un espacio de parámetros de dimensión finita a una característica dimensional posiblemente infinita representada por un kernel en lugar de realizar la recursividad en el espacio de parámetros , cuya dimensión coincide con el tamaño del conjunto de datos de entrenamiento. En general, esto es una consecuencia del teorema del representador . [1]
Optimización convexa en línea
La optimización convexa en línea (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 del juego repetido de la siguiente manera:
Para
- El alumno recibe información
- Resultados del alumno de un conjunto convexo fijo
- La naturaleza devuelve una función de pérdida convexa .
- El alumno 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, considere el caso de la regresión lineal de mínimos cuadrados en línea. Aquí, los vectores de peso provienen del conjunto convexo, y la naturaleza devuelve la función de pérdida convexa . Tenga en cuenta aquí que se envía implícitamente con .
Sin embargo, algunos problemas de predicción en línea no pueden encajar en el marco de OCO. Por ejemplo, en la clasificación en línea, el dominio de predicción y las funciones de pérdida no son convexas. En tales escenarios, se utilizan dos técnicas simples para la convexificación: funciones de aleatorización y pérdida sustituta [ cita requerida ] .
Algunos algoritmos sencillos de optimización convexa en línea son:
Sigue al líder (FTL)
La regla de aprendizaje más simple para probar es seleccionar (en el paso actual) la hipótesis que tiene la menor pérdida en todas las rondas pasadas. Este algoritmo se llama Seguir al líder y simplemente se le da ronda por:
Por tanto, este método puede considerarse un algoritmo codicioso . Para el caso de optimización cuadrática en línea (donde la función de pérdida es), uno puede mostrar un límite de arrepentimiento que crece a medida que . Sin embargo, no se pueden obtener límites similares para el algoritmo FTL para otras familias importantes de modelos como la optimización lineal en línea. Para hacerlo, se modifica FTL agregando regularización.
Siga al líder regularizado (FTRL)
Esta es una modificación natural de FTL que se utiliza para estabilizar las soluciones de FTL y obtener mejores límites de arrepentimiento. Una función de regularizaciónse elige y el aprendizaje se realiza en la ronda t de la siguiente manera:
Como ejemplo especial, considere el caso de la optimización lineal en línea, es decir, donde la naturaleza devuelve funciones de pérdida de la forma . Además, deja. Supongamos que la función de regularización es elegido por algún número positivo . Entonces, uno puede demostrar que el arrepentimiento por minimizar la iteración se vuelve
Tenga en cuenta que esto se puede reescribir como , que se ve exactamente como el descenso de gradientes en línea.
Si S es en cambio un subespacio convexo de, S tendría que proyectarse sobre, lo que conduciría a la regla de actualización modificada
Este algoritmo se conoce como proyección diferida, como el vector acumula los gradientes. También se conoce como el algoritmo de promediado dual de Nesterov. En este escenario de funciones de pérdida lineal y regularización cuadrática, el arrepentimiento está limitado pory, por lo tanto, el arrepentimiento promedio llega a 0 según lo deseado.
Descenso de subgrado en línea (OSD)
Lo anterior demostró ser un lamentable límite para las funciones de pérdida lineal. . Para generalizar el algoritmo a cualquier función de pérdida convexa, el subgradiente de se utiliza como una aproximación lineal a cerca , lo que lleva al algoritmo de descenso de subgrados en línea:
Inicializar parámetro
Para
- Predecir el uso , recibir de la naturaleza.
- Escoger
- Si , actualizar como
- Si , proyectar gradientes acumulativos en es decir
Se puede utilizar el algoritmo OSD para derivar lamento límites para la versión en línea de SVM para la clasificación, que utilizan la pérdida de bisagra
Otros algoritmos
Los algoritmos FTRL cuadráticamente regularizados conducen a algoritmos de gradiente proyectados de manera perezosa como se describe anteriormente. Para usar lo anterior para regularizadores y funciones convexas arbitrarias, se usa el descenso de espejo en línea. La regularización óptima en retrospectiva se puede derivar para funciones de pérdida lineal, esto conduce al algoritmo AdaGrad . Para la regularización euclidiana, uno puede mostrar un límite de arrepentimiento de, que se puede mejorar aún más para funciones de pérdida fuertemente convexas y exp-cóncavas.
Interpretaciones del aprendizaje en línea
El paradigma del aprendizaje en línea tiene diferentes interpretaciones dependiendo de la elección del modelo de aprendizaje, cada una de las cuales tiene distintas implicaciones sobre la calidad predictiva de la secuencia de funciones. . El algoritmo de descenso de gradiente estocástico prototípico se utiliza para esta discusión. Como se señaló anteriormente, su recursividad viene dada por
La primera interpretación considera el método de descenso de gradiente estocástico aplicado al problema de minimizar el riesgo esperadodefinido anteriormente. [5] De hecho, en el caso de un flujo de datos infinito, dado que los ejemplos se supone que se extraen iid de la distribución , la secuencia de gradientes de en la iteración anterior hay una muestra iid de estimaciones estocásticas del gradiente del riesgo esperado y por lo tanto, se pueden aplicar resultados de complejidad para el método de descenso de gradiente estocástico para limitar la desviación , dónde es el minimizador de . [6] Esta interpretación también es válida en el caso de un conjunto de entrenamiento finito; aunque con múltiples pasadas a través de los datos los gradientes ya no son independientes, aún se pueden obtener 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, en cambio, uno mira el riesgo empírico:
Dado que los gradientes de en las iteraciones de descenso de gradiente incremental también son 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 contraposición al 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., dónde es el minimizador de .
Implementaciones
- Vowpal Wabbit : sistema de aprendizaje en línea rápido fuera de núcleo de código abierto que se destaca por admitir una serie de 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 truco de hash para delimitar 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: Perceptron , clasificador SGD , clasificador naive bayes .
- Regresión: Regresor SGD, Regresor pasivo agresivo.
- Agrupación: k-medias de mini lotes .
- Extracción de características: aprendizaje de diccionario por mini lotes , PCA incremental .
Ver también
Paradigmas de aprendizaje
- Aprendizaje incremental
- Aprendizaje perezoso
- Aprendizaje fuera de línea , el modelo opuesto
- Aprendizaje reforzado
- Aprendizaje supervisado
Algoritmos generales
- Algoritmo en línea
- Optimización online
- Algoritmo de transmisión
- Descenso de gradiente estocástico
Modelos de aprendizaje
- Teoría de la resonancia adaptativa
- Memoria temporal jerárquica
- algoritmo de vecino k-más cercano
- Aprendizaje de la cuantificación de vectores
- Perceptrón
Referencias
- ^ a b c d e f g L. Rosasco, T. Poggio, Machine Learning: a Regularization Approach, MIT-9.520 Lectures Notes, Manuscrito, diciembre de 2015. Capítulo 7 - Aprendizaje en línea
- ^ Yin, Harold J. Kushner, G. George (2003). Aproximación estocástica y algoritmos y aplicaciones recursivas (Segunda ed.). Nueva York: Springer. pp. 8 -12. ISBN 978-0-387-21769-7.
- ↑ a b Bertsekas, DP (2011). Métodos de gradiente incremental, subgrado y proximal para la optimización convexa: una encuesta. Optimización para aprendizaje automático, 85.
- ^ Hazan, Elad (2015). Introducción a la optimización convexa en línea (PDF) . Fundamentos y Tendencias en Optimización.
- ^ Bottou, Léon (1998). "Algoritmos online y aproximaciones estocásticas". Aprendizaje en línea y redes neuronales . Prensa de la Universidad de Cambridge. ISBN 978-0-521-65263-6.
- ^ Aplicaciones y algoritmos de aproximación estocástica , Harold J. Kushner y G. George Yin, Nueva York: Springer-Verlag, 1997. ISBN 0-387-94916-X ; 2a ed., Titulada Aproximación estocástica y algoritmos y aplicaciones recursivos , 2003, ISBN 0-387-00894-2 .
enlaces externos
- http://onlineprediction.net/ , Wiki para predicción en línea.
- 6.883: Métodos en línea en aprendizaje automático: teoría y aplicaciones. Alexander Rakhlin. MIT