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.

En el entorno del aprendizaje supervisado, una función de ${\displaystyle f:X\to Y}$ será aprendida, en el que ${\displaystyle X}$ es considerado como un espacio de entradas y ${\displaystyle Y}$ como un espacio de salidas que predice bien sobre instancias que se extraen de una distribución de probabilidad conjunta ${\displaystyle p(x,y)}$ en ${\displaystyle X\times Y}$. En realidad, el aprendiz nunca conoce la distribución verdadera ${\displaystyle p(x,y)}$, sobre instancias. En su lugar, el aprendiz suele tener acceso a un conjunto de ejemplos de entrenamiento ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$. En este caso, la función de pérdida es la siguiente ${\displaystyle V:Y\times Y\to \mathbb {R} }$, de modo que ${\displaystyle V(f(x),y)}$ mide la diferencia entre el valor predicho ${\displaystyle f(x)}$ y el valor real ${\displaystyle y}$. El objetivo ideal es seleccionar una función ${\displaystyle f\in {\mathcal {H}}}$, en elq ue ${\displaystyle {\mathcal {H}}}$ 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.

En los modelos de aprendizaje estadístico, las muestras de entrenamiento ${\displaystyle (x_{i},y_{i})}$ se asumen que han sido extraídas de la distribución verdadera ${\displaystyle p(x,y)}$ y el objetivo es minimizar el "riesgo" esperado${\displaystyle I[f]=\mathbb {E} [V(f(x),y)]=\int V(f(x),y)\,dp(x,y)\ .}$

Un paradigma común en esta situación es estimar una función ${\displaystyle {\hat {f}}}$ 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 ${\displaystyle (x_{t+1},y_{t+1})}$, el mejor predictor actual ${\displaystyle f_{t}}$ 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 ${\displaystyle f_{t+1}}$ puede depender de ${\displaystyle f_{t}}$ y todos los puntos de datos anteriores ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{t},y_{t})}$. 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 ${\displaystyle b\geq 1}$ puntos de datos a la vez, esto puede considerarse como pseudoaprendizaje online para ${\displaystyle b}$ 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.

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.

También llamado como "batch learning" (en inglés). Consideremos el aprendizaje supervisado con ${\displaystyle f}$ una función lineal que debe aprenderse:

${\displaystyle f(x_{j})=\langle w,x_{j}\rangle =w\cdot x_{j}}$

donde ${\displaystyle x_{j}\in \mathbb {R} ^{d}}$ es un vector de entradas (puntos de datos) y ${\displaystyle w\in \mathbb {R} ^{d}}$ es un vector de filtro lineal. El objetivo es calcular el vector de filtro ${\displaystyle w}$. Para ello, una función de pérdida cuadrada

${\displaystyle V(f(x_{j}),y_{j})=(f(x_{j})-y_{j})^{2}=(\langle w,x_{j}\rangle -y_{j})^{2}}$

se utiliza para calcular el vector ${\displaystyle w}$ que minimiza la pérdida empírica

${\displaystyle I_{n}[w]=\sum _{j=1}^{n}V(\langle w,x_{j}\rangle ,y_{j})=\sum _{j=1}^{n}(x_{j}^{T}w-y_{j})^{2}}$

donde

${\displaystyle y_{j}\in \mathbb {R} }$.

Sea ${\displaystyle X}$ la matriz de datos ${\displaystyle i\times d}$ y ${\displaystyle y\in \mathbb {R} ^{i}}$ es el vector columna de valores objetivo tras la llegada de los primeros puntos de datos ${\displaystyle i}$. Suponiendo que la matriz de covarianza ${\displaystyle \Sigma _{i}=X^{T}X}$ es invertible (en caso contrario es preferible proceder de forma similar con la regularización de Tikhonov), la mejor solución ${\displaystyle f^{*}(x)=\langle w^{*},x\rangle }$ al problema lineal de mínimos cuadrados viene dado por

${\displaystyle w^{*}=(X^{T}X)^{-1}X^{T}y=\Sigma _{i}^{-1}\sum _{j=1}^{i}x_{j}y_{j}}$

Ahora, calculando la matriz de covarianza ${\displaystyle \Sigma _{i}=\sum _{j=1}^{i}x_{j}x_{j}^{T}}$ requiere tiempo ${\displaystyle O(id^{2})}$, invirtiendo la matriz ${\displaystyle d\times d}$ requiere tiempo ${\displaystyle O(d^{3})}$, mientras que el resto de la multiplicación requiere el tiempo ${\displaystyle O(d^{2})}$, lo que da un tiempo total de ${\displaystyle O(id^{2}+d^{3})}$. Cuando hay ${\displaystyle n}$ puntos totales en el conjunto de datos, para volver a calcular la solución tras la llegada de cada punto de datos ${\displaystyle i=1,\ldots ,n}$, el enfoque ingenuo tendrá una complejidad total ${\displaystyle O(n^{2}d^{2}+nd^{3})}$. Obsérvese que al almacenar la matriz ${\displaystyle \Sigma _{i}}$, para actualizarla en cada paso sólo es necesario añadir ${\displaystyle x_{i+1}x_{i+1}^{T}}$, que requiere ${\displaystyle O(d^{2})}$ tiempo, reduciendo el tiempo total a ${\displaystyle O(nd^{2}+nd^{3})=O(nd^{3})}$, pero con un espacio de almacenamiento adicional de ${\displaystyle O(d^{2})}$ para almacenar ${\displaystyle \Sigma _{i}}$.^[1]​

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 ${\displaystyle \textstyle w_{0}=0\in \mathbb {R} ^{d}}$ y ${\displaystyle \textstyle \Gamma _{0}=I\in \mathbb {R} ^{d\times d}}$, la solución del problema lineal de mínimos cuadrados dado en la sección anterior puede calcularse mediante la siguiente iteración:

${\displaystyle \Gamma _{i}=\Gamma _{i-1}-{\frac {\Gamma _{i-1}x_{i}x_{i}^{T}\Gamma _{i-1}}{1+x_{i}^{T}\Gamma _{i-1}x_{i}}}}$

${\displaystyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})}$

El algoritmo de iteración anterior puede demostrarse mediante inducción sobre ${\displaystyle i}$.^[2]​ La prueba también muestra que ${\displaystyle \Gamma _{i}=\Sigma _{i}^{-1}}$. También se puede considerar el RLS en el contexto de los filtros adaptativos (véase RLS).

La complejidad para ${\displaystyle n}$ pasos de este algoritmo es ${\displaystyle O(nd^{2})}$, 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 ${\displaystyle \Gamma _{i}}$, que es constante en ${\displaystyle O(d^{2})}$. Para el caso en que ${\displaystyle \Sigma _{i}}$ no es invertible, consideremos la versión regularizada de la función de pérdida del problema ${\displaystyle \sum _{j=1}^{n}(x_{j}^{T}w-y_{j})^{2}+\lambda ||w||_{2}^{2}}$. Entonces, es fácil demostrar que el mismo algoritmo funciona con ${\displaystyle \Gamma _{0}=(I+\lambda I)^{-1}}$, y las iteraciones proceden para dar ${\displaystyle \Gamma _{i}=(\Sigma _{i}+\lambda I)^{-1}}$.^[1]​

Cuando

${\displaystyle \textstyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})}$

es reemplazado por

${\displaystyle \textstyle w_{i}=w_{i-1}-\gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{i}\rangle ,y_{i})}$

o ${\displaystyle \Gamma _{i}\in \mathbb {R} ^{d\times d}}$ por ${\displaystyle \gamma _{i}\in \mathbb {R} }$, se convierte en el algoritmo de descenso de gradiente estocástico. En este caso, la complejidad para ${\displaystyle n}$ pasos de este algoritmo se reduce a ${\displaystyle O(nd)}$. Las necesidades de almacenamiento en cada paso ${\displaystyle i}$ son constantes en ${\displaystyle O(d)}$.

Sin embargo, el step size ${\displaystyle \gamma _{i}}$ debe elegirse cuidadosamente para resolver el problema de minimización del riesgo esperado, como se ha detallado anteriormente. Al elegir un step size decreciente ${\displaystyle \gamma _{i}\approx {\frac {1}{\sqrt {i}}},}$ se puede demostrar la convergencia de la iterada media ${\displaystyle {\overline {w}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}w_{i}}$. Este escenario es un caso especial de optimización estocástica, un problema bien conocido en optimización.^[1]​

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

${\displaystyle \textstyle w_{i}=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{t_{i}}\rangle ,y_{t_{i}})}$

La principal diferencia con el método del gradiente estocástico es que aquí una secuencia ${\displaystyle t_{i}}$ se elige para decidir qué punto de entrenamiento se visita en la secuencia ${\displaystyle i}$-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]​

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 ${\displaystyle X_{i}}$ es la matriz de datos y ${\displaystyle w_{i}}$ es la salida después de ${\displaystyle i}$ pasos del algoritmo SGD, entonces,

${\displaystyle w_{i}=X_{i}^{T}c_{i}}$

donde ${\displaystyle \textstyle c_{i}=((c_{i})_{1},(c_{i})_{2},...,(c_{i})_{i})\in \mathbb {R} ^{i}}$ y la secuencia ${\displaystyle c_{i}}$ satisface la recursión

${\displaystyle c_{0}=0}$

${\displaystyle (c_{i})_{j}=(c_{i-1})_{j},j=1,2,...,i-1}$ y

${\displaystyle (c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x_{i}\rangle {\Big )}}$.

Observe que aquí ${\displaystyle \langle x_{j},x_{i}\rangle }$ es simplemente el Kernel estándar en ${\displaystyle \mathbb {R} ^{d}}$ y el predictor es de la forma

${\displaystyle f_{i}(x)=\langle w_{i-1},x\rangle =\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x\rangle }$.

Ahora bien, si en su lugar se introduce un kernel general ${\displaystyle K}$ y dejamos que el predictor sea

${\displaystyle f_{i}(x)=\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x)}$

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

${\displaystyle (c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x_{i}){\Big )}}$

La expresión anterior requiere almacenar todos los datos para actualizar ${\displaystyle c_{i}}$. La complejidad de tiempo total para la recursión cuando se evalúa para el ${\displaystyle n}$-n punto de datos es ${\displaystyle O(n^{2}dk)}$, donde ${\displaystyle k}$ 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 ${\displaystyle \textstyle w_{i}\in \mathbb {R} ^{d}}$ a una característica de dimensión posiblemente infinita representada por el kernel ${\displaystyle K}$, realizando en su lugar la recursión en el espacio de parámetros ${\displaystyle \textstyle c_{i}\in \mathbb {R} ^{i}}$, 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]​

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 ${\displaystyle t=1,2,...,T}$

• El aprendiz recibe la entrada ${\displaystyle x_{t}}$
• El aprendiz emite ${\displaystyle w_{t}}$ a partir de un conjunto convexo fijo ${\displaystyle S}$
• La naturaleza devuelve una función de pérdida convexa ${\displaystyle v_{t}:S\rightarrow \mathbb {R} }$.
• El aprendiz sufre una pérdida ${\displaystyle v_{t}(w_{t})}$ 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 ${\displaystyle u\in S}$ 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 ${\displaystyle S=\mathbb {R} ^{d}}$ y la naturaleza devuelve la función de pérdida convexa ${\displaystyle v_{t}(w)=(\langle w,x_{t}\rangle -y_{t})^{2}}$. Nótese aquí que ${\displaystyle y_{t}}$ se envía implícitamente con ${\displaystyle v_{t}}$.

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:

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 ${\displaystyle t}$ por:

${\displaystyle w_{t}=\operatorname {arg\,min} _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)}$

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 ${\displaystyle v_{t}(w)=||w-x_{t}||_{2}^{2}}$), se puede mostrar un límite de arrepentimiento que crece como ${\displaystyle \log(T)}$. 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 (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 ${\displaystyle R:S\rightarrow \mathbb {R} }$, y el aprendizaje se realiza en la ronda ${\displaystyle t}$ de la siguiente manera:

${\displaystyle w_{t}=\operatorname {arg\,min} _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)+R(w)}$

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 ${\displaystyle v_{t}(w)=\langle w,z_{t}\rangle }$. Además, déjese ${\displaystyle S=\mathbb {R} ^{d}}$. Supongamos que la función de regularización ${\displaystyle R(w)={\frac {1}{2\eta }}||w||_{2}^{2}}$ se elige para algún número positivo ${\displaystyle n}$. Entonces, se puede demostrar que la iteración que minimiza el arrepentimiento se convierte en

${\displaystyle w_{t+1}=-\eta \sum _{i=1}^{t}z_{i}=w_{t}-\eta z_{t}}$

Nótese que esto puede ser reescrito como ${\displaystyle w_{t+1}=w_{t}-\eta \nabla v_{t}(w_{t})}$, que se parece exactamente a un descenso de gradiente online.

Si en cambio ${\displaystyle S}$ es algún subespacio convexo de ${\displaystyle \mathbb {R} ^{d}}$, ${\displaystyle S}$ tendría que ser proyectado, lo que lleva a la regla de actualización modificada

${\displaystyle w_{t+1}=\Pi _{S}(-\eta \sum _{i=1}^{t}z_{i})=\Pi _{S}(\eta \theta _{t+1})}$

Este algoritmo se conoce como proyección perezosa, ya que el vector ${\displaystyle \theta _{t+1}}$ 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 ${\displaystyle O({\sqrt {T}})}$ y, por tanto, el arrepentimiento medio se reduce a ${\displaystyle 0}$, tal y como se desea.

Lo anterior demostró un límite de arrepentimiento para funciones de pérdida lineales ${\displaystyle v_{t}(w)=\langle w,z_{t}\rangle }$. Para generalizar el algoritmo a cualquier función de pérdida convexa, el subgradiente ${\displaystyle \partial v_{t}(w_{t})}$ de ${\displaystyle v_{t}}$ se utiliza como aproximación lineal a ${\displaystyle v_{t}}$ cerca de ${\displaystyle w_{t}}$, dando lugar al algoritmo de descenso subgradiente online:

Inicializar el parámetro ${\displaystyle \eta ,w_{1}=0}$

Para ${\displaystyle t=1,2,...,T}$

• Predecir utilizando ${\displaystyle w_{t}}$, recibir ${\displaystyle f_{t}}$ de la naturaleza.
• Elija ${\displaystyle z_{t}\in \partial v_{t}(w_{t})}$
• Si ${\displaystyle S=\mathbb {R} ^{d}}$, actualizar como ${\displaystyle w_{t+1}=w_{t}-\eta z_{t}}$
• Si ${\displaystyle S\subset \mathbb {R} ^{d}}$, proyectar los gradientes acumulativos sobre ${\displaystyle S}$, es decir, ${\displaystyle w_{t+1}=\Pi _{S}(\eta \theta _{t+1}),\theta _{t+1}=\theta _{t}+z_{t}}$

Se puede utilizar el algoritmo OSD para obtener ${\displaystyle O({\sqrt {T}})}$ límites de arrepentimiento para la versión online de las SVM de clasificación, que utilizan la pérdida de bisagra ${\displaystyle v_{t}(w)=\max\{0,1-y_{t}(w\cdot x_{t})\}}$

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 ${\displaystyle O({\sqrt {T}})}$ que puede mejorarse hasta un valor de ${\displaystyle O(\log T)}$ para funciones de pérdida fuertemente convexas y expocóncavas.

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.

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 ${\displaystyle f_{1},f_{2},\ldots ,f_{n}}$. 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

${\displaystyle \textstyle w_{t}=w_{t-1}-\gamma _{t}\nabla V(\langle w_{t-1},x_{t}\rangle ,y_{t})}$

La primera interpretación considera el método de descenso de gradiente estocástico aplicado al problema de minimización del riesgo esperado ${\displaystyle I[w]}$ definido anteriormente.^[6]​ En efecto, en el caso de un flujo infinito de datos, puesto que los ejemplos ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),\ldots }$ se suponen extraídos i.i.d. de la distribución ${\displaystyle p(x,y)}$, la secuencia de gradientes de ${\displaystyle V(\cdot ,\cdot )}$ en la iteración anterior son una muestra i.i.d. de estimaciones estocásticas del gradiente del riesgo esperado ${\displaystyle I[w]}$ 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 ${\displaystyle I[w_{t}]-I[w^{\ast }]}$, donde ${\displaystyle w^{\ast }}$ es el minimizador de ${\displaystyle I[w]}$.^[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:

${\displaystyle I_{n}[w]={\frac {1}{n}}\sum _{i=1}^{n}V(\langle w,x_{i}\rangle ,y_{i})\ .}$

Dado que los gradientes de ${\displaystyle V(\cdot ,\cdot )}$ en las iteraciones de descenso de gradiente incremental son también estimaciones estocásticas del gradiente de ${\displaystyle I_{n}[w]}$. 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 ${\displaystyle I_{n}[w_{t}]-I_{n}[w_{n}^{\ast }]}$, donde ${\displaystyle w_{n}^{\ast }}$ es el minimizador de ${\displaystyle I_{n}[w]}$.

• 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.

Paradigmas del aprendizaje automático

• Aprendizaje activo
• Aprendizaje por imitación
• Aprendizaje por refuerzo
• Aprendizaje supervisado
• Aprendizaje vago
• Bandido multibrazo

Algoritmos generales

• Descenso de gradiente estocástico

Modelos de aprendizaje

• k vecinos más próximos
• Perceptrón
• Teoría de la resonancia adaptativa

1. ↑ ^{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. 
2. ↑ 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. 
3. ↑ ^{a b} Bertsekas, D. P. (2011). «Incremental gradient, subgradient, and proximal methods for convex optimization: a survey.». Optimization for Machine Learning: 85. 
4. ↑ Hazan, Elad (2015). Introduction to Online Convex Optimization. Foundations and Trends in Optimization. 
5. ↑ 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. 
6. ↑ Bottou, Léon (1998). «Online Algorithms and Stochastic Approximations». Online Learning and Neural Networks. Cambridge University Press. ISBN 978-0-521-65263-6. 
7. ↑ 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. 

• Alexander Rakhlin. 6.883: Online Methods in Machine Learning: Theory and Applications. MIT (en inglés)