Interactive companion · Chapter 11 · Supervised learning

Supervised Learning Lab

Supervised learning imitates labeled examples. With graphs, attention and pointers, it can classify nodes, trace a convex hull, or score the roads of a traveling salesman’s tour.

∇ Neural networks  H W GCN α Attention → Pointer networks TSP Graph ML

Based on Chapter 11, “Supervised and unsupervised learning,” Sections 11.2, 11.3, 11.6, 11.7 and 11.9, in Alaa Khamis, Optimization Algorithms: AI techniques for design, planning, and control problems, Manning Publications, 2024 (ISBN 978-1633438835).

A graph convolutional network labeling the members of a karate club from 4 known labels.

Part 1 · Section 11.2

Supervised learning

Supervised learning maps data to known labels: classification predicts classes, regression continuous values.

Section 11.2 of the book frames one predictive-maintenance dataset as classification, regression and forecasting, and introduces geometric deep learning.

Part 2 · Neural networks

Training a neural network

Training is optimization: backpropagation computes the gradient of the loss and Adam moves the weights downhill. Press Train and watch the decision boundary and loss curve.

Neural network playground

class 0class 1ringed: test points
Part 3 · Section 11.3

Machine learning with graphs

Graphs capture relationships, and tabular data becomes a graph once you choose the nodes and edges. The panel shows Listing 11.1: soccer players linked to their clubs and nationalities.

Section 11.3 of the book explains why graph data is non-Euclidean and compares graph-embedding methods.

Listing 11.1 as a graph

playerclubnationality

Message passing and graph convolution

In a graph convolutional network, each layer lets every node aggregate messages from its neighbors, H(t+1) = σ(Â H(t) W(t)). Click a node to put a signal there, then apply layers to watch it spread hop by hop.

Figures 11.6 and 11.7 in the book build the normalized matrix  step by step.

Signal spreading through Â

Node classification with a GCN

A two-layer GCN learns which side of a split karate club each member joined from just 4 labeled members. Press Train.

Listing 11.2 in the book applies the same recipe to the Cora citation network, with the full training setup.

Semi-supervised node classification

Squares: the 4 labeled members

Part 4 · Section 11.3.2

Attention

Attention lets a model decide how much each input matters: a graph attention network scores each neighbor and normalizes the scores with a softmax. Switch between GAT and GCN or change the heads; below, click a word to see what it attends to.

Section 11.3.2 of the book derives equations 11.1 and 11.2, explains multi-head attention (Figure 11.10), and links GAT to the Transformer.

Node 5 attends to nodes 2, 4 and itself (Figure 11.9)

Which words does “bank” attend to?

Illustrative 2D word vectors, not a trained model

Part 5 · Sections 11.3.3 and 11.9

Pointer networks and the convex hull

When the outputs are positions in the input, a pointer network uses attention as a pointer, picking one input element per step. Click Next pointer to build the convex hull of the points one vertex at a time.

Sections 11.3.3 and 11.9 of the book give equations 11.3 to 11.5 and train a ConvexNet (Listing 11.6).

Decoding a hull, one pointer at a time

Pointer scores here come from geometry, not a trained network

Part 6 · Section 11.7

Solving the TSP with supervised graph ML

A graph network scores each edge’s chance of being in the optimal tour; a search step decodes a tour. Here the probabilities are a simple stand-in; set the beam width (1 is greedy) and press Decode.

Section 11.7 of the book walks through the five-step pipeline of Figure 11.16, and Listing 11.4 runs a pretrained model on TSP20 to TSP50.

Edge probabilities to a tour

Edge darkness: probability
edge probabilitiesdecoded touroptimal tour (dashed)
Part 7 · Section 11.6

Amortized optimization: learning to optimize

A model can learn to map a problem’s parameters straight to its solution, so the training cost is amortized over many problems. Train on 64 random problems on the circle, then test on unseen ones.

Listing 11.3 in the book does this on the sphere with c-convex functions, using the objective itself as the training loss.

Predicting minimizers on the circle

Part 8 · Code

Python in Google Colab

Open the book’s notebooks or the companion notebook with the from-scratch code below in Colab.

Notebooks

All examplesSupervised Learning Lab companion notebookThe from-scratch code below, ready to run Chapter 11Listing 11.1Tabular data to a graph Chapter 11Listing 11.2Node embedding with a GCN (Cora) Chapter 11Listing 11.3Amortized optimization on the sphere Chapter 11Listing 11.4TSP with a pretrained GNN Chapter 11Listing 11.6Convex hull with a pointer network

From-scratch implementations

Open all in Colab
# A multilayer perceptron trained by backpropagation and gradient descent (supervised classification)
import numpy as np

rng = np.random.default_rng(0)
t = rng.uniform(0, np.pi, 200)
X = np.vstack([np.c_[np.cos(t), np.sin(t)], np.c_[1 - np.cos(t), 0.5 - np.sin(t)]]) + 0.1 * rng.standard_normal((400, 2))
y = np.repeat([0, 1], 200)
idx = rng.permutation(400); train, test = idx[:300], idx[300:]

H = 16
W1, b1 = rng.normal(0, 1, (2, H)), np.zeros(H)
W2, b2 = rng.normal(0, 1 / np.sqrt(H), (H, 1)), np.zeros(1)
sigmoid = lambda z: 1 / (1 + np.exp(-z))
lr = 0.5


def forward(X):
    h = np.tanh(X @ W1 + b1)
    return h, sigmoid(h @ W2 + b2).ravel()


for epoch in range(2001):
    h, p = forward(X[train])
    loss = -np.mean(y[train] * np.log(p + 1e-12) + (1 - y[train]) * np.log(1 - p + 1e-12))   # cross-entropy
    dz = (p - y[train])[:, None] / len(train)          # gradient of the loss at the output
    dW2, db2 = h.T @ dz, dz.sum(0)
    dh = dz @ W2.T * (1 - h ** 2)                       # backpropagate through tanh
    dW1, db1 = X[train].T @ dh, dh.sum(0)
    W1 -= lr * dW1; b1 -= lr * db1; W2 -= lr * dW2; b2 -= lr * db2
    if epoch % 500 == 0:
        acc = lambda s: np.mean((forward(X[s])[1] > 0.5) == y[s])
        print(f"epoch {epoch:4d}: loss {loss:.3f}, train accuracy {acc(train):.1%}, test accuracy {acc(test):.1%}")

relu = lambda z: np.maximum(0, z)
leaky = lambda z, a=0.2: np.where(z > 0, z, a * z)
print("ReLU(-2), ReLU(3):", relu(-2.0), relu(3.0), "  LeakyReLU(-2), LeakyReLU(3):", leaky(-2.0), leaky(3.0))
Part 9 · Summary

What to remember

Training is optimization

Backpropagation plus a gradient method fits the weights.

Graphs

GCNs pass messages; k layers see k hops.

Attention and pointers

Pointer networks use attention to output input positions.

Learned optimizers

Training time buys fast solutions to new instances.

References: T. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” 2017. P. Veličković et al., “Graph attention networks,” 2018. A. Vaswani et al., “Attention is all you need,” 2017. O. Vinyals, M. Fortunato and N. Jaitly, “Pointer networks,” 2015. C. K. Joshi, T. Laurent and X. Bresson, “An efficient graph convolutional network technique for the travelling salesman problem,” 2019. B. Amos, “Tutorial on amortized optimization,” 2023. W. Zachary, “An information flow model for conflict and fission in small groups,” 1977. A. Khamis, Optimization Algorithms: AI techniques for design, planning, and control problems, Manning, 2024, Chapter 11.

Part 10 · Quiz

Check your understanding

Two quick questions on Chapter 11. Pick an answer to check it.

Q1. After k layers of a graph convolutional network, what information does a node’s embedding encode?

Q2. Why is a pointer network, rather than a standard sequence-to-sequence model, a natural fit for the convex hull problem?

For more exercises with full solutions, see Appendix C, “Exercises and solutions,” in Optimization Algorithms. The coding solutions are also on GitHub (Chapter 11).