Learning Optimized Or's of And's

By Tong Wang, Cynthia Rudin. 2015

25 citations recorded by the source corpus.

Or's of And's (OA) models are comprised of a small number of disjunctions of conjunctions, also called disjunctive normal form. An example of an OA model is as follows: If ($x_1 = $ `blue' AND $x_2=$ `middle') OR ($x_1 = $ `yellow'), then predict $Y=1$, else predict $Y=0$. Or's of And's models have the advantage of being interpretable to human experts, since they are a set of conditions that concisely capture the characteristics of a specific subset of data. We present two optimization-based machine learning frameworks for constructing OA models, Optimized OA (OOA) and its faster version, Optimized OA with Approximations (OOAx). We prove theoretical bounds on the properties of patterns in an OA model. We build OA models as a diagnostic screening tool for obstructive sleep apnea, that achieves high accuracy with a substantial gain in interpretability over other methods.

Subfields: Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistical Learning Theory

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, background): “Sometimes decision lists or decision sets are optimized by sampling (Letham et al., 2015; Yang et al., 2017; Wang and Rudin, 2015a), providing a Bayesian interpretation.”
Boolean Decision Rules via Column Generation (2018, methodology): “A greedy forward-backward algorithm [33], simulated annealing [52], or integer programming (IP) (in an unpublished manuscript [51]) are then used to select rules from the candidates.”
Optimal Generalized Decision Trees via Integer Programming (2016, background): “etween the misclassiﬁcation rate and the number of literals that appear in the “or of and’s”. The work in [18] remarks on the relationship between this problem and learning optimal decision trees. In [18], for the sake of computational eﬃciency, the authors ultimately resort to optimally selecting f”
Interpretable Optimal Stopping (2018, background): “Another stream of research considers the design of disjunctive rules and rule lists; recent examples include Wang et al. (2015), Wang and Rudin (2015), Wang et al. (2017), Letham et al. (2015), Angelino et al. (2017) and Lakkaraju et al. (2016).”
Learning sparse two-level boolean rules (2016, methodology): “In addition, the greedy style of the set covering method in [15] leaves room for improvement, and the additive combination of clauses in boosted classiﬁers reduces interpretability.”
Optimal decision trees for categorical data via integer programming (2021, background): “In particular, [18] considered the problem of learning optimal “or’s of and’s”, which fits into the problem of learning optimal disjunctive normal forms (DNFs), where optimality is measured by a trade-off between the misclassification rate and the number of literals that appear in the “or of and’s”.”