In machine learning, there is a long-standing tension between the complexity of a model and its interpretability. Standard approaches to building decision trees or rule sets often rely on "greedy" heuristics—making the best local decision at each step—which frequently results in bloated, redundant structures that are difficult for humans to audit.
A growing body of research suggests a more principled alternative: treating model structure itself as a Bayesian inference problem. By applying sparsity-inducing priors to the space of possible trees, grammars, and rule lists, researchers can find "glass-box" models that are significantly smaller than traditional versions while maintaining, or even exceeding, state-of-the-art accuracy.
The Structural Occam’s Razor
The core intuition behind this direction is that a model’s complexity should be a formal part of its objective function, not an afterthought addressed by pruning. In a Bayesian framework, this is achieved through complexity-penalizing priors.
For example, Benjamin Letham, Cynthia Rudin, and colleagues developed Bayesian Rule Lists (BRL), which use Poisson distributions as priors to explicitly favor shorter lists and fewer conditions per rule. Instead of growing a list until it fits the data and then cutting it back, the prior acts as a "structural Occam’s Razor," guiding the model toward the simplest logical explanation from the start.
This approach has been extended to various domains:
- Medical Decision Support: Veerajalandhar Allareddy and Tong Wang used Multi-value Rule Sets (MRS) to predict patient mortality. By penalizing the number of rules and unique features, they created logic that hospital staff can read and trust.
- Causal Inference: In Causal Rule Sets (CRS), Cynthia Rudin and Tong Wang applied these priors to identify subgroups where treatments are most effective, ensuring the resulting descriptions remain human-readable.
From Greedy Splitting to Global Optimization
Traditional decision trees like CART are built top-down, one split at a time. This greedy approach is fast but often misses the most compact global structure. Recent work has reframed tree induction as a search for the Maximum A Posteriori (MAP) model—the single most likely structure given the data and the prior.
Mo Tiwari, Sebastian Thrun, and Colin Sullivan demonstrated this with MAPTree. By framing the search as an efficient AND/OR graph problem, they found trees that are provably optimal under the Bayesian objective. These trees are often an order of magnitude smaller than those produced by standard "optimal" tree algorithms, yet they are more robust to noise because the prior prevents them from over-fitting to small fluctuations in the training data.
Sparsity in Linguistic Structures
The same principles apply to the complex, recursive structures of human language. In grammar induction, the goal is to find a set of rules that explain a corpus of text. Without a strong preference for simplicity, models tend to "memorize" the training data by creating thousands of highly specific rules.
Percy Liang, Michael Jordan, and Dan Klein addressed this by incorporating Hierarchical Dirichlet Process priors into PCFGs. This nonparametric approach allows the model to determine the "right" number of rules automatically. The result is a compact grammar that uses roughly half the rules of standard models while maintaining competitive accuracy.
Similarly, in the context of Tree Substitution Grammars (TSGs), Benjamin Swanson and Eugene Charniak showed that Bayesian induction produces more concise and informative "syntactic fingerprints" than heuristic methods. By focusing on statistically significant structures rather than every possible subtree, the Bayesian approach yields features that generalize better to new data.
Why It Works: The Power of Global Constraints
The success of these models across disparate fields—from crime analysis to sentence compression—stems from a shared mechanism: global regularization.
In Cascaded High Dimensional Histograms, Cynthia Rudin and Siong Thye Goh show that Bayesian priors allow for a controlled trade-off between statistical fit and human interpretability. Because the prior penalizes the total number of leaves or branches across the entire model, the optimization process is forced to group data into a limited number of high-impact partitions.
This global view is what allows BCART-PCFG to produce decision trees that are up to 20x smaller than those from standard methods. By transforming tree induction into a grammar problem and applying tractable priors, Colin E. Sullivan and colleagues proved that we don't have to sacrifice performance for simplicity. When we define "goodness" as a balance of accuracy and parsimony, the resulting models are not just easier to understand—they are often more fundamentally correct.