Research map / Adversarial robustness and security / Certified and empirical robustness
Robustness Verification of Multi-Class Tree Ensembles
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that one-versus-other reduction fails for multiclass tree ensemble robustness verification and proposes a multiclass search-based heuristic (extending VERITAS) with a proven consistent heuristic and open-source implementation.
Problem
Robustness verification of multiclass tree ensembles is handled by reducing to binary one-versus-other subproblems, which can return incorrect results for targeted evasion decision problems.
Approach
Generalizes VERITAS's binary search-based verification to reason about all classes simultaneously via a multiclass scoring function (max over target class vs. min/max over competing classes), with a proof of heuristic consistency, instead of solving independent one-versus-other subproblems.
Key results
- One-versus-other reduction yields inconclusive results in 7% to 30% of instances for GBDT and 9% to 27% for RF on the benchmark datasets (1.8% and 5.3% on img).
- Multiclass approach is considerably slower than one-versus-other for GBDT, but for RF it is competitive and even faster on wine, mnist, letter and sensorless.
- Proves that the one-versus-other reduction cannot solve the targeted evasion decision problem (Theorem 1) and proves consistency of the new multiclass heuristic (Theorem 2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use one-versus-other subproblems instead of reasoning across all classes simultaneously | Targeted evasion verification for multiclass tree ensembles · Seven benchmark datasets | inconclusive result rate: 7% to 30% of the time | Hurt |
| Use one-versus-other reduction rather than multiclass search | GBDT targeted evasion verification · Benchmark datasets | time (seconds) | Mixed |
| Use multiclass search rather than one-versus-other reduction | RF targeted evasion verification · wine, mnist, letter, sensorless | time (seconds) | Helped |
Surprising findings
- Naively applying one-versus-other reduction can yield incorrect verification results for multiclass tree ensembles, with solutions to all C-1 subproblems existing without any simultaneous solution.
- Inconclusive results occur more frequently for RF than GBDT, especially for unsatisfiable instances.
Limitations
- Verification is NP-hard, so the heuristic is approximate and may time out on hard instances; experiments tuned to avoid timeouts.
- Multiclass approach is considerably slower than one-versus-other for GBDT ensembles.
Experimental setup
Datasets: img (synthetic) wine bean mnist letter pendigits sensorless
Benchmarks: img wine bean mnist letter pendigits sensorless
Metrics: fraction satisfiable/unsatisfiable/inconclusive targeted eva average run time per instance
Baselines: one-versus-other reduction with VERITAS
Builds on: VERITAS Kantchelian et al. MILP attack A* search heuristic (Hart et al.) Chen et al. K-partite graph verification
Closest papers by meaning
- Robustness Verification of Tree-based Models (NeurIPS 2019 · similarity 0.92)
- Abstract Interpretation of Decision Tree Ensemble Classifiers (AAAI 2020 · similarity 0.90)
- Versatile Verification of Tree Ensembles (ICML 2021 · similarity 0.90)
- Faster Repeated Evasion Attacks in Tree Ensembles (NeurIPS 2024 · similarity 0.88)
- Sensitivity Verification for Additive Decision Tree Ensembles (ICLR 2025 · similarity 0.88)
- Probably Approximately Global Robustness Certification (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.