Correcting Split Selection in Online Decision Trees via Anytime-Valid Inference

Resumo Técnico: Corrigindo a Seleção de Divisões em Árvores de Decisão Online via Inferência Válida a Qualquer Momento

1. Definição do Problema

O artigo aborda uma falha estatística fundamental nas Árvores de Hoeffding (HT), o aprendiz base padrão para métodos de ensemble em aprendizado de fluxo de dados (ex: Florestas Aleatórias Adaptativas). Embora as HTs tenham alcançado sucesso empírico ao crescer árvores incrementalmente usando desigualdades de concentração (como as de Hoeffding ou McDiarmid) para determinar quando uma divisão é estatisticamente significativa, suas garantias teóricas são inválidas na prática.

O problema central é o problema da parada opcional (optional stopping problem). As desigualdades de concentração padrão assumem um tamanho de amostra fixo. No entanto, as HTs empregam uma regra de parada dependente dos dados: elas monitoram continuamente estimativas de impureza e comprometem-se com uma divisão na primeira vez que um limiar é ultrapassado. Essa "continuação opcional" invalida os limites de tempo fixo, potencialmente inflando a probabilidade de divisões falsas para um. Além disso, as correções existentes frequentemente assumem dados independentes e estacionários, enquanto as HTs são frequentemente implantadas em fluxos não estacionários e dependentes dentro de estruturas de ensemble.

2. Metodologia

Os autores propõem uma alternativa fundamentada baseada em Inferência Segura e Válida a Qualquer Momento (SAVI - Safe, Anytime-Valid Inference), especificamente utilizando Teste por Apostas (Testing by Betting) e Sequências de Confiança (CS - Confidence Sequences).

• Reenquadramento da Seleção de Divisão: Em vez de comparar divisões candidatas entre si para encontrar o ótimo global (que pode ser mal definido em configurações não estacionárias), o método enquadra a seleção de divisão como uma comparação de modelos online. Ele testa se um modelo "desafiante" (uma divisão de folha de acordo com um candidato) supera demonstravelmente o modelo "incumbente" (a folha não dividida) com base nos dados observados.
• Funções de Perda: O desempenho preditivo é avaliado usando funções de perda limitadas (ex: log loss ou Brier score), servindo como análogos à entropia e impureza de Gini.
• Teste de Hipótese:
  • Nula Forte ($H_0$): O desafiante nunca supera o incumbente em nenhum momento ($\delta_t \le 0$).
  • Nula Fraca ($H_{w,0}$): O desafiante não supera o incumbente em média ao longo do tempo.
  • O artigo adota principalmente a Nula Forte, alinhando-se às recomendações para comparar algoritmos intimamente relacionados nos mesmos dados de fluxo.
• Mecanismos de Teste:
  1. Teste Baseado em Apostas (AVTB): Interpreta o teste de hipótese como um jogo de apostas. Um apostador aposta no sinal da diferença de perda ($\Delta_t$). Sob a nulidade, nenhuma estratégia produz crescimento esperado positivo. O método utiliza uma estratégia de Portfólio Universal (UP - Universal Portfolio) com uma priori de Jeffreys para atualizar a riqueza ($W_t$). Se $W_t$ exceder $1/\alpha$, a nulidade é rejeitada e a divisão é comprometida. Este processo é um supermartingal não negativo, garantindo validade sob tempos de parada arbitrários via desigualdade de Ville.
  2. Teste de Sequência de Confiança (AVTCS): Utiliza sequências de confiança de Bernstein empíricas para testar a nulidade fraca. O tempo de parada é definido quando o limite inferior da sequência de confiança para a vantagem média excede zero.
• Controle de Erro Global: Para lidar com o número potencialmente infinito de divisões candidatas geradas ao longo do tempo, os autores alocam níveis de significância ($\alpha_{v,c}$) entre todos os testes de modo que sua soma seja limitada por um $\alpha$ global. Isso garante que a probabilidade de qualquer divisão falsa ocorrer durante a vida útil da árvore seja, no máximo, $\alpha$.

3. Principais Contribuições

1. Critério de Divisão Válido: Derivação de um critério de divisão que permanece estatisticamente válido sob regras de parada arbitrárias dependentes de dados, aplicável tanto a fluxos de dados não estacionários quanto dependentes.
2. Comprometimento Finito: Prova de que, se uma divisão candidata exibe uma vantagem preditiva persistente, o procedimento compromete a divisão em tempo finito com uma taxa de $\tilde{O}(\log(1/\alpha)/\Delta^2)$.
3. Redução Monotônica de Risco: Sob dados i.i.d. estacionários, mostra-se que a perda preditiva esperada da árvore implantada é não crescente ao longo do tempo e melhora estritamente a cada compromisso de divisão.
4. Substituição Direta (Drop-in Replacement): O método serve como uma substituição direta para as Árvores de Hoeffding dentro de estruturas de ensemble existentes, como as Florestas Aleatórias Adaptativas (ARF), criando uma "Floresta Válida a Qualquer Momento" (AVF - Anytime-Valid Forest).

4. Resultados Experimentais

Os autores avaliaram seu método (AVT) e sua variante de ensemble (AVF) em 12 fluxos de dados do mundo real (6 regressão, 6 classificação) e benchmarks sintéticos.

• Desempenho:
  • Estabilidade: Ao contrário das Árvores de Hoeffding padrão, que exibiram quedas repetidas e abruptas no desempenho de generalização mesmo em dados estacionários, os métodos válidos a qualquer momento mostraram melhoria estável e monótona.
  • Acurácia: O AVTB (baseado em apostas) geralmente superou a HT padrão e foi competitivo ou superior à linha de base ARF em vários fluxos. O ensemble AVF superou consistentemente a ARF padrão em quase todos os conjuntos de dados.
  • Tamanho do Modelo: Os métodos propostos produziram árvores substancialmente menores (menos nós/folhas) em comparação com HT e ARF, mantendo desempenho preditivo igual ou superior.
• Custo Computacional:
  • O tempo de inferência permaneceu comparável ao da HT.
  • Os tempos de atualização foram maiores devido à manutenção de estatísticas de desafiantes de sombra e cálculos de riqueza, mas permaneceram dentro de limites práticos (milissegundos por instância).
  • Os autores observam que o AVF frequentemente aprende árvores mais rasas, reduzindo o número de nós que requerem atualizações, o que mitiga o overhead computacional.

5. Significância e Alegações

O artigo afirma resolver uma "limitação fundamental" dos métodos existentes de árvores de decisão online. Ao abandonar desigualdades de tamanho de amostra fixo em favor da inferência válida a qualquer momento, os autores fornecem garantias estatísticas que se mantêm sob as mesmas condições (parada dependente de dados, não estacionariedade) onde os métodos anteriores falham.

A significância reside em:

• Rigor Teórico: Fornecer as primeiras garantias estatísticas válidas para a seleção de divisão em árvores online sob parada opcional.
• Robustez Prática: Demonstrar que a validade estatística se traduz em estabilidade empírica, evitando o "colapso" de desempenho visto nas HTs padrão.
• Eficiência: Alcançar melhor desempenho preditivo com modelos mais parcos e menores, sugerindo que o "ruído" introduzido por decisões de divisão inválidas nas HTs padrão leva ao crescimento desnecessário da árvore.

Os autores concluem que seu framework serve como uma substituição robusta e direta para as Árvores de Hoeffding, corrigindo efetivamente a fundação estatística de um dos algoritmos mais amplamente utilizados na mineração de fluxos de dados.