EDRS: Explanations Using Defeasible Rule Sets

Introduction

Systems utilizing Machine Learning models are increasingly deployed across domains involving high-stakes decisions, where they replace, improve, or assist decisions traditionally made by humans. However, their predictions often rely on internal representations, weights, embeddings, and learned feature interactions that have no natural correspondence to human reasoning. Any decision-making system, not only those built on machine learning, faces an explainability problem when its decisions are used to justify consequential outcomes. Explainability is the property by which a model can produce details or reasons that make its functioning easy and clear to understand

Symbolic rule-based classifiers mitigate the problem of explainability by construction rather than reconstruction. They consist of explicit “IF-THEN” decision rules over meaningful features. In this project, we study Exception Closed Conjuctive Rule Sets, (ECCRS); it is built for rules learnt from data with exceptions and conflict, resolving them through a Most Specific Wins(MSW) operator. MSW states that when multiple rules apply from a given instance ("situation"), the rule which is strictly more specfic than the other determines the conclusion / prediction. The explainability of this classifier comes naturally as 1) A set of rules that applies in a given instance, 2) Rules that are strictly more specific than other, and overrides them 3) The prediction/conclusion from the surving rules.

ECCRS' inference method for dealing with exception and conclusion is clean and straighforward , producing human readable explanation. It does not, however establish that the resulting decision is semantically correct under a formal theory of reasoning with exceptions. This motivates checking ECCRS against such a theory: the KLM framework, a standard formal account of defeasible reasoning, where conclusions hold by default but may be withdrawn when more specific information applies, developed by Kraus, Lehmann and Magidor, . The framework offers several concrete methods for deciding what a set of default rules implies; we use the following ones: Rational Closure, Lexicographic Closure and System W.

Translate ECCRS rule sets into KLM knowledge bases.
Implement Rational Closure, Lexicographic Closure and System W.
Compare every prediction against the classifier, instance by instance.

Background

ECCRS: Exception-Closed Conjunctive Rule Sets

A classifier made of IF-THEN rules. When rules disagree, the most specific one wins, and the steps that pick the winner are the explanation.

The rules

Each rule is a pair $(B, \ell)$: a body $B$ of feature values, and a label $\ell$.

$r_1$: odour = none $\Rightarrow$ edible
$r_2$: odour = none $\land$ spore = green $\Rightarrow$ poisonous (exception to $r_1$)
$r_3$: odour = foul $\Rightarrow$ poisonous

How a prediction is made

1 Applicable rules

Keep every rule whose body the instance satisfies.

$$\mathcal{A}(F) = \{ (B, \ell) \in \mathcal{R} : F \models B \}$$

2 Inclusion-Maximal Applicable Rules

Drop any rule with a strictly more specific rival.

$$\mathcal{M}(F) = \{ (B, \ell) \in \mathcal{A}(F) : \nexists (C, \ell') \in \mathcal{A}(F),\ B \subset C \}$$

3 Most Specific Wins

Answer with their label, or abstain if nothing applies.

$$\mathrm{MSW}(F) = \begin{cases} \ell & \text{all of } \mathcal{M}(F) \text{ say } \ell \\ \bot & \mathcal{M}(F) = \emptyset \end{cases}$$

Strict exception closure guarantees $\mathcal{M}(F)$ never holds both labels, so step 3 never has to break a tie.

Defeasible reasoning (KLM)

Classical logic breaks on exceptions. Defeasible reasoning draws conclusions that hold typically, and drops them when more specific information turns up.

Why classical logic is not enough

$\text{bird} \rightarrow \text{flies}$
$\text{penguin} \rightarrow \text{bird}$
$\text{penguin} \rightarrow \neg\text{flies}$

Taken together, these say penguins cannot exist.

Typical statements

KLM writes $\alpha \dent \beta$ for "if $\alpha$, then typically $\beta$".

$\text{bird} \dent \text{flies}$ (birds typically fly)
$\text{penguin} \rightarrow \text{bird}$
$\text{penguin} \dent \neg\text{flies}$

Now penguins are simply an exception: birds that don't fly.

How a query is answered

Rank

Sort statements from general (rank 0) to specific. A statement moves up if its antecedent clashes with everything at its level.

$$\mathcal{E}_0 = \mathcal{K}, \qquad \mathcal{E}_{i+1} = \{ \alpha \dent \beta \in \mathcal{E}_i : \overrightarrow{\mathcal{E}_i} \models \neg\alpha \}$$

Drop

To ask $\alpha \dent \beta$, throw away the most general ranks until $\alpha$ is consistent with what is left.

$$\mathcal{K} \models \alpha \dent \beta \iff \overrightarrow{\mathcal{R}_{\geq i}} \models \alpha \rightarrow \beta$$

Three closures

They differ only in what they drop.

Rational Closure: whole ranks.
Lexicographic Closure: as few statements as possible from the clashing rank.
System W: compares worlds by the set of statements they break.

$\overrightarrow{X}$ reads each $\alpha \dent \beta$ in $X$ as $\alpha \rightarrow \beta$. $\mathcal{R}_{\geq i}$ is everything ranked $i$ or higher, where $i$ is the lowest rank at which $\alpha$ stops clashing.

From ECCRS to KLM

ECCRS decides by specificity. KLM decides by defeasible entailment. To compare the two on the same question, the rule set first has to become a knowledge base.

The translation

One atom, $m$, stands for the class: $m$ is label 1 and $\neg m$ is label 0. Each rule becomes one typical statement with the same body:

$$(B, 1) \mapsto B \dent m \qquad\qquad (B, 0) \mapsto B \dent \neg m$$ $$\mathcal{K}(\mathcal{R}) = \{ B \dent m : (B, 1) \in \mathcal{R} \} \cup \{ B \dent \neg m : (B, 0) \in \mathcal{R} \}$$

Using a single atom makes the two labels exact opposites, so "abstain" simply means neither $m$ nor $\neg m$ is entailed.

On the running example

$r_1$: odour = none $\Rightarrow$ edible becomes $\text{none} \dent m$
$r_2$: odour = none $\land$ spore = green $\Rightarrow$ poisonous becomes $\text{none} \land \text{green} \dent \neg m$
$r_3$: odour = foul $\Rightarrow$ poisonous becomes $\text{foul} \dent \neg m$

To classify an instance $F$, ask the knowledge base two questions: does it entail $F \dent m$, and does it entail $F \dent \neg m$?

The alignment theorem

Madzime and Meyer proved that the translation is faithful, provided the rule set satisfies three assumptions:

Strict exception closure: any two opposite-label rules that can apply together are comparable, one body inside the other.
Sanity: no two rules share a body but disagree on the label.
No total override: every rule has at least one instance where no more specific opposite-label rule overrides it.

Then, for every complete instance $F$:

Abstain no rule applies $\Rightarrow$ $\mathcal{K}$ entails neither $F \dent m$ nor $F \dent \neg m$
Label 1 $\mathrm{MSW}(F) = 1 \Rightarrow \mathcal{K}$ entails $F \dent m$ only
Label 0 $\mathrm{MSW}(F) = 0 \Rightarrow \mathcal{K}$ entails $F \dent \neg m$ only

So the classifier's three verdicts line up exactly with the three entailment outcomes.

The theorem says the two should agree. Our workbench checks whether they actually do on real rule sets, and what happens when an assumption is broken.

The workbench

A Python/C workbench checks the three assumptions, runs MSW inference with an explanation trace for every instance, translates the rule set into a KLM knowledge base, and asks each closure whether the instance entails m or ¬m. The two sides are then compared side by side.

Click any box to jump to the part of the page that explains it.

Results

13,509instances checked

3closures: RC, LC and System W

100%agreement with ECCRS

Assumptions hold: Bank, Breast Cancer and Mushroom rule sets
Instances	RC	LC	System W
13,509	100%	100%	100%

Assumptions broken on purpose (MSW vs LC, 13,509 instances per row)
Assumption broken	Agree	Abstain	Conflict
Exception closure	13,395	114	0
Sanity	12,019	0	1,490
No total override	13,374	0	135

On every tested instance, the label ECCRS predicts is the label all three closures entail. When an assumption breaks, the check fails safely: an abstention or a flagged conflict, never a confident wrong label.

Team

Each of us implemented one closure. Click a team member to see their individual work, paper and source code.

Antony Baker System W Daniel Schlesinger Rational Closure Augustine Mochoeneng Lexicographic Closure

Supervisor: Prof. Thomas Meyer, Department of Computer Science, University of Cape Town.

Documents

Individual papers and source code are on each team member's page.