Resumo Técnico: Aprendizado de Conjuntos de Regras Parsimoniosos de Alta Cobertura e Discriminativos (CDPR)

1. Definição do Problema

O artigo aborda uma limitação crítica no aprendizado de máquina interpretável atual: o problema "alta acurácia-baixa cobertura". Embora os algoritmos de aprendizado de regras de estado da arte (SOTA) atuais (ex: IDS, RIPPER, DefragTrees) frequentemente alcancem alta acurácia preditiva, eles frequentemente falham em cobrir uma parte significativa do espaço de entrada. Baixa cobertura significa que, para uma grande fração de pontos de dados, o modelo depende de uma regra padrão com lógica desconhecida, prejudicando a transparência e a explicabilidade exigidas em domínios críticos como saúde e finanças.

Os autores definem o problema de aprendizado de Conjunto de Regras Parsimonioso, Discriminativo e de Alta Cobertura (CDPR). O objetivo é aprender um conjunto de regras $S$ que maximize simultaneamente a cobertura (a fração do conjunto de dados coberta pelas regras) enquanto satisfaz restrições rigorosas de qualidade em relação a:

• Poder Discriminativo: Acurácia mínima da regra ($\alpha$).
• Parsimônia: Largura máxima da regra ($\delta$) e tamanho máximo do conjunto de regras ($\gamma$).
• Interpretabilidade: Taxa de sobreposição máxima ($\beta$) entre quaisquer duas regras para garantir redundância mínima.

Formalmente, o problema (CDPRL) é definido como:
$$\text{maximizar}_{S \subseteq B_{\alpha,\delta}} \text{cobertura}(S)$$
$$sujeito a: \text{tamanho-da-regra}(S) \le \gamma, \quad \text{taxa-de-sobreposição}(r_i, r_j) \le \beta$$
onde $B_{\alpha,\delta}$ é o conjunto de regras candidatas com acurácia $\ge \alpha$ e largura $\le \delta$. Os autores observam que os solvers existentes não podem abordar isso diretamente porque a restrição de taxa de sobreposição não é nem um matroide nem uma restrição de mochila (knapsack).

2. Metodologia

O artigo propõe dois algoritmos baseados em maximização submodular para resolver o problema CDPR.

2.1 Algoritmo de Regras de Grafo (GRA)

O GRA é projetado para resolver o problema CDPRL diretamente, transformando-o em um problema de otimização submodular sobre uma estrutura de grafo.

• Construção do Grafo de Sobreposição: Um grafo direcionado $G=(V, E)$ é construído onde os vértices representam regras candidatas em $B_{\alpha,\delta}$. Uma aresta direcionada $(r_i, r_j)$ existe se a taxa de sobreposição entre $r_i$ e $r_j$ exceder o limite $\beta$.
• Processo de Seleção: O algoritmo seleciona iterativamente o vértice (regra) com a maior cobertura do grafo, adiciona-o ao conjunto de regras $S$ e remove o vértice selecionado junto com quaisquer vértices conectados a ele por uma aresta direcionada (para satisfazer a restrição de sobreposição). Isso continua até que o conjunto de regras atinja o tamanho $\gamma$ ou o grafo fique vazio.
• Garantia Teórica: Os autores provam que o GRA fornece uma garantia de aproximação de $(1 - (1 - \frac{1-\beta}{\gamma(1+d\beta)})^\gamma)$, onde $d$ é o grau de entrada mínimo dos nós selecionados.
• Complexidade: O tempo de execução é quadrático no tamanho do conjunto candidato $|B_{\alpha,\delta}|$.

2.2 Algoritmo Ganancioso (GDY)

Para lidar com o custo computacional do GRA, os autores introduzem uma variante relaxada chamada CDPRL-MO (Sobreposição Média).

• Objetivo Relaxado: Em vez de impor estritamente uma taxa de sobreposição $\le \beta$ para cada par, o GDY otimiza uma função $g(S)$ que equilibra a cobertura e a minimização da sobreposição média através do conjunto.
• Submodularidade: Os autores provam que a função objetivo $g(S)$ é uma função submodular não-monótona.
• Algoritmo: O GDY emprega um algoritmo de aproximação ganancioso (greedy) projetado para maximização submodular não-monótona com restrições de cardinalidade.
• Garantia Teórica: O GDY alcança uma garantia de aproximação de $1/4$.
• Complexidade: O tempo de execução é quase linear em $|B_{\alpha,\delta}|$, tornando-o significativamente mais rápido que o GRA para grandes conjuntos candidatos.

3. Principais Contribuições

1. Formulação do Problema: O artigo introduz o CDPR como uma nova formulação de problema que visa explicitamente o compromisso entre alta acurácia-baixa cobertura, uma lacuna que os autores identificam como não abordada na literatura anterior.
2. Algoritmos Inovadores:
   • GRA: Um algoritmo baseado em grafos com garantias de aproximação prováveis para o problema estrito de CDPR.
   • GDY: Um algoritmo ganancioso computacionalmente eficiente para a variante relaxada CDPRL-MO.
3. Análise Teórica: Os autores fornecem provas formais para as garantias de aproximação de ambos os algoritmos, estabelecendo sua validade teórica dentro do framework de otimização submodular.
4. Validação Empírica: Experimentos extensos em 12 conjuntos de dados (10 conjuntos de dados UCI e 2 conjuntos de dados de doença de Alzheimer) demonstram a eficácia dos métodos propostos.

4. Resultados Experimentais

Os autores avaliaram o GRA e o GDY contra baselines SOTA (IDS, DefragTrees, RIPPER) e modelos de caixa-preta padrão (Random Forest, Regressão Logística).

• Cobertura: A melhoria mais significativa foi observada nas taxas de cobertura. O GRA alcançou uma taxa de cobertura média de 97%, e o GDY alcançou 91%. Em contraste, o próximo melhor baseline (IDS) alcançou apenas 35%, e o RIPPER alcançou 31%. Isso representa uma melhoria de 2,5 vezes na cobertura média sobre o melhor algoritmo de aprendizado de regras existente.
• Acurácia (Poder Discriminativo): O GRA alcançou uma Acurácia de Conjunto de Regras (RSA) média de 0,85, superando o IDS (0,82), DefragTrees (0,76) e RIPPER (0,80). O desempenho do GRA foi competitivo com o Random Forest (RF), igualando ou superando o RF em 7 de 12 conjuntos de dados.
• Parsimônia: Tanto o GRA quanto o GDY mantiveram baixas larguras de regra (largura máxima média de 4) e tamanhos de conjunto de regras razoáveis (tamanho médio de 7 regras), comparáveis ao IDS e RIPPER, e significativamente melhores que o DefragTrees (largura máxima média de 10).
• Estudo de Caso (Doença de Alzheimer): Em uma aplicação específica de design de testes neurocognitivos para triagem de Alzheimer, o GRA e o GDY geraram com sucesso conjuntos de regras que reduziram o número de características necessárias em pelo menos 18% em comparação ao DefragTrees, mantendo alta acurácia e cobertura (>70%).

5. Significância e Alegações

O artigo afirma que o CDPR representa a primeira tentativa de estabelecer uma abordagem que otimize simultaneamente alta cobertura, poder discriminativo e parsimônia no aprendizado de regras.

Os autores enfatizam que, embora a interpretabilidade seja frequentemente definida meramente pela complexidade do modelo (menos regras), a verdadeira interpretabilidade em aplicações críticas exige que o modelo possa explicar decisões para a vasta maioria das entradas (alta cobertura). Ao resolver o problema de alta acurácia-baixa cobertura, os métodos propostos (GRA e GDY) permitem a implantação de modelos interpretáveis em domínios onde a transparência e a fidelidade são primordiais, como saúde e justiça criminal, sem sacrificar o desempenho preditivo. O trabalho sugere que a maximização submodular é um framework viável e eficaz para aprender conjuntos de regras de alta qualidade, oferecendo um caminho para sistemas de IA mais confiáveis.