Probabilistic Truly Unordered Rule Sets

Lincen Yang; Matthijs van Leeuwen

cs.LGJan 18, 2024

Probabilistic Truly Unordered Rule Sets

Authors: Lincen Yang, Matthijs van Leeuwen

Organizations: LIACS, Leiden University Niels Bohrweg 1, 2333 CA, Leiden, The Netherlands

Abstract

Rule set learning has recently been frequently revisited because of its interpretability. Existing methods have several shortcomings though. First, most existing methods impose orders among rules, either explicitly or implicitly, which makes the models less comprehensible. Second, due to the difficulty of handling conflicts caused by overlaps (i.e., instances covered by multiple rules), existing methods often do not consider probabilistic rules. Third, learning classification rules for multi-class target is understudied, as most existing methods focus on binary classification or multi-class classification via the one-versus-rest" approach. To address these shortcomings, we propose TURS, for Truly Unordered Rule Sets. To resolve conflicts caused by overlapping rules, we propose a novel model that exploits the probabilistic properties of our rule sets, with the intuition of only allowing rules to overlap if they have similar probabilistic outputs. We next formalize the problem of learning a TURS model based on the MDL principle and develop a carefully designed heuristic algorithm. We benchmark against a wide range of rule-based methods and demonstrate that our method learns rule sets that have lower model complexity and highly competitive predictive performance. In addition, we empirically show that rules in our model are empirically independent" and hence truly unordered.

Figures & tables

Algorithm	Model Type	Strategy	Prob.	Overlap Handling
CBA ( Liu et al., 1998 )	ordered rule list	div. and conq.	$\checkmark$	explicit order
CN2-ordered ( Clark and Niblett, 1989 )	ordered rule list	div. and conq.	$\checkmark$	explicit order
PART ( Frank and Witten, 1998 )	ordered rule list	div. and conq.	$\checkmark$	explicit order
CLASSY ( Proença and van Leeuwen, 2020 )	ordered rule list	div. and conq.	$\checkmark$	explicit order
RIPPER ( Cohen, 1995 )	ordered list of rule sets	div. and conq.	$\times$	explicit order
C4.5Rules ( Quinlan, 2014 )	ordered list of rule sets	one-vs-rest	$\times$	explicit order

Table 1: Comparison of rule-learning algorithms. Abbreviations: div. and conq. (divide and conquer), asso. rule mining (association rule mining); Prob. indicates whether the method produces probabilistic output; impl. order denotes implicit ordering, with the tie-breaking criterion in parentheses.

Panel of Figure 2 — Figure 2: Illustrative example: rule set $M=\{S_{1},S_{2}\}$ over $\mathcal{X}=[0,1]^{2}$ , with $S_{1}:X_{1}<0.6\rightarrow P_{\boldsymbol{\beta}_{1}}(Y)$ (region $\Gamma_{1}$ , left of the vertical line) and $S_{2}:X_{2}<0.5\rightarrow P_{\boldsymbol{\beta}_{2}}(Y)$ (region $\Gamma_{2}$ , below the horizontal line). Each instance $x$ is modeled by the distribution conditioned on exactly one region (shaded): (a) the whole region of the covering rule when $x$ is covered by a single rule, (b) the union of the covering rules’ regions when $x$ lies in an overlap, and (c) the else region $\Gamma_{0}$ when $x$ is covered by no rule.

Data	# rows	# columns	# classes	max. class prob.	min. class prob.
aloi	49534	28	2	0.970	0.030
backdoor	95329	197	2	0.976	0.024
backnote	1372	5	2	0.555	0.445
chess	3196	37	2	0.522	0.478
diabetes	768	9	2	0.651	0.349
glass-2	214	8	2	0.958	0.042

Table 2: Datasets for binary (top) and multi-class classification (bottom), publicly available on the UCI repository ( Dua and Graff, 2017 ) and the ADBench Python package ( Han et al., 2022 ) ; datasets from the latter are marked in Italic . We use the maximum and minimum of the marginal class probabilities to indicate the degree of class imbalance.

Data	BRS	C45	CART	CLASSY	Ripper	CN2	DRS	IDS	TURS (diff to best)
aloi	0.519	0.398	0.621	0.654	0.485	0.569	—	0.509	0.617 (-0.037)
backdoor	0.917	0.990	0.979	0.996	0.976	0.997	—	—	0.997
backnote	0.957	0.987	0.983	0.990	0.982	0.993	0.988	0.776	0.983 (-0.01)
chess	0.957	0.998	0.995	0.992	0.995	0.532	0.809	0.677	0.990 (-0.008)
diabetes	0.725	0.710	0.667	0.737	0.641	0.709	0.727	0.594	0.748
glass-2	0.676	0.890	0.790	0.730	0.793	0.941	0.926	0.912	0.949

Table 3: Average ROC-AUC scores obtained using cross-validation. BRS can only be applied to binary datasets, and DRS and IDS fail to get results on a few datasets, denoted as “—” in the table. The best ROC-AUC for each dataset is shown in bold, and the difference between the best ROC-AUC for each dataset and the ROC-AUC of TURS for the same dataset is shown in parentheses.

Figure 3: For each algorithm, we calculate for every individual dataset the difference between its ROC-AUC score and the best ROC-AUC score. The differences to the best ROC-AUC scores for each algorithm are illustrated by a box-plot.

Figure 4: The weighted average of the differences between the class probability estimates of each individual rule on the training and test sets, shown as an empirical cumulative distribution function (CDF). The weights are defined by the coverage of each rule on the training set. The zoomed panel emphasizes the range $[0,0.5]$ to improve visibility where most differences are concentrated.

Data	BRS	C45	CART	CLASSY	RIPPER	CN2	DRS	IDS	TURS
aloi	3	2659.1 ∗	26952.8	52.3	26.2 ∗	2121	—	14 ∗	41.7
backdoor	13	701.5	2460.5	72.6	101.5	264.6	—	—	50.7
backnote	35.8	79.6	116.7	22.7	22.3	42.7	54	13.2 ∗	16.2
chess	19.2	250.2	340.5	33	57.9	298.7 ∗	54.2 ∗	14.5 ∗	43.7
diabetes	15.6	107.6	700.5	5	6.6 ∗	170	82.5	13.2 ∗	6
glass-2	10.8 ∗	19.7	6.7 ∗	3 ∗	5.9 ∗	3.9	37.2	15.5	1

Table 4: Total number of literals in the rule set, rule list, or decision tree, averaged over the five cross-validation folds. Entries marked with ∗ indicate models whose ROC-AUC is more than

0.1

lower than that of TURS on the same dataset; bold entries denote the smallest total number of literals among the remaining models.

Data	BRS	C45	CART	CLASSY	RIPPER	CN2	DRS	IDS	TURS
aloi	1	157.2 ∗	1056	12.4	4.2 ∗	468.8	—	7 ∗	10
backdoor	4.6	61.2	130.4	19	19	76.6	—	—	17.6
backnote	12	14.8	23.4	8	6.4	13.6	20.4	7 ∗	7
chess	6.8	28.6	41.2	9.4	14.2	83.4 ∗	12 ∗	7.2 ∗	13.4
diabetes	5.2	18	87.2	2.6	2 ∗	31.2	21.4	6.6 ∗	3.4
glass-2	3.6 ∗	5.2	3.6 ∗	1 ∗	1.8 ∗	2.8	12.6	8.2	1

Table 5: The number of rules in the learned models. For decision trees, each root-to-leaf path is treated as a rule. Entries marked with ∗ indicate models whose ROC-AUC is more than

0.1

lower than that of TURS on the same dataset; bold entries denote the smallest number of rules among the remaining models.

Data	BRS	C45	CART	CLASSY	RIPPER	CN2	DRS	IDS	TURS
aloi	3	16.9 ∗	25.5	4.2	6.2 ∗	4.5	—	2 ∗	4.2
backdoor	2.8	11.5	18.9	3.8	5.3	3.5	—	—	2.9
backnote	3	5.4	5	2.8	3.5	3.1	2.6	1.9 ∗	2.3
chess	2.8	8.7	8.3	3.5	4.1	3.6 ∗	4.5 ∗	2 ∗	3.3
diabetes	3	6	8	1.9	3.3 ∗	5.4	3.9	2 ∗	1.8
glass-2	3 ∗	3.8	1.9 ∗	3 ∗	3.3 ∗	1.4	3	1.9	1

Table 6: Average rule length in the learned models. For decision trees, rule length is computed over root-to-leaf paths. Entries marked with ∗ indicate models whose ROC-AUC is more than

0.1

lower than that of TURS on the same dataset; bold entries denote the smallest average rule length among the remaining models.

Figure 5: Histograms of the maximum pairwise

\ell_{1}

-distance between probability estimates of overlapping rules, computed on the test set of a single cross-validation fold.

Figure 6: ROC-AUC obtained by TURS and CN2 versus ROC-AUC obtained using random picking for overlaps. The annotated numbers denote the fractions of instances covered by the overlaps.

Figure 7: Average runtime (in seconds) for five rule set methods and CART across datasets. The y-axis is shown on a $\log_{10}(\cdot)$ scale. Datasets on the x-axis are ordered by the number of rows $\times$ (number of columns + number of classes), from smallest to largest.

Figure 8: Ablation study comparing the base TURS model with the learning-speed-score ablation. Bars show differences between the base and ablated models across datasets. Positive values indicate higher values for the base model (higher ROC-AUC, higher model complexity). Note that the three plots use different y-axis ranges, and that the ROC-AUC difference plot does not show the full ROC-AUC range

(0,1)

Figure 9: Ablation study comparing the base TURS model with variants. Bars show differences between the base and ablated models across datasets. Positive values indicate higher values for the base model (higher ROC-AUC, higher model complexity). Note that the plots use different y-axis ranges, and that the ROC-AUC difference plot does not show the full ROC-AUC range

(0,1)

Local testing	# rules	rule length	ROC-AUC	MDL-based score	train/test prob. diff.
No	12.48( $\pm$ 1.56)	5.597( $\pm$ 0.42)	0.722( $\pm$ 0.02)	2191.189( $\pm$ 65.91)	0.049( $\pm$ 0.01)
Yes	1( $\pm$ 0)	1( $\pm$ 0)	0.724( $\pm$ 0.01)	2050.087( $\pm$ 68.88)	0.007( $\pm$ 0)

Table 7: Results of ablation study on local testing. We report the mean (

\pm

standard deviation) over

100

repetitions.

Figure 10: The process of adding rules to the rule set, with and without the local testing heuristic, using the first dataset among the 100 simulated datasets. Each point represents the status after a single rule is added, with the x-axis representing the coverage of the (potentially incomplete) rule set after adding this rule, and the y-axis representing the MDL-based score.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Aspect	Previous work ( Yang and van Leeuwen, 2022 )	This paper
Probabilistic model	1) No probabilistic model formally defined; 2) intuitive probabilistic interpretation; 3) overlaps motivated by uncertainty and exceptionalness	Formally defined probabilistic TURS model without rule ordering with theoretical justification
Overlap handling	Separate treatment of nested and non-nested overlaps	Unified overlap modeling framework
Model selection	MDL-based model selection criterion but the code length is excluded to achieve better practical performance	MDL-based criterion with a principled encoding with the code length of the model included
Search heuristic	FOIL-like MDL compression gain	Learning speed score (MDL reduction per additionally covered instance)
Rule learning algorithm	Diverse beam search; surrogate CART-based evaluation for uncovered instances	Redesigned beam search with MDL-based local testing and patience-diversified beam strategy
Experimental evaluation	Predictive performance and model complexity on 10 datasets	1) Large-scale predictive study (31 datasets); 2) empirical overlap consistency; 3) interpretability with both model complexity and the generalizability of individual rules’ outputs; 4) efficiency (runtimes); 5) large-scale ablation studies

Appendix

Table 8: Summary of differences between the previous and present work.

Explore similar work

Evidential Rule Learning for Interpretable Classification with Abstention
Aug 6, 2026Javier Fumanal-Idocin, Javier Andreu-PerezEvidential Uncertainty Interpretability
School of Computer Science and Electronic Engineering University of Essex, Colchester CO4 3SQ, UK
Learning High Coverage Discriminative Parsimonious Rulesets
Jun 12, 2026Mariamma Antony, Raman Sankaran, Chiranjib Bhattacharyya +1Interpretability Discriminative
Indian Institute of Science, CV Raman Rd, Bengaluru, Karnataka 560012 · Compass, Bengaluru, Karnataka 560012
TT-Sparse: Learning Sparse Rule Models with Differentiable Truth Tables
Mar 8, 2026Hans Farrell Soegeng, Sarthak Ketanbhai Modi, Thomas PeyrinInterpretability Decision Trees
School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore.

Aug 6, 2026, cs.LGJ/K move · Enter open · S save

Evidential Rule Learning for Interpretable Classification with Abstention

Javier Fumanal-Idocin, Javier Andreu-Perez

School of Computer Science and Electronic Engineering University of Essex, Colchester CO4 3SQ, UK

Evidential Uncertainty Interpretability Fuzzy Abstention

Open paper AskPDF arXiv

Interpretable classification often requires more than accurate predictions for real-life deployment: models should be transparent about the evidence behind their decisions and abstain when they cannot decide reliably. We introduce Fast Evidential Rule Learning (FERL), a method that learns interpretable, accurate fuzzy rule models whose outputs are evidential. Unlike post-hoc calibration, FERL's belief, plausibility, and abstention capabilities arise directly from the fuzzy memberships in a single deterministic pass, with no auxiliary head, held-out set, or repeated inference. Our theoretical analysis further shows that FERL is Lipschitz stable, which means that its evidential outputs vary smoothly with the input. Against state-of-the-art rule learners, FERL is statistically significantly more accurate across a 30 tabular-dataset benchmark (

+2.6\%

average accuracy over the second best). Its native set predictions attain the best utility-discounted accuracy among credal classifiers (

u_{65}/u_{80}=0.80/0.83

vs.\

0.79/0.80

for the naive credal classifier), at higher set coverage (

0.92

vs.\

\le0.82

). FERL also matches dedicated out-of-distribution detectors on tabular near-OOD detection (

77.7

vs.\

77.4

AUROC for the strongest baseline). Under detector-class-disjoint concept-bottleneck evaluation, its it is within

2.3

AUROC points of the strongest dedicated detector on both CUB and AwA2, while attaining the best AwA2 AUPR-Out (

68.3

) and novel-class rejection (

57.2

), while being able to name which attributes are anomalous.

Abstract

Explore similar work

Evidential Rule Learning for Interpretable Classification with Abstention

Learning High Coverage Discriminative Parsimonious Rulesets

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