Content
Summary
Machine learning is categorized into supervised learning, which uses labeled data for classification, and unsupervised learning, which identifies hidden structures in unlabeled data. Model effectiveness is evaluated using distinct training, validation, and test sets to prevent overfitting, while non-parametric methods like K-nearest neighbors face challenges such as the curse of dimensionality.
Intuition
Think of supervised learning as a teacher providing answer keys (labeled data) so the model can learn exact rules for classification. In contrast, unsupervised learning is like exploring a dark room (unlabeled data) to find natural groupings or clusters without prior knowledge. To ensure the model actually learns rather than just memorizing, we split data into three parts: training to learn parameters, validation to tune settings and prevent overfitting, and a final test set for unbiased evaluation. However, if the data has too many dimensions, the 'curse of dimensionality' makes finding meaningful neighbors difficult, especially for flexible non-parametric models like KNN.
Key equations
The classification function mapping an l-dimensional data domain to a discrete set of n+1 class labels.
The clustering function mapping an l-dimensional data domain to an estimated set of n̂+1 class labels.
The probability estimate for class c in KNN, where N_K is the set of K nearest neighbors and I is the indicator function.
The indicator function used in the KNN probability calculation.
The expected edge length of a hyper-cube in D dimensions needed to contain a fraction f of the data, illustrating the curse of dimensionality.
Derivation
- Supervised learning defines a function f mapping input space R^l to discrete labels {0,1,2,...,n} using labeled data.
- Unsupervised learning defines a function f̂ mapping input space R^l to estimated labels {0,1,2..., n̂} by discovering structure in unlabeled data.
- Non-parametric models like KNN estimate class probability by averaging indicator functions over K nearest neighbors.
- The curse of dimensionality shows that as dimensions D increase, the volume grows exponentially, making e_D(f) = f^(1/D) approach 1, meaning points are far apart.
- To evaluate models, data is split into training (optimize parameters), validation (optimize hyperparameters/prevent overfitting), and test (unbiased accuracy) sets.
Worked example
A researcher uses KNN with K=1 on a 100-dimensional dataset. They report 0% error on the training set but poor performance on new data. Explain why this happens using the provided concepts.
- K=1 induces a Voronoi tessellation where each region contains points closer to a specific training point.
- The training error is 0% because every training point is its own nearest neighbor.
- However, in high dimensions (D=100), the curse of dimensionality makes the concept of 'nearest' less meaningful.
- Most points are far from each other, so the model memorizes noise (overfitting) rather than learning generalizable rules.
- Without a validation set to tune K or a test set to measure generalization, this overfitting is not detected during development.
Answer The model overfits because K=1 memorizes training data exactly, and high dimensionality prevents meaningful neighbor estimation, leading to poor generalization.
Common mistakes
- Confusing 'algorithm' in computer science (step-by-step instructions) with 'algorithm' in machine learning (the learning procedure to find optimal parameters).
- Using training error to compare algorithms or select models, which fails because complex models always have lower training error due to overfitting.
- Assuming that a validation set alone is sufficient for evaluation without accounting for randomness in training data or initial weights, which may require multiple runs for reliable assessment.
- Believing that there is a universally 'best' learning algorithm, whereas the No Free Lunch Theorem indicates that performance is problem-dependent.