Transcript Knowledge Engineering for Bayesian Networks

Knowledge Engineering for
Bayesian Networks
Ann Nicholson
School of Computer Science
and Software Engineering
Monash University
1
Overview


Representing uncertainty
Introduction to Bayesian Networks
» Syntax, semantics, examples




The knowledge engineering process
Case Study: Intelligent Tutoring
Summary of other BN research
Open research questions
2
Sources of Uncertainty




Ignorance
Inexact observations
Non-determinism
AI representations
» Probability theory
» Dempster-Shafer
» Fuzzy logic
3
Probability theory for
representing uncertainty

Assigns a numerical degree of belief between
0 and 1 to facts
» e.g. “it will rain today” is T/F.
» P(“it will rain today”) = 0.2 prior probability
(unconditional)

Posterior probability (conditional)
» P(“it wil rain today” | “rain is forecast”) = 0.8

Bayes’ Rule: P(H|E) = P(E|H) x P(H)
P(E)
4
Bayesian networks



Directed acyclic graphs
Nodes: random variables,
» R: “it is raining”, discrete values T/F
» T: temperature, cts or discrete variable
» C: colour, discrete values {red,blue,green}
Arcs indicate dependencies (can have causal
interpretation)
5
Bayesian networks

Conditional Probability Distribution (CPD)
– Associated with each variable
– probability of each state given parent states
“Jane has the flu”
FXlu
P(Flu=T) = 0.05
TY
e
P(Te=High|Flu=T) = 0.4
P(Te=High|Flu=F) = 0.01
Models causal relationship
“Jane has a
high temp”
Models possible sensor error
“Thermometer
temp reading”
TQh
P(Th=High|Te=H) = 0.95
P(Th=High|Te=L) = 0.1
6
BN inference


Evidence: observation of specific state
Task: compute the posterior probabilities for query
node(s) given evidence.
Flu
Flu
Y
Te
TY
e
Th
Th
Diagnostic
inference
Causal
inference
Flu
TB
Te
Flu
Te
Th
Intercausal
inference
Mixed
inference
7
BN software

Commerical packages: Netica, Hugin,
Analytica (all with demo versions)
Free software: Smile, Genie, JavaBayes, …

http://HTTP.CS.Berkeley.EDU/~murphyk/Bayes/bnsoft.
html

Example running Netica software
8
Decision networks

Extension to basic BN for decision making
» Decision nodes
» Utility nodes

EU(Action) =  p(o|Action,E) U(o)
o
» choose action with highest expect utility

Example
9
Elicitation from experts

Variables
» important variables? values/states?

Structure
» causal relationships?
» dependencies/independencies?

Parameters (probabilities)
» quantify relationships and interactions?

Preferences (utilities)
10
Expert Elicitation Process




These stages are done iteratively
Stops when further expert input is no longer
cost effective
Process is difficult and time consuming.
Current BN tools
» inference engine
» GUI

BN
EXPERT
Domain
EXPERT
Next generation of BN tools?
BN TOOLS
11
Knowledge discovery

There is much interest in automated methods
for learning BNS from data
» parameters, structure (causal discovery)

Computationally complex problem, so current
methods have practical limitations
» e.g. limit number of states, require variable
ordering constraints, do not specify all arc
directions

Evaluation methods
12
The knowledge engineering process
1. Building the BN
» variables, structure, parameters, preferences
» combination of expert elicitation and knowledge discovery
2. Validation/Evaluation
» case-based, sensitivity analysis, accuracy testing
3. Field Testing
» alpha/beta testing, acceptance testing
4. Industrial Use
» collection of statistics
5. Refinement
» Updating procedures, regression testing
13
Case Study: Intelligent tutoring


Tutoring domain: primary and secondary school
students’ misconceptions about decimals
Based on Decimal Comparison Test (DCT)
» student asked to choose the larger of pairs of decimals
» different types of pairs reveal different misconceptions


ITS System involves computer games involving
decimals
This research also looks at a combination of expert
elicitation and automated methods (UAI2001)
14
Expert classification of Decimal
Comparison Test (DCT) results
expert
class
“apparent
expert”
“longer is
larger”
“shorter is
larger”
ATE
AMO
MIS
AU
LWH
LZE
LRV
LU
SDF
SRN
SU
UN
1
0.4
0.35
H
H
L
H
L
L
L
L
H
H
H
-
2
5.736
5.62
H
H
L
H
H
H
H
H
L
L
L
-
Item Type
3
4
4.7
0.452
4.08
0.45
H
H
H
L
L
L
L
H
H
H
L
H
H
L
H
L
-
H = high (all correct or only one wrong)
L = low (all wrong or only one correct)
5
0.4
0.3
H
H
L
H
H
H
H
L
-
6
0.42
0.35
H
H
L
H
H
L
H
L
15
The ITS architecture
Adaptive
Bayesian
Network
Inputs
Student
Generic BN
model of student
Decimal
comparison
test
(optional)
Answers
Diagnose
misconception
Predict outcomes
Identify most
useful information
Information about
student e.g. age
(optional)
Classroom
diagnostic test
results (optional)
Answer
Computer Games
Hidden
number
Answer
Feedback
Answer
System
Controller
Module
Sequencing
tactics
Item
Select next item
type
Decide to present
help
Decide change to
new game
Identify when
expertise gained
Flying
photographer
Item type
Item
Decimaliens
New
game
Help
Number
between
Help
….
Report
on student
Classroom
Teaching
Activities
16
Teacher
Expert Elicitation

Variables
» two classification nodes: fine and coarse (mut. ex.)
» item types: (i) H/M/L (ii) 0-N

Structure
» arcs from classification to item type
» item types independent given classification

Parameters
» careless mistake (3 different values)
» expert ignorance: - in table (uniform distribution)
17
Expert Elicited BN
18
Evaluation process

Case-based evaluation
» experts checked individual cases
» sometimes, if prior was low, ‘true’ classification did
not have highest posterior (but usually had biggest
change in ratio)

Adaptiveness evaluation
» priors changes after each set of evidence

Comparison evaluation
» Differences in classification between BN and
expert rule
» Differences in predictions between different BNs
19
Comparison evaluation



Development of measure: same classification,
desirable and undesirable re-classification
Use item type predictions
Investigation of effect of item type granularity
and probability of careless mistake
20
Comparison: expert BN vs rule
lwh
lwh 386
lze 0
lrv 10
lu
6
sdf 0
srn 0
su 0
ate 0
amo 0
mis 0
au 9
un 43
Same
lze
0
98
0
9
0
0
0
0
0
0
0
6
lrv
0
0
0
0
0
0
0
0
0
0
0
0
lu
0
0
0
54
0
0
0
0
0
0
0
15
sdf
0
0
0
0
83
0
2
0
0
0
0
35
srn
0
0
0
0
0
159
22
0
0
0
0
14
Undesirable
su
0
0
0
0
4
0
40
0
0
0
0
11
ate
0
0
0
0
0
0
3
1050
0
0
63
119
Desirable
amo
0
0
0
0
0
0
0
0
79
0
8
26
mis
0
0
0
0
0
0
0
0
0
6
0
2
au
0
0
0
0
0
0
0
0
0
0
0
0
un
0
0
0
6
0
0
2
0
0
0
1
66
21
Results
0-N
varying
prob. of
careless
mistake
A
0.22 86.95%
A
1207
S
3
L
0
UN
157
0.11 88.02
A
1206
S
3
L
0
UN
147
0.03 89.29%
A
1202
S
3
L
0
UN
102
S
12.56%
0
312
0
71
11.12%
0
310
0
60
9.48%
0
308
0
49
L
UN A
0.49%
87.61%
9
0
1213
0
0
4
569
0
0
78 31
150
0.86%
87.28%
9
1
1184
0
2
4
563
6
7
64 66
139
1.23%
91.63%
8
6
1173
0
4
0
560
9
0
80 106
83
H/M/L
S
L
UN
11.98% 0.441%
0
0
3
310
0
1
0
557
2
82
60 45
10.71% 2.01%
0
23
9
310
0
1
0
557
5
73
49 76
5.25% 3.12%
0
0 43
304
0 11
0
547 22
9
36 309
varying granularity of item type: 0-N and H/M/L
Same
Desir.
Undes.
22
Investigation by Automated
methods



Classification (using SNOB program, based
on MML)
Parameters
Structure (using CaMML)
23
Results
Method Type
values
Expert 0-N
H/M/L
24 DCT
0-N
H/M/L
EBN
0-N
learned H/M/L
CaMML 0-N
contr.
H/M/L
CaMML 0-N
uncontr. H/M/L
Match
0.22
0.11
0.03
0.22
0.11
0.03
SNOB
Avg
Avg
Avg
Avg
Avg
Avg
77.88
82.93
84.37
80.47
83.91
90.40
79.81
72.06
72.51
95.97
97.63
86.51
83.48
85.15
92.63
Desir.
Undes.
Change Change
20.39
1.72
15.63
1.44
11.86
3.78
18.71
0.82
13.66
2.42
6.48
3.12
17.60
2.49
16.00
11.94
17.03
10.46
2.36
1.66
1.61
0.75
5.08
8.41
8.12
8.34
5.87
7.92
4.61
2.76
24
Another Case Study: Seabreeze
prediction





2000 Honours project, joint with Bureau of
Meteorology (with Russell Kennett and Kevin Korb,
PAKDD’2001 paper, TR)
BN network built based on existing simple expert rule
Several years data available for Sydney seabreezes
CaMML (Wallace and Korb, 1999) and Tetrad-II (Spirtes et
al. 1993) programs used to learn BNs from data
Comparative analysis showed automated methods
gave improved predictions.
25
Other BN-related projects


DBNS for discrete monitoring (PhD, 1992)
Approximate BN inference algorithms based on a
mutual information measure for relevance (with Nathalie
Jitnah, ICONIP97, ECSQARU97, PRICAI98,AI99)


Plan recognition: DBNs for predicting users actions
and goals in an adventure game (with David Albrecht,
Ingrid Zukerman, UM97,UMUAI1999,PRICAI2000)
Bayesian Poker (with Kevin Korb, UAI’99, honours students)
26
Other BN-related projects (cont.)



DBNs for ambulation monitoring and fall diagnosis
(with biomedical engineering, PRICAI’96)
Autonomous aircraft monitoring and replanning (with
Ph.D. student Tim Wilkin, PRICAI2000)
Ecological risk assessment (2003 honours project with
Water Studies Centre)

Writing a textbook! (with Kevin Korb)
Bayesian Artificial Intelligence
27
Open Research Questions

Methodology for combining expert elicitation and
automated methods
» expert knowledge used to guide search
» automated methods provide alternatives to be presented to
experts

Evaluation measures and methods
» may be domain depended

Improved tools to support elicitation
» e.g. visualisation of d-separation

Industry adoption of BN technology
28