aima.core.probability.bayes.exact

Class EliminationAsk

java.lang.Object

aima.core.probability.bayes.exact.EliminationAsk

All Implemented Interfaces:

BayesInference

public class EliminationAsk
extends java.lang.Object
implements BayesInference

Artificial Intelligence A Modern Approach (3rd Edition): Figure 14.11, page 528.

 function ELIMINATION-ASK(X, e, bn) returns a distribution over X
   inputs: X, the query variable
           e, observed values for variables E
           bn, a Bayesian network specifying joint distribution P(X1, ..., Xn)
   
   factors <- []
   for each var in ORDER(bn.VARS) do
       factors <- [MAKE-FACTOR(var, e) | factors]
       if var is hidden variable the factors <- SUM-OUT(var, factors)
   return NORMALIZE(POINTWISE-PRODUCT(factors))
 

Figure 14.11 The variable elimination algorithm for inference in Bayesian networks.

Note: The implementation has been extended to handle queries with multiple variables.

Author:

Ciaran O'Reilly

Constructor Summary

Constructors

Constructor and Description
EliminationAsk()

Method Summary

Modifier and Type	Method and Description
CategoricalDistribution	ask(RandomVariable[] X, AssignmentProposition[] observedEvidence, BayesianNetwork bn)
protected void	calculateVariables(RandomVariable[] X, AssignmentProposition[] e, BayesianNetwork bn, java.util.Set<RandomVariable> hidden, java.util.Collection<RandomVariable> bnVARS) Note:Override this method for a more efficient implementation as outlined in AIMA3e pgs.
CategoricalDistribution	eliminationAsk(RandomVariable[] X, AssignmentProposition[] e, BayesianNetwork bn) The ELIMINATION-ASK algorithm in Figure 14.11.
protected java.util.List<RandomVariable>	order(BayesianNetwork bn, java.util.Collection<RandomVariable> vars) Note:Override this method for a more efficient implementation as outlined in AIMA3e pgs.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

EliminationAsk

public EliminationAsk()

Method Detail

eliminationAsk

public CategoricalDistribution eliminationAsk(RandomVariable[] X,
                                              AssignmentProposition[] e,
                                              BayesianNetwork bn)

The ELIMINATION-ASK algorithm in Figure 14.11.

Parameters:

X - the query variables.

e - observed values for variables E.

bn - a Bayes net with variables {X} ∪ E ∪ Y /* Y = hidden variables //

Returns:

a distribution over the query variables.

ask

public CategoricalDistribution ask(RandomVariable[] X,
                                   AssignmentProposition[] observedEvidence,
                                   BayesianNetwork bn)

Specified by:

ask in interface BayesInference

Parameters:

X - the query variables.

observedEvidence - observed values for variables E.

bn - a Bayes net with variables {X} ∪ E ∪ Y /* Y = hidden variables

Returns:

a distribution over the query variables.

calculateVariables

protected void calculateVariables(RandomVariable[] X,
                                  AssignmentProposition[] e,
                                  BayesianNetwork bn,
                                  java.util.Set<RandomVariable> hidden,
                                  java.util.Collection<RandomVariable> bnVARS)

Note:Override this method for a more efficient implementation as outlined in AIMA3e pgs. 527-28. Calculate the hidden variables from the Bayesian Network. The default implementation does not perform any of these.

Two calcuations to be performed here in order to optimize iteration over the Bayesian Network:
1. Calculate the hidden variables to be enumerated over. An optimization (AIMA3e pg. 528) is to remove 'every variable that is not an ancestor of a query variable or evidence variable as it is irrelevant to the query' (i.e. sums to 1). 2. The subset of variables from the Bayesian Network to be retained after irrelevant hidden variables have been removed.

Parameters:

X - the query variables.

e - observed values for variables E.

bn - a Bayes net with variables {X} ∪ E ∪ Y /* Y = hidden variables //

hidden - to be populated with the relevant hidden variables Y.

bnVARS - to be populated with the subset of the random variables comprising the Bayesian Network with any irrelevant hidden variables removed.

order

protected java.util.List<RandomVariable> order(BayesianNetwork bn,
                                               java.util.Collection<RandomVariable> vars)

Note:Override this method for a more efficient implementation as outlined in AIMA3e pgs. 527-28. The default implementation does not perform any of these.

Parameters:

bn - the Bayesian Network over which the query is being made. Note, is necessary to provide this in order to be able to determine the dependencies between variables.

vars - a subset of the RandomVariables making up the Bayesian Network, with any irrelevant hidden variables alreay removed.

Returns:

a possibly opimal ordering for the random variables to be iterated over by the algorithm. For example, one fairly effective ordering is a greedy one: eliminate whichever variable minimizes the size of the next factor to be constructed.