Machine Learning (AD-502) Unit 5 Notes - RGPV

How unit 5 is examined

This unit covers why many features hurt, the families of reduction methods (selection, projection, manifold), PCA, Kernel PCA and PAC/VC theory; the marks sit in the approaches comparison, PCA principal components, VC dimension, benefits of reduction and backward elimination.

The Curse of Dimensionality

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Dimensionality reduction is the process of reducing the number of input features while keeping as much useful information as possible; the curse of dimensionality is the set of problems that appear because data becomes sparse and distances lose meaning as the number of features grows.</mark>

Key points.

In high dimensions the volume of space grows exponentially, so a fixed number of samples becomes very sparse and needs exponentially more data to cover it.
Distances between points become nearly equal, so distance-based methods such as k-NN and clustering fail.
Models with many features overfit easily and are slow to train.
Benefits of reduction: less computation and storage, less overfitting, easier visualization in 2D or 3D, less noise and redundancy, and better model accuracy. Example: PCA compresses hundreds of correlated features into a few components.

Asked: [7 marks] (Nov 2022) What is dimensionality reduction? Explain the benefits of applying dimensionality reduction.

Main Approaches for Dimensionality Reduction (Projection, Manifold Learning)

Definition. Dimensionality reduction either selects a subset of the original features (feature selection) or builds new, fewer features from them (feature extraction), and extraction is done by projection or manifold learning.

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-01" viewBox="0 0 631 262" width="631" height="262" role="img" aria-label="Approaches to dimensionality reduction"><style>#dsfig-u5-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-01 .t{fill:#16181D;font-weight:500}#dsfig-u5-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-01 .dot{fill:#16181D}#dsfig-u5-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-01 .ah{fill:#454C5A}#dsfig-u5-01 .ah.hi{fill:#2340B8}#dsfig-u5-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-01 .e{stroke:#B1B7C3}html.dark #dsfig-u5-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-01 .t{fill:#E6E8ED}html.dark #dsfig-u5-01 .t.inv{fill:#0F1115}html.dark #dsfig-u5-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-01 .dot{fill:#E6E8ED}html.dark #dsfig-u5-01 .ann{fill:#8FA3FF}html.dark #dsfig-u5-01 .lbl{fill:#858D9C}html.dark #dsfig-u5-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-01 .ah{fill:#B1B7C3}html.dark #dsfig-u5-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="278" y1="39" x2="138.5" y2="103"/><line class="e" x1="278" y1="39" x2="417.5" y2="103"/><line class="e" x1="138.5" y1="103" x2="47.5" y2="167"/><line class="e" x1="138.5" y1="103" x2="134.5" y2="167"/><line class="e" x1="138.5" y1="103" x2="229.5" y2="167"/><line class="e" x1="417.5" y1="103" x2="336" y2="167"/><line class="e" x1="417.5" y1="103" x2="499" y2="167"/><line class="e" x1="336" y1="167" x2="311" y2="231"/><line class="e" x1="336" y1="167" x2="361" y2="231"/><line class="e" x1="499" y1="167" x2="434.5" y2="231"/><line class="e" x1="499" y1="167" x2="501" y2="231"/><line class="e" x1="499" y1="167" x2="563.5" y2="231"/><rect class="n" x="213" y="24" width="130" height="30" rx="8"/><text class="t" x="278" y="39" dy=".35em" text-anchor="middle">Dim. reduction</text><rect class="n" x="62" y="88" width="153" height="30" rx="8"/><text class="t" x="138.5" y="103" dy=".35em" text-anchor="middle">Feature selection</text><rect class="n" x="14" y="152" width="67" height="30" rx="8"/><text class="t" x="47.5" y="167" dy=".35em" text-anchor="middle">Filter</text><rect class="n" x="97" y="152" width="75" height="30" rx="8"/><text class="t" x="134.5" y="167" dy=".35em" text-anchor="middle">Wrapper</text><rect class="n" x="188" y="152" width="83" height="30" rx="8"/><text class="t" x="229.5" y="167" dy=".35em" text-anchor="middle">Embedded</text><rect class="n" x="337" y="88" width="161" height="30" rx="8"/><text class="t" x="417.5" y="103" dy=".35em" text-anchor="middle">Feature extraction</text><rect class="n" x="287" y="152" width="98" height="30" rx="8"/><text class="t" x="336" y="167" dy=".35em" text-anchor="middle">Projection</text><circle class="n" cx="311" cy="231" r="17"/><text class="t" x="311" y="231" dy=".35em" text-anchor="middle">PCA</text><circle class="n" cx="361" cy="231" r="17"/><text class="t" x="361" y="231" dy=".35em" text-anchor="middle">LDA</text><rect class="n" x="422.5" y="152" width="153" height="30" rx="8"/><text class="t" x="499" y="167" dy=".35em" text-anchor="middle">Manifold learning</text><rect class="n" x="401" y="216" width="67" height="30" rx="8"/><text class="t" x="434.5" y="231" dy=".35em" text-anchor="middle">Isomap</text><circle class="n" cx="501" cy="231" r="17"/><text class="t" x="501" y="231" dy=".35em" text-anchor="middle">LLE</text><rect class="n" x="534" y="216" width="59" height="30" rx="8"/><text class="t" x="563.5" y="231" dy=".35em" text-anchor="middle">t-SNE</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Approaches to dimensionality reduction</figcaption></figure>

Key points.

Filter selection ranks features by a statistical score such as correlation or chi-square, independent of any model.
Wrapper selection tests feature subsets by training a model, for example forward selection and backward elimination.
Embedded selection picks features during training, for example Lasso or tree feature importance.
Projection projects data onto a lower-dimensional linear subspace (PCA preserves variance, LDA preserves class separation) and assumes the data lies near a flat subspace.
Manifold learning assumes the data lies on a curved low-dimensional manifold and unrolls it; Isomap keeps geodesic distances, LLE keeps local neighbourhoods, t-SNE keeps neighbour probabilities.
Autoencoders learn a nonlinear compressed code with a neural network.

Basis	Projection	Manifold learning
Assumption	Data near a linear subspace	Data on a curved manifold
Objective	Preserve global variance or separation	Preserve local or geodesic structure
Examples	PCA, LDA	Isomap, LLE, t-SNE
Mapping	Explicit, applies to new data	Usually no direct map for new data
Cost	Fast	Slower, sensitive to neighbours
Use	Compression, preprocessing	Visualization, unrolling curved data

Backward elimination (wrapper).

Step 1: Start with all features and fit the model.
Step 2: Find the feature with the highest p-value (least significant).
Step 3: If that p-value exceeds the threshold (for example 0.05), remove it and refit.
Step 4: Repeat until every remaining p-value is below the threshold (stopping criterion).

It is simple and considers feature interactions, but it is costly for many features and cannot re-add a removed feature.

Answer frame. Open with the two families, selection and extraction; draw the tree; for the comparison draw the table then state objectives; close with one line on when to use each.

Asked: [6 marks] (Nov 2022) List out main approaches for dimensionality reduction. Asked: [7 marks] (Nov 2023) Differentiate between projection-based dimensionality reduction and manifold learning. What are their primary objectives? Asked: [7 marks] (Nov 2022) Explain Backward Elimination technique in detail.

PCA: Preserving the Variance, Principal Components, Projecting Down to d Dimensions, Explained Variance Ratio, Choosing the Right Number of Dimensions, PCA for Compression, Randomized PCA, Incremental PCA

Definition. <mark>Principal components are new mutually orthogonal axes, each a linear combination of the original features, ordered so that the first captures the maximum variance in the data, the second the most remaining variance, and so on.</mark>

Key points.

Computation: centre the data by subtracting the mean, compute the covariance matrix $C=\frac{1}{n-1}X^TX$, then find its eigenvectors (directions) and eigenvalues (variance along them).
Sort eigenvectors by eigenvalue and keep the top $d$; project with $Z = XW_d$.
Explained variance ratio of a component is $\lambda_i/\sum_j\lambda_j$; choose $d$ so the cumulative ratio reaches about 95%.
Reconstruction $X_{rec}=ZW_d^T$ gives compression with small loss. Randomized PCA is a fast approximate SVD for large data, and Incremental PCA processes mini-batches when data does not fit in memory.

Asked: [7 marks] (Nov 2023) Define principal components in the context of PCA. How are they calculated from the original data?

Kernel PCA: Selecting a Kernel and Tuning Hyper parameters

Definition. <mark>Kernel PCA applies the kernel trick to PCA: it implicitly maps data to a high-dimensional feature space with kernel $k(x,y)$ and performs PCA there, capturing nonlinear structure.</mark>

Key points.

Common kernels are linear, polynomial and RBF $k(x,y)=e^{-\gamma\|x-y\|^2}$.
Choose the kernel and hyperparameters (such as $\gamma$) by grid search with cross-validation, scoring a downstream supervised task or reconstruction error.
It suits data like Swiss roll or concentric circles where linear PCA fails.

Learning Theory: PAC and VC model

Definition. <mark>PAC (Probably Approximately Correct) learning asks whether a learner can, with probability at least $1-\delta$, output a hypothesis with error at most $\epsilon$ using a polynomial number of samples; the VC dimension is the size of the largest set of points that a hypothesis class can shatter.</mark>

Key points.

A class shatters a set if it can realise every possible labelling of it; a linear classifier in 2D has VC dimension 3.
VC dimension measures the capacity of the hypothesis class, and generalization error is bounded by training error plus a term that grows with VC dimension and shrinks with more samples.
A higher VC dimension means a more complex model with greater overfitting risk and a need for more data.
It guides model selection through Structural Risk Minimization (SRM), which picks the class with the best trade-off of training error and capacity.

Asked: [7 marks] (Nov 2023) Discuss the significance of the VC dimension in understanding the generalization ability of learning algorithms.

Last-minute revision

Dimensionality reduction removes or combines features while keeping information.
Curse of dimensionality: data sparse, distances lose meaning, overfitting.
Selection: filter, wrapper, embedded; extraction: PCA, LDA, t-SNE, autoencoders.
Projection is linear and preserves variance; manifold learning preserves local geometry.
Backward elimination starts with all features and drops the highest p-value.
Principal components: orthogonal, ordered by variance, from eigenvectors of the covariance matrix.
Explained variance ratio $=\lambda_i/\sum\lambda_j$; keep about 95%.
Randomized PCA is fast and approximate; Incremental PCA uses mini-batches.
Kernel PCA uses the kernel trick for nonlinear data.
PAC: error at most $\epsilon$ with probability at least $1-\delta$.
VC dimension of a 2D linear classifier is 3.

Memory hooks

Selection picks, extraction creates.
PCA = Centre, Covariance, Eigen, Project.
Isomap geodesic, LLE local, t-SNE neighbours.
High VC means high capacity means high overfitting.

Coverage checklist

The Curse of Dimensionality: what is dimensionality reduction and its benefits.
Main Approaches for Dimensionality Reduction (Projection, Manifold Learning): list of approaches, projection vs manifold, backward elimination.
PCA: Preserving the Variance, Principal Components, Projecting Down to d Dimensions, Explained Variance Ratio, Choosing the Right Number of Dimensions, PCA for Compression, Randomized PCA, Incremental PCA: principal components definition and computation.
Kernel PCA: Selecting a Kernel and Tuning Hyper parameters: no past questions.
Learning Theory: PAC and VC model: significance of VC dimension.

Account

Machine Learning (AD-502) - Unit 5 Short Notes

How unit 5 is examined

The Curse of Dimensionality

Main Approaches for Dimensionality Reduction (Projection, Manifold Learning)

PCA: Preserving the Variance, Principal Components, Projecting Down to d Dimensions, Explained Variance Ratio, Choosing the Right Number of Dimensions, PCA for Compression, Randomized PCA, Incremental PCA

Kernel PCA: Selecting a Kernel and Tuning Hyper parameters

Learning Theory: PAC and VC model

Last-minute revision

Memory hooks

Coverage checklist