Hi everyone, I'm researching predictive AI, but I'm trying to figure out whether I should be looking into "inference" or "prediction" topics. Basically, I plan to use the following situation in the project. The user is a character who jumps from one colored square to another. (There can be a huge number of colors). The AI enemy has to try and guess which direction will be the next one based on the past trends. However, it's not as simple as calculating how many times the user has jumped from one color to another because of the number of colours as well as other factors that are taken into account. Lets say there are 5 other factors that need to be taken into account (such as current weapon held), a simple matrix would be too large and inefficient. I've read about Markov Models but they also seem to just be a large matrix and Baye's theorem? Are there any particular methods/topics I should be looking into for this? Some sources seem to use 'inference' and 'prediction' interchangeably, which is slightly confusing lol. Thanks for any advice

Hi,

As a side remark, humans can't distinguish that many colors, so a game with a "huge" number of colors may be difficult to play in the first place.

That aside, the real question seems to be, what information *can* you use to predict human moves? For example, is it the case that the human will use similar colors in a similar manner? Or is there some expected correlation between, say, a color and a weapon used? I think it's essential to understand the sources of information you might have. This is the only thing that can help you pick a good inference algorithm.

If there is no additional information you can use, then I don't think you can do better than computing the full matrix of correlations. After all, it *is* possible (in this situation) that a person would randomly initialize such a matrix and behave accordingly.

Hi,
Thank you for the reply. The color is just a starting point. I just mentioned huge as I'm hoping that the method implemented would be transferable to other areas that may involve a range of input. The main aim behind it is to try and profile a user with the way they act/react to certain stimuli (the 5 factors mentioned). So, if the user is given a sword, then monitor if their behaviour changes, and if so, in what way. Then after training, hopefully the AI will predict that given a sword, the user will perform certain (approximate) movements. The problem with a matrix (and I'm no expert on matrices, so please correct me) fundamentally stems from the 5 factors.

Let's say we have two matrices: y axis is previous color and x axis is current color. From this we can put probabilities of past movements between colors (e.g. user moved from red to blue 10 times). However, this may not be enough information to say that if the user is on red, then they will go to blue, since their past actions haven't been taken into account. (e.g. they never go from red to blue after green). As you can see, this matrix would increase in size very quickly.

However, I may be thinking of this in the wrong way and there might be something obvious I've missed. Are there any algorithms that might condense this, or be more efficient for real time use?
Thanks again for any help

Probably the answer of me is wrong and somebody else can give a better answer,

you can always work with artificial neural networks or with support vector machines (this is called inference i think)(it is possible to use Bayesian inference with these techniques to get a real prediction/certainty).
You can train such systems and then they can predict the next step.

A example of predicting the next step with Least Squares Support Vector Machines (a type of SVM) is A Time-Series Example: Santa Fe Laser Data Prediction. Time Series is the same as predicting the next step. The example in the link gives the first 50 data points to the system as an input and will predict the 51st data point. And the process is repeated, take data points 2-51 to predict the 52st data point. In this example we are talking only about 1 factor in your case we are talking about several factors (color, etc.) so you can give for example the 5 previous colors and the 5 previous factors of each thingy factor you meant. Off course with ANNs you can get in trouble because of the many inputs.

But probably somebody else can give a better solution.

I'm still not sure I understand the problem completely. I'll reply first to the parts I do understand.

Quote:

Original post by BassGrime From this we can put probabilities of past movements between colors (e.g. user moved from red to blue 10 times). However, this may not be enough information to say that if the user is on red, then they will go to blue, since their past actions haven't been taken into account. (e.g. they never go from red to blue after green). As you can see, this matrix would increase in size very quickly. However, I may be thinking of this in the wrong way and there might be something obvious I've missed. Are there any algorithms that might condense this, or be more efficient for real time use?

So the formulation you suggest is called Markov model. A 1st-order MM is when the next color depends only on the current color. A 2nd-order MM is when it depends on the two last colors, and so on. Now, to specify a 1st-order MM, you need a CxC matrix of transition probabilities (C is the number of color). For 2nd-order MM, you need CxC^2, and so on. So the size of the transition probability matrix indeed grows pretty fast.

There are basically two somewhat different ways to deal with this. First, as suggested by Litheon, you can use a neural net (or SVM, or some other classifier) to represent the transition matrix implicitly. E.g. as an input to NN, you have the 10 last colors the user visited, and you train the network to output the next color. If the user behavior is predictable, this can represent the large matrix with just the few NN parameters.

Second, you can use a hidden Markov model (HMM). Basically, it assumes the user has some hidden state, and their actions depend on that hidden state. The color affects the user's move not directly, but by first changing their state. The advantage of this is that the hidden state may be meaningful somehow (in your case, the hidden state may include "does the user have a sword", for example). The disadvantage is that learning the transition matrices for HMMs is more complicated. If you do decide to do that, look up "Baum-Welch algorithm".

Quote:

Original post by BassGrime The main aim behind it is to try and profile a user with the way they act/react to certain stimuli (the 5 factors mentioned). So, if the user is given a sword, then monitor if their behaviour changes, and if so, in what way. Then after training, hopefully the AI will predict that given a sword, the user will perform certain (approximate) movements.

So, is the goal to just predict what the user will do in a certain situation (with/without sword, etc), or is the goal to model behavior with sword separately, behavior without sword separately, and then assess whether the behaviors are different? (The latter task is what psychologists/sociologists are doing, they check e.g. whether users behave differently when their identity is known.)

Thanks for the help!

I read some Markov Model journal papers, but even with certain compressions, it seems that it may be overkill/too complicated for this scenario.

The main aim is to predict what the user will do in a certain situation (with/without sword etc..). The emperical difference between what they do in situation X and situation Y is not too important as I'd just like to predict the outcome.

I've also looked into simply using a feedforward neural network with back prop for feedback. However, I'm slightly concerned with the training of it. Say for example, a user performs some action , which is used as the input to the NN (with the other factors), the output would be actionX. However, over time, the user's habits may have significant changes which the NN will not pick up on until it has completley been retrained. I want to keep any intrusion minimal so retraining would be inefficent. Is there a way for the system to adapt continually, after an initial training?

I don't think the project has been explained well enough here...


If the user is encouraged to jump from one color to a different color randomly, then "color" wouldn't seem like much of a candidate for use as input to an AI subroutine. So, unless you think you can successfully tease out a person's bias to certain colors, it seems you'll need stronger inputs to make predictions with.

Apologies for any confusion over the project. At the moment, this project is just a test bed for, hopefully, a larger prediction framework. I tried to make the situation as simple as possible, and decided that having colours on a grid might be a simple aspect to predict and mess around with to ensure the system is working on a fundamental level.

The main aim is to have the user select certain colours on a grid in whichever fashion they like. It can be random, in rows, patterns etc... Then, given various other stimuli such as the sword, or certain music, they can then continue selecting colours. The system will monitor how the squares are now being chosen. After this 'training', given a certain song/weapon, the system will predict which squares are most likely to be chosen by the user.

This project isn't a game per se, more of a tech demo. Essentially, it aims to profile users (without collaborative filtering as it's just the one user) and emulate any changes in their selection based on stimuli provided.

I hope that's made is slight more clearer :D

edit: Although this may seem like a job for simple matrices, I'm looking to make it a lot bigger in scale, so scalability is an issue from the offset.