ConceptDBISAI-written · not yet proofread

Hidden Markov Model

Also HMM

A probabilistic model of a sequence in which hidden states form a Markov chain (each state depends only on its predecessor) and each hidden state emits one observable, given by initial, transition and emission probabilities.

Know these firstConditional Probability Statistical Independence N-Gram Model

Definition

A Hidden Markov Model (HMM) consists of a finite set $H$ of hidden states, a finite set $O$ of observables, and

initial probabilities $\Pr(h)$ for $h \in H$ (state of the first position),
transition probabilities $\Pr(h' \mid h)$ for $h, h' \in H$ (next hidden state given the current one),
emission probabilities $\Pr(o \mid h)$ for $h \in H$ , $o \in O$ (observable given the hidden state),

each of them a probability distribution. For hidden states $h_1, \dots, h_n$ and observations $o_1, \dots, o_n$ , the likelihood is

\Pr(h_1, \dots, h_n, o_1, \dots, o_n) = \Pr(h_1)\,\Pr(o_1 \mid h_1) \cdot \prod_{i=2}^{n} \Pr(h_i \mid h_{i-1})\,\Pr(o_i \mid h_i).

Formula#

The factorization follows from two independence assumptions (Conditional Probability, Statistical Independence):

Markov property: $h_i$ depends only on $h_{i-1}$ , not on earlier states or observations. The hidden states form a bigram model (N-Gram Model with $n = 2$ ) over $H$ .
Output independence: $o_i$ depends only on $h_i$ .

With an END state. For POS-Tagging a special hidden state END is appended after the last position, with learned transition probabilities $\Pr(\text{END} \mid h)$ . The likelihood gets the extra factor $\Pr(\text{END} \mid h_n)$ , which encodes which states are likely at the end of a sequence (exam WS 19/20, Task 5.4).

Decoding. Given $o_1, \dots, o_n$ , the most likely hidden sequence is

\arg\max_{h_1, \dots, h_n} \Pr(h_1, \dots, h_n, o_1, \dots, o_n),

which the Viterbi Algorithm computes in $O(n \cdot |H|^2)$ instead of trying all $|H|^n$ sequences. Maximizing the joint probability is the same as maximizing $\Pr(h_1, \dots, h_n \mid o_1, \dots, o_n)$ , because $\Pr(o_1, \dots, o_n)$ does not depend on the $h_i$ .

Training for POS tagging on a tagged corpus by relative frequencies: $\Pr(t' \mid t) = \#(t\,t') / \#(t)$ (tag $t'$ follows tag $t$ ), $\Pr(w \mid t) = \#(w \text{ tagged } t) / \#(t)$ , $\Pr(t) =$ fraction of sentences that start with $t$ .

Properties#

Posterior of a single state. $\Pr(h_i = h \mid o_1, \dots, o_n) = \sum_{\text{sequences with } h_i = h} \Pr(h, o) \,/\, \sum_{\text{all sequences}} \Pr(h, o)$ . For short sequences this is a direct sum over all $|H|^n$ hidden sequences (exam WS 17/18, Task 6.1).
Zero probabilities are decisive. If an observable can only be emitted by one state (emission probability $0$ for all others), every positive-probability sequence must use that state at that position. This can determine the most likely sequence without any computation (exam WS 17/18, Task 6.2).
Brute force over all $|H|^n$ sequences with the likelihood formula is correct but exponential in $n$ (exam WS 17/18, Task 6.4).

Example#

ExampleSentiment HMM (exam WS 17/18, Task 6)

$H = \{\text{plus}, \text{minus}\}$ , $O = \{\text{good}, \text{great}, \text{bad}\}$ , no END state.

	initial	$\to$ plus	$\to$ minus	good	great	bad
plus	$1/2$	$1/3$	$2/3$	$1/3$	$2/3$	$0$
minus	$1/2$	$2/3$	$1/3$	$2/3$	$0$	$1/3$

Likelihood of (plus, minus, plus) for “great bad great”:

\tfrac12 \cdot \tfrac23 \;\cdot\; \tfrac23 \cdot \tfrac13 \;\cdot\; \tfrac23 \cdot \tfrac23 = \tfrac{8}{243}.

great is only emitted by plus and bad only by minus, so this is the only sequence with positive probability, hence the most likely one.

Sources#

Not covered by a WS 25/26 lecture. Source: the former Information Retrieval exams.
Exam WS 17/18, Task 6 (not published) (posterior, decoding by argument, likelihood, brute force)
Exam WS 18/19, Task 6.3 (not published) (weather/mood HMM, greedy vs. Viterbi)
Exam WS 19/20, Task 5.4 (not published) (END tag)

Connections

Required by builds on this1

Viterbi Algorithm

Mentioned in inline links2

Viterbi Algorithm
Given a Hidden Markov Model with hidden states $H$ and observations $o_1, \dots, o_n$ , let $\delta_i(h)$ be the maximal likelihood of any hidden sequence $h_1, \dots, h_i$ with $h_i = h$ for the first $i$ observations. The Viterbi algorith… §
Parameters as in Hidden Markov Model (initial $1/2$ each; transitions plus→plus $1/3$ , plus→minus $2/3$ , minus→plus $2/3$ , minus→minus $1/3$ ; $\Pr(\text{good} \mid \text{plus}) = 1/3$ , $\Pr(\text{good} \mid \text{minus}) = 2/3$ ). §
POS-Tagging
Hidden Markov Model — initial, transition and emission probabilities; likelihood of a state/observation sequence; END tag §

Search in these mentions →