Approximating the Permanent with Fractional Belief Propagation
We discuss schemes for exact and approximate computations of permanents, and compare them with each other. Specifically, we analyze the belief propagation (BP) approach and its fractional belief propagation (FBP) generalization for computing the permanent of a non-negative matrix. Known bounds and C...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2013
|
| Online Access: | http://hdl.handle.net/1721.1/81423 https://orcid.org/0000-0002-9814-9879 |
| _version_ | 1826194770342445056 |
|---|---|
| author | Chertkov, Michael Yedidia, Adam B. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Chertkov, Michael Yedidia, Adam B. |
| author_sort | Chertkov, Michael |
| collection | MIT |
| description | We discuss schemes for exact and approximate computations of permanents, and compare them with each other. Specifically, we analyze the belief propagation (BP) approach and its fractional belief propagation (FBP) generalization for computing the permanent of a non-negative matrix. Known bounds and Conjectures are verified in experiments, and some new theoretical relations, bounds and Conjectures are proposed. The fractional free energy (FFE) function is parameterized by a scalar parameter y ∈ [−1;1], where y = −1 corresponds to the BP limit and y = 1 corresponds to the exclusion principle (but ignoring perfect matching constraints) mean-field (MF) limit. FFE shows monotonicity and continuity with respect to g. For every non-negative matrix, we define its special value y∗ ∈ [−1;0] to be the g for which the minimum of the y-parameterized FFE function is equal to the permanent of the matrix, where the lower and upper bounds of the g-interval corresponds to respective bounds for the permanent. Our experimental analysis suggests that the distribution of y∗ varies for different ensembles but y∗ always lies within the [−1;−1/2] interval. Moreover, for all ensembles considered, the behavior of y∗ is highly distinctive, offering an empirical practical guidance for estimating permanents of non-negative matrices via the FFE approach. |
| first_indexed | 2024-09-23T10:01:31Z |
| format | Article |
| id | mit-1721.1/81423 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:01:31Z |
| publishDate | 2013 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/814232022-09-26T15:14:31Z Approximating the Permanent with Fractional Belief Propagation Chertkov, Michael Yedidia, Adam B. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Yedidia, Adam B. We discuss schemes for exact and approximate computations of permanents, and compare them with each other. Specifically, we analyze the belief propagation (BP) approach and its fractional belief propagation (FBP) generalization for computing the permanent of a non-negative matrix. Known bounds and Conjectures are verified in experiments, and some new theoretical relations, bounds and Conjectures are proposed. The fractional free energy (FFE) function is parameterized by a scalar parameter y ∈ [−1;1], where y = −1 corresponds to the BP limit and y = 1 corresponds to the exclusion principle (but ignoring perfect matching constraints) mean-field (MF) limit. FFE shows monotonicity and continuity with respect to g. For every non-negative matrix, we define its special value y∗ ∈ [−1;0] to be the g for which the minimum of the y-parameterized FFE function is equal to the permanent of the matrix, where the lower and upper bounds of the g-interval corresponds to respective bounds for the permanent. Our experimental analysis suggests that the distribution of y∗ varies for different ensembles but y∗ always lies within the [−1;−1/2] interval. Moreover, for all ensembles considered, the behavior of y∗ is highly distinctive, offering an empirical practical guidance for estimating permanents of non-negative matrices via the FFE approach. Los Alamos National Laboratory (Undergraduate Research Assistant Program) United States. National Nuclear Security Administration (Los Alamos National Laboratory Contract DE C52-06NA25396) 2013-10-18T12:46:22Z 2013-10-18T12:46:22Z 2013-07 2013-01 Article http://purl.org/eprint/type/JournalArticle 1532-4435 1533-7928 http://hdl.handle.net/1721.1/81423 Chertkov, Michael, and Adam B. Yedidia. “Approximating the Permanent with Fractional Belief Propagation.” Journal of Machine Learning Research 14 (2013): 2029–2066. https://orcid.org/0000-0002-9814-9879 en_US http://jmlr.org/papers/volume14/chertkov13a/chertkov13a.pdf Journal of Machine Learning Research Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Association for Computing Machinery (ACM) MIT Press |
| spellingShingle | Chertkov, Michael Yedidia, Adam B. Approximating the Permanent with Fractional Belief Propagation |
| title | Approximating the Permanent with Fractional Belief Propagation |
| title_full | Approximating the Permanent with Fractional Belief Propagation |
| title_fullStr | Approximating the Permanent with Fractional Belief Propagation |
| title_full_unstemmed | Approximating the Permanent with Fractional Belief Propagation |
| title_short | Approximating the Permanent with Fractional Belief Propagation |
| title_sort | approximating the permanent with fractional belief propagation |
| url | http://hdl.handle.net/1721.1/81423 https://orcid.org/0000-0002-9814-9879 |
| work_keys_str_mv | AT chertkovmichael approximatingthepermanentwithfractionalbeliefpropagation AT yedidiaadamb approximatingthepermanentwithfractionalbeliefpropagation |