# Trouble applying hidden Markov models

Edit: I updated the question to hopefully make it more easy to understand. I think it was overly complex.

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 estimate what’s currently 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.

• This may or may not be a hmm problem. I personally thought it was a neural network problem and another person suggested particle filter issue. Although the majority of people I spoke with said hmm, I have no attachment to any specific solution(just want something that works). Jan 2, 2012 at 16:55

## 2 Answers

The Markovian property of the problem means that each new basket depends on the changing fruit prices and the currently held basket only.

The real problem in your case, is that you do not know the probability of selecting new fruits to place in the basket. This distribution is changing with time since fruit prices are not constant.

You can use what you have learned to estimate each users current basket. Either you estimate the most probable basket they current have or you can estimate the probability distribution of the basket (i.e., with prob. p1 their basket contents is X1, with prob. p2, X2, etc.).

Next, you need to give some probability distribution to the next state (future basket) given the currently known basket contents. This may be difficult because prices are changing and this distribution is changing with time.

The output of multiplying P(current basket)*P(next basket|current basket) will give you the probability distribution of the user's future basket.

### Some more information

Define C[n] the cost of the basket at time 'n'. Define B[n] the user's basket at time 'n' And say that given P[n+1] (price list at time 'n') and B[n], you have a set of possible baskets that are based on small changes of B[n] so that the price is P[n+1]. This is S[n+1] -- the belief state at time n+1 (the set of all possible B[n+1] values).

You start with S[0] with is the set of all possible baskets given C[0] the total cost and P[0] the price list at the beginning of the game.

Now you get C[1] and P[1] and for each possible basket in S[0] you determine possible next baskets that fit the given cost C[1] and prices P[1]. The set of all these baskets is S[1].

Now, some possible baskets in S[0] will have several possible following baskets. But some baskets in S[0] will no possible following basket. This is true only if the rules ensure that the user can only make small changes (say change N items for N smaller than the size of the basket). So this is how you eliminate possible baskets from S[0]. Given what you see now, they are no longer possible.

When you continue like this, you will find out that sometimes information given at time 'n' will reduce your belief space not only at time n-1 but also n-2 and may be more.

Essentially, you are looking for sequences of baskets that are possible given the list of P[n] and C[n] from 0..current time. Each of these sequences is equally likely.

• Thanks for the great answer, ninrodm. I think I wasn't totally clear in my question, I don't care about the users future basket, I am merely trying to predict their current basket. I'm not quite clear how to get the estimation of the current basket. I have a list of all possible baskets that they could have, but not really sure how to plug those in to narrow down to make a guess. Dec 31, 2011 at 20:41
• opps, I didn't realize you updated your answer. Wasn't alerted, sorry. Thanks for the update ninrodm. I'm a newbie to algo's so I took some time to study your answer. Not sure if I understood it correctly, but I think I'm already doing what you described. Over time my list of baskets stabilize(few new ones are added and a few are dropping off), but I'm still not sure how to estimate what is most likely based on this universe of baskets. I thought hidden markov models could do that but I'm not sure how to apply. Sorry if I don't fully understand, I'm pretty new but if i'm missing anything Jan 2, 2012 at 3:54
• if i'm missing anything, let me know and I'll research/read up on it and hopefully be able to apply what your saying. Right now, I don't see how to apply what your saying to get either probabilities or estimations. I feel the estimates could train itself by knowing if it was wrong or not(by seeing the next value of the basket didn't work based on its estimation), just not sure how to apply that. Jan 2, 2012 at 3:55
• Without putting probabilities on the players selections (i.e., with probability p[i|j] he chooses to select new basket i given that he is currently holding basket j) you cannot put any probabilities on the baskets. So what you have done up to this point (narrow down the belief space) is the best that you can do. If you assume players have some preferences (say, they tend to prefer apples to oranges) you can try learning these probabilities (assuming they do not change over time) and use that information to estimate more probable baskets. Jan 2, 2012 at 10:38
• I highly respect what you write and you seem very knowledgable, but I disagree. For example, when using graphs(like I did initially), each possible basket was a node and each basket was connected to the baskets it was similar to the next day. Without me creating any preference probability, I had more edges going to certain nodes(those nodes weren't right but they were somewhat close). I'm not sure but I suspect there's something that, unlike my graph, takes into account price changes to figure out probability also. Jan 2, 2012 at 16:16

When I go to the grocery store I don't say to the cashier "Here's \$39, guess what I bought". Record the items that the user picks.

If the challenge of the game is merely that you are requiring the player to do the math in their head, then don't display the sum to the user until after they submit their selection.

• It's more of a programming/algo learning exercise for myself. Dec 31, 2011 at 8:15