Building HMM from the data

318 views
Skip to first unread message

Krzysiek Kuriata

unread,
Apr 8, 2013, 7:10:27 AM4/8/13
to accor...@googlegroups.com
Hi. I won't paste the same question. I will just paste a link for it. If you could help me to solve my problem. Jason told me I can look for help in here:)

César

unread,
Apr 9, 2013, 10:05:35 PM4/9/13
to accor...@googlegroups.com
Hi there!

I have answered the question directly in Stackoverflow. Please see if it helps!

Best regards,
Cesar

Krzysiek Kuriata

unread,
Apr 11, 2013, 5:41:37 PM4/11/13
to accor...@googlegroups.com
Hello.
Thank you for your answer.

I have actually one more question about HMMs themselves. I have quantized my gestures into codebook with codewords 1-18 (I counted angles between sequent points and divided them onto codewords - each 20 degrees == 1 codeword - that's why there is 18 codewords:P 360/20=18).

Now I want to create HMMs. I don't know if I should use any algorithm for that (maybe Baum-Welsch)? As far as I know, I need to create transmission matrix A, initial vector v and emission matrix B.
As I understood HMMs, I need to do this for each kind of gesture (circles, swipes, squares, etc.).
Soooo now what is what:
- A - to count it I need to go through all the kinds of gestures (each kind separately) and count transitions between points and divide by sum (so I get probability matrix),
- v - same as A but I only count the number of first codewords (that begin the gesture) and divide it by sum (so I get a probability that concrete codeword starts concrete kind of a gesture),
- B - here I'm not sure - I think B is the same in all the types of gestures (it's a vector?) and it's simply the sum of all the transitions in all the kinds of gestures divided by sum (so I get the probability of concrete transition).
Could you confirm that I'm right?

What should I do next?

Thanks in advance for an answer!

Cheers, Chris.

César

unread,
Apr 11, 2013, 6:49:38 PM4/11/13
to accor...@googlegroups.com
Hi Chris,

Yeah, do achieve what you wish you can use the HiddenMarkovClassifier class of the Accord.NET Framework. It is actually a container for HiddenMarkovModels. It creates one Markov model after each gesture you are trying to model, then when you present it with a new observation, it computes the responses of all models to the given gesture, then select the class of the most probable model as the best class estimate.

If you would like to create a model for discrete probabilities, please take a look at the HiddenMarkovClassifierLearning documentation page. It has some examples on how to estimate (learn) the model from the data. It is a bit more elaborated than what you have suggested. The approach you have suggested is more akin to the MaximumLikelihoodLearning algorithm for HMMs. However, it can only be used when your states are visible rather than hidden. So I would recommend you to stay with Baum-Welch at first!

Hope it helps!

Best regards,
Cesar

Krzysiek Kuriata

unread,
Apr 14, 2013, 1:53:04 PM4/14/13
to accor...@googlegroups.com
Hey. The problem is I need to implement my own system:/ I can't use Accord.NET (I regret...). Could you answer if Im right with my HMM parameters?

- A - transition matrix - to count it I need to go through all the kinds of gestures (each kind separately) and count transitions between points and divide by sum (so I get probability matrix),
- v - initial vector - same as A but I only count the number of first codewords (that begin the gesture) and divide it by sum (so I get a probability that concrete codeword starts concrete kind of a gesture),
- B - emission matrix - here I'm not sure - I think B is the same in all the types of gestures (it's a vector?) and it's simply the sum of all the transitions in all the kinds of gestures divided by sum (so I get the probability of concrete transition).

I have a problem, because I think it looks so. But when I was reading some papers, the people say, that I need to choose the number of states (e.g. N = 10). I don't know how to choose the number of states and what are the states in gesture recognition (time steps for example?)...
So as the ppl say. I should determine the number of states (I guess e.g. N = 10 time steps), and the number of discrete symbols (arcs at my project - M = 18, my codebook).
Now I need to count probabilities for each gesture type:
- A - transition matrix - size N x N
- v - initial vector - size N
- B - emission matrix - size N x M

Which one is correct?

César

unread,
Apr 15, 2013, 5:18:01 PM4/15/13
to accor...@googlegroups.com
Hi Krzyslek,

Indeed, you have to select a number of states and number of discrete symbols in your alphabet beforehand. The number of states can often be inferred from some known characteristics of your sequences. For example, in fingerspelling recognition [1] you can use the number of letters in a given word as the number of hidden states for the classifier corresponding to this word. 

However, as I mentioned before, the problem of determining A, B and v is not plain "counting". You will have to use the Forward and Backward algorithms inside a modified E-M algorithm to estimate them (e.g. Baum-Welch) or use some other learning technique which can handle the sequences of hidden states. I think the best description and explanation I have ever seen on Baum-Welch for HMMs was given by Christopher Bishop on his book "Pattern Recognition and Machine Learning". I think if you wish to implement your model from scratch this would be a must read, as it gives a lot of information on the involved probabilities.

You can only "count" things when your model is not hidden (i.e. you know beforehand the sequence of states which lead to a sequence of observations). But I think this may not be the case in your situation. You can find more information on creating those matrices by "counting" if you look for "Maximum Likelihood Estimation" of HMMs (it is different from what you have described, by the way).

So, answering your question: if you need your model to be hidden, you can't create the parameter matrices by counting. By the way; I am not sure if this is clear to you, but a gesture classifier is actually created using a collection of hidden Markov models, one for each gesture. So, if you would like to build a sequence classifier for D gestures you will build D models, each of them with their own A_D, B_D, v_D parameters. 

Hope it helps!

Best regards,
Cesar

[1] Fingerspelling Recognition with Support Vector Machines and Hidden Conditional Random Fields - A Comparison with Neural Networks and Hidden Markov Models. César Roberto de Souza, Ednaldo Brigante Pizzolato, and Mauro dos Santos Anjo. IBERAMIA, volume 7637 of Lecture Notes in Computer Science, page 561-570. Springer, (2012)

[2] Christopher M. Bishop. Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verlag New York, Inc., Secaucus, NJ, USA (2006).

Krzysiek Kuriata

unread,
Apr 15, 2013, 5:49:48 PM4/15/13
to accor...@googlegroups.com
Ahh, I see it now. I was thinking about HMMs badly... I will do something like that: I will go through my gestures and find the longest one (in a matter of time). Now I define an interval for gesture e.g. 200ms. This interval will help me to analyze my gestures (I skip most frames, I get each frame every 200ms). I divide longest gesture time by 200ms and I get a number of hidden states (N) that is a pretty good value in my opinion (because there are as many states as frames that build the longest gesture - always between 8-12 states, because gestures are about 2s long). Now I use Baum - Welch to estimate HMM parameters like A, B and v (A is NxN, B is NxM, where M is my codebook size and v is a vector of size of N).

Thank you for the papers and you help!

César

unread,
Apr 15, 2013, 6:08:46 PM4/15/13
to accor...@googlegroups.com
I am glad it could be useful!

By the way, keep in mind that, in your gesture classifier, each HMM will correspond to a class of gestures. This means each HMM can have a different number of hidden states, depending on the gesture. If you have gestures which are complex and some that are simpler, perhaps it would help to specify more states to complex ones and less states for the simple ones.

On the other hand, you may also as well just set an arbitrary number of hidden states for all models just to start. Then you can tune the number appropriately until you get better results.

Best regards,
Cesar

Krzysiek Kuriata

unread,
Apr 20, 2013, 8:42:54 PM4/20/13
to accor...@googlegroups.com
Hi.

Could you tell me how to create matrices A, B and initial vector Pi for my classes of gestures? I tried to do this like in this paper.
- matrix A - I get my gestures from given class and I find the longest one - because e.g. 5 gestures in class "swipe left" can have different number of frames - (it's my T parameter from the paper - length of a gesture). Then I count Ai,i and Ai,i+1 elements using the formula from the paper.
- matrix B - M is my codebook size (numbet of possible observations). I set a new matrix B of size NxM with values 1/M (as in the paper).
- initial vector Pi - always size of N, and values like [1,0,0,0,...].

Is it good? I set (for now) N = 8 (my number of hidden states).

Using such created HMMs I try to execute these functions (from your tutorial): http://crsouza.blogspot.it/2010/03/hidden-markov-models-in-c.html

            int[] observationsSwipeUp = { 5, 5, 5, 5, 5, 4, 4, 16, 15, 14, 14, 13 };
           
int[] observationsSwipeLeft = { 10, 8, 10, 10, 10, 10, 11, 12, 10, 11, 12 };
           
var prob1 = _HMMs["SwipeUp"].Evaluate(observationsSwipeUp);
           
var prob2 = _HMMs["SwipeUp"].Evaluate(observationsSwipeLeft);
           
var prob3 = _HMMs["SwipeLeft"].Evaluate(observationsSwipeUp);
           
var prob4 = _HMMs["SwipeLeft"].Evaluate(observationsSwipeLeft);

Observations are copied from my input data, But here are the results:
-34,68446
-31,79409
-34,68446
-31,79409
I know I didn't teach my HMMs, because I didn't analize my input gesture data.
What to do now?
I suppose I should use Forward-Backward algorithm (e.g. Baum-Welch) to teach my HMMs.

Could you share missing code samples from your tutorial? I mean methods: 
- checkConvergence(),
- backward(),
- if you have any samples, initialization of each HMM.

It would be very helpful:) Cheers!

César

unread,
Apr 20, 2013, 9:07:39 PM4/20/13
to accor...@googlegroups.com
Hi Krzysiek!

Sure! If you would like a working example, you can download the source code of the HMM sample application. It shows how to create and train HMMs to perform basic gesture recognition. Please see if it helps.

The tutorial you linked is a bit outdated (the framework has changed a bit since then) but the documentation still have many examples on how to create hidden Markov models, both discrete and continuous. Please take a look on these two aforementioned links and check if the example helps!


Also, the framework source code is entirely available in the web. For example, here is the way Baum-Welch computes the Ksi matrix:

Here is how Baum-Welch computes the Gamma matrix and updates the A, and pi matrices:

And here is the source code for computing the Forward and Backward matrices:


By the way, also keep in mind that the models work with log-probabilities instead of actual probabilities. In order to recover the probabilities, you have to compute the exp(x) of the values. For example, if you got a log-probability of -34,68446 then it means you got a probability of exp(-34,68446) ~ 0 (almost zero).

Hope it helps!

Regards,
Cesar

Krzysiek Kuriata

unread,
Apr 21, 2013, 11:03:30 AM4/21/13
to accor...@googlegroups.com
You're my guardian angel and a gentleman!:P Thank you so much for any help!!!
I have downloaded your repository from SVN and I'm currently analyzing algorithms. I will look for some papers you used/created as a part of technical documentation on your site later (if any exist :P).

I will buy you tons of beer! :)

vasy...@gmail.com

unread,
Jul 19, 2013, 9:43:25 AM7/19/13
to accor...@googlegroups.com
Hi Cesar,

Would you have the completed ver of the Continuous HMM example, as I'm having problems running the framework rebuild binaries. Let me know of the link I can download, I already have HMM-discrete example working.

Thanks,
Vasanth

Message has been deleted

hamid.mo...@gmail.com

unread,
Dec 20, 2014, 12:50:58 AM12/20/14
to accor...@googlegroups.com
hi
Can you help me to solve the problem ?
will solve using both value iteration and policy iteration, which you are allowed to do in any way you like (by
hand or computer), but you should show all your work (including your source code or whatever else you use).
A little autonomous rover on Mars depends on its solar panels for energy. Its goal is to collect as much energy as
possible. It is close to a small hill; it collects the most energy when it is at the top of the hill, but it has a tendency to
roll off the hill, and it takes energy to get back up the hill.
Specifically, the rover can be in one of three states: on top of the hill, rolling down the hill, or at the bottom of the
hill. There are two actions that it can take in each state: drive or don’t drive. Driving always costs 1 unit of energy.
When it is at the top of the hill, it collects 3 units of energy; in the other two states, it collects 1 unit of energy. For
example, if the rover is at the top of the hill and is driving (to stay on top of the hill), its reward is 3 􀀀 1 = 2.
If the rover is at the top of the hill and drives, then it is still at the top of the hill in the next period with probability
.9, and rolling down in the next period with probability .1. If it is at the top of the hill and does not drive, these
probabilities are .7 and .3, respectively.If it is rolling down and drives, then with probability .3 it is at the top of the hill in the next period, with probability
.6 it is still rolling down in the next period, and with probability .1 it is at the bottom in the next period. If it is rolling
down and does not drive, then with probability 1 it is at the bottom in the next period.
Finally, if it is at the bottom of the hill and drives, then in the next period it is at the top of the hill with probability
.6, and at the bottom with probability .4. If it does not drive, then with probability 1 it is at the bottom in the next
period.
1 (25 points). Draw the MDP graphically, similarly to the machine example from class.
2 (25 points). Using a discount factor of .8, solve the MDP using value iteration (until the values have become
reasonably stable). You should start with the values set to zero. You should show both the optimal policy and the
optimal values.
3 (25 points). Using a discount factor of .8, solve the MDP using policy iteration (until you have complete convergence).
You should start with the policy that never drives. Again, you should show both the optimal policy and the
optimal values (and of course they should be the same as in 2...).
4 (25 points). Change the MDP in three different ways: by changing the discount factor, changing the transition
probabilities for a single action from a single state, and by changing a reward for a single action at a single state. Each
of these changes should be performed separately starting at the original MDP, resulting in three new MDPs (which
you do not have to draw), each of which is different from the original MDP in a single way. In each case, the change
should be so that the optimal policy changes, and you should state what the optimal policy becomes and give a short
intuitive argument for this.

hamid.mo...@gmail.com

unread,
Dec 21, 2014, 1:39:23 AM12/21/14
to accor...@googlegroups.com
can you help me please
Reply all
Reply to author
Forward
0 new messages