Pattern Recognition (CS-503 (B)) Unit 4 Notes

How unit 4 is examined

This unit covers reducing the number of features by extraction (PCA, LDA) or selection (branch and bound, forward/backward, (l,r)); types of feature extraction and the three search algorithms carry the marks.

Introduction of feature extraction and feature selection

<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">Low weight</span>

Definition. <mark>Dimension reduction is the process of mapping a d-dimensional feature vector to m < d features while keeping the information needed to classify well.</mark> Feature extraction builds m new features by transforming all d originals; feature selection picks m of the d originals unchanged.

Key points.

The curse of dimensionality says that as d grows, the data needed to estimate a classifier grows exponentially, so a fixed training set becomes sparse and the classifier overfits.
Dimension reduction is needed for visualization (plot in 2-D or 3-D), compression (less storage and faster computation) and better classification (noise and redundant features are removed).
Feature extraction gives new, combined features (PCA, LDA) and the original meaning is lost; feature selection keeps original features, so results stay interpretable.
Both methods work in three stages: define a criterion $J$ (variance, class separability, error rate), search for the best m features or projection, and then classify in the reduced space.
Example: 100 pixel intensities of a digit image reduced by PCA to 10 components, or a 20-attribute patient record reduced to the 5 best attributes by selection.

Asked: [7 marks] (Dec 2020) What is dimension reduction? Explain.

Types of feature extraction

Definition. <mark>Feature extraction transforms the raw measurements into a smaller set of new, informative features that are less redundant and easier to classify.</mark>

Key points.

Statistical features (mean, variance, moments, histograms) summarise the distribution of the raw values.
Transform features (Fourier, wavelet, DCT, PCA) express the signal in another basis, where few coefficients carry most of the energy.
Edge and shape features (gradients, contours, Hough lines) describe boundaries in images.
Texture features (co-occurrence matrix, Gabor filters) describe the repeating spatial pattern of intensity.
Linear methods use $y = W^T x$: PCA is unsupervised and keeps maximum variance, while LDA is supervised and keeps maximum class separation.
Selection criteria for a method: whether labels are available, whether linearity is acceptable, and the class separability retained.

PCA steps.

Step 1: Take n samples x_i in R^d and compute the mean mu = (1/n) sum x_i.
Step 2: Centre the data: x_i' = x_i - mu.
Step 3: Compute the covariance matrix C = (1/n) sum x_i' x_i'^T  (d x d).
Step 4: Find eigenvalues and eigenvectors of C; sort by eigenvalue, largest first.
Step 5: Keep the top m eigenvectors as W (d x m); choose m so that sum of top m eigenvalues / sum of all >= 90-95%.
Step 6: Project: y = W^T (x - mu).

LDA. Choose $W$ to maximise $J(W) = \dfrac{|W^T S_B W|}{|W^T S_W W|}$, where $S_B$ is the between-class scatter and $S_W$ the within-class scatter; for c classes it gives at most c-1 features.

PCA limits. It is linear, unsupervised (the high-variance direction need not separate classes), and sensitive to feature scaling; its uses are compression, noise removal and visualization.

Answer frame. For PCA: open with "PCA is a linear, unsupervised method that projects data onto the orthogonal directions of maximum variance"; draw a 2-D scatter with the PC1 axis along the long axis; give steps 1-6, then uses and limits; close with the variance-retained rule. For types: open with the definition; list points 1-4 as a table of type and example, then PCA and LDA (point 5), then selection criteria.

Asked: [7 marks] (Jun 2020) Discuss Principle Component Analysis (PCA) algorithm for dimension reduction. Asked: [7 marks] (Nov 2023) Discuss the various types of feature extraction.

Problem statement and uses

Definition. <mark>Given d candidate features, feature selection finds the subset of m features that maximises a criterion $J$.</mark>

Key points.

The number of possible subsets is $\binom{d}{m}$, and $2^d$ over all sizes, so exhaustive search is impractical for large d.
Uses: fewer measurements, faster and cheaper classifiers, less overfitting, and better accuracy when irrelevant features are dropped.
The curse of dimensionality (peaking phenomenon) is the reason: beyond some d, accuracy falls with a finite sample.
The criterion $J$ is a class separability measure, such as Mahalanobis distance or the classifier accuracy.

Algorithms: branch and bound

Definition. <mark>Branch and bound is an optimal search that finds the best m-feature subset without testing every subset, by pruning branches whose bound cannot beat the best found so far.</mark>

Key points.

It needs a monotonic criterion: for subsets $X \subset Y$, $J(X) \le J(Y)$, so removing features never increases $J$.
Branching: the root holds all d features and each level discards one feature, giving a tree of depth d-m; discarded indices increase down a path to avoid duplicates.
Bounding: the best complete m-subset found so far gives a bound B.
Pruning: if a node has $J \le B$, every descendant has $J \le B$ by monotonicity, so the whole subtree is skipped.
It is optimal, but worst-case complexity is still exponential; it is far faster in practice.

Example. d = 4, m = 2, $J = 1 - \prod(1-r_i)$ with r = 0.5, 0.3, 0.4, 0.2 for features 1-4; explored right to left.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-01" viewBox="0 0 685 194" width="685" height="194" role="img" aria-label="Search tree. Drop i removes feature i; leaves show the 2-feature subset and J."><style>#dsfig-u4-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-01 .t{fill:#16181D;font-weight:500}#dsfig-u4-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-01 .dot{fill:#16181D}#dsfig-u4-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-01 .ah{fill:#454C5A}#dsfig-u4-01 .ah.hi{fill:#2340B8}#dsfig-u4-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-01 .e{stroke:#B1B7C3}html.dark #dsfig-u4-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-01 .t{fill:#E6E8ED}html.dark #dsfig-u4-01 .t.inv{fill:#0F1115}html.dark #dsfig-u4-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-01 .dot{fill:#E6E8ED}html.dark #dsfig-u4-01 .ann{fill:#8FA3FF}html.dark #dsfig-u4-01 .lbl{fill:#858D9C}html.dark #dsfig-u4-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-01 .ah{fill:#B1B7C3}html.dark #dsfig-u4-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah2" 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="ahh2" 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="382.3" y1="37" x2="166.5" y2="101"/><line class="e" x1="382.3" y1="37" x2="434" y2="101"/><line class="e" x1="382.3" y1="37" x2="598" y2="101"/><line class="e" x1="166.5" y1="101" x2="59.5" y2="165"/><line class="e" x1="166.5" y1="101" x2="166.5" y2="165"/><line class="e" x1="166.5" y1="101" x2="273.5" y2="165"/><line class="e" x1="434" y1="101" x2="380.5" y2="165"/><line class="e" x1="434" y1="101" x2="487.5" y2="165"/><line class="e" x1="598" y1="101" x2="598" y2="165"/><rect class="n" x="325.3" y="22" width="114" height="30" rx="8"/><text class="t" x="382.3" y="37" dy=".35em" text-anchor="middle">All 4 J=.832</text><rect class="n" x="113.5" y="86" width="106" height="30" rx="8"/><text class="t" x="166.5" y="101" dy=".35em" text-anchor="middle">Drop 1 .664</text><rect class="n" x="14" y="150" width="91" height="30" rx="8"/><text class="t" x="59.5" y="165" dy=".35em" text-anchor="middle">{3,4} .52</text><rect class="n" x="121" y="150" width="91" height="30" rx="8"/><text class="t" x="166.5" y="165" dy=".35em" text-anchor="middle">{2,4} .44</text><rect class="n" x="228" y="150" width="91" height="30" rx="8"/><text class="t" x="273.5" y="165" dy=".35em" text-anchor="middle">{2,3} .58</text><rect class="n" x="385" y="86" width="98" height="30" rx="8"/><text class="t" x="434" y="101" dy=".35em" text-anchor="middle">Drop 2 .76</text><rect class="n" x="335" y="150" width="91" height="30" rx="8"/><text class="t" x="380.5" y="165" dy=".35em" text-anchor="middle">{1,4} .60</text><rect class="n" x="442" y="150" width="91" height="30" rx="8"/><text class="t" x="487.5" y="165" dy=".35em" text-anchor="middle">{1,3} .70</text><rect class="n" x="549" y="86" width="98" height="30" rx="8"/><text class="t" x="598" y="101" dy=".35em" text-anchor="middle">Drop 3 .72</text><rect class="n" x="552.5" y="150" width="91" height="30" rx="8"/><text class="t" x="598" y="165" dy=".35em" text-anchor="middle">{1,2} .65</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Search tree. Drop i removes feature i; leaves show the 2-feature subset and J.</figcaption></figure>

Visit	Node	J	Bound B
1	Drop 3 then 4: {1,2}	0.65	0.65
2	Drop 2 (0.76 > B): leaf {1,4}	0.60	0.65
3	Leaf {1,3}	0.70	0.70
4	Drop 1: 0.664 <= 0.70, pruned	-	0.70

Answer: best subset {1, 3}, J = 0.70; 3 of 6 leaves evaluated.

Answer frame. Open with the definition and monotonicity; draw the search tree; explain branch, bound, prune in order; work the example table; close with optimality and exponential worst case.

Asked: [7 marks] (Nov 2023) Illustrate branch and bound Algorithm with suitable example.

Sequential forward / backward selection

Definition. <mark>Sequential forward selection (SFS) starts with an empty set and repeatedly adds the one feature that most improves $J$; sequential backward selection (SBS) starts with all features and repeatedly removes the least useful one.</mark>

Key points.

SFS is a greedy, bottom-up search, and SBS is greedy, top-down.
At each step SFS evaluates $d - k$ candidates when k features are chosen, so it needs about $md$ evaluations, far fewer than $\binom{d}{m}$.
Once a feature is added (SFS) or removed (SBS) it is never reconsidered (the nesting problem), so the result may be suboptimal.
Stopping criteria: the subset reaches size m, or the gain in $J$ falls below a threshold.

Step 1: S = empty set, k = 0.
Step 2: For every feature f not in S, compute J(S + {f}).
Step 3: Add the f with the largest J to S; k = k + 1.
Step 4: If k = m (or gain < threshold) stop; otherwise go to Step 2.

Example. Same J as above, m = 2. Step 1: J(1)=0.5, J(2)=0.3, J(3)=0.4, J(4)=0.2, so add feature 1. Step 2: J(1,2)=0.65, J(1,3)=0.70, J(1,4)=0.60, so add feature 3. Answer: S = {1, 3}, J = 0.70.

Answer frame. Open with the definition of SFS; write the algorithm; show the two-step example; close with stopping criteria and the nesting drawback (SBS is the reverse).

Asked: [7 marks] (Nov 2023) Write an algorithm for forward selection with suitable example.

(l,r) algorithm

Definition. <mark>The (l,r) algorithm, also called plus-l take-away-r, adds l features by forward selection and then removes r by backward selection, repeating until m features remain.</mark>

Key points.

If l > r it starts from the empty set and grows; if l < r it starts from the full set and shrinks.
Because r features can be removed after l are added, it corrects the nesting problem of SFS and SBS.
It is still greedy, so it is not guaranteed optimal, and it costs more than SFS.
With l = 1, r = 0 it becomes SFS; with l = 0, r = 1 it becomes SBS.

Last-minute revision

Dimension reduction maps d features to m < d; extraction transforms, selection picks.
Curse of dimensionality: data needed grows exponentially with d.
PCA: centre, covariance, eigen decomposition, keep top m, project $y = W^T(x-\mu)$.
PCA keeps maximum variance (unsupervised); LDA maximises $|W^TS_BW|/|W^TS_WW|$ (supervised), at most c-1 features.
Types: statistical, transform, edge/shape, texture.
Subsets of size m: $\binom{d}{m}$.
Branch and bound: optimal, needs monotonic J, prunes nodes with $J \le B$.
Worked example: J(1,3) = 0.70 is best for d=4, m=2.
SFS adds best feature, SBS removes worst; both greedy with nesting problem.
(l,r): add l, remove r; l > r starts empty.

Memory hooks

PCA = "Centre, Covariance, Component, Cut, Convert" (project).
Extraction makes new features; selection chooses old ones.
Branch and bound: "bound beats branch" when node J is at most B.
SFS is Small-to-Full, SBS is Big-to-Small.
(l,r) = plus l, take away r.

Coverage checklist

introduction of feature extraction and feature selection: Dec 2020 dimension reduction.
types of feature extraction: Jun 2020 PCA; Nov 2023 types of feature extraction.
Problem statement and Uses: no past question.
Algorithms - Branch and bound algorithm: Nov 2023 branch and bound.
sequential forward / backward selection algorithms: Nov 2023 forward selection.
(l,r) algorithm: no past question.

Account

Pattern Recognition (CS-503 (B)) - Unit 4 Short Notes

How unit 4 is examined

Introduction of feature extraction and feature selection

Types of feature extraction

Problem statement and uses

Algorithms: branch and bound

Sequential forward / backward selection

(l,r) algorithm

Last-minute revision

Memory hooks

Coverage checklist