/
RejectionSampling.java
115 lines (103 loc) · 3.3 KB
/
RejectionSampling.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
package aima.core.probability.bayes.approx;
import java.util.Map;
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;
/**
* Artificial Intelligence A Modern Approach (3rd Edition): page 533.<br>
* <br>
*
* <pre>
* function REJECTION-SAMPLING(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
* N, the total number of samples to be generated
* local variables: <b>N</b>, a vector of counts for each value of X, initially zero
*
* for j = 1 to N do
* <b>x</b> <- PRIOR-SAMPLE(bn)
* if <b>x</b> is consistent with e then
* <b>N</b>[x] <- <b>N</b>[x] + 1 where x is the value of X in <b>x</b>
* return NORMALIZE(<b>N</b>)
* </pre>
*
* Figure 14.14 The rejection-sampling algorithm for answering queries given
* evidence in a Bayesian Network.<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 RejectionSampling implements BayesSampleInference {
private PriorSample ps = null;
public RejectionSampling() {
this(new PriorSample());
}
public RejectionSampling(PriorSample ps) {
this.ps = ps;
}
// function REJECTION-SAMPLING(X, e, bn, N) returns an estimate of
// <b>P</b>(X|e)
/**
* The REJECTION-SAMPLING algorithm in Figure 14.14. 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
* @param Nsamples
* the total number of samples to be generated
* @return an estimate of <b>P</b>(X|e)
*/
public CategoricalDistribution rejectionSampling(RandomVariable[] X,
AssignmentProposition[] e, BayesianNetwork bn, int Nsamples) {
// local variables: <b>N</b>, a vector of counts for each value of X,
// initially zero
double[] N = new double[ProbUtil
.expectedSizeOfCategoricalDistribution(X)];
// for j = 1 to N do
for (int j = 0; j < Nsamples; j++) {
// <b>x</b> <- PRIOR-SAMPLE(bn)
Map<RandomVariable, Object> x = ps.priorSample(bn);
// if <b>x</b> is consistent with e then
if (isConsistent(x, e)) {
// <b>N</b>[x] <- <b>N</b>[x] + 1
// where x is the value of X in <b>x</b>
N[ProbUtil.indexOf(X, x)] += 1.0;
}
}
// return NORMALIZE(<b>N</b>)
return new ProbabilityTable(N, X).normalize();
}
//
// START-BayesSampleInference
@Override
public CategoricalDistribution ask(final RandomVariable[] X,
final AssignmentProposition[] observedEvidence,
final BayesianNetwork bn, int N) {
return rejectionSampling(X, observedEvidence, bn, N);
}
// END-BayesSampleInference
//
//
// PRIVATE METHODS
//
private boolean isConsistent(Map<RandomVariable, Object> x,
AssignmentProposition[] e) {
for (AssignmentProposition ap : e) {
if (!ap.getValue().equals(x.get(ap.getTermVariable()))) {
return false;
}
}
return true;
}
}