Aprendizaje automático en línea

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de noviembre de 2021; las comprobaciones requieren 2 ediciones .

El aprendizaje automático en línea es una técnica de aprendizaje automático en la que los datos están disponibles en orden secuencial y se utilizan para actualizar la mejor predicción para los datos posteriores, realizados en cada paso de entrenamiento. El método es opuesto a la técnica de entrenamiento por lotes, en la que la mejor predicción se genera de una sola vez a partir del conjunto de datos de entrenamiento completo. El aprendizaje en línea es una técnica común utilizada en áreas de aprendizaje automático cuando no es posible entrenar en todo el conjunto de datos, como cuando se necesitan algoritmos que funcionen con memoria externa. El método también se usa en situaciones en las que el algoritmo tiene que adaptar dinámicamente nuevos patrones en los datos o cuando los datos mismos se forman en función del tiempo, por ejemplo, cuandopredicción del precio del mercado de valores . Los algoritmos de aprendizaje en línea pueden ser propensos a interferencias catastróficas , un problema que puede resolverse con un enfoque de aprendizaje paso a paso [1] .

Introducción

En condiciones de aprendizaje supervisado , se entrena una función , donde se considera como el espacio de datos de entrada, y es el espacio de datos de salida, que predice bien sobre los elementos de la distribución de probabilidad conjunta sobre . En realidad, en los entrenamientos nunca se conoce la verdadera distribución. Por lo general, por el contrario, se accede al conjunto de ejemplos de entrenamiento . Bajo estas condiciones , la función de pérdida se da como , tal que mide la diferencia entre el valor predicho y el valor real de . El objetivo ideal es elegir una función , donde hay un espacio de funciones, llamado espacio de hipótesis, tal que la pérdida total sea mínima en algún sentido. Dependiendo del tipo de modelo (estadístico o contradictorio), se pueden desarrollar diferentes conceptos de pérdida que conducen a diferentes algoritmos de aprendizaje. ${\ estilo de visualización f: X \ a Y}$ $X$ $Y$ $p(x, y)$ $X \veces Y$ $p(x, y)$ ${\ estilo de visualización (x_ {1}, y_ {1}), \ puntos, (x_ {n}, y_ {n})}$ $V:Y\times Y\to \mathbb {R}$ ${\ estilo de visualización V (f (x), y)}$ $f(x)$ $y$ $f\in {\mathcal {H}}$ ${\ matemáticas {H}}$

Una visión estadística del aprendizaje en línea

En los modelos de aprendizaje estadístico, se supone que la muestra de prueba se extrae de la distribución real y el objetivo del aprendizaje es minimizar el "riesgo" esperado. ${\ estilo de visualización (x_ {i}, y_ {i})}$ $p(x, y)$

I[f]=\mathbb {E} [V(f(x),y)]=\int V(f(x),y)\,dp(x,y)\ .

El paradigma general en esta situación es evaluar la función minimizando el riesgo empírico o minimizando el riesgo empírico regularizado (típicamente usando la regularización de Tikhonov ). La elección de la función de pérdida aquí produce 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 estaría entrenando solo en nuevas entradas , el mejor predictor actual y alguna información almacenada adicional (que generalmente tiene requisitos de memoria independientes del tamaño de los datos). Para muchas configuraciones de problemas, como los métodos de kernel no lineales , el verdadero aprendizaje en línea no es posible, aunque se pueden usar formas híbridas de aprendizaje en línea con algoritmos recursivos, donde se permite que el valor dependa de todos los puntos de datos anteriores . En este caso, los requisitos de memoria ya no se pueden limitar porque se deben mantener todos los puntos anteriores, pero la solución puede tomar menos tiempo para calcularse con nuevos puntos de datos agregados que las técnicas de aprendizaje por lotes. ${\ estilo de visualización {\ sombrero {f))}$ ${\ estilo de visualización (x_{t+1},y_{t+1})}$ ${\ Displaystyle f_ {t}}$ ${\ estilo de visualización f_ {t + 1}}$ $pie$ $(x_{1},y_{1}),\ldots,(x_{t},y_{t})$

Una estrategia común para hacer frente a este problema es el aprendizaje por lotes pequeños, en el que se procesan pequeños lotes de puntos de datos en un momento dado, y esto puede verse como aprendizaje pseudo-en línea para un número total mucho menor de puntos de entrenamiento. La técnica de minilotes se utiliza iterando sobre los datos de entrenamiento para obtener una versión optimizada de algoritmos de aprendizaje automático de memoria externa, como el descenso de gradiente estocástico . Cuando se combina con la retropropagación, este es actualmente el método de entrenamiento de facto para las redes neuronales artificiales . ${\ estilo de visualización b \ geq 1}$ $b$

Ejemplo: mínimos cuadrados lineales

Los mínimos cuadrados lineales se utilizan aquí para explicar varias ideas de aprendizaje en línea. Las ideas son lo suficientemente generales como para ser aplicables a otros entornos, como otras funciones de pérdida convexa.

Aprendizaje por lotes

En un entorno supervisado con una función de pérdida cuadrática , el objetivo es minimizar la pérdida empírica

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}

, dónde

x_{j}\en \mathbb {R} ^{d},w\en \mathbb {R} ^{d},y_{j}\en \mathbb {R}

Sea una matriz de datos y sea una matriz de valores objetivo después de la llegada de los primeros puntos de datos. Suponiendo que la matriz de covarianza es invertible (de lo contrario, se debe realizar un procedimiento similar a la regularización de Tikhonov), la mejor solución del método de mínimos cuadrados está dada por la igualdad $X$ ${\ estilo de visualización i \ veces d}$ $Y$ ${\ estilo de visualización i \ veces 1}$ $i$ ${\ estilo de visualización \ Sigma _ {i} = X ^ {T} X}$ $f^{*}(x)=\langle w^{*},x\rangle$

w^{*}=(X^{T}X)^{-1}X^{T}Y=\Sigma_{i}^{-1}\sum_{j=1}^{ i}x_{j}y_{j}

Ahora el cálculo de la matriz de covarianza tomará tiempo, la inversión de matriz tomará tiempo y la multiplicación de matriz tomará tiempo, lo que da el tiempo total . Si hay un total de puntos en el conjunto de datos y necesita volver a calcular la solución después de que llega cada punto de datos , el enfoque natural tendrá una complejidad completa . Tenga en cuenta que si la matriz está almacenada, la actualización en cada paso solo requiere agregar , lo que lleva tiempo, lo que reduce el tiempo total a , pero requiere espacio de almacenamiento adicional [ 2] . ${\displaystyle \Sigma _{i}=\sum _{j=1}^{i}x_{j}x_{j}^{T))$ ${\ estilo de visualización O (identificación ^ {2})}$ ${\ estilo de visualización d \ veces d}$ ${\ estilo de visualización O (d ^ {3})}$ ${\ estilo de visualización O (d ^ {2})}$ $O(id^{2}+d^{3})$ $norte$ $i=1,\ldots,n$ $O(n^{2}d^{2}+nd^{3})$ ${\ estilo de visualización \ Sigma _ {i}}$ ${\ estilo de visualización x_{i+1}x_{i+1}^{T))$ ${\ estilo de visualización O (d ^ {2})}$ $O(fin^{2}+fin^{3})=O(fin^{3})$ ${\ estilo de visualización O (d ^ {2})}$ ${\ estilo de visualización \ Sigma _ {i}}$

Aprendizaje en línea: mínimos cuadrados recursivos

Los mínimos cuadrados recursivos consideran un enfoque en línea para los mínimos cuadrados. Se puede demostrar que con la inicialización y la solución del método de mínimos cuadrados lineales se puede calcular de la siguiente manera: ${\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} ^ {T} \ Gamma _ {i-1} }}{1+x_{i}^{T}\Gamma _{i-1}x_{i}}}}

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

El algoritmo iterativo anterior se puede probar por inducción en [3] . La prueba también muestra que . Se pueden considerar mínimos cuadrados recursivos en el contexto de filtros adaptativos (ver Mínimos cuadrados recursivos ). $i$ ${\ estilo de visualización \ Gamma _ {i} = \ Sigma _ {i} ^ {-1}}$

La complejidad de los pasos de este algoritmo es , que es más rápida que la complejidad de aprendizaje por lotes correspondiente. La memoria requerida para cada paso para almacenar la matriz es aquí una constante . Para el caso en que no sea reversible, se considera una versión regularizada de la función de pérdida . Entonces es fácil mostrar que el mismo algoritmo funciona con , y las iteraciones continuas dan [2] . $norte$ $O(nd^{2})$ $i$ $\gamma _{i}$ ${\ estilo de visualización O (d ^ {2})}$ ${\ estilo de visualización \ Sigma _ {i}}$ $\sum _{j=1}^{n}(x_{j}^{T}w-y_{j})^{2}+\lambda ||w||_{2}^{2 }$ ${\ estilo de visualización \ Gamma _ {0} = (yo + \ lambda yo) ^ {-1))$ ${\displaystyle \Gamma _{i}=(\Sigma _{i}+\lambda I)^{-1))$

Método de descenso de gradiente estocástico

Si la igualdad

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

Reemplazado por

\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 en , esto se convierte en un algoritmo de descenso de gradiente estocástico. En este caso, la complejidad de los pasos de este algoritmo se reduce a . El requisito de memoria en cada paso es una constante . ${\displaystyle \Gamma _{i}\in \mathbb {R} ^{d\times d))$ $\gamma _{i}\in \mathbb {R}$ $norte$ ${\ estilo de visualización O (fin)}$ $i$ ${\ estilo de visualización O (d)}$

Sin embargo, el tamaño del paso para resolver el problema de minimización del riesgo esperado debe elegirse con cuidado, como se explicó anteriormente. Eligiendo el tamaño del paso de amortiguamiento , se puede probar la convergencia de la iteración promedio . Estos ajustes son un caso especial de optimización estocástica , un problema de optimización muy conocido [2] . ${\ estilo de visualización \ gamma _ {i}}$ ${\ estilo de visualización \ gamma _ {i} \ approx {\ frac {1} {\ sqrt {i}}}}$ ${\overline {w}}_{n}={\frac {1}{n}}\sum_{i=1}^{n}w_{i}$

Descenso de gradiente estocástico incremental

En la práctica, es posible realizar varios pases de gradiente estocástico sobre los datos. El algoritmo resultante se denomina método de gradiente incremental y corresponde a la iteración

\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 de gradiente estocástico es que aquí se elige decidir qué punto de entrenamiento se visita en el paso . Tal secuencia puede ser aleatoria o determinista. El número de iteraciones se desacopla así del número de puntos (cada punto se puede ver más de una vez). Puede demostrarse que el método del gradiente incremental proporciona una minimización empírica del riesgo [4] . Las técnicas incrementales pueden tener ventajas cuando se considera la función objetivo como la suma de muchos elementos, por ejemplo, como un error empírico de un conjunto de datos muy grande [2] . $t_{yo}$ $i$

Métodos nucleares

Los núcleos se pueden usar para extender los algoritmos anteriores a modelos no paramétricos (o modelos en los que los parámetros forman un espacio de dimensión infinita). El procedimiento correspondiente ya no estará realmente en línea y en su lugar almacenará todos los puntos de datos, pero el método sigue siendo más rápido que la fuerza bruta. Esta discusión se limita al caso de pérdida cuadrática, aunque puede extenderse a cualquier función de pérdida convexa. Se puede demostrar por inducción directa [2] que cuando a es una matriz de datos, a es la salida después de los pasos del algoritmo de descenso de gradiente aleatorio, entonces ${\ estilo de visualización X_ {i}}$ ${\ estilo de visualización w_ {i}}$ $i$

w_{i}=X_{i}^{T}c_{i}

donde y la secuencia satisface las relaciones recurrentes $\textstyle c_{i}=((c_{i})_{1},(c_{i})_{2},...,(c_{i})_{i})\in \mathbb{R} ^{i}$ $c_{i}$

{\ estilo de visualización c_ {0} = 0}

(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 )))

Tenga en cuenta que aquí está el kernel estándar en , y la función predictiva tiene la forma $\langle x_{j},x_{i}\rangle$ ${\displaystyle \mathbb {R} ^{d))$

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

Ahora, si introducimos un núcleo común y representamos la función de predicción como $k$

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

entonces la misma prueba muestra que la minimización por mínimos cuadrados de la función de pérdida se obtiene reemplazando la recursividad anterior con

{\displaystyle (c_{i})_{i}=\gamma_{i}{\Big (}y_{i}-\sum_{j=1}^{i-1}(c_{i-1 })_{j}K(x_{j},x_{i}){\Grande)))

La expresión anterior requiere recordar todos los datos a actualizar . La complejidad de tiempo total para la recursividad, si se calcula para el -ésimo punto de datos, es , donde es el costo de calcular el kernel en un par de puntos [2] . Luego, el uso del kernel permite el movimiento desde un espacio de parámetros de dimensión finita a un espacio posiblemente de dimensiones infinitas representado por el kernel , en lugar de recurrir al espacio de parámetros , cuya dimensión es la misma que el tamaño del conjunto de datos de entrenamiento. En general, este enfoque es una consecuencia del teorema de representación [2] . $c_{i}$ $norte$ $O(n^{2}dk)$ $k$ ${\displaystyle \textstyle w_{i}\in \mathbb {R} ^{d))$ $k$ ${\displaystyle \textstyle c_{i}\in \mathbb {R} ^{i))$

Aprendizaje progresivo

El aprendizaje progresivo es un modelo de aprendizaje efectivo que se demuestra en el proceso de aprendizaje de las personas. Este proceso de aprendizaje es continuo, proveniente de la experiencia directa. La técnica de aprendizaje progresivo en el aprendizaje automático puede aprender nuevas clases o etiquetas dinámicamente sobre la marcha [5] . Si bien el entrenamiento en línea puede entrenar nuevas muestras de datos que ingresan secuencialmente, no pueden entrenar nuevas clases de datos . El paradigma de aprendizaje de aprendizaje progresivo es independiente del número de restricciones de clase y puede enseñar nuevas clases conservando el conocimiento de las clases anteriores. Sin embargo, si se encuentra una nueva clase (que no ocurre naturalmente), el clasificador se reconstruye automáticamente y los parámetros se calculan de tal manera que se conserva el conocimiento previo. Esta técnica es adecuada para aplicaciones del mundo real donde a menudo se desconoce el número de clases y se requiere aprendizaje en línea a partir de datos en tiempo real.

Optimización convexa en línea

La optimización convexa en línea [6] es un esquema de decisión general que utiliza la optimización convexa para obtener algoritmos eficientes. El esquema es una repetición múltiple de las siguientes acciones:

Para ${\ estilo de visualización t = 1,2,..., T}$

El estudiante recibe entrada ${\ Displaystyle x_ {t}}$
El estudiante forma una salida a partir de un conjunto convexo fijo ${\ estilo de visualización w_ {t}}$ $S$
Nature devuelve el valor de una función de pérdida convexa . $v_{t}:S\rightarrow \mathbb {R}$
El alumno da cuenta de la pérdida y actualiza el modelo . $v_{t}(w_{t})$

El objetivo es minimizar el "arrepentimiento" o la diferencia entre la pérdida total y la pérdida en el mejor punto fijo en retrospectiva. Como ejemplo, considere el caso de la regresión lineal de mínimos cuadrados en línea. Aquí el peso de los vectores proviene de un conjunto convexo y la naturaleza devuelve una función de pérdida convexa . Tenga en cuenta que se envía implícitamente con . ${\ estilo de visualización u \ en S}$ ${\displaystyle S=\mathbb {R} ^{d))$ $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 pueden encajar en el esquema de optimización convexo en línea. Por ejemplo, en la clasificación en línea, el área de predicción y las funciones de pérdida no son convexas. En tales escenarios, se utilizan dos técnicas simples de reducción de casos convexos: aleatorización y funciones de pérdida sustituta.

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

Sigue al líder

La regla de aprendizaje más simple para un ensayo es elegir (en el paso actual) la hipótesis que tiene la menor pérdida entre todas las rondas anteriores. Este algoritmo se llama " Seguir al líder " y simplemente da una vuelta : $t$

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

Este método se puede considerar entonces como un algoritmo codicioso . Para el caso de la optimización cuadrática en línea (donde la función de pérdida es ), se puede demostrar que el límite de "arrepentimiento" crece a medida que . Sin embargo, no se pueden obtener límites similares para el algoritmo de seguimiento del líder para otras familias de modelos importantes como para la optimización lineal en línea. Para obtenerlos, se agrega regularización al algoritmo. $v_{t}(w)=||w-x_{t}||_{2}^{2}$ ${\ estilo de visualización \ registro (T)}$

Siguiendo a un líder regularizado

Esta es una modificación natural del algoritmo de seguimiento de líderes que se utiliza para estabilizar las decisiones de seguimiento de líderes y obtener mejores límites de arrepentimiento. Se elige una función de regularización y se realiza el entrenamiento en la ronda t de la siguiente manera: $R:S\rightarrow \mathbb {R}$

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

Como caso especial, considere el caso de la optimización lineal en línea, es decir, cuando la naturaleza devuelve funciones de pérdida de la forma . También deja . Supongamos que se elige la función de regularización para algún número positivo . Entonces se puede demostrar que la iteración de minimizar el "arrepentimiento" se convierte en $v_{t}(w)=\langle w,z_{t}\rangle$ ${\displaystyle S=\mathbb {R} ^{d))$ $R(w)={\frac {1}{2\eta}}||w||_{2}^{2}$ ${\ estilo de visualización \ eta}$

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

Tenga en cuenta que esto se puede reescribir como , que se ve exactamente como el método de descenso de gradiente en línea. $w_{t+1}=w_{t}-\eta \nabla v_{t}(w_{t})$

Si S es un subespacio convexo , S debe proyectarse, lo que da como resultado una regla de actualización modificada ${\displaystyle \mathbb {R} ^{d))$

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

El algoritmo se conoce como proyección perezosa porque el vector acumula gradientes. Esto también se conoce como el algoritmo de promedio doble de Nesterov (o método de promedio doble subgradiente [7] ). En este escenario, las funciones de pérdida lineal y el "arrepentimiento" de regularización cuadrática se limitan a , y luego el "arrepentimiento" promedio tiende a 0 . ${\ estilo de visualización \ theta _ {t + 1}}$ ${\ estilo de visualización O ({\ sqrt {T)))}$

Descenso de subgradiente en línea

El límite de "arrepentimiento" para las funciones de pérdida lineal se ha demostrado anteriormente . Para generalizar el algoritmo a cualquier función de pérdida convexa, la función subgradiente se usa como una aproximación lineal alrededor de , lo que conduce al algoritmo de descenso de subgradiente en línea: $v_{t}(w)=\langle w,z_{t}\rangle$ $\parcial v_{t}(w_{t})$ ${\ Displaystyle v_ {t}}$ ${\ Displaystyle v_ {t}}$ ${\ estilo de visualización w_ {t}}$

Iniciar un parámetro ${\ estilo de visualización \ eta, w_ {1} = 0}$

Para ${\ estilo de visualización t = 1,2,..., T}$

Hacemos una predicción usando , lo obtenemos de la naturaleza . ${\ estilo de visualización w_ {t}}$ $pie$
Elegir $z_{t}\in \parcial v_{t}(w_{t})$
Si , haz una actualización ${\displaystyle S=\mathbb {R} ^{d))$ ${\displaystyle w_{t+1}=w_{t}-\eta z_{t))$
Si , proyecte gradientes acumulativos a ie ${\displaystyle S\subconjunto \mathbb {R} ^{d))$ $S$ ${\displaystyle w_{t+1}=\Pi _{S}(\eta \theta _{t+1}),\theta _{t+1}=\theta _{t}+z_{t))$

Puede usar el algoritmo de descenso de subgradiente en línea para obtener los límites de "arrepentimiento" para la versión en línea de la máquina de vectores de soporte para la clasificación, que usa una función de pérdida lineal por partes ${\ estilo de visualización O ({\ sqrt {T)))}$ $v_{t}(w)=\max\{0,1-y_{t}(w\cdot x_{t})\}$

Otros algoritmos

Los algoritmos de seguimiento de líder con regularización cuadrada conducen a algoritmos de gradiente proyectados perezosamente, como se describió anteriormente. Para usar el enfoque anterior para cualquier función convexa y regularizadores, se puede usar el descenso de espejo en línea. La regularización óptima en una función lineal por partes se puede obtener para funciones de pérdida lineal, lo que lleva al algoritmo AdaGrad . Para la regularización euclidiana, se puede demostrar que el límite de "arrepentimiento" es igual y se puede mejorar para funciones de pérdida estrictamente convexas y exp-cóncavas. ${\ estilo de visualización O ({\ sqrt {T)))}$ ${\ estilo de visualización O (\ log T)}$

Interpretaciones del aprendizaje en línea

El paradigma de aprendizaje en línea tiene diferentes interpretaciones según la elección del modelo de aprendizaje, cada una con una calidad diferente de predicciones de secuencias de características . Para la discusión, usamos el algoritmo de descenso de gradiente estocástico. Como se señaló anteriormente, la recursividad del algoritmo viene dada por la igualdad ${\displaystyle f_{1},f_{2},\ldots,f_{n))$

\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 del gradiente estocástico como una aplicación al problema de minimización del riesgo esperado definido anteriormente [8] . Además, en el caso de un flujo de datos infinito, dado que se supone que las instancias se muestrean a partir de una distribución independiente e igualmente distribuida , las secuencias de gradiente en la iteración anterior son muestras independientes e igualmente distribuidas de la estimación del gradiente estocástico de riesgo esperado y, por lo tanto, uno puede aplicar los resultados de complejidad para el método de descenso de gradiente estocástico para restringir la desviación , donde es el minimizador [9] . Esta interpretación también es válida para conjuntos de entrenamiento finitos. Aunque los gradientes ya no serán independientes al iterar sobre los datos, se pueden obtener resultados de complejidad en casos especiales. ${\ estilo de visualización yo [w]}$ ${\ estilo de visualización (x_{1}, y_ {1}), (x_ {2}, y_ {2}), \ puntos }$ $p(x, y)$ ${\ estilo de visualización V (\ cdot, \ cdot)}$ ${\ estilo de visualización yo [w]}$ $yo[w_{t}]-yo[w^{\ast}]$ $w^{\ast}$ ${\ estilo de visualización yo [w]}$

La segunda interpretación se aplica al caso de un conjunto de entrenamiento finito y considera el algoritmo de descenso de gradiente estocástico como un representante del descenso de gradiente incremental [4] . En este caso, uno puede mirar el riesgo empírico:

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

Dado que los gradientes en iteraciones de descenso de gradiente incremental son estimaciones estocásticas del gradiente , esta interpretación está relacionada con el método de descenso de gradiente estocástico, pero se aplica a la minimización empírica del riesgo en lugar del riesgo esperado. Debido a que esta interpretación se trata del riesgo empírico en lugar del riesgo esperado, los pases múltiples sobre los datos son perfectamente válidos y, de hecho, conducen a límites de varianza estrechos , donde . ${\ estilo de visualización V (\ cdot, \ cdot)}$ ${\ estilo de visualización I_ {n} [w]}$ $I_{n}[w_{t}]-I_{n}[w_{n}^{\ast}]$ ${\displaystyle w_{n}^{\ast))$ ${\ estilo de visualización I_ {n} [w]}$

Implementaciones

Vowpal Wabbit : un sistema de aprendizaje en línea rápido, de código abierto y de memoria externa con un conjunto de técnicas de aprendizaje automático compatibles, con ponderación de importancia y una selección de varias funciones de pérdida y algoritmos de optimización. El sistema utiliza un truco hash para limitar el tamaño del conjunto de funciones, independientemente del tamaño de los datos de entrenamiento.
scikit-learn : proporciona una implementación fuera de memoria de algoritmos para
- clasificadores: perceptrón , clasificador de descenso de gradiente estadístico , clasificador bayesiano ingenuo .
- regresiones: regresión de descenso de gradiente estocástico, regresor pasivo agresivo.
- agrupamiento: método k-means .
- extracción de características: aprendizaje de vocabulario en mini lotes , análisis incremental de componentes principales .

Véase también

Memoria temporal jerárquica
método del k-vecino más cercano
Aprendizaje perezoso
Cuantificación de vectores durante el entrenamiento
Aprendizaje sin conexión , modelo opuesto
Algoritmo en línea
Algoritmo de flujo
perceptrón
Descenso de gradiente estocástico
Aprendiendo con un maestro
Optimización en línea

Notas

↑ La interferencia catastrófica es la tendencia de las redes neuronales artificiales a olvidar repentinamente por completo todo lo que la red ha sido entrenada para hacer antes.
↑ 1 2 3 4 5 6 7 Rosasco, Poggio, 2015 .
↑ Yin, Kushner, 2003 , pág. 8–12.
↑ 12 Bertsekas , 2011 .
↑ Venkatesan, Meng Joo, 2016 , pág. 310–321.
↑ Hazán, 2015 .
↑ Dolgopolik, 2016 .
↑ Botto, 1998 .
↑ Kushner, Yin, 1997 .

Literatura

León Bottou. Algoritmos en línea y aproximaciones estocásticas // Aprendizaje en línea y redes neuronales . - Prensa de la Universidad de Cambridge, 1998. - ISBN 978-0-521-65263-6 .
Rosasco L., Poggio T. Capítulo 7 - Aprendizaje en línea // Aprendizaje automático: un enfoque de regularización . MIT-9.520 Apuntes de clase. - 2015. - (Manuscrito).
Harold J. Kushner, G. George Yin. Algoritmos de Aproximación Estocástica y Aplicaciones. - Nueva York: Springer-Verlag, 1997. - ISBN 0-387-94916-X .
- Harold J. Kushner, G. George Yin. Aproximación Estocástica y Algoritmos Recursivos y Aplicaciones. - 2ª ed. - Nueva York: Springer-Verlag, 2003. - ISBN 0-387-00894-2 .
Elad Hazán. Introducción a la optimización convexa en línea . — Fundamentos y Tendencias® en Optimización, 2015.
Rajasekar Venkatesan, Er Meng Joo. Una nueva técnica de aprendizaje progresivo para la clasificación multiclase // Neurocomputación. - 2016. - T. 207 . -doi : 10.1016/ j.neucom.2016.05.006 . -arXiv : 1609.00085 . _
El método de Dolgopolik MV Nesterov para minimizar funciones convexas. — 2016.
Harold J. Yin, G. George Kushner. Aproximación estocástica y algoritmos y aplicaciones recursivos. - Segundo. - Nueva York: Springer, 2003. - ISBN 978-0-387-21769-7 .
Bertsekas DP Métodos de gradiente incremental, subgradiente y proximal para la optimización convexa: una encuesta // Optimización para el aprendizaje automático. - 2011. - Edición. 85 .

Enlaces

http://onlineprediction.net/ Archivado el 31 de octubre de 2018 en Wayback Machine , Wiki for On-Line Prediction.

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ICA LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG