Revisiting Algebra and Complexity of Inference in Graphical Models
Siamak Ravanbakhsh \affil{University of Alberta
% <- trailing '%' for backward compatibility of .sty file %Graphical Models use the intuitive and well-studied %methods of graph theory to implicitly represent %dependencies between variables in large systems and % model the global behaviour of a complex system by specifying %only local factors. This paper studies the form and complexity of inference in graphical models using the abstraction offered by algebraic structures. In particular, we broadly formalize inference problems in graphical models by viewing them as a sequence of operations based on commutative semigroups. We then study the computational complexity of inference by organizing various problems into an inference hierarchy. When the underlying structure of an inference problem is a commutative semiring -- \ie a combination of two commutative semigroups with the distributive law -- a message passing procedure called belief propagation can leverage this distributive law to perform polynomial-time inference for certain problems. After establishing the \NP-hardness of inference in any commutative semiring, we investigate the relatioin between algebraic properties in this setting and further show that polynomial-time inference using distributive law does not (trivially) extend to inference problems that are expressed using more than two commutative semigroups. We then extend the algebraic treatment of message passing procedures to survey propagation, providing a novel perspective using a combination of two commutative semirings. This formulation generalizes the application of survey propagation to new settings.
arxive2.tex
% v2-acmsmall-sample.tex, dated March 6 2012
% This is a sample file for ACM small trim journals
%
% Compilation using 'acmsmall.cls' - version 1.3 (March 2012), Aptara Inc.
% (c) 2010 Association for Computing Machinery (ACM)
%
% Questions/Suggestions/Feedback should be addressed to => "acmtexsupport@aptaracorp.com".
% Users can also go through the FAQs available on the journal's submission webpage.
%
% Steps to compile: latex, bibtex, latex latex
%
% For tracking purposes => this is v1.3 - March 2012




\documentclass[prodmode]{acmsmallanon} % acmjacm Aptara syntax %prodmode,
% \documentclass[journal,compsoc,letterpaper]{IEEEtran}
% \usepackage{natbib}
% \usepackage{euler}
% \usepackage{cleveref}
% \usepackage{times}
% \usepackage{helvet}
% \usepackage{courier}
% \frenchspacing

% Package to generate and customize Algorithm as per ACM style
\usepackage[ruled]{algorithm2e}
\renewcommand{\algorithmcfname}{ALGORITHM}
\SetAlFnt{\small}
\SetAlCapFnt{\small}
\SetAlCapNameFnt{\small}
\SetAlCapHSkip{0pt}
\IncMargin{-\parindent}

% Metadata Information
%\acmVolume{9}
%\acmNumber{9}
%\acmArticle{99}
%\acmYear{2014}
%\acmMonth{10}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amsfonts}
\usepackage{amssymb}    % if you want extra symbols
\usepackage{mathrsfs}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{tabu}
\usepackage{multicol}
\usepackage{multirow}
%\usepackage{cleveref}
\newcommand{\magn}[1]{{\textbf{#1}}}
\newcommand{\refSection}[1]{section~\textbf{\ref{#1}}}%{\cref{#1}}%
\newcommand{\RefSection}[1]{Section~\textbf{\ref{#1}}}%{\cref{#1}}%
\newcommand{\refEq}[1]{eq~(\textbf{\ref{#1}})}%{\cref{#1}}%
\newcommand{\refEqs}[2]{eqs~(\textbf{\ref{#1}}) and (\textbf{\ref{#2}})}%{\cref{#1}}%
\newcommand{\RefEq}[1]{Eq~(\textbf{\ref{#1}})}%{\cref{#1}}%
\newcommand{\RefEqs}[2]{Eqs~(\textbf{\ref{#1}}) and (\textbf{\ref{#2}})}%{\cref{#1}}%
\newcommand{\refFigure}[1]{figure~\textbf{\ref{#1}}}
\newcommand{\RefFigure}[1]{Figure~\textbf{\ref{#1}}}
\newcommand{\refTheorem}[1]{theorem~\textbf{\ref{#1}}}
\newcommand{\RefTheorem}[1]{Theorem~\textbf{\ref{#1}}}
\newcommand{\RefExample}[1]{Example~\textbf{\ref{#1}}}
\newcommand{\refExample}[1]{example~\textbf{\ref{#1}}}
\newcommand{\RefClaim}[1]{Claim~\textbf{\ref{#1}}}
\newcommand{\refClaim}[1]{claim~\textbf{\ref{#1}}}
\newcommand{\RefProposition}[1]{Proposition~\textbf{\ref{#1}}}
\newcommand{\refProposition}[1]{proposition~\textbf{\ref{#1}}}
\newcommand{\refTable}[1]{table~\textbf{\ref{#1}}}
\newcommand{\RefTable}[1]{Table~\textbf{\ref{#1}}}
\newcommand{\RefAlgorithm}[1]{Algorithm~\textbf{\ref{#1}}}
\newcommand{\RefDefinition}[1]{Definition~\textbf{\ref{#1}}}
\newcommand{\refDefinition}[1]{definition~\textbf{\ref{#1}}}
\newcommand{\bullitem}[0]{\ensuremath{\bullet~}}%{\ref{#1}}
\newcommand{\circitem}[0]{\ensuremath{\circ}}%{\ref{#1}}
\newcommand{\bulitem}[0]{\bullitem}
\newcommand{\powerop}{\ensuremath{{\odot}}}

\def\todo#1{ [[ todo:\ #1\ ]]}
\newcommand{\ie}[0]{\emph{i.e.},~}
\newcommand{\eg}[0]{\emph{e.g.},~}
\newcommand{\aka}[0]{\emph{a.k.a}.~}
\newcommand{\etal}{\emph{et al.~}}
\newcommand{\etc}{\emph{etc.~}}

\usepackage[ampersand]{easylist}
\ListProperties(Hide=100, Hang=true, Progressive=3ex, Style*=-- ,
Style2*=$\bullet$ ,Style3*=$\circ$ ,Style4*=\tiny$\blacksquare$ )


\renewcommand{\Re}[0]{\mathbb{R}} 
\newcommand{\Qe}[0]{\mathbb{Q}} 
\newcommand{\Ce}[0]{\mathbb{C}} 
\newcommand{\spsign}[0]{\ensuremath{\frown}} 
\newcommand{\mb}{\ensuremath{\Delta}}%Markov Blanket
\newcommand{\pancake}{\nabla}
\newcommand{\xx}[0]{\ensuremath{x}}%variable x
\newcommand{\xxh}[0]{\ensuremath{\hat{x}}}%variable x
\newcommand{\xxx}[2]{\ensuremath{\xx_{#1:#2}}}%variable x
\newcommand{\xxs}[2]{\ensuremath{\xs_{#1:#2}}}%variable x
\newcommand{\ww}[0]{\ensuremath{w}}%variable x
\newcommand{\yy}[0]{\ensuremath{y}}
\newcommand{\zz}[0]{\ensuremath{z}}
\newcommand{\zzz}[2]{\ensuremath{\zz_{#1:#2}}}
\DeclareRobustCommand{\xs}{\ensuremath{\underline{\xx}}}%variable x
\newcommand{\xsh}[0]{\ensuremath{\hat{\underline{\xx}}}}%variable x
\newcommand{\ws}[0]{\ensuremath{\underline{\ww}}}%variable x
\newcommand{\ys}[0]{\ensuremath{\underline{\yy}}}
\newcommand{\zs}[0]{\ensuremath{\underline{\zz}}}
\newcommand{\zzs}[2]{\ensuremath{\zs_{#1:#2}}}
\newcommand{\expo}[1]{\exp\left(#1\right)}
\newcommand{\comment}[1]{}
\newcommand{\marnote}[1]{\comment{#1}}

\let\oldbigotimes\bigotimes
\let\oldbigoplus\bigoplus
\let\oldbigodot\bigodot
\let\oldotimes\otimes
\let\oldoplus\oplus
\let\oldnabla\nabla

%\renewcommand{\oplus}{\gls{opp}}
%\renewcommand{\otimes}{\otimes}}
%\renewcommand{\oplus}{\gls{oplus}}
%\renewcommand{\bigotimes}{\overset{\otimes}{\prod}}
%\renewcommand{\bigoplus}{\overset{\oplus}{\sum}}
%\renewcommand{\bigodot}{\overset{\odot}{\sum}}
%\newcommand{\bigoslash}{\bigodot}%{\overset{\oslash}{\sum}}
%\renewcommand{\oslash}{\odot}
\newcommand{\opp}[1]{{\overset{#1}{\oplus}}}%{\oplus_#1}%
\newcommand{\bigopp}[1]{\overset{#1}{\bigoplus}}%{\overset{\oplus_#1}{\sum}}%{\overset{#1}{\oldbigoplus}}

\newcommand{\falsemath}{\ensuremath{\text{\textsc{false}}}}
\newcommand{\truemath}{\ensuremath{\text{\textsc{true}}}}
\newcommand{\nulll}{\ensuremath{\text{\textsc{null}}}}
\newcommand{\perm}{\ensuremath{\sigma}}
\newcommand{\sn}{\ensuremath{\settype{S}_{N}}}


\newcommand{\func}[1]{\mathsf{#1}}
\newcommand{\jfun}{\ensuremath{\jmath}}
\newcommand{\ff}{\ensuremath{\func{f}}}
\newcommand{\fg}{\ensuremath{\func{g}}}
\newcommand{\pp}{\ensuremath{\func{p}}}
\newcommand{\mm}{\ensuremath{\func{m}}}
\newcommand{\ph}{\ensuremath{\widehat{\pp}}}
\newcommand{\PP}{\ensuremath{\func{P}}}
\newcommand{\PH}{\ensuremath{\widehat{P}}}

\newcommand{\hp}{\ensuremath{\func{h}}}
\newcommand{\hh}{\ensuremath{\widehat{\hp}}}

%\newcommand{\ptilde}{\ensuremath{\widetilde{\pp}}}
\newcommand{\qq}{\ensuremath{\func{q}}}
\newcommand{\strat}{\ensuremath{\func{s}}}
%\newcommand{\qqsp}{\ensuremath{\overset{\spsign}{\func{q}}}}%remove
%\newcommand{\qh}{\ensuremath{\widehat{\qq}}}
\newcommand{\QQ}{\ensuremath{\func{Q}}}
\newcommand{\QH}{\ensuremath{\widehat{\QQ}}}
%sets
\newcommand{\settype}[1]{\ensuremath{\mathcal{#1}}}
\newcommand{\II}{\ensuremath{\mathrm{I}}}
\newcommand{\AAA}{\ensuremath{\mathrm{A}}}
\newcommand{\BBB}{\ensuremath{\mathrm{B}}}
\newcommand{\JJ}{\ensuremath{\mathrm{J}}}
\newcommand{\KK}{\ensuremath{\mathrm{K}}}
\newcommand{\LL}{\ensuremath{\mathrm{L}}}
\newcommand{\HH}{\ensuremath{\mathrm{H}}}
\newcommand{\NN}{\ensuremath{\settype{N}}}
\newcommand{\interaction}{\ensuremath{{\mathit{J}}}}
\newcommand{\localfield}{\ensuremath{{\mathit{h}}}}
\newcommand{\xor}{\ensuremath{{\mathrm{xor}}}}

%sp domain
\newcommand{\OO}{\mathbf{\mathcal{O}}}
%\newcommand{\GG}{\settype{G}}
%\newcommand{\HG}{\settype{H}}
%\newcommand{\VV}{\settype{V}}
%\newcommand{\UU}{\settype{U}}
%\newcommand{\EE}{\settype{E}}
%\newcommand{\CC}{\settype{C}}
\renewcommand{\SS}{\settype{S}}
%\newcommand{\DD}{\settype{D}}
%\newcommand{\TT}{\settype{T}}
\newcommand{\FF}{\settype{F}}
\newcommand{\YY}{\settype{Y}}
\newcommand{\XX}{\settype{X}}
\newcommand{\RR}{\settype{Y}^*}
%\newcommand{\MM}{\settype{M}}
\newcommand{\WW}{\settype{P}}
%\newcommand{\ZZ}{\settype{Q}}
%\newcommand{\rg}[2]{\region_{#1:#2}}
\newcommand{\sumset}[0]{{ \settype{S}}}
\newcommand{\pset}[0]{{ \settype{D}}}
\newcommand{\semig}{\mathscr{G}}
\newcommand{\semiring}{\mathscr{S}}
%\newcommand{\spsemiring}{\overset{\spsign}{\mathscr{S}}}
%\newcommand{\inference}[0]{\ensuremath{\mathscr{P}}}
\newcommand{\factorgraph}[0]{\ensuremath{\mathscr{F}}}

\newcommand{\Dn}{\ensuremath{\mathbf{A}}}
%\newcommand{\dn}{\ensuremath{\mathbf{d}}}
%\newcommand{\Vn}{\ensuremath{\mathbf{V}}}
%\newcommand{\En}{\ensuremath{\mathbf{E}}}
%\newcommand{\Mn}{\ensuremath{\mathbf{M}}}
%\newcommand{\Dt}{\ensuremath{\mathbf{B}}}
%particle index
%\newcommand{\nn}[1]{[\mathrm{#1}]}
%\newcommand{\tst}[1]{\ensuremath{^{(\mathrm{#1})}}}
\newcommand{\nb}{\partial}

%functionals
\newcommand{\functional}[1]{\mathsf{#1}}
%\newcommand{\choice}{\functional{C}}
\newcommand{\psp}{\ensuremath{\func{S}}}
%\newcommand{\psph}{\ensuremath{\widehat{\psp}}}
%\newcommand{\entropy}{\functional{H}}
%\newcommand{\partition}{\functional{Z}}
%\newcommand{\partit}[2]{\functional{Z}_{#1 \to #2}}
\newcommand{\energy}{\functional{e}}
%\newcommand{\expenergy}{\functional{U}}
%\newcommand{\divergence}{\functional{D}}
%\newcommand{\freeenergy}{\functional{F}}
%\newcommand{\psurvey}{\ensuremath{\functional{P}}}
%\newcommand{\phsurvey}{\ensuremath{\widehat{\functional{P}}}}
%\newcommand{\mfunc}{\functional{X}}
\newcommand{\compclass}{\mho}
%messages
%sum-product message

\newcommand{\msg}[2]{{\ph}_{#1 \to #2}}
%\newcommand{\msgh}[2]{{\widehat{\func{p}}}_{#1 \to #2}}
%\newcommand{\msgover}[2]{\tilde{\func{p}}_{#1 \to #2}}
\newcommand{\msgs}{{\underline{\ph}}}%remove
\newcommand{\msgss}[2]{{\underline{\ph}}_{#1 \to #2}}
%\newcommand{\msgssh}[2]{{\widehat{\underline{\func{p}}}}_{#1 \to #2}}
\newcommand{\msgsbi}[2]{{\underline{\ph}}_{#1 \leftrightarrow #2}}
\newcommand{\msgsbit}[2]{{{\underline{\ph}}}_{#1 \leftrightarrow #2}}
%q version
\newcommand{\msgq}[2]{\func{q}_{#1 \to #2}}
\newcommand{\msgssq}[2]{\underline{\func{q}}_{#1 \to #2}}

%tilde version
\newcommand{\msgt}[2]{{\widetilde{\func{p}}}_{#1 \to #2}}
\newcommand{\pht}{\ensuremath{\widetilde{\pp}}}
\newcommand{\msgsst}[2]{{\widetilde{\underline{\func{p}}}}_{#1 \to #2}}
\newcommand{\MSGT}[2]{{\widetilde{\func{P}}}_{#1 \to #2}}
\newcommand{\MSGSST}[2]{{\widetilde{\underline{\func{P}}}}_{#1 \to #2}}
\newcommand{\MSGTUPLE}{{\underline{\func{P}}}}
\newcommand{\PHT}{\ensuremath{\widetilde{\PP}}}
%\newcommand{\SPHT}{\ensuremath{\widetilde{\S}}}
\newcommand{\MSGBIT}[2]{{\widetilde{{\func{P}}}}_{#1 \leftrightarrow #2}}
%\newcommand{\SPMSGBIT}[2]{{\widetilde{{\func{S}}}}_{#1 \leftrightarrow #2}}
\newcommand{\msgbit}[2]{{{\underline{\widetilde{\pp}} }}_{#1 \leftrightarrow #2}}
%operator version
\newcommand{\MSG}[2]{{\func{P}}_{#1 \to #2}}
\newcommand{\MSGSS}[2]{{\underline{\func{P}}}_{#1 \to #2}}
\newcommand{\MSGQ}[2]{\func{Q}_{#1 \to #2}}
\newcommand{\MSGSSQ}[2]{\underline{\func{Q}}_{#1 \to #2}}

%sp version

%\newcommand{\RRSP}{\overset{\spsign}{\RR}}
\newcommand{\MSP}[2]{\func{S}_{#1 \to #2}} 
\newcommand{\MSPSS}[2]{\underline{\func{S}}_{#1 \to #2}} 
\newcommand{\PSP}[0]{\func{S}} 
\newcommand{\msp}[2]{\func{S}_{#1 \to #2}}
%\newcommand{\mmp}[2]{\func{w}_{#1 \to #2}} 
%capitalize non math
\newcommand{\back}[1]{\ensuremath{\setminus #1}}
%\newcommand{\capi}[1]{\textsc{#1}}
\newcommand{\ident}{\mathbf{\func{1}}}
\newcommand{\anih}{\mathbf{\func{0}}}
\newcommand{\identt}[1]{\overset{#1}{\ident}}
\newcommand{\NP}{\ensuremath{\mathbb{NP}}}
\newcommand{\coNP}{\ensuremath{\mathbf{co}\mathbb{NP}}}
\newcommand{\Aclass}{\ensuremath{\mathbb{A}}}
\newcommand{\PPclass}{\ensuremath{\mathbb{PP}}}
\newcommand{\Poly}{\ensuremath{\mathbb{P}}}
\newcommand{\RP}{\ensuremath{\mathbb{RP}}}
\newcommand{\poly}{\Poly}
\newcommand{\pspace}{\ensuremath{\mathbb{PSPACE}}}
\newcommand{\sharpP}{\ensuremath{\mathbb{\#P}}}
%operations
\newcommand{\defeq}{\ensuremath{\overset{\text{def}}{=}}}
\newcommand{\bptimes}{\ensuremath{\overset{\text{}}{\otimes}}}
\newcommand{\bpplus}{\ensuremath{\overset{\text{}}{\oplus}}}
\newcommand{\bigbpplus}{\ensuremath{\overset{\text{}}{\bigoplus}}}
\newcommand{\bigbptimes}{\ensuremath{\overset{\text{}}{\bigotimes}}}
\newcommand{\sptimes}{\ensuremath{\overset{\spsign}{\otimes}}}
\newcommand{\spplus}{\ensuremath{\overset{\spsign}{\oplus}}}
\newcommand{\bigspplus}{\ensuremath{\overset{\spsign}{\bigoplus}}}
\newcommand{\bigsptimes}{\ensuremath{\overset{\spsign}{\bigotimes}}}

\newcommand{\sumop}{\ensuremath{\mathrm{sum}}}
\newcommand{\prodop}{\ensuremath{\mathrm{prod}}}
\newcommand{\sumprod}{\ensuremath{(+, \cdot)}}
\newcommand{\maxprod}{\ensuremath{(\max, \cdot)}}
\newcommand{\minsum}{\ensuremath{(\min, +)}}
\newcommand{\maxsum}{\ensuremath{(\max, +)}}
\newcommand{\minmax}{\ensuremath{(\min, \max)}}
%operators

\newtheorem{claim}[theorem]{Claim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% Document starts
\begin{document}

% Page heads
\markboth{S. Ravanbakhsh and R. Greiner}{Revisiting Algebra \& Complexity of Inference in Graphical Models}

% Title portion
\title{Revisiting Algebra and Complexity of Inference in Graphical Models}
\author{Siamak Ravanbakhsh
\affil{University of Alberta}
Russell Greiner
\affil{University of Alberta}
}
% NOTE! Affiliations placed here should be for the institution where the
%       BULK of the research was done. If the author has gone to a new
%       institution, before publication, the (above) affiliation should NOT be changed.
%       The authors 'current' address may be given in the "Author's addresses:" block (below).
%       So for example, Mr. Abdelzaher, the bulk of the research was done at UIUC, and he is
%       currently affiliated with NASA.



\begin{abstract}%   <- trailing '%' for backward compatibility of .sty file
%Graphical Models use the intuitive and well-studied 
%methods of graph theory to implicitly represent 
%dependencies between variables in large systems and  
% model the global behaviour of a complex system by specifying 
%only local factors.
This paper studies the form and complexity of inference in graphical models using the abstraction offered by algebraic structures.
In particular, we broadly formalize inference problems in graphical models by viewing them as a sequence of operations based on commutative semigroups. We then study the computational complexity
of inference by organizing various problems into
an \textit{inference hierarchy}.
When the underlying structure of an inference problem is a commutative semiring -- \ie a combination of two commutative semigroups with the distributive law --   
a message passing procedure called belief propagation can leverage this distributive law to perform polynomial-time inference for certain problems. 
After establishing the \NP-hardness of inference 
in any commutative semiring, we investigate the relatioin between algebraic properties in this setting and further show that polynomial-time inference using
distributive law does not (trivially) extend to inference problems that are expressed using more than two commutative semigroups.
We then extend the algebraic treatment of message passing procedures to survey propagation, providing a novel perspective using a 
combination of two commutative semirings. This formulation generalizes the application of survey propagation to new settings.
\end{abstract}

\maketitle

%\begin{keywords}
% .Graphical Models, Inference Hierarchy, Complexity, Belief Propagation, Survey Propagation, Factor-graph, Commutative Semigroup
%\end{keywords}

\section{Introduction}
Many complicated systems can be modeled as a graphical structure with interacting local functions. Many fields have (almost independently) discovered this:
 grpahical models have been used in
bioinformatics
(protein folding, pedagogy
trees, regulatory networks), 
 neuroscience
(formation of associative memory and
neuroplasticity), 
 communication theory 
(low density parity check codes), 
 statistical physics 
(physics of dense matter and spin-glass theory), 
 image processing
(inpainting, stereo/texture reconstruction, denoising and super-resolution),
 compressed sensing, 
robotics (particle filters), 
 sensor networks, social networks, natural language processing, speech recognition,
combinatorial optimization and 
artificial intelligence
 (artificial neural networks, Bayesian networks).
Two general perspectives have emerged from these varied approaches to local computation, 
namely  variational~\cite{Wainwright2007} versus algebraic~\cite{Aji2000} perspectives on graphical models.
These two perspectives are to some extent ``residuals'' from the different origins of research in AI and statistical physics.

In the statistical study of physical systems, Boltzmann distribution   
 relates the 
probability of each state of a physical system to its energy, 
which is often decomposed due to local interactions \cite{Mezard1987,Mezard09}.
These studies often  
 model systems at the thermodynamic limit of infinite variables and the 
average behaviour through the study of random ensembles.  
Inference techniques with this origin (\eg mean-field and cavity methods) are asymptotically exact under these assumptions. 
Most importantly these studies have reduced inference to optimization through the notion of free energy --\aka the variational approach. 

In contrast, graphical models in the AI community have emerged from the study of knowledge representation
and reasoning under uncertainty \cite{pearl_probabilistic_1988}. These advances are characterized by  their attention to the 
theory of computation and logic \cite{bacchus1991representing}, where  interest in computational (as opposed to analytical) 
solutions has motivated the study of approximability, computational complexity \cite{Cooper90:Computational,roth1993hardness} and 
 the invention of inference techniques such as belief propagation that are efficient and exact on tree structures.  
But, most relevant to the topic of this paper, these studies have lead to algebraic abstractions 
in modeling systems that allow local computation \cite{shenoy1990axioms,lauritzen1997local}.


The common foundation underlying these two approaches is information theory, 
where the derivation of probabilistic principles from logical axioms \cite{jaynes2003probability} leads to
notions such as entropy and divergences that are closely linked to their physical counter-parts
\ie entropy and free energies in  physical systems. At a less abstract level, \cite{Yedidia2001a} showed that
inference techniques in AI and communication are attempting to minimize  (approximations to) free energy (also see \cite{Aji01,Heskes03}).


Another exchange of ideas between the two fields was in the study of critical phenomenon in random constraint satisfaction problems by both computer scientists and physicists \cite{fu_application_1986,mitchell1992hard,monasson1999determining}.
Satisfiability is at the heart of the theory of computation and is used to investigate reasoning in AI. 
On the other hand, the study of critical phenomena and phase transitions 
is central in the statistical physics of disordered systems. This culminated when
a variational analysis lead to the discovery of survey propagation~\cite{mezard_analytic_2002} for constraint satisfaction, which
significantly advanced the state-of-the-art in solving random satisfiability problems.

Despite this convergence, variational and algebraic perspectives are to some extent complementary -- \eg the variational approach does not extend beyond (log) probabilities, while the algebraic approach cannot justify application of message passing to graphs with loops.
%variational approach, although very powerful, is limited to (log) probabilities.
%while interest in variational perspective has grown, 
%little is gained in algebraic approach to graphical models since the past decade. 
This paper is concerned with the algebraic approach. We organize and generalize the previous work on the algebra of graphical models and give several new
results on the complexity and limit of inference in this framework. To this end, 
\refSection{sec:inference} broadly formalizes (and extends) the problem of inference using factor-graphs and commutative semigroups. 
\RefSection{sec:hierarchy} organizes a subset of inference problems into an inference hierarchy 
with increasing levels of computational complexity under \pspace. 
\RefSection{sec:gdl} reviews the distributive property that make efficient inference possible (using Belief Propagation), establishes the difficulty of inference in general commutative semirings and derives a negative result regarding the application of the distributive law beyond commutative semirings.  \RefSection{sec:sp} moves beyond Belief Propagation and introduces an algebraic interpretation of survey propagation that generalizes its application to new settings.


\section{The problem of inference}\label{sec:inference}
We use commutative semigroups to both define what a graphical 
model represents and also to define inference over this graphical model. 
The idea of using structures such as semigroups, monoids and semirings in expressing inference has a long history~\cite{lauritzen1997local,schiex1995valued,bistarelli1999semiring}. 
Our approach, based on factor-graphs~\cite{kschischang_factor_2001} 
and commutative semigroups, generalizes
a variety of previous frameworks, including
Markov networks~\cite{clifford1990markov}, 
Bayesian networks~\cite{pearl1985bayesian}, 
Forney graphs~\cite{forney2001codes}, hybrid models~\cite{dechter2001hybrid}, 
influence diagrams \cite{howard2005influence} and valuation
networks \cite{shenoy1992valuation}. 

In particular, the combination of factor-graphs and
semigroups that we consider here  
generalizes the plausibility, feasibility and utility framework of \cite{pralet2007algebraic},
which is explicitly reduced to  the graphical models mentioned above and many more.
The main difference in our approach is in keeping the framework free of semantics (\eg 
decision and chance variables, utilities, constraints),
that are often associated with variables, factors and operations, without changing the
expressive power.
These notions can later be associated with individual inference problems
 to help with interpretation.


\begin{definition}\label{def:semigroup}
A \magn{commutative semigroup} is a pair $\semig = (\RR, \otimes)$, where $\RR$ is a set and $\otimes: \RR \times \RR \to \RR$ is a binary operation that is 
(I)~associative: $ a \otimes (b \otimes c) = (a \otimes b) \otimes c$ and (II)~commutative: $a \otimes b = b \otimes a$ for all $a, b, c \in \RR$.
A \magn{commutative monoid} is a commutative semigroup plus an identity element $\identt{\otimes}$
such that  $a \otimes \identt{\otimes} = a$. 
If every element $a \in \RR$ has an inverse $a^{-1}$ (often written $\frac{1}{a}$), 
 such that $a \otimes a^{-1} = \identt{\otimes}$,
the commutative monoid is an \magn{Abelian group}.
\end{definition}
Here, the associativity and commutativity properties of a commutative semigroup make the operations invariant to the order of elements.  In general, these properties are not 
``vital'' and one may define inference starting from a \textit{magma}.\footnote{A  magma \cite{pinter2012book} generalizes a semigroup, as it does not require associativity property nor an identity element. Inference in graphical models can be also extended to use magma (in \refDefinition{def:fg}). For this, 
the elements of $\RR$ and/or $\XX$ should be ordered and/or parenthesized so as to avoid ambiguity in the order of pairwise operations over the set. Here, to avoid unnecessary complications, we confine our treatment to commutative semigroups.}


\begin{example} Some examples of semigroups are:
\begin{easylist}%[itemize]
& The set of strings with the concatenation operation forms a semigroup with the 
empty string as the identity element. However this semigroup is not commutative.
& The set of natural numbers $\settype{N}$ with summation defines a commutative semigroup. 
%However inverse is not defined for this semigroup as $\frac{1}{a} \notin \settype{N}$.
& Integers modulo $n$ with addition defines an Abelian group.
& The power-set $2^{\SS}$ of any set $\SS$, with intersection operation defines a commutative semigroup with $\SS$ as its identity element.
& The set of natural numbers with greatest common divisor defines a commutative monoid with $0$ as its identity. In fact any semilattice is a commutative semigroup~\cite{davey2002introduction}.
& Given two commutative semigroups on two sets $\RR$ and $\settype{Z}^*$, their Cartesian product is also a commutative semigroup.
\end{easylist}
\end{example}

%Here, we only consider graphical models over discrete variables. 
Let $\xs = (\xx_1,\ldots,\xx_N)$ be a tuple of $N$ discrete
variables $\xx_i\in \XX_i$, where $\XX_i$ is the finite domain of
$\xx_i$  and $\xs \in \XX =  \XX_1 \times \ldots \times \XX_N$.  
Let $\II \subseteq \NN = \{1,2,\ldots,N\}$ denote a subset
of variable indices and $\xs_\II \!=\! \{ \xx_i\! \mid\! i\in \II\} \in \XX_\II$ be the
tuple of variables in $\xs$ indexed by the subset $\II$.
A factor $\ff_{\II}: \XX_{\II} \to \YY_\II$ is a function over a subset of variables and 
$\YY_\II = \{\, \ff_\II(\xs_\II) \, \mid\, \xs_\II \in \XX_\II\, \}$ is the range of this factor. 


\begin{definition}\label{def:fg}
 A \magn{factor-graph}  is a pair $(\FF, \semig)$  such that
\begin{itemize}
\item $\FF = \{ \ff_{\II}\}$ is a collection of factors with collective range  $\YY = \bigcup_\II \YY_\II$.
\item  $|\FF| = \mathrm{Poly}(N)$.  % $|\XX_\II| = \mathrm{Poly}(N) \forall \ff_\II \in \FF$
\item $\ff_\II$ has a polynomial representation in $N$ and it is possible to evaluate $\ff_\II(\xs_\II)\; \forall \II, \xs_\II$ in polynomial time.
% $\vert \II \vert$ is constant for all factors (\ie it does not grow with $N$).
\item $\semig = (\RR, \otimes)$ is a commutative semigroup, where  $\RR$ is the closure of $\YY$ w.r.t. $\otimes$.
\end{itemize}
The factor-graph compactly represents the expanded (joint) form
\begin{align}\label{eq:expanded}
  \qq(\xs) = \bigotimes_\II \ff_\II(\xs_\II)
\end{align}
%where we use $\bigotimes$ instead of $\oldbigotimes$ for better readability.
\end{definition}

% \begin{figure}
% \centering
% \includegraphics[width=.4\textwidth]{factor_graph}
% \caption[A simple factor-graph.]{\small{A simple factor-graph with 5 variables (circles) and five factors (squares).
% Here the neighbourhood of $xx_i$ is $\nb i = \{I, J, K\}$ and its Markov blanket is 
% $\mb i = \{ j,k,m,n\}$. Similarly the neighbourhood of factor $\ff_\JJ$ is $\nb \JJ = \{ i, k, m\}$}
% }\label{fig:factor-graph}
% \end{figure}

Note that the connection between the set of factors $\FF$ and the commutative semigroup is through the ``range''  of factors.
%The source of difficulty of inference is that while $\FF$ is polynomial in $N$, the expanded form is exponential.
The conditions of this definition are necessary and sufficient to 1) compactly represent a factor-graph and 2) evaluate the expanded form, $\qq(\xs)$, in polynomial time.
In the following we make a stronger assumption that ensures a factor has a tractable tabular form -- that is $|\XX_\II| = \mathrm{Poly}(N)$, which means  $\ff_\II(\xs_\II)$ 
can be explicitly expressed for each $\xs_\II \in \XX_\II$ as 
an element of $|\II|$-dimensional array or table.\footnote{Important factor-graphs that violate this assumption are the ones with high-order sparse factors \cite{Tarlow2010,Potetz2008}. 
Although it is possible to obtain polynomial time message passing updates for special high-order factors, general high-order factors do not have
polynomial representation.}
 
%Two characteristics decide the
%tabular size of each factor $|\XX_\II|$ 1) the cardinality of the factor $|\II|$ and 2) the size of individual variable domains $|\XX_i|\; i \in \nb \II$. 
%The restriction $|\XX_\II| = \mathrm{Poly}(N)$ on the factor size implies that either a) 


%The requirements in the definition above ensure that
%1) evaluation of the expanded form, $\qq(\xs)$, polynomialy tractable 2) $\FF$ has a polynomial 
%representation. %Here, for a fixed size domain $|\XX_i|\; \forall i$, $\II = \OO(\log()$ 

%However, our condition on the size of $\II$ is not always necessary as
%exponential-sized sparse factors allow efficient 
%In this case, the requirement above translates to $\vert \II \vert = \OO(\log(N)) \; \forall \II$.


$\FF$ can be conveniently represented as a bipartite graph %~\cite{kschischang_factor_2001},
that includes two sets of nodes: variable nodes $\xx_i$, and factor 
 nodes ${\II}$. A variable node $i$ (note that we will often
identify a variable $\xx_i$ with its index ``$i$'') is connected to a
factor node $\II$ if and only if $i \in \II$ --\ie $\II$ is a set that is also an index. 
We will use $\nb$ to denote the neighbours of a variable or factor node in the factor
graph -- that is $\nb \II = \{\, i \; \mid \; i \in \II\, \}$ (which is
the set $\II$) and $\nb i = \{\, \II \; \mid \; i \in \II\, \}$.

Also, we use $\mb i$ to denote the \magn{Markov blanket} of node $\xx_i$ -- \ie $\mb i 
= \{ j \in \nb \II\; \mid \; \II \in \nb i,\; j \neq i\}$.
\begin{example}\label{example:fig1}
\refFigure{fig:fg} shows a factor-graph with 12 variables and 12 factors.
Here \\ $\xs = (\xx_i, \xx_j,\xx_k, \xx_e, \xx_m, \xx_o, \xx_r, \xx_s, \xx_t, \xx_u, \xx_v, \xx_w)$, $\II = \nb \II =  \{i,j,k\}$,  $\xs_\mathrm{K} = \xs_{\{k,w,v\}}$
and $\nb j = \{\II, \mathrm{V}, \mathrm{W}\}$. 
Assuming $\semig_e = (\Re, \min)$, the expanded
form represents  $$\qq(\xs) = \min \{\, \ff_{\II}(\xs_\II), \ff_{\JJ}(\xs_\JJ),\ldots,\ff_{\mathrm{Z}}(\xs_{\mathrm{Z}})\, \}.$$

Now, assume that all variables are binary -- \ie $\XX = \{0,1\}^{12}$ and $\qq(\xs)$ is 12-dimensional hypercube, with one value per each assignment at each corner. Also assume
each of the factors count the number of non-zero variables -- \eg for $\zs_{\mathrm{W}} = (1,0,1) \in \XX_{\mathrm{W}}$ we have $\ff_{\mathrm{W}}(\zs_{\mathrm{W}}) = 2$. Then, for the complete assignment 
$\zs = (0,1,0,1,0,1,0,1,0,1,0,1) \in \XX$, it is easy to check that the expanded form is 
$\qq(\zs) = \min \{2, 0, 1,\ldots, 1\} = 0$. 
\end{example} 


A marginalization operation shrinks the expanded form $\qq(\xs)$ using another commutative semigroup with binary operation $\oplus$.
Inference is a combination of an expansion and one or more marginalization operations,
which can be computationally intractable due to the exponential size of the expanded form.
\begin{definition} 
Given a function $\qq: \XX_{\JJ} \to \YY$, and a commutative semigroup $\semig = (\RR, \oplus)$, where $\RR$ is the closure of $\YY$ w.r.t. $\oplus$,
 the marginal of $\qq$ for $\II \subset \JJ$ is 
\begin{align}\label{eq:marginalization}
 \qq(\xs_{\JJ \back \II}) \quad \defeq \quad \bigoplus_{\xs_{\II}} \qq(\xs_{\JJ}) 
\end{align}
%where we use $\bigoplus$ instead of $\oldbigoplus$ for better readability 
where $\bigoplus_{\xs_{\II}} \qq(\xs_{\JJ})$ is short for $\bigoplus_{\xs_{\II} \in \XX_{\II}} \qq(\xs_{\JJ \back \II}, \xs_{\II})$, 
which means to compute $\qq(\xs_{\JJ \back \II})$ for each $\xs_{\JJ \back \II}$, one should perform the operation $\oplus$
over the set of all the assignments to the tuple $\xs_{\II} \in \XX_{\II}$.
%therefore we can completely identify marginalization by a tuple $\marginal = (\qq, \II, \oplus)$.
\end{definition}
We can think of $\qq(\xs_\JJ)$ as a $\vert \JJ \vert$-dimensional tensor and marginalization as performing $\oplus$ operation over the axes
in the set $\II$. The result is another $\vert \JJ \back \II \vert$-dimensional tensor (or function) that we call the \magn{marginal}. 
Here if the marginalization is over all the dimensions in $\JJ$, we denote the marginal by $\qq(\emptyset)$ instead of $\qq(\xs_\emptyset)$ and call it the \magn{integral} of $\qq$.


\begin{figure}
\centering
\includegraphics[width=.5\textwidth]{inference.pdf}
\caption{A factor-graph with variables as circles and factors as squares. The partitioning of variables indicated by the shading in parts defines an inference problem over this factor-graph.}
\label{fig:fg}
\end{figure}


Now we define an inference problem as a sequence of marginalizations over the expanded form of a factor-graph.
%\marnote{inference problem}
\begin{definition}\label{def:inference}
An \magn{inference problem} seeks
  \begin{align}
    \qq(\xs_{\JJ_0}) = \bigopp{M}_{\xs_{\JJ_M}} \bigopp{M-1}_{\xs_{\JJ_{M-1}}} \ldots \bigopp{1}_{\xs_{\JJ_1}} \bigotimes_{\II} \ff_\II(\xs_\II) 
  \end{align}
where
  \begin{itemize}
%  \item $\factorgraph$ is a factor-graph $\ff_\II: \XX_{\II} \to \YY_\II$ with $XX_{\NN}$ and $\YY$ denoting the collective domain and range of factors and $\vert \II\vert \forall \II$ is constant.
  \item $\RR$ is the closure of $\YY$ (the collective range of factors), w.r.t. $\opp{1},\ldots,\opp{M}$ and $\otimes$. 
  \item $\semig_m = (\RR, \opp{m})\quad \forall 1 \leq m \leq M$ and $\semig_e=(\RR, \otimes)$ are all  commutative semigroups.
%$\semig_l = (\RR, \opp{l})\; \forall 1 \leq l \leq L$ and $(\RR, \otimes)$ are commutative semigroups and $\RR$ is the closure of $\YY$ w.r.t. $\opp{l})\; \forall 1 \leq l \leq L$ and $\otimes$.
\item $\JJ_0,\ldots,\JJ_L$ partition the set of variable indices $\NN = \{1,\ldots,N\}$. 
\item $\qq(\xs_{\JJ_0})$ has a polynomial representation in $N$ -- \ie $|\XX_{\JJ_0}| = \mathrm{Poly}(N)$ %is a constant (\ie does not grow with $N$).
\end{itemize}
\end{definition}
%\marnote{integration \& marginalization}
%Here assuming $\JJ_0$ is constant is sufficient to make the query tractable.

Note that $\opp{1},\ldots,\opp{M}$  refer to potentially different operations as each belongs to a different semigroup.
When $\JJ_0 = \emptyset$, we call the inference problem \magn{integration} (denoting the inquiry by $\qq(\emptyset)$) and otherwise we call it \magn{marginalization}.
Here, having a constant sized $\JJ_0$ is not always enough to ensure that $\qq(\xs_{\JJ_0})$  has a polynomial representation in $N$. This is because 
the size of $\qq(\xs_{\JJ_0})$ for any individual $\xs_{\JJ_0} \in \XX_{\JJ_0}$ may grow exponentially with $N$ (\eg see \refClaim{th:product_pspace}).
In the following we call $\semig_e = (\RR, \otimes)$ the expansion semigroup and $\semig_m = (\RR, \opp{m})$ for each $m$ in $\{1,\ldots,M\}$
is a marginalization semigroup.


%This definition of an inference problem involves some choices that may seem arbitrary at first.
% The restrictions in this definition are necessary for both problem and solution to be polynomial in $N = \vert \NN \vert$:
% (I) since $\vert \II \vert$ does not grow with $N$, the space-complexity of the factor-graph is $\OO(\sum_{\II} \vert \XX_\II \vert)$, which is polynomial in $N$,
% whereas the expanded form of \cref{eq:expanded} is exponential in $N$.
% (II) since $\vert \JJ_0 \vert$ is constant, the inference query is also polynomial in $N$.

\begin{example}\label{example:fig2}
Going back to \refExample{example:fig2}, the shaded region in \refFigure{fig:fg}
shows a partitioning of the variables that we use to define the following inference problem:
$$
\qq(\xs_{\JJ_0}) = \max_{\xs_{\JJ_3}} \sum_{\xs_{\JJ_2}} \min_{\xs_{\JJ_1}} \min_\II \ff_\II(\xs_\II) 
$$
We can associate this problem with the following semantics: we may 
think of each factor as an agent, where
$\ff_{\II}(\xs_\II)$ is the payoff for agent $\II$, which only depends
on a subset of variables $\xs_\II$. 
We have adversarial variables ($\xs_{\JJ_1}$), environmental or chance variables ($\xs_{\JJ_2}$), controlled variables ($\xs_{\JJ_3}$) and query variables ($\xs_{\JJ_0}$).  
For the inference problem above, 
each query $\xs_{\JJ_0}$ seeks to maximize 
the expected minimum payoff of all agents,
without observing the adversarial or chance variables, and 
assuming the adversary makes its decision after observing control and chance variables.
\end{example}

\begin{example}\label{example:ising}
A ``probabilistic'' graphical model is defined using a expansion semigroup $\semig_e = (\Re^{\geq 0}, \times)$ and often a marginalization semigroup $\semig_m = (\Re^{\geq 0}, +)$. The expanded form represents the unnormalized joint probability
$\qq(\xs) = \prod_{\II}\ff_{\II}(\xs_{\II})$, whose marginal probabilities are simply called marginals.
%Here since, $\semig_m$ is an Abelian group, every element of the group has an inverse and we can 
% ``normalize'' $\qq$ to obtain a probability
% \begin{align}
% \label{eq:p}
% \pp(\xs) = \frac{1}{\qq(\emptyset)} \prod_{\II}\ff_{\II}(\xs_{\II}) 
% \end{align}
Replacing the summation with the marginalization semigroup $\semig_m = (\Re^{\geq 0}, \max)$, seeks the
 maximum probability state and the resulting integration problem 
%\begin{align}\label{eq:map}
$\qq(\emptyset) =  \max_{\xs} \prod_{\II} \ff_\II(\xs_\II)$
%\end{align}
is known as \magn{maximum a posteriori (MAP)} inference. 
\index{MAP}
\index{maximum a posteriori|see{MAP}}
\index{max-product}
% and as we showed is obtainable at 
%Here note that domain for both semigroups where expanded to include the identity of $\max$ (\ie $+\infty$).
 Alternatively by adding a second marginalization operation to the summation, we get the \magn{marginal MAP} inference
\index{marginal MAP}
\index{max-sum-product}
\begin{align}\label{eq:marginalmap}
    \qq(\xs_{\JJ_0}) \quad = \quad \max_{\xs_{\JJ_2}} \sum_{\xs_{\JJ_1}} \prod_{\II} \ff_{\II}(\xs_\II).
\end{align}
where here $\bigotimes = \prod$, $\bigopp{1} = \sum$ and $\bigopp{2} = \max$ (recall the numbering of operations is left to right.)

If the object of interest is the negative 
\index{energy}
log-probability (\aka energy), the product expansion semigroup is
replaced by $\semig_e=(\Re, +)$. Instead of the sum marginalization semigroup, we can
\index{log-sum-exp semigroup}
\index{semigroup!log-sum-exp}
use the \magn{log-sum-exp} semigroup, $\semig_m = (\Re, +)$ where 
$a \oplus b \defeq \log(e^{-a} + e^{-b})$. The integral in this case is the log-partition function.
If we change the marginalization semigroup to $\semig_m = (\Re, \min)$, the integral is the minimum energy (corresponding to MAP).
\end{example}


\section{The inference hierarchy}\label{sec:hierarchy}
%The complexity class of several of inference problems using $\min, \max$, $\sumop$ and $\prodop$ operators have been previously established.
Often, the complexity class is concerned with the \magn{decision version} of the %\marnote{decision problem}
inference problem in \refDefinition{def:inference}. The decision version of an inference problem asks a yes/no question about the integral such as $\qq(\emptyset) \overset{?}{\geq} q$ \footnote{Assuming an ordering on $\RR$.} or 
$\qq(\emptyset) \overset{?}{=} q$
for a given $q \in \RR$. 

% \begin{figure}
% \centering
% \includegraphics[width=.5\textwidth]{hierarchy}
% \caption[Inference hierarchy.]{
% The inference hierarchy 
% %with $\mathrm{sum}$, $\max$ and $\min$ for marginalization semigroup and
% %sum, $\max$, $\min$ and prod for expansion semigroup.
% }\label{fig:hierarchy}
% \end{figure}


% \begin{example}
% The decision version of MAP inference asks whether $\qq(\emptyset) > q$ asks whether an assignment $\xs^*$ with a MAP value larger than a threshold exists.
% The decision version of sum-product marginal $\xs_{\II}^* \quad s.t. \quad \pp(\xs_{\II}) > c$ asks a similar question about the normalized sum-product marginals. Similarly we can define decision-marginal-MAP $\xs_{\II}^* \quad s.t. \max \big ( \sum_{\xs} \qq(\xs) \ident(\xs_{\II} = \xs^*_{\II}) \big ) > c$ and  decision-min-max  $\xs^* \quad s.t.  \min_{\xs} \max_{ \II} \ff(\xs_{\II}) \big ) > c$.% and  
% \end{example}


Here, we produce a hierarchy of inference problems  
in analogy to the polynomial~\cite{stockmeyer1976polynomial}, the counting~\cite{wagner1986complexity} and  the arithmetic~\cite{rogers1987theory} hierarchies. 

To define the hierarchy, we 
assume the following in \refDefinition{def:inference}:
\begin{easylist}
& Any two consecutive marginalization operations are distinct ($\opp{l} \neq \opp{{l+1}} \; \forall 1 \leq l < M$).
& The marginalization index sets $\JJ_l \; \forall 1 \leq l \leq M$ are non-empty. Moreover if 
$| \JJ_l| = \OO(\log(N))$ we call this marginalization operation a \magn{polynomial marginalization} as here $| \XX_{\JJ_{l}} | = \mathrm{Poly}(N)$. 
%\item inference involves M ($1 < M \leq N$) marginalization operations -- that is \emph{$M$ may grow with $N$}. 
& In defining the factor-graph, we required each factor to be polynomially computable.
In building the hierarchy, we require the operations over each semigroup to be polynomially computable as well. To this end we consider 
the set of rational numbers $\RR \subseteq \Qe^{\geq 0} \cup \{\pm \infty\}$. Note that this automatically eliminates semigroups that involve operations such as exponentiation and logarithm (because $\Qe$ is not closed under these operations) and only consider summation, multiplication, minimization
and maximization. %Here, the choice of this subset of problems is partly due to constraints imposed by the models of computation. 
\end{easylist}
We can always re-express any inference problem to enforce the first two conditions and therefore they do not impose any restriction. Below, we will use a \magn{language} to identify inference problems for an arbitrary set of factors $\FF = \{\ff_\II\}$. For example, sum-product refers to the inference problem $\sum_{\xs} \prod_\II \ff_\II(\xs_\II) \overset{?}{\geq} q$.
In this sense the rightmost ``token'' in the language (here \textit{product}) identifies the expansion semigroup $\semig_e = (\mathbb{Q}, \times)$ and the rest of tokens identify the marginalization semigroups over $\mathbb{Q}$ in the given order. Therefore, this minimal language exactly identifies the inference problem. The only information that affects the computational complexity of an inference
problem but is not specified in this language is whether each of the marginalization operations are polynomial or exponential.
%We start by the most basic forms of inference and build more difficult instances by adding marginalization operations.

%\begin{proposition}\label{th:sumsum_poly}
% sum-sum, min-min and max-max inference are in \poly.
%\end{proposition}
%(I) $\Delta$ for any operation if $\vert \JJ_1\vert = \Omega(\log(N))$.
We define five \magn{inference families}: $\Sigma, \Pi, \Phi, \Psi, \Delta$. The families
are associated with that ``outermost'' marginalization operation  -- \ie $\opp{M}$ in \refDefinition{def:inference}. 
$\Sigma$ is the family of
inference problems where $\opp{M} = \sumop$. Similarly,
$\Pi$ is associated with product, $\Phi$ with minimization and $\Psi$ with maximization.
$\Delta$ is the family of inference problems where the last marginalization is polynomial (\ie $|\JJ_M| = \OO(\log(N))$ regardless of $\opp{M}$).

Now we define \magn{inference classes} in each family, such that all the problems in the same class
have the same computational complexity. Here, the hierarchy is exhaustive -- \ie
 it includes all inference problems using any combination of the four operations sum, min, max and product
 whenever the integral $\qq(\emptyset)$ has a polynomial representation (see \refClaim{th:product_pspace}). 
 Moreover the inference classes are disjoint.
 For this, each family
is parameterized by a subscript $M$ and two sets $\sumset$ and $\pset$ (\eg $\Phi_M(\sumset, \pset)$ is an inference ``class'' in family $\Phi$). As before, $M$
is the number of marginalization operations, $\sumset$ is the set of indices
of the (exponential) $\sumop$-marginalization and $\pset$ is the set of indices of
polynomial marginalizations.
%We will see that these arguments are sufficient to 
%identify the complexity class of inference. %This becomes more clear when we define each 
%inference family. 
%Here, we will use the short notation to identify an inference problem. 
\begin{example}
Sum-min-sum-product identifies the decision problem
\begin{align*}
\sum_{\xs_{\JJ_3}} \min_{\xs_{\JJ_2}} \sum_{\xs_{\JJ_1}} \prod_{\II} \ff_\II(\xs_\II) \quad \overset{?}{\geq} \quad q
\end{align*}
where $\JJ_1$, $\JJ_2$ and $\JJ_3$ partition $\settype{N}$. Assume
$\JJ_1 = \{2,\ldots,\frac{N}{2}\}$, $\JJ_2 = \{\frac{N}{2} + 1,\ldots, N\}$ and $\JJ_3 = \{1\}$. Since we have three marginalization operations $M = 3$.
Here the first and second marginalizations are exponential and the third one is polynomial (since $|\JJ_3|$ is constant). Therefore $\pset = \{3\}$.
Since the only exponential summation is $\bigopp{1}_{\xs_{\JJ_1}} = \sum_{\xs_{\JJ_1}}$,
$\sumset = \{1\}$.
In our inference hierarchy, this problem belongs to the class $\Delta_{3}( \{1\}, \{3\})$. 

Alternatively, if we use different values for $\JJ_1$, $\JJ_2$ and $\JJ_3$ whose sizes each grow linearly with $N$,
%(\eg $\JJ_1 = \{1,\ldots,\lfloor N/3 \rfloor\}, \JJ_1 = \{\lceil N/3 \rceil, \ldots, \}$
the corresponding inference problem becomes a member of  $\Sigma_3(\{1,3\}, \emptyset)$.
%Moreover, as we will see all members of 
%this class belong to ${\Poly}^{\coNP^{\PPclass}}$.
\end{example}
\begin{remark}
Note that arbitrary assignments to $M$, $\sumset$ and $\pset$ do not necessarily define a valid inference class.
For example we require that $\sumset \cap \pset = \emptyset$ and no index in $\pset$ or $\sumset$
can be larger than $M$. Moreover, the values in $\sumset$ and $\pset$ should be compatible with the inference class. For example, for inference class $\Sigma_M(\sumset,\pset)$, $M$ is a member of $\sumset$.
For notational convenience, if an inference class notation is invalid we equate it with an empty set -- \eg $\Psi_1(\{1\}, \emptyset) = \emptyset$, because $\sumset = \{1\}$ and $M=1$ means the inference class is $\Sigma$ rather than $\Psi$. 
\end{remark}

In the definition below, we ignore the inference problems in which product
appears in any of the marginalization semigroups (\eg product-sum).
The following claim, explains this choice. %is the reason for our lack of interest in such inference problems. \marnote{\pspace}
\begin{claim}\label{th:product_pspace}%\footnote{All proofs appear in the appendix.}
For $\oplus_M = \prodop$, the inference query $\qq(\xs_{\JJ_0})$ can have an exponential representation in $N$. % and inference is outside \pspace.
\end{claim}
\begin{proof}
The claim states that when the product appears in the marginalization operations, the marginal (and integral) can become very large, such that we can no longer represent them in space polynomial in $N$.
 We show this for an integration problem. The same idea can show the exponential representation of a marginal query. %Since the integral can be obtained from a polynomial-sized marginal, the exponential representation of the integral implies the exponential representation of the marginal. For example, if $\qq(\xx_i)$ has a polynomial representation in $N$, then
%the same should hold for $\qq(\emptyset) = \bigoplus_{\xx_i} \qq(\xx_i)$. 

To see why this integral has an exponential representation in $N$, consider its simplified form
\begin{align*}
  \qq(\emptyset) = \prod_{\xs_{\II}} \qq(\xs_{\II})
\end{align*}
where $\qq(\xs)$ here is the result of inference up to the last marginalization step $\opp{M}$, which is product, where $\XX_\II$ grows exponentially with $N$. 
Recall that the hierarchy is defined for operations on $\mathbb{Q}^{\geq 0}$. Since $\qq(\xs_\II)$ for each $\xs_\II \in \XX_\II$ 
has a constant size, say  $c$, the size of representation of $\qq(\emptyset)$ using a binary scheme is 
\begin{align*}
  \left \lceil \log_2(\qq(\emptyset)) \right \rceil = \left \lceil \log_{2} \big ( \prod_{\xs_{\II}} \qq(\xs_{\II}) \big ) \right \rceil = \left \lceil \sum_{\xs_{\II}} c \right \rceil = \left \lceil c \vert \XX_\II \vert \right \rceil
\end{align*}
which is exponential in $N$.%%\qed
%The exponential representation of the query also means the corresponding computation is outside \pspace.
\end{proof}

Define the \magn{base members} of the families as
\begin{align} \label{eq:basemembers}
\Sigma_0(\emptyset, \emptyset) \defeq \{\sumop\} \quad &
\Phi_0(\emptyset, \emptyset) \defeq \{ \min \} \\
\Psi_0(\emptyset, \emptyset) \defeq \{ \max \} \quad &
\Pi_0(\emptyset, \emptyset) \defeq \{ \prodop \} \notag \\
\Delta_0(\emptyset, \emptyset) = \emptyset \quad &\Delta_{1}(\emptyset, \{1\}) \defeq \{\sumop-\sumop,\, \min-\min,\, \max-\max \} \notag
\end{align}
where the initial members of each family only identify the expansion semigroup -- \eg $\sumop$ in $\Sigma_0(\emptyset, \emptyset)$ identifies $\qq(\xs) = \sum_{\II} \ff_{\II}(\xs_\II)$.  
%where none of these initial members are actual inference problems  and only provide the basis for recursive definition of different families.
Here, the exception is $\Delta_1(\emptyset, \{1\})$, which contains three \textit{inference problems}.\footnote{We treat $M=1$ for $\Delta$ specially as in this case the marginalization operation can not be polynomial. This is because if $|\JJ_1| = \OO(\log(N))$, then $|\JJ_0| = \Omega(N)$ which violates the conditions in the definition of the inference problem. 
%Despite this exponential size of marginalization, min-min, max-max and sum-sum are in $\Poly$ and belong to $\Delta$ family; see proposition~\ref{th:sumsum_poly}.
}

Let $\Xi_M(\sumset, \pset)$ denote the union of corresponding classes within all families:
\begin{align*}
  \Xi_M(\sumset, \pset) = \Sigma_M(\sumset, \pset) \cup \Pi_M(\sumset, \pset) \cup \Phi_M(\sumset, \pset) \cup \Psi_M(\sumset, \pset) \cup \Delta_M(\sumset, \pset)
  \end{align*}
Now define the \magn{inference family members} recursively, by adding a marginalization operation to all the problems in each inference class. If this marginalization is polynomial then the new class belongs to the $\Delta$ family and the set $\pset$ is updated accordingly. Alternatively, if this outermost marginalization is exponential, depending on the new marginal operation (\ie $\min, \max, \sumop$) the new class is defined to be a member of $\Phi, \Psi$ or $\Sigma$. For the case that the last marginalization is summation set $\sumset$ is updated.
%{\small


\noindent {\bullitem\ \textbf{Adding an exponential marginalization}} $ \forall \; |\XX_{\JJ_M}| = \mathrm{Poly}(N),\, M > 0$
\begin{align}
\Sigma_{M+1}(\sumset \cup \{M+1\}, \pset) &\defeq \big \{ \sumop - \xi \mid \xi \in  \Xi_M(\sumset, \pset) \back \Sigma_{M}(\sumset, \pset)  \} \label{eq:hierarchymembers1}\\
\Phi_{M+1}(\sumset, \pset) &\defeq \big \{ \min - \xi \mid \xi \in \Xi_M(\sumset, \pset) \back \Phi_{M}(\sumset, \pset) \big \} \notag \\
\Psi_{M+1}(\sumset, \pset) &\defeq \big \{ \max - \xi \mid \xi \in \Xi_M(\sumset, \pset) \back \Psi_{M}(\sumset, \pset) \big \} \notag \\
\Pi_{M+1}(\sumset, \pset) &\defeq  \emptyset \notag 
\end{align}

\noindent \bullitem\ \textbf{Adding a polynomial marginalization} $\quad \forall \; |\XX_{\JJ_M}| =  \mathrm{Poly}(N),\, > 1$  %\;\text{and}\;\oplus \in \{\sumop,\min,\max\}
  \begin{align}\label{eq:hierarchymembers2}
\Delta_{M+1}(\sumset, \pset \cup \{M+1\}) &\defeq \big \{ \oplus-\xi \mid 
 \xi \in  \Xi_M(\sumset, \pset) \; , \oplus \in \{\min,\max,\sumop \} \big \}
\end{align}

% We will enumerate some of the members of these families shortly, but for now we need to point out special treatment of 
% $\Delta_{1}$. If inference only involves a single marginalization operation, $|\JJ_1|$ can not be sub-logarithmic in $N$, because
% it means $\JJ_0$ is linear in $N$, and the inference query $\qq(\xs_{\JJ_0})$ is exponential and not well-defined.
% On the other hand min-min, max-max and sum-sum inference problems 
% All the other inference problems using min, max, sum and product are in the \pspace; the class of decision problems that a Turing machine with polynomial
% amount of space can solve.

\subsection{Single marginalization}
Following the recursive construction of the hierarchy as defined above,
the inference classes in the hierarchy with \textit{one} marginalization are 
\begin{align}
\Delta_1(\emptyset, \{1\}) &= \{\min-\min,\; \max-\max,\; \sumop-\sumop\}\\
\Psi_1(\emptyset, \emptyset)  &= \{\max-\min,\; \max-\sumop,\; \max-\prodop\} \\
\Phi_1(\emptyset, \emptyset)  &= \{\min-\max,\; \min-\sumop,\; \min-\prodop\} \\
\Sigma_1(\{1\}, \emptyset)  &=  \{ \sumop-\prodop,\; \sumop-\min,\; \sumop-\max \}
\end{align}

Now we review all the problems above and prove that $\Delta_1, \Psi_1, \Phi_1$ and $\Sigma_1$ are complete w.r.t. \poly, \NP, \coNP\ and \PPclass\ respectively.  
Starting from $\Delta_1$:
\begin{proposition}\label{th:sumsum_poly}
sum-sum, min-min and max-max inference are in \poly.
\end{proposition}
\begin{proof}
To show that these inference problems are in \poly, we 
provide polynomial-time algorithms for them:

\noindent \bullitem\ $\sumop-\sumop$ is short for
\begin{align*}
  \qq(\emptyset) = \sum_{\xs} \sum_{\II} \ff_\II(\xs_\II)
\end{align*}
which asks for the sum over all assignments of $\xs \in \XX$, of the sum
of all the factors. It is easy to see that each factor value $\ff_\II(\xs_\II)\; \forall \II,\ \XX_\II$
is counted $\vert \XX_{\back \II} \vert$ times in the summation above.
Therefore we can rewrite the integral above as
\begin{align*}
  \qq(\emptyset) = \sum_{\II} \vert \XX_{\back \II} \vert \big ( \sum_{\xs_{\II}} \ff_{\II}(\xs_\II) \big )
\end{align*}
where the new form involves polynomial number of terms and therefore is easy to calculate.

\noindent \bullitem\ $\min-\min$ (similar for $\max-\max$) is short for
\begin{align*}
  \qq(\emptyset) = \min_{\xs} \min_{\II} \ff_\II(\xs_\II)
\end{align*}
where the query seeks the minimum achievable value of any factor.
We can easily obtain this by seeking the range of all factors and reporting the minimum value in polynomial time. %\qed
\end{proof}

Max-sum and max-prod are widely studied and it is known that their decision version are \NP-complete~\cite{shimony1994finding}.
By reduction from satisfiability we can show that max-min inference~\cite{ravanbakhsh_minmax} is also \NP-hard.%, and the corresponding decision problem is \NP-complete.\marnote{min-max complexity}

\begin{proposition}\label{th:minmaxnp}
The decision version of max-min inference that asks $\max_{\xs} \min_{\II} \ff_{\II}(\xs_\II) \overset{?}{\geq} q$ is \NP-complete.
\end{proposition}
\begin{proof}
Given $\xs$ it is easy to verify the decision problem, so max-min decision belongs to \NP. 
To show \NP-completeness, we reduce the 3-SAT to a max-min inference problem, such that
3-SAT is satisfiable \textit{iff} the max-min value is $\qq(\emptyset) \geq 1$ and unsatisfiable otherwise. 

Simply define one factor per clause of 3-SAT, such that $\ff_{\II}(\xs_{\II}) = 1$
if $\xs_{\II}$ satisfies the clause and any number less than one otherwise.
With this construction, the max-min value $\max_{\xs} \min_{\II \in \FF} \ff_{\II}(\xs_\II)$ is one \emph{iff} the original SAT problem was satisfiable, otherwise it is less than one. This reduces 3-SAT to Max-Min-decision.%\qed
\end{proof}


This means all the problems in $\Psi_1(\emptyset, \emptyset)$ are in \NP\ (and in fact are complete w.r.t.~this complexity class).
In contrast, problems in $\Phi_1(\emptyset, \emptyset)$ are in \coNP, which is the class of decision problems in which the ``NO instances'' result has a polynomial time verifiable witness or proof.
Note that by changing the decision problem from $\qq(\emptyset) \overset{?}{\geq} q$ to $\qq(\emptyset) \overset{?}{\leq} q$, the complexity classes
of problems in $\Phi$ and $\Psi$ family are reversed (\ie problems in $\Phi_1(\emptyset, \emptyset)$ become $\NP$-complete and the problems in $\Psi_1(\emptyset, \emptyset)$ become \coNP-complete).

Among the members of $\Sigma_1(\{1\}, \emptyset)$, sum-product is known to be \PPclass-complete~\cite{littman2001stochastic,roth1993hardness}.
It is easy to show the same result for sum-min (sum-max) inference.
\begin{proposition}\label{th:summinsharpp}
The sum-min decision problem $\sum_{\xs} \min_{\II} \ff_\II(\xs_\II) \overset{?}{\geq} q$ is \PPclass-complete for $\YY = \{0,1\}$.%$\ff_{\II}: \XX_{\II} \to \{0,1\}\; \forall \II$. 
\end{proposition}
 \PPclass\ is the class of problems that are polynomially solvable using a non-deterministic Turing machine, where the acceptance condition is that the majority of computation paths accept.
%$\PPclass$ as opposed to $\NP$ contains its complement.
\begin{proof}
%\PPclass\ is the class of problems that are polynomially solvable using a non-deterministic Turing machine, where the acceptance condition is that the majority of paths accept.
To see that $\sum_{\xs} \min_\II \ff_{\II}(\xs_\II) \overset{?}{\geq} q$ is in \PPclass, 
 enumerate all $\xs \in \XX$ non-deterministically and for each assignment
calculate $\min_\II \ff_{\II}(\xs_\II)$ in polynomial time 
(where each path accepts iff $\min_\II \ff_{\II}(\xs_\II) = 1$) and accept
iff at least $q$ of the paths accept.

Given a matrix $\Dn \in \{0,1\}^{N \times N}$ the problem of calculating its permanent
\begin{align*}
  \mathsf{perm}(\Dn) = \sum_{\zs \in \sn} \prod_{i = 1}^{N} \Dn_{i, \zz_i}
\end{align*}
where $\sn$ is the set of permutations of $1,\ldots,N$ 
is \sharpP-complete and the corresponding decision problem is \PPclass-complete~\cite{valiant1979complexity}.
To show completeness w.r.t. \PPclass\ it is enough to reduce the problem of computing the matrix permanent to sum-min inference in a graphical model.

The problem of computing the permanent has been reduced to sum-product inference in graphical models  \cite{huang2009approximating}. However, when $\ff_{\II}(\xs_\II) \in \{0,1\}\;\forall \II$,
sum-product is isomorphic to sum-min. This is because $y_1 \times y_2 = \min(y_1,y_2) \forall y_i \in \{0,1\}$. Therefore, the problem of computing the permanent for such matrices reduces to sum-min
inference in the factor-graph of \cite{huang2009approximating}.
\end{proof}

% Recall that
% \sharpP\ is the corresponding is the corresponding function problem that ``counts'' the number of such accepting computation paths.
% In both cases, the acceptance of a computation path can be mapped to a \textit{binary} assignment to the expanded form $\qq(\xs) \in \{\falsemath,\truemath\}$,
% where $\truemath$ means the computation path corresponding to $\qq(\xs)$ is accepted and $\qq(\xs) = \falsemath$ indicates the opposite. 
% This confinement to the binary case may at first question the generality of $\PPclass$ and $\sharpP$ to characterize inference problems in the inference hierarchy (where $\RR = \mathbb{Q}^{\geq 0}$).
% However it is alway possible to convert $\qq(\xs): \XX \to \mathbb{Q}^{\geq 0}$ to $\qq'(\xs'): \XX' \to \{\truemath, \falsemath\}$.\footnote{The conversion is pseudo-polynomial as it depends on the
% collective range of factors $\YY$}
%For example the sum-product inference where $\RR = \mathbb{Q}^{\geq 0}$. First we multiply the factors with the least common multiple of common denominator of $y \in \YY$. At this point $\RR = \mathbb{N}$.
%Then we can 
 

%their ability to characterize the complexity of inference in factor-graphs defined over $\semig_e = (\mathbb{Q}^{\geq}, \otimes)$. However, 
%it is not difficult to convert any such factor-graph to the an equivalent factor-graph on  $\semig_e = (\{0,1\}, \otimes)$ without 

 

\subsection{Complexity of general inference classes}
Let $\compclass(.)$ denote the complexity class of an inference class in the hierarchy.
In obtaining the complexity class of problems with $M > 1$, we use the following fact, which is also used in the polynomial hierarchy: $\Poly^{\NP} = \Poly^{\coNP}$~\cite{arora2009computational}. %papadimitriou2003computational}.
In fact $\Poly^{\NP^{\Aclass}} = \Poly^{\coNP^{\Aclass}}$, for any oracle $\Aclass$. 
This means that by adding a polynomial marginalization to the problems in $\Phi_M(\sumset, \pset)$ and $\Psi_M(\sumset, \pset)$,
we get the same complexity class $\compclass(\Delta_{M+1}(\sumset, \pset \cup \{M+1\}))$.
The following gives a recursive definition of complexity class for problems in the inference hierarchy.\footnote{
We do not prove the completeness w.r.t. complexity classes beyond the first level of the hierarchy and only assert the membership.
} Note that the definition of the complexity for each class is very similar to the recursive definition
of members of each class in \refEq{eq:hierarchymembers1} and \refEq{eq:hierarchymembers2}

\begin{theorem} The complexity of inference classes in the hierarchy is given by the recursion
\begin{align}
&\compclass(\Phi_{M+1}(\sumset, \pset)) =  \coNP^{\compclass(\Xi_M(\sumset, \pset) \back \Phi_M(\sumset, \pset))}\label{eq:compmin}\\
&\compclass(\Psi_{M+1}(\sumset, \pset)) =  \NP^{\compclass(\Xi_M(\sumset, \pset) \back \Psi_M(\sumset, \pset))} \label{eq:compmax}\\
&\compclass(\Sigma_{M+1}(\sumset\cup \{M+1\}, \pset)) = \PPclass^{\compclass(\Xi_M(\sumset, \pset) \back \Sigma_M(\sumset, \pset))} \label{eq:compsum}\\
&\compclass(\Delta_{M+1}(\sumset, \pset\cup \{M+1\})) =  \Poly^{\compclass(\Xi_M(\sumset, \pset))} \label{eq:comppoly}
\end{align}
where the base members are defined in \refEq{eq:basemembers} and belong to $\Poly$.
\end{theorem}
\begin{proof}
  Recall that our definition of factor graph ensures that $\qq(\xs)$ can be evaluated in polynomial time and therefore the base members are in $\Poly$ (for complexity of base members of $\Delta$ see \refTheorem{th:sumsum_poly}). We use these classes as the base of our induction and assuming the complexity classes above are correct for $M$, we show that are correct for $M+1$. We consider all the above statements one by one:
  
\noindent \bullitem\ \textit{Complexity for members of} $\Phi_{M+1}(\sumset, \pset)$:\\
 Adding an exponential-sized \emph{min}-marginalization to an inference problem with known complexity $\Aclass$,
 requires a Turing machine to non-deterministically enumerate 
$\zs_{\JJ_M} \in \XX_{\JJ_M}$ possibilities, then call the $\Aclass$
oracle with the ``reduced factor-graph'' -- in which $\xs_{\JJ_M}$ is clamped to $\zs_{\JJ_M}$ -- 
and reject iff any of the calls to oracle rejects. This means 
$\compclass(\Phi_{M+1}(\sumset, \pset)) = \coNP^{\Aclass}$.

Here, \refEq{eq:compmin} is also making another assumption expressed in the following claim.
\begin{claim}\label{claim:inproof}
All inference classes in 
$\Xi_M(\sumset, \pset) \back \Phi_M(\sumset, \pset)$ have the same complexity $\Aclass$.
\end{claim}
\begin{itemize}
  \item $M = 0$: the fact that $\qq(\xs)$ can be evaluated in polynomial time means that $\Aclass = \Poly$.
\item  $M > 0$:  $\Xi_M(\sumset, \pset) \back \Phi_M(\sumset, \pset)$  only contains one inference class -- that is exactly only one of the following cases
is correct:
\begin{itemize}
\item $M \in \sumset \; \Rightarrow \; \Xi_M(\sumset, \pset) \back \Phi_M(\sumset, \pset) = \Sigma_M(\sumset, \pset)$
\item $M \in \pset \; \Rightarrow \; \Xi_M(\sumset, \pset) \back \Phi_M(\sumset, \pset) =  \Delta_M(\sumset, \pset)$
\item $M \notin \sumset \cup \pset \; \Rightarrow \; \Xi_M(\sumset, \pset) \back \Phi_M(\sumset, \pset) =  \Psi_M(\sumset, \pset)$. \\
(in constructing the hierarchy we assume two consecutive marginalizations are distinct and the current marginalization is a minimization.)
\end{itemize}
But if $\Xi_M(\sumset, \pset) \back \Phi_M(\sumset, \pset)$ contains a single class, the inductive hypothesis ensures that all problems in $\Xi_M(\sumset, \pset) \back \Phi_M(\sumset, \pset)$ have the same complexity class $\Aclass$.
\end{itemize}
This completes the proof of our claim.

\noindent \bullitem\ \textit{Complexity for members of} $\Psi_{M+1}(\sumset, \pset)$:\\
Adding an exponential-sized \emph{max}-marginalization to an inference problem with known complexity $\Aclass$,
 requires a Turing machine to non-deterministically enumerate 
$\zs_{\JJ_M} \in \XX_{\JJ_M}$ possibilities, then call the $\Aclass$
oracle with the reduced factor-graph  
and accept iff any of the calls to oracle accepts. 
This means 
$\compclass(\Psi_{M+1}(\sumset, \pset)) = \NP^{\Aclass}$.
Here, an argument similar to that of \refClaim{claim:inproof} ensures that
$\Xi_M(\sumset, \pset) \back \Psi_M(\sumset, \pset)$
in \refEq{eq:compmax} contains a single inference class.


\noindent \bullitem\ \textit{Complexity for members of} $\Sigma_{M+1}(\sumset\cup \{M+1\}, \pset)$:\\
Adding an exponential-sized \emph{sum}-marginalization to an
inference problem with known complexity $\Aclass$,
 requires a Turing machine to non-deterministically enumerate 
$\zs_{\JJ_M} \in \XX_{\JJ_M}$ possibilities, then call the $\Aclass$
oracle with the reduced factor-graph  
and accept iff majority of the calls to oracle accepts. 
This means $\compclass(\Psi_{M+1}(\sumset, \pset)) = \PPclass^{\Aclass}$.
\begin{itemize}
\item $M = 0$: the fact that $\qq(\xs)$ can be evaluated in polynomial time means that $\Aclass = \Poly$.
\item  $M > 0$: 
  \begin{itemize}
\item $M \in \pset \; \Rightarrow \; \Xi_M(\sumset, \pset) \back \Sigma_M(\sumset, \pset) = \Delta_M(\sumset, \pset)$.
  \item $M \notin \pset \cup \sumset \; \Rightarrow \; \Xi_M(\sumset, \pset) \back \Sigma_M(\sumset, \pset) = \Psi_M(\sumset, \pset) \cup \Phi_M(\sumset, \pset)$: 
 despite the fact that $\Aclass = \compclass(\Psi_{M}(\sumset, \pset))$ is different from
$\Aclass' = \compclass(\Phi_{M}(\sumset, \pset))$, since \textit{$\PPclass$ is closed under complement},
%the Turing machine may instead accept iff majority of the calls to the oracle do NOT accept.
which means $\PPclass^\Aclass = \PPclass^{\Aclass}$ and the recursive definition of complexity  \refEq{eq:compsum} remains correct.
  \end{itemize}
\end{itemize}

\noindent \bullitem\ \textit{Complexity for members of} $\Delta_{M+1}(\sumset, \pset\cup \{M+1\})$:\\
Adding a polynomial-sized marginalization to an
inference problem with known complexity $\Aclass$,
 requires a Turing machine to deterministically enumerate 
 $\zs_{\JJ_M} \in \XX_{\JJ_M}$ possibilities in polynomial time,
 and each time call the $\Aclass$ oracle with the reduced factor-graph  
and accept after some polynomial-time calculation. This means 
$\compclass(\Psi_{M+1}(\sumset, \pset)) = \Poly^{\Aclass}$. Here, there are
three possibilities:
\begin{itemize}
\item $M = 0$: here again  $\Aclass = \Poly$.
\item $M \in \sumset \; \Rightarrow \; \Xi_M(\sumset, \pset) = \Sigma_M(\sumset, \pset)$.
  \item $M \in \pset \; \Rightarrow \; \Xi_M(\sumset, \pset) = \Delta_M(\sumset, \pset)$.
   \item $M \notin \pset \cup \sumset \; \Rightarrow \; \Xi_M(\sumset, \pset) = \Psi_M(\sumset, \pset) \cup \Phi_M(\sumset, \pset)$, in which case since $\PPclass^{\NP^{\mathbb{B}}} = \PPclass^{\coNP^{\mathbb{B}}}$, the recursive definition of complexity in \refEq{eq:comppoly} remains correct.
\end{itemize}
\end{proof}

\begin{example}\label{example:marginalmap}
  Consider the marginal-MAP inference of \refEq{eq:marginalmap}.
The decision version of this problem, $\qq(\emptyset) \overset{?}{\geq} q$,
 is a member of $\Psi_{2}(\{1\}, \emptyset)$ which also includes
 $\max-\sumop-\min$ and $\max-\sumop-\max$.
%Here, the summation operation appears as the first marginalization operation, therefore $\sumset = \{1\}$.
The complexity of this class according to \refEq{eq:compmax} is $\compclass(\Psi^{2}(\{1\}, \emptyset)) = \NP^{\PPclass}$.
However, marginal-MAP is also known to be ``complete'' w.r.t. $\NP^{\PPclass}$~\cite{park2004complexity}.
Now suppose that the max-marginalization over $\xs_{\JJ_2}$ is polynomial (\eg $|\JJ_2|$ is constant). 
Then marginal-MAP belongs to $\Delta_{2}(\{1\}, \{2\})$ with complexity $\poly^{\PPclass}$.
This is because a Turing machine can enumerate all $\zs_{\JJ_2} \in \XX_{\JJ_2}$ in polynomial time and
call its $\PPclass$ oracle to see if 
  \begin{align*}
    &\qq(\xs_{\JJ_0} \mid \zs_{\JJ_2}) \overset{?}{\geq} q\\
     \text{where} \quad &\qq(\xs_{\JJ_0} \mid \zs_{\JJ_2}) = \sum_{\xs_{\JJ_2}} \prod_{\II} \ff_{\II}(\xs_{\II \back \JJ_2}, \zs_{\II \cap \JJ_2}) 
  \end{align*}
and \emph{accept} if any of its calls to oracle accepts, and rejects otherwise.
Here, $\ff_{\II}(\xs_{\II \back \JJ_2}, \zs_{\II \cap \JJ_2})$ is the reduced factor, in which all the variables in $\xs_{\JJ_2}$ are fixed to $\zs_{\JJ_2\cap \II}$.  
\end{example}

Here, \magn{Toda's theorem} \cite{toda1991pp} has an interesting implication w.r.t.~the hierarchy. 
This theorem states that  $\PPclass$ is as hard as the polynomial hierarchy, which means
$\min-\max-\min-\ldots-\max$ inference for an arbitrary, but constant, number of min and max operations appears below the
sum-product inference in the inference hierarchy. 


\subsection{Complexity of the hierarchy}\label{sec:logical}
By restricting the domain $\RR$ to $\{0,1\}$, min and max become isomorphic to logical AND ($\wedge$) and OR ($\vee$) respectively,
where $1 \cong \truemath, 0 \cong \falsemath$. By considering the restriction of the inference hierarchy to these
two operations, we can express quantified satisfiability (QSAT) as inference in a graphical model, where $\wedge \cong \forall$ and $\vee \cong \exists$. Let each factor $\ff_\II(\xs_\II)$ be a disjunction --\eg $\ff(\xs_{i,j,k}) = \xx_i \vee \neg \xx_j \vee \neg \xx_k$. Then we have
\begin{align*}
\forall_{\xs_{\JJ_M}} \exists_{\xs_{\JJ_{M-1}}} \ldots \exists_{\xs_{\JJ_2}} \forall_{\xs_{\JJ_1}}  \bigwedge_{\II} \ff_\II(\xs_\II)\; \cong  
\min_{\xs_{\JJ_M}} \max_{\xs_{\JJ_{M-1}}} \ldots \max_{\xs_{\JJ_2}} \min_{\xs_{\JJ_1}} \min_{\II} \ff_\II(\xs_\II)
\end{align*}
By adding the summation operation, we can express the stochastic satisfiability~\cite{littman2001stochastic} and by generalizing the constraints from disjunctions 
we can represent any quantified constraint problem (QCP)~\cite{bordeaux2002beyond}.
%  \begin{align*}
% \exists_{\xs_{\JJ_M}} \invscr_{\xs_{\JJ_{M-1}}} \ldots \forall_{\xs_{\JJ_M}}  \mathbf{E}\big [ \bigwedge_{\II} \bigvee_{i \in \nb \II} \xx_i \big \big ] >  q \; \cong \max_{\xs_{\JJ_M}} \sum_{\xs_{\JJ_2}} \ldots \max_{\xs_{\JJ_M}} \big (\min_{\II} \max_{i \in \nb \II} \xx_i \big )
%  \end{align*}
QSAT, stochastic SAT and QCPs are all \pspace-complete,
where \pspace\ is the class of problems that can be solved by a (non-deterministic) Turing machine in polynomial space.
Therefore if we can show that inference in the inference hierarchy is in \pspace, 
it follows that inference hierarchy is in \pspace-complete as well.

\begin{algorithm}[h]
\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}
%\SetKwFunction{pspace_inference}{PspaceInference}
%\SetKwProg{pspace_inference}{PspaceInference}
\DontPrintSemicolon
%\Procedure{pspace_inference}{inference problem}
\Input{$\bigopp{M}_{\xs_{\JJ_M}} \bigopp{{M-1}}_{\xs_{\JJ_{M-1}}} \ldots \bigopp{1}_{\xs_{\JJ_1}} \bigotimes_{\II} \ff_\II(\xs_\II)$}
\Output{$\qq(\xs_{\JJ_0})$}
\DontPrintSemicolon
 \For(\tcp{loop over the query domain}){ \textbf{each} $\zs_{\JJ_0} \in \XX_{\JJ_0}$}{
 \For(\tcp{loop over $\XX_{i_N}$}){ \textbf{each} $\zz_{i_N} \in \XX_{i_N}$}{
.\;
.\;
.\;
\For(\tcp{loop over $\XX_{i_1}$}){ \textbf{each} $\zz_{i_{1}} \in \XX_{i_1}$}{
$\qq_{1}(\zz_{i_1}) := \bigotimes_{\II} \ff_\II(\zs_\II)$;
}
$\qq_{i_2}(\zz_{i_2}) := \bigopp{\jfun(i_1)}_{\xx_{i_1}} \qq_1(\xx_{i_1})$\;
.\;
.\;
.\;
$\qq_{N}(\zz_{i_N}) := \bigopp{\jfun(i_{{N-1}})}_{\xx_{i_{{N-1}}}} \qq_{{N-1}}(\xx_{i_{{N-1}}})$\;
}
$\qq(\zs_{\JJ_{0}}) := \bigopp{\jfun(i_{{N}})}_{\xx_{i_N}} \qq_N(\xx_{i_N})$\;
}
\caption{inference in \pspace}\label{alg:pspace_inference}
\end{algorithm}

\begin{theorem}\label{th:hierarchy_complexity}
The inference hierarchy is \pspace-complete.
\end{theorem}

\begin{proof} %(\pcref{th:hierarchy_complexity})
To prove that a problem is \pspace-complete, we have to show that 1) it is in \pspace\ and 2) a \pspace-complete problem reduces to it.
We already saw that QSAT, which is \pspace-complete, reduces to the inference hierarchy.
But it is not difficult to show that inference hierarchy is contained in \pspace.
Let 
  \begin{align*}
    \qq(\xs_{\JJ_0}) = \bigopp{M}_{\xs_{\JJ_M}} \bigopp{M-1}_{\xs_{\JJ_{M-1}}} \ldots \bigopp{1}_{\xs_{\JJ_1}} \bigotimes_{\II} \ff_\II(\xs_\II)
  \end{align*}
be any inference problem in the hierarchy.
We can simply iterate over all values of $\zs \in \XX$ in nested loops or using a recursion.
Let $\jfun(i): \{1,\ldots,N\} \to \{1,\ldots,M\}$ be the index of the marginalization that involves $\xx_i$ -- that is $i \in \JJ_{\jfun(i)}$. Moreover let $i_1,\ldots,i_N$ be an ordering of variable indices
such that $\jfun(i_k) \leq \jfun(i_{k+1})$.
\RefAlgorithm{alg:pspace_inference} uses this notation to demonstrate this procedure using nested loops.
Note that here we loop over individual domains $\XX_{i_k}$ rather than $\XX_{\JJ_m}$ and track
only temporary tuples $\qq_{i_k}$, so that the space complexity remains polynomial in $N$. 

\end{proof}

% Moreover, it is not difficult to see that restriction of the inference hierarchy to $\Delta$, $\Phi$ and $\Psi$ inference families
% with a ``fixed'' number of marginalization operations $M$, is equivalent to the polynomial hierarchy.

\section{Polynomial-time inference}\label{sec:gdl}
Our definition of inference 
was based on an expansion operation $\otimes$ and one or more marginalization operations $\opp{1}, \ldots, \opp{M}$.
If we assume only a single marginalization operation, polynomial time inference
is still not generally possible.
However, if we further assume that the expansion operation is distributive
over marginalization and the factor-graph has no loops,
exact polynomial time inference is possible. 
%The resulting inference procedure
%takes the form of message passing called Belief Propagation. More importantly, it turns out that message passing gives surprisingly good approximations even if applied to loopy graphs.
\begin{definition}
A \magn{commutative semiring} $\semiring=(\RR, \oplus, \otimes)$ is the combination of two 
commutative semigroups $\semig_e = (\RR, \otimes)$ and $\semig_m = (\RR, \oplus)$ with two additional properties
\begin{itemize} 
\item identity elements $\identt{\oplus}$ and $\identt{\otimes}$ such that $\identt{\oplus} \oplus a = a$ and $\identt{\otimes} \otimes a = a$. Moreover  $\identt{\oplus}$ is an \magn{annihilator} for $\semig_e = (\otimes, \RR)$: $a \otimes \identt{\oplus} = \identt{\oplus}\quad \forall a \in \RR$.\footnote{
When dealing with reals, this is $\identt{\oplus} = 0$; note $a \times 0 = 0$. Indeed it may be useful to view $\identt{\otimes}$ as $1 \in \Re$ and $\identt{\oplus}$ as $0 \in \Re$.}

\item distributive property: $$a \otimes (b \oplus c) = (a \otimes b) \oplus (a \otimes b)\quad \forall a,b,c \in \RR$$
\end{itemize}
\end{definition}
%Note that the identity elements are not necessary in using distributive law and message passing -- \ie the basic structure that allows efficient message passing is a combination of two commutative semigroups on the same set where one operation distributes over the other.


The mechanism of efficient inference using distributive law can be seen in a simple example: instead of  calculating $ \min(a +  b , a + c)$,
using the fact that summation distributes over minimization, we may instead obtain the same result using $a + \min(b , c)$, which requires fewer operations.
%We investigate the second property in \refSection{sec:hard_constraints}.


\begin{example}\label{example:semirings}
The following are some examples of commutative semirings:
\begin{easylist}
& Sum-product $(\Re^{\geq 0}, + , \times)$. 
& Max-product $(\Re^{\geq 0} \cup  \{-\infty\}, \max, \times)$ and $(\{0,1\}, \max, \times)$. 
& Min-max $(\settype{S}, \min, \max)$ on any ordered set $\settype{S}$. 
& Min-sum $(\Re \cup \{ \infty \}, \min, +)$ and $(\{0,1\}, \min, +)$. 
& Or-and $(\{\truemath,\falsemath\}, \vee, \wedge)$.
& Union-intersection $(2^{\SS}, \cup, \cap)$ for 
any power-set $2^{\SS}$.
& The semiring of natural numbers with greatest common divisor and least common multiple $(\settype{N},\mathsf{lcm}, \mathsf{gcd})$. 
& Symmetric difference-intersection semiring for any power-set $(2^\SS,\nabla, \cap)$.
\end{easylist}
Many of the semirings above are isomorphic --\eg $y' \cong -\log(y)$ defines an isomorphism between min-sum and max-product. 
It is also easy to show that the or-and semiring is 
isomorphic to min-sum/max-product semiring on $\RR = \{0,1\}$.
\end{example}

%\subsection{Normalized inquiries}
The inference problems in the example above have different properties indirectly inherited from their commutative semirings:
for example, the operation $\min$ (also $\max$) is a \magn{choice function},
 which means $\min_{a \in \settype{A}} a \quad \in \settype{A}$. 
The implication is that if the summation ($\oplus$) of the semiring is  
$\min$ (or $\max$), we can replace it with $\arg_{\xs_{\JJ_M}} \max$
and (if required) recover $\qq(\emptyset)$
using $\qq(\emptyset) = \bigotimes_{\II} \ff_\II(\xs^*)$ in polynomial time.

%As another example, in performing min-max inference we may ask for
%\begin{align*}
%$\xs^* \quad = \quad \arg_{\xs}\min \max_{\II} \ff_\II(\xs_\II)$
%\end{align*}
%and similarly in min-max inference we may inquire about the minimizing assignment
%\begin{align*}%\label{eq:minmax_ass}
%\xs^* \quad = \quad \arg_{\xs} \min \max_{\II} \ff_{\II}(\xs_{\II})
%\end{align*}

As another example, since both operations have inverses, sum-product is a \magn{field} \cite{pinter2012book}. 
The availability of inverse for $\otimes$ operation -- \ie when $\semig_e$ is an Abelian group -- 
has an important implication for inference:
the expanded form of \refEq{eq:expanded} can be normalized, and we may inquire about \textbf{normalized marginals}
%However if $\otimes$ operation has an inverse, inference may inquire about \magn{normalized marginals}
\begin{align}
\quad \pp(\xs_{\JJ}) \quad = \quad &  \bigoplus_{ \xs_{\back \JJ}}  \pp(\xs)&\label{eq:semiring_marginalization}\\
\text{where}\quad \pp(\xs) \quad \defeq \quad & \frac{1}{\qq(\emptyset)} \otimes \big (\bigotimes_{\II}\ff_{\II}(\xs_{\II}) \big ) &\quad \text{if} \quad \qq(\emptyset) \neq \identt{\oplus}\label{eq:p}\\
\pp(\xs) \quad \defeq \quad \identt{\oplus} &\quad \text{if} \quad \qq(\emptyset) = \identt{\oplus} \label{eq:specialp}
\end{align}
where $\pp(\xs)$ is the normalized joint form. We deal with the case where the integral evaluates to the annihilator as a special case because
division by annihilator may not be well-defined.
This also means, when working with normalized expanded form and normalized marginals, we always have
%\begin{align*}
$\bigoplus_{\xs_{\JJ}} \pp(\xs_{\JJ}) = \identt{\otimes}$ 
%\end{align*}
\begin{example}
Since $\semig_{e} = (\Re^{>0}, \times)$ and $\semig_{e} = (\Re, +)$
are both Abelian groups, min-sum and sum-product inference have normalized marginals. 
For min-sum inference this means $\min_{\xs_{\JJ}}\pp(\xs_{\JJ}) = \identt{\sumop} = 0$. However, for min-max inference, since $(\SS, \max)$ is not Abelian, normalized marginals are not defined.
\end{example}

We can apply the identity and annihilator of a commutative semiring to define constraints.
%Our interest in constraints as special type of factors is solely because it enables us to 
%establish the complexity of inference in commutative semirings.
\begin{definition}\label{def:constraint}
A \magn{constraint} is a factor $\ff_\II: \XX_{\II} \to \{\identt{\otimes}, \identt{\oplus}\}$
whose range is limited to identity and annihilator of the expansion monoid.\footnote{Recall that a monoid is a semigroup with an identity. 
The existence of identity here is a property of the semiring.}
\end{definition}
Here, $\ff_{\II}(\xs) = \identt{\oplus}$ iff $\xs$ is forbidden and 
$\ff_{\II}(\xs) = \identt{\otimes}$ iff it is permissible. 
A \magn{constraint satisfaction problem} (CSP) %~\cite{mackworth1977consistency} 
is any inference problem on a semiring
in which all factors are constraints. Note that this allows definition 
of the ``same'' CSP on any commutative semiring and also indicates that inference in general semirings should be difficult. The following theorem formalizes this intuition.
%The idea of using different semirings to define CSPs has been studied in the 
%past~\cite{bistarelli1999semiring}, however its implication about inference on commutative
%semirings has been ignored.
\begin{theorem}\label{th:semiring_inference}
Inference in any commutative semiring is \NP-hard under randomized polynomial-time reduction.
\end{theorem}
\begin{proof}
To prove that inference in any semiring $\semiring = (\RR, \identt{\oplus}, \identt{\otimes})$ is \NP-hard under randomized polynomial
 reduction, we deterministically reduce \textit{unique satisfiability} (USAT) to an inference problems on any semiring.
USAT is a so-called ``promise problem'', that asks whether a satisfiability problem that is promised to have either zero or one satisfying assignment is satisfiable.
\cite{valiant1986np} prove that a polynomial time randomized algorithm (\RP) for USAT
implies that \RP=\NP.
%Unique satisfiability is a variation of satisfiability in which the problem has either one or zero solution and it is .

For this reduction consider a set of binary variables $\xs \in \{0,1\}^{N}$, 
one per each variable in the given instance of USAT.
For each clause, define a constraint factor $\ff_{\II}$ such that $\ff_{\II}(\xs_{\II}) = \identt{\otimes}$ if $\xs_{\II}$ satisfies that clause and  $\ff_{\II}(\xs_{\II}) = \identt{\oplus}$ otherwise. This means, $\xs$ is a satisfying assignment for USAT iff $\qq(\xs) = \bigotimes_{\II} \ff_\II(\xs_{\II}) = \identt{\otimes}$. If the instance is unsatisfiable, the integral $\qq(\emptyset) = \bigoplus_{\xs} \identt{\oplus} = \identt{\oplus}$ (by definition of $\identt{\oplus}$).
If the instance is satisfiable there is only a single instance $\xs^*$ for which $\qq(\xs^*) = \identt{\otimes}$, and therefore the integral evaluates to $\identt{\otimes}$.
Therefore we can decide the satisfiability of USAT by performing inference on any semiring, by only relying on the properties of identities.  
%The satisfying assignment can be recovered using a decimation procedure, assuming access to an oracle for inference on the semiring.

% Now, assuming $\qq(\emptyset) = \identt{\otimes}$, we show how to recover the satisfying assignment $\xs^*$ by having access to an oracle that performs inference over the semiring.
% Start from the complete factor-graph (constructed above) and find the marginal $\qq(\xx_1)$ by calling the oracle.
% If $\qq(\xx_1) = \identt{\oplus} \; \forall \xx_1 \in \XX_1$ then the given 3-SAT instance is unsatisfiable.
% This is because by definition of identity $\qq(\emptyset) = \bigoplus_{\xx_1} \qq(\xx_1) = \identt{\oplus}$ and therefore
\end{proof}
\begin{example}
Inference on xor-and semiring $(\{\truemath,\falsemath\}, \xor, \wedge)$, where each factor has
a disjunction form, is called parity-SAT, 
which asks whether the number of SAT solutions is even or odd. A corollary to theorem~\ref{th:semiring_inference} is that parity-SAT is \NP-hard under randomized reduction,
which is indeed the case \cite{valiant1986np}.
%If we swap the $\otimes$ and $\oplus$ in the semiring we get another inference problem, called
%XOR-SAT, which is not a semiring. XOR-SAT is in \poly\ as one may use Gaussian elimination to solve it in polynomial time~\cite{schaefer1978complexity}.
\end{example}
We find it useful to use the same notation for the 
 \magn{identity function} $\ident(\mathrm{condition})$ -- \eg
\begin{align}\label{eq:identity}
  \ident(\mathrm{cond.}) \; \defeq \;  \left \{ 
\begin{array}{r c c c}
 &(+,\times) & (\min,+) & (\min,\max)\\
\mathrm{cond.} = \truemath & 1 & 0 & -\infty\\
\mathrm{cond.} = \falsemath & 0 & +\infty & +\infty\\
\end{array}   
\right .
\end{align}
where the intended semiring for $\ident(.)$ function will be clear from the context. 



\subsection{Distributive law and its limits}\label{sec:bp}
A naive approach to inference over commutative semirings  
\begin{align}\label{eq:semiringinference}
\qq(\xs_{\JJ}) \quad = \quad \bigoplus_{\xs_{\back \JJ}} \bigotimes_{\II} \ff_{\II}(\xs_\II) 
\end{align}
or its normalized version (\refEq{eq:semiring_marginalization}), involves constructing a complete $N$-dimensional array of $\qq(\xs)$
using the tensor product $\qq(\xs) \; = \; \bigotimes_\II \ff_\II(\xs_\II)$ and then perform $\oplus$-marginalization.
However, the number of elements in $\qq(\xs)$ is $\vert \XX \vert$, which is exponential in $N$, the number of variables.


If the factor-graph is loop free, 
we can use distributive law to make inference tractable. 
Assuming $\qq(\xs_\KK)$ (or $\qq(\xx_k)$) is the marginal of interest, form a tree with $\KK$ (or $k$) as its root.
Then starting from the leaves, using the distributive law, we can move the $\oplus$ inside the $\otimes$ 
 and define ``messages'' from leaves towards the root as follows:
\begin{align}
\msgq{i}{{{\II}}}(\xx_i) \quad & = \quad  \bigotimes_{\JJ \in \nb{i} \back \II} \msgq{{\JJ}}{i}(\xx_i) \label{eq:miI_semiring}\\
\msgq{{{\II}}}{i}(\xx_i) \quad & = \quad  \bigoplus_{ \xs_{\back i}} \ff_{{\II}}(\xs_{\II})
\bigotimes_{j \in \nb \II \back i} \msgq{j}{{\II}}(\xx_{j})  \label{eq:mIi_semiring}
\end{align}
where \refEq{eq:miI_semiring} defines the message from a variable to a factor, 
closer to the root and similarly \refEq{eq:mIi_semiring} defines the message from factor ${\II}$ to a variable $i$ closer to the root.
%as the product of $\ff_{\II}$ and all the incoming messages to this factor from variables 
%other than $i$ (which are further away from the root), marginalized over $\xx_i$.
Here, the distributive law allows moving the $\bpplus$ over the domain $\XX_{\II \back i}$ from outside to inside of \refEq{eq:mIi_semiring} --
the same way $\oplus$ moves its place in $(a \otimes b) \oplus (a \otimes c)$ to give $a \otimes (b \oplus c)$, where 
$a$ is analogous to a message.

\begin{figure}
\centering
\includegraphics[width=.5\textwidth]{bp.pdf}
\caption[Belief Propagation on a loop-free factor-graph]{The figure shows a loop-free factor-graph and the direction of 
messages sent between variable and factor nodes in order to calculate the marginal over the grey region.}
\label{fig:bp-tree}
\end{figure}

By starting from the leaves, and calculating the messages towards the root, we obtain 
the marginal over the root node as the product of incoming messages
\begin{align}
%\qq(\xs_{\II}) \quad &= \quad  \ff_{\II}(\xs_{\II}) \otimes \left (\bigotimes_{i \in \nb \II} \msg{i}{\II}(\xx_i) \right )\\
\qq(\xx_{k}) \quad &= \quad  \bigotimes_{\II \in \nb k} \msgq{\II}{k}(\xx_k)
\end{align}
%and the integral $\partition$ as 
%\begin{align}
%\partition = \bigoplus_{\XX_i} \qq(\xx_{i})
%\end{align}
In fact, we can assume any
subset of variables $\xs_{\AAA}$ (and factors within those variables) to be the root. Then, the set of all incoming messages to $\AAA$, 
produces the marginal 
\begin{align}\label{eq:bpmarg_region}
\qq(\xs_{\AAA}) \quad = \quad \left ( \bigotimes_{\II \subseteq \AAA} \ff_{\II}(\xs_{\II}) \right ) \left (\bigotimes_{i \in \AAA, \JJ \in \nb i, \JJ \not \subseteq \AAA} \msgq{\JJ}{i}(\xs_i) \right )
\end{align}

\begin{example}
Consider the joint form represented by the factor-graph of  \refFigure{fig:bp-tree} 
\begin{align*}
  \qq(\xs) \quad = \quad \bigotimes_{\AAA \in \{\II,\JJ,\KK, \mathrm{L},\mathrm{O},\mathrm{T},\mathrm{U},\mathrm{V},\mathrm{W},\mathrm{X},\mathrm{Y},\mathrm{Z}\}}  \ff_{\AAA}(\xs_{\AAA}) 
\end{align*}
and the problem of calculating the marginal over $\xs_{\{i,j,k\}}$ (\ie the shaded region).
\begin{align*}
  \qq(\xs_{\{i,j,k\}}) \quad = \quad \bigoplus_{\xs_{\back \{i,j,k\}}} \quad \bigotimes_{\AAA \in \{\II,\JJ,\KK, \mathrm{L},\mathrm{O},\mathrm{T},\mathrm{U},\mathrm{V},\mathrm{W},\mathrm{X},\mathrm{Y},\mathrm{Z}\}}  \ff_{\AAA}(\xs_{\AAA}) 
\end{align*}

We can move the $\oplus$ inside the $\otimes$ to obtain
\begin{align*}
 \qq(\xs_{\{i,j,k\}}) \quad = \quad  \ff_{\II}(\xs_{\II}) \bptimes \msgq{\mathrm{L}}{i}(\xx_i) \bptimes \msgq{\mathrm{K}}{i}(\xx_i) \bptimes \msgq{\mathrm{V}}{j}(\xx_j) \bptimes \msgq{\mathrm{W}}{j}(\xx_j) \bptimes \msgq{\mathrm{K}}{k}(\xx_k)
\end{align*}
where each term $\msgq{\AAA}{i}$ factors the summation on the corresponding sub-tree.
For example 
\begin{align*}
  \msgq{\mathrm{L}}{i} \quad = \quad \bigoplus_{\xx_w} \ff_{\mathrm{L}}(\xs_{\mathrm{L}})
\end{align*}

Here the message $\msgq{\mathrm{W}}{j}$ is itself a computational challenge
\begin{align*}
  \msgq{\mathrm{W}}{j} \quad = \quad \bigoplus_{\xs_{\back j}} \bigotimes_{\AAA \in \{\mathrm{W}, \mathrm{U}, \mathrm{Y}, \mathrm{X}, \mathrm{O}, \mathrm{T}, \mathrm{Z} \} }\ff_{\mathrm{\AAA}}(\xs_{\AAA})
\end{align*}

However we can also decompose this message over  sub-trees
\begin{align*}
  \msgq{\mathrm{W}}{j} \quad = \quad \bigoplus_{\xs_{\back j}} \ff_{\mathrm{\AAA}}(\xs_{\AAA})
\bptimes \msgq{e}{\mathrm{W}}(\xx_{e}) \bptimes \msgq{r}{\mathrm{W}}(\xx_{r})
\end{align*}
where again, using the distributive law, $\msgq{e}{\mathrm{W}}$ and  $\msgq{r}{\mathrm{W}}$ 
further simplify based on the incoming messages to the variable nodes $\xx_r$ and $\xx_e$.
\end{example}

This procedure is known as Belief Propagation (BP), which is sometimes prefixed with the corresponding semiring -- \eg sum-product BP.
Even though BP is only guaranteed to produce correct answers when the factor-graph is a
tree (and few other cases \cite{Aji1998,Weiss2001a,bayati2005maximum,weller2013map}), 
it performs surprisingly well when applied as a fixed point iteration to graphs with loops \cite{Murphy1999,gallager1962low}. In the case of loopy graphs, the message updates are repeatedly applied in the hope of convergence. 
Here, for numerical stability, when the $\otimes$ operator has an inverse, the messages are normalized. We use $\propto$ to indicate this normalization according to the mode of inference  
\begin{align}
\msg{{{\II}}}{i}(\xx_i) \quad & \propto \quad   \bigoplus_{ \xs_{\back i}} \ff_{{\II}}(\xs_{\II})
\bigotimes_{j \in \nb \II \back i} \msg{j}{{\II}}(\xx_{j})  & \;\propto\; \MSG{\II}{i}(\msgss{\nb \II \back i}{\II})(\xx_i)\label{eq:mIi_semiring_norm}\\
\msg{i}{{{\II}}}(\xx_i) \quad & \propto \quad   \bigotimes_{\JJ \in \nb{i} \back \II} \msg{{\JJ}}{i}(\xx_i)  &\;\propto\; \MSG{i}{\II}(\msgss{\nb i \back \II}{i})(\xx_i)\label{eq:miI_semiring_norm}\\
\ph(\xs_{\II}) \quad &\propto \quad   \ff_{\II}(\xs_{\II}) \bigotimes_{i \in \nb \II} \msgs{i}{\II}(\xx_i)  &\quad \label{eq:marg_semiring_factor_norm}\\
\ph(\xx_{i}) \quad & \propto \quad    \bigotimes_{\II \in \nb i} \msg{\II}{i}(\xx_i)  &\quad \label{eq:marg_semiring_norm}
\end{align}
%where $\partit{\II}{i}$, $\partit{i}{\II}$, $\partition_i$ and $\partition_\II$ are normalization constants and can be used to recover the integral $\partition$ (see \refSection{sec:meta}).
%For simplicity, we will sometimes drop these constants
Here, for general graphs, $\ph(\xx_i)$ and $\ph(\xs_{\II})$ are approximations to $\pp(\xx_i)$
and $\pp(\xs_\II)$ of \refEq{eq:semiring_marginalization}.
The \textbf{functionals} $\MSG{i}{\II}(\msg{\nb i \back \II}{i})(.)$ and 
$\MSG{\II}{i}(\msgss{\nb \II \back i}{\II})(.)$ cast the BP message updates as an operator on a subset of incoming messages -- \ie $\msgss{\nb i \back \II}{i} = \{ \msg{\JJ}{i} \mid \JJ \in \nb i \back \II \}$. We use these functional notation in presenting the algebraic form of survey propagation in \refSection{sec:sp}.

\subsection{The limits of message passing}\label{sec:limits}
By observing the application of distributive law in semirings, a natural question to ask is: can we use distributive law for polynomial time inference on loop-free graphical models over any of the inference problems at higher levels of inference hierarchy or in general, for any inference problem with more than one marginalization operation?
The answer to this question is further motivated by the fact that, when loops exists, the same scheme may become a powerful approximation technique. 
When we have more than one marginalization operations, a natural assumption in using distributive law 
is that the expansion operation distributes over all the marginalization operations -- \eg  as in min-max-sum (where sum distributes over both min and max), min-max-min, xor-or-and.
\index{marginalization!two operations}
\index{inference!efficient}
Consider the simplest case with three operators $\opp{1}$, $\opp{2}$ and $\otimes$, where $\otimes$ distributes over both $\opp{1}$ and $\opp{2}$.
Here the integration problem is
$$\qq(\emptyset) \quad = \quad \bigopp{2}_{\xs_{\JJ_2}} \bigopp{1}_{\xs_{\JJ_1}} \bigotimes_{\II} \ff_{\II}(\xs_\II)$$
where $\JJ_1$ and $\JJ_2$ partition $\{1,\ldots,N\}$.

In order to apply distributive law for each pair $(\opp{1}, \otimes)$ and $(\opp{2}, \otimes)$, we need to be able to commute $\opp{1}$ and $\opp{2}$ operations.
That is, we require 
\begin{align}\label{eq:op_commute}
\bigopp{1}_{\xs_{\AAA}} \bigopp{2}_{\xs_{\BBB}} \fg(\xs_{\AAA \cup \BBB}) = \bigopp{2}_{\xs_\BBB} \bigopp{1}_{\xs_{\AAA}} \fg(\xs_{\AAA \cup \BBB}).
\end{align}
for the specified $\AAA \subseteq \JJ_1$ and $\BBB \subseteq \JJ_2$.
%To see why this is necessary, consider 
%the example of \refFigure{fig:bp}.

Now, consider a simple case involving two binary variables $\xx_i$ and $\xx_j$, where $\fg(\xs_{\{i,j\}})$ is 
\vspace{.05in}
\begin{center}
\scalebox{.8}{
\begin{tabu}{r r |[2pt] c | c }
\multicolumn{2}{c}{}&\multicolumn{2}{c }{$\xx_j$}\\
\multicolumn{2}{c}{}&0&1\\\tabucline[2pt]{3-4}
\multirow{2}{*}{$\xx_i$}&0&a&\multicolumn{1}{c |[2pt]}{b}\\\cline{2-4}
&1&c&\multicolumn{1}{c |[2pt]}{d}\\\tabucline[2pt]{3-4}
\end{tabu}
}
\end{center}
\vspace{.05in}
Applying \refEq{eq:op_commute} to this simple case (\ie $\AAA = \{i\}, \BBB=\{j\}$), we require
$$
  (a \opp{1} b) \opp{2} (c \opp{1} d) \quad = \quad (a \opp{2} b) \opp{1} (c \opp{2} d). 
$$

The following theorem leads immediately to a  negative result:
\begin{theorem}\cite{eckmann1962group}:
\begin{align*}
  (a \opp{1} b) \opp{2} (c \opp{1} d) \; = \; (a \opp{2} b) \opp{1} (c \opp{2} d)
\quad \Leftrightarrow \quad \opp{1} = \opp{2} \quad \forall a,b,c
\end{align*}
\end{theorem}
\noindent which implies that \emph{direct application of distributive law to tractably and exactly solve any  inference problem with more than one marginalization operation is unfeasible, even for tree structures.} This limitation was previously known for marginal MAP inference~\cite{park2004complexity}.
\index{marginal MAP}

Min and max operations have an interesting property in this regard.
Similar to any other operations for min and max we have
\begin{align*}
  \min_{\xs_{\JJ}} \max_{\xs_{\II}} \fg(\xs_{\II \cup \JJ}) \neq \max_{\xs_{\II}} \min_{\xs_{\JJ}} \fg(\xs_{\II \cup \JJ})
\end{align*}

However,
\index{minimax theorem}
\index{game theory}
\index{graphical games}
\index{graphical models!game theory}
 if we slightly change the inference problem (from pure assignments $\xs_{\JJ_l}  \in \XX_{\JJ_l}$ to a distribution over assignments; \aka mixed strategies), as a result of the celebrated \emph{minimax theorem} \cite{von2007theory}, the min and max operations commute -- \ie
\begin{align*}
   \min_{\strat(\xs_{\JJ})} \max_{\strat(\xs_{\II})} \sum_{\xs_{\II \cup \JJ}} \strat(\xs_{\JJ}) \fg(\xs_{\II \cup \JJ}) \strat(\xs_{\II}) \quad = \quad \max_{\strat(\xs_{\II})} \min_{\strat(\xs_{\JJ})} \sum_{\xs_{\II \cup \JJ}}  \strat(\xs_{\II}) \fg(\xs_{\II \cup \JJ}) \strat(\xs_{\JJ_1})
\end{align*}
where $\strat(\xs_{\JJ_1})$ and $\strat(\xs_{\JJ_2})$ are mixed strategies.
This property has enabled addressing problems with min and max marginalization operations using message-passing-like procedures. For example, \cite{ibrahimi2011robust} solve this (mixed-strategy) variation of min-max-product inference. Message passing procedures that operate on graphical models for game theory  (\aka ``graphical games'')  also rely on this property~\cite{ortiz2002nash,kearns2007graphical}.

\section{Algebra of survey propagation}\label{sec:sp}
Survey propagation (SP) was first introduced as a message passing solution to satisfiability~\cite{braunstein_survey_2002} and was later generalized to general CSP
\cite{braunstein_constraint_2002} and arbitrary inference problems over factor-graphs~\cite{Mezard09}.
Several works offer different interpretations and generalizations of survey propagation \cite{Kroc2002,braunstein_survey_2003,maneva_new_2004}.
Here, we propose a generalization based the same notions that extends the application of BP to arbitrary commutative semirings.
Our derivation generalizes the variational approach of  
\cite{Mezard09}, in the same way that the algebraic approach to BP (using commutative semirings) generalizes the variational derivation of sum-product and min-sum BP.


As a fixed point iteration procedure,
if BP has more than one fixed points,
it may not converge at all. Alternatively, if the messages are initialized properly, BP may converge to one of its fixed points.
SP equations take ``all'' BP fixed points into account.
We view this task, of dealing with all fixed points, as using a third binary operation 
%In our algebraic perspective, this accounting of all fixed points is using a third operation
$\spplus$ on $\RR$. In particular, we require that $\otimes$ also distribute over $\spplus$, forming 
a second commutative semiring. We refer to this new semiring as a \magn{SP semiring}. 
To better explain the role of the third operation we need to introduce some notation.

Let $\msgss{\cdot}{\cdot}$ be a BP fixed point -- that is let
$$
\msgss{\cdot}{\cdot} = \{\, \msg{i}{\II} = \MSG{i}{\II}(\msgss{\nb i\back \II}{i}),
 \msg{\II}{i} = \MSG{\II}{i}(\msgss{\nb \II \back i}{\II})\, \mid \mid \forall i, \II \in \nb i \,\}
$$
and denote the set of all such fixed points by $\WW$.
Each BP fixed point corresponds to an approximation to the integral $\qq(\emptyset)$,
which we denote by $\QQ(\msgss{\cdot}{\cdot})(\emptyset)$ -- using this functional form
to emphasize the dependence of this approximation on BP messages.
Recall that in the original problem, $\XX$ is the domain of assignments, 
$\qq(\xs)$ is the  expanded form and $\bpplus$-marginalization is (approximately) performed by BP.
In the case of survey propagation, $\WW$ is the domain of assignments and the integral $\QQ(\msgss{\cdot}{\cdot})(\emptyset)$ 
evaluates a particular assignment $\msgss{\cdot}{\cdot}$ to all the messages -- \ie 
$\QQ(\msgss{\cdot}{\cdot})(\emptyset)$  is the new expanded form.


In this algebraic perspective, SP efficiently performs a second integral  using $\spplus$ over all fixed points:
\begin{align}\label{eq:sp_q_intmarg}
\QQ(\emptyset)(\emptyset) = \bigspplus_{\msgss{\cdot}{\cdot} \in \WW} \QQ(\msgssq{\cdot}{\cdot})(\emptyset)
\end{align}
%\QQ(\msg{\II}{})(\xx_i) \propto \bigspplus_{\msgss{\cdot}{\cdot} \in \WW} %\QQ(\msgssq{\cdot}{\cdot})(\xx_i)\quad \text{and} \quad
\RefTable{table:sp} summarizes this correspondence. It is not immediately obvious how this second integration can be usefull in practice.
The following examples attempts to motivate SP before we explain its derivation.

\begin{example}
If the $\otimes$ operator of the semiring has an inverse, any BP fixed point $\msgss{\cdot}{\cdot}$ represents a joint form $\ph(\xs)$. We can explicitly write this distribution
based on BP marginals (ergo BP messages):
%\begin{proposition} \label{th:reparam} and the factor-graph is loop-free, we can write $\pp(\xs)$ as
\begin{align}\label{eq:semiring_reparam}
  \ph(\xs) \quad = \quad \frac{\bigbptimes_\II \ph(\xs_\II)}{\bigbptimes_i \big ( \ph(\xx_i) \powerop ({ \vert \nb i \vert - 1 }) \big )} \quad = \quad \PH(\msgss{\cdot}{\cdot})(\xs) 
\end{align}
where the inverse is w.r.t $\otimes$ and the \textit{exponentiation operator} is defined as $a \powerop b \defeq \underbrace{a \otimes \ldots \otimes a}_{b\; \text{times}}$. Our notation using $\PH(\msgss{\cdot}{\cdot})(\xs)$ is to explicitly show the dependence of this joint form on BP messages.
To see why this is correct, we use the exactness of BP on trees and 
 substitute BP marginals \refEqs{eq:marg_semiring_norm}{eq:marg_semiring_factor_norm}
into \refEq{eq:semiring_reparam}:
\begin{align*}
  &\frac{\bigbptimes_\II \ph(\xs_\II)}{\bigbptimes_i \big ( \ph(\xx_i) \powerop ({ \vert \nb i \vert - 1 }) \big )} & \quad = \quad 
  &\frac{\bigbptimes_\II  \ff_{\II}(\xs_{\II}) \bigotimes_{i \in \nb \II} \msg{i}{\II}(\xx_i)}{\bigbptimes_i 
\big ( \bigotimes_{\II \in \nb i} \msg{\II}{i}(\xx_i) \powerop ({ \vert \nb i \vert - 1 }) \big )} & = \\
&\frac{\bigbptimes_\II  \ff_{\II}(\xs_{\II}) \bigotimes_{i \in \nb \II} \msg{i}{\II}(\xx_i)}{\bigbptimes_i 
\big ( \bigotimes_{\II \in \nb i} \msg{i}{\II}(\xx_i) \big )} & \quad = \quad
&\bigbptimes_\II  \ff_{\II}(\xs_{\II}) \quad = \quad  \pp(\xs)
\end{align*}


In some interesting settings for sum-product inference, BP has many ``disjoint'' fixed points, in the sense that $\ph(\xs)$ estimates (as defined above) have small overlap with each other (\eg citep{Mezard1987}) -- \ie $\pp(\xs) \approx \sum_{\msgss{\cdot}{\cdot} \in \WW} \PH(\msgss{\cdot}{\cdot})(\xs)$. In this setting the BP estimate of the integral (and marginals) is inaccurate. However, summing over all such BP integrals gives a more accurate estimate of $\qq(\emptyset)$. This is an application of SP where $\bpplus = \spplus = +$ in \refEq{eq:sp_q_intmarg}. %The same argument extends to the estimate of marginals in these settings.
\end{example}


\begin{table}
\tbl{The correspondance between BP and SP}{
\begin{tabu}{ r|[2pt]l}
\textbf{Belief Propagation} & \textbf{Survey Propagation} \\
\multicolumn{2}{l}{domain:}\\
$\xs$ & $\msgss{\cdot}{\cdot}$ \\ 
$\forall i \quad \xx_i$ & $\msg{i}{\II}\;,\; \msg{\II}{i} \quad \forall i, \II \in \nb i$  \\ 
$\XX$ & $\WW$ \\
\multicolumn{2}{l}{expanded form:}\\
$\qq(\xs)$ & $\QQ(\msgss{\cdot}{\cdot})(\emptyset)$\\
\multicolumn{2}{l}{integration:}\\
 $\qq(\emptyset) = \bigbpplus_{\xs} \qq(\xs)$ & $\QQ(\emptyset)(\emptyset) = \bigspplus_{\msgss{\cdot}{\cdot}} \QQ(\msgss{\cdot}{\cdot})(\emptyset)$\\
\multicolumn{2}{l}{marginalization:}\\
 $\pp(\xx_i) \propto \bigbpplus_{\xs \back i} \pp(\xs)$ & $\PSP(\msg{\II}{i}) \propto \bigspplus_{\back \msgss{\II}{i}} \PP(\msgss{\cdot}{\cdot})$\\
\multicolumn{2}{l}{factors:}\\
$ \forall \II \quad \ff_\II(\xs_\II) $ & $\PHT_\II(\msgss{\nb \II}{\II})(\emptyset)$, $\PHT_i(\msgss{\nb i \back \II}{i})(\emptyset)$ and $\MSGBIT{i}{\II}(\msg{i}{\II},\msg{\II}{i})(\emptyset)^{-1} \quad \forall i, \II \in \nb i$
\end{tabu}
}
\label{table:sp}
\end{table}

%Here, we propose a second commutative semiring $(\RRSP,\spplus,\sptimes)$, s.t. $\sptimes = \bptimes$
%and further require $(\RR, \bptimes)$ to be an Abelian group (\ie every element of $\RR$ has an inverse w.r.t. $\bptimes$.\footnote{
%  The requirement for $\bptimes$ to have an inverse is for convenience of presenting SP as BP over a factor-graph. This condition is only used to define the factors $\MSGBIT{i}{\II}^{-1}$ in \cref{th:integral_decompose}. However this type of factor is introduced, and then removed in proposition~\ref{th:simplify_sp} (see also the  claim~\ref{claim:simplify_sp} on \cpageref{claim:simplify_sp}). 
%This suggests that the requirement for division is superficial and is a result of 
% defining SP as BP on a factor-graph. The implication is that the non-uniform version
%of SP is probably applicable to commutative semirings without inverse for $\bptimes$ operator.  
%})
%The $\spplus$ operator in the new semiring decides ``how'' to account for original BP fixed points.


Our derivation of SP requires $(\RR, \bptimes)$ to be an Abelian group (\ie every element of $\RR$ has an inverse w.r.t.~$\bptimes$).
We require $\bptimes$ to be invertable as we need to work with normalized BP
and SP messages.
In \refSection{sec:uniformsp} we introduce another variation of SP that simply counts the 
BP fixed points and relaxes this requirement.

%In the next section we see that when BP uses normalized messages the integral $\QQ(\msgssq{\cdot}{\cdot})(\emptyset)$ decomposes into local factors. This means we can
%use BP on a new graphical model to infer $\QQ(\emptyset)(\emptyset)$. The simplified
%form of BP equations when applied to the new factor-graph is called survey propagation.

%Our treatment generalizes the two previously studied variations of Survey Propagation (SP),
%namely entropic and energetic SP and their temperature limits ( using Parisi parameter \eg see \cite{Mezard2009,spmore}).
\subsection{Decomposition of the integral}
\label{sec:decompose_integral}
In writing the normalized BP equations in \refSection{sec:bp}, we hid the normalization constant using $\propto$ sign.
Here we explicitly define the normalization constants or \magn{local integrals} by defining unnormalized messages, based on their normalized version
\begin{align}
\msgt{\II}{i}(\xx_i) \quad &\defeq \quad   \bigoplus_{ \xs_{\back i}} \ff_{{\II}}(\xs_{\II}) 
\bigotimes_{j \in \nb \II \back i} \msg{j}{{\II}}(\xx_{j}) \quad &\defeq \quad \MSGT{\II}{i}(\msgss{\nb \II \back i}{\II})(\xx_i) \label{eq:mIi_partition}\\
\msgt{i}{\II}(\xx_i)  \quad &\defeq \quad   \bigotimes_{\JJ \in \nb{i} \back \II} \msg{{\JJ}}{i}(\xx_i)  \quad &\defeq \quad  \MSGT{i}{\II}(\msgss{\nb i \back \II}{i})(\xx_i)\label{eq:miI_partition}\\
\pht_\II(\xs_\II)  \quad &\defeq \quad   \ff_{\II}(\xs_{\II}) \bigotimes_{i \in \nb \II} \msgss{i}{\II}(\xx_i)   \quad &\defeq \quad \PHT_\II(\msgss{\nb \II}{\II})(\xs_\II) \label{eq:marg_factor_partition}\\
\pht_i(\xx_i) \quad  &\defeq \quad  \bigotimes_{\II \in \nb i} \msg{\II}{i}(\xx_i)  \quad &\defeq \quad  \PHT_i(\msgss{\nb i}{i})(\xx_i)  \label{eq:marg_partition}
\end{align}
where each update also has a functional form on the r.h.s.
%where on the r.h.s. we still use the normalized messages.
In each case, the local integrals are simply the integral of unnormalized messages or marginals -- \eg $\msgt{\II}{i}(\emptyset) = \bigoplus_{\xx_i} \msgt{\II}{i}(\xx_i)$.

Define the functional $\MSGBIT{i}{\II}(\msg{i}{\II},\msg{\II}{i})$ as the product of messages from $i$ to $\II$ and vice versa
\begin{align} \label{eq:bi_direction}
  \msgbit{i}{\II}(\xx_i) \quad \defeq \quad  \msg{i}{\II}(\xx_i) \otimes \msg{\II}{i}(\xx_i) \quad \defeq \quad \MSGBIT{i}{\II}(\msg{i}{\II},\msg{\II}{i})(\xx_i)
\end{align}

%The following theorem is at the heart of our derivation.

%Let $\msgss{\cdot}{\cdot} \defeq \{\msg{i}{\II}, \msg{\II}{i} \mid i, \II \in \nb i\}$ denote the set of all BP messages 
%and also let $\QQ(\msgss{\cdot}{\cdot})(\emptyset)$
%be the integral $\qq(\emptyset)$ as a function of BP messages.
%\marnote{integral from messages}
\begin{theorem}\label{th:integral_decompose} 
If the factor-graph has no loops and $(\RR, \otimes)$ is an Abelian group, the global integral decomposes to local BP integrals as
  \begin{align}\label{eq:partition_decomp_nofunc}
    \qq(\emptyset) \quad = \quad \bigotimes_{\II} \pht_\II(\emptyset) \;\bigotimes_i\pht_i(\emptyset)
\left (\bigotimes_{i, \II \in \nb i} \msgbit{i}{\II}(\emptyset) \right )^{-1}  
  \end{align}
or in other words $\qq(\emptyset)  =  \QQ(\msgss{\cdot}{\cdot})(\emptyset)$ where
  \begin{align}\label{eq:partition_decomp}
    \QQ(\msgss{\cdot}{\cdot})(\emptyset) = \bigotimes_{\II} \PHT_\II(\msgss{\nb \II}{\II})(\emptyset) \;\bigotimes_i\PHT_i(\msgss{\nb i}{i})(\emptyset)
 \left ( \bigotimes_{i, \II \in \nb i} \MSGBIT{i}{\II}(\msg{i}{\II},\msg{\II}{i})(\emptyset) \right)^{-1} 
  \end{align}
\end{theorem}
\begin{proof} 
For this proof we build a tree around an  root node $r$
that is connected to one factor. (Since the factor-graph is a tree such a node always exists.) 
Send BP messages from the leaves, up towards the root $r$ and back to the leaves. 
Here, any message $\msgq{i}{\II}(\xx_i)$,
can give us the integral for the sub-tree that contains all the nodes and factors up to node $i$ using $\msgq{i}{\II}(\emptyset) = \bigbpplus_{\xx_i}\msgq{i}{\II}(\xx_i)$.
Noting that the root is connected to exactly one factor, the global integral is 
\begin{align}\label{eq:genesis}
\bigbpplus_{\xx_r} \qq(\xx_r) = \bigbpplus_{\xx_r} \bigbptimes_{\II \in \nb r} \msgq{\II}{r}(\xx_r) = 
\msgq{\II}{r}(\emptyset)
\end{align}

On the other hand, we have the following relation between $\msgq{i}{\II}$ and $\msg{i}{\II}$ (also corresponding factor-to-variable message)
\begin{align}
  \msgq{i}{\II}(\xx_i) &= \msg{i}{\II}(\xx_i) \bptimes \msgq{i}{\II}(\emptyset) \quad \forall i, \II \in \nb i \label{eq:integral_subs1}\\
  \msgq{\II}{i}(\xx_i) &= \msg{\II}{i}(\xx_i) \bptimes \msgq{\II}{i}(\emptyset) \quad \forall i, \II \in \nb i \label{eq:integral_subs2}
\end{align}

Substituting this into BP \refEqs{eq:miI_semiring}{eq:mIi_semiring} we get
\begin{align}
\msgq{i}{{{\II}}}(\xx_i) \quad & = \quad  \bigotimes_{\JJ \in \nb{i} \back \II} \msgq{\JJ}{i}(\emptyset) \msg{{\JJ}}{i}(\xx_i) \label{eq:step1_1}\\
\msgq{{{\II}}}{i}(\xx_i) \quad & = \quad  \bigoplus_{ \xs_{\back i}} \ff_{{\II}}(\xs_{\II}) 
\bigotimes_{j \in \nb \II \back i} \msgq{j}{{\II}}(\emptyset) \msg{j}{{\II}}(\xx_{j})  
\label{eq:step1_2}
\end{align}
By summing over both l.h.s and r.h.s in equations above and substituting from \refEq{eq:miI_partition}, we get
\begin{align}
\bigbpplus_{\xx_i} \msgq{i}{{{\II}}}(\xx_i) \quad & = \quad  \left ( \bigotimes_{\JJ \in \nb{i} \back \II} \msgq{\JJ}{i}(\emptyset) \right ) \otimes \left (\bigbpplus_{\xx_i} \bigotimes_{\JJ \in \nb{i} \back \II}  \msg{{\JJ}}{i}(\xx_i) \right ) \Rightarrow \notag \\
\msgq{i}{{{\II}}}(\emptyset) \quad & = \quad  \msgt{i}{\II}(\emptyset)\; \bigotimes_{\JJ \in \nb{i} \back \II} \msgq{\JJ}{i}(\emptyset) \label{eq:recurse_1}
\end{align}
and similarly for \refEq{eq:step1_2} using integration and substitution from \refEq{eq:mIi_partition} we have
\begin{align}
\bigbpplus_{\xx_i} \msgq{{{\II}}}{i}(\xx_i) \quad & = \quad  \left ( \bigotimes_{j \in \nb \II \back i} \msgq{j}{{\II}}(\emptyset) \right) \otimes \left( \bigoplus_{ \xs_{\II}} \ff_{{\II}}(\xs_{\II}) 
\bigotimes_{j \in \nb \II \back i} \msg{j}{{\II}}(\xx_{j})  \right ) \Rightarrow \notag \\
\msgq{{{\II}}}{i}(\emptyset) \quad & = \quad   \msgt{\II}{i}(\emptyset)
\bigotimes_{j \in \nb \II \back i} \msgq{j}{{\II}}(\emptyset)   \label{eq:recurse_2}
\end{align}

\RefEqs{eq:recurse_1}{eq:recurse_2} are simply recursive integration on a tree, where the integral
up to node $i$ (\ie $\msgq{i}{{{\II}}}(\emptyset)$ in \refEq{eq:recurse_1}) is reduced to the integral over its sub-trees.
By unrolling this recursion we see that $\msgq{i}{{{\II}}}(\emptyset)$ is simply the product of all $\msgt{\II}{i}(\emptyset)$ and $\msgt{\II}{i}(\emptyset)$
in its sub-tree, where the messages are towards the root. \RefEq{eq:genesis}
tells us that the global integral is not different.
Therefore, \refEqs{eq:recurse_1}{eq:recurse_2} we can completely expand the recursion
for the global integral.
For this, let $\uparrow i$
restrict the $\nb i$ to the factor that is higher than variable $i$ in the tree (\ie closer to the root $r$). Similarly let $\uparrow \II$ be the variable that is closer to the root than $\II$.
We can write the global integral as
 \begin{align}\label{eq:partition_by_message_partition}
   \qq(\emptyset) = \bigbptimes_{i, \II = \uparrow i} \msgt{i}{\II}(\emptyset) \bigbptimes_{\II, i = \uparrow \II} \msgt{\II}{i}(\emptyset)
 \end{align}

\RefProposition{th:simplify_sp} shows that these local integrals can be written in terms of local integrals of interest -- \ie
  \begin{align*}
    \msgt{\II}{i}(\emptyset) \quad = \quad \frac{\pht_\II(\emptyset)}{\msgbit{i}{\II}(\emptyset)} \quad \text{and} \quad
    \msgt{i}{\II}(\emptyset) \quad = \quad \frac{\pht_i(\emptyset)}{\msgbit{i}{\II}(\emptyset)}
  \end{align*}
Substituting from the equations above into \refEq{eq:partition_by_message_partition} we get
the equations of \refTheorem{th:integral_decompose}. %\qed
\end{proof}

% \begin{proof}%(\pcref{th:simplify_sp})
%  By definition of $\pht_\II(\xs_\II)$ and $\msg{i}{\II}(\xx_i)$ in \refEqs{eq:mIi_partition}{eq:marg_factor_partition}
% \begin{align*}
%   \pht_\II(\xx_i) =  \msgt{\II}{i}(\xx_i) \bptimes \msg{i}{\II}(\xx_i) \quad &\Rightarrow \quad \bigbpplus_{\xx_i}\pht_\II(\xx_i) = \bigbpplus_{\xx_i} \msgt{\II}{i}(\xx_i) \bptimes \msg{i}{\II}(\xx_i) 
% &\Rightarrow\\
% \pht_{\II}(\emptyset) = \msgt{\II}{i}(\emptyset) \bptimes \left (\bigbpplus_{\xx_i} \msg{\II}{i}(\xx_i) \bptimes \msg{i}{\II}(\xx_i) \right ) \quad &\Rightarrow \quad \pht_{\II}(\emptyset) = \msgt{\II}{i}(\emptyset) \bptimes \msgbit{i}{\II}(\emptyset)
% \end{align*}
% where in the last step we used \refEq{eq:bi_direction}.

% Similarly for the second statement of the proposition we have
% \begin{align*}
%   \pht_i(\xx_i) =  \msgt{i}{\II}(\xx_i) \bptimes \msg{\II}{i}(\xx_i) \quad &\Rightarrow \quad \bigbpplus_{\xx_i}\pht_i(\xx_i) = \bigbpplus_{\xx_i} \msgt{i}{\II}(\xx_i) \bptimes \msg{\II}{i}(\xx_i) 
% &\Rightarrow\\
% \pht_{i}(\emptyset) = \msgt{i}{\II}(\emptyset) \bptimes \big (\bigbpplus_{\xx_i} \msg{\II}{i}(\xx_i) \bptimes \msg{i}{\II}(\xx_i) \big ) \quad &\Rightarrow \quad \pht_{i}(\emptyset) = \msgt{i}{\II}(\emptyset) \bptimes \msgbit{i}{\II}(\emptyset)
% \end{align*}
% \end{proof}

%When the factor-graph has loops, this decomposition only gives an approximation.   $\QQ(\msgss{\cdot}{\cdot})(\emptyset)$ to also denote the approximation.

\subsection{The new factor-graph and semiring}\label{sec:newsemiring}
% Assume that BP has several (possibly exponentially many) fixed points, where each fixed point is identified with an assignment to all BP messages ($\msgss{\cdot}{\cdot}$).
% % \begin{align}
% % \msgss{.}{.} = \{\msg{i}{\II}, \msg{\II}{i} \mid i, \II \in \nb i\}   
% % \end{align}

% Denote the set of messages that satisfy BP equations by $\WW$ -- \ie
% \begin{align}
%   \WW \; \defeq \; \bigg \{  \msgss{\cdot}{\cdot}
% \mid \forall i, \II \in \nb i \quad \msg{i}{\II} = \MSG{i}{\II}(\msgss{\nb i\back \II}{i}),
%  \msg{\II}{i} = \MSG{\II}{i}(\msgss{\nb \II \back i}{\II}) 
%  \bigg \}
% \end{align}

% Recall that in the original problem, $\XX$ is the domain of assignments and $\qq(\xs)$ is the  expanded form 
% on the semiring $(\RR, \bpplus, \bptimes)$. 
% In the new semiring $(\RRSP, \spplus, \sptimes)$, $\WW$ is domain of assignments and the integral $\QQ(\msgss{\cdot}{\cdot})(\emptyset)$ 
% evaluates a particular assignment $\msgss{\cdot}{\cdot}$ to all the messages.
% \cref{table:sp} summarizes this correspondence.
The decomposition of integral in \refTheorem{th:integral_decompose} means $\QQ(\msgss{\cdot}{\cdot})(\emptyset)$
has a factored form. Therefore, a factor-graph with 
$\msgss{\cdot}{\cdot}$ as the set of variables and 
three different types of factors corresponding to different
terms in the decomposition -- \ie $\PHT_\II(\msgss{\nb \II}{\II})(\emptyset)$, $\PHT_i(\msgss{\nb i \back \II}{i})(\emptyset)$ and $\MSGBIT{i}{\II}(\msg{i}{\II},\msg{\II}{i})(\emptyset)^{-1}$ -- can represent $\QQ(\msgss{\cdot}{\cdot})(\emptyset)$. %This means the expanded form in the new 
%factor-graph evaluates to the BP integral in the original factor-graph.

%Here, $\sptimes = \bptimes$ ensures that for a particular fixed point $\msgs{\cdot}{\cdot}$
%the SP semiring-product (\ie $\sptimes$) of these factors evaluate to the integral in the 
%original inference problem. 

\RefFigure{fig:spfg} shows a simple factor-graph 
and the corresponding SP factor-graph. The new factor-graph has one variable per each message in the
original factor-graph and three types of factors as discussed above.
Survey propagation is simply belief propagation applied to the  this new factor-graph using
the new semiring.
As before, BP messages are exchanged between variables and factors.
But here, we can simplify BP messages by substitution and only keep two types of factor-to-factor messages. 
We use $\msp{i}{\II}$ and $\msp{\II}{i}$ to denote these two types of SP messages.
These messages are exchanged between two types of factors, namely $\PHT_\II(\msgss{\nb \II}{\II})(\emptyset)$ and $\PHT_i(\msgss{\nb i \back \II}{i})(\emptyset)$.
Since the third type of factors $\MSGBIT{i}{\II}(\msg{i}{\II},\msg{\II}{i})(\emptyset)^{-1}$ 
are always connected to only two variables, $\msg{i}{\II}$ and $\msg{\II}{i}$, 
we can simplify their role in the SP message update to get 
\begin{align}
  \msp{i}{\II}(\msg{i}{\II}, \msg{\II}{i}) \; &\propto \; \bigspplus_{\back \msg{i}{\II},\msg{\II}{i}} \left ( \frac{\PHT_i(\msgss{\nb i}{i})(\emptyset)}{\MSGBIT{i}{\II}(\msg{i}{\II},\msg{\II}{i})(\emptyset)} \;
 \bigbptimes_{\JJ \in \nb i \back \II} \msp{\JJ}{i}(\msg{i}{\JJ},\msg{\JJ}{i}) \right ) \label{eq:spiI_first}\\
  \msp{\II}{i}(\msg{i}{\II}, \msg{\II}{i}) \; &\propto \; \bigspplus_{\back \msg{i}{\II},\msg{\II}{i} } \left (\frac{\PHT_\II(\msgss{\nb \II}{\II})(\emptyset)}{\MSGBIT{i}{\II}(\msg{i}{\II},\msg{\II}{i})(\emptyset)} \;
 \bigbptimes_{j \in \nb \II \back i} \msp{j}{\II}(\msg{j}{\II},\msg{\II}{j}) \right ) \label{eq:spIi_first}
\end{align}
where in all cases we are assuming the messages $\msgss{\cdot}{\cdot} \in \WW$ are consistent with each other -- \ie satisfy BP equations on the original factor-graph.
Note that, here again we are using the normalized BP message update and the normalization
factor is hidden using $\propto$ sign. This is possible because we assumed $\bptimes$ has an inverse.  
%Also note that in these update, all the messages depend on ``two variables''.
We can further simplify this update using the following proposition.

\begin{figure}
\centering
\includegraphics[width=1\textwidth]{sp_both}
\caption[Survey propagation factor-graph.]{Part of a factor-graph (left) and the corresponding SP factor-graph on the right.
The variables in SP factor-graph are the messages in the original graph. The SP factor-graph
has three type of factors: (I)~$\PHT_\II(.)(\emptyset)$, (II)~$\PHT_i(.)(\emptyset)$ and (III)~${\MSGBIT{i}{\II}(.)(\emptyset)}^{-1}$. 
As the arrows suggest, SP message updates
are simplified so that only two type of messages are exchanged: $\msp{i}{\II}$ and $\msp{\II}{i}$ between factors of type (I) and (II).
}
\label{fig:spfg}
\end{figure}


\begin{proposition} \label{th:simplify_sp} For $\msgss{\cdot}{\cdot} \in \WW$
  \begin{align} 
    \frac{\PHT_i(\msgss{\nb i}{i})(\emptyset)}{\MSGBIT{i}{\II}(\msg{\II}{i}, \msg{i}{\II})(\emptyset)} \; &= \; \MSGT{i}{\II}(\msgss{\nb i \back \II}{i})(\emptyset) \\
\quad &\text{and} \quad \notag \\
    \frac{\PHT_\II(\msgss{\nb \II}{\II})(\emptyset)}{\MSGBIT{i}{\II}(\msg{\II}{i}, \msg{i}{\II})(\emptyset)} \; &= \;  \MSGT{\II}{i}(\msgss{\nb \II \back i}{\II})(\emptyset)
  \end{align}
\end{proposition}
\begin{proof}
 By definition of $\pht_\II(\xs_\II)$ and $\msg{i}{\II}(\xx_i)$ in \refEqs{eq:mIi_partition}{eq:marg_factor_partition}
\begin{align*}
  \pht_\II(\xx_i) =  \msgt{\II}{i}(\xx_i) \bptimes \msg{i}{\II}(\xx_i) \quad &\Rightarrow \quad \bigbpplus_{\xx_i}\pht_\II(\xx_i) = \bigbpplus_{\xx_i} \msgt{\II}{i}(\xx_i) \bptimes \msg{i}{\II}(\xx_i) 
&\Rightarrow\\
\pht_{\II}(\emptyset) = \msgt{\II}{i}(\emptyset) \bptimes \left (\bigbpplus_{\xx_i} \msg{\II}{i}(\xx_i) \bptimes \msg{i}{\II}(\xx_i) \right ) \quad &\Rightarrow \quad \pht_{\II}(\emptyset) = \msgt{\II}{i}(\emptyset) \bptimes \msgbit{i}{\II}(\emptyset)
\end{align*}
where in the last step we used \refEq{eq:bi_direction}.

Similarly for the second statement of the proposition we have
\begin{align*}
  \pht_i(\xx_i) =  \msgt{i}{\II}(\xx_i) \bptimes \msg{\II}{i}(\xx_i) \quad &\Rightarrow \quad \bigbpplus_{\xx_i}\pht_i(\xx_i) = \bigbpplus_{\xx_i} \msgt{i}{\II}(\xx_i) \bptimes \msg{\II}{i}(\xx_i) 
&\Rightarrow\\
\pht_{i}(\emptyset) = \msgt{i}{\II}(\emptyset) \bptimes \big (\bigbpplus_{\xx_i} \msg{\II}{i}(\xx_i) \bptimes \msg{i}{\II}(\xx_i) \big ) \quad &\Rightarrow \quad \pht_{i}(\emptyset) = \msgt{i}{\II}(\emptyset) \bptimes \msgbit{i}{\II}(\emptyset)
\end{align*}
\end{proof}


The term on the l.h.s. in the proposition above appear in \refEqs{eq:spiI_first}{eq:spIi_first} and the terms on the r.h.s.~are local message integrals given by \refEqs{eq:mIi_partition}{eq:miI_partition}.
We can enforce $\msgss{\cdot}{\cdot} \in \WW$, by enforcing BP updates 
$\msg{i}{\II} = \MSG{i}{\II}(\msgss{\nb i \back \II}{i})$ and 
$\msg{\II}{i} = \MSG{\II}{i}(\msgss{\nb \II \back }{\II})$ ``locally'', 
during the message updates in the new factor-graph.
Combining this constraint with the simplification offered by
\refProposition{th:simplify_sp} gives us the SP message updates 
{\small
\begin{align}
  \msp{i}{\II}(\msg{i}{\II}) &\propto  \underset{\msgss{\nb i \back \II}{i}}{\bigspplus} \left (  
\ident\big ( \msg{i}{\II} = \MSG{i}{\II}(\msgss{\nb i \back \II}{i}) \big) \bptimes 
\MSGT{i}{\II}(\msgss{\nb i \back \II}{i})(\emptyset) \;  
 \bigbptimes_{\JJ \in \nb i \back \II} \msp{\JJ}{i}(\msg{\JJ}{i}) \right )\label{eq:spiI_semiring}\\
  \msp{\II}{i}(\msg{\II}{i})  &\propto  \underset{\msgss{\nb \II \back i}{\II}}{\bigspplus} \left ( 
\ident\big ( \msg{\II}{i} = \MSG{\II}{i}(\msgss{\nb \II \back i}{\II}) \big) \bptimes 
\MSGT{\II}{i}(\msgss{\nb \II \back i}{\II})(\emptyset) \;
 \bigbptimes_{j \in \nb \II \back i} \msp{j}{\II}(\msg{j}{\II}) \right ) \label{eq:spIi_semiring}
\end{align}
}%
where $\ident(.)$ is the identity function on the SP semiring, where $\ident(\truemath) = \identt{\bptimes}$ and
$\ident(\falsemath) = \identt{\spplus}$.

Here each SP message is a functional over all possible BP messages between the same variable and factor. However, in updating the SP messages, the identity functions
ensure that only the messages that locally satisfy BP equations are taken into account.
%can make a contribution according to their local integral. 
Another difference from the updates of \refEqs{eq:spiI_first}{eq:spIi_first} is that SP messages
have a single argument. This is because the new local integrals either depend on
$\msg{i}{\II}$ or $\msg{\II}{i}$, and not both.

\begin{example} In variational approach, survey propagation comes in two variations: entropic $\mathrm{SP}(\xi)$ and energetic $\mathrm{SP}(\mathbf{y})$ \cite{Mezard09}. For the readers familiar
with variational derivation of SP, here we express the relation to the algebraic approach.
According to the variational view, the partition function of the \textit{entropic SP}  is  $\sum_{\msgss{\cdot}{\cdot}} e^{\xi \log(\QQ(\msgss{\cdot}{\cdot})(\emptyset))}$, where $\QQ(\msgss{\cdot}{\cdot})(\emptyset)$ is the partition function for the sum-product semiring.
The entropic SP has an inverse temperature parameter, \aka \textit{Parisi parameter}, $\xi \in \Re$. It is easy to see that $\xi = 1$ corresponds to $\spplus = +, \bpplus=+$ and $\bptimes = \times$ in our algebraic approach. 
The limits of $\xi \to \infty$ corresponds to $\spplus = \max$. On the other hand, the limit of
$\xi \to 0$ amounts to ignoring $\QQ(\msgss{\cdot}{\cdot})(\emptyset)$ and corresponds to the counting SP; see \refSection{sec:uniformsp}.

The \textit{energetic $\mathrm{SP}(\mathbf{y})$} is different only in the sense that 
$\QQ(\msgss{\cdot}{\cdot})(\emptyset)$ in $\sum_{\msgss{\cdot}{\cdot}} e^{-\mathbf{y} \log(\QQ(\msgss{\cdot}{\cdot})(\emptyset))}$ is the ground state energy.
This corresponds to $\spplus = +, \bpplus=\max$ and $\bptimes = \sum$, and the limits of
the inverse temperature parameter $\mathbf{y} \to \infty$ is equivalent to $\spplus = \min, \bpplus=\min$ and $\bptimes = \sum$.
By taking an algebraic view we can choose between both operations and domains. For instance,
an implication of algebraic view is that all the variations of SP can be applied to the domain of complex numbers $\RR = \Ce$.
\end{example}


\subsection{The new integral and marginals}
Once again we can use \refTheorem{th:integral_decompose}, this time to approximate the \emph{SP integral}
$\QQ(\emptyset)(\emptyset) = \bigspplus_{\msgss{\cdot}{\cdot}} \QQ(\msgss{\cdot}{\cdot})(\emptyset)$
using local integral of SP messages.

The \emph{SP marginal} over each BP message $\msg{i}{\II}$ or $\msg{\II}{i}$ 
is the same as the corresponding SP message -- \ie $\PSP(\msg{i}{\II}) = \msp{i}{\II}(\msg{i}{\II})$.
To see this in the factor-graph of \refFigure{fig:spfg},
note that each message variable is connected to two factors, and both of these factors are already
contained in calculating one SP messages.

Moreover, from the SP marginals over messages we can recover the SP marginals over BP marginals
which we denote by $\PSP(\ph)(\xx_i)$.
For this, we simply need to enumerate all combinations of BP messages that produce a particular marginal (weighting them by their local integral $\PHT_i(\msgss{\nb i}{i})(\emptyset)$)
\begin{align}\label{eq:sp_marg}
  \PSP(\ph)(\xx_i) \; \propto \; \bigspplus_{\msgss{\nb i}{i}} \ident(\ph(\xx_i) = \PP(\msgss{\nb i}{i})(\xx_i)) \bptimes \PHT_i(\msgss{\nb i}{i})(\emptyset) \bigbptimes_{\II \in \nb i} \msp{\II}{i}(\msg{\II}{i}) 
\end{align}

% \begin{example}
% %Depending on the BP and SP semiring this marginal my imply a marginal over the orginal domain $\XX_i$.
% For entropic SP, where BP and SP are performed on real domain with $\bpplus = \spplus = +$ and $\bptimes = \times$, the marginal of \refEq{eq:sp_marg} implies a marginal $\pp^*(\xx_i)$
% on the original domain $\XX_i$ 
% \begin{align}\label{eq:sp_implicit_marg}
%   \pp^*(\xx_i) \; = \; \int_{\pp} \pp(\xx_i)  \PSP(\pp)\; \mathrm{d}x
% \end{align}

% In thermodynamic limit of an spin-glass system $\pp^*(\xx_i)$ is an improved approximation over $\ph(\xx_i)$,
% because the Gibbs measure~\cite{} decomposes to non-overlapping states and BP fixed points may represent one such state.
% \end{example}

% \begin{itemize}
% \item $(\spplus: +, \bpplus:+, \bptimes: .)$: 
% \item $(\spsum: +, \bpsum:\max, \bptimes: .)$: MAP values of compatible cases are added to produce the marginals. The SP marginal for a particular value is the sum of MAP values of compatible messages.
% \item $(\spplus: \min, \bpplus:\min, \bptimes: .)$: the minimum over compatible values is calculated.
%  \item $(\spplus: \max, \bpplus:+, \bptimes: .)$: only the locally consistent fixed point with largest partition function count towards each message/marginal value. 
% \end{itemize}



\subsection{Counting survey propagation}\label{sec:uniformsp}
Previously we required the $\otimes$ operator to have an inverse, so that we can decompose the BP integral $\qq(\emptyset)$ into local integrals.
%(see \refSection{sec:decompose_integral}).
Moreover, for a consistent decomposition of the BP integral, SP and BP semiring previously shared the $\otimes$ operation.\footnote{This is because, if the expansion operation $\sptimes$ was different from the expansion operation of BP, $\bptimes$, the expanded form $\QQ(\msgss{\cdot}{\cdot})$ in the SP factor-graph
would not evaluate the integral $\qq(\emptyset)$ in the BP factor-graph, even in factor-graphs without any loops.}
 
Here, we lift these requirements by discarding the BP integrals altogether. This means SP semiring could be completely distinct from BP semiring and $(\RR, \otimes)$ does not have to be an Abelian group. This setting is particularly interesting when the SP semiring is sum-product over real domain 
\begin{align}
  \msp{i}{\II}(\msg{i}{\II}) \; &\propto \; \sum_{\msgss{\nb i \back \II}{i}}  
\ident\big ( \msg{i}{\II} = \MSG{i}{\II}(\msgss{\nb i \back \II}{i}) \big) 
 \prod_{\JJ \in \nb i \back \II} \msp{\JJ}{i}(\msg{\JJ}{i}) \label{eq:spiI_counting}\\
  \msp{\II}{i}(\msg{\II}{i}) \; &\propto \; \sum_{\msgss{\nb \II \back i}{\II}} 
\ident\big ( \msg{\II}{i} = \MSG{\II}{i}(\msgss{\nb \II \back i}{\II}) \big) 
 \prod_{j \in \nb \II \back i} \msp{j}{\II}(\msg{j}{\II})  \label{eq:spIi_counting}
\end{align}

Here, the resulting SP integral $\QQ(\msgss{\cdot}{\cdot}) = \sum_{\msgss{\cdot}{\cdot}} \ident(\msgss{\cdot}{\cdot} \in \WW)$ simply ``counts'' the number of BP fixed points and
SP marginals over BP marginals (given by \refEq{eq:sp_marg}) which approximates the frequency of a particular
marginal.
The original survey propagation equations in \cite{braunstein_survey_2002}, which are very
successful in solving satisfiability,
correspond to counting SP applied to the or-and semiring.%, where the marginals of \refEq{eq:sp_marg} were used to find satisfying solutions.
%The SP marginals over BP marginals (\refEq{eq:}) are simply
%with $(\{0,1\}, \bpplus = ?, \bptimes =?)$ and $(\Re, \spplus = +, \bptimes =.)$
%to solve constraint satisfaction problems. 
%Also, because we relaxed the requirement for $\bptimes$-inverse, we can apply uniform SP to min-max %semirings.
\begin{example}
Interestingly, in all min-max problems with discrete domains $\XX$, min-max BP messages can only take the values that are in the range of factors -- \ie $\RR = \YY$.
This is because any ordered set is closed under min and max operations.
Here, each counting SP message $\msp{i}{\II}(\msg{i}{\II}): \YY^{|\XX_i|} \to \Re$
is a discrete distribution over all possible min-max BP messages.
This means counting survey propagation where the BP semring is min-max is  
computationally ``tractable''.
In contrast, (counting) SP, when applied to sum-product BP over real domains, is not tractable.
This is because, in this case, each SP message is a distribution over an uncountable set:
$\msp{i}{\II}(\msg{i}{\II}): \Re^{|\XX_i|} \to \Re$.

In practice, (counting) SP is only interesting if it remains tractable. The most
well-known case corresponds to counting SP when applied to the or-and semiring. In this case
the factors are constraints and the domain of SP messages is $\{\truemath, \falsemath\}^{|\XX_i|}$.
Our algebraic perspective extends this set of tractable instances. For example, it show that 
counting SP can be used to count the number of fixed points of BP when applied to xor-and or min-max semiring.  
\end{example}



\section*{Conclusion}
This paper builds on previous work to addresses three basic questions about inference in graphical models:
(\textbf{I}) \emph{``what is an inference problem in a graphical model?''}  We use the combination of commutative semigroups and a factor-graph to answer this question in a broad sense, generalizing a variety of previous models.
(\textbf{II}) \emph{``How difficult is inference?''} By confining inference to four operations of min, max, sum and product that easily lend themselves to models of computation, we build an inference hierarchy
that is complete for \pspace\ and organizes inference problems into complexity classes with increasing levels of difficulty.
Only a few of these problems had previously been studied and 
only a handful of them now have a variational interpretation.
%This hierarchy reduces to polynomial hierarchy and formulates quantified boolean satisfiability and 
%stochastic satisfiability as inference problems in graphical models.
Moreover, we prove that inference for ``any'' commutative semiring is \NP-hard under randomized reduction, which generalizes previous results for particular semirings.  
(\textbf{III}) \emph{``When does distributive law help?''} After reviewing the algebraic form of belief propagation, and the conditions that allow its normalized form, we show that application of distributive law in performing exact inference is limited to inference problems with one marginalization operation. (\textbf{IV}) Finally we extend the algeberaic treatment of message passing techniques to survey propagation. This perspective generalizes SP to new settings and we hope that it also makes this powerfull message passing procedure -- that has its origins in statistical physics -- more accessible to the machine learning community.

% Acknowledgments
%\begin{acks}
%The authors would like to thank someone.
%\end{acks}

% Bibliography
\bibliographystyle{ACM-Reference-Format-Journals}
\bibliography{refs.bib}
                             % Sample .bib file with references that match those in
                             % the 'Specifications Document (V1.5)' as well containing
                             % 'legacy' bibs and bibs with 'alternate codings'.
                             % Gerry Murray - March 2012

% History dates
%\received{November 2014}{ddd}{ddd}


% Electronic Appendix
%\elecappendix

%\medskip

%\section{This is an example of Appendix section head}


%\section{Appendix section head}

\end{document}
% End of v2-acmsmall-sample.tex (March 2012) - Gerry Murray, ACM



arxive2.bbl
%%% -*-BibTeX-*-
%%% Do NOT edit. File created by BibTeX with style
%%% ACM-Reference-Format-Journals [18-Jan-2012].

\begin{thebibliography}{00}

%%% ====================================================================
%%% NOTE TO THE USER: you can override these defaults by providing
%%% customized versions of any of these macros before the \bibliography
%%% command.  Each of them MUST provide its own final punctuation,
%%% except for \shownote{}, \showDOI{}, and \showURL{}.  The latter two
%%% do not use final punctuation, in order to avoid confusing it with
%%% the Web address.
%%%
%%% To suppress output of a particular field, define its macro to expand
%%% to an empty string, or better, \unskip, like this:
%%%
%%% \newcommand{\showDOI}[1]{\unskip}   % LaTeX syntax
%%%
%%% \def \showDOI #1{\unskip}           % plain TeX syntax
%%%
%%% ====================================================================

\ifx \showCODEN    \undefined \def \showCODEN     #1{\unskip}     \fi
\ifx \showDOI      \undefined \def \showDOI       #1{{\tt DOI:}\penalty0{#1}\ }
  \fi
\ifx \showISBNx    \undefined \def \showISBNx     #1{\unskip}     \fi
\ifx \showISBNxiii \undefined \def \showISBNxiii  #1{\unskip}     \fi
\ifx \showISSN     \undefined \def \showISSN      #1{\unskip}     \fi
\ifx \showLCCN     \undefined \def \showLCCN      #1{\unskip}     \fi
\ifx \shownote     \undefined \def \shownote      #1{#1}          \fi
\ifx \showarticletitle \undefined \def \showarticletitle #1{#1}   \fi
\ifx \showURL      \undefined \def \showURL       #1{#1}          \fi

\bibitem[\protect\citeauthoryear{Aji and McEliece}{Aji and McEliece}{2001}]%
        {Aji01}
{S Aji} {and} {R McEliece}. 2001.
\newblock \showarticletitle{{The Generalized distributive law and free energy
  minimization}}. In {\em Allerton Conf}.
\newblock


\bibitem[\protect\citeauthoryear{Aji, Horn, and McEliece}{Aji
  et~al\mbox{.}}{1998}]%
        {Aji1998}
{Srinivas~M Aji}, {Gavin~B Horn}, {and} {Robert~J McEliece}. 1998.
\newblock \showarticletitle{{On the Convergence of iterative decoding on graphs
  with a single cycle}}. In {\em Proc 1998 IEEE Int Symp Information Theory}.
\newblock


\bibitem[\protect\citeauthoryear{Aji and McEliece}{Aji and McEliece}{2000}]%
        {Aji2000}
{S~M Aji} {and} {R~J McEliece}. 2000.
\newblock \showarticletitle{{The generalized distributive law}}.
\newblock {\em Information Theory, IEEE Transactions on\/} {46}, 2 (2000),
  325--343.
\newblock


\bibitem[\protect\citeauthoryear{Arora and Barak}{Arora and Barak}{2009}]%
        {arora2009computational}
{Sanjeev Arora} {and} {Boaz Barak}. 2009.
\newblock {\em Computational complexity: a modern approach}.
\newblock Cambridge University Press.
\newblock


\bibitem[\protect\citeauthoryear{Bacchus}{Bacchus}{1991}]%
        {bacchus1991representing}
{Fahiem Bacchus}. 1991.
\newblock {\em Representing and reasoning with probabilistic knowledge: a
  logical approach to probabilities}.
\newblock MIT press.
\newblock


\bibitem[\protect\citeauthoryear{Bayati, Shah, and Sharma}{Bayati
  et~al\mbox{.}}{2005}]%
        {bayati2005maximum}
{Mohsen Bayati}, {Devavrat Shah}, {and} {Mayank Sharma}. 2005.
\newblock \showarticletitle{Maximum weight matching via max-product belief
  propagation}. In {\em ISIT}. IEEE, 1763--1767.
\newblock


\bibitem[\protect\citeauthoryear{Bistarelli, Montanari, Rossi, Schiex,
  Verfaillie, and Fargier}{Bistarelli et~al\mbox{.}}{1999}]%
        {bistarelli1999semiring}
{Stefano Bistarelli}, {Ugo Montanari}, {Francesca Rossi}, {Thomas Schiex},
  {G{\'e}rard Verfaillie}, {and} {H{\'e}lene Fargier}. 1999.
\newblock \showarticletitle{Semiring-based CSPs and valued CSPs: Frameworks,
  properties, and comparison}.
\newblock {\em Constraints\/} {4}, 3 (1999), 199--240.
\newblock


\bibitem[\protect\citeauthoryear{Bordeaux and Monfroy}{Bordeaux and
  Monfroy}{2002}]%
        {bordeaux2002beyond}
{Lucas Bordeaux} {and} {Eric Monfroy}. 2002.
\newblock \showarticletitle{Beyond NP: Arc-consistency for quantified
  constraints}. In {\em Principles and Practice of Constraint Programming-CP
  2002}. Springer, 371--386.
\newblock


\bibitem[\protect\citeauthoryear{Braunstein, Mezard, Weigt, and
  Zecchina}{Braunstein et~al\mbox{.}}{2002b}]%
        {braunstein_constraint_2002}
{A Braunstein}, {M Mezard}, {M Weigt}, {and} {R Zecchina}. 2002b.
\newblock \showarticletitle{Constraint Satisfaction by Survey Propagation}.
\newblock {\em Physics\/} 2 (2002), 8.
\newblock


\bibitem[\protect\citeauthoryear{Braunstein, Mezard, and Zecchina}{Braunstein
  et~al\mbox{.}}{2002a}]%
        {braunstein_survey_2002}
{A Braunstein}, {M Mezard}, {and} {R Zecchina}. 2002a.
\newblock \showarticletitle{Survey propagation: an algorithm for
  satisfiability}.
\newblock {\em Random Structures and Algorithms\/} {27}, 2 (2002), 19.
\newblock
\showLCCN{0000}


\bibitem[\protect\citeauthoryear{Braunstein and Zecchina}{Braunstein and
  Zecchina}{2003}]%
        {braunstein_survey_2003}
{A. Braunstein} {and} {R. Zecchina}. 2003.
\newblock \showarticletitle{Survey Propagation as local equilibrium equations}.
\newblock {\em {arXiv:cond-mat/0312483}\/} (Dec. 2003).
\newblock
\showLCCN{0000}
\showDOI{%
\url{http://dx.doi.org/10.1088/1742-5468/2004/06/P06007}}
\newblock
\shownote{J. Stat. Mech., P06007 (2004).}


\bibitem[\protect\citeauthoryear{Clifford}{Clifford}{1990}]%
        {clifford1990markov}
{Peter Clifford}. 1990.
\newblock \showarticletitle{Markov random fields in statistics}.
\newblock {\em Disorder in physical systems\/} (1990), 19--32.
\newblock


\bibitem[\protect\citeauthoryear{Cooper}{Cooper}{1990}]%
        {Cooper90:Computational}
{G Cooper}. 1990.
\newblock \showarticletitle{The computational complexity of probabilistic
  inference using {Bayesian} belief networks}.
\newblock {\em Artificial Intelligence\/}  {42} (1990).
\newblock


\bibitem[\protect\citeauthoryear{Davey and Priestley}{Davey and
  Priestley}{2002}]%
        {davey2002introduction}
{Brian~A Davey} {and} {Hilary~A Priestley}. 2002.
\newblock {\em Introduction to lattices and order}.
\newblock Cambridge university press.
\newblock


\bibitem[\protect\citeauthoryear{Dechter and Larkin}{Dechter and
  Larkin}{2001}]%
        {dechter2001hybrid}
{Rina Dechter} {and} {David Larkin}. 2001.
\newblock \showarticletitle{Hybrid processing of beliefs and constraints}. In
  {\em Proceedings of the Seventeenth conference on Uncertainty in artificial
  intelligence}. Morgan Kaufmann Publishers Inc., 112--119.
\newblock


\bibitem[\protect\citeauthoryear{Eckmann and Hilton}{Eckmann and
  Hilton}{1962}]%
        {eckmann1962group}
{Beno Eckmann} {and} {Peter~J Hilton}. 1962.
\newblock \showarticletitle{Group-like structures in general categories I
  multiplications and comultiplications}.
\newblock {\it Math. Ann.} {145}, 3 (1962), 227--255.
\newblock


\bibitem[\protect\citeauthoryear{Forney~Jr}{Forney~Jr}{2001}]%
        {forney2001codes}
{G~David Forney~Jr}. 2001.
\newblock \showarticletitle{Codes on graphs: normal realizations}.
\newblock {\em Information Theory, IEEE Transactions on\/} {47}, 2 (2001),
  520--548.
\newblock


\bibitem[\protect\citeauthoryear{Fu and Anderson}{Fu and Anderson}{1986}]%
        {fu_application_1986}
{Y Fu} {and} {P~W Anderson}. 1986.
\newblock \showarticletitle{Application of statistical mechanics to
  {NP-complete} problems in combinatorial optimisation}.
\newblock {\em Journal of Physics A: Mathematical and General\/} {19}, 9 (June
  1986), 1605--1620.
\newblock
\showISSN{0305-4470, 1361-6447}
\showLCCN{0000}
\showDOI{%
\url{http://dx.doi.org/10.1088/0305-4470/19/9/033}}


\bibitem[\protect\citeauthoryear{Gallager}{Gallager}{1962}]%
        {gallager1962low}
{Robert~G Gallager}. 1962.
\newblock \showarticletitle{Low-density parity-check codes}.
\newblock {\em Information Theory, IRE Transactions on\/} {8}, 1 (1962),
  21--28.
\newblock


\bibitem[\protect\citeauthoryear{Heskes}{Heskes}{2003}]%
        {Heskes03}
{T Heskes}. 2003.
\newblock \showarticletitle{Stable Fixed Points of Loopy Belief Propagation Are
  Local Minima of the {Bethe} Free Energy}. In {\em NIPS}.
\newblock


\bibitem[\protect\citeauthoryear{Howard and Matheson}{Howard and
  Matheson}{2005}]%
        {howard2005influence}
{Ronald~A Howard} {and} {James~E Matheson}. 2005.
\newblock \showarticletitle{Influence diagrams}.
\newblock {\em Decision Analysis\/} {2}, 3 (2005), 127--143.
\newblock


\bibitem[\protect\citeauthoryear{Huang and Jebara}{Huang and Jebara}{2009}]%
        {huang2009approximating}
{Bert Huang} {and} {Tony Jebara}. 2009.
\newblock \showarticletitle{Approximating the permanent with belief
  propagation}.
\newblock {\em arXiv preprint arXiv:0908.1769\/} (2009).
\newblock


\bibitem[\protect\citeauthoryear{Ibrahimi, Javanmard, Kanoria, and
  Montanari}{Ibrahimi et~al\mbox{.}}{2011}]%
        {ibrahimi2011robust}
{Morteza Ibrahimi}, {Adel Javanmard}, {Yashodhan Kanoria}, {and} {Andrea
  Montanari}. 2011.
\newblock \showarticletitle{Robust max-product belief propagation}. In {\em
  Signals, Systems and Computers (ASILOMAR), 2011 Conference Record of the
  Forty Fifth Asilomar Conference on}. IEEE, 43--49.
\newblock


\bibitem[\protect\citeauthoryear{Jaynes}{Jaynes}{2003}]%
        {jaynes2003probability}
{Edwin~T Jaynes}. 2003.
\newblock {\em Probability theory: the logic of science}.
\newblock Cambridge university press.
\newblock


\bibitem[\protect\citeauthoryear{Kearns}{Kearns}{2007}]%
        {kearns2007graphical}
{Michael Kearns}. 2007.
\newblock \showarticletitle{Graphical games}.
\newblock {\em Algorithmic game theory\/}  {3} (2007), 159--180.
\newblock


\bibitem[\protect\citeauthoryear{Kroc, Sabharwal, and Selman}{Kroc
  et~al\mbox{.}}{2002}]%
        {Kroc2002}
{Lukas Kroc}, {A Sabharwal}, {and} {Bart Selman}. 2002.
\newblock \showarticletitle{{Survey Propagation Revisited}}.
\newblock {\em 23rd UAI\/} (2002), 217--226.
\newblock


\bibitem[\protect\citeauthoryear{Kschischang and Frey}{Kschischang and
  Frey}{2001}]%
        {kschischang_factor_2001}
{F~R Kschischang} {and} {B~J Frey}. 2001.
\newblock \showarticletitle{Factor graphs and the sum-product algorithm}.
\newblock {\em Information Theory, {IEEE}\/} (2001).
\newblock
\showLCCN{3306}


\bibitem[\protect\citeauthoryear{Lauritzen and Jensen}{Lauritzen and
  Jensen}{1997}]%
        {lauritzen1997local}
{Steffen~L Lauritzen} {and} {Finn~Verner Jensen}. 1997.
\newblock \showarticletitle{Local computation with valuations from a
  commutative semigroup}.
\newblock {\em Annals of Mathematics and Artificial Intelligence\/} {21}, 1
  (1997), 51--69.
\newblock


\bibitem[\protect\citeauthoryear{Littman, Majercik, and Pitassi}{Littman
  et~al\mbox{.}}{2001}]%
        {littman2001stochastic}
{Michael~L Littman}, {Stephen~M Majercik}, {and} {Toniann Pitassi}. 2001.
\newblock \showarticletitle{Stochastic boolean satisfiability}.
\newblock {\em Journal of Automated Reasoning\/} {27}, 3 (2001), 251--296.
\newblock


\bibitem[\protect\citeauthoryear{Maneva, Mossel, and Wainwright}{Maneva
  et~al\mbox{.}}{2004}]%
        {maneva_new_2004}
{E~N. Maneva}, {E Mossel}, {and} {M~J Wainwright}. 2004.
\newblock \showarticletitle{A New Look at Survey Propagation and its
  Generalizations}.
\newblock {\em {arXiv:cs/0409012}\/} (Sept. 2004).
\newblock
\showLCCN{0000}


\bibitem[\protect\citeauthoryear{M{\'e}zard and Montanari}{M{\'e}zard and
  Montanari}{2009}]%
        {Mezard09}
{M. M{\'e}zard} {and} {A. Montanari}. 2009.
\newblock {\em Information, physics, and computation}.
\newblock Oxford.
\newblock


\bibitem[\protect\citeauthoryear{M{\'e}zard, Parisi, and Virasoro}{M{\'e}zard
  et~al\mbox{.}}{1987}]%
        {Mezard1987}
{Marc M{\'e}zard}, {Georgio Parisi}, {and} {M.~A. Virasoro}. 1987.
\newblock {\em {Spin Glass Theory and Beyond}}.
\newblock Singapore: World Scientific.
\newblock


\bibitem[\protect\citeauthoryear{Mezard, Parisi, and Zecchina}{Mezard
  et~al\mbox{.}}{2002}]%
        {mezard_analytic_2002}
{M. Mezard}, {G. Parisi}, {and} {R. Zecchina}. 2002.
\newblock \showarticletitle{Analytic and Algorithmic Solution of Random
  Satisfiability Problems}.
\newblock {\em Science\/} {297}, 5582 (Aug. 2002), 812--815.
\newblock
\showISSN{0036-8075, 1095-9203}
\showLCCN{0633}
\showDOI{%
\url{http://dx.doi.org/10.1126/science.1073287}}


\bibitem[\protect\citeauthoryear{Mitchell, Selman, and Levesque}{Mitchell
  et~al\mbox{.}}{1992}]%
        {mitchell1992hard}
{D Mitchell}, {B Selman}, {and} {H Levesque}. 1992.
\newblock \showarticletitle{Hard and easy distributions of SAT problems}. In
  {\em AAAI}, Vol.~92. 459--465.
\newblock


\bibitem[\protect\citeauthoryear{Monasson, Zecchina, Kirkpatrick, Selman, and
  Troyansky}{Monasson et~al\mbox{.}}{1999}]%
        {monasson1999determining}
{R{\'e}mi Monasson}, {Riccardo Zecchina}, {Scott Kirkpatrick}, {Bart Selman},
  {and} {Lidror Troyansky}. 1999.
\newblock \showarticletitle{Determining computational complexity from
  characteristic ‘phase transitions’}.
\newblock {\em Nature\/} {400}, 6740 (1999), 133--137.
\newblock


\bibitem[\protect\citeauthoryear{Murphy, Weiss, and Jordan}{Murphy
  et~al\mbox{.}}{1999}]%
        {Murphy1999}
{Kevin Murphy}, {Yair Weiss}, {and} {Michael Jordan}. 1999.
\newblock \showarticletitle{{Loopy-belief Propagation for Approximate
  Inference: An Empirical Study}}. In {\em 15}. 467--475.
\newblock


\bibitem[\protect\citeauthoryear{Ortiz and Kearns}{Ortiz and Kearns}{2002}]%
        {ortiz2002nash}
{Luis~E Ortiz} {and} {Michael Kearns}. 2002.
\newblock \showarticletitle{Nash propagation for loopy graphical games}. In
  {\em Advances in Neural Information Processing Systems}. 793--800.
\newblock


\bibitem[\protect\citeauthoryear{Park and Darwiche}{Park and Darwiche}{2004}]%
        {park2004complexity}
{James~D Park} {and} {Adnan Darwiche}. 2004.
\newblock \showarticletitle{Complexity Results and Approximation Strategies for
  MAP Explanations.}
\newblock {\em J. Artif. Intell. Res.(JAIR)\/}  {21} (2004), 101--133.
\newblock


\bibitem[\protect\citeauthoryear{Pearl}{Pearl}{1985}]%
        {pearl1985bayesian}
{Judea Pearl}. 1985.
\newblock \showarticletitle{Bayesian networks: a model of self-activated memory
  for evidential reasoning}.
\newblock  (1985).
\newblock


\bibitem[\protect\citeauthoryear{Pearl}{Pearl}{1988}]%
        {pearl_probabilistic_1988}
{J Pearl}. 1988.
\newblock {\em Probabilistic Reasoning in Intelligent Systems: Networks of
  Plausible Inference}. Representation and Reasoning, Vol.~88.
\newblock Morgan Kaufmann.
\newblock
\showISBNx{1558604790}
\showLCCN{17013}


\bibitem[\protect\citeauthoryear{Pinter}{Pinter}{2012}]%
        {pinter2012book}
{Charles~C Pinter}. 2012.
\newblock {\em A book of abstract algebra}.
\newblock Courier Dover Publications.
\newblock


\bibitem[\protect\citeauthoryear{Potetz and Lee}{Potetz and Lee}{2008}]%
        {Potetz2008}
{Brian Potetz} {and} {Tai~Sing Lee}. 2008.
\newblock \showarticletitle{{Efficient Belief Propagation for Higher Order
  Cliques Using Linear Constraint Nodes Cliques Using Linear Constraint
  Nodes}}.
\newblock {\em Computer Vision and Image Understanding\/} {112}, 1 (2008),
  39--54.
\newblock
\showDOI{%
\url{http://dx.doi.org/10.1016/j.cviu.2008.05.007}}


\bibitem[\protect\citeauthoryear{Pralet, Verfaillie, and Schiex}{Pralet
  et~al\mbox{.}}{2007}]%
        {pralet2007algebraic}
{C{\'e}dric Pralet}, {G{\'e}rard Verfaillie}, {and} {Thomas Schiex}. 2007.
\newblock \showarticletitle{An Algebraic Graphical Model for Decision with
  Uncertainties, Feasibilities, and Utilities.}
\newblock {\em J. Artif. Intell. Res.(JAIR)\/}  {29} (2007), 421--489.
\newblock


\bibitem[\protect\citeauthoryear{Ravanbakhsh, Srinivasa, Frey, and
  Greiner}{Ravanbakhsh et~al\mbox{.}}{2014}]%
        {ravanbakhsh_minmax}
{S Ravanbakhsh}, {C Srinivasa}, {B Frey}, {and} {R Greiner}. 2014.
\newblock \showarticletitle{Min-Max Problems on Factor-Graphs}.
\newblock {\em ICML\/} (2014).
\newblock


\bibitem[\protect\citeauthoryear{Rogers}{Rogers}{1987}]%
        {rogers1987theory}
{Hartley Rogers}. 1987.
\newblock \showarticletitle{Theory of recursive functions and effective
  computability}.
\newblock  (1987).
\newblock


\bibitem[\protect\citeauthoryear{Roth}{Roth}{1993}]%
        {roth1993hardness}
{Dan Roth}. 1993.
\newblock \showarticletitle{On the hardness of approximate reasoning}. In {\em
  Proceedings of the 13th international joint conference on Artifical
  intelligence-Volume 1}. Morgan Kaufmann Publishers Inc., 613--618.
\newblock


\bibitem[\protect\citeauthoryear{Schiex, Fargier, and Verfaillie}{Schiex
  et~al\mbox{.}}{1995}]%
        {schiex1995valued}
{Thomas Schiex}, {Helene Fargier}, {and} {Gerard Verfaillie}. 1995.
\newblock \showarticletitle{Valued constraint satisfaction problems: hard and
  easy problems}. In {\em Proceedings of the 14th international joint
  conference on Artificial intelligence-Volume 1}. Morgan Kaufmann Publishers
  Inc., 631--637.
\newblock


\bibitem[\protect\citeauthoryear{Shenoy}{Shenoy}{1992}]%
        {shenoy1992valuation}
{Prakash~P Shenoy}. 1992.
\newblock \showarticletitle{Valuation-based systems: A framework for managing
  uncertainty in expert systems}. In {\em Fuzzy logic for the management of
  uncertainty}. John Wiley \& Sons, Inc., 83--104.
\newblock


\bibitem[\protect\citeauthoryear{Shenoy and Shafer}{Shenoy and Shafer}{1990}]%
        {shenoy1990axioms}
{Prakash~P Shenoy} {and} {Glenn Shafer}. 1990.
\newblock \showarticletitle{Axioms for probability and belief-function
  propagation}. In {\em Uncertainty in Artificial Intelligence}.
\newblock


\bibitem[\protect\citeauthoryear{Shimony}{Shimony}{1994}]%
        {shimony1994finding}
{Solomon~Eyal Shimony}. 1994.
\newblock \showarticletitle{Finding MAPs for belief networks is NP-hard}.
\newblock {\em Artificial Intelligence\/} {68}, 2 (1994), 399--410.
\newblock


\bibitem[\protect\citeauthoryear{Stockmeyer}{Stockmeyer}{1976}]%
        {stockmeyer1976polynomial}
{Larry~J Stockmeyer}. 1976.
\newblock \showarticletitle{The polynomial-time hierarchy}.
\newblock {\em Theoretical Computer Science\/} {3}, 1 (1976), 1--22.
\newblock


\bibitem[\protect\citeauthoryear{Tarlow and Zemel}{Tarlow and Zemel}{2010}]%
        {Tarlow2010}
{Daniel Tarlow} {and} {Richard~S Zemel}. 2010.
\newblock \showarticletitle{{HOP-MAP : Efficient Message Passing with High
  Order Potentials}}.
\newblock {\em Journal of Machine Learning Research Proceedings Track\/}  {9}
  (2010), 812--819.
\newblock
\showURL{%
\url{http://www.cs.toronto.edu/~dtarlow/TarlowGivoniZemel\_AISTATS2010.pdf}}


\bibitem[\protect\citeauthoryear{Toda}{Toda}{1991}]%
        {toda1991pp}
{Seinosuke Toda}. 1991.
\newblock \showarticletitle{PP is as hard as the polynomial-time hierarchy}.
\newblock {\it SIAM J. Comput.} {20}, 5 (1991), 865--877.
\newblock


\bibitem[\protect\citeauthoryear{Valiant}{Valiant}{1979}]%
        {valiant1979complexity}
{L~G. Valiant}. 1979.
\newblock \showarticletitle{The complexity of computing the permanent}.
\newblock {\em Theoretical computer science\/} {8}, 2 (1979), 189--201.
\newblock


\bibitem[\protect\citeauthoryear{Valiant and Vazirani}{Valiant and
  Vazirani}{1986}]%
        {valiant1986np}
{Leslie~G Valiant} {and} {Vijay~V Vazirani}. 1986.
\newblock \showarticletitle{NP is as easy as detecting unique solutions}.
\newblock {\em Theoretical Computer Science\/}  {47} (1986), 85--93.
\newblock


\bibitem[\protect\citeauthoryear{Von~Neumann and Morgenstern}{Von~Neumann and
  Morgenstern}{2007}]%
        {von2007theory}
{John Von~Neumann} {and} {Oskar Morgenstern}. 2007.
\newblock {\em Theory of Games and Economic Behavior (60th Anniversary
  Commemorative Edition)}.
\newblock Princeton university press.
\newblock


\bibitem[\protect\citeauthoryear{Wagner}{Wagner}{1986}]%
        {wagner1986complexity}
{Klaus~W Wagner}. 1986.
\newblock \showarticletitle{The complexity of combinatorial problems with
  succinct input representation}.
\newblock {\em Acta Informatica\/} {23}, 3 (1986), 325--356.
\newblock


\bibitem[\protect\citeauthoryear{Wainwright and Jordan}{Wainwright and
  Jordan}{2007}]%
        {Wainwright2007}
{Martin~J Wainwright} {and} {Michael~I Jordan}. 2007.
\newblock \showarticletitle{{Graphical Models, Exponential Families, and
  Variational Inference}}.
\newblock {\em Foundations and Trends® in Machine Learning\/} {1}, 1–2
  (2007), 1--305.
\newblock
\showISBNx{1601981848}
\showISSN{19358237}
\showDOI{%
\url{http://dx.doi.org/10.1561/2200000001}}


\bibitem[\protect\citeauthoryear{Weiss}{Weiss}{2001}]%
        {Weiss2001a}
{Yair Weiss}. 2001.
\newblock \showarticletitle{{Correctness of belief propagation in Gaussian
  graphical models of arbitrary topology}}.
\newblock {\em Neural computation\/} June (2001).
\newblock


\bibitem[\protect\citeauthoryear{Weller and Jebara}{Weller and Jebara}{2013}]%
        {weller2013map}
{Adrian Weller} {and} {Tony~S Jebara}. 2013.
\newblock \showarticletitle{On MAP inference by MWSS on Perfect Graphs}.
\newblock {\em arXiv preprint arXiv:1309.6872\/} (2013).
\newblock


\bibitem[\protect\citeauthoryear{Yedidia and Freeman}{Yedidia and
  Freeman}{2001}]%
        {Yedidia2001a}
{JS Yedidia} {and} {WT Freeman}. 2001.
\newblock \showarticletitle{{Generalized belief propagation}}.
\newblock {\em Advances in neural information\/} (2001).
\newblock


\end{thebibliography}
