package aima.core.probability.bayes.approx;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Random;
import aima.core.probability.CategoricalDistribution;
import aima.core.probability.RandomVariable;
import aima.core.probability.bayes.BayesianNetwork;
import aima.core.probability.proposition.AssignmentProposition;
import aima.core.probability.util.ProbUtil;
import aima.core.probability.util.ProbabilityTable;
import aima.core.util.JavaRandomizer;
import aima.core.util.Randomizer;
import aima.core.util.datastructure.Pair;
/**
* Artificial Intelligence A Modern Approach (3rd Edition): page 534.
*
*
*
* function LIKELIHOOD-WEIGHTING(X, e, bn, N) returns an estimate of P(X|e)
* inputs: X, the query variable
* e, observed values for variables E
* bn, a Bayesian network specifying joint distribution P(X1,...,Xn)
* N, the total number of samples to be generated
* local variables: W, a vector of weighted counts for each value of X, initially zero
*
* for j = 1 to N do
* x,w <- WEIGHTED-SAMPLE(bn,e)
* W[x] <- W[x] + w where x is the value of X in x
* return NORMALIZE(W)
* --------------------------------------------------------------------------------------
* function WEIGHTED-SAMPLE(bn, e) returns an event and a weight
*
* w <- 1; x <- an event with n elements initialized from e
* foreach variable Xi in X1,...,Xn do
* if Xi is an evidence variable with value xi in e
* then w <- w * P(Xi = xi | parents(Xi))
* else x[i] <- a random sample from P(Xi | parents(Xi))
* return x, w
*
*
* Figure 14.15 The likelihood-weighting algorithm for inference in Bayesian
* networks. In WEIGHTED-SAMPLE, each nonevidence variable is sampled according
* to the conditional distribution given the values already sampled for the
* variable's parents, while a weight is accumulated based on the likelihood for
* each evidence variable.
*
* Note: The implementation has been extended to handle queries with
* multiple variables.
*
* @author Ciaran O'Reilly
* @author Ravi Mohan
*/
public class LikelihoodWeighting implements BayesSampleInference {
private Randomizer randomizer = null;
public LikelihoodWeighting() {
this(new JavaRandomizer(new Random()));
}
public LikelihoodWeighting(Randomizer r) {
this.randomizer = r;
}
// function LIKELIHOOD-WEIGHTING(X, e, bn, N) returns an estimate of
// P(X|e)
/**
* The LIKELIHOOD-WEIGHTING algorithm in Figure 14.15. For answering queries
* given evidence in a Bayesian Network.
*
* @param X
* the query variables
* @param e
* observed values for variables E
* @param bn
* a Bayesian network specifying joint distribution
* P(X1,...,Xn)
* @param N
* the total number of samples to be generated
* @return an estimate of P(X|e)
*/
public CategoricalDistribution likelihoodWeighting(RandomVariable[] X,
AssignmentProposition[] e, BayesianNetwork bn, int N) {
// local variables: W, a vector of weighted counts for each value of X,
// initially zero
double[] W = new double[ProbUtil
.expectedSizeOfCategoricalDistribution(X)];
// for j = 1 to N do
for (int j = 0; j < N; j++) {
// x,w <- WEIGHTED-SAMPLE(bn,e)
Pair, Double> x_w = weightedSample(bn,
e);
// W[x] <- W[x] + w where x is the value of X in x
W[ProbUtil.indexOf(X, x_w.getFirst())] += x_w.getSecond();
}
// return NORMALIZE(W)
return new ProbabilityTable(W, X).normalize();
}
// function WEIGHTED-SAMPLE(bn, e) returns an event and a weight
/**
* The WEIGHTED-SAMPLE function in Figure 14.15.
*
* @param e
* observed values for variables E
* @param bn
* a Bayesian network specifying joint distribution
* P(X1,...,Xn)
* @return return x, w - an event with its associated weight.
*/
public Pair, Double> weightedSample(
BayesianNetwork bn, AssignmentProposition[] e) {
// w <- 1;
double w = 1.0;
// x <- an event with n elements initialized from e
Map x = new LinkedHashMap();
for (AssignmentProposition ap : e) {
x.put(ap.getTermVariable(), ap.getValue());
}
// foreach variable Xi in X1,...,Xn do
for (RandomVariable Xi : bn.getVariablesInTopologicalOrder()) {
// if Xi is an evidence variable with value xi
// in e
if (x.containsKey(Xi)) {
// then w <- w * P(Xi = xi |
// parents(Xi))
w *= bn.getNode(Xi)
.getCPD()
.getValue(
ProbUtil.getEventValuesForXiGivenParents(
bn.getNode(Xi), x));
} else {
// else x[i] <- a random sample from
// P(Xi | parents(Xi))
x.put(Xi, ProbUtil.randomSample(bn.getNode(Xi), x, randomizer));
}
}
// return x, w
return new Pair, Double>(x, w);
}
//
// START-BayesSampleInference
@Override
public CategoricalDistribution ask(final RandomVariable[] X,
final AssignmentProposition[] observedEvidence,
final BayesianNetwork bn, int N) {
return likelihoodWeighting(X, observedEvidence, bn, N);
}
// END-BayesSampleInference
//
}