/
Factory.scala
373 lines (346 loc) · 17.1 KB
/
Factory.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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
/*
* Factory.scala
* Methods to create factors over variables.
*
* 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
*
* Paul Philips May 23, 2017
*/
package com.cra.figaro.algorithm.factored.factors.factory
import com.cra.figaro.algorithm._
import com.cra.figaro.language._
import com.cra.figaro.util._
import com.cra.figaro.algorithm.lazyfactored._
import com.cra.figaro.algorithm.lazyfactored.ValueSet._
import com.cra.figaro.algorithm.factored._
import com.cra.figaro.algorithm.factored.factors._
import com.cra.figaro.library.compound._
import com.cra.figaro.library.collection._
import com.cra.figaro.library.atomic.discrete._
import com.cra.figaro.algorithm.structured._
import scala.reflect.runtime.universe.{typeTag, TypeTag}
/**
* Methods for creating probabilistic factors associated with elements.
*/
object Factory {
/**
* Get the variable associated with the given element in the given component collection.
* If the element does not exist in the component collection, an intermediate variable is created whose range is { Star }.
*/
def getVariable[T](cc: ComponentCollection, element: Element[T]): Variable[T] = {
if (cc.contains(element)) {
val component = cc(element)
component.variable
} else {
makeVariable(cc, withStar(Set[T]()))
}
}
/**
* Create an intermediate variable in the given component collection with the given value set.
*/
def makeVariable[T](cc: ComponentCollection, valueSet: ValueSet[T]): Variable[T] = {
val v = new Variable(valueSet)
cc.intermediates += v
v
}
def makeVariable[T](cc: ComponentCollection, valueSet: ValueSet[T], chain: Chain[_, _]): Variable[T] = {
val v = new InternalChainVariable(valueSet, chain, getVariable(cc, chain))
cc.intermediates += v
v
}
/**
* Create a new factor in which one variable is replaced with another.
*/
def replaceVariable[T](factor: Factor[Double], oldVariable: Variable[T], newVariable: Variable[T]): Factor[Double] = {
if (oldVariable.range != newVariable.range) throw new IllegalArgumentException("Replacing variable with variable with different range")
if (!factor.variables.contains(oldVariable)) factor
else {
val newVariables = factor.variables.map(v => if (v == oldVariable) newVariable else v)
val newFactor =
factor match {
case s: SparseFactor[Double] => new SparseFactor[Double](newVariables, List())
case b: DenseFactor[Double] => new DenseFactor[Double](newVariables, List())
}
for { indices <- factor.getIndices } { newFactor.set(indices, factor.get(indices)) }
newFactor
}
}
/**
* The mutliplicative identity factor.
*/
def unit[T: TypeTag](semiring: Semiring[T]): Factor[T] = {
val result = new DenseFactor[T](List(), List(), semiring)
result.set(List(), semiring.one)
result
}
/**
* Given a sequence of variables, create a new variable representing the tuple of the inputs
* and create the factor mapping the inputs to their tuple.
* @param inputs the variables to be formed into a tuple
*/
def makeTupleVarAndFactor(cc: ComponentCollection, chain: Option[Chain[_, _]], inputs: Variable[_]*): (Variable[List[Extended[_]]], Factor[Double]) = {
val inputList: List[Variable[_]] = inputs.toList
// Subtlety alert: In the tuple, we can't just map inputs with * to *. We need to remember which input was *.
// Therefore, instead, we make the value a regular value consisting of a list of extended values.
val tupleRangeRegular: List[List[_]] = cartesianProduct(inputList.map(_.range): _*)
val tupleVS: ValueSet[List[Extended[_]]] = withoutStar(tupleRangeRegular.map(_.asInstanceOf[List[Extended[_]]]).toSet)
val tupleVar: Variable[List[Extended[_]]] = if (chain.nonEmpty) Factory.makeVariable(cc, tupleVS, chain.get) else Factory.makeVariable(cc, tupleVS)
val tupleFactor = new SparseFactor[Double](inputList, List(tupleVar))
for { pair <- tupleVar.range.zipWithIndex } {
val tupleVal: List[Extended[_]] = pair._1.value
val tupleIndex = pair._2
val inputIndices =
for { (input, value) <- inputList.zip(tupleVal) } yield input.range.indexOf(value)
tupleFactor.set(inputIndices ::: List(tupleIndex), 1.0)
}
(tupleVar, tupleFactor)
}
/**
* Create a DenseFactor from the supplied parent and children variables
*/
def defaultFactor[T: TypeTag](parents: List[Variable[_]], children: List[Variable[_]], _semiring: Semiring[T] = SumProductSemiring().asInstanceOf[Semiring[T]]) =
new DenseFactor[T](parents, children, _semiring)
private def makeFactors[T](cc: ComponentCollection, const: Constant[T]): List[Factor[Double]] = {
val factor = new DenseFactor[Double](List(), List(getVariable(cc, const)))
factor.set(List(0), 1.0)
List(factor)
}
/*
* The conditional selector creates a factor in which, when the selector's value is such that the result
* element is relevant to the final result, the result element and overall element must have the same
* value (handled by makeCares). Otherwise, the result element and overall element can take on any
* value (handled by makeDontCares)
*/
/**
* Make a conditional selector factor used in the decomposition of chain and other elements.
* A chain defines a factor over the parent element, each of the possible result elements of the chain,
* and the overall chain element. This can produce a very large factor when there are many result elements.
* This is solved by decomposing the chain factor into a product of factors, each of which contains the
* parent element, one of the result elements, and the overall chain element.
*/
def makeConditionalSelector[T, U](pairVar: Variable[List[Extended[_]]], parentXVal: Extended[T], outcomeVar: Variable[U], choices: Set[U])(implicit mapper: PointMapper[U]): Factor[Double] = {
val factor = new ConditionalSelector[Double](List(pairVar), List(outcomeVar))
for {
(pairXVal, pairIndex) <- pairVar.range.zipWithIndex
(outcomeXVal, outcomeIndex) <- outcomeVar.range.zipWithIndex
} {
// See makeTupleVarAndFactor: pairXVal is always regular and consists of a list of two elements: the extended parent value
// and the extended outcome value.
val List(selectXVal, overallXVal) = pairXVal.value
val entry =
if (selectXVal.isRegular && parentXVal.isRegular) {
if (selectXVal.value == parentXVal.value) {
if ((!overallXVal.isRegular && !outcomeXVal.isRegular) || (overallXVal.isRegular && outcomeXVal.isRegular && overallXVal.value == mapper.map(outcomeXVal.value, choices))) 1.0 else 0.0
} else 1.0
} else if (selectXVal.isRegular || parentXVal.isRegular) 1.0 // they are different
else if (!overallXVal.isRegular) 1.0 // if parentXVal is *, the only possible outcomeXVal is *
else 0.0
factor.set(List(pairIndex, outcomeIndex), entry)
}
factor
}
private def isTemporary[_T](variable: Variable[_]): Boolean = {
variable match {
case e: ElementVariable[_] => e.element.isTemporary
case _ => false
}
}
private def makeFactors[T](cc: ComponentCollection, inject: Inject[T]): List[Factor[Double]] = {
def rule(values: List[Extended[_]]) = {
val inputXvalues :+ resultXvalue = values
// See logic under makeCares
if (inputXvalues.exists(!_.isRegular)) {
if (!resultXvalue.isRegular) 1.0; else 0.0
} else if (resultXvalue.isRegular) {
if (resultXvalue.value.asInstanceOf[List[T]] == inputXvalues.map(_.value.asInstanceOf[T])) 1.0; else 0.0
} else 0.0
}
val inputVariables = inject.args map (getVariable(cc, _))
val resultVariable = getVariable(cc, inject)
// val variables = resultVariable :: inputVariables
val factor = new DenseFactor[Double](inputVariables, List(resultVariable))
factor.fillByRule(rule _)
List(factor)
}
// When we're using a parameter to compute expected sufficient statistics, we just use its expected value
private def makeParameterFactors(cc: ComponentCollection, param: Parameter[_]): List[Factor[Double]] = {
// The parameter should have one possible value, which is its expected value
val paramVar = getVariable(cc, param)
assert(paramVar.range.size == 1)
val factor = new DenseFactor[Double](List(), List(paramVar))
factor.set(List(0), 1.0)
List(factor)
}
private def makeFactors[T](cc: ComponentCollection, atomic: Atomic[T]): List[Factor[Double]] = {
val atomicVar = getVariable(cc, atomic)
val atomicComp = cc(atomic)
// Map each extended value to its probability density, preserving the order of the list
val probs = atomicVar.range.map(atomicComp.probs)
List(SelectFactory.makeSimpleDistribution(atomicVar, probs))
}
def parameterCheck(elem: Element[_], parameterized: Boolean): Boolean = {
elem match {
case parameter: DoubleParameter => parameterized
case _ => false
}
}
/**
* Invokes Factor constructors for a standard set of Elements. This method uses various
* secondary factories.
*/
def concreteFactors[T](cc: ComponentCollection, elem: Element[T], parameterized: Boolean): List[Factor[Double]] = {
// TODO have factor creation for all atomics use the new method above
elem match {
case flip: ParameterizedFlip => DistributionFactory.makeFactors(cc, flip, parameterized)
case pSelect: ParameterizedSelect[_] => SelectFactory.makeFactors(cc, pSelect, parameterized)
case pBin: ParameterizedBinomialFixedNumTrials => DistributionFactory.makeFactors(cc, pBin, parameterized)
case parameter: DoubleParameter if parameterized => makeParameterFactors(cc, parameter)
case array: ArrayParameter if parameterized => makeParameterFactors(cc, array)
case constant: Constant[_] => makeFactors(cc, constant)
case f: AtomicFlip => DistributionFactory.makeFactors(cc, f)
case f: CompoundFlip => DistributionFactory.makeFactors(cc, f)
case ab: AtomicBinomial => DistributionFactory.makeFactors(cc, ab)
case s: AtomicSelect[_] => SelectFactory.makeFactors(cc, s)
case s: CompoundSelect[_] => SelectFactory.makeFactors(cc, s)
case d: AtomicDist[_] => SelectFactory.makeFactors(cc, d)
case d: CompoundDist[_] => SelectFactory.makeFactors(cc, d)
case s: IntSelector => SelectFactory.makeFactors(cc, s)
case c: Chain[_, _] => ChainFactory.makeFactors(cc, c)
case b: BooleanOperator => ApplyFactory.makeBooleanFactors(cc, b)
case a: Apply1[_, _] => ApplyFactory.makeFactors(cc, a)
case a: Apply2[_, _, _] => ApplyFactory.makeFactors(cc, a)
case a: Apply3[_, _, _, _] => ApplyFactory.makeFactors(cc, a)
case a: Apply4[_, _, _, _, _] => ApplyFactory.makeFactors(cc, a)
case a: Apply5[_, _, _, _, _, _] => ApplyFactory.makeFactors(cc, a)
case i: Inject[_] => makeFactors(cc, i)
case r: SingleValuedReferenceElement[_] => ComplexFactory.makeFactors(cc, r)
case r: MultiValuedReferenceElement[_] => ComplexFactory.makeFactors(cc, r)
case r: Aggregate[_, _] => ComplexFactory.makeFactors(cc, r)
//case m: MakeList[_] => ComplexFactory.makeFactors(cc, m)
case m: MakeArray[_] => ComplexFactory.makeFactors(cc, m)
case f: FoldLeft[_, _] => ComplexFactory.makeFactors(cc, f)
case f: FactorMaker[_] => f.makeFactors
case a: Atomic[_] => makeFactors(cc, a)
case _ => throw new UnsupportedAlgorithmException(elem)
}
}
private def makeAbstract[T](cc: ComponentCollection, atomic: Atomic[T], abstraction: Abstraction[T]): List[Factor[Double]] = {
val variable = getVariable(cc, atomic)
assert(!variable.valueSet.hasStar, "can't make abstract factors with *")
val values = variable.range.map(_.value)
val densityMap = scala.collection.mutable.Map[T, Double]()
for { v <- values } {
val currentDensity = densityMap.getOrElse(v, 0.0)
densityMap.update(v, currentDensity + atomic.density(v))
}
val factor = new DenseFactor[Double](List(), List(variable))
for { (v, i) <- values.zipWithIndex } {
factor.set(List(i), densityMap(v))
}
List(factor)
}
private def makeAbstract[T](cc: ComponentCollection, elem: Element[T], abstraction: Abstraction[T]): List[Factor[Double]] =
elem match {
case apply: Apply1[_, _] => ApplyFactory.makeFactors(cc, apply)(abstraction.scheme)
case apply: Apply2[_, _, _] => ApplyFactory.makeFactors(cc, apply)(abstraction.scheme)
case apply: Apply3[_, _, _, _] => ApplyFactory.makeFactors(cc, apply)(abstraction.scheme)
// In the case of a Chain, its pragmas are inherited by the expanded result elements. The abstraction will be
// taken into account when we generate factors for the result elements.
case chain: Chain[_, _] => ChainFactory.makeFactors(cc, chain)(abstraction.scheme)
case atomic: Atomic[_] => makeAbstract(cc, atomic, abstraction)
case _ => throw new UnsupportedAlgorithmException(elem)
}
/**
* Make the non-constraint factors corresponding to the given element in the component collection.
*
* @param parameterized If true, parameterized elements are assumed to be equal to their previously computed MAP value. If false, they are treated like any other element.
*/
def makeFactors[T](cc: ComponentCollection, elem: Element[T], parameterized: Boolean): List[Factor[Double]] = {
val component = cc(elem)
if (component.range.hasStar && component.range.regularValues.isEmpty) List()
else {
Abstraction.fromPragmas(elem.pragmas) match {
case None => concreteFactors(cc, elem, parameterized)
case Some(abstraction) => makeAbstract(cc, elem, abstraction)
}
}
}
/**
* Create the probabilistic factor encoding the probability of evidence in the dependent universe as a function of the
* values of variables in the parent universe. The third argument is the the function to use for computing
* probability of evidence in the dependent universe. It is assumed that the definition of this function will already contain the
* right evidence.
*/
def makeDependentFactor(cc: ComponentCollection, parentUniverse: Universe,
dependentUniverse: Universe,
probEvidenceComputer: () => Double): Factor[Double] = {
val uses = dependentUniverse.parentElements filter (_.universe == parentUniverse)
def rule(values: List[Any]) = {
for { (elem, value) <- uses zip values } { elem.value = value.asInstanceOf[Regular[elem.Value]].value }
val result = probEvidenceComputer()
result
}
val variables = uses map (cc(_).variable)
val factor = new DenseFactor[Double](variables, List())
factor.fillByRule(rule _)
factor
}
/**
* Make factors for a particular element. This function wraps the SFI method of creating factors using component collections
*/
def makeFactorsForElement[Value](elem: Element[_], upper: Boolean = false, parameterized: Boolean = false) = {
val variable = Variable(elem)
val comp = Variable.cc(elem)
if (elem.intervention.isDefined) {
val factor = new DenseFactor[Double](List(), List(variable))
factor.set(List(0), 1.0)
List(factor)
}
else {
comp match {
// If the element is a chain, we need to create subproblems for each value of the chain
// to create factors accordingly
case chainComp: ChainComponent[_, _] =>
val chain = chainComp.chain
val chainMap = LazyValues(elem.universe).getMap(chain)
chainMap.foreach(f => {
val subproblem = new NestedProblem(Variable.cc, f._2)
Variable.cc.expansionToProblem += ((chain.chainFunction, f._1), 0) -> subproblem
chainComp.subproblems = chainComp.subproblems.updated(f._1, subproblem)
})
// If the element is a MakeArray, we need mark that it has been expanded. Note that
// the normal Values call will expand the MakeArray, we are just setting the max expansion here
case maComp: MakeArrayComponent[_] =>
val ma = maComp.makeArray
maComp.maxExpanded = Variable.cc(ma.numItems).range.regularValues.max
// If the element is an apply, we need to populate the Apply map used by the factor creation
case applyComp: ApplyComponent[Value] =>
val apply = applyComp.apply
val applyMap = LazyValues(elem.universe).getMap(apply)
applyComp.setMap(applyMap)
case atomicComp: AtomicComponent[Value] =>
// The range for this component was generated, but not its distribution
// This computes the probability mass for each value in the range
atomicComp.probs = atomicComp.ranger.discretize()
case _ => ()
}
// Make the constraint and non-constraint factors for the element by calling the
// component factor makers
val constraint = if (upper) {
comp.constraintFactors(Upper)
} else {
comp.constraintFactors(Lower)
}
constraint ::: comp.nonConstraintFactors(parameterized)
}
}
}