text:
\section{Introduction}

Inference problems are common to almost any scientific discipline.
Often an inference problem can be recast in that of computing some
marginal probability on a small subset of variables, given a joint
probability distribution over a large number $N$ of variables,
$\{s_1,\ldots,s_N\} \equiv \sigma$. A typical example is the
computation of the expectation value of a variable $\langle s_i
\rangle \equiv \sum_{s_i} s_i\, p_i(s_i)$ where $p_i(s_i)$ is the
single-variable marginal probability defined as
\[
p_i(s_i) \equiv \sum_{\sigma \setminus s_i} P(\sigma)\;.
\]
Clearly the computation of the sum in the r.h.s.\ is as difficult as
the computation of the partition function $Z \equiv \sum_\sigma
P(\sigma)$, which is the main subject of statistical mechanics.  In
the general (and the most interesting) case, this problem can not be
solved exactly in a time growing sub-exponentially with the size $N$.
We are deemed to use some kind of approximation in order to compute
marginals in a time growing linearly in $N$.  The approximation
schemes used so far are mainly adopted from the field of statistical
mechanics \cite{libroMarcAndrea}, where mean-field-like approximations
are standard and well controlled tools for approximating the
free-energy, $-\beta f = \ln Z$.

For non-disordered models, like the Ising ferromagnetic model, these
approximations work quite well and provide good results
\cite{pelizzola}.  However, much less is known for models with
disorder, and for this reason we will focus on spin glasses in the
present paper.  In disordered models one usually deals with an
ensemble of problems (e.g.\ in spin glasses each sample has its own
couplings, randomly chosen from a given distribution), and the results
obtained by the statistical mechanics tools refer to average
quantities, i.e. those of the typical samples.  In other words one is
not concerned with the behavior of a specific sample, but rather one
looks at the whole ensemble.  On the contrary when doing inference one
is interested on the properties of a single specific problem and thus
the above approximation schemes (based on statistical mechanics
mean-field approaches) need to be converted into an algorithm that can
be run on such a specific sample.  Computing marginals on a given
sample clearly gives more information than computing averages over the
ensemble.

To our knowledge, effective (i.e. linear time in $N$) algorithms for
computing marginals can be essentially divided in two broad classes:
stochastic local search algorithms, that roughly sample the
configurational space according to $P(\sigma)$, and algorithms based
on some kind of mean-field approximation.  The former are exact on the
long run, but the latter can be much more useful if an approximated
answer is required in a short time.  Unfortunately the latter also
have some additional drawback due to the mean-field nature of the
underlying approximation, e.g. the appearance of spurious phase
transitions, that may prevent the proper convergence of the algorithm.

One more reason why this latter class of algorithms has a limited
scope of application is that the convergence of the algorithm may
strongly depend on the presence of short loops in the network of
variables interactions.  In this sense the successful application of
one of these algorithms to models defined on regular lattices (which
have many short loops) would be a major achievement.

In this paper we introduce a fast algorithm for computing marginals in
2D and 3D spin glass models \cite{libroYoung} defined by the
Hamiltonian (further details are given below)
\begin{equation}
\mathcal{H} (\sigma) = - \sum_{(i,j)} J_{ij} s_i s_j\;.
\label{Ham}
\end{equation}

The first non trivial mean-field approximation for the above model
corresponds to the Bethe-Peierls approximation scheme and the Belief
Propagation (BP) algorithm \cite{kabaSaad}. Unfortunately when BP is
run on a given spin glass sample defined on a $D$ dimensional lattice,
it seems to provide exactly the same output as if it were run on a
random regular graph with fixed degree $2D$: that is, for $T \gtrsim
T_\text{Bethe}$ it converges to a solution with all null local
marginals ($\langle s_i \rangle = 0$), while for $T \lesssim
T_\text{Bethe}$ it does not converge to a fixed point.

The next step in the series of mean-field approximations (also known
as Kikuchi approximations or `cluster variation method') is to
consider joint probability distributions of the four spins belonging
to the same plaquette \cite{kikuchi,pelizzola}. Under this
approximation an algorithm has been derived which is called
Generalized Belief Propagation (GBP) \cite{yedidia}.  To our
knowledge, this algorithm has been applied to 2D spin glasses, but
only in presence of an external magnetic field, which is known to
improve the convergence properties of GBP.  Our experience says that,
running plain GBP on a generic sample of a 2D spin glass without
external field, a fixed point is reached only for high enough
temperatures, well above the interesting region.  The lack of
convergence of GBP (and other similar message-passing algorithms, MPA)
is a well known problem, whose solution is in general far from being
understood.  For this reason, a new class of algorithms has been
recently introduced \cite{HAK03}, which provably converge to a fixed
point: these algorithms use a double loop iterative procedure (to be
compared to the single loop in GBP) and for this reason they are
usually quite slow.

The algorithm we are going to introduce is as fast as BP (which is the
fastest algorithm presenty available), and converges in a wider range
of temperatures than BP. Moreover the marginal probabilities provided
by our algorithm are as accurate as those which can be obtained by
Double Loop algorithms in a much larger running time.

Our algorithm works in the absence of external field, that is in the
situation where MPA have more problems in converging to a fixed point.
In this sense it is a very important extension to presently available
inference algorithms.

The rest of the work is organized as follows.  First, in section
\ref{GBP2D} we derive the GBP equations for the 2D Edward Anderson
model. Then, in section \ref{sec:multfields} we rewrite these
equations in terms of fields, a notation that has a nicer physical
interpretation and that we are going to use in the rest of the
work. Section \ref{Dual} presents the novel algorithm, inspired by the
paramagnetic Ansatz to the GBP equations.  In section \ref{Results2D}
we show the results of running this algorithm on the 2D
Edward-Anderson model. There we compare its performance with Monte
Carlo simulations, with the Double Loop algorithm and with exact
calculation of the ground state of systems with bimodal and Gaussian
interactions. Then, in section \ref{Results3D} we generalized our
message passing equation to general dimensions and present some
results for the 3D Edward-Anderson model. Finally, some conclusions
are drawn in section \ref{Conclusions}.

\section{Generalized Belief Propagation on the 2D EA model}
\label{GBP2D}

Here we present the GBP equations for
the Edwards-Anderson (EA) model on a 2D square lattice, and we refer
the reader to \cite{yedidia,pelizzola} for a more general
introduction.  In our case (as well as in many other cases) GBP is
equivalent to Kikuchi's approximation, known as the Cluster
Variational Method (CVM) \cite{kikuchi}. We will try a presentation as
physical as possible.

Consider the 2D EA model consisting of a set $\sigma=\{s_1, \ldots,
s_N\}$ of $N$ Ising spins $s_i=\pm 1$ located at the nodes of a 2D
square lattice, interacting with a Hamiltonian
\begin{equation}
\mathcal{H} (\sigma) = - \sum_{\langle i,j \rangle} J_{ij} s_i s_j\;,
\label{eq:Ham}
\end{equation}
where the sum runs over all couples of neighboring spins (first
neighbors on the lattice). The $J_{ij}$ are the coupling constants
between spins and are supposed to be fixed for any given instance of
the model. If the interactions are not random variables, \textit{i.e.\ } $J_{ij}=J$,
then the 2D ferromagnet is recovered.  We will focus on the two most
common disorder distributions: bimodal interactions, $P(J) =
\frac{1}{2} \delta(J-1)+\frac{1}{2} \delta(J+1)$, and Gaussian
interactions $P(J) = \exp(-J^2/2)/\sqrt{2 \pi}$.

The statistical mechanics of the EA model, at a given temperature
$T=1/\beta $, is given by the Gibbs-Boltzmann distribution
\[
P(\sigma) = \frac{e^{-\beta\mathcal{H}(\sigma)}}{Z}\;.
\]
The direct computation of the partition function
\[
Z=\sum_{\sigma} e^{-\beta \mathcal{H}(\sigma)}
\]
or any marginal distribution $p(s_i,s_j)=\sum_{\sigma \setminus
  s_i,s_j}P(\sigma)$ is a time consuming task, unattainable in
practice, since it involves the addition of $2^N$ terms, and therefore
an approximation is required\footnote{The 2D case is special: indeed,
  thanks to the small genus topology, the partition function $Z$ can
  be computed efficiently. However we are interested in developing an
  algorithm for the general case, and we will not make use of this
  peculiarity.}.

The idea of the Region Graph Approximation to Free Energy
\cite{yedidia} is to replace the real distribution $P(\sigma)$ by a
reduced set of its marginals. The hierarchy of approximations is given
by the size of such marginals, starting with the set of all single
spins marginals $p_i(s_i)$ [mean-field], then following to all
neighboring sites marginals $p_{ij}(s_i,s_j)$ [Bethe], then to all
square plaquettes marginals $p_{ijkl}(s_i,s_j,s_k,s_l)$, and so
on. Since the only way of knowing such marginals exactly is the
unattainable computation of $Z$, the method pretends to approximate
them by a set of beliefs $b_i(s_i)$, $b_{ij}(s_i,s_j)$, etc.\ obtained
from the minimization of a region based free energy. In the Region
Graph Approximation to Free Energy, a set of regions, \textit{i.e.\ } sets of
variables and their interactions, is defined, and a free energy is
written in terms of the beliefs at each region. The Cluster
Variational Method does a similar job, but instead of starting from an
arbitrary choice of regions, it starts by defining the set of largest
regions, and smaller regions are defined recursively by the
intersections of bigger regions. In this sense, CVM is a specific
choice of region graph approximation to the free energy.

For the 2D EA model, we will consider the expansion of the free energy
in terms of the marginals at three levels of regions: single sites (or
spins), links, and plaquettes. By plaquettes we mean the square basic
cell of the 2D lattice. This choice of regions corresponds to the CVM
having the square plaquettes as biggest regions. The free energy of
the system is therefore written as
\[
F=\sum_{R}c_R  F_R\;,
\]
where $R$ runs over all regions considered, and the free energy in a
particular region depends on the marginals at that level
$b_R(\sigma_R)$:
\[
\beta F_R = \sum_{\sigma_R} b_R(\sigma_R) \beta E_R(\sigma_R) +
b_R(\sigma_R) \log b_R(\sigma_R)\;.
\]
The symbol $\sigma_R$ refers to the set of spins in region $R$, while
$E_R$ is the energy contribution in that region. The counting numbers
$c_R$ (also Moebius coefficients) are needed to ensure that bigger
regions do not over count the contribution in free energy of smaller
regions, and follow the prescription
\begin{equation}
c_R = 1- \sum_{R'\supset R} c_{R'}\;,
\label{eq:countingnumbers}
\end{equation}
where $R'$ is any region containing completely region $R$, as e.g.\ a
plaquette containing a link or a link containing a site.  In the case
of the 2D lattice, the biggest regions are the square plaquettes, and
therefore $c_\text{plaq} = 1$, while the links regions have
$c_\text{link} = 1 - 2 c_\text{plaq} = -1$ (as each of them is
contained in 2 plaquettes regions), and finally the spins regions have
$c_\text{site} = 1 - 4 c_\text{plaq} - 4 c_\text{link} = 1$ (as each
spin belongs to 4 links and 4 plaquettes). So the actual approximation
for the EA model on a 2D square lattice is
\begin{eqnarray}
\beta F &=& \sum_{\mathcal{P}} \sum_{\sigma_\mathcal{P}} b_\mathcal{P}(\sigma_\mathcal{P})
  \log \frac{b_\mathcal{P}(\sigma_\mathcal{P})}{\exp[-\beta E_\mathcal{P}(\sigma_\mathcal{P})]}
  \qquad \text{Plaquettes} \nonumber\\
& & -\sum_{L} \sum_{\sigma_L} b_L(\sigma_L)
  \log \frac{b_L(\sigma_L)}{\exp[-\beta E_L(\sigma_L)]}
  \qquad \text{Links} \label{eq:freeen} \\
& & +\sum_{i} \sum_{s_i} b_i(s_i)
  \log \frac{b_i(s_i)}{\exp[-\beta E_i(s_i)]}
  \qquad\text{Sites} \nonumber
\end{eqnarray}
where the sums run over all plaquettes, links and sites respectively.
Please note that we are using the following notation for region
indices: lower-case for sites, upper-case for links and upper-case
calligraphic for plaquettes.  The energy term $E_i(s_i)$ in the sites
contribution is only relevant when an external field acts over spins,
and can be taken as zero in our case, since no external field is
considered. Notice that whenever the interactions are included in more
than one region (in our case are included in Link and Plaquette
regions), the counting numbers guarantee that the exact
thermodynamical energy $U=\sum_\sigma P(\sigma) \mathcal{H}(\sigma)$ is
obtained when the beliefs are the exact marginals of the Boltzmann
distribution. On the other hand, the entropy contribution is
intrinsically approximated, since the cutoff in the regions sizes
imposes a certain kind of factorization of $P(\sigma)$ in terms of its
marginals (see \cite{pelizzola} for an explanation of the region graph
approximation in terms of cumulants expansions of the entropy).

The next step in the method, is to compute the beliefs from the
minimization condition of the free energy. However, an unrestricted
minimization will generally produce inconsistent solutions, since the
beliefs (marginals) are not independent, as they are related by the
marginalization conditions
\begin{equation}
\begin{array}{l}
b_i(s_i) = \sum_{\sigma_{L \setminus i}} b_L(\sigma_L) = \sum_{s_j}
b_L(s_i,s_j)\;,\\
b_L(\sigma_L) = b_L(s_i,s_j) = \sum_{\sigma_{\mathcal{P} \setminus L}}
b_\mathcal{P}(\sigma_\mathcal{P}) = \sum_{s_k,s_l} b_\mathcal{P}(s_i,s_j,s_k,s_l)\;,
\end{array}
\label{eq:marginalization}
\end{equation}
where $\sigma_L=\{s_i,s_j\}$ and $\sigma_\mathcal{P}=\{s_i,s_j,s_k,s_l\}$.  In
order to minimize under the constraints in \rref{eq:marginalization}
and under the normalization condition for each belief, a set of
Lagrange multipliers should be added to the free energy in
\rref{eq:freeen}. There are different ways of choosing the Lagrange
multipliers \cite{yedidia}, and each of them will produce a different
set of self consistency equations. We choose the so called Parent to
Child scheme (see section XX in \cite{yedidia}), in which constraints
in \rref{eq:marginalization} are imposed by two sets of Lagrange
multipliers: $\mu_{L\to i}(s_i)$ relating the belief at link $L$ to
that at site $i$, and $\nu_{\mathcal{P}\to L}(\sigma_L)$ relating the one at
plaquette $\mathcal{P}$ to the one at link $L$.

With constraints (\ref{eq:marginalization}) enforced by Lagrange
multipliers, the free energy stationary conditions for the beliefs are
the following:
\begin{eqnarray}
b_i(s_i) &=& \frac{1}{Z_i} \exp\left(-\beta E_i(s_i) - \sum_{L\supset
  i}^4 \mu_{L\to i}(s_i)\right)\;, \nonumber\\
b_L(\sigma_L) &=& \frac{1}{Z_L} \exp\left(-\beta E_L(\sigma_L) -
\sum_{\mathcal{P} \supset L}^2 \nu_{\mathcal{P}\to L}(\sigma_L) - \sum_{i\subset L}^2
\mathop{\sum_{L'\supset i}^3}_{L' \neq L} \mu_{L'\to i}(s_i)
\right)\;, \label{eq:beliefs}\\
b_\mathcal{P}(\sigma_\mathcal{P}) &=& \frac{1}{Z_\mathcal{P}} \exp\left(-\beta E_\mathcal{P}(\sigma_\mathcal{P})
- \sum_{L\subset\mathcal{P}}^4 \mathop{\sum_{\mathcal{P}'\supset L}^1}_{\mathcal{P}' \neq \mathcal{P}}
\nu_{\mathcal{P}'\to L}(\sigma_L) - \sum_{i\subset \mathcal{P}}^4 \mathop{\sum_{L \supset
    i}^2}_{L \not\subset \mathcal{P}} \mu_{L\to i}(s_i) \right)\;, \nonumber
\end{eqnarray}
where the notation $L\supset i$ refers to all links containing site
$i$ and $\mathcal{P}\supset L$ to all plaquettes containing link $L$.  The
upper indices in the sums are written just to help understanding how
many terms are in each sum for the 2D case.  The precise meaning of
the indices in each summation can be understood from the graphical
representation in Figure \ref{fig:beliefs2D}.  Lagrange multipliers
are shown as arrows going from parent regions to children regions:
simple arrows correspond to $\mu_{L\to i}$ and triple arrows to
$\nu_{\mathcal{P}\to L}$. Let us consider, for instance, the belief in a link
region $b_L(\sigma_L)$, depicted in the central picture of
Fig.~\ref{fig:beliefs2D}: the sum of the two Lagrange multipliers
$\nu_{\mathcal{P}\to L} (\sigma_L)$ corresponds to the triple arrows from
plaquettes on the left and right of the link $L$, while the double sum
over the three $\mu_{L\to i}(s_i)$ and the three $\mu_{L\to j}(s_j)$
correspond to the three arrows acting over the two spins.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.9\textwidth]{resources/beliefs.eps}
\caption{Schematic representation of belief equations
  (\ref{eq:beliefs}).  Lagrange multipliers are depicted as arrows,
  going from parent regions to children regions.}
\label{fig:beliefs2D}
\end{center}
\end{figure}

In Eq.(\ref{eq:beliefs}), the $Z_R$ are normalization constants, and
the terms $E_\mathcal{P}(\sigma_\mathcal{P})=E_\mathcal{P}(s_i,s_j,s_k,s_l)=-(J_{ij} s_i s_j +
J_{jk} s_j s_k + J_{kl} s_k s_k + J_{li} s_l s_i)$ and $E_L(\sigma_L)
= E_L(s_i,s_j)=- J_{ij} s_i s_j$ are the corresponding energies in
plaquettes and links, and are represented in Fig.~\ref{fig:beliefs2D}
by bold lines (interactions) between circles (spins). In our case
$E_i(s_i)$ is zero since no external field is acting on the spins.

The Lagrange multipliers are fixed by the constraints they were
supposed to enforce, \rref{eq:marginalization}, and they must satisfy
the following set of self-consistency equations:
\begin{eqnarray}
& \exp\!\! & \Big[-\mu_{L\to i}(s_i)\Big] = \sum_{s_j} \exp\Bigg[-\beta
    E_{L\setminus i}(s_i,s_j) - \sum_{\mathcal{P} \supset L}^2 \nu_{\mathcal{P}\to
      L}(s_i,s_j) - \mathop{\sum_{L'\supset j}^3}_{L' \neq L}
    \mu_{L'\to j}(s_j) \Bigg] \nonumber \\
& \exp\!\! & \Big[ -\nu_{\mathcal{P}\to L}(s_i,s_j) - \mu_{D\to i}(s_i) -
    \mu_{U\to j}(s_j)\Big] = \label{eq:message2D} \\
&& \sum_{s_k,s_l} \exp \Bigg[-\beta E_{\mathcal{P}\setminus L}(s_i,s_j,s_k,s_l) -
    \mathop{\sum_{L' \in \mathcal{P}}^3}_{L' \neq L} \mathop{\sum_{\mathcal{P}'
        \supset L'}^1}_{\mathcal{P}' \neq \mathcal{P}} \nu_{P'\to L'}(\sigma_{L'}) -
    \mathop{\sum_{L' \supset k}^2}_{L'\not\subset\mathcal{P}} \mu_{L'\to
      k}(s_k) - \mathop{\sum_{L' \supset l}^2}_{L'\not\subset\mathcal{P}}
    \mu_{L'\to l}(s_l) \Bigg]\nonumber
\end{eqnarray}
Again, to help understanding these equations, we provide in
Fig.~\ref{fig:message2D} their graphical representation. Note that
there is one of these equations for every pair of Link-Site and every
pair of Plaquette-Link in the graph. With $E_{P\setminus L}$ we refer
to interactions in plaquette $P$ that are not in link $L$.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.9\textwidth]{resources/messages.eps}
\caption{Message passing equations (\ref{eq:message2D}), shown
  schematically.  Messages are depicted as arrows, going from parent
  regions to children regions. On any link $J_{ij}$, represented as bold
  lines between spins (circles), a Boltzmann factor $e^{\beta J_{ij} s_i
    s_j}$ exists. Dark circles represent spins to be traced
  over. Messages from plaquettes to links $\nu_{P\to L}(s_i,s_j)$ are
  represented by a triple arrow, because they can be written in terms
  of three parameters $U$, $u_i$ and $u_j$, defining the correlation
  $\< s_i s_j \>$ and magnetizations $\< s_i \>$ and $\< s_j \>$,
  respectively.}
\label{fig:message2D}
\end{center}
\end{figure}

For each link $L$ in the 2D lattice, there are two link-to-site
multipliers, $\mu_{L\to i} (s_i)$ and $\mu_{L\to j} (s_j)$. For each
plaquette there are four plaquette-to-link multipliers $\nu_{P\to
  L}(s_i,s_j)$, corresponding to the four links contained inside the
plaquette. Let $N$ be the number of spins in the lattice, there are $2
N$ links and $N$ plaquettes. So the originally intractable problem of
computing marginals, has been replaced by the problem of solving a set
of $4 N + 4 N$ coupled equations for the Lagrange multipliers as those
in \rref{eq:message2D}.  Once these equations are solved, the
approximation for the marginals is obtained from \rref{eq:beliefs} for
the beliefs, and all thermodynamic quantities are derived from them as
in \rref{eq:freeen}.

Minimizing a region graph approximation to free energy, as that in
\rref{eq:freeen} with constraints \rref{eq:marginalization}, or
equivalently solving the set of self-consistent equations in
\rref{eq:message2D}, is still a non trivial task. Let us consider two
ways of doing it. The first method is the ``direct'' minimization of
the constrained free energy, using a Double Loop algorithm
\cite{HAK03}. This method is quite solid, since it guarantees
convergence to an extremal point of the constrained free energy, but
it may be very slow to converge. The second method, which is generally
faster but is not guaranteed to converge, is the family of the so
called Message-Passing algorithm (MPA), in which the Lagrange
multipliers are interpreted as \textit{messages} $\nu_{\mathcal{P}\to
  L}(\sigma_L)$ going from plaquettes to links, and messages
$\mu_{L\to i}(s_i)$ from links to sites. Self consistency equations
(\ref{eq:message2D}) can be viewed as the update rules for the
messages in the left hand side, in terms of those in the right hand
side. A random order updating of the messages in the graph by
\rref{eq:message2D} (message passing) can reach a fixed point
solution, and therefore, to an extremal point of the constrained free
energy \cite{yedidia}. Next, we show explicitly how the
message-passing equations looks like in terms of fields.

\subsection{From multipliers to fields}
\label{sec:multfields}

A particularly useful way of representing the multipliers (messages),
with a nice physical interpretation, is the one used in
\cite{kabashima}, which we adopt here. In full generality
\cite{kabashima, TLMF10}, these multipliers can be written in terms of
effective fields
\begin{eqnarray}
\mu_{L\to i}(s_i) &=& \beta\, u_{L\to i}\,s_i \\
\nu_{\mathcal{P}\to L}(s_i,s_j) &=& \beta\,(U_{\mathcal{P}\to L}\,s_i\,s_j + u_{\mathcal{P}\to
  i}\,s_i + u_{\mathcal{P}\to j}\,s_j)
\end{eqnarray}
In particular, the field $u$ corresponds to the cavity field in the
Bethe approximation \cite{yedidia}. Using Lagrange multipliers,
messages or fields, is essentially equivalent. We will often refer to
fields as $u$-messages to emphasize their role in a message-passing
algorithm, and we will refer to self-consistency equations
(\ref{eq:message2D}) as the message-passing equations.

This parametrization of the multipliers has proved useful to other
endeavors, like the extension of the replica theory to general region
graph approximations \cite{TLMF10}. Here, all the relevant information
in the Lagrange multipliers is translated to ``effective fields'' $u$
and $(U,u_a, u_b)$. Notice that in this representation every single
field $u$ corresponds to an arrow in the schematic messages-passing
equations in Figure \ref{fig:message2D}. In particular, the messages
going from plaquettes to links are characterized by three fields
$(U,u_a,u_b)$, and the field $U$ acts as an effective interaction
term, that adds directly to the energy terms in the Boltzmann
factor. For instance, the first message-passing \rref{eq:message2D} is
\begin{align}
\exp \Big[ \beta u_{L\to i} s_i \Big] = \sum_{s_j} \exp \bigg[ \beta \Big(
(u_{\mathcal{P}\to i} + u_{\mathcal{L}\to i})\, s_i +
(U_{\mathcal{P}\to L} + U_{\mathcal{L} \to L} + J_{ij})\, s_i s_j + \nonumber\\
(u_{\mathcal{P}\to j} + u_{\mathcal{L}\to j} + u_{A\to j} + u_{B\to j} + u_{U\to j})\, s_j
\Big) \bigg]
\end{align}
where the indices refer to the notation used in
Fig. \ref{fig:message2D} and $J_{ij}$ is the interaction coupling
constant between spins $s_i$ and $s_j$.  This equation naturally
defines the updating rule for the message $u_{L\to i}$:
\begin{equation}
u_{L\to i} = \hat{u}(u_{\mathcal{P}\to i} + u_{\mathcal{L} \to i},\;
U_{\mathcal{P}\to L} + U_{\mathcal{L}\to L} + J_{ij},\;
u_{\mathcal{P}\to j} + u_{\mathcal{L}\to j} + u_{A\to j} + u_{B\to j} + u_{U\to j})\;,
\label{eq:message-u}
\end{equation}
where
\[
\hat{u}(u,U,h) \equiv u + \frac{1}{2\beta} \log\frac{\cosh\beta(U+h)}{\cosh\beta(U-h)}
\]
Note that the usual cavity equation for fields in the Bethe
approximation \cite{basicBethe} is recovered if all contributions
from plaquettes $\mathcal{P}$ and $\mathcal{L}$ are set to zero.

Working in a similar way for the second equation in
(\ref{eq:message2D}) we end up with the updating rule for the message
$(U_{\mathcal{P}\to L},u_{\mathcal{P}\to i},u_{\mathcal{P}\to j})$ sent from any given
plaquette region $\mathcal{P}$ to one of its children links $L$ (see right
picture in Fig.~\ref{fig:message2D})
\begin{eqnarray}
U_{\mathcal{P}\to L} &=& \frac{1}{4\beta}\log\frac{K(1,1)K(-1,-1)}{K(1,-1)K(-1,1)} \nonumber \\
u_{\mathcal{P}\to i} &=& u_{\mathcal{D}\to i} - u_{D\to i} + \frac{1}{4\beta}\log\frac{K(1,1)K(1,-1)}{K(-1,1)K(-1,-1)}
\label{eq:message-Uuu} \\
u_{\mathcal{P}\to j} &=& u_{\mathcal{U}\to j} - u_{U\to j} + \frac{1}{4\beta}\log\frac{K(1,1)K(-1,1)}{K(1,-1)K(-1,-1)} \nonumber
\end{eqnarray}
where
\begin{eqnarray*}
K(s_i,s_j) &=& \sum_{s_k,s_l} \exp \bigg[
\beta \Big( (U_{\mathcal{U}\to U} + J_{jk}) s_j s_k +
(U_{\mathcal{R}\to R} + J_{kl}) s_k s_l + (U_{\mathcal{D}\to D} + J_{li}) s_l s_i + \\
&& (u_{U\to k} + u_{C\to k} + u_{E\to k} + u_{R\to k}) s_k +
(u_{R\to l} + u_{F\to l} + u_{G\to l} + u_{D\to l}) s_l \Big) \bigg]
\end{eqnarray*}

Equations (\ref{eq:message-u}) and (\ref{eq:message-Uuu}) are
equivalent to equations in (\ref{eq:message2D}), once multipliers
(messages) are parametrized in terms of fields. For instance, note
that the $\mu$ multipliers in the left hand side of second equation in
(\ref{eq:message2D}) appear now subtracted in the right hand side of
\rref{eq:message-Uuu}.

The field notation is more comprehensible and has a clear physical
meaning. Each plaquette $\mathcal{P}$ is telling its children links $L$ that
they should add an effective interaction term $U_{\mathcal{P}\to L}$ to the
real interaction $J_{ij}$, due to the fact that spins $s_i$ and $s_j$
are also interacting through the other three links in the plaquette
$\mathcal{P}$. Fields $u$ act like magnetic fields upon spins, and the
complete $\nu_{\mathcal{P}\to L}(s_i,s_j)-$message is characterized by the
triplet $(U_{\mathcal{P}\to L},u_{\mathcal{P}\to i},u_{\mathcal{P}\to j})$, and will be
referred from now on as $Uuu-$message. Furthermore, it is clear that
some fields enter directly in the message-passing equations like
$u_{\mathcal{P}\to i}$ and $u_{\mathcal{L}\to i}$ in \rref{eq:message-u} and
$u_{\mathcal{D}\to i}$ and $u_{\mathcal{U}\to j}$ in \rref{eq:message-Uuu}. Also note
that since our model has no external field, the fields $u$ break the
symmetry of the original Hamiltonian whenever they are non zero. For
instance, in the ferromagnetic model, when all $J_{ij}=J$, these fields
are zero at high temperature and become non zero at Kikuchi's critical
temperature $T=1.42$ \cite{kikuchi}, implying a spontaneous
magnetization in the ferromagnet.

\section{The Dual approximation for the paramagnetic phase}
\label{Dual}

Unfortunately, the iterative message-passing algorithm for solving the
GBP equations (\ref{eq:message-u}) and (\ref{eq:message-Uuu}) often
does not converge on finite dimensional lattices.  While this is
expected if long range correlations are present, it is rather
disappointing that it happens also in the paramagnetic phase, where
one would like to find easily the solution to the model.  Here we are
going to focus only on the paramagnetic phase, and propose an improved
solving algorithm based on physical assumptions.

In the paramagnetic phase of any spin model defined by the Hamiltonian
in \rref{eq:Ham}, that is with no external field, variables have no
polarization or magnetization: this in turn implies that in the
solution all $u-$fields must be zero, and only $U-$fields should be
fixed self-consistently to non zero values.

This paramagnetic solution has some interesting properties. First, it
is always a solution of the GBP equations, since \rref{eq:message-u}
and \rref{eq:message-Uuu} are self-consistent with all $u=0$. This
means that starting from unbiased messages (all $u=0$) the iterative
GBP algorithm keeps this property. Second, the paramagnetic Ansatz is
correct, from the GBP perspective, at least at high enough
temperatures, meaning that even if we start with biased messages ($u
\neq 0$), the iterative algorithm converges to all $u=0$ at high
temperatures. And last, but not least, the well studied physical
behavior for the 2D EA model with zero-mean random interactions
$J_{ij}$, is expected to remain always paramagnetic, \textit{i.e.\ } to have no
transition to a spin glass phase at any finite temperature
\cite{JLMM}.  Therefore, the Ansatz $u=0$ is both physically plausible
and algorithmically desirable.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=0.5\textwidth]{resources/messagesDual.eps}
\end{center}
\caption{Message passing of correlation messages in the dual
  approximation. In the right hand side the trace is taken over the
  black spins.}
\label{fig:messageDual}
\end{figure}

Under the paramagnetic Ansatz, which we shall also call Dual
approximation for a reason to be explained soon, the message-passing
equation (\ref{eq:message-u}) is irrelevant, as it is always satisfied
given that $\hat{u}(0,U,0)=0$, while \rref{eq:message-Uuu} now turns
into (see Fig.~\ref{fig:messageDual})
\begin{multline}
U_{\mathcal{P}\to L} = \widehat{U}(U_{\mathcal{U}\to U},U_{\mathcal{R}\to R},U_{\mathcal{D}\to D}) =\\
\frac{1}{\beta}\:\arctanh\Big[\tanh \beta (U_{\mathcal{U}\to U} + J_{jk})
\tanh \beta (U_{\mathcal{R}\to R} + J_{kl}) \tanh \beta (U_{\mathcal{D}\to D} + J_{li}) \Big]\;.
\label{eq:message-U}
\end{multline}
The only relevant messages now are those associated to the multipliers
$\nu_{\mathcal{P}\to L}(s_i,s_j) = \beta U_{\mathcal{P}\to L}\, s_i\, s_j$, and they will
be refereed to as $U-$messages. \rref{eq:message-U} can be interpreted
as a correlation message-passing equation, giving the new interaction
field $\widehat{U}$ that a certain link shall experience as a
consequence of the correlations transmitted around the plaquette. The
belief \rref{eq:beliefs} also simplify. Obviously $b(s_i)=0.5$ for
every spin in the graph, and the link and plaquette beliefs are
\begin{eqnarray}
b_L(s_i,s_j) &=& \frac{1}{Z_L} e^{\beta (U_{\mathcal{L}\to L} + U_{\mathcal{P}\to L} +
  J_{ij}) s_i s_j}\;, \label{eq:belief_U}\\
b_\mathcal{P}(s_i,s_j,s_k,s_l) &=& \frac{1}{Z_\mathcal{P}} e^{\beta (U_{\mathcal{L}\to L} + J_{ij})
  s_i s_j + \beta (U_{\mathcal{U}\to U} + J_{jk}) s_j s_k + \beta (U_{\mathcal{R}\to R} + J_{kl})
  s_k s_l + \beta (U_{\mathcal{D}\to D} + J_{li}) s_l s_i}\;. \nonumber
\end{eqnarray}

The Dual algorithm we are proposing to study the paramagnetic phase of
the EA model, is a standard message passing algorithm for the
$U$-messages, which works as follows.

\algsetup{indent=4em}
\begin{algorithmic}[1]
\STATE Start with all $U$-messages null
\REPEAT
\STATE Choose randomly one plaquette $\mathcal{P}$ and one of its children
links $L$
\STATE Update the field $U_{\mathcal{P}\to L}$ according to \rref{eq:message-U}
as in Fig.~\ref{fig:messageDual}
\UNTIL{The last change for any $U$-message is less than $\epsilon$ (we
  use typically $\epsilon = 10^{-10}$)}
\RETURN The beliefs $b_L(s_i,s_j)$ defined in \rref{eq:belief_U} for
every pair of neighboring spins
\end{algorithmic}
Some damping factor $\gamma \in [0,1)$ can be added in the update step
$U_{\mathcal{P}\to L} = \gamma U_{\mathcal{P}\to L} + (1-\gamma) \widehat{U}$ in order
to help convergence.

\subsection{Mapping to the dual model}

It is worth noticing that \rref{eq:message-U} is nothing but the
BP equation for the corresponding dual model
(hence the name of the algorithm).

The dual model has a binary variable $x_{ij} \equiv s_i s_j$ on every
link of the original model, and the original coupling constants play
now the role of an external polarizing (eventually random) field
\[
\mathcal{H}_\text{dual}(\vec x) = - \sum_{\< i,j \>} J_{ij} x_{ij}\;.
\]
This Hamiltonian looks like the sum of independent variables, but this
is not the case. The dual variables $x_{ij} = \pm 1$ must satisfy a
constraint for each cycle (or closed path) in the original graph,
enforcing that their product along the cycle must be equal to 1. On a
regular lattice any closed path can be expressed in terms of
elementary cycles of 4 links (the plaquettes) and so it is enough to
enforce the constraint on every plaquette: $x_{ij} x_{jk} x_{kl}
x_{li} = 1$. The Gibbs-Boltzmann probability distribution for the dual
model is then given by
\begin{equation}
P(\vec{x}) = \frac{1}{Z} e^{-\beta \mathcal{H}_\text{dual}(\vec x)}
\prod_{\langle i,j,k,l \rangle} \delta_{x_{ij} x_{jk} x_{kl}
  x_{li},\, 1}\;,
\label{eq:measureDual}
\end{equation}
where the product runs over all elementary plaquette.

The model described by the probability measure in
\rref{eq:measureDual} can be viewed as a constraint satisfaction
problem with a non uniform prior (given by $e^{-\beta
  \mathcal{H}_\text{dual}(\vec x)}$). It is straightforward to derive the BP
equations for such a problem. Indeed by defining the marginal for the
variable $x_{ij}$ on link $L$ in the presence of the solely
neighboring plaquette $\mathcal{P}$ as $\big(1+x_{ij}\tanh \beta U_{\mathcal{P}\to
  L}\big)/2 \propto \exp(\beta U_{\mathcal{P}\to L}x_{ij}\big)$, the BP equations
read
\begin{multline}
\frac12 \big(1+x_{ij}\tanh \beta U_{\mathcal{P}\to L}\big) \propto\\
\sum_{x_{jk},x_{kl},x_{li}}
e^{\beta U_{\mathcal{U}\to U}x_{jk}} e^{\beta J_{jk} x_{jk}}
e^{\beta U_{\mathcal{R}\to R}x_{kl}} e^{\beta J_{kl} x_{kl}}
e^{\beta U_{\mathcal{D}\to D}x_{li}} e^{\beta J_{li} x_{li}}
\delta_{x_{jk}x_{kl}x_{li},\,x_{ij}} \propto\\
\mathop{\sum_{x_{jk},x_{kl},x_{li}:}}_{x_{jk}x_{kl}x_{li}=x_{ij}}
\!\!\!\!\!\!\!\!\!
\big(1 + x_{jk} \tanh \beta (U_{\mathcal{U}\to U} + J_{jk})\big)
\big(1 + x_{kl} \tanh \beta (U_{\mathcal{R}\to R} + J_{kl})\big)
\big(1 + x_{li} \tanh \beta (U_{\mathcal{D}\to D} + J_{li})\big)=\\
1+x_{ij}\tanh \beta (U_{\mathcal{U}\to U} + J_{jk})
\tanh \beta (U_{\mathcal{R}\to R} + J_{kl}) \tanh \beta (U_{\mathcal{D}\to D} + J_{li})\;.
\end{multline}
In the second summation the terms containing one or two $x$ variables
sums to zero, while the other two terms are those written in the last
expression. Equating the first and the last expressions, this equation
is manifestly equal to \rref{eq:message-U}.

\subsection{Average Case Solution}

GBP in general, and the Dual approximation in particular, are methods
for the study of the thermodynamical properties of a given problem.
However, in the limit of large systems ($N\to \infty$, thermodynamical
limit), we expect a typical behavior to arise. This is the so called
\textit{self-averaging} property of disordered systems. By typical we
mean that almost every realization of the interactions $J_{ij}$ will
result in a system whose thermodynamical properties (free energy,
energy, entropy) are very close to the average value.

Normally, in disordered systems, we cope with the $N\to \infty$ limit
and with the average over the random $J_{ij}$ by the replica method.
The application of the replica trick to regions graph approximations
is a challenging task \cite{TLMF10}. However, we can still grasp the
average case behavior with a cavity average case solution of the dual
message-passing equations, at the price of neglecting the local
structure of the graph (beyond plaquettes).

The idea is to represent the set of $U$-messages flowing in any given
graph, by a population of messages $Q(U)$. Then the message-passing
\rref{eq:message-U} is used to obtain such population in a
self-consistent way. More precisely, in every iteration three messages
$U_1,U_2,U_3$ are randomly drawn from the population $Q(U)$ and a new
message $U_0=\widehat{U}(U_1,U_2,U_3)$ is computed by
\rref{eq:message-U} using three couplings randomly selected from
$P(J)$.  The obtained message $U_0$ is put back into the population,
and the iteration is repeated many times, until the population
stabilizes.

Once we have the self consistent population of messages, we can
compute the average energy
\begin{equation}
E_{\mbox{Ave}} = \<-J_{ij} \tanh\beta\left( J_{ij} +U_1 +U_2 \right)
\>_{Q(U_1),Q(U_2),P(J_{ij})}
\label{eq:aveEner}
\end{equation}
by a random sampling of the population and of the interactions. The
average case solution is supposed to be very good whenever the network
of interactions has no or few short loops. This is not the case in any
finite dimensional lattice, since there the short loops (plaquettes)
are abundant.  Nonetheless, the average case solution gives a
reasonably good approximation to the single instance results in 2D and
3D, as shown in the next Section.

\section{Results on 2D EA model}
\label{Results2D}

Message-passing algorithms work fine in the high temperature regime
($T > T_c$) of models defined on random topologies: this is the reason
why these methods have been successfully applied in random constraint
satisfaction problems, like random-SAT or random-Coloring
\cite{KSAT,Col}. However, when used on regular finite-dimensional
lattices, they can experience difficulties even in the paramagnetic
phase, because the presence of short loops spoils message-passing
convergence.

\begin{figure}[!htb]
\includegraphics[angle=270,width=0.8\textwidth]{resources/prob_conv.eps}
\caption[0]{Convergence probability of BP (Bethe approximation) and
  GBP on a 2D square lattice, as a function of inverse
  temperature. Data points are averages over 100 systems with random
  bimodal interactions. System sizes are $N=L^2$ with $L=32, 128$ and
  a damping factor $\gamma=0.5$ has been used in the iteration of the
  message-passing equations. The Bethe spin glass transition is
  expected to occur at $\beta_\text{Bethe} \simeq 0.66$
  ($T_\text{Bethe}\simeq 1.52$) for a random graph with the same
  connectivity as the 2D square lattice. Notably, that temperature
  also marks the convergence threshold for BP equations in the 2D
  square lattice. GBP, on the contrary, reaches lower temperatures,
  but eventually stop converging.}
\label{fig:betheEA2D}
\end{figure}

It is well known that on a random graph of fixed degree (connectivity)
$c=4$ the cavity approximation gives a paramagnetic result above
$T_{\text{Bethe}} \simeq 1.52$ (i.e.\ $\beta_\text{Bethe} \simeq
0.66$) with all cavity fields $u_i=0$.  Below the Bethe critical
temperature, this solution becomes unstable to perturbations, and we
expect many solutions to appear with non trivial messages $u_i\neq
0$. The presence of many solutions in the messages passing equations
is connected to the existence of many thermodynamical states in the
Gibbs-Boltzmann measure, or, equivalently, to the presence of replica
symmetry breaking. The appearance of such a spin glass phase is also
responsible for the lack of convergence of message-passing equations,
since the intrinsic locality of the message-passing equations fails to
coordinate distant regions of the graph (which are now long-range
correlated). As a consequence, the application of BP to the 2D EA
model (that also has fixed degree $c=4$) still finds the paramagnetic
phase at high temperatures, but below $T_{\text{Bethe}}$, the Bethe
instability takes the message-passing iteration away from the $u=0$
solution and does not allow the messages to convergence to a fixed
point (\textit{i.e.\ } the algorithm wanders forever).  In Figure
\ref{fig:betheEA2D} we show the convergence probability for the BP
message-passing equations in the 2D EA model.

On the other hand, a straightforward GBP Parent-to-Child
implementation does not fully overcome this problem. At high
temperatures, the Parent-to-Child equations converge to a paramagnetic
solution with all $u=0$ and non trivial $U\neq0$, which turns out to
be the same solution found by our Dual algorithm. When going down in
temperature, the convergence properties of the algorithm worsen, and
are sensitive to tricks like damping and bounding in the fields. A
thorough discussion of these properties is left for a future work, but
let us summarize that typically the algorithm stop converging at low
temperatures, somewhere below $T_\text{Bethe}$, as shown in Figure
\ref{fig:betheEA2D}.

So, in general, BP and GBP equations are not simple to use in finite
dimensional systems at low enough temperatures: this warning was
already reported in Refs.~\cite{pelizzola,HAK03,MooKap07}. Indeed a
different method for extremizing the constrained free energy named
Double Loop algorithm \cite{HAK03,Yuille} was developed to overcome
such difficulties. As mentioned earlier, Double Loop guarantees
convergence of the beliefs, on any topology, with or without short
loops.  Given the convergence problems in GBP, researchers typically
resort to Double Loop algorithms to extremize region graph
approximations to the free energy, below the Bethe critical
temperature.

In order to make a fair comparison with our Dual algorithm, we have
used an optimized code for GBP and Double Loop algorithms: the open
source LibDai library written in C++ \cite{libdai0.2.3}.

The first interesting result of our work is that our Dual algorithm
converges at all temperatures, just as
Double Loop does. The reason why it converges is that there are no
$u$-messages, so the Bethe instability will not affect our
message-passing iteration.

The second relevant result of our Dual algorithm, is the fact that it
finds the same solution found by the Double Loop algorithm at all
temperatures. In other words, the direct extremization of the region
graph approximation to free energy \rref{eq:freeen} via a Double Loop
algorithm finds a paramagnetic solution characterized by the beliefs
$b_i(s_i)=0.5$ and $b_L(s_i,s_j) = \frac{1}{z} e^{-\beta \tilde{J}_{ij}
  s_i s_j}$; and the effective interactions $\tilde{J}_{ij}$ found by
the Double Loop algorithm are exactly equal to those found with our
Dual algorithm, $\tilde{J}_{ij} = J_{ij} + U_{\mathcal{P} \to L} + U_{\mathcal{L} \to
  L}$. This means that beliefs and correlations found by the two
algorithms are identical: $\< s_i s_j \>_\text{Double Loop} = \< s_i
s_j \>_\text{Dual}$.

The third result is that the running times of our Dual algorithm are
nearly four orders of magnitude smaller than those required by the
Double Loop implementation in libdai, at least in a wide range of
temperatures (see figure \ref{fig:timeDAIDual}). More precisely, the
convergence time of the Dual algorithm growth exponentially with
$\beta=1/T$, but still, in the relevant range of temperatures where the
region graph approximation is a good approximation (not too low
temperatures), the running time is always roughly a factor $10^4$
smaller than Double Loop.

\begin{figure}[!htb]
\includegraphics[angle=270,width=0.8\textwidth]{resources/Time_DAIvsDual.eps}
\caption[0]{Running times of the Double Loop algorithm
  \cite{HAK03,libdai0.2.3} (libdai) and the Dual algorithm averaged
  over 10 realizations of a 2D $8\times8$ EA model with Gaussian
  interactions. Generally the Double Loop algorithm requires a time 4
  orders of magnitude larger than that used by the Dual algorithm.
  Three different precision goals where used for the Dual algorithm
  $10^{-5},10^{-10},10^{-15}$, while the precision of the Double Loop
  algorithm is $10^{-9}$. The inset shows the behavior of the running
  times for both algorithm versus the system size $L=\sqrt{N}$.}
\label{fig:timeDAIDual}
\end{figure}

\subsection{Dual approximation \textit{vs} Monte Carlo simulations}

The fact that our Dual algorithm provides the same results (and much
faster) than the Double Loop algorithm is a very good
news. Essentially is telling us that we are not loosing anything by
restricting the space of possible messages, as far as the region graph
approximation is concerned. However, the ultimate comparison for the
approximation has to be done with the exact marginals and
correlations. In figure \ref{fig:PT-Dual16} we show a comparison
between the exact correlations $\< s_i s_j \>_\text{PT}$ of
neighboring spins obtained with a Parallel Tempering (PT) Monte Carlo
simulation, and the Dual approximation estimate for the same two-spins
correlations.  The coincidence between $\< s_i s_j \>_\text{PT}$ and
$\< s_i s_j \>_\text{Dual}$ is essentially perfect at high
temperatures, and it becomes weaker as the temperature is decreased.
The reason for the discrepancies is obviously the fact that we are
using an approximation in which collective behaviors of spins is
accounted exactly only until the plaquette level; more distant
correlations are approximated and these correlations become more
important at low temperatures.

\begin{figure}[!htb]
\includegraphics[angle=270,width=0.8\textwidth]{resources/Jcorr2D.eps}
\caption[0]{Comparison between the correlations $\< s_i s_j
  \>_\text{Dual}$ obtained by the Dual algorithm and the nearly exact
  correlations obtained by a Parallel Tempering simulation. We used a
  $64\times 64$ EA model with Gaussian interactions. At each
  temperature the data correlation coefficient $\rho$ is reported.}
\label{fig:PT-Dual16}
\end{figure}

\begin{figure}[!htb]
\includegraphics[angle=270,width=0.8\textwidth]{resources/E_2D.eps}
\caption[0]{Energy as a function of the inverse temperature $\beta$ for a
  $64\times64$ 2D EA model, with both types of interactions, Gaussian
  and bimodal. Full lines represent the exact thermodynamical energy
  as obtained by a Monte Carlo simulation, points are the energies
  obtained under the Dual approximation, and dashed lines are the
  average case energies.}
\label{fig:ene2D}
\end{figure}

Given such a good correspondence between the correlations under the
Dual approximation and the true correlations, we expect a very good
estimate for the energy too. In Figure~\ref{fig:ene2D} we show with
points the energy under the Dual approximation and with full lines the
Monte Carlo exact energy: the data are indeed very close.  The dashed
lines show the average case energy for the Dual approximation,
\rref{eq:aveEner}. In spite of the fact that the average case does not
take into account the local structure of the lattice, the average case
energy is quite close to the single instance one.

\subsection{Ground State Configuration in 2D}
\label{GroundState}

The good agreement between the correlations found by the Dual
algorithm, and those found in a Monte Carlo simulation, for the 2D EA
model, compels us to push this correspondence down to $T=0$. More
precisely, using the correlations obtained by our Dual algorithm at
low temperatures, we try to compute a ground state configuration by
the following procedure. The idea is to freeze iteratively the
relative position $s_i s_j$ of those interacting spins that are more
strongly correlated, which is done by setting $J_{ij}\to \pm\infty$,
and re-running the Dual algorithm until convergence every time one
pair of spins is frozen. Note that freezing the relative position of
spins is equivalent to freeze the dual variable $x_{ij} = s_i s_j$.
The freezing procedure is very simple, but for the fact one has to
check that frozen links must be consistent with a spin
configuration. More precisely, frozen $x_{ij}$ variables must satisfy
the requirement that on any closed loops the product is one,
\begin{equation}
\prod_{ij}^{\text{closed loop}} x_{ij} = 1\;.
\label{eq:condition}
\end{equation}
For very short loops the satisfaction of this condition is
automatically induced by the Dual algorithm: for example if three
links on a plaquette freeze, the fourth link is immediately frozen to
a value satisfy condition in \rref{eq:condition}.  However, for longer
loops (as the one shown in Fig.~\ref{fig:cluster}), the propagation of
these constraints by the Dual algorithm is not perfect, since the
information degrades with distance beyond the plaquette level.  Then
we need to enforce the constraints of \rref{eq:condition} by a proper
algorithm.  At each stage of the freezing process, we define the
clusters of frozen links as follows: if two frozen links share a spin,
then they belong to the same cluster. In Figure~\ref{fig:cluster} a
cluster of frozen links is represented by bold lines. Notice that,
once a spin is fixed in a cluster, all other spins are fixed as well
by the frozen correlations. On the other hand, different clusters of
spins can have arbitrary relative orientations.

\begin{figure}[!htb]
\includegraphics[angle=0,width=0.4\textwidth]{resources/cluster.eps}
\caption[0]{Even if the link marked by the arrow is not the most
  polarized link according to the marginals provided by the Dual
  algorithm, the spins it connects are fully correlated by the fact
  that they belong to a cluster of frozen links (bold lines).
  Therefore, the marked link must be immediately fixed accordingly.}
\label{fig:cluster}
\end{figure}

Consider now the situation depicted in Figure~\ref{fig:cluster} and
focus on the value of the correlation between the two spins connected
by the link marked by an arrow. From the fact these two spins belong
to the same cluster of frozen links (shown as bold link in
Figure~\ref{fig:cluster}) we know they are perfectly correlated,
however by running the Dual algorithm we could get a weak value for
this correlation and then proceed by freezing a different link. A set
of sub-optimal choices of this kind may finally produce a
configuration of frozen links where the constraints in
\rref{eq:condition} are not all satisfied.  In order to avoid these
constraint violations we force any link whose spins are already part
of the same cluster to be polarized accordingly. The freezing
algorithm, therefore, works as follows.

\label{alg:reinforcement}
\algsetup{indent=4em}
\begin{algorithmic}[1]
\REPEAT
\STATE run the Dual algorithm until convergence (at a low enough
temperature)
\STATE find the link $L$ with largest finite
$\tilde{J}_L=J_L+U_{\mathcal{P}\to L}+U_{\mathcal{L}\to L}$
\STATE freeze that link by setting $J_L \leftarrow
\Sign(\tilde{J}_L)\, \infty$
\IF {link $L$ is connected to clusters $\mathbf{C}$ and $\mathbf{C'}$
  of frozen links}
\STATE merge clusters $\mathbf{C}$, $\mathbf{C'}$ and link $L$ in a
unique cluster
\ELSE
\IF {link $L$ is connected to a single cluster $\mathbf{C}$ of frozen
  links}
\STATE add link $L$ to cluster $\mathbf{C}$
\ELSE
\STATE create a new cluster with link $L$
\ENDIF
\ENDIF
\FORALL {non-frozen links $L'$ at the boundaries of a cluster of
  frozen links}
\IF {link $L'$ shares both spins with the same cluster}
\STATE freeze link $L'$ accordingly \COMMENT{To avoid violations of
  constraint}
\ENDIF
\ENDFOR
\UNTIL{all links are frozen}
\RETURN the spins configuration obtained by setting one spin and
fixing the rest according to frozen links
\end{algorithmic}

The results obtained with this freezing procedure are quite good. In
figure \ref{fig:EGSvsEBP} we compare the resulting ground state
energies with the exact solutions obtained using a web service running
an exact solving algorithm~\cite{juergengroundwww}. We used an
ensemble of 100 EA models on the 2D square lattice with Gaussian
interactions (so the ground state is not degenerate) and with bimodal
interactions.  Most points are along the bisecting line, meaning that
the ground state found by either methods are the same. The relative
error for the ground state energy is $0.0013$ for Gaussian systems,
and $0.00078$ for bimodal systems. Looking at how many links are
frustrated in one of the solutions and unfrustrated in the other, we
found that the Dual+Freezing algorithm returns $94.3\%$ of the correct
link correlation signs with respect to the true ground state solution
for the Gaussian models. For the bimodal system, given the degeneracy
of the ground state configuration, it is more probable to find the
actual ground state energy but for the same reason the link overlap
between the exact Ground State and the one found with Dual+Freezing is
significantly lower ($86.0\%$).

\begin{figure}[!htb]
\includegraphics[angle=270,width=0.8\textwidth]{resources/EGSvsEBP.eps}
\caption[0]{Correlation of the Dual+Freezing ground state energy with
  the exact ground state energy in $N=16\times 16$ systems. The top
  left points correspond to 100 bimodal systems $J_{ij} = \pm1$, while
  the right bottom points correspond to 100 systems with Gaussian
  interactions. For bimodal interactions, the degeneracy of the ground
  state improves the probability of actually finding the correct
  ground state energy ($93\%$), and conversely reduces the expected
  link correlation overlap with the exact ground state solution
  ($86\%$). For Gaussian interactions, the ground state is not
  degenerated, and only in $\sim 7\%$ of the samples the Dual+Freezing
  method finds the actual ground state; however the average link
  overlap is very high ($94\%$). The line $f(x)=x$ is shown to guide
  the eye. Kindly note that two set of axes are being used.}
\label{fig:EGSvsEBP}
\end{figure}

In general we believe these results on the ground states to be very
encouraging, considering that the Dual algorithm is very fast and not
restricted to the 2D case (at variance to fast exact algorithms for
computing ground states). They provide evidence that the marginals
obtained by this Dual algorithm are reliable even at very low
temperatures.

\section{Generalization to other dimensions}
\label{Results3D}

Let us now consider the region graph based approximation to the free
energy for a generic $D$-dimensional (hyper-)cubic lattice, using the
same hierarchy of regions: square plaquettes, links and spins. After
computing the counting numbers for a general $D$-dimensional lattice,
see \rref{eq:countingnumbers}, the free energy approximation becomes
\begin{eqnarray}
\beta F &=& \sum_\mathcal{P} \sum_{\sigma_\mathcal{P}} b_\mathcal{P}(\sigma_\mathcal{P}) \log
\frac{b_\mathcal{P}(\sigma_\mathcal{P})}{\exp(-\beta E_\mathcal{P}(\sigma_\mathcal{P}))}
\qquad\text{Plaquettes} \nonumber\\
& & -(2D-3) \sum_{L} \sum_{\sigma_L} b_L(\sigma_L) \log
\frac{b_L(\sigma_L)}{\exp(-\beta E_L(\sigma_L))}
\qquad\text{Links}  \label{eq:freeen_D_dim} \\
& & +(2 D^2-4 D+ 1)\sum_{i} \sum_{s_i} b_i(s_i) \log
\frac{b_i(s_i)}{\exp(-\beta E_i(s_i))}  \qquad\mbox{Spins} \nonumber
\end{eqnarray}
Plaquettes are still the biggest regions considered at so have
counting number 1, but now each link is contained in $2(D-1)$
plaquettes, and each spin is in $2 D$ links and $2 D (D-1)$
plaquettes.  The message passing equations for the Dual algorithm in
$D$ dimensions are then
\begin{multline}
U_{\mathcal{P}\to L} = \frac{1}{\beta}\:\arctanh\Bigg[\tanh \beta
\left(\sum_i^{2(D-1)-1} U_{\mathcal{U}_i \to U} + J_U\right)\\
\tanh \beta \left(\sum_i^{2(D-1)-1} U_{\mathcal{R}_i \to R} + J_R\right) \tanh \beta
\left(\sum_i^{2(D-1)-1} U_{\mathcal{D}_i \to D} + J_D\right) \Bigg]\;,
\end{multline}
where $\mathcal{U}_i$ (resp.\ $\mathcal{R}_i$ and $\mathcal{D}_i$) are the $2(D-1)-1$
plaquettes containing the link $U$ (resp.\ $R$ and $D$) excluding
plaquette $\mathcal{P}$.

In the high temperature phase, this Dual approximation with all $u=0$
should be still a valid approach for any dimensionality $D$.  At low
temperatures, however, the EA model in more than two dimensions have a
spin glass phase transition and, therefore, we expect the Dual
approximation to become poorer, as it can not account for a non
trivial order parameter.

By running the Dual algorithm for the 3D EA model we have found a
divergence of $U$-fields around $\beta\simeq 0.39$ for bimodal couplings
and around $\beta\simeq 0.41$ for Gaussian couplings. This divergence is
due to the fact the $U$-fields get too much self-reinforced under
iteration. This divergence does not come as a surprise given that it
happens also when studying the simpler pure ferromagnetic Ising
model. However in the ferromagnetic model the temperature at which
$U$-fields diverge is always below the critical temperature and so the
Dual algorithm still provides a very good description of the entire
paramagnetic phase.

Unfortunately in the 3D EA the divergence of $U$-fields takes place
well above the critical temperature (which is $T_c \simeq 1.12$ for
bimodal coupling and at $T_c \simeq 0.95$ for Gaussian couplings, see
Ref.~\onlinecite{KKY} for a summary of critical temperatures in 3D
spin glasses) and this would make the Dual algorithm of very little
use.  We have studied the origin of this divergence and we have found
a general principle for reducing the divergence of $U$-fields due to
self-reinforcement, thus improving the convergence properties of the
Dual algorithm.  The idea is the following.  When writing the Dual
approximation as a constraint satisfaction problem with a non uniform
prior, see \rref{eq:measureDual}, the constraints may be redundant.
This is the case for the 3D cubic lattice: indeed both the number of
links (i.e.\ variables in the dual problem) and the number of
plaquettes (i.e.\ constraints in the dual problem) are $3N$. So, if
constraints were independent, the entropy would be null at $\beta=0$ and
negative for $\beta>0$ (and this is clearly absurd).  The solution to the
apparent paradox is that constraints are not independent: actually
only $2/3$ of these are independent, and the remaining third is
uniquely fixed by the value of the former. In this way the correct
entropy is recovered at $\beta=0$, given that a problem with $3N$
unbiased binary variables subject to $2N$ independent parity-check
constraints has entropy $N \log(2)$.  The dependence among constraints
can be easily appreciated by looking at the 6 plaquette around a cube:
if 5 of the 6 constraints are satisfied, then the sixth one is
automatically satisfied and redundant.

The general rule for improving the convergence of the Dual algorithm
is to remove redundant constraints (this principle is similar to the
maxent-normal property of region based free energy approximations
\cite{yedidia}).  Redundant constraints have no role in determining
the fixed point values for the beliefs (since they are redundant), but
during the iterations they provide larger fluctuations to messages and
may be responsible for the lack of convergence.  In practice, on a 3D
cubic lattice, we may remove redundant constraints in many different
ways: the basic rule states that one constraint (i.e.\ a plaquette)
should be removed for each elementary cube, otherwise if a cube
remains with its 6 plaquettes at least one redundant constraint will
exist. We have used two different ways of removing one constraint per
cube and we have found the same results in the entire paramagnetic
phase. So, for simplicity, we are going to present data obtained by
removing all constraints corresponding to plaquettes in the $xy$
plane.

\begin{figure}[!htb]
\includegraphics[angle=270,width=0.8\textwidth]{resources/Time_DAIvsDual3D.eps}
\caption[0]{Running times of the Double Loop algorithm
  \cite{HAK03,libdai0.2.3} (libdai) and of the Dual algorithm on a
  $8\times8\times8$ EA model with bimodal interactions ($J_{ij}=\pm
  1$). The Dual algorithm is generally several orders of magnitude
  faster and returns the same solution as the Double Loop algorithm.}
\label{fig:timeDAIDual3D}
\end{figure}

\begin{figure}[!htb]
\includegraphics[angle=270,width=0.8\textwidth]{resources/Jcorr3D.eps}
\caption[0]{Comparison between the correlations $\< s_i s_j
  \>_\text{Dual}$ obtained with the Dual algorithm and the (nearly)
  exact correlations $\< s_i s_j \>_\text{PT}$ obtained with a
  Parallel Tempering simulation in a 3D EA model of size $8\times
  8\times 8$ with random bimodal interactions $J_{ij}=\pm1$. At each
  temperature the correlation coefficient $\rho$ is reported. For the
  lowest temperature shown, $\beta =1.0$, we also report the fraction w-s
  of pairs of spins such that $\< s_i s_j \>_\text{Dual}\< s_i s_j
  \>_\text{PT}<0$.}
\label{fig:PT-Dual3D}
\end{figure}

\begin{figure}[!htb]
\includegraphics[angle=270,width=0.8\textwidth]{resources/E_3D.eps}
\caption[0]{The energy predicted by the Dual approximation in 3D EA
  model, compared to the average case energy, and the Monte Carlo
  simulation. We used a $8\times 8\times 8$ system with both types of
  random interactions, bimodal ($J_{ij}=\pm 1$) and Gaussian
  distributed. }
\label{fig:PT-E3D}
\end{figure}

The Dual algorithm for the 3D EA model on the cubic lattice with no
redundant constraints converges for any temperature above $T\simeq
0.8$ and so we can use it to study the entire paramagnetic phase.  The
lack of convergence deep in the spin glass phase is to be expected.
Just as in the 2D case, the Dual algorithm (when converges) still
finds the same solution obtained by a Double Loop algorithm, and
again, it finds the solution nearly 100 times faster (see
Fig.~\ref{fig:timeDAIDual3D}).  Double Loop has the apparent advantage
of converging at any temperature even at very low ones. However, deep
in the spin glass phase, where the underlying paramagnetic
approximation is clearly inaccurate, we believe that an algorithm
(like the Dual one) that stops converging, is providing an important
warning that something wrong is probably happening. Such a warning
would be lacking by using a Double Loop algorithm.

In Figure \ref{fig:PT-Dual3D} the correlations predicted by the Dual
approximation, and those obtained by a Parallel Tempering Monte Carlo
simulation are compared. At high temperatures the correspondence is
quite good, but not as good as in 2D. However, it is important to
stress that the 3D EA model is much more difficult to simulate than
the 2D case: there is no exact method for computing the thermodynamics
(at variance to the 2D case) and Monte Carlo methods require huge
thermalization times, while the Dual algorithm runs in \emph{linear}
time with the system size.

In Figure~\ref{fig:PT-E3D} we show the estimates for the energy
obtained from the Monte Carlo and the Dual algorithm (both on a single
sample and on the average case).  The very strong agreement between
the Dual algorithm results on single samples and on the average case
is telling us that $U$-messages arriving at a given point on the
lattice are uncorrelated to a very large extent.  In other words, the
effect of short loops in the lattice is not manifestly present in
correlations between messages.  On the contrary, the comparison
between Dual algorithm results and Monte Carlo results is good only at
high temperatures, and it degrades when approaching the critical
temperature.  This discrepancy can be understood as due to a growing
correlation length in the EA model that diverges at the critical
temperature: our Dual approximation does not account for correlations
beyond the plaquette level and so it becomes inevitably poorer when
the correlation length diverges.  However, given the extremely fast
converging times of the Dual algorithm, it can be viewed as a very
effective algorithm for sampling the high temperature paramagnetic
phase and as a reasonable approximate algorithm when approaching the
critical point.

\section{Conclusions}
\label{Conclusions}

We have introduced a novel Dual algorithm to compute marginals
probabilities in the paramagnetic phase of frustrated spin models
(e.g.\ spin glasses) on finite dimensional lattices.  Inspired by the
fact that in a paramagnetic phase with no external field each variable
is unbiased (i.e.\ local magnetizations are null), the Dual algorithm
is derived by adding such paramagnetic constraints in the GBP
equations.  While BP (i.e.\ Bethe approximation) and GBP algorithms
have serious convergence problems at low temperatures even in the
paramagnetic phase, the Dual algorithm converges very fast in a much
wider range thanks to these constraints.  The Dual algorithm can also
be seen as BP on the dual lattice, where the interactions $J_{ij}$ act
as external fields on dual variables, thus improving convergence
properties of the message passing algorithm.

We have tested the Dual algorithm for the Edwards Anderson spin glass
model with bimodal and Gaussian couplings on 2D (square) and 3D
(cubic) lattices.  The results are very encouraging, showing
convergence in the whole paramagnetic phase (and even slightly in the
frozen phase for the 3D EA model) and comparing very well with exact
correlations measured in Monte Carlo simulations. A comparison with a
Double Loop algorithm (which is the state-of-the-art among general
purpose inference algorithms) shows that both algorithms found the
same result, but our Dual algorithm runs roughly 100 times faster. We
also tried to push the Dual approximation to the limit, and we used
the correlations inferred by the Dual algorithm to compute ground
states configurations in the 2D EA model by a freezing
procedure. Again, we showed that the ground states obtained in this
way compare very well with exact computations.

The success of our proposal clearly shows that as long as variables
are not long range correlated, the computation of correlations in a
generic spin model can be done in a very fast way by means of message
passing algorithms, based on mean-field like approximations. This kind
of inference algorithms do not provide in general an exact answer
(unless one uses it at very high temperatures or on locally tree-like
topologies), and so they can not be seen as substitutes for a Monte
Carlo (MC) sampling. However there are many situations where a fast
and approximate answer is required more that a slow and exact
answer. Let us just make a couple of examples of these situations. On
the one side, if one need to sample from very noisy data, an
approximated inference algorithm whose level of approximation is
smaller than data uncertainty is as valid as a perfect MC sampler. On
the other side, if one need to use the inferred correlations as input
for a second algorithm (as for the freezing algorithm in
Section~\ref{GroundState}) that will eventually modify/correct these
correlations, a fast and reasonably good inference is enough.

The promising results shown in the present work naturally ask for an
improvement in several directions.  For example, in the paramagnetic
phase of a model defined on a 3D lattice, our inference algorithm
could be improved by using the $2\times 2\times 2$ cube as the
elementary region, instead of the plaquette.  An even more important
improvement would be to extend the applicability range of the
algorithm to the low temperature phase: but this requires a rather non
trivial modification, since in low temperatures phase the assumption
of zero local magnetizations needs to be broken.

\begin{acknowledgments}
F. Ricci-Tersenghi acknowledges financial support by the Italian
Research Minister through the FIRB project RBFR086NN1 on ``Inference
and optimization in complex systems: from the thermodynamics of spin
glasses to message passing algorithms''.
\end{acknowledgments}

redpajama_set_name: RedPajamaArXiv


I had no idea you lived in Brisbane. That's so cool! I lived there for a couple of years straight out of school to study Digital Film and Television, at JMC Academy right next to South Bank. I worked casually in the CBD next to Myers at the time, I was in there every day and loved it. I live in Townsville now and miss Brisbane at times, sadly. Like you I loved Singapore and holidayed there every year. I have one of the fondest memories being there to celebrate the year 2000 in a fancy hotel, and from the top floor they had thousands of balloons that dropped down to the foyer, I was like 11 at the time and remember it so well lol. Did you live in Singapore? I spent half my childhood in Malaysia, where I lived in Melaka and then later Ipoh.
Be careful with your heart hey, while you may have interest in just a short casual relationship you will likely still get hurt. Some people can get away unscaved in these type of relationships. Life has a way of surprising us, so be careful shutting the door on a long term relationship if the right person does indeed come knocking.
I really enjoy reading your blog too. Oh and Happy Birthday!
Wow, the millennia, I remember celebrating that on Sentosa beach… I was only 6, but I guess what I really remember is the fireworks and cake, haha!
Yeah, I lived in Singapore for 17 or so years! I really loved it there, still miss it from time to time but I'm keeping myself busy and trying to not think about all the things I miss about my childhood home. It's hard sometimes, but I guess moving country is never easy. I miss the food and the friends and the nightlife, how safe it was and how I knew my way around like the back of my hand… I'm sure with a bit more time I'll know Brisbane better, but I don't know if I'll ever be settled anywhere quite as permanently as I was in Singapore for a while at least.


Good morning my awesome readers! Today is a long awaited day for sure. Today we are going to get the three elements of the chicken space assembled!
I can in no way say this was easy, but anything worth having is not easy. We begin the day by getting the ramp fitted to the coop side. With a little trimming it came right together.
The next chore is getting all three pieces in the same area, so it's off to the tractor. The work area was a bit of a harrowing experience. The center of gravity was so high, and the wheelbase on the garden trailer is narrow. Every rock made it seem like we were going over. We emerged triumphant though.
Now that the three pieces are married up, I can see the beast that has been created, in all its glory.
This is leading me to believe that I need about ten more acres. It will surely take some creative wiggling to employ this unit for sure.
Well as with any project around the house, it has the potential to devolve into a playground run. We are pretty fortunate to have some good ones near by.
After the playground, it's back to work. The final bit of chicken wire is in. Tomorrow morning we introduce some birds to this thing!
There are still some minor bugs to work out, but at least now the birds can begin to occupy it while I tinker.
Some of the minor bugs are the doors that need to be reconfigured, I have to block off the nesting boxes until it's time to lay. I also need to screw in a few roosting benches, and give it some shavings. The big feeders will also need to be installed. There is still a bunch of work to do, but we have cleared the biggest hurdle.
Previous PostThis may be more complex than I had thought.
Next PostToday is the big day!


Melanie Barboni also known as 'hummingbird whisperer' is working as an assistant researcher in the UCLA Earth, Planetary and Space Science. She has successfully built a community of birds (about 200) outside her office and because of the cordial relationship she has with them, they do complain whenever she is late to serve their food.
Her obsession with hummingbirds started long ago when she was a child in Switzerland, this is a country without any population of this species.
"My dream as a child was to see hummingbirds. I was joyous when I discovered that my next job assignment is in Los Angeles where hummingbirds live all year round," said Barboni.
She also added that "She can't go to other environment where these birds can't be seen…..This is amazing, but they do help people and I have seen that myself. They also make me happy. Having a fulfilled day? Who cares, there are hummingbirds around and they make the day lovely and fulfilled" The birds definitely make the good day better.


text:
Q: Grails fails to parse request when content type is specified during post Using wget I make two posts to the same url with xml in the body.  The first works.  The second has the content type specified and it does not work.  Why is this and how do I get grails to parse the request even when the content type is specified?
first wget:
wget http://localhost:8080/myApp/myMoeView/save --post-file=xmltest.xml

Grails logs (notice the "parsed params"):
2014-02-27 18:44:05,465 [http-bio-8080-exec-9] INFO  httplogger.DefaultHttpLogger  - << #3425 POST http://localhost:8080/myApp/mrMoeView/save
2014-02-27 18:44:05,465 [http-bio-8080-exec-9] INFO  httplogger.DefaultHttpLogger  - << #3425 headers [Cookie: JSESSIONID=D5B2399D6FFB800130E826DCD7DB0C37]
2014-02-27 18:44:05,465 [http-bio-8080-exec-9] INFO  httplogger.DefaultHttpLogger  - << #3425 body: ''
2014-02-27 18:44:05,491 [http-bio-8080-exec-9] INFO  httplogger.DefaultHttpLogger  - << #3425 dispatched to mrMoeView/save with parsed params ['<?xml version':'{"1.0" encoding="UTF-8" standalone="yes"?><mrMoeView><absoluteTolerance>1.004</absoluteTolerance><endTime>0</endTime><id>4187</id><lastModified>2014-01-07 00:00:00.000 PST</lastModified><modelRealizationId>1193</modelRealizationId><mrMoeId>4187</mrMoeId><mrMoeName>Default MOE from Model 2140</mrMoeName><relativeTolerance>1e-4</relativeTolerance><startTime>0</startTime></mrMoeView>

second wget:
wget http://localhost:8080/myApp/mrMoeView/save --post-file=xmltest.xml --header="Content-Type:application/xml"

Grails logs (notice no parsed params, and the body has all the xml):
2014-02-27 18:46:27,291 [http-bio-8080-exec-5] INFO  httplogger.DefaultHttpLogger  - << #3427 POST http://localhost:8080/processdb/mrMoeView/save
2014-02-27 18:46:27,291 [http-bio-8080-exec-5] INFO  httplogger.DefaultHttpLogger  - << #3427 headers [Cookie: JSESSIONID=B1FAAB54422AC7F1E243D4CE68C72B77]
2014-02-27 18:46:27,291 [http-bio-8080-exec-5] INFO  httplogger.DefaultHttpLogger  - << #3427 body: '<?xml version="1.0" encoding="UTF-8" standalone="yes"?><mrMoeView><absoluteTolerance>1.004</absoluteTolerance><endTime>0</endTime><id>4187</id><lastModified>2014-01-07 00:00:00.000 PST</lastModified><modelRealizationId>1193</modelRealizationId><mrMoeId>4187</mrMoeId><mrMoeName>Default MOE from Model 2140</mrMoeName><relativeTolerance>1e-4</relativeTolerance><startTime>0</startTime></mrMoeView>'
2014-02-27 18:46:27,320 [http-bio-8080-exec-5] INFO  httplogger.DefaultHttpLogger  - << #3427 dispatched to mrMoeView/save with parsed params [].

Grails version 2.3.5
UPDATE
UrlMapping:
class UrlMappings {

static mappings = {
    "/$controller/$action?/$id?"(parseRequest:true){
        constraints {
            // apply constraints here
        }
    }

    "/"(view:"/index")
    "500"(view:'/error')
}
}

A: With content type specified content will be received as part of request body instead of parsed params.
Body can be accessed as request.XML in action. Going through the comments, we found out the usage of a older way to bindData. With Grails 2.3.*, the request payload can be directly bound to a domain object provided the body has a valid id as :
def save(MyDomain abc){
    //use abc.name
}

If a valid id is not present in request body then domain object will be null inside the action.
@Data binding.

redpajama_set_name: RedPajamaStackExchange


text:
An exciting new career for EK's Imagineers
A NEW alternative rock band hailing from East Kilbride are already making waves after catching the eye of an indie record label.
Having played just a handful of gigs, the Imagineers are virtual newcomers to the Glasgow gig scene, but their edgy latin-tinged pop sound and unique style was enough to impress Glasgow-based Sunstone Records.
The independent label professes to promote and release new music that it believes in, and record boss Garry Opray believes he has discovered something big.
Garry said: "I knew the minute I saw them live that I was going to sign them, they had the songs, the charisma, stage presence and image that you rarely see in young bands. They definitely have what it takes to go far in the music industry.
"They are 100 per cent committed to the cause, be it rehearsing, recording and gigging. They have a great attitude and mentality towards their music."
Frontman Steven Young, 23, of Greenhills; lead guitarist Lee Ballard, 24, of Larkhall; Bassist Alistair Greig, 21, of Calderwood and drummer Stephen Forbes, 25, of Kilmarnock, formed almost a year ago, but decided to focus all their energies on perfecting their musical style before going live.
The four-piece rock outfit say they know exactly what they want – big choruses, perfect harmonies and tight rhythms.
The band boasts an effortlessly cool style dripping with raw energy and nostalgia. From tunes with guitar parts that wouldn't sound out of place in a Tarantino movie to delightful lovelorn acoustica, The Imagineers' electric ideas and remarkable songwriting abilities are creating a buzz.
Lead singer Steven Young, also on acoustic guitar, said: "We're really excited to be gigging now and signing to Sunstone is so exciting. It's quite a contrast in mood, with elements of both soft folk and edgy up-beat rock."
The former St Bride's pupil added: "There seems to be a real buzz about our gigs. We're getting a really good reaction and it's busier each time we play."
The band's first single will be released on Sunstone Records in September but catch their unique sound at the Buff Club tonight. The full band will play Nice and Sleazys on May 29.
Visit the bands myspace at www.myspace.com/theimagineers1

redpajama_set_name: RedPajamaCommonCrawl


text:
example :french wine 1997 yearglasses for white wine 37 cl
Cognac "Camus" V.S.O.P., gift box, 0.7 L
m. Savelovskaya New — under the order
m. Leninsky Prospekt New — under the order
m. Serpukhovskaya New — under the order
m. Shosse Entuziastov New — under the order
m. Suharevskaya New — under the order
m. Rizhskaya New — under the order
m. Pervomayskaya New — under the order
m. Krylatskoye New — under the order
m. Varshavskaya New — under the order
m. Myakinino New — under the order
m. Novokosino New — under the order
France, Cognac
Cognac class:
Ugni Blanc
0.7 L  in the box 4 537 rub
Cognac on Camus
Reviews of purchase "Camus" V.S.O.P., gift box, 0.7 L
Cognac rich amber-golden color.
Cognac has a great taste with notes of flowers, honey, spices, fruit and oak.
Cognac is a harmonious aroma with notes of flowers, fruit and woody.
Cognac is used in pure form with ice, and is also an excellent ingredient for cocktails.
Camus VSOP - a high-quality brandy, which is made of the finest cognac, comes from the most famous regions. Cognac is aged in oak barrels for 10-15 years. Poured Camus in elegant bottles made in a bright, modern design.
In 1863, Jean-Baptiste Camus Cognac House founded Camus, whose goal was to produce only the highest quality cognac. Within a few years Cognac Camus won the hearts of Europeans, and later became the official cognac at the court of Nicholas II. For the production of high-quality Camus selects the best harvest in the intricate art of assemblage and distillation of wine used a number of family secrets that are passed from generation to generation. Each step in the manufacturing process is strictly controlled by the masters. The company has its own vineyards in the best areas of the region of Cognac: Grand and Petit Champagne, Fins Bois, Bons Bois. Brandy is made from grapes Ugni Blan, Folle Blanche and Colombard, which is aged in barrels of Limousin oak and tronseyskogo. Maturation takes place in several stages: young alcohols two months aged in new barrels, then poured into the old, in which several boards (staves) are replaced by new ones. Camus Cognac House - is an independent family-owned company, whose head, Jean-Paul Camus, personally engaged in assemblage of cognac. Camus is one of the best-selling brandy.
Website: http://www.camus.fr/
Similar to "Camus" V.S.O.P., gift box, 0.7 L
"Remy Martin" VSOP, with box, 0.7 L
RCTS 16
"Courvoisier" VS, gift box, 0.7 L
"Courvoisier" XO Imperial, gift box, 0.7 L
Hine Rare VSOP with box, 0.7 L
"Grey Goose", 0.7 L
A. de Fussigny, "Selection", gift tube, 0.5 L
In our store you can buy cognac "Camus" V.S.O.P., gift box, 0.7 L, price "Camus" V.S.O.P., gift box, 0.7 L — 4 537 rub.. Producer cognac Camus. Delivery "Camus" V.S.O.P., gift box, 0.7 L.


Therapy designed around your needs.
Individual therapy at the Mind Therapy Clinic is designed around your needs by some of the best psychologists in the field who've dedicated their lives to helping people overcome mental health challenges. Each therapist is trained specifically to help you with your unique issues whether they are everyday concerns such as stress and relationships, or more complex diagnosed mental conditions. Your therapy is determined by you and your therapist.
Because you may need more intensive care from time to time, these therapies can be integrated with the Mind Therapy Clinic's Intensive Outpatient Program (IOP), Partial Hospitalization Program (PHP), and Trauma Treatment Programs at any point in time during your treatment.
We utilize evidence-based, scientific approaches to healing because we believe our clients deserve the best treatment possible based on the latest objective findings. Our team of highly skilled medical doctors, nurses and doctoral- and master's-level specialists integrate a wide range of services to carefully design treatment plans and guide you through the entire journey. Because our mission is the same as yours - to help you heal and move toward more productive and healthy lives.


This page is about the monster type. For the divination card, see The Watcher.
Watchers are a type of monster added in Version 1.1.0.
The blinding attacks can be avoided by not being faced towards the enemy when the attack hits.
1% increased Lightning DamageDeals (3-22) to (48-426) Lightning DamagePlace into an item socket of the right colour to gain this skill. Right click to remove from a socket.


FAQ :: Can you lose your eternal rewards?
The Bible doesn't really mention if eternal rewards can be earned and then later, lost. However, it does plainly say that many people will not receive a large portion of the rewards they thought that they had coming to them.
The apostle Paul, in 1 Corinthians, stated that all of our works will be tested by fire, and we will only get to keep the valuables that the flames do not destroy. Nearly all Christians have a good idea of what they've accomplished in life. Many of the folks who think they are due a sizable reward will be shocked when the fire of judgment reveals that most of their deeds were based on vain self-glory.
"For no other foundation can anyone lay than that which is laid, which is Jesus Christ. Now if anyone builds on this foundation with gold, silver, precious stones, wood, hay, straw, each one's work will become clear; for the Day will declare it, because it will be revealed by fire; and the fire will test each one's work, of what sort it is. If anyone's work which he has built on it endures, he will receive a reward. If anyone's work is burned, he will suffer loss; but he himself will be saved, yet so as through fire" (1 Corinthians 3:11-15).


text:
R & S Records
Djrum – Portrait With Firewood 2x LP
Decrease quantity for Djrum – Portrait With Firewood 2x LP
Increase quantity for Djrum – Portrait With Firewood 2x LP
'Portrait With Firewood' is Felix's most personal body of work to date, the product of an emotionally turbulent 2017, capturing the range of feelings and emotions he went through in vivid sonic beauty. By putting aside his previous sampleadelic approach he returned to his childhood instrument of the piano as a core starting point.
"It's a confessional record… I realise that's a word mostly used to describe singer/songwriter rather than (largely) instrumental music, but I think it's apt. There's a sort of emotional candour."
Felix is classically trained in the jazz tradition and influenced by the likes of Keith Jarrett and Alice Coltrane. Previously he was shy at the prospect of fans hearing his piano playing, but determined to overcome this fear he has brought forward a new honesty to his work. "Finding the confidence to work with my own piano improvisations was a big part of that. Once I had figured out how I was going to make the music, it actually fell in to place rather quickly."
Felix's goal was to create something "overwhelmingly beautiful", but also to capture the "inherent melancholy in beauty in all it's impermanance and fragility". He took inspiration and solace from performance artist Marina Abramovic. "She has an incredibly deep understanding of the human condition, and expresses it in such a poetic way. Many of the themes of her work had particular resonance for me over the course of 2017 as I worked on the album. I was moved to tears on several occasions watching her videos or reading about her work."
Felix collaborated with cellist Zosia Jagodzinska and vocalist Lola Empire. Jagodzinska recorded several takes of improvisations over the track 'Creature' which Felix would chop, pitch and layer into new melodic lines and seed throughout the album.
Felix's new approach expanded to experimentation with field recording, contact micing his beloved piano and purchasing his first hardware synth, all in service of enriching the personal, humane quality of the record.
"Music helps me to communicate the sorts of things that I find almost impossible to put in to words. I think the process for this album has helped me create a more rich and emotionally complex body of work than I have managed before."


Plot potential (subject to planning) in the Bradbourne Lakes area of Sevenoaks.
A three bedroom semi-detached family house, located on a quiet cul-de-sac in 'The Lakes', a popular residential area close to Sevenoaks station and town centre.
The house sits on a generous corner plot and based on recent development in the immediate area, we believe there could be potential with this plot, subject to the necessary planning consent. The property is well presented throughout with a neutral décor and bright, spacious accommodation.
The front door opens into an entrance hall with stairs leading to the first floor. The living room is at the front of the house has a large window to the front and an attractive fireplace with gas fire. The kitchen is fitted with a range of wooden wall and base units with a worktop over incorporating a sink and drainer. There is a built-in double oven and a gas hob with extractor fan over. There is an integral fridge, freezer and dishwasher, and space and plumbing for further appliances. This room has been extended to create a lovely dining area which overlooks the garden and has doors leading outside. A family bathroom completes the ground floor accommodation and is fitted with a white suite comprising a bath with shower over, wash hand basin and low level W.C.
Upstairs the first floor landing leads to three good size bedrooms, the two largest bedrooms benefit from built-in cupboards.
Outside the property is set back off the road with a pretty front garden and footpath leading to the front door, with a side gate providing rear access. The property sits on a corner plot with a good size garden to the side and rear of the house. There is a generous patio to the side of the house and the remainder is mainly laid to lawn, with a gate at the rear providing access to a driveway and single garage.


Helga's Show (S03E27) is the twenty-seventh episode of season three of "Hey Arnold!" ... More Helga's Show (S03E27) is the twenty-seventh episode of season three of "Hey Arnold!" released on Wed Nov 25, 1998. Hey Arnold! stars Dan Butler, Jim Belushi and Craig Bartlett.


text:
South Carolina AFL-CIO
Union Member Benefits
Central Labor Councils (CLC)
Labor Thought of the Day
Labor in Pictures
Join our email list to stay in the loop!
Space Structure
Tier 1 National Org
Tier 1 Sites
Subspaces
Catawba Central Labor Union, AFL-CIO
Charleston Central Labor Council, AFL-CIO
Columbia Central Labor Union
All Spaces...
All Groups...
We are one of nearly 500 state and local labor councils of the AFL-CIO and are the heart of the labor movement. We are democratically elected bodies dedicated to represent the interests of working people at the state and local level. We mobilize our members and community partners to advocate for social and economic justice and we strive daily to vanquish oppression and make our communities better for all people—regardless of race, color, gender, religion, age, sexual orientation, or ethnic or national origin.
ILA Disaffiliation Statement
International Longshoreman's Association (ILA) after 61 years of membership with the AFL-CIO has decided to disaffiliate themselves from the AFL-CIO. This disaffiliation has impacted the SC AFL-CIO President, as he is a member of the ILA. In order for Mr. Brave to continue to serve as President he has decided to join the Washington Baltimore News Guild (TNG-CWA 32035). If you have any questions please contact the office either by email [email protected] or by phone 803-926-8680.
Charles Brave
April Lott
Boris Gibson
Lindsay McClelland
Board Member - OPEIU
421 Zimalcrest Drive
© AFL-CIO. All rights reserved.
Photographs and illustrations, as well as text, cannot be used without permission from the AFL-CIO.
Privacy Policy | Terms of Use | Log In
This page is Public


Focus on how to set up SOLIDWORKS PDM in a model-based environment. Learn the what and how of 3D model-based workflows and recommended practices for using SOLIDWORKS PDM in compliance with model-based standards. Pricing is per person/pp.
Learn the best ways to use SOLIDWORKS PDM in a collaborative design environment.


text:
Patents | Patente
Building structure of pre-cast monolithic walls and interfloor slabs
(10) WO 2013/019134 A1
(22) 1 September 2011 (01.09.2011)
(43) 7 February 2013 (07.02.2013)
(57) The invention relates to a building structure comprising composite floor slabs and pre-cast wall panels. The floor slabs comprise a styrofoam block (I) having longitudinal (2) and transverse channels (3) cut into an upper surface, the channels are provided with reinforcement and spacers therefor and are filled to first depth with concrete. Such a pre-cast slab may be transported to a building site and the floor structure finished by applying a reinforcing mesh and additional concrete. The pre-cast...
BFT 04/2013
Issue 2018-05
Permanent form panel, assembly of said panels, and method for producing a concrete floor slab
(11) EP3292254 A1 (57) The invention relates to a permanent form panel (1) for creating, at elevation, a concretecompression floor slab. When the slab is cast, said panel makes up the bottom portion...
Precast floor slab and method for forming a flooring deck and building formed of precast floor slabs
(11) EP 3 517 698 Al (22) 29.01.2019 (43) 31.07.2019 Bulletin 2019/31 (57) The invention relates to a floor slab, which is intended to form a flooring deck. The floor slab (26) includes cast...
Pre-cast concrete formwork, wall system and method of construction
(11) 2567341 A (22) 26.07.2017 (43) 10.04.2019 (57) ) Formwork for building a wall system, the formwork comprising: a first pre-cast concrete wall panel and a second pre-cast concrete wall panel, the...
Modular concrete building
(10) US 2013/0061553 A1 (22) Mar. 13, 2012 (43) Mar. 14, 2013 (73) THE SPANCRETE GROUP, INC., Waukesha, WI (US) (57) A modular concrete building is made of a plurality of precast concrete panels which...
Precast building construction system
(11) GB 2578197 (22) 19.08.2019 (43) 22.04.2020 (57) The floor panels comprise precast concrete panels 10 Each panel has a reinforced precast concrete slab having an upper surface 12 and downstands...


The South Coast Air Quality Management District issued a smoke advisory through noon Monday due to Southern California fires.
Wildfires raging up and down California are creating hazardous air quality conditions for residents across Southern California and in the Coachella Valley.
The South Coast Air Quality Management District issued a smoke advisory through noon Monday but said Santa Ana winds could help move smoky air out of Riverside, San Bernardino and Orange counties in the coming days.
SCAQMD monitors in the Coachella Valley show desert air quality was still "good," but many areas surrounding the valley have seen air quality conditions rated "moderate" or "unhealthy for sensitive groups."
The Ventura County Air Pollution Control District also issued a smoke advisory over the weekend. In a release Sunday, officials said changing wind conditions could alleviate some of the air quality concerns.
Offshore winds are expected to push smoke in the western part of the county over the ocean, meaning clearer air conditions for Piru, Ojai and the city of Ventura. Officials said air quality in these areas would remain moderate on Sunday. However, people sensitive to smoke were advised to remain cautious.
"Fire smoke as well as fire debris, such as ash, stirred up from the winds will continue to impact areas in and around Camarillo, Thousand Oaks and Simi Valley," district officials said in the release. "Air quality will be unhealthy for sensitive groups in these areas and at times reach unhealthy levels, especially in the Thousand Oaks area."
District officials added that smoke conditions can change rapidly and people should remain alert.
Older adults, young kids, pregnant women and people with heart or lung problems should take additional precautions.
Air quality experts also said that people should not rely exclusively on paper dust masks, which block large particles but not small particles and gasses.
Check DesertSun.com for continuous updates on California wildfires and fire-related news.


The LifeFORCE aromatherapy products for cats have been formulated to ensure feline safety and effectiveness. And are pure essential oil products of 100% Therapeutic Quality.
Ingredients: proprietary blend of pure Lavender, Benzoin, Palo Santo, Marjoram and Patchouli Essential Oils, Distilled Water, Organic Veg Glycerin and Aqua-Em (Natural Vegetable Source).


We've had several requests to just test our gamma radiation pod. We've been working on it for years. Honestly, it even had nothing to do with the Incredible Hulk and the guy's practically unlimited degree of strength and regenerative prowess. We were actually just trying to open a gateway into the unicorn dimension. (You know how they gallop along light to traverse from here to their… well, that's all besides the point.) The fact is that the gamma radiation room is not ready for testing in any capacity, especially not for empowering humans to become Avengers-level heroes!
But, we're also not going to just sit back while your desires are going unanswered. Granting wishes is, of course, one of the most important things that we can do! So, we can at least get you part way there with these officially licensed adult Hulk Avengers II Gloves. Possessing all of the gamma radiation that could be accidentally poured into a set of otherwise normal gloves, these super green, super powered Hulk Smashers will no doubt make you feel incredible and at least start you on your way to unbeatable strength!


FIND A STOCKIST md node.
Use locater to find retailer near you information steam condensate pumps selection application You are getting SBHH everytime want drive train? modified one default routes messed something up? Are there missing on trains? shower is an enclosure that has fast become newest bathroom innovation supplying style, luxury, cutting-edge technological encompassed js.
Visit a dedicated Insignia showroom readme.
Steam Workshop: The Elder Scrolls V: Skyrim 81157 1 14 rev n/c 3/09 sas thermasol installation instructions ssb/ssp kits, asd ls generators, tt control directions detailed this guideline designed familiarize reader general understanding variety mr. This mod replaces bow firing sounds with PEW best practices trap two major functions, remove as quickly it forms, prevent discharge. I take no responsibility for your sanity, install at own risk fjp says: may 17, 2010 10:19 pm. Gift friends, trade items, and even create new content games in the Workshop turbine car killed itself. Help shape future of favorite games due constant high rpm necessary operation, city fuel economy inherently abysmal. PRODUCT RANGE ein häufig auftretendes problem einfach gelöst. Check out our entire range products learn about preventing backflow hammer return lines. INSIGNIA OUTLETS includes illustrated tips proper check valve installation. Visit a dedicated Insignia showroom readme. FIND A STOCKIST md node. Use locater to find retailer near you information steam condensate pumps selection application You are getting SBHH everytime want drive train? modified one default routes messed something up? Are there missing on trains? shower is an enclosure that has fast become newest bathroom innovation supplying style, luxury, cutting-edge technological encompassed js. All Schluter products available local Mosaic Tile location node. more details What showers History js port steamkit2. history room goes back thousands years lets interface without running actual client. It was popular ancient Greeks subsequently adopted by the could be used run an.


text:
module.exports = function (Arrow) {
	return Arrow.Model.extend('user_post', {
		fields: {
			users: { type: Array, model: 'user' },
			posts: { type: Array, model: 'post' }
		},
		connector: 'appc.composite'
	});
};

redpajama_set_name: RedPajamaGithub