CS代考 Bayesian Networks – cscodehelp代写 – INTERVIEW&CODEHELP

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
We evaluate this expression
ÿÿ
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
řř
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)
ř
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

CS代考 Bayesian Networks – cscodehelp代写

Published by admin

Leave a Reply Cancel reply