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:
- States = are the possible baskets I have created for each day
- Observations = are the final value of the basket entered by the user
- 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.
- 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.