Implementations: Real Machine Learning Schemes (part 2: 6.3–6.4)
Open in the Padhaiko app6.3 Extending Linear Models: Support Vector Machines (SVM), Multilayer Perceptrons (Neural Nets)
A basic Perceptron finds any separating hyperplane for linearly separable data and fails completely on non-linearly separable problems like XOR. Support Vector Machines (SVMs) and Multilayer Perceptrons (MLPs) overcome both limitations.
1. Support Vector Machines (SVM)
Given linearly separable training pairs with , infinitely many hyperplanes separate the two classes. An SVM selects the unique Maximum-Margin Hyperplane (MMH)—the boundary farthest from the nearest instances of both classes.
Support Vectors and Maximum Margin
- Support Vectors: The training instances closest to the separating hyperplane, lying directly on the margin boundaries . Removing non-support vectors does not change the learned boundary at all.
- Geometric Margin: The perpendicular distance between the two canonical margin planes and is . Maximizing margin equals minimizing subject to for all .
Soft Margin and the Kernel Trick
- Soft Margin (Non-Separable / Noisy Data): Allow controlled margin violations using slack variables :
Here trades off margin width (small wider margin, tolerates outliers) against training errors (large strict fit, risk of overfitting).
- Kernel Trick (Nonlinear Decision Boundaries): Map inputs via a nonlinear transformation into a higher-dimensional space where classes become linearly separable. Solving the Lagrangian dual expresses the classifier purely via inner products , avoiding explicit high-dimensional coordinates:
- Polynomial Kernel:
- Radial Basis Function (RBF / Gaussian) Kernel: The final decision function depends only on the support vectors ():
2. Multilayer Perceptrons (Neural Networks)
A Multilayer Perceptron (MLP) stacks an input layer, one or more hidden layers with nonlinear activation functions, and an output layer. Because hidden units apply nonlinear activations (such as sigmoid , , or ), even a single hidden layer can learn arbitrary nonlinear decision boundaries—including XOR.
Backpropagation Learning Algorithm
Backpropagation trains an MLP via gradient descent (chain rule) in two passes per training batch or instance:
- Forward Pass: Compute weighted sums and activations layer-by-layer from inputs to the output prediction , then evaluate squared error (or cross-entropy loss).
- Backward Pass (Error Propagation): Using sigmoid :
- For an output unit (with squared error): .
- For a hidden unit connected forward to units : .
- Weight Update: With learning rate (and optional momentum or weight decay to prevent overfitting):
| Aspect | Support Vector Machine (SVM) | Multilayer Perceptron (MLP) |
|---|---|---|
| Optimization Objective | Convex quadratic program (unique global optimum) | Non-convex loss landscape (risk of local minima) |
| Nonlinear Mapping | Implicit via kernel functions | Explicit learned representations across hidden layers |
| Sparsity / Parameters | Depends only on support vectors () | Dense weight matrices across all layers |
| Hyperparameters | Penalty , kernel choice and or degree | Architecture (layers, widths), , epochs, regularization |
6.4 Advanced Clustering: Hierarchical clustering, incremental clustering (Cobweb)
Unlike -means, which requires choosing in advance and produces a flat partition, hierarchical and incremental conceptual clustering build multi-level cluster trees.
1. Hierarchical Clustering
Hierarchical clustering constructs a nested tree of clusters called a dendrogram:
- Agglomerative (Bottom-Up): Start with singleton clusters (each point is its own cluster) and repeatedly merge the two closest clusters until one root cluster remains.
- Divisive (Top-Down): Start with all points in one cluster and recursively split until singletons remain.
The key design choice in agglomerative clustering is how inter-cluster distance is defined:
| Linkage Method | Distance Definition | Cluster Shape & Behavior |
|---|---|---|
| Single Linkage (MIN) | Captures non-elliptical elongated shapes; vulnerable to the chaining effect via noisy bridge points | |
| Complete Linkage (MAX) | Produces tight, compact spherical clusters; sensitive to outliers | |
| Average Linkage (UPGMA) | Balanced compromise between single and complete linkage | |
| Centroid / Ward's Method | Distance between centroids (or merge SSE increase) | Ward's minimizes within-cluster variance increase; closely parallels -means |
2. Incremental Clustering (Cobweb)
Cobweb (Fisher, ) performs incremental conceptual clustering: instances arrive one at a time in a stream, and Cobweb updates a hierarchical classification tree dynamically without re-reading old instances from scratch. Each node in the tree stores probabilistic attribute-value counts summarizing the instances beneath it.
Category Utility (CU)
Cobweb guides tree structure using Category Utility, which measures how much a partition improves the expected number of attribute values that can be predicted correctly compared to having no clusters:
Dividing by penalizes creating trivially small singleton clusters for every instance. (For numeric attributes, Cobweb's extension Classit replaces with , bounded below by an acuity parameter , plus a cutoff threshold to ignore overly fine splits.)
Four Cobweb Tree-Update Operators
When a new instance arrives at a tree node, Cobweb evaluates Category Utility for four candidate actions and picks the highest-CU choice:
- Incorporate: Place the instance into the single best-matching existing child cluster and recurse down that branch.
- Create New Disjunct: Add the instance as a brand-new singleton child cluster.
- Merge: Combine the two best-matching child clusters under a new intermediate parent and place the new instance there.
- Split: Replace the single best child cluster by promoting its own children up one level, then re-evaluate placement.
Worked Examples
SVM Margin Width and Kernel Decision Evaluation
- A hard-margin linear SVM learns the separating hyperplane (where the canonical margin planes are ). Compute the total margin width and classify the point .
- A kernelized SVM uses the degree- polynomial kernel and retains two support vectors:
- , ,
- , , with bias . Compute the decision score and predicted class for .
Part 1 — Computing total margin width and classifying : Here , so :
Evaluating the hyperplane at :
Part 2 — Computing kernel values at :
Evaluating the dual SVM decision function:
Since , the predicted class is .
- Total margin width ; lies right on the boundary ().
- predicted class .
Single Forward and Backward Pass in a Sigmoid MLP
Consider a single sigmoid neuron with input , current weight , bias , target , and learning rate .
- Perform the forward pass to compute , output , and squared error .
- Perform the backward pass to compute and update weight and bias .
Forward pass:
Backward pass (output delta ): Using the sigmoid derivative :
Updating weight and bias ():
Both and increase slightly, pushing future closer to target .
- Forward pass: , , .
- Backward pass: , , .
Single, Complete, and Average Linkage on a 1D Distance Matrix
Suppose four points are , so after the first two merges we have two clusters and . Compute the inter-cluster distance under:
- Single linkage (MIN)
- Complete linkage (MAX)
- Average linkage (UPGMA)
Listing all pairwise distances between and :
Applying the three linkage formulas:
- Single linkage: .
- Complete linkage: .
- Average linkage: .
, , and .
Exercises
Practice Exercises — SVM, Neural Nets, Hierarchical & Cobweb
What are support vectors, and why does maximizing the margin improve generalization? Given a hyperplane with margin planes at , compute its geometric margin width.
Support Vectors and Margin Generalization: Support vectors are the training instances lying closest to the decision boundary (on the canonical margin planes ). Maximizing the margin creates the widest possible buffer zone between classes, reducing sensitivity to small measurement perturbations in unseen test instances and lowering classifier capacity (VC complexity).
Computing the Geometric Margin Width: Here , so :
Support vectors are the closest boundary points defining the margin planes; wider margins reduce overfitting to noise. For , margin width .
Explain the kernel trick in SVMs and why the soft-margin parameter controls the bias–variance tradeoff. Compute the RBF kernel value for , , and .
Kernel Trick and Parameter : The kernel trick replaces explicit high-dimensional feature mappings with a cheap kernel function evaluated in the original input space, enabling nonlinear boundaries without materializing huge feature vectors. Small allows slack violations for a wide, smooth margin (higher bias, lower variance); very large heavily penalizes every training error (low bias, higher risk of overfitting noisy points).
Evaluating the RBF Kernel:
The kernel trick computes high-dimensional dot products directly via ; trades margin width against training error penalty. Here .
Explain why a single-layer Perceptron cannot learn the XOR function, how a Multilayer Perceptron (MLP) solves it, and outline the forward and backward passes of backpropagation.
Why Single-Layer Perceptrons Fail on XOR: In , XOR outputs at and and (or ) at and . No single straight line can place and on one side and and on the other, so XOR is not linearly separable.
How an MLP Solves XOR and Backpropagation Steps: Adding a hidden layer with nonlinear activations (e.g., sigmoid or ReLU) lets hidden neurons learn two linear boundaries (such as OR and NAND), which an output neuron then linearly combines (AND) to compute XOR. Backpropagation trains the weights by:
- Forward pass: propagate inputs through hidden layers to output and compute loss.
- Backward pass: apply the chain rule from output to earlier layers to compute error gradients .
- Update: adjust each weight opposite the error gradient.
XOR is not linearly separable, so a single hyperplane fails. An MLP combines nonlinear hidden units (e.g., OR and NAND) into a separable representation, trained via backpropagation's forward activation pass, backward chain-rule pass, and gradient weight updates.
Compare Single Linkage, Complete Linkage, and Average Linkage in agglomerative hierarchical clustering, and explain the chaining effect.
Comparing Linkage Criteria:
- Single Linkage (MIN): Distance between two clusters equals their closest pair of points. Can discover non-spherical, elongated clusters, but suffers from the chaining effect—a narrow bridge of noisy points can merge two distinct clusters prematurely into one long chain.
- Complete Linkage (MAX): Distance equals the farthest pair of points across the two clusters. Resists chaining and builds compact spherical clusters, though outliers can distort merges.
- Average Linkage: Distance equals the mean of all cross-cluster pairwise distances, moderating both chaining and extreme sensitivity to single outliers.
Single linkage uses minimum pairwise distance (prone to the chaining effect across noisy bridges), complete linkage uses maximum distance (compact clusters, outlier-sensitive), and average linkage averages all cross-cluster distances as a balanced compromise.
Explain the purpose of Category Utility (CU) and the four tree-update operators (incorporate, new disjunct, merge, split) in Cobweb. Suppose a dataset has one binary attribute with base proportions , and a -cluster partition splits instances equally () with and . Compute .
Category Utility and Cobweb Operators: Category Utility measures the expected increase in correct attribute-value predictions gained by knowing an instance's cluster, divided by to discourage trivial singleton clusters. As each instance arrives, Cobweb tests four local operators—incorporate into best child, create a new singleton disjunct, merge the two best children, or split the best child—and keeps whichever yields the highest CU, thereby countering order sensitivity incrementally.
Computing : Base sum: . In : . Gain . In : . Gain .
Category Utility balances within-cluster predictability against cluster count , while incorporate/new-disjunct/merge/split update the tree incrementally without order lock-in. Here .