Bagging Online
- Proposto por
- Oza, N. C. & Russell, S.
- Ano
- 2001
- Tipo
- Online ensemble (streaming bagging)
- Família
- Machine learning
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
Bagging Online é um método de ensemble de streaming introduzido por Oza e Russell em 2001 que adapta o framework clássico de agregação de bootstrap (Bagging) para o cenário de aprendizado online.
Em vez de reamostrar um conjunto de dados fixo, cada instância de entrada é fornecida a cada aprendiz base um número de vezes distribuído por Poisson(1), aproximando fielmente a amostragem bootstrap à medida que o fluxo evolui. O resultado é um ensemble robusto e atualizado incrementalmente que pode lidar com desvio de conceito e chegada contínua de dados sem armazenar o conjunto de dados completo.
A intuição por trás do método
O Bagging Clássico extrai amostras bootstrap aleatórias de um conjunto de dados fixo e treina uma árvore por amostra. O Bagging Online imita isso sem nunca ver o conjunto de dados inteiro de uma vez: quando um novo exemplo chega, ele é passado para cada aprendiz base um número aleatório de vezes extraído de uma distribuição de Poisson com média 1. Em média, cada aprendiz vê o exemplo uma vez — exatamente o que o reamostragem bootstrap alcança em modo batch — mas a aleatoriedade descorrela os aprendizes. Como nenhum dado precisa ser armazenado, o ensemble pode crescer indefinidamente com o fluxo e se ajustar naturalmente a distribuições mutáveis ao longo do tempo.
História
O Bagging Online foi introduzido por Nitesh Oza e Stuart Russell na AISTATS 2001 como uma extensão teórica e prática do algoritmo Bagging de Breiman de 1996 para o cenário online. A ideia chave — substituir o reamostragem bootstrap por ponderação Poisson(1) por instância — tornou a aproximação matematicamente rigorosa. Tornou-se um algoritmo fundamental na literatura de aprendizado de máquina de streaming e é o ensemble de base em plataformas como MOA (Massive Online Analysis), que impulsionou a maioria das avaliações empíricas de classificadores de fluxo desde 2010.
Quando usar
Use Bagging Online quando os dados chegam como um fluxo contínuo e o armazenamento do conjunto de dados completo é inviável ou proibido (por exemplo, logs de sensores, clickstreams, dados de tick financeiro, monitoramento em tempo real). É apropriado quando você precisa de classificação ou regressão que se atualiza a cada nova observação, tolera desvio de conceito leve e permanece eficiente em memória. Não use Bagging Online como um substituto direto para Random Forest em batch em um conjunto de dados fixo, pequeno a médio — ensembles em batch com validação cruzada terão melhor desempenho nesses casos. Evite-o também quando o fluxo de dados exibe desvio abrupto severo sem adicionar um mecanismo explícito de detecção de desvio.
Limitações e considerações
- Em conjuntos de dados estáticos, métodos em batch como Random Forest ou XGBoost consistentemente superam o Bagging Online porque podem usar validação cruzada completa e divisões ótimas.
- O Bagging Online básico oferece apenas resiliência limitada a desvio de conceito severo; detectores de desvio dedicados (por exemplo, ADWIN) devem ser adicionados externamente.
- A ponderação de Poisson introduz variância extra por instância, o que pode desacelerar a convergência em fluxos curtos.
- A interpretabilidade é baixa: o ensemble de muitas árvores crescidas incrementalmente é mais difícil de inspecionar do que uma única árvore de decisão.
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 dados uma instância por vez com memória constante, permitindo fluxos verdadeiramente ilimitados.
- A ponderação de Poisson aproxima provadamente o reamostragem bootstrap, proporcionando redução de variância do ensemble comparável ao Bagging em batch.
- Naturalmente paralelizável: cada aprendiz base se atualiza independentemente, tornando-o adequado para arquiteturas de streaming distribuídas.
- Nenhum hiperparâmetro tão sensível quanto a profundidade da árvore — o ensemble se autorregula através da diversidade.
- Estende-se de forma direta para classificação multiclasse e regressão sem alterações estruturais.
Aplicações
- Detecção de fraude em tempo real em fluxos contínuos de transações.
- Manutenção preditiva a partir de fluxos de dados de sensores em cenários de IoT industrial.
- Previsão de taxa de cliques em publicidade online onde o comportamento do usuário evolui continuamente.
- Detecção de intrusão em rede em fluxos de pacotes de alta vazão.
- Monitoramento ambiental: classificação incremental de leituras de sensores de qualidade do ar ou clima.
Como funciona
Como funciona
Para cada instância que chega, um peso k é amostrado independentemente de uma distribuição Poisson(1) para cada aprendiz base. Um peso de 0 significa que o aprendiz ignora completamente esta instância; um peso de 2 significa que ele aprende com a instância duas vezes. Esta ponderação estocástica é o análogo online do reamostragem bootstrap e é o núcleo matemático do algoritmo.
Fórmula
k \sim \text{Poisson}(1)Cada aprendiz base — tipicamente uma árvore de decisão incremental como uma Árvore de Hoeffding — recebe a instância atual com seu peso atribuído e atualiza seu modelo interno imediatamente. Nenhuma instância é armazenada após o processamento. Esta propriedade de passagem única mantém a memória limitada e permite que o ensemble escale para fluxos arbitrariamente longos.
Quando uma previsão é necessária, todos os M aprendizes base produzem sua saída individual para a instância de consulta. O ensemble combina essas saídas por voto majoritário para classificação ou por média aritmética para regressão, dando a mesma lógica agregada do Bagging em batch, mas computada em modelos treinados incrementalmente.
Fórmula
\hat{y} = \text{mode/mean of } M \text{ base learners}Erros comuns
- Avaliar Bagging Online com um conjunto de teste retido criado antes do início do treinamento — use avaliação prequencial (testar-then-train) em vez disso, que é o padrão em aprendizado de máquina de streaming.
- Assumindo que o número padrão de aprendizes base (frequentemente 10) é suficiente; ensembles de pelo menos 50–100 aprendizes são tipicamente necessários para previsões estáveis.
- Ignorar o desvio de conceito: implantar Bagging Online em um fluxo com desvio sem detecção de desvio leva à degradação silenciosa da precisão.
- Comparar a precisão em um benchmark estático com métodos em batch e concluir que Bagging Online é inferior — a comparação correta é a precisão por instância vista em um benchmark de streaming.
- Usar aprendizes base que não são verdadeiramente incrementais (por exemplo, árvores em batch re-treinadas), o que nega as vantagens de memória e velocidade do framework online.
Perguntas frequentes
Por que especificamente Poisson(1)?
Uma distribuição de Poisson com média 1 aproxima o número de vezes que uma observação aparece em uma amostra bootstrap de tamanho n à medida que n se aproxima do infinito. Usar Poisson(1) por instância por aprendiz replica exatamente esse comportamento limite, tornando a aproximação online teoricamente sólida.
Como o Bagging Online difere do Adaptive Random Forest?
O Adaptive Random Forest (Gomes et al., 2017) estende o Bagging Online adicionando subamostragem aleatória de features em cada divisão (como Random Forest em batch) e integrando detectores de desvio por árvore que reiniciam aprendizes individuais quando o desvio de conceito é detectado. O Bagging Online é a base mais simples; o Adaptive Random Forest é o ensemble de streaming de ponta atual construído sobre ele.
Qual aprendiz base devo usar?
A escolha mais comum é a Árvore de Hoeffding (também chamada VFDT), que é a árvore de decisão incremental canônica. Ela usa limites de Hoeffding para decidir quando dados suficientes foram vistos em um nó para dividir, mantendo a árvore atualizável sem armazenar instâncias passadas.
Quantos aprendizes base preciso?
Benchmarks empíricos no framework MOA sugerem 50–100 aprendizes base para desempenho estável do ensemble na maioria das tarefas de streaming. Menos aprendizes reduzem o custo computacional, mas aumentam a variância da previsão, especialmente no início do fluxo.
Como devo avaliar um classificador Bagging Online?
Use avaliação prequencial: para cada instância que chega, primeiro preveja seu rótulo, depois atualize o modelo. A precisão é calculada como a média móvel de previsões corretas. Isso evita qualquer viés de look-ahead e reflete as condições reais de implantação.
Métodos relacionados
Fontes
Oza, N. C., & Russell, S. (2001). Online bagging and boosting. In Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics (AISTATS 2001), pp. 105–112.
Abrir referência da publicaçãoCopiado.Bifet, A., Holmes, G., Kirkby, R., & Pfahringer, B. (2010). MOA: Massive Online Analysis. Journal of Machine Learning Research, 11, 1601–1604.
Abrir referência da publicaçãoCopiado.