LOOP CALCULUS AND BELIEF PROPAGATION FOR Q-ARY ALPHABET: LOOP TOWER

CHERTKOV, MICHAEL¹  CHERNYAK, VLADIMIR¹ 

[1] Los Alamos National Laboratory

关键词: 99;    COLOR;    CONSTRUCTION;    EXCITED STATES;    GROUND LEVEL;    GROUND STATES;    PARTITION FUNCTIONS;    TRANSFORMATIONS;   

DOI  :  10.2172/1000500
RP-ID  :  LA-UR-07-0149
PID  :  OSTI ID: 1000500
Others  :  TRN: US201101%%635

美国|英语

来源: SciTech Connect

【 摘 要 】

Loop calculus introduced in [1], [2] constitutes a new theoretical tool that explicitly expresses symbol Maximum-A-Posteriori (MAP) solution of a general statistical inference problem via a solution of the Belief Propagation (BP) equations. This finding brought a new significance to the BP concept, which in the past was thought of as just a loop-free approximation. In this paper they continue a discussion of the Loop Calculus, partitioning the results into three Sections. In Section 1 they introduce a new formulation of the Loop Calculus in terms of a set of transformations (gauges) that keeping the partition function of the problem invariant. The full expression contains two terms referred to as the 'ground state' and 'excited states' contributions. The BP equations are interpreted as a special (BP) gauge fixing condition that emerges as a special orthogonality constraint between the ground state and excited states, which also selects loop contributions as the only surviving ones among the excited states. In Section 2 they demonstrate how the invariant interpretation of the Loop Calculus, introduced in Section 1, allows a natural extension to the case of a general q-ary alphabet, this is achieved via a loop tower sequential construction. The ground level in the tower is exactly equivalent to assigning one color (out of q available) to the 'ground state' and considering all 'excited' states colored in the remaining (q-1) colors, according to the loop calculus rule. Sequentially, the second level in the tower corresponds to selecting a loop from the previous step, colored in (q-1) colors, and repeating the same ground vs excited states splitting procedure into one and (q-2) colors respectively. The construction proceeds till the full (q-1)-levels deep loop tower (and the corresponding contributions to the partition function) are established. In Section 3 they discuss an ultimate relation between the loop calculus and the Bethe-Free energy variational approach of [3].