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
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({}), pedantic=False, pow_op=None, plate_to_scale=None)[source]¶
Performs partial sum-product contraction of a collection of factors.
- Returns
a list of partially contracted Funsors.
- Return type
- 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 higer-order markov dimensions in addition to plate dimensions. Markov dimensions in transition factors are eliminated efficiently using the parallel-scan 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.
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 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.
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({}), pedantic=False, pow_op=None, plate_to_scale=None)[source]¶
Performs sum-product contraction of a collection of factors.
- Returns
a single contracted Funsor.
- Return type
- 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:
FunsorMeta
Wrapper to convert
step
to a tuple and fill in defaultstep_names
.
- class MarkovProduct(sum_op, prod_op, trans, time, step, step_names=None)[source]¶
Bases:
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.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.