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