Semi-Markov Canditional Random Fields for Information Extraction

by Sunita Sarawagi and William W. Cohen

This paper modifies the CRF structure with semi-Markov property, which allow the Markov chain to go in to a state Markovian does not hold (the state persists in this period). This is useful for finding a site, e.g. NER (named entity recognition). I guess it might also be useful in bioinformatics.

Their basic strategy is extending the label y in the feature function into a pair, not only y but also the starting and ending position (under certain constraints). Then we try to get the learning/inference algorithms in the new settings.

The search range of the inference increase (but still a polynomial time algorithm) due to the segmentation search. The learning algorithm does not change too much though.