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

決定木の効率的で正確な予測等価性

基本情報

論文ID: 2509.17774
タイトル: Efficient & Correct Predictive Equivalence for Decision Trees
著者: João Marques-Silva (ICREA & University of Lleida)、Alexey Ignatiev (Monash University)
分類: cs.AI cs.LG cs.LO
発表時期/会議: Journal of Machine Learning Research 23 (2025) 1-35
論文リンク: https://arxiv.org/abs/2509.17774

要約

決定木のラシモン集合は重要な応用価値を有している。最近の研究により、同一の分類関数を計算する決定木（すなわち予測等価決定木）がラシモン集合の大部分を占める可能性があることが示されている。このような冗長性は望ましくなく、例えばラシモン集合に基づく特徴重要度がこのような予測等価決定木の存在により不正確になる可能性がある。McTavishら最近の研究では、決定木関連の計算問題を解決するための方法が提案されており、予測等価決定木の判定も含まれている。彼らの方法は、有名なQuine-McCluskey (QM)法を使用して決定木の最小DNF表現を取得し、その後決定木の予測等価性を比較するために使用される。しかし、公式最小化問題は多項式階層の第2層に対してNP困難であり、QM法は最悪ケースにおいて指数的な実行時間と空間複雑性を示す可能性がある。本論文は、第一に、QM法の最悪ケース指数複雑性を引き起こす決定木が存在することを証明し、第二に、2つの重要な制約が満たされない場合、QM法が予測等価性を誤って判定する可能性があることを示し、第三に、最小DNF表現を適用するすべての問題が決定木のサイズの多項式時間で解決できることを証明する。

研究背景と動機

問題定義

本論文が解決する中核的な問題は、決定木の予測等価性判定の効率性と正確性である。予測等価な決定木とは、任意の入力に対して同一の予測結果を生成する異なる決定木を指す。

問題の重要性

ラシモン集合の最適化：機械学習において、ラシモン集合は性能が類似した複数のモデルを含む。予測等価な決定木はこの集合内に冗長性を生じさせ、特徴重要度評価の正確性に影響を与える。
解釈可能性の要件：決定木は広く解釈可能なモデルとして認識されているが、最適な決定木であっても形式的な説明が必要であり、特に高リスク応用シナリオにおいてそうである。
計算効率：既存の方法は大規模決定木の処理において深刻な計算ボトルネックに直面している。

既存方法の限界

McTavishらが提案した方法はQuine-McCluskey (QM)アルゴリズムに基づいており、以下の問題が存在する：

計算複雑性：QM法はΣₚ²-困難問題を解くため、最悪ケースでは指数時間と空間が必要
正確性の問題：特定の制約が満たされない場合、誤った結果が生じる可能性がある
実用性：数十個の変数を持つ問題に対して、QM法の拡張性は既知のように不良である

核心的貢献

理論分析：QM法の最悪ケース指数複雑性を引き起こす決定木が存在することを証明
正確性分析：予測等価性判定におけるQM法の潜在的な不正確性の問題を明らかにした
高効率アルゴリズム：完全性、簡潔性、予測等価性判定の問題を解決する多項式時間アルゴリズムを提案
実験検証：QM法の最悪ケースを引き起こす決定木において、新しいアルゴリズムは既存方法より数桁高速
理論的関連性：予測等価性と論理的説明、重要度測定との間の理論的関連性を確立

方法の詳細

タスク定義

2つの決定木T₁とT₂が与えられたとき、それらが予測等価であるかどうかを判定する。すなわち：

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

ここでFは特徴空間、κは分類関数である。

核心的技術フレームワーク

1. 弱帰納的説明 (WAXp) 方法

論文はWAXpに基づく多項式時間アルゴリズムを提案している：

アルゴリズム1：パス一貫性チェック

def ConsistentPath(A, P, T):
    # 部分割り当てAとツリーパスPの一貫性をチェック
    for each feature i:
        combine literals from A and P for feature i
        if inconsistent: return False
    return True

アルゴリズム2：WAXp判定

def IsWAXp(A, c, T):
    # 部分割り当てAがクラスcのWAXpであるかどうかを判定
    for each path P in T:
        if Class(P) != c and ConsistentPath(A, P, T):
            return False  # Aは他のクラスパスと一貫している
    return True

2. 予測等価性判定アルゴリズム

アルゴリズム5：予測等価性判定

def PredictivelyEquivalent(T1, T2):
    for P1 in Paths(T1):
        c1 = Class(P1)
        A1 = Literals(P1)  # 部分割り当てを作成
        for P2 in Paths(T2):
            c2 = Class(P2)
            if c1 != c2 and ConsistentPath(A1, P2, T2):
                return False  # 非等価の証拠を発見
    return True  # 非等価を証明できないため、等価である

技術的革新点

指数複雑性の回避：可能性のある指数サイズのBCF表現の生成を避け、決定木構造上で直接操作
多項式時間保証：すべてのアルゴリズムの時間複雑性は決定木サイズの多項式
形式的正確性：アルゴリズムの正確性を保証する厳密な数学的証明を提供
並列化可能性：予測等価性アルゴリズムは並列化可能であり、さらなる効率向上が可能

実験設定

構築されたテストケース

論文は定理1の証明に基づいた特殊な決定木構造を使用：

パラメータr：ツリーの複雑性を制御
ノード数：6r + 3個のノード
特徴数：2r + 1個の特徴
BCFサイズ：クラス1の場合、2^r個の主蕴含項の下限

評価指標

実行時間：アルゴリズム実行時間（秒）
BCFサイズ：Blake標準形式における主蕴含項の数量
スケーラビリティ：異なる規模の決定木を処理する能力

比較方法

SymPyのQM実装：McTavishらが使用したベンチマーク方法
独立BCF生成：著者が実装した標準QM主蕴含項生成ステップ

実装詳細

プラットフォーム：Macbook M3 Proプロセッサ
プログラミング言語：Python
タイムアウト設定：QM法は150000秒のタイムアウト制限を設定

実験結果

主要結果

QM法の指数複雑性の検証

r	SymPy時間(s)	\|BCF₀(T)\|	\|BCF₁(T)\|	BCF時間(s)
3	0.13	4	22	0.01
4	0.57	5	46	0.07
5	39.60	6	94	0.84
6	2789.45	7	190	11.28
7	>150000.00	8	382	161.25

新しいアルゴリズムの拡張性能

r	DTノード数	特徴数	\|BCF₁(T)\|	1つのAXp	isWAXp?	PE?
200	1203	401	2²⁰⁰	1.71s	0.005s	3.7s
500	3003	1001	2⁵⁰⁰	26.98s	0.032s	57.1s
1000	6003	2001	2¹⁰⁰⁰	224.62s	0.126s	469.0s

主要な発見

指数増加の確認：BCF₁(T)のサイズはrに対して指数的に増加し、理論分析を検証
巨大な性能差：r=200の場合、新しいアルゴリズムは1203個のノードを持つ決定木をわずか数秒で処理できるのに対し、QM法は57個のノードでタイムアウト
実用性の検証：新しいアルゴリズムは実際の応用で発生する可能性のある大規模決定木を処理可能