Aprendizado de máquina online - Online machine learning

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 é usado 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 por aprendizado em 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 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 do preço das ações . Algoritmos de aprendizagem online podem estar sujeitos a interferências catastróficas , um problema que pode ser resolvido por abordagens de aprendizagem incrementais .

Introdução

No cenário de aprendizagem supervisionada , uma função de está a ser aprendida, onde é pensada como um espaço de entradas e como um espaço de saídas, que prevê bem as instâncias que são extraídas de uma distribuição de probabilidade conjunta em . Na realidade, o aluno nunca sabe a verdadeira distribuição nas instâncias. Em vez disso, o aluno geralmente tem acesso a um conjunto de exemplos de treinamento . Nesse cenário, a função de perda é dada como , de 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 denominado espaço de hipóteses, de forma que alguma noção de perda total seja minimizada. Dependendo do tipo de modelo (estatístico ou contraditório), podem-se conceber diferentes noções de perda, que levam a diferentes algoritmos de aprendizagem.

Visão estatística da aprendizagem online

Em modelos de aprendizagem estatística, a amostra de treinamento é assumida como tendo sido extraída da distribuição verdadeira e o objetivo é minimizar o "risco" esperado

Um paradigma comum nesta situação é estimar uma função por meio da minimização do risco empírico ou minimização do risco empírico regularizado (geralmente regularização de Tikhonov ). A escolha da função de perda aqui dá origem a vários algoritmos de aprendizagem bem conhecidos, 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 normalmente têm requisitos de armazenamento independentes do tamanho dos dados de treinamento). Para muitas formulações, por exemplo , métodos de kernel não lineares , o verdadeiro aprendizado online não é possível, embora uma forma de aprendizado online híbrido com algoritmos recursivos possa ser usado onde é permitido depender de todos os pontos de dados anteriores . Nesse caso, os requisitos de espaço não são mais garantidos como constantes, uma vez que requer o armazenamento de todos os pontos de dados anteriores, mas a solução pode levar menos tempo para calcular 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 usando minilotes, que processam um pequeno lote de pontos de dados por vez. Isso pode ser considerado um aprendizado pseudo-online para muito menor do que o número total de pontos de treinamento. As técnicas de minilote são usadas com passagens repetidas sobre os dados de treinamento para obter versões out-of-core otimizadas de algoritmos de aprendizado de máquina, por exemplo, descida gradiente estocástica . Quando combinado com retropropagação , este é atualmente o método de treinamento de fato para o treinamento de redes neurais artificiais .

Exemplo: mínimos quadrados lineares

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

Aprendizagem em lote

Considere a configuração da aprendizagem supervisionada como sendo uma função linear a ser aprendida:

onde é um vetor de entradas (pontos de dados) e é um vetor de filtro linear. O objetivo é calcular o vetor do filtro . Para este fim, uma função de perda quadrada

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

Onde

.

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

.

Agora, o cálculo da matriz de covariância leva tempo , a inversão da matriz leva tempo , enquanto o resto da multiplicação leva tempo , dando um tempo total de . Quando houver pontos totais no conjunto de dados, para recomputar a solução após a chegada de cada ponto de dados , a abordagem ingênua terá uma complexidade total . Note que ao armazenar a matriz , para então atualizá-la a cada passo é necessário apenas adicionar , o que leva tempo, reduzindo o tempo total para , mas com um espaço de armazenamento adicional de para armazenar .

Aprendizagem online: mínimos quadrados recursivos

O algoritmo de mínimos quadrados recursivos (RLS) considera uma abordagem online para o problema de mínimos quadrados. Pode-se mostrar que, ao inicializar e , a solução do problema dos mínimos quadrados lineares dado na seção anterior pode ser calculada pela seguinte iteração:

O algoritmo de iteração acima pode ser provado usando a indução ativada . A prova também mostra isso . Pode-se observar o RLS também no contexto dos filtros adaptativos (consulte RLS ).

A complexidade para as etapas desse algoritmo é , que é uma ordem de magnitude mais rápida do que a complexidade de aprendizagem em lote correspondente. Os requisitos de armazenamento em cada etapa aqui são armazenar a matriz , que é constante em . Para o caso em que não é invertível, considere a versão regularizada da função de perda de problemas . Então, é fácil mostrar que o mesmo algoritmo funciona , e as iterações passam a dar .

Descida gradiente estocástica

Quando isso

é substituído por

ou por , torna-se o algoritmo de descida gradiente estocástico. Nesse caso, a complexidade das etapas desse algoritmo se reduz a . Os requisitos de armazenamento em cada etapa são constantes em .

No entanto, o tamanho da etapa precisa ser escolhido com cuidado para resolver o problema de minimização de risco esperado, conforme detalhado acima. Ao escolher um tamanho de degrau decadente, pode-se provar a convergência da iteração média . Essa configuração é um caso especial de otimização estocástica , um problema bem conhecido em otimização.

Descida gradiente estocástico incremental

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

A principal diferença com o método do gradiente estocástico é que aqui uma sequência é escolhida para decidir qual ponto de treinamento é visitado na -ésima etapa. Essa sequência pode ser estocástica ou determinística. O número de iterações é então desacoplado para o número de pontos (cada ponto pode ser considerado mais de uma vez). O método do gradiente incremental pode ser mostrado para fornecer um minimizador para o risco empírico. As 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 kernel

Kernels podem ser usados ​​para estender os algoritmos acima para modelos não paramétricos (ou modelos onde os parâmetros formam um espaço dimensional infinito). O procedimento correspondente não estará mais verdadeiramente online e, em vez disso, envolverá o armazenamento de todos os pontos de dados, mas ainda é mais rápido do que o método de força bruta. Esta discussão é restrita ao caso da perda quadrada, embora possa ser estendida a qualquer perda convexa. Pode ser mostrado por uma indução fácil que se é a matriz de dados e é a saída após as etapas do algoritmo SGD, então,

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

e

Observe que aqui está apenas o Kernel padrão ativado e o preditor tem a forma

.

Agora, se um kernel geral é introduzido em vez disso e deixe o preditor ser

então a mesma prova também mostrará que o preditor que minimiza a perda de mínimos quadrados é obtido alterando a recursão acima para

A expressão acima requer o armazenamento de todos os dados para atualização . A complexidade de tempo total para a recursão ao avaliar para o -ésimo ponto de dados é , onde é o custo de avaliar o kernel em um único par de pontos. Assim, o uso do kernel permitiu o movimento de um espaço de parâmetro dimensional finito para um recurso dimensional possivelmente infinito representado por um kernel, em vez de realizar 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 representador .

Otimização convexa online

A otimização convexa online (OCO) é uma estrutura geral para tomada de decisão que alavanca a otimização convexa para permitir algoritmos eficientes. A estrutura é a de jogos repetidos da seguinte maneira:

Para

  • O aluno recebe informações
  • Resultados do aluno a partir de um conjunto convexo fixo
  • A natureza envia de volta uma função de perda convexa .
  • O aluno sofre perda e atualiza seu modelo

O objetivo é minimizar o arrependimento , ou 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 aqui que é enviado implicitamente com .

Alguns problemas de previsão online, entretanto, não se enquadram 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 substituta.

Alguns algoritmos de otimização convexa on-line simples são:

Siga o líder (FTL)

A regra de aprendizado mais simples a se tentar é selecionar (na etapa atual) a hipótese que apresenta a menor perda em todas as rodadas anteriores. Esse algoritmo é chamado de Seguir o líder e é simplesmente distribuído por:

Este método pode, portanto, ser visto como um algoritmo ganancioso . Para o caso de otimização quadrática online (onde está a função de perda ), pode-se mostrar um limite de arrependimento que cresce conforme . No entanto, limites semelhantes não podem ser obtidos para o algoritmo FTL para outras famílias importantes de modelos, como a 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 de FTL que é usada para estabilizar as soluções de FTL e obter melhores limites de arrependimento. Uma função de regularização é escolhida e a aprendizagem realizada na rodada t da seguinte forma:

Como um exemplo especial, considere o caso da otimização linear online, isto é, onde a natureza envia de volta funções de perda do formulário . Além disso, deixe . Suponha que a função de regularização seja escolhida para algum número positivo . Então, pode-se mostrar que o arrependimento de minimizar a iteração torna-se

Observe que isso pode ser reescrito como , que se parece exatamente com a descida gradiente online.

Se S for, em vez disso, algum subespaço convexo de , S precisaria ser projetado, levando à regra de atualização modificada

Esse algoritmo é conhecido como projeção preguiçosa, pois o vetor acumula os gradientes. É também conhecido como algoritmo de média dupla de Nesterov. Nesse cenário de funções de perda linear e regularização quadrática, o arrependimento é limitado por e, portanto, o arrependimento médio vai para 0 conforme desejado.

Descida de subgradiente online (OSD)

O exposto acima provou ser um limite de pesar para funções de perda linear . Para generalizar o algoritmo para qualquer função de perda convexa, o subgradiente de é usado como uma aproximação linear para próximo , levando ao algoritmo de descida do subgradiente online:

Parâmetro de inicialização

Para

  • Prever usando , receber da natureza.
  • Escolher
  • Se , atualize como
  • Se , projete gradientes cumulativos em ie

Pode-se usar o algoritmo OSD para derivar limites de arrependimento para a versão online do SVM para classificação, que usa a perda de dobradiça

Outros algoritmos

Algoritmos FTRL quadraticamente regularizados levam a algoritmos gradientes projetados lentamente, conforme descrito acima. Para usar o acima para funções convexas arbitrárias e regularizadores, usa-se a descida de 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 , que pode ser melhorado ainda mais para a para funções de perda fortemente convexa e exp-côncava.

Aprendizagem Contínua

Aprendizagem contínua significa melhorar constantemente o modelo aprendido, processando fluxos contínuos de informações. Capacidades de aprendizado contínuo são essenciais para sistemas de software e agentes autônomos interagindo em um mundo real em constante mudança. No entanto, o aprendizado contínuo é um desafio para o aprendizado de máquina e modelos de rede neural, uma vez que a aquisição contínua de informações incrementalmente disponíveis a partir de distribuições de dados não estacionárias geralmente leva ao esquecimento catastrófico .

Interpretações de aprendizagem 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 . O algoritmo de descida gradiente estocástico prototípico é usado para esta discussão. Conforme observado acima, sua recursão é dada por

A primeira interpretação considera o método de descida gradiente estocástico aplicado ao problema de minimização do risco esperado definido acima. De fato, no caso de um fluxo infinito de dados, uma vez que os exemplos são assumidos como tirados iid da distribuição , a sequência de gradientes da iteração acima é uma amostra iid de estimativas estocásticas do gradiente do risco esperado e, portanto, pode-se aplicar resultados de complexidade para o método de descida gradiente estocástico para limitar o desvio , onde é o minimizador de . Essa interpretação também é válida no caso de um conjunto de treinamento finito; embora com várias passagens pelos dados os gradientes não sejam mais independentes, ainda assim os resultados da complexidade podem ser obtidos em casos especiais.

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

Uma vez que os gradientes de nas iterações de descida de gradiente incremental também são estimativas estocásticas do gradiente de , essa interpretação também está relacionada ao método de descida de gradiente estocástico, mas aplicada para minimizar o 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 estreitos nos desvios , onde está o minimizador de .

Implementações

Veja também

Paradigmas de aprendizagem

Algoritmos gerais

Modelos de aprendizagem

Referências

  1. ^ a b c d e f g L. Rosasco, T. Poggio, Machine Learning: a Regularization Approach, MIT-9.520 Lectures Notes, Manuscrito, dezembro de 2015. Capítulo 7 - Aprendizagem Online
  2. ^ Yin, Harold J. Kushner, G. George (2003). Aproximação estocástica e algoritmos recursivos e aplicações (segunda edição). Nova York: Springer. pp.  8 -12. ISBN 978-0-387-21769-7.
  3. ^ a b Bertsekas, DP (2011). Gradiente incremental, subgradiente e métodos proximais para otimização convexa: um levantamento. Otimização para aprendizado de máquina, 85.
  4. ^ Hazan, Elad (2015). Introdução à Otimização Convexa Online (PDF) . Fundamentos e tendências em otimização.
  5. ^ Parisi, alemão I .; Kemker, Ronald; Parte, Jose L .; Kanan, Christopher; Wermter, Stefan (2019). "Aprendizagem contínua ao longo da vida com redes neurais: uma revisão" . Redes Neurais . 113 : 54–71. arXiv : 1802.07569 . doi : 10.1016 / j.neunet.2019.01.012 . ISSN  0893-6080 .
  6. ^ Bottou, Léon (1998). “Algoritmos Online e Aproximações Estocásticas”. Aprendizagem online e redes neurais . Cambridge University Press. ISBN 978-0-521-65263-6.
  7. ^ Stochastic Approximation Algorithms and Applications , Harold J. Kushner e G. George Yin, Nova York: Springer-Verlag, 1997. ISBN  0-387-94916-X ; 2ª ed., Intitulada Stochastic Approximation and Recursive Algorithms and Applications , 2003, ISBN  0-387-00894-2 .

links externos