Machine Learning: Trends, Perspectives, and Prospects

A rule you write by hand stays frozen. A rule learned from examples gets better as the examples grow. Move the slider and watch both try to catch the same fraud.

Drag Examples shown to the learner from 0 to 200, then switch between the hand-written rule and the learned one. Then we build, piece by piece, what Jordan and Mitchell say machine learning is: a search for a program, guided by experience, inside an environment that sets limits.

You need a feel for a scatter plot and the idea of a percentage. We build the rest from zero.

Based on M. I. Jordan and T. M. Mitchell, “Machine learning: Trends, perspectives, and prospects”, Science 349 (6245), 255 to 260, 17 July 2015. A reading for the MIT MMAI course, taught by Paul Liang. It belongs with Lecture 2, Datasets and Research. Every idea is re-taught here in our own words and devices.

Write the rule, or learn it

20

Toy data, made up for this page (the paper has no such experiment): each transaction has two numbers between 0 and 1, an amount and a distance from home. About 35% are fraud. Both rules are scored on the same 400 fresh transactions. The learner is logistic regression (Chapter 2), trained on the first n examples of a pool of 200; with 0 examples it can only guess the common label. Each press of the button draws a new pool, so scores vary a little from draw to draw.

Chapter 0

Machines That Improve With Experience

See why a short review from 2015 still frames how the field thinks about learning, data and responsibility

It is two in the morning at a bank. An analyst reads a list of rules that flag stolen credit cards. One rule says: block any purchase over a set amount in a country the customer has never visited. Last week thieves learned the rule, so they now buy many small things instead. The analyst adds a new rule. Next week the thieves change again.

The analyst is writing a program by hand: a list of steps that a person thought of in advance. The trouble is that a person must foresee every case. The thieves only need to find the one case nobody foresaw.

There is another way. Give the computer thousands of past purchases, each marked “fraud” or “not fraud” after the fact. Let the computer find a rule that fits them. When the thieves change, add the new examples and let the computer fit again. This second way is machine learning: building computer systems that improve automatically through experience, meaning the examples they are shown. The hero at the top of this page is exactly this contrast. Go back and drag the slider if you have not yet.

What this paper is

Michael I. Jordan (University of California, Berkeley) and Tom M. Mitchell (Carnegie Mellon University) wrote this paper for the journal Science, in the issue of 17 July 2015. It is a review: it does not announce one new method. It surveys a field, says what drives it, and points at what is unsolved. That makes it a map, and a map is useful when you are new.

The paper opens with two questions. First: how can we build computer systems that automatically improve through experience? Second: what are the fundamental laws, from statistics, computing and information theory, that govern all learning systems, whether they are computers, humans or organizations? The first question is engineering. The second is science. The rest of the paper moves between them.

The authors give three reasons why progress has been fast. New learning algorithms and theory were developed. Data became available online in huge amounts. And computing became cheap. They also note a change of mind among builders of artificial intelligence: for many tasks, it is far easier to train a system by showing it examples of desired inputs and outputs than to program it by anticipating the right response to every possible input. That is the bank analyst’s lesson, stated for a whole field.

Where it is used

The paper names a wide spread of uses. The abstract lists health care, manufacturing, education, financial modeling, policing and marketing. Figure 1 shows four areas as pictures: robotics and autonomous vehicle control, speech and language processing, neuroscience research, and computer vision. Press a chip below to see what the paper says about each area. The map also shows how few of these areas are about one industry. They are about one method applied to different data.

Browse the paper’s applications

The hub is “learning from experience”. Blue spokes are the four areas drawn in Figure 1. Warm spokes are areas the abstract or the text names. Press a chip to light one spoke.

Everything on this device is taken from the paper’s abstract, its Figure 1 caption and its text. The four blue areas are the four panel groups of Figure 1; the six warm areas are the ones the abstract lists (health care, manufacturing, education, financial modeling, policing, marketing). The positions on the wheel mean nothing.

Look at what the examples share. Health care has records of past patients. Policing has records of past crimes. Vision has labelled images. Each has a large pile of experience, and a question about what to do next. The paper calls the whole trend a movement toward data-intensive, evidence-based decision-making. It says we appear to be at the beginning of a decades-long trend.

How the paper is organized

The paper has a short opening that defines the learning problem, then four headed parts. “Drivers of machine-learning progress” explains why the field grew: big data, and the need for scalable, personal and privacy-aware methods. “Core methods and recent progress” covers the three learning paradigms: supervised, unsupervised and reinforcement learning. “Emerging trends” covers the environment a learner works in: computers, privacy and communication. “Opportunities and challenges” looks at what nature does better and at questions of data ownership. This lesson follows that order, with one extra step: it explains in plain words how a learner is found, in Chapter 2.

  1. A learning problem has three parts: the task, the performance measure and the experience.
  2. Learning is a search for a program: a function with knobs, and an optimizer that turns them.
  3. How much data, how much computing: sample complexity and computational complexity.
  4. Supervised learning and deep networks: labelled pairs, and a network that writes captions.
  5. Finding structure without labels: clustering, dimension reduction and topic models.
  6. Learning from rewards, and the blends: reinforcement learning, semi-supervised and active learning.
  7. The environment sets the rules: privacy, communication and computing as resources.
  8. Learning like nature, and who owns the data: never-ending learners and an ethical trade-off.
  9. Field guide: numbers, terms, a checklist and the core code.
Why did the bank analyst’s hand-written rules keep failing, and what does machine learning change?

Chapter 1

A Learning Problem Has Three Parts

Name the task, the performance measure and the experience, and see how changing one of them changes the answer

A friend asks you to build a program that spots credit-card fraud. Before you write any code, you must answer three plain questions. What exactly should the program do for each purchase? How will we decide whether it does that job well? And what examples do we have to learn from? Jordan and Mitchell say every learning problem is defined by exactly these three answers.

The paper states it in one sentence. A learning problem is the problem of improving some measure of performance when executing some task, through some type of training experience. Think of a student. The task is the exam question. The performance measure is the grade. The experience is the practice problems. Change any one, and you have a different student’s problem.

The paper’s own example, taken apart

The paper uses fraud detection. The task is to give each credit-card transaction a label, “fraud” or “not fraud”. The performance measure is the accuracy of that labelling. The experience is a collection of old transactions, each labelled in hindsight as fraudulent or not.

Then the authors change the pieces one at a time. This is the useful part. They suggest a different performance measure that charges a higher penalty when “fraud” is labelled “not fraud” than when “not fraud” is wrongly labelled “fraud”. They also suggest a different kind of experience: add unlabeled transactions to the labelled ones. Same task, yet two new problems.

Why accuracy alone can fool you

Here is the failure first, as a symptom. A team ships a fraud detector and reports 99% accuracy. A week later the bank discovers that almost no fraud was caught. The team is not lying. The numbers are real.

Now the measurement. Say there are 1,000 transactions and only 10 are fraud. A program that always answers “not fraud” is right on 990 of them. That is 99% accuracy, and it catches 0 of the 10 frauds. Accuracy counted every mistake as equal, and the rare mistakes were drowned by the common ones.

The fix is the paper’s second idea: change the performance measure so it matches what the mistakes really cost. Let a missed fraud cost cmiss and a false alarm cost calarm. Then total cost counts each kind of mistake with its own price.

Cost
The number we want small. It replaces “accuracy” as the performance measure.
cmiss
The price of one missed fraud, a fraud labelled “not fraud”. We set it to 10 in the device below.
Nmiss
How many frauds the program missed.
calarm
The price of one false alarm, a good purchase labelled “fraud”. We set it to 1.
Nalarm
How many good purchases the program flagged.

“Always not fraud” on 1,000 purchases: 10 × 10 + 0 × 1 = 100. Flagging every purchase: 0 × 10 + 990 × 1 = 990.

Under this measure the lazy program no longer looks good. Its cost is 100, and a program that finds half the frauds and raises 20 false alarms costs 5 × 10 + 20 = 70. The measure now says what the business cares about.

A dial you can turn

Most learners do not output a bare label. They output a score, a number between 0 and 1 where higher means more suspicious. You then pick a threshold: flag every purchase whose score is above it. The threshold is a dial. Turn it down and you catch more fraud but raise more false alarms. Turn it up and the reverse happens.

Below, 200 purchases have been scored: 50 fraud and 150 good. Move the threshold under each performance measure. Notice that the best setting moves when the measure changes.

Turn the threshold

Bars show how many scores fall in each slice: blue for good purchases, purple for fraud. Fraud left of the line is missed. Good purchases right of the line are false alarms. The curve underneath shows the total for every possible threshold.

0.50

Illustrative, not from the paper: 200 made-up scores from a seeded random draw, 50 fraud (centred near 0.66) and 150 good (centred near 0.36), both with a spread of 0.15. The costs 10 and 1 are our choice for the example. The paper only says the penalty for a missed fraud could be higher.

With the plain error count, the best threshold sits where the two piles of bars cross. With a miss costing 10, the best threshold slides left. The program accepts more false alarms because each miss hurts ten times more. Nothing about the data changed. Only the performance measure changed, and so did the best answer.

Where the threshold comes from

There is a tidy rule behind this. Suppose the score is a true probability p that a purchase is fraud. Flagging it costs calarm with probability 1 − p, since it is then a false alarm. Not flagging it costs cmiss with probability p. Flag when the first is smaller, which means p × 10 > (1 − p) × 1. Solve it: p > 1/11, which is about 0.09. A purchase only has to look 9% likely to be fraud before the cost-aware detector flags it. This rule is standard decision theory, not a claim of the paper, but it is the reason the paper’s sentence about unequal penalties matters.

The third part: experience

The same thinking applies to experience. Labelled transactions are expensive, because someone must find out in hindsight which were fraud. Unlabeled ones are plentiful. A problem that may use both is a different problem from one that uses only the labelled set, and later chapters show methods built for it. For now, remember the habit: before you pick an algorithm, write down the task, the measure and the experience.

Only 1% of purchases are fraud. A program that always says “not fraud” scores 99% accuracy. What does the paper’s framing tell you to change?

Chapter 2

Learning Is a Search for a Program

Treat a learner as a function with tunable knobs, and follow an optimizer as it turns the knobs downhill

Picture an old mixing board in a music studio, with a row of knobs. Nobody knows the right setting for the song. So the engineer plays the song, listens, nudges one knob, and listens again. Each nudge is small. Over time the sound gets better. A learning algorithm does the same thing, with thousands or billions of knobs and a score instead of an ear.

The paper puts it in one careful sentence. Machine-learning algorithms can be viewed as searching through a large space of candidate programs, guided by training experience, to find a program that optimizes the performance metric. Two choices define any algorithm. The first is the representation: what kind of program is allowed. The paper lists decision trees, mathematical functions and general programming languages. The second is the search: how we move through the space of allowed programs. The paper lists optimization with well-understood convergence guarantees, and evolutionary search, which tests generations of randomly changed programs.

Function approximation, with knobs

Most of the paper’s methods are function approximation problems. The task is a function, such as “given a transaction, output fraud or not fraud”. The experience is a sample of known input and output pairs of that function. The learner must find a function that matches them and also works on inputs it has not seen.

The function is usually written with parameters: the knobs. The paper says training corresponds to finding values for these parameters that optimize the performance metric. The simplest example is a straight line, f(x) = w0 + w1x. It has two knobs. Knob w1 tilts the line. Knob w0 lifts it. The hero’s learner has three knobs, a lift and two tilts, one for each of the two numbers that describe a transaction.

Scoring the knobs: a loss

To search, we need a score for every setting of the knobs. For a line we use the average squared miss. For each example, take the line’s prediction, subtract the true answer, and square the result. Then average. We call this the loss. Smaller is better. A perfect fit has loss 0.

L(w0, w1)
The loss for one setting of the two knobs. It is one number.
1/n
Divide by the number of examples, so the loss does not grow just because we have more data.
∑i=1n
Add up one term for each example, from the first to the n-th. The paper stresses that the objective is often a sum over a large number of terms.
w0 + w1xi
The line’s prediction for example i.
yi
The true answer for example i.

Walking downhill

Imagine the loss as the height of a landscape, where each spot is one setting of the knobs. We want the lowest point. We cannot see the whole landscape, but at our feet we can feel the slope. The slope is the gradient: for each knob, how much the loss changes if we turn that knob a little. Gradient descent takes a small step against the slope, then feels the slope again.

For our loss the slopes have a clean form. Let ei = w0 + w1xi − yi be the miss on example i. Then the slope for w0 is the average of 2ei. The slope for w1 is the average of 2eixi. The update turns each knob against its slope:

w (left)
The new value of a knob.
w (right)
The old value of the same knob.
η
The learning rate: how big a step to take. We choose it.
∂L/∂w
The slope of the loss along this knob. Minus the slope points downhill.

Here is one full step by hand. Take three examples: (1, 2), (2, 3) and (3, 5). Start with both knobs at 0. Every prediction is 0, so the misses are −2, −3 and −5. The loss is (4 + 9 + 25)/3 = 12.67. The slope for w0 is 2 × (−10/3) = −6.67. The slope for w1 is 2 × (−2 − 6 − 15)/3 = −15.33. With η = 0.1, the new knobs are w0 = 0.667 and w1 = 1.533. The new predictions are 2.2, 3.73 and 5.27. The misses are now 0.2, 0.73 and 0.27, and the loss is 0.216. One step cut the loss by a factor of nearly 60.

12.67 → (w0, w1) = (0.667, 1.533) → 0.216

Try it, and break it

The device below holds 12 points and the loss landscape of a line fitted to them. The warm shading is the loss: dark is low, bright is high. Press Step to walk. Then raise the learning rate and look for the failure.

Walk the loss landscape

Left: the landscape of the two knobs, with your path in teal. Right: the data and the line the knobs currently make. Press Step or Run 30 steps, then change the learning rate and the step style.

0.08

Illustrative: 12 points from a seeded random draw around the line y = 0.5 + 1.4x, with noise of 0.35. The loss is the average squared miss from the equation above, computed exactly. The path starts at both knobs set to the same wrong place on every reset.

With a small rate the path creeps down the valley and settles. With the rate near 0.3 and above, each step overshoots the valley floor by more than it gained, so the loss grows and the path flies off the map. That is the failure: the symptom is a loss that goes up instead of down. The measurement is the loss printed after each step. The fix is a smaller learning rate. The device stops and says so when the loss passes 1,000.

The one-example mode matters for a reason the paper names. Real objectives are sums over huge numbers of terms, so computing the exact slope over everything is costly. Using a small sample of terms per step gives a noisy slope that is far cheaper. The path wobbles, but on average it still walks downhill. The paper says the form of machine-learning problems, a large sum of terms, has driven innovations in optimization.

Finally, remember the second search the paper mentions. Evolutionary search does not follow a slope. It tries many random changes and keeps the better programs. It suits representations where no slope exists, such as a general programming language.

During gradient descent the loss rises after every step and keeps growing. What is the most likely cause, and the standard fix?

Chapter 3

How Much Data, How Much Computing

Measure how error falls as examples grow, and learn why the paper asks for data and computation budgets together

You are preparing for an exam. Two questions decide how you study. How many practice problems must you do before you can answer new ones? And how many hours do you have to think them through? Too few problems, and you only memorize. Too few hours, and you never finish. A learning system faces the same two limits, and the paper says a science of learning must study both.

The authors write that a key scientific and practical goal is to characterize, in theory, what a learning algorithm can do and how hard a learning problem is. They ask four questions. How accurately can the algorithm learn from a particular type and volume of training data? How robust is it to errors in its assumptions or in the data? Given a problem and a volume of data, can a successful algorithm be designed at all, or is the problem fundamentally intractable? And how do the answers depend on features such as the representation the algorithm uses?

Two kinds of cost

The paper names two measures. Sample complexity is how much data are required to learn accurately. Computational complexity is how much computation is required. The paper says attempts to characterize learning have led to blends of statistical and computational theory, in which both are characterized together.

The tools come from two older fields: statistical decision theory, which asks how to decide well under uncertainty, and computational complexity theory, which asks how much time and memory a task needs. A well-known blend is the PAC framework, short for “probably approximately correct”. It asks how error rate, training-set size and other parameters relate when the learner must also finish in a polynomial amount of time. Polynomial time means the running time grows as a power of the input size, such as the square, rather than exploding as an exponential.

Train error and test error

To see the first cost, we must separate two scores. The training error is how often the learned rule is wrong on the examples it studied. The test error is how often it is wrong on fresh examples from the same source. Only the second matters in use, because the bank cares about tomorrow’s purchases, not yesterday’s.

Here is the failure, as symptom, measurement and fix. The symptom: a model that looks perfect in the lab fails in the field. The measurement: compare training error to test error. With only a handful of examples, a flexible learner can fit them all, so training error is near 0, while test error is far higher. The gap between the two is the sign of overfitting, fitting the accidents of a small sample instead of the pattern. The fixes are more data, a simpler rule, or both.

As examples grow, the two errors move toward each other, and test error falls toward a floor. The floor exists because some inputs are truly ambiguous: a good purchase and a fraud can look the same. If the two groups overlap, no rule can be perfect. For two equal groups whose centres are a distance d apart, each spread out by s in every direction, the best possible error has a closed form:

floor
The lowest error any rule can reach on this data, however much data it sees.
Φ
The chance that a standard bell-curve variable falls below a given value.
d
The distance between the two group centres. We use 0.424.
s
The spread of each group. A larger spread means more overlap.

s = 0.15: Φ(−0.424 / 0.30) = Φ(−1.41) = 7.9%. s = 0.25: Φ(−0.85) = 19.8%.

So a spread of 0.15 means 7.9% of purchases are ambiguous even to a perfect rule. This is a standard result for two bell-shaped groups, not a formula from the paper. It shows the shape of the paper’s question: how close to the floor can we get, with how much data?

Data and time are traded against each other

The paper goes further. It says the core of the problem involves time-data trade-offs that are far from the polynomial and exponential boundary. Large data sets need algorithms whose time and space grow linearly or less than linearly with the problem size. Researchers use subsampling (learn from a random part of the data), random projections (squeeze each example into fewer numbers with a random matrix) and algorithm weakening (use a cheaper, less exact method on purpose), while keeping statistical control. The ultimate goal, the authors write, is to give the system time and space budgets as well as accuracy requirements, and let the system find an operating point that meets all of them.

The device lets you feel two budgets at once. The data budget is the number of examples. The time budget is how many gradient steps (Chapter 2) the learner may take. The curves are measured, not drawn by hand: each point averages 12 fresh training sets.

Spend data, spend time

The warm curve is error on fresh data. The blue curve is error on the examples themselves. The dashed line is the floor from the equation. Set the group spread and the time budget, then slide the number of examples.

0.15
20

Our own measurement, not the paper’s. Two equal groups with centres at (0.35, 0.35) and (0.65, 0.65); logistic regression trained by gradient descent with learning rate 5; each point averages 12 random training sets of the given size and is scored on 500 fresh points. Example counts: 5, 10, 20, 40, 80, 160, 320.

Set the spread to 0.15, give the learner 600 steps, and slide the examples down to 5. Error on the examples is 5.0% but error on new data is 12.4%: a gap, the sign of overfitting. Slide to 320 and the two meet near the floor, at 7.4% and 7.7%. Now cut the time budget to 3 steps. With 320 examples the error on new data ends at 11.0%, not 7.7%, and the curve bumps up and down on the way. A learner with no time cannot use the data it has. Both budgets matter, and a good system chooses a point on both axes.

A model scores 100% on its training examples and 70% on new ones. What is this, and what is a sound response?

Chapter 4

Supervised Learning and Deep Networks

Follow one picture through a deep network that writes a caption, one word and one glance at a time

You upload a photo of a bird over a lake. Your phone writes a caption: “A bird flying over a body of water.” Nobody wrote a rule for birds or for lakes. The system learned to caption from a huge pile of photos that people had already captioned. This is supervised learning, the most widely used kind of machine learning, and the paper’s first topic in “Core methods and recent progress”.

The setup: pairs of an input and an answer

In supervised learning the training data are pairs (x, y). The input x is the thing you know. The output y is the answer a teacher supplied. After training, you give the system a new query x* and it produces a prediction y*. The star marks “new, never seen”. Spam filters, face recognizers and medical diagnosis systems all fit this shape.

The paper stresses how varied the two sides can be. The input may be a plain list of numbers, but it may also be a document, an image, a DNA sequence or a graph. The output has many forms too. In binary classification it has two values, such as “spam” or “not spam”. In multiclass classification it is one of K labels. In multilabel classification several of the K labels can be true at once. In ranking the output is a partial order on a set of items. In structured prediction the output is a combinatorial object, and its parts must satisfy constraints. The paper’s example is part-of-speech tagging: label every word of a sentence at once as a noun, a verb or another part of speech. Outputs can also be real numbers.

A supervised learner usually forms its prediction through a learned mapping f(x) that returns an output, or a probability distribution over outputs. The paper lists many forms for f: decision trees, decision forests, logistic regression, support vector machines, neural networks, kernel machines and Bayesian classifiers. It notes that generic procedures such as boosting combine the outputs of several learners. It also says this variety is not an accident. Different forms capture different structure, differ in how easily they can be visualized and explained after the fact, and trade off computing, data and performance.

Deep networks

The paper calls out one high-impact area: deep networks. These are multilayer networks of threshold units. Each unit computes a simple function of its inputs, with a few tunable numbers. Gradient-based optimization, the walk downhill from Chapter 2, adjusts the numbers throughout all the layers, using the errors seen at the output. Graphics processing units, built first for video games, made it possible to build systems with billions of parameters and to train them on the huge piles of images, videos and speech on the internet. The authors say these systems brought major gains over earlier approaches in computer vision and speech recognition, and they were being pursued for translation and collaborative filtering.

The paper adds an idea that matters for later chapters. The internal layers of a deep network can be viewed as providing learned representations of the input. A representation is a rewriting of the raw input into numbers that make the task easier. Nobody designs it by hand. Training discovers it.

Figure 2: a network that writes captions

Figure 2 of the paper shows a captioning system built from two networks. A convolutional neural network reads the image. It is a network whose early layers slide small detectors across the picture. Its output is a 14 × 14 map of features, so 14 × 14 = 196 locations. A recurrent neural network, here the LSTM variety, then writes the caption word by word. At each word it looks at the map again, and the bottom row of Figure 2 shows where it looked for each word. Under the diagram, the figure shows one glowing map for each word of the caption, laid over the photo of a bird.

The paper only draws this. The details come from the work it cites for the figure (Xu and others, 2015), so treat the next paragraph as background from that work, not from the review. Let ai be the feature vector at location i, one of the 196. Before word t, the writer has a state ht−1, a memory of the words so far. It gives every location a score eti. A softmax turns the 196 scores into 196 positive weights that add to 1, written αti. The writer then mixes the features using those weights.

αti
How much attention word t pays to location i. All 196 values for one word add up to 1.
exp(eti) / ∑j exp(etj)
The softmax: raise e to each score, then divide by the total, so large scores win most of the weight.
zt
The context for word t: one vector that summarizes what the writer is looking at.
∑i αti ai
A weighted average of the 196 feature vectors.

Four locations with features (1,0), (0,1), (1,1), (0,0) and weights (0.1, 0.7, 0.1, 0.1): z = 0.1(1,0) + 0.7(0,1) + 0.1(1,1) + 0.1(0,0) = (0.2, 0.8).

With weights concentrated on the second location, the context is nearly that location’s feature vector. The data flow per word is: 196 weights, then one context vector, which the LSTM combines with its state to produce a probability for every word in the vocabulary. The chosen word becomes the next input, and the loop repeats until the full stop.

Watch it write

Step through the caption below. The brightness of each cell shows the attention weight for the current word. The bars add up the attention on the bird cells, the water cells and everywhere else.

Write the caption, one glance at a time

The grid is the 14 by 14 feature map laid over a toy scene: sky on top, a bird in the upper left, water below. Press Next word and watch the teal glow move.

Illustrative: the attention weights are drawn by us, one bell-shaped glow per word, to show the pattern of Figure 2. They are not read from a real trained network. The caption words are the figure’s. The grid size, 14 by 14, is the figure’s too.

In our toy version, “bird” and “flying” pull attention to the bird, “body” and “water” pull it to the lake, and small words like “a” and “of” spread it thin. This picture is also a debugging tool. If the system writes “dog” for a bird, the failure shows as attention on the wrong cells for that word. The fix is usually better or more labelled pairs, which is why the paper keeps returning to data. Its remark that models differ in how easily they can be explained afterward is exactly this: some forms give you a picture like this one, and others do not.

In the captioning network, what does the attention step produce for each new word?

Chapter 5

Finding Structure Without Labels

Group unlabeled points into clusters, and see how clustering, dimension reduction and topic models share one idea

You inherit a library of ten thousand news articles. Nobody has labelled them. There is no list of subjects, no teacher, no right answer to copy. Yet you can still tidy the library: put articles that look alike in the same pile, and notice that some piles are about sport and others about cooking. You found structure without being told what to look for.

The paper calls this unsupervised learning, the second major paradigm. The data come without labels. The learner analyzes them under assumptions about their structure: algebraic, combinatorial or probabilistic. The paper adds that the interest is practical: unlabeled data come in huge amounts, and the goal is to exploit them when you give up on labels.

Idea one: the data live on something small

A photo has millions of numbers, but photos of faces do not use all the ways those numbers could vary. The paper’s example is the assumption that data lie on a low-dimensional manifold: a thin, possibly curved sheet inside the big space of all possible numbers. Think of a long thread curled up in a room. The room is 3-dimensional, but you can locate any point on the thread with one number, the distance along it.

Dimension reduction methods find that thread. The paper lists principal components analysis, manifold learning, factor analysis, random projections and autoencoders. Each makes a different assumption: that the data lie on a linear subspace (a flat sheet), a smooth curved manifold, or a collection of several smaller manifolds. Principal components analysis, for example, finds the straight line along which the data vary most, and writes each point as one number on that line. Choose the assumption that fits, and a few numbers carry most of the information.

Idea two: documents are mixtures of topics

Figure 3 of the paper shows topic modeling, which the authors present as another form of dimension reduction. A document is viewed as a bag of words. The words are viewed as generated by a small set of hidden topics. A topic is a probability distribution over words: some words are likely, others are not. Each document is described by a distribution over topics, the proportions it uses of each. Nobody labels the topics. They are inferred from a whole collection of documents, and then used to classify, index and summarize the content.

Topic (our label)Likely words and their probabilities in Figure 3What it shows
Geneticsgene 0.04, dna 0.02, genetic 0.01One topic is a list of words with probabilities
Life and evolutionlife 0.02, evolve 0.01, organism 0.01A document can mix several topics
Computingdata 0.02, number 0.02, computer 0.01Topics are found, not given

The labels in the first column are ours; the figure marks topics by colour. The idea is that one article about genome sequencing might be 40% one topic, 30% another and 30% a third. Ten thousand articles shrink to a short list of topic proportions each.

How are these found? The paper describes a common recipe for these methods. State your assumptions. Write a criterion function, a score for how well a candidate structure fits the data, using a general principle such as maximum likelihood (pick the structure that makes the data most probable), the method of moments or Bayesian integration. Then use an optimization or sampling algorithm, as in Chapter 2, to optimize the criterion.

Idea three: clustering

Clustering asks for a partition of the observed data, plus a rule for placing future data. The paper notes that many clustering methods exist, each resting on a specific assumption about what a cluster is. Here is the best-known one, k-means. Its assumption is that a cluster is a round blob around a centre. The score is the total squared distance from each point to its own cluster centre; smaller is tighter.

J
The score to make small: the total squared distance to the centres.
∑i
Add up one term for every data point.
‖ xi − μc(i) ‖2
The squared straight-line distance from point xi to μc(i), the centre of the cluster that point i belongs to.

The method alternates two moves. Assign: send each point to its nearest centre. Update: move each centre to the average of its points. Repeat until nothing changes. A tiny worked case: six points on a line at 1, 2, 3, 10, 11 and 12, with two centres starting at 1 and 2. First assign: point 1 goes to centre A; 2, 3, 10, 11 and 12 go to centre B. Update: A = 1, B = (2 + 3 + 10 + 11 + 12)/5 = 7.6. Assign again: now 1, 2 and 3 are nearer A, and 10, 11, 12 are nearer B. Update: A = 2, B = 11. Assign again: nothing moves. The score is (1 + 0 + 1) + (1 + 0 + 1) = 4.

Each move can only lower the score or leave it unchanged, so the loop must stop. But it may stop at a poor answer, because it depends on the starting centres. That is the first failure. The second: you must choose k yourself, and a wrong k cuts one blob in two or glues two blobs into one. The measurement is the score for each k. It always falls as k grows, but it falls sharply until the right k and then only slowly. The fix is to look for that bend, and to restart from several starting positions.

Find the piles

90 unlabeled points sit in three loose groups. Choose how many clusters to look for, then press Step to assign and update. Circles are the centres. Bars show the best score for each k.

3

Illustrative toy data from a seeded random draw: three groups of 30 points with a spread of 0.08. The score J is computed exactly. The bar for each k is the best of 8 random starts, so it does not depend on the starting centres you see.

Set k to 3 and run it: the three piles are found. Set k to 2 and a real pile is glued to its neighbour. Set k to 6 and a real pile is cut. Look at the bars: the big drops stop at k = 3. The paper adds a warning that applies here: with unlabeled data the concern with computational cost is paramount, since the point is to exploit the very large data sets available when you give up on labels.

You run k-means with k = 2 on data that really has three groups. What do you see, and how can you detect it?

Chapter 6

Learning From Rewards, and the Blends

Learn from a thumbs up or down alone, then see how real systems blend the three paradigms

You are in a casino with three slot machines. Each one pays out at a different, hidden rate. Nobody tells you which is best. Nobody labels a pull as “correct”. You only see whether you won. Which machine do you play, and how often do you test the others? This small puzzle holds the core of the paper’s third paradigm.

Reinforcement learning: only a thumbs up or a thumbs down

In reinforcement learning the training data sit between the supervised and the unsupervised kinds. The paper says that, instead of examples showing the correct output for an input, the data only indicate whether an action was correct or not. If the action was wrong, the problem of finding the correct action remains. The signal is called a reward.

The problem gets harder when actions come in sequences, as in a game or a robot’s walk. The paper says the reward signals then refer to the entire sequence. Nobody says which single action deserved the credit or the blame. This is the credit assignment problem. You win the chess game after sixty moves. Which move won it?

The paper defines the general setting as a control problem. An agent acts in an unknown dynamical environment. The learner must find a policy, a rule that picks an action for any state (a description of the situation right now). The goal is to maximize the expected reward over time.

π*
The best policy: the rule that maps each state to an action and earns the most.
E
The expected value: the average over all the luck the environment may deal.
∑t=0T
Add up the rewards from the first time step to the last, T steps later.
rt
The reward received at time step t.

The paper ties this to older fields. Reinforcement learning uses ideas familiar from control theory, such as policy iteration, value iteration, rollouts and variance reduction. Markov decision processes and their partially observed cousins give points of contact. It adds innovations for machine learning’s needs: large problems, few assumptions about the environment, and supervised-learning architectures to represent policies. It also notes the ties to psychology and neuroscience. Reinforcement learning algorithms were used to predict the responses of dopamine neurons in monkeys learning to link a light to a later sugar reward.

The simple case: bandits

The paper mentions simplified versions called bandit problems, where the reward arrives after each action. Our casino is a bandit problem, a “multi-armed bandit”. The learner keeps an estimate of each machine’s payout rate, Q, which is the average of the rewards it has seen from that machine. After each new reward r from a machine pulled n times so far, the average updates in one line.

Q (left)
The new estimate of this machine’s payout rate.
Q (right)
The old estimate.
n
How many times we have now pulled this machine, counting this pull.
r
The reward just seen: 1 for a win, 0 for a loss.
r − Q
The surprise: how far the new reward is from what we expected.

Estimate 0.50 after 4 pulls (2 wins), then a win on pull 5: 0.50 + (1/5)(1 − 0.50) = 0.60.

Now the dilemma. If you always play the machine with the best estimate, you exploit what you know. If you sometimes try another machine, you explore. The simplest rule, called epsilon-greedy, plays the best-looking machine most of the time and picks a random one with a small probability ε. The failure with ε = 0 is easy to see. The symptom: the learner sticks with a mediocre machine forever. The measurement: compare the reward earned with the reward of the best machine. The fix: keep exploring. The opposite failure, ε near 1, wastes pulls on machines already known to be bad.

Explore or exploit

Three machines pay at hidden rates of 30%, 50% and 65%. Set how often the learner tries a random machine, then press Pull 200 times. Bars show its estimates against the hidden truth.

0.10

Illustrative toy, not from the paper. Win rates 0.30, 0.50 and 0.65 are our choice; estimates start at 0, and ties are broken at random. The line shows one run. The “on average” figure is the mean of 200 seeded whole runs of 200 pulls at your ε.

Try ε = 0 a few times with New luck. Sometimes the learner finds the 65% machine and sometimes it locks on to a worse one, whichever machine happens to pay first. Try ε = 0.1: in our 200 seeded runs it played the 65% machine most of the time in 159 of them, and it wins about 118 of the best possible 130. Try ε = 1: it plays at random and wins about 48% of the time, the mean of the three rates.

The blends

The paper is careful to say that the three paradigms help organize ideas, but much current research blends them. It names several blends. Each is a way to give a learner a different kind of experience.

BlendWhat gets mixedThe paper’s words
Semi-supervised learningA few labelled examples and many unlabeled onesUses unlabeled data to augment labelled data
Discriminative trainingUnsupervised architectures and label-based objectivesBlends architectures from unsupervised learning with label optimization
Model selectionFitting a model and choosing among modelsUses training data to select from a family of models; leads to bandits and Bayesian optimization
Active learningThe learner chooses its own examplesThe learner queries the trainer, such as for the label of an unlabelled example
Causal modelingPrediction and causeGoes beyond predictive relations to which variables influence others

Causal modeling deserves a worked example, which the paper supplies. A high white-blood-cell count predicts an infection. But the infection causes the high count, not the other way around. A system that only predicts would be happy to say “lower the count and the patient is healed”. A causal model knows that lowering the count does not touch the infection. The paper lists more design issues that cut across paradigms: whether data arrive in batches or over time, how the data were sampled, whether users need to interpret the model, and robustness when data do not fit prior assumptions.

A slot-machine learner never explores (ε = 0) and settles on a 30% machine while a 65% machine is available. What does the paper’s description of reinforcement learning explain about this?

Chapter 7

The Environment Sets the Rules

Treat privacy, communication and computing as resources, and watch noise buy privacy at a price in accuracy

A hospital group wants to learn which treatments work from its patient records. The records sit in four buildings in four cities, and moving them all to one place is slow and legally risky. The patients also did not agree to have their lives read by strangers. So the learner faces limits that have nothing to do with its algorithm: where the data are, who owns them, and how much of them may be seen.

The paper’s section on “Emerging trends” makes this the central point. It says one major trend is a growing concern with the environment in which a learning algorithm operates. The word has three meanings in the paper.

Three meanings of environment

First, the computing architecture. A classical learner was one program on one machine. Today it is common to deploy learners across thousands or tens of thousands of processors. Then communication and parallelism take center stage. Figure 5 of the paper shows a data-analytics stack: layers of storage, resource management, a processing engine, and access tools, with learning methods such as streaming, subsampling, pipelines and graph processing built on top. The figure comes from Berkeley’s AMP Laboratory.

Second, the source of the data. It ranges from people with privacy or ownership concerns, to an analyst who may require that results can be visualized, to the social, legal or political rules around the system. Third, other learners and agents, which may cooperate or compete. The paper sums up: environments provide resources to a learning algorithm and place constraints on those resources. Researchers increasingly formalize these relations and aim to design algorithms that are provably effective in various environments, and that let users express and control trade-offs among resources.

Privacy as a resource you spend

The paper’s main example is differential privacy. Its definition is a probabilistic channel between the data and the outside world, built so that someone looking at the output cannot reliably tell whether any particular person supplied data. The classical use was answering database queries, such as the largest balance across a set of accounts, with an answer close to the true one. Recent work brings it to machine learning, where the query is a prediction, such as the chance that a new transaction is fraud.

The paper then makes a design point. Placing a privacy-enhancing system inside a decision-theoretic framework gives the user a tuning knob. The user picks a privacy level that takes into account the questions that will be asked and what the answers are worth to them. A person might share most of their genome for research on a disease in the family, yet want much stronger protection when the same data might set insurance rates.

How the knob works

The paper does not give a formula, so here is the standard recipe from the work it cites (Dwork and others, 2006). Say we want to answer “how many people have a balance over a limit?” We add random noise to the true count. The noise comes from a Laplace distribution: a pointed tent-shaped curve centred on zero, whose width is set by a scale b. Wider tent, more noise.

answer
The number we release to the outside world.
count
The true number, which stays secret.
Laplace(b)
A random number drawn from the tent curve with scale b. Its median size, ignoring sign, is b times 0.693.
b
The noise scale. Larger b means more noise.
ε
The privacy budget. Small ε means strong privacy and heavy noise.

Why does 1/ε give privacy? Add or remove one person, and the true count moves by at most 1. A tent of scale b has height proportional to exp(−distance / b), so moving its centre by 1 changes any outcome’s likelihood by at most a factor of exp(1/b) = exp(ε). That is the guarantee: whatever an observer sees, adding or removing one person changes its likelihood by at most a factor of eε.

ε = 0.1: b = 10, typical error = 10 × 0.693 = 6.9 people, odds shift at most 1.11×. ε = 1: b = 1, typical error = 0.69, odds shift at most 2.72×.

Now the failure. The symptom: a private answer is useless. The measurement: compare the noise with the true count, as a share of it. The same 6.9-person error that is invisible on a count of 3,120 is 58% of a count of 12. The fix is not a cleverer algorithm. It is a larger group, or a larger budget, which the paper says users should be able to choose for themselves. Try both groups below.

Spend a privacy budget

Each bar counts how many of 600 private answers landed at that distance from the truth. Choose a group, then slide ε. Strong privacy is on the left of the slider.

0.1

Illustrative, and our own: the paper describes differential privacy in words only. Counts of 3,120 and 12 are made up; the Laplace recipe is the standard one from the cited 2006 work. The typical error is the median of 600 random draws, so it varies a little each time you ask.

Communication and time are resources too

The paper treats communication the same way. Data may be spread across sites because they are too big to gather, or because of administrative borders. We can then impose a bit-rate limit on the learner and study how performance falls as bandwidth shrinks, and how it improves as more sites join, trading these off against the amount of data. The aim, as in classical information theory, is a lower bound on what is achievable, and algorithms that reach it. A simple case: four hospitals each send only the average of their own patients, one number each, instead of every record. If the hospitals hold equal numbers of patients, the average of the four averages is exactly the global average. Four numbers crossed the network instead of thousands of records.

The paper links this to Chapter 3: the long-term goal is to give a system time and space budgets alongside accuracy goals, and let it find an operating point that meets all of them.

Noise of typical size 7 people is added to a count. For which true count does it hurt the most?

Chapter 8

Learning Like Nature, and Who Owns the Data

Test the idea of a never-ending learner, then weigh the privacy and public-good trade-off the authors leave to society

A toddler learns to crawl. Months later she learns to walk, and the crawling helps. Then she learns to run, and walking helps. Nobody gave her a separate data set for each skill. She learned in a long sequence, from simple to hard, with every skill making the next one easier.

Compare that with the learners in this lesson. Each one learns a single function from a single source of data, then stops. The paper’s section “Opportunities and challenges” starts here. It says machine learning remains a young field with many open problems, and that we can see some of them by comparing today’s methods with learning in nature: in humans and animals, in organizations, in economies and in biological evolution.

Opportunity one: learners that never stop

The authors note that humans learn many skills and kinds of knowledge from years of varied training, some supervised and some unsupervised, in a sequence from simple to harder. This has led researchers to explore lifelong or never-ending learners: systems that run nonstop for years, learning thousands of interrelated skills inside one architecture. The key property is that the system gets better at learning one skill because it has already learned another. One cited work (Mitchell and others, 2015) comes from the Never-Ending Language Learner project, which Mitchell, one of this paper’s authors, led. That project name is background from outside the review.

In plain terms, the learner carries its earlier knobs forward (Chapter 2) instead of starting from zero. This is called transfer. It works when the new skill resembles the old one. Say skill A is to separate good purchases from fraud, and skill B is the same job for a new country with slightly different habits. Starting from A’s knobs, B needs far fewer examples.

When the old skill gets in the way

Now the failure. The symptom: a learner that kept its old skill does worse on the new task than one that started fresh. The cause is that the old knobs point the wrong way, and the few new examples have to push them back. This is negative transfer. The measurement is a head-to-head comparison at the same number of examples, one learner warm-started from A and one cold-started from zero. The fix is to check how related the tasks are before reusing, or to hold the old knobs more loosely.

We can measure this. Let skill A be a straight-line boundary through the middle of a square. Let skill B be the same kind of boundary turned by an angle δ. A small δ means related skills. A turn of 180 degrees means B asks the opposite of A. We first train on 200 examples of A, then give a learner only a few examples of B and a fixed budget of 8 gradient steps. One learner starts from A’s knobs. The other starts from zero. For a turn of δ degrees, a perfect copy of A’s boundary labels a share 1 − δ/180 of B’s points correctly. So at 20 degrees it would score about 89% before seeing a single example of B, and at 90 degrees about 50%, a coin flip. The A that the device really learns scores 83% and 49% at those turns.

Carry a skill forward

The small square shows skill A’s boundary (pink) and the new skill B’s boundary (warm). The chart compares two learners on B. Turn B away from A, then change how many examples of B they get.

20°
5

Our own measurement; the paper makes the point in words and does not test it. Both learners are logistic regression with 8 gradient steps at learning rate 2. Each point averages 20 random sets of examples of B and is scored on 500 fresh points. Example counts: 0, 2, 5, 10, 20, 40.

Leave the turn at 20 degrees. With 5 examples of B the learner that keeps A is right 81% of the time, and the fresh learner only 59%. Now push the turn toward 180. The advantage shrinks, then flips: the learner that kept A is worse than one starting fresh, because its knobs point the wrong way. Unrelated skills are not free to reuse. A never-ending learner needs a way to decide what to carry over.

Opportunity two: learning in teams

The paper’s second idea is team-based, mixed-initiative learning. Today a learner usually analyzes data alone. People often work in teams: biologists have collected and analyzed genomic data together, combining different experiments and views. The authors imagine machines and people analyzing complex data side by side. Machines are good at teasing out subtle statistical regularities from huge data. People can draw on wide background knowledge to propose plausible explanations and new hypotheses. Together they might do what neither does alone. “Mixed-initiative” means either side can start a step.

The authors add that many results in learning theory apply to every learning system, whether a computer, an animal, an organization or evolution itself. So theory and algorithms from machine learning may help us understand learning in brains, groups and evolution, and machine learning may in turn gain from studying those systems.

Who owns the data, and who decides

The last part of the paper turns from method to society. Any powerful technology raises questions about which uses to encourage and which to discourage. The push to collect new kinds of personal data, driven by its economic value, raises privacy issues, as the paper has said. It also raises a second ethical issue: who will have access to online data, and who will own it and reap its benefits? Today, much data are collected by companies for particular uses that raise profits, with little reason to share. The authors argue that society could gain a lot, even from data already online, if those data were opened for the public good.

They give one worked scenario. Combine location data from online sources (cell phones, credit-card purchases at shops, security cameras) with online medical data such as emergency-room admissions. It would be feasible today to phone anyone who was in close contact yesterday with a person just admitted with an infectious disease, and tell them which symptoms to watch for. That could slow the spread of a pandemic. But the same system watches where everyone goes. The authors say there is a clear tension between personal privacy and public health, and that society as a whole must decide the trade-off. Their larger point is that the data already exist online, yet we lack the laws, customs, culture and mechanisms to let society benefit from them if it so chooses.

The paper’s closing claim. The authors write that machine learning is likely to be one of the most transformative technologies of the 21st century. Although it is impossible to predict the future, they say it is essential that society begin now to consider how to maximize its benefits.

Notice how the earlier chapters connect to this scenario. The privacy knob of Chapter 7 is a way to give such a system a tunable level of protection. The transfer idea above suggests the system could keep learning, which makes the question of who controls it more pressing, not less.

A learner carried over its knobs from skill A to a new skill B and did worse than a learner starting fresh. Which description fits, according to our measurement?

Chapter 9

Field Guide

Keep the numbers, the terms, a checklist and the core code on one page, and find where to go next

Jordan and Mitchell wrote a map of machine learning in 2015. A learning problem has three parts: a task, a performance measure and experience. A learner searches a space of programs, guided by that experience. Theory asks how much data and computing it needs. The three paradigms differ in the experience they use: labelled pairs, unlabeled data, or only a reward. Real systems blend them. The environment sets resource limits: computers, communication, privacy. The prospects are lifelong learning, human and machine teams, and a public decision on data ownership.

The numbers and ideas that matter

WhatNumber or ideaWhy it matters
The paperScience 349 (6245), pages 255 to 260, 17 July 2015A review, so a map and not an experiment
A learning problemtask + performance measure + training experienceChange one part and the best answer changes
Missed fraud 10, false alarm 1 (ours)flag when p > 1/11, about 0.09The performance measure sets the threshold
One gradient step, worked (ours)loss 12.67 to 0.216 at rate 0.1Training is a walk downhill on a loss
Floor on error (ours)7.9% at spread 0.15; 19.8% at 0.25More data cannot beat overlap in the problem
Figure 2, caption network14 × 14 feature map, 196 locationsAttention is 196 weights that add to 1 per word
k-means, worked (ours)six points, k = 2, score 4 after three assignsAssign and update lower the score and then stop
Bandit update, worked (ours)0.50 + (1/5)(1 − 0.50) = 0.60A running average of rewards
Noise for privacy (ours, standard)scale 1/ε; ε = 0.1 gives about 6.9 people, odds shift at most 1.11×Privacy is a budget paid in accuracy
Keeping an old skill (ours)81% vs 59% with 5 examples at 20°; worse at 90° and aboveTransfer helps related skills and hurts unrelated ones

Terms in one line each

TermMeaning
Supervised learningLearn a mapping from inputs to outputs from (x, y) pairs
Unsupervised learningFind structure in data with no labels: clusters, low-dimensional shape, topics
Reinforcement learningLearn a policy from rewards alone, often for a whole sequence of actions
RepresentationA rewriting of the input, learned by the inner layers of a deep network
Sample complexityHow much data a learner needs to reach a target accuracy
Computational complexityHow much computation a learner needs
OverfittingLow training error with high test error
Differential privacyA guarantee that one person’s presence barely changes the output
Lifelong learningOne system that learns many related skills over years and reuses them

A checklist before you build

  1. Write the three parts. State the task, the performance measure with its costs, and the experience you have.
  2. Pick the paradigm. Do you have labelled pairs, unlabeled data, or only rewards? Can you blend them?
  3. Score on fresh data. Report test error, not training error, and compare them.
  4. Know your floor. Ask how much of the error is overlap in the problem and how much is the learner.
  5. Set budgets. Decide data, time, space and communication limits before you choose a method.
  6. Check the environment. Who owns the data, what must stay private, who must be able to read the output?
  7. Separate prediction from cause. If someone will act on the model, ask whether it knows what causes what.
  8. Reuse with care. Compare a warm start against a fresh start before you trust an old skill.

The core as code

Five short functions carry the lesson. Each one is a sketch in plain NumPy that runs as written; the chapter number in each comment says where to find its explanation.

pythonimport numpy as np

# Chapter 2: learn a program by walking downhill (logistic regression)
def fit(X, y, steps=1200, lr=5.0):
    w = np.zeros(X.shape[1] + 1)                       # knobs: one bias, one tilt per feature
    Xb = np.c_[np.ones(len(X)), X - 0.5]               # shape (n, d+1), centred features
    for _ in range(steps):
        p = 1 / (1 + np.exp(-Xb @ w))                  # predicted chance of fraud, shape (n,)
        w -= lr * Xb.T @ (p - y) / len(y)              # slope of the loss, then a step against it
    return w

# Chapter 1: choose the threshold that minimizes cost, not errors
def best_threshold(scores, y, c_miss=10, c_alarm=1):
    ts = np.linspace(0.05, 0.95, 91)
    cost = [c_miss * np.sum((y == 1) & (scores <= t)) + c_alarm * np.sum((y == 0) & (scores > t)) for t in ts]
    return ts[int(np.argmin(cost))]

# Chapter 5: k-means, assign then update
def kmeans(X, k, iters=50, seed=0):
    rng = np.random.default_rng(seed)
    C = X[rng.choice(len(X), k, replace=False)]        # k starting centres, shape (k, d)
    for _ in range(iters):
        a = ((X[:, None] - C[None]) ** 2).sum(-1).argmin(1)          # nearest centre, shape (n,)
        C = np.array([X[a == j].mean(0) if np.any(a == j) else C[j] for j in range(k)])
    return C, a

# Chapter 6: epsilon-greedy bandit
def bandit(rates, eps=0.1, pulls=200, seed=0):
    rng = np.random.default_rng(seed)
    Q, n, wins = np.zeros(len(rates)), np.zeros(len(rates)), 0
    for _ in range(pulls):
        a = rng.integers(len(rates)) if rng.random() < eps else int(np.argmax(Q))
        r = float(rng.random() < rates[a])
        n[a] += 1
        Q[a] += (r - Q[a]) / n[a]                       # running average of rewards
        wins += r
    return Q, wins

# Chapter 7: release a count with differential privacy
def private_count(true_count, eps, rng):
    return true_count + rng.laplace(scale=1.0 / eps)    # one person changes the count by at most 1

Read it function by function. fit is the walk downhill: shapes (n, d+1) in, one knob per column out. best_threshold shows the cost measure picking the dial. kmeans is assign and update. bandit keeps a running average and explores with probability ε. private_count adds noise at scale 1/ε.

Where this sits

The paper is from 2015, before the large language models and the multimodal systems of this course. Its frame still applies. Today’s pretraining is unsupervised or self-supervised learning on huge unlabeled data, followed by supervised and reward-based training. The authors’ worries about data ownership, privacy and public benefit are now central to the field. Read it as the map that the course’s later lectures fill in. It is the reading for Lecture 2, Datasets and Research, which looks at where the data for such learners come from.

Keep going

Credit

All ideas in this lesson belong to the authors, Michael I. Jordan (University of California, Berkeley) and Tom M. Mitchell (Carnegie Mellon University). Read the original: Machine learning: Trends, perspectives, and prospects, Science 349 (6245), 255 to 260, 17 July 2015, DOI 10.1126/science.aaa8415. The paper’s own figures are not reproduced here. Every device in this lesson is our own toy, and each one says in its fine print what is ours and what is the paper’s.

The takeaway. Machine learning is a search for a program, guided by experience and judged by a performance measure that you choose. It works inside an environment of limited data, time, communication and trust. The paper asks you to hold both views at once: the science of what any learner can do, and the choices a society must make about the data.
Your team reports 98% accuracy for a rare-event detector. Using the paper’s framing, what is the first thing to check?

Now press Present or Teach and explain the paper from memory: the three parts of a learning problem, the search for a program, the data and time budgets, the three paradigms, and what the environment and society add. Then go back to the fraud scatter at the top, set the examples to 4 and then to 60, and say in your own words why the learned rule overtakes the hand-written one.

Machine Learning: Trends, Perspectives, and Prospects, by M. I. Jordan and T. M. Mitchell
Read the paper · Lecture 2, Datasets and Research · The MMAI course schedule · Back to Gleams