Markov Model decision process in Java

Question

I'm writing an assisted learning algorithm in Java.

I've run into a mathematical problem that I can probably solve, but because the processing will be heavy I need an optimum solution.

That being said if anyone knows an optimized library that will be totally awesome, but the language is Java so that will need to be taken into consideration.

The idea is fairly simple:

Objects will store a combination of variables such as ABDC, ACDE, DE, AE.

The max number of the combination will be based on how many I can run without slowing down the program, so theoretically 100 let us say.

The decision process will generate one random variable per iteration. If the variable generated is part of one of the combinations, eg. 'A' which is part of ABDC and ACDE, than the propensity for C and B (or any following letter in a stored combination) will increase.

To make things a little more clear, let's assume that 'A', 'B', 'C', 'D', and 'E', are the only possible variables. The truth is, there will be more like 12 or 14, but that maximum will also depend on how many I can process without lag.

Since there are five possible variables, it will generate a weighted 1/5 random roll for the first iteration. If that roll turns out to be 'A', then in the next iteration 'B' and 'C' will now have 2/5 propensity instead of 1/5.

If the next iteration were to generate 'B', the 'D' propensity will increase to 3/5. Note: the relationship is exponential; realistically, it won't be 1/5 but a slight boost like 10%, which will snowball to say 50% if it reaches the 4th variable in a sequence.

Now, in Java, I can probably achieve this functionality by tracking all of the stored combinations for each object. I was thinking that by distributing the tracking process in small steps across each iteration, it shouldn't be too slow.

Another solution would be mapping all of the possible combinations and their potential propensities. This will of course simply require a search function but also presents problems in calculating all of the possibilities and storing somewhere, probably in a file.

It has been suggested that I should use a Markov Model and/or library, though I am not too familiar with this type of mathematics.

How can I compute this process quickly in Java?

.

Example >>>

Only one sequence ABC.

For three numbers, chances begin equal so it would look something like rand(1,3)

If A is the result, we increase the likelihood of B, because it is the next letter in the sequence. Let us say we double it.

So now the chances are: A=1/4, C=1/4, B=2/4

The function will now look like rand(1,4) where the results of 3 and 4 both represent option B.

If the next result is B we want to increase the likelihood of C because it is the next character in the sequence, but twice as much as it was increased last time (exponentially)

Chances are now something like A=1/6, C=1/6, B=4/6

The function is now rand(1/6) where values 3, 4, 5, 6 represent C.

Answer 1

This link provides a Java implementation of solving Markov Decision Processes (MDPs). To demonstrate how to use the Java package, it shows an implementation of the adaptive dynamic programming algorithm. The code serves several purposes, like:

• Firstly, you can use it as a base for your training method. 

• Secondly, if the package as a whole doesn't fit your requirements, you can use part of it, e.g., the parser of the MDP description file and the MDP class itself. 

• Thirdly, if you want to start from the very basic all by yourself, you can use the code as a reference and compare your results against those produced by the code. 

• Lastly, a real Java implementation of various algorithms in the textbook helps you understand the material.