Experiments with Optimal Model Trees

Este artigo investiga empiricamente a construção de árvores de modelo globalmente ótimas utilizando programação linear inteira mista, demonstrando que elas alcançam precisão competitiva com árvores muito menores em comparação aos métodos tradicionais de crescimento ganancioso.

O essencial

Imagine que você precisa ensinar um computador a tomar decisões, como um médico diagnosticando uma doença ou um banco aprovando um empréstimo. A maneira mais comum e fácil de entender como o computador "pensa" é usando uma Árvore de Decisão.

Pense nessa árvore como um jogo de "20 Perguntas" ou um mapa do tesouro:

1. Você começa na raiz (o topo).
2. Faz uma pergunta simples: "A idade é maior que 30?".
3. Se sim, vai para a esquerda; se não, vai para a direita.
4. Repete o processo até chegar a uma folha (o final do caminho), onde o computador dá a resposta final.

O Problema das Árvores Comuns

A maioria das árvores de decisão funciona como um algoritmo ganancioso. Imagine que você está descendo uma montanha tentando achar o ponto mais baixo, mas só olha para o chão logo à sua frente. Você dá um passo para o lado mais baixo, depois outro, e assim por diante. O problema é que você pode ficar preso em um pequeno vale, sem perceber que, se tivesse dado um passo diferente no início, teria encontrado um vale muito mais profundo (uma solução melhor).

No mundo das árvores, isso significa que elas podem ficar gigantescas e confusas para tentar ser precisas, perdendo a vantagem de serem fáceis de entender.

A Solução: Árvores de Modelo (Model Trees)

Os autores deste paper propuseram uma evolução: as Árvores de Modelo.
Em vez de chegar a uma folha e apenas dizer "A resposta é 50" (um valor fixo), a folha da árvore contém um pequeno especialista (um modelo matemático linear, como uma linha reta que ajusta os dados).

• Analogia: Imagine uma árvore comum como um manual de instruções que diz: "Se o carro é vermelho, o preço é 10 mil".
• Árvore de Modelo: É como um manual que diz: "Se o carro é vermelho, use esta fórmula para calcular o preço baseada no ano e na quilometragem".

Isso permite que a árvore seja muito menor e mais precisa, porque cada "final de caminho" é inteligente, não apenas um número estático.

A Grande Inovação: O "Mestre do Tabuleiro" (MILP)

O grande desafio é: como encontrar a árvore perfeita?
Os métodos comuns (gananciosos) constroem a árvore peça por peça, sem olhar para o todo. Os autores usaram uma técnica chamada Programação Linear Inteira Mista (MILP).

• A Analogia: Imagine que você está montando um quebra-cabeça gigante.
  • O método comum pega uma peça, encaixa onde parece bom agora, e segue em frente.
  • O método MILP é como ter um Mestre do Tabuleiro que olha para todas as peças de uma vez, calcula todas as combinações possíveis e monta o quebra-cabeça perfeito de uma só vez, garantindo que o resultado final seja o melhor possível, não apenas o melhor "agora".

O papel mostra que, ao usar esse "Mestre do Tabuleiro" (computadores potentes resolvendo equações complexas), eles conseguiram criar árvores que:

1. São muito menores (mais fáceis de ler e entender).
2. São tão precisas (ou até mais) do que as árvores gigantes feitas pelos métodos comuns.
3. Conseguem fazer previsões complexas mantendo a simplicidade visual.

O Custo: O Tempo de Computação

Há um "mas". Encontrar essa solução perfeita é como tentar encontrar a chave de ouro em um labirinto gigante olhando para cada caminho possível.

• O Resultado: Para árvores pequenas (até 2 ou 3 divisões), o método é incrível e rápido.
• O Desafio: Se a árvore precisa ser grande, o computador pode demorar horas (ou dias) para achar a solução perfeita. Em alguns testes, o computador "desistiu" (time-out) depois de uma hora, mas mesmo assim, a solução que ele tinha até aquele momento era muito boa.

Conclusão Simples

Este paper diz: "Se você precisa de um modelo de IA que seja preciso e, ao mesmo tempo, fácil de explicar para um humano (como um juiz ou um médico), não use as árvores gigantes e confusas de sempre. Use essas novas 'Árvores de Modelo' otimizadas."

Elas são como navios de luxo: pequenos, eficientes e com tudo o que você precisa, em vez de construir um transatlântico gigante e lento só para chegar ao mesmo lugar. O único preço é que construir o navio de luxo exige mais tempo e energia no início, mas o resultado vale a pena quando a clareza é essencial.

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "Experiments with Optimal Model Trees", apresentado em português:

Título: Experiências com Árvores de Modelo Ótimas (Experiments with Optimal Model Trees)

Autores: Sabino Francesco Roselli (Chalmers University of Technology) e Eibe Frank (University of Waikato).

---

1. Problema e Motivação

As árvores de decisão são modelos preditivos amplamente utilizados devido à sua interpretabilidade. No entanto, as árvores de decisão "clássicas" possuem valores constantes nas folhas, o que pode exigir árvores grandes e complexas para atingir alta precisão, especialmente em problemas de regressão ou classificação complexos.

As Árvores de Modelo (Model Trees) surgem como uma alternativa, onde cada nó folha contém um modelo linear (como regressão linear ou SVM) em vez de um valor constante. Isso permite representar funções lineares por partes, muitas vezes resultando em árvores menores e mais precisas.

O problema central abordado é que os algoritmos tradicionais de aprendizado de árvores (como CART, C4.5, M5P) operam de forma gananciosa (greedy). Eles fazem divisões localmente ótimas em cada nó sem considerar o impacto global na estrutura da árvore. Isso frequentemente leva a árvores desnecessariamente grandes ou subótimas.

O objetivo deste trabalho é investigar empiricamente se a construção de árvores de modelo globalmente ótimas utilizando Programação Linear Inteira Mista (MILP - Mixed-Integer Linear Programming) pode superar as abordagens ganancias e dinâmicas, oferecendo árvores menores com precisão competitiva ou superior.

2. Metodologia

Os autores propõem uma formulação matemática rigorosa para aprender árvores de modelo ótimas, combinando a estrutura discreta da árvore com os parâmetros contínuos dos modelos lineares nas folhas.

• Abordagem MILP: O problema é formulado como um problema de otimização global onde todas as divisões e os coeficientes dos modelos lineares são decididos simultaneamente.
• Modelos nas Folhas:
  • Regressão: Utilizam Máquinas de Vetores de Suporte (SVM) lineares com perda de erro absoluto (equivalente a SVM com $\epsilon=0$).
  • Classificação: Utilizam SVMs lineares para classificação binária e multiclasse.
• Tipos de Árvores:
  • Univariadas: Divisões baseadas em um único recurso e um limiar.
  • Multivariadas: Divisões baseadas em combinações lineares de recursos (menos interpretáveis, mas potencialmente mais precisas).
• Formulação:
  • A estrutura da árvore é modelada com variáveis binárias ($d_n$) indicando se um nó se divide.
  • As restrições garantem que os pontos de dados sejam roteados corretamente para as folhas e que os modelos SVM nas folhas minimizem o erro nos dados que chegam a elas.
  • A função objetivo minimiza a soma dos pesos absolutos dos SVMs (regularização L1) e o erro de previsão.
• Hiperparâmetros: Otimização iterativa do coeficiente de regularização $C$ (para SVM) e do número máximo de divisões $S$ (profundidade da árvore), utilizando conjuntos de validação.

3. Contribuições Principais

1. Formulação MILP para Classificação: Apresentam uma nova formulação baseada em SVM para árvores de modelo de classificação (OCMT), sendo os primeiros a fornecer uma avaliação empírica extensiva.
2. Revisão da Abordagem Global: Diferentemente de trabalhos anteriores (como [14]) que abandonaram a otimalidade global em favor de buscas locais para acelerar o processo, este trabalho foca estritamente na solução ótima global usando ambientes computacionais modernos (Gurobi 11.0.1).
3. Comparação Abrangente: Avaliam as árvores de modelo ótimas (OCMT e ORMT) contra uma vasta gama de concorrentes:
   • Árvores de decisão ótimas (OCT/ORT).
   • Árvores de modelo com busca local (LS-OMT).
   • Algoritmos gananciosos (CART, M5P, LMT).
   • Florestas Aleatórias (Random Forests) e SVMs lineares.
   • Métodos baseados em Programação Dinâmica (DL8.5, SRT-L).
4. Análise de Escalabilidade e Interpretabilidade: Investigam o compromisso entre tempo de computação, tamanho da árvore e precisão, destacando que árvores pequenas e precisas são viáveis para conjuntos de dados de tamanho moderado.

4. Resultados Experimentais

Os experimentos foram realizados em 20 problemas de classificação binária, 5 multiclasse e 20 problemas de regressão do repositório OpenML.

• Precisão vs. Tamanho:
  • As Árvores de Modelo Ótimas (OCMT/ORMT) alcançaram precisão significativamente superior às árvores de decisão ótimas clássicas (OCT/ORT) com o mesmo tamanho (profundidade máxima). Em alguns casos de classificação, a OCMT superou a OCT em mais de 30%.
  • Comparadas a algoritmos gananciosos (CART, M5P, LMT) e métodos de busca local (LS-OMT), as árvores ótimas foram competitivas em precisão, mas consistentemente menores.
  • Árvores menores implicam maior interpretabilidade. Enquanto o CART e o LMT frequentemente geravam árvores com dezenas ou centenas de folhas, as árvores ótimas geradas via MILP geralmente tinham menos de 10 folhas.
• Univariadas vs. Multivariadas:
  • Contrariando a expectativa, as árvores multivariadas (OCMT-H/ORMT-H) não superaram consistentemente as univariadas em termos de precisão, embora tenham mostrado ganhos em casos específicos (ex: conjuntos de dados "Parity" e "Long").
  • No entanto, árvores ótimas multivariadas (sem SVM) superaram consistentemente suas contrapartes univariadas.
• Desempenho Comparativo:
  • Florestas Aleatórias (RF) geralmente tiveram o melhor desempenho absoluto (maior precisão), mas são "caixas pretas" e menos interpretáveis.
  • As árvores de modelo ótimas ofereceram um equilíbrio superior entre interpretabilidade (tamanho pequeno) e precisão, superando SVMs lineares simples e árvores de decisão estáticas.
• Escalabilidade (Tempo de Execução):
  • O principal gargalo é o tempo de computação. Para árvores com mais de uma divisão (profundidade > 1), o solver MILP frequentemente atingiu o limite de tempo (3600 segundos) sem provar a otimalidade, embora as soluções encontradas fossem de alta qualidade.
  • O tempo de execução aumenta drasticamente com o número de pontos de dados e recursos.

5. Significado e Conclusão

O artigo demonstra que a abordagem baseada em MILP para árvores de modelo é uma ferramenta poderosa para gerar modelos de aprendizado de máquina que são simultaneamente altamente precisos e altamente interpretáveis.

• Interpretabilidade: Ao produzir árvores muito menores do que os métodos gananciosos para atingir a mesma (ou melhor) precisão, o método facilita a explicação das decisões para especialistas humanos.
• Viabilidade Prática: Embora o tempo de computação seja alto para conjuntos de dados muito grandes, o método é viável e superior para conjuntos de dados de tamanho moderado (até ~10.000 pontos) onde a interpretabilidade é crítica (ex: saúde, finanças, manufatura).
• Futuro: Os autores sugerem que técnicas de decomposição e formulações para árvores de política ótima podem ser exploradas para melhorar a escalabilidade.

Em resumo, o trabalho valida que, ao custo de tempo computacional, é possível obter árvores de decisão que não apenas "funcionam" bem, mas que são estruturalmente eficientes e transparentes, superando as limitações das abordagens puramente ganancias.