Sample the most probable alignments from the entire alignment space

First, determine the best alignment according to IBM Model 2. With this initial alignment, use hill climbing to determine the best alignment according to a higher IBM Model. Add this alignment and its neighbors to the sample set. Repeat this process with other initial alignments obtained by pegging an alignment point.

Hill climbing may be stuck in a local maxima, hence the pegging and trying out of different alignments.

Parameters:sentence_pair (AlignedSent) – Source and target language sentence pair to generate a sample of alignments from
Returns:A set of best alignments represented by their AlignmentInfo and the best alignment of the set for convenience
Return type:set(AlignmentInfo), AlignmentInfo