Average your neighbors

Why use nearby inputs?

We want to estimate the mean output at input $x$. If several observations have exactly that input, we can average their outputs:

$\hat f(x)=\frac{1}{|D_x|}\sum_{i\in D_x}y_i,\qquad D_x=\{i:x_i=x\}.$

D_x is the set of rows whose input equals x. For an ideal continuously distributed input, a fixed target x has probability zero of matching any of a finite number of sampled rows. Rounded measurements can repeat, but exact matches may still be too scarce. An empty set has no sample average. So widen the target: take rows within a distance r of x.

$\hat f(x)=\frac{1}{|D_r(x)|}\sum_{i\in D_r(x)}y_i,\qquad D_r(x)=\{i:\lVert x_i-x\rVert\le r\}.$

‖x_i − x‖ is the distance between two input lists; for a single number it is just |x_i − x|. r is the window’s radius. Average the outputs of nearby examples, provided the neighborhood contains at least one example.

This assumes the conditional mean changes slowly enough nearby that neighbors have similar means. Otherwise their outputs tell you little about your target. With several features, also scale them sensibly: a distance dominated by dollars may ignore a meaningful change measured in another unit.

Dots within r of x₀ light up; their average is the estimate there. Trace it everywhere and compare to the rule.

Try it

Shrink r until windows come up empty and the trace turns jagged. Grow r past 1 and watch the bends flatten. Compare the intermediate radii. The useful range can change when you generate more observations.

The radius affects the estimate in two ways:

window	neighbors	the estimate
too small	a few, or none	the average of a couple of noisy y’s — jumps around from one dataset to the next
too big	many	includes dots whose x is far away, where the rule is different — the bends get blurred

These effects lead to the distinction between bias and variance.

Count the neighbors

For this calculation, suppose the N dots are uniformly distributed in a unit-radius ball and the radius-r neighborhood is centered at the ball’s center, with 0 ≤ r ≤ 1. The fraction that land in a window is the window’s share of the space:

dimension	the space	the window	window’s share
p = 1	a segment of length 2	a segment of length 2r	r
p = 2	a disc of area π·1²	a disc of area π·r²	r²
p = 3	a ball of volume k₃·1³	a ball of volume k₃·r³	r³
any p	volume k_p·1^p	volume k_p·r^p	r^p

k_p is whatever constant makes the volume formula work in p dimensions; it cancels. Each extra dimension multiplies the share by r again. Expected neighbors: N · r^p. A thousand dots and a window of radius 1/10:

p	share r^p	expected neighbors
1	1/10	100
2	1/100	10
3	1/1,000	1
5	1/100,000	0.01
10	1/10,000,000,000	0.0000001

Ten inputs, and this small centered window is almost always empty. Turn it around: to have 10 neighbors on average you need $r=(10/N)^{1/p}$ — 0.01 in one dimension, 0.1 in two, 0.22 in three, 0.40 in five, 0.63 in ten. By p = 10 the radius reaches about 63% of the full radius just to capture 1% of the volume. The neighborhood reaches far away even though it contains little probability mass. That is the curse of dimensionality: high-dimensional spaces can require enormous datasets to provide enough genuinely local examples. The volume calculation depends on the sampling distribution and the neighborhood location; near a boundary or in nonuniform data it changes.

Count how many of 1,000 sampled points fall within radius r of the center as the dimension changes.

How much of a cube fits inside its inscribed ball?

The course’s practice set uses a cube of side 2 with a ball of radius 1 inside it, touching every face. The ball’s share of the cube is $\pi^{p/2}/\bigl(2^p\Gamma(p/2+1)\bigr)$ — Γ is the factorial extended to fractions, so Γ(p/2 + 1) is “(p/2)!”:

p	1	2	3	4	5	6	8	10	12
ball ÷ cube	1	0.785	0.524	0.308	0.164	0.081	0.016	0.0025	0.0003

Fill the cube with dots and by p = 10 only one in 400 sits inside the ball: most of the cube’s volume lies outside the inscribed ball. And two random dots in the cube are typically √(2p/3) apart — each coordinate’s gap has average square 2/3, and squares add across coordinates — so distances grow like √p. This is the root-mean-square distance, and distances concentrate around this scale in high dimensions. Lower-dimensional structure in real data can make the effective problem much smaller.

Next

Local averaging can need too much data when inputs fill many dimensions. Another approach is to fit a model with shared parameters.