# Sum-Product Algorithms¶

`partial_unroll`(factors, eliminate=frozenset(), plate_to_step={})[source]

Performs partial unrolling of plated factor graphs to standard factor graphs. Only plates with history={0, 1} are supported.

For plates (history=0) unrolling operation appends `_{i}` suffix to variable names for index `i` in the plate (e.g., “x”->”x_0” for i=0). For markov dimensions (history=1) unrolling operation renames the suffixes `var_prev` to `var_{i}` and `var_curr` to `var_{i+1}` for index `i` (e.g., “x_prev”->”x_0” and “x_curr”->”x_1” for i=0). Markov vars are assumed to have names that follow `var_suffix` formatting and specifically `var_0` for the initial factor (e.g., `("x_0", "x_prev", "x_curr")` for history=1).

Parameters: factors (tuple or list) – A collection of funsors. eliminate (frozenset) – A set of free variables to unroll, including both sum variables and product variable. plate_to_step (dict) – A dict mapping markov dimensions to `step` collections that contain ordered sequences of Markov variable names (e.g., `{"time": frozenset({("x_0", "x_prev", "x_curr")})}`). Plates are passed with an empty `step`. a list of partially unrolled Funsors, a frozenset of partially unrolled variable names, and a frozenset of remaining plates.
`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. list
`modified_partial_sum_product`(sum_op, prod_op, factors, eliminate=frozenset(), plate_to_step={})[source]

Generalization of the tensor variable elimination algorithm of `funsor.sum_product.partial_sum_product()` to handle markov dimensions in addition to plate dimensions. Markov dimensions in transition factors are eliminated efficiently using the parallel-scan algorithm in `funsor.sum_product.sequential_sum_product()`. The resulting factors are then combined with the initial factors and final states are eliminated. Therefore, when Markov dimension is eliminated `factors` has to contain a pairs of initial factors and transition factors.

Parameters: sum_op (AssociativeOp) – A semiring sum operation. prod_op (AssociativeOp) – A semiring product operation. factors (tuple or list) – A collection of funsors. eliminate (frozenset) – A set of free variables to eliminate, including both sum variables and product variable. plate_to_step (dict) – A dict mapping markov dimensions to `step` collections that contain ordered sequences of Markov variable names (e.g., `{"time": frozenset({("x_0", "x_prev", "x_curr")})}`). Plates are passed with an empty `step`. a list of partially contracted Funsors. 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. `Funsor`
`naive_sequential_sum_product`(sum_op, prod_op, trans, time, step)[source]
`sequential_sum_product`(sum_op, prod_op, trans, time, step)[source]

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.
`mixed_sequential_sum_product`(sum_op, prod_op, trans, time, step, num_segments=None)[source]

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")
```

by mixing parallel and serial scan algorithms over `num_segments` segments.

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. num_segments (int) – number of segments for the first stage
`naive_sarkka_bilmes_product`(sum_op, prod_op, trans, time_var, global_vars=frozenset())[source]
`sarkka_bilmes_product`(sum_op, prod_op, trans, time_var, global_vars=frozenset(), num_periods=1)[source]
class `MarkovProductMeta`(name, bases, dct)[source]

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)[source]

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)[source]
`eager_markov_product`(sum_op, prod_op, trans, time, step, step_names)[source]