Skip to content

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:

\[\mathbf{f} = [f(\mathbf{x}_1),…,f(\mathbf{x}_N)]^\top \sim \mathcal{N}(\boldsymbol{\mu}, \mathbf{K})\]

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:

\[\begin{align*} p(f_* | \mathbf{x}_*, \mathcal{D}) &= \mathcal{N}(\mu_*, \sigma_*^2) \\ \mu_* &= k_*^\top(\mathbf{K}+\sigma_n^2\mathbf{I})^{-1}\mathbf{y} \\ \sigma_*^2 &= k_{**} - k_*^\top(\mathbf{K}+\sigma_n^2\mathbf{I})^{-1}k_* \end{align*}\]

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})\):

\[\log p(\mathbf{x}) = \underbrace{\mathbb{E}_{q_\phi}\!\left[\log\frac{p(\mathbf{x},\mathbf{z})}{q_\phi(\mathbf{z})}\right]}_{\text{ELBO}(\phi)} + D_{\text{KL}}(q_\phi\|p(\mathbf{z}|\mathbf{x}))\tag{5.5}\]

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})\):

\[\mathcal{L}_{\text{VAE}} = -\mathbb{E}_{q_\phi(\mathbf{z}|\mathbf{x})}[\log p_\theta(\mathbf{x}|\mathbf{z})] + D_{\text{KL}}(q_\phi(\mathbf{z}|\mathbf{x}) \| p(\mathbf{z}))\tag{5.6}\]

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\):

\[\begin{align*} \mathbf{m}_v^{(\ell)} &= \text{AGG}\!\left(\{\text{MSG}^{(\ell)}(\mathbf{h}_v^{(\ell-1)}, \mathbf{h}_u^{(\ell-1)}, e_{uv}) : u\in\mathcal{N}(v)\}\right) \\ \mathbf{h}_v^{(\ell)} &= \text{UPDATE}^{(\ell)}(\mathbf{h}_v^{(\ell-1)}, \mathbf{m}_v^{(\ell)}) \end{align*}\]

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:

\[\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta}\!\left[\nabla_\theta\log\pi_\theta(a|s)\cdot Q^{\pi_\theta}(s,a)\right]\tag{5.9}\]

Algorithm: REINFORCE Algorithm

  1. For each episode: collect trajectory \(\tau = (s_0,a_0,r_0,…,s_T)\) using \(\pi_\theta\)

  2. Compute returns \(G_t = \sum_{k=t}^T \gamma^{k-t}r_k\)

  3. 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:

\[\mathcal{L}_{\text{t-SNE}} = \sum_{i\neq j} p_{ij}\log\frac{p_{ij}}{q_{ij}}\tag{5.10}\]

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