An Optimization Approach to Learning Falling Rule Lists

INTRODUCTION

In many real-life scenarios, we want to learn a predictive model that allows us to easily identify the most significant conditions that are predictive of a certain outcome. For example, in health care, doctors often want to know the conditions that signify a high risk of stroke, so that patients with such conditions can be prioritized in receiving treatment. A falling rule list, whose form was first proposed by Wang and Rudin (2015), is a type of model that serves this purpose.

Table 1 shows a falling rule list we learned from the bank-full dataset, which was used by Moro et al. (2011) in their study of applying data mining techniques to direct marketing. As we can see, a falling rule list is a probabilistic decision list for binary classification, consisting of a series of if-then rules with antecedents in the if clauses and probabilities of the desired outcome (“1”) in the then clauses, where the probabilities of the desired outcome (“1”) are monotonically decreasing down the list (hence the name “falling” rule list). The falling rule list in Table 1 has identified clients for whom the previous marketing campaign was successful (“poutcome=success”), and who have no credit in default (“default=no”), as individuals who are most likely to subscribe to a term deposit in the current marketing campaign. Their probability of subscribing is $0.65$. Of the remaining clients, those who are next most likely to sign up for a term deposit are older people (aged between 60 and 100) with no credit in default. Their probability of subscribing is $0.28$. The two rightmost columns in Table 1, labeled $+$ and $-$, show the number of positive training examples (i.e. clients who subscribe to a term deposit in the current campaign) and of negative training examples, respectively, that satisfy the antecedent in each rule of the falling rule list.

Falling rule lists can provide valuable insight into data – if we know how to construct them well. In this paper, we propose an optimization approach to learning falling rule lists and “softly” falling rule lists, along with Monte-Carlo search algorithms that use bounds on the optimal solution to prune the search space. The falling rule list shown in Table 1 was produced using Algorithm FRL, which we shall introduce later.

Our work lives within several well-established fields, but is the first work we know of to use an optimization approach to handling monotonicity constraints in rule-based models. It relates closely to associative classification (e.g. the RIPPER$k$ algorithm (Cohen,, 1995) and the CBA algorithm (Liu et al.,, 1998); see Thabtah, (2007) for a comprehensive review) and inductive logic programming (Muggleton and De Raedt,, 1994). The proposed algorithms are competitors for decision tree methods like CART (Breiman et al.,, 1984), ID3 (Quinlan,, 1986), C4.5 (Quinlan,, 1993), and C5.0 (Quinlan,, 2004), and decision list learning (Rivest,, 1987). Almost all methods from this class build decision trees from the top down using greedy splitting criteria. Greedy splitting criteria do not lend naturally to constrained models like falling rule lists. There are some works on decision trees with monotonicity constraints (e.g. Altendorf et al.,, 2005; Ben-David,, 1995; Feelders and Pardoel,, 2003), but they focus mostly on enforcing the monotonic relationship between certain attributes and ordinal class labels. In addition, our work also relates to those that underline the importance of the interpretability of models (Freitas,, 2014; Huysmans et al.,, 2011; Kodratoff,, 1994; Martens and Baesens,, 2010).

Wang and Rudin (2015) proposed the form of a falling rule list, and a Bayesian approach to learning falling rule lists (extending the ideas of Letham et al., (2015) and Yang et al., (2017)). The Bayesian approach offers some advantages: e.g. a full posterior over rule lists allows model averaging. However, the optimization perspective has an important computational advantage: the search space is made substantially smaller by the tight bounds presented here. The concept of softly falling rule lists is novel to this paper and has not been done in the Bayesian setting.

PROBLEM FORMULATION

We first formalize the notion of an antecedent, of a rule list, of a falling rule list, and of a prefix.

An antecedent $a$ on an input domain $\mathcal{X}$ is a Boolean function that outputs true or false. Given an input $\mathbf{x}\in\mathcal{X}$, we say that $\mathbf{x}$ satisfies the antecedent $a$ if $a(\mathbf{x})$ evaluates to true. For example, (poutcome=success AND default=no) in Table 1 is an antecedent.

A rule list $d:\mathcal{X}\rightarrow$ on an input domain $\mathcal{X}$ is a probabilistic decision list of the following form: “if $\mathbf{x}$ satisfies $a_{0}^{(d)}$, then $\text{Pr}(y=1|\mathbf{x})=\hat{\alpha}_{0}^{(d)}$; else if $\mathbf{x}$ satisfies $a_{1}^{(d)}$, then $\text{Pr}(y=1|\mathbf{x})=\hat{\alpha}_{1}^{(d)}$; $...$; else if $\mathbf{x}$ satisfies $a_{|d|-1}^{(d)}$, then $\text{Pr}(y=1|\mathbf{x})=\hat{\alpha}_{|d|-1}^{(d)}$; else $\text{Pr}(y=1|\mathbf{x})=\hat{\alpha}_{|d|}^{(d)}$” where $a_{j}^{(d)}$ is the $j$-th antecedent in $d$, $j\in\{0,1,...,|d|-1\}$, and $|d|$ denotes the size of the rule list, which is defined as the number of rules, excluding the final else clause, in the rule list. We can denote the rule list $d$ as follows:

The rule list $d$ of Equation (1) is a falling rule list if the following inequalities hold:

For convenience, we sometimes refer to the final else clause in $d$ as the $|d|$-th antecedent $a_{|d|}^{(d)}$ in $d$, which is satisfied by all $\mathbf{x}\in\mathcal{X}$. We denote the space of all possible rule lists on $\mathcal{X}$ by $\mathcal{D}(\mathcal{X})$.

A prefix $e$ on an input domain $\mathcal{X}$ is a rule list without the final else clause. We can denote the prefix $e$ as follows:

where $a_{j}^{(e)}$ is the $j$-th antecedent in $e$, $j\in\{0,1,...,|e|-1\}$, and $|e|$ denotes the size of the prefix, which is defined as the number of rules in the prefix.

Given the rule list $d$ of Equation (1) (or the prefix $e$ of Equation (3)), we say that an input $\mathbf{x}\in\mathcal{X}$ is captured by the $j$-th antecedent in $d$ (or $e$) if $\mathbf{x}$ satisfies $a_{j}^{(d)}$ (or $a_{j}^{(e)}$, respectively), and for all $k\in\{0,1,...,|d|\}$ (or $k\in\{0,1,...,|e|-1\}$, respectively) such that $\mathbf{x}$ satisfies $a_{k}^{(d)}$ (or $a_{k}^{(e)}$, respectively), $j\leq k$ holds – in other words, $a_{j}^{(d)}$ (or $a_{j}^{(e)}$, respectively) is the first antecedent that $\mathbf{x}$ satisfies. We define the function capt by $\text{capt}(\mathbf{x},d)=j$ (or $\text{capt}(\mathbf{x},e)=j$) if $\mathbf{x}$ is captured by the $j$-th antecedent in $d$ (or $e$). Moreover, given the prefix $e$ of Equation (3), we say that an input $\mathbf{x}\in\mathcal{X}$ is captured by the prefix $e$ if $\mathbf{x}$ is captured by some antecedent in $e$, and we define $\text{capt}(\mathbf{x},e)=|e|$ if $\mathbf{x}$ is not captured by the prefix $e$.

Let $D=\{(\mathbf{x}_{i},y_{i})\}_{i=1}^{n}$ be the training data, with $\mathbf{x}_{i}\in\mathcal{X}$ and $y_{i}\in\{1,-1\}$ for each $i\in\{1,2,...,n\}$. We now define the empirical positive proportion of an antecedent, and introduce the notion of a rule list (or a prefix) that is compatible with $D$.

Given the training data $D$ and the rule list $d$ of Equation (1) (or the prefix $e$ of Equation (3)), we denote by $n^{+}_{j,d,D}$, $n^{-}_{j,d,D}$, $n_{j,d,D}$ (or $n^{+}_{j,e,D}$, $n^{-}_{j,e,D}$, $n_{j,e,D}$), the number of positive, negative, and all training inputs captured by the $j$-th antecedent in $d$ (or $e$), respectively, and define the empirical positive proportion of the $j$-th antecedent in $d$ (or $e$), denoted by $\alpha_{j}^{(d,D)}$ (or $\alpha_{j}^{(e,D)}$), as:

Given the training data $D$ and the rule list $d$ of Equation (1) (or the prefix $e$ of Equation (3)), we say that the rule list $d$ (or the prefix $e$) is compatible with $D$ if for all $j\in\{0,1,...,|d|\}$ (or $j\in\{0,1,...,|e|-1\}$, respectively), the equation $\hat{\alpha}_{j}^{(d)}=\alpha_{j}^{(d,D)}$ ($\hat{\alpha}_{j}^{(e)}=\alpha_{j}^{(e,D)}$, respectively) holds. We denote the space of all possible rule lists on $\mathcal{X}$ that are compatible with the training data $D$ by $\mathcal{D}(\mathcal{X},D)$.

Given the training data $D$, the rule list $d$ of Equation (1), a threshold $\tau$, and the weight $w$ for the positive class, the empirical risk of misclassification by the rule list $d$ on the training data $D$ with threshold $\tau$ and with weight $w$ for the positive class, denoted by $R(d,D,\tau,w)$, is:

If $d$ is compatible with $D$, we can replace $\hat{\alpha}_{\text{capt}(\mathbf{x}_{i},d)}^{(d)}$ in Equation (4) with $\alpha_{\text{capt}(\mathbf{x}_{i},d)}^{(d,D)}$. We define the empirical risk of misclassification by the prefix $e$ on the training data $D$ with threshold $\tau$ and with weight $w$ for the positive class, denoted by $R(e,D,\tau,w)$, analogously:

If $e$ is compatible with $D$, we can replace $\hat{\alpha}_{\text{capt}(\mathbf{x}_{i},e)}^{(e)}$ in Equation (5) with $\alpha_{\text{capt}(\mathbf{x}_{i},e)}^{(e,D)}$. Note that for any rule list $d$ that begins with a given prefix $e$, $R(e,D,\tau,w)$ is the contribution by the prefix $e$ to $R(d,D,\tau,w)$.

We can formulate the problem of learning falling rule lists as a minimization program of the empirical risk of misclassification, given by Equation (4), with a regularization term $C|d|$ that penalizes each rule in $d$ with a cost of $C$ to limit the number of rules, subject to the monotonicity constraint (2). For now, we focus on the problem of learning falling rule lists that are compatible with the training data $D$.

Let $L(d,D,\tau,w,C)=R(d,D,\tau,w)+C|d|$ and $L(e,D,\tau,w,C)=R(e,D,\tau,w)+C|e|$ be the regularized empirical risk of misclassification by the rule list $d$ and by the prefix $e$, respectively, on the training data $D$. The former defines the objective of the minimization program, and the latter gives the contribution by the prefix $e$ to $L(d,D,\tau,w,C)$ for any rule list $d$ that begins with $e$. The following theorem provides a motivation for setting the threshold $\tau$ to $1/(1+w)$ in the minimization program – the empirical risk of misclassification by a given rule list $d$ is minimized when $\tau$ is set in this way.

Given the training data $D$, a rule list $d$ that is compatible with $D$, and the weight $w$ for the positive class, we have $R(d,D,1/(1+w),w)\leq R(d,D,\tau,w)$ for all $\tau\geq 0$.

For reasons of computational tractability and model interpretability, we further restrict our attention to learning compatible falling rule lists whose antecedents must come from a pre-determined set of antecedents $A=\{A_{l}\}_{l=1}^{m}$. We now present the optimization program for learning falling rule lists, which forms the basis of the rest of this paper.

The constraint (6) is exactly the monotonicity constraint (2) for the falling rule lists that are compatible with $D$. The constraint (7) limits the choice of antecedents. An instance of Program 2.9 is defined by the tuple $(D,A,w,C)$.

ALGORITHM

In this section, we outline a Monte-Carlo search algorithm, Algorithm FRL, based on Program 2.9, for learning compatible falling rule lists from data. Given an instance $(D,A,w,C)$ of Program 2.9, the algorithm constructs a compatible falling rule list $d$ in each iteration, while keeping track of the falling rule list $d^{*}$ that has the smallest objective value $L_{\text{best}}=L(d^{*},D,\tau,w,C)$ among all the falling rule lists that the algorithm has constructed so far. At the end of $T$ iterations, the algorithm outputs the falling rule list that has the smallest objective value out of the $T$ lists it has constructed.

In the process of constructing a falling rule list $d$, the algorithm chooses the antecedents successively, and uses various properties of Program 2.9, presented in Section 4, to prune the search space. In particular, when the algorithm is choosing the $p$-th antecedent in $d$, it considers only those antecedents $A_{l}\in A$ satisfying the following conditions: (1) the inclusion of $A_{l}$ as the $p$-th antecedent in $d$ gives rise to a rule $(a_{p}^{(d)},\alpha_{p}^{(d,D)})$ that respects the monotonicity constraint $\alpha_{p}^{(d,D)}\leq\alpha_{p-1}^{(d,D)}$ and the necessary condition for optimality $\alpha_{p}^{(d,D)}>1/(1+w)$ (Corollary 4.5), and (2) the inclusion of $A_{l}$ as the $p$-th antecedent in $d$ gives rise to a prefix $e^{\prime}$ such that $e^{\prime}$ is feasible for Program 2.9 under the training data $D$ (Proposition 4.2), and the best possible objective value $L^{*}(e^{\prime},D,w,C)$ achievable by any falling rule list that begins with $e^{\prime}$ and is compatible with $D$ (Theorem 4.6) is less than the current best objective value $L_{\text{best}}$. The algorithm terminates the construction of $d$ if Inequality (9) in Theorem 4.6 holds. The details of the algorithm can be found in the supplementary material.

PREFIX BOUND

The goal of this section is to find a lower bound on the objective value of any compatible falling rule list that begins with a given compatible prefix, which we call a prefix bound, and to prove the various results used in the algorithm. To derive this prefix bound, we first introduce the concept of a feasible prefix, with which it is possible to construct a compatible falling rule list from data.

Given the training data $D$ and the set of antecedents $A$, a prefix $e$ is feasible for Program 2.9 under the training data $D$ and the set of antecedents $A$ if $e$ is compatible with $D$, and there exists a falling rule list $d$ such that $d$ is compatible with $D$, the antecedents of $d$ come from $A$, and $d$ begins with $e$.

The following proposition gives necessary and sufficient conditions for a prefix $e$ to be feasible.

We now introduce the concept of a hypothetical rule list, whose antecedents do not need to come from the pre-determined set of antecedents $A$.

Given a pre-determined set of antecedents $A$, a hypothetical rule list with respect to $A$ is a rule list that contains an antecedent that is not in $A$.

We need the following lemma to prove the necessary condition for optimality (Corollary 4.5), and to derive a prefix bound (Theorem 4.6).

Suppose that we are given an instance $(D,A,w,C)$ of Program 2.9, a prefix $e$ that is feasible for Program 2.9 under $D$ and $A$, and a (possibly hypothetical) falling rule list $d$ that begins with $e$ and is compatible with $D$. Then there exists a falling rule list $d^{\prime}$, possibly hypothetical with respect to $A$, such that $d^{\prime}$ begins with $e$, has at most one more rule (excluding the final else clause) following $e$, is compatible with $D$, and satisfies

A consequence of the above lemma is that an optimal solution for a given instance $(D,A,w,C)$ of Program 2.9 should not have any antecedent whose empirical positive proportion falls below $1/(1+w)$.

If $d^{*}$ is an optimal solution for a given instance $(D,A,w,C)$ of Program 2.9, then we must have $\alpha_{j}^{(d^{*},D)}>1/(1+w)$ for all $j\in\{0,1,...,|d^{*}|-1\}$.

Another implication of Lemma 4.4 is that the objective value of any compatible falling rule list that begins with a given prefix $e$ cannot be less than a lower bound on the objective value of any compatible falling rule list that begins with the same prefix $e$, and has at most one more rule (excluding the final else clause) following $e$. This leads to the following theorem.

Suppose that we are given an instance $(D,A,w,C)$ of Program 2.9 and a prefix $e$ that is feasible for Program 2.9 under $D$ and $A$. Then any falling rule list $d$ that begins with $e$ and is compatible with $D$ satisfies

is a lower bound on the objective value of any compatible falling rule list that begins with $e$, under the instance $(D,A,w,C)$ of Program 2.9. We call $L^{*}(e,D,w,C)$ the prefix bound for $e$. Further, if

The results presented in this section are used in Algorithm FRL to prune the search space. The proofs can be found in the supplementary material.

SOFTLY FALLING RULE LISTS

An instance of Program 5.1 is defined by the tuple $(D,A,w,C,C_{1})$. Similarly, we have a Monte-Carlo search algorithm, Algorithm softFRL, based on Program 5.1, for learning softly falling rule lists from data. Given an instance $(D,A,w,C,C_{1})$ of Program 5.1, this algorithm searches through the space of rule lists that are compatible with $D$ and finds a compatible rule list whose antecedents come from $A$, and whose objective value is the smallest among all the rule lists that the algorithm explores. It then turns this compatible rule list into a softly falling rule list. In the search phase, the algorithm uses the following prefix bound (Theorem 5.2) to prune the search space of compatible rule lists. The details of Algorithm softFRL and the proof of Theorem 5.2 can be found in the supplementary material.

Suppose that we are given an instance $(D,A,w,C,C_{1})$ of Program 5.1 and a prefix $e$ that is compatible with $D$. Then any rule list $d$ that begins with $e$ and is compatible with $D$ satisfies

is a lower bound on the objective value of any compatible rule list that begins with $e$, under the instance $(D,A,w,C,C_{1})$ of Program 5.1. In Equation (10), $\alpha_{\min}^{(e,D)}$, $\zeta$, and $g$ are defined by

EXPERIMENTS

In this section, we demonstrate our algorithms for learning falling rule lists using a real-world application – learning the conditions that are predictive of the success of a bank marketing effort, from previous bank marketing campaign data. We used the public bank-full dataset (Moro et al.,, 2011), which contains $45211$ observations, with $12$ predictor variables that were discretized. We used the frequent pattern growth (FP-growth) algorithm (Han and Pei,, 2000) to generate the set of antecedents $A$ from the dataset. For reasons of model interpretability and generalizability, we included in $A$ the antecedents that have at most $2$ predicates, and have at least $10\%$ support within the data that are labeled positive or within the data that are labeled negative. Besides the FP-growth algorithm, there is a vast literature on rule mining algorithms (e.g. Agrawal and Srikant,, 1994; Han et al.,, 2000; Landwehr et al.,, 2005), and any of these can be used to produce antecedents for our algorithms.

The bank-full dataset is imbalanced – there are only $5289$ positive instances out of $45211$ observations. A trivial model that always predicts the negative outcome for a bank marketing campaign will achieve close to $90\%$ accuracy on this dataset, but it will not be useful for the bank to understand what makes a marketing campaign successful. Moreover, when predicting if a future campaign will be successful in finding a client, the bank cares more about “getting the positive right” than about “getting the negative right” – a false negative means a substantial loss in revenue, while a false positive incurs little more than some phone calls.

We also plotted the number of antecedents considered by Algorithm FRL and Algorithm softFRL in the process of constructing a rule list at each iteration (Figures 1(b) and 1(c)), when we applied the two algorithms to the entire dataset. Each curve in either plot corresponds to a rule list constructed in an iteration of the appropriate algorithm. The intensity of the curve is inversely proportional to the iteration number – the larger the iteration number, the lighter the curve is. The number of antecedents considered by Algorithm FRL stays below $60$ in all but a few early iterations (despite a choice of $276$ antecedents available), and the number considered by either algorithm generally decreases drastically in each iteration after three or four antecedents have been chosen. The curves generally become lighter as we move vertically down the plots, indicating that as we find better rule lists, there are less antecedents to consider at each level. Algorithm softFRL needs to consider more antecedents in general since the search space is less constrained. All of these demonstrate that the prefix bounds we have derived for our algorithms are effective in excluding a large portion of the search space of rule lists. The supplementary material contains more rule lists created using our algorithms with different parameter values.

Since this paper was directly inspired by Wang and Rudin (2015), who proposed a Bayesian approach to learning falling rule lists, we conducted a set of experiments comparing their work to ours. We trained falling rule lists on the entire bank-full dataset using both the Bayesian approach and our optimization approach, and plotted the weighted training loss over real runtime for each positive class weight $w\in\{1,3,5,7\}$ with the threshold set to $1/(1+w)$ (By Theorem 2.8, this is the threshold with the least weighted training loss for any given rule list). Since we want to focus our experiments on the efficiency of searching the model space, the runtimes recorded do not include the time for mining the antecedents. Note that the Bayesian approach is not cost-sensitive, and does not optimize the weighted training loss directly. However, in many real-life applications such as predicting the success of a future marketing campaign, it is desirable to minimize the expected weighted loss. Therefore, it is reasonable to compare the two approaches using the weighted training loss to demonstrate the advantages of our optimization approach. We compared the Bayesian approach only with Algorithm FRL, because both methods strictly enforce the monotonicity constraint on the positive proportions of the training data that are classified into each rule. Softly falling rule lists do not strictly enforce the monotonicity constraint, and are therefore not used for comparison. Figure 2 shows the plots of the weighted training loss over real runtime. Due to the random nature of both approaches, the experiments were repeated several times – more plots of the weighted training loss over real runtime for different trials of the same experiment, along with falling rule lists created using both approaches, can be found in the supplementary material. As shown in Figure 2, our optimization approach tends to find a falling rule list with a smaller weighted training loss faster than the Bayesian approach. This is not too surprising because in our approach, the search space is made substantially smaller by the tight bounds presented here, whereas in the original Bayesian approach, there are no tight bounds on optimal solutions to restrict the search space – even if we constructed bounds for the original Bayesian approach, they would involve loose approximations to gamma functions.

CONCLUSION

We have proposed an optimization approach to learning falling rule lists and softly falling rule lists, along with Monte-Carlo search algorithms that use bounds on the optimal solution to prune the search space. A recent work by Angelino et al., (2017) on (non-falling) rule lists showed that it is possible to exhaustively optimize an objective over rule lists, indicating that the space of lists is not as large as one might think. Our search space is a dramatically constrained version of their search space, allowing us to reasonably believe that it can be searched exhaustively. Unfortunately, almost none of the logic of Angelino et al., (2017) can be used here. Indeed, introducing the falling constraint or the monotonicity penalty changes the nature of the problem, and the bounds in our work are entirely different. The algorithm of Angelino et al., (2017) is not cost-sensitive, which led in this work to another level of complexity for the bounds.

Falling rule lists are optimized for ease-of-use – users only need to check a small number of conditions to determine whether an observation is in a high risk or high probability subgroup. As pointed out by Wang and Rudin, (2015), the monotonicity in probabilities in falling rule lists allows doctors to identify the most at-risk patients easily. Typical decision tree methods (CART, C4.5, C5.0) do not have the added interpretability that comes from the falling constraint in falling rule lists: one may have to check many conditions in a decision tree to determine whether an observation is in a high risk or high probability subgroup – even if the decision tree has a small depth, it is possible that high risk subgroups are in different parts of the tree, so that one still has to check many conditions in order to find high risk subgroups. In this sense, falling rule lists and softly falling rule lists are as sparse as we need them to be, and they can provide valuable insight into data.

Supplementary Material and Code: The supplementary material and code are available at https://github.com/cfchen-duke/FRLOptimization.

This work was sponsored in part by MIT Lincoln Laboratory.

References

References

Supplementary Material

Algorithm FRL

In this section, we present Algorithm FRL in detail. Given an instance $(D,A,w,C)$ of Program 2.9, the algorithm searches through the space of falling rule lists that are compatible with $D$ and outputs a compatible falling rule list that respects the constraints of Program 2.9, and whose objective value is the smallest among all the falling rule lists that the algorithm explores. It does so by iterating over $T$ steps, in each of which the algorithm constructs a compatible falling rule list $d$, while keeping track of the falling rule list $d^{*}$ that has the smallest objective value $L_{\text{best}}=L(d^{*},D,1/(1+w),w,C)$ among all the falling rule lists that the algorithm has constructed so far. At the end of $T$ iterations, the algorithm outputs the falling rule list that has the smallest objective value out of the $T$ lists it has constructed.

The algorithm uses various properties of Program 2.9, which are presented in Section 4, to prune the search space. More specifically, the algorithm terminates the construction of $d$ if Inequality (9) in Theorem 4.6 holds. Otherwise it either terminates the construction of $d$ with some probability, or proceeds to construct a candidate set $S$ of possible next antecedents, as follows. For every antecedent $A_{l}\in A$ that has not been chosen before, it constructs a candidate next rule $(a_{p}^{(d)},\alpha_{p}^{(d,D)})$ by setting $a_{p}^{(d)}=A_{l}$ and computing $\alpha_{p}^{(d,D)}$ using Definition 2.5. The algorithm then checks if the monotonicity constraint $\alpha_{p}^{(d,D)}\leq\alpha_{p-1}^{(d,D)}$ and the necessary condition for optimality $\alpha_{p}^{(d,D)}>1/(1+w)$ (Corollary 4.5) are satisfied, if the prefix $e^{\prime}=\{e,(a_{p}^{(d)},\alpha_{p}^{(d,D)})\}$ is feasible under Program 2.9 (i.e. whether there exists a compatible falling rule list that begins with the prefix $e^{\prime}$) using Proposition 4.2, and if the best possible objective value $L^{*}(e^{\prime},D,w,C)$ achievable by any falling rule list that begins with $e^{\prime}$ and is compatible with $D$ (Theorem 4.6) is less than the current best objective value $L_{\text{best}}=L(d^{*},D,1/(1+w),w,C)$. If all of the above conditions are satisfied, the algorithm adds $A_{l}$ to $S$. Once the construction of $S$ is complete, the algorithm randomly chooses an antecedent $A_{l}\in S$ with probability $P(A_{l}|S,e,D)$ and uses this antecedent, together with its empirical positive proportion, as the next rule $(a_{p}^{(d)},\alpha_{p}^{(d,D)})$ for $d$. If $S$ is empty, the algorithm terminates the construction of $d$.

A possible choice of the curiosity function $f_{S,e,D}$ for use in Algorithm FRL is given by

The pseudocode of Algorithm FRL is shown in Algorithm 1.

Algorithm softFRL

A possible choice of the curiosity function $f_{S,e,D}$ for use in Algorithm softFRL is given by

The pseudocode of Algorithm softFRL is shown in Algorithm 2.

Proofs of Theorem 2.8, Proposition 4.2, Lemma 4.4, Corollary 4.5, and Theorem 4.6

Theorem 2.8. Given the training data $D$, a rule list $d$ that is compatible with $D$, and the weight $w$ for the positive class, we have

Suppose $\tau>1/(1+w)$. Consider the $j$-th rule $(a_{j}^{(d)},\alpha_{j}^{(d,D)})$ in $d$, whose antecedent captures $\alpha_{j}^{(d,D)}n_{j,d,D}$ positive training inputs and $(1-\alpha_{j}^{(d,D)})n_{j,d,D}$ negative training inputs. Let $R_{j}(d,D,\tau,w)$ denote the contribution by the $j$-th rule to $R(d,D,\tau,w)$, i.e.

Case 1. $1/(1+w)<\alpha_{j}^{(d,D)}\leq\tau$. In this case, we have

Case 2. $\alpha_{j}^{(d,D)}>\tau$. In this case, both $R_{j}(d,D,1/(1+w),w)$ and $R_{j}(d,D,\tau,w)$ are equal to $\frac{1}{n}n^{-}_{j,d,D}$.

Case 3. $\alpha_{j}^{(d,D)}\leq 1/(1+w)$. In this case, both $R_{j}(d,D,1/(1+w),w)$ and $R_{j}(d,D,\tau,w)$ are equal to $\frac{w}{n}n^{+}_{j,d,D}$.

The proof for $R(d,D,1/(1+w),w)\leq R(d,D,\tau,w)$ given $\tau<1/(1+w)$ is similar. ∎

(1) $\Rightarrow$ (3): Suppose that Statement (1) holds. Then there exists a falling rule list

(3) $\Rightarrow$ (2): Suppose that Statement (3) holds. Then we have

Before we proceed with proving Lemma 4.4, we make the following observation.

that begins with a given prefix $e$, we have

We can establish Equations (15) and (16) using essentially the same argument. ∎

Lemma 4.4. Suppose that we are given an instance $(D,A,w,C)$ of Program 2.9, a prefix $e$ that is feasible for Program 2.9 under the training data $D$ and the set of antecedents $A$, and a (possibly hypothetical) falling rule list $d$ that begins with $e$ and is compatible with $D$. Then there exists a falling rule list $d^{\prime}$, possibly hypothetical with respect to $A$, such that $d^{\prime}$ begins with $e$, has at most one more rule (excluding the final else clause) following $e$, is compatible with $D$, and satisfies

Case 1. There exists some $k\in\{|e|+1,...,|d|\}$ that satisfies $\alpha_{k-1}^{(d,D)}>1/(1+w)$ but $\alpha_{k}^{(d,D)}\leq 1/(1+w)$. For any $j\in\{|e|,...,k-1\}$, we have $\alpha_{j}^{(d,D)}>1/(1+w)$, and the contribution $R_{j}(d,D,1/(1+w),w)$ by the $j$-th rule to $R(d,D,1/(1+w),w)$, defined by Equation (13) with $\tau=1/(1+w)$, is given by

For any $j\in\{k,...,|d|\}$, we have $\alpha_{j}^{(d,D)}\leq 1/(1+w)$, and the contribution $R_{j}(d,D,1/(1+w),w)$ by the $j$-th rule to $R(d,D,1/(1+w),w)$ is given by

The rest of the proof for this case proceeds in three steps.

Step 1. Construct a hypothetical falling rule list $d^{\prime}$ that begins with $e$, has exactly one more rule (excluding the final else clause) following $e$, and is compatible with $D$. In later steps, we shall show that the falling rule list $d^{\prime}$ constructed in this step satisfies $L(d^{\prime},D,1/(1+w),w,C)\leq L(d,D,1/(1+w),w,C)$.

Let $d^{\prime}=\{e,(a_{|e|}^{(d^{\prime})},\hat{\alpha}_{|e|}^{(d^{\prime})}),\hat{\alpha}_{|e|+1}^{(d^{\prime})}\}$ be the falling rule list of size $|d^{\prime}|=|e|+1$ that is compatible with $D$, such that

is the antecedent given by the logical or’s of the antecedents $a_{|e|}^{(d)}$ through $a_{k-1}^{(d)}$ in $d$.

Step 2. Show that the empirical risk of misclassification by the falling rule list $d^{\prime}$ is the same as that by the falling rule list $d$.

To see this, we observe that the training instances captured by $a_{|e|}^{(d^{\prime})}$ in $d^{\prime}$ are exactly those captured by the antecedents $a_{|e|}^{(d)}$ through $a_{k-1}^{(d)}$ in $d$, and the training instances captured by $a_{|e|+1}^{(d^{\prime})}$ (i.e. the final else clause) in $d^{\prime}$ are exactly those captured by the antecedents $a_{k}^{(d)}$ through $a_{|d|}^{(d)}$ in $d$. This observation implies

Since $d^{\prime}$ is compatible with $D$, using the definition of a compatible rule list in Definition 2.6 and the definition of the empirical positive proportion in Definition 2.5, together with (19), (21), (22), and (23), we must have

This means that the contribution $R_{|e|}(d^{\prime},D,1/(1+w),w)$ by the $|e|$-th rule to $R(d^{\prime},D,1/(1+w),w)$ is given by

where we have used (20), and the contribution $R_{|e|+1}(d^{\prime},D,1/(1+w),w)$ by the $(|e|+1)$-st “rule” (i.e. the final else clause) to $R(d^{\prime},D,1/(1+w),w)$ is given by

It then follows that the empirical risk of misclassification by the rule list $d^{\prime}$ is the same as that by the rule list $d$:

Using (24), together with the observation $|d^{\prime}|=|e|+1\leq|d|$, we must also have

Case 2. $\alpha_{j}^{(d,D)}>1/(1+w)$ holds for all $j\in\{|e|,|e|+1,...,|d|\}$. Then the contribution $R_{j}(d,D,1/(1+w),w)$ by the $j$-th rule to $R(d,D,1/(1+w),w)$, for all $j\in\{|e|,|e|+1,...,|d|\}$, is given by Equation (17). Let $d^{\prime}=\{e,\hat{\alpha}_{|e|}^{(d^{\prime})}\}$ be the falling rule list of size $|d^{\prime}|=|e|$ that is compatible with $D$. Then the instances captured by $a_{|e|}^{(d^{\prime})}$ (i.e. the final else clause) in $d^{\prime}$ are exactly those that are not captured by $e$, or equivalently, those that are captured by $a_{|e|}^{(d)}$ through $a_{|d|}^{(d)}$. This implies

Since $d^{\prime}$ is compatible with $D$, using the definition of a compatible rule list in Definition 2.6 and the definition of the empirical positive proportion in Definition 2.5, together with (25) and (27), we must have

Inequality (29) implies that the contribution $R_{|e|}(d^{\prime},D,1/(1+w),w)$ by the $|e|$-th “rule” (i.e. the final else clause) to $R(d^{\prime},D,1/(1+w),w)$ is given by

It then follows that the empirical risk of misclassification by the rule list $d^{\prime}$ is the same as that by the rule list $d$:

Since we clearly have $|d^{\prime}|=|e|\leq|d|$, we must also have

Case 3. $\alpha_{j}^{(d,D)}\leq 1/(1+w)$ holds for all $j\in\{|e|,|e|+1,...,|d|\}$. The proof is similar to Case 2, with $R_{j}(d,D,1/(1+w),w)$ for all $j\in\{|e|,|e|+1,...,|d|\}$ given by Equation (18), the “greater than” in Inequality 29 replaced by “less than or equal to”, and $R_{|e|}(d^{\prime},D,1/(1+w),w)$ given by

Corollary 4.5. If $d^{*}$ is an optimal solution for a given instance $(D,A,w,C)$ of Program 2.9, then we must have $\alpha_{j}^{(d^{*},D)}>1/(1+w)$ for all $j\in\{0,1,...,|d^{*}|-1\}$.

Suppose that $d^{*}$ were an optimal solution for a given instance $(D,A,w,C)$ of Program 2.9, such that $\alpha_{k}^{(d^{*},D)}\leq 1/(1+w)$ form some $k\in\{0,1,...,|d^{*}|-1\}$. Let

Before we proceed with proving Theorem 4.6, we make two other observations.

Observation 10.2. For any rule list $d^{\prime}$, we have

Since $n_{|e|,d^{\prime},D}$ denotes the total number of training inputs captured by the $|e|$-th antecedent in $d^{\prime}$, which is exactly the sum of the number of positive training inputs captured by that antecedent (denoted $n^{+}_{|e|,d^{\prime},D}$), and the number of negative training inputs captured by the same antecedent (denoted $n^{-}_{|e|,d^{\prime},D}$), we have

The desired equation follows from rearranging the terms. ∎

that has exactly one rule (excluding the final else clause) following a given prefix $e$, we have

Applying Observation 10.1 with $|d^{\prime}|=|e|+1$, we have

Equations (31), (32), and (33) follow from rearranging the terms in the above equations. ∎

Theorem 4.6. Suppose that we are given an instance $(D,A,w,C)$ of Program 2.9 and a prefix $e$ that is feasible for Program 2.9 under the training data $D$ and the set of antecedents $A$. Then any falling rule list $d$ that begins with $e$ and is compatible with $D$ satisfies

is a lower bound on the objective value of any compatible falling rule list that begins with $e$, which we call a prefix bound for $e$, under the instance $(D,A,w,C)$ of Program 2.9. Furthermore, if

Let $\mathcal{F}(\mathcal{X},D,e)$ be the set of (hypothetical and non-hypothetical) falling rule lists that begin with $e$ and are compatible with $D$, and let $\mathcal{F}(\mathcal{X},D,e,k)$ be the subset of $\mathcal{F}(\mathcal{X},D,e)$, consisting of those falling rule lists in $\mathcal{F}(\mathcal{X},D,e)$ that have exactly $k$ rules (excluding the final else clause) following the prefix $e$.

Case 1. $\alpha_{|e|-1}^{(e,D)}>1/(1+w)$.

which implies that $\bar{e}$ is indeed compatible with $D$.

Conversely, for any $d_{0}=\{e,\hat{\alpha}_{|e|}^{(d_{0})}\}\in\mathcal{F}(\mathcal{X},D,e,0)$, we must have

which implies $d_{0}=\bar{e}$. This establishes $\mathcal{F}(\mathcal{X},D,e,0)=\{\bar{e}\}$.

Let $\mathcal{F}^{\prime}(\mathcal{X},D,e,1)$ be the subset of $\mathcal{F}(\mathcal{X},D,e,1)$, consisting of those falling rule lists

with $\alpha_{|e|}^{(d^{\prime},D)}>1/(1+w)$ and $\alpha_{|e|+1}^{(d^{\prime},D)}\leq 1/(1+w)$. Note that for any $d_{1}=\{e,(a_{|e|}^{(d_{1})},\alpha_{|e|}^{(d_{1},D)}),\alpha_{|e|+1}^{(d_{1},D)}\}\in\mathcal{F}(\mathcal{X},D,e,1)-\mathcal{F}^{\prime}(\mathcal{X},D,e,1)$, we have either $\alpha_{|e|}^{(d_{1},D)}\geq\alpha_{|e|+1}^{(d_{1},D)}>1/(1+w)$ or $\alpha_{|e|+1}^{(d_{1},D)}\leq\alpha_{|e|}^{(d_{1},D)}\leq 1/(1+w)$, and Lemma 4.4 implies $L(d_{1},D,1/(1+w),w,C)\geq L(\bar{e},D,1/(1+w),w,C)$. This means

Using $\mathcal{F}(\mathcal{X},D,e,0)=\{\bar{e}\}$ and (36), we can write the right-hand side of (35) as

The rest of the proof for this case proceeds in three steps.

Step 1. Compute $L(\bar{e},D,1/(1+w),w,C)$.

Since the contribution by the final else clause to $L(\bar{e},D,1/(1+w),w,C)$ is given by

Step 2. Determine a lower bound of $L(d^{\prime},D,1/(1+w),w,C)$ for all $d^{\prime}\in\mathcal{F}^{\prime}(\mathcal{X},D,e,1)$.

Let $d^{\prime}=\{e,(a_{|e|}^{(d^{\prime})},\alpha_{|e|}^{(d^{\prime},D)}),\alpha_{|e|+1}^{(d^{\prime},D)}\}\in\mathcal{F}^{\prime}(\mathcal{X},D,e,1)$. Since the contribution by both the $|e|$-th rule and the final else clause to $L(d^{\prime},D,1/(1+w),w,C)$ is given by $R_{|e|}(d^{\prime},D,1/(1+w),w)+R_{|e|+1}(d^{\prime},D,1/(1+w),w)+C$, where $R_{|e|}(d^{\prime},D,1/(1+w),w)$ and $R_{|e|+1}(d^{\prime},D,1/(1+w),w)$ are defined by Equation (13) and are given by

(because we have $\alpha_{|e|}^{(d^{\prime},D)}>1/(1+w)$ and $\alpha_{|e|+1}^{(d^{\prime},D)}\leq 1/(1+w)$ for $d^{\prime}\in\mathcal{F}^{\prime}(\mathcal{X},D,e,1)$), it is not difficult to see

Substituting (30) in Observation 10.2 and (31) in Observation 10.3 into Equation (39), we have

Note that Equation (40) shows that given the prefix $e$, $L(d^{\prime},D,1/(1+w),w,C)$ is a function of $\alpha_{|e|}^{(d^{\prime},D)}$ and of $n^{+}_{|e|,d^{\prime},D}$. Since we have

because $\alpha_{|e|}^{(d^{\prime},D)}>1/(1+w)$ holds for any $d^{\prime}\in\mathcal{F}^{\prime}(\mathcal{X},D,e,1)$, and

Using (35), (37), (38), and (41), we have

Case 2. $\alpha_{|e|-1}^{(e,D)}\leq 1/(1+w)$.

This implies $\alpha_{j}^{(d,D)}\leq 1/(1+w)$ for all $j\in\{|e|,...,|d|\}$. By Lemma 4.4, we have

Since $L(\bar{e},D,1/(1+w),w,C)$ is given by Equation (38), we have

Given $\alpha_{|e|-1}^{(e,D)}\leq 1/(1+w)$, we must also have

Substituting (43) into (42) completes the proof for Case 2.

Finally, if Inequality (34) holds, then we have

Proof of Theorem 5.2

Theorem 5.2. Suppose that we are given an instance $(D,A,w,C,C_{1})$ of Program 5.1 and a prefix $e$ that is compatible with $D$. Then any rule list $d$ that begins with $e$ and is compatible with $D$ satisfies

is a lower bound on the objective value of any compatible rule list that begins with $e$, under the instance $(D,A,w,C,C_{1})$ of Program 5.1. In Equation (44), $\alpha_{\min}^{(e,D)}$, $\zeta$, and $g$ are defined by

To prove Theorem 5.2, we need the following lemma:

Lemma. Suppose that we are given an instance $(D,A,w,C,C_{1})$ of Program 5.1, a prefix $e$ that is compatible with $D$, and a (possibly hypothetical) rule list $d$ that begins with $e$ and is compatible with $D$. Then there exists a rule list $d^{\prime}$, possibly hypothetical with respect to $A$, such that $d^{\prime}$ begins with $e$, has at most one more rule (excluding the final else clause) following $e$, is compatible with $D$, and satisfies

Case 1. There exists some $k\in\{|e|,...,|d|\}$ that satisfies $\alpha_{k}^{(d,D)}>1/(1+w)$ and some $k^{\prime}\in\{|e|,...,|d|\}$ that satisfies $\alpha_{k^{\prime}}^{(d,D)}\leq 1/(1+w)$. For any $j\in\{|e|,...,|d|\}$ with $\alpha_{j}^{(d,D)}>1/(1+w)$, the contribution $R_{j}(d,D,1/(1+w),w)$ by the $j$-th rule to $R(d,D,1/(1+w),w)$, defined by the right-hand side of Equation (13) with $\tau=1/(1+w)$, is given by

For any $j\in\{|e|,...,|d|\}$ with $\alpha_{j}^{(d,D)}\leq 1/(1+w)$, the contribution $R_{j}(d,D,1/(1+w),w)$ by the $j$-th rule to $R(d,D,1/(1+w),w)$ is given by

The rest of the proof for this case proceeds in four steps.

Step 1. Construct a hypothetical rule list $d^{\prime}$ that begins with $e$, has exactly one more rule (excluding the final else clause) following $e$, and is compatible with $D$. In later steps, we shall show that the rule list $d^{\prime}$ constructed in this step satisfies (45).

Let $d^{\prime}=\{e,(a_{|e|}^{(d^{\prime})},\hat{\alpha}_{|e|}^{(d^{\prime})}),\hat{\alpha}_{|e|+1}^{(d^{\prime})}\}$ be the hypothetical rule list of size $|d^{\prime}|=|e|+1$ that is compatible with $D$, and whose $|e|$-th antecedent $a_{|e|}^{(d^{\prime})}$ is defined by

Step 2. Show that the empirical risk of misclassification by the rule list $d^{\prime}$ is the same as that by the rule list $d$.

To see this, we observe that the training instances in $D$ captured by $a_{|e|}^{(d^{\prime})}$ in $d^{\prime}$ are exactly those captured by the antecedents $a_{j}^{(d)}$, $|e|\leq j\leq|d|$, in $d$ whose empirical positive proportion satisfies $\alpha_{j}^{(d,D)}>1/(1+w)$, and the training instances in $D$ captured by $a_{|e|+1}^{(d^{\prime})}$ (i.e. the final else clause) in $d^{\prime}$ are exactly those captured by the antecedents $a_{j}^{(d)}$, $|e|\leq j\leq|d|$, in $d$ whose empirical positive proportion satisfies $\alpha_{j}^{(d,D)}\leq 1/(1+w)$. This observation implies

Since $d^{\prime}$ is compatible with $D$, using the definition of a compatible rule list in Definition 2.6 and the definition of the empirical positive proportion in Definition 2.5, together with (46), (48), (49), and (50), we must have

This means that the contribution $R_{|e|}(d^{\prime},D,1/(1+w),w)$ by the $|e|$-th rule to $R(d^{\prime},D,1/(1+w),w)$ is given by

where we have used (47), and the contribution $R_{|e|+1}(d^{\prime},D,1/(1+w),w)$ by the $(|e|+1)$-st “rule” (i.e. the final else clause) to $R(d^{\prime},D,1/(1+w),w)$ is given by

It then follows that the empirical risk of misclassification by the rule list $d^{\prime}$ is the same as that by the rule list $d$:

Step 3. Show that the monotonicity penalty of the rule list $d^{\prime}$ is at most that of $d$.

Let $S(d,D)=\sum_{j=0}^{|d|}\lfloor\alpha_{j}^{(d,D)}-\min_{k<j}\alpha_{k}^{(d,D)}\rfloor_{+}$ be the monotonicity penalty of the rule list $d$. We now show $S(d^{\prime},D)\leq S(d,D)$. Let $S_{j}(d,D)=\lfloor\alpha_{j}^{(d,D)}-\min_{k<j}\alpha_{k}^{(d,D)}\rfloor_{+}$ be the monotonicity penalty for the $j$-th rule in $d$.