Programming or learning

Two flows of information

Programming means building a function that, given the rules and the data, produces the answers:

Learning swaps the roles of data and rules: you start from examples with their answers and search for the rule.

Here “rules” means a model with parameters $\theta$, chosen so that it is wrong as rarely as possible on the examples. A classic definition, by Tom Mitchell (1997): a program learns from experience $E$ with respect to a class of tasks $T$ and a performance measure $P$ if its performance at tasks in $T$, as measured by $P$, improves with experience $E$. In the lesson, $T$ is classifying emails, $E$ is the thirty examples with answers, and $P$ is accuracy on new emails.

The lesson’s model

Each email is summarized by two measures, $x_1$ (links) and $x_2$ (% capital letters). The model computes a score and decides by its sign:

The parameters are $\theta = (w_1, w_2, b)$ and the boundary $w_1 x_1 + w_2 x_2 + b = 0$ is a straight line. To train it, the score is turned into a probability with $p = \sigma(s) = 1/(1+e^{-s})$ and the error is measured with cross-entropy over the $n$ examples, with $y_i = 1$ for spam and $0$ for legitimate:

Each step moves the parameters against the gradient, $\theta \leftarrow \theta - \eta\,\nabla L(\theta)$ (lesson 4). In the scene: $\eta = 0.5$, 300 steps, and the 30 examples, with the measures standardized, $(x_1 - 3.5)/2.5$ and $(x_2 - 14)/8$, and an arbitrary starting point. The result, in the original units, is $w_1 \approx 0.69$, $w_2 \approx 0.53$ and $b \approx -9.63$. Accuracy is hits divided by total: 27 of 30 on the examples and 52 of 60 on the new emails. The data is synthetic, made up for illustration; these are not real emails.

The hand-written rule in the lesson, “spam if $x_1 \ge a$ or $x_2 \ge b$”, is not free either: it also has parameters, the two thresholds. Learning means letting the data set them instead of tuning them by eye.

Why the figure on the examples is misleading

Accuracy measured on the very examples used for tuning is, on average, optimistic. In the lesson, the best of the $10 \times 36 = 360$ rules the sliders allow gets 28 of the 30 examples right ($\approx 93\,\%$); six rules tie, and on the 60 new emails those six get between 47 and 52 right ($\approx 78\,\%$ to $87\,\%$). Among the 84 rules that get 24 or more of the 30 right, 58 drop on the new emails, 16 rise, and 10 stay the same; the average change is $-3.2$ percentage points. That is a tendency, not a law: with only 60 new emails each figure is noisy, and a carefully tuned rule can hold up (“links $\ge 5$ or capitals $\ge 17\,\%$” gets 27 of 30 and 54 of 60). The more options you try on the same data, the more you fit the luck of that data.

Something similar happens with few examples. With 4 examples, the model gets the 4 it saw right and 48 of the 60 new ones ($80\,\%$); with all 30, it gets 27 of 30 ($90\,\%$) and 52 of 60 ($87\,\%$): the two figures move closer. Splitting training, validation, and test data, and measuring well, is the topic of lesson 10.

Samuel and checkers (1959)

The name machine learning is associated with Arthur L. Samuel, who uses it in the title of “Some Studies in Machine Learning Using the Game of Checkers” (IBM Journal of Research and Development, vol. 3, no. 3, July 1959). His program, on an IBM 704, chose moves by looking several moves ahead and scored each board position with a “linear polynomial,” in his words: a weighted sum of board features. In one of his two forms of learning (“generalization”), the program determined the sign and magnitude of the coefficients that multiply those features and chose which terms to use: the same form of model as in this lesson, though with a different purpose (scoring positions, not classifying). In the version he describes there were 38 terms, besides the piece-advantage term, 16 of them active at any one time. The abstract states that a computer can be programmed to learn to play a better game of checkers than the person who wrote the program, in 8 or 10 hours of machine-playing time, given only the rules of the game, a sense of direction, and a redundant and incomplete list of parameters. And the paper itself states the goal: programming computers to learn from experience “should eventually eliminate the need for much of this detailed programming effort.” The oft-repeated phrase “the field of study that gives computers the ability to learn without being explicitly programmed” is frequently attributed to him, but it does not appear in that paper.

A real case: filtering junk mail

In 1998, Sahami, Dumais, Heckerman, and Horvitz studied how to build junk-mail filters automatically. They point out that hand-written rules assume users who can build them and must be tuned constantly as junk mail changes, and they propose learning from the user’s own messages instead. Their probabilistic classifier (naive Bayes) combined the text of the message with problem-specific features, such as the percentage of non-alphanumeric characters in the subject. They also stress that classifying a legitimate email as junk usually costs far more than letting a junk one through; so they only marked a message as junk if its probability exceeded 99.9%.

In code

import math

# (links, % capital letters, is_spam)
data = [(0, 5, 0), (1, 8, 0), (2, 10, 0), (3, 7, 0),
        (4, 20, 1), (6, 25, 1), (7, 15, 1), (9, 30, 1)]

def score(w1, w2, b, links, caps):
    return w1 * links + w2 * caps + b

w1 = w2 = b = 0.0            # parameters: start from zeros
eta = 0.1                    # step size
for _ in range(2000):        # training: many passes over the examples
    g1 = g2 = gb = 0.0
    for links, caps, y in data:
        z = score(w1, w2, b, links / 10, caps / 100)   # measures on a 0-1 scale
        p = 1 / (1 + math.exp(-z))                     # probability of spam
        e = p - y                                      # how wrong it is
        g1 += e * links / 10
        g2 += e * caps / 100
        gb += e
    n = len(data)
    w1 -= eta * g1 / n
    w2 -= eta * g2 / n
    b -= eta * gb / n

print(round(w1, 1), round(w2, 1), round(b, 1))   # weights on the 0-1 scale of the measures
# using it: frozen parameters, just arithmetic
for links, caps in [(1, 6), (8, 12), (5, 30)]:
    s = score(w1, w2, b, links / 10, caps / 100)
    print((links, caps), round(s, 1), 'spam' if s > 0 else 'legit')
# 7.7 2.8 -3.3
# (1, 6) -2.3 legit
# (8, 12) 3.3 spam
# (5, 30) 1.5 spam
# These 8 examples are perfectly separable: with more steps the weights would keep growing;
# 2000 are enough to classify them correctly.

What comes next

In lesson 2 we will see how any data (an image, a sound, a text) is turned into numbers so it can be used as $x_1, x_2, \dots$; in lesson 3, how a model’s error is measured; and in lesson 4, how the parameters are adjusted step by step (the gradient descent we only saw at work here). This lesson’s model, a weighted sum that decides by its sign, is in essence an artificial neuron (lesson 5).