Sum-Product Algorithms¶
-
partial_sum_product
(sum_op, prod_op, factors, eliminate=frozenset(), plates=frozenset())[source]¶ Performs partial sum-product contraction of a collection of factors.
Returns: a list of partially contracted Funsors. Return type: list
-
sum_product
(sum_op, prod_op, factors, eliminate=frozenset(), plates=frozenset())[source]¶ Performs sum-product contraction of a collection of factors.
Returns: a single contracted Funsor. Return type: Funsor
-
sequential_sum_product
(sum_op, prod_op, trans, time, step)[source]¶ For a funsor
trans
with dimensionstime
,prev
andcurr
, computes a recursion equivalent to:tail_time = 1 + arange("time", trans.inputs["time"].size - 1) tail = sequential_sum_product(sum_op, prod_op, trans(time=tail_time), time, {"prev": "curr"}) return prod_op(trans(time=0)(curr="drop"), tail(prev="drop")) .reduce(sum_op, "drop")
but does so efficiently in parallel in O(log(time)).
Parameters: - sum_op (AssociativeOp) – A semiring sum operation.
- prod_op (AssociativeOp) – A semiring product operation.
- trans (Funsor) – A transition funsor.
- time (Variable) – The time input dimension.
- step (dict) – A dict mapping previous variables to current variables. This can contain multiple pairs of prev->curr variable names.
-
class
MarkovProductMeta
(name, bases, dct)[source]¶ Bases:
funsor.terms.FunsorMeta
Wrapper to convert
step
to a tuple and fill in defaultstep_names
.
-
class
MarkovProduct
(sum_op, prod_op, trans, time, step, step_names)[source]¶ Bases:
funsor.terms.Funsor
Lazy representation of
sequential_sum_product()
.Parameters: - sum_op (AssociativeOp) – A marginalization op.
- prod_op (AssociativeOp) – A Bayesian fusion op.
- trans (Funsor) – A sequence of transition factors,
usually varying along the
time
input. - time (str or Variable) – A time dimension.
- step (dict) – A str-to-str mapping of “previous” inputs of
trans
to “current” inputs oftrans
. - step_names (dict) – Optional, for internal use by alpha conversion.