Hidden Markov Models in C#: Demo application we are going to build today
Mouse Gesture Recognition Application in C#, using Hidden Markov Models: Download
Hidden Markov Models
In Machine Learning, sequence classification is a type of pattern recognition task. Only this time the algorithm takes a sequence of observed values as an input. In mathematics, a sequence is an enumerated collection of objects. In which repetitions are allowed and order matters. Just like a set, it contains members. So, a sequence can be thought of as a list of elements with a particular order.
For example, the prime numbers are the natural numbers bigger than 1 that have no divisors but 1 and themselves.
2, 3, 5, 7, 11, 13, 17, ...
The Fibonacci numbers comprise the integer sequence whose elements are the sum of the previous two elements.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
But how does all this tie into our problem?
Hidden Markov Models for Sequence Classification
Well let’s say that you have a sequence of events. It can be any kind of sequences. For example, it can be a sequence of letters, words, images, sounds, or coordinates. The question is, can we somehow categorize them? Can we put a label on a sequence of events?
Well as it turns out, we can. And we can do that by using the Hidden Markov Model. The Hidden Markov Models are sequence models. And why use Machine Learning algorithm to solve this problem?
Well distance metrics between arbitrary pairs of sequences can be hard to define. This is because the sequence can vary in length, but most importantly we might need the model to learn the context or dependencies between the elements in the sequence. As a result, we end up with a model that tries to mimic them. It needs to behave more or less like the sequence you provide.
But the sequences must follow some pattern, or some regularity. That way you can start grouping similar sequences which follow the same model/pattern. And this is the most important claim. A sequence must follow a pattern that the model has been trained on. And this is how you do sequence classification using Hidden Markov Models.
Part-Of-Speech Tagging Example
A good example that I was able to find on Hidden Markov Models is in part-of-speech tagging task. Let us look at the following sentence:
They refuse to permit us to obtain the refuse permit.
In this sentence the word refuse is being used twice. To pronounce this text correctly, we need to know which refuse is being used in the sentence. The first refuse plays the role of a verb meaning “deny”. The second one is a noun meaning “trash”. Now, everything we have mentioned earlier ties up altogether.
If we use just a regular algorithm, we will miss out on the sentence context, by missing the dependencies between the elements in the sequence. What I mean by that is, we are missing the relationships between the words preceding or following the word refuse.
For example, an algorithm that proceeds from left to right, labelling one word at a time, can only use the left-adjacent words. Therefore, it might fail to detect the difference in the meaning of the words. On the other hand, a Hidden Markov Model can assume on how the word needs to be pronounced, based on the adjacent word labels.
Now, let’s see what we are going to implement today.
Mouse Gesture Recognition
The Hidden Markov Model has a lot of practical applications. We are going to examine and implement a few using C#. But for right now we will focus on something simple. We are going to train the Hidden Markov Model to recognize mouse movement sequence. Specific mouse movements, and when the sequence is detected it will execute a command.
This scenario fits perfectly as a Hidden Markov Model example. By moving the mouse, we are creating a sequence placed in a C# collection. Once we have populated the list, we are ready to make the mouse gesture recognition. We are going to train for two sequences. The first pattern will match the letter B which stands for Blue and the second one R for Red. Once the pattern is detected the Picture Box will change its color to match the recognized mouse gesture label.
But first, let’s take a quick look at the application interface.
Mouse Gesture Recognition a C# application walkthrough
As you can see, we are going to use C# and Windows Forms to build this demo app. The top section of the app serves as a sequence creator. And the middle one is the Hidden Markov Model training section. At the bottom we have a simple Picture Box control.
Sequence Creation
Like we mentioned before, the Hidden Markov Model works with sequences. The Sequence Number tells the C# application how many mouse coordinates to gather. The interval field represents the time frame at which a mouse point is collected. So, every 100 milliseconds one mouse coordinate is taken.
Behind the scenes in C# we are using a Timer control. It fires an event every x amount of milliseconds exactly y times. Where x is the value put in the Interval control and y is the value placed in the Sequence numeric.
Also, we assign a label to each sequence. The label should be a known color. For example, a mouse movement that looks like the letter B should get the label Blue. This is just for a demonstration purpose. You can easily assign any kind of operation on the recognized sequence. C# allows you to get the screen mouse coordinates, so this easily can be transferred on a system level. Maybe, instead of using the keyboard shortcuts, you can train your own Hidden Markov Model to execute a command once a mouse gesture is recognized.
To change the background color of the Picture Box we must use what C# refers to a known color. This is because we’ll use the command:
Color.FromName(label);The label is just a string provided to us by the Hidden Markov Model. So it has to be a known color for this to work.
Hidden Markov Model: Training Section
Next comes the Hidden Markov Model section. We will explain what these parameters mean when we examine the C# code. But for now, we will set the Number of states to 5, and set the Tolerance level to 0.01. In order to differentiate between two mouse gestures 100 iterations are enough.
The Rejection check box tells the C# application to not classify unknown mouse movement patterns. When this is checked any pattern that is unknown to the Hidden Markov Model will be dismissed.
When an unknown sequence is detected the label is set to None. None is not a color so we map it to the color White.
Again, we will talk about this in a sec.
The button Train obviously runs the training procedure on the Hidden Markov Model. Once the model is trained, we can test it by creating a new mouse movement sequence and click the button Decide. This procedure will try and classify the collected pattern.
The Run and Stop buttons allow the C# application to run indefinitely. As you move your mouse inside the Picture Box control the Hidden Markov Model will try to classify each gesture in real time. Until the Stop button is pressed.
Mouse Gesture Recognition a C# application in action
This window demonstrates how the training is done. The red circles represent a mouse point taken every 100 milliseconds. There are 20 points in total. This way we are building a C# collection of mouse points that is our sequence. This sequence is passed to the Hidden Markov Model database for training by clicking the Add button. The input label as you can see is set to Blue. In this application when the mouse gesture is recognized under the label Blue, the picture box will set that as its background color.
Similarly, for our second pattern. If a mouse gesture in the shape of the letter R is detected, the Picture Box will change its color to Red.
This is our goal result. A trained Hidden Markov Model that can do a mouse gesture recognition. As you can see the movement of the mouse is forming a sequence in the shape of B which translates into the label Blue. As a result, our C# application changes the background color of the Picture Box control to the output label from the model.
Mouse Gesture Recognition: C# Code Walkthrough
The focus of this section will be the Hidden Markov Model. Currently I am working on a C# implementation of this algorithm, and I will be releasing it soon. In order to explain and implement this machine learning model it would take quite some time and a couple of posts. So, I decided to split this tutorial into couple of sections.
This one will explain how to use the Accord implementation. The next post on this subject will explain the mathematics and the pure C# implementation. So, stay tuned.
Hidden Markov Models in C# for any kind of observations
The Hidden Markov Model can be used in conjunction with a supervised and unsupervised learning algorithms. For this particular scenario we are using unsupervised learning algorithm. We will discuss this a little later.
In this demo we are using the generic version of the Hidden Markov Model in C#. Let’s declare the variable:
HiddenMarkovClassifier<MultivariateNormalDistribution, double[]> hmm;Now, lets make an instance of this class and we will explain the generic types.
hmm = new HiddenMarkovClassifier<MultivariateNormalDistribution, double[]>
(database.Classes.Count,
new Forward(_states),
new MultivariateNormalDistribution(2), database.Classes.ToArray());
The first generic type represents the Distribution. This parameter is responsible for setting the initial probability distribution for the hidden states. The second generic type represents the observation (our input type).
The first statement is a little bit abstract, especially if you are following this without a prior knowledge on machine learning and Hidden Marko Model. So, let’s better define the C# code we just wrote.
Hidden Markov Models are probabilistic frameworks where the observed data are modeled as a series of outputs generated by one of several hidden states. Inside the model there is a matrix which explains what the probability is, from going to one state from another, or going from one state to an observation. So, to start the process, we must set the initial state distribution. This will get the model going by starting at a certain hidden state.
As a result, we will set the initial probability distribution for the hidden states using the MultivariateNormalDistribution instance of a class.
Instantiating the Hidden Markov Model class
Each observation we gathered is represented as a Point. A Point is a C# struct which contains an ordered pair of (x, y) coordinates in a two-dimensional plane. Since we can not use the Point struct in our Hidden Markov Model, we need to translate it to an array with two elements [x, y]. And this array will be our observation. This explains our two generic types. Now off to the instantiation process.
When we instantiate the generic Hidden Markov Classifier, we need to specify the number of outputs. This is the number of classes we are observing. In our demo we have two distinct classes: Blue and Red.
Next, comes the topology of the Hidden Markov Model. The Topology defines the way a Markov Model transitions from one state to another. In our demo it is safe to say that we do not want to travel back in time to a previously seen state. It makes sense that we only move forward. As a result, state transitions are only allowed forward. So, we will use the Forward topology.
This Forward class has an input parameter. And that is the number of states. So how do we choose the number of states in a Hidden Markov Model? Well, this is a parameter that you must tune to see what works best for your problem. And five is good enough for this demo.
Next, we instantiate the MultivariateNormalDistribution class with the parameter denoting the number of dimensions our observation has. This way we are creating a multivariate Gaussian for two dimensions.
Lastly, we specify the class label for each of the models. Those will be represented as a C# array of strings, consisting of “Blue” and “Red”.
Hidden Markov Models in C# Learning Algorithm
After the model has been created, we can create the learning algorithm to train the classifier. The Baum-Welch algorithm is an unsupervised algorithm used to learn a single hidden Markov model object from a set of observation sequences. Although Accord allows us to use different learning algorithm for each model, we will use the same one for all our models.
The learning algorithm can be created, configured, and tuned individually for each model, which gives us higher train flexibility. We will work with different learning models in another post.
Right now, we will use the Baum Welch learning algorithm, so let’s see how to instantiate it.
new BaumWelchLearning<MultivariateNormalDistribution, double[]>(hmm.Models[i])
{
Tolerance = _tolerance,
MaxIterations = iterations
}
First, we need to set the tolerance level. The algorithm will stop the learning process when the change in the likelihood for two consecutive iterations has not changed by more than the specified value. If we set this to zero, the algorithm will end its work when the MaxIterations limit is reached.
Then, we specify the MaxIterations parameter. It specifies the maximum number of learning iterations to be performed by the algorithm. If this is set to zero, the learning algorithm will fall back to the Tolerance parameter to know when it has done working.
The last important parameter we are going to set is Rejection. In short, Rejection allows us to dismiss a pattern not known to the Hidden Markov Model. Because I want to be able not to act on an unknown pattern, I will set this value to true.
All we must do now is to call the Learn method provided by the learning algorithm and wait for the process to complete. Once done, we can use the model to classify sequences.
Hidden Markov Models in C#: Summary
Use the Hidden Markov Models when you want to classify a sequence of elements. Although this is an overly simplified statement, it works well for the scenario we just implemented. Use the generic version of the Hidden Markov Model implementation to best suite your observation type. Don’t forget that we must initialize the probability distribution for the hidden states. Set the Topology according to your problem and tune the States (number of states) parameter by trying different values.
Hidden Markov Models in C#: Conclusion
We are going to end this post here. It’s already too long. Join me in the next one, where we are going to explore all the things that were not mentioned here – and more. For now, this is enough. The premise of this post is to learn how and when to use the Hidden Markov Model in your C# project. Next time, we can try and classify a sequence of images to decide what kind of video are we watching. Or maybe do a text to speech project using Hidden Markov Models. The possibilities are endless, so we are going to continue this series with a C# implementation of this machine learning algorithm, and use it in a different scenario.