On Imbalanced Regression with Hoeffding Trees

Este artigo estende a estimação por densidade de kernel (KDE) para configurações de streaming e integra o encolhimento hierárquico (HS) em árvores de decisão incrementais para regressão desbalanceada, demonstrando empiricamente que a KDE melhora consistentemente o desempenho inicial, enquanto o HS oferece ganhos limitados.

O essencial

Imagine que você é um chef de cozinha tentando prever o sabor de um prato que está sendo cozido em tempo real, enquanto os ingredientes chegam em uma esteira rolante infinita. Esse é o cenário do aprendizado online (ou streaming): dados que nunca param de chegar.

O problema é que, na vida real, alguns ingredientes são raros (como açafrão ou trufas), enquanto outros são comuns (como sal e água). Na ciência de dados, isso se chama desequilíbrio de dados. Se o seu "chef" (o algoritmo) só aprendeu com sal, ele vai ter muita dificuldade em prever o sabor quando a trufa aparecer.

Este artigo de pesquisa é como um manual para melhorar esse chef, usando duas técnicas novas para lidar com essa escassez de ingredientes raros. Vamos entender como eles fizeram isso:

1. O Chef: Árvores de Hoeffding

O "chef" principal que eles estão usando é chamado de Árvore de Hoeffding. Pense nele como um árbitro de futebol muito rápido.

• Em vez de esperar o jogo todo terminar para decidir quem ganhou (o que seria lento demais para dados em tempo real), ele faz uma decisão baseada nos primeiros minutos do jogo.
• Ele usa uma regra matemática (a desigualdade de Hoeffding) para dizer: "Ok, já vi o suficiente para saber que este jogador é melhor que aquele, vou tomar uma decisão agora".
• Isso é ótimo para velocidade, mas ele pode ser um pouco "rude" e errar quando vê algo muito incomum (como a trufa rara).

2. A Técnica 1: O "Suavizador" (KDE)

A primeira melhoria que eles adicionaram é chamada de Estimativa de Densidade de Kernel (KDE).

• A Analogia: Imagine que você está tentando adivinhar a temperatura de amanhã. Se você olhar apenas para o termômetro de hoje, pode errar. Mas, se você olhar para uma "nuvem" de temperaturas dos últimos dias ao redor de hoje, você terá uma ideia mais suave e precisa.
• Como funciona no papel: Quando o algoritmo vê um dado raro (como um valor de temperatura extremo), ele não olha apenas para aquele ponto isolado. Ele olha para os vizinhos próximos e cria uma "nuvem" de probabilidade. Isso ajuda o modelo a não se assustar com valores estranhos e a prever melhor os casos raros.
• O Resultado: Os autores chamaram isso de "telescópio" (telescoping), porque eles conseguem atualizar essa "nuvem" de informação a cada novo dado que chega, sem precisar guardar tudo na memória.
• Veredito: Foi um sucesso! O "suavizador" (KDE) ajudou muito o chef a prever os ingredientes raros com mais precisão, especialmente no início do processo.

3. A Técnica 2: O "Freio de Segurança" (Hierarchical Shrinkage)

A segunda melhoria é a Encolhimento Hierárquico (HS).

• A Analogia: Imagine que o chef tem uma receita complexa com 100 passos. Às vezes, ele exagera e coloca muito tempero em um passo específico, estragando o prato. O "Encolhimento Hierárquico" é como um ajudante de cozinha que segura a mão do chef.
• Ele diz: "Ei, você não precisa ser tão radical nesse passo. Vamos reduzir um pouco a influência desse ingrediente e confiar mais na média geral". Ele suaviza as decisões extremas do modelo.
• O Resultado: Surpreendentemente, essa técnica não ajudou muito. O artigo diz que ela deu ganhos mínimos. Parece que, para esse tipo de problema (dados em fluxo contínuo), o "freio de segurança" não era necessário ou não funcionou tão bem quanto o "suavizador".

O Grande Experimento

Os pesquisadores testaram isso em várias situações do mundo real, como:

• Prever o preço de casas na Califórnia.
• Estimar o tamanho de táxis em Nova York.
• Medir a espessura de filmes finos em semicondutores (tecnologia).

Eles usaram dois "laboratórios" de código (bibliotecas Python chamadas scikit-multiflow e River) para rodar esses testes.

Conclusão Simples

O que eles descobriram?

1. O "Suavizador" (KDE) é o herói: Ele transformou o chef comum em um mestre, especialmente quando os dados são desbalanceados (quando temos poucos exemplos de algo importante). Ele ajuda o modelo a não ignorar os casos raros.
2. O "Freio" (HS) é apenas um coadjuvante: Ele não fez muita diferença nesse cenário específico.
3. O Futuro: Agora, qualquer pessoa pode usar esse código (que eles disponibilizaram gratuitamente) para melhorar seus próprios sistemas de previsão em tempo real, desde prever o preço de energia até detectar fraudes.

Em resumo: Para prever o futuro em uma esteira rolante de dados, não basta apenas olhar para o que está acontecendo agora; você precisa olhar para a "nuvem" de dados ao redor para entender o contexto, especialmente quando os eventos importantes são raros. O artigo nos ensinou como fazer exatamente isso.

Resumo técnico

1. Problema Investigado

O artigo aborda o desafio de realizar regressão em fluxos de dados (data streams) quando os dados apresentam desequilíbrio (imbalanced data).

• Contexto: Muitos aplicativos do mundo real (como previsão de preços de energia, detecção de fraudes e monitoramento climático) geram dados contínuos que exigem aprendizado online.
• Desafio Específico: Enquanto o desequilíbrio de dados é amplamente estudado em classificação (onde certas classes são raras), ele também ocorre em regressão, onde certos intervalos de valores-alvo são muito menos frequentes que outros.
• Limitação Atual: Técnicas avançadas de aprendizado em lote (batch), como Kernel Density Estimation (KDE) para suavização de previsões e Hierarchical Shrinkage (HS) para regularização, não foram adaptadas para algoritmos de árvores de decisão incrementais (como Árvores de Hoeffding) que operam em tempo real sobre fluxos de dados.

2. Metodologia

Os autores propõem uma integração de técnicas de aprendizado em lote com algoritmos de árvores de decisão incrementais (Hoeffding Trees - HT e Hoeffding Adaptive Trees - HAT).

• Estimativa de Densidade de Kernel (KDE) Adaptada para Streaming:

  • O KDE é utilizado para suavizar as previsões, tratando a distribuição desequilibrada dos rótulos.
  • Para torná-lo viável em fluxos de dados, os autores desenvolveram uma formulação telescópica (telescoping formulation). Isso permite atualizar a estimativa de densidade incrementalmente, usando apenas a média anterior e a nova observação, sem precisar reprocessar todo o histórico.
  • Utiliza-se um tumbling window (janela deslizante) para manter as estatísticas locais e binarização (binning) dos valores-alvo.

• Encolhimento Hierárquico (Hierarchical Shrinkage - HS):

  • Técnica de regularização pós-hoc que não altera a estrutura da árvore.
  • Modifica a previsão final ponderando a contribuição de cada nó no caminho da raiz até a folha, com base no número de amostras em cada nó e um hiperparâmetro de regularização ($\lambda$).
  • Foi integrado às árvores incrementais, mantendo as estatísticas necessárias durante o fluxo de dados.

• Processo de Aprendizado e Sintonização (Tuning):

  • Utiliza uma variação do algoritmo Follow-the-Leader (FTL) para ajuste de hiperparâmetros online.
  • O sistema alterna entre fases de treinamento e fases de sintonização, onde múltiplos modelos (com diferentes combinações de parâmetros de KDE, HS, tamanho de janela e kernel) são executados em paralelo para selecionar o melhor desempenho cumulativo.

• Implementação:

  • Os experimentos foram realizados utilizando as bibliotecas Python scikit-multiflow e River.
  • Foram testados modelos base: HT e HAT (scikit-multiflow), além de iSOUP e SGT (River).

3. Principais Contribuições

1. Implementação de HS em Árvores Incrementais: Primeira integração conhecida do Hierarchical Shrinkage em árvores de decisão incrementais para fluxos de dados, avaliando seu impacto na precisão preditiva.
2. Adaptação do KDE para Streaming: Revisão e adaptação do KDE para algoritmos de mineração de fluxos, permitindo a suavização de distribuições desequilibradas em tempo real através de atualizações incrementais eficientes.
3. Avaliação Empírica Abrangente: Teste das técnicas combinadas (KDE e HS) em benchmarks padrão de regressão online, demonstrando que o KDE melhora consistentemente o desempenho, enquanto o HS oferece ganhos limitados.
4. Código Aberto: Disponibilização pública da implementação para reprodutibilidade e uso pela comunidade.

4. Resultados Experimentais

Os experimentos foram conduzidos em cinco conjuntos de dados (Abalone, California Housing, NY Taxi, Electric Power Consumption e Film Thickness).

• Desempenho do KDE:

  • O KDE demonstrou melhoria consistente no desempenho, especialmente no início do fluxo de dados (early-stream performance).
  • Em 18 de 24 casos (medido por RMSE) e 15 de 24 casos (medido por WRMSE - Weighted RMSE), os modelos aprimorados com KDE superaram os modelos base.
  • A melhoria foi particularmente notável em métricas ponderadas (WRMSE), que penalizam erros em regiões raras da distribuição.

• Desempenho do HS:

  • O Hierarchical Shrinkage forneceu ganhos mínimos ou insignificantes na maioria dos casos.
  • Em alguns cenários, a combinação de KDE + HS não superou o uso isolado do KDE.

• Comparação entre Bibliotecas:

  • Resultados similares foram observados tanto na biblioteca scikit-multiflow quanto na River, validando a generalidade da abordagem KDE em diferentes implementações de árvores de Hoeffding (incluindo iSOUP e SGT).

• Métricas:

  • Foram utilizados MAE, RMSE, WRMSE e $R^2$. O WRMSE foi crucial para evidenciar a capacidade do modelo de lidar com a cauda da distribuição (valores raros).

5. Significado e Conclusões

• Eficácia da Suavização: O estudo conclui que, para regressão em fluxos de dados desequilibrados, a suavização baseada em KDE é uma ferramenta poderosa e eficaz para melhorar a precisão das previsões, superando a necessidade de técnicas mais complexas de reamostragem (como SMOTE) que podem ser difíceis de aplicar incrementalmente.
• Limitação da Regularização HS: A técnica de Hierarchical Shrinkage, embora promissora em aprendizado em lote, não trouxe benefícios significativos no contexto de árvores incrementais para regressão desequilibrada neste estudo.
• Futuro: Os autores sugerem que os benefícios observados podem se estender a ensembles baseados em árvores (como Random Forests online). Eles também destacam que o foco deste trabalho não foi em concept drift (mudança de conceito), sugerindo que a combinação de drift, dados desequilibrados e KDE é uma direção promissora para pesquisas futuras.

Em resumo, o artigo demonstra que adaptar técnicas de suavização de densidade (KDE) para o contexto de aprendizado online é uma estratégia viável e superior para lidar com o desequilíbrio em problemas de regressão contínua, enquanto a regularização estrutural (HS) tem impacto limitado neste cenário específico.