How learning works

A number on a page is not yet a prediction. First we need a rule. Put 2 marbles in a bowl, then add 1. The rule takes 2 and gives back 3. Mathematicians call a rule like this a function.

A function sends an input number to an output. Start with 2 and add 1.

function addOne(value) {
  return { output: value + 1 };
}
const result = addOne(2);

In f(x), the letter x is a space for whatever number goes in; f is the name of the rule. The brackets mean “use this input.” You can put 4 in place of 2 and get f(4) = 5.

The paper groups numbers into sets. ℕ holds counting numbers; ℤ also includes zero and negative numbers, like a debt of −2; ℝ includes numbers such as 1.5 as well. The shorthand [5] means {1, 2, 3, 4, 5}, not just 5. A vector is a list of numbers, such as (2, 3).

Imagine four equally likely outcomes: 0, 0, 0 and 1. Add them and divide by 4: (0 + 0 + 0 + 1)/4 = 0.25. This is the expected average, written with E: it uses the chances of all outcomes. An average from actual draws can differ. Σ means add the numbers.

The rest of the paper uses lengths, distances and probabilities to compare functions. We will meet those symbols as soon as we need them. For now, try changing the number of marbles in the illustration: the rule stays “add one.”

Suppose we want to predict the temperature tomorrow. One example contains an input, such as today’s temperature, and a correct answer, such as tomorrow’s temperature. The pair is written z = (x, y): x goes in; y is the label we hope to predict.

For invented temperatures in degrees Celsius, an input of 2 has label 5. A rule predicts 4. How far is it from the label?

function predictionLoss(value, target) {
  const prediction = 2 * value;
  return { prediction, loss: (prediction - target) ** 2 };
}
const result = predictionLoss(2, 5);

The squared loss is 1°C². An error of 2°C would cost 4°C². Predicting a number this way is called regression.

Another task is choosing between two classes. Imagine a spam filter: +1 means spam and −1 means ordinary mail. Its raw score might be any number. We turn that number into a class and compare the class with the label, rather than treating a raw zero as automatically correct.

Use +1 and −1 for two classes. The label is +1; the score starts at −2.

function classify(score, target) {
  if (target !== 1 && target !== -1) {
    throw new Error('Target must be +1 or -1');
  }
  let predicted = -1;
  if (score >= 0) predicted = 1;
  let loss = 0;
  if (predicted !== target) loss = 1;
  return { predicted, loss };
}
const result = classify(-2, 1);

At score 0 the paper’s sign rule chooses +1. JavaScript’s Math.sign(0) returns 0, so it is not the same rule. For a toy input labelled −1, a zero score would be a classification mistake.

With labelled examples, a learner can adjust a rule. This is supervised learning. Without human-supplied labels, it might instead look for structure. It can also create a question by hiding part of its own input: hide “sleeps” from “The cat sleeps”; use the visible words as input and the hidden word as the target. That is one way to make a learning task from unlabelled data.

A learner can instead describe which temperatures are common. A density curve helps show which ranges, such as 19°C to 21°C, are more likely. The area under the curve over a range gives its probability: the chance that a measurement falls in that range. The curve’s height at one exact temperature is not itself a probability.

Now how can a rule learn a complicated prediction? A neuron starts with input numbers, multiplies each by a weight, adds the products, and adds a bias. A weight controls how strongly an input matters; a bias shifts the sum even if all the inputs are zero.

Put the inputs in a list x. A table W holds the weights, and a list b holds the biases. For one neuron, inputs 2 and 3, weights 2 and −1, and bias 1 give 2×2 − 1×3 + 1 = 2. The layer then applies a rule called an activation, written ρ.

function layer(firstInput, secondInput, bias) {
  const sum = 2 * firstInput - secondInput + bias;
  return { sum, relu: Math.max(0, sum) };
}
const result = layer(2, 3, 1);

ReLU keeps a positive sum and changes a negative one to zero: −2 becomes 0. In the formula, Φ names the calculation, θ holds its adjustable settings, and (1) marks the first layer. A bar over Φ marks the result after activation. A rule that multiplies inputs by weights and then adds a bias is called affine. If the bias is zero, it is linear.

The network in Figure 1.1 joins many neurons into stages: 3 input numbers → 4 hidden neurons → 6 hidden neurons → 1 output. There are two hidden layers and three sets of trainable weights and biases. The final stage is affine; there is no ReLU after its output in the paper’s definition.

The network has 3 inputs, then hidden layers of 4 and 6 neurons, then 1 output. Each neuron connects to every number in the stage before it. The first stage has 3×4 = 12 weights and 4 biases. The next has 4×6 = 24 weights and 6 biases. The last has 6×1 = 6 weights and 1 bias.

function countParameters(
  inputs, firstLayer, secondLayer, outputs
) {
  const weights = inputs * firstLayer + firstLayer * secondLayer
    + secondLayer * outputs;
  const biases = firstLayer + secondLayer + outputs;
  return { weights, biases, parameters: weights + biases };
}
const result = countParameters(3, 4, 6, 1);

The network has 42 weights and 11 biases, for 53 adjustable numbers.

Each hidden neuron applies an activation after the weighted sum. ReLU and sigmoid are two different possible rules for this step; an architecture usually chooses its activation design in advance.

Apply ReLU and sigmoid to the same input 0. These are two choices from the paper’s activation table.

function activations(value) {
  const relu = Math.max(0, value);
  const sigmoid = 1 / (1 + Math.exp(-value));
  return { relu, sigmoid };
}
const result = activations(0);

Sigmoid takes 0 to 0.5, while ReLU takes 0 to 0. At −2, ReLU gives 0 and sigmoid gives about 0.119. The paper also lists a Gaussian activation: it is highest at zero and falls on either side.

Why not use only weight-and-bias steps? Two affine steps with nothing nonlinear between them can be combined into one affine step.

First apply an affine rule, then another: multiply the first result by 4 and add 5.

function combineLayers(value) {
  const h = 2 * value + 3;
  return { h, output: 4 * h + 5, combined: 8 * value + 17 };
}
const result = combineLayers(1);

The two steps combine into 8x + 17. An activation like ReLU lets different inputs follow different pieces, which cannot always be collapsed this way.

Imagine changing the 53 weights and biases while keeping the layers and their activation rules fixed. Different settings can give different prediction rules; some settings give the same rule. The layer sizes and activation rules make up the architecture. All rules it can produce form its hypothesis set: the rules it is allowed to choose from.

Next comes the question “Which settings are good?” We need a numerical way to judge mistakes. On each training example we compute a loss, then add the losses and divide by how many examples we saw.

A model makes two mistakes in five invented training examples. Each mistake counts as 1 and each correct answer as 0.

function averageRisk(losses) {
  let mistakes = 0;
  for (const loss of losses) mistakes += loss;
  return { mistakes, average: mistakes / losses.length };
}
const result = averageRisk([0, 0, 1, 0, 1]);

The average 0.4 is a 40% error rate for this loss. Squared loss has different units and is not a percentage.

The practice average is the total loss on the training examples divided by their number. Choosing an allowed rule with the smallest practice average is called empirical risk minimization, or ERM. It chooses using the examples we have; it does not promise success on future ones.

In the formula, F is the set of allowed rules, s is the collected training examples, and R̂ is their average loss. The symbol argmin means choose a rule with the lowest average. For example, three candidates have average losses 0.5, 0.2 and 0.4.

function bestCandidate(losses) {
  const minimum = Math.min(...losses);
  return { minimum, candidate: losses.indexOf(minimum) + 1 };
}
const result = bestCandidate([0.5, 0.2, 0.4]);

Candidate 2 wins this toy comparison. With millions of weights, an algorithm normally searches for a good setting rather than comparing every possibility.

Classification loss has a problem for this search: scores −2 and −1 are both wrong when the label is +1. Counting mistakes gives each a loss of 1, even though −1 is closer to becoming positive. A smooth replacement loss can change before the chosen class does.

For a positive label, compare a score with zero. Both −2 and −1 produce a wrong class, but logistic loss distinguishes them.

function compareLosses(score) {
  let classLoss = 0;
  if (score < 0) classLoss = 1;
  const logistic = Math.log(1 + Math.exp(-score));
  return { classLoss, logistic };
}
const result = compareLosses(-2);

For label +1, logistic loss rates the score −2 at about 2.127 and −1 at about 1.313. The class is still wrong, but the smaller loss signals improvement. This helps training search, although the lowest logistic loss need not give the fewest mistakes in every family of rules.

Sometimes we also dislike extreme parameter values. We can add a penalty: square each parameter, add the squares, and multiply by a small strength α. The training objective then balances fit with parameter size.

Compare two toy models. With penalty strength 0.01, model A has objective 0.10 + 0.01×100 = 1.10; model B has 0.15 + 0.01×2 = 0.17. The strength sets how much the squared parameters count.

function penalizedLoss(strength) {
  return { A: 0.1 + strength * 100, B: 0.15 + strength * 2 };
}
const result = penalizedLoss(0.01);

At this penalty strength model B has the smaller objective. This does not prove B will predict future examples better.

We have measured the errors on examples we already possess. But the real goal is to do well on a fresh example drawn from the same kind of process. The paper calls the average over that unknown distribution the risk, written R(f).

Imagine two kinds of future case. A no-mistake case has a three-in-four chance, or 0.75; a mistake has a one-in-four chance, or 0.25. Compare that chance-weighted average with two observed cases: one correct and one wrong.

function compareRisk(chance) {
  if (!(chance >= 0 && chance <= 1)) {
    throw new Error('Chance must be between 0 and 1');
  }
  const expectedRisk = (1 - chance) * 0 + chance * 1;
  const observedAverage = (0 + 1) / 2;
  return { expectedRisk, observedAverage };
}
const result = compareRisk(0.25);

The expected loss is 0.25; the observed mean is 0.5. Expectation describes the distribution, while the sample mean describes the cases drawn.

For its classical results, the paper assumes each training example and the new example is drawn independently from the same distribution: each comes from the same kind of world, without one draw deciding another. If the world changes, the guarantees need not hold. Uncertain labels can cause unavoidable error even for the best predictor.

A rule can miss the answer for three reasons. The allowed rules may not include a close enough answer. The search may fail to find the best allowed rule. Or the practice examples may give a misleading average. These are called approximation, optimization and generalization errors, in that order.

Imagine the best possible rule and its average loss on future examples. Excess risk is how much more loss our rule has than that best average. The next bound adds three allowances: for missing the best setting, for gaps between practice and future averages, and for missing a good enough rule. The gap allowance uses the largest such gap across all allowed rules, not just five test cases. Try 0.1, 0.2 and 0.3.

function riskBound(generalization) {
  return { upperBound: 0.1 + 2 * generalization + 0.3 };
}
const result = riskBound(0.2);

Put the toy values into the ceiling: 2×0.2 = 0.4, then 0.1 + 0.4 + 0.3 = 0.8. Under the paper’s definitions, excess risk cannot exceed this ceiling. It is not the actual error. The middle term is counted twice because the comparison uses two training-to-future gaps.

We now have a map for the rest of the paper: can we find good settings, can this kind of network express the answer, and can we trust it on examples we did not show it?

The model family might contain a very good rule, but how do we find its weights? Take a single dial w that should equal 2. Use squared loss L(w) = (w − 2)². At w = 5 the loss is (5 − 2)² = 9.

A gradient tells us the local direction in which loss rises fastest. For this one-dial example the gradient is 2(w − 2), so at w = 5 it is 6. A positive gradient means a small move left should reduce loss.

The paper updates parameters Θ by averaging the loss gradients over a mini-batch S′ of m′ examples, with learning rate η. For one weight and one practice example, use loss L(w) = (w − 2)² at w = 5.

function updateWeight(weight, target, step) {
  const gradient = 2 * (weight - target);
  return { gradient, next: weight - step * gradient };
}
const result = updateWeight(5, 2, 0.25);

Subtracting 0.25 × 6 moves the dial from 5 to 3.5. The new loss is (3.5 − 2)² = 2.25, smaller than 9. The number 0.25 is a learning rate: too large a rate can jump past a good setting.

A weight near the beginning can change a later calculation, which can change the final loss. The chain rule works out how these changes connect. Backpropagation keeps track of them from the loss back through the layers, so we can see how each earlier weight affects the loss. During prediction, the output does not travel backward.

Instead of measuring loss across every training example for every move, stochastic gradient descent (SGD) can use a small randomly chosen group called a mini-batch. Its direction is a noisy estimate of the full gradient. Some simple bowl-shaped losses have convergence guarantees; general neural-network landscapes can have several valleys or flat areas. A successful step here is not a proof of global success.

What if we search perfectly, but none of the allowed rules can give the right answers? A machine that can only return the number 1 cannot reproduce the targets 0, 1 and 2 at three different inputs.

The approximation question is about the family of rules itself, before we ask whether training has found the right member.

At toy inputs 0, 1, 2 the target outputs are 0, 1, 2. Compare the flat rule 1 with the flexible rule that returns its input.

function approximationError(flatOutput, inputs, targets) {
  let flatTotal = 0;
  let flexibleTotal = 0;
  for (let index = 0; index < targets.length; index++) {
    flatTotal += (flatOutput - targets[index]) ** 2;
    flexibleTotal += (inputs[index] - targets[index]) ** 2;
  }
  return {
    flat: flatTotal / targets.length,
    flexible: flexibleTotal / targets.length,
  };
}
const result = approximationError(1, [0, 1, 2], [0, 1, 2]);

The flat rule predicts 1, 1, 1: its squared errors are 1, 0, 1, with mean 2/3. The rule f(x) = x predicts 0, 1, 2 with zero error on these three points. This is a finite toy comparison, not a claim that the flexible rule is correct everywhere.

Take a target rule that changes without jumps as its inputs change, and restrict the inputs to a limited range. The paper reviews results showing that networks with suitable activations, including ReLU, and enough hidden neurons can get as close as desired under their stated conditions. This means the needed settings exist; it does not promise a small network or a way to find them by training.

A network can also fit a finite list of examples exactly, including arbitrary labels under suitable conditions. Exact matching of those points says nothing on its own about what happens between them or on future inputs.

A model might remember five practice questions perfectly without understanding what rule will work on the sixth. We therefore distinguish its training average from how it behaves on unfamiliar examples.

Use a separate collection of examples to check a finished model. Do not use that collection to pick the weights if you want an honest check. The test examples should come from the kind of world in which the model will be used.

A toy rule gets 4 of 5 training cases and 3 of 5 new cases correct.

function compareMistakes(newMistakes, cases) {
  if (!Number.isInteger(cases) || cases <= 0
    || !Number.isInteger(newMistakes)
    || newMistakes < 0 || newMistakes > cases) {
    throw new Error('Use whole numbers: 0 <= mistakes <= cases');
  }
  return { training: 1 / cases, newCases: newMistakes / cases };
}
const result = compareMistakes(2, 5);

Both fractions are noisy estimates from five cases; the new-case fraction is not automatically the true future risk.

Classical theory often assumes examples are picked independently: one pick does not decide the next. It also limits the family of rules being considered. Under such assumptions, it can bound the gap between practice and future averages. More independent examples usually tighten the bound; more freedom to fit any labels can make some bounds larger.

For two points, can our family of rules assign every possible pair of labels: (+1, +1), (+1, −1), (−1, +1) and (−1, −1)? VC dimension measures how many points a family can label in every possible way. A bound using only a huge network’s parameter count often tells us little about its performance on new cases.

Put our three questions together. First, can the chosen network express the needed rule? Second, can training locate useful parameters? Third, will the result work beyond its practice examples?

A toy model makes no mistakes on five training cases but two on five new cases.

function generalizationGap(newMistakes, cases) {
  if (!Number.isInteger(cases) || cases <= 0
    || !Number.isInteger(newMistakes)
    || newMistakes < 0 || newMistakes > cases) {
    throw new Error('Use whole numbers: 0 <= mistakes <= cases');
  }
  const training = 0 / cases;
  const newCases = newMistakes / cases;
  return { training, newCases, gap: newCases - training };
}
const result = generalizationGap(2, 5);

The observed gap of 0.4 on five new cases does not tell us the true average over all future cases.

The rest of the paper follows seven further questions: why very large networks sometimes generalize; what extra layers buy; how they handle many inputs; why gradient-based training can succeed; what special structures change; what features are learned; and why scientific equations can help.

Each answer has conditions. Sometimes the authors show a rigorous result for a specific model; sometimes they give a mathematical illustration or report an observation that researchers still want to explain.