Efficient Learning of Interpretable Classification Rules
- URL: http://arxiv.org/abs/2205.06936v1
- Date: Sat, 14 May 2022 00:36:38 GMT
- Title: Efficient Learning of Interpretable Classification Rules
- Authors: Bishwamittra Ghosh, Dmitry Malioutov, Kuldeep S. Meel
- Abstract summary: This paper contributes an interpretable learning framework IMLI, that is based on maximum satisfiability (MaxSAT) for classification rules expressible in proposition logic.
In our experiments, IMLI achieves the best balance among prediction accuracy, interpretability, and scalability.
- Score: 34.27987659227838
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Machine learning has become omnipresent with applications in various
safety-critical domains such as medical, law, and transportation. In these
domains, high-stake decisions provided by machine learning necessitate
researchers to design interpretable models, where the prediction is
understandable to a human. In interpretable machine learning, rule-based
classifiers are particularly effective in representing the decision boundary
through a set of rules comprising input features. The interpretability of
rule-based classifiers is in general related to the size of the rules, where
smaller rules are considered more interpretable. To learn such a classifier,
the brute-force direct approach is to consider an optimization problem that
tries to learn the smallest classification rule that has close to maximum
accuracy. This optimization problem is computationally intractable due to its
combinatorial nature and thus, the problem is not scalable in large datasets.
To this end, in this paper we study the triangular relationship among the
accuracy, interpretability, and scalability of learning rule-based classifiers.
The contribution of this paper is an interpretable learning framework IMLI,
that is based on maximum satisfiability (MaxSAT) for synthesizing
classification rules expressible in proposition logic. Despite the progress of
MaxSAT solving in the last decade, the straightforward MaxSAT-based solution
cannot scale. Therefore, we incorporate an efficient incremental learning
technique inside the MaxSAT formulation by integrating mini-batch learning and
iterative rule-learning. In our experiments, IMLI achieves the best balance
among prediction accuracy, interpretability, and scalability. As an
application, we deploy IMLI in learning popular interpretable classifiers such
as decision lists and decision sets.
Related papers
- STAND: Data-Efficient and Self-Aware Precondition Induction for Interactive Task Learning [0.0]
STAND is a data-efficient and computationally efficient machine learning approach.
It produces better classification accuracy than popular approaches like XGBoost.
It produces a measure called instance certainty that can predict increases in holdout set performance.
arXiv Detail & Related papers (2024-09-11T22:49:38Z) - Optimized Feature Generation for Tabular Data via LLMs with Decision Tree Reasoning [53.241569810013836]
We propose a new framework based on large language models (LLMs) and decision Tree reasoning (OCTree)
Our key idea is to leverage LLMs' reasoning capabilities to find good feature generation rules without manually specifying the search space.
Our empirical results demonstrate that this simple framework consistently enhances the performance of various prediction models.
arXiv Detail & Related papers (2024-06-12T08:31:34Z) - An Incremental MaxSAT-based Model to Learn Interpretable and Balanced Classification Rules [0.0]
This work aims to propose an incremental model for learning interpretable and balanced rules based on MaxSAT.
The approach based on MaxSAT, called IMLI, presents a technique to increase performance that involves learning a set of rules by incrementally applying the model in a dataset.
arXiv Detail & Related papers (2024-03-25T04:43:47Z) - Machine Learning with Probabilistic Law Discovery: A Concise
Introduction [77.34726150561087]
Probabilistic Law Discovery (PLD) is a logic based Machine Learning method, which implements a variant of probabilistic rule learning.
PLD is close to Decision Tree/Random Forest methods, but it differs significantly in how relevant rules are defined.
This paper outlines the main principles of PLD, highlight its benefits and limitations and provide some application guidelines.
arXiv Detail & Related papers (2022-12-22T17:40:13Z) - Stabilizing Q-learning with Linear Architectures for Provably Efficient
Learning [53.17258888552998]
This work proposes an exploration variant of the basic $Q$-learning protocol with linear function approximation.
We show that the performance of the algorithm degrades very gracefully under a novel and more permissive notion of approximation error.
arXiv Detail & Related papers (2022-06-01T23:26:51Z) - How Fine-Tuning Allows for Effective Meta-Learning [50.17896588738377]
We present a theoretical framework for analyzing representations derived from a MAML-like algorithm.
We provide risk bounds on the best predictor found by fine-tuning via gradient descent, demonstrating that the algorithm can provably leverage the shared structure.
This separation result underscores the benefit of fine-tuning-based methods, such as MAML, over methods with "frozen representation" objectives in few-shot learning.
arXiv Detail & Related papers (2021-05-05T17:56:00Z) - Rule Generation for Classification: Scalability, Interpretability, and Fairness [0.0]
We propose a new rule-based optimization method for classification with constraints.
We address interpretability and fairness by assigning cost coefficients to the rules and introducing additional constraints.
The proposed method exhibits a good compromise between local interpretability and fairness on the one side, and accuracy on the other side.
arXiv Detail & Related papers (2021-04-21T20:31:28Z) - A Scalable Two Stage Approach to Computing Optimal Decision Sets [29.946141040012545]
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 to generate minimum-size decision sets.
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.
arXiv Detail & Related papers (2021-02-03T06:51:49Z) - Fast Few-Shot Classification by Few-Iteration Meta-Learning [173.32497326674775]
We introduce a fast optimization-based meta-learning method for few-shot classification.
Our strategy enables important aspects of the base learner objective to be learned during meta-training.
We perform a comprehensive experimental analysis, demonstrating the speed and effectiveness of our approach.
arXiv Detail & Related papers (2020-10-01T15:59:31Z) - Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
Partial-label learning (PLL) is a typical weakly supervised learning problem, where each training instance is equipped with a set of candidate labels among which only one is the true label.
Most existing methods elaborately designed as constrained optimizations that must be solved in specific manners, making their computational complexity a bottleneck for scaling up to big data.
This paper proposes a novel framework of classifier with flexibility on the model and optimization algorithm.
arXiv Detail & Related papers (2020-02-19T08:35:15Z) - IMLI: An Incremental Framework for MaxSAT-Based Learning of
Interpretable Classification Rules [40.497133083839664]
We propose IMLI: an incremental approach to MaxSAT based framework that achieves scalable runtime performance.
IMLI achieves up to three orders of magnitude runtime improvement without loss of accuracy and interpretability.
arXiv Detail & Related papers (2020-01-07T05:03:53Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.