 # hidden Markov model

(data structure)

Definition: A variant of a finite state machine having a set of states, Q, an output alphabet, O, transition probabilities, A, output probabilities, B, and initial state probabilities, Π. The current state is not observable. Instead, each state produces an output with a certain probability (B). Usually the states, Q, and outputs, O, are understood, so an HMM is said to be a triple, (A, B, Π).

Formal Definition: After Michael Cohen's lectures for CN760.

• A = {aij = P(qj at t+1 | qi at t)}, where P(a | b) is the conditional probability of a given b, t ≥ 1 is time, and qi ∈ Q.
Informally, A is the probability that the next state is qj given that the current state is qi.
• B = {bik = P(ok | qi)}, where ok ∈ O.
Informally, B is the probability that the output is ok given that the current state is qi.
• Π = {pi = P(qi at t=1)}.

Also known as HMM.

Generalization (I am a kind of ...)
finite state machine.

Aggregate parent (I am a part of or used in ...)
Baum Welch algorithm, Viterbi algorithm.

Note: Computing a model given sets of sequences of observed outputs is very difficult, since the states are not directly observable and transitions are probabilistic. One method is the Baum Welch algorithm.

Although the states cannot, by definition, be directly observed, the most likely sequence of sets for a given sequence of observed outputs can be computed in O(nt), where n is the number of states and t is the length of the sequence. One method is the Viterbi algorithm.

Thanks to Arvind <uk_arvind@mail.utexas.edu> May 2002.

Named after Andrei Andreyevich Markov (1856 - 1922), who studied poetry and other texts as stochastic sequences of characters.

Author: PEB