Add your own alternative version
Stats
164.3K views 8.4K downloads 102 bookmarked
Posted
30 Mar 2010

Comments and Discussions



How can i use this framework to clustering with EM algorithm?
I personally would prefer coding my own EM algorithm however i can not find anywhere real data example and i cant figure out how does it work with just looking mathematical equations
So my question is are there any example to use EM algorithm with this framework?
Thank you






hi,
I am new to HMM.
first of all nice code and documentation, it helped me to understand HMM better.
however I have some questions on states.
in the spreadsheet, rows 5,6 & 7 have three different digits/Events in sequence.
00022212222222 A 2(states)
01111222222212 B 2(States)
11111022222222 B 2(states)
1)how to decide that states outcome is 2, and not 3?
2)is it because the output is has higher probability to be either 2 out of the 3 classes?
3)if so, could I increase states according to the probability percentage, instead of hard coded? example, if all 3 distinct values have equal support of (33.33%), states will be set to 3.
thanks





Awesome code examples!
I was looking through the evaluation function and started to wonder what actually happens when you calculate the probability of the model generating a sequence of symbols. For me, it seems natural to use the alpha variable as defined by the forward algorithm, and add the value of the alpha variable for each state, with t = (length of sequence).
Instead, it seems like you multiply a number n of coefficients, where n is the length of the sequence.
Can you help me, I am bit confused about what those coefficients mean, and how multiplying them (adding in log space) calculates the likelihood of the sequence?





Hi there!
Thanks for the interest and for the nice feedback! However, I have to say that article is a bit outdated; it has been superseded by Sequence Classifiers in C#  Part I: Hidden Markov Models[^]. Also, the latest version of the code is also available in GitHub[^] if you would like to take a look.
In any case, also please let me explain what is going on the code. One problem when evaluating hidden Markov models is that their evaluation might involve multiplying lots of very small numbers, that become even smaller as the length of the sequence grows. As such, at some point, we start getting lots of precision errors because our computer have only finite precision for double numbers.
The implementation shown in the article was made using the scaling technique. This technique basically consists at, at each step of the forward algorithm, normalize the obtained probabilities so they sum up to one. However, we keep track of the normalization constants that we used at each step using the coefficients vector shown above. In the end, to get the probability of the sequence, we multiply those coefficients.
This is wellknown technique, but it is not the best one. That is why in the latest version of the Accord.NET Framework[^] this computation is done using logprobabilities instead. The idea is to first transform every probability in the forward matrix into the log domain, then use summations instead of multiplications at each step. This avoids getting very small numbers in the computations, and also avoids the need for normalizing at each step.
Hope it helps!
Best regards,
Cesar





Is the code somewhere available on GitHub?
I would like to make some contributions improving the performance of the algorithm.






Since the diff is too long, I can't comment on it on GitHub. Something quite strange is that when one evaluates a sequence with length zero, the result is double.NegativeInfinity . One would expect one, since such sequence is always "represented" in the hidden Markov model, and furthermore if one uses the real probability, an exp operation should be applied on it resulting in zero.
What is the rationale behind this decision?





Boas César !
I have a question.
You did this in your code: B[i, observations[0]].
If the value of "observations[0]" is negative or its value is greater than the column size of B, we will have an error.
So, why did you do this?
Thank you in advance.





Hello there!
Thanks for the interest in the code! In the discrete case, symbols can be represented by integer labels ranging from 0 to the number of symbols. For example, if you have observations "Sunny", "Cloudy", "Rain", you can easily replace them by 0, 1 and 2. And that is exactly what the HMM is expecting: a vector of integers ranging from 0 to the number of symbols. Thus, observations cannot be negative nor greater than the size of B. The number of symbols must be passed on the HMM's constructor so it can build the forward and emission matrices appropriately.
However, if you really need negative observations, which may imply that your observations are not discrete or cannot be translated into a set of integer symbols, then you can use the generic version of the hidden Markov models which can accept even realvalued variables[^]. For a more detailed explanation, please also take a look at the main article I submitted some years after this one, Sequence Classifiers in C#  Part I: Hidden Markov Models[^]. I hope it helps!
If you have more questions, don't hesitate to ask.
Best regards,
Cesar





Boas Cesar!
Muito obrigado.
It became more clear.
I would like to ask you another question. I have these observations, all negatives:
(62,58,46,41)
(53,56,46,40)
(50,55,41,37)
(61,53,46,38)
(60,55,40,42)
...
(52,49,46,37)
Each sequence represents a position in 2D, I mean (X,Y).
How can I infer the estimated values of X and Y from these observations using HMM?
I am a little confused all to deal with, so your help is greatly appreciated.
Thank you in advance for your help.





Hi Cesar!
I search Hidden markov model in C# and I found in code project. Is it using library ?
I need hidden markov model in C# without library. Can you help me explain concept hidden markov model and Is it must using more algorithm ? (i.e backwardforward, viterbi and baumwelch algorithm)
Thank you.
regards,
ervin





What do you mean with library? A library is simply a collection of source code. All the code to make this algorithm work is opensource (except for the .NET standard library), but these are low level instructions and are well documented...





Hi Cesar!
Great work. I am new to the whole .net thing and im kind of lost on how to get it working.
I installed the Accord.Net, Forge.Net and also SharpDevelop. So im wondering how can i import this in and get it to work? Sorry to bother u on such a simple question. But HMM has been around for a very long time. I did it during my school days using matlab but this is really intriguing.
Hope to hear from you soon.
Cheers,
Keevin





Hi Keevin!
Perhaps you could take a look on Accord.NET's getting started guide[^]. It shows how to add references to some projects. For HMMs, please take a look on the newer article, Sequence Classifiers in C#  Part I: Hidden Markov Models[^]. The assemblies you are looking for are Accord.Statistics and Accord.Math.
You can also download the sample project, which should come with an already working project configuration!
Hope it helps!
Cesar





Hello,
first of all. Thank you. Your code and article helps me a lot.
But I need to ask you something. How to interpreate the result ?
double l1 = hmm.Evaluate(new int[] { 0,1 }); double l2 = hmm.Evaluate(new int[] { 0,1,1,1 });
Why l1 has higher score than l2 ? l2 is much longer and same as l1 it fits to every sequence from sequences
What the result mean ? Is that 99% vs ~92% ?
Second thing I'm checking something and I've created 2 models. Each for diffrent sequence and I want to evaluate a squence and fit it to one of 2 models so I did this
int[][] sequences = new int[][]
{
new int[] { 1,1,1,1,1 },
new int[] { 1,1,1,1,0 },
new int[] { 1,1,1,1,1 },
new int[] { 1,1,1,1,1 },
};
int[][] sequences2 = new int[][]
{
new int[] { 0,0,0,0,0 },
new int[] { 0,0,0,0,0 },
new int[] { 0,0,0,0,1 },
new int[] { 0,0,0,0,0 },
};
HiddenMarkovModel hmm = new HiddenMarkovModel(2, 5, HiddenMarkovModelType.Forward);
HiddenMarkovModel hmm2 = new HiddenMarkovModel(2, 5, HiddenMarkovModelType.Forward);
hmm.Learn(sequences, 0.0001);
hmm2.Learn(sequences, 0.0001);
double l11 = hmm.Evaluate(new int[] { 0, 0, 0, 1, 1 });
double l21 = hmm2.Evaluate(new int[] { 0, 0, 0, 0, 0 });
Console.WriteLine("1) {0}  {1}", l11, l21);
funny thing is that l21 is rly small
1) 1,97215247536716E198  1,11546110202783E197
And I don't get why. The given sequence is like the one from sequnces2. So why isn't it near 1 ?
I hope i wrote is in a clear way
Best regards,
Dawid Pacholczyk
modified 6Jan13 11:48am.





1) Well a hidden Markov model is "trained" such that generating the given sequences (with which it is trained) is the most probable outcome. The Evaluate method calculates what the probability is of generating such sequence. A result is that the longer the sequence is, the less probable it is to generate the sequence, because there are more occasions where the sequence might "fail" to come with the queried one.
2) In the code you provide you both train hmm and hmm2 with the same sequence (sequences ) which is quite the opposite of the queried sequences.





hi, i have problem i have the 6 signal for each action like thinking ,move,calculate for 3 subject and each signal has 2500 sampling how to implement learing and clasification for action





Hi all, I'm a student. I've never used before HMM and I need an help.
I'm working on a project for gesture recognition, this is my application's video:
http://www.youtube.com/watch?v=PDkfgxEV8TI
I'm using DTW (dynamic time warping) for recognition, but this is very slow.
I have ten sequence of movements, I post here an example:
="1.0" ="utf8"
>
<Sequence ID_sequence="10">
<Observation ID_observation="0">
<Joint joint_element="Head">
<X>0,0681642160598825</X>
<Y>0,829331295395237</Y>
</Joint>
<Joint joint_element="HandLeft">
<X>0,704363565952119</X>
<Y>1,60185907740724</Y>
</Joint>
<Joint joint_element="HandRight">
<X>0,681642160598825</X>
<Y>1,67002329346712</Y>
</Joint>
<Joint joint_element="Spine">
<X>0</X>
<Y>0,727084971305413</Y>
</Joint>
<Joint joint_element="FootLeft">
<X>0,261296161562883</X>
<Y>3,73767118061689</Y>
</Joint>
<Joint joint_element="FootRight">
<X>0,261296161562883</X>
<Y>3,70358907258695</Y>
</Joint>
</Observation>
<Observation ID_observation="1">
.......
I work with positive and negative numbers (double) .
Can I create a HMM for these value?
How much states and characters I should use?
(HiddenMarkovModel hmm = new HiddenMarkovModel(2, 2);)
For test I use only the sequence of points for HandLeft (X and Y).







Hi all! I go back to writing for another question.
I have read your link HiddenMarkovClassifierLearning but I have got a problem.
First, I created the sequence for the motion examples with my body points (Head, Hand Left, Hand Right, Spine, Foot Left, Foot Right)
I have a struct with type double[][][]
double[] Head double[] HandLeft
...
double[] FootRight
After, I put these double array in another double array
double[][] action = new double[][]{
Head, HandLeft,
...
FootRight,
};
Finally, I have put this double[][] array in double[][][] for create my library sequences.
double[][][] sequences = new double[][][]
{
new double[][]
{
Head, ....
FootRight,
},
.......
.......
.......
new double[][]
{
Head,
....
FootRight,
}
};
I have wrote this code for HMM's learning.
int size = sequences.Count;
int[] num_labels = { 0, 1, 2, 3, 4,...., sequence.Count1 };
MultivariateNormalDistribution initialDensity = new MultivariateNormalDistribution(size);
HiddenMarkovClassifier<MultivariateNormalDistribution> classifier = new HiddenMarkovClassifier<MultivariateNormalDistribution>(
classes: size, topology: new Forward(size), initial: initialDensity);
HiddenMarkovClassifierLearning<MultivariateNormalDistribution> teacher = new HiddenMarkovClassifierLearning<MultivariateNormalDistribution>(
classifier,
modelIndex => new BaumWelchLearning<MultivariateNormalDistribution>(
classifier.Models[modelIndex])
{
Tolerance = 0.0001,
Iterations = 0,
FittingOptions = new NormalOptions()
{
Diagonal = true, Regularization = 1e5 }
}
);
but when I go to launch the Run method I have a problem
logLikelihood = teacher.Run(sequences, num_labels);
where do I have wrong?
Somebody can help me please? Thanks
modified 15Dec12 13:30pm.





Hi there,
I think you are misunderstanding the concept of a feature vector. Each double[] observation should have the form <Head, Hand Left, Hand Right, Spine, Foot Left, Foot Right>. At a given instant t, your observation should be initialized something like
double[] observation = new double[] { Head[t], HandLeft[t], HandRight[t], Spine[t], FootLeft[t], FootRight[t] };
Besides, you have not told what problem do you have when you are calling the method "Run". If it is giving something like a DimensionMismatchException or an IndexOutOfRange, then it means you are not passing the sequences of observations in the expected form.
Please see if it helps.
Best regards,
Cesar






Hi,
The AggregateException usually shows the actual exception which caused the issue in the InnerExceptions public property. Please take a look at it to see what it reports. But in any case, the problem should likely be the specification of the feature vectors as I mentioned. Did you try changing it to the way I suggested?
Best Regards,
Cesar





I don't understand who I should do with double[] observation...
Cesar, thank you very much for precious advice.
Maybe these can help for understand my structure:
Screen1
Screen2
screen3
modified 15Dec12 18:55pm.





If I understood the example you gave, you were transforming your arrays of head, hands and etc positions as double[][] by doing:
double[][] sequence =
{
Head,
HandLeft,
HandRight,
etc
};
But what you really need to do is to build the feature vectors like this:
double[][] sequence = new double[numberOfObservationsInYourSequence];
for (int i = 0; i < sequence.Length; i++)
sequence[i] = new double[] { Observation[i].Head.X, Observation[i].Head.Y, Observation[i].HandLeft.X, Observation[i].HandLeft.Y, ... };
I hope this makes it more clear.





Yes, this is very more clear. Thanks
I have modified my old post with photo of my double[][][] structure.
screen1
screen2
screen3
Now i try to modify my code, I hope it work.
modified 15Dec12 19:25pm.





Cesar, with your advices, HMM is working. But the recognition is wrong.
HMM recognizes wrong movements, (es drink instead of walk ecc..)
Is this a problem with constructor of the classifier or for a small number of examples?
NormalDistribution density = new NormalDistribution();
var classifier = new HiddenMarkovClassifier<NormalDistribution>(library.Length, new Ergodic(2), density);
var teacher = new HiddenMarkovClassifierLearning<NormalDistribution>(classifier,
modelIndex => new BaumWelchLearning<NormalDistribution>(classifier.Models[modelIndex])
{
Tolerance = 0.0001,
Iterations = 0
}
);
library.Length = //number of action how walk, drink, ecc...
modified 16Dec12 11:31am.





The first argument of the constructor is the number of classes. It should be the number of different actions you are trying to classify, i.e. if you are trying to distinguish between walking and drinking the number of classes would be 2.
For gesture classification, it would also be better to change from using a Ergodic topology to a Forward one. Just use "new Forward(2)" instead.
And finally, to learn an HMM correctly you need several examples of each class. If you have just a single example of each class it won't work well.
Hope it helps!
Cesar






You really should be using Forward instead of Ergodic . But in any case, this is not how you train the model; you should pass all sequence/label pairs at once, not in batches. Besides, I am not sure why but you seem to be swapping indices i and j , and it is not clear where the i comes from in the first loop, and the j comes from in the second loop.
So, in short, just call the teacher.Run(learningSequence, labels) once, and if your sequences are correctly structured it should do the trick.
Regards,
Cesar






Hi, I'm a final year university student and currently doing my final year project. It is basically gesture recognition system. I want to track dynamic hand motions and identify hand gestures. I had try to implement that using HMM. But I couldn't identify starting and end points of the gesture. is any one know how I can track the stating and end points of the gesture. are there any implementations for achieve this. Please help me to short out this problem and it was a great help for me...
Thank you..





Hi there,
Detecting the start and end points of a gesture is another problem altogether. This problem is known as gesture spotting, and I don't think there is a definite and default answer for solving it yet. One possible approach is to use Lee and Kim's gesture spotter[^] based on threshold models. Please let me know if you have found something that works better.
Best regards,
Cesar





Thank you very much Cesar for your guidance. I tried to implement Lee and Kim's gesture spotter. but I couldn't do it. Did you have any implementation for gesture spotter ?
Regards,
Prasad






Thank you for this great tutorial and code example!
Really helped me a lot with understanding hidden markov models.





Hi,
Completely new to C#. Programmed in c/c++ 6 years ago, then matlab since. Need faster hmming, so came across this, and c# as a good language. However, this does not compile, giving the error: Error CS0246: The type or namespace name `OleDbConnectionStringBuilder' could not be found. Are you missing a using directive or an assembly reference? (CS0246) (HMM)
What am I doing wrong? Any help would be great. Thanks.
Ian





Hi Ian,
The OleDb* classes are only required to read Excel files. If you are using it under OSX, it would be understandable there would be no support for it. To fix this error, you could remove the OleDb dependences and insert your data another way (such as using .csv files). In any case, I would recommend using the latest version of this code available in the Accord.NET Framework. However, the problem is that it most likely won't compile under Mono as well. But you could try loading the assemblies directly, without recompiling.
If you really need it I could try working on the Mono support again. At some time the framework did compile on Mono, but since there wasn't much interest on this feature it gradually faded away after some releases.
Best regards,
Cesar





Hi Cesar,
I kinda figured as much, but hoped that it was something really dumb that I was doing. I'll have to do a bunch more learning to implement .csv or other data type input so that It will work with your function, but I suppose that that will do me well... Unless its quite trivial for you to implement mono support, I'll (continue to) work more to see if I can get it to work via other input routes. Thanks!
Ian





Hi Cesar
Thank you very much for you previous answers.
Could you please comment if your code implements autoregressive HMM (regime switching is another name) as described in Rabiner 1989 tutorial. Would it be difficult to add it if it is not implemented?
Thank you,
Sergey.





Hi,
Sorry for noticing the question this late. I have heard about autoregressive HMMs but I don't know much about them. I can't really say if it would be difficult or not because I haven't tried, but since the framework already contains codes for many related algorithms such as the Forward, Backward, learning and etc I suspect it would be easier to achieve something starting with the framework than from scratch.
Best regards,
Cesar





Hello César
Thank you for sharing your code. I am a new C# programmer and new to HMM but have some knowledge of C++.
I have the following question:
Using this code how do I make prediction for the next symbol. Let's say I have very long single sequence (10000 samples) with about 2^k symbols (64 is common) and a few hidden states (may be 410). Given the current state I want to calculate probaility of the next symbol. In your example you have more than one sequences, I have only one but very long. In your example you look for proability of the particular sequence but I would like to get only probability of single symbol but from current location.
Thank you very much!





Hi ssamson,
The latest version is this code, available in the Accord.NET Framework[^], has a "Predict"[^] method which can be used to predict the next observation in a sequence.
It works by calculating the likelihood of the sequence you gave, plus all possible variations for the next symbol, then selecting the one with the highest likelihood. You can browse the specific source code for the prediction method here[^], if you would like to.
Please keep in mind, however, this isn't always a very useful prediction due the limitations of the Markov assumption.
Best regards,
Cesar





Thank you Cesar. I was confused because all your sequences starting from 0 have high probability but all sequences starting from 1 have low probability, so in your example why sequence 11 have low probability, it can be just a part of your HMM, for example, starting from the middle (0111 sequence).
Could you please give me a more general recomendation. In my example I have descrete symbols and in reality I have continuous that I discretized. This symbols are derived from wavelet coeficients. Is there a more general approach that will be able to process contunuous symbols to produce prediction. These are not ARMA time series so Markov approach seems the best.





Hi ssamson,
It isn't part of the HMM because, by default, the HMMs were created with forwardonly topologies. I just realized the code in this article was a bit outdated and this wasn't entirely clear. In the supported framework version you are able to specify different topologies[^] in the model constructor.
And about your data, instead of discretizing your samples you could instead use continuousdensity hidden Markov models[^]. Those HMMs are able to work directly with continuous observations. The drawback, however, is that you can't anymore predict an observation by testing all possible symbol combinations, since those are now continuous. The framework has a version of the "Predict[^]" method for continuous distributions based on the mode for the next state distribution.
But again, this isn't always useful. There are more complex schemes for finding predictions based on sequence alignment which may work better, such as the ones shown in this thesis[^] or this paper[^]





Its nice... Very helpful..





Its nice tutorial for beginners.I have downloaded source code from given link. But I didn't get how to run this program.
Can you help me with this problem?
waiting for your reply..





Hi,
The latest version of the downloadable executable can be found in Google Code[^]. If you would just like to run it, you can download the .rar, then open the HMM.exe executable. You can load some test data by clicking File>Open. By default, it will open a folder with an "example.xls" file. Now, you can press "create" to create the classifier for the file loaded. On the second tab you can press "start training" to train the just created models. Then, finally, on the last tab, you can test the model in your own data by clicking "Evaluate". Please note this is just a sample application, to demonstrate how the code can be used.
If you would rather develop your own application with this software, please take a look on the full Accord.NET Framework[^]. It includes the most uptodate version of this code, with the latest fixes and enhancements. Plus it has a getting started guide[^] which can help creating your own applications.
Best regards,
Cesar







General News Suggestion Question Bug Answer Joke Praise Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

