Discovering Classification Rules for Interpretable Learning with Linear Programming
Authors: Hakan Akyuz
Ilker Birbil
Venue: ICLR 2022 Submitted (2022)
Keywords: Rule generation
linear programming
interpretability

Abstract: Rules embody a set of if-then statements which include one or more conditions to classify a subset of samples in a dataset. In various applications such classification rules are considered to be interpretable by the decision makers. We introduce two new algorithms for interpretability and learning. Both algorithms take advantage of linear programming, and hence, they are scalable to large data sets. The first algorithm extracts rules for interpretation of trained models that are based on tree/rule ensembles. The second algorithm generates a set of classification rules through a column generation approach. The proposed algorithms return a set of rules along with their optimal weights indicating the importance of each rule for classification. Moreover, our algorithms allow assigning cost coefficients, which could relate to different attributes of the rules, such as; rule lengths, estimator weights, number of false negatives, and so on. Thus, the decision makers can adjust these coefficients to divert the training process and obtain a set of rules that are more appealing for their needs. We have tested the performances of both algorithms on a collection of datasets and presented a case study to elaborate on optimal rule weights. Our results show that a good compromise between interpretability and accuracy can be obtained by the proposed algorithms.

Under review as a conference paper at ICLR 2022
DISCOVERING CLASSIFICATION RULES FOR INTERPRETABLE LEARNING WITH LINEAR PROGRAMMING
Anonymous authors Paper under double-bling review
ABSTRACT
Rules embody a set of if-then statements which include one or more conditions to classify subset of samples in dataset. In various applications such classifica- tion rules are considered be interpretable by the decision makers. We introduce new algorithms for interpretability and learning. Both algorithms take advan- tage of linear programming, and hence, they are scalable to large data sets. The first algorithm extracts rules for interpretation of trained models that based tree/rule ensembles. The second algorithm generates a set classification rules through column generation approach. The proposed algorithms return a of rules along with their optimal weights indicating the importance of each rule for classification. Moreover, our algorithms allow assigning cost coefficients, which could relate to different attributes of the rules, such as; rule lengths, estimator weights, number of false negatives, and on. Thus, the decision makers can ad- just these coefficients to divert the training process and obtain a set of rules that are more appealing for their needs. We have tested the performances of both al- gorithms on collection of datasets and presented case study to elaborate on optimal rule weights. Our results show that a good compromise between inter- pretability and accuracy can be obtained by the proposed algorithms.
INTRODUCTION
Medical diagnosis, educational and juridical decisions often have important consequences for the society. Therefore, both the accuracy and interpretability of these decisions are of crucial impor- tance. In particular, these decisions should be understandable by the decision makers. Rule sets consisting of a few intuitively coherent rules have shown to accomplish this purpose in such domains (Lakkaraju et al. 2016). Here, we first aim at rule extraction from powerful ensemble methods and then solely focus on rule generation. In both cases, our objective is to obtain set of classification rules that balances the trade-off between accuracy and interpretability. Our main tools in this effort linear programming and column generation.
rule is an independent if-then statement, which contains one or more conditions that assign a class set of samples. For example in binary classification, "if (Clump Thickness is greater than six) and (Single Epithell siall Cell Size is less than four) then the tumor is malignant" such a rule that can be used for breast cancer diagnosis. When sample satisfies this rule, then it receives label corresponding to one of the two classes. In case a sample is covered by more than one rule, then majority voting among the assigned labels is used to determine the class of the sample.
Growing decision trees is closely related rule-based learning. Decision Tree (DT) naturally results with set of leaves, where each leaf corresponds to a different rule. On one hand, rule learning is considered to be more flexible for interpretability than tree-based learning approaches. Fürnkran (1999) lists superiorities of rule-based learning over tree-based learning. Leaves (rules) of a DT are not independent from each other. For example, in binary tree when a splitting is performed at node, the left child grows a rule, while its right sibling grows its negation. As result, every sample obeys to exactly one rule and it is classified according to the corresponding leaf. Thus, inaccurate rules, which negations of their siblings after splitting, can be created. This

---

Under review as a conference paper at ICLR 2022
may render false classification of samples and reduce both accuracy and interpretability. However, independently constructed rules do not need such a negation rule, and hence, rule-based learning can be considered more flexible for interpretability. On the other hand, unlike DTs, an independent set of rules does not necessarily cover the entire sample space. This may result in a state where a test sample can not be classified with the proposed rule set. This drawback is often handled by assigning a default label to those uncovered samples (Fürnkranz et al.] (012)). To minimize the number of uncovered samples during testing, the training data required be fully covered. Separate-and- conquer algorithm by Fürnkranz (1999) achieves this heuristically by fitting rules on uncovered training samples, and new rules are generated until each training sample covered by at least one rule. Instead of such a sequential covering, we take advantage of our linear programming (LP) approach and explicitly impose a covering constraint on the training set.
In this paper, we propose two algorithms for interpretability and learning that are based on mathe- matical programming. We give generic LP model that is first used by our Rule Extraction (RUX) algorithm, which selects rules from trained tree or rule ensembles for interpretation. Then, we develop a Rule Generation (RUG) algorithm, which generates classification rules using column generation (CG) solve the LP model.
Rule extraction methods attempt to select a set of rules from accurate complex or black- -ox models to interpret the predictions of these models (Hayashi & Oishi 2018). For instance, several works in the literature aim at interpreting Random Forest (RF) models by extracting rules from the trees in the forest (Liu et al. 2012 Lu Thi et al.] 2015 Adnan & Islam 2017: Wang et al.
2020 Birbil
iet al. 2020). Most of these studies use heuristic approaches to select the desired set of rules. Birbil
al. 2020 suggest a set covering formulation to extract intrepretable rules from RFs. Other appli- cations include extraction of rules from artificial neural networks (Andrews et al., 1995) and support vector machines (Barakat & Bradley 2010). As a remark, there are other post-hoc interpretabil- ity approaches in the literature such as SHAP (Lundberg & Lee| (017)) and LIME (Ribeiro et al.) 2016) that are considered to be model-agnostic. However, our RUX algorithm is a model-specific approach.
There are several studies that are closely related to ours, since they also employ mathematical pro- gramming for rule learning. Malioutov & Varshney (2013) propose rule-based binary classifier solving a binary program that minimizes the number of rules for a boolean compressed sensing problem. Wang & Rudin (015)) present a mixed integer linear programming (MILP) formulation to learn decision rules for binary classification (e.g.. patterns). They give a discussion on how their classifier is equivalent to DT's and RFs. The MILP formulation is solved using generated rules with an objective of minimizing the number of misclassified samples, the number of rules generated, and the total length of each rule. |Dash al. (2020) offer CG-based framework to find optimal rule set for binary classification, where the objective is to find a trade-off between classification rule simplicity and accuracy. One-hot encoding is used to binarize categorical data, and numerical data is also discretized with sample deciles as thresholds. For large instances, the pricing subproblem is either solved with time limits, or the model columns are generated by a greedy heuristic. |Wii et al. (2019) propose generalized linear rule models using a similar CG framework of the work by Dash et al. (020). Malioutov & Meel (2018) solve Max-Sat formulation by constraint programming to construct interpretable classification rules. Ghosh & Meel (2019) also propose framework based on MaxSAT formulation that can be applied to binary classification problems with binary features to minimize the number of generated rules and the number of misclassified samples. Their approach is incremental and takes advantage of partitioning the data set into several clusters.
Contributions. RUX and RUG are based on an LP model and thus, both algorithms are scalable for large datasets. This is an important advantage compared to the existing studies that use MILP formulations. The proposed algorithms directly address multi-class problems while the existing studies using optimization-baan
approaches are for binary classification. To that end, the objective function in our L.P formulation minimizes classification error using a loss function instead of explic- itly counting misclassified samples. Both RUX and RUG can work with continuous or categorical features, and hence, they do not require encoding of the data. Along with the set of rules, our al- gorithms also return the optimal weights for the rules. These weights allow to attach importance to each rule for interpreting the classification. Our algorithms admit assigning cost coefficients to the rules. These coefficients could relate to different attributes of the rules, such as; rule lengths, estimator weights, number of false negatives, and so on. The objective function also allows penaliz-
2

---

Under review as a conference paper at ICLR 2022
ing rules that may have undesired outcomes (like long rule lengths). Thus, the decision makers can use these coefficients to lead the training process to obtain a set of rules that are more appealing for their needs. The novelty in column generation approach is the use of regular decision tree with sample weights as the pricing subproblem. Training trees with sample weights is very fast, and also standard in all machine learning packages boosting methods also rely sample weights. Lastly, we present our algorithms for multi-class classification problems. However, the proposed ideas can also be extended to discovering regression rules for interpretable learning with linear programming.
RULE EXTRACTION
We consider classification problem with K classes and denote the set of class labels by K. The training dataset consists of samples with features æ; E IR" for E I and labels for E I. To work with multiple classes, we define a vector-valued mapping y(x)) K. R K in Zhu et 2009). That is, if yj k. then
y(x;) = (-x- K-1
JT,
(1)
where the value one appears only at the kdth component of the vector.
Suppose that we have collection of rules indexed by J. A rule j I assigns the vector R (2;;)
K. input 2; only if rule covers sample This vector also formed in the same manner as in equation [ To predict the class of given sample with this collection of rules, we use set of nonnegative weights w.. E I associated with the rules and evaluate
U(x;)) = Σ any (a, JEJ
where dzy {0,1) } indicates whether rule j covers sample not. Then, the index of the largest component of the resulting vector (xx)) is assigned as the predicted label i of sample E I. Note that equation 2 is similar to the weighting of the classifiers in standard boosting methods. Here, instead of classifiers, we use rules for classifying only the covered samples.
In order to evaluate the classification error, we use the hinge loss and define the total classification loss by
Σ NET
max {1 (1-}
Σ āij 0}. JET
where ā;j = Kaij (x:)) with k = (K-)) T/KKTTii This loss function allows us to write a linear programming model, where the objective is to find the of rules that minimizes the total loss. To this end, we introduce the auxiliary variables v; i E I standing for es 2 max {1 {1- ΣSEs Wz 0}.
and obtain our master problem
minimize subject to
Eier 1/ + +EjEJ 1j
Ejer uigWy + 11, iE I: i I: Ejer AijWy" 26,
(3)
2 2 0,
i i I:
Wj 2 0,
j E J.
where 2 j E J are the cost coefficients. These coefficients and the second set of constraints require further explanation. The cost coefficients serve two important roles: First, solutions involv- ing many rules with nonzero weights are avoided. The less the number of rules in the resulting set, the easier it is to interpret solution. In other words, we prefer sparse solutions and e, serves to that preference. Second, in many different application domains, rules have actual costs that need to be taken into consideration. As we also highlight in our title, when interpretability one could try to obtain rules with few features because shorter rules are considered to be easier to interpret (Lakkaraju et al. 2016). this case, the number of conditions a rule can be set as the rule cost. As another example, consider a classification problem in medical diagnosis, where false negatives are likely to be perceived as more costly than false positives. Such an evaluation could also be easily incorporated with rule cost in the proposed model. We should point out that there
of concern,
3

---

Under review as a conference paper at ICLR 2022
exists trade-off between model accuracy and the rule set size. This can also be handled with our formulation by introducing a fixed cost coefficient, i.e,, using the same value for all Cj. J E J.
The master problem equation also involves set of covering constraints with the fixed right-hand- side, e > 0. These constraints make sure that each sample is covered by at least one rule. The need for these covering constraints is exemplified follows:
Consider a binary classification problem, where we select three samples {æ,, Lk. 2x, along with their labels y: = 1, yk -1 and yi -11 Suppose that we have two rules j and j' such that the former covers all three, whereas the latter covers only the last two samples. Here, the rules use majority voting as it is applied to the leaves in trained DTs. The labels assigned by the rules j and j' are
as follows: R2 (z;) = (x(x)) ) = Rg (xi) = -1 1 and R (Ix) = Ry(( = -1.
The first set of constraints in equation 3 then becomes
W
+
1
WkjW;
Wok
+Uk
1.
aijWi
+UI
1.
For simplicity, if we also assume that Cj cy. then the optimal solution becomes
w = Ukk = 2i = 0 and wy = 02 1. With this solution, sample æ; is not covered.
We remark that covering each sample in dataset is crucial from the perspective of giving literal interpretation with the obtained rules. This is particularly important when the resulting set of rules is used interpret the classification of individual samples in the dataset. Clearly, varying e may lead to a change in the set of optimal rules. For instance a large & value may impose larger rule weights on those samples covered with only few rules. However, we point out that the role of this constraint is just coverage, and hence, setting & to a small strictly positive value is sufficien
Up until this point, have not specified any details about the rule set J. On one hand, this rule set can be static in the sense that it can be obtained by extracting the rules available through a trained tree ensemble algorithm or by using the rules resulting from rase- method (Cohen & Singer 1999). For instance, consider a RF model trained on a given dataset. Then, the rule set J can be obtained from the leaves of the trees in the forest, since each leaf corresponds to a rule. Solving equation Enntionnnwiith such rule set allows us to extract the rules that were most critical for classification. As we have mentioned before, we can assign the length of rule as its cost and try to obtain rules with desirable lengths for interpretation. In a similar vein, consider another example with a trained AdaBoost (Freund & Schapire 1997) model for which the base estimators are set as DTs. Again, the leaves of the trees from AdaBoost can be used to construct the rule set J in equation 3 which is then solved to extract an interpretable set of rules. The costs of the rules in this case could be the inverse of the estimator weights assigned by the AdaBoost algorithm to the trees. In this way, the obtained set of rules is more likely to inherit the importance of the DT's from the AdaBoost model. Using these trained models construct our master problem leads to our first algorithm RUX, which is based on tree ensembles. We show in Section that RUX can indeed extract only selection of rules from the trained models without significantly sacrificing accuracy. The computational complexity for RUX is determined by the underlying LP solver used. In practice, most of the LP solvers use interior point methods that work in polynomial-time.
RULE GENERATION
Suppose now that we do not have the entire set of rules I explicitly, or the size of this collection is too large to be constructed by an existing learning framework. Notice that, the universe of rules J contains exponentially many rules due to all possible combinations of different levels of the considered features. This aspect shows the combinatorial structure of the problem. Thus, the rules should be generated an iterative fashion. Since equation
3 is a linear programming problem
In case one insists on treating E as a hyperparameter and proceeds with tuning. it is important to know that there will be intervals of values where the optimal set of rules remains the same. We have given this parametric analysis in Section A.2 of the supplementary document. Using this analysis, the tuning can be conducted in computationally efficient manner.
4

---

Under review as a conference paper at ICLR 2022
and rules correspond to columns, this iterative scheme leads to the well-known column generation approach in optimization (Desaulniers et al. 2006). At each iteration of column generation, a linear programming model is constructed with a subset of the columns (column pool) of the overall model. This model is called the restricted master problem. After solving the restricted master problem, the dual optimal solution is obtained. Then using this dual solution, pricing subproblem is solved to identify the columns with negative reduced costs. These columns are the only candidates for improving the objective function value when they are added to the column pool. The next iteration continues after extending the column pool with the negative reduced cost columns.
In order to apply column generation to our problem, we define subset of rules Jr C J at iteration t and form the restricted master problem by replacing J with J. in equation Let us denote the dual variables associated with the first set of constraints by 3r E I. Likewise, let "s i E I be the dual variables corresponding to the coverage constraints. In vector notation, we simply use B and y. Then, the dual restricted master problem at iteration t becomes
maximize subject to
Ever (B, + +%%)
EEEI (diz + asy71) S S.z j Tn:
0 S 3 L 7 2 0,
i I;
i I.
If we denote the optimal dual solution at iteration by (0() and (1), then improving the objective function value of problem equation 4 requires finding at least one rule j' TT/ such that
Σ (agg aig (1)) <<0 O,
By = cj'
(5)
where õy is the reduced cost of column jr. In fact, this condition simply checks whether j' E J J violates the dual feasibility. To find those rules with negative reduced costs, we formulate the pricing pricing subproblem as
max JEJ/J
Eaye
+ aiyh (0)
(6)
Linear programming theory ensures that if the pricing subproblem does not return any rule with a negative reduced cost, then we have the optimal solution to our master problem equation [ with the current set of rules, T.. Otherwise, we have at least one rule with a negative reduced cost. After adding one more rules with negative reduced costs to Jr. we proceed with J++1 and solve the restricted master problem or, equivalently, its dual equation 4 Algorithm shows the steps of the exact rule generation approach. It is important to note that the sole purpose of solving pricing subproblem equation
6 is to return a subset of rules with negative reduced costs. We denote this
subset by J_ S J/Tr-
[lh] Exact Rule Generation Input: training data, (I;, t = 0 Construct initial rule pool, To True (g(() (1)) < Solve equation
J_ + Solve pricing subproblem, equation 6 J_
return J, t + Jr T--UU
We have overlooked two important steps in Algorithm| 3 The first one is the construction of the initial rule pool To (line three). One possible solution for this step is to train DT and use its leaves as the starting set of rules. The second step is solving the pricing subproblem (line six). Note that solving equation associated with finding a rule with the highest accuracy when the samples have weights 8 E I. As constructing an optimal binary decision tree is known to be -oP-copleeee Lauurent & Rivest 1976), solving problem equation 6 is rather difficult even when (()) = O. This leads us to the proxy pricing subproblem of column generation shown in Figure Here, treating % 0 allows the construction of a DT using the dual values (t()) as sample weights. DTs can be solved very quickly using standard libraries that are available in all machine learning packages. Therefore, we propose to train DT as heuristic pricing approach, where the sample weights correspond to dual variables (tt) E I. Then, we can check whether any leaf of the DT satisfies equation 5 before adding those rules to the current rule pool. Notice that negative reduced cost column (rule) with 7/2 = O would also have a negative reduced cost when the pricing subproblem is solved exactly.
5

---

Under review as a conference paper at ICLR 2022
Initial Rule Pool
Proxy Pricing Subproblem
Ju
g
Solve Dual Model (4)
DecisionTrve(e)
DecisiorTree(
3
T.
J. - I1-1 UJ-
J_
0
DovE
Figure Proposed rule generation algorithm.
Figure shows the proposed heuristic approach for rule generation. The procedure DecisionTree takes vector of sample weights as an input and returns set of rules J (leaves of the decision tree). The vector e is the vector of ones. The subset J- S I contains those rules with negative reduced costs satisfying equation 5 As we use the dual solution ((t) only for checking the reduced cost, training decision trees with sample weights this manner boils down solving proxy pricing subproblem. Indeed, our rule generation algorithm RUG does not guarantee to solve the overall problem equation 3 to optimality. Fortunately, this may to our advantage since a sub- optimal solution can rectify the problem of overfitting to the training data. In fact, overfitting due to exact optimality is a common concern also in recent optimization-bazn
approaches to lcarning (Günlük et al.) 2018 Verwer & Zhang 2019). Avid readers of optimization- learning would also notice that there are some connections between RUG and the boosting methods. We elaborate on this point in Section Section|A.3Jof the supplementary document.
We remark once again that growing decision trees with sample weights a standard tool in every library machine learning. Likewise, there are various options solve linear programs. Both growing DT's and solving I.Ps can be achieved in polynomial-time. Therefore, the proposed algo- rithm in Figure 3 extremely easy implement with the existing packages of popular programming languages.
COMPUTATIONAL STUDY
We have evaluated the performances of the proposed algorithms on collection of frequently used datasets. The details of these datasets given in Section the supplementary document. Both the rule extraction (RUX) and the rule generation (RUG) algorithms are implemented in Python H Since our computation times do not exceed one minute even on standard laptop computer, we do not report them here. We have used stratified 10 x 3 nested cross validation to estimate the generalization performance of the tested methods. In all experiments, the right-hand-side value of each covering constraint is set to E = 0.01
4.1 NUMERICAL EXPERIMENTS
First, we apply our RUX algorithm trained random forest (RF) and AdaBoost (ADA) models. For both RF and ADA, we have selected the eeximun-dept. parameter from the set {1,2, 3} and the number ceabber-of-ee f-setttiii i mimmtto torr parameter from the set (100, 200). After obtaining the best parameter set, we have used the corresponding trained model to apply RUX. We denote the models after applying RUX to RF and ADA by RUX-RF and RUX-ADA, respectively. In RUX-RE, we have used the rule-length cost coefficients are assigned as the inverse of the estimator weights of the trees in the trained ADA model. That is, the rules coming from the same tree receive the same cost coefficient.
the cost coefficients Cj. j E J in equation 3 For RUX-ADA, the
"Our implementation is available in the supplementary file.

---

Under review as a conference paper at ICLR 2022
Table I summarizes our results. Overall, we observe that RUX-RF and RUX-ADA give accuracies on par with RF and ADA. In fact, RUX-RF can even outperform RF on several datasets. These BANKNOTE, TICTACTOE, ADULT, BANK-MKT, MAGIC, MUSHROOM, MUSK, PHONEME and MAMMOGRAPHY On average, RUX-RF and RUX-ADA obtain far fewer number of rules than their counterparts RF and ADA, respectively. When we compare RUX variants, we observe that RUX- ADA generally obtains smaller sets with shorter rule lengths than RUX-RF. This is due to the larger trees preferred by RF models as the average number of rules obtained with RF is higher than ADA. Take for instance GLASS and SENSORLESS, for which ADA returns more rules than RF. For those instances, we clearly see that the average rule length resulting from RUX-RF is smaller than those from RUX-ADA.
Table 1: The performances of Random Forest (RF), AdaBoost (ADA) as well as Rule Extraction applied to RF and ADA denoted as RUX-RF and RUX-ADA. In the table, ACC., RULES, and RULE LEN. stand for accuracy, number of rules and rule length, respectively. The first value in each cell gives the mean, whereas the value in parenthesis gives the standard deviation.
DATART
EF
APM
RUX RF
RIX ADA
BANKNOTE
2:922 (3.015)
ACC
1935.5
5351
0,599 (8.203)
(338.274)
0.991 COO
ACC:
16.2 544
2.15 (LD81)
0.562 (3.030)
XDC
(15:(15.403)
1.564 (0,533)
HEARTS
8.412 (991
753
L0N0 415)
0.815 18
23018053 3450
515
1944
28. 3..9
1000 10000000033
FONDSPIRRE
2/924 1221
19222 7921
0.866 18:3413
119
0233 1811
0912001011
$2.216.3
01 1621
61:3117 (02)
PIMA
5.755 0333
1355.7 (009 -09
0.360 (5.374)
(1461144
0.743 00 0480
175.5
2.643
1 0..055
0.753 (3-137
$5.4 2011
1,300 (0-41:3
1151
10:200)
TRANSPUSION
07750 1221
145.8 1122
0.794
0123-3333300 5551
0.099 10
26.5
214 5354
00.303
(3:21:)
66/1
1.300 10:4553
2.744 (100)
038-33683000 2091
1.870 (0.376)
612.0:345-41
01 775
2.032
1663-23-27)
20.6 5155
1180
ADULLT
1587.5
125
0.557 (06)
065
0.50:33-033
(8:036)
BANK MKY
0:78: (2.1144)
1527-1 1220
11:44 15.3123
1271:2 300)
0.525 01012)
257 270
2 5544 (00000
0.844 (3-09)
232-2 0716
0.00000 10.20-1
MESSEROOM
3:481 (3 (933)
1013 0338 7077
1,000 (0-300)
141-3:115000 5.858)
Lam 600
11:661056 056
1.07 m 160
1 (-030)
12-3
1153 761
DOLSPILL
2:057
(403 1421
0.570 10.2003
1058 (44.23
0.65 (0.035)
60.7 155
2.359
(3-234)
$1.019.00
(5.27%
0.000 (8.01)
1353.5 0383 5451
01555 10.320)
44.33
0.545
1662-22.83
2.56 (1.02)
0.865 2-013)
(98/4110991)
MASHMOGRAPHY
1036
401
105
303)
SERDS
2-410 1963)
533-5.000-0 555)
ILAA 18-2783
1105 584)
1.20% 1890
120 m
5m
(8.543)
CLASS
2:487 (773)
1253.7 (355 563)
0.796 (5-206)
(134-11233400
0.799 0 0730
2 2.564 0 160
0.116 (3113)
15.5 06 755)
2742 (0/248)
NON-OOLEESS
0:288 (991
143% 2112 96.1
0.99
1100 (53)
09.001
211 15:210:214)
ANTRAGE
310 (901
220
(9335)
We report our results with the proposed RUG algorithm in Table 2 we have also added a DT algorithm for comparison. The same set of values {1, 3} used for tuning the maximum-deep. parameter both in DT and RUG (for constructing the initial column pool and the proxy pricing subproblem; see Figure T In RUG, we have used the rule length as cost coefficients. When we compare the accuracies of different methods, we observe that the average performance of RUG is better than those of DT and RF, and close to ADA. Since the resulting models from DT are interpretable, DT. RUG outperforms DT in terms of accuracy at the expense of generating more rules. However, the average lengths of the rules obtained with RUG are shorter than those obtained with DT in all instances.
In addition to RF and ADA,
also report the rule numbers well as the rule lengths for
In their recent work. Dash et al. (2020) propose rule learning approach based on column gen- eration. They also give a comparison against other studies and present that their algorithm shows one of the best performances. We compare their results against variant of RUG in Table 4 of the supplementary document (Section A.4. We remark that their numerical study is limited to binary classification instances, and hence, the benchmarking is conducted only on subset of datasets that we have used in our previous two tables. On average, our results are on par with the results obtained with their method in terms of accuracy and interpretability. variants and RUG are an order of magnitude faster on large datasets than the approach of Dash et al. 2020). Section A.4 of the supplementary document involves a further discussion.
important to note that both RUX
When it comes to the scalability of our algorithms, our preliminary results on large instances are very promising and favor of RUG in terms of both accuracy and interpretability. RUX variants also surpass the accuracy of their corresponding trained models from both RF and ADA. We also observe that RUG outputs comparable computational times with RF and ADA. Our results are presented and discussed in detail in Section of the supplementary document.
Even though RUX variants and RUG obtain few number of rules with short lengths for many datasets, there also several datasets where the resulting sets of rules are still challenging to interpret. However, note that the results that we present in Table Table given for all rules with nonzero optimal weights. Using a threshold weight for rule and monitoring the accuracy,
7

---

Under review as a conference paper at ICLR 2022
Table 2: The performances of Random Forest (RF), AdaBoost (ADA), Decision Tree (DT) and Rule Gen- cration (RUG). Here, ACC., # RULES, and RULE LEN, stand for accuracy, number rules, and rule length, respectively. The first value in each cell gives the mean, whereas the value in parenthesis gives the standard deviation.
DATASET
ADA
PT
RLG
FRULES
RULE
FRULES
LEX.
BANKNOTE
(0.018)
0.999
(03)
0.937
8.0.0.0)
(.0
2.063 (0 (36)36)
HEARTS
(0.059)
0.815
0.775 (0 041)
7.4(1.877)
(0.63))
(0.066)
035)
1.169
ILPD
(0,11:
0.700
1.0
(0.042)
(4 253)
1.493
JONOSPHERE
(.1
2.510.527)
41.6
(0.060)
0.747
068)
2.110.675)
08.88)
33.55 (26.44)
(..49(0
PIMA
0.359 (0.03))
0,760 (0.054)
4.4(1.265)
(0.31)
(0.057)
26.8 206)
(0.39)
TICTACTOE
(0.049)
1,000
8.0.0.00
5.0
0.968
865)
TRANSFUSION
11766 (0:025)
0.794 (0.030)
0.75% (0.035)
6.012.667)
2.4 (0.34))
0.775 (0.033)
1.771
WDBC
(0.020)
0.970 (0.026)
0.919/0.030)
7.0(1.633)
2.8 (0.422)
0.965 (0.025)
(91.
2,034
(0.452)
ADULT
0.798 (0:064)
0.866 0044)
844-4000 005)
8.0.00.01
(0.0)
0.859
5144 213)
(8:
MKT
(0:014)
0.344 (0.012)
0.775
0006
8.0.00.1
3.0 (0.0)
0.852 (0.810)
113.5 142)
(1)
MAGIC
0. 2.804:0.007)
0.872
004)
0.787
(0 009)
7.2(1.687)
2.8 (0.20.422)
0 865 (0 007)
96.4 172)
2.47 (0, 301)
MUSHROOM
0.981 (0.008)
1,000
000)
0.985
0044
7.0
3.0 (0.0)
1,000
11:2.(4
2.138 177)
MUSK
0.904 (0.007)
0.994
(0.003)
0.915 (0.011)
8.0
3.0 (0.0)
0.940 (0.007)
26.4 055)
2.78 (0.081)
OILSPILL
0.957 (0.000)
0.970 (0.011)
0.963 (0.0133
(.6
2.2 (0.422)
0.962 (0 (0.010)
36.3 557)
1.642 (0.507)
PHONEME
01800 (0.017)
0.85% (0 (38)
0.769 020)
62012.108)
2.5 (0.527)
0.863 (0 021)
91.1 503)
2.318 (8.078)
MAMMOGRAPHY
119833 (0.002)
0.987 (0.00) (015)
0.954 (0.002)
(.691)
2.7 (0.4K3)
0.986 10 (015)
62.3 (2.3)2))27))
(. (0.25)
SEEDS
1,910 (8.04)
0.933 (0.078)
(0.00)
6.2 (1.311)
2.8 (0.422)
0.914 10.)
(1.2
2.029 (0. 209)
WINE
IL978 (0.039)
0.955 (0.051)
0.904 (0 071)
(1.66)))))
(.00
0.950 (0 067)
19.0 342)
1.52 (0. 114)
GLASS
116887 (0.072)
0.794 (0. 066)
0.687 056)
7.7 (..75)
(.00)
0.640 (0 084)
(10:41))
2.545 (0. 207)
ECOLT
0.854 (0.055
0.836 (0005)
0.804 (0 04
(.000.0)
(.00
0.816 (0.00) 062)
16.5 06.1)
2 2.498 (0.211)
SENSORLESS
0.768 (0.008)
0.892
(0.014)
0.425
(0 0025
6.0.00.)
3.0
0.690 (0 038)
(44447))
2.744 (D. 097)
AVERAGE
1RLE4 (0.033)
0.857 10.030)
0.512 (0.029)
6,273 (0.9931
2.677 (0.259)
0.858 10.030)
44
(1..61
2.082 (0.291)
one can end up with set of rules that is easier to interpret. We elaborate on this point in the next subsection with a case study.
4.2
CASE STUDY
We demonstrate an interpretation of RUG results using "Breast Cancer Wisconsin (Original)" dataset (Dua & Graff 2017). This dataset has nine features with integer values from [1, 10) and two diagno- sis classes (henign or malignant). RUG reaches the accuracy level of 0.96 and generates 18 rules that we denote as R2 to Ris. Figure shows that RUG can also attain accuracy level of 0.95 using only the first 12 rules. The plot given in Sigureebe used by decision makers (DMs) to interpret the rules and their weights obtained with RUG. The horizontal axis lists the rules in descending order of their optimal weights assigned by RUG. Here, the rule weights shown on the left side of the vertical axis normalized by dividing the weights with the largest among them. On the right side, present the accuracy of RUG on the test data cumulatively adding one rule at a time in the model. In other words, using only the first rule results with the accuracy of 0.92. With the addition of second and third rules, the accuracy level increases to 0.93. This can be traced following the blue line and the corresponding point for each rule. When rule twelve is added, the accuracy of RUG catches that of the RF. As remark, there is a slight deterioration in the accuracy when rule four is included and it rebounds back with addition of rule eleven. This can be expected since the performance is evaluated on the test data. Above each bar in the plot, we give the cumulative percentage of test instances covered by the rules. That is, rule one covers 73% of the test data and coverage gradually increases with the addition of subsequent rules. The coverage of samples reaches to 95% with only three rules and when the first nine rules are used, the coverage becomes full. Overall, interpretability plot is a playground for DMs to choose the best trade-off between accuracy and interpretability depending on the sensitivity of the application. Further details on our case study is presented in Section A.5 of the supplementary document.
5 CONCLUSION
We have proposed a linear programming (LP) approach to discover a set of critical rules in multi- class classification. The objective of this LP is to find a set of rule weights such that the sum of the classification error and the total rule cost is minimized. Using the optimal weights of the LP, a set of interpretable rules is obtained that can be used for classification. This approach has led to two algorithms that are both simple, fast and eas-tto-implement The numerical experiments have shown that the proposed algorithms may be used for hitting the right balance between accuracy and interpretability.
8

---

Under review as a conference paper at ICLR 2022
73.0%
10
10
0.8
0.8
Mean Accuracy
Rule Weight
0.6
0.6
0%
95.0% 98.0%
0.4
0.4
98.
98,
99
100
0%200 0%
0.2
100 0%000 0%
0.2
0.0
0.0
2
3
10
11
12
Rules
Figure 2: Interpretation plot. RUG surpasses accuracy level of DT by using the first 3 rules that ordered terms of their normalized weights (bar heights). The percentages show the cumulative fractions of the samples covered after adding each rule.
The first algorithm works with predefined set of rules. To demonstrate algorithm, have used the models trained by Random Forest and AdaBoost algorithms. These two algorithms are frequently used for their remarkable accuracy. However, it is very difficult to interpret the trained models as both algorithms return tree ensembles involving thousands of rules. With Random For- est, we have used the rule lengths cost coefficients in algorithm to obtain shorter rules for interpretation. As AdaBoost returns also a set of estimator weights, we have used these weights as cost coefficients show that the performance of our rule extraction algorithm is close to -for several datasets even better than- its ensemble counterparts. More importantly, this performance comes with much fewer rules than the rules produced with both Random Forest and AdaBoost. On one hand, the set of rules required to apply our rule extraction algorithm may result from tree ensembles. On the other hand, this set may also come from other learning methods such as rule ensembles that produce large collection rules. Testing our algorithm further with those rule ensembles is an interesting future research direction.
mimic the performance of the trained AdaBoost model. Our numerical results
Instead of a given collection of rules, our second algorithm uses a rule generation mechanism that iteratively solves LPs and builds up set of rules. This algorithm has solid mathematical basis as its core idea comes from the well-known column generation approach in large-scale linear pro- gramming. A significant advantage of this algorithm is having the rules. However, there a challenge that lies within the difficult exact pricing subproblem. As remedy, we have proposed solve proxy subproblem by training decision trees with sample weights. These sample weights are obtained from the dual of the LPs at that iteration. Decision can be easily trained with the existing software packages, and hence, this proxy pricing prob- lem can be implemented quite efficiently. We have compared the performance of our rule generation algorithm with the highly interpretable Decision Tree algorithm, and with the highly accurate tree ensemble algorithms, Random Forest and AdaBoost. At the expense of more but shorter rules than Decision Trees, our rule generation algorithm performs on par with tree ensemble algorithms in terms of accuracy.
control the generation of
This study conducted for multi-class classification. With a piecewise-linear loss function (e.g. mean absolute deviation), our LP model can also be reformulated for regression problems. An alternative approach can be to incorporate the dual values corresponding to coverage constraints within the solution of the proxy pricing subproblem. This might require developing specially tailored DT that use all the dual values. These are other lines of research that we plan to pursue in the future.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Md Nasim Adnan and Md Zahidul Islam. Forex++: A new framework for knowledge discovery from decision forests. Australasian Journal of Information Systems, 21, 2017.
Robert Andrews, Joachim Diederich, and Alan B Tickle. Survey and critique of techniques for extracting rules from trained artificial neural networks. Knowledge-based systems, 8(6):333-389, 1995.
Nahla Barakat and Andrew P Bradley. Rule extraction from support vector machines: review. Neurocomputing. 74(1-3):178-190, 2010.
S. liker Birbil, Mert Edali, and Birol Yuceoglu. Rule covering for interpretation and boosting. arXiv preprint arXiv:2007.06377 2020.
William W Cohen. Fast effective rule induction. Machine learning proceedings 1995, pp. 115- 123. Elsevier, 1995.
William Cohen and Yoram Singer. A simple, fast, and effective rule learner. AAAIAAAI, 99 (335-342):3 1999.
Sanjeeb Dash, Oktay Günlük, and Dennis Wei. Boolean decision rules via column generation. arXiv preprint arXiv: 805,09901, 2020.
Ayhan Demiriz, Kristin P Bennett, and John Shawe-Taylor. Linear programming boosting via col- umn generation. Machine Learning, 46(1-3):225-25, 2002.
Guy Desaulniers, Jacques Desrosiers, and Marius M Solomon. Column generation, volume 5. Springer Science Business Media, 2006.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL httt::
ics uci edu/ml
Yoav Freund and Robert E Schapire. A
generalization on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-13) 1997.
Jerome H Friedman, Bogdan E Popescu, et al. Predictive learning via rule ensembles. The Annals of Applied Statistics, 2(3):916-954, 2008.
Johannes Fürnkranz. Separate-anddcooquuer rule learning. Artificial Intelligence Review, 13(1):
3-54, 1999.
Johannes Fürnkranz, Dragan Gamberger, and Nada Lavrač. Foundations of rule learning. Springer Science & Business Media, 2012.
Bishwamittra Ghosh and Kuldeep Meel. Imli: An incremental framework for maxsat-based learn- ing of interpretable classification rules. In Proceedings of the 2019 AAAI/ACM Conference AI, Ethics, and Society, pp. 203-210, 2019.
Adam J Grove and Dale Schuurmans. Boosting in the limit: Maximizing the margin of learned ensembles. In AAAI/AAI, pp. 692-699, 1998.
Oktay Günlük, Jayant Kalagnanam, Matt Menickelly, and Katya Scheinberg. Optimal decision trees for categorical data via integer programming. arXiv preprint wtX.v:1662..322200 2018.
Yoichi Hayashi and Tatsuhiro Oishi. High eccuracy-priority rule extraction for reconciling accuracy and interpretability in credit scoring, New Generation Computing, 36(4):393-418, 2018.
Miroslav Kubat, Robert C Holte, and Stan Matwin. Machine learning for the detection of oil spills in satellite radar images. Machine learning, 30(2):195-21) 1998.
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 2016.
international conference knowledge discovery and data mining, pp.
10

---

Under review as a conference paper at ICLR 2022
Hyafil Laurent and Ronald L Rivest. Constructing optimal binary decision trees is np-complete. Information processing letters, 5(1):15-17, 1976.
Sheng Liu, Ronak Y Patel, Pankaj R Daga, Haining Liu, Gang Fu, Robert Doerksen, Yixin Chen, and Dawn E Wilkins. Combined rule extraction and feature elimination in supervised classifica- tion. IEEE transactions on nanobioscience, 11(3):228-236, 2012.
K. P. Lu Thi, N. C. Vo Thi, and N. H. Phung. Extracting rule rf in educational data classifica- tion: From a random forest to interpretable refined rules. In 2015 International Conference on Advanced Computing and Applications (ACOMP), pp. 20-27, 2015.
Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Proceedings of the 31st international conference on neural information processing systems, pp- 4768 4777, 2017.
Dmitry Malioutov and Kuldeep S Meel. Mlic: A maxsat-based framework for learning inter- pretable classification rules, In International Conference on Principles and Practice of Constraint Programming, pp. 312-327. Springer, 2018
Dmitry Malioutov and Kush Varshney. Exact rule learning via boolean compressed sensing. In International Conference on Machine Learning, pp. 765-773. PMLR, 2013.
Llew Mason, Jonathan Baxter, Peter L Bartlett, and Marcus R Frean. Boosting algorithms gradient descent. In Advances neural information processing systems, pp. 512-518, 2000.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "why should trust you?": Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16, pp. 1135-1144, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781 4503422222 2939778. URL https: http://ooo.rgg/1///// 00....115229922... 2939777
doi: 10. 10.1145/2939672.
Robert E Schapire, Yoav Freund, Peter Bartlett, Wee Sun Lee, et al. Boosting the margin: A new explanation for the effectiveness of voting methods. The annals of statistics, 26(5):1651-1686, 1998.
Guolong Su, Dennis Wei, Kush R Varshney, and Dmitry M Malioutov. Learning sparse two-level boolean rules. In 2016 IEEE 26th International Workshop on Machine Learning for Signal Processing (MLSP). pp. 1-6. IEEE, 2016.
Sicco Verwer and Yingqian Zhang. Learning optimal classification trees using a binary linear pro- gram formulation. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp.
2019.
Sutong Wang, Yuyan Wang, Dujuan Wang, Yunqiang Yin, Yanzhang Wang, and Yaochu Jin. An improved random forest-based rule extraction method for breast cancer diagnosis. Applied Soft Computing, 86: 10591,, 2020.
Tong Wang and Cynthia Rudin. Learning optimized or's of and's. arXiv preprint 1111v:1511.002110 2015.
Tong Wang, Cynthia Rudin, Finale Doshi- Velez, Yimin Liu, Erica Klampfl, and Perry MacNeille. A bayesian framework for learning rule sets for interpretable classification. The Journal of Machine Learning Research, 18(1):2357-235
2017.
Dennis Wei, Sanjeeb Dash, Tian Gao, and Oktay Günlük. Generalized linear rule models. arXiv preprint 1rXiv:1906.01777 2019.
Zhu, Hui Zou, Saharon Rosset, and Trevor Hastie. Multi-class adaboost. Statistics and its
Interface, 2(3):349-360, 2009.
11


Reviews:
[{"review_id": "yUZnX4dgRK4", "reviewer": "Reviewer_Pz5i", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strength: an easy to implement method to select some rules from an existing set of rules, or by iteratively generating them through decision trees. Using LP allows for some scalability, even if modern MILP and SAT solvers could handle quite large instance (and certainly the thousands of rules considered in the experiments). \n\nWeaknesses: the method does not really \"learn\" a rule system, but rather select a subset of rules from existing rules (either batch-given or generated on the fly). It also starts from the premises that a rule system with as few short rules as possible will ensure interpretability, which is something I would disagree on. This may be considered as necessary, but I would not say sufficient.  \n\nQuestions:\n\n* The authors compare their methods to other reduction techniques that start from a large set of rules, however there is a big body of work that concentrates on producing directly compact set of rules. How does the proposed method compare to such approaches? For instance, authors could compare to the work \"A Bayesian Framework for Learning Rule Sets for Interpretable Classification\" that they do cite in the paper. One could also think of older works focusing on rule systems and interpretability, such as fuzzy ones (e.g.,\"Guillaume, Serge. \"Designing fuzzy inference systems from data: An interpretability-oriented review.\" IEEE Transactions on fuzzy systems 9.3 (2001): 426-443.\")\n\n* Author claim that scalability is an essential feature of the considered approach, yet most considered problems count at most around 1000 rules, a scale that can be easily handled by modern MILP and SAT solvers. The question is then to know if in practice, when one starts from existing rules to select, scalability is such an important aspect? \n\n* While conciseness and compactness is certainly desirable for interpretability, and henceforth to explainability, I think interpretability goes beyond that. For instance, majority voting is mentioned by the authors when multiple rules having different conclusions apply to an example. How in practice do we ensure interpretability in those cases where contradictory information is present? Is there a limit to the number of rules that can be activated by an example? \n\n* The parameter $c_i$, which is a scalar, is supposed to be able to include a lot, and a lot of aspects such as rule length, rule complexity, rule accuracy, etc. Could it be explained how, in practice, one could include all these aspects in one number? In the experiment, only rule length is considered, and I am curious about how $c_i$ should be assessed when other aspects should be included in it?\n\n* A recent trend to produce explanations from trees, random forest and other classifiers through the use of logical formulas (e.g., prime implicants), with the idea of producing logically readable explanation as to why an example is classified the way it is. See for example \"Audemard, Gilles, et al. \"Trading Complexity for Sparsity in Random Forest Explanations.\" arXiv preprint arXiv:2108.05276 (2021).\" for a recent paper going along this trend. How is the current method positioned with respect to such works? \n\nOther comments:\n\n* The paper could have benefited from a final read/check. For instance, P5 algorithm 1 does not compile well (probably due to the floating environment). \n\n* The paper is not always fully accurate in its statements. For instance, it is inaccurate to say that a sibling growth the negation of a rule, it only includes the negation of the induced (Boolean) literal. Strictly speaking, one rule is not the negation of the other. Similarly, features are sometimes mentioned as belonging to the real-valued hyper-cube (start of section 2), sometimes to be categorical (start of section 3). ", "summary_of_the_paper": "The paper discusses how, from an existing set of rules or a procedure generating rules \"on the fly\", one can use linear programming to select a subset of rules that would increase \"interpretability\", where an interpretable system of rules is here understood as a system with few, short rules. \n\nThe idea is to ensure a good accuracy level by minimizing a continuous hinge loss (ensuring the linearity of the problem), while penalizing retained rule (rules having a positive weight) through a cost proportional to the complexity of those rules. The experiments show that the paper does, indeed, improve upon the metric retained by the authors (rule length and rule quantity). Whether this produces something that is readable is not checked further on (assuming that this is sufficient for user-readability). ", "summary_of_the_review": "The proposed method does accomplish its intent, which is to reduce a rule system or incrementally integrate rules so that the final system is rather concise and compact. It does not, however, learn the rule system itself, mainly selecting rules that are learned by an external method (in this sense, the title may be misleading). One thing that is not clear is whether the interpretability goal is achieved (but then most papers on interpretability do not go till checking actual interpretability), and how the method would compare to approaches that directly aim at building a compact, \"interpretable\" rule base? \n\nThe paper could also benefit from some small corrections, but is overall quite understandable. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "mCvzMlKdL0s", "reviewer": "Reviewer_fGw9", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "From a conceptual point-of-view, it is unclear what is gained by using linear programming in the proposed manner: runtime is not shown to be improved compared to classic greedy rule learning algorithms and optimality is not preserved in either new algorithm variant because heuristic tree learning algorithms are used to provide the starting point for rule simplification and are also used within the algorithm in the second variant of the proposed approach.\n\nThe empirical results do not show an advantage compared to classic rule learning. The main text of the paper only compares to decision tree learning, which is not the appropriate comparison. There are results for some datasets for other rule learners in an appendix, which are obtained from other publications, but these were almost certainly not obtained using exactly the same experimental methodology. (Notably, assuming the methodology is in fact the same, the proposed algorithm is actually outperformed by the classic rule learning algorithm RIPPER: accuracy of RIPPER is slightly better on average, and the rule sets are generally much smaller; also RIPPER does not require a voting mechanism to obtain classifications, which simplifies the interpretation.)\n\nAlmost all the datasets in the experiments are two-class problems, and the results indicate that the proposed method performs poorly on the five multi-class problems included in the experiments compared to AdaBoost (which is a boosting algorithm not particularly suited to multi-class problems either). The comparison to other rule learners in the appendix is restricted to two-class problems. This means there is little evidence to show that the proposed algorithm performs well on multi-class problems.\n\nThere is a comparison to decision tree learning in Table 3, which the second variant of the proposed approach outperforms, but the decision tree is crippled by setting its maximum depth to three!\n\nSimilarly, the comparison to random forests is problematic because trees of a maximum depth of three are used in them. This is fine in the case of boosting (because boosting works well with weak learners), but it is not appropriate for random forests.\n\nGiven that the paper employs AdaBoost, it should compare to SLIPPER from \"A Simple, Fast, and Effective Rule Learner\", which is based on the confidence-rated version of the boosting algorithm.\n\nAnother rule learner that should be compared against is FURIA, which was shown to perform better than RIPPER:\n\nHühn, J., Hüllermeier, E. FURIA: an algorithm for unordered fuzzy rule induction. Data Min Knowl Disc 19, 293–319 (2009)\n\nThere is no excuse for not running experiments under exactly the same experimental conditions because code is available and experiments can be run quickly. The authors should also consider using repeated 10-fold cross-validation because most of the datasets are quite small. A single 10-fold cross-validation run produces an estimate of high variance for such datasets.\n\nThe case study is based on the very old breast cancer dataset from the UCI repository. Why not use a modern dataset that is of greater interest to people?\n\nOther comments:\n\n* Table 1: \"RUX-RF and RUX-ADA give accuracies on par with RF and ADA\" - no, for many datasets, accuracy is quite noticeably reduced: ionosphere, liver, transfusion, wdbc, musk, oilspill, seeds, wine, glass, sensorless(!).\n\n* Table 2: \"average performance is close to ... ADA\" - no, for many datasets, accuracy is quite noticeably reduced and the average accuracy is substantially lower.\n\n* \"solving LPs can be achieved in polynomial time\" - please state the time complexity of the full rule learning algorithm. How does it compare to that of an algorithm based on classic separate-and-conquer rule learning?\n\n* \"one of the two classes\" - not necessarily\n\n* \"then, majority voting ... is used\" - not necessarily\n\n* \"the training data is required to be fully covered\" - not necessarily, the majority class can be covered by a default rule, for example; or a hybrid nearest-neighbour-based approach can be employed\n\n* \"the best parameter set\" - this is done using the internal 3-fold cross-validation? Please spell this out.", "summary_of_the_paper": "The paper presents an approach to learning ensembles of classification rules using linear programming. Two variants of the algorithm are considered: one uses a collection of rules extracted from ensembles of decision trees as the starting point, and another one that learns rules from scratch by applying decision tree learning within the rule learning algorithm. UCI datasets (mostly two-class problems) are used to compare classifier complexity and accuracy with that of random forests, AdaBoost, and learning a single decision tree.", "summary_of_the_review": "The paper does not show convincingly that the proposed methods improve on existing rule learning algorithms.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "hhC9GLyLO0A", "reviewer": "Reviewer_a6cV", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "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": "\nEven though the idea in the paper is quite interesting and the paper is well-written, I find the experimental section insufficient to show the method's superiority in comparison to related algorithms.\n\n1. RandomForest to obtain good results often require component tress with max_depth higher than 3. Therefore, claims that the method obtains similar results as RF are - for the moment - not fully supported since the hyperparametrizatoin of RF is very much suboptimal.\n2. The proposed method for extracting decision rules from ensembles only selects them and has no mechanism of simplifying them. Despite the fact that the method allows for weighting rules according to their length, in practice, ensembles are often a collection of large decision trees with long decision rules. It can be hard to construct a good classifier with short rules from a large tree without any simplifying mechanism. Currently presented experiments do not tackle this issue.\n3. In the experiments with AdaBoost, it would be interesting to see the method's results without providing the information about rule weight calculated by boosting (through cost coefficient). The proposed method calculates the weights automatically, the weights from boosting are no measure of interpretability - therefore, the proposed method should be able to calculate the correct rule weights on its own.\n4. In my opinion, the differences in Accuracy between AdaBoost and extracted rules are quite considerable. Even though on average it is -2,6%, there is a drop of 25% on SENSORLESS and several drops of 8-5%. What are the possible reasons of poor algorithm performance on some datasets? Moreover, the method for extraction rules is not compared against any other method of this type.\n4. The comparisons in the main paper should include some modern methods for constructing small, interpretable decision rule sets rather than comparisons with standard baselines. Unfortunately, the comparison with other SOTA method in the Appendix does not clearly demonstrate the superiority of the proposed method. For instance, CG on average constructs significantly less complex and slightly more accurate rules. The method's advantage is that it also works on multi-class data; however, the authors should show some comparisons on multi-class data that would prove its usefulness in this setup (besides comparing it to standard, not-interpretable ensembles)\n\nMinor issues:\n- The related works could include Angelino et al. CORELS algorithm that constructs optimal decision rules.\n- The formatting of Algorithm 3 is incorrect (some Latex error, I guess)\n", "summary_of_the_paper": "The paper presents a simple method for constructing decision rules for classification problems through linear programming. In fact, the method rather uses rules generated by the standard DecisionTree algorithm but later selects the most useful rules, weights instances, and poses a new learning problem for the Decision Tree algorithm.\n", "summary_of_the_review": "The idea presented in the paper is simple but quite interesting. Unfortunately, I find the experimental section insufficient to show the method's superiority in comparison to related algorithms. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers are rather critical about the paper and the authors did not take a part in the discussion phase. Let me also add that the paper ignores a vast number of papers dealing with a similar problem. The column generation algorithm is a core of LPBooting also used for rule learning ("Rule Learning with Monotonicity Constraints", "The Linear Programming Set Covering Machine"). There are many other papers also using linear relaxation of integer programming to build rule models. Logical analysis of Data is also a well-known method being close to such approaches. There is also a plenty other rule learning systems that should be compared in the experimental study such as Ripper, Slipper, MLRules, or Ender (to mention only a few of them).
Decision: Reject