Scribd
Upload
15 views2 pages

s3 Mat

A Hidden Markov Model (HMM) is a statistical model characterized by hidden states, observable outputs, transition probabilities, emission probabilities, and an initial state distribution. The three core problems associated with HMMs are evaluation (using the Forward Algorithm), decoding (using the Viterbi Algorithm), and learning (using the Baum-Welch Algorithm). The document also provides Python implementations for the Forward and Viterbi algorithms.

Uploaded by

mail2rolex
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views2 pages

s3 Mat

A Hidden Markov Model (HMM) is a statistical model characterized by hidden states, observable outputs, transition probabilities, emission probabilities, and an initial state distribution. The three core problems associated with HMMs are evaluation (using the Forward Algorithm), decoding (using the Viterbi Algorithm), and learning (using the Baum-Welch Algorithm). The document also provides Python implementations for the Forward and Viterbi algorithms.

Uploaded by

mail2rolex
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

HMM

Definition:
A Hidden Markov Model (HMM) is a statistical model in which the system being modeled is
assumed to be a Markov process with unobservable (hidden) states.

Key Components:

 States (hidden): S={s1,s2,...,sN}S = \{s_1, s_2, ..., s_N\}S={s1,s2,...,sN}


 Observations: O={o1,o2,...,oT}O = \{o_1, o_2, ..., o_T\}O={o1,o2,...,oT}
 Transition probabilities: A=[aij]A = [a_{ij}]A=[aij], where aij=P(sj∣si)a_{ij} =
P(s_j | s_i)aij=P(sj∣si)
 Emission probabilities: B=[bj(k)]B = [b_j(k)]B=[bj(k)], where bj(k)=P(ok∣sj)b_j(k)
= P(o_k | s_j)bj(k)=P(ok∣sj)
 Initial state distribution: π=[πi]\pi = [\pi_i]π=[πi], where πi=P(si at t=1)\pi_i = P(s_i
\text{ at } t=1)πi=P(si at t=1)

Three Core Problems

1. Evaluation: Compute the probability of an observed sequence given the model:


Use Forward Algorithm
2. Decoding: Find the most likely sequence of hidden states that produced the
observations:
Use Viterbi Algorithm
3. Learning: Adjust the model parameters to best fit an observed sequence:
Use Baum-Welch Algorithm (an EM algorithm)

Algorithms

a. Forward Algorithm (Evaluation)

python
CopyEdit
def forward(O, A, B, pi):
N = len(A)
T = len(O)
alpha = [[0]*N for _ in range(T)]

for i in range(N):
alpha[0][i] = pi[i] * B[i][O[0]]

for t in range(1, T):


for j in range(N):
alpha[t][j] = sum(alpha[t-1][i] * A[i][j] for i in range(N)) *
B[j][O[t]]

return sum(alpha[T-1])
Viterbi Algorithm (Decoding)

python
CopyEdit
def viterbi(O, A, B, pi):
N = len(A)
T = len(O)
delta = [[0]*N for _ in range(T)]
psi = [[0]*N for _ in range(T)]

for i in range(N):
delta[0][i] = pi[i] * B[i][O[0]]

for t in range(1, T):


for j in range(N):
max_prob, max_state = max((delta[t-1][i] * A[i][j], i) for i in
range(N))
delta[t][j] = max_prob * B[j][O[t]]
psi[t][j] = max_state

path = [0]*T
path[-1] = max(range(N), key=lambda i: delta[T-1][i])
for t in reversed(range(1, T)):
path[t-1] = psi[t][path[t]]

return path

You might also like