Pattern prediction using Markov Chains..
Author
Hi guys...
I really need some help here...
I have a code :
"A 0.25, C 0.125, B 0.25, A 0.25, C 0.125, B 0.25, A 0.25, N 0.0625, N 0.0625, B 0.25, A 0.25, C 0.125, J 0.0625, B 0.25, A 0.25, C 0.125, B 0.25, A 0.25, C 0.125, B 0.25, E 0.0625, A 0.25, B 0.25, E 0.0625, A 0.25, B 0.25, A 0.25, B 0.25, D 0.125, D 0.125, D 0.125, D 0.125, A 0.25, B 0.25, A 0.25, B 0.25, A 0.25, C 0.125, B 0.25, A 0.25, C 0.125, B 0.25, D 0.125, A 0.25, B 0.25, D 0.125, Y 0.0625, A 0.25, J 0.0625, C 0.125, B 0.25, E 0.0625, D 0.125, Y 0.0625, A 0.25, C 0.125, B 0.25, D 0.125, D 0.125, A 0.25, B 0.25, A 0.25, B 0.25, A 0.25, J 0.0625, C 0.125, C 0.125, B 0.25, A 0.25, C 0.125, C 0.125, B 0.25, A 0.25, B 0.25, A 0.25, C 0.125, B 0.25, Y 0.0625, A 0.25, C 0.125, J 0.0625, B 0.25, D 0.125, E 0.0625, E 0.0625, A 0.25, B 0.25, D 0.125, A 0.25, B 0.25, D 0.125, D 0.125, D 0.125, E 0.0625, A 0.25, B 0.25, A 0.25, C 0.125, C 0.125, B 0.25, "
Now, I need to compute the next 30 numbers. I know I need to use markov distributions but I am not quite sure how to apply it. Specifically, I'm confused about these things :
- What would I use for the distribution vector ?
- what would I use for the transition matrix ?
- How many steps of the transition matrix is required ? I suspect 130 is that right ?
I have found got these following statistics :
0.25 ---> 0.25 : 27
0.25 ---> 0.125 : 19
0.25 ---> 0.0625 : 7
0.125 ---> 0.25 : 16
0.125 ---> 0.125 : 9
0.125 ---> 0.0625 : 6
0.0625 ---> 0.25 : 10
0.0625 ---> 0.125 : 3
0.0625 ---> 0.0625 : 2
=======================================
Number of 0.25 elements : 53
Number of 0.125 elements : 32
Number of 0.0625 elements : 15
=======================================
Number of A elements : 27
Number of B elements : 26
Number of C elements : 14
Number of D elements : 18
Number of E elements : 6
Number of J elements : 4
Number of N elements : 2
Number of Y elements : 3
Any help would be really appreciated !!
Thanks in advance !
Author
No it is not homework.
I am trying to crack this code for work. Please help ..
I believe I can see theee finish line.. Just need a bit of assistance to cross it.
I am trying to crack this code for work. Please help ..
I believe I can see theee finish line.. Just need a bit of assistance to cross it.
Quote:Original post by VViCKiD
- How many steps of the transition matrix is required ? I suspect 130 is that right ?
Markov chains can't be used to predict the next 30 numbers with certainty. All they can do is give you the PROBABILITY that a certain number/letter will occur. For instance, you could predict the probability of two 0.25s being in a row within the next 20 numbers, or you could find the expected number of additional elements necessary to have one of each of the three numbers appear. Since you say 130 steps, I assume that you're looking for the steady-state probabilities. All this means is that, if this sequence continued for a long time, then if you suddenly stop and look at a number, it will be x with probability y. How many iterations should you undergo? Until the probabilities do not vary much. Note that not all matrices will even have a steady state though, so this may never occur at all!
Markov chains also only work on certain classes of problems (UNLESS you use certain tricks). For instance, does the next number of your sequence ONLY depend on the previous number? If it doesn't, then Markov chains probably aren't your answer. Also, is this particular sample of the code accurately representative of the probabilities of an entire message? If not, then you may want to rethink using this technique. Note that when Markov chains are used to analyze large books, LOTS of text is present. In your example, you hardly have anything to make predictions from!
Quote:Original post by VViCKiD
- what would I use for the transition matrix ?
0.25 ---> 0.25 : 27
0.25 ---> 0.125 : 19
0.25 ---> 0.0625 : 7
0.125 ---> 0.25 : 16
0.125 ---> 0.125 : 9
0.125 ---> 0.0625 : 6
0.0625 ---> 0.25 : 10
0.0625 ---> 0.125 : 3
0.0625 ---> 0.0625 : 2
Divide each element by the sum of its initial row. You might want to find the (larger) transition matrix which associates each letter with a number for a more accurate prediction. You didn't say much about your problem ...
Quote:Original post by VViCKiD
- What would I use for the distribution vector ?
Number of 0.25 elements : 53
Number of 0.125 elements : 32
Number of 0.0625 elements : 15
Divide each element in the vector by the total number of elements (53 + 32 + 15). If you want to pair the numbers with the letter next to them, that might yield a more accurate result.
EDIT: Changed post order, added more text.
VV, I did get your pm...I've just been flat out these past few days... I'll try and get to writing up an answer today or tonight.
Cheers,
Timkin
Cheers,
Timkin
Author
Timkin ... you're a legend mate !!
I will be looking forward to hearing from you soon...
Cheers !!! Hip Hip Hooray !!!
I will be looking forward to hearing from you soon...
Cheers !!! Hip Hip Hooray !!!
Author
Thanks a GaZillioN mnansgar !!!
I have tried those approaches that you have mentioned. i had the following transition matrix without success...
[27/53 19/53 7/53 ]
[16/32 9/32 6/32 ]
[10/15 3/15 2/15 ]
I know the associations of letters to numbers. That is :
A 0.25
B 0.25
C 0.125
D 0.125
E 0.0625
I 0.0625
J 0.0625
N 0.0625
These letter to number associations are always correct.
One thing I don't understand is that if the probability of going from state 0.25 to 0.25 is always the greatest, wouldn't we always see consecutive sequence according to the markov chain ?
Eg. 0.25 -> 0.25 -> 0.25 -> 0.25 -> 0.25 ......
Also what other "special techniques" would you be talking about ? I have heard of the Baum Welch algorithm and the Viterbi algorithm". Not sure if it applies to this problem.
I've noticed that on a larger 400 element dataset, the numbers are a little more accurate to the occurences of the letters. Eg. A occurs ~100 times and C occurs ~50 times...
But there are certain states that can not happen. For a, the possible state transitions are
A-> B (0.25)
A-> N (0.0625)
A-> C (0.125)
A-> J (0.0625)
Now according to Markov transition matrix, each row of the matrix has to equal 1. This is not true of 0.25 + 0.0625 + 0.0625 + 0.125...
So I am confused.. .
Cheers..
I have tried those approaches that you have mentioned. i had the following transition matrix without success...
[27/53 19/53 7/53 ]
[16/32 9/32 6/32 ]
[10/15 3/15 2/15 ]
I know the associations of letters to numbers. That is :
A 0.25
B 0.25
C 0.125
D 0.125
E 0.0625
I 0.0625
J 0.0625
N 0.0625
These letter to number associations are always correct.
One thing I don't understand is that if the probability of going from state 0.25 to 0.25 is always the greatest, wouldn't we always see consecutive sequence according to the markov chain ?
Eg. 0.25 -> 0.25 -> 0.25 -> 0.25 -> 0.25 ......
Also what other "special techniques" would you be talking about ? I have heard of the Baum Welch algorithm and the Viterbi algorithm". Not sure if it applies to this problem.
I've noticed that on a larger 400 element dataset, the numbers are a little more accurate to the occurences of the letters. Eg. A occurs ~100 times and C occurs ~50 times...
But there are certain states that can not happen. For a, the possible state transitions are
A-> B (0.25)
A-> N (0.0625)
A-> C (0.125)
A-> J (0.0625)
Now according to Markov transition matrix, each row of the matrix has to equal 1. This is not true of 0.25 + 0.0625 + 0.0625 + 0.125...
So I am confused.. .
Cheers..
Quote:Original post by VViCKiD
I have tried those approaches that you have mentioned. i had the following transition matrix without success...
[27/53 19/53 7/53 ]
[16/32 9/32 6/32 ]
[10/15 3/15 2/15 ]
One thing I don't understand is that if the probability of going from state 0.25 to 0.25 is always the greatest, wouldn't we always see consecutive sequence according to the markov chain ?
Eg. 0.25 -> 0.25 -> 0.25 -> 0.25 -> 0.25 ......
Maybe I should be more specific about the algorithm :-)
0.25 0.125 0.06250.25 [27/53 19/53 7/53 ]0.125 [16/32 9/32 6/32 ]0.0625 [10/15 3/15 2/15 ]To "predict" the next 30 numbers, you'd do a random walk through this transition matrix. So, your initial sequence ends as follows: "C 0.125, C 0.125, B 0.25". Hence, your starting state is "B 0.25". Now, choose a random number between 1 and 53 (inclusive). If the number is between 1 and 27, then your next number is 0.25. If it is between 28 and 27+19, then your next number is 0.125. Else, it is 0.0625. Now, your current state is this number. Proceed as we did above by choosing a random number between 1 and (53 or 32 or 15), then select the next number, and so on until you have 30 numbers. This is called a random walk.
The problem (as you may see already) is that at each state, there are three choices for the next number. Even if the next following unknown numbers have the EXACT same transition matrix, we still cannot precisely predict what those numbers will be.
Quote:Original post by VViCKiD
Also what other "special techniques" would you be talking about ? I have heard of the Baum Welch algorithm and the Viterbi algorithm". Not sure if it applies to this problem.
Many techniques exist which allow you to get past the "Markov property" (i.e. a future state is only dependent on its previous state). Look up 2nd or higher order Markov chains (which basically cheat by collapsing previous state data into each state to get a larger transition matrix). The second necessary assumption I alluded to earlier is that your data must satisfy the "stationarity property" (i.e. the probability of a certain state coming after a certain one must be the same at all times). Since your sample size is so small, I really doubt Markov chains would be a good technique to solve your problem, since the small data size most likely does not satisfy either of the above properties (the first since it's a code, and codes are generally in some sort of language which has larger units than letters).
Quote:Original post by VViCKiD
But there are certain states that can not happen. For a, the possible state transitions are
A-> B (0.25)
A-> N (0.0625)
A-> C (0.125)
A-> J (0.0625)
Now according to Markov transition matrix, each row of the matrix has to equal 1. This is not true of 0.25 + 0.0625 + 0.0625 + 0.125...
This isn't a transition matrix, so the rows won't sum to one. Remember how we constructed it before? Make a frequency table of A->B, A->N, ... then divide each element of that row by the total count.
EDIT: grammatical (e.g. -> i.e.)
[Edited by - mnansgar on November 28, 2005 9:23:20 PM]
Author
mnansgar, once again ... Thank you very much for your response ..
Thank you very much for your response ! I think I will try re-making the frequency table of A->N based on the calculated probabilities in the sample data...
I will also try looking at particular sequences of events...
I will let you guys all know how this goes..
Cheers !
Thank you very much for your response ! I think I will try re-making the frequency table of A->N based on the calculated probabilities in the sample data...
I will also try looking at particular sequences of events...
I will let you guys all know how this goes..
Cheers !
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
