Sequential Data and Markov Models

Most machine learning algorithms assume that data points are independent and identically distributed (i.i.d.). However, in many real-world scenarios—like speech recognition, stock prices, or DNA sequencing—the order of the data matters.

1. The Markov Property

A sequence of random variables $S_1, S_2, \dots, S_T$ satisfies the First-Order Markov Property if the probability of the next state depends only on the current state:

This drastically simplifies the modeling of sequential data, as we only need to specify a Transition Matrix $A$, where $A_{ij} = p(S_t = j \mid S_{t-1} = i)$.

2. Hidden Markov Models (HMM)

In many cases, the state we are interested in is hidden (latent), and we only see noisy observations generated by that state.

An HMM is defined by:

1. Hidden States: $z_1, z_2, \dots, z_T$
2. Observations: $x_1, x_2, \dots, x_T$
3. Transition Probabilities: $p(z_t \mid z_{t-1})$
4. Emission Probabilities: $p(x_t \mid z_t)$

3. The Three Fundamental Problems for HMMs

1. Evaluation: Given the model, how likely is a certain sequence of observations? (Solved by the Forward Algorithm).
2. Decoding: Given the observations, what is the most likely sequence of hidden states? (Solved by the Viterbi Algorithm).
3. Learning: Given the observations, how do we adjust the model parameters to maximize likelihood? (Solved by the Baum-Welch Algorithm, a specific form of EM).