A Brief Introduction to HMM

---

Prerequisites/Assumptions of HMM

        +------+     +------+     +------+     +------+
Start-> | S₁   | --> | S₂   | --> | S₃   | --> | Sₙ   |
        +------+     +------+     +------+     +------+
           |             |             |             |
           v             v             v             v
        +------+     +------+     +------+     +------+
        | O₁   |     | O₂   |     | O₃   |     | Oₙ   |
        +------+     +------+     +------+     +------+

• Markov property: The state at time t depends only on the state at time t-1, and is independent of earlier states.
• Observation independence: The observation at time t depends only on the state at that time, and is independent of observations and states at any other time.

In HMM, once we have the dataset, we model their joint probability function:

$$\begin{aligned} P(O_1, O_2, ...,O_n, X_1, X_2, ..., X_n) &= P(X_1, O_1, X_2, O_2, ..., X_n, O_n) \\ &= P(X_1) * P(O_1 | X_1) * P(X_2 | X_1 O_1) * P(O_2|X_2X_1O_1) * ...\\ &=P(X_1) * P(O_1 | X_1) * P(X_2 | X_1) * P(O_2 | X_2) * ....P(X_n | X_{n - 1}) * P(O_n | X_n) \\ &=P(X_1) P(O_1 | X_1) \prod_{t = 2}^n P(X_t | X_{t - 1}) P(O_t | X_t) \end{aligned}$$

Therefore, the joint probability depends only on:

• $P(X_1)$: Initial state probability distribution, denoted as $\pi$
• $P(X_t | X_{t - 1})$: State transition probability matrix, denoted as $A$
• $P(O_t | X_t)$: The probability distribution of observations given a state, also called emission probability, denoted as $B$

All computations and predictions in HMM revolve around how to derive $\lambda = (\pi, A, B)$ from the dataset.

• Evaluation problem: Given $\lambda = (\pi, A, B)$ and an observation sequence $O_1, O_2, ... , O_n$, we need to compute the probability of this observation sequence occurring. The standard solution is the forward algorithm or the backward algorithm.
• Prediction problem: Given $\lambda = (\pi, A, B)$ and an observation sequence $O_1, O_2, ... , O_n$, predict the most likely state sequence. The standard solutions are the greedy algorithm or the Viterbi algorithm.
• Learning problem: The model parameters $\lambda = (\pi, A, B)$ are unknown and need to be learned or inferred. This falls into two scenarios:
  • Supervised learning with known observation sequences and state sequences: directly compute the $A$ matrix and $B$ matrix by statistical counting from the dataset.
  • Unsupervised learning where only observation sequences are known and the underlying states are unknown: this typically employs the EM algorithm.

On the Evaluation Problem:

$$\begin{aligned} P(O_1, O_2, ..., O_n) &= \sum_{all possible state sequences X} P(O, X) \\ &= \sum_{x_1, x_2, ..., x_n} P(o_1, o_2, ..., o_n, x_1, x_2, ..., x_n) \end{aligned}$$

Since the number of possible state sequences grows exponentially — if there are $T$ possible states, then there are $T^N$ possible state sequences — it is impossible to enumerate them all. Therefore, the forward algorithm based on dynamic programming is used instead. I haven't looked into the specific algorithm details.

On the Prediction Problem

$$\begin{aligned} MAX_{x_1, x_2, ..., x_n}P(x_1, x_2, ..., x_n) & = MAX(P(x_1)) * MAX(P(x_2)) * ... * MAX(P(x_n)) (greedy solution) \end{aligned}$$

We want to find a state sequence $x_1, x_2, ..., x_n$ that maximizes the probability. The greedy solution is to maximize the probability of each individual state, i.e., choose the state with the highest probability at each step.

I haven't looked into the Viterbi algorithm.

On the Learning Problem

Supervised Scenario

Since we already know the state behind each observation, the state transition matrix and emission matrix can be directly computed by counting:

• Divide the state sequence into pairs, and directly obtain the frequency of transitioning from one state to another, then normalize to probabilities.
• Directly count the number of times a state produces a certain observation to obtain the emission frequency, then normalize to emission probabilities.

Unsupervised Scenario

We can only see the observation sequences and do not know the underlying states. The goal is to learn the model parameters $\lambda = (\pi, A, B)$ such that $P(O | \lambda)$ is maximized.

This is done using the EM algorithm. However, the E-step of the EM algorithm used in HMM is a bit unusual, and I haven't been able to resolve it for now.