Aprendizaje automático en línea

Método de aprendizaje automático

En informática , el aprendizaje automático en línea es un método de aprendizaje automático en el que los datos se vuelven 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 en línea es una técnica común utilizada en áreas de aprendizaje automático donde es computacionalmente inviable 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 como una función del tiempo, por ejemplo, la predicción del precio de las acciones . Los algoritmos de aprendizaje en línea pueden ser propensos a interferencias catastróficas , un problema que se puede abordar con enfoques de aprendizaje incremental .

Introducción

En el contexto del aprendizaje supervisado , se debe aprender una función de , donde se considera 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 distribución verdadera sobre instancias. En cambio, el alumno generalmente tiene acceso a un conjunto de entrenamiento de ejemplos . En este contexto, la función de pérdida se proporciona como , de modo que mide la diferencia entre el valor predicho y el valor verdadero . El objetivo ideal es seleccionar una función , donde es un espacio de funciones llamado espacio de hipótesis, de modo que se minimice alguna noción de pérdida total. Dependiendo del tipo de modelo (estadístico o adversarial), se pueden idear diferentes nociones de pérdida, que conducen a diferentes algoritmos de aprendizaje. ${\displaystyle f:X\to Y}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle p(x,y)}$ ${\displaystyle X\times Y}$ ${\displaystyle p(x,y)}$ ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{n},y_{n})}$ ${\displaystyle V:Y\times Y\to \mathbb {R} }$ ${\displaystyle V(f(x),y)}$ ${\displaystyle f(x)}$ ${\displaystyle y}$ ${\displaystyle f\in {\mathcal {H}}}$ ${\displaystyle {\mathcal {H}}}$

Visión estadística del aprendizaje en línea

En los modelos de aprendizaje estadístico, se supone que la muestra de entrenamiento se ha extraído 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 a través de la minimización del riesgo empírico o la minimización del riesgo empírico regularizado (generalmente 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 en línea en esta categoría aprendería basándose solo en la nueva entrada , el mejor predictor actual y alguna información almacenada adicional (que generalmente 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 en línea no es posible, aunque se puede usar una forma de aprendizaje en línea híbrido 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 tiempo en calcularse con la adición de un nuevo punto de datos, en comparación con las técnicas de aprendizaje por lotes. ${\displaystyle (x_{i},y_{i})}$ ${\displaystyle p(x,y)}$ $${\displaystyle I[f]=\mathbb {E} [V(f(x),y)]=\int V(f(x),y)\,dp(x,y)\ .}$$ ${\displaystyle {\hat {f}}}$ ${\displaystyle (x_{t+1},y_{t+1})}$ ${\displaystyle f_{t}}$ ${\displaystyle f_{t+1}}$ ${\displaystyle f_{t}}$ ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{t},y_{t})}$

Una estrategia común para superar los problemas anteriores es aprender usando minilotes, que procesan un pequeño lote de puntos de datos a la vez, esto puede considerarse como un aprendizaje pseudo-en línea para un número mucho menor que el total de puntos de entrenamiento. Las técnicas de minilotes se utilizan con el paso repetido sobre los datos de entrenamiento para obtener versiones optimizadas fuera del núcleo de algoritmos de aprendizaje automático, por ejemplo, descenso de gradiente estocástico . Cuando se combina con retropropagación , este es actualmente el método de entrenamiento de facto para entrenar redes neuronales artificiales . ${\displaystyle b\geq 1}$ ${\displaystyle b}$

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

Aprendizaje por lotes

Consideremos el contexto del aprendizaje supervisado con una función lineal que se debe aprender: 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, se utiliza una función de pérdida cuadrada para calcular el vector que minimiza la pérdida empírica donde ${\displaystyle f}$ $${\displaystyle f(x_{j})=\langle w,x_{j}\rangle =w\cdot x_{j}}$$ ${\displaystyle x_{j}\in \mathbb {R} ^{d}}$ ${\displaystyle w\in \mathbb {R} ^{d}}$ ${\displaystyle w}$ $${\displaystyle V(f(x_{j}),y_{j})=(f(x_{j})-y_{j})^{2}=(\langle w,x_{j}\rangle -y_{j})^{2}}$$ ${\displaystyle w}$ $${\displaystyle I_{n}[w]=\sum _{j=1}^{n}V(\langle w,x_{j}\rangle ,y_{j})=\sum _{j=1}^{n}(x_{j}^{\mathsf {T}}w-y_{j})^{2}}$$ $${\displaystyle y_{j}\in \mathbb {R} .}$$

Sea la matriz de datos y el vector columna de los valores objetivo después de la llegada de los primeros 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 viene dada por ${\displaystyle X}$ ${\displaystyle i\times d}$ ${\displaystyle y\in \mathbb {R} ^{i}}$ ${\displaystyle i}$ ${\displaystyle \Sigma _{i}=X^{\mathsf {T}}X}$ ${\displaystyle f^{*}(x)=\langle w^{*},x\rangle }$ $${\displaystyle w^{*}=(X^{\mathsf {T}}X)^{-1}X^{\mathsf {T}}y=\Sigma _{i}^{-1}\sum _{j=1}^{i}x_{j}y_{j}.}$$

Ahora bien, calcular la matriz de covarianza lleva tiempo , invertir la matriz lleva tiempo , mientras que el resto de la multiplicación lleva tiempo , lo que da 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 actualizarla en cada paso solo necesita agregar , lo que lleva tiempo, reduciendo el tiempo total a , pero con un espacio de almacenamiento adicional de para almacenar . ^[1] ${\displaystyle \Sigma _{i}=\sum _{j=1}^{i}x_{j}x_{j}^{\mathsf {T}}}$ ${\displaystyle O(id^{2})}$ ${\displaystyle d\times d}$ ${\displaystyle O(d^{3})}$ ${\displaystyle O(d^{2})}$ ${\displaystyle O(id^{2}+d^{3})}$ ${\displaystyle n}$ ${\displaystyle i=1,\ldots ,n}$ ${\displaystyle O(n^{2}d^{2}+nd^{3})}$ ${\displaystyle \Sigma _{i}}$ ${\displaystyle x_{i+1}x_{i+1}^{\mathsf {T}}}$ ${\displaystyle O(d^{2})}$ ${\displaystyle O(nd^{2}+nd^{3})=O(nd^{3})}$ ${\displaystyle O(d^{2})}$ ${\displaystyle \Sigma _{i}}$

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 lineal dado en la sección anterior se puede calcular mediante la siguiente iteración: El algoritmo de iteración anterior se puede demostrar utilizando inducción en . ^[2] La prueba también muestra que . Se puede considerar a RLS también en el contexto de filtros adaptativos (ver RLS ). ${\displaystyle \textstyle w_{0}=0\in \mathbb {R} ^{d}}$ ${\displaystyle \textstyle \Gamma _{0}=I\in \mathbb {R} ^{d\times d}}$ $${\displaystyle \Gamma _{i}=\Gamma _{i-1}-{\frac {\Gamma _{i-1}x_{i}x_{i}^{\mathsf {T}}\Gamma _{i-1}}{1+x_{i}^{\mathsf {T}}\Gamma _{i-1}x_{i}}}}$$ $${\displaystyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)}$$ ${\displaystyle i}$ ${\displaystyle \Gamma _{i}=\Sigma _{i}^{-1}}$

La complejidad de los pasos de este algoritmo es , que es un orden de magnitud más rápido que la complejidad de aprendizaje por lotes correspondiente. Los requisitos de almacenamiento en cada paso aquí son almacenar la matriz , que es constante en . Para el caso en el que no es invertible, considere la versión regularizada de la función de pérdida del problema . Luego, es fácil demostrar que el mismo algoritmo funciona con , y las iteraciones proceden a dar . ^[1] ${\displaystyle n}$ ${\displaystyle O(nd^{2})}$ ${\displaystyle i}$ ${\displaystyle \Gamma _{i}}$ ${\displaystyle O(d^{2})}$ ${\displaystyle \Sigma _{i}}$ ${\displaystyle \sum _{j=1}^{n}\left(x_{j}^{\mathsf {T}}w-y_{j}\right)^{2}+\lambda \left\|w\right\|_{2}^{2}}$ ${\displaystyle \Gamma _{0}=(I+\lambda I)^{-1}}$ ${\displaystyle \Gamma _{i}=(\Sigma _{i}+\lambda I)^{-1}}$

Descenso de gradiente estocástico

Cuando se reemplaza por o por , se convierte en el algoritmo de descenso de gradiente estocástico. En este caso, la complejidad de los pasos de este algoritmo se reduce a . Los requisitos de almacenamiento en cada paso son constantes en . $${\displaystyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)}$$ $${\displaystyle w_{i}=w_{i-1}-\gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{i}\rangle ,y_{i})}$$ ${\displaystyle \Gamma _{i}\in \mathbb {R} ^{d\times d}}$ ${\displaystyle \gamma _{i}\in \mathbb {R} }$ ${\displaystyle n}$ ${\displaystyle O(nd)}$ ${\displaystyle i}$ ${\displaystyle O(d)}$

Sin embargo, el tamaño del paso debe elegirse con cuidado para resolver el problema de minimización del riesgo esperado, como se detalla anteriormente. Al elegir un tamaño de paso decreciente, se puede demostrar la convergencia de la iteración promedio . Esta configuración es un caso especial de optimización estocástica , un problema bien conocido en optimización. ^[1] ${\displaystyle \gamma _{i}}$ ${\displaystyle \gamma _{i}\approx {\frac {1}{\sqrt {i}}},}$ ${\textstyle {\overline {w}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}w_{i}}$

Descenso de gradiente estocástico incremental

En la práctica, se pueden realizar múltiples pasadas de gradiente estocástico (también llamados ciclos o épocas) sobre los datos. El algoritmo así obtenido se llama 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í se elige una secuencia para decidir qué punto de entrenamiento se visita en el paso -ésimo. Tal secuencia puede ser estocástica o determinista. El número de iteraciones se desacopla entonces del número de puntos (cada punto se puede considerar 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 objetivo formadas por una suma de muchos términos, por ejemplo, un error empírico correspondiente a un conjunto de datos muy grande. ^[1] $${\displaystyle w_{i}=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{t_{i}}\rangle ,y_{t_{i}})}$$ ${\displaystyle t_{i}}$ ${\displaystyle i}$

Métodos del núcleo

Los kernels 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 será verdaderamente en línea y, en cambio, implicará almacenar 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 se puede extender a cualquier pérdida convexa. Se puede demostrar mediante una inducción fácil ^[1] que si es la matriz de datos y es la salida después de los pasos del algoritmo SGD , entonces, donde y la secuencia satisface la recursión: y Observe que aquí solo se trata del Kernel estándar en , y el predictor tiene la forma ${\displaystyle X_{i}}$ ${\displaystyle w_{i}}$ ${\displaystyle i}$ $${\displaystyle w_{i}=X_{i}^{\mathsf {T}}c_{i}}$$ ${\displaystyle c_{i}=((c_{i})_{1},(c_{i})_{2},...,(c_{i})_{i})\in \mathbb {R} ^{i}}$ ${\displaystyle c_{i}}$ $${\displaystyle c_{0}=0}$$ $${\displaystyle (c_{i})_{j}=(c_{i-1})_{j},j=1,2,...,i-1}$$ $${\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 )}}$$ ${\displaystyle \langle x_{j},x_{i}\rangle }$ ${\displaystyle \mathbb {R} ^{d}}$ $${\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 se introduce un kernel general en su lugar y se deja que el predictor sea entonces la misma prueba también mostrará que el predictor que minimiza la pérdida de mínimos cuadrados se obtiene cambiando la recursión anterior a La expresión anterior requiere almacenar todos los datos para actualizar . La complejidad temporal total para la recursión al evaluar el -ésimo punto de datos es , donde 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 de un espacio de parámetros de dimensión finita a una característica de dimensión posiblemente infinita representada por un kernel al realizar en cambio la recursión en el espacio de parámetros , cuya dimensión es la misma que el tamaño del conjunto de datos de entrenamiento. En general, esto es una consecuencia del teorema del representador . ^[1] ${\displaystyle K}$ $${\displaystyle f_{i}(x)=\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x)}$$ $${\displaystyle (c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x_{i}){\Big )}}$$ ${\displaystyle c_{i}}$ ${\displaystyle n}$ ${\displaystyle O(n^{2}dk)}$ ${\displaystyle k}$ ${\displaystyle \textstyle w_{i}\in \mathbb {R} ^{d}}$ ${\displaystyle K}$ ${\displaystyle \textstyle c_{i}\in \mathbb {R} ^{i}}$

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 de una repetición del juego, como se muestra a continuación:

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

• El alumno recibe información ${\displaystyle x_{t}}$
• Salidas del alumno de un conjunto convexo fijo ${\displaystyle w_{t}}$ ${\displaystyle S}$
• La naturaleza envía una función de pérdida convexa . ${\displaystyle v_{t}:S\rightarrow \mathbb {R} }$
• El alumno sufre una pérdida y actualiza su modelo ${\displaystyle v_{t}(w_{t})}$

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 envía de vuelta la función de pérdida convexa . Observe aquí que se envía implícitamente con . ${\displaystyle u\in S}$ ${\displaystyle S=\mathbb {R} ^{d}}$ ${\displaystyle v_{t}(w)=(\langle w,x_{t}\rangle -y_{t})^{2}}$ ${\displaystyle y_{t}}$ ${\displaystyle v_{t}}$

Sin embargo, algunos problemas de predicción en línea no encajan 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 convexos. En tales escenarios, se utilizan dos técnicas simples para la convexificación : la aleatorización y las funciones de pérdida sustitutivas. ^{[ cita requerida ]}

Algunos algoritmos simples de optimización convexa en línea son:

Sigue al líder (FTL)

La regla de aprendizaje más simple que se puede probar es seleccionar (en el paso actual) la hipótesis que tenga la menor pérdida en todas las rondas anteriores. Este algoritmo se llama Follow the leader (Seguir al líder) y la ronda se da simplemente por: Este método puede verse como un algoritmo voraz . Para el caso de la optimización cuadrática en línea (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 en línea. Para ello, se modifica FTL agregando regularización. ${\displaystyle t}$ $${\displaystyle w_{t}=\mathop {\operatorname {arg\,min} } _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)}$$ ${\displaystyle v_{t}(w)=\left\|w-x_{t}\right\|_{2}^{2}}$ ${\displaystyle \log(T)}$

Seguir al líder regularizado (FTRL)

Esta es una modificación natural de FTL que se utiliza para estabilizar las soluciones FTL y obtener mejores límites de arrepentimiento. Se elige una función de regularización y se realiza el aprendizaje 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 envía funciones de pérdida de la forma . Además, sea . Suponga que la función de regularización se elige para algún número positivo . Entonces, se puede demostrar que la iteración de minimización del arrepentimiento se convierte en Nótese que esto se puede reescribir como , que se ve exactamente como el descenso de gradiente en línea. ${\displaystyle R:S\to \mathbb {R} }$ $${\displaystyle w_{t}=\mathop {\operatorname {arg\,min} } _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)+R(w)}$$ ${\displaystyle v_{t}(w)=\langle w,z_{t}\rangle }$ ${\displaystyle S=\mathbb {R} ^{d}}$ ${\textstyle R(w)={\frac {1}{2\eta }}\left\|w\right\|_{2}^{2}}$ ${\displaystyle \eta }$ $${\displaystyle w_{t+1}=-\eta \sum _{i=1}^{t}z_{i}=w_{t}-\eta z_{t}}$$ ${\displaystyle w_{t+1}=w_{t}-\eta \nabla v_{t}(w_{t})}$

Si S es en cambio un subespacio convexo de , sería necesario proyectar S sobre , 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 lo tanto el arrepentimiento promedio tiende a 0 como se desea. ${\displaystyle \mathbb {R} ^{d}}$ $${\displaystyle w_{t+1}=\Pi _{S}(-\eta \sum _{i=1}^{t}z_{i})=\Pi _{S}(\eta \theta _{t+1})}$$ ${\displaystyle \theta _{t+1}}$ ${\displaystyle O({\sqrt {T}})}$

Descenso de subgradiente en línea (OSD)

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

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

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

• Predecir usando , recibir de la naturaleza. ${\displaystyle w_{t}}$ ${\displaystyle f_{t}}$
• Elegir ${\displaystyle z_{t}\in \partial v_{t}(w_{t})}$
• Si , actualice como ${\displaystyle S=\mathbb {R} ^{d}}$ ${\displaystyle w_{t+1}=w_{t}-\eta z_{t}}$
• Si , proyecta gradientes acumulativos sobre ie ${\displaystyle S\subset \mathbb {R} ^{d}}$ ${\displaystyle S}$ ${\displaystyle w_{t+1}=\Pi _{S}(\eta \theta _{t+1}),\theta _{t+1}=\theta _{t}+z_{t}}$

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

Otros algoritmos

Los algoritmos FTRL regularizados cuadráticamente conducen a algoritmos de gradiente proyectados de forma perezosa como se describió anteriormente. Para utilizar lo anterior para funciones convexas y regularizadores arbitrarios, se utiliza el descenso de espejo en línea . La regularización óptima en retrospectiva se puede derivar para funciones de pérdida lineales, esto conduce al algoritmo AdaGrad . Para la regularización euclidiana, se puede mostrar un límite de arrepentimiento de , que se puede mejorar aún más a para funciones de pérdida fuertemente convexas y cóncavas exponenciales. ${\displaystyle O({\sqrt {T}})}$ ${\displaystyle O(\log T)}$

Aprendizaje continuo

El aprendizaje continuo implica mejorar constantemente el modelo aprendido mediante el procesamiento de 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 desafío 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 generalmente conduce a un olvido catastrófico .

Interpretaciones del aprendizaje en línea

El paradigma del aprendizaje en línea tiene diferentes interpretaciones según la elección del modelo de aprendizaje, cada una de las cuales tiene distintas implicaciones sobre la calidad predictiva de la secuencia de funciones . Para esta discusión se utiliza el algoritmo prototípico de descenso de gradiente estocástico. Como se señaló anteriormente, su recursión está dada por ${\displaystyle f_{1},f_{2},\ldots ,f_{n}}$ $${\displaystyle 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 minimizar el riesgo esperado definido anteriormente. ^[6] De hecho, en el caso de un flujo infinito de datos, dado que se supone que los ejemplos se extraen iid de la distribución , la secuencia de gradientes de en la iteración anterior son 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 , 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 a través de los datos los gradientes ya no son independientes, aún se pueden obtener resultados de complejidad en casos especiales. ${\displaystyle I[w]}$ ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2}),\ldots }$ ${\displaystyle p(x,y)}$ ${\displaystyle V(\cdot ,\cdot )}$ ${\displaystyle I[w]}$ ${\displaystyle I[w_{t}]-I[w^{\ast }]}$ ${\displaystyle w^{\ast }}$ ${\displaystyle I[w]}$

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, uno mira en cambio 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 se aplica para minimizar el riesgo empírico en oposició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 en realidad conducen a límites más estrictos en las desviaciones , donde es el minimizador de . $${\displaystyle I_{n}[w]={\frac {1}{n}}\sum _{i=1}^{n}V(\langle w,x_{i}\rangle ,y_{i})\ .}$$ ${\displaystyle V(\cdot ,\cdot )}$ ${\displaystyle I_{n}[w]}$ ${\displaystyle I_{n}[w_{t}]-I_{n}[w_{n}^{\ast }]}$ ${\displaystyle w_{n}^{\ast }}$ ${\displaystyle I_{n}[w]}$

Implementaciones

• Vowpal Wabbit : sistema de aprendizaje en línea rápido y 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 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 Naive Bayes .
  • Regresión: Regresor SGD, Regresor pasivo-agresivo.
  • Agrupamiento: minilotes k-medias .
  • Extracción de características: aprendizaje de diccionario en minilotes , PCA incremental .

Véase también

Paradigmas de aprendizaje

• Aprendizaje incremental
• Aprendizaje perezoso
• Aprendizaje offline , el modelo opuesto
• Aprendizaje por refuerzo
• Bandido de múltiples brazos
• Aprendizaje supervisado

Algoritmos generales

• Algoritmo en línea
• Optimización en línea
• Algoritmo de transmisión
• Descenso de gradiente estocástico

Modelos de aprendizaje

• Teoría de la resonancia adaptativa
• Memoria temporal jerárquica
• algoritmo de k vecinos más cercanos
• Aprendiendo cuantificación vectorial
• Perceptrón

Referencias

1. 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
2. Kushner, Harold J.; Yin, G. George (2003). Aproximación estocástica y algoritmos recursivos con aplicaciones (segunda edición). Nueva York: Springer. pp. 8-12. ISBN 978-0-387-21769-7.
3. Bertsekas, DP (2011). Métodos de gradiente incremental, subgradiente y proximal para optimización convexa: un estudio. Optimización para aprendizaje automático, 85.
4. Hazan, Elad (2015). Introducción a la optimización convexa en línea (PDF) . Fundamentos y tendencias en optimización.
5. Parisi, German I.; Kemker, Ronald; Part, Jose L.; Kanan, Christopher; Wermter, Stefan (2019). "Aprendizaje continuo a lo largo de la vida con redes neuronales: una revisión". Redes neuronales . 113 : 54–71. arXiv : 1802.07569 . doi :10.1016/j.neunet.2019.01.012. ISSN  0893-6080.
6. Bottou, Léon (1998). "Algoritmos en línea y aproximaciones estocásticas". Aprendizaje en línea y redes neuronales . Cambridge University Press. ISBN 978-0-521-65263-6.
7. Algoritmos y aplicaciones de aproximación estocástica , Harold J. Kushner y G. George Yin, Nueva York: Springer-Verlag, 1997. ISBN 0-387-94916-X ; 2.ª ed., titulada Aproximación estocástica y algoritmos recursivos y aplicaciones , 2003, ISBN 0-387-00894-2 .  

Enlaces externos

• 6.883: Métodos en línea en aprendizaje automático: teoría y aplicaciones. Alexander Rakhlin. MIT