Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces novel mixed integer linear programming (MILP) formulations for training sparse disjunctive normal form (DNF) networks by optimizing weights on a fixed structure, directly yielding interpretable Boolean rules. The core technical contribution is an enhanced MILP formulation that significantly reduces integer variables and redundant constraints while maintaining exact Boolean semantics. Experiments demonstrate that this approach achieves competitive or superior accuracy and computational efficiency compared to existing interpretable learning methods.
Globally optimized Boolean rule sets are now achievable with explicit control over accuracy-sparsity trade-offs, thanks to a novel MILP formulation that drastically cuts down on integer variables.
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.