5
$\begingroup$

I'm really new to Math so sorry in advance if this question does not make sense. Also I cross posted this on stats.stackexchange.com also.

Background:

I'm trying to learn about hidden Markov models and they seem interesting but I was wondering about the probabilities they use to generate their predictions. Most of the information I have read has probabilities already about changing states and staying in the current state.

I was on Github and looked up code(mainly python code) to understand a bit better but either they have the probabilities already computed or are calculating it based on occurrences in other documents(in the case of a spell checker, it studied a book to understand the words occurrences as well as the probability of them being beside each other).

Problem:

But I'm trying to understand the theory of figuring out probabilities for the HMM when I'm not using speech or text recognition. I'm trying to make a game which is trying to guess numbers based on a users behaviour(i.e. user is given a list of fruit prices and picks a basket of various fruits. We know the individual fruit prices and the users only reports the total cost of their basket, we then try to find the quantities of fruit they choose. They are not adversarial and cannot change their total quantities by more than 5%). My approach was to first find all the possibilities for all days, then using a graph to create edges between nodes that were within 5% and remove all improbable nodes. Now I have a range and with every turn new paths are being created and impossible ones are being removed. So within that range I am trying have a program 'zero' in on the correct solution.

I think the HMM model would be helpful for this but I'm a bit confused on the application of Baum–Welch or forward-backward algorithm to create probabilities(that I can feed into my implementation of hmm).

If it helps, I originally posted this at stackexchange (alot of details about the game itself as well code I have) . I got a very good solution, to find the nodes with the highest amount of edges as solutions. Its okay but it doesn't select a solution and if it makes a mistake it simply continues the path. I was also advised from mathexchange that this can be solved as a hidden markov model. I am basically struggling with applying it to my problem(right now figuring out the probability part. I have been told to create all paths as equally probable but I don't understand how that helps a HMM pick the most probable solution).

If anyone has any suggestions or suggested reading or sample code(I'm learning python, but I can try to understand any other code thats provided). If possible can it be explained to a layman(I think I can apply the code if I can clearly understand the theory, which apparently I do not).

Thanks in advance and sorry again if this question does not apply or is not explained correctly.

$\endgroup$
5
  • $\begingroup$ Now that I've read your other posts I agree that this is a nice HMM problem and you should ignore my earlier answers here. There are online tutorials for HMMs but yours will be a little hairier than any example; one reason is that you have essentially an infinite number of possible states, although only a finite number are allowed to follow a given state, and the one-step conditional distribution of basket buying given the previous basket has an interesting structure. $\endgroup$
    – opt
    Oct 26, 2011 at 20:17
  • $\begingroup$ Thanks HHM. I have gotten so far that I removed alot of the states that are not likely, but figuring out the probabilities is hard for me. I know all paths are equally likely but not sure how to exactly change that. All HMM examples I have seen already provide probabilities, so I'm trying to figure out if another model is needed to get the probabilities to send the HMM model. $\endgroup$
    – Lostsoul
    Oct 27, 2011 at 3:52
  • $\begingroup$ It is OK that all valid paths are equally likely. The benefit of putting this in terms of an HMM is that it gives access to the efficient HMM inference algorithms. But if you are clever enough to think of these dynamic programming algorithms by yourself, then you do not need to frame your problem in terms of an HMM. $\endgroup$
    – opt
    Oct 28, 2011 at 8:29
  • $\begingroup$ @DidierPiau Sorry about that. I just accepted an answer. Got more of the answer I was going for on another site so I posted it here. $\endgroup$
    – Lostsoul
    Oct 31, 2011 at 18:30
  • $\begingroup$ Sweet. $ $ $ $ $ $ $\endgroup$
    – Did
    Oct 31, 2011 at 19:15

4 Answers 4

Reset to default
6
$\begingroup$

One could do worse than to begin with What is a hidden Markov model? by Sean R Eddy. And these pages on Baum-Welch and Viterbi algorithms contain some links to the literature you might try.

$\endgroup$
1
  • $\begingroup$ Thank you for the great links. I will read them. I have read the wiki pages and used the examples(which are great) but the probabilities are provided. I'm trying to figure out how to create the probabilities myself(well at least the logic to do it so I can code it). $\endgroup$
    – Lostsoul
    Oct 27, 2011 at 3:53
2
$\begingroup$

You should price the different fruits as different powers of ten dollars. Then you will know how many of which ones they buy, if they buy fewer than ten of the same fruit.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you for the answer, opt. I'm not sure if I'm understanding your answer correctly but I have no control over the price of the fruit. The fruit prices are known but random. If I could control the prices this game would be boring because after their first turn I could change the numbers so largely that on the next turn their combination would be clear. $\endgroup$
    – Lostsoul
    Oct 26, 2011 at 19:24
2
$\begingroup$

When you see a shopper buy a fruit basket you should make a list of all possible combinations of fruits that cost the same as the fruit basket they bought. Rank the potential baskets in this list according to which combinations taste the best. Your best guess for the shopper's fruit basket is the highest ranked basket in this list.

$\endgroup$
2
  • $\begingroup$ I have already created all possible combinations with the current prices and total value of their basket. Then I use a graph to connect day1's possible basket to day2's if the basket didn't change more than 5%. My problem is as I get more data, how do I figure out which one is more probable? I thought I could remove possible baskets but all it does is give me less baskets to choose from. I want to figure something out that can look at the past baskets and then somehow predict what the basket currently is(or will be, based on the their users behaviour). $\endgroup$
    – Lostsoul
    Oct 26, 2011 at 19:37
  • $\begingroup$ I think this sounds impossible, but I thought about it and there's two main sources of feedback(it seems to be). One, if the computer guesses the correct number and two, if the computer's guess is totally wrong(and the node is removed on the next turn). I thought with these two feedbacks, it should be somehow feasible to apply a markov model to help it guess. $\endgroup$
    – Lostsoul
    Oct 26, 2011 at 19:39
2
$\begingroup$

Here's the answer I got on Quora, which helped explain at a high level how probabilities are decided.

There are many ways of estimating the probabilities of a hidden Markov model. But the most common is the Baum-Welch re-estimation algorithm (http://en.wikipedia.org/wiki/Baum%E2%80%93Welch_algorithm). There are two key things about this algorithm:

  • It's a kind of generalized expectation-maximization algorithm: in
    other words, you start with an initial guess of the probabilities,
    you then run the data through and adjust the parameters, and then you run it again with the improved parameters being your new initial
    guess. This type of algorithm turns up all over the place

    (http://en.wikipedia.org/wiki/Expectation-maximization_algorithm).

  • It is built on the forward-backward algorithm
    (http://en.wikipedia.org/wiki/Forward-backward_algorithm). The
    forward/backward algorithm works by taking a signle observed
    sequence, and running it through an existing HMM. For each timestep
    in the sequence, and for each state you say "Right: if I was in this state at this time, how probable was it that I got here from the
    beginning (the forward probability) and what is the probability from here that I will get to the end (the backward probability). You then work out at each state how probable it was, and then smooth the
    probability of the transitions at each state.

So basically, you apply forward-backward on each element of the training data, smoothing as you go, then repeat until the probabilities don't change much.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .