jmlr jmlr2013 jmlr2013-13 jmlr2013-13-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Michael Chertkov, Adam B. Yedidia
Abstract: 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 γ ∈ [−1; 1], where γ = −1 corresponds to the BP limit and γ = 1 corresponds to the exclusion principle (but ignoring perfect matching constraints) mean-field (MF) limit. FFE shows monotonicity and continuity with respect to γ. For every non-negative matrix, we define its special value γ∗ ∈ [−1; 0] to be the γ for which the minimum of the γ-parameterized FFE function is equal to the permanent of the matrix, where the lower and upper bounds of the γ-interval corresponds to respective bounds for the permanent. Our experimental analysis suggests that the distribution of γ∗ varies for different ensembles but γ∗ always lies within the [−1; −1/2] interval. Moreover, for all ensembles considered, the behavior of γ∗ is highly distinctive, offering an empirical practical guidance for estimating permanents of non-negative matrices via the FFE approach. Keywords: permanent, graphical models, belief propagation, exact and approximate algorithms, learning flows
M. Bayati and C. Nair. A rigorous proof of the cavity method for counting matchings. In Proc. 44th Allerton Conf. on Communications, Control, and Computing, 2006. M. Bayati, D. Shah, and M. Sharma. Max-product for maximum weight matching: Convergence, correctness, and LP duality. IEEE Transactions on Information Theory, 54(3):1241–1251, 2008. D.P. Bertsekas. Auction algorithms for network flow problems: a tutorial introduction. Comput. Optimiz. Applic., 1:7–66, 1992. H.A. Bethe. Statistical theory of superlattices. Proceedings of Royal Society of London A, 150:552, 1935. G. Birkhoff. Three observations on linear algebra. Univ. Nac. Tacuman Rev. Ser. A, 5:147–151, 1946. M. Chertkov. Exactness of belief propagation for some graphical models with loops. Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10016 (12pp), 2008. URL http: //stacks.iop.org/1742-5468/2008/P10016. M. Chertkov and V. Y. Chernyak. Loop calculus in statistical physics and information science. Phys. Rev. E, 73(6):065102, Jun 2006a. doi: 10.1103/PhysRevE.73.065102. M. Chertkov and V.Y. Chernyak. Loop series for discrete statistical models on graphs. Journal of Statistical Mechanics: Theory and Experiment, 2006(06):P06009, 2006b. URL http: //stacks.iop.org/1742-5468/2006/i=06/a=P06009. M. Chertkov, L. Kroc, and M. Vergassola. Belief propagation and beyond for particle tracking. arxiv, abs/0806.1199, 2008. M. Chertkov, L. Kroc, F. Krzakala, M. Vergassola, and L. Zdeborova. Inference in particle tracking experiments by passing messages between images. Proceedings of the National Academy of Science, 107:7663–7668, April 2010. doi: 10.1073/pnas.0910994107. B. Cseke and T. Heskes. Properties of Bethe Free Energies and message passing in Gaussian models. J. Artif. Intell. Res. (JAIR), 41:1–24, 2011. K. Drescher, R. E. Goldstein, N. Michel, M. Polin, and I. Tuval. Direct measurement of the flow field around swimming microorganisms. Phys. Rev. Lett., 105(16):168101, Oct 2010. doi: 10. 1103/PhysRevLett.105.168101. 2064 A PPROXIMATING THE P ERMANENT WITH F RACTIONAL B ELIEF P ROPAGATION P.V. Egorychev. Proof of the van der Waerden conjecture for permanents. Siberian Mathematical Journal, 22(6):854–859, 1981. URL http://www.springerlink.com/content/ k692377516k1x778/. G. M. Engel and H. Schneider. Inequalities for determinants and permanents. Linear and Multilinear Algebra, 1:187–201, 1973. D.I. Falikman. Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix. Mathematical Notes, 29(6):475–479, 1981. URL http://www. springerlink.com/content/h41162g677317110/. R.G. Gallager. Low-Density Parity-Check Codes. MIT Press, Cambridge, MA, 1963. J. S. Guasto, K. A. Johnson, and J. P. Gollub. Oscillatory flows induced by microorganisms swimming in two dimensions. Phys. Rev. Lett., 105(16):168102, Oct 2010. doi: 10.1103/PhysRevLett. 105.168102. L. Gurvits. Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all. Electronic Journal of Combinatorics, 15:R66, 2008. URL http://www.emis.ams.org/journals/EJC/Volume_15/PDF/v15i1r66.pdf. L. Gurvits. Unharnessing the power of Schrijver’s permanental inequality. ArXiv e-prints, June 2011. B. Huang and T. Jebara. Approximating the permanent with belief propagation, arxiv:0908.1769, 2009. URL http://arxiv.org/abs/0908.1769. M. Huber and J. Law. Fast approximation of the permanent for very dense problems. in: SODA 08: Proc. 19th ACM-SIAM Sympos. on Discrete Algorithms, page 681689, 2008. M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM, 51(4):671–697, 2004. ISSN 0004-5411. doi: http://doi.acm.org/10.1145/1008731.1008738. D. K˝ nig. Theorie der Endlichen und Unendlichen Graphen. Akademische Verlags Gesellschaft, o Leipzig, 1936. P. Knopp and R. Sinkhorn. Concerning nonnegative matrices and doubly stochastic matrices. Pacific J. Math., 21(2):343–348, 1967. D. E. Knuth. The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams. Addison-Wesley Professional, 12th edition, 2009. ISBN 0321580508, 9780321580504. H. W. Kuhn. The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly, 2:8397, 1955. M. Laurent and A. Schrijver. On Leonid Gurvits’s proof for permanents. American Mathematical Monthly, 117(10), 2010. URL http://homepages.cwi.nl/˜lex/files/perma5.pdf. 2065 C HERTKOV AND Y EDIDIA N. Linial, A. Samorodnitsky, and A. Wigderson. A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. Combinatorica, 20(4):545–568, 2000. S. Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Design Automation, 1993. 30th Conference on, pages 272 – 277, 1993. doi: 10.1109/DAC.1993.203958. J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. San Francisco: Morgan Kaufmann Publishers, Inc., 1988. H.A. Peierls. Ising’s model of ferromagnetism. Proceedings of Cambridge Philosophical Society, 32:477–481, 1936. H. J. Ryser. Combinatorial mathematics. The Carus Mathematical Monographs, 14, 1963. S. Sanghavi, D. Malioutov, and A. Willsky. Belief propagation and lp relaxation for weighted matching in general graphs. Information Theory, IEEE Transactions on, 57(4):2203 –2212, april 2011. ISSN 0018-9448. doi: 10.1109/TIT.2011.2110170. A. Schrijver. Counting 1-factors in regular bipartite graphs. Journal of Combinatorial Theory, 72: 122–135, 1998. doi: 10.1006/jctb.1997.1798. TheCodeProject. http://www.codeproject.com/KB/applications/ RyserPermanent.aspx. Computes permanent of a matrix with Ryser’s algorithm. L.G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8: 189201, 1979. B. L. van der Waerden. [Aufgabe] 45, Jahresbericht der Deutschen Mathematiker-Vereinigung, 35: 117, 1926. J. von Neumann. A certain zero-sum two-person game equivalent to an optimal assignment problem. Ann. Math. Studies, 28:5–12, 1953. P.O. Vontobel. The Bethe permanent of a non-negative matrix. In Communication, Control, and Computing (Allerton), 2010 48th Annual Allerton Conference on, pages 341 –346, 29 2010-oct. 1 2010. doi: 10.1109/ALLERTON.2010.5706926. P.O. Vontobel. The bethe permanent of a non-negative matrix. IEEE Trans. Inf. Theory, 59(3): 1866–1901, 2013. Y. Watanabe and M. Chertkov. Belief propagation and loop calculus for the permanent of a nonnegative matrix. Journal of Physics A: Mathematical and Theoretical, 43(24):242002, 2010. URL http://stacks.iop.org/1751-8121/43/i=24/a=242002. W. Wiegerinck and T. Heskes. Fractional belief propagation. Advances in Neural Information Processing Systems 15, 12:438–445, 2003. A.B. Yedidia. Counting independent sets and kernels of regular graphs. arxiv, abs/0910.4664, 2009. J.S. Yedidia, W.T. Freeman, and Y. Weiss. Constructing free-energy approximations and generalized belief propagation algorithms. Information Theory, IEEE Transactions on, 51(7):2282 – 2312, July 2005. ISSN 0018-9448. doi: 10.1109/TIT.2005.850085. 2066