# Distance metric invariant to dimensionality?

I'm working on a classification/prediction problem where I have to predict a location of an object. The problem that I have is that for every location, I have a unique and different number of feature dimensionality. So for example if I'm searching for an object in 5 possible locations. I have 10'000 training and testing samples in location 1, that have dimensionality 1000, location 2 features have dimensionality 500, and so forth, (let's imagine location 5 has dimensionality 50).

What would be the correct way of assessing a prediction if the features have different dimensions? For example, using an euclidean distance metric by doing Nearest Neighbours would be a poor approach since I will very likely have a minimal distance (on average) for the 50 dimensional case than the 1000-dim case, even though the 1000 dim case might be correct.

How should I go about this for the Nearest Neighbour scenario, or for other classifiers like LDA and SVM? Applying a soft-max, on the score of every output doesn't seem to do the trick for the previous reasons explained before...

• You need a measure which is not convex, me thinks. – Aksakal Oct 3 '15 at 4:18

You're right. It doesn't make sense to compare L2 distances in 1000 dimensional space with L2 distances in 50 dimensional space. These are raw distances and they should be converted to probabilities for them to be comparable. Sigmoid fitting is a tool for making this conversion.

Suppose you have a training set $D=\{(x_i, y_i)\}_{i=1}^N$ and on this dataset, you trained two different classifiers, $f_1()$ and $f_2()$, which operate on different number of features.

$f_1(x_1)$ is a raw classification score or a discriminant score as it is sometimes called. It doesn't make sense to directly compare $f_1(x_1)$ with $f_2(x_1)$. One way to make this comparison is to train a separate sigmoid function for each of your classifiers.

For $f_1()$, your sigmoid function, let's call it $g_1()$, should map a positive example to 1 and a negative example to 0. That is, for an example $(x,y)$ you ideally want:

$$g_1(x) = \frac{1}{1+\mathrm{exp}(-(\alpha f_1(x) + \beta))} = \begin{cases} 1,& \mathrm{if}\;\;y_i=1\\ 0, &\mathrm{if}\;\;y_i=-1 \end{cases}$$

Training a sigmoid function amounts to searching for the optimal values of $\alpha$ and $\beta$.