Chapter 5: Advanced Classical Machine Learning¶
This chapter bridges classical and quantum ML by examining advanced classical techniques whose structure or limitations motivate quantum approaches. Gaussian processes motivate quantum kernel methods; reinforcement learning grounds quantum RL; graph neural networks connect to quantum graph algorithms; Bayesian deep learning relates to quantum Bayesian inference.
Learning Objectives
By the end of this chapter, you will be able to:
-
Apply Gaussian Processes for regression and classification
-
Understand variational inference and the ELBO
-
Work with Graph Neural Networks via message passing
-
Formulate MDPs and derive policy gradient algorithms
-
Identify classical techniques that motivate quantum extensions
5.1 Gaussian Processes¶
5.1.1 GP Prior and Posterior¶
A Gaussian Process \(f\sim\mathcal{GP}(\mu,k)\) is a distribution over functions such that any finite collection has a joint Gaussian distribution:
where \(\mathbf{K}_{ij} = k(\mathbf{x}_i,\mathbf{x}_j)\) (kernel/covariance matrix).
GP Regression (Gaussian likelihood \(y_i = f(\mathbf{x}_i) + \varepsilon_i\), \(\varepsilon_i\sim\mathcal{N}(0,\sigma_n^2)\)):
Posterior predictive:
where \(k_* = [k(\mathbf{x}_*,\mathbf{x}_1),…]^\top\) and \(k_{**}=k(\mathbf{x}_*,\mathbf{x}_*)\).
Note
GP regression requires inverting an \(N\times N\) matrix: \(O(N^3)\) time and \(O(N^2)\) memory. For large \(N\), sparse GPs, inducing points, or quantum-enhanced kernel evaluation may help. See Chapter 8 for the connection.
Solved Example 5.1
Problem: GP regression with \(k(\mathbf{x},\mathbf{x}') = e^{-(x-x')^2}\), \(\sigma_n^2=0.01\), training data \(\{(0,1),(1,0.5),(2,0)\}\). Predict \(f(1.5)\).
Solution: \(\mathbf{K} = \begin{pmatrix}1 & e^{-1} & e^{-4}\\ e^{-1} & 1 & e^{-1}\\ e^{-4} & e^{-1} & 1\end{pmatrix} \approx \begin{pmatrix}1&0.368&0.018\\0.368&1&0.368\\0.018&0.368&1\end{pmatrix}\)
\(k_* = [e^{-2.25}, e^{-0.25}, e^{-0.25}]^\top \approx [0.105, 0.779, 0.779]^\top\)
\(\mu_{1.5} = k_*^\top(\mathbf{K}+0.01I)^{-1}[1, 0.5, 0]^\top \approx 0.26\) (computed numerically).
5.2 Bayesian Machine Learning and Variational Inference¶
5.2.1 Variational Inference and ELBO¶
For a model \(p(\mathbf{x},\mathbf{z})\) with latent \(\mathbf{z}\), the exact posterior \(p(\mathbf{z}|\mathbf{x})\) is often intractable. Variational inference approximates it with \(q_\phi(\mathbf{z})\):
Maximizing the ELBO (Evidence Lower BOund) minimizes the KL divergence.
5.2.2 Variational Autoencoders¶
A VAE has encoder \(q_\phi(\mathbf{z}|\mathbf{x})\) and decoder \(p_\theta(\mathbf{x}|\mathbf{z})\):
The reparameterization trick: \(\mathbf{z} = \boldsymbol{\mu}_\phi + \boldsymbol{\sigma}_\phi \odot \boldsymbol{\varepsilon}\), \(\boldsymbol{\varepsilon}\sim\mathcal{N}(0,I)\), enables gradient flow through sampling.
Important
The ELBO structure directly parallels the training objective of quantum Boltzmann machines and quantum VAEs. Replacing the classical Gaussian latent with a quantum state produces the quantum generative models studied in Chapter 14.
5.3 Graph Neural Networks¶
5.3.1 Message Passing Neural Networks¶
A graph \(G=(V,E)\) with node features \(\mathbf{h}_v^{(0)}=\mathbf{x}_v\). Message passing for layer \(\ell\):
After \(L\) layers, readout: \(\mathbf{h}_G = \text{READOUT}(\{\mathbf{h}_v^{(L)}\}_{v\in V})\).
GCN (Kipf & Welling, 2017): \(\mathbf{H}^{(\ell+1)} = \sigma(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\mathbf{H}^{(\ell)}\mathbf{W}^{(\ell)})\), where \(\tilde{A} = A + I\) (self-loops), \(\tilde{D}\) is diagonal degree matrix.
Note
Quantum graph neural networks replace classical message passing with quantum operations on graph states. The graph structure maps to qubit connectivity, and quantum entanglement encodes graph topology. See Chapter 19.
5.4 Reinforcement Learning¶
5.4.1 Markov Decision Processes¶
An MDP is \((\mathcal{S}, \mathcal{A}, P, R, \gamma)\):
-
States \(s\in\mathcal{S}\), Actions \(a\in\mathcal{A}\)
-
Transition \(P(s'|s,a)\), Reward \(R(s,a)\), Discount \(\gamma\in[0,1)\)
Value function: \(V^\pi(s) = \mathbb{E}_\pi\!\left[\sum_{t=0}^\infty \gamma^t R(s_t,a_t)|s_0=s\right]\). Bellman equation: \(V^\pi(s) = \sum_a\pi(a|s)\sum_{s'}P(s'|s,a)[R(s,a)+\gamma V^\pi(s')]\).
5.4.2 Policy Gradient (REINFORCE)¶
For a parameterized policy \(\pi_\theta\), the policy gradient theorem:
Algorithm: REINFORCE Algorithm
-
For each episode: collect trajectory \(\tau = (s_0,a_0,r_0,…,s_T)\) using \(\pi_\theta\)
-
Compute returns \(G_t = \sum_{k=t}^T \gamma^{k-t}r_k\)
-
Update: \(\theta \leftarrow \theta + \eta\sum_t G_t \nabla_\theta\log\pi_\theta(a_t|s_t)\)
Tip
Quantum reinforcement learning (QRL) replaces the classical policy network with a parameterized quantum circuit \(U(\boldsymbol{\theta})\). The policy gradient theorem applies directly — swap out the neural network for a PQC and use the parameter shift rule for gradients.
5.5 Dimensionality Reduction¶
5.5.1 t-SNE and UMAP¶
t-SNE (van der Maaten & Hinton, 2008) minimizes KL divergence between high-dimensional Gaussian similarities and low-dimensional Student-\(t\) similarities:
UMAP uses topological data analysis (Riemannian manifold approximation) and is faster than t-SNE for large datasets.
import numpy as np
from scipy.optimize import minimize
def rbf_kernel(X1, X2, length_scale=1.0, variance=1.0):
"""RBF kernel matrix."""
diffs = X1[:, None, :] - X2[None, :, :]
sq_dists = np.sum(diffs**2, axis=-1)
return variance * np.exp(-0.5 * sq_dists / length_scale**2)
class GaussianProcessRegressor:
def __init__(self, kernel=rbf_kernel, noise=1e-3):
self.kernel = kernel
self.noise = noise
def fit(self, X_train, y_train):
self.X_train = X_train
self.y_train = y_train
K = self.kernel(X_train, X_train)
self.K_inv = np.linalg.inv(K + self.noise * np.eye(len(X_train)))
self.alpha = self.K_inv @ y_train
def predict(self, X_test, return_std=True):
K_star = self.kernel(X_test, self.X_train)
mean = K_star @ self.alpha
if return_std:
K_ss = self.kernel(X_test, X_test)
cov = K_ss - K_star @ self.K_inv @ K_star.T
return mean, np.sqrt(np.diag(cov))
return mean
# Usage
X_train = np.array([[0.0], [1.0], [2.0]])
y_train = np.array([1.0, 0.5, 0.0])
gp = GaussianProcessRegressor()
gp.fit(X_train, y_train)
X_test = np.linspace(-0.5, 2.5, 50).reshape(-1, 1)
mu, sigma = gp.predict(X_test)
print(f"Prediction at x=1.5: {gp.predict(np.array([[1.5]]))[0][0]:.3f}")
5.6 Chapter Summary¶
Chapter Summary
-
Gaussian Processes: Bayesian non-parametric regression via kernel matrices. GP prediction requires \(O(N^3)\) – quantum speedup via quantum kernels.
-
Variational inference: ELBO framework for approximate Bayesian inference. Foundation for VAEs and quantum Boltzmann machines.
-
GNNs: Message passing over graph topology – quantum analogue uses quantum entanglement to encode graph structure.
-
Reinforcement learning: Policy gradient theorem applies to quantum policies via parameter shift rule.
-
Dimensionality reduction: t-SNE/UMAP as classical baselines for comparing against quantum circuit-based dimensionality reduction.
Exercises
Exercise . Derive the GP posterior mean and variance in equations (5.3) and (5.4) from the joint Gaussian conditioning formula.
Exercise . Show that maximizing the ELBO is equivalent to minimizing \(D_{\text{KL}}(q_\phi(\mathbf{z})\|p(\mathbf{z}|\mathbf{x}))\).
Exercise . For the GCN update rule, show that when \(A\) is the adjacency matrix of a complete graph (\(K_n\)), the layer reduces to a global averaging plus self-loop term.
Exercise . Implement a 2-layer GCN using NumPy (no frameworks) for node classification on the Karate Club graph. Report accuracy.
Further Reading
-
Rasmussen & Williams, Gaussian Processes for Machine Learning (Rasmussen and Williams 2006) (free online)
-
Kipf & Welling (2017), Semi-supervised classification with GCNs (Kipf and Welling 2017)
-
Sutton & Barto, Reinforcement Learning: An Introduction (Sutton and Barto 2018)