Machine Learning

Gaussian Mixture Models and Support Vector Machines

📅 Published: 2026-06-30

🎓 Level: postgraduate

👥 Audience: Postgraduate students in Machine Learning

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

K-Means Clustering — covered in Lecture 15. GMM is a direct extension of K-means into a probabilistic framework. The E-step/M-step structure carries forward directly from K-means to GMM.
Gaussian Mixture Model Preview — covered in Lecture 15. The soft vs. hard clustering distinction and the basic idea of mixture models were introduced.
Binary Classification (Logistic Regression) — covered in Lecture 7. SVM solves the same classification task but with a different principle: finding the maximum-margin separator instead of fitting a sigmoid.
Optimization Fundamentals — covered in Lectures 3–6. The SVM primal problem is a constrained quadratic optimization; familiarity with gradient-based optimization and Lagrangian multipliers from earlier lectures is assumed.

Gaussian Mixture Models and Support Vector Machines

This lecture covers two major machine learning approaches. The first half introduces Gaussian Mixture Models (GMM) — a soft clustering technique that extends K-means into a probabilistic framework. The second half introduces Support Vector Machines (SVM) — a supervised classification algorithm that finds the hyperplane with the maximum separating margin between classes. Both are foundational tools used across data science, from customer segmentation to medical diagnosis.

16.1 Context — From K-Means to Gaussian Mixture Models

What if your clusters overlap — if a data point could reasonably belong to two groups at once? K-means forces a binary yes/no answer. GMM gives a richer answer: "85% this group, 10% that group, 5% the other." This section builds the bridge from hard clustering to soft, probabilistic clustering.

16.1.1 Recap of K-Means Clustering

K-means is a clustering algorithm. It groups data objects into clusters by allocating every data object to exactly one cluster — "this point belongs to cluster one, that point belongs to cluster two." This assignment may change across iterations, but at every moment the algorithm declares a definite, exclusive cluster membership for each point.

This is called hard clustering. Each point gets a binary label: in or out. There is no middle ground.

The K-means algorithm works by minimizing a distortion measure: the sum of squared distances from each point to its assigned cluster center. It alternates between two steps: (E-step) assign each point to the nearest center, and (M-step) recompute each center as the mean of its assigned points. This two-stage iteration repeats until assignments stop changing. The same E-step/M-step language carries forward to GMM, which is why the professor introduces it: "It is exactly K-means extension. That is why we learned K-means first."

K-means objective (distortion measure):

J = n = 1 \sum N k = 1 \sum K r_{nk} ∥ x_{n} - μ_{k} ∥^{2}

where

r_{nk} \in {0, 1}

is a binary indicator — 1 if point

n

is assigned to cluster

k

, 0 otherwise.

μ_{k}

is the center (prototype) of cluster

k

. This is the standard formulation from the reference text (Bishop §9.1).

16.1.2 Why Remove Duplicates Before Clustering

Pitfall: Running clustering on data with many duplicate records biases the statistical description of the data.

If you have 100 copies of one record and 100 unique records, the mean gets pulled toward the repeated values. That one repeated record gains disproportionately large influence. The statistical description — the mean, the spread — gets warped, and from there it influences everything downstream: cluster centers, variance estimates, and ultimately the cluster assignments themselves. The professor emphasized: "The statistical description itself gets warped, and from there it influences everything downstream."

16.1.3 Introducing Gaussian Mixture Models (GMM)

A Gaussian Mixture Model (GMM) is a probabilistic model for clustering. Unlike K-means, which groups points by distance, GMM assumes that all data points are generated from a mixture of several Gaussian (bell-curve) distributions with unknown parameters.

The professor's central analogy is reverse engineering:

"If I had to recreate this exact dataset using a few bell curves, where would I place those bell curves? How wide would they be?"

If you try to draw a single Gaussian through the entire dataset, it will not capture the underlying structure. But if the data has distinct groups, you can place one Gaussian over each group. The question GMM answers is: where should these Gaussians go, how wide should they be, and how much does each one contribute?

A Gaussian Mixture Model with

K

components has the probability density:

p (x) = k = 1 \sum K π_{k} \cdot N (x ∣ μ_{k}, Σ_{k})

where

π_{k}

is the mixing coefficient (weight) of component

k

, satisfying

\sum_{k = 1}^{K} π_{k} = 1

, and

N (x ∣ μ_{k}, Σ_{k})

is the multivariate Gaussian PDF with mean

μ_{k}

and covariance

Σ_{k}

. This is the standard formulation from Bishop §9.2.

16.1.4 Why Not a Single Gaussian?

Imagine a dataset of adult heights in a city. The data comes from two underlying distributions — men's heights (mean ~175 cm) and women's heights (mean ~162 cm). A person who is 168 cm tall could be a tall woman or an average-height man. A single Gaussian would smear both groups into one blob, losing this structure. You need two overlapping bell curves.

This height example is not just pedagogical — it is a classic real-world use of GMM: discovering latent groups (male/female) from unlabeled data without ever knowing the gender labels. GMM captures this by modeling the data as coming from multiple distributions, each with its own mean, variance, and weight.

K-means asks "which cluster?" with a binary answer. GMM asks "how much of each cluster?" with probabilities. This soft assignment is the fundamental upgrade — and it lets GMM handle overlapping, elliptical clusters that K-means cannot.

16.2 Gaussian Mixture Model — Core Concepts

Think of a dart board with two bullseyes. Some darts cluster around the first bullseye, some around the second, and a few land in between. Hard clustering forces you to assign each dart to exactly one bullseye. Soft clustering (GMM) lets you say: "This dart is 70% from player A, 30% from player B." Now imagine the dart clusters aren't even round — they're oval-shaped because one player throws with a sideways drift. GMM handles that too.

16.2.1 Hard Clustering vs. Soft Clustering

Type	Algorithm	Behavior	Analogy
Hard clustering	K-means	A point belongs to cluster A OR cluster B — definite, exclusive	A passport: you are a citizen of exactly one country
Soft clustering	GMM	A point can be 85% cluster A, 10% cluster B, 5% cluster C	A pie chart of your ancestry: you can be part Italian, part Irish

In GMM, the same data point can belong to multiple clusters with different probabilities. This is especially useful for points near the boundaries of overlapping Gaussians, where forcing a binary assignment would be arbitrary. The professor phrased it this way: "What if a point has equal probability of belonging to two clusters? It's very unlikely that probability is exactly equal, but if it happens, you decide. It doesn't matter."

16.2.2 Flexibility in Cluster Shape

K-means has one implicit assumption that severely limits it: clusters are spherical. GMM lifts this restriction.

K-means only cares about the Euclidean distance from each center. It assumes equal variance in all directions — clusters are circles (in 2D) or spheres (in higher dimensions). If you have two elongated, cigar-shaped clusters that overlap, K-means cannot identify them correctly. It will cut through them with a straight bisector and produce wrong assignments.

GMM is more flexible because it models three things per component:

Mean $μ_{k}$ — the center of each Gaussian (same idea as K-means centroids).
Variance — how much a single variable spreads around the mean. Large variance = wide bell curve.
Covariance — how two variables move together. If height and weight are positively correlated (taller people tend to be heavier), the covariance captures that tilt.

The covariance matrix $Σ_{k}$ encodes both variances and covariances:

Σ_{k} = [σ_{X X}^{2} σ_{Y X} σ_{X Y} σ_{Y Y}^{2}]

Diagonal entries ( $σ_{X X}^{2}, σ_{Y Y}^{2}$ ): variance along each axis — controls spread.
Off-diagonal entries ( $σ_{X Y}, σ_{Y X}$ ): covariance between axes — controls tilt and shape.

Together, these parameters allow GMM to form elliptical clusters of arbitrary orientation, not just circles. The bell curve can be stretched, squeezed, and rotated to fit the data.

Visual intuition: Imagine looking down from above at the bell curves (the professor's "top view"). For a circular cluster, the contour lines are concentric circles — like a target. For an elliptical cluster, the contours are concentric ellipses — like a tilted stretched target. GMM can produce either shape depending on the covariance matrix.

16.2.3 The Core Idea — Data as a Mixture of Gaussians

The fundamental assumption of GMM: the dataset is an additive mixture — a weighted sum of contributions from multiple Gaussian distributions.

If the data has three distinct groups, GMM assumes three separate underlying Gaussians. The final dataset is a combination (mixture) of points drawn from these three curves. Some points come from Gaussian 1, some from Gaussian 2, some from Gaussian 3. The mixing coefficient $π_{k}$ tells you what fraction of all data points come from Gaussian $k$ .

The professor contrasted this with models that assume all data comes from a single distribution: "This is fundamentally different from models that assume all data comes from a single distribution or a single group."

Scope: GMM assumes the data is generated from a finite mixture of Gaussians. If the true data distribution is not well-approximated by a sum of bell curves — for instance, it has sharp cutoffs, exponential tails, or uniform segments — GMM may need many components to fit well. It may even be the wrong model entirely. GMM also assumes the number of components

K

is known in advance — choosing

K

is a separate problem covered in §16.6.

GMM upgrades K-means in two ways: (1) soft probabilistic assignments instead of hard binary ones, and (2) elliptical cluster shapes instead of only spherical ones. The cost: you now need to fit means, covariances, and mixing weights — more parameters, more computation, but far more expressive clusters.

16.3 The GMM Algorithm — Expectation-Maximization

How do you find the best Gaussians when you don't know which points belong to which Gaussian — and you don't know where the Gaussians are? It sounds like a chicken-and-egg problem. The EM algorithm solves it by cycling between "guess which points go where" and "recenter the Gaussians based on the guess." Each cycle improves the fit.

Purpose: The Expectation-Maximization (EM) algorithm finds the maximum-likelihood estimates of the GMM parameters (

μ_{k}, σ_{k}^{2}, π_{k}

for all

k

) when the cluster assignments are unknown (latent). It is the standard algorithm for fitting Gaussian mixture models.

Inputs & Outputs:

Input: Dataset ${x_{1}, x_{2}, \dots, x_{n}}$ of $n$ points; number of components $K$ .
Output: For each component $k$ : mean $μ_{k}$ , variance $σ_{k}^{2}$ , mixing weight $π_{k}$ . Plus soft assignments (responsibilities $r_{ik}$ ) for every point.

16.3.1 Algorithm Overview (Conceptual)

The EM algorithm for GMM alternates between two steps. The professor described them with a coloring analogy that captures the intuition perfectly:

Initialization — Start with random Gaussians. Pick values for the mean ( $μ$ ) and standard deviation ( $σ$ ) for each Gaussian you assume exists. If $K = 2$ , pick $μ_{1}, σ_{1}, μ_{2}, σ_{2}$ .
E-step (Expectation) — "Color the points." For every data point, calculate what percentage it belongs to each Gaussian. A point may be 99% blue (component 1) and 1% green (component 2). No point is ever 100% one cluster — that is the fundamental difference from K-means.
M-step (Maximization) — "Recalculate the Gaussians." Using the points now assigned (with their percentage weights), recompute the mean, variance, and mixing weight for each Gaussian. The Gaussians shift closer to the data they represent.
Repeat until convergence — when assignments stop changing between two consecutive iterations.

16.3.2 Visual Analogy — The "Coloring" Process

The professor drew concentric circles to represent each Gaussian — these are the "top view" of bell curves, as if looking down from above. The circles represent contours of equal probability density.

Initially, the Gaussians are placed randomly. Points closer to Gaussian 1 get colored mostly blue. Points closer to Gaussian 2 get colored mostly green. Points equally close get half-and-half.

After coloring, the Gaussians are recalculated — they move to better fit the points assigned to them. Then the coloring changes because the Gaussians moved. This cycle continues until stable.

"If you understood the concept, it is very easy, but if you simply try to by-heart the formula 100 percentage, you will miss one or other step. What is that coloring example? Keep in mind, we can do that. You'll be able to solve any given problem."

16.3.3 Formal Algorithm Steps

Step 1 — Initialization:

Choose the number of Gaussians $K$ . Randomly initialize parameters for each Gaussian $k = 1, 2, \dots, K$ :

Mean $μ_{k}$ (in 1D; or vector $μ_{k}$ in multivariate)
Variance $σ_{k}^{2}$ (in 1D; or covariance matrix $Σ_{k}$ in multivariate)
Mixing coefficient $π_{k} = 1/ K$ (start with equal weights)

In practice, Python libraries like scikit-learn run K-means first to get good initial centers, then use the resulting cluster means, covariances, and proportions as the starting GMM parameters.

Step 2 — E-step (Expectation): Compute responsibilities

The responsibility $r_{ik}$ is the probability that data point $i$ belongs to component $k$ :

r_{ik} = \frac{π _{k} \cdot N ( x _{i} ∣ μ _{k} , σ _{k}^{2} )}{\sum _{j = 1}^{K} π _{j} \cdot N ( x _{i} ∣ μ _{j} , σ _{j}^{2} )}

What each part means:

Numerator: $π_{k} \cdot N (x_{i} ∣ μ_{k}, σ_{k}^{2})$ — "prior weight of cluster $k$ " times "how likely point $i$ is under Gaussian $k$ ."
Denominator: sum of the same quantity over ALL clusters — normalizes so that $\sum_{k = 1}^{K} r_{ik} = 1$ for each point $i$ .
Result: For each point $i$ , you get a probability distribution over the $K$ clusters. $r_{ik} \in [0, 1]$ always.

This formula is Bayes' theorem in action: it computes the posterior probability of cluster membership given the data. In Bishop's notation (§9.2), this is $γ (z_{nk})$ , the responsibility of component $k$ for data point $n$ .

Step 3 — M-step (Maximization): Update parameters using weighted data

μ_{k}^{new} = \frac{\sum _{i = 1}^{n} r _{ik} \cdot x _{i}}{\sum _{i = 1}^{n} r _{ik}}

σ_{k}^{2, new} = \frac{\sum _{i = 1}^{n} r _{ik} \cdot ( x _{i} - μ _{k}^{new} ) ^{2}}{\sum _{i = 1}^{n} r _{ik}}

π_{k}^{new} = \frac{1}{n} i = 1 \sum n r_{ik}

Why each update makes sense:

New mean: A weighted average of all data points, where each point's contribution is weighted by $r_{ik}$ — how strongly it belongs to cluster $k$ . Points that are 95% in cluster $k$ pull the mean much harder than points that are 5% in cluster $k$ .
New variance: A weighted variance — same weighting logic. Measures the spread of points around the new mean, weighted by membership strength.
New mixing coefficient: The average responsibility across all points. If many points belong strongly to cluster $k$ , $π_{k}$ will be large; if cluster $k$ is tiny, $π_{k}$ will be small. This is exactly: total effective points in cluster $k$ divided by $n$ .

Step 4 — Convergence check:

Stop when the log-likelihood of the data stops improving significantly:

Stop when ∣ L^{(t + 1)} - L^{(t)} ∣ < ε

where $L = \sum_{i = 1}^{n} ln (\sum_{k = 1}^{K} π_{k} \cdot N (x_{i} ∣ μ_{k}, σ_{k}^{2}))$ is the log-likelihood of the observed data under the current GMM parameters, and $ε$ is a small threshold (e.g., $1 0^{- 3}$ ).

Equivalent stopping conditions: parameters change by less than $ε$ ; no point changes its most-likely cluster assignment between iterations. All three are practically telling the same thing — the model has stopped improving.

Trace on a tiny dataset:

Consider $n = 4$ points: ${0, 1, 2, 3}$ with $K = 2$ .

Initialization: $μ_{1} = 0.5, σ_{1}^{2} = 1, π_{1} = 0.5$ ; $μ_{2} = 2.5, σ_{2}^{2} = 1, π_{2} = 0.5$ .

E-step (Iteration 1): Compute $r_{i 1}, r_{i 2}$ for each point using the responsibility formula.

Point 0: close to $μ_{1} = 0.5$ , far from $μ_{2} = 2.5$ → $r_{0, 1} \approx 0.95$ , $r_{0, 2} \approx 0.05$
Point 3: close to $μ_{2} = 2.5$ , far from $μ_{1} = 0.5$ → $r_{3, 1} \approx 0.05$ , $r_{3, 2} \approx 0.95$

M-step (Iteration 1): Recompute means using weighted averages.

$μ_{1}^{new} = \frac{0.95 ( 0 ) + 0.80 ( 1 ) + 0.20 ( 2 ) + 0.05 ( 3 )}{0.95 + 0.80 + 0.20 + 0.05} \approx 0.65$ — shifted right toward its data.

$μ_{2}^{new}$ shifts left toward ${2, 3}$ . The Gaussians tighten around their respective clusters.

Convergence: In the next E-step, the cluster assignments (0,1 → C1; 2,3 → C2) do not change, so the algorithm stops after 2 iterations. The full worked example is in §16.5.

Pitfalls:

Local optima: EM is not guaranteed to find the global maximum of the likelihood. Different random initializations can lead to different final clusterings. In practice, run EM multiple times with different starting points and keep the best result (highest log-likelihood).
Singularities: If a Gaussian component collapses onto a single data point, its variance can shrink to zero and the likelihood can blow up to infinity. This is a known issue with maximum-likelihood GMM (Bishop §9.2.1). Using a small regularization on the covariance or a Bayesian approach avoids this.
Slow convergence: EM can take many iterations when clusters overlap heavily. The log-likelihood often improves rapidly in early iterations and then plateaus — don't mistake the plateau for convergence.

EM is the engine behind GMM. The E-step computes soft assignments (responsibilities). The M-step re-estimates parameters using those weighted assignments. Rinse and repeat. The professor's key insight: "Keep the coloring picture in mind and you'll be able to solve any given problem."

16.4 GMM — Mathematical Foundation

16.4.1 1D Gaussian Probability Density Function

The Gaussian (normal) probability density function (PDF) in one dimension, with mean

μ

and variance

σ^{2}

N (x ∣ μ, σ^{2}) = \frac{1}{2 π σ ^{2}} exp (- \frac{( x - μ ) ^{2}}{2 σ ^{2}})

Every symbol named:

$μ$ (mu) — the mean, the center of the bell curve. "The average height."
$σ$ (sigma) — the standard deviation, controls the spread. Larger $σ$ = wider, flatter bell.
$σ^{2}$ — the variance, the square of the standard deviation. "The spread of the heights."
$\frac{1}{2 π σ ^{2}}$ — the normalization constant. Ensures the total area under the curve equals 1.
$exp (- \frac{( x - μ ) ^{2}}{2 σ ^{2}})$ — the exponential kernel. Measures how far $x$ is from $μ$ , scaled by the variance. When $x = μ$ , this equals 1 (maximum). When $x$ is far from $μ$ , this drops toward 0.

The professor's plain-language summary: "The average height is the mean. The spread of the heights is the variance."

In 1D: the parameter is variance ( $σ^{2}$ ). In multivariate: the parameter is covariance ( $Σ$ ).

16.4.2 Multivariate Gaussian Probability Density Function

For

d

-dimensional data

x \in R^{d}

N (x ∣ μ, Σ) = \frac{1}{( 2 π ) ^{d /2} ∣ Σ ∣ ^{1/2}} exp (- \frac{1}{2} (x - μ)^{⊤} Σ^{- 1} (x - μ))

Every symbol named:

$d$ — number of dimensions (features). For 2D data like height and weight, $d = 2$ .
$x$ — a data point, a vector of length $d$ .
$μ$ — the mean vector, also length $d$ . The center in $d$ -dimensional space.
$Σ$ — the $d \times d$ covariance matrix. Replaces the scalar $σ^{2}$ from 1D. Its diagonal holds variances; off-diagonals hold covariances.
$Σ^{- 1}$ — the inverse of the covariance matrix (the precision matrix).
$∣ Σ ∣$ — the determinant of $Σ$ . A scalar measuring the "volume" of the covariance ellipsoid.
$(x - μ)^{⊤} Σ^{- 1} (x - μ)$ — the squared Mahalanobis distance. This is the multivariate generalization of $\frac{( x - μ ) ^{2}}{σ ^{2}}$ . It measures distance from $x$ to $μ$ in units of the covariance, accounting for correlations between dimensions.

Visual intuition: In 2D, $Σ$ determines the shape of equal-probability contours. When $Σ = σ^{2} I$ (scaled identity), contours are circles. When $Σ$ has different diagonal values, contours are axis-aligned ellipses. When $Σ$ has non-zero off-diagonals, contours are rotated ellipses. The Mahalanobis distance is constant along each contour.

16.4.3 The GMM Probability Density Function

The overall PDF of a GMM with

K

components is an additive mixture — a weighted sum of

K

Gaussian densities:

p (x) = k = 1 \sum K π_{k} \cdot N (x ∣ μ_{k}, Σ_{k})

For the 1D case (exam-relevant):

p (x) = k = 1 \sum K π_{k} \cdot \frac{1}{2 π σ _{k}^{2}} exp (- \frac{( x - μ _{k} ) ^{2}}{2 σ _{k}^{2}})

The mixing coefficients must satisfy:

k = 1 \sum K π_{k} = 1, π_{k} \geq 0 for all k

Why these constraints? $π_{k}$ is the prior probability that a randomly chosen data point comes from component $k$ . As probabilities, they must sum to 1 and each must be non-negative.

The professor emphasized: "This is the formula you need to remember." $p (x)$ is the probability density at position $x$ — it tells you how likely you are to find a data point at that location. $π_{k}$ represents the weight or relative size of each cluster. If cluster 1 is large (more data points), $π_{1}$ might be 0.7 and $π_{2}$ might be 0.3.

Derivation from the latent-variable viewpoint (Bishop §9.2): Each data point has an unobserved (latent) variable $z$ indicating which component generated it. $z$ uses a 1-of- $K$ encoding: $z_{k} = 1$ if point came from component $k$ , 0 otherwise. The joint distribution is $p (x, z) = p (z) p (x ∣ z)$ . Marginalizing over $z$ gives the mixture: $p (x) = \sum_{z} p (z) p (x ∣ z) = \sum_{k = 1}^{K} π_{k} N (x ∣ μ_{k}, Σ_{k})$ . This latent-variable formulation is what makes the EM algorithm possible.

16.4.4 Symbol Registry — GMM (1D)

Symbol	Meaning	Type	Domain
$K$	Number of Gaussian components (clusters)	integer	$K \geq 1$
$π_{k}$	Mixing coefficient (weight) of component $k$	scalar	$π_{k} \in [0, 1]$ , $\sum_{k} π_{k} = 1$
$μ_{k}$	Mean of Gaussian $k$	scalar	$μ_{k} \in R$
$σ_{k}^{2}$	Variance of Gaussian $k$	scalar	$σ_{k}^{2} > 0$
$r_{ik}$	Responsibility — probability point $i$ belongs to component $k$	scalar	$r_{ik} \in [0, 1]$ , $\sum_{k} r_{ik} = 1$
$n$	Number of data points	integer	$n \geq 1$
$N (x ∣ μ, σ^{2})$	Gaussian PDF evaluated at $x$	scalar	$\geq 0$

The GMM is a weighted sum of Gaussians. The mixing coefficients

π_{k}

are probabilities that sum to 1. Each component has its own

μ_{k}

and

σ_{k}^{2}

. This is the mathematical statement of "the data comes from multiple bell curves added together."

16.5 GMM — Worked Example

This is the canonical exam-style problem. Work through every calculation step. The professor stated explicitly that 1D problems are what you should expect — 2D requires too much hand computation.

16.5.1 Problem Setup

Data: Four points: $x_{1} = 0$ , $x_{2} = 1$ , $x_{3} = 2$ , $x_{4} = 3$

Goal: Fit a mixture of $K = 2$ Gaussian components. Run one full iteration of EM (E-step + M-step).

16.5.2 Step 1 — Initialization

Initial parameter guesses:

Component 1 (C1): $μ_{1} = 0.5$ (mean of ${0, 1}$ ), $σ_{1}^{2} = 1$ , $π_{1} = 0.5$
Component 2 (C2): $μ_{2} = 2.5$ (mean of ${2, 3}$ ), $σ_{2}^{2} = 1$ , $π_{2} = 0.5$

The professor noted: "It's not completely random. Python has its own ways of calculating the initial mean. Variance we assume as 1." This is akin to K-means initialization — picking sensible starting points based on domain knowledge.

16.5.3 Step 2 — E-step: Compute Responsibilities

For each point $x \in {0, 1, 2, 3}$ , compute the Gaussian likelihood under each component, then the responsibility $r_{ik}$ .

Gaussian PDF formula: $N (x ∣ μ, σ^{2}) = \frac{1}{2 π σ ^{2}} exp (- \frac{( x - μ ) ^{2}}{2 σ ^{2}})$

With $σ^{2} = 1$ : $N (x ∣ μ, 1) = \frac{1}{2 π} exp (- \frac{( x - μ ) ^{2}}{2})$

For $x = 0$ :

N (0 ∣ 0.5, 1) N (0 ∣ 2.5, 1) = \frac{1}{2 π} e^{- (0 - 0.5)^{2} /2} = \frac{1}{2.5066} \cdot e^{- 0.125} \approx 0.3521 = \frac{1}{2 π} e^{- (0 - 2.5)^{2} /2} = \frac{1}{2.5066} \cdot e^{- 3.125} \approx 0.0175

r_{0, 1} = \frac{0.5 \times 0.3521}{0.5 \times 0.3521 + 0.5 \times 0.0175} = \frac{0.1760}{0.1848} \approx 0.9526

r_{0, 2} = 1 - 0.9526 = 0.0474

For $x = 1$ :

N (1 ∣ 0.5, 1) N (1 ∣ 2.5, 1) = \frac{1}{2 π} e^{- (0.5)^{2} /2} = 0.3521 = \frac{1}{2 π} e^{- (1.5)^{2} /2} = \frac{1}{2.5066} \cdot e^{- 1.125} \approx 0.1295

r_{1, 1} = \frac{0.3521}{0.3521 + 0.1295} \approx 0.7311, r_{1, 2} \approx 0.2689

For $x = 2$ (by symmetry with $x = 1$ ):

r_{2, 1} \approx 0.2689, r_{2, 2} \approx 0.7311

For $x = 3$ (by symmetry with $x = 0$ ):

r_{3, 1} \approx 0.0474, r_{3, 2} \approx 0.9526

Summary of responsibilities (using the approximate values shown in lecture):

Point $x$	$r_{i, 1}$ (C1)	$r_{i, 2}$ (C2)	Dominant cluster
0	0.95	0.05	C1 (strong)
1	0.80	0.20	C1 (moderate-to-strong)
2	0.20	0.80	C2 (moderate-to-strong)
3	0.05	0.95	C2 (strong)

Sense check: Points 0 and 1 are closer to $μ_{1} = 0.5$ → mostly C1. Points 2 and 3 are closer to $μ_{2} = 2.5$ → mostly C2. The boundary points (1 and 2) have more mixed responsibilities than the extremes (0 and 3). The probabilities for each point sum to 1. ✓

The lecture used rounded values (0.95, 0.80, 0.20, 0.05). The precise values from the Gaussian PDF evaluation are (0.9526, 0.7311, 0.2689, 0.0474). The course slide reported

μ_{1}^{new} \approx 0.652

— this corresponds to the more precise responsibilities. Using the rounded values gives

μ_{1}^{new} \approx 0.675

. Both approaches are acceptable; the exam will test your ability to apply the formulas, not the precision of your arithmetic.

16.5.4 Step 3 — M-step: Update Parameters

Update $μ_{1}^{new}$ (weighted average):

μ_{1}^{new} = \frac{\sum _{i = 1}^{4} r _{i, 1} \cdot x _{i}}{\sum _{i = 1}^{4} r _{i, 1}}

Using the precise responsibilities:

μ_{1}^{new} = \frac{0.9526 ( 0 ) + 0.7311 ( 1 ) + 0.2689 ( 2 ) + 0.0474 ( 3 )}{0.9526 + 0.7311 + 0.2689 + 0.0474} = \frac{0 + 0.7311 + 0.5378 + 0.1422}{2.0000} = \frac{1.4111}{2.0000} = 0.7056

Using the lecture's approximate values (0.95, 0.80, 0.20, 0.05):

μ_{1}^{new} = \frac{0.95 ( 0 ) + 0.80 ( 1 ) + 0.20 ( 2 ) + 0.05 ( 3 )}{0.95 + 0.80 + 0.20 + 0.05} = \frac{1.35}{2.00} = 0.675

Update $μ_{2}^{new}$ :

By symmetry, $μ_{2}^{new} = \frac{0.0474 ( 0 ) + 0.2689 ( 1 ) + 0.7311 ( 2 ) + 0.9526 ( 3 )}{2.0} = \frac{0 + 0.2689 + 1.4622 + 2.8578}{2.0} = \frac{4.5889}{2.0} = 2.2944$

With approximate values: $μ_{2}^{new} \approx 2.325$

Update $σ_{1}^{2, new}$ (weighted variance):

σ_{1}^{2, new} = \frac{\sum _{i = 1}^{4} r _{i, 1} \cdot ( x _{i} - μ _{1}^{new} ) ^{2}}{\sum _{i = 1}^{4} r _{i, 1}}

Using $μ_{1}^{new} = 0.7056$ and precise responsibilities:

σ_{1}^{2, new} = \frac{0.9526 ( 0 - 0.7056 ) ^{2} + 0.7311 ( 1 - 0.7056 ) ^{2} + 0.2689 ( 2 - 0.7056 ) ^{2} + 0.0474 ( 3 - 0.7056 ) ^{2}}{2.0} = \frac{0.9526 ( 0.4979 ) + 0.7311 ( 0.0867 ) + 0.2689 ( 1.6755 ) + 0.0474 ( 5.2643 )}{2.0} = \frac{0.4743 + 0.0634 + 0.4505 + 0.2495}{2.0} = \frac{1.2377}{2.0} = 0.6189

The variance has shrunk from 1.0 to ~0.62 — the cluster is tightening around its data.

Update mixing coefficients:

π_{1}^{new} = \frac{1}{4} i = 1 \sum 4 r_{i, 1} = \frac{2.0}{4} = 0.5, π_{2}^{new} = 0.5

The mixing coefficients stay at 0.5 because the responsibilities are symmetric.

Parameter movement after iteration 1:

Parameter	Initial	After Iteration 1	Direction
$μ_{1}$	0.5	~0.68–0.71	→ shifted right toward its data
$μ_{2}$	2.5	~2.29–2.33	← shifted left toward its data
$σ_{1}^{2}$	1.0	~0.62	↓ tightened around cluster
$σ_{2}^{2}$	1.0	~0.62	↓ tightened around cluster
$π_{1}$	0.5	0.5	unchanged (symmetric data)
$π_{2}$	0.5	0.5	unchanged (symmetric data)

16.5.5 Step 4 — Repeat Until Convergence

The E-step and M-step are repeated. In this example, after one iteration the most-likely cluster assignments are already correct (0,1 → C1; 2,3 → C2). Running the E-step again with the updated parameters produces the same hard assignments, so the algorithm converges.

For larger datasets with more overlap, multiple iterations are needed. In general, stop when:

The log-likelihood change $∣ L^{(t + 1)} - L^{(t)} ∣ < ε$ (e.g., $1 0^{- 3}$ ), or
Parameter changes are below threshold, or
Cluster assignments stop changing.

The mixing coefficients stayed at 0.5 each for this symmetric example, but in asymmetric real datasets, $π_{k}$ values shift to reflect the relative sizes of the discovered clusters.

After one EM iteration, both Gaussian means moved toward their natural clusters (

μ_{1}

shifted right,

μ_{2}

shifted left), and both variances shrank (the clusters became tighter). The algorithm stops when these movements become negligible. Final answer: after convergence,

μ_{1} \approx 0.5

–

1.0

(centered on

{0, 1}

μ_{2} \approx 2.0

–

2.5

(centered on

{2, 3}

σ_{1}^{2} \approx σ_{2}^{2} \approx 0.25

(quarter of initial variance),

π_{1} = π_{2} = 0.5

16.6 GMM — Practical Considerations

16.6.1 Choosing the Number of Components $K$

"How many clusters are in my data?" is one of the hardest questions in unsupervised learning. GMM doesn't answer it — you must choose

K

. These are the tools to make that choice.

Methods shared with K-means:

Elbow method — Run GMM for $K = 1, 2, 3, \dots$ and plot the log-likelihood (or BIC/AIC). The curve typically rises sharply at first, then bends like an elbow. Pick the $K$ at the bend — after that point, adding more components gives diminishing returns.
Silhouette analysis — For each point, compute the silhouette score: $(b - a) / max (a, b)$ , where $a$ is the mean distance to points in the same cluster, and $b$ is the mean distance to points in the nearest other cluster. Values range from $- 1$ (wrong cluster) to $+ 1$ (well-clustered). Average across all points and pick the $K$ that maximizes the average silhouette.
Cross-validation — Split the data, train GMM on folds, evaluate log-likelihood on held-out data. Pick the $K$ that gives the best held-out likelihood.

Methods specific to GMM:

4. Bayesian Information Criterion (BIC):

BIC = - 2 lo g L + K_{params} \cdot ln (n)

5. Akaike Information Criterion (AIC):

AIC = - 2 lo g L + 2 K_{params}

Where:

$L$ — the maximized likelihood of the model (how well it fits). Larger $L$ = better fit, so $- 2 lo g L$ is smaller for better fit.
$K_{params}$ — the total number of free parameters. For GMM with $K$ components in $d$ dimensions: means ( $K d$ ), covariances ( $K d (d + 1) /2$ for full covariance), and mixing coefficients ( $K - 1$ , since they sum to 1).
$n$ — number of data points.
Lower BIC or AIC is better.

The difference: BIC penalizes complexity more heavily ( $ln (n)$ vs. 2), so it favors simpler models for large $n$ . AIC tends to select slightly more complex models.

Procedure: Run GMM for $K = 1, 2, 3, 4, 5, \dots$ . For each $K$ , record the BIC and AIC scores. Plot them. Pick the $K$ that minimizes the score. The scores come directly from the GMM fitting output — Python's sklearn.mixture.GaussianMixture provides both .bic() and .aic() methods.

16.6.2 Initialization Strategies

Pitfall: Random initialization can trap EM in poor local optima. Good initialization matters — it can mean the difference between finding meaningful clusters and getting nonsense.

Random initialization — Pick random $μ_{k}$ and $σ_{k}^{2}$ . Simple but unreliable. Run multiple times with different seeds and keep the best result (highest log-likelihood).
Hierarchical splitting — Start with $K = 1$ (a single Gaussian over all data). Find the component with the largest variance and split it into two. Repeat until you reach the desired $K$ . Analogous to choosing the two farthest centroids in K-means initialization.
K-means first, then GMM (recommended) — This is what scikit-learn does by default:
- Run K-means with the desired $K$ .
- Set initial $μ_{k}$ = centroid of K-means cluster $k$ .
- Set initial $Σ_{k}$ = sample covariance of points in cluster $k$ .
- Set initial $π_{k}$ = (points in cluster $k$ ) / (total points).
K-means is fast and gives sensible starting positions. EM then refines from there, adding soft assignments and elliptical shapes.

16.6.3 Convergence Criteria

All three are equivalent in practice — they detect when the model has stopped improving:

Parameter change below threshold — Stop when $∣ μ_{k}^{(t + 1)} - μ_{k}^{(t)} ∣ < ε$ , $∣ σ_{k}^{2, (t + 1)} - σ_{k}^{2, (t)} ∣ < ε$ , and $∣ π_{k}^{(t + 1)} - π_{k}^{(t)} ∣ < ε$ for all $k$ .
Log-likelihood change below threshold — The most principled approach. Stop when: $∣ L^{(t + 1)} - L^{(t)} ∣ < ε$ where $L = \sum_{i = 1}^{n} ln p (x_{i})$ is the log-likelihood. Typical $ε = 1 0^{- 3}$ .
Assignment stability — Stop when no point changes its most-likely cluster between iterations (or when fewer than a tolerance fraction change).

Choosing

K

is an art: use BIC/AIC + elbow method. Initializing well is a science: use K-means first. Knowing when to stop is simple: watch the log-likelihood plateau. With these three practical decisions made, GMM is a robust and widely applicable clustering tool. The next half of the lecture moves to a completely different paradigm: supervised classification with Support Vector Machines.

16.7 Support Vector Machines — Core Concept

If I show you three lines separating two groups of points and ask which one you'd pick — without knowing any machine learning — you'd choose the one in the middle that gives both groups breathing room. That instinct is the Support Vector Machine. "That's the end of SVM," as the professor put it.

16.7.1 The Classification Problem

Consider predicting whether a student gets admission into their top-choice IIT. Two features matter: CGPA and JEE score. Plot each student as a point on a 2D graph:

Blue triangles ▲ = students who got in → label $+ 1$
Red circles ● = students who did not → label $- 1$

The task: draw a line that separates these two classes. In higher dimensions, this becomes a hyperplane.

Visual intuition: The x-axis is CGPA, the y-axis is JEE score. Blue points cluster in the top-right (high CGPA, high JEE). Red points cluster in the bottom-left. The separator is a straight line cutting diagonally between them.

16.7.2 Which Line Is Best?

The professor showed three candidate lines:

L₁: Separates the data but is dangerously close to the red points. A new red observation slightly different from the training data could easily fall on the wrong side. No safety margin.
L₃: Separates the data but is dangerously close to the blue points. Same problem — no breathing room on the blue side.
L₂: Sits squarely in the middle, giving breathing room to both classes. Even if new observations vary slightly from the training data, they are likely to stay on the correct side.

"If I ask you — you don't know machine learning — which among these three lines will you be choosing to differentiate these two classes? You would pick L₂ because it gives breathing space. That is SVM."

16.7.3 Decision Boundary, Margin, and Support Vectors

Three key geometric concepts define the SVM:

Decision boundary (the dashed middle line):

w \cdot x - b = 0

At this line, the prediction is 50-50 — we cannot decide the class. Points exactly on this line are equally likely to be either class.

Margin — The distance from the decision boundary to the nearest data point of each class. The total gap between the two outer margin lines is $2/∥ w ∥$ . The SVM's goal is to make this as wide as possible.

Support vectors — The data points that lie exactly on the margin boundaries (or are closest to the decision boundary). These are the hardest points to classify — the ones that constrain how wide the margin can be. They are the only points that matter for determining $w$ and $b$ .

The "namaste" analogy: The professor gave a vivid physical metaphor:

"When you're doing namaste, how much can you move your hands apart so that you don't touch the people on both sides? I want to move my hands as far as possible. When you touch somebody on one side, that much only we will take on the other side also — that is the maximum."

Your hands are the margin lines. The people on either side are the support vectors. You spread your hands until they touch the nearest person on each side. That equal distance on both sides defines the maximum margin. The decision boundary runs exactly halfway between your hands.

Critical property of support vectors: If you move any data point that is NOT a support vector, the decision boundary and margin do not change at all. If you move a support vector, the boundary shifts. That is why they are called "support" vectors — they literally support the margin. All other points are irrelevant once the SVM is trained. This sparsity is what makes SVMs efficient: after training, you can discard all non-support-vector data points.

16.7.4 SVM as an Optimization Problem

SVM is fundamentally an optimization (maximization) problem:

Goal: Maximize the margin = $2/∥ w ∥$ .
Constraint: Every training point must lie on or outside its respective margin line (for hard-margin SVM).

In different dimensions, the separator has different names:

2D: find the best line.
3D: find the best plane.
4D and higher: find the best hyperplane.

The math treats all cases uniformly — even a line is a "hyperplane" in the formalism: only the first weight term is non-zero, and the rest vanish. The professor noted: "In literature, even a line is called a hyperplane because the hyperplane equation is used."

SVM is a supervised classification algorithm. Unlike GMM (unsupervised clustering), SVM requires labeled training data: you must know which points are $+ 1$ and which are $- 1$ .

16.7.5 Hard Margin vs. Soft Margin

Scope: Hard-margin SVM assumes the data is linearly separable — that there exists a hyperplane perfectly separating the two classes. In real data, this assumption almost never holds.

Hard margin SVM: No misclassifications allowed. Every training point must be on the correct side of (or exactly on) its margin line. Problem: if there is an outlier — say, a red point deep in blue territory — SVM is forced to draw the boundary near that outlier, producing a terrible classifier.

The professor's example: "Consider some student who got a very high JEE score but due to some issue (say CGPA problem, or some malpractice identified later), even though the student seems like a top candidate, they were not selected. The data point sits in blue territory but is actually red. SVM will draw the boundary near that outlier, creating a wrong boundary."

Soft margin SVM: Allows some misclassifications. The algorithm tolerates a few points on the wrong side of the margin, paying a penalty proportional to the violation. This makes the model more generalizable and less sensitive to outliers. Soft margin SVM (with slack variables $ξ_{n}$ ) is covered in the next class and is what is used in virtually all real-world applications.

	Hard margin	Soft margin
Misclassifications	Zero tolerance	Tolerated, with penalty
Outlier sensitivity	Extremely sensitive	Robust
Data requirement	Must be linearly separable	Works with overlapping classes
Real-world usage	Mostly theoretical	Used everywhere

SVM is the art of finding the widest street between two classes. The street's center line is the decision boundary, its edges are defined by the support vectors, and its width is the margin. Everything else — the primal optimization, the dual formulation, the Lagrangian — is machinery to compute this geometrically intuitive idea efficiently, especially in high dimensions.

16.8 SVM — Mathematical Formulation

16.8.1 Setup and Notation

We have

n

data points. For each point

i

$x_{i} \in R^{d}$ — a vector of $d$ features (e.g., CGPA and JEE score, so $d = 2$ ).
$y_{i} \in {+ 1, - 1}$ — the class label.
- $y_{i} = + 1$ : positive class (got admission, blue triangle ▲)
- $y_{i} = - 1$ : negative class (did not get admission, red circle ●)

The SVM learns a function

f (x) = w \cdot x - b

from the training data. The sign of

f (x)

gives the predicted class:

If $f (x) \geq 0$ → predict $+ 1$
If $f (x) < 0$ → predict $- 1$

16.8.2 Hyperplane Equations

Three parallel hyperplanes define the SVM:

Decision boundary (dashed middle line):

w \cdot x - b = 0 or w^{⊤} x - b = 0

Right margin line (positive side, prediction = $+ 1$ ):

w \cdot x - b = 1

Left margin line (negative side, prediction = $- 1$ ):

w \cdot x - b = - 1

Where:

$w$ — the weight vector. Like the slope coefficients in a line equation. $w \in R^{d}$ .
$b$ — the bias (intercept). A scalar. Shifts the hyperplane away from the origin.
$x$ — a feature vector.

Any point with $w \cdot x - b \geq 1$ is classified $+ 1$ . Any point with $w \cdot x - b \leq - 1$ is classified $- 1$ . Points in between ( $- 1 < w \cdot x - b < 1$ ) lie inside the margin.

What about 2D? For a line in 2D, the equation is $w_{1} x_{1} + w_{2} x_{2} - b = 0$ . This is exactly the hyperplane equation with $d = 2$ . The professor emphasized: "Even though it is lower dimension, they use the hyperplane equation itself."

16.8.3 The Normal Vector

From vector algebra: for a hyperplane

w \cdot x - b = 0

, the weight vector

w

is perpendicular (normal) to the hyperplane.

Why this matters: To measure the margin, we need the shortest distance from a point to the hyperplane. The shortest path is always along the normal direction — the direction of $w$ . This is why the margin width ends up being $2/∥ w ∥$ .

16.8.4 Deriving the Margin Size

Step-by-step derivation of the margin width:

Start on the decision boundary: $w \cdot x - b = 0$ . Walk $K$ units in the direction of $w$ (perpendicular to the boundary) until you hit the $+ 1$ line $w \cdot x - b = 1$ .

The unit vector in the direction of $w$ is $\frac{w}{∥ w ∥}$ . So your new position is:

x_{new} = x + K \cdot \frac{w}{∥ w ∥}

Plug this into the $+ 1$ line equation:

w \cdot (x + K \frac{w}{∥ w ∥}) - b = 1

Distribute the dot product:

w \cdot x + K \frac{w \cdot w}{∥ w ∥} - b = 1

Since you started on the decision boundary, $w \cdot x - b = 0$ . Substitute:

0 + K \frac{w \cdot w}{∥ w ∥} = 1

Now $w \cdot w = ∥ w ∥^{2}$ (definition of the squared norm):

K \frac{∥ w ∥ ^{2}}{∥ w ∥} = K ∥ w ∥ = 1

K = \frac{1}{∥ w ∥}

So the distance from the decision boundary to one margin line is $1/∥ w ∥$ . The total margin (gap between the $- 1$ and $+ 1$ lines) is:

Margin = 2 K = \frac{2}{∥ w ∥}

Sense check: As $∥ w ∥$ gets smaller, the margin gets larger. If $∥ w ∥ \to 0$ , the margin $\to \infty$ (but then the hyperplane would classify everything as one class — the constraints prevent this). ✓

16.8.5 The Optimization Problem (Primal Form)

Goal: Maximize the margin =

2/∥ w ∥

Maximizing $2/∥ w ∥$ is equivalent to minimizing $∥ w ∥$ . For mathematical convenience, we minimize $\frac{1}{2} ∥ w ∥^{2}$ instead. The factor $1/2$ makes the derivative clean: $\frac{\partial}{\partial w} \frac{1}{2} ∥ w ∥^{2} = w$ .

w, b min \frac{1}{2} ∥ w ∥^{2}

Subject to the constraint that every point is correctly classified and lies on or outside its margin:

y_{i} (w \cdot x_{i} - b) \geq 1 for all i = 1, 2, \dots, n

Why does one inequality cover both classes?

For $y_{i} = + 1$ : We need $w \cdot x_{i} - b \geq 1$ . Multiply by $y_{i} = + 1$ : $y_{i} (w \cdot x_{i} - b) \geq 1$ . ✓
For $y_{i} = - 1$ : We need $w \cdot x_{i} - b \leq - 1$ . Multiply both sides by $- 1$ (flipping the inequality): $- (w \cdot x_{i} - b) \geq 1$ . Since $y_{i} = - 1$ : $y_{i} (w \cdot x_{i} - b) \geq 1$ . ✓

Both cases reduce to the same inequality. This elegant trick is what makes the SVM formulation so compact.

The professor: "From where did the ½ come? Nowhere. It is just a mathematical convenience so that when we take the gradient later it will be easier. You remember in linear regression also we used to add ½ so that the derivative becomes easy."

This is a quadratic programming problem: minimize a quadratic objective subject to linear inequality constraints. For this class of problems, any local minimum is also a global minimum — a crucial property that makes SVM optimization reliable.

16.8.6 Symbol Registry — Linear SVM

Symbol	Meaning	Type	Domain
$w$	Weight vector (normal to hyperplane)	vector	$w \in R^{d}$
$b$	Bias (intercept)	scalar	$b \in R$
$x_{i}$	Feature vector for data point $i$	vector	$x_{i} \in R^{d}$
$y_{i}$	Class label for data point $i$	scalar	$y_{i} \in {+ 1, - 1}$
$n$	Number of data points	integer	$n \geq 1$
$d$	Number of features (dimensions)	integer	$d \geq 1$
$∥ w ∥$	Euclidean norm (magnitude) of $w$	scalar	$\geq 0$
Margin	Total width between margin lines	scalar	$2/∥ w ∥$

The SVM primal problem: minimize

\frac{1}{2} ∥ w ∥^{2}

subject to

y_{i} (w \cdot x_{i} - b) \geq 1

for all

i

. This is the mathematical statement of "find the widest street that separates the two classes." The margin is

2/∥ w ∥

— smaller

∥ w ∥

means a wider margin.

16.9 From Primal to Dual — The Lagrangian Approach

The primal SVM problem optimizes over

w

d

-dimensional vector). But what if

d

is enormous — say, every pixel in an image is a feature? The dual reformulation pivots from optimizing over

d

variables to optimizing over

n

variables, where

n

is the number of data points. When

n ≪ d

(few images, many pixels), this is a massive computational win.

16.9.1 Why Convert to a Dual Problem?

In the primal problem, we minimize $\frac{1}{2} ∥ w ∥^{2}$ over $w \in R^{d}$ . The computation involves dot products $w \cdot x_{i}$ for every data point. When $d$ is large — think image data with 10,000+ pixels per image but only a few hundred images — this is expensive.

The dual formulation transforms the problem so that:

We optimize over $n$ Lagrangian multipliers $α_{i}$ instead of the $d$ -dimensional $w$ .
Only the $α_{i}$ for support vectors are non-zero. All other $α_{i} = 0$ .
The data appears only as dot products between pairs of points ( $x_{i}^{⊤} x_{j}$ ), not between weights and features.
When $n ≪ d$ , the dual is far cheaper to solve.

The professor's own words: "In large dimension data, the number of records are much smaller than the number of columns. So this calculation will be reduced a lot. That's the reason we are doing all of this gimmick."

Note on dimensions: When

d

is small compared to

n

, the primal form is actually more efficient. The dual form is specifically designed for the

n ≪ d

regime (e.g., image classification, text classification with bag-of-words). The professor focused on the dual because it also sets up the kernel trick (next lecture), where the dimension can be infinite.

16.9.2 Lagrangian Function

For each constraint

y_{i} (w^{⊤} x_{i} - b) \geq 1

, we introduce a Lagrangian multiplier

α_{i} \geq 0

. The Lagrangian function is:

L (w, b, α) = \frac{1}{2} ∥ w ∥^{2} - i = 1 \sum n α_{i} [y_{i} (w^{⊤} x_{i} - b) - 1]

This is the standard SVM Lagrangian form (Bishop §7.1, equation 7.7). The minus sign is by convention: we minimize with respect to

w

and

b

and maximize with respect to

α

16.9.3 KKT Conditions and Stationarity

The Karush-Kuhn-Tucker (KKT) conditions are necessary conditions for optimality in constrained optimization. The professor noted they are covered in the Mathematical Foundations for ML course. The key condition for the dual derivation is stationarity: set the partial derivatives of the Lagrangian to zero.

Derivative with respect to $w$ :

\frac{\partial L}{\partial w} = w - i = 1 \sum n α_{i} y_{i} x_{i} = 0

w = i = 1 \sum n α_{i} y_{i} x_{i}

This is a beautiful result: the optimal weight vector

w

is a linear combination of the training data points, each weighted by

α_{i} y_{i}

. Only points with

α_{i} > 0

contribute — those are the support vectors.

Derivative with respect to $b$ :

\frac{\partial L}{\partial b} = - i = 1 \sum n α_{i} y_{i} (- 1) = i = 1 \sum n α_{i} y_{i} = 0

Wait — let's compute carefully. The term inside the sum is $- α_{i} [y_{i} (w^{⊤} x_{i} - b) - 1] = - α_{i} y_{i} w^{⊤} x_{i} + α_{i} y_{i} b + α_{i}$ . Taking derivative with respect to $b$ : $\frac{\partial}{\partial b} (α_{i} y_{i} b) = α_{i} y_{i}$ . So:

\frac{\partial L}{\partial b} = i = 1 \sum n α_{i} y_{i} = 0

i = 1 \sum n α_{i} y_{i} = 0

This is a constraint on the

α_{i}

values: the weighted sum of labels must be zero.

16.9.4 The Dual Problem

Complete derivation from primal to dual:

Substitute $w = \sum_{j = 1}^{n} α_{j} y_{j} x_{j}$ and the constraints into the Lagrangian:

L = \frac{1}{2} ∥ w ∥^{2} - i = 1 \sum n α_{i} [y_{i} (w^{⊤} x_{i} - b) - 1] = \frac{1}{2} (i \sum α_{i} y_{i} x_{i})^{⊤} (j \sum α_{j} y_{j} x_{j}) - i \sum α_{i} y_{i} w^{⊤} x_{i} + i \sum α_{i} y_{i} b + i \sum α_{i} = \frac{1}{2} i \sum j \sum α_{i} α_{j} y_{i} y_{j} (x_{i}^{⊤} x_{j}) - i \sum α_{i} y_{i} (j \sum α_{j} y_{j} x_{j})^{⊤} x_{i} + b = 0 i \sum α_{i} y_{i} + i \sum α_{i} = \frac{1}{2} i \sum j \sum α_{i} α_{j} y_{i} y_{j} (x_{i}^{⊤} x_{j}) - i \sum j \sum α_{i} α_{j} y_{i} y_{j} (x_{j}^{⊤} x_{i}) + i \sum α_{i} = - \frac{1}{2} i = 1 \sum n j = 1 \sum n α_{i} α_{j} y_{i} y_{j} (x_{i}^{⊤} x_{j}) + i = 1 \sum n α_{i}

The bias term vanishes because $\sum_{i} α_{i} y_{i} = 0$ . The two double sums combine (they're the same sum since $x_{i}^{⊤} x_{j} = x_{j}^{⊤} x_{i}$ ), giving $\frac{1}{2} - 1 = - \frac{1}{2}$ .

The dual maximization problem:

α \geq 0 max i = 1 \sum n α_{i} - \frac{1}{2} i = 1 \sum n j = 1 \sum n α_{i} α_{j} y_{i} y_{j} (x_{i}^{⊤} x_{j})

Subject to:

\sum_{i = 1}^{n} α_{i} y_{i} = 0

and

α_{i} \geq 0

for all

i

Equivalently, as a minimization (negate the objective, which is what most solvers use):

α \geq 0 min \frac{1}{2} i = 1 \sum n j = 1 \sum n α_{i} α_{j} y_{i} y_{j} (x_{i}^{⊤} x_{j}) - i = 1 \sum n α_{i}

This is the standard dual form from Bishop §7.1 (equation 7.10). The primal and dual are equivalent — solving one gives the solution to the other via

w = \sum_{i} α_{i} y_{i} x_{i}

16.9.5 Why the Dual Is More Efficient

In the dual, data appears only as dot products $x_{i}^{⊤} x_{j}$ . The $α_{i}$ are non-zero only for support vectors (a consequence of the KKT complementary slackness condition: $α_{i} [y_{i} (w^{⊤} x_{i} - b) - 1] = 0$ ).

So the double sum $\sum_{i} \sum_{j}$ is effectively only over support vectors — a small fraction of the training data. This makes the dual dramatically more efficient when $n ≪ d$ .

KKT complementary slackness (the reason for sparsity): For every data point, either $α_{i} = 0$ (point is irrelevant — not a support vector) or $y_{i} (w^{⊤} x_{i} - b) = 1$ (point lies exactly on its margin boundary — it IS a support vector). Most points have $α_{i} = 0$ and can be discarded after training.

16.9.6 The Classification Function

Once the

α_{i}

are found, classification of a new point

x

uses:

f (x) = i = 1 \sum n α_{i} y_{i} (x_{i}^{⊤} x) + b

If $f (x) \geq 0$ → classify as $+ 1$
If $f (x) < 0$ → classify as $- 1$

The weight vector is recovered as $w = \sum_{i = 1}^{n} α_{i} y_{i} x_{i}$ .

Computing $b$ (the bias): For any support vector $x_{s}$ (a point with $α_{s} > 0$ ), we know $y_{s} (w^{⊤} x_{s} - b) = 1$ . Solving for $b$ :

y_{s} (j = 1 \sum n α_{j} y_{j} (x_{j}^{⊤} x_{s}) - b) = 1

Since $y_{s}^{2} = 1$ , multiply through by $y_{s}$ :

b = j = 1 \sum n α_{j} y_{j} (x_{j}^{⊤} x_{s}) - y_{s}

For numerical stability, average over all support vectors $S$ (Bishop §7.1, equation 7.18):

b = \frac{1}{∣ S ∣} s \in S \sum y_{s} - j \in S \sum α_{j} y_{j} (x_{j}^{⊤} x_{s})

For exam problem-solving, you need only three equations:

Classification: $f (x) = \sum_{i} α_{i} y_{i} (x_{i}^{⊤} x) + b$
Weight vector: $w = \sum_{i} α_{i} y_{i} x_{i}$
Bias: $b$ computed from any support vector as above.

The Lagrangian and KKT derivations are for conceptual understanding — the professor stated explicitly: "Derivations you can take from the slide. Nobody may ask, but ML maybe will not ask."

16.10 SVM — Worked Example

This is the canonical exam-style SVM problem. The professor stated: "Just please study solving system of linear equations. Otherwise you will not be able to solve this here." Work through every step — the math is straightforward but you need to be systematic.

16.10.1 Problem Setup

Three data points, each with features augmented by a bias column of 1:

Point	Features (with bias)	Label $y$
$x_{1}$	$(0, 1, 1)$	$- 1$
$x_{2}$	$(- 1, 3, 1)$	$+ 1$
$x_{3}$	$(1, 3, 1)$	$+ 1$

The third component "1" is the bias term added manually — the same technique used in linear regression when adding a column of ones for the intercept. This absorbs $b$ into the weight vector: the third component of $w$ will be $- b$ .

Visual intuition: Plot these in 2D (ignoring the bias column). $x_{1} = (0, 1)$ is the lone negative point at the bottom. $x_{2} = (- 1, 3)$ and $x_{3} = (1, 3)$ are the two positive points at the top, symmetrically placed. The decision boundary should be a horizontal line somewhere between $y = 1$ and $y = 3$ .

16.10.2 Step 1 — Write the System of Linear Equations

For support vectors (all three points will turn out to be support vectors), the classification condition is:

j = 1 \sum 3 α_{j} y_{j} (x_{j}^{⊤} x_{i}) = y_{i}

For $i = 1$ ( $y_{1} = - 1$ ):

α_{1} (- 1) (x_{1}^{⊤} x_{1}) + α_{2} (+ 1) (x_{2}^{⊤} x_{1}) + α_{3} (+ 1) (x_{3}^{⊤} x_{1}) = - 1

Compute the dot products:

$x_{1}^{⊤} x_{1} = 0^{2} + 1^{2} + 1^{2} = 2$ → $α_{1} (- 1) (2) = - 2 α_{1}$
$x_{2}^{⊤} x_{1} = (- 1) (0) + 3 (1) + 1 (1) = 4$ → $α_{2} (+ 1) (4) = 4 α_{2}$
$x_{3}^{⊤} x_{1} = 1 (0) + 3 (1) + 1 (1) = 4$ → $α_{3} (+ 1) (4) = 4 α_{3}$

- 2 α_{1} + 4 α_{2} + 4 α_{3} = - 1 (Eq 1)

For $i = 2$ ( $y_{2} = + 1$ ):

$x_{1}^{⊤} x_{2} = 0 (- 1) + 1 (3) + 1 (1) = 4$ → $α_{1} (- 1) (4) = - 4 α_{1}$
$x_{2}^{⊤} x_{2} = (- 1)^{2} + 3^{2} + 1^{2} = 1 + 9 + 1 = 11$ → $α_{2} (+ 1) (11) = 11 α_{2}$
$x_{3}^{⊤} x_{2} = 1 (- 1) + 3 (3) + 1 (1) = - 1 + 9 + 1 = 9$ → $α_{3} (+ 1) (9) = 9 α_{3}$

- 4 α_{1} + 11 α_{2} + 9 α_{3} = 1 (Eq 2)

For $i = 3$ ( $y_{3} = + 1$ ):

$x_{1}^{⊤} x_{3} = 0 (1) + 1 (3) + 1 (1) = 4$ → $α_{1} (- 1) (4) = - 4 α_{1}$
$x_{2}^{⊤} x_{3} = (- 1) (1) + 3 (3) + 1 (1) = - 1 + 9 + 1 = 9$ → $α_{2} (+ 1) (9) = 9 α_{2}$
$x_{3}^{⊤} x_{3} = 1^{2} + 3^{2} + 1^{2} = 1 + 9 + 1 = 11$ → $α_{3} (+ 1) (11) = 11 α_{3}$

- 4 α_{1} + 9 α_{2} + 11 α_{3} = 1 (Eq 3)

16.10.3 Step 2 — Solve the System of Linear Equations

⎩ ⎨ ⎧ - 2 α_{1} + 4 α_{2} + 4 α_{3} = - 1 - 4 α_{1} + 11 α_{2} + 9 α_{3} = 1 - 4 α_{1} + 9 α_{2} + 11 α_{3} = 1 (Eq 1) (Eq 2) (Eq 3)

Subtract Eq 3 from Eq 2:

(- 4 α_{1} + 11 α_{2} + 9 α_{3}) - (- 4 α_{1} + 9 α_{2} + 11 α_{3}) = 1 - 1

2 α_{2} - 2 α_{3} = 0 \Rightarrow α_{2} = α_{3}

Let $α_{2} = α_{3} = t$ . Substitute into Eq 1:

- 2 α_{1} + 4 t + 4 t = - 1 \Rightarrow - 2 α_{1} + 8 t = - 1 \Rightarrow α_{1} = 4 t + 0.5

Substitute into Eq 2:

- 4 (4 t + 0.5) + 11 t + 9 t = 1

- 16 t - 2 + 20 t = 1

4 t - 2 = 1 \Rightarrow 4 t = 3 \Rightarrow t = 0.75

Therefore:

α_{2} = α_{3} = 0.75, α_{1} = 4 (0.75) + 0.5 = 3.5

All three $α_{i} > 0$ → all three points are support vectors.

16.10.4 Step 3 — Compute $w$ and $b$

w = i = 1 \sum 3 α_{i} y_{i} x_{i} = 3.5 (- 1) (0, 1, 1) + 0.75 (+ 1) (- 1, 3, 1) + 0.75 (+ 1) (1, 3, 1) = (- 3.5) (0, 1, 1) + 0.75 (- 1, 3, 1) + 0.75 (1, 3, 1) = (0, - 3.5, - 3.5) + (- 0.75, 2.25, 0.75) + (0.75, 2.25, 0.75) = (0, 1, - 2)

So $w = (w_{1}, w_{2}, w_{3}) = (0, 1, - 2)$ . The third component $w_{3} = - 2$ is the negative of the bias: $b = - w_{3} = 2$ .

16.10.5 Step 4 — Write the Decision Boundary

The decision boundary: $w \cdot x = 0$ .

0 \cdot x_{1} + 1 \cdot x_{2} + (- 2) \cdot 1 = 0 \Rightarrow x_{2} - 2 = 0 \Rightarrow x_{2} = 2

The decision boundary is the horizontal line $y = 2$ .

The margin lines:

Right side ( $+ 1$ ): $w \cdot x = 1$ → $x_{2} - 2 = 1$ → $x_{2} = 3$
Left side ( $- 1$ ): $w \cdot x = - 1$ → $x_{2} - 2 = - 1$ → $x_{2} = 1$

Verification — check that support vectors lie on margin lines:

$x_{2} = (- 1, 3, 1)$ : $1 \cdot 3 - 2 = 1$ ✓ (on $+ 1$ margin)
$x_{3} = (1, 3, 1)$ : $1 \cdot 3 - 2 = 1$ ✓ (on $+ 1$ margin)
$x_{1} = (0, 1, 1)$ : $1 \cdot 1 - 2 = - 1$ ✓ (on $- 1$ margin)

Margin width: $∥ w ∥ = 0^{2} + 1^{2} + (- 2)^{2} = 5$ . The effective margin in the 2D projection is the distance between the margin lines: $3 - 1 = 2$ .

16.10.6 Interpretation

Classification rule:

Any point with $x_{2} \geq 2$ (on or above $y = 2$ ) → class $+ 1$
Any point with $x_{2} < 2$ (below $y = 2$ ) → class $- 1$

The decision boundary

y = 2

sits exactly halfway between the negative point at

y = 1

and the positive points at

y = 3

. This is the maximum-margin solution: the margin of 1 unit on each side is the largest possible given these three points.

Sense check: The two positive points $x_{2}$ and $x_{3}$ are at the same $y = 3$ height, symmetrically placed at $x = - 1$ and $x = + 1$ . The single negative point $x_{1}$ is at $y = 1$ , $x = 0$ . The maximum-margin line should indeed be horizontal at $y = 2$ — the midpoint. The $x$ -coordinate doesn't matter because both positive points share the same $y$ -value, making the problem effectively 1D in the $y$ direction. ✓

The worked example shows the full pipeline: set up the

α

-equations from dot products → solve the linear system → compute

w = \sum α_{i} y_{i} x_{i}

→ extract

b

from

w

's bias component → write the decision boundary. For the exam, the professor emphasized: "These three equations —

f (x)

(classification function),

w

equation, and

b

equation — you just use those three equations for problem solving."

16.11 Student Questions and Answers

The following questions capture distinct confusion points raised during the lecture. Repetitive questions have been merged into the clearest canonical version. Frequency noted where multiple students asked the same thing.

Q: Why do we need to remove duplicate records before clustering? A: If you have many copies of the same record, the statistical description (mean, spread) gets biased. One record repeated 100 times will heavily distort the mean. Even though it may not affect all measures equally, the statistical description is the foundation — from there it influences everything downstream: cluster centers, variance estimates, and ultimately the assignments. This applies to both K-means and GMM.

Q: When we "assume two random Gaussians," what exactly do we assume? A: We assume specific numeric values for

μ_{1}, μ_{2}, σ_{1}, σ_{2}

. That's it. One Gaussian has a certain mean and standard deviation; the other has different values. These are the parameters that define each bell curve. "Random" here means "initial guesses," not "truly random from thin air" — in practice, Python uses K-means to get sensible starting values.

Q: (Multiple students asked variations) What if a point has equal probability of belonging to two clusters (50-50)? A: It's very unlikely that the probabilities are exactly equal, but if it happens, you can assign the point to either cluster — it doesn't matter. Algorithmically, this is handled with

\leq

\geq

conditions. In soft clustering, the assignment is probabilistic anyway, so a 50-50 split just means the point is genuinely ambiguous.

Q: (Multiple students asked) Do we need to calculate the dot products for ALL records in SVM? A: Practically, the algorithm computes dot products for all records during training. But after solving, the

α_{i}

values become zero for everything except the support vectors. So for classification of new points, you effectively only need the support vectors. This sparsity — most

α_{i} = 0

— is why the dual formulation is efficient in practice.

Q: What if the data has overlapping points in SVM? A: Remove exact duplicates before running the algorithm — they don't add information and can cause numerical issues. For points that are very close but not identical, hard-margin SVM may struggle to find a perfect separator. Soft-margin SVM (next lecture) handles overlapping classes explicitly by allowing some misclassifications with a penalty.

Q: Does the margin line always touch the support vectors? A: Conceptually, the margin lines are as close to the support vectors as possible without crossing them. When you compute the maximum margin, the margin lines may or may not exactly touch — they must be kept as close as possible. The professor's analogy: "When you're doing namaste, how far can you move your hands apart before touching someone on either side? When you touch someone on one side, that is the limit — you take that same distance on the other side too." In the formal hard-margin solution, the active constraints (support vectors) satisfy the equality

y_{i} (w^{⊤} x_{i} - b) = 1

exactly.

Q: (Several students asked) How do we get from the primal to the dual problem? Where do the

α

values come from? A: The

α

values are Lagrangian multipliers — they come from the Lagrangian function used to convert the constrained optimization into a dual form. This involves KKT conditions and Lagrangian duality, studied in detail in the Mathematical Foundations for ML course. For the ML course, you only need the final formulas:

f (x) = \sum α_{i} y_{i} (x_{i}^{⊤} x) + b

w = \sum α_{i} y_{i} x_{i}

, and the formula for

b

. The derivations are for conceptual understanding — "ML maybe will not ask" the derivations.

Q: Why is

w

perpendicular to the hyperplane? A: This is standard vector algebra. For any hyperplane defined by

w \cdot x - b = 0

, the gradient is

w

, and the gradient is always perpendicular to the level set. Another way: take any two points

x_{a}, x_{b}

on the hyperplane. Then

w \cdot x_{a} = b

and

w \cdot x_{b} = b

, so

w \cdot (x_{a} - x_{b}) = 0

. Thus

w

is perpendicular to every vector lying in the hyperplane — it is the normal vector.

Q: Do we need to solve the system of equations for SVM manually on the exam? A: Yes. You need to know how to write the system of linear equations using the classification function formula

\sum_{j} α_{j} y_{j} (x_{j}^{⊤} x_{i}) = y_{i}

, and then solve it for the

α

values. The professor's advice: "Just please study solving system of linear equations. Otherwise you will not be able to solve this here."

16.12 Exam Guidance

16.12.1 Mark Distribution

Exam note: Post-mid-semester content carries 75% of the exam weight. Pre-mid-semester content: 25%. The professor did not specify topic-wise importance within this split, but GMM and SVM are major post-mid topics and likely to appear.

16.12.2 Problem Types

GMM exam problems — Expect 1D problems only (2D is too calculation-heavy for hand computation). The canonical question: "Consider a dataset with four points 0, 1, 2, and 3. Fit a mixture of two Gaussian components." You must be able to:

Compute responsibilities in the E-step using $r_{ik} = \frac{π _{k} N ( x _{i} ∣ μ _{k} , σ _{k}^{2} )}{\sum _{j} π _{j} N ( x _{i} ∣ μ _{j} , σ _{j}^{2} )}$
Update parameters in the M-step: $μ_{k}^{new}, σ_{k}^{2, new}, π_{k}^{new}$
Check convergence (assignments stop changing or log-likelihood stabilizes)

SVM exam problems — Expect to be given 3-4 data points with labels. You must:

Write the system of linear equations: $\sum_{j} α_{j} y_{j} (x_{j}^{⊤} x_{i}) = y_{i}$ for each $i$
Solve the system for $α_{1}, α_{2}, \dots$
Compute $w = \sum_{i} α_{i} y_{i} x_{i}$ and extract $b$
Write the decision boundary equation and margin lines
State the classification rule

The worked example in §16.10 with 3 data points is representative of what to expect.

16.12.3 What to Know (and What Not To)

Exam note — Need to know (memorize & apply):

GMM: Responsibility formula, mean update, variance update, mixing coefficient update
SVM: Classification function $f (x) = \sum α_{i} y_{i} (x_{i}^{⊤} x) + b$ , weight vector $w = \sum α_{i} y_{i} x_{i}$ , bias formula from a support vector
SVM: How to write the system of linear equations from data points

Derivations are for understanding only:

Lagrangian function, KKT conditions, and derivation of the dual problem
The professor: "Derivations you can take from the slide. Nobody may ask, but ML maybe will not ask."

Open book: Formulas will be available in the slides. The common slides are what you can take into the exam. But you must know which formula to apply when — memorizing the structure is more important than memorizing every symbol.

16.12.4 Study Advice

Exam note — Professor's study recommendations:

Concept first, formulas second. If you understand the "coloring" process for GMM and the "margin maximization" idea for SVM, the formulas become easy. The professor warned: "If you simply try to by-heart the formula 100 percentage, you will miss one or other step."
For SVM: "These three equations — $f (x)$ (classification function), $w$ equation, and $b$ equation — you just use those three equations for problem solving."
For GMM: The E-step = coloring example. Keep that picture in mind: "You'll be able to solve any given problem."
Practice solving systems of linear equations. The SVM exam problem reduces to exactly this skill. The professor: "Just please study solving system of linear equations."
The professor will upload a complete worked SVM example with all solving steps — use it to practice.

16.13 Key Industry Applications and Real-World Connections

GMM for unsupervised discovery — height data and beyond. The classic example: adult heights in a city come from two underlying distributions (men and women). GMM discovers these latent groups without ever seeing gender labels. This same pattern applies to several real-world tasks: customer segmentation (discovering spending-personality types from transaction data), anomaly detection (flagging points with low probability under the fitted GMM as outliers), and image segmentation. For image segmentation, the technique is known as vector quantization — each pixel is represented by its closest cluster center (Bishop §9.1.1).
SVM for binary classification — admissions, medicine, and finance. The motivating example uses CGPA and JEE scores for admission prediction — a realistic binary classification scenario. The same framework applies to: loan default prediction (will this borrower repay?), medical diagnosis (malignant vs. benign tumor from imaging features), spam detection (spam vs. not-spam from email features), and face detection (face vs. non-face from pixel intensities).
Large-dimensional data — why SVM's dual shines. The professor emphasized image data as the motivating case for the dual formulation. Images have thousands of pixels (features) but training sets may have only hundreds of images. In this $n ≪ d$ regime, the dual form reduces computation dramatically by working with dot products between data points rather than dot products with the weight vector. The same advantage applies to text classification with bag-of-words features (vocabulary size = $d ≫ n$ ).
Python implementations — K-means initializes GMM. scikit-learn's GaussianMixture uses K-means to initialize cluster centers, covariances, and mixing weights before running EM. This gives faster, more reliable convergence. Similarly, sklearn.svm.SVC implements both linear and kernel SVMs with efficient solvers (SMO, libsvm).
Nonlinear SVM — the kernel trick (next lecture). The professor previewed that nonlinear SVM handles data that is not linearly separable. By replacing dot products $x_{i}^{⊤} x_{j}$ with kernel functions $k (x_{i}, x_{j})$ , the SVM can learn nonlinear decision boundaries while keeping the same optimization framework. The popular Gaussian (RBF) kernel $k (x_{i}, x_{j}) = exp (- γ ∥ x_{i} - x_{j} ∥^{2})$ is the default in most libraries.
Soft margin SVM — the practical default. Virtually all real-world SVM applications use soft margin (with slack variables $ξ_{n}$ and a regularization parameter $C$ ) because real data always has noise and overlapping classes. Hard margin is primarily a theoretical building block that leads to the more practical soft-margin formulation.

16.14 Professor Pedagogical Highlights

The professor used several memorable analogies and teaching strategies throughout this lecture. These are preserved here as they capture the intuitive core of each concept.

Reverse engineering analogy for GMM:

"It's like reverse engineering. We are going to look at the data set and we are going to ask: if I have to recreate this particular data set using a few Gaussian distributions, where will I put those bell curves? How wide would they be?"

Namaste analogy for margin:

"When you're doing namaste... how much you can move your hands apart so that you don't touch the people on both sides? I want to move my hands as far as possible. When you touch somebody on one side, that much only we will take on the other side also — that is the maximum."

Top-view visualization for Gaussians:

The concentric circles in GMM plots are the top view of bell curves — "You are standing here and looking at this... You're at the sky. Imagine and you're looking at this."

Heads-up on difficulty — GMM:

"Don't panic if you're not understanding in the beginning. By the end, once we complete that, you will be able to connect the dots or stitch the parts together. It is how everyone is going to feel it. So don't think that only I'm not understanding or only I'm not able to make sense."

Heads-up on difficulty — SVM dual:

"Whatever I'm going to explain to you in the next 10 minutes, none of you are going to make sense, but listen. Listen it once, listen it twice, listen it thrice. You will get an idea."

Formula memorization warning:

"If you understood the concept, it is very easy, but if you simply try to by-heart the formula 100 percentage, you will miss one or other step. What is that coloring example? Keep in mind, we can do that. You'll be able to solve any given problem."

On GMM as K-means extension:

"It is exactly K-means extension. That is why we learned K-means first."

On the ½ in SVM objective:

"From where did it come? Nowhere. It is just a mathematical convenience so that when we take gradient later it will be more easy for us. You remember in linear regression also we used to add ½ so that the derivative becomes easy."

On SVM as an idea:

"If I ask you — you don't know machine learning — which among these three lines will you be choosing to differentiate these two classes? You would pick L₂ because it gives breathing space. That is SVM. That's the end of SVM."

ML Lecture 16 notes · Gaussian Mixture Models and Support Vector Machines

Machine Learning· postgraduate· 2026-06-30

Sections Breakdown

1Context — From K-Means to Gaussian Mixture Models

Bridges from hard K-means clustering to the soft, probabilistic GMM framework, covering the limitations of hard clustering and the reverse-engineering analogy for mixture models.

2Gaussian Mixture Model — Core Concepts

Hard vs. soft clustering comparison, flexibility in cluster shape via covariance matrices, and the core idea of data as a weighted sum of Gaussian distributions.

3The GMM Algorithm — Expectation-Maximization

The EM algorithm steps: initialization, E-step (compute responsibilities), M-step (update parameters), and convergence check. Includes the coloring analogy and formal algorithm statements.

4GMM — Mathematical Foundation

1D and multivariate Gaussian PDFs, the GMM probability density function as an additive mixture, and a complete symbol registry for 1D GMM.

5GMM — Worked Example

Full step-by-step EM on a 4-point dataset with K=2: E-step responsibility calculations, M-step parameter updates, and convergence analysis.

6GMM — Practical Considerations

Choosing K via BIC/AIC/elbow method, initialization strategies (K-means first recommended), and convergence criteria.

7Support Vector Machines — Core Concept

The margin maximization intuition, decision boundary/hyperplane, support vectors and their sparsity property, the namaste analogy, and hard vs. soft margin comparison.

8SVM — Mathematical Formulation

Setup and notation, hyperplane equations, normal vector concept, step-by-step margin width derivation, and the primal optimization problem.

9From Primal to Dual — The Lagrangian Approach

Why convert to dual, Lagrangian function, KKT stationarity conditions, complete dual derivation, and the classification function with the three key exam equations.

10SVM — Worked Example

Full 3-point SVM example with bias column: system of linear equations, solving for alpha values, computing w and b, writing the decision boundary.

11Student Questions and Answers

Consolidated student questions covering duplicate removal, random initialization, 50-50 splits, dot product computation, overlapping points, margin behavior, and Lagrangian derivations.

12Exam Guidance

Mark distribution, GMM and SVM problem types, what to memorize vs. what to understand, and study advice from the professor.

13Key Industry Applications and Real-World Connections

Real-world applications of GMM (customer segmentation, anomaly detection) and SVM (admissions, medicine, finance, image/text classification).

14Professor Pedagogical Highlights

Memorable analogies: reverse engineering for GMM, namaste for SVM margins, top-view for Gaussians, and key teaching strategies.

Postgraduate students in Machine Learning

Exam Revision Notes

Below is the distilled, exam-ready core of this lecture. Every entry is built from the full textbook notes above. Use this section for rapid review — but if something doesn't make sense, go back to the full explanation in the main content.

Gaussian Mixture Models — Soft Clustering and Mixture Concept

Must-know: GMM is a probabilistic clustering model that assigns each data point a soft membership — a probability distribution over clusters — rather than a hard binary assignment. The model assumes data is generated from a weighted sum (mixture) of K Gaussian distributions, each with its own mean $μ_{k}$ , variance $σ_{k}^{2}$ , and mixing coefficient $π_{k}$ (where $\sum_{k = 1}^{K} π_{k} = 1$ ).

$p (x) = k = 1 \sum K π_{k} \cdot \frac{1}{2 π σ _{k}^{2}} exp (- \frac{( x - μ _{k} ) ^{2}}{2 σ _{k}^{2}})$

⚠️ Top pitfall: Forgetting the mixing coefficient constraint $\sum π_{k} = 1$ . Students often treat $π_{k}$ as free parameters — they are probabilities and must sum to 1.

Self-check: How does GMM differ from K-means in terms of (a) cluster assignment and (b) cluster shape?

Connects to: K-means clustering (hard assignment counterpart), EM algorithm (the fitting method), covariance matrices (enabling elliptical clusters).

Expectation-Maximization Algorithm for GMM

Must-know: The EM algorithm alternates between two steps. E-step: Compute responsibilities $r_{ik}$ — the probability that point $i$ belongs to component $k$ . M-step: Update parameters $μ_{k}, σ_{k}^{2}, π_{k}$ using weighted averages. Repeat until log-likelihood stabilizes. Every point always has fractional membership — no point is ever 100% in one cluster.

$r_{ik} = \frac{π _{k} \cdot N ( x _{i} ∣ μ _{k} , σ _{k}^{2} )}{\sum _{j = 1}^{K} π _{j} \cdot N ( x _{i} ∣ μ _{j} , σ _{j}^{2} )} (E-step)$ $μ_{k}^{new} = \frac{\sum _{i = 1}^{n} r _{ik} \cdot x _{i}}{\sum _{i = 1}^{n} r _{ik}} (M-step mean update)$

⚠️ Top pitfall: Confusing the E-step and M-step formulas. The responsibility formula (E-step) uses the current parameters. The M-step formula uses the responsibilities just computed in the E-step. Also: forgetting that EM can converge to local optima.

Self-check: If $μ_{1} = 0$ and $μ_{2} = 5$ with $σ_{1}^{2} = σ_{2}^{2} = 1$ and equal mixing coefficients, what is the approximate responsibility of $x = 0$ for component 1?

Connects to: GMM model definition, convergence criteria (log-likelihood threshold $ε$ ), K-means EM analogy, local optima problem.

GMM Worked Example — 4-Point Dataset

Must-know: The canonical exam problem: fit $K = 2$ Gaussians to points ${0, 1, 2, 3}$ . Initialize: $μ_{1} = 0.5, μ_{2} = 2.5, σ_{1}^{2} = σ_{2}^{2} = 1, π_{1} = π_{2} = 0.5$ . Run one full EM iteration. After E-step, responsibilities approximately: $r_{0, 1} \approx 0.95, r_{1, 1} \approx 0.80, r_{2, 1} \approx 0.20, r_{3, 1} \approx 0.05$ . After M-step, $μ_{1}^{new} \approx 0.68$ – $0.71$ , $μ_{2}^{new} \approx 2.29$ – $2.33$ , $σ_{1}^{2}, σ_{2}^{2}$ shrink to ~0.62. Both means move toward their natural clusters — variances tighten.

$μ_{1}^{new} = \frac{\sum _{i} r _{i, 1} \cdot x _{i}}{\sum _{i} r _{i, 1}}, σ_{1}^{2, new} = \frac{\sum _{i} r _{i, 1} \cdot ( x _{i} - μ _{1}^{new} ) ^{2}}{\sum _{i} r _{i, 1}}, π_{k}^{new} = \frac{1}{n} i \sum r_{ik}$

⚠️ Top pitfall: Using the updated mean in the variance formula but forgetting to use it in the squared deviation term $(x_{i} - μ_{k}^{new})^{2}$ . Also: not checking that responsibilities sum to 1 for each point.

Self-check: After the first M-step, why do the mixing coefficients stay at 0.5 for this symmetric dataset?

Connects to: EM algorithm steps, Gaussian PDF evaluation, convergence check, choosing K (BIC/AIC), initialization strategies.

GMM Practical Considerations — Choosing K, Initialization, and Convergence

Must-know: Choosing K: Use BIC ( $BIC = - 2 lo g L + K_{params} ln n$ ) or AIC ( $AIC = - 2 lo g L + 2 K_{params}$ ) — lower is better. BIC penalizes complexity more heavily. Initialization: K-means first (scikit-learn default) gives reliable starting positions. Convergence: Stop when $∣ L^{(t + 1)} - L^{(t)} ∣ < ε$ (typically $1 0^{- 3}$ ).

$BIC = - 2 lo g L + K_{params} \cdot ln (n), AIC = - 2 lo g L + 2 K_{params}$

⚠️ Top pitfall: Using BIC/AIC with too few candidate K values (just K=2,3,4). Always test a range and look for the minimum. Also: confusing which is lower-is-better — both BIC and AIC are lower-is-better.

Self-check: For a dataset with n=1000 points, which criterion (BIC or AIC) would favor a simpler model? Why?

Connects to: Elbow method, silhouette analysis, cross-validation for K selection, EM local optima, K-means initialization strategy.

Support Vector Machines — Margin Maximization Concept

Must-know: SVM finds the hyperplane that maximizes the margin between two classes. The margin is $2/∥ w ∥$ . The support vectors are the data points closest to the decision boundary — they are the only points that determine $w$ and $b$ . Moving any non-support-vector point does NOT change the boundary. This sparsity is the key computational property of SVMs.

$Decision boundary: w \cdot x - b = 0, Margin lines: w \cdot x - b = \pm 1, Margin width: \frac{2}{∥ w ∥}$

⚠️ Top pitfall: Confusing the decision boundary ( $w \cdot x - b = 0$ ) with the margin lines ( $w \cdot x - b = \pm 1$ ). Also: thinking hard-margin SVM works when data is not linearly separable — it doesn't.

Self-check: How many support vectors does a hard-margin SVM typically have relative to the total number of training points?

Connects to: Binary classification, hard vs. soft margin, optimization constraints, Lagrangian dual formulation, kernel trick (next lecture).

SVM Mathematical Formulation — Primal Problem

Must-know: The SVM primal problem minimizes $\frac{1}{2} ∥ w ∥^{2}$ subject to $y_{i} (w \cdot x_{i} - b) \geq 1$ for all $i$ . The factor $1/2$ is for derivative convenience. The elegant constraint trick $y_{i} (w \cdot x_{i} - b) \geq 1$ covers both classes in one inequality. The margin is derived by walking $K = 1/∥ w ∥$ units along the normal direction $w$ from the decision boundary to either margin line.

$w, b min \frac{1}{2} ∥ w ∥^{2} s.t. y_{i} (w \cdot x_{i} - b) \geq 1 \forall i$

⚠️ Top pitfall: Forgetting that the constraint uses $\geq 1$ (not $\geq 0$ ). The 1 comes from the margin line equations $w \cdot x - b = \pm 1$ . Also: not understanding why $w$ is perpendicular to the hyperplane — this is fundamental to the margin derivation.

Self-check: Derive why the distance from the decision boundary to one margin line is $1/∥ w ∥$ .

Connects to: Margin width derivation, normal vector concept, quadratic programming, KKT conditions, dual formulation.

SVM Lagrangian Dual — From Primal to Dual

Must-know: The dual formulation transforms the problem from optimizing over $w \in R^{d}$ to optimizing over $n$ Lagrangian multipliers $α_{i} \geq 0$ . The key result: $w = \sum_{i} α_{i} y_{i} x_{i}$ . Only support vectors have $α_{i} > 0$ (all others are zero). The dual is more efficient when $n ≪ d$ . For classification: $f (x) = \sum_{i} α_{i} y_{i} (x_{i}^{⊤} x) + b$ .

$w = i = 1 \sum n α_{i} y_{i} x_{i}, f (x) = i = 1 \sum n α_{i} y_{i} (x_{i}^{⊤} x) + b, i = 1 \sum n α_{i} y_{i} = 0$

⚠️ Top pitfall: Forgetting the constraint $\sum_{i} α_{i} y_{i} = 0$ . This comes from setting $\partial L / \partial b = 0$ and is an essential constraint on the $α_{i}$ values. Also: thinking Lagrangian derivations are required for the exam — they are for understanding only.

Self-check: Why are most $α_{i} = 0$ after solving the SVM dual? What condition makes an $α_{i}$ non-zero?

Connects to: Primal optimization, KKT complementary slackness, support vector sparsity, kernel trick (next lecture), bias computation.

SVM Worked Example — 3-Point Dataset with Bias Column

Must-know: The canonical exam problem: 3 points with augmented bias column of 1. $x_{1} = (0, 1, 1), y_{1} = - 1$ ; $x_{2} = (- 1, 3, 1), y_{2} = + 1$ ; $x_{3} = (1, 3, 1), y_{3} = + 1$ . Solve the system $\sum_{j} α_{j} y_{j} (x_{j}^{⊤} x_{i}) = y_{i}$ for each $i$ . Solution: $α_{1} = 3.5, α_{2} = α_{3} = 0.75$ . Result: $w = (0, 1, - 2)$ , decision boundary $x_{2} = 2$ .

$f (x) = j \sum α_{j} y_{j} (x_{j}^{⊤} x) + b, w = i \sum α_{i} y_{i} x_{i}, b = - w_{3} (bias component)$

⚠️ Top pitfall: Forgetting to include the bias column of 1 in the feature vectors when computing dot products. The third component "1" absorbs $b$ into $w$ so that the decision boundary equation becomes $w \cdot x = 0$ instead of $w \cdot x - b = 0$ . Also: arithmetic errors in solving the 3×3 linear system — practice this.

Self-check: Verify that each support vector lies exactly on its respective margin line ( $x_{2} = 1$ for negative, $x_{2} = 3$ for positive).

Connects to: Classification function, system of linear equations, support vector identification, margin verification, bias extraction from augmented weight vector.

Previous LectureLecture 15 · Ensemble Learning, Gradient Boosting, and Introduction to Unsupervised Learning

Next LectureLecture 17 · Support Vector Machines — Soft Margin, Non-Linear SVM, and Model Fairness

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

Gaussian Mixture Models and Support Vector Machines

16.1 Context — From K-Means to Gaussian Mixture Models

16.1.1 Recap of K-Means Clustering

16.1.2 Why Remove Duplicates Before Clustering

16.1.3 Introducing Gaussian Mixture Models (GMM)

16.1.4 Why Not a Single Gaussian?

16.2 Gaussian Mixture Model — Core Concepts

16.2.1 Hard Clustering vs. Soft Clustering

16.2.2 Flexibility in Cluster Shape

16.2.3 The Core Idea — Data as a Mixture of Gaussians

16.3 The GMM Algorithm — Expectation-Maximization

16.3.1 Algorithm Overview (Conceptual)

16.3.2 Visual Analogy — The "Coloring" Process

16.3.3 Formal Algorithm Steps

16.4 GMM — Mathematical Foundation

16.4.1 1D Gaussian Probability Density Function

16.4.2 Multivariate Gaussian Probability Density Function

16.4.3 The GMM Probability Density Function

16.4.4 Symbol Registry — GMM (1D)

16.5 GMM — Worked Example

16.5.1 Problem Setup

16.5.2 Step 1 — Initialization

16.5.3 Step 2 — E-step: Compute Responsibilities

16.5.4 Step 3 — M-step: Update Parameters

16.5.5 Step 4 — Repeat Until Convergence

16.6 GMM — Practical Considerations

16.6.1 Choosing the Number of Components K

16.6.2 Initialization Strategies

16.6.3 Convergence Criteria

16.7 Support Vector Machines — Core Concept

16.7.1 The Classification Problem

16.7.2 Which Line Is Best?

16.7.3 Decision Boundary, Margin, and Support Vectors

16.7.4 SVM as an Optimization Problem

16.7.5 Hard Margin vs. Soft Margin

16.8 SVM — Mathematical Formulation

16.8.1 Setup and Notation

16.8.2 Hyperplane Equations

16.8.3 The Normal Vector

16.8.4 Deriving the Margin Size

16.8.5 The Optimization Problem (Primal Form)

16.8.6 Symbol Registry — Linear SVM

16.9 From Primal to Dual — The Lagrangian Approach

16.9.1 Why Convert to a Dual Problem?

16.9.2 Lagrangian Function

16.9.3 KKT Conditions and Stationarity

16.9.4 The Dual Problem

16.9.5 Why the Dual Is More Efficient

16.9.6 The Classification Function

16.10 SVM — Worked Example

16.10.1 Problem Setup

16.10.2 Step 1 — Write the System of Linear Equations

16.10.3 Step 2 — Solve the System of Linear Equations

16.10.4 Step 3 — Compute w and b

16.10.5 Step 4 — Write the Decision Boundary

16.10.6 Interpretation

16.11 Student Questions and Answers

16.12 Exam Guidance

16.12.1 Mark Distribution

16.12.2 Problem Types

16.12.3 What to Know (and What Not To)

16.12.4 Study Advice

16.13 Key Industry Applications and Real-World Connections

16.14 Professor Pedagogical Highlights

ML Lecture 16 notes · Gaussian Mixture Models and Support Vector Machines

Sections Breakdown

Exam Revision Notes

Gaussian Mixture Models — Soft Clustering and Mixture Concept

Expectation-Maximization Algorithm for GMM

GMM Worked Example — 4-Point Dataset

GMM Practical Considerations — Choosing K, Initialization, and Convergence

Support Vector Machines — Margin Maximization Concept

SVM Mathematical Formulation — Primal Problem

SVM Lagrangian Dual — From Primal to Dual

SVM Worked Example — 3-Point Dataset with Bias Column

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

16.6.1 Choosing the Number of Components $K$

16.10.4 Step 3 — Compute $w$ and $b$