Friday, March 27, 2009

AdaBoost

There are a couple of algorithms that float around that I always feel I need to know more about. During a number of data mining conferences the top 10 algorithms in data mining were collated.

One that seems to get a lot of attention in computer vision and robotics is Adaptive Boosting (aka AdaBoost). You can use this algorithm to create a strong classifier from a set of weak classifiers. (One way to think of this is that weak classifiers give you a very approximate answer to a classification problem, strong ones give a much much better approximation)

For example in the figures below, you can see how the algorithm builds up a strong classifier from combining multiple weak classifiers.
(from Jan Sochman's AdaBoost talk)











AdaBoost combines these classifiers through a set of weights that it adaptively adjusts.

I can hardly claim to be an expert on the subject, but since I find the mathsy description of it on Wikipedia confusing, here is my summary of it in CS-algorithmish talk:

Start with a training data set of features, labeled with the correct answer.
ie: data[i], correct_answer[i]
Run each weak classifier with the data set and store its results.
ie:results[x,i] = classifierX(data[i])
Initialize each of the weightings with 1 / (number of entries in the data set).
At this step we are starting of with each classifier having equal weighting.
ie: D[i] = 1/m

For N number of iterations:
For each classifier:
For each feature, i:
if the output of the classifier does not equal the correct answer, update the error.
error+=D[i]
(ie: sum of the weights of the misclassified samples)
if the error is less than the minimum error, mark this as the best classifier
End For
Now update the importance of the classifier:
alpha[best classifier] = 0.5 * log(1 - minimum error)/minimum error
And update all the classifier weightings:
For each feature,i
D[i] = *= exp(-alpha[best] * answer[i] * result(best,i)
z+=D[i]
End for
For each feature, update D[i] = D[i]/z to renormalize.

And.. were done!

In my experiments it seems not to work too well,.. it definitely improves on your weak classifiers a bit, but they have to be pretty close to spot on or able to solve the problem already. I think I'd still prefer using a neural net for classification..

Wednesday, March 25, 2009

Environment Design

Environment design for levels/missions seems to be a very tricky thing to get right.
My favorite resource on the topic is from Bungie:
Environment Design in HALO 3 by Mike Zak. It goes through some great detail on how they design and built up their levels, and dealt with AI.

Here's the halo 3 whiteboard for the factory level:



Alex Galuzin has some nice introductory material on Level Design Work Flow and Planning levels. Also check World of Level Design.

Basics of good design are also covered in Brian Upton's GDC 2007 talk on Narrative Landscapes.

There are some good tips on environmental storytelling by Don Carson, part 1
part 2.

Ben Cousins gives some good metrics to evaluate a map in Low-Level Game Design, Atoms, Measurement and Hierarchies, and Cevat Yerli illustrates some great examples of how a map can be effecitvly laid out in "Crysis in the Making".

Finally Realistic Level Design in Max Payne by Aki Määttä covers some details on indoor levels.

Alright, you should be all up and ready to make some awesome levels now!

Monday, March 09, 2009

Underwater Robot

The problem with real robots is that they keep breaking. Little things add up, hardware acts weird, batteries run out. Simulations are much easier to deal with.




Above is a picture of Markus and I trying to debug the AUV in the water. The AUV is slightly positively buoyant - which means at least you don't need to worry about it sinking..

Sunday, March 08, 2009

Update

Been a week or so since I blogged. (or remember doing so) Had a busy week, did some experiments with an autonomous underwater vehicle, and created a benchmark set for physics engines. Create a mini website for the physics engine benchmark - MoDBench repository - COLLADA & PAL API benchmarks.

Also found Pocket UFO. It's great to play all your old games on your PDA again. Other great toys for your PDA are ScummVM, Pocket Lemmings (runs multiple versions of lemmings),
Pocket Nester Plus (NES emulator!),
Vexed, SuperDoku (sudoku)

and Patiences (Spider Solitare, Free Cell)

That should keep you busy with your new windows mobile phone.