kNN, Naive Bayes, and SVMs

Naive Bayes assumes that once the class label is known, the features carry no further information about each other. That licenses replacing the whole likelihood P(features | class) with a product of one-feature terms P(x_i | class).

Laplace smoothing adds one pseudo-count to every word-class pair before dividing, so no estimated likelihood is exactly zero. Without it, a word never seen in a class drives that class's whole product to zero whatever the other words say.

Only the training points lying exactly on the margin boundary - the support vectors - hold the hyperplane in place. Every other point sits strictly further away, so removing it leaves the same widest street and the same fitted boundary.

A support vector machine optimises one hyperplane, which has exactly two sides, so its objective can only express a positive and a negative class. Forty categories are covered by training one SVM per class pair: 780 models.

Exact brute-force search compares the query against every stored point: O(nd) time per query for n stored points with d features each. Memory is the whole training set, all nd values plus their labels, held resident.

k-NN finds the k stored examples closest to the query, then aggregates their labels: for classification it predicts the class held by the most neighbours, and for regression it predicts the average of their target values.

C sets the price of a margin violation. A large C makes violations expensive, so the boundary narrows its margin and bends around individual points. A small C tolerates violations and buys a wider, more heavily regularised boundary.

Euclidean distance sums one term per feature, so its typical size grows with the number of features while its spread grows only like the square root. The relative gap between the nearest and the farthest point therefore shrinks toward zero.

Gamma sets how fast the RBF kernel's similarity decays with distance, so it is an inverse neighbourhood radius. Large gamma makes each training point influential only in a tiny region, producing an islands-around-points boundary that memorises the training set.

A kernel returns the inner product two points would have after being mapped into a high-dimensional feature space, computed straight from the original coordinates. An SVM needs only those inner products, so the lifted features are never built.

Match the likelihood to the feature type. Gaussian suits continuous readings assumed normal within each class, multinomial suits non-negative counts such as term frequencies, and Bernoulli suits binary present/absent flags where an absence is itself evidence.

When two classes are linearly separable, infinitely many hyperplanes separate them and all score zero training errors. The maximum-margin one sits as far as possible from the nearest point of each class, leaving a buffer that unseen points are less likely to cross.

The boundary starts jagged and grows smoother. At k=1 it wraps around individual points, including mislabelled ones; as k rises each prediction averages more neighbours, so the boundary flattens until, at k equal to the training-set size, every query gets the majority class.

The 0/1 error rate is a step function: flat almost everywhere, so its gradient carries no direction and minimising it directly is intractable. Hinge loss, max(0, 1 - y*score), is a convex upper bound on it that an optimiser can actually descend.

About a hundred million times more. Splitting each feature into ten bins gives 100 cells with 2 features and ten billion with 10, and the requirement grows like bins raised to the power of the feature count.

Cosine distance compares the direction of two count vectors and discards their length, so two sessions with the same browsing mix are treated as close even when one user viewed five times as many pages.

Manhattan adds absolute per-feature gaps instead of squaring them, so one badly mismatched feature is less overwhelming, and it matches domains where movement is axis-constrained, such as travel along a city grid.

Classification needs only which class scores highest, not the size of the score. Double-counted correlated evidence inflates the leading class, so a naive Bayes posterior of 0.99999 is meaningless, but the ordering of the classes — and therefore the predicted label — usually survives.

The functional margin of a point is the signed score y times (w.x + b); the geometric margin divides that by the length of w, giving an actual perpendicular distance. Rescaling w and b inflates the functional margin but leaves the geometric one unchanged.

It ignores them entirely. Any prediction within epsilon of the target has zero loss, so it does not pull on the fit and does not become a support vector. Only points on or beyond that tube shape the model.

A KD-tree splits space with axis-aligned cuts and keeps a best-so-far distance while searching. Any subtree whose bounding box is farther than that is skipped, still exactly. Add features and almost no box is far enough.

Distance-weighted k-NN gives each of the k neighbours a vote proportional to its closeness, typically 1/d or 1/d squared, instead of one vote each. Near neighbours dominate, far ones fade out, so the prediction becomes far less sensitive to the exact value of k.

One variable spread over 5,000 columns dominates the distance, so neighbours are chosen by merchant match rather than by the six numeric features. Take the ID block out of the metric, or model it separately, and re-measure the near/far contrast.

The score adds thousands of log-likelihood terms, so small per-feature errors compound and the log-odds land far from zero; exponentiating then saturates the posterior at 0 or 1. Treat the number as a ranking score, not a probability.

Kernel SVM training solves a quadratic program over an n-by-n matrix of pairwise kernel values, so cost grows between quadratically and cubically in rows. Subsample, drop the kernel for a linear model, or approximate the kernel.

Do the arithmetic first: 50 queries over 2 million rows is 100 million row-distances per second, so the work is memory-bound. Batch queries into one pass, store rows contiguously, cache squared norms, shard across cores.

The margin is a Euclidean distance in feature space, so a feature in dollars dwarfs one in [0,1]. Rescaling changes the weight vector's length and therefore what a unit of margin costs, so C must be re-tuned after any scaling change.

A kernel is an assumption about which points count as similar. The RBF default fails when Euclidean distance is not meaningful — heterogeneous or mostly-categorical features, very high dimensions where distances concentrate — or when the problem needs readable per-feature effects.

This is hubness, a high-dimensional artefact: points nearest the data centroid are slightly closer to everything, and once distances concentrate that edge wins almost every neighbour list. The mirror image is tracks retrieved by nobody.