Hidden Markov Models (HMMs)
Md Mynoddin
Assistant Professor (CSE), RMSTU
26 Nov 2024
Md Mynoddin (Assistant Professor (CSE), RMSTU)Hidden Markov Models (HMMs) 26 Nov 2024 1/9
Introduction to Hidden Markov Models (HMMs)
Definition:
A Hidden Markov Model is a statistical model that represents a
sequence of observable events dependent on a sequence of hidden
states.
Key Characteristics:
Hidden States: States are not directly observable.
Markov Property: The next state depends only on the current state.
Observations: Each state generates an observable output.
Widely used in NLP, Speech Recognition, and Bioinformatics.
Md Mynoddin (Assistant Professor (CSE), RMSTU)Hidden Markov Models (HMMs) 26 Nov 2024 2/9
Components of an HMM
A Hidden Markov Model is defined by:
States (S):
A finite set of hidden states, S = {s1 , s2 , . . . , sn }.
Observations (O):
A finite set of observable events, O = {o1 , o2 , . . . , om }.
Transition Probabilities (A):
A = {aij }, where aij = P(sj |si ).
Emission Probabilities (B):
B = {bj (ok )}, where bj (ok ) = P(ok |sj ).
Initial Probabilities (π):
πi = P(si ), the probability of starting in state si .
Md Mynoddin (Assistant Professor (CSE), RMSTU)Hidden Markov Models (HMMs) 26 Nov 2024 3/9
Example of an HMM
Consider a weather prediction problem:
States: Hidden states are Rainy and Sunny.
Observations: Observables are Walk, Shop, and Clean.
Transition Probabilities (A):
0.7 0.3
A=
0.4 0.6
Emission Probabilities (B):
0.1 0.4 0.5
B=
0.6 0.3 0.1
Initial Probabilities (π):
π = 0.6 0.4
Md Mynoddin (Assistant Professor (CSE), RMSTU)Hidden Markov Models (HMMs) 26 Nov 2024 4/9
Three Fundamental Problems of HMMs
Problem 1 (Likelihood Estimation):
Given an observation sequence O and model λ = (A, B, π), compute
P(O|λ).
Solved using the Forward Algorithm.
Problem 2 (Decoding):
Find the most probable sequence of states S = {s1 , s2 , . . . } given O
and λ.
Solved using the Viterbi Algorithm.
Problem 3 (Learning):
Adjust parameters A, B, and π to maximize P(O|λ).
Solved using the Baum-Welch Algorithm.
Md Mynoddin (Assistant Professor (CSE), RMSTU)Hidden Markov Models (HMMs) 26 Nov 2024 5/9
Forward Algorithm
Computes P(O|λ), the probability of an observation sequence.
Uses dynamic programming to compute probabilities recursively.
Recurrence relation:
N
!
X
αt (j) = αt−1 (i)aij bj (ot )
i=1
Complexity: O(N 2 T ), where N is the number of states and T is the
length of the observation sequence.
Md Mynoddin (Assistant Professor (CSE), RMSTU)Hidden Markov Models (HMMs) 26 Nov 2024 6/9
Viterbi Algorithm
Finds the most probable sequence of hidden states.
Recurrence relation:
N
δt (j) = max [δt−1 (i)aij ] bj (ot )
i=1
Backtracking to recover the best path:
st = arg max δt (i)
i
Complexity: O(N 2 T ).
Md Mynoddin (Assistant Professor (CSE), RMSTU)Hidden Markov Models (HMMs) 26 Nov 2024 7/9
Applications of HMMs
Natural Language Processing (NLP):
Part-of-Speech Tagging
Named Entity Recognition
Speech Recognition:
Mapping audio signals to phonemes and words.
Bioinformatics:
Gene prediction and protein modeling.
Finance:
Modeling stock market trends.
Md Mynoddin (Assistant Professor (CSE), RMSTU)Hidden Markov Models (HMMs) 26 Nov 2024 8/9
Summary
HMMs are powerful tools for modeling sequences with hidden states.
Key components: states, observations, transitions, emissions, and
initial probabilities.
Solving HMM problems:
Likelihood estimation: Forward Algorithm.
Decoding: Viterbi Algorithm.
Parameter learning: Baum-Welch Algorithm.
Widely used in NLP, speech recognition, and bioinformatics.
Md Mynoddin (Assistant Professor (CSE), RMSTU)Hidden Markov Models (HMMs) 26 Nov 2024 9/9
