1、Tagging with Hidden Markov Models,CMPT 882 Final Project Chris Demwell Simon Fraser University,The Tagging Task,Identification of the part of speech of each word of a corpusSupervised: Training corpus provided consisting of correctly tagged textUnsupervised: Uses only plain text,Hidden Markov Models
2、 1,Observable states (corpus text) generated by hidden states (tags) Generative model,Hidden Markov Models 2,Model: = A, B, A: State transition probability matrix ai,j = probability of changing from state i to state j B: Emission probability matrix bj,k = probability that word at location k is assoc
3、iated with tag j : Intial state probability i = probability of starting in state i,Hidden Markov Models 3,Terms in this presentationN: Number of hidden states in each column (distinct tags) T: Number of columns in trellis (time ticks) M: Number of symbols (distinct words) O: The observation (the unt
4、agged text) bj(t): The probability of emitting the symbol found at tick t, given state j t,j and t,j : The probability of arriving at state i in time tick t, given the observation before and after tick t (respectively),Hidden Markov Models 4,A is a NxN matrix B is a NxT matrix is a vector of size N,
5、1,2,a1,1,a1,2,b1,1,b1,2,Forward Algorithm,Used for calculating Likelihood quickly t,i: The probability of arriving at trellis node (t,j) given the observation seen “so far”. Initialization 1,i = i Induction,2,2,1,1,1,2,1,3,Backward Algorithm,Symmetrical to Forward Algorithm Initialization T,i =1 for
6、 all I Induction:,1,2,2,1,2,2,2,3,Baum-Welch Re-estimation,Calculate two new matrices of intermediate probabilities , Calculate new A, B, given these probabilities Recalculate and , p(O | ) Repeat until p(O | ) doesnt change much,HMM Tagging 1,Training Method Supervised Relative Frequency Relative F
7、requency with further Maximum Likelihood training Unsupervised Maximum Likelihood training with random start,HMM Tagging 2,Read corpus, take counts and make translation tables Train HMM using BW or compute HMM using RF Compute most likely hidden state sequence Determine POS role that each state most
8、 likely plays,HMM Tagging: Pitfalls 1,Monolithic HMM Relatively opaque to debugging strategies Difficult to modularize Significant time/space efficiency concerns Varied techniques for prior implementations Numerical Stability Very small probabilities likely to underflow Log likelihood Text Chunking
9、Sentences? Fixed? Stream?,HMM Tagging: Pitfalls 2,State role identification Lexicon giving p(tag | word) from supervised corpus Unseen words Equally likely tags for multiple states Local maxima HMM not guaranteed to converge on correct model Initial conditions Random Trained Degenerate,HMM Tagging:
10、Prior Work 1,Cutting et al. Elaborate reduction of complexity (ambiguity classes) Integration of bias for tuning (lexicon choice, initial FB values) Fixed-size text chunks, model averaging between chunks for final model 500,000 words of Brown corpus: 96% accurate after eight iterations,HMM Tagging:
11、Prior Work 2,Merialdo Contrasted computed (Relative Frequency) vs trained (BWRE) models Constrained training Keep p(tag | word) constant from bootstrap corpus RF Keep p(tag) constant from bootstrap corpus RF Constraints allow degradation, but more slowly Constraints required extensive calculation,Co
12、nstraints and HMM Tagging 1,Elworthy: Accuracy of classic trained HMM always decreases after some point,From Elworthy, “Does Baum-Welch Re-Estimation Help Taggers?”,Constraints and HMM Tagging 2,Tagging: An excellent candidate for a CSP Many degrees of freedom in nave case Linguistically, only some
13、few tagging solutions are possible HMM, like modern CSP techniques, does not make final choices in order Merialdos t and t-w constraints Expensive, but helpful,Constraints and HMM Tagging 3,Obvious places to incorporate constraints Updates to A, B, Deny an update to A if tag at (t+1) should not foll
14、ow tag at (t) Deny an update to B if we are confident that word at (t) should not be associated with tag at (t) Merialdos t and t-w constraints,Constraints and HMM Tagging 4,Obvious places to incorporate constraints Forward-Backward calculations Some tags are linguistically impossible sequentially D
15、eny transition probability,Constraints and HMM Tagging 5,Where to get constraints?Grammar databases (WordNet)Bootstrap corpus Use relative frequencies of tags to guess rules Use frequencies of words to estimate confidence Allow violations?,reMarker: Motivation,reMarker, an implementation in Java of
16、HMM taggingSupport for multiple modelsModular updates for constraint implementation,reMarker: The Reality,HMM component too time-consuming to debug Preliminary rule implementations based on corpus RF Using Tapas Kanugos HMM implementation in C, externally,reMarker: Method,Penn-Treebank Wall Street J
17、ournal part-of-speech tagged data Corpus handled as stream of words Restriciton of Kanugos HMM implementation Results in enormous resource requirements Results in degradation of accuracy with increase in training data size,reMarker: Experiment,Two corpora 200 words of PT WSJ Section 00 5000 words of
18、 PT WSJ Section 00 Three training methods Relative Frequency, computed Supervised, but with BWRE Unsupervised BWRE,reMarker: Results,Future Work,Fix the reMarker HMM Allow corpus chunking Allow more complicated constraints Incorporate tighter constraints Merialdos t and t-w Possible POS for each wor
19、d: WordNet Machine-learned rules,References,A Tutorial on Hidden Markov Models. Rakesh Dugad and U. B. Desai. Technical Report, Signal Processing and Artificial Neural Networks Laboratory, Indian Institute of Technology, SPANN-96.1. Does Baum-Welch Re-estimation help taggers? (1994). David Elworthy.
20、 Proceedings of 4th ACL Conf on ANLP, Stuttgart. pp. 53-58. A Practical Part-of-Speech Tagger (1992). Doug Cutting, Julian Kupiec, Jan Pedersen and Penelope Sibun. In Proceedings of ANLP-92. Tagging text with a probabilistic model (1994). Bernard Merialdo. Computational Linguistics 20(2):155-172. A Gentle Tutorial on the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models (1997). Jeff A. Bilmes, Technical Report, University of Berkeley, ICSI-TR-97-021.,
