Classifying documents with linear models

1A weight per word

A speech is a bag of words: a vector x that counts each word of the vocabulary in it, as each chapter was a vector of counts in the vector space model note. A linear model gives each word i a weight w_i and adds up the counts times their weights into a score:

The sum starts at i = 0, with x₀ = 1 in every speech, so that w₀, the bias, is the score of a speech with none of the vocabulary's words. Here a positive score means Sancho and a negative one Don Quixote. A word pushes toward whoever says it, not toward whoever it names: sancho pushes toward Don Quixote, who is the one that calls his squire by name. The weights in the figure were learned from the speeches of four chapters in every five (section 5 shows how), and its six speeches come from the fifth, which the model never saw. All 2,541 words of its vocabulary are kept, stopwords included: the don't and I'll that a search engine would drop are part of Sancho's voice.

The heaviest weights belong to the words with which each addresses the other: worship and master point to Sancho; thou, friend and sancho to Don Quixote. Words the model never met in training, such as cabbages, weigh 0. The last speech is Sancho's, but it addresses no one, and the small weights of its common words lean the other way: what this model reads, above all, is to whom a speech is spoken.

2A line between the two

A speech is a point in a space with a dimension for each word, and the sign of its score splits that space in two: Sancho's side, where s > 0, and Don Quixote's, where s < 0. The boundary between them, where s = 0, is a hyperplane perpendicular to w, and w points toward the positive side. With two words the space is a plane and the boundary a line, which can be drawn.

Take two of the heaviest words: worship, from the your worship with which Sancho addresses his master, and thou, with which his master addresses him. Each speech sits at its counts of the two, and many share a point: 817 of the 1,232 contain neither word and pile up at (0, 0). With only these two words the score is s = w₀ + w₁x₁ + w₂x₂. In the figure, pick the direction of w and the bias, and see where the line falls.

A pile goes whole to one side, so the pile at the origin, two speeches in three, is decided by the bias alone: whatever the line does elsewhere, it gets right either the 427 by Sancho there or the 390 by Don Quixote. No line on these two words gets more than 820 of the 1,232 speeches right, 67%. The model of section 1 does better because it reads every word: of the speeches from its unseen chapters that contain neither of these two, it names the speaker of 161 of 218, 74%.

3From a score to a probability

A score says on which side of the line a speech falls, and how far from it, but not how sure to be. Three classic models compute the same score and differ only in the function θ they apply to it:

The perceptron keeps only the sign, a step from 0 for Don Quixote to 1 for Sancho: it decides, but says nothing of its confidence, and a jump has no slope to learn from. Linear regression keeps the score itself, any real number, which suits a quantity to predict, not a class. Logistic regression squeezes the score between 0 and 1 with the logistic function, smooth enough to learn from its slope, and reads the result as a probability:

the probability that Sancho, y = 1, said the speech x, rather than Don Quixote, y = 0. Don Quixote's needs no second model: θ(−s) = 1 − θ(s), the same score with its sign turned. In the figure, drag the score and follow the three outputs.

Far from 0 the logistic flattens: a score of 4 or of 8 gives nearly the same certainty, near 1, as the step would. Near 0 it rises steeply, and there a small change in the score moves the probability most.

4How wrong a probability is

To learn its weights, the model needs one number that says how wrong its probabilities are on the speeches whose speaker it knows. For one speech, look at the probability p it gave the right speaker: h(x) if Sancho spoke, 1 − h(x) if Don Quixote did. A good model makes p large for all the speeches at once, that is, makes their product large; the logarithm turns that product into a sum, and a minus sign turns it into a loss to make small. Averaged over the N speeches, with natural logarithms, this is the binary cross-entropy:

Since each y_n is 1 or 0, one of the two terms vanishes for every speech, and what is left is −log p. A right answer given with confidence, p near 1, costs almost nothing; a wrong one given with confidence, p near 0, costs without bound. In the figure, drag the probability h that the model gives Sancho, and choose who really spoke.

The two curves are mirror images: Sancho's loss is small where the model leans to him, Don Quixote's where it leans away. That is the asymmetry the loss is built for: hesitating costs a little, and being confidently wrong costs a lot.

5Learning the weights

Learning means finding the w that makes ℒ smallest. The loss depends on w through the probability h, which depends on the score s, which depends on w; by the chain rule, its derivative for one speech is the product of three links,

and the product is simply (h − y)x: the speech's error times the speech. Averaged over the speeches, it gives the gradient, which points to where the loss grows fastest, and gradient descent steps the other way, by a length set by the learning rate η:

A speech that the model gives too much of Sancho pushes the weights of its words toward Don Quixote, and the reverse: the perceptron's rule, with a graded error instead of a yes or a no. The figure runs gradient descent on the plane of section 2, from w = 0, where every speech gets h = 0.5. Choose a learning rate and take steps.

With η = 0.5 the line soon finds its place, but the weights, and with them the probabilities, grow slowly: after thirty steps the loss, 0.569, is still far above its lowest, 0.538. With η = 5 the loss comes within 0.01 of its lowest in seven steps. With η = 16 the steps jump past the minimum, back and forth: the gradient changes sign at nearly every step, the weights swing and grow, and the loss climbs above where it started. The model of section 1 learned its 2,542 weights the same way, every word a dimension of the same descent.

6Three voices: softmax

The book has a third voice, the narrator's, who tells what the two do between their words. With K classes, w becomes a matrix with a row of weights per class, and each line gets a score from each row:

The softmax turns the K scores into probabilities, all positive and adding up to 1, each the larger the further its score stands above the others; with K = 2 it is the logistic function again, applied to the difference of the two scores. Trained on the same chapters, with sentences of the narrator as a third class, the model names the voice of 76% of the lines from chapters it never saw. Pick a line to see its three scores and what the softmax makes of them.

The table counts how the model reads the 445 lines of its unseen chapters:

Of its 107 mistakes, 43 take the knight and the squire for each other and 49 take a speech for the narrator. Those speeches run short, half of them 22 words or fewer against 40 for speeches in general, with few telling words, like the last line of the figure. The narrator's own sentences are misread only 15 times in 99.

7Summary

The note's ideas in NumPy. x holds the speeches' counts, a row per speech with a first column of ones, y their labels, 1 for Sancho and 0 for Don Quixote, and w the weights, the bias first; for three voices, w has a row per class.