Aprendizaje automático online

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.