0
$\begingroup$

Consider the k-NN algorithm and let $k(N)$ be the choice of k as a function of N (data points).

For $N \to \infty$, if $k(N) \to \infty$ and $k(N)/N \to 0$, then k-NN converges to optimal classifier.

Question: How does the condition $k(N)/N \to \infty$ ensure that all the k nearest neighbors are close to a given test point $\mathbf{x}$?

For content, please see:

https://amlbook.com/eChapters/6-Oct2022-readeronly.pdf

Theorem 6.2

Password: Paraskavedekatriaphobia

Improve this question
$\endgroup$
2
  • $\begingroup$ that "Question:" condition is never mentioned in your actual question, is that a typo? $\endgroup$
    – Alberto
    Nov 21 at 13:09
  • $\begingroup$ İt is mentioned like this in the given reference when a sketch of the proof is done. $\endgroup$
    – DSPinfinity
    Nov 21 at 14:10

1 Answer 1

Reset to default
0
$\begingroup$

The goal here is to prove the fraction of the test point $\mathbb{x}$'s $k$ nearest neighbors with $y=1$ approximates the conditional probability $P(y=1|\mathbb{x})$ defined as $\pi(\mathbb{x})$, therefore strictly speaking you only need to prove all $\mathbb{x}$'s $k(N)$ nearest neighbors out of $N$ data points are close to $\mathbb{x}$ relative to the maximum $N$. Formally you define a ratio $r$ between $\mathbb{x}$ and its farthest neighbor within its $k$ nearest neighbors which is nothing but the $k$th nearest neighbor, divided by the maximum distance. Under the assumption of $k(N)/N$ which means the fraction of points within $r$ of $\mathbb{x}$ approaches $0$ in the limit as $N$ approaches $\infty$, this relative $r$ must approach $0$ too.

Improve this answer
$\endgroup$
2
  • $\begingroup$ It is really hard to follow the explanations since statements are not clear. $\endgroup$
    – DSPinfinity
    Nov 22 at 0:30
  • $\begingroup$ Once you understand what the goal the condition $k(N)/N \to 0$ can achieve, my propositions would become clear. I've highlighted the goal here is to use the faction of a test point's 'nearest neighbors with class label 1' as a proxy to the 'conditional probability of class label 1 given the said data feature', ensuring KNN classifier converges to the optimal classifier in the limit with infinite training data. Indeed the mere absolute distance in your reference never approaches 0 especially if you have numerous nearest neighbors, only relative distance approaches 0 and this implies the goal. $\endgroup$
    – Double Knot
    Nov 23 at 8:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .