Abstract
An efficient implementation of Scalable Bayesian Rule Lists Algorithm, a competitor algorithm for decision tree algorithms; see Hongyu Yang, Cynthia Rudin, Margo Seltzer (2017) https://proceedings.mlr.press/v70/yang17h.html. It builds from pre-mined association rules and has a logical structure identical to a decision list or one-sided decision tree. Fully optimized over rule lists, this algorithm strikes a practical balance between accuracy, interpretability, and computational speed.
TL;DR
The sbrl package implements the Scalable Bayesian Rule Lists algorithm, a powerful alternative to traditional decision trees. By combining pre-mined association rules with a Bayesian hierarchical model, it produces "if-then-else" decision lists that are both highly accurate and easily interpretable by humans.
Introduction: The Interpretability-Accuracy Trade-off
In machine learning, there is often a painful trade-off between accuracy and interpretability. Complex "black-box" models like Deep Neural Networks or Random Forests might predict well, but they offer little insight into why a specific decision was made. Conversely, simple models like small decision trees are easy to understand but often lack predictive power.
The Scalable Bayesian Rule Lists (SBRL) model addresses this gap. It targets the need for models that can handle large datasets while producing a logical structure—specifically a "one-sided decision tree" or decision list—that a human can read and validate in seconds. This is particularly crucial in high-stakes domains like healthcare or criminal justice, where understanding the logic behind a prediction is as important as the prediction itself.
Methods: From Rule Mining to Bayesian Optimization
The sbrl algorithm operates in a two-stage process:
- Rule Mining: Instead of building a tree from scratch, the algorithm starts with a set of pre-mined association rules (using the
arulespackage). These are simple patterns found in the data (e.g., "if feature A is true and feature B is false"). - Bayesian Optimization: The core of the package is a Bayesian hierarchical model that searches through the space of possible rule lists. It uses Markov Chain Monte Carlo (MCMC) to find an optimal sequence of these rules.
The resulting model is a Decision List: a series of "if-then" statements ending in a final "else" (default) rule. Unlike standard decision trees that can branch in many directions, SBRL produces a linear, one-sided structure that is significantly easier for a human to follow.
The optimization process is guided by several key parameters, including lambda (the expected length of the rule list) and eta (the expected cardinality of the rules). These allow users to tune the complexity and interpretability of the final model.
Datasets: Benchmarking with Tic-Tac-Toe
The documentation highlights the use of the Tic-Tac-Toe Endgame Dataset (sourced from the UCI Machine Learning Repository).
- Details: This dataset contains 958 observations of legal tic-tac-toe board configurations.
- Goal: The task is to predict whether "x" has won the game based on the state of the nine board squares (c1 through c9).
- Role: It serves as a benchmark for demonstrating how SBRL can take categorical features and turn them into a human-readable winning/losing logic.
Key Insights and Ideas
- One-Sided Logic: By restricting the model to a decision list (rather than a complex branching tree), the authors prioritize human cognitive limits. You only ever have to follow one path to reach a conclusion.
- Global Optimization: Unlike standard decision tree algorithms (like CART) which use "greedy" searches—making the best local choice at each split—SBRL optimizes over the entire rule list simultaneously using Bayesian inference.
- Scalability: As the name suggests, the implementation is "fully optimized," utilizing C++ (via
Rcpp) to handle the heavy lifting of the MCMC chains, making it practical for modern data scales. - Probabilistic Output: Instead of just a hard classification, the model provides the "positive probability" for each rule, allowing users to understand the level of certainty for different segments of the population.
Key Results
While the package manual focuses on implementation, it points to the foundational research showing that SBRL:
- Matches Accuracy: It performs competitively with state-of-the-art (but opaque) models like Random Forests on many benchmark datasets.
- Superior Interpretability: It consistently produces models with fewer rules and simpler conditions than traditional decision tree learners.
- Computational Efficiency: The MCMC implementation is designed to strike a "practical balance" between the time required to train the model and the quality of the resulting rule list.
Limitations and Future Work
- Categorical Constraints: The algorithm is primarily designed for discrete/categorical data. Continuous variables must be discretized (binned) before they can be used to mine association rules.
- MCMC Convergence: Like all MCMC-based methods, the quality of the result depends on the number of iterations and chains. Users must tune parameters like
lambdaandetato get the best results. - Pre-mining Dependency: The model's performance is inherently limited by the quality of the rules generated in the initial mining phase. If the "perfect" rule isn't mined at the start, the Bayesian optimizer cannot find it.
Summary updated