Decomposing Observational Multiplicity in Decision Trees: Leaf and Structural Regret

Este artigo introduz e valida uma decomposição teórica da multiplicidade observacional em árvores de decisão, identificando o arrependimento estrutural como o principal fator de variabilidade e demonstrando que o uso dessas medidas como mecanismo de abstenção melhora a segurança e a precisão do modelo.

O essencial

Imagine que você é um juiz tentando decidir se alguém deve receber um empréstimo ou não. Você usa um "livro de regras" (um modelo de aprendizado de máquina, especificamente uma Árvore de Decisão) para tomar essa decisão.

Este livro de regras divide as pessoas em caixas (chamadas de "folhas" da árvore). Se você cai na caixa "Renda Alta + Pouca Dívida", o livro diz "Aprovar". Se cai na caixa "Renda Baixa + Muitas Dívidas", diz "Negar".

Agora, aqui está o problema que este artigo resolve: O que acontece se o livro de regras mudar um pouquinho?

O Problema: A "Multiplicidade" das Observações

Imagine que você treinou esse livro de regras usando os dados de 1.000 pessoas. Mas, e se você tivesse treinado com 1.001 pessoas, ou com as mesmas 1.000 pessoas, mas com alguns erros de digitação nos dados?

O resultado é assustador: você pode ter vários livros de regras diferentes que funcionam quase igualmente bem no geral, mas que dão respostas opostas para a mesma pessoa.

Isso é chamado de Multiplicidade Observacional. É como se o destino de uma pessoa dependesse de qual "versão" do livro de regras o computador escolheu aleatoriamente. Isso é perigoso em áreas como saúde ou crédito, onde a decisão precisa ser justa e estável.

A Solução: Dividindo o "Arrependimento" (Regret)

Os autores deste artigo propuseram uma maneira inteligente de entender por que essas decisões mudam. Eles dividiram a incerteza em duas partes, como se fosse uma conta de luz dividida em duas taxas:

1. O "Arrependimento da Folha" (Leaf Regret)

A Analogia: Imagine que você está dentro de uma sala (uma "folha" da árvore) onde todas as pessoas são muito parecidas. O livro de regras diz: "80% das pessoas aqui são aprovadas".

• O que é: A incerteza aqui vem apenas do fato de que, em uma sala pequena, talvez você tenha sorte ou azar com quem você sorteou. Se você tivesse sorte, a porcentagem seria 85%; se tivesse azar, 75%.
• Em resumo: É o "ruído" natural dentro de uma decisão já tomada. É como tentar adivinhar a cor de uma bola tirada de um pote: se o pote tem poucas bolas, sua previsão é menos estável.

2. O "Arrependimento Estrutural" (Structural Regret)

A Analogia: Agora, imagine que, ao mudar levemente os dados de treinamento, o livro de regras inteiro muda. A parede que separava a sala "Aprovar" da sala "Negar" se moveu! De repente, a mesma pessoa que estava na sala "Aprovar" agora caiu na sala "Negar".

• O que é: É a instabilidade da própria estrutura da árvore. O modelo é tão sensível que uma pequena mudança nos dados faz ele redesenhar todo o mapa.
• A Descoberta Chave: O artigo descobriu que, na maioria dos casos, esse "Arrependimento Estrutural" é o vilão principal. Ele é responsável por mais de 15 vezes mais instabilidade do que o ruído dentro das salas. Ou seja, o problema não é o que acontece dentro da caixa, é que a caixa inteira está se movendo de lugar!

Por que isso é importante? (O "Pulo do Gato")

Se você sabe que o problema é a estrutura móvel, você pode agir de forma inteligente. Os autores sugerem usar essa medida de instabilidade como um sistema de alerta.

A Metáfora do "Não sei":
Imagine que o modelo de IA tem um botão de "Não sei" (ou "Abstenção").

• Quando o modelo vê uma pessoa e percebe que a "parede" da árvore está tremendo muito perto dela (alto Arrependimento Estrutural), ele diz: "Eu não tenho certeza. Não tomei essa decisão sozinho."
• Em vez de dar uma resposta errada e arbitrária, ele passa a decisão para um humano.

O Resultado Mágico:
Nos testes com dados de crédito, quando eles usaram essa técnica para ignorar as decisões instáveis e deixar apenas as mais seguras:

• A precisão das decisões positivas (quem realmente deveria receber o empréstimo) subiu de 92% para 100%.
• Eles conseguiram identificar exatamente onde o modelo estava "chutando" e evitar esses erros.

Conclusão Simples

Este artigo nos ensina que, ao usar árvores de decisão para coisas importantes, não basta olhar apenas para a precisão geral. Precisamos olhar para o quanto a estrutura do modelo é frágil.

Eles criaram uma ferramenta para medir essa fragilidade. Se a estrutura é instável, o modelo deve admitir que está inseguro e pedir ajuda humana. Isso torna a Inteligência Artificial mais honesta, segura e justa, evitando que o destino de uma pessoa dependa de um pequeno erro nos dados ou de uma escolha aleatória do computador.

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "Decomposing Observational Multiplicity in Decision Trees: Leaf and Structural Regret", apresentado em português:

Título: Decompondo a Multiplicidade Observacional em Árvores de Decisão: Arrependimento de Folha e Estrutural

1. Problema e Contexto

O artigo aborda o fenômeno da multiplicidade preditiva, onde múltiplos modelos com desempenho agregado quase idêntico podem atribuir previsões conflitantes ao mesmo indivíduo. Enquanto a literatura anterior focava na "multiplicidade de Rashomon" (devido à subespecificação do modelo ou escolhas de otimização), este trabalho concentra-se na multiplicidade observacional.

A multiplicidade observacional surge da natureza estocástica da coleta de dados: os rótulos de treinamento observados são apenas uma realização única de probabilidades de verdade subjacentes. Em domínios de alto risco (como crédito, saúde e justiça), essa variabilidade irreduzível gera "arbitrariedade preditiva", onde a decisão sobre um indivíduo depende de qual modelo "equivalente" foi escolhido, comprometendo a segurança e a interpretabilidade.

Embora frameworks teóricos para multiplicidade observacional existam para regressão logística (modelos suaves), eles são insuficientes para árvores de decisão, que são modelos não suaves e baseados em partições. As árvores são notoriamente instáveis a pequenas perturbações nos dados, e a literatura carece de uma decomposição formal de como essa instabilidade se manifesta.

2. Metodologia

Os autores propõem uma decomposição formal da incerteza preditiva total em duas componentes complementares:

• Arrependimento de Folha (Leaf Regret):

  • Definição: Quantifica a variabilidade intrínseca das previsões dentro de uma folha fixa, condicionada a uma estrutura de árvore específica.
  • Causa: Ruído de amostragem finita (variabilidade aleatória dos rótulos dentro de uma partição fixa).
  • Tratamento Teórico: É tratado como uma quantidade estatística bem definida. Os autores provam que o arrependimento de folha é limitado superiormente por $1/(4n_L)$(onde$n_L$ é o tamanho da folha) e fornece desigualdades de concentração para o estimador de plug-in.
  • Estimativa: Pode ser estimado analiticamente ou via procedimentos de Monte Carlo (resampleamento de Bernoulli dentro da folha).

• Arrependimento Estrutural (Structural Regret):

  • Definição: Captura a variabilidade adicional induzida pela aleatoriedade na própria estrutura da árvore aprendida (como a seleção de divisões e a topologia da árvore).
  • Causa: Instabilidade algorítmica; diferentes realizações de rótulos de treinamento levam a árvores com topologias diferentes.
  • Tratamento Teórico: É analisado através de argumentos de estabilidade. O artigo demonstra que, sob condições de estabilidade da árvore, o arrependimento estrutural tende a zero assintoticamente.
  • Estimativa: É aproximado via métodos de Monte Carlo, treinando múltiplas árvores em amostras bootstrap e calculando a variância das previsões para um mesmo ponto de entrada.

Decomposição Total:
O trabalho estabelece a identidade matemática:
$$\text{Variância Preditiva Total} = \mathbb{E}[\text{Arrependimento de Folha}] + \text{Arrependimento Estrutural}$$

3. Contribuições Principais

1. Formalização Teórica: Introdução de dois conceitos distintos de arrependimento para classificar árvores, preenchendo a lacuna entre a teoria da multiplicidade observacional e a indução baseada em partições.
2. Garantias Estatísticas: Prova de consistência e desigualdades de concentração para o estimador de arrependimento de folha, mostrando que ele é uma medida estatisticamente robusta.
3. Decomposição Empírica: Validação experimental de que a variância total pode ser exatamente decomposta nessas duas componentes.
4. Aplicação em Segurança (Seleção Seletiva): Proposta de usar essas medidas de arrependimento como um mecanismo de "abstenção" (recusa em prever) para identificar regiões onde o modelo está "adivinhando" devido à instabilidade, melhorando a segurança do sistema.

4. Resultados Experimentais

Os autores avaliaram o framework em diversos conjuntos de dados reais de risco de crédito (ex: taiwan_credit, german_credit, bank_marketing).

• Validação da Decomposição: Houve uma correspondência quase perfeita entre a variância preditiva simulada (verdade) e a soma dos componentes estimados (folha + estrutural), confirmando a precisão do modelo teórico.
• Dominância do Arrependimento Estrutural: A descoberta mais impactante foi que o arrependimento estrutural é o principal motor da multiplicidade observacional. Em alguns conjuntos de dados (como taiwan_credit), a variabilidade estrutural foi mais de 15 vezes maior que a variabilidade de folha. Isso indica que a instabilidade das fronteiras de decisão (topologia da árvore) é um problema maior do que o ruído dentro das folhas.
• Impacto do Tamanho da Folha: Aumentar o tamanho mínimo da folha reduz drasticamente o arrependimento de folha (conforme a teoria), mas pode levar a underfitting (aumento da perda logística), sugerindo um compromisso necessário entre viés e estabilidade.
• Seleção Seletiva e Segurança: Ao classificar indivíduos pelo seu arrependimento total e abster-se das previsões mais instáveis:
  • Em dados de crédito alemão (german_credit), a Recall (sensibilidade) aumentou de 92% para 100% ao focar apenas nos subgrupos mais estáveis.
  • O uso de Arrependimento Estrutural mostrou-se mais eficaz do que o de folha para filtrar previsões arbitrárias e identificar regiões onde o modelo é fundamentalmente inseguro.

5. Significado e Implicações

Este trabalho oferece uma nova lente para a segurança algorítmica em modelos baseados em árvores:

• Diagnóstico de Instabilidade: Permite distinguir se a incerteza de uma previsão vem de ruído local (que pode ser mitigado com mais dados na folha) ou de instabilidade global da estrutura (que requer regularização, poda ou ensembles).
• Princípio de "Honestidade" do Modelo: O framework permite que o modelo sinalize honestamente quando não deve tomar uma decisão automática (abstenção), especialmente em casos de alto risco onde a estrutura do modelo é instável.
• Direcionamento de Mitigação: Como o arrependimento estrutural domina, as estratégias de segurança devem priorizar a estabilização da estrutura da árvore (ex: bagging, poda mais agressiva) em vez de apenas aumentar o tamanho das folhas.

Em resumo, o artigo estabelece um framework rigoroso para quantificar e decompor a multiplicidade observacional, provando que a instabilidade estrutural das árvores de decisão é a fonte predominante de arbitrariedade preditiva e fornecendo ferramentas práticas para mitigar esse risco em cenários de alto impacto.