Learning Interpretable Classification Rules via Boolean Compressed Sensing

• Activity Number: 468
• Type: Invited
• Date/Time: Wednesday, August 12, 2015 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Dmitry Malioutov* and Kush Varshney and Sanjeeb Dash
• Companies: IBM Research and IBM Research and IBM Research
• Keywords: classification rules ; Boolean compressed sensing ; LP relaxation ; interpretable

Abstract

Many powerful classification methods, such as random forests or neural networks, provide little insight into how the results are obtained, and can be viewed as black box learning systems. This limits their adoption in management settings where decision makers may have limited training in statistics. However, simple interpretable techniques such as logistic regression or decision rules may not match their impressive performance. We propose a rule-based classification system based on ideas from Boolean compressed sensing that allows to strike a balance between classification accuracy and interpretability. We represent the problem of learning individual conjunctive clauses or individual disjunctive clauses as Boolean group testing, and apply a novel linear programming relaxation to find solutions. We derive results for exact rule recovery which parallel the conditions for recovery of sparse signals in the compressed sensing literature. In contrast, most prior in rule learning had focused on heuristic solutions. Furthermore we construct rule sets from these learned clauses using set covering and boosting. We show competitive classification accuracy using the proposed approach.