Hi! I am supposed to let fotball players learn how to judge how likely a pass to a teammate is to succed. And then what i want is a way to given a set of training samples, generated from the environment, traing this structure to output a probability given some input. Now, i i looked at bayesian networks, byt from what i understand they do not "learn" probability distributions, merely calculates some probability given already known distributions...right? But, in the article Layered learning in multi-agent systems, Peter Stone describes how he uses decision trees to accomplish this. My question is then if there are other ways to train a structure, preferably not neural networks, towards a probability distribution? thank you all --Spencer "Relax, this dragon is sleeping..."

You need to distinguish the representation from the algorithm.

The decision tree and neural networks are used to provide generalisations, which means you don''t have to store the probabilities for each state/action. The data-structure learns to approximate the probability distribution with a more compact representation.

If your representation is not too complex, why not just use a simple array?


The algorithm used to find the best representation is probably a derivative of reinforcement learning. The problem you describe is a very simple instance of a reinforcement problem.

I hope that helps a bit!


AiGameDev.com

quote: Original post by Spencer
I am supposed to let fotball players learn how to judge how likely a pass to a teammate is to succed. And then what i want is a way to given a set of training samples, generated from the environment, traing this structure to output a probability given some input.
Now, i i looked at bayesian networks, byt from what i understand they do not "learn" probability distributions, merely calculates some probability given already known distributions...right? But, in the article Layered learning in multi-agent systems, Peter Stone describes how he uses decision trees to accomplish this.
My question is then if there are other ways to train a structure, preferably not neural networks, towards a probability distribution?

There are many ways to estimate probabilities based on historical examples: regression (there are many kinds), neural networks, decision trees, k-nearest neighbors, etc. If you do not need learning to take place on-the-fly, then the field is wide open. If you do, though, your choice will be restricted to those algorithms which can update their models fast enough in your environment. Depending on the time constraints and complexity of the probabilities being inferred, this may be difficult.

Can you provide more details regarding the nature of the inputs? How many there are, etc.?

Good luck,
Predictor
http://will.dwinnell.com






[edited by - Predictor on October 2, 2003 6:24:44 AM]

Thank you for your replays.

Actually i have not decided the input yet, i thought perhaps i could get some of that work done by selecting the appropriate approximator.
The speed of the learning is not an issue here since i am gonna pre-train whatever structure i choose. Reinforcement learning is however not favourable since i''m gonna use that elswhere in my program and i want to have some diversity in my learning algorithms.....
But the input is gonna be something like number of opponents surrounding the passing players, number of opponents surrounding receiving player, distance to player etc.



--Spencer

"Relax, this dragon is sleeping..."

quote: Original post by Spencer
Reinforcement learning is however not favourable since i''m gonna use that elswhere in my program and i want to have some diversity in my learning algorithms.....

There are so many different solutions that fall into the RL category, chances are they both will anyway... don''t let that stop you!

Thank you so much for the replies...i will do some more research...


--Spencer

"Relax, this dragon is sleeping..."

A very robust method for estimating probabilities is the following model:
estimated_probability(i_1,i_2,i_3,...,i_n) = sigma(c_1*i_1+c_2*i_2+...+c_n*i_n), where
sigma(x):=1/(1+exp(-x))

Use i_1="number of opponents surrounding passing player", etc.
Find the weights that minimize the quadratic error. A neural network consisting of a single neuron with sigma as transfer function will do this.

Another important point is that, in general, the data structure you use to represent the domain model is (mostly) independent of the learning algorithm you use to discern the parameters of the model.

That's not to say that one should choose them in concert with each other, as some algorithms perform better on certain sorts of data structures.

You mentioned that your training will be offline (batch). While this gives you ample time to train and tune your model before implementation, it doesn't allow you to cope with an environment where the rules change (so as to make your training space an inadequate representation of the true domain at time t). If this is not going to happen, then stick with the batch learning approach.

One big question is, 'how much computational load can you commit to determining an output decision given an input state vector? A Bayesian network, once compiled, requires a small amount of computation. A decision tree even less. An ANN slightly more (depending on size).

Finally, as to learning probabilities, there are two methods: expert elicitation and learning from data. The former method requires an expert to estimate the probability of all types of events and their certainty/uncertainty in that estimate. Learning from data can take on two aspects: learning the model structure and learning the model parameters. If you want to read something regarding learning probabilities for Bayesian networks, check out the following paper (gratuitous self plug!):

A. Nicholson, T. Boneh, T. Wilkin, K. Stacey, L.Sonenberg and V. Steinle, "A Case Study in Knowledge Discovery and Elicitation in an Intelligent Tutoring Application".
In UAI01 Proc. of the 17th Conference on Uncertainty in Artificial Intelligence, Seattle, 2001, pp. 386-394.

Cheers,

Timkin



[edited by - Timkin on October 2, 2003 8:05:19 PM]

quote: Original post by alvaro
A very robust method for estimating probabilities is the following model:
estimated_probability(i_1,i_2,i_3,...,i_n) = sigma(c_1*i_1+c_2*i_2+...+c_n*i_n), where
sigma(x):=1/(1+exp(-x))

Use i_1="number of opponents surrounding passing player", etc.
Find the weights that minimize the quadratic error. A neural network consisting of a single neuron with sigma as transfer function will do this.

In regards to this approach, see also "logistic regression" (and related techniques).

-Predictor
http://will.dwinnell.com

quote: Original post by Spencer
Thank you so much for the replies...i will do some more research...

Although they tend to deal with larger data, it might be worth examining the data mining techniques used in the Software section at KDNuggets (http://www.kdnuggets.com).

-Predictor
http://will.dwinnell.com