Possible Duplicate:
having trouble applying hidden markov/machine learning models

Happy New Year!

I’m having a problem applying hidden Markov models to a game I’m building to learn about programming.


I have a game that tries to intelligently guess what’s in your shopping basket. As a user, you are given random prices for items and then only provide the total value of your basket. Here’s an example:

         Value(P)quantity(day1)(Q)    Value(P) value(day1)(Q)
Apple    1      100                   2        200
Pears    2      20                    1        20
Orange   3      1                     3        3
Total(T)        121                            223

And so on. All my program is given is the Value(P) and Total(T) to be able to guess what the quanti-ty(Q) is. A restriction I put is that the baskets cannot change more than 5%, but ultimately I’m not sure if it matters because the human is not adversarial and I think a pattern should emerge over the turns.

Where I am now:

I generate all possible values that Q can be based on P and T(generates many many possible baskets) and then eliminate all the impossible baskets. So over the turns I have a few baskets disappearing and few new ones appearing. I’m trying to figure out which basket is most likely(at that given time, and hopefully over the turns it gets more accurate).

My problem:

I’m having problem applying hidden markov models to this problem. I have been told by various sources that this is a hidden Markov model. I’m being told the sequence I’m looking for is a set of hidden states(quantity). Here’s an explanation I got when I cross posted: You have a sequence of hidden states, characterized by the number of each object at time-step T. You have a nice known linear map from your hidden state to an observed value, and a known transition function from states at T to states at T+1. There are strong Bayesian methods to find the hidden states -- but you can expect them to take a long time to converge.

So I took the time to learn about HMM’s but I’m having a lot of trouble fitting in my problem to the variables required for HMM’s. Here’s what I have so far:

  1. States = are the possible baskets I have created for each day
  2. Observations = are the final value of the basket entered by the user
  3. Transition probability = I don't know if I should leave it at equal weighting for all of the states or if I should be calculating this. I assume this should be changing every turn as certain baskets become extremely unlikely as certain ones become very likely.
  4. Emission probabilities: Not sure what to put in here because all of the possible states(for each turn) have the same final value.

Parallel problems:

I’m not sure if this helps but I want to help find the solution so I thought of a parallel problem that maybe helpful(if you have any insight to this problem it may help with mine). I’m thinking character recognition is simlair because there are a universe of words(in my case baskets of fruit) and the program needs to figure out which word(basket) is most likely given the way the user wrote a sentence. Of course it might not be totally accurate at first but it should train itself as it makes mistakes and is corrected(in my case if it picked the wrong basket which is no longer available on the next turn). I though this would create some kind of probability distribution.

To learn, I have coded this in java and python, if it helps but I don’t care about the language, I’m looking for the logic. I hope someone can help me figure out this problem. Its my first real program and has been a great challenge but a bit frustrated at this part. Its very challenging but I think this is a good learning exercise.

Thanks in advance and sorry for the long question. I tried to add as much info to make your life easier to help but if I missed anything or you have any questions please let me know!

Thanks again!

  • $\begingroup$ At time T do you know what was in the basket at time T-1? In other words do you get any sort of feedback as to the accuracy of your previous prediction? $\endgroup$ – JonnyBoats Jan 2 '12 at 4:59
  • $\begingroup$ Not as the game currently is. Only given is price and total. If I get the basket, it would make the game really easy to predict so I didn't want to do that. If it becomes close to impossible, then I might make a rule that every x turns(maybe 100) I see how their basket looked 100 turns ago(def. not last turn though), but that is not part of the rules(I'd rather avoid it if possible because it make take the amazement factor out). $\endgroup$ – Lostsoul Jan 2 '12 at 5:15
  • $\begingroup$ The only feedback, as far as I can tell, is based on the next turn's basket value the program will know if it was wrong(if the new value isn't part of the previous estimate). $\endgroup$ – Lostsoul Jan 2 '12 at 5:16
  • $\begingroup$ For what its worth, it would seem that as defined a better approach would be particle filters. $\endgroup$ – JonnyBoats Jan 2 '12 at 6:12
  • $\begingroup$ Thanks JonnyBoats! I am very new to machine learning, I'll read up on particle filters(didn't know anything about them). Thanks for the suggestion $\endgroup$ – Lostsoul Jan 2 '12 at 16:20