Scalable Rule-Based Representation Learning for Interpretable Classification
Year: 2021

Abstract:
Rule-based models, e.g., decision trees, are widely used in scenarios demanding high model interpretability for their transparent inner structures and good model expressivity. However, rule-based models are hard to optimize, especially on large data sets, due to their discrete parameters and structures. Ensemble methods and fuzzy/soft rules are commonly used to improve performance, but they sacrifice the model interpretability. To obtain both good scalability and interpretability, we propose a new classifier, named Rule-based Representation Learner (RRL), that automatically learns interpretable non-fuzzy rules for data representation and classification. To train the non-differentiable RRL effectively, we project it to a continuous space and propose a novel training method, called Gradient Grafting, that can directly optimize the discrete model using gradient descent. An improved design of logical activation functions is also devised to increase the scalability of RRL and enable it to discretize the continuous features end-to-end. Exhaustive experiments on nine small and four large data sets show that RRL outperforms the competitive interpretable approaches and can be easily adjusted to obtain a trade-off between classification accuracy and model complexity for different scenarios. Our code is available at: https://github.com/12wang3/rrl.

heading: 1 Introduction
text: Although Deep Neural Networks (DNNs) have achieved impressive results in various machine learning tasks (Goodfellow et al., 2016), rule-based models, benefiting from their transparent inner structures and good model expressivity, still play an important role in domains demanding high model interpretability, such as medicine, finance, and politics (Doshi-Velez and Kim, 2017). In practice, rule-based models can easily provide explanations for users to earn their trust and help protect their rights (Molnar, 2019; Lipton, 2016). By analyzing the learned rules, practitioners can understand the decision mechanism of models and use their knowledge to improve or debug the models (Chu et al., 2018). Moreover, even if post-hoc methods can provide interpretations for DNNs, the interpretations from rule-based models are more faithful and specific (Murdoch et al., 2019). However, conventional rule-based models are hard to optimize, especially on large data sets, due to their discrete parameters and structures, which limit their application scope. To take advantage of rule-based models in more scenarios, we urgently need to answer such a question: how to improve the scalability of rule-based models while keeping their interpretability?
∗Corresponding authors.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Studies in recent years provide some solutions to improve conventional rule-based models in different aspects. Ensemble methods and soft/fuzzy rules are proposed to improve the performance and scalability of rule-based models but at the cost of model interpretability (Ke et al., 2017; Breiman, 2001; Irsoy et al., 2012). Bayesian frameworks are also leveraged to more reasonably restrict and adjust the structures of rule-based models (Letham et al., 2015; Wang et al., 2017; Yang et al., 2017). However, due to the non-differentiable model structure, they have to use methods like MCMC or Simulated Annealing, which could be time-consuming for large models. Another way to improve rule-based models is to let a high-performance but complex model (e.g., DNN) teach a rule-based model (Frosst and Hinton, 2017; Ribeiro et al., 2016). However, learning from a complex model requires soft rules, or the fidelity of the student model is not guaranteed. The recent study Wang et al. (2020) tries to extract hierarchical rule sets from a tailored neural network. When the network is large, the extracted rules could behave quite differently from the neural network and become useless in most cases. Nevertheless, combined with binarized networks (Courbariaux et al., 2015), it inspires us that we can search for the discrete solutions of interpretable rule-based models in a continuous space leveraging effective optimization methods like gradient descent.
In this paper, we propose a novel rule-based model named Rule-based Representation Learner (RRL) (see Figure 1a). We summarize the key contributions as follows:
• To achieve good model transparency and expressivity, RRL is formulated as a hierarchical model, with layers supporting automatic feature discretization, rule-based representation learning in flexible conjunctive and disjunctive normal forms, and rule importance evaluation. • To facilitate training effectiveness, RRL exploits a novel gradient-based discrete model training method, Gradient Grafting, that directly optimizes the discrete model and uses the gradient information at both continuous and discrete parametric points to accommodate more scenarios. • To ensure data scalability, RRL utilizes improved logical activation functions to handle highdimensional features. By further combining the improved logical activation functions with a tailored feature binarization layer, it realizes the continuous feature discretization end-to-end. • We conduct experiments on nine small data sets and four large data sets to validate the advantages, i.e., good accuracy and interpretability, of our model over other representative classification models. The benefits of the model’s key components are also verified by the experiments.

heading: 2 Related Work
text: Rule-based Models. Decision tree, rule list, and rule set are the widely used structures in rule-based models. For their discrete parameters and non-differentiable structures, we have to train them by employing various heuristic methods (Quinlan, 1993; Breiman, 2017; Cohen, 1995; Wei et al., 2019), which may not find the globally best solution or a solution with close performance. Alternatively, train them with search algorithms (Wang et al., 2017; Angelino et al., 2017; Lin et al., 2020), which could take too much time on large data sets. In recent studies, Bayesian frameworks are leveraged to restrict and adjust model structure more reasonably (Letham et al., 2015; Wang et al., 2017; Yang et al., 2017). Lakkaraju et al. (2016) learns independent if-then rules with smooth local search. However, except for heuristic methods, most existing rule-based models need frequent itemsets mining and/or long-time searching, which limits their applications. Moreover, it is hard for these rule-based models to get comparable performance with complex models like Random Forest.
Ensemble models like Random Forest (Breiman, 2001) and Gradient Boosted Decision Trees (Chen and Guestrin, 2016; Ke et al., 2017) have better performance than the single rule-based model. However, since the decision is made by hundreds of models, ensemble models are commonly not considered as interpretable models (Hara and Hayashi, 2016). Soft or fuzzy rules are also used to improve model performance (Irsoy et al., 2012; Ishibuchi and Yamamoto, 2005), but non-discrete rules are much harder to understand than discrete ones. Deep Neural Decision Tree (Yang et al., 2018) is a tree model realized by neural networks with the help of soft binning function and Kronecker product. However, due to the use of Kronecker product, it is not scalable with respect to the number of features. Other studies try to teach the rule-based model by a complex model, e.g., DNN, or extract rule-based models from complex models (Frosst and Hinton, 2017; Ribeiro et al., 2016; Wang et al., 2020). However, the fidelity of the student model or extracted model is not guaranteed.
Gradient-based Discrete Model Training. The gradient-based discrete model training methods are mainly proposed to train binary or quantized neural networks for network compression and
acceleration. Courbariaux et al. (2015, 2016) propose to use the Straight-Through Estimator (STE) for binary neural network training. However, STE requires gradient information at discrete points, which limits its applications. ProxQuant (Bai et al., 2018) formulates quantized network training as a regularized learning problem and optimizes it via the prox-gradient method. ProxQuant can use gradients at non-discrete points but cannot directly optimize for the discrete model. The RB method (Wang et al., 2020) trains a neural network with random binarization for its weights to ensure the discrete and the continuous model behave similarly. However, when the model is large, the differences between the discrete and the continuous model are inevitable. Gumbel-Softmax estimator (Jang et al., 2016) generates a categorical distribution with a differentiable sample. However, it can hardly deal with a large number of variables, e.g., the weights of binary networks, for it is a biased estimator. Our method, i.e., Gradient Grafting, is different from all the aforementioned works in using gradient information of both discrete and continuous models in each backpropagation.

heading: 3 Rule-based Representation Learner
text: Notation Description. Let D = {(X1, Y1), . . . , (XN , YN )} denote the training data set with N instances, where Xi is the observed feature vector of the i-th instance with the j-th entry as Xi,j , and Yi is the corresponding one-hot class label vector, i ∈ {1, . . . , N}. Each feature value can be either discrete or continuous. All the classes take discrete values, and the number of class labels is denoted by M . We use one-hot encoding to represent all discrete features as binary features. Let Ci ∈ Rm and Bi ∈ {0, 1}b denote the continuous feature vector and the binary feature vector of the i-th instance respectively. Therefore, Xi = Ci ⊕Bi, where ⊕ represents the operator that concatenates two vectors. Throughout this paper, we use 1 (True) and 0 (False) to represent the two states of a Boolean variable. Thus each dimension of a binary feature vector corresponds to a Boolean variable.
Overall Structure. A Rule-based Representation Learner (RRL), denoted by F , is a hierarchical model consisting of three different types of layers. Each layer in RRL not only contains a specific number of nodes but also has trainable edges connected with its previous layer. Let U (l) denote the l-th layer of RRL, u(l)j indicate the j-th node in the layer, and nl represent the corresponding number of nodes, l ∈ {0, . . . , L}. The output of the l-th layer is a vector containing the values of all the nodes in the layer. For ease of expression, we denote this vector by u(l). There are only one binarization layer, i.e., U (0), and one linear layer, i.e., U (L), in RRL, but the number of middle layers, i.e., logical layers, can be flexibly adjusted according to the specific situation. The logical layers mainly aim to learn the non-linear part of the data, while the linear layer aims to learn the linear part. One example of RRL is shown in Figure 1a.
When we input the i-th instance to RRL, the binarization layer will first binarize the continuous feature vector Ci into a new binary vector C̄i. Then, C̄i and Bi are concatenated together as u(0) and inputted to the first logical layer. The logical layers are designed to automatically learn data
representations using logical rules, and the stacked logical layers can learn rules in more complex forms. After going through all the logical layers, the output of the last logical layer can be considered as the new feature vector to represent the instance, wherein each feature corresponds to one rule formulated by the original features. As such, the whole RRL is composed of a feature learner and a linear classifier (linear layer). Moreover, the skip connections in RRL can skip unnecessary logical layers. In what follows, the details of these components will be elaborated.

heading: 3.1 Logical Layer
text: Considering the binarization layer needs the help of its following logical layer to binarize features in an end-to-end way, we introduce logical layers first. As mentioned above, logical layers can learn data representations using logical rules automatically. To achieve this, logical layers are designed to have a discrete version and a continuous version. The discrete version is used for training, testing and interpretation while the continuous version is only used for training. It is worth noting that the discrete RRL indicates the parameter weights of logical layers take discrete values (i.e., 0 or 1) while the parameter weights and biases of the linear layer still take continuous values.
Discrete Version. One logical layer consists of one conjunction layer and one disjunction layer. In discrete version, let R(l) and S(l) denote the conjunction and disjunction layer of U (l) (l ∈ {1, 2, . . . , L − 1}) respectively. We denote the i-th node in R(l) by r(l)i , and the i-th node in S(l) by s(l)i . Specifically speaking, node r (l) i corresponds to the conjunction of nodes in the previous layer connected with r(l)i , while node s (l) i corresponds to the disjunction of nodes in previous layer connected with s(l)i . Formally, the two types of nodes are defined as follows:
r (l) i = ∧ W
(l,0) i,j =1
u (l−1) j , s (l) i = ∨ W
(l,1) i,j =1
u (l−1) j , (1)
where W (l,0) denote the adjacency matrix of the conjunction layerR(l) and the previous layer U (l−1), and W (l,0)i,j ∈ {0, 1}. W (l,0) i,j = 1 indicates there exists an edge connecting r (l) i to u (l−1) j , otherwise W (l,0) i,j = 0. Similarly, W
(l,1) is the adjacency matrix of the disjunction layer S(l) and U (l−1). Similar to neural networks, we regard these adjacency matrices as the weight matrices of logical layers. u(l) = r(l) ⊕ s(l), where r(l) and s(l) are the outputs ofR(l) and S(l) respectively. The function of the logical layer is similar to the notion “level” in Wang et al. (2020). However, one level in that work, which actually consists of two layers, can only represent rules in Disjunctive Normal Form (DNF), while two logical layers in RRL can represent rules in DNF and Conjunctive Normal Form (CNF) at the same time. Connecting nodes inR(l) with nodes in S(l−1), we get rules in CNF, while connecting nodes in S(l) with nodes inR(l−1), we get rules in DNF. The flexibility of logical layer is quite important. For instance, the length of CNF rule (a1 ∨a2)∧ · · · ∧ (a2n−1 ∨a2n) is 2n, but the length of its corresponding DNF rule (a1 ∧a3 · · · ∧a2n−1)∨ · · · ∨ (a2 ∧a4 · · · ∧a2n) is n · 2n, which means layers that only represent DNF can hardly learn this CNF rule. Continuous Version. Although the discrete logical layers have good interpretability, they are hard to train for their discrete parameters and non-differentiable structures. Inspired by the training process of binary neural networks that searches the discrete solution in a continuous space, we extend the discrete logical layer to a continuous version. The continuous version is differentiable, and when we discretize the parameters of a continuous logical layer, we can obtain its corresponding discrete logical layer. Therefore, the continuous logical layer and its corresponding discrete logical layer can also be considered as sharing the same parameters, but the discrete logical layer needs to discretize the parameters first.
Let Û (l) denote the continuous logical layer, and R̂(l) and Ŝ(l) denote the continuous conjunction and disjunction layer respectively, l ∈ {1, 2, . . . , L− 1}. Let Ŵ (l,0) and Ŵ (l,1) denote the weight matrices of R̂(l) and Ŝ(l) respectively. Ŵ (l,0)i,j , Ŵ (l,1) i,j ∈ [0, 1]. To make the whole Equation 1 differentiable, we leverage the logical activation functions proposed by Payani and Fekri (2019):
Conj(h,Wi) = n∏
j=1
Fc(hj ,Wi,j), Disj(h,Wi) = 1− n∏
j=1
(1− Fd(hj ,Wi,j)), (2)
where Fc(h,w) = 1− w(1− h) and Fd(h,w) = h · w. In Equation 2, if h and Wi are both binary vectors, then Conj(h,Wi) = ∧ Wi,j=1 hj and Disj(h,Wi) = ∨ Wi,j=1 hj . Fc(h,w) and Fd(h,w) decide how much hj would affect the operation according to Wi,j . If Wi,j = 0, hj would have no effect on the operation. Equation 2 can be considered as extensions to t-norm fuzzy logic (Hájek, 2013). After using continuous weights and logical activation functions, the nodes in R̂(l) and Ŝ(l) are defined as follows:
r̂ (l) i = Conj(û (l−1), Ŵ (l,0)i ), ŝ (l) i = Disj(û (l−1), Ŵ (l,1)i ) (3) Now the whole logical layer is differentiable and can be trained by gradient descent. However, the above logical activation functions suffer from the serious vanishing gradient problem. The main reason can be found by analyzing the partial derivative of each node w.r.t. its directly connected weights and w.r.t. its directly connected nodes as follows:
∂r̂ (l) i
∂Ŵ (l,0) i,j
= (û (l−1) j −1)· ∏ k 6=j Fc(û (l−1) k , Ŵ (l,0) i,k ),
∂r̂ (l) i
∂û (l−1) j
= Ŵ (l,0) i,j · ∏ k 6=j Fc(û (l−1) k , Ŵ (l,0) i,k ) (4)
Since û(l−1)k and Ŵ (l,0) i,k are in the range [0, 1], the values of Fc(·) in Equation 4 are in the range [0, 1] as well. If nl−1 is large and most of the values of Fc(·) are not 1, then the derivative is close to 0 due to the multiplications (See Appendix D for the analysis of ŝ(l)i ). Wang et al. (2020) tries to use weight initialization to make Fc(·) close to 1 at the beginning. However, when dealing with hundreds of features, the vanishing gradient problem is still inevitable.
Improved Logical Activation Functions. We found that using the multiplications to simulate the logical operations in Equation 2 is the main reason for vanishing gradients and propose an improved design of logical activation functions. One straightforward idea is to convert multiplications into additions using logarithm, e.g., log( ∏n j=1 Fc(hj ,Wi,j)) = ∑n j=1 log(Fc(hj ,Wi,j)). However, after taking the logarithm, the logical activation functions in Equation 2 cannot keep the characteristics of logical operations any more, and the ranges of Conj(·) and Disj(·) are not [0, 1]. To deal with this problem, we need a projection function to fix it. Apparently, the inverse function of log(x), i.e., ex, is not suitable.
For the projection function g, three conditions must be satisfied: (i) g(0) = e0. (ii) limx→−∞ g(x) = limx→−∞ ex = 0. (iii) limx→−∞ e x
g(x) = 0. Condition (i) and (ii) aim to keep the range and tendency of logical activation functions. Condition (iii) aims to lower the speed of approaching zero when x→ −∞. In this work, we choose g(x) = −1−1+x as the projection function, and the improvement of logical activation functions can be summarized as the function P(v) = −1−1+log(v) . The improved conjunction function Conj+ and disjunction function Disj+ are given by:
Conj+(h,Wi) = P( n∏
j=1
(Fc(hj ,Wi,j)+ )), Disj+(h,Wi) = 1−P( n∏
j=1
(1−Fd(hj ,Wi,j)+ )) (5)
where is a small constant, e.g., 10−10. The improved logical activation functions can avoid the vanishing gradient problem in most scenarios and are much more scalable than the originals. Moreover, considering that dP(v)dv = P2(v) v , when n in Equation 5 is extremely large, dP(v) dv may be very close to 0 due to P2(v). One trick to deal with it is replacing P 2(v) v with P(P2(v)) v for P can lower the speed of approaching 0 while keeping the value range and tendency.

heading: 3.2 Binarization Layer
text: The binarization layer is mainly used to divide the continuous feature values into several bins. By combining one binarization layer and one logical layer, we can automatically choose the appropriate bins for feature discretization (binarization), i.e., binarizing features in an end-to-end way.
For the j-th continuous feature to be binarized, there are k lower bounds (Tj,1, . . . , Tj,k) and k upper bounds (Hj,1, . . . ,Hj,k). All these bounds are randomly selected (e.g., from uniform distribution) in the value range of the j-th continuous feature, and these bounds are not trainable. When inputting one continuous feature vector c, the binarization layer will check if cj satisfies the bounds and get the following binary vector:
Qj = [q(cj − Tj,1), . . . , q(cj − Tj,k), q(Hj,1 − cj), . . . , q(Hj,k − cj)], (6)
where q(x) = 1x>0. If we input the i-th instance, i.e., c = Ci, then C̄i = Q1 ⊕ Q2 · · · ⊕ Qm and u(0) = C̄i ⊕ Bi. After inputting u(0) to the logical layer U (1), the edge connections between U (1) and U (0) indicate the choice of bounds (bins). For example, if r(1)i is connected to the nodes corresponding to q(cj −Tj,1) and q(Hj,2−cj), then r(1)i contains the bin (Tj,1 < cj)∧ (cj < Hj,2). If we replace r(1)i with s (1) i in the example, we can get (Tj,1 < cj)∨ (cj < Hj,2). It should be noted that, in practice, if Tj,1 ≥ Hj,2, then r(1)i = 0, and if Tj,1 < Hj,2, then s (1) i = 1. When using the continuous version, the weights of logical layers are trainable, which means we can choose bounds in an end-to-end way. For the number of bounds is 2k times of features, which could be large, only logical layers with improved logical activation functions are capable of choosing the bounds.

heading: 3.3 Gradient Grafting
text: Although RRL can be differentiable with the continuous logical layers, it is challenging to search for a discrete solution in a continuous space (Qin et al., 2020). One commonly used method to tackle this problem is the Straight-Through Estimator (STE) (Courbariaux et al., 2016). The STE method needs gradients at discrete points to update the parameters. However, the gradients of RRL at discrete points have no useful information in most cases (See Appendix E). Therefore STE is not suitable for RRL. Other methods like ProxQuant (Bai et al., 2018) and Random Binarization (Wang et al., 2020) cannot directly optimize for the discrete model and be scalable at the same time.
Inspired by plant grafting, we propose a new training method, called Gradient Grafting, that can effectively train RRL. In stem grafting, one plant is selected for its roots, i.e., rootstock, and the other plant is selected for its stems, i.e., scion. By grafting, we obtain a new plant with the advantages of both two plants. In Gradient Grafting, the gradient of the loss function w.r.t. the output of discrete model is the scion, and the gradient of the output of continuous model w.r.t. the parameters of continuous model is the rootstock. Specifically, let θ denote the parameter vector and θt denote the parameter vector at step t. q(x) = 1x>0.5 is the binarization function that binarizes each dimension of x with 0.5 as the threshold. Let Ŷ and Ȳ denote the output of the continuous model F̂ and discrete model F respectively, then Ŷ = F̂(θt, X), Ȳ = F(q(θt), X). The parameters update with Gradient Grafting is formulated by:
θt+1 = θt − η ∂L(Ȳ ) ∂Ȳ · ∂Ŷ ∂θt , (7)
where η is the learning rate and L(·) is the loss function. One simplified computation graph of Gradient Grafting is shown in Figure 1b for intuitive understanding.
Gradient Grafting can directly optimize the loss of discrete models and use the gradient information at both continuous and discrete points, which overcomes the problems occurring in RRL training when using other gradient-based discrete model training methods. The convergence of Gradient Grafting is verified in the experiments (See Figure 3).

heading: 3.4 Model Interpretation
text: After training with Gradient Grafting, the discrete RRL can be used for testing and interpretation. RRL is easy to interpret, for we can simply consider it as a feature learner and a linear classifier. The binarization layer and logical layers are the feature learner, and they use logical rules to build and describe the new features. The linear classifier, i.e., the linear layer, makes decisions based on the new features. We can first find the important new features by the weights of the linear layer, then understand each new feature by analyzing its corresponding rule. One advantage of RRL is that it can be easily adjusted by the practitioners to obtain a trade-off between the classification accuracy and model complexity. Therefore, RRL can satisfy the requirements from different tasks and scenarios. There are several ways to limit the model complexity of RRL. First, we can reduce the number of logical layers in RRL, i.e., the depth of RRL, and the number of nodes in each logical layer, i.e., the width of RRL. Second, the L1/L2 regularization can be used during training to search for an RRL with shorter rules. The coefficient of the regularization term in the loss function can be considered as a hyperparameter to restrict the model complexity. After training, the dead nodes detection and redundant rules elimination proposed by Wang et al. (2020) can also be used for better interpretability.

heading: 4 Experiments
text: In this section, we conduct experiments to evaluate the proposed model and answer the following questions: (i) How is the classification performance of RRL? (ii) How is the model complexity of RRL? (iii) How is the convergence of Gradient Grafting compared to other gradient-based discrete model training methods? (iv) How is the scalability of the improved logical activation functions?

heading: 4.1 Dataset Description and Experimental Settings
text: Dataset Description. We took nine small and four large public datasets to conduct our experiments, all of which are often used to test classification performance and model interpretability (Dua and Graff, 2017; Xiao et al., 2017; Anguita et al., 2013; Rozemberczki et al., 2019). Appendix B summarizes the statistics of these 13 datasets. Together they show the data diversity, ranging from 178 to 102944 instances, from 2 to 26 classes, and from 4 to 4714 original features. See Appendix A for licenses.
Performance Measurement. We adopt the F1 score (Macro) as the classification performance metric since some of the data sets are imbalanced, i.e., the numbers of different classes are quite different. We adopt 5-fold cross-validation to evaluate the classification performance more fairly. The average rank of each model is also adopted for comparisons of classification performance over all the data sets (Demšar, 2006). Considering that reused structures exist in rule-based models, e.g., one branch in Decision Tree can correspond to several rules, we use the total number of edges instead of the total length of all rules as the metric of model complexity for rule-based models. See Appendix C for details about the experiment environment and parameter settings of all models.

heading: 4.2 Classification Performance
text: We compare the classification F1 score (Macro) of RRL with six interpretable models and five complex models. C4.5 (Quinlan, 1993), CART (Breiman, 2017), Scalable Bayesian Rule Lists (SBRL) (Yang et al., 2017), Certifiably Optimal Rule Lists (CORELS) (Angelino et al., 2017), and Concept Rule Sets (CRS) (Wang et al., 2020) are rule-based models. Logistic Regression (LR) (Kleinbaum et al., 2002) is a linear model. These six models are considered interpretable models. Piecewise Linear Neural Network (PLNN) (Chu et al., 2018), Support Vector Machines (SVM) (Scholkopf and Smola, 2001), Random Forest (Breiman, 2001), LightGBM (Ke et al., 2017), and XGBoost (Chen and Guestrin, 2016) are considered complex models. PLNN is a Multilayer Perceptron (MLP) that adopts piecewise linear activation functions, e.g., ReLU (Nair and Hinton, 2010). RF, LightGBM, and XGBoost are ensemble models. See Appendix C for the parameters tuning.
The results are shown in Table 1, and the first nine data sets are small data sets while the last four are large data sets. We can observe that RRL performs well on almost all the data sets and gets the best results on 6 data sets. The two-tailed Student’s t-test (p<0.01) is used for significance testing, and we can observe that RRL significantly outperforms all the compared interpretable models on 8 out of 13 data sets. The average rank of RRL is also the top three among all the models. Only two complex models that use hundreds of estimators, i.e., XGBoost and LightGBM, have comparable results with
RRL. For Table 1, the Friedman statistic is 73.84, corresponding to a p-value of 2.26× 10−11. Hence the null hypothesis of no significant differences is rejected. We then calculate pairwise comparisons using Conover post-hoc test, and RRL significantly outperforms all the compared interpretable models with p<0.01. Comparing RRL with LR and other rule-based models, we can see RRL can fit both linear and non-linear data well. CRS performs well on small data sets but fails on large datasets due to the limitation of its logical activation functions and training method. Good results on both small and large data sets verify RRL has good scalability. Moreover, SBRL and CRS do not perform well on continuous feature data sets like letRecog and magic04 for they need preprocessing to discretize continuous features, which may bring bias to the data sets. On the contrary, RRL overcomes this problem by discretizing features end-to-end.

heading: 4.3 Model Complexity
text: Interpretable models seek to keep low model complexity while ensuring high accuracy. To show the relationships between accuracy and model complexity of RRL and baselines, we draw scatter plots of F1 score against log(#edges) for rule-based models in Figure 2 (see Appendix K for other data sets). The baselines are typical models in different categories of methods with good trade-offs between accuracy and model complexity. For RRL, the legend markers and error bars indicate means and standard deviations, respectively, of F1 score and log(#edges) across cross-validation folds. For baseline models, each point represents an evaluation of one model, on one fold, with one parameter setting. Therefore, in Figure 2, the closer its corresponding points are to the upper left corner, the better one model is. To obtain RRL with different model complexities, we tune the depth and width of RRL and the coefficient of L2 regularization term. The value in CART(·), e.g., CART(0.03), denotes the complexity parameter used for Minimal Cost-Complexity Pruning (Breiman, 2017), and a higher value corresponds to a simpler tree. We also show results of XGBoost with 10 and 100 estimators.
In Figure 2, on both small and large data sets, we can observe that if we connect the results of RRL, it will become a boundary that separating the upper left corner from other models. In other words, if RRL has a close model complexity with one baseline, then the F1 score of RRL will be higher. If the F1 score of RRL is close to one baseline, then the model complexity of RRL will be lower. It indicates that RRL can make better use of rules than rule-based models using heuristic and ensemble methods in most cases. The results in Figure 2 also verify that we can adjust the model complexity of RRL by setting the model structure and the coefficient of L2 regularization term. In this way, the practitioners are able to select an RRL with suitable classification performance and model complexity for different scenarios, which is crucial for practical applications of interpretable models.

heading: 4.4 Ablation Study
text: Training Method for Discrete Model. To show the effectiveness of Gradient Grafting for training RRL, we compare it with other representative gradient-based discrete model training methods, i.e., STE (Courbariaux et al., 2015, 2016), ProxQuant (Bai et al., 2018) and RB (Wang et al., 2020), by training RRL with the same structure. Hyperparameters are set to be the same for each method except exclusive hyperparameters, e.g., random binarization rate for RB, are fine-tuned. The training loss of the compared discrete model training methods and Gradient Grafting are shown in Figure 3, and we can see that the convergence of Gradient Grafting is faster and stabler than other methods on all data sets. As we mentioned in Section 3.3, RRL has little useful gradient information at discrete points,
thus RRL trained by STE cannot converge. Due to the difference between discrete and continuous RRL, RRL trained by ProxQuant and RB cannot converge well as well.
Improved Logical Activation Functions. We also compare RRL trained by Gradient Grafting with or without improved logical activation functions. The results are also shown in Figure 3, and GradGrafting(NI) represents RRL using original logical activation functions instead of improved logical activation functions. We can observe that the original activation functions work well on small data sets but fail on the large data set activity while the improved activation functions work well on all data sets, which means the improved logical activation functions make RRL more scalable. It should be noted that GradGrafting(NI) works well on the large data set facebook. The reason is facebook is a very sparse data set, and the number of 1 in each binary feature vector is less than 30 (See Appendix D for detailed analyses).

heading: 4.5 Case Study
text: We show how the learned RRL looks like by case studies. Take the bank-marketing data set as an example. We first show the distribution of weights in the linear layer of the trained RRLs in Figure 4a. Each weight in the linear layer corresponds to one rule. For a better viewing experience, we show the normalized absolute values of weights. The model structures of these RRLs are the same, but different coefficients of the L2 regularization term, denoted by λ, lead to different model complexities. We can observe that, when λ is small, which means the RRL is more complex, there are many rules with small weights. These small weight rules are mainly used to slightly adjust the outputs. Hence, they make the RRL more accurate but less interpretable. However, in practice, we can ignore these small weight rules and only focus on rules with large weights first. After analyzing rules with large weights and having a better understanding of the learned RRL and the data set, we can then understand those less important rules gradually. When λ is large, the number of rules is small, and we can directly understand the whole RRL rather than understanding RRL step by step.
In Figure 4b, we show the learned rules, with high weights, of one RRL trained on the bank-marketing data set (see Appendix J for the fashion data set). These rules are used to predict if the client will subscribe a term deposit by telesales. Different types of features are marked in different colors, e.g., purple for previous behaviours of the bank. We can clearly see that middle-aged married persons with low balance are more likely to subscribe a deposit, and the previous behaviour of the bank would also affect the client. Then the bank can change its strategies according to these rules.

heading: 5 Conclusion and Future Work
text: We propose a new scalable classifier, named Rule-based Representation Learner (RRL), that can automatically learn interpretable rules for data representation and classification. For the particularity of RRL, we propose a new gradient-based discrete model training method, i.e., Gradient Grafting, that directly optimizes the discrete model. We also propose an improved design of logical activation functions to increase the scalability of RRL and make RRL capable of discretizing the continuous features end-to-end. Our experimental results show that RRL enjoys both high classification performance and low model complexity on data sets with different scales. For the current design of RRL is limited to structured data, when dealing with unstructured data using RRL, we need to convert them into structured data first. For example, RRL needs to convert a 2D image into a 1D vector, which could lose spatial information. We will extend RRL to suit more unstructured data as future work.

heading: 6 Acknowledgments
text: This work was supported in part by National Key Research and Development Program of China under Grant No. 2020YFA0804503, National Natural Science Foundation of China under Grant No. 61521002 and 62072182, and Beijing Academy of Artificial Intelligence (BAAI).

Review summaries:
This paper presents a new scalable classifier, named Rule-based Representation Learner (RRL), that can automatically learn interpretable rules for data representation and classification.  A new gradient-based discrete model training method, i.e., Gradient Grafting, is proposed as well that directly optimizes the discrete model. RRL's performance on structured data seems promising wrt experiments performed.   

The authors propose a new classifier - called Rule-based Representation Learner - that learns interpretable non-fuzzy rules. The model consists of 3 main modules:  - the binarization layer - the logical layer(s) - the linear layer.  Further, the authors propose a new training algorithm called Gradient Grafting. The model was tested tested on 13 datasets and compared with six interpretable models and five complex models.

This submission proposes a new rule-based learner for classification. The learner uses discrete logical learners to obtain the rules. In order to obtain differentiability, the authors also propose a continuous approximation to the discrete layers. After a discussion about avoiding vanishing gradients problem, the authors conduct numerical experiments on a set of datasets.