Support vector machines and k-nearest neighbours

In short

Support vector machines (SVM) and k-nearest neighbours (KNN) are two classical supervised learning algorithms that sit at opposite ends of the modelling spectrum: SVM fits one global decision boundary that maximises the margin between classes, while KNN stores the training data and decides each query locally by majority vote of its nearest neighbours. SVM dominates small-to-medium, high-dimensional problems (text, gene expression, handwriting) and KNN is the standard baseline, recommender-style matcher and teaching example for instance-based learning. Both are examined heavily in AICTE/CBCS machine learning papers and in GATE DA (Data Science and AI), where margin geometry, kernels, distance metrics and the curse of dimensionality are recurring questions. In Indian placement tests (TCS Digital, Infosys, Wipro, Accenture, Mu Sigma, Fractal, ZS, Flipkart, Swiggy) interviewers use them to test whether a candidate understands scaling, regularisation and the bias-variance effect of a single hyperparameter.

Explained

Separating hyperplanes and the maximum-margin idea

• A linear classifier in d dimensions is a hyperplane wᵀx + b = 0; prediction is sign(wᵀx + b), with w the normal vector and b the bias (intercept).
• If the classes are linearly separable, infinitely many separating hyperplanes exist. SVM chooses the unique one that maximises the margin - the perpendicular distance to the closest training points.
• Distance of a point x from the hyperplane = |wᵀx + b| / ||w||. Fixing the scale so that the closest points satisfy |wᵀx + b| = 1 (canonical form), the margin width becomes 2/||w||.
• Support vectors are the training points lying exactly on the margin boundaries (and, with soft margins, those inside or across them). Only these determine w and b - moving or deleting any other point changes nothing.
• SVM is a maximum-margin / large-margin classifier: a wide margin gives better generalisation (lower VC-dimension bound), which is why it works even when d > n (features outnumber samples).
• Labels are coded y ∈ {−1, +1} (not {0,1}) so that the constraint can be written compactly as yᵢ(wᵀxᵢ + b) ≥ 1.

Hard margin, soft margin and the C parameter

1. Hard-margin primal: minimise ½||w||² subject to yᵢ(wᵀxᵢ + b) ≥ 1 for all i. A convex quadratic programme (QP) - a single global optimum, no local minima.
2. Real data overlap, so slack variables ξᵢ ≥ 0 are introduced: yᵢ(wᵀxᵢ + b) ≥ 1 − ξᵢ. ξᵢ = 0 means correctly classified outside the margin; 0 < ξᵢ ≤ 1 means inside the margin; ξᵢ > 1 means misclassified.
3. Soft-margin primal: minimise ½||w||² + C Σξᵢ. C is the penalty for violations.
4. Role of C: large C → few violations tolerated, narrow margin, low bias / high variance (approaches hard margin, risks overfitting noise). Small C → wide margin, more violations, high bias / low variance. C is therefore the regularisation knob; in the loss view, 1/C plays the role of λ.
5. Hinge-loss view: soft-margin SVM is equivalent to minimising Σ max(0, 1 − yᵢ f(xᵢ)) + (1/2C)·... i.e. hinge loss + L2 penalty. The hinge loss is zero once a point is correctly classified beyond the margin - unlike logistic loss, which is never exactly zero.
6. Dual formulation: maximise Σαᵢ − ½ΣΣ αᵢαⱼyᵢyⱼ xᵢᵀxⱼ subject to 0 ≤ αᵢ ≤ C and Σαᵢyᵢ = 0. Then w = Σαᵢyᵢxᵢ, and only points with αᵢ > 0 (support vectors) contribute.
7. KKT conditions (examined as a derivation outline): αᵢ = 0 → point outside margin; 0 < αᵢ < C → point exactly on margin (used to compute b); αᵢ = C → point inside margin or misclassified.
8. Why the dual matters: it depends on data only through inner products xᵢᵀxⱼ, which opens the door to kernels. Solvers use SMO (sequential minimal optimisation), which optimises two multipliers at a time.

Kernels and non-linear SVM

• Map x to a higher-dimensional feature space φ(x) where classes become linearly separable. The kernel trick computes K(xᵢ, xⱼ) = φ(xᵢ)ᵀφ(xⱼ) without ever forming φ explicitly.
• Linear: K = xᵀz. Best for text / very high-dimensional sparse data; fast and interpretable (weights per feature).
• Polynomial: K = (γ xᵀz + r)^p. Degree p controls flexibility; p = 2 captures pairwise feature interactions.
• RBF (Gaussian): K = exp(−γ||x − z||²), γ > 0. The default general-purpose kernel; corresponds to an infinite-dimensional feature space. Equivalent form uses σ with γ = 1/(2σ²).
• Sigmoid: K = tanh(γ xᵀz + r) - occasionally used, not always a valid (positive semi-definite) kernel.
• Effect of γ in RBF: large γ → narrow bumps around each support vector → very wiggly boundary, overfitting; small γ → smooth, nearly linear boundary, underfitting. C and γ must be tuned jointly, usually by grid search with cross-validation on a log scale (e.g. C, γ ∈ {10⁻³ … 10³}).
• Mercer's theorem: a symmetric function is a valid kernel if its Gram matrix is positive semi-definite. Sums and products of valid kernels are valid kernels.
• Representer form: f(x) = Σ αᵢyᵢK(xᵢ, x) + b - prediction cost grows with the number of support vectors, so a model with 80% of points as support vectors is both slow and a sign of poor tuning.

Multi-class SVM, SVR and practical notes

• SVM is intrinsically binary. Extensions: one-vs-rest (K classifiers, pick the largest margin score) and one-vs-one (K(K−1)/2 classifiers, majority vote - what scikit-learn's SVC uses).
• Support vector regression (SVR): fit a tube of width ε around the function; errors inside the tube cost nothing (ε-insensitive loss), errors outside are penalised by C. Points on or outside the tube are the support vectors.
• One-class SVM / ν-SVM: ν ∈ (0,1] bounds the fraction of margin errors and support vectors; one-class SVM learns the support of a single distribution (used for novelty detection).
• SVM outputs a signed distance, not a probability. Probabilities come from Platt scaling (a logistic fit on the scores via internal cross-validation) - this is what probability=True does, and it is slow.
• Scaling is mandatory: ||w||² and ||x − z||² mix feature units, so a salary column in rupees swamps an age column. Standardise or min-max scale, fitting the scaler on train only.
• Class imbalance: use class_weight='balanced' to scale C per class rather than resampling blindly.
• Complexity: training is roughly O(n²d) to O(n³d) - SVMs become impractical above a few hundred thousand rows; use LinearSVC / SGD with hinge loss instead.

k-nearest neighbours: how it works

1. Instance-based, lazy, non-parametric: there is no training phase beyond storing the data (and perhaps building an index). All computation happens at query time - hence "lazy learning". It is also a memory-based and non-generalising method.
2. For a query x: compute distance to all n training points, take the k smallest, and (classification) assign the majority class, or (regression) the mean/median of the k neighbours' targets.
3. Distance metrics:
   • Euclidean (L2): √Σ(xᵢ − zᵢ)² - the default for continuous features.
   • Manhattan (L1): Σ|xᵢ − zᵢ| - more robust in high dimensions and for grid-like data.
   • Minkowski (Lp): (Σ|xᵢ − zᵢ|^p)^1/p; p = 2 is Euclidean, p = 1 is Manhattan.
   • Hamming - categorical/binary features; cosine distance - text and TF-IDF vectors; Mahalanobis - accounts for feature covariance.
4. Choosing k: k = 1 gives zero training error but very high variance (fits noise); large k smooths the boundary, raises bias, and k = n predicts the overall majority always. Choose by cross-validation; a common rough start is k ≈ √n. Use odd k for two-class problems to avoid ties.
5. Weighted KNN: weight each neighbour by 1/distance (or a kernel), so closer points count more - reduces sensitivity to k and breaks ties naturally.
6. Decision boundary is piecewise linear and irregular; with k = 1 it is exactly the Voronoi tessellation of the training points.
7. Speed-ups: KD-tree (efficient for d ≲ 20), ball-tree (better for higher d and non-Euclidean metrics), and approximate nearest neighbour libraries (LSH, HNSW, FAISS) for large-scale search. Brute force is O(nd) per query.
8. Curse of dimensionality: as d grows, all pairwise distances become nearly equal, so "nearest" loses meaning and the data needed to keep a neighbourhood locally dense grows exponentially. Remedy: feature selection or reduction before KNN.
9. Editing and condensing: condensed nearest neighbour (CNN) keeps a consistent subset (consistent with the full set's 1-NN labels, though not guaranteed to be the minimal such subset); edited NN (ENN) removes noisy/misclassified points - both shrink the stored set.
10. Missing values and categorical data must be handled explicitly (imputation, one-hot with care, or a mixed metric such as Gower).

Comparing the two, and when to use which

• Model type: SVM is a global, parametric-in-effect, eager learner (one boundary, fixed parameters after training); KNN is local, non-parametric, lazy.
• Cost profile: SVM = expensive training, cheap prediction; KNN = no training, expensive prediction and large memory. For a real-time API serving millions of requests, SVM (or a linear model) wins; for a rarely-queried prototype, KNN is fine.
• Dimensionality: SVM with a linear or RBF kernel handles d ≫ n well; KNN degrades badly as d rises.
• Noise/outliers: SVM with small C tolerates them; KNN with k = 1 is very sensitive, larger k helps.
• Interpretability: linear SVM gives per-feature weights; KNN explains a prediction by showing the actual neighbours - often more convincing to a business user.
• Shared requirement: both need feature scaling, and neither handles irrelevant features gracefully (SVM less badly than KNN).
• Decision boundaries: SVM smooth and margin-centred; KNN jagged and data-shaped - KNN can model arbitrarily complex shapes with enough data.

Key points

• Hyperplane - wᵀx + b = 0; classification by the sign of wᵀx + b.
• Margin - 2/||w|| in canonical form; SVM maximises it, equivalent to minimising ½||w||².
• Support vectors - the only training points that define the model; others can be deleted without effect.
• Hard vs soft margin - hard margin needs perfect separability; soft margin adds slack ξᵢ and penalty C.
• C - inverse regularisation strength: high C = low bias/high variance, low C = wide margin/high bias.
• Hinge loss - max(0, 1 − y f(x)); zero beyond the margin, which is what makes the solution sparse in support vectors.
• Dual problem - depends only on inner products, with 0 ≤ αᵢ ≤ C and Σαᵢyᵢ = 0; solved by SMO.
• Kernel trick - replace xᵢᵀxⱼ by K(xᵢ, xⱼ) to work in a high-dimensional space without computing φ(x).
• RBF γ - controls boundary wiggliness; large γ overfits, small γ underfits.
• Mercer condition - a valid kernel has a positive semi-definite Gram matrix.
• SVR - ε-tube regression; errors inside the tube are free.
• Multi-class SVM - one-vs-rest (K models) or one-vs-one (K(K−1)/2 models).
• KNN - lazy, instance-based, non-parametric; prediction = majority vote (or mean) of k nearest points.
• k - small k = high variance, large k = high bias; tune by cross-validation, use odd k for binary tasks.
• Distance metric - Minkowski family (L1, L2), cosine for text, Hamming for categorical; always scale first.
• Curse of dimensionality - distances concentrate in high d, so KNN loses discriminating power.
• KD-tree / ball-tree - index structures that cut query time below brute-force O(nd).
• Cost asymmetry - SVM: slow train, fast predict; KNN: no train, slow predict.

Formulas and examples

Example 1 - margin width and classification from a given hyperplane. A linear SVM trained on two features (experience in years, CTC in ₹ lakh per annum) gives w = (2, −1), b = −3, i.e. 2x₁ − x₂ − 3 = 0.

• ||w|| = √(2² + (−1)²) = √5 ≈ 2.2361.
• Margin width M = 2/||w|| = 2/2.2361 ≈ 0.894 units (in the scaled feature space).
• Candidate A = (4, 2): f = 2(4) − 2 − 3 = +3 → class +1; distance = 3/2.2361 ≈ 1.342, well outside the margin, so αᵢ = 0 (not a support vector).
• Candidate B = (2, 1): f = 4 − 1 − 3 = 0 → exactly on the boundary, undefined/ambiguous class.
• Candidate C = (1, 1): f = 2 − 1 − 3 = −2 → class −1; distance = 2/2.2361 ≈ 0.894.

Example 2 - deriving w and b for a two-point separable problem. Positive point x⁺ = (3, 3), y = +1; negative point x⁻ = (1, 1), y = −1; both are support vectors.

• The optimal w is parallel to x⁺ − x⁻ = (2, 2), so w = k(1, 1).
• Canonical constraints: wᵀx⁺ + b = +1 → 6k + b = 1; wᵀx⁻ + b = −1 → 2k + b = −1.
• Subtracting: 4k = 2 → k = 0.5, so w = (0.5, 0.5); then b = 1 − 6(0.5) = −2.
• Check: ||w|| = √0.5 ≈ 0.7071 → margin = 2/0.7071 ≈ 2.828, which equals the distance between the two points ||(2,2)|| = 2.828. Consistent.
• Boundary: 0.5x₁ + 0.5x₂ − 2 = 0, i.e. x₁ + x₂ = 4 - the perpendicular bisector of the segment, as expected.

Example 3 - KNN classification by hand, with and without scaling. Training data for shortlisting candidates; query Q = (CGPA 7.6, coding score 62).

Raw Euclidean distances from Q = (7.6, 62):

• P1: √(0.4² + 8²) = √(0.16 + 64) = √64.16 ≈ 8.010
• P2: √(0.6² + 7²) = √(0.36 + 49) = √49.36 ≈ 7.026
• P3: √(0.2² + 3²) = √(0.04 + 9) = √9.04 ≈ 3.007
• P4: √(1.1² + 2²) = √(1.21 + 4) = √5.21 ≈ 2.283
• P5: √(0.9² + 12²) = √(0.81 + 144) = √144.81 ≈ 12.034

k = 3 nearest: P4 (2.283, Rejected), P3 (3.007, Shortlisted), P2 (7.026, Rejected) → majority Rejected. Note the CGPA term contributes almost nothing - the coding score dominates purely because of its scale.

Now min-max scale each column to [0,1] (CGPA range 6.5-8.5 → divide by 2.0; score range 50-70 → divide by 20). Q becomes ((7.6−6.5)/2, (62−50)/20) = (0.55, 0.60).

• P1 (0.75, 1.00): √(0.20² + 0.40²) = √(0.04 + 0.16) = √0.20 ≈ 0.447
• P2 (0.25, 0.25): √(0.30² + 0.35²) = √(0.09 + 0.1225) = √0.2125 ≈ 0.461
• P3 (0.65, 0.75): √(0.10² + 0.15²) = √(0.01 + 0.0225) = √0.0325 ≈ 0.180
• P4 (0.00, 0.50): √(0.55² + 0.10²) = √(0.3025 + 0.01) = √0.3125 ≈ 0.559
• P5 (1.00, 0.00): √(0.45² + 0.60²) = √(0.2025 + 0.36) = √0.5625 = 0.750

k = 3 nearest: P3 (0.180, Shortlisted), P1 (0.447, Shortlisted), P2 (0.461, Rejected) → majority Shortlisted. Scaling flipped the answer - this is the single most common KNN exam/interview point.

Example 4 - KNN regression, plain and distance-weighted. Predict monthly rent (₹) from flat area; the k = 3 nearest flats have targets ₹18,000 (d = 1.0), ₹22,000 (d = 2.0), ₹28,000 (d = 4.0).

• Simple mean: (18,000 + 22,000 + 28,000)/3 = 68,000/3 ≈ ₹22,667.
• Inverse-distance weights: 1/1 = 1, 1/2 = 0.5, 1/4 = 0.25; Σw = 1.75.
• Weighted sum = 18,000(1) + 22,000(0.5) + 28,000(0.25) = 18,000 + 11,000 + 7,000 = 36,000.
• Weighted prediction = 36,000/1.75 ≈ ₹20,571 - pulled towards the closest flat, as intended.

Example 5 - RBF kernel value and the effect of γ. x = (1, 2), z = (2, 4): ||x − z||² = (−1)² + (−2)² = 5.

• γ = 0.1 → K = e^−0.5 ≈ 0.6065 (points look similar; smooth boundary).
• γ = 1 → K = e⁻⁵ ≈ 0.00674 (almost dissimilar).
• γ = 10 → K = e⁻⁵⁰ ≈ 1.9 × 10⁻²² ≈ 0 - each support vector influences only its immediate neighbourhood, so the model memorises the training set. Large γ with large C is the classic overfitting combination.

from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import GridSearchCV, StratifiedKFold

cv = StratifiedKFold(n_splits=5, shuffle=True, random_state=42)

# Scaler inside the pipeline so it is re-fitted on each CV training fold only
svm = Pipeline([("sc", StandardScaler()), ("clf", SVC(kernel="rbf"))])
gs_svm = GridSearchCV(svm,
                      {"clf__C": [0.1, 1, 10, 100],
                       "clf__gamma": [1e-3, 1e-2, 0.1, 1]},
                      cv=cv, scoring="f1_macro").fit(X, y)

knn = Pipeline([("sc", StandardScaler()), ("clf", KNeighborsClassifier())])
gs_knn = GridSearchCV(knn,
                      {"clf__n_neighbors": [1, 3, 5, 7, 11, 15, 21],
                       "clf__weights": ["uniform", "distance"],
                       "clf__p": [1, 2]},
                      cv=cv, scoring="f1_macro").fit(X, y)

print(gs_svm.best_params_, gs_svm.best_score_)
print(gs_knn.best_params_, gs_knn.best_score_)
print("support vectors per class:", gs_svm.best_estimator_["clf"].n_support_)

Where it is used

• IT services and analytics firms (TCS, Infosys, Wipro, Accenture, Fractal, Mu Sigma, ZS): SVM for text and ticket classification, sentiment and churn models on small labelled datasets; KNN as the baseline every model must beat.
• Banking, NBFC and fintech (HDFC, ICICI, Paytm, PhonePe, CIBIL-linked scorecards): SVM/one-class SVM in fraud and anomaly screening; KNN for "similar customer" matching in cross-sell. Note that RBI's model-governance expectations and the Digital Personal Data Protection Act, 2023 push regulated lenders towards explainable models, so a black-box RBF SVM usually needs documentation and a challenger model.
• Healthcare and bio-informatics (AIIMS/IIT research groups, Tata Memorial, diagnostic AI startups): SVM is a standard choice for gene-expression and medical-image classification where n is small and d is huge.
• E-commerce and delivery (Flipkart, Myntra, Swiggy, Zomato, Nykaa): approximate nearest-neighbour search (FAISS/HNSW) behind visual search, "similar products" and vector-embedding recommenders - KNN at production scale.
• OCR, biometrics and government systems: handwritten digit/character recognition and signature verification historically ran on SVM; nearest-neighbour matching underlies deduplication and template matching in large identity and document-digitisation projects.
• Job roles: data scientist, ML engineer, data analyst, quantitative analyst, research associate; also lab/mini-project work in B.Tech AI&DS where SVM and KNN are the mandated classifiers.

Interview questions

• Q: What exactly does an SVM maximise, and why does that help? A: It maximises the margin 2/||w||, the distance from the boundary to the nearest points of each class; a wider margin means a less complex decision rule and better generalisation to unseen data.
• Q: What is a support vector? A: A training point lying on the margin boundary or violating it (αᵢ > 0); only these points determine w and b, so the rest can be removed without changing the model.
• Q: What does the C parameter do? A: It penalises margin violations - large C fits the training data tightly with a narrow margin (high variance), small C allows violations for a wider, smoother boundary (high bias). It is the inverse of regularisation strength.
• Q: Explain the kernel trick in one line. A: Since the dual objective uses only inner products, replacing xᵢᵀxⱼ with K(xᵢ, xⱼ) gives a linear boundary in a high-dimensional space while all computation stays in the original space.
• Q: How do C and γ differ in an RBF SVM? A: C controls how much misclassification is tolerated; γ controls the reach of each support vector - high γ makes the boundary wiggly and local, so high C with high γ is the classic overfit.
• Q: Why is KNN called a lazy learner? A: It builds no model at training time - it just stores the data - and defers all computation to the query, when it finds the k nearest points and votes.
• Q: How do you choose k? A: By cross-validation over a range of values, favouring odd k for binary problems to avoid ties; small k overfits noise and large k over-smooths towards the majority class.
• Q: Why must features be scaled before KNN and SVM? A: Both use distances or norms, so a feature with a large numeric range (salary in rupees) dominates one with a small range (CGPA), distorting neighbours and the margin alike.
• Q: What is the curse of dimensionality for KNN? A: As dimensions grow, the ratio of nearest to farthest distance tends to 1, so neighbours stop being meaningfully "near" and the required sample size grows exponentially.
• Q: SVM or KNN for a real-time prediction service with millions of training rows? A: SVM (or a linear model) - it trains once and predicts in O(#SV × d); KNN would need the whole dataset in memory and an O(nd) scan per request unless an approximate index is used.
• Q: Does an SVM give class probabilities? A: Not natively; it returns a signed distance. Probabilities require Platt scaling (a logistic fit on the scores with internal cross-validation), which adds cost and can be poorly calibrated on small data.
• Q: Can KNN be used for regression and can SVM handle outliers in the target? A: Yes - KNN regression averages the neighbours' targets; SVR's ε-insensitive tube plus a modest C makes SVM fairly robust to target outliers compared with squared-error regression.

Common mistakes

• Forgetting to scale features, or scaling before the train-test split / outside the CV pipeline - which leaks test information and inflates reported accuracy.
• Saying "SVM has no regularisation": minimising ½||w||² *is* L2 regularisation, and C sets its strength.
• Confusing the roles of C and γ, or claiming a larger γ smooths the boundary (it does the opposite).
• Writing the margin as 1/||w|| instead of 2/||w||, or dropping the canonical scaling |wᵀx + b| = 1 while deriving it.
• Treating every training point as a support vector, or using {0, 1} labels in the constraint yᵢ(wᵀxᵢ + b) ≥ 1, which breaks the algebra.
• Choosing even k in a two-class KNN problem, then having no tie-break rule; or claiming k = 1 is best because its training error is zero.
• Running KNN on hundreds of raw dimensions (or on one-hot encoded high-cardinality columns) without any dimensionality reduction, and calling the poor result a data problem.

Related topics

Linear and logistic regression · Overfitting, bias-variance and regularisation · Dimensionality reduction and PCA · Model evaluation metrics · Clustering: k-means and hierarchical · Anomaly detection