This paper is the first in the series devoted to evaluation of the partition function in statistical models on graphs with loops in terms of the Berezin/fermion integrals. The paper focuses on a representation of the determinant of a square matrix in terms of a finite series, where each term corresponds to a loop on the graph. The representation is based on a fermion version of the Loop Calculus, previously introduced by the authors for graphical models with finite alphabets. Our construction contains two levels. First, we represent the determinant in terms of an integral over anti-commuting Grassman variables, with some reparametrization/gauge freedom hidden in the formulation. Second, we show that a special choice of the gauge, called BP (Bethe-Peierls or Belief Propagation) gauge, yields the desired loop representation. The set of gauge-fixing BP conditions is equivalent to the Gaussian BP equations, discussed in the past as efficient (linear scaling) heuristics for estimating the covariance of a sparse positive matrix. PACS numbers: 02.50. Tt, 64.60.Cn, 05.50.+q The series in general, and this paper in particular, belongs to the new emerging field of statistical inference and graphical models born on the cross-roads of statistical/mathematical physics, computer science, and information theory (see the following recent books as introductory reviews [1, 2, 3] ). A typical problem in the field can be stated as follows. Given a graph (trees, sparse graphs or lattices are the three most popular examples), finite or infinite alphabet with the variables defined on the graph elements (typically vertexes or edges) and a cost function (probability) associated with any given variables configuration, one should find the marginals, correlation functions, or solve the weighted counting problem (calculate the partition function). The main problems that define the field are: (a) to estimate the efficiency of exact evaluation for a typical or worst case problem for a class in terms of its dependence on the problem size; and (b) when an exact evaluation is not feasible, as it requires an unacceptably large number of steps, to suggest an approximation and a corresponding efficient algorithmic implementation. A powerful approach in the field of statistical inference is to build an efficient scheme based on a simple case or limit, where the evaluation is easy, i.e. complexity is polynomial in the number of variables. One simple case corresponds to trees, i.e. graphs without loops. Following the so-called Bethe-Peierls approach inspired by [4, 5] , one can show that the computational effort for the partition function on a tree is linear in its size. Furthermore, one anticipates that the tree-based methods and corresponding algorithms should perform reasonably well on sparse graphs with relatively few loops. This approach was reinvented and successfully explored in coding theory [6] (see e.g. [7] for a modern discussion of the graph-based codes) and artificial intelligence [8] , where the corresponding algorithm was coined Belief Propagation (BP) and this name is now commonly accepted across the disciplines. In a recent development we suggested an approach, called Loop Calculus (LC) [9, 10] , which establishes an explicit relation between the BP (previously thought of as just heuristics) and exact results. Formally, LC expresses the partition function of a graphical model in terms of a series over certain subgraphs (referred to as generalized loops), where each individual term (that corresponds to a generalized loop) is expressed explicitly in terms of the BP solution (strictly speaking, a fixed point of the corresponding BP equations). LC, originally formulated for a binary alphabet, has been extended to an arbitrary finite alphabet in [11] , and the corresponding approach has been called the Loop Tower. There is also a class of problems that are easy in spite of a large number of loops contained in the underlying graphical structure. A so-called Gaussian Graphical Model (GGM) that belongs to this class is closely related to the subject of this paper. Consider a graphical model with continuous variables defined on vertexes of a graph with a Gaussian pair-wise interaction. The corresponding partition function, represented simply by a multi-dimensional Gaussian integral, is, therefore, reduced to evaluating the covariance (inverse) of the interaction matrix (note that this operation is well defined only if the matrix is positive definite). For an arbitrary interaction matrix, expressed in terms of a dense graph, this is a problem of N 3 complexity, where N is the number of the graph vertices. However, as shown in [12, 13] , one can also use a more efficient, linear in N , Gaussian Belief Propagation (GBP) algorithm for exact calculations of the marginals within the Gaussian continuous-alphabet model. The GBP can also be used for finding the covariance or evaluating the determinant of the interaction matrix. However, it does not give an exact result, but rather provide an approximation, which is conjectured to be a reasonably accurate heuristics at least for sufficiently sparse graphs. An intuitive (but also mathematically rigorous) explanation for the exactness of GBP in the case of marginals and its insufficiency for the covariance and related object has been given in [14] via the so-called Walk-Sum Approach (WSA). WSA relates the exact result for the covariance to the sum over all possible oriented paths on the arXiv:0809.3479v2 [cond-mat.stat-mech] 21 Nov 2008 2 graph, while GBP (strictly speaking asymptotic GBP, evaluated on an infinite computational tree) corresponds to the summation over a special sub-family of directed walks, specifically backtracking directed walks. This approach has also been extended to evaluate the partition function of GGM (related to the determinant of the interaction matrix) in [15] . The majority of these and other recent studies of GGM have focused on the analysis of the conditions for the Gaussian BP convergence [13, 14, 16, 17, 18, 19] or practical implementations of the GBP algorithm [17, 20] . However, and in spite of this important progress and practical significance, a systematic analysis of the accurateness of GBP as an approximation and a possibility for systematic improvements of the GBP so far has been largely left unexplored. Even though we are still unable to provide the full answers, this paper reports some progress towards the future resolution of these important questions. In this paper we introduce a fermion-based version of the Loop Calculus approach of [9, 10, 11 ] that provides an exact representation for a determinant as a finite loop series, where the first term corresponds to a fixed point of the GBP algorithm for the corresponding GGM (that we will also be calling a solution of the GBP equations, or simply GBP solution). Each subsequent term of the Loop Series is associated with a loop on the underlying graph and is expressed explicitly in terms of the GBP solution. Our approach explores the power of the Berezin representation for a determinant in terms of symbolic integrals over anti-commuting Grassman variables [21, 22] . Note, that a relation between some binary graphical models on a planar graph and Grassman integrals was briefly discussed in [23] . In this and subsequent papers of the series [24] we take broader perspectives and do not limit our discussions to planar graphs. The paper is organized as follows. In Section I we start our discussion with an extensive introduction (reminder) to the Berezin integral approach, that will culminate in a Grassman integral representation for the determinant of the underlying correlation matrix. Section II is split in three Subsections and forms the core of the paper. Gauge transformations that keep the partition function of the fermion model (the determinant) invariant are introduced in Section II A. In Section II B the Belief Propagation is interpreted as a gauge fixing condition. Section II C finalizes the construction of the Loop Series. The manuscript also contains two Appendices. Appendix A is auxiliary to Section II C and contains some technical details of the Grassman integral calculations. Appendix B derives the BP equations for the standard (Bose) representation. Section III summarizes the results, briefly discusses the relations between the results reported in this paper and other results and future directions, e.g. related to the second paper in the series [24] .
This interpretation has led in particular to a better understanding of planar graphical models REF .
Fermions and Loops on Graphs. I. Loop Calculus for Determinant
J.Stat.Mech.0812:P12011,2008
Mathematics Physics Computer Science