Belief Revision

Footprints found at ancient lake in New Mexico challenge old belief of first humans in Americas

FOX News

Fox News Flash top headlines are here. Check out what's clicking on The oldest direct evidence of human presence in the Americas are likely fossilized human footprints found in New Mexico, challenging once-conventional wisdom regarding humans migrating to the New World from Russia roughly 15,000 years ago, new research confirms. The new discovery suggests that the first people actually arrived in the Americas much earlier than previously believed. According to research published Thursday in the journal Science, footprints discovered at the edge of an ancient lake bed in White Sands National Park date back to between 21,000 and 23,000 years ago.

Minimum Weight Perfect Matching via Blossom Belief Propagation ∗ Sejun Park

Neural Information Processing Systems

Max-product Belief Propagation (BP) is a popular message-passing algorithm for computing a Maximum-A-Posteriori (MAP) assignment over a distribution represented by a Graphical Model (GM). It has been shown that BP can solve a number of combinatorial optimization problems including minimum weight matching, shortest path, network flow and vertex cover under the following common assumption: the respective Linear Programming (LP) relaxation is tight, i.e., no integrality gap is present. However, when LP shows an integrality gap, no model has been known which can be solved systematically via sequential applications of BP. In this paper, we develop the first such algorithm, coined Blossom-BP, for solving the minimum weight matching problem over arbitrary graphs. Each step of the sequential algorithm requires applying BP over a modified graph constructed by contractions and expansions of blossoms, i.e., odd sets of vertices.

Reviews: Constraints Based Convex Belief Propagation

Neural Information Processing Systems

General comments: (i) The authors only solve a new special kind of higher order consistency constraints, generalizing soft PN-potentials, but not a truly general class of constraints, as indicated in the title or in the abstract. In case of MAP-inference, which is normally desired, the goal is to obtain a single assignment which satisfies all given linear constraints. The relaxed model the authors optimize is simply a byproduct of looking for marginals instead of MAP-assignments (the added entropy is responsible for this). In case of vanishing entropy one gets the same model. Hence there certainly remains the disadvantage of a parameter in the PN-potential, but now hidden in the entropy.

Constraints Based Convex Belief Propagation

Neural Information Processing Systems

Inference in Markov random fields subject to consistency structure is a fundamental problem that arises in many real-life applications. In order to enforce consistency, classical approaches utilize consistency potentials or encode constraints over feasible instances. Unfortunately this comes at the price of a tremendous computational burden. In this paper we suggest to tackle consistency by incorporating constraints on beliefs. This permits derivation of a closed-form message-passing algorithm which we refer to as the Constraints Based Convex Belief Propagation (CBCBP). Experiments show that CBCBP outperforms the conventional consistency potential based approach, while being at least an order of magnitude faster.

Reviews: Achieving the KS threshold in the general stochastic block model with linearized acyclic belief propagation

Neural Information Processing Systems

Major comments: - As mentioned by the authors in the introduction, the SBM is widely used throughout many areas, and not only for detecting communities. The authors introduce no condition on the parameter matrix Q so that their setup includes (in principle) cases as diverse as communities, anti-communities (graphs of a bipartite type) and any other type of connectivity structure. However, I believe that their algorithm (based on belief propagation and thus on the community structure) will reveal only communities. If I am right, they should specify where this underlying assumption comes into play. Is it only that definition 3 becomes useless when the structure is not the one of communities?

Achieving the KS threshold in the general stochastic block model with linearized acyclic belief propagation

Neural Information Processing Systems

The stochastic block model (SBM) has long been studied in machine learning and network science as a canonical model for clustering and community detection. In the recent years, new developments have demonstrated the presence of threshold phenomena for this model, which have set new challenges for algorithms. For the detection problem in symmetric SBMs, Decelle et al. conjectured that the so-called Kesten-Stigum (KS) threshold can be achieved efficiently. This was proved for two communities, but remained open for three and more communities. We prove this conjecture here, obtaining a general result that applies to arbitrary SBMs with linear size communities. The developed algorithm is a linearized acyclic belief propagation (ABP) algorithm, which mitigates the effects of cycles while provably achieving the KS threshold in O(n ln n) time. This extends prior methods by achieving universally the KS threshold while reducing or preserving the computational complexity. ABP is also connected to a power iteration method on a generalized nonbacktracking operator, formalizing the spectral-message passing interplay described in Krzakala et al., and extending results from Bordenave et al.

Reviews: Synthesis of MCMC and Belief Propagation

Neural Information Processing Systems

The authors develop an very interesting method to the hard problem of computing the partition function of GM. In particular, there is no method to compute Z for general graphs accurately and log(Z) is a particularly interesting component in many fields: it is related to the likelihood in Machine Learning, it gives all the statistical information of a system in statistical mechanic, ... I think therefore that any effort toward that direction is an important contribution. Concerning the work presented here, I have some questions and concerns that I would like the authors to answer: 1) the authors mentioned that BP in general fail to converge on general graph but that more involved convergent alternative exists. I think the author should be more specific, precising if all the convergent algorithms do provide the same estimation of the BP partition function and it they are indeed linear in the system size. The 2-reg loop can be proven to converge in polynomial time but the full loop does not have these garranty.

Reviews: Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay

Neural Information Processing Systems

The major contributions of this paper are that it proves the global convergence of BP(Theorem 1.3) and VI(Theorem 1.2) on ferromagnetic Ising model with a specific initialization, i.e., to initialize variables to be 1. The proof of Theorem 1.2 is based on the fact that the mean-field free energy function, i.e., \Phi(x) is concave on the set S obtained by the update rule, and then we can use Holder's inequality to expand the \Phi(x*) - Phi(x_t) and get the upper bounds. The proof of Theorem 1.3 is based on the fact that the norm of \Phi(v)'s gradient is less than 1(Lemma 3.2), and the properties of variable \mu sandwiched between v 0 and final v T(Lemma 3.5 and Lemma F.1). Other minor contributions include that it provides examples to empirically show the convergence(appendix G) and it shows how to use ellipsoid method to optimize the beliefs(appendix H). I have to admit that I am not familiar with this area, so can only go through a part of the proof, and I am not able to evaluate the originality and quality of this work.

Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay

Neural Information Processing Systems

Belief propagation is a fundamental message-passing algorithm for probabilistic reasoning and inference in graphical models. While it is known to be exact on trees, in most applications belief propagation is run on graphs with cycles. Understanding the behavior of "loopy" belief propagation has been a major challenge for researchers in machine learning and other fields, and positive convergence results for BP are known under strong assumptions which imply the underlying graphical model exhibits decay of correlations. We show, building on previous work of Dembo and Montanari, that under a natural initialization BP converges quickly to the global optimum of the Bethe free energy for Ising models on arbitrary graphs, as long as the Ising model is ferromagnetic (i.e.