A scalable two stage approach to computing optimal decision sets

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

8 Citations (Scopus)


Machine learning (ML) is ubiquitous in modern life. Since it is being deployed in technologies that affect our privacy and safety, it is often crucial to understand the reasoning behind its decisions, warranting the need for explainable AI. Rule-based models, such as decision trees, decision lists, and decision sets, are conventionally deemed to be the most interpretable. Recent work uses propositional satisfiability (SAT) solving (and its optimization variants) to generate minimum-size decision sets. Motivated by limited practical scalability of these earlier methods, this paper proposes a novel approach to learn minimum-size decision sets by enumerating individual rules of the target decision set independently of each other, and then solving a set cover problem to select a subset of rules. The approach makes use of modern maximum satisfiability and integer linear programming technologies. Experiments on a wide range of publicly available datasets demonstrate the advantage of the new approach over the state of the art in SAT-based decision set learning.

Original languageEnglish
Title of host publicationProceedings of the AAAI Conference on Artificial Intelligence, AAAI-21
EditorsKevin Leyton-Brown, Mausam
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages9
ISBN (Electronic)9781577358664
Publication statusPublished - 2021
EventAAAI Conference on Artificial Intelligence 2021 - Online, United States of America
Duration: 2 Feb 20219 Feb 2021
Conference number: 35th
https://aaai.org/Conferences/AAAI-21/ (Website)

Publication series

Name35th AAAI Conference on Artificial Intelligence, AAAI 2021
PublisherAssociation for the Advancement of Artificial Intelligence
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468


ConferenceAAAI Conference on Artificial Intelligence 2021
Abbreviated titleAAAI 2021
Country/TerritoryUnited States of America
Internet address


  • Satisfiability
  • Rule Mining & Pattern Mining
  • Classification and Regression
  • Knowledge Representation Languages

Cite this