quimb.tensor.belief_propagation.hv1bp¶

Hyper, vectorized, 1-norm, belief propagation.

Classes¶

HV1BP

Object interface for hyper, vectorized, 1-norm, belief propagation. This

Functions¶

`_compute_all_hyperind_messages_tree_batched`(bm)
`_compute_all_hyperind_messages_prod_batched`(bm[, ...])
`_compute_all_tensor_messages_tree_batched`(bx, bm)	Compute all output messages for a stacked tensor and messages.
`_compute_all_tensor_messages_prod_batched`(bx, bm[, ...])
`_compute_output_single_t`(bm, bx, normalize[, ...])
`_compute_output_single_m`(bm, normalize[, smudge_factor])
`_update_output_to_input_single_batched`(batched_input, ...)
`_gather_zb`(zb[, power])	Given a vector of local contraction estimates zb, compute their
`_contract_index_region_single`(bm)
`_contract_tensor_region_single`(rank, batched_tensors, ...)
`_contract_messages_pair_single`(ranki, ranko, mask, ...)
`_extract_messages_from_inputs_batched`(...)	Get all messages as a dict from the batch stacked input form.
`contract_hv1bp`(tn[, messages, max_iterations, tol, ...])	Estimate the contraction of `tn` with hyper, vectorized, 1-norm
`run_belief_propagation_hv1bp`(tn[, messages, ...])	Run belief propagation on a tensor network until it converges.
`sample_hv1bp`(tn[, messages, output_inds, ...])	Sample all indices of a tensor network using repeated belief propagation

Module Contents¶

quimb.tensor.belief_propagation.hv1bp._compute_all_hyperind_messages_tree_batched(bm)¶

quimb.tensor.belief_propagation.hv1bp._compute_all_hyperind_messages_prod_batched(bm, smudge_factor=1e-12)¶

quimb.tensor.belief_propagation.hv1bp._compute_all_tensor_messages_tree_batched(bx, bm)¶: Compute all output messages for a stacked tensor and messages.

quimb.tensor.belief_propagation.hv1bp._compute_all_tensor_messages_prod_batched(bx, bm, smudge_factor=1e-12)¶

quimb.tensor.belief_propagation.hv1bp._compute_output_single_t(bm, bx, normalize, smudge_factor=1e-12)¶

quimb.tensor.belief_propagation.hv1bp._compute_output_single_m(bm, normalize, smudge_factor=1e-12)¶

quimb.tensor.belief_propagation.hv1bp._update_output_to_input_single_batched(batched_input, batched_output, mask, _distance_fn, damping=0.0)¶

quimb.tensor.belief_propagation.hv1bp._gather_zb(zb, power=1.0)¶

Given a vector of local contraction estimates zb, compute their product, avoiding underflow/overflow by accumulating the sign and exponent separately.

Parameters:

zb (array) – The local contraction estimates.
power (float, optional) – Raise the final result to this power.

Returns:

sign (float) – The accumulated sign or phase.
exponent (float) – The accumulated exponent.

quimb.tensor.belief_propagation.hv1bp._contract_index_region_single(bm)¶

quimb.tensor.belief_propagation.hv1bp._contract_tensor_region_single(rank, batched_tensors, batched_inputs_t)¶

quimb.tensor.belief_propagation.hv1bp._contract_messages_pair_single(ranki, ranko, mask, batched_inputs_m, batched_inputs_t)¶

quimb.tensor.belief_propagation.hv1bp._extract_messages_from_inputs_batched(batched_inputs_m, batched_inputs_t, input_locs_m, input_locs_t)¶: Get all messages as a dict from the batch stacked input form.

class quimb.tensor.belief_propagation.hv1bp.HV1BP(tn, *, messages=None, damping=0.0, update='parallel', normalize='L2', distance='L2', smudge_factor=1e-12, thread_pool=False, contract_every=None, inplace=False)¶

Bases: quimb.tensor.belief_propagation.bp_common.BeliefPropagationCommon

Object interface for hyper, vectorized, 1-norm, belief propagation. This is the fast version of belief propagation possible when there are many, small, matching tensor sizes.

Parameters:

tn (TensorNetwork) – The tensor network to run BP on.
messages (dict, optional) – Initial messages to use, if not given then uniform messages are used.
damping (float or callable, optional) – The damping factor to apply to messages. This simply mixes some part of the old message into the new one, with the final message being damping * old + (1 - damping) * new. This makes convergence more reliable but slower.
update ({'sequential', 'parallel'}, optional) – Whether to update messages sequentially (newly computed messages are immediately used for other updates in the same iteration round) or in parallel (all messages are comptued using messages from the previous round only). Sequential generally helps convergence but parallel can possibly converge to differnt solutions.
normalize ({'L1', 'L2', 'L2phased', 'Linf', callable}, optional) – How to normalize messages after each update. If None choose automatically. If a callable, it should take a message and return the normalized message. If a string, it should be one of ‘L1’, ‘L2’, ‘L2phased’, ‘Linf’ for the corresponding norms. ‘L2phased’ is like ‘L2’ but also normalizes the phase of the message, by default used for complex dtypes.
distance ({'L1', 'L2', 'L2phased', 'Linf', 'cosine', callable}, optional) – How to compute the distance between messages to check for convergence. If None choose automatically. If a callable, it should take two messages and return the distance. If a string, it should be one of ‘L1’, ‘L2’, ‘L2phased’, ‘Linf’, or ‘cosine’ for the corresponding norms. ‘L2phased’ is like ‘L2’ but also normalizes the phases of the messages, by default used for complex dtypes if phased normalization is not already being used.
smudge_factor (float, optional) – A small number to add to the denominator of messages to avoid division by zero. Note when this happens the numerator will also be zero.
thread_pool (bool or int, optional) – Whether to use a thread pool for parallelization, if True use the default number of threads, if an integer use that many threads.
contract_every (int, optional) – If not None, ‘contract’ (via BP) the tensor network every contract_every iterations. The resulting values are stored in zvals at corresponding points zval_its.
inplace (bool, optional) – Whether to perform any operations inplace on the input tensor network.

smudge_factor = 1e-12¶

pool = None¶

property normalize¶

property distance¶

initialize_messages_batched(messages=None)¶

property messages¶

_compute_outputs_batched(batched_inputs, batched_tensors=None)¶: Given stacked messsages and optionally tensors, compute stacked output messages, possibly using parallel pool.

_update_outputs_to_inputs_batched(batched_inputs, batched_outputs, masks)¶: Update the stacked input messages from the stacked output messages.

iterate(tol=None)¶

Perform a single iteration of belief propagation. Subclasses should implement this method, returning either max_mdiff or a dictionary containing max_mdiff and any other relevant information:

{
“nconv”: nconv, “ncheck”: ncheck, “max_mdiff”: max_mdiff,

}

get_messages_dense()¶: Get messages in individual form from the batched stacks.

get_messages()¶

contract(strip_exponent=False, check_zero=False)¶

Estimate the contraction of the tensor network using the current messages. Uses batched vectorized contractions for speed.

Parameters:

strip_exponent (bool, optional) – Whether to strip the exponent from the final result. If True then the returned result is (mantissa, exponent).
check_zero (bool, optional) – Whether to check for zero values and return zero early. Currently True is not implemented for HV1BP.

Return type:

scalar or (scalar, float)

contract_dense(strip_exponent=False, check_zero=True)¶: Slow contraction via explicit extranting individual dense messages. This supports check_zero=True and may be useful for debugging.

quimb.tensor.belief_propagation.hv1bp.contract_hv1bp(tn, messages=None, max_iterations=1000, tol=5e-06, damping=0.0, diis=False, update='parallel', normalize='L2', distance='L2', tol_abs=None, tol_rolling_diff=None, smudge_factor=1e-12, strip_exponent=False, check_zero=False, info=None, progbar=False)¶

Estimate the contraction of tn with hyper, vectorized, 1-norm belief propagation, via the exponential of the Bethe free entropy.

Parameters:

tn (TensorNetwork) – The tensor network to run BP on, can have hyper indices.
messages (dict, optional) – Initial messages to use, if not given then uniform messages are used.
max_iterations (int, optional) – The maximum number of iterations to perform.
tol (float, optional) – The convergence tolerance for messages.
damping (float, optional) – The damping factor to use, 0.0 means no damping.
diis (bool or dict, optional) – Whether to use direct inversion in the iterative subspace to help converge the messages by extrapolating to low error guesses. If a dict, should contain options for the DIIS algorithm. The relevant options are {max_history, beta, rcond}.
update ({'parallel'}, optional) – Whether to update messages sequentially or in parallel.
normalize ({'L1', 'L2', 'L2phased', 'Linf', callable}, optional) – How to normalize messages after each update. If None choose automatically. If a callable, it should take a message and return the normalized message. If a string, it should be one of ‘L1’, ‘L2’, ‘L2phased’, ‘Linf’ for the corresponding norms. ‘L2phased’ is like ‘L2’ but also normalizes the phase of the message, by default used for complex dtypes.
distance ({'L1', 'L2', 'L2phased', 'Linf', 'cosine', callable}, optional) – How to compute the distance between messages to check for convergence. If None choose automatically. If a callable, it should take two messages and return the distance. If a string, it should be one of ‘L1’, ‘L2’, ‘L2phased’, ‘Linf’, or ‘cosine’ for the corresponding norms. ‘L2phased’ is like ‘L2’ but also normalizes the phases of the messages, by default used for complex dtypes if phased normalization is not already being used.
tol_abs (float, optional) – The absolute convergence tolerance for maximum message update distance, if not given then taken as tol.
tol_rolling_diff (float, optional) – The rolling mean convergence tolerance for maximum message update distance, if not given then taken as tol. This is used to stop running when the messages are just bouncing around the same level, without any overall upward or downward trends, roughly speaking.
smudge_factor (float, optional) – A small number to add to the denominator of messages to avoid division by zero. Note when this happens the numerator will also be zero.
strip_exponent (bool, optional) – Whether to strip the exponent from the final result. If True then the returned result is (mantissa, exponent).
check_zero (bool, optional) – Whether to check for zero values and return zero early.
info (dict, optional) – If specified, update this dictionary with information about the belief propagation run.
progbar (bool, optional) – Whether to show a progress bar.

Return type:

scalar or (scalar, float)

quimb.tensor.belief_propagation.hv1bp.run_belief_propagation_hv1bp(tn, messages=None, max_iterations=1000, tol=5e-06, damping=0.0, diis=False, update='parallel', normalize='L2', distance='L2', tol_abs=None, tol_rolling_diff=None, smudge_factor=1e-12, info=None, progbar=False)¶

Run belief propagation on a tensor network until it converges.

Parameters:

tn (TensorNetwork) – The tensor network to run BP on.
messages (dict, optional) – The current messages. For every index and tensor id pair, there should be a message to and from with keys (ix, tid) and (tid, ix). If not given, then messages are initialized as uniform.
max_iterations (int, optional) – The maximum number of iterations to run for.
tol (float, optional) – The convergence tolerance.
damping (float, optional) – The damping factor to use, 0.0 means no damping.
diis (bool or dict, optional) – Whether to use direct inversion in the iterative subspace to help converge the messages by extrapolating to low error guesses. If a dict, should contain options for the DIIS algorithm. The relevant options are {max_history, beta, rcond}.
update ({'parallel'}, optional) – Whether to update messages sequentially or in parallel.
normalize ({'L1', 'L2', 'L2phased', 'Linf', callable}, optional) – How to normalize messages after each update. If None choose automatically. If a callable, it should take a message and return the normalized message. If a string, it should be one of ‘L1’, ‘L2’, ‘L2phased’, ‘Linf’ for the corresponding norms. ‘L2phased’ is like ‘L2’ but also normalizes the phase of the message, by default used for complex dtypes.
distance ({'L1', 'L2', 'L2phased', 'Linf', 'cosine', callable}, optional) – How to compute the distance between messages to check for convergence. If None choose automatically. If a callable, it should take two messages and return the distance. If a string, it should be one of ‘L1’, ‘L2’, ‘L2phased’, ‘Linf’, or ‘cosine’ for the corresponding norms. ‘L2phased’ is like ‘L2’ but also normalizes the phases of the messages, by default used for complex dtypes if phased normalization is not already being used.
tol_abs (float, optional) – The absolute convergence tolerance for maximum message update distance, if not given then taken as tol.
tol_rolling_diff (float, optional) – The rolling mean convergence tolerance for maximum message update distance, if not given then taken as tol. This is used to stop running when the messages are just bouncing around the same level, without any overall upward or downward trends, roughly speaking.
smudge_factor (float, optional) – A small number to add to the denominator of messages to avoid division by zero. Note when this happens the numerator will also be zero.
info (dict, optional) – If specified, update this dictionary with information about the belief propagation run.
progbar (bool, optional) – Whether to show a progress bar.

Returns:

messages (dict) – The final messages.
converged (bool) – Whether the algorithm converged.

quimb.tensor.belief_propagation.hv1bp.sample_hv1bp(tn, messages=None, output_inds=None, max_iterations=1000, tol=0.01, damping=0.0, diis=False, update='parallel', normalize='L2', distance='L2', tol_abs=None, tol_rolling_diff=None, smudge_factor=1e-12, bias=False, seed=None, progbar=False)¶

Sample all indices of a tensor network using repeated belief propagation runs and decimation.

Parameters:

tn (TensorNetwork) – The tensor network to sample.
messages (dict, optional) – The current messages. For every index and tensor id pair, there should be a message to and from with keys (ix, tid) and (tid, ix). If not given, then messages are initialized as uniform.
output_inds (sequence of str, optional) – The indices to sample. If not given, then all indices are sampled.
max_iterations (int, optional) – The maximum number of iterations for each message passing run.
tol (float, optional) – The convergence tolerance for each message passing run.
damping (float, optional) – The damping factor to use, 0.0 means no damping.
diis (bool or dict, optional) – Whether to use direct inversion in the iterative subspace to help converge the messages by extrapolating to low error guesses. If a dict, should contain options for the DIIS algorithm. The relevant options are {max_history, beta, rcond}.
update ({'parallel'}, optional) – Whether to update messages sequentially or in parallel.
normalize ({'L1', 'L2', 'L2phased', 'Linf', callable}, optional) – How to normalize messages after each update. If None choose automatically. If a callable, it should take a message and return the normalized message. If a string, it should be one of ‘L1’, ‘L2’, ‘L2phased’, ‘Linf’ for the corresponding norms. ‘L2phased’ is like ‘L2’ but also normalizes the phase of the message, by default used for complex dtypes.
distance ({'L1', 'L2', 'L2phased', 'Linf', 'cosine', callable}, optional) – How to compute the distance between messages to check for convergence. If None choose automatically. If a callable, it should take two messages and return the distance. If a string, it should be one of ‘L1’, ‘L2’, ‘L2phased’, ‘Linf’, or ‘cosine’ for the corresponding norms. ‘L2phased’ is like ‘L2’ but also normalizes the phases of the messages, by default used for complex dtypes if phased normalization is not already being used.
tol_abs (float, optional) – The absolute convergence tolerance for maximum message update distance, if not given then taken as tol.
tol_rolling_diff (float, optional) – The rolling mean convergence tolerance for maximum message update distance, if not given then taken as tol. This is used to stop running when the messages are just bouncing around the same level, without any overall upward or downward trends, roughly speaking.
smudge_factor (float, optional) – A small number to add to each message to avoid zeros. Making this large is similar to adding a temperature, which can aid convergence but likely produces less accurate marginals.
bias (bool or float, optional) – Whether to bias the sampling towards the largest marginal. If False (the default), then indices are sampled proportional to their marginals. If True, then each index is ‘sampled’ to be its largest weight value always. If a float, then the local probability distribution is raised to this power before sampling.
thread_pool (bool, int or ThreadPoolExecutor, optional) – Whether to use a thread pool for parallelization. If an integer, then this is the number of threads to use. If True, then the number of threads is set to the number of cores. If a ThreadPoolExecutor, then this is used directly.
seed (int, optional) – A random seed to use for the sampling.
progbar (bool, optional) – Whether to show a progress bar.

Returns:

config (dict[str, int]) – The sample configuration, mapping indices to values.
tn_config (TensorNetwork) – The tensor network with all index values (or just those in output_inds if supllied) selected. Contracting this tensor network (which will just be a sequence of scalars if all index values have been sampled) gives the weight of the sample, e.g. should be 1 for a SAT problem and valid assignment.
omega (float) – The probability of choosing this sample (i.e. product of marginal values). Useful possibly for importance sampling.