Welcome to week 5 of FNLP. This week we will continue to study POS tagging. We will study how hidden Markov models (HMMs) can be used model POS tagging. We will also discuss how, in principle, HMMs can be applied to virtually any problem which can be framed as sequence labeling (though with variable success). We will discuss the assumptions underlying HMMs and seeing how sensible they for the problem in question. We will then see how HMMs can be estimated from data. We will present an algorithm for predicting the most likely sequence of tags (Viterbi algorithm for HMM), computing the probability of observations/word sequence (Forward algorithm) and also sketch the estimation procedure for the unsupervised setting (Forward-Backward algorithm, an instance of EM).
We'll then progress from POS tagging to sentential parsing. Parsing is the process of mapping a sentence to a representation of its syntactic form. We will start with how you decide whether a sequence of words group together into a syntactic constituent. We'll show how you can account for an unbounded number of well-formed NL sentences using a finite number of rules, in particular we'll present context-free grammars. We then will discuss a parsing algorithm that, given a sequence of words and a context-free grammar, determines whether that string is grammatical, and also determines its syntactic representation(s).
The number of representations is plural because of syntactic ambiguity. In week 6, we will continue to study syntactic parsing, and in particular we will discuss how to use labelled data to resolve syntactic ambiguities.
The content in the following pages is structured as follows:
13: PoS tagging / HMMs
14: Context-free Grammars (CFGs)
15: CKY Parsing
Each of the above includes the slides, required readings, and a post-lecture quiz. The quiz is a chance for you to gauge your understanding of the material presented here, and so we strongly encourage you to review this content and then complete the quiz. If there is anything you don't understand, then you have several options:
- Post a question on piazza;
- Ask a question at the in person lectures; and/or
- Ask your tutor.