/
ProbQueryAlgorithm.scala
207 lines (173 loc) · 6.83 KB
/
ProbQueryAlgorithm.scala
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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
/*
* ProbQueryAlgorithm.scala
* Algorithms that compute conditional probabilities of queries.
*
* Created By: Avi Pfeffer (apfeffer@cra.com)
* Creation Date: Jan 1, 2009
*
* Copyright 2017 Avrom J. Pfeffer and Charles River Analytics, Inc.
* See http://www.cra.com or email figaro@cra.com for information.
*
* See http://www.github.com/p2t2/figaro for a copy of the software license.
*/
/*
* Additional Updates from our community
*
* Cagdas Senol Jul 3, 2016
* Cagdas Senol Jul 16, 2016
*/
package com.cra.figaro.algorithm
import com.cra.figaro.language._
import scala.language.higherKinds
/**
* Algorithms that compute conditional probabilities of queries over elements in a universe.
*/
trait ProbQueryAlgorithm extends BaseProbQueryAlgorithm[Element] {
val universe: Universe
/**
* Return an element representing the posterior probability distribution of the given element.
*/
def posteriorElement[T](target: Element[T], universe: Universe = Universe.universe): Element[T] = {
Select(distribution(target).toList:_*)("", universe)
}
universe.registerAlgorithm(this)
}
/**
* Algorithms that compute conditional probabilities of queries. This is a base trait, to provide
* support for both elements in a single universe, or references across multiple universes.
* Generic type U is either an Element or a Reference. T is the type of the element or reference.
*/
trait BaseProbQueryAlgorithm[U[_]]
extends Algorithm {
class NotATargetException[T](target: U[T]) extends AlgorithmException
/*
* @param targets List of elements that can be queried after running the algorithm.
*/
val queryTargets: Seq[U[_]]
/*
* Particular implementations of algorithm must provide the following two methods.
*/
/**
* Return an estimate of the marginal probability distribution over the target that lists each element
* with its probability. The result is a lazy stream. It is up to the algorithm how the stream is
* ordered.
*/
def computeDistribution[T](target: U[T]): Stream[(Double, T)]
/**
* Return an estimate of the expectation of the function under the marginal probability distribution
* of the target.
*/
def computeExpectation[T](target: U[T], function: T => Double): Double
/**
* Return an estimate of the probability of the predicate under the marginal probability distribution
* of the target.
*/
def computeProbability[T](target: U[T], predicate: T => Boolean): Double = {
computeExpectation(target, (t: T) => if (predicate(t)) 1.0; else 0.0)
}
protected[algorithm] def computeProjection[T](target: U[T]): List[(T, Double)] = {
projectDistribution(computeDistribution(target))
}
private def projectDistribution[T](distribution: Stream[(Double, T)]): List[(T, Double)] = {
(distribution map (_.swap)).toList
}
/*
* The following methods are defined in either the onetime or anytime versions of this class,
* and do not need to be defined by particular algorithm implementations.
*/
protected def doDistribution[T](target: U[T]): Stream[(Double, T)]
protected def doExpectation[T](target: U[T], function: T => Double): Double
protected def doProbability[T](target: U[T], predicate: T => Boolean): Double
protected def doProjection[T](target: U[T]): List[(T, Double)] = {
projectDistribution(doDistribution(target))
}
protected def check[T](target: U[T]): Unit = {
if (!active) throw new AlgorithmInactiveException
if (!(queryTargets contains target)) throw new NotATargetException(target)
}
/**
* Return an estimate of the marginal probability distribution over the target that lists each element
* with its probability. The result is a lazy stream. It is up to the algorithm how the stream is
* ordered.
* Throws NotATargetException if called on a target that is not in the list of
* targets of the algorithm.
* Throws AlgorithmInactiveException if the algorithm is inactive.
*/
def distribution[T](target: U[T]): Stream[(Double, T)] = {
check(target)
doDistribution(target)
}
/**
* Return an estimate of the expectation of the function under the marginal probability distribution
* of the target.
* Throws NotATargetException if called on a target that is not in the list of
* targets of the algorithm.
* Throws AlgorithmInactiveException if the algorithm is inactive.
*/
def expectation[T](target: U[T], function: T => Double): Double = {
check(target)
doExpectation(target, function)
}
/**
* Return an estimate of the expectation of the function under the marginal probability distribution
* of the target.
* Throws NotATargetException if called on a target that is not in the list of
* targets of the algorithm.
* Throws AlgorithmInactiveException if the algorithm is inactive.
*/
def expectation[T](target: U[T])(function: T => Double, c: Any = DummyImplicit): Double = {
check(target)
doExpectation(target, function)
}
/**
* Return the mean of the probability density function for the given continuous element.
*/
def mean(target: U[Double]): Double = {
expectation(target, (d: Double) => d)
}
/**
* Return the variance of the probability density function for the given continuous element.
*/
def variance(target: U[Double]): Double = {
val m = mean(target)
val ex2 = expectation(target, (d: Double) => d * d)
ex2 - m*m
}
/**
* Return an estimate of the probability of the predicate under the marginal probability distribution
* of the target.
* Throws NotATargetException if called on a target that is not in the list of
* targets of the algorithm.
* Throws AlgorithmInactiveException if the algorithm is inactive.
*/
def probability[T](target: U[T], predicate: T => Boolean): Double = {
check(target)
doProbability(target, predicate)
}
/**
* Return an estimate of the probability of the predicate under the marginal probability distribution
* of the target.
* Throws NotATargetException if called on a target that is not in the list of
* targets of the algorithm.
* Throws AlgorithmInactiveException if the algorithm is inactive.
*/
def probability[T](target: U[T])(predicate: T => Boolean, c: Any = DummyImplicit): Double = {
probability(target, predicate)
}
/**
* Return an estimate of the probability that the target produces the value.
* Throws NotATargetException if called on a target that is not in the list of
* targets of the algorithm.
* Throws AlgorithmInactiveException if the algorithm is inactive.
*/
def probability[T](target: U[T], value: T): Double = {
check(target)
doProbability(target, (t: T) => t == value)
}
}
trait StreamableProbQueryAlgorithm extends ProbQueryAlgorithm {
/**
* Sample an value from the posterior of this element
*/
def sampleFromPosterior[T](element: Element[T]): Stream[T]
}