PadhaikoAll subjects

Implementations: Real Machine Learning Schemes (part 2: 6.3–6.4)

Data Mining (ENCT 435)

Open in the Padhaiko app

6.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.

Definition

Support Vectors and Maximum Margin

Soft Margin and the Kernel Trick

  1. 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).

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

  1. Forward Pass: Compute weighted sums and activations layer-by-layer from inputs to the output prediction , then evaluate squared error (or cross-entropy loss).
  2. Backward Pass (Error Propagation): Using sigmoid :
    • For an output unit (with squared error): .
    • For a hidden unit connected forward to units : .
  3. Weight Update: With learning rate (and optional momentum or weight decay to prevent overfitting):
AspectSupport Vector Machine (SVM)Multilayer Perceptron (MLP)
Optimization ObjectiveConvex quadratic program (unique global optimum)Non-convex loss landscape (risk of local minima)
Nonlinear MappingImplicit via kernel functions Explicit learned representations across hidden layers
Sparsity / ParametersDepends only on support vectors ()Dense weight matrices across all layers
HyperparametersPenalty , 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:

The key design choice in agglomerative clustering is how inter-cluster distance is defined:

Agglomerative Hierarchical Linkage Criteria
Linkage MethodDistance 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 MethodDistance 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:

  1. Incorporate: Place the instance into the single best-matching existing child cluster and recurse down that branch.
  2. Create New Disjunct: Add the instance as a brand-new singleton child cluster.
  3. Merge: Combine the two best-matching child clusters under a new intermediate parent and place the new instance there.
  4. Split: Replace the single best child cluster by promoting its own children up one level, then re-evaluate placement.

Worked Examples

Example 1

SVM Margin Width and Kernel Decision Evaluation (6 marks)

  1. A hard-margin linear SVM learns the separating hyperplane (where the canonical margin planes are ). Compute the total margin width and classify the point .
  2. 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 .

Answer:
  1. Total margin width ; lies right on the boundary ().
  2. predicted class .
Example 2

Single Forward and Backward Pass in a Sigmoid MLP (6 marks)

Consider a single sigmoid neuron with input , current weight , bias , target , and learning rate .

  1. Perform the forward pass to compute , output , and squared error .
  2. 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 .

Answer:
  1. Forward pass: , , .
  2. Backward pass: , , .
Example 3

Single, Complete, and Average Linkage on a 1D Distance Matrix (6 marks)

Suppose four points are , so after the first two merges we have two clusters and . Compute the inter-cluster distance under:

  1. Single linkage (MIN)
  2. Complete linkage (MAX)
  3. Average linkage (UPGMA)

Listing all pairwise distances between and :

Applying the three linkage formulas:

  1. Single linkage: .
  2. Complete linkage: .
  3. Average linkage: .
Answer:

, , and .


Exercises

Practice Exercises — SVM, Neural Nets, Hierarchical & Cobweb

Question 1

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 :

Answer:

Support vectors are the closest boundary points defining the margin planes; wider margins reduce overfitting to noise. For , margin width .

Question 2

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:

Answer:

The kernel trick computes high-dimensional dot products directly via ; trades margin width against training error penalty. Here .

Question 3

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:

  1. Forward pass: propagate inputs through hidden layers to output and compute loss.
  2. Backward pass: apply the chain rule from output to earlier layers to compute error gradients .
  3. Update: adjust each weight opposite the error gradient.
Answer:

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.

Question 4

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

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.

Question 5

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 .

Answer:

Category Utility balances within-cluster predictability against cluster count , while incorporate/new-disjunct/merge/split update the tree incrementally without order lock-in. Here .

← Implementations: Real Machine Learning Schemes (part 1: 6.1–6.2)Data Transformations →