Other core algorithms

Three algorithms can learn from the same labelled table for three very different reasons.

k-NN trusts nearby examples. An SVM searches for a wide separating boundary. Naive Bayes multiplies class-conditional evidence.

Why this matters

Not every tabular problem needs a tree ensemble.

Neighbour methods are transparent local baselines. Linear SVMs can excel on high-dimensional sparse text. Kernel SVMs capture nonlinear boundaries on suitable smaller datasets. Naive Bayes trains quickly and provides a strong sparse-text baseline.

Plain-English mental model

Part 1 — k-NN stores examples and delays the work

k-nearest neighboursk-nearest neighboursA non-parametric method that predicts from the targets of the k training examples closest to a query under a chosen distance. Classification votes or averages class values; regression averages numerical targets., shortened to k-NN, has a minimal fitting stage:

1. Store training features and targets.
2. For a query, calculate distance to training examples.
3. Select the closest k.
4. Combine their targets.

Classification:

prediction = majority vote or distance-weighted vote

Regression:

prediction = mean or distance-weighted mean target

k-NN is sometimes called a lazy learner because prediction performs most of the search.

Part 2 — Distance defines “near”

A distance metricDistance metricA rule for quantifying how far two feature vectors are, such as Euclidean or Manhattan distance. Its meaning depends on representation, units, scaling, missing-value handling, and domain relevance. quantifies separation between feature vectors.

Euclidean distance:

d(x,q) = square_root(Σ(x_j-q_j)²)

Manhattan distance:

d(x,q) = Σ|x_j-q_j|

Cosine distance is often defined from cosine similarity:

distance = 1 - cosine_similarity

Choice depends on representation. Euclidean distance on one-hot categories means something different from Euclidean distance on physical coordinates.

Scale can dominate

Suppose:

• age ranges 18–90;
• annual income ranges 15,000–300,000.

Raw Euclidean distance is dominated by income units.

Standardise numerical features using training statistics:

scaled = (value - training_mean) / training_std

Apply the frozen transform to validation, test, and query rows.

Part 3 — Calculate a neighbour prediction

Expected output:

[(1.414, 'billing'), (2.0, 'billing'), (2.236, 'billing')]
{'billing': 3}
prediction: billing

Part 4 — Choosing k changes smoothness

Small k:

• captures local detail;
• sensitive to noise and single points;
• produces irregular decision boundaries.

Large k:

• smooths local variation;
• may ignore minority neighbourhoods;
• eventually approaches the global majority.

Choose odd k to reduce binary vote ties, but ties can still occur with multiple classes or distance weighting.

Select k with validation or cross-validation. Do not choose it because a training plot looks attractive.

Part 5 — The curse of dimensionality

The curse of dimensionalityCurse of dimensionalityA collection of effects that appear as feature dimensions grow, including rapidly expanding space and less informative nearest-neighbour distances unless data grows enormously or representation has useful structure. describes problems that appear as dimensions grow.

If each feature ranges from 0 to 1, the unit hypercube volume stays 1, but neighbourhood volume becomes difficult to cover. To span only 10% of each coordinate:

1 dimension: 0.1 of the interval
10 dimensions: 0.1¹⁰ of the volume

Data becomes sparse, and nearest and farthest distances can become less distinguishable.

Responses:

• select relevant features;
• learn or choose a meaningful embedding;
• reduce dimension;
• use cosine similarity for suitable text embeddings;
• collect more representative data;
• choose another model.

Do not apply k-NN to thousands of raw noisy columns and assume “nearest” means similar.

Part 6 — k-NN engineering trade-offs

Training is cheap; prediction can be expensive:

brute-force query cost ≈ number of rows × dimensions

Search structures:

• k-d trees;
• ball trees;
• approximate nearest-neighbour indexes.

Their effectiveness depends on metric, dimension, and accuracy/latency trade-offs.

k-NN also stores training examples. For personal or sensitive data, this creates retention, deletion, access-control, and possible information-exposure concerns.

Part 7 — SVMs prefer a wide margin

A linear classifier has boundary:

w · x + b = 0

A support-vector machineSupport-vector machineA model that chooses a separating boundary with a large margin, allowing controlled violations in the soft-margin form. The closest influential training examples are support vectors., shortened to SVM, chooses a separating boundary with a large marginMarginThe distance between an SVM decision boundary and the closest class-constraining examples. Maximising it expresses a preference for a robust separator, balanced against training violations through regularisation..

The margin is the corridor between the boundary and closest class-constraining examples.

Those closest influential points are support vectorsSupport vectorA training example on or inside the SVM margin that directly influences the fitted decision boundary. Many more distant examples can move without changing that boundary..

Distant training points often do not change the fitted boundary unless they move into the margin.

Hard margin versus soft margin

A hard-margin SVM requires perfect separation. It fails when classes overlap and is brittle to outliers.

A soft-margin SVM allows violations through slack variables.

Hyperparameter C controls penalty:

• larger C: violations cost more; fit training data more aggressively;
• smaller C: violations cost less; wider margin and stronger regularisation.

This convention applies to common SVM APIs, but always check library definitions.

Part 8 — Hinge loss

For labels y ∈ {-1,+1} and score f(x)=w·x+b:

hinge loss = max(0, 1 - y f(x))

If y f(x) ≥ 1, the example is correctly placed outside the margin and loss is zero.

If it is inside the margin or incorrectly classified, loss is positive.

The SVM objective balances:

• a small weight norm, which corresponds to a wider margin;
• penalties for hinge-loss violations.

SVM scores are not probabilities by default. Probability calibration is a separate fitted procedure requiring held-out or cross-validated evidence.

Part 9 — Kernels create nonlinear boundaries

A linear SVM separates with a hyperplane in its feature space.

A feature map can add nonlinear coordinates:

(x1, x2) → (x1², square_root(2)x1x2, x2²)

The kernel trickKernel trickComputing inner products corresponding to a richer feature mapping without explicitly constructing every mapped coordinate. It allows an SVM to form nonlinear boundaries while keeping a linear separator in the implicit feature space. computes inner products in an implicit richer space without explicitly constructing all mapped coordinates.

Common kernels:

• linear: K(x,z)=x·z;
• polynomial;
• radial basis function, shortened to RBF;
• sigmoid, used less commonly.

RBF:

K(x,z) = exp(-gamma × ||x-z||²)

gamma controls locality:

• high gamma: influence falls quickly; flexible boundary and overfitting risk;
• low gamma: broad influence; smoother boundary and underfitting risk.

Scale features before RBF SVM, because squared distance drives the kernel.

Part 10 — SVM computational choices

Kernel SVM training can scale poorly with the number of rows because it uses pairwise similarities. Exact complexity depends on data and solver, but large datasets can become expensive in time and memory.

For large sparse text:

• use a linear SVM implementation designed for many rows/features;
• avoid an RBF kernel by default;
• compare logistic regression and Naive Bayes.

For smaller nonlinear datasets:

• scale features;
• tune C and gamma inside cross-validation;
• compare against trees and simpler baselines.

Part 11 — Naive Bayes applies Bayes by class

For class c and features x:

P(c | x) ∝ P(c) × P(x | c)

Naive BayesNaive BayesA probabilistic classifier that combines class priors with feature likelihoods using a conditional-independence assumption. The assumption is often unrealistic, but the model can work well for sparse text and small-data baselines. assumes features are conditionally independentConditional independenceTwo variables are conditionally independent given a third when knowing one provides no additional information about the other after the third is known. Naive Bayes assumes features are conditionally independent given the class. given the class:

P(x1, x2, ... | c)
= P(x1|c) × P(x2|c) × ...

Text words are not truly independent. “credit” and “card” correlate. The assumption still produces a useful, fast classifier in many sparse problems.

Work in log space

Multiplying many tiny probabilities underflows:

log score(c)
= log P(c) + Σ log P(feature_j | c)

Choose the largest log score, or use stable log-sum-exp to normalise.

Part 12 — A small text calculation

Training counts:

Without smoothing, P(server|billing)=0, so any document containing server gives billing score zero.

Laplace smoothingLaplace smoothingAdding a positive pseudo-count, commonly one, to categorical or word counts before estimating probabilities. It prevents unseen training combinations from forcing a Naive Bayes class score to zero. adds one to every vocabulary count:

P(word | class)
= (count(word,class)+1) / (total_words_in_class + vocabulary_size)

Smoothing strength is a hyperparameter in general additive smoothing.

Expected output:

{'billing': 0.376, 'technical': 0.624}

The result depends on simplified counts, vocabulary, tokenisation, smoothing, and independence assumptions.

Part 13 — Naive Bayes variants

Choose a likelihood model matching feature type.

Gaussian Naive Bayes

Models each numeric feature with a Gaussian distribution per class.

Suitable baseline for continuous features when the approximation is reasonable.

Multinomial Naive Bayes

Models non-negative counts or count-like values.

Common for word-count and TF–IDF-style text features, though TF–IDF is not literally generated by a multinomial count process.

Bernoulli Naive Bayes

Models binary feature presence/absence.

Useful when whether a token appears matters more than how often.

Complement Naive Bayes

Uses statistics from the complement of each class and is often useful for imbalanced text classification.

Validate variants; names describe assumptions, not guaranteed winners.

Part 14 — Probability quality and duplicated evidence

Naive Bayes posterior numbers can be overconfident because correlated features are multiplied as if independent.

If refund, refunds, and refunding all encode nearly the same evidence, the model may count it several times.

Evaluate:

• discrimination;
• calibration;
• errors by class and group;
• robustness to vocabulary and tokenisation;
• out-of-vocabulary behaviour;
• probability stability under duplicated correlated features.

Use calibrated probabilities when downstream decisions require trustworthy risk estimates.

Worked comparison — ticket topic classification

Goal: classify a new ticket as billing or technical.

k-NN

Represent messages with embeddings, scale any added numeric features, and retrieve nearby labelled tickets.

Strength: inspect actual neighbours.

Risk: embedding distance may not match topic; queries grow expensive; stored examples may expose sensitive text.

Linear SVM

Represent messages with sparse TF–IDF features and fit a wide-margin separator.

Strength: strong high-dimensional sparse baseline.

Risk: score is not a probability; tune C; inspect token and label bias.

Multinomial or Complement Naive Bayes

Use token counts or suitable non-negative text features with smoothing.

Strength: extremely fast and effective with small sparse data.

Risk: correlated words and likelihood assumptions can create overconfidence.

Selection

Use the same time-and-customer split. Compare the declared metric, calibration if required, latency, memory, privacy, and explainability.

The best algorithm depends on representation and operating constraints, not the name.

In a real AI system

Common mistakes

Exercises

Knowledge check

Practice activity

from math import dist

training = [
    ((0, 0), "billing"),
    ((1, 0), "billing"),
    ((0, 1), "billing"),
    ((4, 4), "technical"),
]
query = (2, 1)

neighbours = sorted(
    (dist(point, query), label)
    for point, label in training
)[:3]

margin_score = query[0] + query[1] - 2.5

print("neighbours:", [(round(d, 3), label) for d, label in neighbours])
print("k-NN:", "billing")
print("margin score:", margin_score)
print("SVM-style class:", int(margin_score >= 0))
print("Naive Bayes:", {"billing": 0.376, "technical": 0.624})

neighbours: [(1.414, 'billing'), (2.0, 'billing'), (2.236, 'billing')]
k-NN: billing
margin score: 0.5
SVM-style class: 1
Naive Bayes: {'billing': 0.376, 'technical': 0.624}

Key takeaways

Flashcards

One-page sketchnote summary

knn = vote(nearest(query, k, metric))
svm_class = sign(weights @ features + bias)
log_score[class] = log(prior[class]) + sum(log_likelihoods)
posterior = softmax(log_scores)

Resources