/
LikelihoodWeighting.java
157 lines (146 loc) · 5.59 KB
/
LikelihoodWeighting.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
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.<br>
* <br>
*
* <pre>
* function LIKELIHOOD-WEIGHTING(X, e, bn, N) returns an estimate of <b>P</b>(X|e)
* inputs: X, the query variable
* e, observed values for variables E
* bn, a Bayesian network specifying joint distribution <b>P</b>(X<sub>1</sub>,...,X<sub>n</sub>)
* 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
* <b>x</b>,w <- WEIGHTED-SAMPLE(bn,e)
* W[x] <- W[x] + w where x is the value of X in <b>x</b>
* return NORMALIZE(W)
* --------------------------------------------------------------------------------------
* function WEIGHTED-SAMPLE(bn, e) returns an event and a weight
*
* w <- 1; <b>x</b> <- an event with n elements initialized from e
* foreach variable X<sub>i</sub> in X<sub>1</sub>,...,X<sub>n</sub> do
* if X<sub>i</sub> is an evidence variable with value x<sub>i</sub> in e
* then w <- w * P(X<sub>i</sub> = x<sub>i</sub> | parents(X<sub>i</sub>))
* else <b>x</b>[i] <- a random sample from <b>P</b>(X<sub>i</sub> | parents(X<sub>i</sub>))
* return <b>x</b>, w
* </pre>
*
* 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.<br>
* <br>
* <b>Note:</b> The implementation has been extended to handle queries with
* multiple variables. <br>
*
* @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
// <b>P</b>(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
* <b>P</b>(X<sub>1</sub>,...,X<sub>n</sub>)
* @param N
* the total number of samples to be generated
* @return an estimate of <b>P</b>(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++) {
// <b>x</b>,w <- WEIGHTED-SAMPLE(bn,e)
Pair<Map<RandomVariable, Object>, Double> x_w = weightedSample(bn,
e);
// W[x] <- W[x] + w where x is the value of X in <b>x</b>
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
* <b>P</b>(X<sub>1</sub>,...,X<sub>n</sub>)
* @return return <b>x</b>, w - an event with its associated weight.
*/
public Pair<Map<RandomVariable, Object>, Double> weightedSample(
BayesianNetwork bn, AssignmentProposition[] e) {
// w <- 1;
double w = 1.0;
// <b>x</b> <- an event with n elements initialized from e
Map<RandomVariable, Object> x = new LinkedHashMap<RandomVariable, Object>();
for (AssignmentProposition ap : e) {
x.put(ap.getTermVariable(), ap.getValue());
}
// foreach variable X<sub>i</sub> in X<sub>1</sub>,...,X<sub>n</sub> do
for (RandomVariable Xi : bn.getVariablesInTopologicalOrder()) {
// if X<sub>i</sub> is an evidence variable with value x<sub>i</sub>
// in e
if (x.containsKey(Xi)) {
// then w <- w * P(X<sub>i</sub> = x<sub>i</sub> |
// parents(X<sub>i</sub>))
w *= bn.getNode(Xi)
.getCPD()
.getValue(
ProbUtil.getEventValuesForXiGivenParents(
bn.getNode(Xi), x));
} else {
// else <b>x</b>[i] <- a random sample from
// <b>P</b>(X<sub>i</sub> | parents(X<sub>i</sub>))
x.put(Xi, ProbUtil.randomSample(bn.getNode(Xi), x, randomizer));
}
}
// return <b>x</b>, w
return new Pair<Map<RandomVariable, Object>, 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
//
}