ArborEnum: Decision Tree Rashomon Sets over Continuous Features

Imagine que você está tentando resolver um nó enorme e emaranhado de um problema. No mundo da ciência da computação, especificamente em um campo chamado aprendizado de máquina, frequentemente pedimos aos computadores para encontrar a "melhor" maneira de fazer previsões, como adivinhar se um cliente comprará um produto ou se um paciente tem uma determinada condição. Por muito tempo, os cientistas acreditaram que geralmente existia apenas uma única resposta perfeita — um "modelo dourado" único que era o melhor absoluto. Mas há uma reviravolta fascinante nesta história chamada efeito Rashomon. Nomeado em homenagem a um filme famoso onde quatro testemunhas contam versões diferentes do mesmo evento, este efeito descreve uma realidade onde muitos modelos completamente diferentes podem ter um desempenho quase exatamente igual. Todos são "bons o suficiente", mas podem usar pistas diferentes ou olhar para os dados de maneiras totalmente distintas.

Por que isso importa? Porque se você procurar apenas por esse único modelo "dourado", pode perder toda uma multidão de alternativas igualmente boas. Algumas dessas alternativas podem ser mais seguras, mais fáceis de entender ou mais justas. Para estudar isso, pesquisadores buscam um conjunto Rashomon: uma coleção de todos os modelos que são quase perfeitos. O desafio é que encontrar esse conjunto é como tentar contar cada grão de areia em uma praia. É um trabalho enorme e confuso, especialmente quando os dados não são apenas respostas simples de "sim ou não" (como vermelho ou azul), mas incluem características contínuas — números que podem ser qualquer coisa, como temperatura, altura ou preço, que podem ser divididos em milhões de pontos diferentes.

É aqui que um novo estudo entra, introduzindo uma ferramenta inteligente chamada ArborEnum. Pense nos pesquisadores como exploradores tentando mapear uma floresta densa e nebulosa. Antes, se eles quisessem mapear a floresta, tinham que derrubá-la em quadrados de grade limpos e organizados (um processo chamado binarização) apenas para torná-la gerenciável. Mas, ao fazer isso, eles frequentemente perdiam caminhos ocultos, árvores raras ou atalhos importantes que existiam na paisagem contínua e selvagem. Os autores deste artigo construíram uma nova espécie de bússola que permite explorar a floresta exatamente como ela é, com todas as suas curvas suaves e contínuas, sem precisar cortá-la primeiro. Eles descobriram que, ao ignorar a suavidade dos dados, os métodos antigos estavam perdendo grandes partes dos modelos "bons". Seu novo método consegue listar esses modelos muito mais rápido — às vezes centenas de vezes mais rápido — do que antes. Melhor ainda, eles criaram uma versão "inteligente" que começa com um esboço bruto da floresta e continua a refiná-la, tornando-se mais detalhada quanto mais tempo você a deixa rodar, para que você possa parar sempre que tiver informações suficientes. Eles provaram, através de experimentos com dados do mundo real, que essa abordagem não apenas economiza tempo, mas também encontra características importantes e variações de modelos que os antigos métodos baseados em grades totalmente ignoraram.

A História da Floresta e da Grade

Imagine que você é um detetive tentando resolver um mistério. Você tem um monte de pistas e precisa construir uma árvore de decisão — um fluxograma de perguntas — para descobrir quem o cometeu. Normalmente, você faria perguntas como: "O suspeito é mais alto que 1,80 m?" ou "O suspeito está usando um chapéu?". Nos velhos tempos, os cientistas da computação tinham que transformar cada pista em uma pergunta simples de "sim ou não" antes de começarem a construir sua árvore. Se uma pista fosse um número, como "A altura do suspeito é 1,80 m", eles tinham que cortá-la em baldes: "Ele tem menos de 1,70 m?", "Ele está entre 1,70 m e 1,85 m?" ou "Ele tem mais de 1,85 m?".

Esse processo de corte é chamado de binarização. É como pegar um rio suave e fluido e forçá-lo em uma série de canais de concreto quadrados. O problema é que, ao forçar a água nesses caixas rígidas, você pode perder um pequeno redemoinho perfeito ou uma corrente oculta que flui justamente entre as fendas. No mundo do aprendizado de máquina, isso significa que você pode perder uma divisão perfeita dos dados porque sua "grade" não tinha uma linha exatamente onde os dados precisavam dela.

O efeito Rashomon é a ideia de que não existe apenas um fluxograma perfeito. Existem dezenas, talvez centenas, de fluxogramas diferentes que resolvem o mistério com a mesma alta precisão. Alguns podem usar a altura, outros o peso, ou uma combinação de ambos. O conjunto Rashomon é a coleção de todos esses fluxogramas igualmente bons. Encontrar esse conjunto é extremamente útil porque ajuda a entender quais pistas são realmente importantes e quais são apenas palpites de sorte. Se uma pista aparece em quase todos os bons fluxogramas, ela provavelmente é uma chave real para o mistério. Se ela aparece em apenas um, pode ser apenas um acaso.

O Problema dos Mapas Antigos

Por muito tempo, a única maneira de encontrar esse conjunto Rashomon era usar o método do "canal de concreto" (binarização). Pesquisadores cortavam os números contínuos em alguns baldes e então tentavam encontrar todas as boas árvores. Mas isso tinha dois grandes problemas. Primeiro, o espaço de busca já era enorme; com apenas 20 características binárias, já havia mais árvores do que grãos de areia na Terra. Segundo, ao cortar os dados, eles estavam jogando informação fora. Eles poderiam perder uma divisão que acontecesse em um número muito específico, como 1,79 m, porque seus baldes eram apenas 1,70 m e 1,85 m.

A binarização "grossa" é como tentar encontrar uma agulha em um palheiro olhando apenas para a camada superior do feno. Você pode encontrar uma agulha, mas perderá as que estão enterradas mais fundo ou as que têm formatos ligeiramente diferentes. Os autores descobriram que, ao forçar os dados nesses baldes brutos, eles perderam muitas árvores importantes, características importantes e a verdadeira variedade de soluções (multiplicidade preditiva).

A Nova Bússola: ArborEnum

Entra o ArborEnum. Os autores construíram o primeiro algoritmo que pode explorar a "floresta contínos" sem cortá-la primeiro. Em vez de forçar os dados em baldes quadrados, o ArborEnum respeita a ordem natural dos números. Ele trata os dados como uma linha suave e procura os melhores lugares para cortá-la, sabendo que existem milhares de possíveis pontos de corte.

Para fazer isso, eles usaram um truque inteligente. Imagine que você está procurando o melhor lugar para cortar uma corda. Você não precisa testar cada milímetro. Se você sabe que cortar aos 10 polegadas é ruim, e cortar aos 11 polegadas também é ruim, você provavelmente pode adivinhar que cortar aos 10,5 polegadas também não será ótimo. Os autores desenvolveram uma forma de usar esses "limites" para pular grandes seções da corda que não precisam ser testadas. Eles chamam isso de poda (pruning). É como ter um mapa que diz: "Não perca tempo procurando neste vale inteiro; o tesouro não está lá".

Eles também introduziram um sistema de "proxy". Pense em um proxy como um palpite rápido e bruto. Antes de fazer o trabalho pesado de verificar cada possibilidade, o algoritmo faz um palpite rápido e aproximado para ver se um caminho vale a pena ser explorado. Se o palpite diz "de jeito nenhum", ele pula todo o ramo. Se o palpite diz "talvez", ele cava mais fundo. Isso permite que o algoritmo rode incrivelmente rápido. Em seus testes, este método foi, em média, 270 vezes mais rápido do que os métodos existentes, e em alguns casos, a diferença foi ainda mais dramática.

O Recurso "Anytime": Um Esboço que Melhora

Uma das partes mais legais do ArborEnum é seu algoritmo "anytime" (a qualquer momento). Normalmente, se você quer um mapa perfeito, tem que esperar o computador terminar todo o trabalho. Mas e se você precisar de uma resposta agora? A versão "anytime" do ArborEnum começa com um esboço muito bruto da floresta. Ele pode observar apenas alguns pontos de corte principais. Ele te dá uma lista de boas árvores baseada nesse esboço bruto.

Depois, conforme você o deixa rodar por mais tempo, ele adiciona mais e mais pontos de corte ao seu mapa. Ele refina o esboço, preenchendo as lacunas. Quanto mais tempo você der, mais detalhada e precisa será a lista de árvores. Eventualmente, se você deixá-lo rodar o suficiente, ele encontrará a lista exata e perfeita de todas as boas árvores. O melhor de tudo? Você pode pará-lo a qualquer momento. Se você precisa de uma resposta em 5 minutos, você terá uma boa aproximação. Se você tem 5 horas, terá uma resposta quase perfeita. Os autores descobriram que, mesmo com esse "começo bruto", o método recuperou quase todas as árvores importantes, e o tempo extra que levou para refinar o mapa foi minúsculo — apenas cerca de 2,7% mais tempo do que rodar a versão não refinada no conjunto final de pontos.

O Que Eles Descobriram e O Que Isso Significa

Os experimentos foram realizados em 20 conjuntos de dados do mundo real, desde a previsão de aluguel de bicicletas até inadimplência de cartões de crédito. Os resultados foram claros:

1. A binarização grosseira perde muito: Quando compararam o antigo método de "corte" com o novo método contínuo, o método antigo perdeu muitas árvores e características importantes. Era como olhar para uma foto através de uma janela embaçada; você via a forma geral, mas perdia os detalhes.
2. A velocidade é real: O novo método foi ordens de magnitude mais rápido. Em um conjunto de dados chamado "Bike", o novo método ótimo terminou 63 vezes mais rápido do que o único outro método que conseguia sequer terminar.
3. A precisão é alta: Mesmo usando o método "proxy" rápido e aproximado, eles recuperaram de 94,5% a 100% das árvores que o método perfeito encontrou. Isso significa que você pode obter quase todos os benefícios do conjunto Rashomon sem esperar uma eternidade.
4. A abordagem "anytime" funciona: O método que começa bruto e melhora com o tempo provou ser muito eficiente. Ele encontrou características importantes logo no início, o que significa que você pode obter insights úteis rapidamente sem esperar pelo processamento completo.

O artigo não afirma ter resolvido todos os problemas do aprendizado de máquina. Não diz que características contínuas são a única maneira de fazer as coisas, nem que este método funcione para todo tipo de modelo. Mas mostra, com evidências sólidas de experimentos, que para árvores de decisão, tratar dados contínuos como contínuos é um divisor de águas. Isso nos permite ver o quadro completo do "conjunto Rashomon" sem perder a sanidade (ou nossos computadores) devido à complexidade.

Em resumo, o ArborEnum é uma nova maneira de explorar o cenário de boas soluções. Ele nos impede de forçar o mundo em uma grade que não se encaixa e, em vez disso, nos permite caminhar pelos caminhos suaves e contínuos onde as respostas reais costumam se esconder. Quer você seja um cientista de dados procurando o melhor modelo ou apenas uma pessoa curiosa querendo saber como os computadores tomam decisões, este trabalho sugere que há mais boas respostas do que pensávamos, e agora temos uma maneira melhor de encontrá-las.