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

dynamic_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 higer-order markov dimensions in addition to plate dimensions. Markov dimensions in transition factors are eliminated efficiently using the parallel-scan algorithm in funsor.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 eliminated factors 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 empty step.

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)