2025-11-12T13:34:14.831387

Efficient & Correct Predictive Equivalence for Decision Trees

Marques-Silva, Ignatiev
The Rashomon set of decision trees (DTs) finds importance uses. Recent work showed that DTs computing the same classification function, i.e. predictive equivalent DTs, can represent a significant fraction of the Rashomon set. Such redundancy is undesirable. For example, feature importance based on the Rashomon set becomes inaccurate due the existence of predictive equivalent DTs, i.e. DTs with the same prediction for every possible input. In recent work, McTavish et al. proposed solutions for several computational problems related with DTs, including that of deciding predictive equivalent DTs. The approach of McTavish et al. consists of applying the well-known method of Quine-McCluskey (QM) for obtaining minimum-size DNF (disjunctive normal form) representations of DTs, which are then used for comparing DTs for predictive equivalence. Furthermore, the minimum-size DNF representation was also applied to computing explanations for the predictions made by DTs, and to finding predictions in the presence of missing data. However, the problem of formula minimization is hard for the second level of the polynomial hierarchy, and the QM method may exhibit worst-case exponential running time and space. This paper first demonstrates that there exist decision trees that trigger the worst-case exponential running time and space of the QM method. Second, the paper shows that the QM method may incorrectly decide predictive equivalence, if two key constraints are not respected, and one may be difficult to formally guarantee. Third, the paper shows that any of the problems to which the smallest DNF representation has been applied to can be solved in polynomial time, in the size of the DT. The experiments confirm that, for DTs for which the worst-case of the QM method is triggered, the algorithms proposed in this paper are orders of magnitude faster than the ones proposed by McTavish et al.
academic

Equivalenza Predittiva Efficiente e Corretta per Alberi Decisionali

Informazioni Fondamentali

  • ID Articolo: 2509.17774
  • Titolo: Efficient & Correct Predictive Equivalence for Decision Trees
  • Autori: João Marques-Silva (ICREA & University of Lleida), Alexey Ignatiev (Monash University)
  • Classificazione: cs.AI cs.LG cs.LO
  • Data di Pubblicazione/Conferenza: Journal of Machine Learning Research 23 (2025) 1-35
  • Link Articolo: https://arxiv.org/abs/2509.17774

Riassunto

Gli insiemi di Rashomon degli alberi decisionali hanno un valore applicativo significativo. Ricerche recenti hanno dimostrato che il calcolo di alberi decisionali che implementano la stessa funzione di classificazione (cioè alberi decisionali predittivamente equivalenti) può costituire una parte considerevole dell'insieme di Rashomon. Questa ridondanza è indesiderabile, ad esempio la valutazione dell'importanza delle caratteristiche basata sull'insieme di Rashomon diventa imprecisa a causa della presenza di alberi decisionali predittivamente equivalenti. McTavish et al. hanno recentemente proposto una soluzione per affrontare i problemi computazionali relativi agli alberi decisionali, inclusa la determinazione dell'equivalenza predittiva. Il loro metodo utilizza il rinomato metodo di Quine-McCluskey (QM) per ottenere una rappresentazione DNF minima dell'albero decisionale, successivamente utilizzata per confrontare l'equivalenza predittiva. Tuttavia, il problema della minimizzazione delle formule è difficile per il secondo livello della gerarchia polinomiale, e il metodo QM può presentare complessità di runtime e spazio esponenziale nel caso peggiore. Questo articolo dimostra innanzitutto che esistono alberi decisionali che attivano la complessità esponenziale nel caso peggiore del metodo QM; in secondo luogo, mostra che il metodo QM può giudicare erroneamente l'equivalenza predittiva se non sono soddisfatti due vincoli critici; infine, dimostra che tutti i problemi che applicano rappresentazioni DNF minime possono essere risolti in tempo polinomiale rispetto alla dimensione dell'albero decisionale.

Contesto di Ricerca e Motivazione

Definizione del Problema

Il problema centrale affrontato in questo articolo è l'efficienza e la correttezza della determinazione dell'equivalenza predittiva degli alberi decisionali. Gli alberi decisionali predittivamente equivalenti sono alberi decisionali distinti che producono gli stessi risultati di previsione per qualsiasi input.

Importanza del Problema

  1. Ottimizzazione dell'insieme di Rashomon: Nel machine learning, l'insieme di Rashomon contiene molteplici modelli con prestazioni simili. Gli alberi decisionali predittivamente equivalenti causano ridondanza in questo insieme, influenzando l'accuratezza della valutazione dell'importanza delle caratteristiche.
  2. Esigenze di Interpretabilità: Gli alberi decisionali sono ampiamente riconosciuti come modelli interpretabili, ma anche gli alberi decisionali ottimali richiedono spiegazioni formalizzate, in particolare in applicazioni ad alto rischio.
  3. Efficienza Computazionale: I metodi esistenti affrontano gravi colli di bottiglia computazionali nel trattamento di alberi decisionali su larga scala.

Limitazioni dei Metodi Esistenti

Il metodo proposto da McTavish et al., basato sull'algoritmo di Quine-McCluskey (QM), presenta i seguenti problemi:

  1. Complessità Computazionale: Il metodo QM risolve problemi Σₚ²-hard, richiedendo tempo e spazio esponenziali nel caso peggiore
  2. Problemi di Correttezza: Può produrre risultati errati quando non sono soddisfatti vincoli specifici
  3. Fattibilità Pratica: Il metodo QM è noto per avere scarsa scalabilità con problemi contenenti decine di variabili

Contributi Fondamentali

  1. Analisi Teorica: Dimostrazione dell'esistenza di alberi decisionali che attivano la complessità esponenziale nel caso peggiore del metodo QM
  2. Analisi di Correttezza: Rivelazione dei potenziali problemi di correttezza del metodo QM nella determinazione dell'equivalenza predittiva
  3. Algoritmo Efficiente: Proposizione di un algoritmo in tempo polinomiale per risolvere i problemi di completezza, concisione e determinazione dell'equivalenza predittiva
  4. Verifica Sperimentale: Su alberi decisionali che attivano il caso peggiore di QM, il nuovo algoritmo è più veloce del metodo esistente di diversi ordini di grandezza
  5. Collegamento Teorico: Stabilimento di connessioni teoriche tra equivalenza predittiva e spiegazioni logiche, misure di importanza

Dettagli del Metodo

Definizione del Compito

Dati due alberi decisionali T₁ e T₂, determinare se sono predittivamente equivalenti, cioè:

∀(x ∈ F). (κₜ₁(x) = κₜ₂(x))

dove F è lo spazio delle caratteristiche e κ è la funzione di classificazione.

Quadro Tecnico Principale

1. Metodo di Spiegazione Debole Induttiva (WAXp)

L'articolo propone un algoritmo in tempo polinomiale basato su WAXp:

Algoritmo 1: Controllo di Coerenza del Percorso

def ConsistentPath(A, P, T):
    # Controllare la coerenza dell'assegnazione parziale A con il percorso P dell'albero
    for each feature i:
        combine literals from A and P for feature i
        if inconsistent: return False
    return True

Algoritmo 2: Determinazione di WAXp

def IsWAXp(A, c, T):
    # Determinare se l'assegnazione parziale A è un WAXp per la classe c
    for each path P in T:
        if Class(P) != c and ConsistentPath(A, P, T):
            return False  # A è coerente con un percorso di altra classe
    return True

2. Algoritmo di Determinazione dell'Equivalenza Predittiva

Algoritmo 5: Determinazione dell'Equivalenza Predittiva

def PredictivelyEquivalent(T1, T2):
    for P1 in Paths(T1):
        c1 = Class(P1)
        A1 = Literals(P1)  # Creare un'assegnazione parziale
        for P2 in Paths(T2):
            c2 = Class(P2)
            if c1 != c2 and ConsistentPath(A1, P2, T2):
                return False  # Trovata evidenza di non equivalenza
    return True  # Impossibile provare non equivalenza, quindi equivalente

Punti di Innovazione Tecnica

  1. Evitare Complessità Esponenziale: Operare direttamente sulla struttura dell'albero decisionale, evitando la generazione di rappresentazioni BCF potenzialmente esponenziali
  2. Garanzia di Tempo Polinomiale: Tutti gli algoritmi hanno complessità temporale polinomiale rispetto alla dimensione dell'albero decisionale
  3. Correttezza Formalizzata: Fornire prove matematiche rigorose che garantiscono la correttezza dell'algoritmo
  4. Parallelizzabilità: L'algoritmo di equivalenza predittiva può essere parallelizzato per ulteriore miglioramento dell'efficienza

Configurazione Sperimentale

Casi di Test Costruiti

L'articolo utilizza costruzioni speciali di alberi decisionali basate sul Teorema 1:

  • Parametro r: Controlla la complessità dell'albero
  • Numero di Nodi: 6r + 3 nodi
  • Numero di Caratteristiche: 2r + 1 caratteristiche
  • Dimensione BCF: Per la classe 1, limite inferiore di 2^r implicanti primi

Metriche di Valutazione

  1. Tempo di Esecuzione: Tempo di esecuzione dell'algoritmo (secondi)
  2. Dimensione BCF: Numero di implicanti primi nella forma standard di Blake
  3. Scalabilità: Capacità di elaborare alberi decisionali di diverse dimensioni

Metodi di Confronto

  • Implementazione QM di SymPy: Metodo di riferimento utilizzato da McTavish et al.
  • Generazione BCF Indipendente: Implementazione dell'autore dei passaggi standard di generazione degli implicanti primi di QM

Dettagli di Implementazione

  • Piattaforma: Processore Macbook M3 Pro
  • Linguaggio di Programmazione: Python
  • Limite di Timeout: Limite di timeout di 150000 secondi per il metodo QM

Risultati Sperimentali

Risultati Principali

Verifica della Complessità Esponenziale del Metodo QM

rTempo SymPy(s)|BCF₀(T)||BCF₁(T)|Tempo BCF(s)
30.134220.01
40.575460.07
539.606940.84
62789.45719011.28
7>150000.008382161.25

Prestazioni di Scalabilità del Nuovo Algoritmo

rNodi DTCaratteristiche|BCF₁(T)|Un AXpisWAXp?PE?
20012034012²⁰⁰1.71s0.005s3.7s
500300310012⁵⁰⁰26.98s0.032s57.1s
1000600320012¹⁰⁰⁰224.62s0.126s469.0s

Scoperte Chiave

  1. Conferma della Crescita Esponenziale: La dimensione di BCF₁(T) cresce esponenzialmente con r, confermando l'analisi teorica
  2. Divario di Prestazioni Enorme: Per il caso r=200, il nuovo algoritmo elabora un albero decisionale di 1203 nodi in pochi secondi, mentre il metodo QM raggiunge il timeout con soli 57 nodi
  3. Verifica di Praticità: Il nuovo algoritmo può elaborare alberi decisionali su larga scala che potrebbero verificarsi in applicazioni reali

Lavori Correlati

Ricerca su Insiemi di Rashomon

  • Concetti Fondamentali: Breiman (2001) introduce per primo il concetto di insieme di Rashomon
  • Sviluppi Recenti: Lavori di Fisher et al., Semenova et al. sull'importanza delle caratteristiche
  • Equivalenza Predittiva: McTavish et al. studiano sistematicamente per la prima volta l'equivalenza predittiva degli alberi decisionali

Fondamenti Logici dell'IA Esplicativa

  • Spiegazioni Formalizzate: Lavori di Marques-Silva et al. su AXp e CXp
  • Complessità Computazionale: Ricerche che provano la complessità del calcolo delle spiegazioni
  • Misure di Interpretabilità: Applicazione di valori di Shapley e Banzhaf nel machine learning

Minimizzazione di Formule Booleane

  • Metodi Classici: Sviluppo storico dell'algoritmo di Quine-McCluskey
  • Teoria della Complessità: Stabilimento della complessità Σₚ²-hard
  • Limitazioni Pratiche: Il metodo QM è noto per avere efficienza drasticamente ridotta quando il numero di variabili supera 8

Conclusioni e Discussione

Conclusioni Principali

  1. Contributo Teorico: Dimostrazione che il metodo QM incontra effettivamente complessità esponenziale su alberi decisionali
  2. Contributo Algoritmico: Fornitura di un algoritmo alternativo in tempo polinomiale
  3. Valore Pratico: Il nuovo algoritmo presenta vantaggi significativi nelle applicazioni pratiche
  4. Collegamento Teorico: Stabilimento di connessioni tra equivalenza predittiva e molteplici concetti di XAI

Limitazioni

  1. Implementazione Python: Gli esperimenti utilizzano Python, il che potrebbe influenzare la valutazione dei valori assoluti di prestazione
  2. Costruzioni Speciali: Gli esperimenti si concentrano principalmente su alberi decisionali costruiti appositamente
  3. Parallelizzazione: Il potenziale di parallelizzazione dell'algoritmo di equivalenza predittiva non è stato verificato su cluster su larga scala
  4. Generalità: Sono necessarie ulteriori verifiche su dataset reali

Direzioni Future

  1. Algoritmi Asintoticamente Ottimali: Ricerca di algoritmi teoricamente ottimali
  2. Altri Tipi di Modelli: Estensione del metodo ad altri modelli interpretabili
  3. Applicazioni Pratiche: Applicazione nell'ottimizzazione effettiva degli insiemi di Rashomon
  4. Implementazione Parallela: Sviluppo di implementazioni parallele su larga scala

Valutazione Approfondita

Punti di Forza

  1. Rigore Teorico: Fornisce prove matematiche complete e analisi di complessità
  2. Alto Valore Pratico: Risolve i problemi di prestazione fondamentali dei metodi esistenti
  3. Forte Innovazione: Prima analisi sistematica dei problemi del metodo QM su alberi decisionali
  4. Sperimentazione Completa: Sia verifica di costruzioni teoriche che test su scala pratica
  5. Scrittura Chiara: Struttura articolo ben organizzata, dettagli tecnici chiaramente descritti

Insufficienze

  1. Portata Sperimentale: Verifica principalmente su casi di test costruiti, mancanza di risultati su dataset reali
  2. Linguaggio di Implementazione: L'uso di Python potrebbe non essere la scelta migliore, influenzando la convincibilità del confronto di prestazioni
  3. Verifica Applicativa: Mancanza di verifica in compiti di ottimizzazione effettiva degli insiemi di Rashomon
  4. Analisi dei Vincoli QM: Analisi insufficiente della raggiungibilità pratica dei vincoli di correttezza del metodo QM

Impatto

  1. Valore Accademico: Fornisce nuovi strumenti teorici per la ricerca su alberi decisionali
  2. Significato Pratico: Potrebbe cambiare i metodi pratici di analisi degli insiemi di Rashomon
  3. Riproducibilità: Descrizione dell'algoritmo chiara, facile da riprodurre
  4. Estensibilità: Il metodo potrebbe essere applicabile ad altri modelli interpretabili

Scenari Applicabili

  1. Applicazioni ad Alto Rischio: Campi come medicina e finanza che richiedono IA interpretabile
  2. Selezione di Modelli: Scenari che richiedono la selezione da molteplici modelli equivalenti
  3. Analisi dell'Importanza delle Caratteristiche: Applicazioni che richiedono valutazione accurata dell'importanza delle caratteristiche
  4. Applicazioni Industriali: Elaborazione di alberi decisionali complessi in applicazioni industriali

Riferimenti Bibliografici

L'articolo cita ampi lavori correlati, principalmente includenti:

  1. Insiemi di Rashomon: Breiman (2001), Xin et al. (2022), Fisher et al. (2019)
  2. IA Esplicativa Logica: Marques-Silva (2022), Darwiche (2023), Ignatiev et al. (2019)
  3. Minimizzazione di Funzioni Booleane: Quine (1952, 1955), McCluskey (1956), Umans (1998)
  4. Ottimizzazione di Alberi Decisionali: Bertsimas & Dunn (2017), Hu et al. (2019), Demirovic et al. (2022)

Valutazione Complessiva: Questo è un articolo di alta qualità che combina teoria e pratica, non solo rivelando i difetti fondamentali dei metodi esistenti ma fornendo anche soluzioni pratiche. L'analisi teorica dell'articolo è rigorosa, la verifica sperimentale è completa, e apporta contributi significativi al campo degli alberi decisionali e dell'IA interpretabile.