While most rule learning methods focus on categorical targets for tasks including classification and subgroup discovery, rule learning for numeric targets are under-studied, especially using probabilistic rules: the only existing probabilistic rule list method for numeric targets, named SSD++, is based on Gaussian parametric models. To extend this method, we adopt an adaptive histogram model to estimate the probability distribution of the target variable. We formalize the rule list learning as a model selection problem, which we tackle with the minimum description length principle. We demonstrate that our method produces rule lists with better predictive performance than SSD++.
Learning rules from data is a long studied problem in inductive reasoning, data mining, and machine learning. It has been widely used in practice as rules are directly readable by analysts and domain experts, revealing actionable insights for real-world data-driven tasks. However, rule learning for numeric targets is under-studied, especially the task of inducing a rule-based global model for describing the whole dataset.
Classic rule learning algorithms often follow the separate and conquer strategy: learn a single
rule from the dataset, remove the covered instances, and repeat the process until some stopping
criterion is met. As a result, the separate and conquer strategy leads to an ordered list of rules,
also referred to as decision list or rule list. While it is proved to be eficient in classification
tasks [
The criteria used in rule lists for categorical targets are often based on probabilistic estimates
(i.e., precision, false positive rate, etc), including 1) heuristics for evaluating individual rules
as local patterns, 2) global evaluation metrics for a rule list model, and 3) statistics used for
statistical significance testing in order to prevent overfit [
To strike a balance between the computational cost and model expressiveness, we adopt adaptive histograms for density estimation for learning rules for numeric targets. Our contribution are as follows: 1) we formalize the problem of learning rule lists as a model selection task; 2) by showing that the model selection criterion of the rule lists can be decomposed to the sum of local criterion for each individual rule, we demonstrate our model selection criterion to be compatible with the separate and conquer strategy; 3) we empirically showcase that the rule lists obtained by our method outperforms that of SSD++ in terms of prediction accuracy, measured by the mean squared error.
Related Work. Far fewer rule learning methods exist for numeric targets than categorical
targets. Besides SSD++, PRIM [
Adaptive histogram for numeric targets. Consider a one-dimensional random variable taking values in R, a histogram model for is a set of cut points (including boundaries), denoted as ⃗ = (1, . . . , +1), where represents the number of bins. For any value in the support of , the associated probability distribution, denoted by ℎ(.), has density function defined and denoted as ℎ( = ) = ∑︀
=1 1[,+1)() , where 1(.) is the indicator function and = ( 1, ..., ) is the parameter vector to be estimated from data; i.e., represents the probability of taking values in each of all bins. In practice, can be estimated by the maximum likelihood estimator: ˆ = |{≤ <+1}| , where |.| is the cardinality function.
|| (+1− )
Consider the -dimensional feature variables = (1, . . . , ), where each a single dimension of , and a target variable ∈ R. A histogram-based rule is written as (1 ∈ 1 ∧ 2 ∈ 2 ∧ . . .) → ℎ,( ), where each ∈ is called a literal of the condition of the rule. Specifically, each is a closed interval or a set of categorical levels. A rule in this form describes a subset of the full sample space of , such that for any ∈ , the conditional distribution ( | = ) is approximated by the probability distribution of conditioned on the event { ∈ }, i.e., ( | ∈ ), which is modelled by an adaptive histogram model, associated with and hence denoted as ℎ,( ). Thus, a histogram-based rule is a local probabilistic model for all instances that satisfy the rule. To simplify the notation, when clear from the context we use to refer to the rule itself and the subset of all instances covered by the rule.
Precisely, a rule list is an ordered list of rules connected by the “If...ElseIf...Else..." statements. For instance, a rule list containing only two rules 1 and 2 can be written as “IF ∈ 1, THEN ℎ,1 ; ELSE IF ∈ 2, THEN ℎ,2 ; ELSE: ℎ,0 ". Note that we use ℎ,0 to represent the histogram that is associated with the instances not covered by any rule, and referred to 0 as the “else rule"1. Therefore, a rule list connects multiple rules and hence becomes a global model for the whole dataset: given any instance (, ), we can calculate the probability (density) by firstly going over the rule list until satisfies the condition of a certain rule, and then predicting the density function of conditioned on by the histogram model associated with that rule.
We formalize the task of learning a rule list as a probabilistic model selection task. We adopt the
minimum description length (MDL) principle [
Consider an individual rule (with a histogram with fixed cut points) and all the instances satisfying the condition of , denoted as (, ).
Formally, the
optimal adaptive histogram ℎ* among all possible histograms ℋ is defined as
arg minℎ∈ℋ − log ˆℎ,( = ) + ℛ(, ))︀ ; note that 1) ˆℎ, is the estimated
probabil︀(
ity density function with the maximum likelihood estimator for ⃗ , 2) ˆℎ,() is extended to
=
ℎ*
1A related and widely used notion is the “default rule". The diference lies in whether the parameters associated
with 0 is estimated by all instances (default rule) or by instances that are not covered by any rule in the rule list
(else rule).
ˆℎ,() with the i.i.d assumption, and 3) ℛ(, ) is the so-called regret, the “penalty term" of
the MDL model selection criterion, which is a function of sample size and the number of bins
of the histogram [
The task of learning a rule list needs to simultaneously select the cut points on features (for
constructing the rules’ conditions) and on targets (for constructing the adaptive histograms).
Formally, denote the (training) dataset as = (, ), then the best histogram-based rule list,
denoted as * , among all possible rule lists ℳ, is defined as
* = arg min (, ) = arg min − log ˆ (|) + ℛ( ) + ( ),
∈ℳ ∈ℳ
(1)
where 1) ˆ (|) is the likelihood for the data, based on the maximum likelihood estimator
of the parameter ⃗ for all histograms; 2) ℛ( ) is the MDL regret term for the rule list as a
global model, defined as ℛ( ) = log ∫︀ ˆ ( = |), which can be proved to be the
sum of the regret terms ℛ of all individual rules [
As exhaustive search in rule learning is known to be computationally prohibitive [
To search for the next rule based on the current (incomplete) rule list, we grow the rule
by iteratively adding literals to an empty rule. Intuitively, we should not search for the next
rule by minimizing (, ) directly, as our goal is not to minimize (, ) by adding one
more rule only. Instead, we should search for the next rule such that by adding this rule to the
rule list, we take a step towards our final rule list in the “steepest direction". Informally, the
“steepest direction" can be thought of the direction that reduces (, ) most per extra covered
instance. That is, we use the heuristic named “normalized gain" [
We benchmark our method against SSD++ with widely used UCI datasets for regression tasks, to
investigate the predictive performance improvement by adopting the non-parametric histogram
models. We also include the results of CART [
We report the mean squared error (MSE) and the total number of literals in the rule list in Table 1, and the results are obtained by 10 random train/test splits, in which 80% of the instances are used for training. We show that our histogram-based approach outperforms SSD++ in most datasets. Thus, the Gaussian assumption will indeed lead to sub-optimal results for rule learning. Further, we observe that CART outperforms our method in about half the datasets, but CART in general produces more complicated models than our method in terms of the number of literals in each rule (path from root to leaf).
Next, we observe that SSD++ produces much simpler models than our method. This can be explained as follows: SSD++ and our method both use the MDL principle to control the model complexity, and hence the rule can grow only when the “gain" in likelihood exceeds the “cost" in the regret term and model complexity. Since adaptive histograms are much more expressive than Gaussian parametric models, it is “easier" for the rule to obtain substantial “gain" in likelihoods, which drives the rules to grow longer and hence cover smaller subsets. As a result, more rules are needed to cover the whole dataset and hence our method produces longer rules and a larger number of rules.
We developed a rule list method for numeric targets with the adaptive histogram model, and we demonstrated that the predictive performance is superior to the existing method based on parametric Gaussian models. The limitation of our method is scalability, due to the quadratic complexity of searching the optimal adaptive histograms: for datasets with tens of features and thousands of sample sizes, the training process can take a few minutes. The future work may be focused on developing methods for calculating the “score" of each rule list approximately but eficiently.
This work is part of the research programme ‘Human-Guided Data Science by Interactive Model Selection’ with project number 612.001.804, which is (partly) financed by the Dutch Research Council (NWO). data cholesterol autoMPG8 dee ele-1 forestFires concrete abalone