k-Nearest Neighbors & Naive Bayes with Laplace Smoothing
“Voronoi decision cells, non-parametric boundary complexity, conditional independence, and add-1 smoothing.”
1.Instance-Based vs Generative Classifiers
§ 2.1.k-Nearest Neighbors (k-NN): A non-parametric, lazy-learning algorithm that makes predictions based on the majority label among the k closest training points.
The Bias-Variance Knobs of k-NN:
- Small k (e.g. k=1): Complex, highly flexible decision boundary. High variance, zero training error, sensitive to outliers.
- Large k (e.g. k=N): Oversmoothed decision boundary predicting the global majority class. High bias.
Naive Bayes: A generative probabilistic classifier that assumes all features are conditionally independent given the class label. While the conditional independence assumption is rarely true in reality, Naive Bayes performs surprisingly well for high-dimensional text classification.
2. Worked Practice Problem: Laplace Smoothing Calculation
Do not forget to smooth both positive and negative conditional frequencies when estimating probabilities from sparse data.
Problem: In a binary text classification training set of 20 documents (12 Spam, 8 Ham), the word 'prize' appears in 6 Spam documents and 0 Ham documents. If the vocabulary size is |V| = 1000 words, compute the Laplace-smoothed probability P('prize' | Ham).
Step 1: Identify given parameters:
Count('prize', Ham) = 0
Total words in Ham documents = N_Ham = 800 words
Vocabulary size |V| = 1000 words
Step 2: Apply Laplace Add-1 Smoothing formula:
P('prize' | Ham) = [ Count('prize', Ham) + 1 ] / [ N_Ham + |V| ]
Step 3: Substitute values:
P('prize' | Ham) = (0 + 1) / (800 + 1000) = 1 / 1800 ≈ 0.000556.
Conclusion: Without Laplace smoothing, P('prize' | Ham) would be 0, zeroing out the entire posterior probability Product.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.