Trouble applying hidden Markov models

Question

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.

Answer 1

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.

Answer 2

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.