• Describe, with an example, a Markov chain. What would you need to add to your Markov chain in order to have a Hidden Markov model?

    Solution: A Markov chain is an edge-labelled directed graph, where each node represents a "state", e.g. a lexical category, and the edge-labels are probabilities of moving the state at the end of the directed arc.

    Markov chain diagram

    To convert our example into a Hidden Markov Model (HMM), we would need to add to each node a table of output probabilities, in this case lexical generation probabilities - e.g. if one is in state N, what are the probabilities of producing each possible noun when in this state.