Appearance
12.3.5 — The Other Classical Tools
Linear models and boosted trees cover most tabular problems. Three more classical methods are worth knowing properly, each for a different reason. Nearest neighbours is the simplest idea in machine learning and the direct ancestor of how semantic search and retrieval work today. Naive Bayes is Bayes' rule from 12.2.5 turned into a classifier, and for text it is still a baseline you should run in the first hour of any project. Support vector machines dominated machine learning in the 2000s, and the idea behind them, a maximum safety margin, still appears throughout the field.
The page ends with sentiment analysis, the classic text problem, because it pulls all three together and shows where classical methods stop and LLMs take over.
1. k-nearest neighbours: you are like the people you resemble
Go back to the three customers of 12.2.1: Asha (4, 3), Bilal (8, 6) and Chen (1, 7), each described by their electronics and grocery orders last year. A new customer, Dev, arrives with (5, 4). Cartwise wants to guess what Dev will like, and it knows what Asha, Bilal and Chen liked.
The simplest possible approach: find the customers most similar to Dev, and assume Dev is like them. That is k-nearest neighbours, usually written k-NN. To classify or predict for a new example, find the k training examples closest to it, and let them vote (for a category) or average (for a number). The k is just how many neighbours you ask, typically 5 or 10.
k-NN has a peculiar property: it does no training at all. It simply stores the examples. All the work happens at prediction time, when it measures the distance from the new example to every stored one. Methods like this are called lazy learners, in contrast to the logistic regressions and trees that do their work up front and then predict instantly.
Which distance?
Everything depends on what "closest" means, and the choice changes the answer. Here are the two most common measures, computed for Dev.
Euclidean distance is the straight-line distance from Pythagoras, the length of the arrow from one point to the other:
d(\mathbf{a}, \mathbf{b}) = \sqrt{\sum_i (a_i - b_i)^2}
From Dev (5,4): to Asha it is \sqrt{1^2 + 1^2} \approx 1.41; to Bilal, \sqrt{3^2 + 2^2} \approx 3.61; to Chen, \sqrt{4^2 + 3^2} = 5. By this measure Dev's nearest neighbour is Asha, then Bilal, then Chen.
Cosine similarity compares only directions, as 12.2.1 showed: Dev to Asha is \frac{32}{6.40 \times 5} \approx 0.9995, Dev to Bilal is \frac{64}{6.40 \times 10} \approx 0.9995, and Dev to Chen is \frac{33}{6.40 \times 7.07} \approx 0.73. By this measure Asha and Bilal are equally close to Dev, because all three have the same taste, and Chen is far.
Neither is "right". Euclidean distance says "Dev shops about as much as Asha", and cosine says "Dev wants the same kind of things as Asha and Bilal". For recommending products, taste is what matters, so cosine is usually the better choice. For text, cosine is almost always the choice, because a long document and a short one about the same topic should count as similar even though one has far bigger word counts. There is also Manhattan distance, the sum of the absolute differences, named after walking the street grid of Manhattan, where you cannot cut diagonally across blocks. It is less thrown off by one huge difference than Euclidean distance is.
One rule is non-negotiable with distances: put features on the same scale first, using the standardisation of 12.2.4. If one feature is "amount in rupees" (up to 200,000) and another is "account age in years" (up to 10), the amount completely dominates every distance, and account age might as well not exist.
Two weaknesses, and why they shaped modern search
It is slow at prediction time. To classify one new order against ten million stored ones, k-NN must compute ten million distances. That is fine offline and far too slow for a checkout that needs an answer in 50 milliseconds. The solution, which is a whole industry today, is approximate nearest neighbour search: index the stored vectors cleverly so that you can find very close neighbours while checking only a tiny fraction of them. Chapter 12.6.3 builds it, because it is exactly how "find the documents most similar to this question" works in every retrieval system.
Distances lose meaning in many dimensions. This is called the curse of dimensionality, a phrase coined by the mathematician Richard Bellman in 1957. Here is a concrete way to feel it. Suppose your data is spread evenly through a cube, and you want a small neighbourhood around a point that contains 10 percent of the data. In 2 dimensions, the neighbourhood needs sides about 0.32 of the cube's width, because 0.32^2 \approx 0.1. In 10 dimensions it needs sides about 0.1^{1/10} \approx 0.79 of the width. In 100 dimensions, about 0.98. Your "small neighbourhood" has to cover nearly the whole range of every feature, so the neighbours are not really near at all. In very high dimensions, the nearest and farthest points end up at nearly the same distance.
So why does nearest-neighbour search work so well for modern embeddings, which have hundreds of dimensions? Because real data is not spread evenly through all those dimensions. Product descriptions and questions occupy a thin, structured region, and well-trained embeddings put similar meanings close together within it. Chapter 12.6.1 explains how that structure is learned.
2. Naive Bayes: Bayes' rule, one word at a time
Cartwise's support inbox needs to route emails into teams. Take just two teams, refunds and delivery, and three past emails for each:
| Refund emails | Delivery emails |
|---|---|
| "refund money" | "parcel late" |
| "money back" | "where parcel" |
| "refund please" | "late delivery" |
A new email arrives: "late money parcel". Which team?
Bayes' rule says the probability of a class given the words is proportional to the probability of those words given the class, times how common the class is:
P(\text{class} \mid \text{words}) \propto P(\text{words} \mid \text{class}) \times P(\text{class})
The symbol \propto means "is proportional to": we can skip dividing by P(\text{words}) because it is the same for both classes, and we only need to compare them.
The hard part is P(\text{words} \mid \text{class}): the probability of this exact combination of words in a refund email. With thousands of possible words, almost no combination has ever been seen before. So naive Bayes makes a bold simplification: it pretends each word appears independently of the others, given the class. Then the probability of the combination is just the product of the individual word probabilities:
P(\text{late, money, parcel} \mid \text{refund}) = P(\text{late} \mid \text{refund}) \times P(\text{money} \mid \text{refund}) \times P(\text{parcel} \mid \text{refund})
The independence assumption is plainly false: "money" and "back" clearly tend to appear together. That falseness is why the method is called "naive". It works surprisingly well anyway, because classification only needs the right class to come out on top, not accurate probabilities, and the errors from the false assumption often affect both classes similarly.
Working it out
Each word's probability within a class comes from counting. The refund emails contain 6 words in total: "refund" twice, "money" twice, "back" once, "please" once. The delivery emails also contain 6: "parcel" twice, "late" twice, "where" once, "delivery" once.
There is an immediate problem. "Parcel" never appears in a refund email, so its count is 0, so P(\text{parcel} \mid \text{refund}) = 0, and multiplying by zero makes the whole refund probability zero, whatever other words appear. One unseen word vetoes everything. The standard fix is Laplace smoothing: add 1 to every word's count, and add the vocabulary size to the total, so no probability is ever exactly zero. It is named after Pierre-Simon Laplace, who used the same "add one" idea in the 1700s to estimate the probability that the sun will rise tomorrow.
Our vocabulary has 8 distinct words, so each probability becomes (\text{count} + 1) / (6 + 8):
| Word | Refund count | P(word ∣ refund) | Delivery count | P(word ∣ delivery) |
|---|---|---|---|---|
| late | 0 | 1/14 | 2 | 3/14 |
| money | 2 | 3/14 | 0 | 1/14 |
| parcel | 0 | 1/14 | 2 | 3/14 |
Both classes have 3 of the 6 emails, so P(\text{refund}) = P(\text{delivery}) = 0.5. Now multiply:
- Refund: 0.5 \times \tfrac{1}{14} \times \tfrac{3}{14} \times \tfrac{1}{14} = 0.5 \times \tfrac{3}{2744}
- Delivery: 0.5 \times \tfrac{3}{14} \times \tfrac{1}{14} \times \tfrac{3}{14} = 0.5 \times \tfrac{9}{2744}
The delivery score is three times the refund score. Turning the two scores into probabilities that add up to 1: delivery gets 9/(9 + 3) = 0.75 and refund gets 0.25. The email goes to the delivery team, which makes sense: two of its three words are delivery words.
In a real system with thousands of words, you would add up logarithms of the probabilities instead of multiplying them, to avoid the underflow problem of 12.2.6. In code:
python
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.naive_bayes import MultinomialNB
emails = ["refund money", "money back", "refund please",
"parcel late", "where parcel", "late delivery"]
team = ["refund", "refund", "refund", "delivery", "delivery", "delivery"]
vec = CountVectorizer() # (1) words → count columns
X = vec.fit_transform(emails)
nb = MultinomialNB(alpha=1.0).fit(X, team) # (2) alpha=1 is Laplace smoothing
new = vec.transform(["late money parcel"])
print(nb.classes_, nb.predict_proba(new).round(2)) # → ['delivery' 'refund'] [[0.75 0.25]]Line (1) builds the vocabulary and turns each email into a row of word counts, one column per distinct word. This "bag of words" representation throws away word order completely and keeps only how often each word appears. Line (2) counts words per class, exactly as the table above, with alpha=1.0 adding the 1 for Laplace smoothing. The printed probabilities match the hand calculation.
Naive Bayes trains in a single pass of counting, so it scales to millions of documents on a laptop, and it is very hard to beat with little data. Spam filtering was its great success: Paul Graham's 2002 essay "A Plan for Spam" popularised it, and for years most email filters ran on it.
3. Support vector machines: the widest street
Picture fraud and genuine orders as two clouds of points that can be separated by a straight line. Usually many different lines would separate them. Logistic regression picks one based on probabilities. A support vector machine, or SVM, picks a specific one: the line that stays as far as possible from the nearest point on either side. Imagine the line as the centre of a street, and widen the street until it touches points on both sides. The SVM chooses the line with the widest possible street.
Why the widest street? Because a line that passes very close to some training points is fragile: a new order just slightly different from those points could land on the wrong side. A wide margin leaves room for new points to vary without being misclassified, which tends to generalise better. This argument, developed by Vladimir Vapnik and colleagues, gave SVMs a strong theoretical footing.
The left panel also shows where the name comes from. Only the few points touching the edges of the street, circled in amber, determine where the line goes. They "support" it, like pillars. You could delete every other training point and the line would not move. Those points are the support vectors.
Real data is rarely perfectly separable, so practical SVMs allow some points inside the street or even on the wrong side, at a cost. A setting usually called C controls the trade: a large C punishes every violation heavily and gives a narrow, strict street that may overfit; a small C tolerates violations and gives a wider, more forgiving one. It plays the same role as the regularisation strength \lambda in 12.3.3, but in the opposite direction.
The kernel trick
What if no straight line can separate the classes at all? The right panel shows the classic case: red points clustered in the centre, blue points in a ring around them. Here is a memorable way to picture the fix. Imagine those marbles lying on a table, and you strike the table hard from underneath. The marbles fly up, and suppose the ones near the edge fly higher than the ones in the middle. For a moment, while they are in the air, you could slide a flat sheet of cardboard between the low red ones and the high blue ones.
Mathematically, that means adding a new computed feature, here z = x^2 + y^2, the squared distance from the centre. Red points have small z and blue points have large z, so in three dimensions a flat cut separates them. In general, mapping data into more dimensions can make it separable, but computing those extra dimensions explicitly can be enormously expensive, sometimes infinitely so.
The kernel trick avoids computing them. An SVM's maths only ever needs the dot products between pairs of points, never the points' coordinates themselves. A kernel is a function that computes what the dot product would be in the higher-dimensional space, directly from the original coordinates. The most popular, the radial basis function or RBF kernel, is K(\mathbf{a}, \mathbf{b}) = e^{-\gamma \|\mathbf{a} - \mathbf{b}\|^2}: close points give a value near 1, far points a value near 0. It corresponds to a space with infinitely many dimensions, yet costs only one distance calculation. You get the separating power of the bigger space for the price of the original one.
SVMs were the leading method for many problems, including handwriting and text classification, through the 2000s. Today they are rarely the first choice: boosted trees usually beat them on tables, deep networks beat them on images and text, and kernel SVMs become slow on very large datasets because they compare points in pairs. But the margin idea lives on. The "push the right answer away from the wrong ones by a safety margin" idea appears in how embedding models are trained in Chapter 12.6.2.
4. Sentiment analysis: the classic text problem
Cartwise collects 50,000 product reviews a month. Product managers want to know which products customers are unhappy with, and support wants angry reviews flagged within an hour. Measuring the emotional tone of text is called sentiment analysis, and it is usually described with two numbers:
- Polarity: how positive or negative the text is, on a scale from −1 (very negative) through 0 (neutral) to +1 (very positive).
- Subjectivity: how much the text expresses opinion rather than fact, from 0 (purely factual) to 1 (purely opinion). "The parcel arrived on Tuesday" is factual. "The parcel arrived disgracefully late" is an opinion.
The two are independent. "This is the worst phone I have ever owned" is very negative and very subjective. "The battery stopped working after two days" is negative but fairly objective, and for a product manager it is often more useful, because it says what actually went wrong.
Approach 1: a dictionary of word scores
The oldest method uses a lexicon: a hand-built list giving each opinion word a polarity and a subjectivity. The Python library TextBlob, for example, ships with such a list. To score a sentence, find the words that appear in the lexicon and average their scores, with a few rules for modifiers.
Take "The delivery was great but the app is slow", with illustrative lexicon values of "great" at polarity +0.8, subjectivity 0.75, and "slow" at polarity −0.3, subjectivity 0.4. Averaging gives polarity (0.8 - 0.3)/2 = 0.25, mildly positive, and subjectivity (0.75 + 0.4)/2 \approx 0.58, fairly opinionated. Modifiers adjust the numbers: "very" multiplies the next word's score up, and "not" flips it, so in TextBlob's rules "not great" becomes -0.5 \times 0.8 = -0.4.
This needs no training data and runs instantly, which is why it is still used for quick dashboards. Its failures are just as fast to find. It misses sarcasm entirely: "Brilliant, another unannounced delay" averages to positive. It misses domain meaning: "unpredictable" is bad in a review of a car's brakes and good in a review of a thriller novel. And it cannot handle comparisons like "marginally better than their last miserable attempt".
Approach 2: learn it from labelled examples
The machine learning approach throws the dictionary away and learns from reviews labelled positive or negative, such as reviews with star ratings. First the text must become numbers. Plain word counts, as in naive Bayes above, give too much weight to words like "the" and "parcel" that appear everywhere and say nothing about sentiment. The standard fix is TF-IDF: term frequency multiplied by inverse document frequency.
- Term frequency is how often a word appears in this review, as a fraction of its words.
- Inverse document frequency is \log(N / df), where N is the number of reviews and df is how many of them contain the word. A word in every review gets \log 1 = 0. A rare word gets a large value.
A small example with three reviews: "late parcel late", "parcel arrived" and "great service". For "late" in the first review, the term frequency is 2/3, and "late" appears in 1 of 3 reviews, so its inverse document frequency is \ln(3/1) \approx 1.10, giving TF-IDF \approx 0.73. For "parcel" in the same review, the term frequency is 1/3, but "parcel" appears in 2 of 3 reviews, so its weight is only \ln(3/2) \approx 0.41, giving TF-IDF \approx 0.14. The distinctive word "late" ends up five times as important as the common word "parcel". (Libraries use slightly smoothed versions of the formula, so their exact numbers differ a little.) The idea was introduced by the British computer scientist Karen Spärck Jones in 1972, and the same thinking underlies BM25, the keyword-ranking formula still used inside search engines today, covered in Chapter 12.6.4.
Feed the TF-IDF vectors into a logistic regression and train it on labelled reviews:
python
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.linear_model import LogisticRegression
from sklearn.pipeline import make_pipeline
sentiment = make_pipeline(
TfidfVectorizer(ngram_range=(1, 2), min_df=2), # (1) words and word pairs
LogisticRegression(max_iter=1000), # (2)
)
# sentiment.fit(review_texts, star_rating >= 4)
# sentiment.predict_proba(["the battery died after two days"])[:, 1]Line (1) turns each review into a TF-IDF vector. ngram_range=(1, 2) includes pairs of adjacent words as well as single words, which lets the model learn that "not good" is different from "good", the very thing the lexicon needed a hand-written rule for. min_df=2 ignores words that appear in only one review, which are mostly typos. Line (2) learns a weight for every word and word pair. Because it learns from Cartwise's own reviews, it picks up Cartwise's own language: it will learn that "returned it" is a strong negative in this domain, without anyone writing that rule.
Approach 3: ask an LLM
An LLM, given a review and the instruction "rate the sentiment from −1 to 1 and say what the complaint is about", handles sarcasm, comparisons and mixed reviews far better than either method above, and it can explain itself. So why not always use it?
Cost and speed. Fifty thousand reviews a month is fine for an LLM. Scoring five years of history, or every customer chat message in real time, may not be. A TF-IDF and logistic regression pipeline scores millions of reviews on a laptop in minutes for essentially nothing. The usual production pattern combines them: the cheap model scores everything, and the LLM handles the cases where the cheap model is unsure or where a detailed explanation is needed. That pattern, sending easy cases to a cheap model and hard cases to an expensive one, is called a cascade, and it returns in Chapter 12.10.10.
Recall
- k-nearest neighbours stores examples and predicts from the k closest. Euclidean distance measures position, cosine measures direction; always standardise features first. It is slow at prediction time and suffers the curse of dimensionality, and its fast approximate form is the basis of vector search.
- Naive Bayes applies Bayes' rule assuming words are independent given the class. Training is counting; Laplace smoothing stops one unseen word from zeroing a class. Worked example: "late money parcel" went to delivery with 0.75.
- A support vector machine picks the line with the widest margin; only the support vectors on the margin's edge decide it. The kernel trick computes dot products in a higher-dimensional space without building it.
- Sentiment analysis measures polarity (−1 to +1) and subjectivity (0 to 1). Lexicons are instant but miss sarcasm and domain meaning; TF-IDF plus logistic regression learns the domain; LLMs handle nuance at higher cost, so a cascade often combines them.
Self-test: Using Euclidean distance, which two customers are Dev's nearest neighbours, and does that change with cosine? In the naive Bayes example, what probability would "refund parcel" get for the refund team? Why does a word that appears in every review get a TF-IDF weight of zero?
Next: 12.3.6 Learning Without Labels — every method so far needed the right answers; next come the methods that find groups, simpler descriptions and unusual cases in data that nobody has labelled.