Spectral Learning of Refinement HMMs

Proceedings of the Seventeenth Conference on Computational Natural Language Learning, pages 56–64, Sofia, Bulgaria, August 8-9 2013. c⃝2013 Association for Computational Linguistics Spectral Learning of Refinement HMMs Karl Stratos1 Alexander M. Rush2 Shay B. Cohen1 Michael Collins1 1Department of Computer Science, Columbia University, New-York, NY 10027, USA 2MIT CSAIL, Cambridge, MA, 02139, USA {stratos,scohen,mcollins}@cs.columbia.edu, srush@csail.mit.edu Abstract We derive a spectral algorithm for learn- ing the parameters of a refinement HMM. This method is simple, efficient, and can be applied to a wide range of supervised sequence labeling tasks. Like other spec- tral methods, it avoids the problem of lo- cal optima and provides a consistent esti- mate of the parameters. Our experiments on a phoneme recognition task show that when equipped with informative feature functions, it performs significantly better than a supervised HMM and competitively with EM. 1 Introduction Consider the task of supervised sequence label- ing. We are given a training set where the j’th training example consists of a sequence of ob- servations x(j) 1 ...x(j) N paired with a sequence of labels a(j) 1 ...a(j) N and asked to predict the cor- rect labels on a test set of observations. common approach is to learn a joint distribu-A tion over sequences p(a1 . . . aN, x1 . . . xN) as a hidden Markov model (HMM). The downside of HMMs is that they assume each label ai is inde- pendent of labels before the previous label ai−1. This independence assumption can be limiting, particularly when the label space is small. To re- lax this assumption we can refine each label ai with a hidden state hi, which is not observed in the training data, and model the joint distribu- tion p(a1 . . . aN, x1 . . . xN, h1 . . . hN). This re- finement HMM (R-HMM), illustrated in figure 1, is able to propagate information forward through the hidden state as well as the label. Unfortunately, estimating the parameters of an R-HMM is complicated by the unobserved hid- den variables. A standard approach is to use the expectation-maximization (EM) algorithm which a1, h1 a2, h2 aN, hN x1 x2 xN (a) a1 a2 aN h1 h2 hN x1 x2 xN (b) Figure 1: (a) An R-HMM chain. (b) An equivalent representation where labels and hidden states are intertwined. has no guarantee of finding the global optimum of its objective function. The problem of local op- tima prevents EM from yielding statistically con- sistent parameter estimates: even with very large amounts of data, EM is not guaranteed to estimate parameters which are close to the “correct” model parameters. In this paper, we derive a spectral algorithm for learning the parameters of R-HMMs. Unlike EM, this technique is guaranteed to find the true param- eters of the underlying model under mild condi- tions on the singular values of the model. The al- gorithm we derive is simple and efficient, relying on singular value decomposition followed by stan- dard matrix operations. We also describe the …

Content truncated to 500 words