# In KNN, why does the number of training examples needed to learn a decision boundary increase (exponentially) as the number of dimensions increases?

In book I'm reading the following is said on k-nearest neighbour algorithms:

"As the number of dimensions goes up, the number of training examples you need to locate the concept's frontiers goes up exponentially. With 20 Boolean attributes(features), there are roughly a million different possible examples"

My questions: 1)why exactly does the number of training examples needed to learn a decision boundary increase (exponentially) as the number of dimensions increases?

2)the quoted paragraph says that we need to have a data point in our training data corresponding to each possible example, but do we really need an actually training data point for each and every possible example?

(I can intuitively guess that performance is of course going to be better if we have training data for each possible example but I'd like to know exactly why?)

3)Does link to how in general statistics, as we introduce more parameters into a model, we need to collect more data?

• Are you / the passages from the book specifically addressing the case of all boolean features? Commented Jun 15, 2020 at 3:05
• Check about the curse of dimensionality, for example are stats.stackexchange.com/questions/159070/… Commented Jun 15, 2020 at 8:21
• @RyanVolpi Yes! Should've mentioned it's from the Master Algorithm by Domingos. I am interested in the case where all features are boolean and the general case including other variable types. Commented Jun 15, 2020 at 12:02

I'll try to answer your questions as they relate to the case of binary features since this is a much simpler case to think about. However, many of the statements I'll make about this case also apply somewhat to the case of continuous features.

I think your questions are much easier to answer when you can picture what's happening. I'll assume you know how KNN works generally, but consider specifically the case of all binary features. With two features, there are only four possible points an observation can take: {(0,0) (1,0) (0,1) (1,1)}. We can plot them below.

To understand how things change with added dimensions, we also plot all the possible values with three binary features.

2. Do we need a training data point for every possible example?

The answer is no, you don't need an observation for every possible point, but consider what happens in the case where you don't have a point in the training set, and you want to classify it. In the three binary-variable case, imagine we are trying to classify the blue point, but there are no observations at that point. We look elsewhere for the nearest neighbors, and we find that the three red points are each exactly a distance of one away. However, each of those points might correspond to many observations, meaning there may be thousands of observations that are all the same distance away from the position you want to classify. That doesn't prevent you from getting a prediction, but what kind of accuracy would you expect from a prediction that looks at all of those different points? In some cases, especially in higher dimensions, this might not be a problem. But there are many cases where we would not expect the set of all points equidistant away to be informative of the missing point. In the two-variable case we illustrated above, you'll see that each point is equidistant to two other points instead of three. This pattern continues for higher dimensions. In the case of $$m$$ binary variables, every possible point has $$m$$ other points that are all the same distance away.

1. Why exactly does the number of training examples needed to learn a decision boundary increase (exponentially) as the number of dimensions increases?

You can create a decision boundary in any number of dimensions with only two points. But, as we've shown, you want to have observations in your training set for every possible point. The number of possible points ($$n$$) grows exponentially with the number of dimensions ($$m$$): $$n=2^m$$. In three dimensions, there are $$2^3=8$$ possible points, but in twenty dimensions, there are $$2^{20}=1048576$$

3)Does this link to how in general statistics, as we introduce more parameters into a model, we need to collect more data?

In general, I don't believe the amount of data you need to fit some parameters grows exponentially with respect to the number of parameters. This answer suggests it does not. However, the above reasoning about binary features does generalize roughly to the case of continuous features. In higher dimensions, you'll notice the same trends. With increased dimensions, the volume of space grows exponentially, and more points become close to the same distance away. Many resources discuss issues with high dimensionality. You can search this stack for "curse of dimensionality," for example.

• For 2), would it be correct to say that in the example you provided, predicting the blue point to be red would be "optimal", given that although its three nearest points are equidistant, they are in fact red? Commented Jun 16, 2020 at 13:35
• Is it that in the example you provided the accuracy would be questionable if there were say one black point and one red point both equidistant from the blue point? Commented Jun 16, 2020 at 13:41
• For 2) I did not intend the color of the points to represent the correct label. In reality, the red points may correspond to any number of observations from different classes. With KNN you are assuming that closer points are more likely to be of the same class, and the issue with all binary features is that a very large number of points are all the same distance away. Of course, those points may still happen to be of the same class but in general you would not expect them to be. Commented Jun 16, 2020 at 15:13