Hey, guys.
Welcome back to this class, unsupervised machine learning, hidden Markov models in Python.
One problem that frequently arises when we're working with HMS is the underflow problem.
Imagine you have a very long sequence.
Well, 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, tried to
calculate point one to the power of 500 in Python.
What's the largest power you can multiply without it is going down to zero.
So we find that this caps off at just a few hundred, think of an audio signal.
Audio signals are sampled at 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 Iturbi algorithm.
This is an easy case because it only involves multiplications.
And we know that we can use the law of probability instead of the actual probability because it's monotonically
increasing.
The log of multiplication is just the sum of logs, so of Iturbi 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 initialization step becomes alpha prime of one.
I equals the same expression that we had four alpha before.
The difference is Alpha Prime is just a temporary variable.
We use the prime variables to define the scale, which is just the sum of the variable over all the
states at that time.
Finally, we define our Ferhat to just be the prime variable divided by CFT.
So to get out of a hat for our initialization, we divide what we had before by sea of one.
Next, we can define our induction step as the next prime variable in terms of the old hotted variable.
So this is the same expression we had before, except the thing on the right gets handed 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 sea of tears 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 log probabilities as our cost function.
You'll see that even with multiple observations, we can remove the probability of the sequence from
the update equations entirely.
Next, let's talk about the beta update.
For this, we don't have to calculate and new scale factor, we can just use the same one from before
Medhat is initialize the same as before just to one.
The induction step is defined as follows, so it's basically the old induction step scale by C of T
plus one.
Here are some identities I want you guys to try and improve, 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 updated equations in terms
of the Hadit Alpha and the how to data.
OK, so hopefully you guys were able to prove those identities.
With those in hand, we can define our new updates, sopi I is the same as before, but the probability
goes away.
AIG 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 hotted variables.
Now it's just a matter of implementing these changes.