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

Algorithm 1 Iterated Robust Tabu Search
Input: C: set of weighted clauses in CNF, BestScore: current best score)
CL C = Random initialization of truth values for atoms in C;
CL S = LocalSearch RoTS (CL S );
BestAssignment = CL S ;
BestScore = Score(CL S );
repeat
CL' C = Pert urb RoTS (BestAssignment);
CL' S = LocalSearch RoTS (CL' C );
if Score(CL' S ) BestScore then

BestScore = Score(CL' S )
end if
BestAssignment = accept(BestAssignment,CL' S );
until two consecutive steps have not produced improvement
Return BestAssignment

iteration. There can be strong or weak perturbations which means that if the jump
in the search space is near to the current local optimum the subsidiary local search
procedure LocalSearch RoTS may fall again in the same local optimum and enter
regions with the same value of the objective function called plateau , but if the jump
is too far, LocalSearch RoTS may take too many steps to reach another good solution.
In our algorithm, we use a fixed number of RoTS steps 9n/10 with tabu tenure n/2
where n is the number of atoms (in future work, we intend to dynamically adapt the
nature of the perturbation). Regarding the procedure LocalSearch RoTS , it performs
RoTS steps until no improvement is achieved for n 2 =4 steps with a tabu tenure
n=10 C 4.The accept function always accepts the best solution found so far. The
difference between our algorithm and that in [ 26 ] is that we do not dynamically
adapt the tabu tenure and do not use a probabilistic choice in accept .

4.5.3 MAP Inference Using IRoTS

MAP inference in MNs means finding the most likely state of a set of output
variables given the state of the input variables. This problem is NP-hard. For
discriminative training, the voted perceptron is a special case in which tractable in-
ference is possible using the Viterbi algorithm [ 4 ]. In [ 25 ], the voted perceptron was
generalized to MLNs by replacing the Viterbi algorithm with a weighted SAT solver.
This algorithm is gradient descent, and computing the gradient of the conditional
log-likelihood (CLL) requires the computation of the number of true groundings for
each clause. This can be performed by finding the MAP state which can be com-
puted by dynamic programming methods. Since for MLNs, the MAP state is the
state that maximizes the sum of the weights of the satisfied ground clauses, this
state can be efficiently found using a weighted MAX-SAT solver. The authors in
[ 25 ] use the MaxWalkSat solver [ 24 ]. In this chapter, we propose to use IRoTS as a
MAX-SAT solver and show how this algorithm can be applied not only to MLNs but