Year: 2021

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.

heading: 1 INTRODUCTION
text: 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 importance. 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 a set of classification rules that balances the trade-off between accuracy and interpretability. Our main tools in this effort are linear programming and column generation.
A rule is an independent if-then statement, which contains one or more conditions that assign a class to a set of samples. For example in binary classification, “if (Clump Thickness is greater than six) and (Single Epithelial Cell Size is less than four) then the tumor is malignant” is such a rule that can be used for breast cancer diagnosis. When a sample satisfies this rule, then it receives a 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 to rule-based learning. A Decision Tree (DT) naturally results with a 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. Fürnkranz (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 a binary tree when a splitting is performed at a node, the left child grows a rule, while its right sibling grows its negation. As a result, every sample obeys to exactly one rule and it is classified according to the corresponding leaf. Thus, inaccurate rules, which are negations of their siblings after splitting, can be created. This
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 (Fürnkranz et al., 2012). To minimize the number of uncovered samples during testing, the training data is required to be fully covered. Separate-andconquer algorithm by Fürnkranz (1999) achieves this heuristically by fitting rules on uncovered training samples, and new rules are generated until each training sample is 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 mathematical programming. We give a 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) to solve the LP model.
Rule extraction methods attempt to select a set of rules from accurate complex or black-box 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 et al., 2020). Most of these studies use heuristic approaches to select the desired set of rules. Birbil et al. (2020) suggest a set covering formulation to extract intrepretable rules from RFs. Other applications 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 interpretability approaches in the literature such as SHAP (Lundberg & Lee, 2017) 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 programming for rule learning. Malioutov & Varshney (2013) propose a rule-based binary classifier solving a binary program that minimizes the number of rules for a boolean compressed sensing problem. Wang & Rudin (2015) 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 DTs 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 et al. (2020) offer a 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. Wei et al. (2019) propose generalized linear rule models using a similar CG framework of the work by Dash et al. (2020). Malioutov & Meel (2018) solve a Max-Sat formulation by constraint programming to construct interpretable classification rules. Ghosh & Meel (2019) also propose a 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-based approaches are for binary classification. To that end, the objective function in our LP formulation minimizes classification error using a loss function instead of explicitly 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 algorithms 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-
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 our column generation approach is the use of a 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 as boosting methods also rely on 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.

heading: 2 RULE EXTRACTION
text: We consider a classification problem with K classes and denote the set of class labels by K. The training dataset consists of samples with features xi ∈ Rp for i ∈ I and labels yi for i ∈ I. To work with multiple classes, we define a vector-valued mapping y(xi) ∈ K ⊂ RK as in Zhu et al. (2009). That is, if yi = k, then
y(xi) = (− 1K−1 ,− 1 K−1 , . . . , 1, . . . ,− 1 K−1 ) ᵀ, (1)
where the value one appears only at the kth component of the vector.
Suppose that we have a collection of rules indexed by J . A rule j ∈ J assigns the vectorRj(xi) ∈ K to input xi, only if rule j covers sample i. This vector is also formed in the same manner as in equation 1. To predict the class of a given sample xi with this collection of rules, we use a set of nonnegative weights wj , j ∈ J associated with the rules and evaluate
ŷ(xi) = ∑ j∈J aijRj(xi)wj , (2)
where aij ∈ {0, 1} indicates whether rule j covers sample i or not. Then, the index of the largest component of the resulting vector ŷ(xi) is assigned as the predicted label ŷi of sample i ∈ 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 ∑
i∈I max
{ 1− ∑ j∈J âijwj , 0 } ,
where âij = κaijRj(xi)ᵀy(xi) with κ = (K−1)/K. This loss function allows us to write a linear programming model, where the objective is to find the set of rules that minimizes the total loss. To this end, we introduce the auxiliary variables vi, i ∈ I standing for vi ≥ max { 1− ∑ j∈J âijwj , 0 }
, and obtain our master problem
minimize ∑ i∈I vi + ∑ j∈J cjwj
subject to ∑
j∈J âijwj + vi ≥ 1, i ∈ I;∑ j∈J aijwj ≥ ε, i ∈ I;
vi ≥ 0, i ∈ I; wj ≥ 0, j ∈ J ,
(3)
where cj ≥ 0, j ∈ 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 involving many rules with nonzero weights are avoided. The less the number of rules in the resulting set, the easier it is to interpret a solution. In other words, we prefer sparse solutions and cj 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 is of concern, one could try to obtain rules with few features because shorter rules are considered to be easier to interpret (Lakkaraju et al., 2016). In this case, the number of conditions in 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 a rule cost in the proposed model. We should point out that there
exists a 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 ∈ J . The master problem equation 3 also involves a set of covering constraints with the fixed right-handside, ε > 0. These constraints make sure that each sample is covered by at least one rule. The need for these covering constraints is exemplified as follows:
Consider a binary classification problem, where we select three samples {xi,xk,xl} along with their labels yi = 1, yk = −1 and yl = −1. 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: Rj(xi) = Rj(xk) = Rj(xl) = −1 and Rj′(xk) = Rj′(xl) = −1. The first set of constraints in equation 3 then becomes
−aijwj +vi ≥ 1, akjwj +akj′wj′ +vk ≥ 1, aljwj +alj′wj′ +vl ≥ 1.
For simplicity, if we also assume that cj = cj′ , then the optimal solution becomes wj = vk = vl = 0 and wj′ = vi = 1. With this solution, sample xi is not covered.
We remark that covering each sample in a dataset is crucial from the perspective of giving a literal interpretation with the obtained rules. This is particularly important when the resulting set of rules is used to interpret the classification of individual samples in the dataset. Clearly, varying ε 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 sufficient1.
Up until this point, we 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 a rule-based 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 3 with such a 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 a 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 DTs from the AdaBoost model. Using these trained models to construct our master problem leads to our first algorithm RUX, which is based on tree ensembles. We show in Section 4 that RUX can indeed extract only a 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.

heading: 3 RULE GENERATION
text: Suppose now that we do not have the entire set of rules J 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 in an iterative fashion. Since equation 3 is a linear programming problem
1In case one insists on treating ε 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 a computationally efficient manner.
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, a 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 a subset of rules Jt ⊂ J at iteration t and form the restricted master problem by replacing J with Jt in equation 3. Let us denote the dual variables associated with the first set of constraints by βi, i ∈ I. Likewise, let γi, i ∈ I be the dual variables corresponding to the coverage constraints. In vector notation, we simply use β and γ. Then, the dual restricted master problem at iteration t becomes
maximize ∑
i∈I (βi + εγi) subject to ∑
i∈I (âijβi + aijγi) ≤ cj , j ∈ Jt; 0 ≤ βi ≤ 1, i ∈ I; γi ≥ 0, i ∈ I.
(4)
If we denote the optimal dual solution at iteration t by β(t) and γ(t), then improving the objective function value of problem equation 4 requires finding at least one rule j′ ∈ J /Jt such that
c̄j′ = cj′ − ∑ i∈I ( âij′β (t) i + aij′γ (t) i ) < 0, (5)
where c̄j′ is the reduced cost of column j′. In fact, this condition simply checks whether j′ ∈ J /Jt violates the dual feasibility. To find those rules with negative reduced costs, we formulate the pricing pricing subproblem as
max j∈J /Jt {∑ i∈I âijβ (t) i + aijγ (t) i } . (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 3 with the current set of rules, Jt. Otherwise, we have at least one rule with a negative reduced cost. After adding one or more rules with negative reduced costs to Jt, we proceed with Jt+1 and solve the restricted master problem or, equivalently, its dual equation 4. Algorithm 3 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− ⊆ J /Jt. [!h] Exact Rule Generation Input: training data, (xi, yi)i∈I t = 0 Construct initial rule pool, J0 True (β(t),γ(t)) ← Solve equation 4 J− ← Solve pricing subproblem, equation 6 J− = ∅ return Jt t← t+ 1 Jt = Jt−1 ∪ J− We have overlooked two important steps in Algorithm 3. The first one is the construction of the initial rule pool J0 (line three). One possible solution for this step is to train a 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 6 is associated with finding a rule with the highest accuracy when the samples have weights β(t)i , i ∈ I. As constructing an optimal binary decision tree is known to be NP-complete (Laurent & Rivest, 1976), solving problem equation 6 is rather difficult even when γ(t) = 0. This leads us to the proxy pricing subproblem of column generation as shown in Figure 1. Here, treating γi = 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 a DT as a heuristic pricing approach, where the sample weights correspond to dual variables β(t)i , i ∈ 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 a negative reduced cost column (rule) with γi = 0 would also have a negative reduced cost when the pricing subproblem is solved exactly.
Figure 1 shows the proposed heuristic approach for rule generation. The procedure DecisionTree takes a vector of sample weights as an input and returns a set of rules J̄ (leaves of the decision tree). The vector e is the vector of ones. The subset J̄− ⊆ J̄ 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 in this manner boils down to solving a proxy pricing subproblem. Indeed, our rule generation algorithm RUG does not guarantee to solve the overall problem equation 3 to optimality. Fortunately, this may be to our advantage since a suboptimal 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-based approaches to learning (Günlük et al., 2018; Verwer & Zhang, 2019). Avid readers of optimization-based learning would also notice that there are some connections between RUG and the boosting methods. We elaborate on this point in Section A.3 of the supplementary document.
We remark once again that growing decision trees with sample weights is a standard tool in every library on machine learning. Likewise, there are various options to solve linear programs. Both growing DTs and solving LPs can be achieved in polynomial-time. Therefore, the proposed algorithm in Figure 3 is extremely easy to implement with the existing packages of popular programming languages.

heading: 4 COMPUTATIONAL STUDY
text: We have evaluated the performances of the proposed algorithms on a collection of frequently used datasets. The details of these datasets are given in Section A.1 of the supplementary document. Both the rule extraction (RUX) and the rule generation (RUG) algorithms are implemented in Python 2. Since our computation times do not exceed one minute even on a standard laptop computer, we do not report them here. We have used stratified 10 × 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 ε = 0.01 .

heading: 4.1 NUMERICAL EXPERIMENTS
text: First, we apply our RUX algorithm to trained random forest (RF) and AdaBoost (ADA) models. For both RF and ADA, we have selected the maximum-depth parameter from the set {1, 2, 3} and the number-of-estimators 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-RF, we have used the rule-length as the cost coefficients cj , j ∈ J in equation 3. For RUX-ADA, the 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.
2Our implementation is available in the supplementary file.
Table 1 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 are 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 RUXADA 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.
We report our results with the proposed RUG algorithm in Table 2. In addition to RF and ADA, we have also added a DT algorithm for comparison. The same set of values {1, 2, 3} is used for tuning the maximum-depth parameter both in DT and RUG (for constructing the initial column pool and the proxy pricing subproblem; see Figure 1). 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, we also report the rule numbers as well as the rule lengths for 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 their recent work, Dash et al. (2020) propose a rule learning approach based on column generation. They also give a comparison against other studies and present that their algorithm shows one of the best performances. We compare their results against a 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 a 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. It is important to note that both RUX 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.
When it comes to the scalability of our algorithms, our preliminary results on large instances are very promising and in 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 A.6 of the supplementary document.
Even though RUX variants and RUG obtain few number of rules with short lengths for many datasets, there are also several datasets where the resulting sets of rules are still challenging to interpret. However, note that the results that we present in Table 1 and Table 2 are given for all rules with nonzero optimal weights. Using a threshold weight for a rule and monitoring the accuracy,
one can end up with a set of rules that is easier to interpret. We elaborate on this point in the next subsection with a case study.

heading: 4.2 CASE STUDY
text: 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 diagnosis classes (benign or malignant). RUG reaches the accuracy level of 0.96 and generates 18 rules that we denote as R1 to R18. Figure 2 shows that RUG can also attain accuracy level of 0.95 using only the first 12 rules. The plot given in Figure 2 be 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 are normalized by dividing the weights with the largest among them. On the right side, we 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 a 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.

heading: 5 CONCLUSION
text: We have proposed a linear programming (LP) approach to discover a set of critical rules in multiclass 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 easy-to-implement. The numerical experiments have shown that the proposed algorithms may be used for hitting the right balance between accuracy and interpretability.
The first algorithm works with a predefined set of rules. To demonstrate our algorithm, we 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 Forest, we have used the rule lengths as cost coefficients in our algorithm to obtain shorter rules for interpretation. As AdaBoost returns also a set of estimator weights, we have used these weights as cost coefficients to mimic the performance of the trained AdaBoost model. Our numerical results 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 a large collection of rules. Testing our algorithm further with those rule ensembles is an interesting future research direction.
Instead of a given collection of rules, our second algorithm uses a rule generation mechanism that iteratively solves LPs and builds up a set of rules. This algorithm has a solid mathematical basis as its core idea comes from the well-known column generation approach in large-scale linear programming. A significant advantage of this algorithm is having more control on the generation of the rules. However, there is a challenge that lies within the difficult exact pricing subproblem. As a remedy, we have proposed to solve a proxy subproblem by training decision trees with sample weights. These sample weights are obtained from the dual of the LPs at that iteration. Decision trees can be easily trained with the existing software packages, and hence, this proxy pricing problem 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.
This study is 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 a specially tailored DT that use all the dual values. These are other lines of research that we plan to pursue in the future.

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

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.