A weakness of HMMs themselves is that the Markov assumption (independence of non-neighbors, given the neighbors) is violated by longer-range dependencies in text. For example, in the context of a relative clause (signaled by a noun preceding that clause), a transitive verb may well lack an NP complement ( “I collected the money he threw down on the table.”), and as a result, words following the verb may be tagged incorrectly (down as a noun).  A discriminative approach that overcomes this difficulty is the use of conditional random fields (CRFs). Like HMMs (which they subsume), these allow for local interdependence of hidden states, but employ features that depend not only on adjacent pairs of these states, but also on any desired properties of the entire input. Mathematically, the method is very similar to MaxEnt (as discussed above). The feature coefficients can be learned from training data either by gradient ascent or by an incremental dynamic programming method related to the Baum-Welch algorithm, called improved iterative scaling (IIS) (Della Pietra et al. 1997; Lafferty et al. 2001).  CRFs have been successful in many applications other than POS tagging, such as sentence and word boundary detection (e.g., for Chinese), WSD, extracting tables from text, named entity recognition, and—outside of NLP—in gene prediction and computer vision.