- This problem can be solved with a HMM.
- Using a HMM involves finding the transition probabilities (what is the probability of going from one POS tag to another and emission/output probabilities (what is the probability of observing a word given a POS tag) as explained in the question How do you train an hMM.
- Once hMM is trained using a large enough corpus, then use the Viterbi algorithm to find the most probable sequence of tags.
Interview Tip: Note that one might be in hurry to answer Viterbi algorithm. It is true that Viterbi algorithm is used, but we don’t start with Viterbi rather first train a HMM model and then apply the Viterbi algorithm with the learnt transition and emission matrices to answer the question of finding the POS tags.