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 , em que é pensado como um espaço de entradas e como um espaço de saídas, que prevê bem as instâncias extraídas de uma distribuição de probabilidade conjunta sobre . Na prática, o aprendiz nunca sabe a verdadeira distribuição sobre as instâncias. Em vez disso, o aprendiz geralmente tem acesso a um conjunto de exemplos de treinamento . Nesta configuração, a função de perda é dada como , de tal modo que mede a diferença entre o valor previsto e o valor verdadeiro . O objetivo ideal é selecionar uma função , Onde é 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 foram extraídas da verdadeira distribuição e o objetivo é minimizar o "risco" esperado

Um paradigma comum nesta situação é estimar uma função 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 , o melhor preditor atual 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 dependa de e de todos os pontos de dados anteriores . 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 pontos de dados por vez, isso pode ser considerado como um aprendizagem pseudo-online para 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 é uma função linear a ser aprendida:

em que é um vetor de entradas (pontos de dados) e é um vetor de filtro linear. O objetivo é calcular o vetor de filtro . Para isso, uma função de perda quadrática

é usada para calcular o vetor que minimiza a perda empírica

em que

.

Seja a matriz de dados de ordem e o vetor coluna de valores alvo após a chegada dos primeiros pontos de dados. Assumindo que a matriz de covariância seja invertível (caso contrário, é preferível proceder de forma semelhante à regularização de Tikhonov), a melhor solução para o problema dos mínimos quadrados lineares é dada por

.

Agora, o cálculo da matriz de covariância leva tempo , a inversão de uma matriz leva tempo , enquanto o restante da multiplicação leva tempo , o que resulta em um tempo total de . Quando há um total de pontos no conjunto de dados, o recálculo da solução após a chegada de cada ponto de dados pela abordagem ingênua terá uma complexidade total . Note que ao armazenar a matriz para então atualizá-la em cada etapa é preciso apenas adicionar , que leva tempo , reduzindo o tempo total para , mas com um espaço de armazenamento adicional de para armazenar .L. Rosasco, T. Poggio, Machine Learning: a Regularization Approach, MIT-9.520 Lectures Notes, Manuscript, Dec. 2015. Chapter 7 - Online Learning

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 e , a solução do problema de mínimos quadrados lineares dada na seção anterior pode ser obtida por meio da seguinte iteração:

O algoritmo de iteração acima pode ser provado usando indução em . A prova também mostra que . Pode-se olhar para RLS também no contexto de filtros adaptativos (ver RLS).

A complexidade para passos deste algoritmo é , 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 consistem em armazenar a matriz , que é constante em . Para o caso quando não é invertível, considere a versão regularizada da função de perda do problema . Então, mostra-se que o mesmo algoritmo funciona com , e as iterações fornecem .L. Rosasco, T. Poggio, Machine Learning: a Regularization Approach, MIT-9.520 Lectures Notes, Manuscript, Dec. 2015. Chapter 7 - Online Learning

Gradiente descendente estocástico

Quando a expressão

é substituída por

ou por , tem-se o algoritmo de gradiente descendente estocástico. Neste caso, a complexidade para passos deste algoritmo se reduz a . Os requisitos de armazenamento em cada etapa são constantes em .

No entanto, o tamanho do passo 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 pode-se provar a convergência do iterado médio . Essa configuração é um caso especial de otimização estocástica, um problema bem conhecido em otimização.L. Rosasco, T. Poggio, Machine Learning: a Regularization Approach, MIT-9.520 Lectures Notes, Manuscript, Dec. 2015. Chapter 7 - Online Learning

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

A principal diferença com o método de gradiente estocástico é que aqui uma sequência é escolhida para decidir qual ponto de treinamento é visitado na -é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.Bertsekas, D. P. (2011). Incremental gradient, subgradient, and proximal methods for convex optimization: a survey. Optimization for Machine Learning, 85. 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.L. Rosasco, T. Poggio, Machine Learning: a Regularization Approach, MIT-9.520 Lectures Notes, Manuscript, Dec. 2015. Chapter 7 - Online Learning

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çãoL. Rosasco, T. Poggio, Machine Learning: a Regularization Approach, MIT-9.520 Lectures Notes, Manuscript, Dec. 2015. Chapter 7 - Online Learning que se é a matriz de dados e é a saída depois passos do algoritmo SGD, então,

onde e a sequência satisfaz a recursão:

e

Observe que aqui é apenas o núcleo padrão em , e o preditor tem a forma

.

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

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

A expressão acima requer o armazenamento de todos os dados para atualização de . A complexidade de tempo total para a recursão ao avaliar para o -ésimo ponto de dados é , em que é o custo de avaliar o núcleo em um único par de pontos.L. Rosasco, T. Poggio, Machine Learning: a Regularization Approach, MIT-9.520 Lectures Notes, Manuscript, Dec. 2015. Chapter 7 - Online Learning Assim, o uso do núcleo permitiu o movimento de um espaço de parâmetros de dimensão finita a um feature de dimensão possivelmente infinita representado por um núcleo , executando a recursão no espaço de parâmetros , 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

O aprendiz recebe informações O aprendiz retorna de um conjunto convexo fixo A natureza envia de volta uma função de perda convexa . O aprendiz incorre uma perda 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 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 , e a natureza envia de volta a função de perda convexa . Observe que é implicitamente enviado com .

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 por: