Boolean Decision Rules via Column Generation

2018-05-24 · NeurIPS 2018 12 · Sanjeeb Dash, Oktay Günlük, Dennis Wei

This paper considers the learning of Boolean rules in either disjunctive normal form (DNF, OR-of-ANDs, equivalent to decision rule sets) or conjunctive normal form (CNF, AND-of-ORs) as an interpretable model for classification. An integer program is formulated to optimally trade classification accuracy for rule simplicity. Column generation (CG) is used to efficiently search over an exponential number of candidate clauses (conjunctions or disjunctions) without the need for heuristic rule mining. This approach also bounds the gap between the selected rule set and the best possible rule set on the training data. To handle large datasets, we propose an approximate CG algorithm using randomization. Compared to three recently proposed alternatives, the CG algorithm dominates the accuracy-simplicity trade-off in 7 out of 15 datasets. When maximized for accuracy, CG is competitive with rule learners designed for this purpose, sometimes finding significantly simpler solutions that are no less accurate.

📄 PDF Abstract BibTeX arXiv:1805.09901

Code (0)

등록된 구현이 없습니다.

Tasks

General Classification

Interpretable and Fair Boolean Rule Sets via Column Generation

2021-11-16 · Connor Lawless, Sanjeeb Dash, Oktay Gunluk, Dennis Wei

This paper considers the learning of Boolean rules in disjunctive normal form (DNF, OR-of-ANDs, equivalent to decision rule sets) as an interpretable model for classification. An integer program is formulated to optimall…

Classification Fairness

Fair Decision Rules for Binary Classification

2021-07-03 · Connor Lawless, Oktay Gunluk

In recent years, machine learning has begun automating decision making in fields as varied as college admissions, credit lending, and criminal sentencing. The socially sensitive nature of some of these applications toget…

Binary Classification Classification Decision Making Fairness

On the Computational Intelligibility of Boolean Classifiers

2021-04-13 · Gilles Audemard, Steve Bellart, Louenas Bounia, Frédéric Koriche 외

In this paper, we investigate the computational intelligibility of Boolean classifiers, characterized by their ability to answer XAI queries in polynomial time. The classifiers under consideration are decision trees, DNF…

Explainable Artificial Intelligence (XAI)

A Deep Reinforcement Learning Framework For Column Generation

2022-06-03 · Cheng Chi, Amine Mohamed Aboussalah, Elias B. Khalil, Juyoung Wang 외

Column Generation (CG) is an iterative algorithm for solving linear programs (LPs) with an extremely large number of variables (columns). CG is the workhorse for tackling large-scale \textit{integer} linear programs, whi…

Decision Making Deep Reinforcement Learning reinforcement-learning Reinforcement Learning+2

Explaining Network Intrusion Detection System Using Explainable AI Framework

2021-03-12 · Shraddha Mane, Dattaraj Rao

Cybersecurity is a domain where the data distribution is constantly changing with attackers exploring newer patterns to attack cyber infrastructure. Intrusion detection system is one of the important layers in cyber safe…

BIG-bench Machine Learning Intrusion Detection Network Intrusion Detection