Evidential Rule Learning for Interpretable Classification with Abstention

The paper introduces Fast Evidential Rule Learning (FERL), a fuzzy rule-tree learner designed to address a core problem in high-stakes machine learning deployment: Interpretable classification often requires more accurate predictions for real-life deployment: models should be transparent about the evidence behind their decisions and abstain when they cannot decide reliably.

The authors argue that interpretability alone is insufficient for high-stakes domains: a model must also report realistic, reliable confidence in each decision. They identify problems with existing approaches:

• Post-hoc explainers like LIME, SHAP, and Grad-CAM explain an already existing predictor and can be unfaithful to its actual decision and might give a poor estimation of the global reasoning process of the explained model.

• Post-hoc calibration techniques tend to degrade under distribution shift.

• Deterministic uncertainty methods (DUMs) need spectral fine-tuning of the neural architecture to avoid feature collapse, only reliably detect geometric novelty, and tend to assign deceptively low uncertainty to a near-OOD input that overlaps the training manifold. Besides, they report a scalar with no symbolic account of why a case is doubtful.

FERL is claimed to be to our knowledge, the first model that is at once an interpretable rule learner, a credal classifier with abstention and an OOD detector, in a single deterministic pass. 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.

FERL grows a fuzzy classification tree where each internal split pairs a feature with a fuzzy set of membership µ(·) ∈ [0, 1], and memberships multiply along a root-to-o path into a firing strength ϕo(x) ∈ [0, 1]. Every node stores a consequent class distribution estimated from soft-weighted samples.

Two gain functions are supported: the Complete Classification Index (CCI), which measures the gain in correctly classified soft mass obtained by replacing a node with a candidate split (preferred for small tree variants), and weighted Gini impurity (WGI) (preferred for deeper variants).

For deeper variants, split learning uses bootstrapping: we repeatedly bootstrap and find the standard Gini-optimal cut in each resample. The resulting empirical distribution of cut locations determines the following fuzzy partition:

µθ,h(xf) = min 1, max 0, (θ + h − xf)/(2h)

where θ is the median bootstrap cut location and h = γ·MAD is a robust spread measure. The condition is thus fully active for xf ≤ θ − h, off for xf ≥ θ + h, and behaves linearly across the interval [θ − h, θ + h].

To handle out-of-distribution points, FERL "soft-bound[s] the support of each fuzzy membership function to the feature range the node actually observed in training, decaying it to zero beyond a small margin ε. This makes out-of-distribution points that fall outside the observed range on some feature have their leaf activations collapse towards zero, which raises the model’s ignorance."

For near-OOD detection (novel classes overlapping the training manifold), we model the behaviour of unsplit features in every node: each of them fits a diagonal Gaussian weighted by the fuzzy memberships to its root-to-node path over the features absent from it. Since the firing φo depends on x only through the tested features, this is precisely a model of the unsplit features given the split ones: p(x free(o) φo) ≈ N(µo, diag(σo2)). At test time, the firing-weighted average of the diagonal Mahalanobis distance per node gives feature-level anomaly scores, allowing FERL to detect which attributes are anomalous at any path.

Each activated node becomes a Dempster–Shafer mass function: the node places mass φo(x) po(c) on class c and residual mass 1 − φo(x) on the whole frame Θ. A node that fires weakly contributes mostly ignorance, and a node that fires strongly commits to its class distribution.

The analytical form: before normalisation, the combined mass has only these non-zero terms:

• m̃(Θ) = Π(1 − φo)

• m̃(c) = Π(1 − φo + φo po(c)) − Π(1 − φo)

After normalisation, Bel(c) = m(c) and Pl(c) = m(c) + m(Θ), and interval dominance simplifies to S(x) = c: m(c) ≥ max j m(j) − m(Θ). This credal set prediction chooses classes whose mass lies within the residual ignorance of the best-supported class, and the set prediction expands as the model lacks evidence for the decision.

The paper identifies a key design choice: "In a compact tree... the few internal nodes along a path carry complementary evidence. In fact, we find that internal nodes can be used to regularise the overconfident estimations of the leaves. In a deep tree, the nodes are numerous and strongly correlated, and combining all of them drives ignorance to zero. So, in that case, we only combine the leaves. The paper shows analytically that adding a non-vacuous source cannot increase residual ignorance," explaining why all-node combination in deep trees collapses ignorance.

The paper proves several properties:

Proposition 1 (Lipschitz stability): "The unnormalised evidential masses m̃(c) and m̃(Θ) are Lipschitz in x with constant O(KDλ). Consequently, on the region Ωτ = x: Z(x) ≥ τ where the normaliser is bounded below, the pignistic output is Lipschitz, ‖BetP(·x) − BetP(·x′)‖1 ≤ (κKDλ/τ)‖x − x′‖∞."

Guaranteed Gini improvement: "For every complementary fuzzy split with non-empty children, G(p) − αG(pL) − (1−α)G(pR) = α(1−α)‖pL − pR‖22 ≥ 0. The decrease is strict exactly when both children have positive weight and their class distributions differ."

Routing-mass conservation: If every γ equals one for sample x, then the leaf firings of a finite binary learned tree form a partition of unity: Σ φl(x) = 1. When support gates reduce mass, there is a loss of mass in the routing decomposable node-by-node, each summand names the node and split feature responsible for the loss of mass, making geometric novelty attributable to features.

Local robustness certificate: "On any region where the support gates remain one, ‖PT(x) − PT(x′)‖1 ≤ LT‖x − x′‖∞... the predicted class is unchanged for every ‖x − x′‖∞ < Δ(x)/(2LT)."

FERL is evaluated in three configurations: compact (max 15 rules, precomputed fuzzy partitions with low/medium/high semantics), medium (max 50 rules, bootstrapped partitions), and deep (max 200 rules, leaves-only combination).

Key results from Table 1:

• FERL-deep reaches 83.23% accuracy — the best among all tree/rule-based methods, statistically significantly better than every other rule learner (all p < 0.01 in Holm-corrected Wilcoxon tests), and statistically indistinguishable only from logistic regression.

• FERL-compact achieves 77.77% with only 6 rules, competitive with C4.5 (78.19%) at over 40× smaller size.

• FERL-medium reaches 79.21% with 43 rules, matching or beating most modern rule learners.

• Selective-risk AURC: FERL-deep achieves 9.21, the best among interpretable models, even beating logistic regression (10.59).

The paper notes: It is also remarkable that modern rule learners struggle to compete with CART. NeuRules is the strongest one, matching FERL-medium’s accuracy (79.3 vs. 79.2) with a smaller rule count but at higher selective risk.

Efficiency: FERL-deep fits in 0.26 s: among rule learners only CART (0.002 s) and FIGS (0.17 s) fit faster, while NeuRules (4.8 s), SamRuLe (12.9 s), FUCS (140.4 s) and RL-Net (146.8 s) are one to three orders of magnitude slower. Inference: FERL scores a fold in 1.5 ms against 16.8 ms for FURIA and 744 ms for FUCS.

FERL-deep obtains the highest utility-discounted accuracy at both reference levels: u65 = 0.795, u80 = 0.827 (vs. 0.79/0.80 for NCC). FERL-deep achieves 0.92 set coverage with mean size 1.70, whereas MLP-Conformal reaches 0.952 coverage but with the largest prediction sets (2.17). NCC produces the smallest sets (1.11) but this determinism reflects an overconfident bias, as its performance is lower than most rule-learners. The paper concludes: FERL is capable of very good coverage (close to conformal) while producing significantly smaller sets, without falling into the overconfident estimates of NCC and CDT.

In leave-one-class-out experiments on tabular datasets: "FERL-deep’s OOD residual signal is marginally better than the strongest dedicated competitor (77.7 vs. 77.4 for kNN distance) and clearly ahead of Mahalanobis and Isolation Forest, and... it does so with the lowest standard deviation across datasets of any method, i.e. it is the most consistent detector of the comparison. At a 95% retained-class acceptance threshold, FERL-deep rejects the largest fraction of novel-class inputs (36.5%), ahead of every dedicated detector."

FERL is used as a classification head over concept vectors from CBMs on CUB and AwA2. Key findings:

• Per-concept calibration is particularly important on CUB: FERL-deep improves from 77.67% to 86.28% on CUB-20 and from 59.38% to 65.18% on CUB-200.

• With calibrated concepts it slightly exceeds CART on both tasks, making it the strongest tree-based CBM head in this comparison.

• Standard LR remains strongest, but its advantage disappears when limiting the number of concepts used to the same as FERL, showing that LR's edge comes from using many more concepts per decision.

In detector-class-disjoint open-world detection: "On CUB-200, FERL reaches 68.2 AUROC and 31.0 AUPR-Out, within 2.3 and 2.4 points, respectively, of the strongest dedicated result. On AwA2, it reaches 86.2 AUROC, within 2.0 points of kNN, while obtaining the best AUPR-Out (68.3) and the highest unseen-class rejection at the retained-class validation threshold (57.2%)."

• Evidence sources: All-node Dempster combination drives mean ignorance to 0.07% and produces 99.88% singleton sets; leaves-only raises ignorance to 22.93% and set coverage to 92.31%, while increasing accuracy from 80.62% to 83.18%.

• Cautious vs. Dempster rule: The cautious rule (Denœux, 2008) is more conservative still, raising coverage to 96.78% and ignorance to 37.19%, but accuracy falls by 13.60 points, and both AURC and ECE worsen.

• Bounded support: Enabling the gate changes accuracy from 82.00% to 81.99% in-distribution, but firing-based OOD AUROC rises from 47.03% to 99.29% and ignorance-based AUROC from 23.19% to 98.62%.

• Split criterion: Weighted Gini (83.23%) beats CCI (82.52%) for the deep learned-threshold variant.

• Coverage under covariate shift: Under graded perturbation at k = 1, global conformal coverage falls to 55.0% while its mean set size remains nearly fixed at 1.09, whereas FERL retains 77.3% coverage by widening its mean set from 1.35 to 4.10 classes.

The paper concludes: "We presented FERL, a fast and scalable fuzzy rule-learning method in which Dempster–Shafer evidence is the product of the fuzzy memberships that define the rules, and where each node split is computed using bootstrapped samples that create robust fuzzy partitions. FERL provides a high-performance interpretable classifier with set-valued prediction, abstention, and OOD detection... In a 30-dataset tabular benchmark, the medium-sized FERL tree is competitive with classical and recent rule learners while using fewer rules than most of them, and the deep FERL tree surpasses every other single rule learner with statistical significance. Its native residual also matches or closely approaches dedicated OOD detectors without fitting a separate detector. Within a CBM, FERL remains competitive as a classification head and carries the same OOD mechanism into a detector-class-disjoint open-world setting... These results show that a single concept-level FERL head can provide auditable rules, evidential abstention, and attribute-level novelty diagnostics without an auxiliary uncertainty model."

Here are the concrete improvements you can make to AI systems based on this paper, and what the improved system can then do:

1. Replace post-hoc explainability with intrinsic, evidence-based reasoning.

• The improved system no longer relies on LIME/SHAP-style approximations that can be unfaithful. Instead, it learns transparent fuzzy rules (e.g., if sepal length is high and petal width is medium, then class Iris-versicolor).

• It can now show you the exact evidence behind every decision: which rules fired, how strongly, and which features contributed — in a single deterministic pass.

2. Equip the classifier with native, calibrated abstention and set-valued predictions.

• The system outputs not just a class, but a Dempster-Shafer belief, plausibility, and an explicit ignorance mass.

• When evidence is weak or conflicting, the system returns a set of plausible classes (via interval dominance) instead of a forced single label. As ignorance grows, the set widens — it says I don't know and says why, rather than producing overconfident point estimates.

• Add a predict-or-abstain mode: if the top class's mass is within the residual ignorance of the second-best class, the system abstains or returns both.

3. Give the classifier built-in out-of-distribution detection with no auxiliary model.

• The system soft-bounds the support of each fuzzy membership to observed training ranges, so an OOD point falling outside those ranges collapses leaf firing strengths and automatically raises ignorance.

• It detects near-OOD (novel classes overlapping the training manifold) by modeling unsplit features at each node as weighted diagonal Gaussians, then computing a firing-weighted Mahalanobis distance per path.

• It can report which specific attributes are anomalous for any flagged sample — attribute-level novelty diagnostics, not just a scalar OOD score. It achieves this at accuracy comparable to dedicated detectors (77.7 vs. 77.4 AUROC for kNN) with the lowest variance across datasets.

4. Certify local robustness for safety-critical deployment.

• The system provides a local robustness certificate: on regions where support gates are active, the predicted class is provably unchanged for any input perturbation smaller than Δ(x)/(2L T), with an explicit Lipschitz bound on the output.

• It also guarantees monotone Gini improvement at every split, preventing degenerate splits.

5. Maintain reliable confidence under distribution shift (better than conformal prediction).

• Under graded covariate shift, global conformal methods drop to 55.0% coverage while keeping set size nearly fixed (1.09); the improved system retains 77.3% coverage by adaptively widening its prediction set from mean size 1.35 to 4.10.

• This gives you a system whose uncertainty quantification degrades gracefully and honestly when the input distribution moves.

6. Gain the best of both worlds: interpretable rules with state-of-the-art accuracy.

• Use the deep variant (leaves-only evidence combination) to beat every other tree/rule learner on 30 tabular datasets (83.23% accuracy) with statistical significance, while still being fully interpretable.

• Use the compact variant (6 rules) to get within 0.4 points of C4.5 at 40× smaller model size — usable when humans must read and audit every rule.

7. Scale uncertainty-aware interpretability to large, high-throughput workloads.

• The improved system trains in 0.26 s and scores a fold in 1.5 ms — orders of magnitude faster than modern rule learners (e.g., 140–740 ms for FUCS/FURIA) — while providing evidential abstention and OOD detection for free.

• This makes it practical as an always-on screening layer in front of expensive deep models, or as a standalone classifier for edge/real-time systems.

8. Use it as a concept-level reasoning head over pretrained concept bottleneck models.

• Plug the system onto CBM concept vectors (CUB, AwA2): with per-concept calibration, accuracy jumps from 77.67% to 86.28% on CUB-20 and from 59.38% to 65.18% on CUB-200, beating CART and matching logistic regression when given the same concept count.

• The system then provides auditable concept-level rules, evidential abstention, and open-world novelty detection (detecting unseen classes at 86.2 AUROC on AwA2) in one unified model — no separate OOD detector needed.

9. Make evidence combination itself adaptive to model depth.

• The system solves the overconfidence collapse problem smartly: for compact trees, combine evidence from internal nodes (which carry complementary information and regularize leaf overconfidence); for deep trees, combine only the leaves (since correlated internal nodes drive ignorance to zero).

• The result: a single framework that stays well-calibrated whether you want 6 rules or 200 rules.

10. Improve selective prediction and resource allocation.

• Using its native residual as a risk score, the system achieves the best selective-risk AURC among interpretable models (9.21), beating even logistic regression (10.59).

• You can build a triage pipeline: high-belief samples are auto-classified, low-belief samples are routed to a human or a more expensive model — and the system tells you exactly why each sample was flagged.

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. 0.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.