1. A computer-implemented system for inferring structured variables, comprising: a priority function comprising a probable approximate underestimate to compute a probable approximate solution to an inference problem; and, a classification function, based on a semi-Markov conditional random field model, which assigns a score to a plurality of hypothetical structured variables, and through inferencing, searches for a best scoring hypothesis where the search is guided by the probable approximate underestimate of the priority function, to provide a structured output of unlabeled data based on classification information computed by the classification function.