Learning Optimized Or's of And's

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.

• Publication year

  2015

• Venue

  arXiv.org

• Publication date

  2015-11-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1511.02210
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Clinical Prediction Models for Sleep Apnea: The Importance of Medical History over Symptoms

  2016cited by this paper
• Or's of And's for Interpretable Classification, with Application to Context-Aware Recommender Systems

  2015cited by this paper
• Supersparse linear integer models for optimized medical scoring systems

  2015cited by this paper
• Logic, probability, and human reasoning.

  2015cited by this paper
• Inductive Logic Programming

  2014influential reference
• Disjunctions of Conjunctions, Cognitive Simplicity, and Consideration Sets

  2010influential reference
• Discriminative Frequent Pattern Analysis for Effective Classification

  2007cited by this paper
• A new approach to classification based on association rule mining

  2006cited by this paper
• An implementation of the FP-growth algorithm

  2005cited by this paper
• A Choice Model with Conjunctive, Disjunctive, and Compensatory Screening Rules

  2004cited by this paper
• Learning DNF in time 2Õ(n1/3)

  2004cited by this paper
• CPAR: Classification based on Predictive Association Rules

  2003cited by this paper
• CMAR: accurate and efficient classification based on multiple class-association rules

  2001cited by this paper
• Learning DNF in time 2 Õ(n 1/3 ) .

  2001cited by this paper
• Mining frequent patterns without candidate generation

  2000influential reference
• Integrating Classification and Association Rule Mining

  1998cited by this paper
• Fast Algorithms for Mining Association Rules

  1998cited by this paper
• New Algorithms for Fast Discovery of Association Rules

  1997cited by this paper
• Fast Effective Rule Induction

  1995cited by this paper
• Inductive Logic Programming: Theory and Methods

  1994cited by this paper
• A general lower bound on the number of examples needed for learning

  1988influential reference
• Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm

  1987influential reference
• Judgment under uncertainty: The robust beauty of improper linear models in decision making

  1982cited by this paper
• The magical number seven plus or minus two: some limits on our capacity for processing information.

  1956cited by this paper

• Bias Detection via Maximum Subgroup Discrepancy

  2025cites this paper
• A unified approach to extract interpretable rules from tree ensembles via Integer Programming

  2024cites this paper
• Efficient Exploration of the Rashomon Set of Rule-Set Models

  2024cites this paper
• Efficient Decision Rule List Learning via Unified Sequence Submodular Optimization

  2024cites this paper
• MimicAI: An LLM based system that mimics and explains

  2024cites this paper
• Boolformer: Symbolic Regression of Logic Functions with Transformers

  2023cites this paper
• Explainable AI using expressive Boolean formulas

  2023cites this paper
• Explainable AI for clinical risk prediction: a survey of concepts, methods, and modalities

  2023cites this paper
• An Adaptive Framework for Confidence-constraint Rule Set Learning Algorithm in Large Dataset

  2022cites this paper
• Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach

  2022cites this paper
• Interpretable and Fair Boolean Rule Sets via Column Generation

  2021cites this paper
• Optimal decision trees for categorical data via integer programming

  2021influential citation
• Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges

  2021cites this paper
• Discovering Classification Rules for Interpretable Learning with Linear Programming

  2021cites this paper
• Fair Decision Rules for Binary Classification

  2021cites this paper
• Iterative Rule Extension for Logic Analysis of Data: an MILP-based heuristic to derive interpretable binary classification from large datasets

  2021cites this paper
• Interpretable Clustering via Multi-Polytope Machines

  2021cites this paper
• Rule generation for classification: Scalability, interpretability, and fairness

  2021cites this paper
• Fair and Interpretable Decision Rules for Binary Classification

  2020cites this paper
• Interpretable Optimal Stopping

  2018cites this paper
• Boolean Decision Rules via Column Generation

  2018cites this paper
• Optimal Generalized Decision Trees via Integer Programming

  2016cites this paper
• Learning sparse two-level boolean rules

  2016cites this paper
• Finding patterns in features and observations: new machine learning models with applications in computational criminology, marketing, and medicine

  2016cites this paper
• Interpretable Two-level Boolean Rule Learning for Classification

  2015cites this paper