learn.ifs.name

Sequence Labeling for Parts of Speech and Named Entities

Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft, ch. 18

14 cards in “18.4 HMM part-of-speech tagging” · whole deck

18.4 HMM part-of-speech tagging

  1. What is a Markov chain, and what assumption does it make?
    A model of the probabilities of sequences of states, assuming that to predict the next state only the current state matters: \(P(q_i \mid q_1 \ldots q_{i-1}) = P(q_i \mid q_{i-1})\).
  2. What are the components of a Markov chain?
    A set of states \(Q\), a transition matrix \(A\) with \(a_{ij}\) = probability of moving from state \(i\) to state \(j\) (rows sum to 1), and an initial distribution \(\pi\) over states.
  3. What well-known model is a Markov chain over words?
    A bigram language model: each transition is \(p(w_i \mid w_j)\).
  4. Why do we need a hidden Markov model for POS tagging?
    We observe words, not tags; the tags are hidden events we treat as causal factors, which the HMM relates to the observed words.
  5. What are the components of an HMM?
    States \(Q\), transition probabilities \(A\), emission (observation likelihood) probabilities \(B = b_i(o_t)\) for each observation given each state, and an initial distribution \(\pi\).
  6. What two simplifying assumptions does a first-order HMM make?
    The Markov assumption (a state depends only on the previous state) and output independence (an observation depends only on the state that produced it).
  7. How are HMM tagger transition and emission probabilities estimated?
    By counting on a tagged corpus: \(P(t_i \mid t_{i-1}) = \frac{C(t_{i-1}, t_i)}{C(t_{i-1})}\) and \(P(w_i \mid t_i) = \frac{C(t_i, w_i)}{C(t_i)}\).
  8. What question does the emission probability \(P(\text{will} \mid \text{MD})\) answer?
    Not “which tag is most likely for will?” (that is \(P(\text{MD} \mid \text{will})\)), but “if we generate a modal, how likely is it to be will?”
    MDVBNNP(VB|MD)will .31, can…back, race…bill, back…dashed: emissions P(word | tag)
  9. What is decoding for an HMM?
    Given the HMM \(\lambda = (A, B)\) and an observation sequence, find the most probable sequence of hidden states.
  10. Derive the HMM tagging objective.
    \(\hat{t}_{1:n} = \arg\max P(t_{1:n} \mid w_{1:n}) = \arg\max P(w_{1:n} \mid t_{1:n})P(t_{1:n})\) (Bayes, dropping the denominator) \(\approx \arg\max\prod_i P(w_i \mid t_i)\,P(t_i \mid t_{i-1})\): emission × transition.
  11. What does a cell \(v_t(j)\) of the Viterbi lattice represent?
    The probability that the HMM is in state \(j\) after the first \(t\) observations, having followed the most probable state sequence to get there: \(\max_{q_{1:t-1}} P(q_{1:t-1}, o_{1:t}, q_t = j \mid \lambda)\).
  12. Give the Viterbi recursion.
    \(v_t(j) = \max_{i=1}^{N} v_{t-1}(i)\,a_{ij}\,b_j(o_t)\): previous path probability × transition probability × observation likelihood, keeping a backpointer to the best \(i\).
  13. How does the Viterbi algorithm work overall?
    Initialize \(v_1(s) = \pi_s b_s(o_1)\); fill the lattice column by column with the recursion and backpointers; at the end take the best final cell and follow backpointers to recover the best path. It is dynamic programming, like minimum edit distance.
    NNPMDVBDTNNJanetwillbackthebill
    One column per word, one row per tag; the best path is NNP MD VB DT NN.
  14. In tagging “Janet will back the bill” with an HMM, why are most cells in the first column zero?
    Janet only ever appears as NNP in training, so the emission probability \(P(\text{Janet} \mid t)\) is 0 for every other tag.

Source