arXiv：cs.LG· Thomas Pammer, Johannes F\"urnkranz, Markus Sinnl·· 2 小时前
用混合整数线性规划优化稀疏布尔规则网络
Optimizing Sparse Boolean Rule Networks using Mixed Integer Linear Programming
AI 导读
研究提出用混合整数线性规划（MILP）训练稀疏析取范式（DNF）网络，在固定网络结构下求解最优权重，并通过正则化目标显式权衡误分类成本与稀疏性。其增强公式大幅减少整数决策变量并消除冗余约束，同时保持布尔语义精确，还结合初始化与 dropout 打破规则间权重对称性。在合成基准和 UCI 数据集上，该公式提升了计算效率，精度与 SAT-based DNF 学习及规则、树模型等可解释基线相当或更优。
正文
Abstract:We study the problem of learning accurate and cognitively simple binary classifiers that are directly interpretable as Boolean rules. We propose mixed integer linear programming (MILP) formulations for training sparse disjunctive normal form (DNF) networks, viewed as small networks with a conjunctive hidden layer and a disjunctive output layer. Contrary to previous work that uses MILP for inductive rule learning, we start with a fixed network structure, for which we then find optimal weights. A regularized objective explicitly trades off misclassification costs against sparsity, yielding globally optimized rule sets. Our main technical contribution is an enhanced formulation that substantially reduces the number of integer decision variables and eliminates redundant constraints, while preserving exact Boolean semantics for all feasible solutions. Furthermore, we develop a combined approach based on initialization and dropout to break symmetries in the weights between rules, mitigating redundancy, and encouraging more diverse and stable rule representations. Experiments on synthetic benchmarks and UCI datasets show that the advanced formulation improves computational efficiency and achieves competitive or superior accuracy compared to established interpretable baselines, including SAT-based DNF learning and well-known rule- and tree-based learners. Overall, our approach provides a principled optimization framework for learning compact Boolean rule sets with explicit control over accuracy and sparsity trade-offs.
| Comments: | Preprint (submitted version, prior to peer review) of a paper accepted at RuleML+RR 2026, to appear in LNCS |
| Subjects: | Machine Learning (cs.LG); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.20170 [cs.LG] |
| (or arXiv:2610.20170v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.20170 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Thomas Pammer MSc. [view email]
[v1]
Wed, 14 Oct 2026 13:19:59 UTC (52 KB)
来源：arXiv：cs.LG · arxiv.org