Scholarlink

<p>Fairness-constrained tree learning is highly desirable for high-accountability settings; however, exact combinatorial optimization is often considered computationally impractical when fairness constraints are strictly enforced. While most existing fair classification methods rely on heuristic reductions or surrogate losses, exact tree studies primarily focus on unconstrained predictive accuracy. In this paper, we propose a memoized exact-search framework for decision trees under explicit statistical-parity constraints and provide a parameterized analysis of its runtime with respect to sensitive-group cardinality. Through comprehensive evaluations—including scalability checks, caching ablations, controlled CART comparisons, benchmark repeats, and validation on real-world datasets—we demonstrate that the proposed method preserves exactness while significantly mitigating redundant computations. Our results reveal that exact fair optimization remains practically viable for scenarios with small sensitive-group regimes. Under a 10-repeat shared held-out testing protocol, memoized exact search improves test accuracy over full-training CART, same-120-subset CART, and a demographic-parity reduction baseline using depth-3 CART, while test-set statistical-parity differences remain comparable in magnitude and training-set feasibility is maintained. These findings highlight a concrete trade-off between runtime, accuracy, and parity control for small encoded optimization subsets.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Parameterized exact fair decision tree learning with small sensitive group regimes

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年8月3日

查看全文
  • Zhigao Huang,
  • Miao Pan,
  • Shiyan Zheng,
  • Yuzhuo Pan

摘要

Fairness-constrained tree learning is highly desirable for high-accountability settings; however, exact combinatorial optimization is often considered computationally impractical when fairness constraints are strictly enforced. While most existing fair classification methods rely on heuristic reductions or surrogate losses, exact tree studies primarily focus on unconstrained predictive accuracy. In this paper, we propose a memoized exact-search framework for decision trees under explicit statistical-parity constraints and provide a parameterized analysis of its runtime with respect to sensitive-group cardinality. Through comprehensive evaluations—including scalability checks, caching ablations, controlled CART comparisons, benchmark repeats, and validation on real-world datasets—we demonstrate that the proposed method preserves exactness while significantly mitigating redundant computations. Our results reveal that exact fair optimization remains practically viable for scenarios with small sensitive-group regimes. Under a 10-repeat shared held-out testing protocol, memoized exact search improves test accuracy over full-training CART, same-120-subset CART, and a demographic-parity reduction baseline using depth-3 CART, while test-set statistical-parity differences remain comparable in magnitude and training-set feasibility is maintained. These findings highlight a concrete trade-off between runtime, accuracy, and parity control for small encoded optimization subsets.