The Shape of Explanations: A Topological Account ofRule-Based Explanations in Machine Learning
Introduction

Rule-Based Explanations

Explanation Topology

Rule-based explanations provide simple reasons explaining the behavior of machine learning classifiers
at given points in the feature space. We take advantage of the connection between the inherent definability of rule-based explanations and definability
in topology to develop a general framework to represent explanations based on existing explanation
algorithms.

Given classifier f : X → Y , a rule-based explanation for x ∈ X is a well-defined region of the feature
space containing x whose classification is invariant
within the region, i.e. belonging to the region is sufficient to be classified as f (x). These explanations
have the following properties:

Rule-based explanations are regions of the feature
space that satisfy some predicate or definable property ϕ. We restrict to predicates satisfying the following properties:

Contributions• We present a novel framework of explainability
for classifiers based on existing explanation
algorithms.
• We characterize explainability as a topologicalproperty relative to an explanation scheme i.e.
relative to a choice of explanation shape and ameasure of explanation size. We conjecturethat all classifiers “in-the-wild” satisfy thisnotion of explainability.
• Employing our framework, we identify two
principles for explanation algorithms that
apply both theoretically and in practice.

• Local• Post-Hoc• Perturbation-ResistantFigure 1 illustrates a rule-based explanation that is
an open rectangle on a continuous feature space.
There are several existing algorithms for generating
rule-based explanations including Anchors [1] andLORE [2]. We say that a classifier is explainable if
there exists explanations for all of the feature space
except for a set of edge cases.

Then collection of sets satisfying ϕ is a topologicalbasis [3]. Closing this collection under countable
union and finite intersection, we obtain explanation
topology Tϕ.
Sets belonging to Tϕ are called open. The main
result of this paper characterizes explainability interms of open sets and small sets.

Theorem: A classifier f : X → Y is explainable for scheme (X, ϕ, µ) if and only if, for y ∈ Y , there−1exists open set Oy ∈ Tϕ such that f (y) = Oy ∪ Ey and Ey is Tϕ-meagre, µ-null.

Explanation Schemes

Application: Ensembles

An explanation scheme (X, ϕ, µ) is a reference frame
for analyzing explainability. It consists of the following:

Ensembles aggregate predictions from a collection ofclassifiers and are commmonly used in practice e.g.
Random Forests and XGBoost. Ensembles are often
viewed as complex, whereas their consitutent classifiers are weak or simple. We show that if the constitutent classifiers are explainable for a given scheme
then their ensemble is explainable.

Coverage measures the size of an explanation. Forinstance, µ is often a probability measure if one isknown.
A set of edge cases must be small with respect toboth topology Tϕ and measure µ. The corresponding notions of smallness are Tϕ-meagre and µ-null.

University of Massachusetts, Amherst

Implications
For continuous feature spaces, explanations cantake nearly any desired shape.
2 If features are unbounded and a probability
measure is not known, then the user should only
consider explanations that are bounded.
1

Future Work
Extend Formal Framework• Minimum Coverage Guarantee• Fuzzy Explanations
Explore Connections

Main Result (Explainability is a simple topological property)• X - feature space• ϕ - rule generating the explanation topology Tϕ• µ - coverage measure defined on TϕFigure 1: Example rule-based explanation of x
for a linear classifier• If two explanations for a given point overlap, thenthere exists an explanation in their intersection
covering the point.
• Each point is covered by an explanation.

Brett Mullins

Theorem: If f1, . . . , fk are classifiers explainable
for explanation scheme (X, ϕ, µ) and f is an ensemble of f1, . . . , fk , then f is explainable for (X, ϕ, µ).

• Computational Complexity• Synthetic Topology

References[1] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin.
Anchors: High-precision model-agnostic explanations.
In AAAI Conference on Artificial Intelligence, 2018.
[2] Riccardo Guidotti, Anna Monreale, Salvatore Ruggieri,Dino Pedreschi, Franco Turini, and Fosca Giannotti.
Local rule-based explanations of black box decisionsystems.
ArXiv, abs/1805.10820, 2018.
[3] James Munkres.
Topology.
Prentice Hall, 2nd edition, 2000.

Contact Information• Website: bcmullins.github.io• Email: bmullins@umass.edu