CS 388: Natural Language Processing: Part-Of-Speech Tagging, Sequence Labeling, and Hidden Markov Models (HMMs)Part Of Speech TaggingEnglish POS TagsetsEnglish Parts of SpeechEnglish Parts of Speech (cont.)Closed vs. Open ClassAmbiguity in POS TaggingPOS Tagging ProcessPOS Tagging ApproachesClassification LearningBeyond Classification LearningSequence Labeling ProblemInformation ExtractionSemantic Role LabelingBioinformaticsSequence Labeling as ClassificationSlide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Sequence Labeling as Classification Using Outputs as InputsForward ClassificationSlide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Backward ClassificationSlide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Problems with Sequence Labeling as ClassificationProbabilistic Sequence ModelsMarkov Model / Markov ChainSample Markov Model for POSSlide 57Hidden Markov ModelSample HMM for POSSample HMM GenerationSlide 61Slide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Formal Definition of an HMMHMM Generation ProcedureThree Useful HMM TasksHMM: Observation LikelihoodSequence ClassificationMost Likely SequenceHMM: Observation Likelihood Naïve SolutionHMM: Observation Likelihood Efficient SolutionForward ProbabilitiesForward StepForward TrellisComputing the Forward ProbabilitiesForward Computational ComplexityMost Likely State Sequence (Decoding)Most Likely State SequenceSlide 85Slide 86Slide 87Slide 88Slide 89HMM: Most Likely State Sequence Efficient SolutionViterbi ScoresComputing the Viterbi ScoresComputing the Viterbi BackpointersViterbi BackpointersViterbi BacktraceHMM LearningSupervised HMM TrainingSupervised Parameter EstimationLearning and Using HMM TaggersEvaluating TaggersUnsupervised Maximum Likelihood TrainingMaximum Likelihood TrainingBayes TheoremMaximum Likelihood vs. Maximum A Posteriori (MAP)HMM: Maximum Likelihood Training Efficient SolutionEM AlgorithmEMSlide 108Slide 109Slide 110Slide 111Sketch of Baum-Welch (EM) Algorithm for Training HMMsBackward ProbabilitiesComputing the Backward ProbabilitiesEstimating Probability of State TransitionsRe-estimating AEstimating Observation ProbabilitiesRe-estimating BPseudocode for Baum-Welch (EM) Algorithm for Training HMMsEM PropertiesSemi-Supervised LearningSemi-Supervised EMSlide 123Slide 124Slide 125Slide 126Semi-Supervised ResultsConclusions11CS 388: Natural Language Processing:Part-Of-Speech Tagging,Sequence Labeling, andHidden Markov Models (HMMs)Raymond J. MooneyUniversity of Texas at Austin2Part Of Speech Tagging•Annotate each word in a sentence with a part-of-speech marker.•Lowest level of syntactic analysis.•Useful for subsequent syntactic parsing and word sense disambiguation.John saw the saw and decided to take it to the table.NNP VBD DT NN CC VBD TO VB PRP IN DT NN3English POS Tagsets•Original Brown corpus used a large set of 87 POS tags.•Most common in NLP today is the Penn Treebank set of 45 tags.–Tagset used in these slides.–Reduced from the Brown set for use in the context of a parsed corpus (i.e. treebank).•The C5 tagset used for the British National Corpus (BNC) has 61 tags.4English Parts of Speech•Noun (person, place or thing)–Singular (NN): dog, fork–Plural (NNS): dogs, forks–Proper (NNP, NNPS): John, Springfields–Personal pronoun (PRP): I, you, he, she, it–Wh-pronoun (WP): who, what•Verb (actions and processes)–Base, infinitive (VB): eat–Past tense (VBD): ate–Gerund (VBG): eating–Past participle (VBN): eaten–Non 3rd person singular present tense (VBP): eat–3rd person singular present tense: (VBZ): eats–Modal (MD): should, can–To (TO): to (to eat)5English Parts of Speech (cont.)•Adjective (modify nouns)–Basic (JJ): red, tall–Comparative (JJR): redder, taller–Superlative (JJS): reddest, tallest•Adverb (modify verbs)–Basic (RB): quickly–Comparative (RBR): quicker–Superlative (RBS): quickest•Preposition (IN): on, in, by, to, with•Determiner:–Basic (DT) a, an, the–WH-determiner (WDT): which, that•Coordinating Conjunction (CC): and, but, or,•Particle (RP): off (took off), up (put up)Closed vs. Open Class •Closed class categories are composed of a small, fixed set of grammatical function words for a given language.–Pronouns, Prepositions, Modals, Determiners, Particles, Conjunctions•Open class categories have large number of words and new ones are easily invented.–Nouns (Googler, textlish), Verbs (Google), Adjectives (geeky), Abverb (chompingly) 67Ambiguity in POS Tagging•“Like” can be a verb or a preposition–I like/VBP candy.–Time flies like/IN an arrow.•“Around” can be a preposition, particle, or adverb–I bought it at the shop around/IN the corner.–I never got around/RP to getting a car.–A new Prius costs around/RB $25K.8POS Tagging Process•Usually assume a separate initial tokenization process that separates and/or disambiguates punctuation, including detecting sentence boundaries.•Degree of ambiguity in English (based on Brown corpus)–11.5% of word types are ambiguous.–40% of word tokens are ambiguous.•Average POS tagging disagreement amongst expert human judges for the Penn treebank was 3.5%–Based on correcting the output of an initial automated tagger, which was deemed to be more accurate than tagging from scratch.•Baseline: Picking the most frequent tag for each specific word type gives about 90% accuracy–93.7% if use model for unknown words for Penn Treebank tagset.9POS Tagging Approaches•Rule-Based: Human crafted rules based on lexical and other linguistic knowledge.•Learning-Based: Trained on human annotated corpora like the Penn Treebank.–Statistical models: Hidden Markov Model (HMM), Maximum Entropy Markov Model (MEMM), Conditional Random Field (CRF)–Rule learning: Transformation Based Learning (TBL)•Generally, learning-based approaches have been found to be more effective overall, taking into account the total amount of human expertise and effort involved.10Classification Learning•Typical machine learning addresses the problem of classifying a feature-vector description into a fixed number of classes.•There are many standard learning methods for this task:–Decision Trees and Rule Learning–Naïve Bayes and Bayesian Networks–Logistic Regression / Maximum Entropy (MaxEnt)–Perceptron and Neural