Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach
Authors: Fan Yang
Kai He
Linxiao Yang
Hongxia Du
Jingbang Yang
Bo Yang
Liang Sun
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: interpretable
rule set
submodular
rule-based model

Abstract: Rule sets are highly interpretable logical models in which the predicates for decision are expressed in disjunctive normal form (DNF, OR-of-ANDs), or, equivalently, the overall model comprises an unordered collection of if-then decision rules. In this paper, we consider a submodular optimization based approach for learning rule sets. The learning problem is framed as a subset selection task in which a subset of all possible rules needs to be selected to form an accurate and interpretable rule set. We employ an objective function that exhibits submodularity and thus is amenable to submodular optimization techniques. To overcome the difficulty arose from dealing with the exponential-sized ground set of rules, the subproblem of searching a rule is casted as another subset selection task that asks for a subset of features. We show it is possible to write the induced objective function for the subproblem as a difference of two submodular (DS) functions to make it approximately solvable by DS optimization algorithms. Overall, the proposed approach is simple, scalable, and likely to be benefited from further research on submodular optimization. Experiments on real datasets demonstrate the effectiveness of our method.

Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach
Fan Yang, Kai He, Linxiao Yang, Hongxia Du, Jingbang Yang, Bo Yang, Liang Sun DAMO Academy, Alibaba Group, Hangzhou, China (fanyang . yf, kai. he, linxia. ylx, hongxia dhx, jingbang. mwwai. yb, ww..lii...... sun] Galibaba-ing com
Abstract
Rule sets are highly interpretable logical models in which the predicates for decision are expressed in disjunctive normal form (DNF, OR-of-ANDs), or, equivalently, the overall model comprises an unordered collection of if-then decision rules. In this paper, consider submodular optimization based approach for learning rule sets. The learning problem is framed as subset selection task in which a subset of all possible rules needs be selected to form an accurate and interpretable rule set. We employ an objective function that exhibits submodularity and thus is amenable submodular optimization techniques. To overcome the difficulty arose from dealing with the exponential-siee
ground set of rules, the subproblem of searching rule casted as another subset selection task that asks for a subset of features. We show it is possible to write the induced objective function for the subproblem as a difference of two submodular (DS) functions to make it approximately solvable by DS optimization algorithms. Overall, the proposed approach is simple, scal- able, and likely to be benefited from further research on submodular optimization. Experiments real datasets demonstrate the effectiveness of our method.
Introduction
Interpretability is becoming one of the key considerations when deploying machine learning models to high-stake decision-maiee making scenarios. Black box models, such as random forests and deep neural networks, may achieve impressive prediction accuracy in practice, but it is often difficult to understand the mechanisms about how their predictions are made. Moreover, has been widely known that machine learning models are susceptible spurious correlations, which makes them not robust to distribution shifts or adversarial attacks and leads to misleading predictions. Black box models are particularly problematic here because they are hard audit and diagnose.
The development of inherently interpretable models is a longstanding attempt towards interpretable and trustable machine learning 44 43 In this paper, we consider decision rule sets for binary classification, in which if an example is tested true for Boolean condition expressed in disjunctive normal form (DNF), then predefined label is predicted for it. For instance, rule set for determining whether a patient with community-acquired pneumonia should be hospitalized may be "IF (IsChild True AND OxtuenSaturation < 0.9) OR (IsChild True AND SOB True) OR (IsAAuult True AND CURB65 > 2) THEN Yes". Rule sets are particularly suited for tabular data that contain mixed-type features and exhibit complex high-order feature interactions. When compared to other rule-based models such as decision trees and decision lists, the simpler combinatorial structure of rule sets makes them easier to interpret and to learn from data.
The learning of rule sets has attracted interest from various research communities over the past few decades. Two interplaying subset selection tasks constitute the major challenges in rule set learning. First, the construction of a rule requires choosing a subset of all features. Then a subset of all possible
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

rules has to be selected to form a rule set. In early algorithms from machine learning community, such as FOIL [4, CN2 [2] and RIPPER [13,, usually greedy sequential covering strategy is utilized, in which at each stage a rule is generated from uncovered examples using heuristics and newly covered examples are removed. Associative classification techniques [ 50] developed by data mining community take different two-stage strategy, in which large set of rules are first generated via association rule mining and then a rule set is constructed by ranking and pruning. Both these early approaches lack global objective that guides the generation of rules and optimizes the interpretability of produced rule set.
This paper presents a new submodular optimization perspective on nearly optimal rule set learning.
We employ an objective function that simultancously optimizes accuracy and interpretability. We show that given ground set of rules, this objective is regularized submodular function [27]. for
which algorithms with strong approximation guarantees have been developed recently (33 Instead
of using a pre-mined pool of rules as the ground set, we take an on-the-fly approach in which the ground set consists of all possible rules and elements are picked from it one at time through solving an optimization subproblem. When the subproblem is always solved to optimality, our learning algorithm enjoys the algorithmic guarantees for regularized submodular maximization. For most real cases the global optimum of the subproblem is impractical to reach, therefore we propose an efficient approximate algorithm based on iterative local combinatorial search.
Our contributions are summarized as follows: (i) We formulate interpretable rule set learning as regularized submodular maximization problem which is amenable approximate algorithm with strong guarantees. (ii) We discover an intuitive difference of submodular (DS) decomposition for the induced rule construction subobjective, based on which an iterative refinement algorithm is proposed to solve the subproblem approximately for large datasets. (iii) We conduct a comprehensive experimental evaluation, demonstrating the proposed approach is competitive against state-of-the-arts in both predictive performance and interpretability.
The remainder of this paper is organized as follows: Related work summarized in Section Section 3 introduces the problem formulation. Section [4 presents the algorithmic details. Experimental evaluation is reported in Section We discuss the limitations of this work in Section oand conclude the paper with Section 7
2 Related work
To discover rules from training data, heuristic sequential covering or separate-and-conquer strategy is utilized by almost all early algorithms 12 [3], in which the interpretability of final rule set is not explicitly controlled. In recent years, with the renewed interest in interpretable rule-based models, the rule set learning problem was revisited under modern optimization lens and several new algorithms were developed [22] 49 28
35| 48 [1]. These algorithms mainly follow a two-stage paradigm originating from early associative classification methods [33 [50, in which the learning problem is divided into two separate steps: rule generation and rule selection. For example, Lakkaraju et al. (28 frame the task of constructing a interpretable rule set from pre-mined rules as a submodular optimization problem and solve it approximately with a local search algorithm. In general, such two-stage paradigm suffers from the drawback that some essential rules may be filtered out prematurely.
Dash al. [4] formulate the rule set learning problem as integer program (IP) and solve its linear programming relaxation using the column generation (CG) framework [15] 17]. in which rules are instead generated on the fly by iteratively solving a IP subproblem. In this way they bridge rule generation and rule selection together as a unified optimization procedure and thus avoid the drawbacks of pre-mining. We contribute similar framework from a different submodular optimization perspective. Interestingly, subproblems in both frameworks share the same form (6). which asks the solution to cover more positively weighted samples and less negatively weighted samples. This task shares some similarities with the subgroup discovery [6] problem in data mining.
for which exhaustive search 31 heuristic beam search [30 46) and sampling 9 [0] are commonly utilized. Eckstein and Goldberg [17 designed a specialized branch-and-bour
method for the closely
related maximum monomial agreement (MMA) problem. To the best of our knowledge, we are the first to study this task from DS optimization perspective.

---

Our work is also related to optimization based learning of other rule models, such as optimal decision lists 3 4 and optimal decision trees [24
The learning of decision lists and trees is inherently much harder because their combinatorial structures are more complex than rule sets.
52]
3 Problem formulation
In this work, we consider binary classification based on set of interpretable binary features. Categor- ical features can be easily binarized via one-hot encoding, and numerical features may be binarized through bucketing or comparisons like "Age 2 18". Techniques such as one-versus-one are available for transforming multiclass classification to binary classification.
E {0, 1 a binary feature vector associated with label yı {0, 1]. The goal is to learn interpretable rule set model F: {0, 13dd + {0.1} } to predict the label. A rule set is Boolean classifier of the form "IF P(x) THEN y = ELSE y = 0", in which P(x) is a predicate restricted in disjunctive normal form (DNF) and treats raw features {z, 1 as its variables. For simplicity, the use of not (-) operator in DNF is disabled because equivalent expressivity can be achieved by creating augmented features {-zz)グ=1- Then a concrete P(x) is described as a set S C 2(4], where each element R E S is subset of [d] = {I...., d). The mapping from a S to DNF is given by Ps(x) = VRES AER Ty- We call S a rule set and call each element R of it a rule. A sample x is covered by a rule R. P(R) (x) is true. It is now clear that a rule set classifier can be simplified to y Ps(x), i.., predicts iff x is covered by at least one of the rules.
Suppose we are given the training data (x, y4 ) in which each x; =
To learn rule set from data, consider minimizing the empirical error while penalizing the complexity by solving the optimization problem:
min SC2
Σ (Ps(x:). ((5)
However, even under the simplest setting where I(..-) is the 0-1 loss and 22()) is the cardinality function, this problem is still hard to work with. To proceed, we replace Ps with a surrogate model Ps (0, 13dd + No defined as Ps(x) = ERES AJeR Tj.- Then flexible objective function that balances accuracy and interpretability is chosen to be:
L(S)= = Σ La (Ps(xi)
+ Σ |
(2)
RES
where (a((s)) a loss function with hyperparameters B (Bo. 31. (2) R²:
Buù (y 1) B2 y)
if
(0(0.))
if = 1 1 $1
if = 1A0>1
With a proper choice of hyperparameters, interpretability of the minimizer for this objective comes from two aspects: sparsity and diversity. Sparsity is obvious because of the complexity regularization term. Diversity is encouraged by the loss function through penalizing the overlap of rules. (s(x) > 1 means that x is covered by more than one of the rules, and in this case the objective function will receive penalty. Small overlap among rules benefits interpretability because it makes the decision boundaries more clear and enables people to inspect the learned rules individually.
It may not be immediately clear that L(S) is a supermodular function and thus - -L(S) is submodular function. To show this, we introduce more notations. Let X = fily, 1} and X {ily = 0} be the of positive and negative samples, respectively. Let X {ili e x+ Ps(x:)) and XS {ilii E - A (xx)) be the set of positive and negative samples covered by S, respectively. Then we have
L(S)- 30
Σ RES
+111
\X5 +
+B2
x-t
|x51
+
+
Σ
R
(R)
RES
3

---

Ignoring the weights, then the first term is the miscoverage of negative samples, the second term is the number of uncovered positive samples, the third term the overlap in positive samples, and the last term is the size of rules. After reorganizing the terms, we arrive
L(S) 31 x (3 + 32) X5 +
Σ RES
30 (R)
B2
A/R|
(3)
Then the submodularity immediately follows.
Proposition 1. L(S) is supermodular function and ((S) is a submodular functiion
Proof. The first term in 3 is constant. The second term is negative coverage, while coverage functions are well-known be submodular. The third term sums over elements of S and thus is modular. A submodular function minus modular function is still submodular, therefore - L(S)) is submodular and ((S) supermodular.
We show in the Appendix that several design choices for the original objective in ① may reduce L(S) through upper bounding surrogates, which justifies the generality of this objective function. This objective function also generalizes the Hamming loss used in previous work 44 [4]
4 Algorithms
We consider the algorithms for minimizing L(S) in this section. Define g(S) (81 + B2) [
the revenue of rule set and c(R. 3o [<)} + B2 | A|R| the cost of rule. Let V(S) = y(8) EREs c(R) be the profit of a rule set, which is equal to - up to constant.
Then minimizing L(S) is equivalent to maximizing V(S). For the sake of practicality, we further put a cardinality constraint [S] < K on this optimization problem, which limits the number of rules in the rule set. Then
max SC2
V(S)
is an instance of cardinality constrained submodular maximization problem. For non-negative mono- tone submodular functions, the greedy algorithm achieves a 1/e z 0.632 approximation ratio (38. which is the best approximation possible for this problem. However, in our case V(S) is neither non-negative nor monotone. It is possible to apply non- non-monotone submodular maximization algo- rithms [1] 20 to our problem without care of negativeness, but doing this makes their approximation guarantees invalid.
Fortunately, V(S) is the difference between a non-negative monotone submodular part g(S) and a non-negative modular part LRES c(R). Set functions with such structure, recently named regularized submodular functions [27). have been shown to be amenable to maximization procedures with strong
approximation guarantees
45 23 18 19
4.1 Regularized submodular maximization
We apply the distorted greedy algorithm proposed by Harshaw et al. 2X approximate maximization of VSS). As illustrated in Algorithm] at each iteration, a rule maximizing the marginal gain in distorted objective added the rule set its gain positive. The distorted objective adjusted in way such that initially higher importance is placed on the cost term, and then the importance gradually shifted back the revenue term. By doing this, following approximation guarantce obtained.
Proposition 2. (23) Algorithm D returns a rule set S of cardinality at most K. If the maximization subproblem line 5 is solved to optimality, then
V(S) = g(S)
Σ (L-
Σ c(R))
RES
REOPT
where OPT is the optimal solution problem

---

Algorithm Rule set learning
hyperparameters Input: Training data ((x,, hyyyrpaeesseeerrerereeeeeers (B, X), cardinality K Initialize <-
for k == to K do
Define v4 (R) = (1
<(R)
M ((R(S) = g(S U (R)) - g m/
Solve R t- arg max 2/ (R)
6 if tr (R*) > 0 then S t- U {RR) end if
end for
8 Output: S
In addition, provide algorithm in the Appendix for further refining the output of Algorithm if possible. each step, that algorithm tries to improve the objective through adding, removing, or replacing rule. The remaining question is how to solve the subproblem of marginal gain maximization, which requires search over the subsets of [d]. Naive exhaustive enumeration only works for small d, say, d < 20. For datasets with numerical features high- sighhcardinality categorical features, the preprocessing step may casily produce hundreds or thousands of binary features, making exhaustive enumeration impossible. In such cases, approximate solution should be considered and the guarantee for Al Algorithm] will no longer hold. However, we observe in practice that Al Algorithm D will still work satisfactorily if good enough solutions to the subproblem found. To this end, approximate rather than exact method is considered in this work.
4.2 Solving the subproblem
We approximately solve the marginal gain maximization subproblem through iteratively refining solution with local search until no further improvement can be made. Our local search procedure relies on decomposable structure of the subproblem to find good solutions quickly. Objective functions for the subproblem are of the general form:
u(R(S:a) ag()))) c(R)
aB1 B2) [ X55 - -Bo (R)
B2
X+
[R)
A/R|
(5)
= [a(3] + 32) - 32] XtR) X55 - 30 (R)
- 32
((R) n nx A|R|
where a E (1/e, 1] is a multiplier on the marginal gain of g set by Algorithm For notational simplicity, denote w4 (33 {2) 32. Notice that samples are partitioned into three subsets: still uncovered positive samples X'+ X each with weight w4, already covered positive samples X5 each with weight -32, and negative samples X' each with weight - -Bo As shown in the Appendix, w4 > 0 is ensured by choosing 31 (e 1)32. Let wi {w+, Boo -32} be weight of the i-th sample. Then Equation (5) is equivalent to:
(RR)
Σ w R A/Ri
in which e(R) is short for (R and C x; short for R C [j]zi,j 1). Intuitively, the goal is to find short rule to maximize the total weight of samples covered by it. We further rewrite Equation 66) as:
(R) Σ wii+
Σ
wi R
Σ kwi>0
will WilRgx A|RR
iml
<0
Define u(R)= = En -wi Rgx, and wR) = En will Rgx, + A|R). We get the following result. Proposition 3. u(R) and wRR are non-negative monotone submodular functions.
Proof. Observe that {i|R & x = UJER {ibi} & x i.c., the samples excluded by R are the union of samples excluded by each element of R. Then u(R)) is weighted coverage function, which non-negative monotone submodular. Similarly w(R) is the sum of a weighted coverage function
and non-negative modular function, therefore it is also non-negative monotone submodular. D
5

---

Then maximizing v(R) is equivalent to maximizing the difference between submodular functions, u(R) wRR). This not surprising. because any set function can be expressed as difference of two submodular functions (called DS function) 37 However, finding such decomposition requires exponential complexity for general set function. This lucky discovery opens the door to nontrivial optimization algorithms based on the submodularity of u(R) and w(R). In this work, we (MM) approach proposed by Iyer and Bilmes [25]. For a submodular function f 2 + I20. tight lower and upper bound approximations of f at X S V are given by
take a
following modular functions [3 26
1²x((D)= -10--0))--(----------) -
(8)
jEY
m}x(()= =0 f(x) - E SG1X (it)+
E
S010) 2 SM
(9)
JEXIY
jEYiX
m²xx()= 1(X) - E
SGIV U1)+
E SGIX) JY),, JEY
(10)
JEXVY
where 5 is chain obtained by applying a permutation π [[]]] V the ground set V subject and Six = X. With these bounds, the MM idea works by iteratively updating the solution by optimizing (sub) surrogates of the DS objective function. In our case, u(R) w (R) is approximately maximized using the modular modular procedure 25 detailed in Algorithm 2 At each iteration, lower bounding surrogates of u(R) ((R) are obtained via replacing R by its modular lower bound and replacing (R) by its modular upper bounds. These modular surrogates are maximized exactly through selecting all positive elements.
to Sg = 0, 5 =
Algorithm 2 DS-OPT u, w)
while true do
R' + R
Choose permutation of [d] to form the chain S
4 For Vj e [d]. compute nū (j) = u(ST 167) u(ST 1 -G)-1)
For Vj R. compute " (j) w (j]R \ (i}) and mw (j) w (illd) (i)
For Vj & R. compute m!
u, (f) = w (j10) and m² W. (j) = w (j)
7
R1 + {j]hū,R())
m (i) > 0}. R2 + ()))) m mn (j) > 0}
8
R + arg max ma R2) ((R) w( (R)
R = R'' then break end if
10 end while
11 Output: R
To further reduce the possibility of stucking in local maxima, the MM procedure is augmented with a restricted exact search step and swap-based local search heuristic as sketched in Algorithm 3 At line 6-7, the current solution is enlarged into an active set of size M and an exhaustive subset search restricted on this active set is conducted. The aim of this exact search step is produce good initialization for DS OS-. and we find empirically that the gain ratio ((]]R)/w( (R) is good criterion for including new features in the active set. In our implementation, we set M 16 and carry out the exact search with customized branch-and bound (BnB). At line 9, the SwapLocalSearch subprocedure tries to improve the solution by adding, removing or replacing a feature.
Experiments
We evaluate the proposed approach in terms of predictive performance, interpretability, scalability. and approximation quality.
5.1 Setup
Datasets. Our experimental study is conducted on 20 public datasets. Fifteen of them are from the UCI repository [16], and the other five are variants of the ProPublica recidivism dataset (COMPAS)

---

Algorithm 3 Local combinatorial search
Input: Training data {(x.. 8:) objective function e(R), threshold M for exact search Decompose e(R) = =(R) =(R)
Initialize R. <- 0
while true do
R < R; R' R
6
if [R] < M then R t- Enlarge(R, M, u, w) end if
7
if |R] S M then R +- BestSubset(R,, u, w) end if
R + DS-OPT(R, u,
R 4 SwapLocalSearch((R w)
10
R = R' then break end if'
11 end while
12 Output: R
[29] and the Fair Isaac credit risk dataset (FICO) [21] that have been used in recent work to evaluate interpretable rule-based models [34]. We binarize the features of all datasets in exactly the same created for
way as [14]. Specifically, for categorical features, two features I, = 2 and zj * each category z. For numerical features, we create comparison features I S 2 and T; > 2 via choosing sample deciles as the boundary value The number of binary features of each dataset after preprocessing is given in Table I, which is up to 2922. Note that the negative and comparison features produced in this preprocessing method will make the feature matrices dense and make the features highly correlated, which poses major challenges to rule set learning algorithms.
Baselines. The proposed method is compared with recently developed algorithms that explicitly optimize the interpretability of rule sets including CG [14] and BRS [49], I. as well as a classical sequential cover algorithm, RIPPER [13] The official light version of CG implementation [5] is used in our experiments, which solves the rule generation subproblem using heuristic beam search instead of TP solver. This is exactly comparable to our method because also rely on approximate algorithm, which is more practical than calling a solver. For BRS, we use a third-party implementation 32 that supports generating candidate rules based on random forest instead of frequent itemset miner, because we find that the latter has poor scalability. For RIPPER, an open source Python implementation [36] chosen. In addition, also include the widely used CART and random forest (RF) algorithms implemented in the scikit-learn package 40) to illustrate the competitiveness of rule set models.
Parameter tuning. We estimate numerical results based on 10-fold stratified cross-validation (CV). In each CV fold, we use grid search to optimize the hyperparameters of each algorithm on the training split. For the method proposed in this paper. fix 8o 31 1 and optimize the remaining hyperparameters 82 E {0.5, 0.1, 0.01), À {0.1, 1, 4, 8, 16, 64] and K E (8, 16, 32}. The hyperparameters of CG include the strength of complexity penalty and the beam width, for which we sweep in (0.001, 0.002, 0.005} and { 100 20), respectively. For RIPPER, the proportion of training set used for pruning is varied in {0.2, 0.25 ... 0.6). For BRS, the maximum length of a rule is chosen from (3.5). For CART and RF, we tune the minimum number of samples at leaf nodes from 100 and fix the number of trees in RF to be 100.
5.2 Numerical results
Predictive performance. The predictive performance measured by average test accuracy over 10 folds is reported in Table 2. BRS is not available on magic and gas because it beyond our time limit, and CG is not available on COMPAS because we encountered an LP solver error. On small datasets, the accuracy our submodular optimization based approach matches the CG based approach, and both of them are top-perfon cop-performing rule set learners that are as accurate as the tree-based model, CART. The differences should not be overly concerned here because the variances are high due to small sample sizes. Notably, our method achieves 100% test accuracy on tic-tac-toe and mushroom, for which well-known perfect rule set solutions exist. On larger datasets, we observe that
We failed
IDS 28 and DRS [1 most of the datasets.
7

---

Table 1: Predictive performance measured by average test accuracy (%)
Dataset
#samples
#features
Ours
RIPPER
BRS
CG
CART
RF
tic-tac-toe
958
54
100.0 (0o)
99.7 mm
100.0..m
100.0.00
94.2
99.1 (08)
liver
345
104
(9.5
66.0
60.6a..
68.7 (54)
68.6
73.9 (2.)
heart
303
118
82.2 (13)
76.2
79.7
78.0
82.2
82.8
ionosphere
351
566
(1.4
87.2
85.0
90.6 (44)
89.5
(3.0
ILPD
583
160
71.4 (0.))
57.8
69.0.s.)
71.7 (34)
69.4
71.2
WDBC
569
540
(4.0
94.7
93.9
94.7 (14)
93.5
97.0
pima
768
134
75.4 (4.3)
75.9 (5.5)
(2.2
74.0
(6.4
76.9
transfusion
748
64
78.
78.2 (m
77.1
78.2
78.7
79.7
banknote
1372
72
98.7
92.8
91.1
98.8 (099
99. a.
99.6
mushroom
8124
224
100.0 mm
99.7
99.9 (0))
100.0
100.0
COMPAS-201
5020
30
66.5
57.7 (1.
63,4
66.7 (2.0)
66.2
66.6
COMPAS-binan
6907
24
67.0
56.0
65.5
66.4
(..3
67.3
FICO-binary binary
10459
34
71.2 (1.)
60.1
70.5
71.1 (1.2)
71.9 (.4)
72.3
COMPAS
12381
180
73.3 (1.3)
(1.5)
70.7
N/A
72.2
73.8
FICO
10459
312
70.4
69.1
70. (.9)
71.0
70.9 (L.
72.3
adult
48842
262
84.4 (66)
83.3 (..))
80.3
82.8 (44)
(.4)
84.7 (o5)
bank-market
11162
174
84.4 (08)
82.9 (L.
82.3 (03)
83.0
85.2
magic
19020
180
84.6 (u8)
82.2
N/A
(1.)
84.7 (..)
86.7 (a5)
musk
6598
2922
97.3 (v))
96. mm8)
90.2
95.0
96.0 ms)
97.7 (x))
gas
13910
2304
98.2 (v))
N/A
95.9 (07)
99.0
99.8 (o))
our method generally demonstrates superiority over other rule set learners. Overall, the accuracy gaps between our method and the uninterpretable RF are within 3% on all datasets except liver.
Table Interpretability measured by number of rules, number of literals, and overlap among rules.
#Rulc RIPPER
#Literals RIPPER
Overlap (%) RIPPER
Dataset
Ours
CART
Ours
CART
Ours
CG
8.0
9,5
8.0
69.9
24.0
31.1
24.3
138.8
2.3
52.8
23.3
tic-tac-toe
(1.
(58)
(0.5)
0.1
18.0
14.5
83.8
7.1
58.5
9.0
7.5
28.0
9.7
liver
(24)
00:
(1.2
(105)
15.31
16.90
09.00
(4:)
(2.0
4.0
10.3
11.4
4.4
11.0
41.5
21.8
48.4
heart
6:3
(1.
01:0
(1.11
(1.5)
13.91
(3:2)
(2:1)
(12)
(4.9)
(2.9)
2.0
3.6
4.3
24.7
8.0
12.5
20.3
48.4
3.4
57.2
32.1
ionosphere
6.71
m.5)
00.5
(2.0
(2.4)
13.0
(3.8)
06.33
(5.0)
(7.90
(.0
1.1
2.6
2.0
4.3
0.2
7.0
3.0
7.6
0.0
31.7
0.0
ILPD
63
00.51
00.00
(9:3)
(800)
11.00
(00))
...
8.0
5.0
5.3
7.9
27.7
10.6
13.4
14.8
2.4
35.0
26.8
WDBC
3.2
3.6
6.7
10.1
10.0
13.0
20.0
19.2
2.6
27.0
5.4
pima
(6.5)
1.4
2.1
2.7
11.0
4.3
9.0
7.9
21.0
0.0
21.3
0.8
transfusion
mm
(0.5)
0.50
(1/)
(1.6)
0999
(1D
7.4
28.2
32.8
21.0
10.9
55.4
0.1
41.0
9.5
banknote
03
(1.3)
m.
00.7
05.0
(4.7)
(1.4)
(5.9)
(0.3)
(370
m07)
6.1
5.0
14.1
8.4
10.9
7.0
27.2
0.0
41.6
21.0
mushroom
0:31
(1.))
(0.0)
(0.6)
(1.))
16-01
(80))
(1.1)
(00)
(15.)
(0.1
11.8
9.0
3.0
31.0
41.9
31.4
6.0
61.0
0.0
30.9
0.5
COMPAS-2016
(4
(1.6)
m0.0
(0.7)
(301)
(7.)
(0.0)
(1.5)
(81)
60.1
11.4
12.0
2.9
78.0
42.2
48.1
5.4
155.0
0.1
32.0
0.0
COMPAS-binary
0.5
(1.0
00.3)
(8.
(0.)
0.1
21.6
16.7
2.0
158.5
134.0
106.8
4.0
316.0
0.3
37.8
0.0
FICO-binary
5.5
12.0
N/A
85.9
24.0
66.0
N/A
170.8
0.2
21.2
N/A
COMPAS
127)
(2.)
(148)
(153)
(6.9
(0.1)
(3.5
16.0
16.7
1.1
69.5
118.6
99.7
1.4
138.0
3.5
39.8
0.0
FICO
655
(39)
m..
(1.4)
(30.))
(26-)
n.3)
2.5)
(1.3)
(3.0
10m
9.1
42.7
2.0
398.3
83.4
337.0
5.7
795.6
0.8
25.8
1.8
adult
(138.)
(0.))
09.99
(0-4
17.6
43.8
11.0
289.0
[18.5
269_1
18.7
$77.0
3.6
43.8
7.8
bank-market
(0.))
19.1
52,3
2.7
398.9
136.1
391.3
6.2
796.8
2.8
50.0
7.6
magic
(0.4)
8.9
19.6
5.0
180.0
61.2
101.4
21.0
359.0
0.8
36.9
2.7
musk
(.9)
(1.)
0.6
(20)
(148)
(7.6)
(1.5)
(142)
(95)
(14)
13.1
24.2
172.2
74.2
106.8
14.7
343.4
15.2
22.1
gas
0.55
0.3
(8:00
01.
01.5
(8.
(1.))
m00
(1m

---

Interpretability. The interpretability of learned models is compared in terms of three metrics: the number of rules, the total number of literals in all rules, and the overlap among rules. In our notation. the former two complexity metrics are |S| and ERES 'R.,, respectively. The overlap is measured as the fraction of samples covered by more than one of the rules, i.e., if (x;;) > 1H/n. For CARTs, we treat their root-to-leaf paths as rules. The complexities of RFs are generally high because it consists of many trees, therefore we do not report them here. Note that the overlap among rules generated from a CART is zero because these rules form a partition of the feature space. We leave BRS out here as its predictive performance on larger datasets is incomparable to remaining methods.
The results averaged over 10 folds are reported in Table 2 We observe that CG usually produced rule sets with lowest complexity, while our method is competitive when compared to RIPPER. Our method learned notably simpler rule sets than RIPPER on large datasets except FICO. When it comes to the overlap among learned rules, our method dominates the competition because it explicitly penalizes the overlap in the objective function. We notice that RIPPER is particularly problematic if overlap is the concern, as > 20% samples are covered more than once on all datasets. The learned rule sets on the mushroom and tic-tac-toe datasets are illustrated in Table Remarkably, the rule set for mushroom even simpler than the ground truth provided in the dataset description file [.. as the third rule consists of only two conditions instead of three.
Scalability. Our method scales linearly with the dimensionality, the sample size and the number of iterations. In our experience, the local search algorithm for the subproblem usually terminates at stationary point in a few iterations. Bit vectors are used in implementation to process large number of samples efficiently. Therefore for our algorithm the dimensionality is the main bottleneck in scalability. Figure T shows the training time of our method on the musk and gas datasets when using randomly sampled subsets of features. As the number of features grows, the training time demonstrates roughly linear trend as expected. Our method is thus more practical when compared to solving the subproblem with exact algorithms, e.g., branch-and- bound, because it is well known that exact algorithms for general combinatorial optimization problems scale poorly with dimensionality.
The average running time of each method for fitting each dataset under typical hyperparameters found in cross-validation is reported in the Appendix. In summary, our method is competitive with other rule set learners but is slower than well-optimized tree- based methods. Further boosting of scalability may be achieved through drawing inspiration from scalable submodular optimization techniques [27] and we leave this for future work.
Table 3: Examples of learned rule sets.
Training time vs Number of features
musk
250
mushroom
odor a AND odor ANDA odor 1= n
200
spore poore_pritt_coe coloor =
gillssie AND stalk surface__cloo bewowwring cap_color= = w AND population =
350
ti--acctte
lop-right= = x AND middle-middie x AND bottem-left = x lup-left = AND muddle-middlee AND bottom right middle-left x AND middle middle x AND middle-right =x bottom-left AND bottom-miédle
100
AND bottom-right
top-left x AND top-middle = AND top-right x
top-left= = x AND middle-letl -eft x AND bottom-left
500
1000
1500
2000
2500
3000
top-right right AND middle = x AND hottom right
#teatures
top-middle x AND middle-middle x AND bottom-middle =
Figure 1: Scalability test.
Approximation quality. To examine the effectiveness of Algorithm 3 we conduct a comparison between approximate subproblem solving and exact subproblem solving under the same typical hyperparameter settings. On nine diwdenensiooal datasets, all of the subproblems could be exactly solved within 10 minutes using our customized BnB procedure. As the subproblems for remaining higher-dimeesional datasets could not be solved to optimality with practical running time, a time limit of 10 minutes is specified for the BnB subproblem solver. For each dataset, we record the values of objective function V(S) achieved by learned rule sets under the two setups and calculate the relative gaps between solutions as (Smmb) - (SSapprx)) )) ///VV/(S (Sbob). Results are summarized in the Appendix.
9

---

The relative gaps are small in general and do not grow with the dimensionality, indicating that the proposed approximate algorithm works well on these datasets, For instance, the two setups produced exactly the same rule sets on five of the low-dimensional datasets. Interestingly, it turns out that approximate subproblem solving is not necessarily worse than the exact counterpart. This because the outer loop (Algorithm [T is also an approximation procedure, which does not guarantee that better subproblem solutions will help build a better solution to the main problem.
Limitations
Approximation guarantee. The main limitation of this work is the invalidity of approximation guarantee (Proposition() under inexact subproblem solving. Nonetheless, the approximation guar- antee is still relevant in the case that the optimal solution to the subproblem can be found. This is possible if we restrict the space of rules to a tractable extent. For example, if we move back to the pre-mining approach in which rules can only be picked from given pool (e.g., rules extracted from random forest), the guarantee will still hold for this modified problem. Furthermore, the previous discussion of approximation quality shows that empirically such invalidity will not necessarily lead to much loss of performance. We are planning to analyze this phenomenon theoretically in future work.
Multiclass extension. Another more subtle limitation is the extension multiclass classification. We have suggested the model-agnoste one-versus-one (OvO) transformation, which only requires the base classifiers to produce binary class label, rather than real-valued confidence score required by the one-versus-rest (OvR) approach. However, both OvR and OvO may suffer from ambiguities and class imbalance. Moreover, the OvO reduction not very efficient because K K(K 1)/2 base classifiers must be trained for K-elass classification task. We are investigating if there is a more scalable approach extend this work to multiclass problems.
Societal impact. On the positive side, the underlying decision logic of an interpretable model such as a rule set is more transparent for humans to understand. When used as data exploration tool, such transparency enables people to check easily if the fitted model has discovered some new knowledge about the data. When deployed to make automatic decisions in high-stake scenarios, such transparency helps people to diagnose if there are potential biases or risks in the model and to explain the reason behind a specific decision. On the negative side, a rule set learned by optimizing accuracy and interpretability will not automatically attain other properties requested by trustworthy AI, such as fairness and robustness. In addition, learned rule "IF X=x0 AND Y=yl THEN Z=1" may not conform to the causal mechanism underlying the variables X, Y and Z. This will lead to misunderstandings the rules are not interpreted properly.
7 Conclusions
In this paper, we propose new perspective on interpretable rule set learning based on submodular optimization. The learning task is decomposed into two related subset selection problems, where the main problem selects a subset from all possible rules optimize a regularized submodular objective, and the subproblem selects feature subset to form a rule. The optimization criteria of the subproblem derived based on distorted greedy algorithm for maximizing the main objective, and we observe that this criteria can be expressed as the difference between two submodular functions. Based on this finding, an iterative local combinatorial search algorithm designed to solve the subproblem approximately. The effectiveness of our method is evaluated through a comprehensive experimental study on 20 datasets. Directions for future work include warm-starting the search with rules generated by random forests and extending the method to rule-based regression tasks.
Acknowledgments
We thank the anonymous reviewers at NeurIPS 2021 for their insightful feedback.
10

---

References
[1] Mushroom data set. 2021-05-28.
Accessed:
[2] Gaël Aglin, Siegfried Nijssen, and Pierre Schaus. Learning optimal decision trees using caching branch-and-bowe search. In Proceedings of the AAAI Conference on Artificial Intelligence. 2020.
[3] Elaine Angelino, Nicholas Larus-Stone, Daniel Alabi, Margo Seltzer, and Cynthia Rudin. Learning certifiably optimal rule lists. In Proceedings of the 23rd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, 2017.
[4] Elaine Angelino, Nicholas Larus-Stone, Daniel Alabi, Margo Seltzer, and Cynthia Rudin. Learning certifiably optimal rule lists for categorical data. Journal of Machine Learning Research, 18(23)): 2018.
[5] Vijay Arya, Rachel K. E. Bellamy, Pin-Yu Chen, Amit Dhurandhar, Michael Hind, Samuel C. Hoffman, Stephanie Houde, Q. Vera Liao, Ronny Luss, Aleksandra Mojsilović, Sami Mourad, Pablo Pedemonte, Ramya Raghavendra, John Richards, Prasanna Sattigeri, Karthikeyan Shan- mugam, Moninder Singh, Kush R. Varshney, Dennis Wei, and Yunfeng Zhang. One explana- tion does fit all: A toolkit and taxonomy of ai explainability techniques. arXiv preprint arXiv: (900:::90000001100 2019.
[6] Martin Atzmueller. Subgroup discovery. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 5(1):35-49, 2015.
[7] Martin Atzmueller and Frank Puppe. Sd-map-a fast algorithm for exhaustive subgroup discovery. In European Conference on Principles of Data Mining and Knowledge Discovery, 2006.
[8] Dimitris Bertsimas and Jack Dunn. Optimal classification trees. Machine Learning, 106(7): 1089-1082,000 2017.
[9] Mario Boley, Claudio Lucchese, Daniel Paurat, and Thomas Gärtner. Direct local pattern sampling by efficient two-step random procedures. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011.
[10] Mario Boley, Sandy Moens, and Thomas Gärtner. Linear space direct pattern sampling using coupling from the past. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2012.
[11] Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the twenty-fifth annual ACM-SIAM Symposium On Discrete Algorithms, 2014.
[12] Peter Clark and Tim Niblett. The en2 induction algorithm. Machine Learning, 3(4):261-283. 1989.
[13] William W Cohen. Fast effective rule induction. In Proceedings of the 12th International Conference on Machine Learning, 1995.
[14] Sanjeeb Dash, Oktay Gunluk, and Dennis Wei. Boolean decision rules via column generation. In Advances in Neural Information Processing Systems, 2018
(15) Ayhan Demiriz, Kristin P Bennett, and John -aywerT Linear programming boosting via column generation. Machine Learning, 46(1):225-255 2002.
[16] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL/tttp://archive
ics. uci uci.edu/ml ml
[17] Jonathan Eckstein and Noam Goldberg. An improved branch-and- method for maximum monomial agreement. INFORMS Journal on Computing, 3313413 2012
[18] Alina Ene, Sofia Maria Nikolakaki, and Evimaria Terzi. Team formation: Striking a balance between coverage and cost. arXiv preprint arXiv:2002.07782, 2020.

---

[19] Moran Feldman. Guess free maximization of submodular and linear sums. Algorithmica, 83(3): 853-878, 2021.
[20] Moran Feldman, Christopher Harshaw, and Amin Karbasi. Greed is good: Near-optimal submodular maximization via greedy optimization. In Proceedings of the Conference Learning Theory, 2017.
[21] FICO, Google, Imperial College London, MIT, University of Oxford, UC Irvine, and UC Berke- ley. Explainable machine learning challenge, 2018. URL WRRLhttps:/// http::////mmmmitt// fico. com/ 8 sxxplainable-macho heaaab---- challenge
[22] Jerome H Friedman, Bogdan E Popescu, et al. Predictive learning via rule ensembles. Annals of Applied Statistics, 2(3)9966-9544 2008.
[23] Chris Harshaw Moran Feldman, Justin Ward, and Amin Karbasi. Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In Proceedings of the 36th International Conference on Machine Learning, 2019.
[24] Xiyang Hu, Cynthia Rudin, and Margo Seltzer. Optimal sparse decision trees. In Advances in Neural Information Processing Systems, 2019.
[25] Rishabh Iyer and Jeff Bilmes. Algorithms for approximate minimization of the difference be- tween submodular functions, with applications. In Proceedings of the Twenty-Eightt Conference on Uncertainty in Artificial Intelligence, 2012.
[26] S Jegelka and Bilmes. Submodularity beyond submodular energies: Coupling edges in graph cuts. In Proceedings of the 2011 IEEE Conference on Computer Vision and Puttern Recognition, pages 1897-1904, 2011.
[27] Ehsan Kazemi, Shervin Minaee, Moran Feldman, and Amin Karbasi. Regularized submodular maximization at scale. In Proceedings of the 38th International Conference on Machine Learning, 2021.
[28] Himabindu Lakkaraju, Stephen H Bach, and Jure Leskovec. Interpretable decision sets: A joint framework for description and prediction. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016.
[29] Jeff Larson, Surya Mattu, Lauren Kirchner, and Julia Angwin How we analyzed the compas recidivism algorithm. ProPublica, 2016.
[30] Nada Lavrac, Branko Kavšek, Peter Flach, and Ljupco Todorovski. Subgroup discovery with cn2-sd. Journal of Machine Learning Research, 5:153-188, 2004.
[31] Florian Lemmerich, Martin Becker, and Martin Atzmueller. Generic pattern trees for exhaustive exceptional model mining. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2012.
[32] Peter (Zhen) Li. Bayesian rule set mining, httpp///ghhhaaaoc//////ssseeegss Accessed: 2021-05-28.
[33] Wenmin Li, Jiawei Han, and Jian Pei. Cmar: Accurate and efficient classification based on multiple class-association rules. In Proceedings of the IEEE International Conference on Data Mining, 2001.
[34] Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees. In Proceedings of the 37th International Conference on Machine Learning, 2020.
[35] Graziano Mita, Paolo Papotti, Maurizio Filippone, and Pietro Michiardi. Libre: Learning inter- pretable boolean rule ensembles. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statisties, 2020.
[36] Iln Moscovitz. wittgenstein. http://eeooattt////////oo/oooo/n cessed: 2021-05-28.
12

---

[37] Mukund Narasimhan and Jeff Bilmes. A submodular submodular-supermodee supermodular procedure with applica- tions to discriminative structure learning. In Proceedings of the Twenty-Firs First Conference on Uncertainty in Artificial Intelligence, 2005.
[38] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizzng submodular set functions Mathematical Programming. 14(1):265-22 2944, 1978.
[39] Siegfried Nijssen and Elisa Fromont. Mining optimal decision trees from itemset lattices. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007.
[40] Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning Python. Journal of Machine Learning Research, 12:2825-288 2830, 2011.
[41] J Ross Quinlan and R Mike Cameron-Jones. Foil: A midterm report. In European Conference on Machine Learning, 1993.
[42] Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 155):206-211 215, 2019.
[43] Cynthia Rudin, Chaofan Chen, Zhi Chen, Haiyang Huang, Lesia Semenova, and Chudi Zhong. Interpretable machine learning: Fundamental principles and 10 grand challenges. arXiv preprini 1.Xiv:2103.1125:: 2021.
[44] Guolong Su, Dennis Wei, Kush R Varshney, and Dmitry M Malioutov. Learning sparse two- level boolean rules. In IEEE 26th International Workshop on Muchine Learning for Signal Processing, 2016.
[45] Maxim Sviridenko, Jan Vondrák, and Justin Ward. Optimal approximation for submodular and supermodular optimization with bounded curvature. Mathematics of Operations Research, 42 (4):1197-1218, 2017.
[46] Matthijs Van Leeuwen and Arn Knobbe. Diverse subgroup set discovery. Data Mining and Knowledge Discovery, 25(2):208-24 2012.
[47] Sicco Verwer and Yingqian Zhang. Learning optimal classification trees using binary linear program formulation. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
[48] Tong Wang and Cynthia Rudin. Learning optimized or's of and's, 2015.
[49] Tong Wang, Cynthia Rudin, Finale Doshi-Velez, Yimin Liu, Erica Klampfi, and Perry MacNeille. bayesian framework for learning rule sets for interpretable classification. Journal of Machine Learning Research, 18(70):1-37, 2017.
[50] Xiaoxin Yin and Jiawei Han. Cpar: Classification based predictive association rules. In Proceedings of the SIAM International Conference on Data Mining, 2003.
[51] Guangyi Zhang and Aristides Gionis. Diverse rule sets. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2020.
[52] Haoran Zhu, Pavankumar Murali, Dzung Phan, Lam Nguyen, and Jayant Kalagnanam. scalable mip-based method for learning optimal multivariate decision trees. In Advances in Neural Information Processing Systems, 2020.
13


Reviews:
[{"review_id": "oR3RbK9VvUA", "reviewer": "Reviewer_4Q8k", "summary": "This paper proposes an approach for learning decision rule sets that combines both rule generatino and rule selection. this is accomplished by formulating the an outer subproblem as regularized submodular maximization and an inner problem as maximizing the difference of two submodular functions. Experimental results show that the method has improved test performance with less overlap among decision rules.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: Interesting but straightforward combination of previous work on submodular maximization (distorted greedy, majorize-maximization) to a new domain.\n\nQuality:\n- The authors should discuss how the rule set compares to the true optimal rule set, since two solutions with similar values could be differ in their interpretability.\n- While test accuracy is impressive (Table 1), the results in Table 2 are much more impressive for Overlap percentage, which makes sense because the proposed algorithm is admittedly the only one to minimize that explicitly (line 276). Since #Rules and #Literals are often much worse than baselines, it would be good to argue strongly that overlap is a much more important interpretability measure than either of those.\n\nClarity: Paper is clear, well-organized, and generally a pleasure to read\n\nMethodology: \n- Why set $\\beta_o = \\beta_1 = 1$? Why fix the number of trees in the RF to be 100? \n- What was the problem with running [27]? Since references [14, 27] are discussed in related work and appear to be very relevant, the paper would be improved if it added these works as baselines.\n- Figure 1 (scalability) should include other algorithms as well\n\nQuality/Significance: If the inner subproblem is solved with an approximate local search heuristic, then the theoretical guarantee of Proposition 2, which assumes the inner subproblem is solved to exact optimality, is not relevant. The paper does not address this fully, and would benefit from identifying how much is lost to this approximate inner subproblem either theoretically (assume an approximate inner maximization oracle) or empirically (ablation on different inner subproblem methods).\n\nQuestions:\n- Do other approaches require binarizing the features? If not, how do they scale with d?\n\n---\nEDIT: The authors addressed my main concerns with additional experiments showing the optimality gap with respect to a branch and bound method. I am increasing my score to 6, although the paper would be further strengthened by studying the sensitivity to inner subproblem solver in even greater detail.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No explicit discussion of limitations or negative social impact. The authors could discuss that in general interpretable classification methods need not be more fair or accurate than large neural networks.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "dk0a_qRj-2", "reviewer": "Reviewer_ijjJ", "summary": "This submission addresses learning interpretable rule sets for binary classification problems. The approach is based on using submodular optimization, and the authors come up with a learning algorithm that uses approximation properties from DS optimization. The exact solution of the subproblems are NP-hard, and hence, the authors propose solving the subproblems via heuristic approaches. This is supported by local search operators. Some theoretical results are presented. The computational experiments show the effectiveness of their approach in terms of accuracy. The contribution of this work is an algorithm that works very well on binary classification and manages to find interpretable decision rules.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Major Comments:\n- How do you define small dataset and large dataset? Check lines 258, 262.\n- Interpretability analysis: The number of rules and number of literals are significantly different than the\nwork by Dash et al. (2018) for CG and CART. Why? For RIPPER this is not the case and good. It would be\nbetter to include the outcome of BRS in Table 2. Now the analysis looks incomplete.\n- Limitations of this study are not discussed.\n\nMinor Comments:\n- 22-23: “Black box models are particularly problematic here because they are hard to audit and to diagnose.” => Sentence needs rewording, very informal.\n- 77: one-versus-one or one-versus-all?\n- 154: Missing a space after “cases,”.\n- 218: “Decision lists are special cases of decision trees that grows only in one branching direction, and\nthe root-to-leaf paths of a decision tree form a rule set without overlap.” => Sentence needs rewording,\nnot clear.\n- 220: “However, the learning of decision lists and trees are inherently much”\n- 221: “harder because of their combinatorial structure is more complex than rule sets.”\n- 251: “For BRS, the maximum”\n- Very briefly, there are spelling mistakes in the document and the usage of language can be improved significantly...", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The reasoning behind solving the subproblem via heuristic approaches is understandable. Nevertheless, the running times of the algorithms are not discussed/reported. \n\nThe experiments are given only for binary classification. The other missing point is details about generalization to multi-class classification.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "EYTXFg2x8Iz", "reviewer": "Reviewer_Uvxy", "summary": "This paper addresses learning rule set models for binary classification, ie combinations of logical rules on features to classify a positive class. Since learning rule sets requires selection of features over which the logical rules are applied and selection of the rules themselves, the subset selection problem is exponential. This paper formulates the task loss as a supermodular function comprised of a constant term (ignored in the optimization), a modular function term and a submodular function term. The paper outlines an optimization algorithm that contains a subproblem that is not computationally feasible except for small problems. Thus, it outlines an approximate solution to the subproblem.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution of the work is in the specific formulation of the rule set learning problem as a regularized submodular loss function and then applying the optimization algorithm of [2] to solve it. However the subproblem introduced in that algorithm cannot be solved exactly for larger problems, so the paper proposes an approximate solution to the difference of submodular functions. Thus, the optimization does not have any approximation guarantees. The method may be useful in it's formulation, though the optimization of the loss is less compelling without real 'nice' properties beyond the results that can be seen empirically, ie it seems to work in practice. Without more data on running time, both on the proposed optimization and the baselines, the empirical analysis is still lacking. \n\nClarity: The work is generally well presented and the paper is mostly clear. One exception is the discussion of related work. Section 4 does not go into enough detail of the cited work to place this work into the context of the field. The introduction section even provides more information on some of these works. Can these be combined or reorganized to better contextualize the contribution of the current work as well as the existing work of the relevant literature that is already cited?\nExperiments: It’s not clear why an alternative (light) implementation of the Column Generation (CG) [1] method was used. While the beam search alternative may be more comparable in that it is an approximate algorithm, the full method can be evaluated against the proposed method both on accuracy and speed, for example. Is a full implementation not available? In any case, the running time of the proposed and baseline methods should be reported as well, especially since some methods were excluded based on a running-time cut-off. \n[1] Harshaw, C., Feldman, M., Ward, J. and Karbasi, A. \"Boolean decision rules via column generation.\" Proceedings of the 32nd International Conference on Neural Information Processing Systems. 2018.\n[2] Harshaw, Chris, et al. \"Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications.\" International Conference on Machine Learning. PMLR, 2019.\n\n\n\nPost rebuttal comments:\nThe new results and clarifications from the authors have strengthened the experimental components of the submission, which I believe are the main contribution of the work. Thus, I am updating my score to recommend acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations of the method are not extensively addressed, especially since the approximate solution loses the approximation guarantees admitted by exactly solving the marginal gain maximization subproblem, which can only be computed for small problems. For a small problem like COMPAS-binary with 24 features or other small datasets, the solution could be compared to the exact subproblem solving both in accuracy and running time to investigate some of the gaps in the approximation.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors provide an interesting connection between an interpretable decision rule set and submodular optimization. Technically, they either consider regularized submodular maximization framework or the difference of two submodular functions. 

I found the formalization very interesting. Also, the authors had a successful rebuttal and convincing new set of experiments.  Regarding scaling up the experiments, the authors may look at a recent ICML paper on "Regularized Submodular Maximization at Scale" by Kazemi et al. Also, there is a related paper on interpretability using submodularity that the authors may consider looking into "Streaming Weak Submodularity: Interpreting Neural Networks on the Fly" by Elenberg et al. 

All in all, this is an interesting paper and I suggest acceptance. 
Decision: Accept (Spotlight)