Scribd
Upload
2 views6 pages

Exact Inference in Bayesian Networks

The document discusses exact inference in Bayesian networks, focusing on algorithms like ENUMERATION-ASK and variable elimination for computing posterior probabilities. It highlights the efficiency of clustering algorithms in reducing computation time for multiple queries in polytree networks. The content is prepared by Prof. Mr. J. Arockia Prince from ISRO-IIT Madras.

Uploaded by

AROCKIA PRINCE
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views6 pages

Exact Inference in Bayesian Networks

The document discusses exact inference in Bayesian networks, focusing on algorithms like ENUMERATION-ASK and variable elimination for computing posterior probabilities. It highlights the efficiency of clustering algorithms in reducing computation time for multiple queries in polytree networks. The content is prepared by Prof. Mr. J. Arockia Prince from ISRO-IIT Madras.

Uploaded by

AROCKIA PRINCE
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Exact Inference in Bayesian Networks

The basic task for any probabilistic inference system is to compute the
posterior probability distribution for a set of query variables, given some
observed event—usually, some assign- Event ment of values to a set of evidence
variable
Inference by enumeration

The ENUMERATION-ASK algorithm in Figure evaluates these


expression trees using depth-first, left-to-right recursion. The algorithm is very
similar in structure to the backtracking algorithm for solving CSPs

Prepared by [Link] Prince M.E,M.S,(Ph.D)(ISRO-IIT MADRAS)


function ENUMERATION-ASK(X, e, bn) returns a distribution over X
inputs: X, the query variable e, observed values for variables E bn, a Bayes net
with variables vars
Q(X) a distribution over X, initially empty
for each value xi of X do
Q(xi) ENUMERATE-ALL(vars, exi )
where exi is e extended with X = xi
return NORMALIZE(Q(X))
function ENUMERATE-ALL(vars, e) returns a real number
if EMPTY?(vars) then return 1.0
V FIRST(vars)
if V is an evidence variable with value v in e
then return P(v j parents(V)) _ ENUMERATE-ALL(REST(vars), e)
else return åv P(v j parents(V)) _ ENUMERATE-ALL(REST(vars), ev)
where ev is e extended with V = v
Figure The enumeration algorithm for exact inference in Bayes nets.
The variable elimination algorithm
The idea is simple: do the calculation once and save the results for later
use. This is a form of dynamic programming. There are sev-eral versions of this
approach; we present the variable elimination algorithm, which is the simplest.

Prepared by [Link] Prince M.E,M.S,(Ph.D)(ISRO-IIT MADRAS)


Prepared by [Link] Prince M.E,M.S,(Ph.D)(ISRO-IIT MADRAS)
Operations on factors

Prepared by [Link] Prince M.E,M.S,(Ph.D)(ISRO-IIT MADRAS)


Variable ordering and variable relevance

Clustering algorithms
The variable elimination algorithm is simple and efficient for answering
individual queries. If we want to compute posterior probabilities for all the
variables in a network, however, it can be less efficient. For example, in a polytree
network, one would need to issue O(n) queries costing O(n) each, for a total of
O(n2) time. Using clustering algorithms (also known as join tree algorithms), the
time can be reduced to O(n). For this reason, these algorithms are widely used in
commercial Bayes net tools.

Prepared by [Link] Prince M.E,M.S,(Ph.D)(ISRO-IIT MADRAS)


The basic idea of clustering is to join individual nodes of the network to form
cluster nodes in such a way that the resulting network is a polytree. For example,
the multiply connected network shown in Figure

Prepared by [Link] Prince M.E,M.S,(Ph.D)(ISRO-IIT MADRAS)

You might also like