Unsupervised Learning

What is Unsupervised learning in machine learning?

Unsupervised learning is a type of machine learning where the model learns patterns and structure
from data without using labeled outputs. Unlike supervised learning—where the algorithm is trained
using labeled input-output pairs—unsupervised learning only receives raw input data and tries to find
hidden relationships or groupings within it.

Key Idea

The system explores the dataset and tries to identify:

Groups or clusters of similar data points

Patterns, structures, or relationships

Dimensionality reduction (simplifying data while retaining important information)

Anomalies or outliers

No "correct answers" are provided—so the algorithm self-learns from the inherent structure of the data.

Examples of Unsupervised Learning Problems

Type Description Example Algorithms Use Cases

K-Means, Hierarchical Customer segmentation, market
Clustering Grouping similar items
clustering, DBSCAN research, document classification
Compressing data while
Dimensionality PCA, t-SNE, Data compression, visualization,
preserving key
Reduction Autoencoders feature extraction
information

Market basket analysis (e.g.,

Association Rule Discovering relationships
Apriori, FP-Growth "people who buy bread also buy
Mining between variables
butter")

Anomaly Identifying unusual data Isolation Forest, One-

Fraud detection, fault detection
Detection points Class SVM

Why Use Unsupervised Learning?

Labels are expensive or difficult to obtain.

Data exploration is required to uncover structure.

Helps prepare data for supervised learning by extracting meaningful features.

Real-World Examples

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 1/63
 Netflix / Spotify recommendations based on similarity patterns.
Customer segmentation for targeted marketing.

Face recognition embedding (converting faces into numerical vectors).

Fraud detection by identifying unusual transaction patterns.

Advantages

✔ Works without labeled data

✔ Useful for discovering unknown patterns
✔ Reduces complexity through feature extraction
Limitations

✖ Hard to evaluate performance (no ground truth)

✖ Results may be less precise
✖ Interpretation of clusters may require domain expertise
Simple Example

Suppose a dataset contains customer purchase history but no labels like "type of customer."
A clustering algorithm (like K-Means) may form groups:

Cluster 1: Low-income, low spending

Cluster 2: Medium-income, medium spending

Cluster 3: High-income, high spending

These labels emerge after the model groups similar users.

Summary

Unsupervised learning helps machines discover the hidden structure of unlabeled data.
It is essential for clustering, pattern mining, anomaly detection, and feature extraction
in modern AI systems.

If you'd like, I can also provide a numeric example with K-means clustering.

What is cluster? Discuss Different Types of Clustering Algorirthms

What is a Cluster?

A cluster is a group of data points in which:

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 2/63
 Data points within the same group are highly similar to each other.

Data points across different groups are dissimilar or distinct.

Similarity between data points is usually measured using a distance metric such as:

Euclidean distance
Manhattan distance

Cosine similarity

Example:
If we cluster customers based on shopping behavior:

Cluster 1 → Low-spending customers

Cluster 2 → Medium-spending customers

Cluster 3 → Premium customers

The model finds these groups without labeled supervision.

Types of Clustering Algorithms

Clustering algorithms are generally divided based on how they form clusters.

1️⃣ Partition-Based Clustering

These methods divide the dataset into a fixed number (k) of clusters.

→ K-Means Clustering

Most widely used clustering algorithm.

Starts with k random centroids and assigns data points to the nearest centroid.

Iteratively updates centroids to minimize variance.

✔ Advantages: Simple, fast

✖ Disadvantages: Requires specifying k, sensitive to outliers
→ K-Medoids (PAM)

Similar to K-means but uses actual data points (medoids) instead of centroids.
More robust against noise and outliers.

2️⃣ Hierarchical Clustering

Creates a tree-like structure (dendrogram) to represent group relationships.

→ Agglomerative (Bottom-Up)

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 3/63
 Each point begins as its own cluster.

Clusters are merged step-by-step based on similarity.

→ Divisive (Top-Down)

Starts with one large cluster and splits recursively.

✔ Advantage: No need to predefine k, interpretable

✖ Disadvantage: Computationally expensive for large datasets
3️⃣ Density-Based Clustering
These algorithms group data points based on dense regions in the data.

→ DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

Forms clusters based on dense areas separated by low-density regions.

Identifies noise/outliers naturally.

✔ Works well for arbitrarily shaped clusters

✖ Struggles with varying densities
→ OPTICS (Ordering Points To Identify Clustering Structure)

Extension of DBSCAN that handles datasets with varying density.

4️⃣ Model-Based Clustering

Assumes data is generated from a statistical model.

→ Gaussian Mixture Models (GMM)

Uses probabilistic distribution rather than hard boundaries.

A data point can belong to multiple clusters with probabilities.

✔ Supports soft clustering (probabilistic)

✖ Computationally expensive
5️⃣ Grid-Based Clustering
Works by dividing the data space into a finite number of grid cells.

→ STING (Statistical Information Grid)

Summarizes data in grids and performs clustering efficiently.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 4/63
✔ Fast for large datasets
✖ Accuracy depends on grid size
6️⃣ Fuzzy Clustering
Instead of placing a point in only one cluster, it allows soft assignment.

→ Fuzzy C-Means

Each data point has a degree of belonging to multiple clusters (0–1 membership score).

✔ Useful in ambiguous or overlapping data

✖ Sensitive to noise
Comparison Summary
Method Type Example Algorithm Hard/Soft Clustering Uses
Partition-Based K-Means, K-Medoids Hard Market segmentation, quick grouping

Hierarchical Agglomerative, Divisive Hard Biological taxonomy, social clustering

Density-Based DBSCAN, OPTICS Hard Spatial data, anomaly detection
Model-Based GMM Soft Speech recognition, probabilistic grouping
Grid-Based STING Hard Very large spatial datasets
Fuzzy Fuzzy C-Means Soft Medical imaging, pattern recognition

Conclusion

Clustering is a powerful unsupervised learning technique used to discover structure in unlabeled data.
The choice of clustering algorithm depends on factors such as dataset size, noise level, shape of
clusters, and whether soft or hard clustering is needed.

If you want, I can also provide a numerical example of K-Means clustering or a visual explanation.

Discuss in detail about K-Means Clustering and Kernel-K Means Clustering

I’ll break it into two parts: K-Means first, then Kernel K-Means, and then a short comparison.

1. K-Means Clustering
1.1 Idea

K-Means is a partition-based, hard clustering algorithm that:

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 5/63
 Divides the data into K clusters.
Represents each cluster by its centroid (mean of points in that cluster).
Tries to minimize the within-cluster variance (sum of squared distances from points to their
cluster centroid).

It works best when clusters are roughly spherical and separated in Euclidean space.

1.2 Notation

Data points: x1 , x2 , … , xn
​ ​ ​ ∈ Rd
Number of clusters: K

Cluster assignments: c(i) ∈ {1, 2, … , K} is the cluster label of point xi ​

Centroid of cluster j : μj ​ ∈ Rd

1.3 Objective Function (Optimization View)

K-Means minimizes the Within-Cluster Sum of Squares (WCSS):

n
J = ∑ xi − μc(i)
2
​ ​ ​ ​ ​

i=1

Equivalently, grouped by clusters:

K
J = ∑ ∑ ∥ xi − μ j ∥
2
​ ​ ​ ​

j=1 xi ∈Cj ​ ​

where Cj is the set of points assigned to cluster j .

​

We want to find both:

The assignments c(i)

The centroids μj ​

that minimize J .

This is a hard combinatorial optimization problem, so K-Means uses an iterative heuristic.

1.4 Algorithm (Lloyd’s Algorithm)

Input: Data {xi }n

​

i=1 , number of clusters K .

​

Steps:

1. Initialization
Choose K initial centroids μ1 , … , μK . ​ ​

Common: pick K random data points as initial centroids.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 6/63
 Better: K-Means++ (chooses spread-out initial centers).
2. Assignment Step (E-step-like)

For each point xi , assign it to the nearest centroid:

​

c(i) = arg min ​ ∥ xi − μ j ∥

​ ​

j∈{1,…,K}

3. Update Step (M-step-like)

For each cluster j , recompute the centroid as the mean of its assigned points:

1
μj = ∑ xi
∣Cj ∣
​ ​ ​ ​

xi ∈Cj
​

​ ​

4. Check for Convergence

Repeat Assignment and Update steps until:

Assignments don’t change, or

Centroids stop moving significantly, or

Maximum number of iterations reached.

1.5 Why it Works (Intuition)

Assignment step minimizes J with fixed centroids.

Update step gives the best centroid (mean) for the fixed assignments (because mean minimizes
sum of squared distances).

So each iteration decreases or keeps the same objective value J .

It converges to a local minimum, not necessarily the global minimum.

1.6 Properties

Time complexity: approx. O(n ⋅ K ⋅ d ⋅ T)

where:

n: number of points
d: dimension
K : clusters
T : iterations
Hard clustering: each point belongs to exactly one cluster.

Uses Euclidean distance typically.

1.7 Advantages

Simple and easy to implement.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 7/63
 Fast and scalable for large n and moderate K .

Works well when clusters are:

roughly spherical,

similar size,

and well separated.

1.8 Limitations

Must pre-specify K.

Sensitive to:
Initialization → can get bad local minima.

Outliers and noise.

Feature scaling (need normalization).

Can only find convex / roughly spherical clusters in original space.

This is where Kernel K-Means comes in for non-linear structures.

2. Kernel K-Means Clustering

2.1 Motivation

Standard K-Means can’t handle clusters like:

Concentric circles

“Moon-shaped” clusters

Any non-linearly separable shapes

Idea:
Map data to a higher-dimensional feature space where clusters become linearly separable /
spherical and run K-Means there.
Directly mapping via ϕ(x) can be very high-dimensional or infinite-dimensional. So we use the kernel
trick.

2.2 Feature Space Formulation

Assume there is a mapping:

ϕ : Rd → F

where F is a (possibly high- or infinite-dimensional) feature space.

In feature space, we would like to run K-Means:

Feature-space points: ϕ(x1 ), ϕ(x2 ), … , ϕ(xn )

​ ​ ​

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 8/63
 Feature-space centroid for cluster j :

1
mj = ∑ ϕ(xi )
∣Cj ∣
​ ​ ​ ​

xi ∈Cj
​

​ ​

Objective in feature space:

K
Jkernel = ∑ ∑ ∥ϕ(xi ) − mj ∥
2
​ ​ ​ ​ ​

j=1 xi ∈Cj ​ ​

We never compute ϕ(x) explicitly.

Instead, we use a kernel function:

K(x, z) = ⟨ϕ(x), ϕ(z)⟩

Typical kernels:

RBF (Gaussian) kernel

Polynomial kernel
Sigmoid kernel, etc.

2.3 Distance in Feature Space via Kernel

To perform the assignment step, we need distances:

∥ϕ(xi ) − mj ∥2 ​ ​

Expand:
2
∥ϕ(xi ) − mj ∥ = ⟨ϕ(xi ) − mj , ϕ(xi ) − mj ⟩
​ ​ ​ ​ ​ ​

= ⟨ϕ(xi ), ϕ(xi )⟩ − 2⟨ϕ(xi ), mj ⟩ + ⟨mj , mj ⟩

​ ​

​ ​ ​ ​ ​ ​

Now, express each term with kernels.

1. Self-similarity:

⟨ϕ(xi ), ϕ(xi )⟩ = K(xi , xi )

​ ​ ​ ​

2. Cross-term with centroid:

⟨ϕ(xi ), mj ⟩ = ⟨ϕ(xi ), ∑ ϕ(xp )⟩ =

1 1
∑ K(xi , xp )
∣Cj ∣ ∣Cj ∣
​ ​ ​ ​ ​ ​ ​ ​ ​

xp ∈Cj xp ∈Cj
​ ​

​ ​ ​ ​

3. Centroid self-term:

⟨mj , mj ⟩ = ⟨ ∑ ϕ(xq )⟩ =
1 1 1
∑ ϕ(xp ), ∑ ∑ K(xp , xq )
∣Cj ∣ ∣Cj ∣ ∣Cj ∣2
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

xp ∈Cj xq ∈Cj xp ∈Cj xq ∈Cj

​ ​ ​

​ ​ ​ ​ ​ ​ ​ ​

So:
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 9/63
 2 1
∑ K(xi , xp ) + ∑ ∑ K(xp , xq )
2
∥ϕ(xi ) − mj ∥ = K(xi , xi ) −
∣Cj ∣ ∣Cj ∣2
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

xp ∈Cj xp ∈Cj xq ∈Cj

​ ​

​ ​ ​ ​ ​ ​

This expression requires only kernel values K(⋅, ⋅), not explicit ϕ(x).

2.4 Kernel K-Means Algorithm

Input:

Data {xi }n
i=1​ ​

Number of clusters K

Kernel function K(x, z)

Pre-compute:

Kernel matrix Kij ​ = K(xi , xj ) of size n × n

​ ​

Steps:

1. Initialization

Randomly assign each point xi to a cluster, or ​

Choose initial cluster centers (implicitly) and define initial clusters C1 , … , CK . ​ ​

2. Assignment Step

For each point xi , compute: ​

Dij = ∥ϕ(xi ) − mj ∥2
​ ​ ​

using the kernel formula above.

Assign xi to the cluster with minimum Dij .

​ ​

3. Update Step
Based on the new assignments, recompute the sets Cj and their statistics (e.g., sums over ​

kernels for each cluster).

You don’t form mj explicitly, but you update the cluster composition so that the formulas for
​

Dij use the new Cj .

​ ​

4. Check for Convergence

Repeat steps 2–3 until cluster assignments stop changing or a max iteration limit is reached.

2.5 Characteristics of Kernel K-Means

Can discover non-linearly separable clusters in input space.

More flexible than standard K-Means due to kernel choice.

But:

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 10/63
 Needs computing and storing the kernel matrix: O(n2 ) memory.

Time complexity often around O(n2 KT ), heavier than standard K-Means.

Sensitive to choice of kernel type and kernel parameters (e.g., RBF γ , polynomial degree).

3. K-Means vs Kernel K-Means (Summary)

Aspect K-Means Kernel K-Means

Space used Original data space Implicit high-dimensional feature space via ϕ(x)

Distance Euclidean distance Kernel-induced distance

Clusters Typically spherical / convex Arbitrarily shaped (depends on kernel)

Complexity O(nKdT ) O(n2 KT ) due to kernel matrix

Memory O(nd) O(n2 )
Parameters Mainly K K + kernel choice + kernel parameters
Implementation Very simple More complex due to kernel computations

Short Intuition

K-Means: “Draw K balls (spheres) in the original space and adjust them to best cover the data.”
Kernel K-Means: “First (implicitly) bend and twist the space using a kernel so that complicated
shapes become blob-like, then run K-Means in that transformed world.”

If you want, I can next give you a small numerical example showing how K-Means works step-by-step,
and then conceptually show how the same data can be separated with Kernel K-Means using an RBF
kernel.

What is K Medoid Clustering ? Explain in detail about DBSCAN

I’ll split it into two parts:

(1) K-Medoid Clustering – what it is and how it works

(2) DBSCAN – detailed explanation

1. K-Medoid Clustering
1.1 What is a Medoid?

A medoid is the most centrally located point in a cluster,

but must be one of the actual data points (unlike a centroid in K-Means, which can be any point
in space).

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 11/63
 Formally, in a cluster C , the medoid m is the point that minimizes the total dissimilarity to all
other points in the cluster:

m = arg min ∑ d(xi , xj ) ​ ​ ​ ​

xj ∈C
xi ∈C
​

where d(⋅, ⋅) is a distance (or dissimilarity) function.

1.2 What is K-Medoid Clustering?

K-Medoid clustering is a partition-based clustering method similar to K-Means, but:

It chooses K representative objects (medoids) from the dataset.

Each data point is assigned to the nearest medoid.

Clusters are formed around these medoids.
It focuses on minimizing the sum of dissimilarities between points and their cluster medoid.

Key difference vs K-Means:

K-Means: cluster center is the mean (can be outside data).

K-Medoids: cluster center is an actual data point, so it is more robust to outliers and works with
any distance metric, not just Euclidean.

1.3 Objective Function

Given:

Data points x1 , x2 , … , xn
​ ​ ​

Number of clusters K

Dissimilarity measure d(xi , xj ) ​ ​

We want to choose a set of medoids {m1 , … , mK }, each mk being some xj , to minimize:

​ ​ ​ ​

n
J = ∑ d(xi , mc(i) )
​ ​ ​

i=1

where c(i) is the index of the medoid (cluster) assigned to point xi . ​

1.4 PAM Algorithm (Partitioning Around Medoids – basic K-Medoids)

Input: data, number of clusters K .

Steps:

1. Initialization

Select K points randomly as initial medoids.

2. Assignment Step

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 12/63
 Assign each point to the nearest medoid (smallest distance).
3. Update (Swap) Step
For each medoid m and for each non-medoid point x,
try swapping: make x a medoid and m a normal point.

Compute the total cost (sum of distances to nearest medoid) after the swap.
If the swap reduces the total cost, keep it.

Repeat swaps until no swap improves the objective.

4. Convergence
When no further improving swaps are possible,
the current medoids and assignments define the final clustering.

1.5 Advantages and Disadvantages

Advantages:

More robust to outliers than K-Means (because medoids are real points).
Works with any distance metric: Euclidean, Manhattan, edit distance, etc.

Good for clustering non-numeric or categorical data (where a mean is not meaningful).

Disadvantages:

Classic PAM has higher computational cost than K-Means (because of many swap evaluations).
Still needs K to be specified.
Can be slow on very large datasets (but there are faster variants like CLARA, CLARANS).

2. DBSCAN – Density-Based Spatial Clustering of Applications

with Noise
Now the second part: DBSCAN, a density-based clustering algorithm.

2.1 Intuition

DBSCAN forms clusters as areas of high point density separated by areas of low density.
It’s great for:

Arbitrarily shaped clusters (not just spherical),

Handling noise and outliers naturally,
Not needing to pre-specify the number of clusters K .

Instead, it uses two parameters:

ε (eps): radius of the neighborhood,

minPts: minimum number of points required to form a dense region.
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 13/63
2.2 Key Concepts and Definitions

Given:

A distance function d(xi , xj ) (usually Euclidean),

​ ​

Parameters ε and minPts.

For a point p:

1. ε-neighborhood of p:

Nε (p) = {q ∣ d(p, q) ≤ ε}
​

2. Core Point:
A point p is a core point if:

∣Nε (p)∣ ≥ minPts

​

i.e., there are enough points around it within radius ε.

3. Border Point:

A point p is a border point if:

It is not a core point, but

It lies within the ε-neighborhood of a core point.

4. Noise Point (Outlier):

A point that is neither a core point nor a border point.

It doesn’t belong to any cluster.

5. Directly Density-Reachable:
A point q is directly density-reachable from p if:

p is a core point, and

q ∈ Nε (p).
​

6. Density-Reachable:

A point q is density-reachable from p if there exists a chain:

p = p1 , p2 , … , pk = q
​ ​ ​

such that each pi+1 is directly density-reachable from pi .

​ ​

Important: density-reachability is not symmetric.

7. Density-Connected:

Two points p and q are density-connected if there exists a point o such that:

Both p and q are density-reachable from o.

This is symmetric and is how clusters are defined.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 14/63
2.3 Algorithm Steps of DBSCAN

Input: data points, parameters ε and minPts.

1. Label all points as UNVISITED.

2. For each point p:

If p is UNVISITED:

Mark p as VISITED.

Compute its ε-neighborhood Nε (p). ​

Case 1: |Nε(p)| < minPts

→ Mark p as NOISE (may later change to border if it becomes reachable from a core point).

Case 2: |Nε(p)| ≥ minPts

→ p is a CORE point.

Start a new cluster, say Cluster C.

Add p to C.

Put all points in Nε (p) into a queue or list Seeds.

​

While Seeds is not empty:

Take a point q from Seeds.

If q is UNVISITED:

Mark q as VISITED.

Compute Nε (q). ​

If ∣Nε (q)∣
​
≥ minPts (i.e., q is core):
Add all points of Nε (q) to Seeds (if not already in cluster).
​

If q is not yet in any cluster, add q to cluster C.

3. Continue until all points are processed (visited).

Result: a set of clusters + some noise points.

2.4 Characteristics

No need for K: DBSCAN automatically determines the number of clusters based on density.
Can find arbitrary shapes: e.g., crescent-moon, rings, nested shapes, etc.

Handles noise/outliers: Noise points are simply left unclustered.

Time complexity:

Naive: O(n2 ) if every neighborhood query scans all points.

With spatial indexing (k-d trees, R-trees, etc.): can be closer to O(n log n).

2.5 Choosing ε and minPts (Idea)

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 15/63
 minPts:
Common rule of thumb: minPts ≥ dimensionality + 1.
Often set to something like 4–10 as a starting point.

ε (eps):
Use a k-distance plot:
For each point, compute distance to its k-th nearest neighbor (k = minPts − 1).

Sort these distances and plot them.

Look for a “knee/elbow” in the plot – that value is a good ε.

(You don’t need to calculate this in exam answers, but explaining this process shows understanding.)

2.6 Advantages of DBSCAN

1. Does not require specifying number of clusters in advance.

2. Can find arbitrary-shaped clusters.
3. Naturally identifies noise/outliers.

4. Works well for spatial data (e.g., geography, location clusters).

2.7 Limitations of DBSCAN

1. Parameter sensitivity:
Choosing ε and minPts is non-trivial, especially for high-dimensional data.
2. Varying density problem:

If clusters have very different densities, a single ε and minPts may not work for all.
3. High-dimensional data:

Distance measures become less meaningful (“curse of dimensionality”), making density

estimation hard.

2.8 K-Medoids vs DBSCAN (Quick Comparison)

Aspect K-Medoids DBSCAN

Requires K? Yes, must give number of clusters No, clusters determined automatically
Shape of clusters Usually compact, “ball-like” Arbitrary shapes

Outliers handling Robust but still assigns each point to a cluster Explicitly marks some points as noise
Distance metric Any dissimilarity measure Any distance, but sensitive to choice
Parameters K (number of medoids) ε (radius), minPts

If you want, I can next give you a small conceptual example showing:

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 16/63
 how DBSCAN forms clusters around dense regions and marks some points as noise,
or a comparison example where K-Medoids fails on non-spherical shapes but DBSCAN succeeds.

Discuss in detail about Dimensionality Reduction in unsupervised learning

Dimensionality reduction is about taking data with many features (high-dimensional) and
representing it with fewer, more informative features—without losing too much important
information. In unsupervised learning, this is done without class labels; the algorithm relies only on
the structure of the input data.

1. Why Do We Need Dimensionality Reduction?

Suppose each data point is

xi ∈ R D
​

with large D (e.g., 100, 1000, or more). High dimensionality causes several problems:

1. Curse of dimensionality
Distance measures become less meaningful as dimensions grow.

Points tend to look equally far from each other.

Algorithms like K-Means, KNN, clustering, etc. become less effective.
2. Computational cost

More dimensions → more memory and slower algorithms.

3. Overfitting
Many irrelevant/redundant features can confuse models.

4. Visualization
We can’t visualize data directly in more than 3D.
Dimensionality reduction lets us get 2D/3D embeddings for visualization.

So, dimensionality reduction transforms:

xi ∈ R D → z i ∈ R d ,
​ ​ d≪D

2. Two Main Approaches

(A) Feature Selection (still unsupervised, but less common here)

Choose a subset of the original features.

Unsupervised methods may use:

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 17/63
 Variance-based selection (drop low-variance features).
Correlation-based selection (remove highly correlated/duplicate features).

(B) Feature Extraction (most common in unsupervised DR)

Create new features as combinations of original ones.

Example:

z1 = a11 x1 + a12 x2 + ⋯ + a1D xD

​ ​ ​ ​ ​ ​ ​

Methods: PCA, Kernel PCA, t-SNE, UMAP, Autoencoders, etc.

Most exam discussions of dimensionality reduction focus on feature extraction, especially PCA.

3. Linear Dimensionality Reduction: Principal Component

Analysis (PCA)
3.1 Idea

PCA finds new axes (directions) in the data such that:

The first principal component (PC1) captures the maximum variance.

The second principal component (PC2) captures the maximum remaining variance, subject to
being orthogonal to PC1.
And so on.

We reduce dimension by keeping only the first few principal components.

3.2 Data Setup

Suppose we have n data points:

x1 , x2 , ..., xn ∈ RD
​ ​ ​

Stack them into a data matrix:

− x⊤
1 ​ −
− x⊤
2 ​ −
X= ​ ​ ​ ​ ​ of size n × D
⋮
− x⊤
n ​
−

3.3 Steps of PCA

1. Standardize / Center the data

Compute mean:

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 18/63
 n
1
μ = ∑ xi ​ ​

n
i=1
Center each point:

~ =x −μ
x​

i i ​

~
Let X be the matrix of centered data.
2. Compute covariance matrix

1 ~⊤ ~
Σ= X X​ (D × D)
n
3. Eigen-decomposition
Find eigenvalues λ1 ​ ≥ λ2 ≥ ⋯ ≥ λD and corresponding eigenvectors v1 , v2 , … , vD such
​ ​ ​ ​ ​

that:

Σvj = λj vj
​ ​ ​

Each eigenvector = direction in feature space.

Each eigenvalue = variance along that direction.

4. Select top d components

Choose first d eigenvectors:

W = [v1 , v2 , ..., vd ] (D × d)
​ ​ ​

5. Project data onto new space

Low-dimensional representation:

​
~ i ∈ Rd
zi = W ⊤ x ​

So the original D -dimensional data is now represented in d-dimensional space.

3.4 Properties of PCA

Unsupervised: uses only data covariance, no labels.

Linear: new dimensions are linear combinations of original features.

Orthogonal components: principal components are mutually perpendicular directions.

Variance maximization: keeps the directions with greatest variance → assumes high variance =
important information.

Often used for:

Preprocessing before clustering,
Noise reduction,

Visualization (2D, 3D plots).

4. Other Linear Methods (Brief)

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 19/63
4.1 Factor Analysis

Similar to PCA but assumes a probabilistic model where observed variables are generated from a
few latent factors + noise.
Focuses more on explaining covariance structure than just variance.

4.2 Independent Component Analysis (ICA)

Tries to find components that are statistically independent, not just uncorrelated.
Used in signal separation (e.g., separating voices in an audio mixture).

(These may or may not be in your syllabus, but good to name them.)

5. Nonlinear Dimensionality Reduction (Manifold Learning)

Sometimes data lies on a nonlinear low-dimensional manifold inside high-dimensional space. Linear
methods like PCA may fail to capture this structure.

5.1 Manifold Hypothesis

High-dimensional data (like images, text embeddings, etc.) often live on a low-dimensional curved
surface (manifold) inside the high-dimensional space.

Goal: Uncover this manifold and represent data using a few coordinates.
Common nonlinear DR methods:

5.2 t-SNE (t-Distributed Stochastic Neighbor Embedding)

Used mainly for visualization (2D/3D).

Idea:

For each pair of points in high-dimensional space, define a probability that they are neighbors
(using Gaussian distributions).
Find low-dimensional points such that their pairwise neighbor probabilities match, using a Student
t-distribution in low-dimensional space.
Optimizes a Kullback–Leibler divergence between high- and low-dimensional distributions.

Characteristics:

Excellent for visualizing clusters.

Preserves local structure (neighbors) better than global distances.

Not ideal as a general-purpose feature extractor for other algorithms (more for visualization).

5.3 Isomap (Isometric Mapping)

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 20/63
Idea:

Build a nearest-neighbor graph.

Approximate geodesic distances (distances along the manifold) between all pairs of points using
shortest paths on this graph.
Apply classical MDS (multidimensional scaling) to these geodesic distances to get low-
dimensional coordinates.

Good for:

Manifolds where geodesic distances capture the true structure (e.g., Swiss-roll dataset).

5.4 Locally Linear Embedding (LLE)

Idea:

1. For each point, find its k nearest neighbors.

2. Represent each point as a linear combination of its neighbors, solving for weights wij .​

3. In low-dimensional space, find points that preserve these reconstruction weights as much as
possible.

Goal: Preserve local linear relationships from high to low dimension.

5.5 UMAP (Uniform Manifold Approximation and Projection)

Builds a fuzzy topological representation of the high-dimensional data.

Optimizes a low-dimensional embedding that preserves local neighborhood structure.

Faster and often better at preserving both local and some global structure than t-SNE (in practice).

6. Autoencoders (Neural Network–based Dimensionality

Reduction)
Autoencoders are neural networks trained to reconstruct their input.
Structure:

Encoder:
x → z (maps input to low-dimensional latent code).
Decoder:
z→x ^ (reconstructs input from latent code).

The network is trained to minimize reconstruction error:

L = ∑ ∥xi − x
^ i ∥2
​ ​ ​

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 21/63
If the latent layer z has dimension d ≪ D, the encoder learns a compressed representation →
unsupervised dimensionality reduction.

Variants:

Denoising autoencoders (learn robust representations),

Variational autoencoders (VAEs) (probabilistic latent variables).

7. Role of Dimensionality Reduction in Unsupervised Learning

Dimensionality reduction is itself an unsupervised learning task, and it also supports other
unsupervised tasks:

1. Preprocessing for clustering

Apply PCA or another method first → then run K-Means / DBSCAN on reduced data.
Helps remove noise and redundant features.
2. Visualization

Use PCA / t-SNE / UMAP to plot data in 2D/3D and inspect natural groupings.
3. Noise filtering
Drop low-variance principal components in PCA to remove noise.

4. Feature learning
Autoencoders / deep representation learning discover compact, meaningful latent features.

8. Advantages and Limitations of Dimensionality Reduction

Advantages

Reduces storage and computation.

Can improve performance of clustering and other unsupervised methods.

Helps visualize high-dimensional data.
Reduces overfitting by removing redundant / noisy features.

Limitations

Information is inevitably lost when compressing.

Some methods (PCA) only capture linear relationships.

Nonlinear methods (t-SNE, Isomap, LLE, UMAP) can be:

Computationally heavier,
Sensitive to hyperparameters,
Less interpretable.
Results can be hard to interpret in original feature terms (especially for PCA/autoencoders).

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 22/63
If you’d like, next I can:

Work through a small numerical example of PCA (with actual numbers), or

Explain how PCA + K-Means are combined in practice for better clustering.

Discuss in detail about PCA . Explain the Steps . Give an example

PCA is one of the most important topics, so let’s do it properly:

what PCA is
its intuition
the step-by-step algorithm

a small numerical example

1. What is PCA?
Principal Component Analysis (PCA) is a linear dimensionality reduction technique.
It:

Takes data with many possibly correlated features.

Finds new orthogonal axes (principal components).
Orders these axes so that:
PC1 captures the maximum variance,
PC2 captures the maximum remaining variance, and so on.
Then we keep only the first few components to reduce dimension.

So PCA transforms:

x ∈ RD ⟶ z ∈ Rd , d ≪ D

by projecting data onto the top d principal components.

Intuition: PCA finds the directions in which the data “spreads out” the most and uses those as
new axes.

2. Mathematical Intuition
2.1 Data Setup

We have n data points:

D
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 23/63
 x1 , x2 , … , xn ∈ R D
​ ​ ​

Stack them row-wise into a matrix:

− x⊤
1 ​ −
− x⊤
2 ​ −
X= ​ ​ ​ ​ ​ (n × D)
⋮
− x⊤
n ​ −

2.2 Principal Component (PC1) as an Optimization Problem

We want a direction (unit vector) w ∈ RD such that the variance of the data projected on w is
maximum.
Projection of point xi on w is:
​

z i = w ⊤ xi
​ ​

Variance of these projections is:

Var(z) = w⊤ Σw

where Σ is the covariance matrix of the data.

PCA solves:

max ​ w⊤ Σw subject to ∥w∥ = 1

w

This is a standard problem; solution:

w is the eigenvector of Σ corresponding to the largest eigenvalue.

That eigenvalue is the maximum variance along that direction.

Similarly, PC2 is the eigenvector with second largest eigenvalue, orthogonal to PC1, and so on.
So PCA = eigen-decomposition of the covariance matrix.

3. Steps of PCA (Algorithm)

Assume we want to reduce from D dimensions to d dimensions (d < D).

Step 1: Organize the data

Write the data as an n × D matrix X (each row = one sample, each column = one feature).

Step 2: Mean-centering (and often scaling)

Compute the mean of each feature:

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 24/63
 n
1
μ = ∑ xi ​ ​ ​ (μ ∈ RD )
n
i=1

Subtract the mean from each data point:

~ =x −μ
x i i​ ​

~
Let X be the matrix of centered data.

(Sometimes we also divide by standard deviation of each feature → standardization.)

Step 3: Compute the covariance matrix

Covariance matrix (for centered data) is:

1 ~⊤ ~
Σ= X X ​
(D × D)
n
Element Σjk is the covariance between feature j and feature k .
​

Step 4: Eigen-decomposition of covariance matrix

Find eigenvalues and eigenvectors of Σ:

Σvj = λj vj ​ ​ ​

You get:

Eigenvalues: λ1 ​
≥ λ2 ≥ ⋯ ≥ λD
​ ​

Eigenvectors: v1 , v2 , … , vD
​ ​ ​

Each eigenvector vj is a principal component direction.

​

Each eigenvalue λj is the variance captured along that component.

​

Step 5: Choose number of components d

Common ways:

Fix d (e.g., from 100D to 2D).

Or choose smallest d such that:

\frac{\lambda_1 + \dots + \lambda_d}{\lambda_1 + \dots + \lambda_D} \ge \text{desired variance
threshold (e.g., 90% or 95%)}

Step 6: Form projection matrix and transform the data

Take the top d eigenvectors:

W = [v1 v2 … vd ] (D × d)
​ ​ ​

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 25/63
Project each centered data point:

​
~i
zi = W ⊤ x ​ ∈ Rd

Matrix form:
~
Z = XW (n × d)

This Z is the low-dimensional representation of your data.

4. Worked Numerical Example (Small 2D → 1D PCA)

Let’s take a tiny dataset with 4 points in 2D:

x1 = (2, 0),
​ x2 = (0, 2),
​ x3 = (3, 1),
​ x4 = (1, 3)
​

We want to reduce from 2D to 1D with PCA.

Step 1: Data matrix

2 0
0 2
X=
3 1
​ ​ ​ ​

1 3

Step 2: Compute mean and center the data

Feature-wise mean:

1 1
μ= [(2 + 0 + 3 + 1), (0 + 2 + 1 + 3)] = [6, 6] = (1.5, 1.5)
4 4
​ ​

Subtract mean from each point:

~1 = (2 − 1.5, 0 − 1.5) = (0.5, −1.5)

x ​

~ = (0 − 1.5, 2 − 1.5) = (−1.5, 0.5)

x 2
​

~ = (3 − 1.5, 1 − 1.5) = (1.5, −0.5)

x 3
​

~ = (1 − 1.5, 3 − 1.5) = (−0.5, 1.5)

x 4
​

~
Centered data matrix X :

0.5 −1.5
~ −1.5 0.5
X=
1.5 −0.5
​ ​ ​ ​

−0.5 1.5

Step 3: Covariance matrix

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 26/63
 1 ~⊤ ~
Σ= ​
X X
n
~ ~
Compute X ⊤ X (you don’t have to do all multiplications in an exam, but let’s state the result):

1.25 −0.75
Σ=[ ]
−0.75 1.25
​ ​

Step 4: Eigenvalues and eigenvectors

Solve:

Σv = λv

Eigenvalues (variances along PCs):

λ1 = 2.0
​

λ2 = 0.5
​

Eigenvectors (principal directions):

For λ1 ​
= 2.0:
1
v1 = (1, −1)⊤ ≈ (0.707, −0.707)
2
​ ​

For λ2 ​ = 0.5:
1
v2 = (1, 1)⊤ ≈ (0.707, 0.707)
2
​ ​

So:

PC1 direction: along line y = −x (major variance).

PC2 direction: along line y = x (minor variance).

Step 5: Choose components

We want to reduce to 1D, so we keep only PC1 (the eigenvector with largest eigenvalue).
Projection matrix:

0.707
W = v1 = [ ]
−0.707
​ ​

Step 6: Project data onto PC1

~ , compute:
For each centered point x i ​

~
zi = W ⊤ x
​

i ​

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 27/63
Example for x1 : ​

0.5
z1 = [0.707 −0.707] [ ] = 0.707(0.5) + (−0.707)(−1.5) ≈ 0.3535 + 1.0607 ≈ 1.414
−1.5
​ ​ ​ ​

Similarly, you get (numerically):

z1 ≈ 1.414,
​
z2 ≈ −1.414,
​
z3 ≈ 1.414,
​
z4 ≈ −1.414
​

So all 4 points in 2D are mapped to 1D values on a line:

x1 , x3 → positive side,
​ ​

x2 , x4 → negative side.
​ ​

We have compressed from 2D to 1D, keeping the direction that captures maximum variance (2.0 vs
0.5).

5. Summary (Exam-Friendly)
PCA is an unsupervised linear dimensionality reduction method.
It finds principal components (eigenvectors of covariance matrix) along which data variance is
maximized.
Steps:

1. Arrange data into matrix.

2. Center (and optionally standardize) the data.
3. Compute covariance matrix.
4. Do eigen-decomposition to get eigenvalues and eigenvectors.
5. Choose top d eigenvectors based on eigenvalues (explained variance).

6. Project data onto these eigenvectors to get reduced representation.

Used for:
Dimensionality reduction,
Noise reduction,
Visualization,
Preprocessing before clustering or other ML algorithms.

If you want, I can next show how PCA + K-Means can be combined on a dataset, or give you a short
bullet-note version suitable for writing directly in exams.

What is Kernel PCA. Explain with example

Kernel PCA (Principal Component Analysis)

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 28/63
Kernel PCA is an extension of standard PCA that allows dimensionality reduction on datasets that are
non-linearly separable. Unlike traditional PCA—which works only with linear relationships—Kernel
PCA uses a kernel function to project data into a higher-dimensional feature space where linear
separation becomes possible.
In simple terms:

Kernel PCA = PCA performed in a high-dimensional feature space using the kernel trick
(without explicitly computing that space).

Why Kernel PCA? (Motivation)

Standard PCA works well when data has a linear structure. But if data lies on a curved manifold (like
concentric circles or a moons dataset), PCA fails because no straight linear axis can explain variance
effectively.

Example (visual intuition):

PCA cannot separate classes shaped like circles or spirals.

Kernel PCA can unfold such data into a linearly separable form.

Mathematical Idea Behind Kernel PCA

In normal PCA, we compute eigenvectors of the covariance matrix:

1 T
Σ= ​X X
N
Kernel PCA works differently:

1. Feature Mapping

We assume there exists a nonlinear mapping:

ϕ : Rd → Rm (m ≫ d)

But computing ϕ(x) directly may be expensive or impossible.

2. Kernel Trick

Instead of computing ϕ(x), we use a kernel function:

K(xi , xj ) = ⟨ϕ(xi ), ϕ(xj )⟩

​ ​ ​ ​

Most common kernels:

Kernel Formula Use Case

Polynomial (xT y + c)p Polynomial patterns

∥x−y∥2
RBF (Gaussian) e− 2σ 2
​

Highly non-linear patterns

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 29/63
 Kernel Formula Use Case

Sigmoid tanh(αxT y + c) Neural network-like structure

3. Kernel Matrix

Compute kernel matrix K :

Kij = K(xi , xj ) (N × N )
​ ​ ​

Then center the kernel matrix:

~
K = K − 1N K − K1N + 1N K 1N
​ ​ ​ ​

1
(where 1N ​ = N
11T ).
​

4. Eigenvalue Decomposition

Perform eigen-decomposition on the centered kernel matrix:

~
K v = λv

Eigenvectors v are the principal components in feature space.

5. Projection of New Points

Projection of a new point x onto principal component k :

N
zk (x) = ∑ vi K(x, xi )
(k)
​ ​ ​ ​

i=1

So, PCA is performed without ever computing ϕ(x).

✔ Example: Kernel PCA on Circular Data

Consider 4 two-dimensional points arranged in a circular pattern:

(1, 0), (0, 1), (−1, 0), (0, −1)

These points cannot be separated linearly (standard PCA would give nearly zero useful direction).

Step 1: Choose a Kernel

Use RBF kernel:

∥xi −xj ∥2
−
​ ​

K(xi , xj ) = e
​ ​
2σ 2
​

Assume σ = 1.
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 30/63
Compute pairwise distances and kernel values.
Example pairs:

Distance between (1, 0) and (0, 1):

(1 − 0)2 + (0 − 1)2 = ​ 2 ​

Kernel value:
2
e− 2 = e−1 ≈ 0.3679
​

If two points are identical → K = 1.

So approximate kernel matrix:

1 0.3679 e−4 0.3679

0.3679 1 0.3679 e−4
K≈
e−4 0.3679 1 0.3679
​ ​ ​ ​ ​ ​

−4
0.3679 e 0.3679 1

(where e−4 ≈ 0.0183)

Step 2: Center the Kernel Matrix

Apply kernel centering formula.

Step 3: Compute Eigenvalues & Eigenvectors

After eigen-decomposition, you may get:

λ1 = 1.9
​

λ2 = 1.8
​

λ3 = 0.01
​

λ4 = 0.001
​

Top two eigenvalues capture almost all information → projection dimension = 2.

Step 4: Project the Data

Each transformed value is computed as:

zk (xi ) = ∑ vj K (xi , xj )
(k)
​ ​ ​ ​ ​

After projection, points become linearly separable in new space.

Advantages of Kernel PCA

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 31/63
✔ Can reveal nonlinear structure.
✔ Works well in pattern recognition (face recognition, anomaly detection).
✔ Flexible: Kernel choice allows tuning behavior.
Limitations
✖ Computationally expensive (O(N ) memory for kernel matrix).
2

✖ Must choose kernel function and hyperparameters (nontrivial).

✖ Results harder to interpret compared to linear PCA.
Applications of Kernel PCA
Image denoising

Face recognition
Bioinformatics (gene data)
Nonlinear clustering preprocessing
Anomaly detection

Summary (Exam-Ready)

Kernel PCA is a nonlinear dimensionality reduction technique that uses kernel functions to
compute principal components in a high-dimensional feature space without computing the
mapping explicitly. It overcomes the limitations of standard PCA by capturing nonlinear
structures in data using the kernel trick.

If you'd like, I can also provide:

📌 a handwritten-style short answer

📌 or comparison table between PCA vs Kernel PCA.

Discuss in detail about Matrix Factorization in Unsupervised Learning . Explain the mathematical
preliminaries with examples

Matrix factorization in unsupervised learning is basically about breaking a big data matrix into the
product of two (or more) smaller matrices so that:

Data ≈ Low-dimensional representation × Basis / Features

It is a core idea behind:

Dimensionality reduction
Topic modeling

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 32/63
 Recommendation systems
Representation learning (latent factors)

Let’s go step by step.

1. Basic Setup
Suppose you have a data matrix:

X ∈ Rm×n

Rows = objects (users, documents, images, etc.)

Columns = features (items, words, pixels, etc.)

Matrix factorization aims to find two matrices:

X ≈ WH

where:

W ∈ Rm×k
H ∈ Rk×n
k is much smaller than m, n → low-rank approximation

Interpretation:

Each row of W = low-dimensional representation / latent vector of a data point (like hidden
factors).
Each column of H = how each original feature is built from latent factors.

This is unsupervised because we don’t use labels; we only exploit structure in X .

2. Mathematical Preliminaries
2.1 Rank and Low-Rank Approximation

The rank of a matrix X is the dimension of the space spanned by its rows or columns.

If X has (approximate) low rank k , then we can write:

X ≈ WH

with W and H of inner dimension k .

We usually choose W , H to minimize a reconstruction error, e.g.:

min ∥X − W H∥2F
​ ​

W ,H

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 33/63
where ∥ ⋅ ∥F is the Frobenius norm (like Euclidean norm for matrices):
​

∥X∥2F = ∑ x2ij
​ ​ ​

i,j

2.2 Singular Value Decomposition (SVD) – Core Theorem

For any real matrix X ∈ Rm×n , SVD says:

X = U ΣV ⊤

where:

U ∈ Rm×m is orthogonal (U ⊤ U = I ),
V ∈ Rn×n is orthogonal,
Σ is diagonal (m × n) with non-negative singular values σ1 ≥ σ2 ≥ ⋯ ≥ 0. ​ ​

Low-rank approximation:
If we keep only the top k singular values:

X ≈ Uk Σk Vk⊤
​ ​ ​

this is the best rank-k approximation of X (in Frobenius norm).

Here:

Uk = first k columns of U ,
​

Vk = first k columns of V ,
​

Σk = k × k diagonal matrix with top k singular values.

​

We can interpret:

1/2
W = U k Σk ​ ​

1/2
H = Σk Vk⊤ ​ ​

so that:

X ≈ WH

3. Types of Matrix Factorization in Unsupervised Learning

3.1 SVD / Low-Rank Approximation

Used for:

Latent Semantic Analysis (LSA) in text (documents vs. words matrix).

Basic dimensionality reduction.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 34/63
Objective:

min ​ ∥X − M ∥2F ​

rank(M )≤k

Solution: truncate SVD.

3.2 Non-negative Matrix Factorization (NMF)

If X has non-negative entries (e.g., term frequencies, ratings), we often want:

X ≈ W H, with W ≥ 0, H ≥ 0 (elementwise)

W : basis vectors (e.g., topics in documents)

H : coefficients (how strongly each data point uses each basis)

Objective:

min ​ ∥X − W H∥2F ​

W ≥0,H≥0

or sometimes a divergence like KL-divergence.

The non-negativity leads to parts-based, additive representations (very interpretable).

3.3 Matrix Factorization for Recommendations (Collaborative Filtering)

In recommender systems, we often have a (sparse) user–item rating matrix R:

Rui = rating of user u on item i, many are missing.

​

We approximate:

R ≈ UV ⊤

where:

U \in \mathbb{R}^{\text{(#users)} \times k}: user latent factors

V \in \mathbb{R}^{\text{(#items)} \times k}: item latent factors

Predicted rating:

^ ui = u⊤ vi
R u ​ ​ ​

Typical objective (only over observed entries (u, i) ∈ Ω):

min ∑ (Rui − u⊤ 2 2 2
​

u vi ) + λ (∥U ∥F + ∥V ∥F )
​ ​ ​ ​ ​ ​

U ,V
(u,i)∈Ω

This is also unsupervised w.r.t external labels (we only have interactions).

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 35/63
4. Detailed Example – Small NMF / Low-Rank Factorization
Let’s take a simple document–word matrix as an example.
Suppose we have 3 documents and 4 words:

Words:
w1 ​ = “apple”
w2 ​ = “banana”
w3 ​ = “football”
w4 ​
= “cricket”

Term-frequency matrix X ∈ R3×4 :

3 2 0 0
X= 4 3 0 0 ​ ​ ​ ​ ​ ​

0 0 5 4

We can see:

Doc 1 & 2 are about fruits,

Doc 3 is about sports.

We expect 2 latent topics: Topic 1 = fruits, Topic 2 = sports → choose k = 2.

We want:

X ≈ WH

with:

W ∈ R3×2 : document–topic matrix

H ∈ R2×4 : topic–word matrix

One possible approximate factorization (values illustrative):

1 0
3 2 0 0
W ≈ 1.2 0 , H≈[ ]
0 0 3 2.5
​ ​ ​ ​ ​ ​ ​ ​

0 1.5

Then:

1 0 3 2 0 0
3 2 0 0
W H ≈ 1.2 0 [ ] = 3.6 2.4 0 0
0 0 3 2.5
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

0 1.5 0 0 4.5 3.75

Compare with X :

3 2 0 0
X= 4 3 0 0 ​ ​ ​ ​ ​ ​

0 0 5 4

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 36/63
The approximation is close:

First two docs strong on Topic 1 (fruits).

Third doc strong on Topic 2 (sports).
Topics:

Topic 1 → “apple”, “banana”

Topic 2 → “football”, “cricket”

This illustrates how matrix factorization can discover hidden structure (topics) without labels.

5. Optimization Perspective
General form in unsupervised matrix factorization:

min L(X, W H) + regularization

​

W ,H

Where L could be:

Squared loss: ∥X − W H∥2F ​

KL-divergence or other divergences.

Gradient-based updates or multiplicative update rules are used (for NMF):

Example (classic multiplicative updates for NMF with Frobenius loss):

W ⊤X
H←H⊙
W ⊤W H
​

XH ⊤
W ←W ⊙
W HH ⊤
​

(Here ⊙ is elementwise multiplication, and the divisions are elementwise.)

These updates preserve non-negativity and iteratively reduce reconstruction error.

6. Role of Matrix Factorization in Unsupervised Learning

1. Dimensionality Reduction / Latent Representations

Compress high-dimensional data into k -dimensional codes (rows of W ), similar to PCA but
often more interpretable (NMF).
2. Clustering
The low-dimensional representation can be sent to a clustering algorithm.
Sometimes, rows of W can directly indicate cluster membership (e.g., one factor dominates per
row).
3. Topic Modeling

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 37/63
 Documents vs words → topics discovered as latent factors.
4. Recommendation Systems
Users and items represented via latent factors; predictions made in latent space.
5. Noise Reduction
Low-rank approximation filters out small singular values (noise directions).

7. Summary (Exam-Friendly Points)

Definition: Matrix factorization decomposes a data matrix X into the product of low-rank matrices
W and H : X ≈ W H .
Goal: Find latent factors that explain the structure of data without labels.

Mathematical basis: Low-rank approximation, SVD, constrained optimization (e.g., non-negativity

in NMF).
Key methods:
SVD-based factorization (PCA / LSA).
Non-negative Matrix Factorization (NMF).
Factorization models in collaborative filtering (recommendations).

Example: Document–word matrix factorization reveals topics (“fruits”, “sports”) as latent factors.
Use cases: Dimensionality reduction, topic modeling, recommender systems, clustering, noise
reduction.

If you want, I can next compare PCA vs NMF vs SVD directly, or give you a short handwritten-style
version suitable to write in an exam.

Discuss the steps how to decompose a matrix in SVD method

Singular Value Decomposition (SVD) is a method of decomposing a matrix into three special matrices
that reveal important structural properties of the original matrix. For any real matrix A of size m × n,
SVD expresses it as:

A = U ΣV T

Where:

U = orthogonal matrix of size m × m, contains left singular vectors

Σ = diagonal matrix of singular values (σ1 ≥ σ2 ≥ ⋯ ≥ 0)
​ ​

V T = transpose of orthogonal matrix V , contains right singular vectors

Steps to Decompose a Matrix Using the SVD Method

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 38/63
Let the given matrix be:

Am×n ​

Step 1: Compute AT A

Calculate the matrix multiplication of the transpose and original matrix:

AT A

AT A will be an n × n symmetric and positive semi-definite matrix.

Step 2: Find Eigenvalues and Eigenvectors of AT A

Solve the characteristic equation:

∣AT A − λI∣ = 0

The eigenvalues obtained will be:

λ1 ≥ λ2 ≥ ⋯ ≥ λr > 0,
​ ​ ​
(where r = rank of A)

Also get corresponding eigenvectors v1 , v2 , … , vn .

​ ​ ​

Step 3: Construct Matrix V

Normalize eigenvectors of AT A.

Arrange them as columns to form matrix V :

∣ ∣ ∣
V = v1 ​
​
​ v2 ​
​ ⋯ vn ​
​
​ ​

∣ ∣ ∣

These are called right singular vectors.

Step 4: Compute Singular Values

Singular values σi are computed as:

​

σi = ​ λi ​ ​

Arrange them in decreasing order, forming diagonal matrix:

σ1 ​ 0 ⋯ 0
0 σ2 ​ ⋯ 0
Σ= ​ ​ ​ ​ ​ ​

⋮ ⋮ ⋱ ⋮
0 0 ⋯ σr ​

(For non-square matrices, Σ is padded with zeros to size m × n.)

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 39/63
Step 5: Compute Matrix U

Left singular vectors are obtained using:

1
ui =
​
Avi ​ ​
for i = 1, 2, … , r
σi ​

These vectors form the orthonormal matrix:

∣ ∣ ∣
U = u1 ​ ​ ​ u2 ​ ​ ⋯ um ​ ​ ​ ​

∣ ∣ ∣

Step 6: Verify Orthogonality

Ensure:

UT U = I and V T V = I

Step 7: Write the Final SVD Decomposition

Finally:

A = U ΣV T

Example: Decompose Matrix Using SVD

Let:

3 1
A=[ ]
1 3
​

Step 1: Compute AT A

3 1 3 1 10 6
AT A = [ ][ ]=[ ]
1 3 1 3 6 10
​ ​ ​ ​ ​ ​

Step 2: Find Eigenvalues

Solve:

10 − λ 6
=0
6 10 − λ
​ ​ ​ ​

(10 − λ)2 − 36 = 0

λ1 = 16, ​ λ2 = 4
​

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 40/63
Step 3: Find Singular Values

σ1 =​ 16 = 4,
​ σ2 = ​ 4=2 ​

So:

4 0
Σ=[ ]
0 2
​ ​

Step 4: Compute Eigenvectors of AT A

For λ1 ​
= 16:

(10 − 16)x + 6y = 0 ⇒ −6x + 6y = 0 ⇒ x = y

Eigenvector:

1 1
v1 = [ ]
2 1
​ ​ ​

For λ2 ​ = 4:

(10 − 4)x + 6y = 0 ⇒ 6x + 6y = 0 ⇒ x = −y

Eigenvector:

1 1
v2 = [ ]
2 −1
​ ​ ​

So:

1 1 1
V = [ ]
2 1 −1
​ ​ ​

Step 5: Compute U

1
ui = ​ Avi ​ ​

σi ​

For u1 : ​

1 1 1 1 1 4 1 1
u1 = ⋅A [ ]= ⋅ [ ]= [ ]
4 2 1 4 2 4 2 1
​ ​ ​ ​ ​ ​ ​ ​ ​

​ ​ ​

Similarly:

1 1 1 1 2 1 1
u2 = A [ ]= [ ]= [ ]
2 2 −1 2 2 −2 2 −1
​ ​ ​ ​ ​ ​ ​ ​

​ ​ ​

Thus:

[ to PDF]API.
Printed using ChatGPT to PDF, powered by PDFCrowd HTML 41/63
 1 1 1
U= [ ]
2 1 −1
​ ​ ​

Final SVD of A

1 1 1 4 0 1 1 1
A = U ΣV T = [ ][ ] [ ]
2 1 −1 0 2 2 1 −1
​ ​ ​ ​ ​ ​ ​ ​

​ ​

Summary (Exam Version)

Compute AT A.

Find eigenvalues and eigenvectors of AT A.

Singular values = square roots of eigenvalues → form Σ.

Eigenvectors → form matrix V .
1
Compute U = σi
​
Avi .
​ ​

Final decomposition:

A = U ΣV T

If you'd like, I can also give a short flowchart or handwritten-style notes version for quick
memorization.

Explain in detail about Non-negative Matrix Factorization (NMF) with mathematical preliminaries .
Give an example

Non-negative Matrix Factorization (NMF) is a matrix factorization technique where all values are
constrained to be non-negative. This makes the learned components easy to interpret as “parts” or
“additive combinations” (e.g., topics in documents, parts of faces, etc.).
I’ll cover:

1. What NMF does

2. Mathematical formulation
3. Optimization & multiplicative update rules
4. Geometric / intuitive interpretation
5. A worked example with interpretation

1. Basic Idea of NMF

Given a non-negative data matrix

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 42/63
 X ∈ Rm×n
≥0 ​

we want to approximate it as:

X ≈ WH

where:

W ∈ Rm×k
≥0 (non-negative)
​

H ∈ Rk×n
≥0 (non-negative)
​

k is the number of latent factors / components, typically k ≪ min(m, n)

Interpretation:

Each row of W : how strongly that data point uses each latent factor.

Each column of H : how each original feature is composed from the latent factors.

Because everything is non-negative:

Data ≈ (non-negative combination of parts)

This is different from PCA/SVD where components can have positive and negative values.

2. Mathematical Formulation
2.1 Objective (Euclidean/Frobenius norm)

One common formulation is:

1
min J(W , H) = ∥X − W H∥2F
2
​ ​ ​

W ≥0, H≥0

where the Frobenius norm is

m n
∥X − W H∥2F ​
= ∑ ∑(xij − (W H)ij )2
​ ​ ​ ​

i=1 j=1

subject to:

Wik ≥ 0,
​ Hkj ≥ 0 ∀i, k, j
​

2.2 Alternative objective (KL divergence)

Another common loss is generalized Kullback–Leibler divergence:

DKL (X∥W H) = ∑ (xij log − xij + (W H)ij )

xij ​

(W H)ij
​ ​ ​ ​ ​ ​

i,j

Then the optimization is:

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 43/63
 min ​ DKL (X∥W H) ​

W ≥0, H≥0

Both formulations are unsupervised: no labels, only structure in X .

3. Optimization & Multiplicative Update Rules

The problem is non-convex in (W , H) jointly, but convex in W given H and vice versa. Direct solution
in closed form is not possible, so we use iterative methods.
A famous algorithm (Lee & Seung) uses multiplicative update rules that:

Always keep W , H ≥0
Guarantee non-increase of the objective (monotonic descent)

3.1 For Euclidean (Frobenius) loss

Objective:

1
J(W , H) = ∥X − W H∥2F
2
​ ​

The multiplicative updates are:

(W ⊤ X)kj
Hkj ← Hkj ⋅
​

(W ⊤ W H)kj
​ ​ ​

(XH ⊤ )ik
Wik ← Wik ⋅
​

(W HH ⊤ )ik
​ ​ ​

All operations inside the fractions are standard matrix multiplications.

The division is elementwise.
The multiplication with Hkj or Wik is also elementwise.
​ ​

Why this preserves non-negativity?

Start with W , H having non-negative entries.

Numerator and denominator are non-negative (products and sums of non-negative terms).
So the ratio is non-negative.
Multiplying a non-negative value by a non-negative ratio gives a non-negative result.

3.2 For KL divergence loss (just for completeness)

For

DKL (X∥W H)
​

updates become:

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 44/63
 x
∑i Wik (W H)
ij ​

​ ​ ​

Hkj ← Hkj ⋅
ij ​

∑i Wik
​ ​ ​

​ ​

∑j Hkj (WxH)
ij ​

​ ​ ​

Wik ← Wik ⋅
ij ​

∑j Hkj
​ ​ ​

​ ​

(You usually don’t need exact formula in exams unless explicitly in syllabus; knowing there are different
updates for different losses is enough.)

3.3 Algorithm Outline

1. Choose rank k .

2. Initialize W , H with random non-negative values.

3. Repeat until convergence (or fixed number of iterations):

Update H using its multiplicative rule.

Update W using its multiplicative rule.

Optionally compute the reconstruction error to monitor convergence.

4. Intuition / Geometric Interpretation

Columns of X (data points) lie in the non-negative orthant (all coordinates ≥ 0).

NMF is approximating each column xj as: ​

xj ≈ W hj
​ ​

where hj is the j -th column of H .

​

W gives a set of basis vectors w1 , … , wk (columns of W ).

​ ​

Each data point is an additive combination of basis vectors, with non-negative weights given by
hj .
​

So NMF is like saying:

“Every signal is constructed by adding up a few basic parts, never subtracting.”

This leads to parts-based representation (e.g., face = nose + eyes + mouth + …).

5. Example: Topic Modeling with NMF (Numerical +

Interpretation)
Consider a tiny document–word matrix with 3 documents and 4 words:

Words:
w1 = apple
​

w2 = banana
​

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 45/63
 w3 = football
​

w4 = cricket
​

Suppose we have the term-frequency matrix:

3 2 0 0
X= 4 3 0 0 ​ ​ ​ ​ ​ ​

0 0 5 4

Interpretation:

Doc 1,2 are about fruits (apple, banana),

Doc 3 is about sports (football, cricket).

We suspect 2 latent topics, so choose k = 2.

We want:

X ≈ WH

with:

W ∈ R3×2
≥0 (document–topic matrix)
​

H ∈ R2×4
≥0 (topic–word matrix)
​

One reasonable factorization (not unique, but illustrative):

1 0
3 2 0 0
W ≈ 1.2 0 , H≈[ ]
0 0 3 2.5
​ ​ ​ ​ ​ ​ ​ ​

0 1.5

Now compute the product:

1 0 3 2 0 0
3 2 0 0
W H = 1.2 0 [ ] = 3.6 2.4 0 0 ≈X
0 0 3 2.5
​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

0 1.5 0 0 4.5 3.75

The approximation is close to X :

Doc 1: [3, 2, 0, 0]
Doc 2: [3.6, 2.4, 0, 0] (approx [4, 3, 0, 0])
Doc 3: [0, 0, 4.5, 3.75] (approx [0, 0, 5, 4])

5.1 Interpretation of H (topics)

3 2 0 0
H=[ ]
0 0 3 2.5
​ ​ ​

Topic 1 (row 1): high weights on apple (3), banana (2) → Fruit topic
Topic 2 (row 2): high weights on football (3), cricket (2.5) → Sports topic

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 46/63
5.2 Interpretation of W (document mixtures)

1 0
W = 1.2 0 ​ ​ ​ ​

0 1.5

Doc 1: strong on Topic 1, none on Topic 2 → fruit document.

Doc 2: even stronger on Topic 1, none on Topic 2 → fruit document.
Doc 3: strong on Topic 2 only → sports document.

So NMF automatically discovered topics and how each document is a mixture of them, using only the
non-negative structure of X , no labels.

6. Summary (Exam-style points)

Definition: NMF factors a non-negative matrix X into two non-negative matrices W and H , such
that X ≈ W H.
Goal: Discover latent factors or parts-based representation of data in an unsupervised way.
Mathematical formulation:

min ∥X − W H∥2F
​ ​

W ,H≥0

or minimize KL divergence.
Update rules (Euclidean loss):

W ⊤X XH ⊤
H←H⊙ , W ←W ⊙
W ⊤W H W HH ⊤
​ ​

(elementwise operations).
Interpretation:
Columns of W : basis vectors (parts, topics, components).

Columns of H (or rows): coefficients/activations.

Each data point is an additive, non-negative combination of parts.

Applications: topic modeling, image parts discovery, recommendation systems, dimensionality
reduction.

If you want, I can next give you a short one-page note version of NMF (only key formulas + bullet
points) that you can directly write in an exam.

What is Matrix completion in unsupervised learning . Explain with mathematical Examples

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 47/63
Matrix completion is an unsupervised learning technique used to recover missing entries in a partially
observed matrix by assuming that the full matrix has some underlying low-rank structure. It is widely
used in systems where only a few observations are available—such as recommendation systems, sensor
networks, bioinformatics, and image reconstruction.

1. Intuition Behind Matrix Completion

In many real-world datasets, we only observe a subset of entries. Example:

User / Movie M1 M2 M3 M4
U1 5 ? 3 ?
U2 ? 4 ? 2
U3 1 ? 2 3

Missing entries represent unknown data.

Matrix completion assumes:

Even though the matrix looks incomplete, there is an underlying pattern, and the true matrix
can be approximated by a low-rank matrix.

This assumption allows us to infer missing values instead of guessing randomly.

2. Formal Mathematical Definition

Let:

M ∈ Rm×n

be the true complete matrix, but we only observe some entries.

Define an observation operator Ω that contains indices of known entries.
We observe:

P Ω (M )
​

where:

(PΩ (M ))ij = {
Mij , (i, j) ∈ Ω
​

0, otherwise
​ ​ ​ ​

We want to find an estimate matrix X such that:

PΩ (X) = PΩ (M )
​ ​

and X has low rank.

3. Optimization Formulation

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 48/63
We want to minimize rank:

min rank(X) subject to PΩ (X) = PΩ (M )

​ ​ ​

However, rank minimization is NP-hard (computationally expensive), so we relax it using nuclear

norm minimization (a convex surrogate):

min ∥X∥∗
​ ​ subject to PΩ (X) = PΩ (M ) ​ ​

where:

min(m,n)
∥X∥∗ = ​ ∑ σi ​ ​

i=1

( sum of singular values — also called nuclear norm ).

This relaxation leads to efficient solutions.

4. Matrix Completion Using Low-Rank Factorization

Another practical approach factors the matrix as:

X = UV T

where:

U ∈ Rm×k
V ∈ Rn×k
k ≪ min(m, n)

Then solve:

min ∑ (Mij − uTi vj )2

​ ​ ​ ​ ​

U ,V
(i,j)∈Ω

This approach is widely used in recommender systems like Netflix and Amazon.

5. Worked Example
Suppose we have a partially filled matrix:

5 ? 3
M= 4 2 ? ​ ​ ​ ​ ​

? 3 4

We suspect the matrix has rank 2, so write:

M ≈ UV T

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 49/63
Let:

u1 ​ v1 ​

U = u2 ,
​
​
​ ​ V = v2
​
​
​ ​

u3 ​ v3 ​

Where each ui , vj​ ​ ∈ R2 .

We optimize:

min [(5 − uT1 v1 )2 + (3 − uT1 v3 )2 + (4 − uT2 v1 )2 + (2 − uT2 v2 )2 + (3 − uT3 v2 )2 + (4 − uT3 v3 )2 ]

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

U ,V

Using gradient-based updates (similar to collaborative filtering), we compute missing values:

Assume a resulting approximation matrix:

5 2.5 3
X= 4 2 3.2
​ ​ ​ ​ ​

3.5 3 4

Then:

M1,2 is predicted as 2.5

​

M2,3 predicted as 3.2

​

M3,1 predicted as 3.5

​

These predictions match patterns in known data because the model learned:

User 1 and User 2 share similar taste (high ratings on items 1 and 3),
Item 2 is moderately rated across users,
User 3 prefers item 4.

6. Applications of Matrix Completion

Application Example
Recommendation systems Netflix movie ratings, Amazon product scores
Image inpainting Filling corrupted or missing pixels
Bioinformatics Missing gene expression data
Sensor networks Recovering missing sensor readings
Social network analysis Missing connections inference

7. Key Advantages
✔ Handles missing data naturally
✔ Identifies hidden structure using latent factors
✔ Works well when the matrix is large but low rank
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 50/63
8. Limitations
✖ Requires enough observed entries to detect structure
✖ Assumes low-rank structure (not always true)
✖ Optimization may be costly for very large matrices
Summary (Exam-Ready)

Matrix completion is an unsupervised technique used to reconstruct missing entries in a

partially observed matrix by assuming the full matrix is low rank. It is formulated as a rank
minimization problem and solved using nuclear norm relaxation or low-rank matrix
factorization. It is widely used in recommendation systems, image reconstruction, and sensor
data restoration.

If you'd like, I can also provide a short handwritten-style summary or comparison between matrix
completion and matrix factorization.

Discuss in detail about Generative Models (mixture models and latent factor models) in
unsupervised learning

Generative models in unsupervised learning are all about learning how the data was “generated” –
i.e., learning the full probability distribution of the data, not just boundaries or clusters.
You asked specifically about:

Mixture models
Latent factor models

Let’s go through them one by one, with math and intuition.

1. What is a Generative Model in Unsupervised Learning?

In unsupervised learning, we observe data points:

x1 , x2 , … , xn ∈ R d
​ ​ ​

No labels.
A generative model tries to model the data-generating process by specifying a probabilistic model:

p(x; θ) or more generally p(x, z; θ)

where:

x = observed data

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 51/63
 z = hidden / latent variables (cluster labels, factors, etc.)
θ = model parameters

We then:

Fit θ from data (usually via maximum likelihood).

Use the model for:

density estimation,
clustering,
dimensionality reduction,
generation of new samples.

Two major families:

1. Mixture models → think “data comes from a mixture of several distributions”.

2. Latent factor models → think “data is generated from a few hidden continuous factors”.

2. Mixture Models
2.1 Basic Idea

A mixture model assumes that each data point x comes from one of several components, but we do
not know which one.
Example intuition:

Heights in a population = mixture of male and female height distributions.

Pixel colors in an image = mixture of background, object, shadow distributions.

Formally, suppose we have K components, with a hidden variable z ∈ {1, … , K} indicating which
component generated x.

Prior over components:

K
p(z = k) = πk , ​ with πk ≥ 0, ∑ πk = 1
​ ​ ​

k=1

Component likelihood:

p(x ∣ z = k; θk ) ​

Then the mixture model is:

K
p(x) = ∑ πk p(x ∣ z = k; θk )
​ ​ ​

k=1

This is a generative story:

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 52/63
 1. Choose a component z according to {πk }. ​

2. Generate x from the distribution p(x ∣ z; θz ). ​

We observe only x, not z – so learning is unsupervised.

2.2 Gaussian Mixture Model (GMM) – Classic Example

Most common mixture model: mixture of Gaussians.

Component k :

p(x ∣ z = k) = N (x ∣ μk , Σk ) ​ ​

The overall mixture:

K
p(x) = ∑ πk N (x ∣ μk , Σk ) ​ ​ ​

k=1

Parameters:

πk (mixing weights)
​

μk (means)​

Σk (covariances)
​

Goal: learn these from data.

2.3 Latent Variable View

Introduce latent variable zi for each data point xi :

​ ​

zi is a one-hot K-dimensional vector, or a label in {1, … , K}.

​

Joint probability:

p(xi , zi ) = p(zi ) p(xi ∣ zi )

​ ​ ​ ​ ​

Marginalizing out the latent variable:

p(xi ) = ∑ p(zi ) p(xi ∣ zi )

​ ​ ​ ​ ​

zi ​

This latent structure implies natural soft clustering:

Posterior (called responsibility of component k for point i):

πk p(xi ∣ zi = k)
γik = p(zi = k ∣ xi ) =
​ ​ ​

K
​ ​ ​ ​

∑j=1 πj p(xi ∣ zi =
​ ​ ​ ​ j)

So each point belongs to each cluster with a probability, not a hard label.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 53/63
2.4 Learning with EM (Expectation–Maximization)

We want to maximize likelihood:

n
L(θ) = ∑ log p(xi ; θ) ​ ​

i=1

But p(xi ; θ) involves sum inside log:

​

log ∑ πk p(xi ∣ zi = k)
​ ​ ​ ​

which is messy.
Use EM algorithm:
E-step: (Expectation)

Compute responsibilities using current parameter estimates:

γik = p(zi = k ∣ xi ; θold )

​ ​ ​

M-step: (Maximization)

Update parameters to maximize the expected complete-data log likelihood:

n
1
πknew ​ = ∑ γik ​ ​ ​

n
i=1
n
∑ γik xi
μnew = i=1
​ ​ ​

k n
∑i=1 γik
​ ​

​ ​

n
∑i=1 γik (xi − μnew new ⊤
k )(xi − μk )
Σnew =
​ ​ ​ ​ ​ ​

k n
∑i=1 γik
​ ​

​ ​

Repeat E and M steps until convergence.

2.5 Example (Conceptual)

Suppose 1D heights data:

x = {160, 162, 158, 170, 175, 180} cm

We model with K = 2 Gaussians:

Cluster 1: shorter group (μ₁ around 160)

Cluster 2: taller group (μ₂ around 175)

GMM will:

Learn π1 , μ1 , σ12 and π2 , μ2 , σ22

​ ​ ​ ​ ​ ​

Give each height point a soft membership in the two components.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 54/63
This is unsupervised, but we often interpret components as hidden groups (e.g., male/female).

3. Latent Factor Models

Mixture models usually have discrete latent variables (cluster labels).
Latent factor models use continuous latent variables that explain variation in data.
Idea:

Each high-dimensional data point x is generated from a few continuous hidden factors h ∈
R , where k ≪ d.
k

This is closely related to dimensionality reduction, but in probabilistic form.

3.1 General Setup

Let:

h ∈ Rk : latent factor (low-dimensional)

x ∈ Rd : observed data

Generative model:

1. Draw latent factor:

h ∼ p(h) (e.g., h ∼ N (0, I))

2. Generate data given factor:

x ∼ p(x ∣ h; θ)

Then marginal:

p(x) = ∫ p(x ∣ h; θ)p(h) dh

We learn θ (and possibly properties of h) from the data.

Two classical latent factor models:

Factor Analysis
Probabilistic PCA

3.2 Factor Analysis (FA)

Assume:

x = μ + Wh + ϵ

where:

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 55/63
 h ∼ N (0, Ik ) (latent factors)
​

ϵ ∼ N (0, Ψ) (noise, usually diagonal covariance)

W ∈ Rd×k : factor loading matrix
μ: mean of data

Then:

p(x ∣ h) = N (x ∣ μ + Wh, Ψ)

Integrating out h, we get:

p(x) = N (x ∣ μ, W W ⊤ + Ψ)

We learn W , Ψ, μ from data (often by EM).

Interpretation:

Each latent factor hj captures some underlying source of variation.

​

Each observed variable xi is a linear combination of factors + noise.

​

3.3 Probabilistic PCA (PPCA)

PPCA is a special case of factor analysis where:

Ψ = σ 2 I (isotropic noise)
Same form: x = μ + Wh + ϵ

Then:

p(x) = N (x ∣ μ, W W ⊤ + σ 2 I)

It can be shown that the maximum likelihood solution for the subspace spanned by columns of W
corresponds exactly to the principal components found by PCA.
So PCA is essentially a latent factor model with:

Gaussian latent variables h,

Linear mapping W ,

Isotropic Gaussian noise.

3.4 Matrix Factorization as a Latent Factor Model

In collaborative filtering (recommendation systems), data is a user–item matrix R with missing entries. A
common model:

Rui ≈ u⊤
​

u vi
​ ​

This can be viewed as:

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 56/63
 uu : latent factor vector for user u
​

vi : latent factor vector for item i

​

Observed rating: dot product of these factors + noise.

Generative story:

1. Sample user factors uu ​ ∼ N (0, λ−1 I)

2. Sample item factors vi ∼ N (0, λ−1 I)
3. Rating:

Rui ∼ N (u⊤
​
2
u vi , σ ) ​ ​

This is a latent factor model for matrices.

3.5 Example (Simple Factor Model)

Imagine we measure 3 exam scores for students:

x1 : Math
​

x2 : Physics
​

x3 : Chemistry
​

We suspect there is a single underlying factor: “Science ability” h.

Let:

x = μ + Wh + ϵ,

with:

h ∼ N (0, 1)
10
W = 9 , ​ ​ ​

8
50
μ = 50 , ​ ​ ​

50

Then:

If a student has h = 1.5, expected scores ≈

50 10 65
x ≈ 50 + 9 ⋅ 1.5 = 63.5
​ ​ ​ ​ ​ ​ ​ ​

50 8 62

So one latent factor (“science ability”) explains correlated variation across all three subjects. Fitting
FA/PPCA learns W and μ from data, without labels.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 57/63
4. Mixture Models vs Latent Factor Models (Key Differences)
Aspect Mixture Models Latent Factor Models
Latent variable
Discrete (e.g., cluster label) Continuous (e.g., hidden factors)
type
Data from combination of a few continuous
Interpretation Data from one of K subpopulations
sources
Data approximated by several separate blobs Data lies near a low-dimensional subspace /
Geometry
(clusters) manifold
Gaussian Mixture Models, Mixture of Factor Analysis, Probabilistic PCA, Matrix
Examples
Bernoullis Factorization
Dimensionality reduction, representation
Typical task Clustering, density estimation
learning

Both are generative because they specify how data is generated from latent variables.

5. Why Generative Models Matter in Unsupervised Learning

1. Clustering with uncertainty (mixture models).
2. Low-dimensional representations for visualization and further tasks (latent factor models).
3. Handling missing data naturally (model the full distribution, then infer missing parts).
4. Sampling / generation of new data (e.g., draw new points from the learned p(x)).

5. Provide a probabilistic interpretation of structures everyone uses informally (clusters, factors,

topics, etc.).

If you want, I can next:

Derive the EM steps in more detail for a Gaussian mixture, or

Show how PPCA reduces to classical PCA (sketch of proof), or

Give short exam-style notes for “Generative models: mixture vs latent factor models” that you can
directly write.

What is Confusion Matrix . Explain with examples . What is False positive and False negetive

A confusion matrix is a performance evaluation table used in machine learning classification tasks
(especially binary classification) to compare the actual (true) labels with the predicted labels made by a
model.
It helps visually understand how well the model is performing, including correct predictions and the
types of errors.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 58/63
Structure of a Confusion Matrix (Binary Classification)
Predicted Positive Predicted Negative
Actual Positive True Positive (TP) False Negative (FN)
Actual Negative False Positive (FP) True Negative (TN)

Meaning:

True Positive (TP): Model correctly predicts positive.

True Negative (TN): Model correctly predicts negative.
False Positive (FP): Model predicts positive, but it is actually negative.
False Negative (FN): Model predicts negative, but it is actually positive.

Example
Suppose a classifier predicts whether a person has a disease.

Person Actual Label Predicted Label

1 Positive Positive
2 Negative Negative
3 Positive Negative
4 Negative Positive
5 Positive Positive

Count each category:

TP: Model predicted Positive where actual was Positive → Persons: 1,5 → 2
TN: Model predicted Negative where actual was Negative → Person: 2 → 1

FP: Model predicted Positive but actual was Negative → Person: 4 → 1

FN: Model predicted Negative but actual was Positive → Person: 3 → 1

Confusion Matrix:

Predicted Positive Predicted Negative

Actual Positive TP = 2 FN = 1
Actual Negative FP = 1 TN = 1

False Positive (FP)

A false positive occurs when:

The model predicts positive but the actual value is negative.

Example scenario:

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 59/63
 Spam detection system marks a normal (non-spam) email as spam.
Medical test identifies a healthy person as sick.

This error is also referred to as a Type I Error.

False Negative (FN)

A false negative occurs when:

The model predicts negative but the actual value is positive.

Example scenario:

A spam email passes through as normal.

A medical test fails to detect a disease when the patient actually has it.

This error is considered more serious in medical diagnosis and is also called a Type II Error.

Why Confusion Matrix Is Useful?

It forms the basis for many evaluation metrics:

Metric Formula
TP +TN
Accuracy TP +FP +FN +TN
​

TP
Precision TP +FP
​

TP
Recall (Sensitivity) TP +FN
​

TN
Specificity TN +FP
​

Precision⋅Recall
F1 Score 2× Precision+Recall
​

So the confusion matrix is a central tool for evaluating classification models, especially when class
imbalance exists.

Summary (Exam-Friendly)

A confusion matrix visually summarizes classification performance by showing correct and

incorrect predictions.
It consists of TP, TN, FP, and FN.
False Positive (FP): Predict positive when actual is negative (Type I error).
False Negative (FN): Predict negative when actual is positive (Type II error).

If you'd like, I can also provide a confusion matrix for multiclass classification or generate Python
code to compute it.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 60/63
 Discuss each term in the confusion matrix in detail with their meaning significance

A confusion matrix is more than just a table of predictions—it gives insight into the different types of
success and failure of a classification model. Each cell represents a count of how the predicted values
compare to actual values. Understanding each term helps evaluate model reliability, robustness, and
practical usefulness.
Below is the standard binary classification confusion matrix format:

Predicted Positive Predicted Negative

Actual Positive True Positive (TP) False Negative (FN)
Actual Negative False Positive (FP) True Negative (TN)

1. True Positive (TP)

Meaning:
Cases where the model predicted positive, and the actual class was also positive.

TP = Correctly identified positive instances

Example:
A medical test correctly identifies a sick patient as sick.
Significance:

Shows the model’s ability to detect positive cases correctly.

Higher TP means better detection sensitivity.
Important in applications like medical diagnosis, fraud detection, intrusion detection.

2. True Negative (TN)

Meaning:
Cases where the model predicted negative, and the actual class was negative.

TN = Correctly identified negative instances

Example:
A spam filter correctly identifies a normal email as not-spam.
Significance:

Indicates the model’s accuracy in ruling out negative instances.

A high TN value is important in applications where false alarms must be minimized, such as legal
or finance systems.
Contributes strongly to overall accuracy when classes are balanced.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 61/63
3. False Positive (FP) (Type I Error)
Meaning:
Cases where the model predicted positive, but the actual class was negative.

FP = Incorrectly predicting positive for a negative instance

Example:

A healthy patient is diagnosed as having a disease.

A non-spam email is classified as spam.

Significance:

Indicative of over-sensitive models.

Problematic when the cost of wrong positive predictions is high, such as:
Wrongly approving a loan to a risky customer,
Wrongly flagging harmless activities as cyber intrusions.
Impacts metrics: Precision and Specificity.

4. False Negative (FN) (Type II Error)

Meaning:
Cases where the model predicted negative, but the actual class was positive.

FN = Incorrectly predicting negative for a positive instance

Example:

A cancer patient receives a result saying “no cancer.”

Fraudulent transaction passes undetected.

Significance:

More serious than FP in many safety- and health-critical applications.

Indicates the model is missing important positive cases.
Affects Recall (Sensitivity).
Must be minimized in domains such as:
Medical screening,
Crime detection,
Disaster alerts.

Why Each Term Matters (Summary of Impact)

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 62/63
 Term Indicates Affects Practical Concern
Good performance in identifying
TP Correct detection of positive Recall, Accuracy
target class
Accuracy,
TN Correct rejection of negative Avoids false alarms
Specificity
FP (Type I Wrongly classifying negatives as Precision,
Costs: false alerts, unnecessary action
Error) positives Specificity
FN (Type II Dangerous in critical systems (missed
Missing actual positive cases Recall
Error) detection)

Key Metrics Derived from These Terms

Metric Formula What It Measures
TP +TN
Accuracy TP +FP +FN +TN
​
Overall correctness
TP
Precision TP +FP
​
How many predicted positives are correct
TP
Recall (Sensitivity) TP +FN
​
Ability to detect actual positives
TN
Specificity TN +FP
​
Ability to avoid false alarms
P recision⋅Recall
F1 Score 2⋅ P recision+Recall
​
Balanced metric when data is imbalanced

Conclusion

A confusion matrix does not just show correct and incorrect predictions—it reveals the nature of errors.
Depending on the application, either false positives or false negatives may be more costly, so
understanding each term helps choose the right model, tune thresholds, or select appropriate
evaluation metrics.

If you want, I can also explain:

✔ Confusion matrix for multi-class classification

✔ How to compute it using Python / sklearn
✔ How to decide whether FP or FN matters more in a given domain.

Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 63/63