Dodging Performance Anomaly?

Fragment of a discussion from Talk:Pris
Jump to navigation Jump to search
Edited by author.
Last edit: 23:18, 16 November 2013

I've looked at random forests before, another one which interested me was Extreme Learning Machines which are feed-forward NNs working in an ensemble. The trouble I found was that even though these methods are fast when compared to other machine learning techniques (K-means, feedback NN, SVM), they are still much slower than a single KNN call in a Kd-Tree just because of the amount of data they need to touch for each 'event'. A Kd-Tree trains in O(1) and classifies in O(logN).

Feel free to prove me wrong though =) I'd love something which works well beyond the ubiquitous Kd-Tree!

Another thing to consider is how you are going to pose the question. A lot of the successful NN-based approaches have used a bunch of classifiers, one for each potential firing angle, and shooting at the one with the highest probability. Others have tried posing it as a straight regression problem, but I don't think those worked as well, possibly because of the high noise (against top bots you are lucky to get a 10% hitrate).

I'd be interested to hear what you end up trying, and how it works out.

Skilgannon (talk)12:06, 16 November 2013

Another neural net thing I haven't seen in any bots is recurrent neural nets with memory. I've heard they are very good at certain types of problems, where they need to be able to recall old information while still learning new stuff. I don't know exactly how to implement the back-propagation algorithm on them, and I am no NN expert, but it seems as if they might be good against adaptive movers.

I have heard that SVMs are significantly slower than RF, but work better on smaller data sets. Since RF can handle both categorical and numerical outputs and predictors, you could pose the problem asking for a GF, or a bin to fire in. I'm not sure if you can get multiple outputs out of it. Another nice thing is that you wouldn't have to weight all your different predictors because RF figures out which ones are important for you. I plan to test RF out of a bot on data gathered from battles soon. Even if it doesn't work well or is too slow, it could still determine good weights for predictors used in a KNN algorithm.

In all these classification algorithms, if speed is a big issue, why not make a system allowing the spread of calculations over multiple ticks? It seems like you don't need to train every tick in general.

Straw (talk)23:17, 16 November 2013

Recurrent NN uses a lot of memory and processing power, both of which are fairly limited in the RoboCode setting. Speed is definitely the main issue, particularly when a lot of the time is already taken doing predictions to give more relevant features for classification. Even with spreading calculations over multiple ticks many popular techniques Just Wouldn't Work.

If you can't get multiple outputs out of the RF, just run a bunch of them, one in each bin, and choose the bin with the highest probability. Ie, each bin is a different class and you choose the most probable class. Quick and dirty regression without inter-dependency. I've actually thought about trying a Naive Bayes like this, just for kicks. I think Pris and a few others do their NN classifications this way.

Skilgannon (talk)23:27, 16 November 2013

Running 50+ random forests with 50 trees each would be a lot of computation. I am first going to try seeing how well one RF predicts a GF or bearing offset.

Straw (talk)00:22, 17 November 2013

Executing one tree classification is pretty fast though, isn't it? I don't think 2500 of them per tick seems unreasonable. Or is it many times more than that? My main 1v1 gun does up to 13k loop iterations for its kernel density calculation, and that's on top of the kd-tree search for 225 nearest neighbors among up to ~25k data points. And the gun is the fast part of the bot. :-)

Voidious (talk)00:56, 17 November 2013

The problem would be training the forests, which is much slower. Training one forest would be much easier, allowing you to do more training and perhaps have a higher tree count. I plan to eventually try both anyway, but I am doing the easier approach first.

Straw (talk)04:24, 17 November 2013