Hidden Markov Models Hmm Sequence Modeling
# Hidden Markov Models: HMM & Sequence Modeling
## Introduction & Motivation
Hidden Markov Models: probabilistic sequence model. Hidden states; observable emissions. Markov assumption: future independent of past given present. Applications: speech recognition, biology, finance, sequence tagging.
Motivation: Model temporal dependencies; hidden state interpretation.
Applications: Speech, biology, time series.
---
## Core Concepts & Theory
### Markov Chain
Memoryless property; transition probabilities.
### Hidden States
Unobserved state sequence.
### Emission Probability
Observation likelihood given state.
---
## Mathematical Formulation
HMM definition:
$$P(X, S) = P(S_1) \prod_{t=1}^{T-1} P(S_{t+1}|S_t) \prod_{t=1}^{T} P(X_t|S_t)$$
Forward algorithm:
$$\alpha_t(i) = P(X_1:t, S_t=i) = \sum_j \alpha_{t-1}(j) P(S_t=i|S_{t-1}=j) P(X_t|S_t=i)$$
Viterbi decoding:
$$S^* = \arg\max_S P(S|X)$$
---
## Advanced Theory & Extensions
### Baum-Welch Algorithm
EM for HMM parameter learning.
### Hierarchical HMMs
Nested state structure.
### Continuous Emission Distribution
Gaussian or mixture models.
---
## Computational Considerations
Forward: O(T·N²) where T = sequence length, N = states.
Viterbi: O(T·N²) decoding.
Baum-Welch: O(T·N²) per iteration.
---
## Practical Implementation Strategies
### Scaling
Log-probability to avoid underflow.
### Initialization
Uniform or data-driven priors.
### Stopping Criteria
Likelihood convergence threshold.
---
## Benchmark Datasets & Evaluation
UCI HAR: Activity recognition.
TIMIT: Speech recognition phoneme.
POS Tagging: Sequence labeling benchmark.
---
## Key Challenges & Limitations
### Ergodicity
Some states unreachable; parameter issues.
### Sparsity
Many zero transition probabilities.
### Oversimplification
Markov assumption too restrictive.
---
## Hyperparameter Tuning
Number of states: 5-50; problem dependent.
Emission distribution: Discrete, Gaussian, mixture.
Convergence threshold: 1e-6 to 1e-8.
---
## Real-World Applications & Case Studies
Speech Recognition: Phone sequence modeling.
Gene Prediction: DNA sequence annotation.
Stock Price: Regime switching models.
---
## Integration with Other Methods
HMM + Neural Network → hybrid models.
HMM + Graphical model → structured prediction.
---
## Summary & Key Takeaways
Hidden Markov Models via probabilistic sequence modeling enable temporal pattern recognition through state sequences and transition dynamics.
Principles:
1. Hidden states: latent representation.
2. Markov property: memoryless transitions.
3. Emission: state-observation mapping.
4. Forward algorithm: likelihood computation.
5. Viterbi: optimal path decoding.
---
---
## Appendix: Practical Labs
### Lab 1: Forward Algorithm
import numpy as np
def forward_algorithm(observations, transitions, emissions, initial):
"""Compute forward probabilities"""
T = len(observations)
N = len(initial)
# Forward table
alpha = np.zeros((T, N))
# Initialize
alpha[0] = initial * emissions[:, observations[0]]
# Forward pass
for t in range(1, T):
for j in range(N):
alpha[t, j] = (alpha[t-1] @ transitions[:, j]) * emissions[j, observations[t]]
return alpha
# Test
np.random.seed(42)
observations = [0, 1, 0, 1, 0]
transitions = np.array([[0.7, 0.3], [0.4, 0.6]], dtype=float)
emissions = np.array([[0.8, 0.2], [0.3, 0.7]], dtype=float)
initial = np.array([0.5, 0.5])
alpha = forward_algorithm(observations, transitions, emissions, initial)
assert alpha.shape == (5, 2), "Alpha shape"
assert np.all(alpha >= 0), "Probabilities non-negative"
print("✓ Forward algorithm working")
if __name__ == "__main__":
print("Lab 1: ForwardAlgorithm - PASSED")### Lab 2: Viterbi Decoding
import numpy as np
def viterbi_decode(observations, transitions, emissions, initial):
"""Viterbi algorithm for most likely sequence"""
T = len(observations)
N = len(initial)
# Viterbi table
viterbi = np.zeros((T, N))
backpointer = np.zeros((T, N), dtype=int)
# Initialize
viterbi[0] = np.log(initial + 1e-8) + np.log(emissions[:, observations[0]] + 1e-8)
# Forward pass
for t in range(1, T):
for j in range(N):
# Find best previous state
temp = viterbi[t-1] + np.log(transitions[:, j] + 1e-8)
backpointer[t, j] = np.argmax(temp)
viterbi[t, j] = np.max(temp) + np.log(emissions[j, observations[t]] + 1e-8)
# Backtrack
path = [np.argmax(viterbi[-1])]
for t in range(T-1, 0, -1):
path.append(backpointer[t, path[-1]])
return list(reversed(path))
# Test
np.random.seed(42)
observations = [0, 1, 0, 1, 0]
transitions = np.array([[0.7, 0.3], [0.4, 0.6]], dtype=float)
emissions = np.array([[0.8, 0.2], [0.3, 0.7]], dtype=float)
initial = np.array([0.5, 0.5])
path = viterbi_decode(observations, transitions, emissions, initial)
assert len(path) == 5, "Path length"
assert all(0 <= s < 2 for s in path), "Valid states"
print("✓ Viterbi decoding working")
if __name__ == "__main__":
print("Lab 2: ViterbiDecoding - PASSED")### Lab 3: Backward Algorithm
import numpy as np
def backward_algorithm(observations, transitions, emissions, initial):
"""Compute backward probabilities"""
T = len(observations)
N = len(initial)
# Backward table
beta = np.zeros((T, N))
# Initialize
beta[-1] = 1.0
# Backward pass
for t in range(T-2, -1, -1):
for i in range(N):
beta[t, i] = (transitions[i] * emissions[:, observations[t+1]] * beta[t+1]).sum()
return beta
# Test
np.random.seed(42)
observations = [0, 1, 0, 1, 0]
transitions = np.array([[0.7, 0.3], [0.4, 0.6]], dtype=float)
emissions = np.array([[0.8, 0.2], [0.3, 0.7]], dtype=float)
initial = np.array([0.5, 0.5])
beta = backward_algorithm(observations, transitions, emissions, initial)
assert beta.shape == (5, 2), "Beta shape"
assert np.all(beta >= 0), "Probabilities non-negative"
print("✓ Backward algorithm working")
if __name__ == "__main__":
print("Lab 3: BackwardAlgorithm - PASSED")### Lab 4: HMM Likelihood
import numpy as np
def hmm_likelihood(observations, transitions, emissions, initial):
"""Compute likelihood of observation sequence"""
T = len(observations)
N = len(initial)
# Forward pass
alpha = np.zeros((T, N))
alpha[0] = initial * emissions[:, observations[0]]
for t in range(1, T):
for j in range(N):
alpha[t, j] = (alpha[t-1] @ transitions[:, j]) * emissions[j, observations[t]]
# Likelihood
likelihood = alpha[-1].sum()
return likelihood
# Test
np.random.seed(42)
observations = [0, 1, 0, 1, 0]
transitions = np.array([[0.7, 0.3], [0.4, 0.6]], dtype=float)
emissions = np.array([[0.8, 0.2], [0.3, 0.7]], dtype=float)
initial = np.array([0.5, 0.5])
likelihood = hmm_likelihood(observations, transitions, emissions, initial)
assert 0 <= likelihood <= 1, "Likelihood in [0,1]"
print("✓ HMM likelihood working")
if __name__ == "__main__":
print("Lab 4: HMMLikelihood - PASSED")