Efficient Rule Ensemble Learning using Hierarchical Kernels

Pratik Jawanpuria, Jagarlapudi Saketha Nath, Ganesh RamakrishnanICML 2011 · OpenReview

Introduction

In machine learning, there is often a critical trade-off between model accuracy and interpretability. Rule Ensemble Learning (REL) addresses this by constructing models from a weighted set of simple "if-then" rules (e.g., if (Age > 30) AND (Income < 50k) then Class A). This paper introduces a novel framework for REL that leverages Hierarchical Kernel Learning (HKL) to efficiently search an exponentially large space of potential rules. By generalizing the HKL formulation with a $\rho$-norm regularizer, the authors successfully eliminate the redundancy typically found in hierarchical models, producing rule sets that are both more accurate and significantly more compact than previous state-of-the-art methods.

The Challenge of Rule Ensemble Learning

The primary goal of REL is to discover a small set of simple rules and their optimal weights to achieve strong generalization. However, this presents a two-fold challenge:

  1. Exponential Complexity: The number of possible rules (conjunctions of basic features) grows exponentially with the number of input features. It is computationally intractable to evaluate every possible combination.
  2. Interpretability vs. Accuracy: A highly interpretable model requires a small number of simple rules (few conjunctions). Standard heuristic or greedy methods often result in bloated, redundant rule sets or miss the optimal combinations entirely.

Proposed Methodology: Generalized Hierarchical Kernel Learning

To navigate the massive search space, the authors structure the potential rules into a conjunction lattice, organizing them from the simplest (single conditions) to the most complex. They then apply Hierarchical Kernel Learning (HKL), a framework that allows for searching this exponential space in polynomial time.

However, standard HKL imposes a strict structural constraint: it only selects a complex rule if all of its simpler sub-rules (ancestors in the lattice) are also selected. In the context of rule learning, this creates massive "psycho-visual redundancy." If a specific complex rule is highly predictive, forcing the inclusion of all its generic parent rules bloats the ensemble unnecessarily.

To resolve this, the authors propose Generalized HKL:

  • $\rho$-norm Regularization: They replace the standard 2-norm used in HKL with a $\rho$-norm (where $1 < \rho \leq 2$). This mathematical relaxation encourages sparsity within the hierarchy, allowing the model to select a specific complex rule without being forced to include all its simpler ancestors.
  • Mirror-Descent Active Set Algorithm: Because the optimization problem remains massive, the authors developed an efficient, convex algorithm. It starts with a small "active set" of rules and iteratively adds only the most promising ones, ensuring computation remains manageable while guaranteeing a globally optimal solution for the objective function.

Empirical Results

The researchers evaluated their approach on 10 benchmark datasets from the UCI Machine Learning Repository, covering a mix of categorical, logical, medical, and social science tasks.

The generalized HKL approach (specifically $HKL_{1.1}$, where $\rho = 1.1$) was compared against state-of-the-art algorithms like RuleFit, SLIPPER (SLI), and ENDER.

Table comparing F-scores, rule counts, and rule lengths across different algorithms and datasets.

As demonstrated in the results, $HKL_{1.1}$ consistently outperformed or matched baseline methods across key metrics:

  • Compactness: On the Monk-3 dataset, $HKL_{1.1}$ achieved an outstanding F1-score of 0.972 using only 2 rules, whereas other methods required between 7 and 500 rules.
  • Accuracy: In the Tic-Tac-Toe dataset, $HKL_{1.1}$ achieved an F1-score of 0.935, significantly higher than RuleFit (0.652) and SLIPPER (0.747).
  • Sparsity: The $\rho$-norm proved highly effective at pruning redundant information. The authors noted that $HKL_{1.1}$ resulted in roughly 86.8% of the potential rules in the final "hull" being assigned zero weight.

Limitations and Future Directions

While Generalized HKL represents a significant step forward for interpretable machine learning, the authors note a few limitations:

  • Computational Scaling: The algorithm's complexity is polynomial in the number of selected rules, but the overall complexity scales at $O(m^3 R^3 \log R)$ (where $m$ is the number of examples and $R$ is the active set size). This may still pose computational challenges for extremely large-scale datasets with millions of records.
  • Binary Focus: The current implementation and evaluation focus primarily on binary classification. Extending this convex formulation efficiently to multi-class classification or regression tasks remains a logical next step.
  • Feature Engineering Dependency: The method relies on the initial definition of "basic propositions." The ultimate quality of the learned rules is still bounded by how well the initial continuous feature thresholds are discretized and chosen.

Summary updated

Abstract

This paper addresses the problem of Rule Ensemble Learning (REL), where the goal is simultaneous discovery of a small set of simple rules and their optimal weights that lead to good generalization. Rules are assumed to be conjunctions of basic propositions concerning the values taken by the input features. From the perspectives of interpretability as well as generalization, it is highly desirable to construct rule ensembles with low training error, having rules that are i) simple, i.e., involve few conjunctions and ii) few in number. We propose to explore the (exponentially) large feature space of all possible conjunctions optimally and efficiently by employing the recently introduced Hierarchical Kernel Learning (HKL) framework. The regularizer employed in the HKL formulation can be interpreted as a potential for discouraging selection of rules involving large number of conjunctions – justifying its suitability for constructing rule ensembles. Simulation results show that, in case of many benchmark datasets, the proposed approach improves over state-of-the-art REL algorithms in terms of generalization and indeed learns simple rules. Unfortunately, HKL selects a conjunction only if all its subsets are selected. We propose a novel convex formulation which alleviates this problem and generalizes the HKL framework. The main technical contribution of this paper is an efficient mirror-descent based active set algorithm for solving the new formulation. Empirical evaluations on REL problems illustrate the utility of generalized HKL.
BibTeX
@inproceedings{jawanpuria2011efficient,
  author = {Pratik Jawanpuria and Jagarlapudi Saketha Nath and Ganesh Ramakrishnan},
  title = {{Efficient Rule Ensemble Learning using Hierarchical Kernels}},
  booktitle = {International Conference on Machine Learning},
  year = {2011},
  url = {https://openreview.net/forum?id=HkWIT5-ubr},
}
Figure