Árvores de Decisão em Tempo Real Usando Métodos de Monte Carlo

Árvores de Decisão são ferramentas importantes para fazer previsões em aprendizado de máquina interpretável. Elas são fáceis de entender e foram amplamente estudadas, principalmente usando conjuntos de dados fixos. Algoritmos comuns incluem C4.5, ID3 e CART. No entanto, esses algoritmos costumam depender de medidas locais para criar divisões nas árvores, o que pode levar a árvores complexas e difíceis de interpretar. Recentemente, alguns trabalhos tentaram melhorar essa suboptimalidade, mas não muito foi feito em casos onde os dados chegam em um fluxo em vez de um conjunto de dados completo.

Pra resolver esse problema, apresentamos um novo algoritmo que usa Monte Carlo Tree Search (MCTS) pra gerar Árvores de Decisão ótimas em tempo real à medida que os dados vão chegando. Também mostramos que nosso algoritmo continua a melhorar e a convergir em direção à melhor árvore possível. Além disso, fazemos experimentos extensivos pra dar suporte às nossas descobertas. Nosso algoritmo se sai melhor que os existentes em vários testes, oferecendo uma vantagem prática ao lidar com dados em streaming.

O aprendizado de máquina interpretável é especialmente importante em áreas sensíveis como a medicina, onde as decisões precisam ser explicadas e justificadas. Árvores de Decisão são preferidas nessas situações porque criam regras de decisão bem diretas. No entanto, encontrar a melhor Árvore de Decisão é uma tarefa complexa, por isso algoritmos de batch populares constroem árvores usando métodos gananciosos, dividindo ramos com base em métricas de ganho local. Isso pode resultar em árvores excessivamente complexas que derrotam o propósito da simplicidade.

No mundo de hoje, os dados costumam chegar continuamente em vez de em lotes fixos. Essa tendência tornou os algoritmos tradicionais de batch menos úteis, resultando no aumento de abordagens de aprendizado online. Métodos clássicos de Árvores de Decisão não se encaixam bem no aprendizado online, já que avaliam métricas de divisão com base em conjuntos de dados inteiros.

O algoritmo VFDT foi introduzido pra adaptar Árvores de Decisão ao aprendizado online. VFDT adota um teste estatístico baseado na desigualdade de Hoeffding pra estimar ganhos das divisões, fornecendo uma estrutura razoável. Apesar disso, muitos métodos online ainda enfrentam desafios relacionados à criação de árvores ótimas.

Neste trabalho, propomos uma solução pra contornar essas limitações existentes, fornecendo um algoritmo de Árvore de Decisão online ótimo. Focamos em tarefas de classificação com dados categóricos e trabalhamos pra equilibrar precisão e complexidade da árvore. Modelamos essa tarefa como um Processo de Decisão de Markov (MDP), onde encontrar a melhor política corresponde a construir a melhor Árvore de Decisão. Utilizamos Amostragem de Thompson dentro do MCTS, mostrando que nosso método converge em direção à melhor estratégia de tomada de decisão.

#Trabalho Relacionado

Estudos anteriores focaram em melhorar Árvores de Decisão em configurações controladas, principalmente através de programação matemática. Esses esforços geralmente otimizam divisões internas dentro de uma estrutura de árvore fixa. Enquanto essa abordagem torna o problema mais gerenciável, ela pode deixar de encontrar a árvore ótima completamente. Recentemente, métodos como branch and bound foram sugeridos pra abordar esse problema, levando a avanços como o algoritmo DL8.5. No entanto, esses métodos geralmente trabalham com dados binários, exigindo codificação inicial e possivelmente complicando o processo de solução.

A maioria dessas abordagens existe apenas em um contexto de aprendizado em batch e não se estende bem para configurações online. Outro estudo relacionado empregou MCTS, mas se baseou no algoritmo C4.5, que não é adequado para dados em streaming.

Nosso método adota uma abordagem diferente, aplicando amostragem de Thompson dentro do MCTS pra fornecer novas maneiras de explorar divisões e garantir a convergência em direção à árvore ótima. Reconhecemos que estabelecer resultados sólidos de convergência para métodos de Monte Carlo ainda é um desafio. No entanto, focamos nos aspectos únicos da nossa abordagem pra garantir resultados significativos.

#Formulação do Problema

Consideramos um cenário onde os dados chegam na forma de atributos categóricos com uma classe a ser prevista. As amostras chegam de forma incremental, e assumimos que seguem uma distribuição conjunta. Definimos uma Árvore de Decisão e seu conjunto associado de folhas. Dentro de cada folha, acompanhamos a probabilidade de certos eventos, permitindo que determinemos quão bem nosso modelo prevê os resultados.

Nosso objetivo é maximizar a precisão em relação às previsões enquanto minimizamos a complexidade da árvore. Criamos um objetivo regularizado que leva em conta esse trade-off, equilibrando desempenho com interpretabilidade.

#Processo de Decisão de Markov (MDP)

Desenvolvemos um MDP episódico pra modelar nosso problema. Os estados nesse modelo são representados por possíveis Árvores de Decisão, enquanto ações podem envolver dividir uma folha ou alcançar um estado terminal. A transição de uma ação para outra é determinística e simples, e nós definimos recompensas com base nos resultados das ações.

A política que derivamos mapeia estados não-terminais para distribuições sobre ações potenciais, nos permitindo identificar os melhores caminhos para árvores ótimas.

#Representação da Árvore do Espaço Estado-Ação

No MCTS, o espaço é frequentemente visualizado como uma árvore onde cada nó atua como um ponto de decisão. Esses nós refletem possíveis Árvores de Decisão, enquanto as arestas representam ações específicas tomadas pra chegar a essas árvores. O nó raiz começa com uma estrutura simples, e ao longo do nosso processo, expandimos explorando diferentes ramos.

Ao estimar valores em cada nó com base nos dados observados, criamos uma estrutura que nos permite retroceder e atualizar nosso modelo continuamente. No entanto, determinar quais nós explorar primeiro requer um equilíbrio entre exploração (encontrando novas informações) e exploração (usando conhecimento existente).

#Estimando Valores para Folhas de Busca

Criamos uma estrutura estatística pra estimar valores nas folhas da nossa árvore com base nos dados observados. Usando métodos bayesianos, definimos posteriors que ajudam a refinar nossas estimativas, permitindo um aprendizado colaborativo a partir dos vários nós na árvore.

Podemos também estender essa abordagem de estimativa para nós internos, o que nos permite deduzir recursivamente valores até o nó raiz. Usando aproximações estatísticas, podemos efetivamente retroceder e ajustar nosso modelo com base nos resultados que observamos.

#O Algoritmo

O algoritmo que propomos começa com uma estrutura de árvore inicial e expande iterativamente à medida que novos dados são observados. Durante cada iteração, selecionamos um caminho pela árvore com base em nossa política atual, simulamos resultados com os dados que chegam e atualizamos o modelo de acordo.

À medida que expandimos a árvore, acompanhamos todos os resultados observados, permitindo que refinem nossas estimativas de forma eficaz ao longo do tempo. Essa estrutura mantém a eficiência enquanto garante que nossa exploração de divisões e ações esteja orientada para alcançar um desempenho ótimo.

#Resultados Experimentais

Realizamos vários experimentos pra validar nosso método contra abordagens tradicionais de Árvores de Decisão gananciosas e algoritmos de batch estabelecidos. Nossos testes mostram que, enquanto os métodos clássicos muitas vezes convergem de forma imperfeita ou levam a árvores excessivamente complexas, nosso algoritmo consistentemente alcança resultados ótimos.

Nossos resultados são promissores em vários benchmarks, indicando que nossas técnicas realmente podem superar algoritmos de tomada de decisão existentes, especialmente em contextos de streaming.

#Conclusão, Limitações e Trabalhos Futuros

Apresentamos uma nova família de algoritmos de Monte Carlo Tree Search para Árvores de Decisão online ótimas. Enquanto mostramos forte convergência em nossa abordagem, reconhecemos que limitações atuais existem, particularmente na forma de resultados de convergência assintótica. Esforços futuros vão focar em derivar garantias de tempo finito pra garantir a eficácia de nossos métodos em vários cenários.

Esse trabalho abre novas avenidas de pesquisa sobre alternativas de algoritmos MCTS, potencialmente utilizando outras políticas e incentivando aplicações mais amplas dentro do campo da construção de Árvores de Decisão online.