Hey guys welcome back to this class unsupervised machine learning it in Markov models in Python.
One problem that frequently arises when we're working with ha memes is the underflow problem.
Imagine you have a very long sequence where the forward algorithm says we should just keep multiplying
Alpha until the end of the sequence.
But what happens when you keep multiplying small numbers together.
They get even smaller trying to calculate point 1 to the power of 500 in Python.
What's the largest power you can multiply without it just going down to zero.
So we find that this caps off at just a few hundred think of an audio signal audio signals are assembled
that forty four thousand one hundred samples per second.
Well your HMO is not going to be that useful if you can only represent a few milliseconds of data.
So how do we solve this problem.
Well let's first look at the Turby algorithm.
This is an easy case because it only involves multiplications and we know that we can use the lag probability
instead of the actual probability because it's monotonically increasing the log of a multiplication
is just the sum of logs.
So Viterbo is solved.
We just log everything.
But what about the forward backward algorithm and the training algorithm which involves sums.
This is going to be much harder but what we'll do is introduce the concept of scaling to accomplish
proper scaling.
We're going to introduce a scale factor let's call it CFT just like Alpha Beta it's going to be length
Big T with the scale factor.
We can restate the three steps of the forward algorithm.
The initializations that becomes Alpha Prime of one eye equals the same expression that we had for Alpha
before.
The difference is also Prime is just a temporary variable.
We use the prime variables to define a scale which is just the sum of the prime variable over all the
states at that time.
Finally we define Alpha had to just be the prime variable divided by C of T so to get alpha for our
initialization we divide what we had before.
By C of one next we can define our induction step as the next prime variable in terms of the old how
did variable.
So this is the same expression we had before except the thing on the right gets Hadad and the thing
on the left gets primed the scaling remains the same.
Finally we can calculate the probability of the observation as follows.
This is just the product of all the C of TS as an exercise try to prove to yourself that this is true.
Note that this observation probability is going to be a very tiny number which was the whole reason
we were doing this in the first place.
But notice that it's in the form of a product which means we can just calculate the lag probabilities
as our cost function.
You'll see that even with multiple observations we can remove the probability of a sequence from the
update equation entirely
Next let's talk about the beta update.
For this we don't have to calculate a new scale factor.
We can just use the same one from before the hat is initialize the same as before just to 1 the induction
step is defined as follows.
So it's basically all induction step scale by C. of T plus 1.
Here are some identities.
I want you guys to try and prove.
Often people ask me how can I make sure I know what I'm doing.
How can I get good at this.
Well this is how.
So we have three identities here and these can all be proved using the equations that I previously showed
you.
These identities are important because we'll be using them to rewrite our update equations in terms
of the Hadad Alpha and the hard data OK.
So hopefully you guys were able to prove those identities with those in hand we can define our new updates.
So why is the same as before.
But the probability goes away AJ is also very similar to before the probability has also gone away.
So the probability was just absorbed into these terms and we add a scale factor to the numerator.
We get a similar expression for the b variable and that's all there is to it.
Notice how we've eliminated the actual probability of observation since it's implicitly included in
the Hadad variables.
Now it's just a matter of implementing these changes.