Scribd
Upload
20 views8 pages

Viterbi Algorithm in NLP Decoding

The document presents a lecture on the Viterbi Algorithm, focusing on decoding tasks in Hidden Markov Models (HMMs) where hidden variables are involved. It explains how to compute the likelihood of observation sequences using the Forward Algorithm and discusses the complexities of determining probabilities in HMMs. An example involving ice cream observations is provided to illustrate the concepts.

Uploaded by

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

Viterbi Algorithm in NLP Decoding

The document presents a lecture on the Viterbi Algorithm, focusing on decoding tasks in Hidden Markov Models (HMMs) where hidden variables are involved. It explains how to compute the likelihood of observation sequences using the Forward Algorithm and discusses the complexities of determining probabilities in HMMs. An example involving ice cream observations is provided to illustrate the concepts.

Uploaded by

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

Course Title – Natural Language Processing

Topic Title – Decoding – Viterbi Algorithm

Presenter’s Name – Dr. M Nagaraju


Presenter’s ID – IARE10960
Department Name – CSE (AI & ML)
Lecture Number - 3
Presentation Date – 02-05-2025
1
Viterbi Algorithm

• For an HMM that contains hidden variables, the task of


determining which sequence of variables is the underlying
source of some sequence of observations is called the decoding
task.

• In the ice cream domain, given a sequence of ice cream


observations 3 1 3 and an HMM, the task of the decoder is to
find the best hidden weather sequence (H H H).

2
Computing Likelihood: The Forward Algorithm
• Our first problem is to compute the likelihood of a particular
observation sequence. For example, given the HMM, what is the
probability of the sequence 3 1 3?

3
Computing the Likelihood

• For a Markov chain, where the surface observations are the


same as the hidden events then:
• we could compute the probability of 3 1 3 just by following the
states labeled 3 1 3 and multiplying the probabilities along the
arcs.
• The statement refers to a special case of a Markov chain where
the observed values (outputs) are the same as the states of the
chain.

4
Computing the Likelihood - Example

• If you want to compute the probability of observing a sequence


like 3  1  3, and the states are themselves the observable
then:
• Just look at the transitions from state 3 to 1, and then from 1
to 3.
• Multiply the transition probabilities along the path.

5
Computing the Likelihood - Example

6
HMM for Probabilities

• For a Hidden Markov Model, things are not so simple.


• We want to determine the probability of an ice-cream observation
sequence like 3 1 3, but we don't know what the hidden state
sequence is!
Simple Example:
• Suppose we already knew the weather, and wanted to predict
how much ice cream Jason would eat.
• This is a useful part of many HMM tasks.
• For a given hidden state sequence (e.g. hot hot cold) we can
easily compute the output likelihood of 3 1 3.

7
Thank You

You might also like