0
$\begingroup$

I came across the following problem involving bigram models which I am struggling to solve. Following this tutorial 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.

$\endgroup$
2

1 Answer 1

1
+50
$\begingroup$

You're following a greedy approach, which might not necessarily work. What you've to do is to compute the probabilities of all possible sequences and pick the one with the highest probability. And, there is a clever way to do it, known as the Viterbi decoding. I refer you to the video here.

So, the first character probabilities will be the initial state probabilities and the probabilities of the form p(x|y) will be the transition probabilities from y to x.

The trick of Viterbi algorithm is that, at each time step k, for every symbol in [o,p,e,n,a,i] it is sufficient to remember the most likely path to that symbol from timestep k-1 instead of every path into that symbol.

PS: I haven't answered it in detail since I was only going to post a comment but I was unable to because of my low 'credits'

$\endgroup$
3
  • $\begingroup$ Thanks for taking the time to answer. I will certainly look into Viterbi decoding the above mentioned points. I understand that I have taken a greedy approach, but still confused since $p( 'n' | 'n' ) = 0.84;$ has the highest probability out of all the other possibilities. I will go through the mentioned points to clear this . $\endgroup$
    – rrz0
    Aug 26, 2018 at 10:42
  • $\begingroup$ You have to check how you got these probabilities. I will recommend you to go through the text corpus from which these values were obtained. $\endgroup$
    – Srini Vas
    Aug 26, 2018 at 19:23
  • $\begingroup$ no text corpus unfortunately. This was an online question. $\endgroup$
    – rrz0
    Aug 27, 2018 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.