Hidden Markov Model training using the Baum-Welch Algorithm

The Baum-Welch algorithm determines the (locally) optimal parameters for a Hidden Markov Model by essentially using three equations.

One for the initial probabilities:

\begin{align}
\pi_i &= \frac{E\left(\text{Number of times a sequence started with state}\, s_i\right)}{E\left(\text{Number of times a sequence started with any state}\right)}
\end{align}

Another for the transition probabilities:

\begin{align}
a_{ij} &= \frac{E\left(\text{Number of times the state changed from}\, s_i \, \text{to}\,s_j\right)}{E\left(\text{Number of times the state changed from}\, s_i \, \text{to any state}\right)}
\end{align}

And the last one for the emission probabilities:

\begin{align}
b_{ik} &= \frac{E\left(\text{Number of times the state was}\, s_i \, \text{and the observation was}\,v_k\right)}{E\left(\text{Number of times the state was}\, s_i\right)}
\end{align}

If one had a fully labeled training corpus representing all possible outcomes, this would be exactly the optimal solution: Count each occurrence, normalize and you’re good. If, however, no such labeled training corpus is available — i.e. only observations are given, no according state sequences — the expected values $E(c)$ of these counts would have to be estimated. This can be done (and is done) using the forward and backward probabilities $\alpha_t(i)$ and $\beta_t(i)$ , as described below.

Hidden Markov Models

Given a Hidden Markov Model $\lambda$ as $\lambda = \left\{\mathcal{S}; \mathcal{V}; \underline{A}; \underline{B}; \vec{\pi}\right\}$ with

\begin{align} \mathcal{S} &= \left\{s_1; s_2; \cdots ; s_N\right\} \end{align}	The alphabet of all $N$ possible states, i.e. values of the random variable $X_t$
\begin{align} \mathcal{V} &= \left\{v_1; v_2; \cdots ; v_M\right\} \end{align}	The alphabet of all $M$ possible observations, i.e. emissions of the random variable $Y_t$
\begin{align} \underline{A} &\in \mathbb{R}^{N \times N} \end{align}	The state transition matrix with $a_{ij}$ being the probability of moving from state $s_i$ to $s_j$
\begin{align} \underline{B} &\in \mathbb{R}^{N \times M} \end{align}	The observation matrix with $b_{ij} = b_i(v_j)$ being the probability of emitting the observation $v_j$ when in state $s_i$
\begin{align} \vec{\pi} &\in \mathbb{R}^{n} \end{align}	The initial distribution with $pi_i = P(X_1 = s_i)$ , i.e. the probability that the 1st state is $s_i$

A HMM with three states s₁…s_N and four observations v₁…v_M

then given the graph in the image above and assuming that the probability of staying in a state $s_i$ at time $t$ is simply $P(X_t = s_i | X_{t-1} = s_i) = 1-\left(\sum_{j=1}^n{a_{ij}} \quad \forall j \neq i\right)$ (otherwise the sum of probabilities of leaving $s_3$ would never be 1, as there is no edge in the graph leaving $s_3$ — this is a problem with the image though), i.e.

\begin{align}
a_{11} &= 1-(a_{12}) \\
a_{22} &= 1-(a_{21} + a_{23}) \\
a_{33} &= 1
\end{align}

then the matrices $\underline{A}$ and $\underline{B}$ would look as follows;

\begin{align}
\underline{A} &= \begin{bmatrix}
a_{11} & a_{12} & 0 \\
a_{21} & a_{22} & a_{23} \\
0 & 0 & a_{33}
\end{bmatrix} \\
\underline{B} &= \begin{bmatrix}
b_{11} & b_{12} & b_{13} & b_{14} \\
b_{21} & b_{22} & b_{23} & b_{24} \\
b_{31} & b_{32} & b_{33} & b_{34} %\\
%b_{41} & b_{42} & b_{43} & b_{44}
\end{bmatrix}
\end{align}

The $\vec{\pi}$ vector isn’t given so one might assume an equal distribution, i.e. $\pi_i = \frac{1}{n} \quad \forall s_i \in \mathcal{S}$ , such that

\begin{align}
\vec{\pi} &= \begin{bmatrix}
1/3 \\
1/3 \\
1/3
\end{bmatrix}
\end{align}

so that there is (or would be) an equal probability to start in any of the possible states.

Initial, transition and emission probabilities

Given the model $\lambda$ , here are some probabilities to get us started. But first, some notations:

$ P(X_t = s_i) $	The probability of the state at time $t$ being $s_i$
$ P(X_t = s_j \| X_{t-1} = s_i) $	The conditional probability of the state at time $t$ being $s_j$ given that the state at time $t-1$ was $s_i$
$ P(X_t = s_i, Y_{t} = v_j) $	The probability of the state at time $t$ being $s_i$ while seing an observation that is $v_j$

The probability that the model starts (i.e. $t=1$ ) in a given state $s_i$ is simply:

\begin{align}
P(X_1 = s_i) &= \pi_i
\end{align}

Also, the (conditional) probability that the model emits an observation $v_j$ given that it is in a state $s_i$ at time $t$ is:

\begin{align}
P(Y_t = v_j | X_t = s_i) &= b_{ij}
\end{align}

The probability that the model starts in a given state $s_i$ while emitting the observation $v_j$ then is:

\begin{align}
P(X_1 = s_i, Y_1 = v_j) &= P(X_1 = s_i) \cdot P(Y_1 = v_j | X_1 = s_i) \\
&= \pi_i \cdot b_{ij}
\end{align}

This is because the emission of an observation and the selection of a state are conditionally independent.

By definition, the (conditional) probability of moving from a state $s_i$ at time $t$ to $s_j$ at time $t+1$ is the probability of being at state $s_j$ at time $t$ given the state $s_i$ at time $t-1$ , which simply is:

\begin{align}
P(X_{t} = s_j | X_{t-1} = s_i) &= P(X_{t+1} = s_j | X_{t} = s_i) = a_{ij}
\end{align}

Consequently, the conditional probability of moving from a state $s_i$ to $s_j$ while emitting the observation $v_k$ is then:

\begin{align}
P(X_t = s_j, Y_t = v_k| X_{t-1} = s_i) &= P(X_{t} = s_j | X_{t-1} = s_i) \cdot P(Y_t = v_k | X_t = s_j) \\
&= a_{ij} \cdot b_{jk}
\end{align}

Finally, the conditional probability of starting in state $s_i$ while emitting the observation $v_k$ , then transitioning to state $s_j$ while emitting the observation $v_l$ is

\begin{align}
P(X_2 = s_j, Y_2 = v_l | X_1 = s_i, Y_1 = v_k) &= P(X_1 = s_i, Y_1 = v_k) \cdot P(X_2 = s_j, Y_2 = v_l | X_1 = s_i) \\
&= \pi_i \cdot b_{ik} \cdot a_{ij} \cdot b_{jl}
\end{align}

To make things a bit easier later on, we define $b_j(Y_t)$ as a function of the emission matrix $\underline{B}$ such that

\begin{align}
b_i(Y_t = v_j) &= P(Y_t = v_j, X_t = s_i) = b_{ij} \\
\Leftrightarrow Y_t &= v_j \,\implies \, b_i(Y_t) = P(Y_t, X_t = s_i) = b_{ij}
\end{align}

The forward probabilities

The forward probability $\alpha_t(i)$ describes the probability of a (partial) observation sequence $Y_1,Y_2, \cdots Y_t$ having been emitted while ending in state $s_i$ at time $t$ , i.e.

\begin{align}
\alpha_t(i) &= P(Y_1, Y_2, \cdots, Y_t, X_t = s_i)
\end{align}

It can be seen intuitively that $\alpha_1(i)$ is nothing but the probability of starting (i.e. at time $t=1$ ) with a state $s_i$ while emitting a specific $Y \in \mathcal{V}$.

\begin{align}
\alpha_1(i) &= P(Y_1, X_1 = s_i) = \pi_i \cdot b_{i}(Y_1), \qquad 1 \leq i \leq N
\end{align}

Let’s assume the graph depicted in the image above implicitly contains the probabilities to stay in each node, i.e. $P(X_t = s_i | X_{t-1} = s_i) > 0 \, \forall s_i \in \mathcal{S}$ (which is missing in the image as there are no such edges).
Let’s also assume that we have seen the observation sequence $Y_{1\cdots2} = \left\{v_3, v_1\right\}$ at times $t=1\cdots 2$ (i.e. $T=2$ ) and that we are interested in the probability of being in state $s_1$ after that observation.

Now there are multiple ways to reach state $s_1$ at time $t=2$ (note that there is no edge between $s_3$ and $s_1$ ):

$X_1 \to X_2$	$P(X_2\|X_1)$	$P(X_2, Y_2 \| X_1, Y_1)$
$s_1 \to s_1$	$a_{11}$	$\pi_{1} \cdot b_1(v_3) \cdot a_{11} \cdot b_1(v_1)$
$s_2 \to s_1$	$a_{21}$	$\pi_{2} \cdot b_2(v_3) \cdot a_{21} \cdot b_1(v_1)$
$s_3 \to s_1$	$a_{31}$ = 0	$\pi_{3} \cdot b_3(v_3) \cdot a_{31} \cdot b_1(v_1) = 0$

Now the total probability of reaching $s_1$ while seing the emission $v_1$ is the sum over all these path probabilities, which is $\alpha_{t = 2}(i = 1)$ :