Explainable AI
Rick Kuhn, CSD and Raghu Kacker, ACMD
What is the problem?
• Artificial intelligence and machine learning (AI/ML) systems have
exceeded human performance in nearly every application where they
have been tried
• AI is starting to be incorporated into consumer products. This trend is
accelerating, and AI will be increasingly used in safety-critical systems
• AI systems are good, but sometimes make mistakes, and human users
will not trust their decisions without explanation
• There is a tradeoff between AI accuracy and explainability: the most accurate
methods, such as convolutional neural nets (CNNs), provide no explanations;
understandable methods, such as rule-based, tend to be less accurate
What is the current state of the
art?
Black-box statistical
predictions are
inadequate
Explanations must
be understandable
to non-specialist
Trade
Expert system:
off: Good for explanations,
not so good for accuracy
- OR - Neural nets:
Good for accuracy,
not so good for explanations
How do we get the
best of both worlds?
What can NIST do?
• The classification problem in machine learning is closely related to the
problem of fault location in combinatorial testing for software.
• The objective in both cases is to identify a small number of interactions,
out of possibly billions or more, that trigger a failure (in combinatorial
testing) or produce a conclusion (in machine learning).
• We have methods and tools for fault location in combinatorial testing that
could be adapted to ML problems, to identify the rare combinations of
variable values that produce conclusions in AI systems.
• This approach has not been applied to AI/ML before.
• NIST has established the leading project in combinatorial software testing
Fault location
Given: a set of tests that the SUT fails, which
combinations of variables/values triggered the failure?
variable/value combinations
in passing tests
variable/value combinations
in failing tests
Combinations in failing but
not in passing tests
These are the ones we want
– how do we find them?
Fault location – what's the problem?
If they're in failing set but not in
passing set:
1. which ones triggered the failure?
2. which ones don't matter?
()
t n
out of v t combinations
Example:
30 variables, 5 values each,
input configuration 530
445,331,250 5-way combinations
142,506 combinations in each test
FInd one or two out of >142,000 that
caused failure
Relevance to
explainable AI
Non-class
feature
combinations
aquatic,
venomous, 6 legs,
...
Class feature Individual
combinations - feature
brown & furry, combinations –
black & furry, brown & furry, Animal shares features
whiskers, claws, ... whiskers, claws, with cat class
not aquatic, not not aquatic, not
venomous, not 6 Animal does not share
venomous, not 6
legs, features with non-cat
legs, ...
classes
Input configuration 21561
Why is this
creature
recognized as a
reptile?
No single feature is sufficient
explanation – shares features with
non-reptiles
No pair of features sufficient –
shares 2-way combinations w/
non-reptiles
3-way combinations produce
rules to explain recognition of
Testudo as a reptile
Only reptiles have these combinations of features:
Non-reptiles in the not aquatic AND not toothed AND four legs
database do not have egg-laying AND not aquatic AND four legs
these 3-way not hairy AND four legs AND cat size
not milk-producing AND not aquatic AND four legs
combinations not milk-producing AND four legs AND cat size
not predator AND not toothed AND four legs
Sample ML problem
• “Titanic survivors” – popular demo problem for ML
• Predict which passengers survive, using attributes:
• Passenger class: 1st, 2nd, 3rd
• Sex
• Age: 14 and under, 15 to 20, 21 to 70, over 70
• Number of siblings or spouses onboard
• Number of parents or children onboard
• Embarkation point: Southampton, England; Queenstown,
Ireland; Cherbourg, France
• Input configuration 21324152
Example using
prototype – what
factors explain this
passenger’s
survival?
First class passenger, female aged 21 to 70, no siblings,
spouse, parents, or children onboard, from England
What factors differentiate passenger from casualties?
Consider 2-way combinations of factors:
1st class female passengers (like this one) were only
0.6% of casualties
No single factor is adequate explanation:
15% of dead were 1st class;
16% were female;
61% aged 21 to 70
Survival explained by being female passenger traveling
first class. Neither of these two factors alone is enough.
Heatmap visualization of factor
combinations
Psngr class Sex Age # sibling #parent embarked
spouse child
1 f 21to70 0 0 S
Green to red -> more significant to less significant for explanation
Heatmap female 21to070 no sibling/spouse no parents/children Southampton
1st class 0.0062 0.1174 0.1075 0.1248 0.0964
female 0.0803 0.0803 0.0927 0.1150
21 to 70 0.4561 0.5328 0.4957
no sibling/
spouse 0.6811 0.5340
no parents/
children 0.6131
Another example–
what factors explain
this passenger’s
survival?
First class passenger, male child, with one sibling, two
parents onboard, from England
What factors differentiate passenger from casualties?
Consider 2-way combinations of factors:
1st class passengers with two parents onboard (like this
one) were only 0.7% of casualties
No single factor is adequate explanation:
15% of dead were 1st class;
84% were male;
29% were children 14 and under
Survival explained by being child with parents traveling
first class. No single factor alone is enough.
Easily seen in 3-way combinations:
Mapping combinations to
expressions
• Report identifies t-way combinations that distinguish the predicted class
from others
• Combinations can be mapped to expressions to produce a rule-based
type of explanation
if (1st class passenger AND female) OR (female AND age 21to70) OR
(female AND no siblings/spouses) then SURVIVE
if (1st class passenger AND age 14 or under AND parents onboard) OR
(1st class passenger AND age 14 or under AND siblings onboard)
then SURVIVE
As noted, none of the single factors above is sufficient for explanation
Example: empty
vs. occupied
rooms, using
sensor data
Why do we conclude this room is
occupied?
These levels of humidity and lighting are strong
indication
Considering levels of lighting, CO2, and
humidity ratio provide even stronger evidence:
Empty rooms don’t have these levels
A different example:
lymph node
pathology – why is
this classified as
malignant not
metastatic?
• These combinations are
characteristic of lymphoma that
arises in lymph node instead of
metastatic that spread to node
from somewhere else
Summary
• Combinatorial methods can provide explainable AI
• We have prototype that applies this approach
• Determine combinations of variable values that differentiate an example from other
possible conclusions
Feature combinations present shared with class
Feature combinations not shared with class not present
• Method can be applied to black-box functions such as CNNs
• Present explanation in the preferred form of rules,
“if A & B, or C with D & E, then conclusion is X”
Summary
• Explainability is a critical problem in the acceptance of artificial
intelligence/machine learning, especially for critical applications
• Human users will not trust AI if conclusions cannot be explained
• Methods from combinatorial software testing can be applied to solving the
problem of explainable AI
• We have prototype that applies this approach
• Determine combinations of variable values that differentiate an example from other
possible conclusions
Feature combinations present shared with class
Feature combinations not shared with class not present
• Present explanation in the preferred form of rules, “if A & B, or C with D & E, then
conclusion is X”
• Method can be applied to black-box functions such as CNNs
What has been tried?
• Interpretable models – e.g. rule-based expert systems: “if patient has
symptoms A and B, or has B with C and D, then illness is X”
• best for explanations
• hard to find rules
• less accurate than other approaches
• Modify neural nets etc. to add explanations
• reduces accuracy, complicates the system
• explanations still not very understandable
• Model induction - infer explainable model from black-box
• flexible for application, good explanations using only input, output
• hard to produce the explainable model
• Our approach – derive rule predicates from inputs and outputs to
CNNs and other black-box functions