The ability toleverage large-scale hardware parallelism has been one ofthe key enablers of the accelerated recent progress in machine learning.

In graphical models, factor graphs, and more generally energy-based models, the interactions between variables are encoded by a graph, a hypergraph, or, in the most general case, a partially ordered set (poset). Inference on such probabilistic models cannot be performed exactly due to cycles in the underlying structures of interaction. Instead, one resorts to approximate variational inference by optimizing the Bethe free energy. Critical points of the Bethe free energy correspond to fixed points of the associated Belief Propagation algorithm. A full characterization of these critical points for general graphs, hypergraphs, and posets with a finite number of variables is still an open problem. We show that, for hypergraphs and posets with chains of length at most 1, changing the poset of interactions of the probabilistic model to one with the same homotopy type induces a bijection between the critical points of the associated free energy. This result extends and unifies classical results that assume specific forms of collapsibility to prove uniqueness of the critical points of the Bethe free energy.

Local "belief propagation" rules of the sort proposed by Pearl [15] are guaranteed to converge to the correct posterior probabilities in singly connected graphical models. Recently, a number of researchers have em(cid:173) pirically demonstrated good performance of "loopy belief propagation"(cid:173) using these same rules on graphs with loops. Perhaps the most dramatic instance is the near Shannon-limit performance of "Turbo codes", whose decoding algorithm is equivalent to loopy belief propagation. Except for the case of graphs with a single loop, there has been little theo(cid:173) retical understanding of the performance of loopy propagation. Here we analyze belief propagation in networks with arbitrary topologies when the nodes in the graph describe jointly Gaussian random variables.

Local "belief propagation" rules of the sort proposed by Pearl [15] are guaranteed to converge to the correct posterior probabilities in singly connected graphical models. Recently, a number of researchers have em(cid:173) pirically demonstrated good performance of "loopy belief propagation"(cid:173) using these same rules on graphs with loops. Perhaps the most dramatic instance is the near Shannon-limit performance of "Turbo codes", whose decoding algorithm is equivalent to loopy belief propagation. Except for the case of graphs with a single loop, there has been little theo(cid:173) retical understanding of the performance of loopy propagation. Here we analyze belief propagation in networks with arbitrary topologies when the nodes in the graph describe jointly Gaussian random variables.

We discuss the integration of the expectation-maximization (EM) algorithm for maximum likelihood learning of Bayesian networks with belief propagation algorithms for approximate inference. Specifically we propose to combine the outer-loop step of convergent belief propagation algorithms with the M-step of the EM algorithm. This then yields an approximate EM algorithm that is essentially still double loop, with the important advantage of an inner loop that is guaranteed to converge. Simulations illustrate the merits of such an approach.

Graphical models provide a natural framework for probabilistic modeling and for inference with a large number of random variables. The framework has numerous applications including in computer vision, artificial intelligence, error correcting codes, and statistical physics. Exact inference in graphical models is NP-hard so it is essential to develop approximate inference algorithms that are computationally tractable. Belief propagation is a widely used message passing algorithm that can be used to perform either exact or approximate inference in a graphical model depending on the topology of the graph. This algorithm was first introduced by Judea Pearl in the early 1980s as a method to perform exact inference on a tree-structured graph in polynomial time [15].

Locating each node in a wireless sensor network is essential for starting the monitoring job and sending information about the area. One method that has been used in hard and inaccessible environments is randomly scattering each node in the area. In order to reduce the cost of using GPS at each node, some nodes should be equipped with GPS (anchors), Then using the belief propagation algorithm, locate other nodes. The number of anchor nodes must be reduced since they are expensive. Furthermore, the location of these nodes affects the algorithm's performance. Using multi-objective optimization, an algorithm is introduced in this paper that minimizes the estimated location error and the number of anchor nodes. According to simulation results, This algorithm proposes a set of solutions with less energy consumption and less error than similar algorithms.

This paper employs the extrinsic information transfer (EXIT) method, a technique imported from the analysis of the iterative decoding of error control codes, to study the performance of belief propagation in community detection in the presence of side information. We consider both the detection of a single (hidden) community, as well as the problem of identifying two symmetric communities. For single community detection, this paper demonstrates the suitability of EXIT to predict the asymptotic phase transition for weak recovery. More importantly, EXIT analysis is leveraged to produce useful insights such as the performance of belief propagation near the threshold. For two symmetric communities, the asymptotic residual error for belief propagation is calculated under finite-alphabet side information, generalizing a previous result with noisy labels. EXIT analysis is used to illuminate the effect of side information on community detection, its relative importance depending on the correlation of the graphical information with node labels, as well as the effect of side information on residual errors.

We study the stochastic block model with two communities where vertices contain side information in the form of a vertex label. These vertex labels may have arbitrary label distributions, depending on the community memberships. We analyze a linearized version of the popular belief propagation algorithm. We show that this algorithm achieves the highest accuracy possible whenever a certain function of the network parameters has a unique fixed point. Whenever this function has multiple fixed points, the belief propagation algorithm may not perform optimally. We show that increasing the information in the vertex labels may reduce the number of fixed points and hence lead to optimality of belief propagation.

Belief Propagation algorithms are instruments used broadly to solve graphical model optimization and statistical inference problems. In the general case of a loopy Graphical Model, Belief Propagation is a heuristic which is quite successful in practice, even though its empirical success, typically, lacks theoretical guarantees. This paper extends the short list of special cases where correctness and/or convergence of a Belief Propagation algorithm is proven. We generalize formulation of Min-Sum Network Flow problem by relaxing the flow conservation (balance) constraints and then proving that the Belief Propagation algorithm converges to the exact result.