Protein Fold Recognition Using Markov Logic Networks - Mathematical Approaches to Polymer Sequence Analysis and Related Problems - page 79

also to the proposed extension of SMLNs. IRoTS is one the best weighted MAX-
SAT solvers and MAP inference in SMLNs can benefit from it.
Given a SMLN in the form of clauses based on temporal predicates , includ-
ing a time predicate and a set of evidence atoms, the KB to be used as input for
IRoTS is formed by constructing all groundings of clauses in the SMLNs involving
query atoms. Then the evidence atoms are replaced by their true values followed by
simplification. Once the SMLN has been propositionalized, it is a natural input to
IRoTS.

4.6 Markov Chain Iterated Robust Tabu Search

In this section, we describe how IRoTS can be combined with Markov Chain Monte
Carlo (MCMC) to uniformly sample from the space of satisfying assignments of a
clause. We show how the proposed algorithm MC-IRoTS can be used for inference
and learning in SMLNs.

4.6.1 Conditional Inference Through MC-IRoTS

Conditional inference in graphical models involves computing the distribution of
the query variables given the evidence and it has been shown to be #P-complete
[ 29 ]. The most widely used approach to approximate inference is using MCMC
methods and in particular Gibbs sampling. One of the problems that arises in real-
world applications is that an inference method must be able to handle probabilistic
and deterministic dependencies that might hold in the domain. MCMC methods are
suitable for handling probabilistic dependencies but give poor results when deter-
ministic or near deterministic dependencies characterize a certain domain. On the
other hand, logical ones such as satisfiability testing cannot be applied to proba-
bilistic dependencies. One approach to deal with both kinds of dependencies is that
of [ 21 ] where the authors use SampleSAT [ 28 ] in a MCMC algorithm to uniformly
sample from the set of satisfying solutions. As pointed out in [ 28 ], SAT solvers find
solutions very fast but they may sample highly non-uniformly. On the other hand,
MCMC methods may take exponential time, in terms of problem size, to reach the
stationary distribution. For this reason, the authors in [ 28 ] proposed to use a hybrid
strategy by combining random walk steps with MCMC steps, and in particular with
Metropolis transitions. This permits to efficiently jump between isolated or near-
isolated regions of non-zero probability, while preserving detailed balance.
We use the same approach as the authors did in [ 21 ], but instead of SampleSAT,
for MC-IRoTS we propose to use SampleIRoTS, which performs with probability
p a RoTS step and with probability 1 p a simulated annealing (SA) step. We used
fixed temperature annealing (i.e., Metropolis) moves. The goal is to reach as fast as
possible a first solution through IRoTS and then exploit the ability of SA to explore