I came across the following problem involving bigram models which I am struggling to solve. Following [this tutorial][1] I have a basic understanding of how bigram possibilities are calculated.
**Problem:**
------------
Let's consider sequences of length 6 made out of characters ['o', 'p', 'e', 'n', 'a', 'i']. There are 6^6 such sequences.
We consider bigram model with the following probabilities:
----------
For the first character in the sequence:
p( 'o' ) = 0.05; p( 'p' ) = 0.00; p( 'e' ) = 0.03; p( 'n' ) = 0.76; p( 'a' ) = 0.07; p( 'i' ) = 0.09;
in short: [0.05, 0, 0.03, 0.76, 0.07, 0.09]
For the transitions:
p( 'o' | 'o' ) = 0.73; p( 'p' | 'o' ) = 0.02; p( 'e' | 'o' ) = 0.04; p( 'n' | 'o' ) = 0.07; p( 'a' | 'o' ) = 0.06; p( 'i' | 'o' ) = 0.08;
in short: [0.73, 0.02, 0.04, 0.07, 0.06, 0.08]
$p( 'o' | 'p' ) = 0.01;$ $p( 'p' | 'p' ) = 0.06;$ $p( 'e' | 'p' ) = 0.07;$ $p( 'n' | 'p' ) = 0.07;$ $p( 'a' | 'p' ) = 0.08;$ $p( 'i' | 'p' ) = 0.71;$
in short: $[0.01, 0.06, 0.07, 0.07, 0.08, 0.71]$
$( 'o' | 'e' ) = 0.09;$ $p( 'p' | 'e' ) = 0.08;$ $p( 'e' | 'e' ) = 0.09;$ $p( 'n' | 'e' ) = 0.71;$ $p( 'a' | 'e' ) = 0.03;$ $p( 'i' | 'e' ) = 0.00;$
in short: $[0.09, 0.08, 0.09, 0.71, 0.03, 0]$
$p( 'o' | 'n' ) = 0.05;$ $p( 'p' | 'n' ) = 0.00;$ $p( 'e' | 'n' ) = 0.02;$ $p( 'n' | 'n' ) = 0.84;$ $p( 'a' | 'n' ) = 0.08;$ $p( 'i' | 'n' ) = 0.01;$
in short: $[0.05, 0, 0.02, 0.84, 0.08, 0.01]$
$p( 'o' | 'a' ) = 0.03;$ $p( 'p' | 'a' ) = 0.80;$ $p( 'e' | 'a' ) = 0.07;$ $p( 'n' | 'a' ) = 0.00;$ $p( 'a' | 'a' ) = 0.01;$ $p( 'i' | 'a' ) = 0.09;$
in short: $[0.03, 0.8, 0.07, 0, 0.01, 0.09]$
$p( 'o' | 'i' ) = 0.00;$ $p( 'p' | 'i' ) = 0.04;$ $p( 'e' | 'i' ) = 0.07;$ $p( 'n' | 'i' ) = 0.03;$ $p( 'a' | 'i' ) = 0.79;$ $p( 'i' | 'i' ) = 0.07;$
in short: $[0, 0.04, 0.07, 0.03, 0.79, 0.07]$
----------
Find the most probable sequence in this model and write the answer here:
I am a complete beginner in this field so please bear with me.
So far:
-------
1. The first character is $'n'$ with the highest probability of $0.76$.
2. Next I need to find the probability of which letter follows $'n'$. This is the 4th transition.
3. $p( 'n' | 'n' ) = 0.84$ seems to have the highest probability, so $'n'$ is followed by 'n' and so on.
4. $'n', 'n', 'n', 'n', 'n', 'n'$
I think that I am failing to understand some core concept or misunderstanding the question. Many thanks for any advice.
[1]: https://gist.github.com/ttezel/4138642
**Problem:**
------------
Let's consider sequences of length 6 made out of characters ['o', 'p', 'e', 'n', 'a', 'i']. There are 6^6 such sequences.
We consider bigram model with the following probabilities:
----------
For the first character in the sequence:
p( 'o' ) = 0.05; p( 'p' ) = 0.00; p( 'e' ) = 0.03; p( 'n' ) = 0.76; p( 'a' ) = 0.07; p( 'i' ) = 0.09;
in short: [0.05, 0, 0.03, 0.76, 0.07, 0.09]
For the transitions:
p( 'o' | 'o' ) = 0.73; p( 'p' | 'o' ) = 0.02; p( 'e' | 'o' ) = 0.04; p( 'n' | 'o' ) = 0.07; p( 'a' | 'o' ) = 0.06; p( 'i' | 'o' ) = 0.08;
in short: [0.73, 0.02, 0.04, 0.07, 0.06, 0.08]
$p( 'o' | 'p' ) = 0.01;$ $p( 'p' | 'p' ) = 0.06;$ $p( 'e' | 'p' ) = 0.07;$ $p( 'n' | 'p' ) = 0.07;$ $p( 'a' | 'p' ) = 0.08;$ $p( 'i' | 'p' ) = 0.71;$
in short: $[0.01, 0.06, 0.07, 0.07, 0.08, 0.71]$
$( 'o' | 'e' ) = 0.09;$ $p( 'p' | 'e' ) = 0.08;$ $p( 'e' | 'e' ) = 0.09;$ $p( 'n' | 'e' ) = 0.71;$ $p( 'a' | 'e' ) = 0.03;$ $p( 'i' | 'e' ) = 0.00;$
in short: $[0.09, 0.08, 0.09, 0.71, 0.03, 0]$
$p( 'o' | 'n' ) = 0.05;$ $p( 'p' | 'n' ) = 0.00;$ $p( 'e' | 'n' ) = 0.02;$ $p( 'n' | 'n' ) = 0.84;$ $p( 'a' | 'n' ) = 0.08;$ $p( 'i' | 'n' ) = 0.01;$
in short: $[0.05, 0, 0.02, 0.84, 0.08, 0.01]$
$p( 'o' | 'a' ) = 0.03;$ $p( 'p' | 'a' ) = 0.80;$ $p( 'e' | 'a' ) = 0.07;$ $p( 'n' | 'a' ) = 0.00;$ $p( 'a' | 'a' ) = 0.01;$ $p( 'i' | 'a' ) = 0.09;$
in short: $[0.03, 0.8, 0.07, 0, 0.01, 0.09]$
$p( 'o' | 'i' ) = 0.00;$ $p( 'p' | 'i' ) = 0.04;$ $p( 'e' | 'i' ) = 0.07;$ $p( 'n' | 'i' ) = 0.03;$ $p( 'a' | 'i' ) = 0.79;$ $p( 'i' | 'i' ) = 0.07;$
in short: $[0, 0.04, 0.07, 0.03, 0.79, 0.07]$
----------
Find the most probable sequence in this model and write the answer here:
I am a complete beginner in this field so please bear with me.
So far:
-------
1. The first character is $'n'$ with the highest probability of $0.76$.
2. Next I need to find the probability of which letter follows $'n'$. This is the 4th transition.
3. $p( 'n' | 'n' ) = 0.84$ seems to have the highest probability, so $'n'$ is followed by 'n' and so on.
4. $'n', 'n', 'n', 'n', 'n', 'n'$
I think that I am failing to understand some core concept or misunderstanding the question. Many thanks for any advice.
[1]: https://gist.github.com/ttezel/4138642