Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach
Year: 2021

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.

heading: 1 Introduction
text: Interpretability is becoming one of the key considerations when deploying machine learning models to high-stake decision-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, it has been widely known that machine learning models are susceptible to 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 to audit and to diagnose.
The development of inherently interpretable models is a longstanding attempt towards interpretable and trustable machine learning [42, 43]. In this paper, we consider decision rule sets for binary classification, in which if an example is tested true for a Boolean condition expressed in disjunctive normal form (DNF), then a predefined label is predicted for it. For instance, a rule set for determining whether a patient with community-acquired pneumonia should be hospitalized may be "IF (IsChild = True AND OxygenSaturation < 0.9) OR (IsChild = True AND SOB = True) OR (IsAdult = 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 (NeurIPS 2021).
rules has to be selected to form a rule set. In early algorithms from machine learning community, such as FOIL [41], CN2 [12] and RIPPER [13], usually a 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 [33, 50] developed by data mining community take a different two-stage strategy, in which a 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 a 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 simultaneously optimizes accuracy and interpretability. We show that given a ground set of rules, this objective is a regularized submodular function [27], for which algorithms with strong approximation guarantees have been developed recently [23]. 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 a 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 a regularized submodular maximization problem which is amenable to 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 is summarized in Section 2. Section 3 introduces the problem formulation. Section 4 presents the algorithmic details. Experimental evaluation is reported in Section 5. We discuss the limitations of this work in Section 6 and conclude the paper with Section 7.

heading: 2 Related work
text: To discover rules from training data, heuristic sequential covering or separate-and-conquer strategy is utilized by almost all early algorithms [41, 12, 13], 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, 51]. 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 et al. [14] formulate the rule set learning problem as an 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 a 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 [7, 31], heuristic beam search [30, 46] and sampling [9, 10] are commonly utilized. Eckstein and Goldberg [17] designed a specialized branch-and-bound 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 a 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, 34, 8, 39, 2, 47, 52]. The learning of decision lists and trees is inherently much harder because their combinatorial structures are more complex than rule sets.

heading: 3 Problem formulation
text: In this work, we consider binary classification based on a set of interpretable binary features. Categorical features can be easily binarized via one-hot encoding, and numerical features may be binarized through bucketing or comparisons like "Age ≥ 18". Techniques such as one-versus-one are available for transforming multiclass classification to binary classification.
Suppose we are given the training data {(xi, yi)}ni=1, in which each xi = (xi,1, . . . , xi,d) ∈ {0, 1}d is a binary feature vector associated with a label yi ∈ {0, 1}. The goal is to learn an interpretable rule set model F : {0, 1}d → {0, 1} to predict the label. A rule set is a Boolean classifier of the form "IF P (x) THEN y = 1 ELSE y = 0", in which P (x) is a predicate restricted in disjunctive normal form (DNF) and treats raw features {xj}dj=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 {¬xj}dj=1. Then a concrete P (x) is described as a set S ⊆ 2[d], where each element R ∈ S is a subset of [d] := {1, . . . , d}. The mapping from a S to a DNF is given by PS(x) := ∨ R∈S ∧ j∈R xj . We call S a rule set and call each element R of it a rule. A sample x is covered by a rule R if P{R}(x) is true. It is now clear that a rule set classifier can be simplified to y = PS(x), i.e., it predicts 1 iff x is covered by at least one of the rules.
To learn a rule set from data, we consider minimizing the empirical error while penalizing the complexity by solving the optimization problem:
min S⊆2[d] n∑ i=1 l (PS(xi), yi) + Ω(S) (1)
However, even under the simplest setting where l(·, ·) is the 0-1 loss and Ω(·) is the cardinality function, this problem is still hard to work with. To proceed, we replace PS with a surrogate model P̃S : {0, 1}d → N0 defined as P̃S(x) = ∑ R∈S ∧ j∈R xj . Then a flexible objective function that balances accuracy and interpretability is chosen to be:
L(S) = n∑ i=1 lβ ( P̃S(xi), yi ) + λ ∑ R∈S |R| (2)
where lβ(·, ·) is a loss function with hyperparameters β = (β0, β1, β2) ∈ R3+:
lβ(ŷ, y) =  β0ŷ if y = 0 β1(y − ŷ) if y = 1 ∧ ŷ ≤ 1 β2(ŷ − y) if y = 1 ∧ ŷ > 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. P̃S(x) > 1 means that x is covered by more than one of the rules, and in this case the objective function will receive a 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 thatL(S) is a supermodular function and thus−L(S) is a submodular function. To show this, we introduce more notations. Let X+ = {i|yi = 1} and X− = {i|yi = 0} be the set of positive and negative samples, respectively. Let X+S = {i|i ∈ X+ ∧ PS(xi)} and X−S = {i|i ∈ X− ∧ PS(xi)} be the set of positive and negative samples covered by S, respectively. Then we have
L(S) = β0 ∑ R∈S ∣∣∣X−{R}∣∣∣+ β1 ∣∣X+ \ X+S ∣∣+ β2 (∑ R∈S ∣∣∣X+{R}∣∣∣− ∣∣X+S ∣∣ ) + λ ∑ R∈S |R|
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 is the overlap in positive samples, and the last term is the size of rules. After reorganizing the terms, we arrive at
L(S) = β1 ∣∣X+∣∣− (β1 + β2) ∣∣X+S ∣∣+ ∑
R∈S β0 ∣∣∣X−{R}∣∣∣+ β2 ∣∣∣X+{R}∣∣∣+ λ|R| (3) Then the submodularity immediately follows.
Proposition 1. L(S) is a supermodular function and −L(S) is a submodular function.
Proof. The first term in (3) is a constant. The second term is a negative coverage, while coverage functions are well-known to be submodular. The third term sums over elements of S and thus is modular. A submodular function minus a modular function is still submodular, therefore −L(S) is submodular and L(S) is supermodular.
We show in the Appendix that several design choices for the original objective in (1) may reduce to 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, 14].

heading: 4 Algorithms
text: We consider the algorithms for minimizing L(S) in this section. Define g(S) = (β1 + β2) ∣∣X+S ∣∣
as the revenue of a rule set and c(R) = β0 ∣∣∣X−{R}∣∣∣ + β2 ∣∣∣X+{R}∣∣∣ + λ|R| as the cost of a rule. Let
V (S) = g(S) − ∑ R∈S c(R) be the profit of a rule set, which is equal to −L(S) up to a 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 S⊆2[d],|S|≤K
V (S) (4)
is an instance of cardinality constrained submodular maximization problem. For non-negative monotone submodular functions, the greedy algorithm achieves a 1− 1/e ≈ 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-monotone submodular maximization algorithms [11, 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 ∑ R∈S 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].

heading: 4.1 Regularized submodular maximization
text: We apply the distorted greedy algorithm proposed by Harshaw et al. [23] to approximate maximization of V (S). As illustrated in Algorithm 1, at each iteration, a rule maximizing the marginal gain in a distorted objective is added to the rule set if its gain is positive. The distorted objective is adjusted in a way such that initially higher importance is placed on the cost term, and then the importance is gradually shifted back to the revenue term. By doing this, following approximation guarantee is obtained.
Proposition 2. [23] Algorithm 1 returns a rule set S of cardinality at most K. If the maximization subproblem at line 5 is solved to optimality, then
V (S) = g(S)− ∑ R∈S c(R) ≥ (1− 1/e)g(OPT)− ∑ R∈OPT c(R)
where OPT is the optimal solution to problem (4).
Algorithm 1 Rule set learning 1 Input: Training data {(xi, yi)}ni=1, hyperparameters (β, λ), cardinality K 2 Initialize S ← ∅ 3 for k = 1 to K do 4 Define vk(R) = (1− 1/K)K−kg(R|S)− c(R) /* g(R|S) := g(S ∪ {R})− g(S) */ 5 SolveR? ← arg maxR⊆[d] vk(R) 6 if vk(R?) > 0 then S ← S ∪ {R?} end if 7 end for 8 Output: S
In addition, we provide an algorithm in the Appendix for further refining the output of Algorithm 1 if possible. In each step, that algorithm tries to improve the objective through adding, removing, or replacing a 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 or high-cardinality categorical features, the preprocessing step may easily produce hundreds or thousands of binary features, making exhaustive enumeration impossible. In such cases, approximate solution should be considered and the guarantee for Algorithm 1 will no longer hold. However, we observe in practice that Algorithm 1 will still work satisfactorily if good enough solutions to the subproblem are found. To this end, approximate rather than exact method is considered in this work.

heading: 4.2 Solving the subproblem
text: We approximately solve the marginal gain maximization subproblem through iteratively refining a solution with local search until no further improvement can be made. Our local search procedure relies on a decomposable structure of the subproblem to find good solutions quickly. Objective functions for the subproblem are of the general form:
v(R|S;α) = αg(R|S)− c(R) = α(β1 + β2) ∣∣∣X+{R} \ X+S ∣∣∣− β0 ∣∣∣X−{R}∣∣∣− β2 ∣∣∣X+{R}∣∣∣− λ|R|
= [α(β1 + β2)− β2] ∣∣∣X+{R} \ X+S ∣∣∣− β0 ∣∣∣X−{R}∣∣∣− β2 ∣∣∣X+{R} ∩ X+S ∣∣∣− λ|R| (5)
where α ∈ (1/e, 1] is a multiplier on the marginal gain of g set by Algorithm 1. For notational simplicity, denote ω+ = α(β1 +β2)−β2. Notice that samples are partitioned into three subsets: still uncovered positive samples X+ \ X+S each with weight ω+, already covered positive samples X + S each with weight −β2, and negative samples X− each with weight −β0. As shown in the Appendix, ω+ > 0 is ensured by choosing β1 > (e − 1)β2. Let ωi ∈ {ω+,−β0,−β2} be weight of the i-th sample. Then Equation (5) is equivalent to:
v(R) = n∑ i=1 ωi1R⊆xi − λ|R| (6)
in which v(R) is short for v(R|S;α) and R ⊆ xi is short for R ⊆ {j|xi,j = 1}. Intuitively, the goal is to find a short rule to maximize the total weight of samples covered by it. We further rewrite Equation (6) as:
v(R) = n∑ i=1 ωi + ∑ i:ωi<0 −ωi1R*xi − ∑ i:ωi>0 ωi1R*xi − λ|R| (7)
Define u(R) = ∑ i:ωi<0 −ωi1R*xi and w(R) = ∑ i:ωi>0
ωi1R*xi + λ|R|. We get the following result. Proposition 3. u(R) and w(R) are non-negative monotone submodular functions. Proof. Observe that {i|R * xi} = ⋃ j∈R {i|{j} * xi}, i.e., the samples excluded by R are the union of samples excluded by each element ofR. Then u(R) is a weighted coverage function, which is non-negative monotone submodular. Similarly w(R) is the sum of a weighted coverage function and a non-negative modular function, therefore it is also non-negative monotone submodular.
Then maximizing v(R) is equivalent to maximizing the difference between submodular functions, u(R) − w(R). This is not surprising, because any set function can be expressed as a difference of two submodular functions (called a DS function) [37]. However, finding such a decomposition requires exponential complexity for a 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 take a minorize-maximization (MM) approach proposed by Iyer and Bilmes [25]. For a submodular function f : 2V → R≥0, tight lower and upper bound approximations of f at X ⊆ V are given by following modular functions [38, 26].
hπf,X(Y ) := ∑ j∈Y f(Sππ−1(j))− f(S π π−1(j)−1) ≤ f(Y ),∀Y ⊆ V (8)
m1f,X(Y ) := f(X)− ∑
j∈X\Y
f(j|X \ {j}) + ∑
j∈Y \X
f(j|∅) ≥ f(Y ),∀Y ⊆ V (9)
m2f,X(Y ) := f(X)− ∑
j∈X\Y
f(j|V \ {j}) + ∑
j∈Y \X
f(j|X) ≥ f(Y ),∀Y ⊆ V, (10)
where Sπ is a chain obtained by applying a permutation π : [|V |]→ V to the ground set V subject to Sπ0 = ∅, Sπj = {π(1), . . . , π(j)} and Sπ|X| = X . With these bounds, the MM idea works by iteratively updating the solution by optimizing (sub)modular 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)− w(R) are obtained via replacing u(R) by its modular lower bound and replacing w(R) by its modular upper bounds. These modular surrogates are maximized exactly through selecting all positive elements.
Algorithm 2 DS-OPT(R, u, w) 1 while true do 2 R′ ← R 3 Choose a permutation π of [d] to form the chain Sπ 4 For ∀j ∈ [d], compute hπu,R(j) = u(Sππ−1(j))− u(S π π−1(j)−1)
5 For ∀j ∈ R, compute m1w,R(j) = w (j|R \ {j}) and m2w,R(j) = w (j|[d] \ {j}) 6 For ∀j /∈ R, compute m1w,R(j) = w (j|∅) and m2w,R(j) = w (j|R) 7 R1 ← { j ∣∣hπu,R(j)−m1w,R(j) > 0},R2 ← {j∣∣hπu,R(j)−m2w,R(j) > 0} 8 R ← arg maxR∈{R1,R2} u(R)− w(R) 9 ifR = 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 a 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 to produce good initialization for DS-OPT, and we find empirically that the gain ratio u(j|R)/w(j|R) is a 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.

heading: 5 Experiments
text: We evaluate the proposed approach in terms of predictive performance, interpretability, scalability, and approximation quality.

heading: 5.1 Setup
text: 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 1 Input: Training data {(xi, yi)}ni=1, objective function v(R), threshold M for exact search 2 Decompose v(R) ≡ u(R)− w(R) 3 InitializeR ← ∅ 4 while true do 5 R̃ ← R ; R′ ← R 6 if |R̃| < M then R̃ ← Enlarge(R̃,M, u,w) end if 7 if |R̃| ≤M thenR ← BestSubset(R̃, u, w) end if 8 R ← DS-OPT(R, u, w) 9 R ← SwapLocalSearch(R, u, w)
10 ifR = 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 way as [14]. Specifically, for categorical features, two features xj = z and xj 6= z are created for each category z. For numerical features, we create comparison features xj ≤ z and xj > z via choosing sample deciles as the boundary value z. The number of binary features of each dataset after preprocessing is given in Table 1, 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 sets1, including CG [14] and BRS [49], 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 IP solver. This is exactly comparable to our method because we 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] is chosen. In addition, we 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, we fix β0 = β1 = 1 and optimize the remaining hyperparameters β2 ∈ {0.5, 0.1, 0.01}, λ ∈ {0.1, 1, 4, 8, 16, 64} and K ∈ {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 {10, 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 1 to 100 and fix the number of trees in RF to be 100.

heading: 5.2 Numerical results
text: 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 ran beyond our time limit, and CG is not available on COMPAS because we encountered an LP solver error. On small datasets, the accuracy of our submodular optimization based approach matches the CG based approach, and both of them are top-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
1We failed to run IDS [28] and DRS [51] on most of the datasets.
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.
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 ∑ R∈S |R|, respectively. The overlap is measured as the fraction of samples covered by more than one of the rules, i.e., |{i|P̃S(xi) > 1}|/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 100%-accurate rule sets on the mushroom and tic-tac-toe datasets are illustrated in Table 3. Remarkably, the rule set for mushroom is even simpler than the ground truth provided in the dataset description file [1], 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 a stationary point in a few iterations. Bit vectors are used in our implementation to process a large number of samples efficiently. Therefore for our algorithm the dimensionality is the main bottleneck in scalability. Figure 1 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 a 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.
mushroom
odor != a AND odor != l AND odor != n spore_print_color = r
gill_size = n AND stalk_surface_below_ring = y cap_color = w AND population = c
tic-tac-toe
top-right = x AND middle-middle = x AND bottom-left = x top-left = x AND middle-middle = x AND bottom-right = x
middle-left = x AND middle-middle = x AND middle-right = x bottom-left = x AND bottom-middle = x AND bottom-right = x
top-left = x AND top-middle = x AND top-right = x top-left = x AND middle-left = x AND bottom-left = x
top-right = x AND middle-right = x AND bottom-right = x top-middle = x AND middle-middle = x AND bottom-middle = x
0 500 1000 1500 2000 2500 3000 #features
0
50
100
150
200
250
tim e
(s ec
)
Training time vs Number of features gas musk
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 low-dimensional datasets, all of the subproblems could be exactly solved within 10 minutes using our customized BnB procedure. As the subproblems for remaining higher-dimensional 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 [V (Sbnb)−V (Sapprox)]/V (Sbnb). Results are summarized in the Appendix.
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 is because the outer loop (Algorithm 1) is also an approximation procedure, which does not guarantee that better subproblem solutions will help build a better solution to the main problem.

heading: 6 Limitations
text: Approximation guarantee. The main limitation of this work is the invalidity of approximation guarantee (Proposition 2) under inexact subproblem solving. Nonetheless, the approximation guarantee 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 a given pool (e.g., rules extracted from a 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 to multiclass classification. We have suggested the model-agnostic one-versus-one (OvO) transformation, which only requires the base classifiers to produce a binary class label, rather than a 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 is not very efficient because K(K − 1)/2 base classifiers must be trained for a K-class classification task. We are investigating if there is a more scalable approach to 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 a 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, a learned rule "IF X=x0 AND Y=y1 THEN Z=1" may not conform to the causal mechanism underlying the variables X, Y and Z. This will lead to misunderstandings if the rules are not interpreted properly.

heading: 7 Conclusions
text: In this paper, we propose a 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 to optimize a regularized submodular objective, and the subproblem selects a feature subset to form a rule. The optimization criteria of the subproblem is derived based on a 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 is 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.

heading: Acknowledgments
text: We thank the anonymous reviewers at NeurIPS 2021 for their insightful feedback.

Review summaries:
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.

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. 

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.