2025 Fall UVA CS - Machine Learning



TuTh 3:30pm-4:45PM

KNN and Theory

3Classification 5Theory Local ModelSelection

Att: the following markdown text was generated from the corresponding powerpoint lecture file automatically. Errors and misformatting, therefore, do exist (a lot!)!

K-Nearest Neighbor (KNN) Study Guide

Short-Answer Quiz

Answer each question in 2-3 sentences.

  1. Describe the three main categories of supervised classifiers and provide an example for each.
  2. Explain the concept of “lazy learning” as it applies to the K-Nearest Neighbor algorithm.
  3. What are the three essential components required for a K-Nearest Neighbor (Instance-based) method?
  4. Contrast the process for making a prediction in KNN for a regression task versus a classification task.
  5. What happens during the “Training Mode” of a naïve K-Nearest Neighbor algorithm?
  6. Outline the three steps involved in the “Testing Mode” when using KNN to classify an unknown sample.
  7. Why is feature scaling important for K-Nearest Neighbor algorithms? Provide a brief example.
  8. Discuss the bias-variance tradeoff when selecting the value of k. What is the effect of a k that is too small or too large?
  9. What is the “curse of dimensionality,” and how can it negatively impact the performance of a KNN model?
  10. According to the Cover and Hart theorem (1967), what is the asymptotic relationship between the error rate of 1-nearest-neighbor classification and the Bayes rate?

Quiz Answer Key

  1. The three major types of supervised classifiers are Discriminative, Generative, and Instance-based. Discriminative classifiers, like logistic regression or support vector machines, directly estimate a decision boundary. Generative classifiers, such as Naïve Bayes, build a statistical model of the data. Instance-based classifiers, like KNN, use the training observations directly without building an explicit model.

  2. Instance-based learning is referred to as “lazy learning” because the decision of the output value is delayed until a new instance arrives for prediction. In KNN, no model is built during a training phase; instead, the original training instances themselves represent the knowledge, and computation is deferred until a prediction is requested.

  3. The three essential components for a KNN method are: (1) the set of stored training samples, (2) a distance metric to compute the distance between samples (e.g., Euclidean distance), and (3) the value of k, which specifies the number of nearest neighbors to retrieve.

  4. For a regression task, where the target variable is continuous, KNN makes a prediction by taking the mean value of the k nearest training examples. For a classification task, where the target is discrete, the prediction is determined by a majority vote among the class labels of the k nearest neighbors.

  5. In the naïve version of the K-Nearest Neighbor algorithm, the training mode involves doing nothing other than storing the training samples. The algorithm does not build a model but simply retains the dataset, which will be used directly during the testing or deployment phase.

  6. The three steps in the testing mode are: (1) Compute the distance from the unknown sample to all records in the training set. (2) Identify the k nearest neighbors based on these computed distances. (3) Use the class labels of these nearest neighbors to determine the class label of the unknown record, typically by taking a majority vote.

  7. Feature scaling is important because attributes with larger ranges can dominate distance calculations, skewing the model’s performance. For example, if one feature is a person’s income (e.g., $10K to $1M) and another is height (e.g., 1.5m to 1.8m), the income attribute would have a much larger influence on the Euclidean distance calculation unless the features are scaled to a comparable range.

  8. When selecting k, a small value can lead to a model that is sensitive to noise points, resulting in high variance and an unstable, though potentially accurate, local model. Conversely, a large k can cause the neighborhood to include points from other classes, leading to a model with high bias and an inaccurate estimation, though it will be more stable.

  9. The “curse of dimensionality” refers to the problem where a nearest neighbor algorithm can be easily misled when working with high-dimensional data (i.e., data with many features). In a high-dimensional space, most points are far apart, and the concept of a “close” neighbor becomes less meaningful, especially if many attributes are irrelevant to the target function.

  10. The Cover and Hart theorem states that asymptotically (with an infinite number of training samples), the error rate of 1-nearest-neighbor classification is less than twice the Bayes rate. The Bayes rate is the error rate of an optimal classifier that knows the true data-generating model, representing the lowest achievable error.

Essay Questions

  1. Discuss the core principles of instance-based learning. How does KNN exemplify these principles, and what are the primary advantages and disadvantages of this “lazy” approach compared to “eager” learning models like linear regression?
  2. Explain the role of distance metrics in the KNN algorithm. Compare and contrast at least three different distance metrics mentioned in the source material (e.g., Euclidean, Manhattan, Mahalanobis) and discuss scenarios where one might be preferable over the others.
  3. Elaborate on the different variations of the standard KNN algorithm, such as Distance-Weighted KNN and RBF kernel Weighted KNN. How do these methods attempt to improve upon the naïve majority-vote approach?
  4. Describe the relationship between KNN, non-parametric density estimation, and the Bayes classifier. How can the principles of the Bayes classifier be used to provide a probabilistic interpretation for KNN?
  5. While KNN is conceptually simple, its computational cost can be a significant drawback. Discuss the computational time cost of the naïve KNN search and explain how a data structure like a KD Tree can be used to optimize the search for nearest neighbors.

Glossary of Key Terms

Term Definition
Asymptotic Analysis The study of an algorithm’s properties (like error rate) as the amount of data approaches infinity. In KNN, it shows the error rate of 1-NN is less than twice the Bayes rate.
Bayes Classifier A theoretically optimal classifier that minimizes the probability of classification error. It is achieved when density estimates converge to the true densities with an infinite number of samples.
Bayes Error The lower bound of the probability of classification error, which is the error achieved by the Bayes classifier.
Curse of Dimensionality A phenomenon where a nearest neighbor algorithm is easily misled when the input data has a high number of features (dimensions), making the concept of proximity less meaningful.
Discriminative Classifier A type of supervised classifier that directly estimates a decision rule or boundary. Examples include support vector machines, logistic regression, and neural networks.
Distance Metric A function used to compute the distance or similarity between two data samples. Examples include Euclidean, L1 norm (Manhattan), L∞ norm, and Mahalanobis distance.
Feature Scaling The process of scaling attributes to prevent distance measures from being dominated by features with large ranges.
Features The columns in a tabular dataset used for prediction, also known as attributes, dimensions, independent variables, covariates, predictors, or regressors.
Generative Classifier A type of supervised classifier that builds a generative statistical model of the data. Examples include Bayesian networks and Naïve Bayes classifiers.
Instance-based Learning A form of learning where the training instances themselves represent the knowledge. Predictions are made by searching for training instances that most closely resemble a new instance. It is also known as lazy learning.
K-Nearest Neighbor (KNN) An instance-based algorithm for classification or regression. It predicts the output for a new data point based on the outputs of its k closest neighbors in the training data.
KD Tree A data structure used to optimize the search for nearest neighbors (NN Search), reducing the computational time cost compared to a naïve search across all data points.
Lazy Learning A learning method where the generalization of the training data is deferred until a query is made to the system, as opposed to eager learning, where a model is constructed explicitly. KNN is a form of lazy learning.
Local Smoothness An underlying assumption in KNN that points that are close to each other in the feature space are likely to have similar target values.
Regression A supervised learning task where the target or outcome variable is a continuous, numerical value.
Supervised Classifier An algorithm that learns from a labeled dataset (where both features and outcomes are known) to classify new, unseen data.
Target The special column in a tabular dataset that is to be predicted, also known as the outcome, response, label, or dependent variable.
Voronoi Diagram A partitioning of a plane into regions based on the distance to points in a specific subset of the plane. It can be used to visualize the decision boundaries of a 1-nearest neighbor classifier.