quimb.tensor.belief_propagation.hd1bp ===================================== .. py:module:: quimb.tensor.belief_propagation.hd1bp .. autoapi-nested-parse:: Hyper dense belief propagation for arbitrary `quimb` tensor networks. This is the classic 1-norm version of belief propagation, which treats the tensor network directly as a factor graph. Messages are processed one at a time. TODO: - [ ] implement 'touching', so that only necessary messages are updated - [ ] implement sequential update Classes ------- .. autoapisummary:: quimb.tensor.belief_propagation.hd1bp.HD1BP Functions --------- .. autoapisummary:: quimb.tensor.belief_propagation.hd1bp.compute_all_hyperind_messages_prod quimb.tensor.belief_propagation.hd1bp.compute_all_hyperind_messages_tree quimb.tensor.belief_propagation.hd1bp.compute_all_tensor_messages_shortcuts quimb.tensor.belief_propagation.hd1bp.compute_all_tensor_messages_prod quimb.tensor.belief_propagation.hd1bp.compute_all_tensor_messages_tree quimb.tensor.belief_propagation.hd1bp.contract_hd1bp quimb.tensor.belief_propagation.hd1bp.run_belief_propagation_hd1bp quimb.tensor.belief_propagation.hd1bp.sample_hd1bp Module Contents --------------- .. py:function:: compute_all_hyperind_messages_prod(ms, smudge_factor=1e-12) Given set of messages ``ms`` incident to a single index, compute the corresponding next output messages, using the 'product' implementation. .. py:function:: compute_all_hyperind_messages_tree(ms) Given set of messages ``ms`` incident to a single index, compute the corresponding next output messages, using the 'tree' implementation. .. py:function:: compute_all_tensor_messages_shortcuts(x, ms, ndim) .. py:function:: compute_all_tensor_messages_prod(x, ms, backend=None, smudge_factor=1e-12) Given set of messages ``ms`` incident to tensor with data ``x``, compute the corresponding next output messages, using the 'prod' implementation. .. py:function:: compute_all_tensor_messages_tree(x, ms, backend=None) Given set of messages ``ms`` incident to tensor with data ``x``, compute the corresponding next output messages, using the 'tree' implementation. .. py:class:: HD1BP(tn, *, messages=None, damping=0.0, diis=False, update='sequential', normalize=None, distance=None, smudge_factor=1e-12, inplace=False) Bases: :py:obj:`quimb.tensor.belief_propagation.bp_common.BeliefPropagationCommon` Object interface for hyper, dense, 1-norm belief propagation. This is standard belief propagation in tensor network form. :param tn: The tensor network to run BP on. :type tn: TensorNetwork :param messages: Initial messages to use, if not given then uniform messages are used. :type messages: dict, optional :param damping: 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. :type damping: float or callable, optional :param diis: 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`}. :type diis: bool or dict, optional :param update: 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. :type update: {'sequential', 'parallel'}, optional :param normalize: 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. :type normalize: {'L1', 'L2', 'L2phased', 'Linf', callable}, optional :param distance: 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. :type distance: {'L1', 'L2', 'L2phased', 'Linf', 'cosine', callable}, optional :param smudge_factor: 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. :type smudge_factor: float, optional :param inplace: Whether to perform any operations inplace on the input tensor network. :type inplace: bool, optional .. py:attribute:: smudge_factor :value: 1e-12 .. py:attribute:: messages :value: None .. py:method:: 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, } .. py:method:: get_gauged_tn() Assuming the supplied tensor network has no hyper or dangling indices, gauge it by inserting the BP-approximated transfer matrix eigenvectors, which may be complex. The BP-contraction of this gauged network is then simply the product of zeroth entries of each tensor. .. py:method:: contract(strip_exponent=False, check_zero=True) Estimate the total contraction, i.e. the exponential of the 'Bethe free entropy'. .. py:method:: normalize_messages() Normalize all messages such that the 'region contraction' of a single hyper index is 1. .. py:method:: get_cluster(r, virtual=True, autocomplete=True) Get the tensor network of a region ``r``, with all boundary messages attached. :param r: The region to get, given as a sequence of indices or tensor ids. :type r: sequence of int or str :param virtual: Whether the view the original tensors (`virtual=True`, the default) or take copies (`virtual=False`). :type virtual: bool, optional :param autocomplete: Whether to automatically include all indices attached to the tensors in the region, or just the ones given in ``r``. :type autocomplete: bool, optional :rtype: TensorNetwork .. py:method:: contract_gloop_expand(gloops=None, strip_exponent=False, check_zero=True, optimize='auto-hq', progbar=False, **contract_otps) Contract the hyper tensor network using generalized loop cluster expansion. :param gloops: The generalized loops to use, an integer to generate all loops up to that size, or ``None``/``"min"`` for the automatic size, see :func:`~quimb.tensor.networking.gen_gloops`. :type gloops: None, int, "min" or iterable of tuples, optional :param strip_exponent: Whether to return the mantissa and base-10 exponent separately. :type strip_exponent: bool, optional :param check_zero: Whether to return zero early when combining a product containing a zero contraction. :type check_zero: bool, optional :param optimize: The contraction path optimizer to use. :type optimize: str or PathOptimizer, optional :param progbar: Whether to show a progress bar. :type progbar: bool, optional :param contract_otps: These options configure :meth:`TensorNetwork.contract`. :returns: The generalized loop expansion estimate. The method can return the base-10 exponent separately. :rtype: scalar or (scalar, float) .. py:function:: contract_hd1bp(tn, messages=None, max_iterations=1000, tol=5e-06, damping=0.0, diis=False, update='sequential', normalize=None, distance=None, tol_abs=None, tol_rolling_diff=None, smudge_factor=1e-12, strip_exponent=False, check_zero=True, info=None, progbar=False) Estimate the contraction of ``tn`` with hyper, vectorized, 1-norm belief propagation, via the exponential of the Bethe free entropy. :param tn: The tensor network to run BP on, can have hyper indices. :type tn: TensorNetwork :param messages: Initial messages to use, if not given then uniform messages are used. :type messages: dict, optional :param max_iterations: The maximum number of iterations to perform. :type max_iterations: int, optional :param tol: The convergence tolerance for messages. :type tol: float, optional :param damping: The damping parameter to use, defaults to no damping. :type damping: float, optional :param diis: 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`}. :type diis: bool or dict, optional :param update: Whether to update messages sequentially or in parallel. :type update: {'sequential', 'parallel'}, optional :param normalize: 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. :type normalize: {'L1', 'L2', 'L2phased', 'Linf', callable}, optional :param distance: 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. :type distance: {'L1', 'L2', 'L2phased', 'Linf', 'cosine', callable}, optional :param tol_abs: The absolute convergence tolerance for maximum message update distance, if not given then taken as ``tol``. :type tol_abs: float, optional :param tol_rolling_diff: 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. :type tol_rolling_diff: float, optional :param smudge_factor: 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. :type smudge_factor: float, optional :param strip_exponent: Whether to strip the exponent from the final result. If ``True`` then the returned result is ``(mantissa, exponent)``. :type strip_exponent: bool, optional :param check_zero: Whether to check for zero values and return zero early. :type check_zero: bool, optional :param info: If specified, update this dictionary with information about the belief propagation run. :type info: dict, optional :param progbar: Whether to show a progress bar. :type progbar: bool, optional :rtype: scalar or (scalar, float) .. py:function:: run_belief_propagation_hd1bp(tn, messages=None, max_iterations=1000, tol=5e-06, damping=0.0, smudge_factor=1e-12, info=None, progbar=False) Run belief propagation on a tensor network until it converges. This is the basic version that does not vectorize contractions. :param tn: The tensor network to run BP on. :type tn: TensorNetwork :param messages: 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. :type messages: dict, optional :param max_iterations: The maximum number of iterations to run for. :type max_iterations: int, optional :param tol: The convergence tolerance. :type tol: float, optional :param smudge_factor: 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. :type smudge_factor: float, optional :param info: If specified, update this dictionary with information about the belief propagation run. :type info: dict, optional :param progbar: Whether to show a progress bar. :type progbar: bool, optional :returns: * **messages** (*dict*) -- The final messages. * **converged** (*bool*) -- Whether the algorithm converged. .. py:function:: sample_hd1bp(tn, messages=None, output_inds=None, max_iterations=1000, tol=0.01, damping=0.0, smudge_factor=1e-12, bias=False, seed=None, progbar=False, **bp_opts) Sample all indices of a tensor network using repeated belief propagation runs and decimation. :param tn: The tensor network to sample. :type tn: TensorNetwork :param messages: 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. :type messages: dict, optional :param output_inds: The indices to sample. If not given, then all indices are sampled. :type output_inds: sequence of str, optional :param max_iterations: The maximum number of iterations for each message passing run. :type max_iterations: int, optional :param tol: The convergence tolerance for each message passing run. :type tol: float, optional :param smudge_factor: 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. :type smudge_factor: float, optional :param bias: 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. :type bias: bool or float, optional :param thread_pool: 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. :type thread_pool: bool, int or ThreadPoolExecutor, optional :param seed: A random seed to use for the sampling. :type seed: int, optional :param progbar: Whether to show a progress bar. :type progbar: bool, optional :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.