Discriminative Hidden Markov Modeling with Long State Dependence using a kNN Ensemble

Discriminative Hidden Markov Modeling with Long State Dependence using a kNN Ensemble ZHOU GuoDong Institute for Infocomm Research 21 Heng Mui Keng Terrace Singapore 119613 Email: zhougd@i2r.a-star.edu.sg Abstract This paper proposes a discriminative HMM (DHMM) with long state dependence (LSD- DHMM) to segment and label sequential data. The LSD-DHMM overcomes the strong context independent assumption in traditional generative HMMs (GHMMs) and models the sequential data in a discriminative way, by assuming a novel mutual information independence. As a result, the LSD-DHMM separately models the long state dependence in its state transition model and the observation dependence in its output model. In this paper, a variable-length mutual information- based modeling approach and an ensemble of kNN probability estimators are proposed to capture the long state dependence and the observation dependence respectively. The evaluation on shallow parsing shows that the LSD-DHMM not only significantly outperforms GHMMs but also much outperforms other DHMMs. This suggests that the LSD-DHMM can effectively capture the long context dependence to segment and label sequential data. 1. Introduction A Hidden Markov Model (HMM) is a model where a sequence of observations is generated in addition to the Markov state sequence. It is a latent variable model in the sense that only the observation sequence is known while the state sequence remains “hidden”. In recent years, HMMs have enjoyed great success in many tagging applications, most notably part-of-speech (POS) tagging (Church 1988; Weischedel et al 1993; Merialdo 1994) and named entity recognition (Bikel et al 1999; Zhou et al 2002). Moreover, there have been also efforts to extend the use of HMMs to word sense disambiguation (Segond et al 1997) and shallow/full parsing (Brants et al 1997; Skut et al 1998; Zhou et al 2000). Traditionally, a HMM segments and labels sequential data in a generative way, assigning a joint probability to paired observation and state sequences. More formally, a generative (first-order) HMM (GHMM) is given by a finite set of states including an designated initial state and an designated final state, a set of possible observation , two conditional probability distributions: a state transition model from s to , for and an output model, for S O s ,' o ' s ) (| 's ps (|) pos s ∈S Os ∈S ∈ , ) | 's s . A sequence of observations is generated by starting from the designated initial state, transmiting to a new state according to , emitting an observation selected by that new state according to p , transmiting to another new state and so on until the designated final state is generated. ( p ) ( |s o There are several problems with this generative approach. First, many tasks would benefit from a richer representation of observations—in particular a representation that describes observations in terms of many overlapping features, such as capitalization, word endings, part-of-speech in addition to the traditional word identity. Note that these features always depends on each other. Furthermore, to define a joint probability over the observation and state sequences, …

Content truncated to 500 words