Aprendizagem de máquina online

Na ciência da computação, o aprendizado de máquina online é um método de aprendizado de máquina no qual os dados ficam disponíveis em uma ordem sequencial e são usados para atualizar o melhor preditor para dados futuros em cada etapa, em oposição às técnicas de aprendizado em lote que geram o melhor preditor através do aprendizado com todo o conjunto de dados de treinamento de uma só vez. O aprendizado online é uma técnica comum usada em áreas de aprendizado de máquina onde é computacionalmente inviável treinar sobre todo o conjunto de dados, exigindo a necessidade de algoritmos fora do núcleo. Também é usado em situações em que é necessário que o algoritmo se adapte dinamicamente a novos padrões nos dados ou quando os próprios dados são gerados em função do tempo, por exemplo, previsão de preços de ações. Algoritmos de aprendizado online podem ser propensos a interferências catastróficas, um problema que pode ser resolvido por abordagens de aprendizado incremental.

Introdução

No contexto da aprendizagem supervisionada, deve-se aprender uma função $f:X\to Y$, em que $X$ é pensado como um espaço de entradas e $Y$ como um espaço de saídas, que prevê bem as instâncias extraídas de uma distribuição de probabilidade conjunta $p(x,y)$ sobre $X\times Y$. Na prática, o aprendiz nunca sabe a verdadeira distribuição $p(x,y)$ sobre as instâncias. Em vez disso, o aprendiz geralmente tem acesso a um conjunto de exemplos de treinamento $(x_{1},y_{1}),\ldots ,(x_{n},y_{n})$. Nesta configuração, a função de perda é dada como $V:Y\times Y\to \mathbb {R}$, de tal modo que $V(f(x),y)$ mede a diferença entre o valor previsto $f(x)$ e o valor verdadeiro $y$. O objetivo ideal é selecionar uma função $f\in {\mathcal {H}}$, Onde ${\mathcal {H}}$ é um espaço de funções chamado espaço de hipóteses, de modo que alguma noção de perda total seja minimizada. Dependendo do tipo de modelo (estatístico ou adversário), pode-se conceber diferentes noções de perda, que levam a diferentes algoritmos de aprendizado.

Visão estatística do aprendizado online

Em modelos de aprendizado estatístico, assume-se que as amostras de treinamento $(x_{i},y_{i})$ foram extraídas da verdadeira distribuição $p(x,y)$ e o objetivo é minimizar o "risco" esperado

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

Um paradigma comum nesta situação é estimar uma função ${\hat {f}}$ através da minimização do risco empírico ou minimização do risco empírico regularizado (geralmente regularização de Tikhonov). Aqui a escolha da função de perda dá origem a vários algoritmos de aprendizado bem conhecidos, tais como mínimos quadrados regularizados e máquinas de vetores de suporte. Um modelo puramente online nesta categoria aprenderia com base apenas na nova entrada $(x_{t+1},y_{t+1})$, o melhor preditor atual $f_{t}$ e algumas informações extras armazenadas (que geralmente devem ter requisitos de armazenamento independentes do tamanho dos dados de treinamento). Para muitas formulações, tais como métodos de kernel não lineares, um aprendizado verdadeiramente online não é possível, embora possa ser usada uma forma híbrida de aprendizado online com algoritmos recursivos, em que se permite que $f_{t+1}$ dependa de $f_{t}$ e de todos os pontos de dados anteriores $(x_{1},y_{1}),\ldots ,(x_{t},y_{t})$. Nesse caso, não é mais garantido que os requisitos de espaço sejam constantes, pois é necessário o armazenamento de todos os pontos de dados anteriores, mas a solução pode levar menos tempo para ser calculada com a adição de um novo ponto de dados, em comparação com as técnicas de aprendizado em lote.

Uma estratégia comum para superar os problemas acima é aprender utilizando mini-lotes, que processam um pequeno lote de $b\geq 1$ pontos de dados por vez, isso pode ser considerado como um aprendizagem pseudo-online para $b$ muito menor que o número total de pontos de treinamento. Técnicas de mini-lote são usadas com passagem repetida sobre os dados de treinamento para obter versões otimizadas fora do núcleo de algoritmos de aprendizado de máquina, por exemplo, gradiente descendente estocástico. Quando combinado com retropropagação, este é atualmente o método de treinamento de fato para treinar redes neurais artificiais.

Exemplo: mínimos quadrados lineares

O exemplo simples de mínimos quadrados lineares é usado para explicar uma variedade de ideias em aprendizado online. As ideias são gerais o suficiente para serem aplicadas a outras configurações, por exemplo, com outras funções de perda convexas.

Aprendizagem em lote

Considere o cenário de aprendizado supervisionado em que $f$ é uma função linear a ser aprendida:

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

em que $x_{j}\in \mathbb {R} ^{d}$ é um vetor de entradas (pontos de dados) e $w\in \mathbb {R} ^{d}$ é um vetor de filtro linear. O objetivo é calcular o vetor de filtro $w$ . Para isso, uma função de perda quadrática

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

é usada para calcular o vetor $w$ que minimiza a perda 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}$

em que

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

Seja $X$ a matriz de dados de ordem $i\times d$ e $y\in \mathbb {R} ^{i}$ o vetor coluna de valores alvo após a chegada dos primeiros $i$ pontos de dados. Assumindo que a matriz de covariância $\Sigma _{i}=X^{T}X$ seja invertível (caso contrário, é preferível proceder de forma semelhante à regularização de Tikhonov), a melhor solução $f^{*}(x)=\langle w^{*},x\rangle$ para o problema dos mínimos quadrados lineares é dada por

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

Agora, o cálculo da matriz de covariância $\Sigma _{i}=\sum _{j=1}^{i}x_{j}x_{j}^{T}$ leva tempo $O(id^{2})$, a inversão de uma matriz $d\times d$ leva tempo $O(d^{3})$, enquanto o restante da multiplicação leva tempo $O(d^{2})$, o que resulta em um tempo total de $O(id^{2}+d^{3})$. Quando há um total de $n$ pontos no conjunto de dados, o recálculo da solução após a chegada de cada ponto de dados $i=1,\ldots ,n$ pela abordagem ingênua terá uma complexidade total $O(n^{2}d^{2}+nd^{3})$. Note que ao armazenar a matriz $\Sigma _{i}$ para então atualizá-la em cada etapa é preciso apenas adicionar $x_{i+1}x_{i+1}^{T}$, que leva tempo $O(d^{2})$, reduzindo o tempo total para $O(nd^{2}+nd^{3})=O(nd^{3})$, mas com um espaço de armazenamento adicional de $O(d^{2})$ para armazenar $\Sigma _{i}$.

Aprendizagem online: mínimos quadrados recursivos

O algoritmo recursivo dos mínimos quadrados (RLS) considera uma abordagem online para o problema dos mínimos quadrados. Pode-se mostrar que inicializando $\textstyle w_{0}=0\in \mathbb {R} ^{d}$ e $\textstyle \Gamma _{0}=I\in \mathbb {R} ^{d\times d}$, a solução do problema de mínimos quadrados lineares dada na seção anterior pode ser obtida por meio da seguinte iteração:

$\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})$

O algoritmo de iteração acima pode ser provado usando indução em $i$. A prova também mostra que $\Gamma _{i}=\Sigma _{i}^{-1}$. Pode-se olhar para RLS também no contexto de filtros adaptativos (ver RLS).

A complexidade para $n$ passos deste algoritmo é $O(nd^{2})$, que é uma ordem de magnitude mais rápida do que a complexidade do aprendizado em lote correspondente. Aqui, os requisitos de armazenamento em cada etapa $i$ consistem em armazenar a matriz $\Gamma _{i}$, que é constante em $O(d^{2})$. Para o caso quando $\Sigma _{i}$ não é invertível, considere a versão regularizada da função de perda do problema $\sum _{j=1}^{n}(x_{j}^{T}w-y_{j})^{2}+\lambda ||w||_{2}^{2}$ . Então, mostra-se que o mesmo algoritmo funciona com $\Gamma _{0}=(I+\lambda I)^{-1}$, e as iterações fornecem $\Gamma _{i}=(\Sigma _{i}+\lambda I)^{-1}$.

Gradiente descendente estocástico

Quando a expressão

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

é substituída 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})$

ou $\Gamma _{i}\in \mathbb {R} ^{d\times d}$ por $\gamma _{i}\in \mathbb {R}$, tem-se o algoritmo de gradiente descendente estocástico. Neste caso, a complexidade para $n$ passos deste algoritmo se reduz a $O(nd)$. Os requisitos de armazenamento em cada etapa $i$ são constantes em $O(d)$.

No entanto, o tamanho do passo $\gamma _{i}$ precisa ser escolhido com cuidado para resolver o problema de minimização do risco esperado, conforme detalhado acima. Escolhendo um tamanho de passo cada vez menor $\gamma _{i}\approx {\frac {1}{\sqrt {i}}},$ pode-se provar a convergência do iterado médio ${\overline {w}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}w_{i}$. Essa configuração é um caso especial de otimização estocástica, um problema bem conhecido em otimização.

Gradiente descendente estocástico incremental

Na prática, pode-se realizar múltiplas passagens do gradiente estocástico (também chamadas de ciclos ou épocas) sobre os dados. O algoritmo assim obtido chama-se método do gradiente incremental e corresponde a uma iteração dada por

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

A principal diferença com o método de gradiente estocástico é que aqui uma sequência $t_{i}$ é escolhida para decidir qual ponto de treinamento é visitado na $i$-ésima etapa. Tal sequência pode ser estocástica ou determinística. O número de iterações é então desacoplado do número de pontos (cada ponto pode ser considerado mais de uma vez). Pode-se mostrar que o método de gradiente incremental fornece um minimizador para o risco empírico. Técnicas incrementais podem ser vantajosas ao considerar funções objetivo compostas de uma soma de muitos termos, por exemplo, um erro empírico correspondente a um conjunto de dados muito grande.

Métodos de núcleo

Núcleos podem ser usados para estender os algoritmos acima para modelos não paramétricos (ou modelos em que os parâmetros formam um espaço dimensional infinito). O procedimento correspondente não será mais verdadeiramente online e, em vez disso, envolverá o armazenamento de todos os pontos de dados, mas ainda é mais rápido que o método de força bruta. Essa discussão se restringe ao caso da função de perda quadrática, mas pode ser estendida para qualquer perda convexa. Pode ser mostrado por indução que se $X_{i}$ é a matriz de dados e $w_{i}$ é a saída depois $i$ passos do algoritmo SGD, então,

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

onde $\textstyle c_{i}=((c_{i})_{1},(c_{i})_{2},...,(c_{i})_{i})\in \mathbb {R} ^{i}$ e a sequência $c_{i}$ satisfaz a recursão:

$c_{0}=0$

$(c_{i})_{j}=(c_{i-1})_{j},j=1,2,...,i-1$ e

$(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 aqui $\langle x_{j},x_{i}\rangle$ é apenas o núcleo padrão em $\mathbb {R} ^{d}$, e o preditor tem a forma

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

Agora, se um núcleo geral $K$ é introduzido em vez disso e se considera o preditor

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

então a mesma demonstração também mostrará que o preditor que minimiza a perda de mínimos quadrados é obtido ao modificar a recursão acima para

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

A expressão acima requer o armazenamento de todos os dados para atualização de $c_{i}$. A complexidade de tempo total para a recursão ao avaliar para o $n$-ésimo ponto de dados é $O(n^{2}dk)$, em que $k$ é o custo de avaliar o núcleo em um único par de pontos. Assim, o uso do núcleo permitiu o movimento de um espaço de parâmetros de dimensão finita $\textstyle w_{i}\in \mathbb {R} ^{d}$ a um feature de dimensão possivelmente infinita representado por um núcleo $K$, executando a recursão no espaço de parâmetros $\textstyle c_{i}\in \mathbb {R} ^{i}$, cuja dimensão é igual ao tamanho do conjunto de dados de treinamento. Em geral, isso é uma consequência do teorema do representante.

Otimização convexa on-line

Otimização convexa online (OCO) é uma estrutura geral para tomada de decisão que faz uso de otimização convexa para permitir algoritmos eficientes. A estrutura é a de um jogo de repetição com a seguinte forma:

Para $t=1,2,...,T$

• O aprendiz recebe informações $x_{t}$
• O aprendiz retorna $w_{t}$ de um conjunto convexo fixo $S$
• A natureza envia de volta uma função de perda convexa $v_{t}:S\rightarrow \mathbb {R}$.
• O aprendiz incorre uma perda $v_{t}(w_{t})$ e atualiza seu modelo

O objetivo é minimizar o arrependimento, ou seja, a diferença entre a perda cumulativa e a perda do melhor ponto fixo $u\in S$ em retrospectiva. Como exemplo, considere o caso da regressão linear de mínimos quadrados online. Aqui, os vetores de peso vêm do conjunto convexo $S=\mathbb {R} ^{d}$, e a natureza envia de volta a função de perda convexa $v_{t}(w)=(\langle w,x_{t}\rangle -y_{t})^{2}$. Observe que $y_{t}$ é implicitamente enviado com $v_{t}$.

Alguns problemas de predição online, no entanto, não podem se encaixar na estrutura do OCO. Por exemplo, na classificação online, o domínio de previsão e as funções de perda não são convexos. Em tais cenários, duas técnicas simples de convexificação são usadas: randomização e funções de perda substitutas.

Alguns algoritmos simples de otimização convexa online são:

Siga o líder (FTL)

A regra de aprendizado mais simples é tentar selecionar (na etapa atual) a hipótese que tem a menor perda em todas as rodadas anteriores. Esse algoritmo é chamado de siga o líder e é simplesmente dado na rodada $t$ por:

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

Este método pode ser visto como um algoritmo guloso. Para o caso de otimização quadrática online (onde a função de perda é $v_{t}(w)=||w-x_{t}||_{2}^{2}$), pode-se obter um limite de arrependimento que cresce como $\log(T)$. No entanto, limites semelhantes não podem ser obtidos para o algoritmo FTL para outras famílias importantes de modelos, como otimização linear online. Para fazer isso, modifica-se o FTL adicionando regularização.

Siga o líder regularizado (FTRL)

Esta é uma modificação natural do FTL que é usada para estabilizar as soluções FTL e obter melhores limites de arrependimento. Uma função de regularização $R:S\rightarrow \mathbb {R}$ é escolhida e o aprendizado realizado na rodada t da seguinte forma:

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

Como um exemplo especial, considere o caso de otimização linear online, isto é, aquele em que a natureza envia de volta funções de perda da forma $v_{t}(w)=\langle w,z_{t}\rangle$. Além disso, seja $S=\mathbb {R} ^{d}$. Suponha que a função de regularização $R(w)={\frac {1}{2\eta }}||w||_{2}^{2}$ é escolhida para algum número positivo $\eta$. Então, pode-se mostrar que a iteração de minimização de arrependimento se torna

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

Note que isso pode ser reescrito na forma $w_{t+1}=w_{t}-\eta \nabla v_{t}(w_{t})$, que se parece exatamente com a descida de gradiente online.

Se S é algum subespaço convexo de $\mathbb {R} ^{d}$, seria preciso projetar sobre S, levando à regra de atualização modificada

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

Este algoritmo é conhecido como projeção preguiçosa, pois o vetor $\theta _{t+1}$ acumula os gradientes. Também é conhecido como algoritmo de média dupla de Nesterov. Neste cenário em que as funções de perda são lineares e a regularização é quadrática, o arrependimento é limitado por $O({\sqrt {T}})$, e assim o arrependimento médio vai para 0 conforme desejado.

Subgradiente descendente online (OSD)

O exposto acima demonstrou um limite para o arrependimento para funções de perda lineares $v_{t}(w)=\langle w,z_{t}\rangle$. Para generalizar o algoritmo para qualquer função de perda convexa, o subgradiente $\partial v_{t}(w_{t})$ de $v_{t}$ é usado como uma aproximação linear para $v_{t}$ próximo de $w_{t}$, levando ao algoritmo de descida do subgradiente online:

Inicializar os parâmetros $\eta ,w_{1}=0$

Para $t=1,2,...,T$

• Prever usando $w_{t}$, receber $f_{t}$ da natureza.
• Escolher $z_{t}\in \partial v_{t}(w_{t})$
• Se $S=\mathbb {R} ^{d}$, atualizar como $w_{t+1}=w_{t}-\eta z_{t}$
• Se $S\subset \mathbb {R} ^{d}$, projetar gradientes cumulativos sobre $S$, ou seja, $w_{t+1}=\Pi _{S}(\eta \theta _{t+1}),\theta _{t+1}=\theta _{t}+z_{t}$

Pode-se usar o algoritmo OSD para derivar limites de arrependimento $O({\sqrt {T}})$ para a versão online dos SVM's para classificação, que usam a perda de articulação $v_{t}(w)=\max\{0,1-y_{t}(w\cdot x_{t})\}$.

Outros algoritmos

Algoritmos FTRL regularizados quadraticamente levam a algoritmos de gradiente projetados preguiçosos, conforme descrito acima. Para usar as ideias precedentes para funções convexas arbitrárias e regularizadores, pode-se usar a descida do espelho online. A regularização ótima em retrospectiva pode ser derivada para funções de perda linear, o que leva ao algoritmo AdaGrad. Para a regularização euclidiana, pode-se mostrar um limite de arrependimento de $O({\sqrt {T}})$, que pode ser melhorado ainda mais para $O(\log T)$ para funções de perda fortemente convexas e exp-côncavas.

Aprendizagem contínua

Aprendizado contínuo significa melhorar constantemente o modelo aprendido processando fluxos contínuos de informações. As capacidades de aprendizado contínuo são essenciais para sistemas de software e agentes autônomos que interagem em um mundo real em constante mudança. No entanto, o aprendizado contínuo é um desafio para modelos de aprendizado de máquina e redes neurais, pois a aquisição contínua de informações disponíveis de forma incremental a partir de distribuições de dados não estacionários geralmente leva a um esquecimento catastrófico.

Interpretações do aprendizado online

O paradigma da aprendizagem online tem diferentes interpretações dependendo da escolha do modelo de aprendizagem, cada uma das quais tem implicações distintas sobre a qualidade preditiva da sequência de funções $f_{1},f_{2},\ldots ,f_{n}$ . O algoritmo prototípico do gradiente descendente estocástico é usado para esta discussão. Como observado acima, sua recursão é dada por

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

A primeira interpretação considera o método do gradiente descendente estocástico aplicado ao problema de minimização do risco esperado $I[w]$ definido acima. De fato, no caso de um fluxo infinito de dados, uma vez que os exemplos $(x_{1},y_{1}),(x_{2},y_{2}),\ldots$ são assumidos como sendo retirados iid da distribuição $p(x,y)$, a sequência de gradientes de $V(\cdot ,\cdot )$ na iteração acima são uma amostra iid de estimativas estocásticas do gradiente do risco esperado $I[w]$ e, portanto, pode-se aplicar resultados de complexidade ao método do gradiente descendente estocástico para limitar o desvio $I[w_{t}]-I[w^{\ast }]$, em que $w^{\ast }$ é o minimizador de $I[w]$. Esta interpretação também é válida no caso de um conjunto de treinamento finito; embora com passagens múltiplas pelos dados os gradientes não sejam mais independentes, resultados ainda complexos podem ser obtidos em casos especiais.

A segunda interpretação se aplica quando o conjunto de treinamento é finito e considera o algoritmo SGD como uma instância do método gradiente descendente incremental. Neste caso, em vez disso, olha-se para o risco empírico:

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

Como os gradientes de $V(\cdot ,\cdot )$ nas iterações do gradiente descendente incremental também são estimativas estocásticas do gradiente de $I_{n}[w]$, essa interpretação também está relacionada ao método do gradiente descendente estocástico, mas aplicado a minimização do risco empírico em oposição ao risco esperado. Como essa interpretação diz respeito ao risco empírico e não ao risco esperado, várias passagens pelos dados são prontamente permitidas e, na verdade, levam a limites mais rígidos nos desvios $I_{n}[w_{t}]-I_{n}[w_{n}^{\ast }]$, onde $w_{n}^{\ast }$ é o minimizador de $I_{n}[w]$ .

Implementações

• Vowpal Wabbit: sistema de código aberto de aprendizado on-line rápido e fora do núcleo, notável por oferecer suporte a várias reduções de aprendizado de máquina, ponderação de importância e uma seleção de diferentes funções de perda e algoritmos de otimização. Ele usa o truque de hash para limitar o tamanho do conjunto de características independentemente da quantidade de dados de treinamento.
• scikit-learn: fornece implementações fora do núcleo de algoritmos para
  • Classificação: Perceptron, classificador SGD, classificador Naive bayes.
  • Regressão: Regressor SGD, Regressor Passivo Agressivo.
  • Agrupamento: k-means de minilote.
  • Extração de características: aprendizado de dicionário em minilote, PCA incremental.

Ver também

Paradigmas de aprendizagem

• Aprendizagem incremental
• Aprendizagem preguiçosa
• Aprendizagem offline, o modelo oposto
• Aprendizagem por reforço
• Bandidos multi-armados
• Aprendizagem supervisionada

Algoritmos gerais

• Algoritmo on-line
• Otimização on-line
• Algoritmo de streaming
• Gradiente descendente estocástico

Modelos de aprendizagem

• Teoria de ressonância adaptativa
• Memória temporal hierárquica
• Algoritmo dos k-vizinhos mais próximos
• Aprendizagem de quantização vetorial
• Perceptron

Ligações externas

• 6.883: Métodos Online em Machine Learning: Teoria e Aplicações. (em inglês) Alexandre Rakhlin. MIT.