Overview

11 Supervised and Unsupervised Learning

This chapter surveys how machine learning—positioned within the broader field of artificial intelligence—has moved from research labs into everyday products, and frames the chapter’s central theme: using supervised and unsupervised learning to solve optimization problems. It refreshes key ML concepts and motivations (learning as error minimization, search restriction, and reward optimization), outlines major schools of thought, and highlights why abundant data and compute have propelled deep learning. A practical taxonomy distinguishes supervised, unsupervised, hybrid, and reinforcement learning (deferred to the next chapter), while emphasizing deep learning’s strength in end-to-end representation learning across modalities, reducing manual feature engineering.

The chapter then builds technical foundations needed for optimization use cases. It introduces graph-structured data and geometric deep learning, showing why many real systems are naturally graphs and how tabular data can be recast as nodes and edges. It contrasts Euclidean and non-Euclidean data, explains graph embeddings (transductive vs. inductive), and details Graph Neural Networks—especially Graph Convolutional Networks with message passing for node, edge, and graph prediction. Attention mechanisms refine neighborhood aggregation, yielding Graph Attention Networks with multi‑head attention. The chapter also covers Pointer Networks, which use attention as a pointer to produce variable-length, input-indexed outputs—crucial for combinatorial tasks—and explains Self‑Organizing Maps, whose competitive, neighborhood-based learning preserves topology for clustering and dimensionality reduction.

With these tools, the chapter demonstrates three ways ML supports combinatorial optimization: end-to-end prediction of solutions, learning to configure classical algorithms, and repeatedly consulting learned policies inside search. Worked examples include amortized (supervised) optimization over spheres for fast approximate solvers; a supervised graph-learning pipeline for TSP that embeds instances, predicts solution probabilities, and guides graph search; an unsupervised SOM approach to TSP that improves via parameter tuning; and a Pointer Network that learns convex hulls by selecting input indices in sequence. Collectively, these cases show how supervised and unsupervised methods can approximate or accelerate hard optimization tasks, trading one‑time training cost for rapid inference while leveraging structure (graphs, attention, topology) to generalize across instances.

Different schools of thought of machine learning as per the Master Algorithm [3]
Machine learning taxonomy as a subfield of AI
Graph-structured data of 10 selected soccer players.
Graph embedding
Graph embedding and node/link/graph classification
Message passing and update in GCN
Embedding function in GCN.
Node embedding using GCN in PyG
a) Graph Convolutional Network (GCN) versus Graph Attention Network (GAT)
Multi-head attention with H = 3 heads by node 5. 𝛼52, 𝛼54, 𝛼55 are the attention coefficients between the nodes. The aggregated features from each head are averaged to obtain the final embedding of the node.
Convex Hull. a) Valid convex hull that enclosed all points while maximizing the area and minimizing the circumference. Note that the number of points included in the output sequence of the polygon may be smaller than the number of given points. b) Invalid convex hull as the circumference is not minimized. c) Invalid convex hull as not all the points are enclosed.
Pointer Network (Prt-Net) estimating output sequence [1 4 2] from input data points [1 2 3 4].
Equation 11.1
Equation 11.2
Equation 11.3
Self-Organizing Map (SOM) with Gaussian neighborhood function
Equation 11.4
Machine learning (ML) for combinatorial optimization (CO) problems
Equation 11.5
Example of outputs of the trained amortized model
End-to-end pipeline for combinatorial optimization problems
TSP50 solution using pretrained machine learning model.
Route length per iteration of SOM for Qatar TSP. Final route length is 9,816. Optimal solution is 9,352.
Solving convex hull problem using Pointer Network. The output in each step is just a pointer to the input that maximizes the probability distribution.
Conex hulls generated by Scipy and Ptr-Net for 50 points

Summary

  • Machine learning (ML), a branch of artificial intelligence (AI), grants an artificial system/process the capacity to learn from experiences and observations, rather than through explicit programming.
  • Deep learning (DL) is a subset of machine learning that is focused on the detection of inherent features within data by employing deep neural networks. This allows artificial systems to form intricate concepts from simpler ones.
  • Geometric deep learning (GDL) extends (structured) deep neural models to handle non-Euclidean data with underlying geometric structures, such as graphs, point clouds, molecules, and manifolds.
  • Graph Machine Learning (GML) is a subfield of machine learning that focuses on developing algorithms and models capable of learning from graph-structured data.
  • Graph embedding represents the process aimed at creating a conversion from the discrete, high-dimensional graph domain into a lower-dimensional continuous domain.
  • The attention mechanism allows the model to selectively focus on certain portions of the input data while it is in the process of generating the output sequence.
  • Pointer Network (Ptr-Net) is a variation of the sequence-to-sequence model with attention designed to deal with variable-sized input data sequences.
  • A Self-Organizing Map (SOM), also known as Kohonen map, is a type of artificial neural network (ANN) used for unsupervised learning. SOMs differ from other types of artificial neural networks as they apply competitive learning rather than error-correction learning (such as backpropagation with gradient descent).
  • Neural Combinatorial Optimization refers to the application of machine learning to solve combinatorial optimization problems.
  • Harnessing machine learning for combinatorial optimization can be achieved through three main methods: end-to-end learning where the model directly formulates solutions, using machine learning to configure and improve optimization algorithms, and integrating machine learning with optimization algorithms where the model continuously guides the optimization algorithm based on its current state.

FAQ

How do AI, Machine Learning, and Deep Learning relate, and what learning paradigms does this chapter cover?AI is the broad field of building intelligent systems. Machine Learning (ML) is a subfield of AI focused on learning from data and experience instead of explicit programming. Deep Learning (DL) is a subset of ML that uses deep neural networks to learn hierarchical representations directly from raw data (text, audio, images, video, graphs). The chapter reviews: - Supervised learning: learn mappings from inputs to known labels (e.g., traffic sign classification). - Unsupervised learning: discover structure in unlabeled data (e.g., clustering, dimensionality reduction, SOMs). - Hybrid learning: semi/self-supervised and multiple instance learning. - Reinforcement learning: learn to act via trial-and-error to maximize reward (covered in the next chapter).
What is the difference between Euclidean and non-Euclidean (graph) data, and why does it matter?Euclidean data (e.g., images, audio, text sequences) has regular structure, spatial/temporal locality, and shift invariance, which makes models like CNNs and RNNs effective. Non-Euclidean graph data has arbitrary topology, permutation invariance, and neighborhood-defined “distance” via edges. This changes the modeling toolkit: - Euclidean: CNNs, RNNs/LSTMs. - Graphs: GNNs/GCNs/GATs, spatiotemporal GNNs. The distinction affects how features are aggregated, what invariances are respected, and how models scale to massive, irregular networks.
Why are graphs central to machine learning for optimization, and how can tabular data be turned into a graph?Graphs capture entities and their relationships naturally (nodes/edges), which is crucial in optimization where constraints and interactions drive solutions. Examples include road networks (routing/ETA), social and recommender networks, web graphs, knowledge graphs, and molecules. To convert tabular data: choose entities as nodes and relationships as edges. For example, in a soccer dataset, create nodes for players, clubs, and nationalities; add edges “plays_for” (player→club) and “belongs_to” (player→nationality).
What is graph embedding and what’s the difference between transductive and inductive methods?Graph embedding maps nodes/edges/subgraphs into low-dimensional vectors that preserve structure and attributes, enabling tasks like node classification, link prediction, and community detection. - Transductive (shallow) methods (e.g., DeepWalk, node2vec, matrix factorization) learn embeddings only for nodes seen at train time; they don’t generalize to new nodes. - Inductive methods (e.g., GNNs/GCNs) learn a function that aggregates features from a node’s neighborhood, allowing generalization to unseen nodes/graphs—suitable for evolving networks.
How does a Graph Convolutional Network (GCN) work?GCNs implement message passing: each node aggregates transformed features from its neighbors (and itself), layer by layer. After k layers, a node’s embedding encodes its k-hop neighborhood context. With learned weights and non-linearities: - Node-level tasks: classify nodes from their embeddings. - Edge-level tasks: predict links by comparing node embeddings (e.g., dot product + sigmoid). - Graph-level tasks: aggregate node embeddings (sum/mean/max) into a permutation-invariant graph vector for classification/regression.
What problem does attention solve, and how do Graph Attention Networks (GATs) differ from GCNs?Attention lets models focus on the most relevant parts of the input, addressing long-range dependencies and varying importance (e.g., in Transformers: “Attention Is All You Need”). In graphs, GATs learn attention coefficients for each neighbor so a node can weight neighbors differently; multi-head attention captures diverse relation patterns. In contrast, standard GCNs apply the same learned transformation to all neighbors without explicit importance weighting.
What are Pointer Networks and how do they tackle combinatorial problems like the convex hull or TSP?Pointer Networks (Ptr-Net) are seq2seq models that use attention as a pointer to select indices from the input as outputs. This handles variable-sized outputs and permutations. Architecture: - Encoder: produces context-aware embeddings of inputs (points/cities). - Decoder + attention: at each step points to the next input element (e.g., the next hull vertex). They’ve been used to learn convex hull vertex orderings and to imitate or explore TSP tours.
What is a Self-Organizing Map (SOM) and how can it be used for the Traveling Salesman Problem?SOM is an unsupervised, competitive-learning neural map that preserves topology. For each input, the best matching unit (BMU) and its neighbors (via a Gaussian neighborhood function) update their weights; learning rate and neighborhood radius decay over time. For TSP, a ring of neurons is trained to “wrap around” the cities; the induced order yields a tour. Performance depends on hyperparameters (number of neurons, learning rate, neighborhood/radius, iterations).
In what ways can machine learning be combined with combinatorial optimization?Three complementary modes: - End-to-end learning: predict solutions directly from instances (e.g., Ptr-Net, supervised imitation of optimal solvers or RL with policy gradients). - Learning to configure algorithms: predict or adapt solver hyperparameters (e.g., cooling schedules in simulated annealing, crossover/mutation in GAs, pheromone parameters in ACO). - ML in-the-loop: repeatedly query a learned model during search (e.g., deep learning–assisted tree search that guides branching/bounding). Competitions like NeurIPS ML4CO catalyze advances in these approaches.
What is amortized optimization and when is it useful?Amortized optimization learns a fast predictor that maps problem parameters to near-optimal solutions, spreading (amortizing) the one-time training cost across many queries. Example: learn to output the optimizer (point on the sphere) of a family of functions defined on the 2-sphere. Benefits: - Millisecond inference for repeated, similar problems. - Useful when optimal solutions are costly to compute but abundant training instances exist.

pro $24.99 per month

  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose one free eBook per month to keep
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime

lite $19.99 per month

  • access to all Manning books, including MEAPs!

team

5, 10 or 20 seats+ for your team - learn more

choose your plan

pro

monthly
annual
$24.99
$249.99
only $20.83 per month
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Optimization Algorithms ebook for free

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Optimization Algorithms ebook for free
choose your plan

pro

monthly
annual
$24.99
$249.99
only $20.83 per month
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Optimization Algorithms ebook for free

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Optimization Algorithms ebook for free
choose your plan

pro

monthly
annual
$24.99
$249.99
only $20.83 per month
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Optimization Algorithms ebook for free

team

monthly
annual
$49.99
$499.99
only $41.67 per month
  • five seats for your team
  • access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
  • choose another free product every time you renew
  • choose twelve free products per year
  • exclusive 50% discount on all purchases
  • renews monthly, pause or cancel renewal anytime
  • renews annually, pause or cancel renewal anytime
  • Optimization Algorithms ebook for free