Bayesian Networks
Okay, so what can we do with Bayesian Networks?
⃝c -Trenn, King’s College London 2
Bayesian Networks
Okay, so what can we do with Bayesian Networks?
They are useful for inference (a conclusion reached on the basis of evidence and reasoning)
⃝c -Trenn, King’s College London 3
Inference tasks
Simple queries: compute posterior marginal PpXi |E “ eq PpListening “ true|Status “ excitedq
Conjunctive queries
PpXi,Xj|E“eq “ PpXi|E“eqPpXj|Xi,E“eq
Optimal decisions: decision networks include utility information; probabilistic
inference required for P poutcome|action, evidenceq
Value of information: which evidence to seek next?
Sensitivity analysis: which probability values are most critical? Explanation: why do I need a new starter motor?
⃝c -Trenn, King’s College London 4
Inference tasks
We will focus on simple queries: Compute posterior marginal
PpXi|E“eq
PpListening “ true|Status “ excitedq
We will look a several ways of doing this. 1. Enumeration
2. Rejectionsampling(usingpriorsampling) 3. Likelihoodweighting
4. Gibbssampling
⃝c -Trenn, King’s College London 5
Inference by enumeration
Simplest approach to evaluating the network is to do just as we did for the dentist example
Difference is that we use the structure of the network to tell us which sets of joint probabilities to use.
‚ ThanksProfessorMarkov
Gives us a slightly intelligent way to sum out variables from the joint without
actually constructing its explicit representation
⃝c -Trenn, King’s College London 6
Inference by enumeration
Simple query on the burglary network.
PpB|j, mq “ PpB, j, mq Ppj,mq
“ αPpB, j, mq ÿÿ
“ α
Rewrite full joint entries taking network into account:
⃝c -Trenn, King’s College London
7
PpB|j, mq “ α
PpB,e,a,j,mq ÿÿ
PpBqP peqPpa|B, eqP pj|aqP pm|aq
ea
ea
ÿÿ
“ αPpBq P peq ea
Ppa|B, eqP pj|aqP pm|aq
Inference by enumeration
We evaluate this expression
ÿÿ
PpB|j, mq “ αPpBq P peq Ppa|B, eqP pj|aqP pm|aq ea
by going through the variables in order, multiplying CPT entries along the way. At each point, we need to loop through the possible values of the variable. Involves a lot of repeated calculations.
⃝c -Trenn, King’s College London 8
Evaluation tree
řř
PpB|j, mq “ αPpBq e P peq a Ppa|B, eqP pj|aqP pm|aq ⃝c -Trenn, King’s College London
9
Evaluation tree
Inefficient: computes P pj |aqP pm|aq for each value of e
⃝c -Trenn, King’s College London 10
Enumeration algorithm
function ENUMERATION-ASK(X, e, bn) returns a distribution over X
inputs: X, the query variable
e, observed values for variables E
bn, a Bayesian network t E Y Y
QpX q Ð a distribution over X, initially empty for each value xi of X do
extend e with value xi for X
Qpxi q Ð ENUMERATE-ALL(VARS[bn], e) return NORMALIZE(QpX q)
⃝c -Trenn, King’s College London 11
Enumeration algorithm
function ENUMERATE-ALL(vars, e) returns a real number if EMPTY?(vars) then return 1.0
Y Ð FIRST(vars)
if Y has value y in e
then return P py | P apY qq
ˆ ENUMERATE-ALL(REST(vars), e)
ř
y Ppy |PapYqq
ˆ ENUMERATE-ALL(REST(vars), ey )
where ey is e extended with Y “ y
elsereturn
⃝c -Trenn, King’s College London 12
Other exact approaches
We can improve on enumeration.
Variable elimination evaluates the enumeration tree bottom up, remembering intermediate values.
‚ Simpleandefficientforsinglequeries
Clustering algorithms can be more efficient for multiple queries
‚ Groupvariablestogetherstrategically.
However, all exact inference can be computationally intractable.
⃝c -Trenn, King’s College London 13
Complexity of exact inference
Singly connected networks (or polytrees)
Any two nodes are connected by at most one (undirected) path Time and space cost of variable elimination are:
for k parents, d values.
⃝c -Trenn, King’s College London
14
Opdknq
Complexity of exact inference
Multiply connected networks.
Exponential time and space complexity, even when number of parents of a node is
bounded.
Inference is NP-hard. In fact, #P-complete.
⃝c -Trenn, King’s College London 15