Sum-Product Algorithms

partial_sum_product(sum_op, prod_op, factors, eliminate=frozenset(), plates=frozenset())

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())

Performs sum-product contraction of a collection of factors.

Returns:a single contracted Funsor. Return type:Funsor

naive_sequential_sum_product(sum_op, prod_op, trans, time, step)

sequential_sum_product(sum_op, prod_op, trans, time, step)

For a funsor trans with dimensions time, prev and curr, 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)

Bases: funsor.terms.FunsorMeta

Wrapper to convert step to a tuple and fill in default step_names.

class MarkovProduct(sum_op, prod_op, trans, time, step, step_names)

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 of trans.
• step_names (dict) – Optional, for internal use by alpha conversion.

eager_subs(subs)

eager_markov_product(sum_op, prod_op, trans, time, step, step_names)