Exact Rule Learning via Boolean Compressed Sensing

By Dmitry M. Malioutov, Kush R. Varshney. 2013

95 citations recorded by the source corpus.

Subfields: Statistical Learning Theory, Algorithms & Complexity

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

In Algorithms & Complexity

Citations in the corpus

Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges (2021, methodology): “Associative classification methods assemble decision lists or decision sets from a set of pre-mined rules, generally either by greedily adding rules to the model one by one, or simply including all “top-scoring” rules into a decision set, where each rule is scored separately according to a scoring f”
TreeView: Peeking into Deep Neural Networks Via Feature-Space Partitioning (2016, background): “There have been deliberate efforts to develop models that are interpretable in the recent past [4], [2], [5] .”
On the Safety of Machine Learning: Cyber-Physical Systems, Decision Sciences, and Data Products (2016, methodology): “the acquired company. Speciﬁcally, C5.0 decision trees were used with the rule set option, and the project directly 15 motivated the study of an optimization approach for learning classiﬁcation rules [52]. The reason for conducting the project was to take actions such as salary increases to retain e”
IMLI: An Incremental Framework for MaxSAT-Based Learning of Interpretable Classification Rules (2019, positive): “In recent work, Malioutov et al. has proposed rule based classiﬁcation system by borrowing ideas from Boolean compressed sensing (Malioutov and Varshney 2013).”
Learning customized and optimized lists of rules with mathematical programming (2018, background): “, Malioutov and Varshney, 2013; Rudin et al, 2013; McCormick et al, 2012). Experiments of Wang and Rudin (2015); Yang et al (2017) found that the performance of inductive rule learner RIPPER (Cohen, 1995) was worse than that of other methods; rule learning methods generally do not aim to achieve or ”
MLIC: A MaxSAT-Based Framework for Learning Interpretable Classification Rules (2018, neutral): “Only recently there have been some formulations that attempt to balance the accuracy and the size of the rule in a principled optimization objective either through combinatorial optimization, linear programming (LP) relaxations, submodular optimization, or Bayesian methods [4,25,24][7,34] as we revi”
Learning Optimized Risk Scores (2016, neutral): “[70] Malioutov, Dmitry and Kush Varshney.”
Interpretable Decision Sets: A Joint Framework for Description and Prediction (2016, methodology): “Other methods attempt to construct sets with fewer rules [38, 48, 53], but again do not account for rule overlap.”
Learning Explainable Decision Rules via Maximum Satisfiability (2020, background): “A recent line of work, adapting ideas from Boolean compressed sensing, focuses on learning sparse k-cnf rules via linear programming, [9]–[11].”
Actionable Recourse in Linear Classification (2018, background): “1While transparency does not ensure recourse, simple models such as scoring systems and rule-based models [3, 28, 42, 49, 50] have the benefit that they allow end-users to check the feasibility of recourse without a computer.”
Or's of And's for Interpretable Classification, with Application to Context-Aware Recommender Systems (2015, methodology): “This form of model has some recent precedent in [16, 18, 19, 28] as a form of model that is natural for modeling consumer behavior, and interpretable to human experts.”
Optimal Generalized Decision Trees via Integer Programming (2016, background): “uthors ultimately resort to optimally selecting from a subset of candidate suboptimal DNFs learned by heuristic means rather than solving their proposed mixed-integer optimization problem. Similarly, [13] proposes learning DNF-like rules via integer optimization, and propose a formulation that can b”
Multi-Value Rule Sets (2017, methodology): “There has been a series of research on developing rule-based models for classiﬁcation [1, 3, 5, 8, 12, 17, 19, 22].”
Optimized Risk Scores (2017, methodology): “Our algorithm may be used to solve other problems with non-convex penalties and constraints, such as `0-regularized risk minimization [27], or discrete linear classication problems that minimize a convex loss over a small integers [4, 7, 24, 35].”
Optimal decision trees for categorical data via integer programming (2021, background): “Similarly, [13] proposes learning DNF-like rules via integer optimization, and propose a formulation that can be viewed as boolean compressed sensing, lending theoretical credibility to solving a linear programming relaxation of their integer problem.”
Screening for learning classification rules via Boolean compressed sensing (2014, methodology): “Ideally, one would like to consider all possible thresholds (up to the resolution of the training samples) as candidate terms for the classification rule, but this may require a large number of columns in the sensing matrix and create a large linear program (LP) in the formulation of [6].”
Learning interpretable classification rules using sequential rowsampling (2015, methodology): “…y = A V w through or dinary linear equalities and inequalities, relaxing the fo problem to the f1 problem, relaxing the binary constraint on the vector w to o ::; w ::; 1, and introducing slack variables to account for noise, the rule learning problem is captured in the following LP [1] : n m”