Learning Accurate and Interpretable Decision Rule Sets from Neural Networks

Common tabular datasets generally comprise binary, categorical and numerical features. While our method is based on binary encoded input vectors, we employ the following pre-processing procedures, which are well established and studied in the machine learning literature, to binarize the input features. In particular, the values of binary features are left as what they are, whereas we apply standard one-hot encoding to transform categorical attributes to vectors of binary values. As for numerical features, we adopt quantile discretization to get a set of thresholds for each feature, where the original numerical value is one-hot-encoded into a binary vector by comparing with the thresholds (e.g., age $\leq$ 25, age $\leq$ 50, age $\leq$ 75) and encoded as $1$ if less than the threshold or $0$ otherwise. For example, considering a dataset that consists of the categorical feature “color” chosen from {red, green, blue} and a numerical feature “age” with thresholds {25, 50, 75}, our pre-processing approach will encode an instance [color: red, age: 30] as [red, green, blue, age $\leq$ 25, age $\leq$ 50, age $\leq$ 75] $=$ [1, 0, 0, 0, 1, 1]. Most other rule-learning methods (Wang et al. 2017; Dash, Günlük, and Wei 2018) require to convert binary, categorical and numerical features into both positive conditions, e.g., (color = blue) and (age $\leq$ 50), and negative conditions, e.g., (color $\neq$ blue) and (age $>$ 50), of the binary vectors in their pre-processing procedures. On the other hand, our encoding approach only involves those positive conditions without separately having their negations included. Further explanations will be discussed in the next section.

The essence of a fully-connected layer is the dot-product operation shifted by a bias term. In this context, we notice that with binarized input features, a neuron can be constructed such that it effectively performs a logical AND operation by dynamically adjusting the bias based on the weight values and applying a binary step activation function afterwards. Then, by interpreting the full precision weights in a certain way, each neuron is effectively a conjunction of input features and thus the whole layer can be mapped to a set of clauses that can be later combined with disjunction to form a DNF rule set.

Mathematically, given the input to the Rules Layer as $\mathbf{x}\in\{0,1\}^{D}$ and the output as $y$, a neuron in the Rules Layer performs its operation as follows:

In Equation 1, the dot product of the weights and inputs is added with a dynamic bias, which depends on the weights of the neuron. With the dynamic bias and binarized inputs, the range of the outputs of the neurons in the Rules Layer is within $(-\infty,1]$. Note that the output $y=1$ can only be achieved when all inputs match the sign of the corresponding weights: all positive weights should have the inputs of $1$ and all negative weights should have the inputs of $0$. Just like the behavior of weights in regular neurons, the zero weights in the Rules Layer mean that the corresponding inputs will not have any effect on the output.

In order for the neuron in the Rules Layer to function as a proper logical AND operation, we need to apply a binary step activation function to its output:

When applied at the Rules Layer, the binary step function defined in Equation 2 simply maps the range $(-\infty,1)$ to 0, which ensures that the neuron is turned on only when Equation 1 evaluates to 1. With the dynamic bias and binary step function, each neuron in the Rules Layer encodes a rule that has $k$ predicates, where $k$ is the number of non-zero weights of that neuron. As discussed earlier, in effect neuron in the Rules Layer maps to a logical IF-THEN rule after training, where a positive input weight corresponds to a positive association of the input feature, a negative input weight corresponds to a negative association of the input feature, and a zero weight corresponds to an exclusion of the input feature.

However, as can be observed, the activations of the first layer are discretized into binary integers that are not naturally differentiable and the classic gradient computation approach doesn’t apply here. Therefore, we utilize the straight-through estimator discussed in (Bengio, Léonard, and Courville 2013) with the gradient clipping technique. Denoted by $\hat{y}_{i}$ the binarized activation based on $y_{i}$, we compute the gradient as follows:

where $g_{\hat{y}_{i}}$ and $g_{y_{i}}$ are the gradients of classification loss w.r.t. $\hat{y}_{i}$ and $y_{i}$, respectively. The condition $y_{i}<0$ simulates the backward computation of the ReLU function, which introduces non-linearity into the training process and empirically improves the performance; whereas our motivation of the second condition is to address the saturation effect: we suppress the update of the full-precision activations that are greater than $1$ and are still driven by the gradient to increase, since further raising activations does not produce any difference after binarization.

As discussed in above, the addition of the negative conditions in the input space is critical to the selection-based methods (Wang et al. 2017; Dash, Günlük, and Wei 2018) since they only consider the presence and absence of features and cannot deduce negative correlations unless they are explicitly provided in the input space. On the other hand, besides the presence of a positive association or an exclusion, our Rules Layer also learns the negation of an input feature by assigning a negative weight to it, and hence, DR-Net can directly derive negative conditions from the corresponding input features. Therefore, appending negative conditions in the input binary vector is redundant in DR-Net, and the input space of our DR-Net is reduced by half comparing with those selection-based method.

To produce the disjunction of the logical rules learned in the Rules Layer, the OR Layer contains only one output neuron, where the weights are binarized as follows:

The output neuron performs a dot product with a negative bias $-\epsilon$ as follows:

where $0<\epsilon<1$ is a small value such that $y$ is positive when at least one input is activated. With a sigmoid activation function and a binary cross-entropy loss, this particular neuron behaves as an OR gate: the output is by default turned off because of the negative bias, while it produces a positive value if at least one rule is activated with a corresponding $\hat{w_{i}}=1$, which exactly mimics the behavior of the logical OR function. The binarized weights $\hat{w_{i}}$ act as rule selectors that filter out rules that do not contribute to the model’s predictive performance. An example of our complete network structure is shown in Figure 1. We practically use $\epsilon=0.5$ in our implementations.

The neural network structure proposed above outlines a way to derive a set of decision rules using stochastic gradient descent. As discussed above, a zero weight for a Rules Layer neuron corresponds to the exclusion of the corresponding input feature. Similarly, a zero weight for the OR Layer output neuron corresponds to the exclusion of the corresponding rule from the rule set. Thus, it should be clear that maximizing the sparsity of the Rules Layer neurons corresponds to simplifying the corresponding rules, and maximizing the sparsity of the OR Layer neuron corresponds to minimizing the number of rules.

However, to eliminate an input feature from a logical rule or a logical rule from the complete rule set, the corresponding weight has to be exactly zero, which is difficult to achieve in the typical network training process. To achieve a high degree of sparsity with exact zero weights, we explicitly incorporate a sparsity-based regularization mechanism into the training process using an approach akin to $L_{0}$ regularization by explicitly training mask variables.

As discussed in (Louizos, Welling, and Kingma 2017) as a way to achieve network sparsity through $L_{0}$ regularization, a binary random variable $z_{i}\in\{0,1\}$ is attached to each weight of the model to indicate whether the corresponding weight is kept or removed. With this, we can reparameterize each weight $w_{i}$ as the product of a weight $\tilde{w_{i}}$ and the corresponding binary random variable $z_{i}$:

Assuming each $z_{i}$ is subject to a Bernoulli distribution with parameter $\pi_{i}$, i.e. $q(z_{i}|\pi_{i})=\textrm{Bern}(\pi_{i})$, the probability that $z_{i}$ is 1 is just $\pi_{i}$. In (Louizos, Welling, and Kingma 2017), $L_{0}$ regularization is implemented by summing all $\pi_{i}$ parameters as the penalty term in the loss function¹¹1As explained below, we do not use $L_{0}$ normalization as the regularization term. Instead, we explicitly capture the model complexity with Equation 7 as the regularization term.. In order to train the binary random variables with stochastic gradient descent, two different gradient estimators have been proposed in (Louizos, Welling, and Kingma 2017) and (Li and Ji 2019), respectively, to approximate the Bernoulli distribution.

Applying the above regularization method to the Rules Layer is straightforward: all weight parameters are replaced by their product with the corresponding mask variables. For the OR Layer, since the weights will ultimately be binarized, we can just directly substitute the mask variables for the weights to simplify the process. That is, we can simply treat $w_{i}=z_{i}$, with no need for a separate $\tilde{w_{i}}$ variable²²2Since $w_{i}=z_{i}$ is already binarized, there is no need to further binarize $w_{i}$ to derive $\hat{w_{i}}$ with Equation 4. i.e., we can just use $\hat{w_{i}}=w_{i}=z_{i}$..

We then incorporate a sparsity-based regularization term in the loss function to model the complexity of the rule set represented by the neural network. We denote by $\pi_{1,i,j}$ and $\pi_{2,j}$ the penalty of the non-zero mask variables of the Rules Layer and the OR Layer, respectively, where $i=1,2,\dots,D$ is the feature index, and $j=1,2,\dots,m$ is the index to the $j$-th neuron (rule). Then the regularization loss is defined as follows:

which explicitly captures the model complexity, as similarly defined in (Dash, Günlük, and Wei 2018). In particular, the model complexity of a rule set is defined as the sum of the number of rules and the total number of predicates in all rules. Following this definition, the first and the second terms of Equation 7 quantify the losses for the number of rules and the total number of predicates, respectively. Note that, according to the second term in Equation 7, the loss for the number of predicates in the $j$-th rule will be effectively removed if $\pi_{2,j}$ is at or near zero: i.e., the $j$-th neuron in the Rules Layer is disconnected from the OR Layer.

With the above sparsity-based regularization applied to DR-Net, the overall loss function we optimize for can be expressed as follows:

where $\mathcal{L}_{\mathrm{BCE}}$ is the binary cross-entropy loss, $\mathcal{L}_{R}$ is the regularization penalty that is specified by Equation 7, and $\lambda$ is the regularization coefficient that balances the classification accuracy and rule set complexity.

As previously discussed, each neuron in the first layer (the Rules Layer) of our proposed network architecture encodes an interpretable decision rule, whereas the output neuron in the second layer (the OR Layer) chooses some of the rules to be included in the set of decision rules. Empirically, we noticed that it is more effective to train our DR-Net with gradient-based optimizers (e.g., SGD) in an alternating manner, potentially due to the reduced search space and simpler optimization goals. In particular, our “alternating training strategy” consists of two training phases. We first freeze the OR Layer and only update the parameters in the Rules Layer to learn plausible rules. In the second phase, the Rules Layer is then fixed and we optimize the OR Layer such that redundant rules are eliminated while necessary inactive rules can also be re-enabled. The whole network is trained by alternating between the two training phases until convergence.

In addition, since the sparsity of the Rules Layer is directly related to the simplicity of rules, whereas the second layer is more focused on the selection of these derived rules, we further allow the flexible weighting of the sparsity-based regularization loss of the two layers. Specifically, as illustrated in Equation 8, the balance between classification loss and regularization loss is implemented via the regularization coefficient $\lambda$, where we can practically use different values for the two phases. In other words, the Rules Layer and the OR Layer are optimized over $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$, respectively, where $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ are defined as follows:

In this way, the trade-off between model simplicity and accuracy in our experiments can be modulated by the adjustments of $\lambda_{1}$ and $\lambda_{2}$.

We evaluated the predictive performance of DR-Net by comparing both test accuracy and complexity with other state-of-the-art machine learning models. 5-fold nested cross validation was employed to select the parameters for all rule learners that explicitly trade-off between accuracy and interpretability to maximize the training set accuracies. To ensure that the final rule learner models are interpretable, we constrained the possible parameters for nested cross validation to a range that results in a low model complexity. For DR-Net, We fixed the $\lambda_{2}$ to be $10^{-5}$ in Equation 9 and only $\lambda_{1}$ was varied in the experiment. Although there are many parameters in BRS to control the rule complexity, we followed the procedure used in (Dash, Günlük, and Wei 2018) and only varied the multiplier $\kappa$ in prior hyper-parameter to save running time. For RIPPER, we varied the maximum number of conditions and the maximum number of rules as hyper-parameters of the implementation, which are directly related to the complexity of the model. The CG implementation in (Arya et al. 2019) doesn’t have the complexity bound parameter $C$ as specified in (Dash, Günlük, and Wei 2018) but instead provides two hyper-parameters to specify the costs of each clause and of each condition, which were used in our experiment to control the rule set complexity. We left all other parameters for these three algorithms (CG, BRS, RIPPER) as default. For CART and RF, we constrained the maximum depth of trees to be 100 for all datasets to achieve better generalization. For DNN, we used the same training parameters (number of epochs, batch size, learning rate, etc.) with a weight decay of $10^{-2}$. The test accuracy results of all models on all datasets are shown in Table 1 and the corresponding complexities are shown in Table 2. We omitted the results of the complexities of CART, RF and DNN because they have a different notion of model complexity and rule complexity.

It can be seen in Table 1 that our method outperforms other interpretable models on all datasets. For these better accuracy results, our method does not establish a similar superiority in the complexity comparison (Table 2). However, as shown Figure 2 and further discussed in the next section, our DR-Net approach can often achieve higher accuracy at comparable complexities. It is interesting to see that DR-Net maintains a relatively good model complexity compared with the corresponding rule complexity, which is exactly because our regularization loss function is designed specifically to minimize the model complexity instead of the rule complexity. Compared with RIPPER, which greedily mines good rules in each iteration to maximize the training accuracy, DR-Net is very competitive in the sense that it has similar or better test performance while consistently maintaining a lower model complexity. One advantage of the BRS algorithm over other models is that it consistently generates sparse models across all datasets, but at the expense of significantly inferior accuracies. The CART decision tree algorithm turned out to be the worst performing model in our experiments, which might result from overfitting. The results in Table 1 and Table 2 suggest that our DR-Net approach is very competitive as a machine learning model for interpretable classification. Finally, our DR-Net approach is able to achieve accuracies within only 3% of the uninterpretable models (RF and DNN) on the datasets evaluated.

In this experiment, we compared the accuracy-complexity trade-off of our DR-Net with other rule learning algorithms: CG, BRS and RIPPER. The parameters that were selected to be varied in this experiment are the same as ones in the first experiment. Instead of using nested cross validation to select best parameters on the validation set, we manually picked a set of values for each selected parameters for each algorithm to generate different sets of accuracy-complexity pairs. We ran the experiments on all datasets and the results with the average of the 5-fold cross validation are shown in Figure 2. Apart from model complexity and rule complexity, we included a third metric to show the average number of rules in each generated rule set versus the test accuracy. For each method compared, the dots connected by the line segments shown correspond to Pareto efficient models where all other points below the Pareto frontier have either lower accuracies or higher complexities.

The characteristic of being able to attain a high test accuracy with an acceptable model complexity for DR-Net in Table 1 and Table 2 is carried over to Figure 2. For the magic, adult and house datasets, DR-Net outperforms all other rule learners in terms of the accuracy by a substantial margin when the model complexity, the rule complexity or the number of rules exceeds a certain threshold. Although DR-Net does not dominate RIPPER on the heloc dataset, their accuracy comparison is very close if enough model complexity or number of rules is given. The only thing that DR-Net falls behind a little bit is in the rule complexity vs. accuracy comparison on the heloc dataset. In theory, DR-Net can achieve relatively low rule complexity with a different regularization loss function that can quantify the average number of conditions in the rule set, which we leave as future work. It is also interesting to note that the number of rules from DR-Net varies in a relatively narrower range compared with other approaches as shown in the third column of Figure 2, which is directly resulted by fixing $\lambda_{2}$ in Equation 9. BRS does not demonstrate a clear accuracy-complexity trade-off as its results all group in a very narrow range, which is also noted and explained in (Dash, Günlük, and Wei 2018). This experiment shows that DR-Net can be preferred over other rule learners because of its potential for achieving a much higher test accuracy with a relatively moderate complexity sacrifice.