3
$\begingroup$

My question is motivated by this question, and self-study of the paper "When is nearest neighbor meaningful?", where the authors show the following

Theorem 1: Let $X^{(d)} \in \mathbb{R}^d$ be a sequence of random vectors so that $\frac{||X^{(d)}||}{\mathbb{E}||X^{(d)}||} \to_{p}1 \iff Var\left[\frac{||X^{(d)}||}{\mathbb{E}||X^{(d)}||}\right] \to 0, d \to \infty.$ Then for any given $n \in \mathbb{N},$ and the random sample $\{X_1^{(d)} \dots X_n^{(d)}\}$ generated by $X^{(d)},$ the ratio

$$ \frac{max_{1 \le i \le n}||X_n^{(d)}||}{min_{1 \le i \le n}||X_n^{(d)}||}\to_{p} 1, d \to \infty. $$

Roughly speaking, the theorem shows that if the the norm of the random vector $X^{(d)}$ "behaves more deterministically" (i.e. $\frac{||X^{(d)}||}{\mathbb{E}||X^{(d)}||} \to_{p}1,$) then the nearest neighbor of the origin loses it meaning (i.e. the maximum dist divided by minimum distance to the origin converges in probability to $1.$)

Also of relevance, is a family of examples that satisfies the hypothesis of the above Theorem 1, which is given in this paper "Concentration of Fractional Distances (Wertz. et. al.)", which basically states that (see its Theorem 5, P. 878)

Theorem 2: If $X^{(d)}=(X_1 \dots X_d) \in \mathbb{R}^d$ is a $d$ -dimensional random vector with iid components, then $\frac{||X^{(d)}||}{\mathbb{E}||X^{(d)}||} \to_{p}1.$

*If we combine the above two theorems, we can infer that:

Corollary: For data generated by features that're iid, then the norm "behaves more deterministically" (explained above) in high dimensions (Theorem 2), hence by Theorem 1, the nearest neighbor of the origin loses its meaning in high dimensions.

N.B. assume below tat we're only considering Euclidean distances, not fractional etc. We do this because Euclidean distances are more amenable to manifold learnign or do linear algebraic computations (e.g. it's easy to transform dstances into inner products.)

I'm looking for a practical application of this corollary or the above two theorems, in terms of clustering and classification, where we use nearest neighbor. To be more specific, can we use this theorem or the corollary above as a "warning step" before performing, say kNN or 1-NN classification? So, let's say that we've an idea (maybe after some normality tests) that the data is generated by a normal random vector whose covariance matrix is almost diagonal , then the features are almost iid (thus almost satisfying the hypothesis of Theorem 2 above), and hence we can apply Theorem 2 first and then Theorem 1, to conclude beforehand that the nearest neighborhood classifier is not going to give us good results, without actually computing the maximum and minimum distances. This is just an idea, but are there any other practical applications where we can use the above two theorems?

$\endgroup$
5
  • $\begingroup$ don't use Euclidian norm in high dimensions. that's the practical use. are you looking for something beyond this? $\endgroup$
    – Aksakal
    Jun 19, 2020 at 19:14
  • $\begingroup$ @Aksakal The suggestion for not using the Euclidean distance follows from Corollary 2 of researchgate.net/publication/…, where they shows that while using $L^p, p<2$ metric, the difference between max and min dist go to infty, where for Euclidean dist, it stays bounded. However, I'm not sure for certain practical purposes (e.g. manifold learning), we can use those metrics. With that said, my question is ore geared toward what the theorem means for clustering and classification using NN approaches. $\endgroup$
    – Stat_math
    Jun 19, 2020 at 19:39
  • $\begingroup$ In other words, I'd like to see a concrete application of their theorem in an unsupervised/supervised machine learning task that uses nearest neighbor. I tried to chalk out a potential one in the bold italics in the last paragraph of my OP, but it didn't seem concrete to me. Do you know any paper that does precisely that? $\endgroup$
    – Stat_math
    Jun 19, 2020 at 19:42
  • 1
    $\begingroup$ don't use Euclidian for clustering, it can't discriminate between close and far, everything is equally far to it $\endgroup$
    – Aksakal
    Jun 19, 2020 at 20:07
  • $\begingroup$ @Aksakal Sorry but I don't think Euclidean distance is always going to be useless. It won't be useless if the distance concentration phenomenon doesn't occur, which is very much possible for highly correlated features. The question is more about the use of Euclidean distance itself, and trying to find corresponding applications. $\endgroup$
    – Mathmath
    Jul 28, 2020 at 10:50

1 Answer 1

1
$\begingroup$

What makes this tricky when $d$ is large is that the data can obviously be very far from uniform or Normal or iid or anything, but it may still be unclear whether the distribution is 'nearly' $d$-dimensional or whether it actually concentrates on a low-dimensional subset. For an extreme case, imagine a tangled ball of string, where most of the near neighbours of most points on the string are close in the one-dimensional distance along the string.

What I would do is to pick a few points at random, find their distances from each other and from their nearest neighbour, and see if these were close. This takes advantage of the law-of-large-numbers part of the theorem: as $d$ increases, the probability of a random set of points having nearest neighbours near the typical value goes to 1.

You could even compare the ratio (nearest distance)/(typical distance) to what the theorem says, and say something like "We have 50 dimensions here but the nearest neighbours are only about as useless as in 20 iid dimensions".

$\endgroup$
2
  • $\begingroup$ Thanks for your answer, but I'm really not sure it answers the question. I'm looking for a practical application of the two theorems and/or their corollary in machine learning, e.g. kNN classification or clustering etc. I'm unable to see how your answer relates to that. $\endgroup$
    – Stat_math
    Jun 17, 2020 at 22:22
  • 1
    $\begingroup$ Fair. I thought it was worth a try. $\endgroup$ Jun 17, 2020 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.