Answers.Body: <p>The goal here is to prove the <em>fraction</em> of the test point <span class="math-container">$\mathbb{x}$</span>'s <span class="math-container">$k$</span> nearest neighbors with <span class="math-container">$y=1$</span> approximates the conditional <em>probability</em> <span class="math-container">$P(y=1|\mathbb{x})$</span> defined as <span class="math-container">$\pi(\mathbb{x})$</span>, therefore strictly speaking you only need to prove all <span class="math-container">$\mathbb{x}$</span>'s <span class="math-container">$k(N)$</span> nearest neighbors out of <span class="math-container">$N$</span> data points are close to <span class="math-container">$\mathbb{x}$</span> relative to the maximum <span class="math-container">$N$</span>. Formally you define a ratio <span class="math-container">$r$</span> between <span class="math-container">$\mathbb{x}$</span> and its farthest neighbor within its <span class="math-container">$k$</span> nearest neighbors which is nothing but the <span class="math-container">$k$</span>th nearest neighbor, divided by the maximum distance. Under the assumption of <span class="math-container">$k(N)/N$</span> which means the fraction of points within <span class="math-container">$r$</span> of <span class="math-container">$\mathbb{x}$</span> approaches <span class="math-container">$0$</span> in the limit as <span class="math-container">$N$</span> approaches <span class="math-container">$\infty$</span>, this relative <span class="math-container">$r$</span> must approach <span class="math-container">$0$</span> too.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-11-22T00:30:24.070Z
Answers.Text: It is really hard to follow the explanations since statements are not clear.
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-11-23T08:31:38.680Z
Answers.Text: 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.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-11-21T23:45:26.000Z
Answers.LastActivityDate: 2023-11-21T23:45:26.000Z
Answers.UserDisplayName: cinch
Body: <p>Consider the k-NN algorithm and let <span class="math-container">$k(N)$</span> be the choice of k as a function of N (data points).</p>
  <p>For <span class="math-container">$N \to \infty$</span>, if <span class="math-container">$k(N) \to \infty$</span> and <span class="math-container">$k(N)/N \to 0$</span>, then k-NN converges to optimal classifier.</p>
  <p>Question: How does the condition <span class="math-container">$k(N)/N \to \infty$</span> ensure that all the k nearest neighbors are close to a given test point <span class="math-container">$\mathbf{x}$</span>?</p>
  <p>For content, please see:</p>
  <p><a href="https://amlbook.com/eChapters/6-Oct2022-readeronly.pdf" rel="nofollow noreferrer">https://amlbook.com/eChapters/6-Oct2022-readeronly.pdf</a></p>
  <p>Theorem 6.2</p>
  <p>Password: Paraskavedekatriaphobia</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-11-21T13:09:00.750Z
Comments.Text: that "Question:" condition is never mentioned in your actual question, is that a typo?
Comments.UserDisplayName: Alberto
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-11-21T14:10:17.460Z
Comments.Text: İt is mentioned like this in the given reference when a sketch of the proof is done.
Comments.UserDisplayName: DSPinfinity
Tags: <machine-learning><k-nearest-neighbors>
Title: In k-NN, how does the condition $k(N)/N \to 0$ ensure that all the k nearest neighbors are close to a given test point $\mathbf{x}$?
UserDisplayName: DSPinfinity
ThreadText: # In k-NN, how does the condition $k(N)/N \to 0$ ensure that all the k nearest neighbors are close to a given test point $\mathbf{x}$?
  
  (Asked by: username_0 on 2023-11-21)
  
  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
  
  **Tags:** machine-learning, k-nearest-neighbors
  
  > **Comments:**
  > **username_1**: that "Question:" condition is never mentioned in your actual question, is that a typo?  
  > **username_0**: İt is mentioned like this in the given reference when a sketch of the proof is done.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2023-11-21. Score: 0
  
  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.
  
  > **Comments:**
  > **username_0**: It is really hard to follow the explanations since statements are not clear.  
  > **username_2**: 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.  
  
  ---
  
  