6

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 a 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 combination of variables such as ABDC, ACDE, DE, AE.

The max number of combination will be based on how many I can run without slowing down the program, so theoretically 100 lets 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, lets 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', than 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 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. Lets 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.

bigcodeszzer
  • 916
  • 1
  • 8
  • 27
  • I'm unclear on the percents you share, as with 5 elements if A is selected B and C increase to 2/5, what are the others at? From what I've seen Marchov problems are popular in "online algorithms" and that the solutions can be figured out with use of Markov Chains... take a look at https://en.wikipedia.org/wiki/Markov_chain and see if it helps you with your problem. – James Oravec Dec 18 '15 at 22:02
  • The increase is arbitrary - I'll have to test everything to find a good increase. In the example, the other variables will remain 1/5 and the A and B would be 2/5. (The other variables are not effected) – bigcodeszzer Dec 18 '15 at 22:30
  • So instead of fractions could you think of it as number of tickets? Then sum the total? – James Oravec Dec 18 '15 at 22:32
  • @VenomFangs Not sure what you mean? They are percentages really. There are a number of ways to actually calculate the random out of the percentages, but the question is more about how to track the variable sequences ABDC and so on. – bigcodeszzer Dec 18 '15 at 22:36
  • I'm lost on how the others stay the same and b and c increase. Is a 0/5 or 1/5 after the first pick? If b is 2/5, c is 2/5, d is 1/5, and e is 1/5 then I see 6/5 which is over 100%, which if it was seen as increase of tickets and lotto style that would make more sense to me. The general description you gave makes me think the problem will be solved with a Marchov chain or a dynamic programming solution. But the problem is still unclear to me, so I can't give solid advise – James Oravec Dec 19 '15 at 02:54
  • Can you provide a full example with 3 letters? If so, I can probably help from there – James Oravec Dec 19 '15 at 03:02
  • 1
    @VenomFangs I edited in an example. – bigcodeszzer Dec 19 '15 at 07:11
  • 1
    What are you trying to achieve, i.e., for what do you need this program? I don't understand what you want to do, but I have the impression that it's something pretty standard. And btw, it's Markov Decision Process (MDP), unless you mean something totally different. – ziggystar Dec 21 '15 at 00:45
  • Its part of a reinforcement-learning algorithm. – bigcodeszzer Dec 21 '15 at 00:47
  • @bigcodeszzer, for the 3 elements, to quickly implement something like the random number generator you could use [1,2) for the 1st element, [2,3) for the 2nd, and [3,4) for the 3rd. Lastly, you have a exponential growth of tickets at the end that will be assigned to one lucky element, in which case you an assign the last portion of additional tickets, something like [3, 3+2^(round -1)) to it. So your base logic stays the same, then each iteration you get more likely of picking the item you want. If you don't allow for the same element to be picked twice then reroll if picked. – James Oravec Dec 21 '15 at 16:29
  • @bigcodeszzer, hopefully my last comment answers how to do the example you provided. I'm unclear on what more you need from here. What I described above doesn't really use anything related to the Marchov stuff though... Can you give clarification on the output you desire of this program? I see the input is the set of elements. I'm unclear on the output though. In the example of 3 elements, you run through the change of probability... which I tried to help with in the previous comment. But I'm still unsure how this affects your end result or output. – James Oravec Dec 21 '15 at 16:35

1 Answers1

1

You could write a C/C++ version if you want, and use the NDK (The overhead of the NDK is in the JNI translations from Java to C/C++ methods, but once there, they are much faster)

That is one idea. But... I don't think you have to go that far (at least to get a version that works for smaller sets) (maybe later moving to NDK might be a better option for LARGE sets)

I think you would be much better off treating this like an array of 'whole number fractions' aka... a two dimensional array for each set of action's probabilities. Meaning the numerators on the 'top row' and denominators on the 'bottom row'. Since the sets you are going to be working with are likely small, I'd think that a simple linked list of nodes where each node has its own set of probabilities would work. (These probabilities are the transition tables from S to S' from 'that' node.) 

 int[][] probs = new int[100][2];

So you can think of it as ...

1 2 1 1

4 3 4 9

as 1/4, 2/3, 1/4, 1/9 with whole integer arithmetic. This would be easier in 'some' parts of the algorithm, because you will be able to make nice helper functions for "removeColumn' (make 0/0, and skip rest of processing, etc(or however you want to represent it)) and 'adjustProbabilities()'

(you might be able to get away with a single array of numerators if you make the denominators a single int (the lowest common denominator), but I'd probably make this an optimization after getting the 2D array version working)

Then just write the 'simple' generic P, R, and V methods that interact on that data for each node. Then make them adjustable/extensible/etc with good OO design.

Then just 'play with the numbers' for the discount factor, etc.

I think this is more of a 'just take the time to test it out' more than an issue about any really complex math algorithms, etc. because from what I see, there is not 'obvious' places to optimize the core algorithms.

mawalker
  • 2,072
  • 2
  • 22
  • 34
  • I'm not sure about how exactly you mean to track the sequences. With a 2d array? – bigcodeszzer Dec 19 '15 at 07:39
  • Sorry about that, I posted this tired, and didn't make it clear. I meant each node in the graph having its own 2D array that represents the transitions from that state to the next states (S to S'), I cleaned up the answer with explanation. – mawalker Dec 19 '15 at 15:16
  • Ok, so mapping all the possibilties for each variable state ie (A,B,C...) My concern with that approach is whether or not it can sustain 10-15 different states or more. The other problem is the states change periodically in the program, so the map would have to update. – bigcodeszzer Dec 19 '15 at 18:31
  • My algorithms professors would just stare at you and say "yes and..." ;) But in all seriousness, just write 'helper functions' to do those things for you. I doubt you'll have any(many) problem. I would think that a 100 node fully connected directional graph(all nodes have 99 vertices) , would take at most... 1~2 seconds to calculate (on the very long end), because 100x100 = 10,000 calculations, multiply that by what... 5 (to account for figuring out % etc for each vertices ) You can just make a simple test and see how long it takes to do 0.5 million calculations and go from there for estimates – mawalker Dec 19 '15 at 18:43
  • Calculating the S->S' probs. seems to be a O(N^2) problem no matter what, because the worst case is the first 'draw' where you need to calculate S->S' from every node to every other Node. Then you get O( (N-1)^2 ) for the next 'draw' and it gets better from there. So build the system and then time 100,50,25,15,10 & see how long they take to do all the calcuations, I would expect that 25~50 is probably your sweet spot (unless your 'decisions' have to be made SUPER fast), also you will want to run these in a background thread on android, so as to not get ANR (Application Not Responding) – mawalker Dec 19 '15 at 18:57
  • Well I'll have to take a look for sure. I've been working on my own solution on the premise that each pattern (ABCD) only needs to have one of the states tested per iteration. If the state fails (the draw does not match), than I move the pattern into an array of 'inactive' patterns. The inactive array only needs to test the first 'state' in each pattern, and if it passes, it will move it into the 'active' array. To 'move' the patterns, I decided to create a pseudo pointer array using the indicies where the patterns are stored, so a mock-pass-by-reference. – bigcodeszzer Dec 19 '15 at 19:07
  • So basically the inactive array of indicies all get the first value of the pattern tested, and the 'active' array of indicies only get the 'next' value in their pattern tested, which I track for each pattern. If it was c++, I could just use pointer arithmetic I imagine. – bigcodeszzer Dec 19 '15 at 19:09
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/98439/discussion-between-mawalker-and-bigcodeszzer). – mawalker Dec 19 '15 at 19:13