Mahalanobis Distance
So, I was reading about Mahalanobis distance and it sounds as if it is designed for classifying data that have a definite center about which they are clustered. Has anyone tried using this with robocode?
I've thought about it, but it needs a covariance matrix and it is slow to build a covariance matrix of the entire tree. There might be faster approximate methods though...
Hmm, Mahalanobis distance looks interesting. I have considered using principal component analysis before, which I'd expect to give somewhat similar results (i.e. both normalize for covariance), but never got around to trying it.
Regarding performance issues building a covariance matrix for the entire tree, I also think that doing research into incremental methods of building/updating a covariance matrix may be key to making mahalanobis distance practical for robocode usage.
I also wonder if it may make the most sense to make smaller covariance matrices based on either the most recent X data points, or certain regions in the data, etc. They would be faster to compute, and may be able to take advantage of how the ideal weight of each axis can vary over the search space.
Edit: Oh, one other thought that comes to mind is... perhaps it would make sense to precompute a covariance matrix for your targeting attributes, based on a large data set from battles with many robots? It wouldn't be as nice as computing it on-the-fly for what you're against, but I'd expect it to have some positive impact anyway.
I've spent many a CPU-hour experimenting with quite a few clustering algorithms and never been able to exceed the performance of KNN for Robocode targeting, and KNN is also much faster. So I'm a little skeptical at this point about approaches that assume a data point falls into a specific cluster. But this is interesting stuff... definitely WaveSim (or similar) makes testing this kind of thing a lot more feasible.
Mahalanobis distance can be combined with KNN search. Swap point distance calculation from euclidean to mahalanobis and you have it.
Another way of viewing mahalanobis distance is it rotates the data space, or have "diagonal" weights. Which is good when classifiers are not completely independent from each other.
i.e. lateral velocity and vertical velocity. If lateral velocity is 8, vertical velocity is always 0. Coordinates where both velocities are 8 are always empty. Mahalanobis distance then uses a "diagonal" weight so 5.6 lateral velocity and 5.6 vertical velocity (5.6, 5.6) is normalized as (8, 8). While (8, 0) is still normalized as (8, 0).
You do not have permission to edit this page, for the following reasons:
You can view and copy the source of this page.
Return to Thread:User talk:AW/KNN/Mahalanobis Distance/reply (4).
I tried. Found 2 problems in using mahalanobis distance instead of euclidean distance.
First problem is finding a covariance matrix, which is the mahalanobis equivalent of a weight vector. I tried using sampled covariance matrixes, but they are not always valid. You need a positive semi-definite covariance matrix to use it in mahalanobis distance calculations. There are methods for finding a nearest positive semi-definite matrix from a sampled matrix, but the methods are too slow to be calculated online.
Second problem is optimizing KNN search. Methods like kd-trees only work with euclidean distance. I don´t know of any data structure designed for mahalanobis distances and which supports online learning at the same time.
The first problem can be addressed with genetic tuning to find a valid covariance matrix offline, but I didn´t try it yet. In theory it can be stronger than euclidean distance search due to higher amount of weights to tune.
The second problem is not a serious problem if the data set is not too big. I managed to make a bot work using only real waves (no tick waves), a sampled covariance matrix and simple linear KNN search without skipping turns.
The problem is the matrix was sometimes valid, sometimes not. It fallbacked to euclidean distance (using only the main diagonal) whenever the matrix became invalid. The bot performance decreased and I never uploaded it to the rumble. But again, genetic tuning with an offline covariance matrix may fix it.