Machine Learning

Dr. Indu Joshi

Assistant Professor at
Indian Institute of Technology Mandi

24 February 2025
 The k-NN algorithm

• Assumption: Similar Inputs have similar outputs

• Classification rule: For a test input, assign the most
common label amongst its k most similar training inputs
 The k-NN algorithm
Intuition: k-NN algorithm
Assumption: Similar Inputs have similar outputs Classification rule: For
input x, assign the most common label amongst its k most similar traini

A binary classification example with k = 3.

Figure 1: A binaryThe
classification example with k = 3. The green point in
green point in the center is the test
the center is the test sample x. The labels of the 3 neighbors are 2 ×
sample x. The labels of the 3 neighbors are
(+1) and 1 × (-1) resulting in majority predicting (+1).
2× (+1) and 1×(-1) resulting in majority
predicting (+1).

Formal (and borderline incomprehensible) definition of k-NN:

 k-NN Definition

Assume we have a text point x, denote the set of the k nearest

neighbors of x as Sx . Formally, Sx is defined as Sx ⊆ D s.t.
|Sx | = k and ∀(x ′ , y ′ ) ∈ D\Sx ,

dist(x, x ′ ) ≥ max(x”,y ”)∈Sx dist(x, x”),

i.e., every point in D but not in Sx is at least as far away from x as
the furthest point in Sx . We can then define the classifier h() as a
function returning the most common label in Sx :

h(x) = mode({y ” : (x”, y ”) ∈ Sx })

where mode(·) means to select the label of the highest occurrence
 Distance Function

The k-nearest neighbor classifier fundamentally relies on a distance

metric. The better that metric reflects label similarity, the better
the classification will be. The most common choice is the
Minkowski distance.
d
X 1
dist(x, z) = ( |xr − zr |p ) p
r =1
 kNN: Curse of Dimensionality
In the limit case, the test point and its nearest neighbor are identical. T
• The kNN classifier makes thetwoassumption
are exactly that similarcanpoints
cases when a misclassification occur: when the test
share similar labels. point and its nearest neighbor have different labels. The probability of
• Unfortunately, in highhappening is the probability of the two red events:
dimensional spaces, points that are
(1 − p(s|x))p(s|x) + p(s|x)(1 − p(s|x)) = 2p(s|x)(1 − p(s|x))
drawn from a probability distribution, tend to never be close
together. Good news: As , the -NN classifier is only a factor 2 worse than the b
n → ∞ 1

possible classifier. Bad news: We are cursed!!

• We can illustrate this on a simple example. We will draw
points uniformlyCurse
at random within the unit cube (illustrated in
of Dimensionality
the figure) and we will investigate how much space the k
nearest neighborsDistances
of a test between
pointpoints
inside this cube will take up.
The kNN classifier makes the assumption
similar points share similar labels.
Unfortunately, in high dimensional space
points that are drawn from a probability
distribution, tend to never be close togeth
We can illustrate this on a simple exampl
We will draw points uniformly at random
within the unit cube (illustrated in the fig
23, 11:02 AM k-nearest neighbors / Curse of Dimensionality

and we will investigate how much space the k nearest neighbors of a test point
inside this cube will take up.
kNN: Curse of Dimensionality
Formally, imagine the unit cube [0, 1] . All training data is sampled uniformly
d

within this cube, i.e. ∀i, x i ∈ [0, 1]

d
, and we are considering the k = 10 nearest
neighbors of such a test point.
Formally, imagine the unit cube [0, 1]d . All training data is
sampled uniformly within this cube, i.e., ∀i, xi ∈ [0, 1]d and we are
considering the k = 10 nearest neighbors of such a test point.

d ℓ

2 0.1
10 0.63
100 0.955
1000 0.9954

Let ℓ be the edge length of the smallest hyper-cube that contains all k-nearest
1/d
neighbor of a test point. Then ℓ d
≈
k

n
and ℓ ≈ (
k

n
) . If n , how big is ℓ?
= 1000

So as d ≫ 0 almost the entire space is needed to find the 10-NN. This breaks
 kNN: Curse of Dimensionality

1. Volume Expansion in Higher Dimensions

• Consider a unit cube [0, 1]d containing training data sampled
uniformly.
• The edge length l of the smallest hyper-cube enclosing k
nearest neighbors is given by:
 1
k d
l≈ .
n
• As the dimension d increases, l approaches 1, meaning that
the hyper-cube containing the nearest neighbors spans almost
the entire space.
 kNN: Curse of Dimensionality

2. Breakdown of k-NN Assumptions

• When d is small, l is much less than 1, meaning nearest
neighbors are localized.
• When d is large, l ≈ 1, implying that the k-nearest
neighbors are spread throughout the entire unit cube.
• This undermines the assumption that nearest neighbors are
similar to the test point.
 kNN: Curse of Dimensionality

3. Practical Implications
• In high dimensions, all points become almost equidistant,
making the k-NN algorithm ineffective.
• The distinction between ”nearest” and ”far” neighbors
diminishes.
• Classification accuracy deteriorates as k-NN struggles to find
meaningful local neighborhoods.
 kNN: Curse of Dimensionality

• Let l be the edge length of the smallest hyper-cube that

contains all k−nearest neighbor of a test point. Then, l d ≈ kn
1
and l ≈ ( kn ) d . If n = 1000, how big is l?
• So as d >> 0 almost the entire space is needed to find the
10-NN.
• This breaks down the k-NN assumptions, because the -NN are
not particularly closer (and therefore more similar) than any
other data points in the training set.
• Why would the test point share the label with those k-nearest
neighbors, if they are not actually similar to it?
 Why l d ≈ kn ?

Definition of the Smallest Hyper-Cube:

• The test point is surrounded by its k-nearest neighbors.
• The smallest hyper-cube that contains these k neighbors has
edge length l.
Volume Consideration:
• The volume of a d-dimensional hyper-cube with edge length l
is:
V = ld.
• This volume represents the local region around the test point
that encloses the k neighbors.
 Why l d ≈ kn ?

Density Approximation:
• Assume that the training dataset consists of n points
uniformly distributed in the space.
• The total volume of the space (or the region relevant for
sampling) is assumed to be normalized to 1.
• The density of points in the space is approximately:
n
ρ≈ = n.
1
• In the local region of volume l d , the expected number of
points is given by:

Expected points in V = n · l d .
 Why l d ≈ kn ?

Balancing the Expected Number of Points:

• Since we defined the hyper-cube to contain exactly k nearest
neighbors, we set:
n · l d ≈ k.
• Rearranging this equation:

k
ld ≈ .
n
st point share the label with those k-nearest neighbors, if they are not
ly similar to it?
Distance in higher dimensions: Curse of Dimensionality
Distance in higher dimensions: Curse of Dimensionality

• The histogram plots show the distributions of all pairwise

distances between randomly distributed points within
d-dimensional unit squares. As the number of dimensions d
grows, all distances concentrate within a very small range.
• This figure demonstrates that the distance between two
randomly drawn data points increases drastically with their
dimensionality.
 Curse of Dimensionality

• One might think that one rescue could be to increase the

number of training samples, n, until the nearest neighbors are
truly close to the test point.
• How many data points would we need such that l becomes
truly small?
1
• Fix l = 10 = 0.1 =⇒ n = lkd = k · 10d , which grows
exponentially!
• For d > 100 we would need far more data points than there
are electrons in the universe!!!
 Data with low dimensional structure

• Don’t worry, not all is lost.

• Data may lie in low dimensional subspace or on submanifolds.
Example: natural images (digits, faces).
• Here, the true dimensionality of the data can be much lower
than its ambient space.
 Example- Data with low dimensional structure
• The figure shows ank-nearest
example of /aCurse
neighbors data set sampled from a
of Dimensionality
2-dimensional
that is embedded withinmanifold
3d. Human (i.e. faces
a surface
are in space), example
a typical that is of an
embedded within 3d.
cally low dimensional data set. Although an image of a face may require
• In this example, the blue points are confined to the pink
xels, a person mayarea,
surface be able to describe
which is embedded thisinperson with less ambient
a 3-dimensional than 50
es (e.g. male/female,
space. blond/dark hair, ...) along which faces vary.
 Data with low dimensional structure

• Human faces are a typical example of an intrinsically low

dimensional data set.
• Although an image of a face may require 18M pixels, a person
may be able to describe this person with less than 50
attributes (e.g. male/female, blond/dark hair, ...) along
which faces vary.
 Conclusion

• k-NN is a simple and effective classifier if distances reliably

reflect a semantically meaningful notion of the dissimilarity.
(It becomes truly competitive through metric learning)
• As n → ∞, k-NN becomes provably very accurate, but also
very slow.
• As d >> 0, points drawn from a probability distribution stop
being similar to each other, and the k-NN assumption breaks
down.
 Thank You

Contact: indujoshi@[Link]