Sum-Product Algorithms

partial_unroll(factors, eliminate=frozenset(), plate_to_step={})

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.

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

Performs partial sum-product contraction of a collection of factors.

Returns:a list of partially contracted Funsors. Return type:list

modified_partial_sum_product(sum_op, prod_op, factors, eliminate=frozenset(), plate_to_step={})

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.

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.

mixed_sequential_sum_product(sum_op, prod_op, trans, time, step, num_segments=None)

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

sarkka_bilmes_product(sum_op, prod_op, trans, time_var, global_vars=frozenset(), num_periods=1)

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)