Learning from Data

Strip machine learning to its frame and it is disarmingly simple. You are handed a dataset of examples, each a pair $({\mathbf{x}}_i,y_i)$: a feature vector ${\mathbf{x}}_i\in {\mathbb{R}}^d$ describing one instance (the two coordinates of a point, the pixels of an image, the words of an email), and a label $y_i$ naming the answer (which class it belongs to). This is supervised learning: every training example comes with its correct answer attached.

You then choose a model: a function $f_{\theta }$ from feature vectors to predictions, carrying a bundle of adjustable parameters $\theta$. Learning is the act of setting $\theta$ so that $f_{\theta }(\mathbf{x})$ tends to agree with the true $y$. To make “agree” precise you need a loss function $L(\theta )$ — a single number, computed over the data, that is large when the model is wrong and small when it is right. Training is then an optimization: find the $\theta$ that minimizes $L(\theta )$.

But minimizing the training loss is not the true goal, and this is the subtlety that makes learning more than curve-fitting. The goal is generalization: low error on new, unseen data drawn from the same source. A model that simply memorizes every training pair achieves zero training loss and may still be useless — it has learned the noise, not the pattern. So we always hold back a test set, never shown during training, and judge the model by its error there. Keep that distinction close; §14.4 is entirely about it, and it is the reason a quantum model's expressiveness is a double-edged gift.

The simplest useful model is linear: score a feature vector by a weighted sum of its components. For classification into two classes we want the score to read as a probability, so we squash the linear score through the logistic sigmoid $\sigma (z)=1/(1+e^{-z})$, which maps the whole real line into $(0,1)$. That is logistic regression:

The natural loss for a probabilistic prediction is the cross-entropy (equivalently, the negative log-likelihood): reward the model for putting high probability on the true label,

Now, how do we minimize it? The workhorse of essentially all of machine learning is gradient descent. The gradient $\nabla L$ points in the direction of steepest increase of the loss; so to go down, step the opposite way, a small distance controlled by the learning rate $\eta$:

Repeat, and the loss walks downhill. For logistic regression the gradient is not a numerical approximation but an exact, closed formula — the chain rule applied to (14.1)–(14.2) collapses, thanks to the sigmoid's tidy derivative ${\sigma }^{\prime }=\sigma (1-\sigma )$, into something strikingly clean:

The residual $p_i-y_i$ — how far the predicted probability sits from the truth — weights each example's contribution. Deriving (14.4) is the chapter's hard exercise; the lab then checks the hand-derived formula against a finite-difference gradient to nine digits, because a wrong gradient is the most common and most silent bug in all of learning. Watch the update run: at epoch 0 the boundary is untrained, and each step of (14.3) rotates and slides it until the two blobs fall cleanly apart.

That is the entire engine. Every model in this book — including the variational quantum classifier of Chapter 16 — is trained by some form of (14.3); only the shape of $f_{\theta }$ and the way its gradient is obtained will change.

A linear model draws a straight boundary — a hyperplane. Many problems are not so kind: imagine one class forming a disc and the other a ring around it. No line separates them. The classic fix is a feature map $\varphi$ that lifts each point into a higher-dimensional space where the classes do pull apart. For the ring, the map $\varphi (\mathbf{x})=(x_1,x_2,x_1^2+x_2^2)$ adds a third coordinate — the squared radius — and in that lifted space a flat plane at the right height slices the inner disc from the outer ring. A linear model in $\varphi$-space is a curved model back in the original one.

The difficulty is that useful feature maps are enormous — often infinite-dimensional — and writing out $\varphi (\mathbf{x})$ explicitly is hopeless. Here is the escape, and it is one of the most elegant moves in the subject. Look back at logistic regression: the model and its gradient touch the data only through inner products and evaluations. It turns out that a whole family of linear methods can be rewritten so that features appear only inside inner products $⟨\varphi (\mathbf{x}),\varphi ({\mathbf{x}}^{\prime })⟩$. And an inner product is a single number. So define the kernel

and if you can compute $k$ cheaply, you never need $\varphi$ at all. This is the kernel trick: work in a gigantic feature space while only ever evaluating a small function of pairs of original inputs. The decision function becomes a weighted sum of kernels against the training points,

trained by gradient descent on the coefficients ${\alpha }_j$ — the same optimizer as before, lifted. The most common choice is the Gaussian or radial-basis-function (RBF) kernel,

whose implicit feature space is infinite-dimensional, yet which costs one exponential of a distance to evaluate. The width $\gamma$ sets how far each training point's influence reaches. In the lab the RBF kernel takes two concentric rings — the exact case a line cannot handle — and separates them with a closed curve, lifting test accuracy from chance to above 0.9.

A model powerful enough to fit anything is a model powerful enough to fit noise. Push the RBF width or the training long enough and a kernel model can wrap a tight bubble around every single training point, driving the training loss to zero — and then failing badly on new data, because it memorized the sample rather than learning the rule. This is overfitting, and it is the central hazard of all flexible models.

The diagnosis is the train/test split: reserve part of the data, never train on it, and compare training error to test error. When the two track each other, the model generalizes; when training error keeps falling while test error rises, it is overfitting. The standard cure is regularization — add a penalty on the size of the parameters to the loss, most simply the $L_2$ term

which discourages extreme weights and so favors smoother, simpler boundaries. The strength $\lambda$ trades training fit against smoothness; it is a hyperparameter, tuned by watching the test error, not the training error. The lab uses a small $\lambda$ throughout — enough to make the objective strongly convex and the optimizer well-behaved — and reports the train/test gap directly as a referee. That referee is graded jointly with an absolute accuracy floor, because the gap alone proves nothing: a model stuck at chance scores a perfect gap of zero while having learned nothing at all. Only a small gap and high accuracy on both sides earn the verdict “generalized”.

The lab then goes one step further and produces overfitting on demand: it sweeps the RBF width $\gamma$ across more than three orders of magnitude. At small $\gamma$ the kernel is one broad blur and the model underfits; at moderate $\gamma$ the test accuracy peaks; and at $\gamma =100$ each training point sits inside its own private kernel bubble, so the model memorizes the training set exactly — train accuracy pins to 1 while test accuracy collapses. A referee requires that gap to open by at least 0.25: the memorization failure mode, exhibited as a measurement rather than asserted as a moral.

This is the vocabulary Chapters 15 and 16 rebuild with qubits. There, $f_{\theta }$ becomes a parametrized quantum circuit and the feature map $\varphi$ encodes data into a quantum state — but the loss, the gradient step (14.3), the kernel (14.5), the train/test split, and the specter of overfitting are all exactly these. Knowing which part is genuinely new is knowing this chapter cold.

The lab implements everything above in Rust with no ML library — only rand for synthetic data. The linear model is logistic regression: a probability from a sigmoid, a cross-entropy loss with a small $L_2$ penalty, and the analytic gradient (14.4) worked out by hand:

1impl Linear {
2    fn score(&self, x: &[f64; 2]) -> f64 {
3        self.w[0] * x[0] + self.w[1] * x[1] + self.b
4    }
5    fn prob(&self, x: &[f64; 2]) -> f64 {
6        sigmoid(self.score(x))
7    }
8}
9
10/// Regularized cross-entropy loss:
11///   L = (1/N) Σ [ −y log p − (1−y) log(1−p) ] + (λ/2)‖w‖².
12fn logistic_loss(m: &Linear, data: &[Sample], lambda: f64) -> f64 {
13    let n = data.len() as f64;
14    let mut ce = 0.0;
15    for s in data {
16        let p = m.prob(&s.x).clamp(1e-15, 1.0 - 1e-15);
17        ce += -(s.y * p.ln() + (1.0 - s.y) * (1.0 - p).ln());
18    }
19    ce / n + 0.5 * lambda * (m.w[0] * m.w[0] + m.w[1] * m.w[1])
20}
21
22/// The ANALYTIC gradient of the regularized cross-entropy, returned as
23/// (∂L/∂w0, ∂L/∂w1, ∂L/∂b). Derived once, checked against finite differences.
24///   ∂L/∂w = (1/N) Σ (p_i − y_i) x_i + λ w,   ∂L/∂b = (1/N) Σ (p_i − y_i).
25fn logistic_grad(m: &Linear, data: &[Sample], lambda: f64) -> [f64; 3] {
26    let n = data.len() as f64;
27    let (mut gw0, mut gw1, mut gb) = (0.0, 0.0, 0.0);
28    for s in data {
29        let d = m.prob(&s.x) - s.y;
30        gw0 += d * s.x[0] / n;
31        gw1 += d * s.x[1] / n;
32        gb += d / n;
33    }
34    [gw0 + lambda * m.w[0], gw1 + lambda * m.w[1], gb]
35}

The correctness of learning rests entirely on that gradient being right, so the first referee checks it against a central finite-difference gradient of the very same loss — asserting is_finite() before smallness, and tightened to the accuracy actually achieved:

1// --- Referee 1: analytic gradient vs central finite differences ---------
2// Check at a deliberately non-trivial θ, on the real loss+regularizer.
3let probe = Linear { w: [0.7, -1.3], b: 0.4 };
4let g_analytic = logistic_grad(&probe, &blob_train, lin_lambda);
5let h = 1e-6;
6let mut g_numeric = [0.0f64; 3];
7for k in 0..3 {
8    let mut pp = probe.clone();
9    let mut pm = probe.clone();
10    match k {
11        0 => {
12            pp.w[0] += h;
13            pm.w[0] -= h;
14        }
15        1 => {
16            pp.w[1] += h;
17            pm.w[1] -= h;
18        }
19        _ => {
20            pp.b += h;
21            pm.b -= h;
22        }
23    }
24    g_numeric[k] = (logistic_loss(&pp, &blob_train, lin_lambda)
25        - logistic_loss(&pm, &blob_train, lin_lambda))
26        / (2.0 * h);
27}
28let mut grad_err = 0.0f64;
29for k in 0..3 {
30    grad_err = grad_err.max((g_analytic[k] - g_numeric[k]).abs());
31}
32assert!(grad_err.is_finite());
33// Tolerance sits just above the achieved 2.92e-10, which is the round-off
34// floor of a central difference at h = 1e-6 (≈ ε/h), not slack.
35referees.push(Referee {
36    name: "Analytic ∇L matches finite difference  max|Δ|".into(),
37    value: grad_err,
38    tol: 4.5e-10,
39    pass: grad_err < 4.5e-10,
40});

The kernel classifier reuses the identical gradient-descent loop, lifted into feature space by (14.6)–(14.7). The RBF kernel is one line, and it never forms the feature map $\varphi$ it secretly represents:

1/// Gaussian / radial-basis-function kernel k(u,v) = exp(−γ‖u−v‖²). This single
2/// scalar IS the inner product ⟨φ(u),φ(v)⟩ in an infinite-dimensional feature
3/// space — computed without ever forming φ. That is the kernel trick.
4#[inline]
5fn rbf(u: &[f64; 2], v: &[f64; 2], gamma: f64) -> f64 {
6    let d0 = u[0] - v[0];
7    let d1 = u[1] - v[1];
8    (-gamma * (d0 * d0 + d1 * d1)).exp()
9}
10
11// …
12
13impl Kernel {
14    fn score_new(&self, x: &[f64; 2]) -> f64 {
15        let mut z = self.b;
16        for (a, xj) in self.alpha.iter().zip(self.support.iter()) {
17            z += a * rbf(xj, x, self.gamma);
18        }
19        z
20    }
21    // …
22}

Eight referees run and write their verdicts to JSON, which the panel below reads live — nothing is hardcoded, and every number in this paragraph is a tolerance the referees enforce, not a pasted result. The analytic gradient must match finite differences to better than $5\times 10^{-10}$ (the round-off floor of the central difference itself); gradient descent never lets the loss rise; the plain linear model sits near chance on the concentric rings while the identical code clears 0.95 on the blobs, so its failure is the data's geometry, not a broken optimizer; the RBF kernel clears 0.90 on those same rings; the generalization referee demands a train/test gap under 0.10 and both accuracies above 0.85 — the floor matters, because a chance-level model has a perfect gap; the $\gamma$-sweep must not move when its training budget is doubled; and at $\gamma =100$ the overfitting gap must open by at least 0.25 with train accuracy 0.95 or better. The two heatmaps show the kernel trick plainly — one straight cut versus a closed curve:

Run it yourself with cargo run --release in Rust-QML/ch14-classical-ml. You now have the whole classical skeleton — model, loss, gradient descent, kernel, generalization — built and checked. Part IV spends its remaining chapters swapping the classical pieces for quantum ones, one at a time, and this chapter is the control against which every claimed quantum difference is measured.