I got this question in a quiz, it asked what will be the training error for a KNN classifier when K=1. What does training mean for a KNN classifier? My understanding about the KNN classifier was that it considers the entire data-set and assigns any new observation the value the majority of the closest K-neighbors. Where does training come into the picture? Also the correct answer provided for this was that the training error will be zero irrespective of any data-set. How is this possible?
Training error here is the error you'll have when you input your training set to your KNN as test set. When K = 1, you'll choose the closest training sample to your test sample. Since your test sample is in the training dataset, it'll choose itself as the closest and never make mistake. For this reason, the training error will be zero when K = 1, irrespective of the dataset. There is one logical assumption here by the way, and that is your training set will not include same training samples belonging to different classes, i.e. conflicting information. Some real world datasets might have this property though.
For a visual understanding, you can think of training KNN's as a process of coloring regions and drawing up boundaries around training data.
We can first draw boundaries around each point in the training set with the intersection of perpendicular bisectors of every pair of points. (perpendicular bisector animation is shown below)
To find out how to color the regions within these boundaries, for each point we look to the neighbor's color. When $K=1$, for each data point, $x$, in our training set, we want to find one other point, $x'$, that has the least distance from $x$. The shortest possible distance is always $0$, which means our "nearest neighbor" is actually the original data point itself, $x=x'$.
To color the areas inside these boundaries, we look up the category corresponding each $x$. Let's say our choices are blue and red. With $K=1$, we color regions surrounding red points with red, and regions surrounding blue with blue. The result would look something like this:
Notice how there are no red points in blue regions and vice versa. That tells us there's a training error of 0.
Note that decision boundaries are usually drawn only between different categories, (throw out all the blue-blue red-red boundaries) so your decision boundary might look more like this:
Again, all the blue points are within blue boundaries and all the red points are within red boundaries; we still have a test error of zero. On the other hand, if we increase $K$ to $K=20$, we have the diagram below. Notice that there are some red points in the blue areas and blue points in red areas. This is what a non-zero training error looks like.
When $K = 20$, we color color the regions around a point based on that point's category (color in this case) and the category of 19 of its closest neighbors. If most of the neighbors are blue, but the original point is red, the original point is considered an outlier and the region around it is colored blue. That's why you can have so many red data points in a blue area an vice versa.
In the KNN classifier with the k= 1 and with infinite number of training samples, the minimum error is never higher than twice the of the Bayesian error Reference