How can I use Markov Chains to predict a user's next choice of color?

[EulerInt]

Hi everyone,
I'm more of a programmer than a mathematician/physicist. However, my query on google and such, led me here and I think someone might be able to help me. I'm trying to create a program that guesses the next colour the user will select, based on previous selections. I've come across Markov Chains, and this seems like the tool I need. However, after reading a lot on the theory, I'm having difficulty in implementing it. Basically, I have five colours. (Red, Green, Blue, Yellow, Black). The user selects a colour, then another one and so on. After N amount of colours chosen, the user selects "predict". I want the program to then guess what the next colour would most likely be based on the previous selections. How do I calculate the values of the transition matrix each time the user selects a colour? And how do I allow the program 'learn' that the user likes a particular order? Sorry if this isn't enough information, but I'll be happy to elaborate on any points I've missed.
Thanks for any help

 

[HallsofIvy]

You are going to have to have some "theory" about how the person is choosing. If the person is choosing at random, no one color is more likely to be chosen. You might just identify the color that has been chosen most before is the color most likely to be chosen again. But that's not a mathematics issue.

 

[EulerInt]

Thanks for the reply. I have chosen colours as a simple example, so that I can test any code, before it moves onto more complicated areas. I am assuming that the user is selecting the colours in some fashion as if the colours represented something more complicated. Simply taking into account which colour has been chosen the most would negate the whole issue of what to predict since it's the selection is assumed not to be random. For example, user A tends to select green a lot more after an combination of Red, Yellow, but never after black. Therefore, in the transition matrix, the probabilities would be higher in favouring red+yellow combination, but almost zero after only having selected black. I hope I'm making sense

 

[CRGreathouse]

It all depends how many choices you're willing to look back. If you're willing to look 0 choices back, calculate the % of the time that each color is chosen and choose the color with the highest number. If you're willing to look 1 choice back, you need to track of 5^2 possibilities instead of 5: black -> black, black -> red, ... green -> green. Similar to the case of 0 choices, remove all but the 5 corresponding to the the current last pick and choose the most likely case.

Actually I'm not sure what the problem is; this seems straightforward to me.

 

[EulerInt]

lol when you put it like that, it does seem easy. It's just that I'm completley new to Markov models and all technical papers I've read mention various algorithms such as Baum-Welch, Viterbi etc... This is what is confusing me. Maybe I've jumped into the deep end, but what are these algorithms for and when would I use them? For example, hidden markov models are said to more efficient, and accurate, than normal Markov Models. However, when it comes to implementing, in this case, what would be hidden? The states are known, the colours are the observed states, so what's hidden? I guess I've missed something here, so if you could shed some light, I would be really grateful

 

[Focus]

I don't see why you need to read about Markov Chains, it is waaaay to theoretical for what you are doing, however I will try and help out by discribing your model. You have a discreate Markov process ,X , that has a finite state space of colours (say {red,green,blue} which I will call I). Now the MP (Markov Property) is that $$Pr(X_t=a|X_{t-1}=b, X_{t-2}=c,...,X_0=d)=Pr(X_t=a|X_{t-1}=b)$$. What that is saying is that if you have all the information up to point t-1 (if the user chose t-1 colours) then what effect the next choise is the t-1 th choise, the ones below do not have an effect.

As for the code all you need to do is store the last colour the user chose in a variable. Use a switch statement to see which one is predicted next.

count=0
last=users_last_colour_choise;
predict=0

switch(last)
red: if(predict<cred){predict=cred(last)}
green: if(predict<cgreen){predict=cgreen(last)}
blue: if(predict<cblue){predict=cblue(last)}

cred(last) is the probability of going from last to red.

If you want the code to "learn" then you need to nest more if/switch statements to count how many times user went from one colour to an other.

Hope this helps.

 

[CRGreathouse]

lol when you put it like that, it does seem easy. It's just that I'm completley new to Markov models and all technical papers I've read mention various algorithms such as Baum-Welch, Viterbi etc... This is what is confusing me.

Don't worry about all that, just code up a basic model as Focus and I suggested. Your problem isn't a hard one and doesn't require any special algorithms.

 

[EulerInt]

Hi Focus,
Thanks a lot for your reply. I think I understand it more clearly now, but there's still something that I don't see. In this example, having a few colours and such is fine. However, in the real application, the user can have thousands of categories. Is there a way to make predictions more efficient, as having to loop through each one would be computationally expensive?
Thanks again!

 

[EulerInt]

Don't worry about all that, just code up a basic model as Focus and I suggested. Your problem isn't a hard one and doesn't require any special algorithms.

I've managed to knock up a quick program, which can predict the next colour, based on which colours have been previously picked the most. My current program always assume the pair is Red-X (where X can be Red, Green or Blue), just for simplicity sake. But, if I have thousands of colours (or categories), my program would be highly inefficient as it would have to scroll through each combination possible.

 

[Focus]

Hi Focus,
Thanks a lot for your reply. I think I understand it more clearly now, but there's still something that I don't see. In this example, having a few colours and such is fine. However, in the real application, the user can have thousands of categories. Is there a way to make predictions more efficient, as having to loop through each one would be computationally expensive?
Thanks again!

You could use a sorting algorithm to sort an array of probabilities, for example set an array like
[0.2,"red_blue"]
[0.5,"red_green"]
[0.3,"red_red"]
and so on. Quicksort for example has complexity nlogn. Other than that I don't think you could make the algorithm more efficient. I think you might be underestimating computers, they are pretty fast in nlogn complexities for when n is below 10 000.

If you post your code (or which language you are using), I could help a little more.

PS. I hope you license it GPL :)

 

[EulerInt]

lol GPL ftw! :)
I'm using C#.Although, this problem doesn't seem to complicated, I'm still not sure why certain programs require deeper knowledge. For example, I saw this video:

Would they be using the same method?

 

[quadraphonics]

lol when you put it like that, it does seem easy. It's just that I'm completley new to Markov models and all technical papers I've read mention various algorithms such as Baum-Welch, Viterbi etc... This is what is confusing me. Maybe I've jumped into the deep end, but what are these algorithms for and when would I use them? For example, hidden markov models are said to more efficient, and accurate, than normal Markov Models. However, when it comes to implementing, in this case, what would be hidden? The states are known, the colours are the observed states, so what's hidden? I guess I've missed something here, so if you could shed some light, I would be really grateful

Indeed, there is no clear candidate for a hidden variable in the problem you're describing, and so Hidden Markov Models are not appropriate here. As such, you don't have to worry about either the Baum-Welch or Viterbi algorithms, as these apply only to Hidden Markov Models.

 

[^_^physicist]

Since you are trying to use previous data, have you considered a Neural Net learning algorithm. My computational physics professor found one in a standard introductory computational physics book that may work for you.

 

[EulerInt]

I initially looked at neural networks, but I wasn't quite sure if it would be suitable or as efficient. Did your professor describe the back propagation method, or was it another variation?
Thanks