cs.LGSep 6, 2026

Sparse Oblique Rule Boosting for Simpler Additive Rule Ensembles

Authors: Shahrzad Behzadimanesh, Pierre Le Bodic, Geoffrey I. Webb, Mario Boley

Organizations: Department of Data Science and Artificial Intelligence, Monash University, Melbourne, VIC, Australia. · Department of Information Systems, University of Haifa, Haifa, Israel.

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Small additive ensembles of symbolic rules offer interpretable prediction models. Traditionally, these ensembles use rule conditions based on conjunctions of simple threshold propositions x≥tx \geq t on a single input variable xx and threshold tt, resulting geometrically in axis-parallel polytopes as decision regions. While this form ensures a high degree of interpretability for individual rules and can be learned efficiently using the gradient boosting approach, it relies on having access to a curated set of expressive input features so that a small ensemble of axis-parallel regions can describe the target variable well. Absent such features, reaching sufficient accuracy requires increasing the number and complexity of individual rules, which diminishes the interpretability of the model. Here, we extend classical rule ensembles by introducing logical propositions with learnable sparse linear transformations of input variables, i.e., propositions of the form xTw≥t\mathbf{x}^T\mathbf{w} \geq t, where w\mathbf{w} is a learnable sparse weight vector, enabling decision regions as general polyhedrons with oblique faces. We propose a learning method using gradient boosting based on a weighted logistic regression. Empirical results across 14 regression and classification tasks demonstrate that the proposed method achieves lower model complexity than competitive baselines while maintaining similar or better predictive accuracy. Hence, the approach provides a favorable trade-off between interpretability and accuracy and reduces the reliance on manual feature engineering.

Figures & tables

Figure 1: Standard axis-parallel rule ensemble for modeling propensity to diabetes based on the 2017-18 CDC NHANES survey ( National Center for Health Statistics, 2020 ) ( left ) versus the proposed simple polyhedron conditions ( right ). In conjunction with log-transforms the proposed model enables learning ratio conditions, which are used here to represent the concept of body-mass-index—leading to approx. identical log loss with a simpler rule ensemble.
Figure 2: Decision regions of rules generated by linear transformation learning and traditional gradient boosting for synthetic data with ground truth decision boundary given by x1+x2=0x_{1}+x_{2}=0 .
Sparse Logistic Linear Transformation Boosting
-4.54ifTrue
+6.84if(0.86 pet_length - sep_width ≥\geq -0.5) AND ( pet_width ≤\leq 1.8) AND ( pet_length ≤\leq 5.2)
Rule Fit Oblique Trees
-2.69ifTrue
-1.8if(-0.9 sep_length +2.29 sep_width -0.06 pet_length +1.16 pet_width >> 2.6)
+2.39if(0.78 sep_width -0.56 pet_length +1.31 pet_width >> 1.7) AND
Table 1: Rules generated by different methods on the Iris dataset (label “Versicolor” vs rest). Each ensemble corresponds to the smallest that achieves at least a 50% reduction in normalized test risk.
Figure 3: Comparison of two search strategies for learning a single conjunction with a maximum rule complexity of cmax=5c_{max}=5 . Each box represents a candidate conjunction including candidate proposition p~j(s)\tilde{p}_{j}^{(s)} with sparsity ∥wj∥0=s\|\mathbf{w}_{j}\|_{0}=s , while pj(s)p_{j}^{(s)} denotes a fixed selected proposition. The red paths indicate the best conjunction candidates selected at each complexity level. In both strategies, a new proposition can be added at each level to increase rule complexity. (Left) : At each complexity level (vertical levels), all possible sparsity levels (horizontal levels) for the next proposition while previously learned propositions are fixed. The conjunction candidate with the highest boosting objective is selected as the final conjunction. (Right) : At each complexity level, the conjunction complexity increases by one, allowing previously learned propositions to be refitted with higher sparsity ( s+1s+1 ). All configurations constrained by the current complexity are evaluated via the boosting objective, and the best candidate is retained. Finally, selected conjunctions across all complexity levels are compared on validation risk, and the one with the lowest risk is selected as the final rule.
Figure 4: Risk/complexity trade-offs for different methods and 8 datasets based on cross-validation-selected hyper-parameters (corresponding plots for the remaining datasets are provided in appendix, Figure 6 ). The y-axis shows the mean normalized risk, computed using squared loss for regression datasets and logistic loss for classification datasets, averaged over 15 repetitions for model complexities ranging from 1 to 100. Error bars represent 95% confidence intervals.
 25% risk reduction
DatasetTGBNRERFObTrLLTBEBM
Iris6 8 1310 10 1316 25 298 9 1440 40 40
Liver∞\infty ∞\infty ∞\infty∞\infty ∞\infty ∞\infty∞\infty ∞\infty ∞\infty∞\infty ∞\infty ∞\infty∞\infty ∞\infty ∞\infty
Diabetes14 16 3728 28 286 7 97 7 880 80 80
Breast Cancer7 7 736 50 667 13 136 6 7∞\infty ∞\infty ∞\infty
Banknote3 3 348 50 549 9 115 5 632 32 32
Table 2: Model complexity comparison of methods across benchmark datasets, for three normalized test-risk reduction targets, based on cross-validation-selected hyper-parameters. For each target, the first ensemble with the smallest complexity that hits the target is selected. Three numbers are reported for each experiment, representing the median (center), lower (left), and upper (right) bounds of the 92% confidence interval.
 Normalized Train Risks
DatasetTGBNRERFObTrLLTBEBM
Iris0.20 ±\pm 0.090.45 ±\pm 0.050.16 ±\pm 0.100.09 ±\pm 0.050.50 ±\pm 0.07
Liver0.70 ±\pm 0.060.83 ±\pm 0.000.70 ±\pm 0.040.78 ±\pm 0.040.83 ±\pm 0.00
Diabetes0.45 ±\pm 0.050.46 ±\pm 0.020.46 ±\pm 0.020.47 ±\pm 0.030.53 ±\pm 0.00
Breast Cancer0.14 ±\pm 0.040.18 ±\pm 0.030.04 ±\pm 0.010.08 ±\pm 0.02-
Banknote0.22 ±\pm 0.100.31 ±\pm 0.020.01 ±\pm 0.000.01 ±\pm 0.010.35 ±\pm 0.06
Table 3: Normalized risk comparison of methods across benchmark datasets, averaged over complexities between 1 to 100 based on cross-validation-selected hyper-parameters. For cases where a method does not achieve a valid solution within this complexity budget, (–) is reported.
Datasetdn ′TGBNRERFObTrLLTBEBM
Iris*41500.040.080.040.087.15
Liver*6345-----
Diabetes104420.270.111.710.250.22
Breast Cancer*305690.440.1911.090.45-
Banknote*413720.160.520.160.270.36
Red Wine1115992.320.145.251.710.26
Table 4: Median computation time (in seconds) to achieve 25% risk reduction (see Table 2 ) with dataset size n′n^{\prime} , dimension dd , and task type (classification marked (*)); dash indicates that method does not achieve target risk reduction.
Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Traditional Gradient Boosting
-0.28ifTrue
+1.28if( ave_occup ≤\leq 3.42) AND ( med_income ≥\geq 5.11)
-0.73ifave_rooms ≥\geq 4.3 AND med_income ≤\leq 2.35
+1.12if( ave_occup ≤\leq 2.34) AND ( hs_age ≥\geq 17) AND ( latitude ≤\leq 37.8) AND ( med_income ≥\geq 3.14)
+0.72if( ave_occup ≤\leq 2.98) AND ( hs_age ≥\geq 25) AND ( longitude ≤\leq -118) AND ( med_income ≥\geq 3.9)
-0.49if( latitude ≥\geq 37.8) AND ( longitude ≥\geq -122)
Appendix
Table 5: Rules generated by different methods on the California housing price dataset. Each ensemble corresponds to the smallest that achieves at least a 50% reduction in normalized test risk.
 25% error rate reduction 
DatasetTGBNRERFObTrLLTBEBMBRS
Iris8 8 810 13 5011 18 258 8 940 40 4030 30 30
Liver7 9 18∞\infty ∞\infty ∞\infty8 9 115 7 836 36 3636 42 48
Breast Cancer7 7 736 50 667 13 136 6 7∞\infty ∞\infty ∞\infty57 63 69
Banknote3 3 348 50 549 9 115 5 632 32 3236 42 45
Magic3 10 14∞\infty ∞\infty ∞\infty4 5 55 6 680 80 806 6 6
Appendix
Table 6: Model complexity comparison methods across benchmark classification datasets, considering three test error rate reduction (0/1 loss) targets on test normalized error rate based on cross-validation-selected hyper-parameters. For each target, the first ensemble with the smallest complexity that hits the target is selected. Three numbers are reported for each experiment, representing the median (center), lower (left), and upper (right) bounds of the 92% confidence interval.
Figure 5: Normalized error rate ( R01(c)/R01(0)\mathcal{R}_{01}(c)/\mathcal{R}_{01}(0) ) vs complexity trade-offs by different methods including Bayesian Rule Set (BRS). For each method, ensembles with increasing numbers of rules are extracted, and the mean error rate and mean model complexity are reported for each rule count, up to the maximum number of rules corresponding to a model complexity of 100. Error bars represent 95% CI.
 Normalized Train Error Rates
DatasetTGBNRERFObTrLLTBEBMBRS
Iris0.14 ±\pm 0.110.46 ±\pm 0.060.11 ±\pm 0.080.05 ±\pm 0.040.47 ±\pm 0.080.03 ±\pm 0.01
Liver0.41 ±\pm 0.060.42 ±\pm 0.040.36 ±\pm 0.020.45 ±\pm 0.040.52 ±\pm 0.000.34 ±\pm 0.09
Breast Cancer0.07 ±\pm 0.030.09 ±\pm 0.010.01 ±\pm 0.000.03 ±\pm 0.01-0.24 ±\pm 0.05
Banknote0.13 ±\pm 0.060.22 ±\pm 0.020.00 ±\pm 0.000.00 ±\pm 0.000.21 ±\pm 0.030.37 ±\pm 0.06
Magic0.57 ±\pm 0.060.49 ±\pm 0.000.54 ±\pm 0.020.49 ±\pm 0.030.60 ±\pm 0.000.69 ±\pm 0.01
Appendix
Table 7: Normalized Error rate comparison of methods across benchmark classification datasets, averaged over complexities between 1 to 100 based on cross-validation-selected hyper-parameters. For cases where a method does not achieve a valid solution within this complexity budget, (–) is reported.
 Normalized Train Error Rate
DatasetTGBNRERFObTrLLTBEBMBRS
Iris0.02 0.04 0.060.52 0.53 0.670.02 0.02 0.050 0.02 0.050.09 0.13 0.150.02 0.04 0.05
Liver0.37 0.46 0.491 1 10.34 0.36 0.410.4 0.45 0.470.53 0.54 0.570.5 0.56 0.57
Breast Cancer0.07 0.08 0.10.11 0.15 10.01 0.01 0.010.02 0.02 0.031 1 11 1 1
Banknote0.08 0.09 0.120.21 0.31 10 0 00 0 00.15 0.16 0.180.17 0.4 0.46
Magic0.54 0.55 0.571 1 10.54 0.57 0.570.47 0.47 0.491 1 10.68 0.69 0.71
Appendix
Table 8: Normalized error rate comparison of methods across benchmark datasets for a target model complexity of 5050 , based on cross-validation-selected hyper-parameters. Three numbers are reported for each experiment, representing the median (center), lower (left), and upper (right) bounds of the 92% confidence interval.
Figure 6: Risk vs complexity trade-offs by different methods for red wine , liver , banknote , voice , Friedman1 , Friedman2 datasets based on cross-validation-selected hyper-parameters, continuing Figure 4 . For each method, ensembles with increasing numbers of rules are extracted, and the mean normalized risk and mean model complexity are reported over 15 repetitions for each rule count, up to the maximum number of rules corresponding to a model complexity of 100. Error bars represent 95% CI.
 Normalized Train Risk
DatasetTGBNRERFObTrLLTBEBM
Iris0.09 0.1 0.120.55 0.57 0.590.06 0.08 0.10.04 0.07 0.070.18 0.2 0.25
Liver0.7 0.71 0.731 1 10.69 0.72 0.750.76 0.77 0.80.85 0.88 0.89
Diabetes0.46 0.48 0.50.48 0.5 0.510.43 0.45 0.470.44 0.44 0.471 1 1
Breast Cancer0.12 0.13 0.140.18 0.27 10.03 0.03 0.040.05 0.07 0.081 1 1
Banknote0.13 0.15 0.170.28 0.39 10 0 00 0 00.22 0.23 0.24
Appendix
Table 9: Normalized risk comparison of methods across benchmark datasets for a target model complexity of 5050 , based on cross-validation-selected hyper-parameters. Three numbers are reported for each experiment, representing the median (center), lower (left), and upper (right) bounds of the 92% confidence interval.
 25% risk reduction
DatasetTGBNRERFObTrLLTBEBM
Iris6 8 810 10 1315 21 266 7 740 40 40
Liver∞\infty ∞\infty ∞\infty∞\infty ∞\infty ∞\infty∞\infty ∞\infty ∞\infty∞\infty ∞\infty ∞\infty∞\infty ∞\infty ∞\infty
Diabetes14 16 3128 28 286 7 94 4 480 80 80
Breast Cancer7 7 736 50 667 7 135 5 5∞\infty ∞\infty ∞\infty
Banknote3 3 348 50 549 9 115 5 532 32 32
Appendix
Table 10: Model complexity comparison of methods across benchmark datasets, considering three test risk reduction targets on normalized test risk based on oracle-selected hyper-parameters. For each target, the first ensemble with the smallest complexity that hits the target is selected. Three numbers are reported for each experiment, representing the median (center), lower (left), and upper (right) bounds of the 92% confidence interval over 15 repetitions.
 Train Risks
DatasetTGBNRERFObTrLLTBEBM
Iris0.25 ±\pm 0.090.45 ±\pm 0.050.19 ±\pm 0.100.08 ±\pm 0.020.51 ±\pm 0.06
Liver0.77 ±\pm 0.040.83 ±\pm 0.000.70 ±\pm 0.030.79 ±\pm 0.030.84 ±\pm 0.00
Diabetes0.45 ±\pm 0.050.46 ±\pm 0.020.46 ±\pm 0.020.48 ±\pm 0.030.53 ±\pm 0.00
Breast Cancer0.18 ±\pm 0.040.18 ±\pm 0.030.06 ±\pm 0.010.09 ±\pm 0.02-
Banknote0.23 ±\pm 0.100.31 ±\pm 0.020.01 ±\pm 0.000.01 ±\pm 0.010.35 ±\pm 0.06
Appendix
Table 11: Normalized risk comparison of methods across benchmark datasets, averaged over complexities between 1 to 100 based on oracle-selected hyper-parameters. For cases where a method does not achieve a valid solution within this complexity budget, (–) is reported.
Figure 7: Risk vs complexity trade-offs by different methods for adult , magic , housing price , Friedman3 , used car price , iris , diabetes , breast cancer datasets based on oracle-selected hyper-parameters. For each method, ensembles with increasing numbers of rules are extracted, and the mean normalized risk and mean model complexity are reported over 15 repetitions for each rule count, up to the maximum number of rules corresponding to a model complexity of 100. Error bars represent 95% CI.
Figure 8: Risk vs complexity trade-offs by different methods for red wine , liver , banknote , voice , Friedman1 , Friedman2 datasets based on oracle-selected hyper-parameters, continuing Figure 7 . For each method, ensembles with increasing numbers of rules are extracted, and the mean normalized risk and mean model complexity are reported over 15 repetitions for each rule count, up to the maximum number of rules corresponding to a model complexity of 100. Error bars represent 95% CI.
Figure 9: Empirical computational complexity of the binary search procedure across 14 benchmark datasets with original sample sizes. The x-axis denotes the target sparsity level (up to 10), and the y-axis shows the average number of binary search iterations required to identify the λl1\lambda_{l1} value yielding the desired sparsity. Error bars indicate 95% confidence intervals over 10 repetitions.

Explore similar work

CardsList

  1. TT-Sparse: Learning Sparse Rule Models with Differentiable Truth Tables

    Mar 8, 2026Hans Farrell Soegeng, Sarthak Ketanbhai Modi, Thomas PeyrinBoolean Function LearningInterpretable ML

    School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore.

  2. Learning Auditable Classifier Models: Source-Disjoint Tree Ensembles

    Aug 16, 2026Srikumar KrishnamoorthyInterpretable MLEnsemble Learning

    Information Systems Area, Indian Institute of Management Ahmedabad, India

  3. SR4-Fit: A Unified Interpretable Rule-Based Machine Learning Framework for Informative and Trustworthy Decision-Making

    Sep 27, 2026Shyam Sundar Murali Krishnan, Dean Frederick HougenInterpretable ML

    School of Computer Science, University of Oklahoma, Norman, Oklahoma, USA