Skip to content
Voltar aos resultados

Online Boosting

Proposto por
Oza, N. C. & Russell, S.
Ano
2001
Tipo
Online ensemble (incremental boosting)
Família
Machine learning

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

Online Boosting adapta o framework clássico de boosting a fluxos de dados, atualizando um ensemble de aprendizes fracos um exemplo de cada vez, sem armazenar o conjunto de dados completo.

A formulação Oza-Russell aproxima a reponderação do AdaBoost usando contagens de instâncias amostradas por Poisson, permitindo classificação adaptativa e precisa em tempo real ou em ambientes com recursos limitados.

A intuição por trás do método

O boosting em lote repondera exemplos de treinamento para forçar aprendizes sucessivos a corrigir os erros uns dos outros, mas isso requer a visualização de todos os dados de uma vez. O Online Boosting substitui a reponderação explícita por um truque de amostragem de Poisson: cada exemplo que chega é passado para uma cadeia de aprendizes fracos, e o número de vezes que cada aprendiz o vê (seu peso efetivo) é extraído de uma distribuição de Poisson cuja taxa aumenta quando o aprendiz anterior errou o exemplo e diminui quando acertou. O resultado imita de perto a dinâmica de correção do AdaBoost sem nunca reproduzir dados passados.

História

O Online Boosting foi formalizado por Nikunj Oza e Stuart Russell em seu artigo de 2001 'Online Bagging and Boosting', que mostrou que o truque de amostragem de Poisson fornece uma aproximação estatisticamente sólida ao AdaBoost em lote no cenário de streaming. O trabalho se baseou no AdaBoost de Freund e Schapire (1997) e no bagging de Breiman (1996). Pesquisas subsequentes estenderam a abordagem para lidar com desvio de conceito, problemas multiclasse e aprendizado sensível a custo, cimentando o Online Boosting como uma ferramenta padrão na literatura de mineração de fluxos de dados.

Quando usar

Use Online Boosting quando os dados chegam como um fluxo contínuo e o modelo deve ser atualizado incrementalmente sem revisitar exemplos anteriores — por exemplo, em detecção de fraude em tempo real, monitoramento de intrusão em rede, classificação baseada em sensores, ou qualquer cenário onde armazenar o conjunto de dados completo seja inviável. Ele supera aprendizes online únicos e o online bagging quando o fluxo tem desvio de conceito que se beneficia da reponderação adaptativa. Não o use quando o conjunto de dados for estático e couber na memória — o gradient boosting em lote (XGBoost, LightGBM) quase sempre produzirá maior precisão. Evite-o também quando o fluxo tiver desvio de conceito severo e abrupto, que pode exigir mecanismos explícitos de reinicialização de detecção de desvio que não estão embutidos no Online Boosting básico.

Limitações e considerações

  • Sensível a ruído de rótulo no fluxo, pois rótulos incorretos fazem a taxa de Poisson aumentar, amplificando erros em aprendizes subsequentes.
  • Não se recupera automaticamente de desvio de conceito abrupto, a menos que seja combinado com um mecanismo explícito de detecção de desvio.
  • Menor diversidade de aprendizes do que o boosting em lote, pois exemplos passados não podem ser reproduzidos para correção.
  • O tamanho do ensemble M é fixo na inicialização; adicionar ou remover aprendizes no meio do fluxo requer cuidado para evitar instabilidade.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Processa cada exemplo exatamente uma vez, tornando-o adequado para fluxos de dados de alta velocidade ou com restrição de memória.
  • Herda a forte propriedade de redução de viés do boosting, frequentemente superando o online bagging em tarefas de classificação difíceis.
  • A reponderação adaptativa permite que exemplos posteriores corrijam erros introduzidos por partes anteriores do fluxo.
  • Não é necessário ajuste de hiperparâmetros de pesos de amostra; a aproximação de Poisson é autorregulada.
  • Compatível com qualquer aprendiz fraco atualizável incrementalmente, proporcionando flexibilidade na escolha do modelo.

Aplicações

  • Detecção de fraude e anomalias em tempo real em fluxos de transações.
  • Detecção de intrusão em rede com dados de nível de pacote chegando continuamente.
  • Manutenção preditiva a partir de fluxos de sensores de alta frequência na manufatura.
  • Filtragem de spam por e-mail que se adapta incrementalmente às táticas de spam em evolução.
  • Previsão de taxa de cliques em plataformas de publicidade online.
  • Monitoramento médico onde dados do paciente chegam sequencialmente e as atualizações do modelo devem ser imediatas.

Como funciona

Como funciona

1

Uma sequência ordenada de M aprendizes fracos — tipicamente árvores de decisão rasas ou tocos — é inicializada com taxas de Poisson iguais. Cada aprendiz está associado a um peso alpha e a uma contagem contínua de predições ponderadas corretas e incorretas usadas para estimar sua contribuição.

2

Um novo exemplo rotulado chega do fluxo. Nenhum dado histórico é armazenado; o algoritmo o processa uma vez e segue em frente. Essa restrição de passagem única é a característica definidora que distingue o boosting online de seu contraparte em lote.

3

Para o primeiro aprendiz, a instância é replicada k vezes onde k é extraído de Poisson(1). Isso aproxima a amostragem com reposição como no bagging em lote. A taxa de Poisson lambda se propaga pela cadeia e atua como o peso efetivo da instância para cada aprendiz subsequente.

Fórmula
k \sim \text{Poisson}(\lambda),\; \lambda = 1 \text{ initially}
4

Cada aprendiz fraco atualiza seu modelo interno usando a instância replicada k vezes de acordo com a taxa de Poisson atual. Tocos de decisão, por exemplo, atualizam os limiares de divisão incrementalmente. O aprendiz então emite uma predição binária para o exemplo.

5

Se o aprendiz fraco atual classificou a instância corretamente, a taxa de Poisson passada para o próximo aprendiz é diminuída (reponderar casos tratados corretamente é desnecessário). Se incorreto, a taxa é aumentada para que o próximo aprendiz se concentre mais neste exemplo difícil. O peso de contribuição alpha do aprendiz é atualizado a partir de sua precisão cumulativa.

Fórmula
\lambda_{m+1} = \lambda_m \cdot \frac{e^{\pm \alpha_m}}{Z_m}
6

Para inferência, a predição final é o voto majoritário ponderado de todos os M aprendizes fracos, com cada voto escalado pelo alpha do aprendiz. Isso espelha a soma ponderada com sinal do AdaBoost, fornecendo uma confiança calibrada ao lado do rótulo da classe.

Fórmula
\hat{y} = \operatorname{sign}\!\left(\sum_{m=1}^{M} \alpha_m h_m(x)\right)

Erros comuns

  • Confundir online boosting com batch boosting e esperar precisão idêntica em conjuntos de dados estáticos — use métodos em lote quando puder.
  • Ignorar ruído de rótulo: um fluxo ruidoso degrada o Online Boosting mais rapidamente do que o Online Bagging, pois o boosting amplifica exemplos difíceis (possivelmente mal rotulados).
  • Escolher M (número de aprendizes fracos) muito pequeno e aceitar baixo desempenho sem ajuste.
  • Falhar em monitorar o desvio de conceito e continuar confiando em um modelo cujas suposições de distribuição mudaram.
  • Relatar apenas precisão instantânea em vez de avaliação prequencial (testar-then-train), o que pode mascarar a degradação.

Perguntas frequentes

Como o Online Boosting difere do AdaBoost em lote?

O AdaBoost em lote repondera exemplos de treinamento reescalonando suas probabilidades de amostragem em múltiplas passagens. O Online Boosting aproxima isso passando cada exemplo que chega por uma cadeia de aprendizes fracos e ajustando uma taxa de Poisson que controla quantas vezes cada aprendiz vê o exemplo, sem nunca armazenar ou reproduzir dados históricos.

Quantos aprendizes fracos M devo usar?

Um valor de M entre 10 e 50 é típico para tocos rasos ou árvores pequenas. Mais aprendizes reduzem o viés, mas aumentam a latência de inferência. Ajuste M usando avaliação prequencial em uma fatia de dados representativa antes de implantar.

O Online Boosting é robusto ao desvio de conceito?

O Online Boosting básico não detecta nem responde explicitamente ao desvio de conceito. Para fluxos com desvio, combine-o com um algoritmo de detecção de desvio como ADWIN ou DDM que aciona uma reinicialização parcial ou completa do ensemble quando o desvio é detectado.

Quando devo preferir Online Bagging ao Online Boosting?

Quando o fluxo contém ruído de rótulo significativo, o Online Bagging é mais robusto, pois não amplifica o impacto de exemplos difíceis (potencialmente mal rotulados) como o boosting faz. O Online Boosting é preferível quando o fluxo é relativamente limpo e você precisa de precisão máxima.

Posso avaliar um modelo de streaming sem um conjunto de teste separado?

Sim. Use avaliação prequencial (testar-then-train): preveja cada exemplo que chega antes de atualizar o modelo e acumule essas predições em uma precisão ou F1 contínua. Isso fornece uma estimativa de desempenho não enviesada sem a necessidade de dados retidos.

Métodos relacionados

Fontes

  1. Oza, N. C., & Russell, S. (2001). Online Bagging and Boosting. In Artificial Intelligence and Statistics 2001 (pp. 105–112). Morgan Kaufmann.

    Abrir referência da publicação
    Copiado.
  2. Online machine learning. Wikipedia.

    Abrir referência da publicação
    Copiado.