SumProduct 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 indexi
in the plate (e.g., “x”>”x_0” for i=0). For markov dimensions (history=1) unrolling operation renames the suffixesvar_prev
tovar_{i}
andvar_curr
tovar_{i+1}
for indexi
(e.g., “x_prev”>”x_0” and “x_curr”>”x_1” for i=0). Markov vars are assumed to have names that followvar_suffix
formatting and specificallyvar_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 emptystep
.
Returns: 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 sumproduct contraction of a collection of factors.
Returns: a list of partially contracted Funsors. Return type: list

dynamic_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 higerorder markov dimensions in addition to plate dimensions. Markov dimensions in transition factors are eliminated efficiently using the parallelscan algorithm infunsor.sum_product.sarkka_bilmes_product()
. The resulting factors are then combined with the initial factors and final states are eliminated. Therefore, when Markov dimension is eliminatedfactors
has to contain 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 emptystep
.
Returns: a list of partially contracted Funsors.
Return type:

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 parallelscan algorithm infunsor.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 eliminatedfactors
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 emptystep
.
Returns: a list of partially contracted Funsors.
Return type:

sum_product
(sum_op, prod_op, factors, eliminate=frozenset(), plates=frozenset())[source]¶ Performs sumproduct 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.

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

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 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 strtostr mapping of “previous” inputs of
trans
to “current” inputs oftrans
.  step_names (dict) – Optional, for internal use by alpha conversion.