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

How unit 2 is examined

This unit covers classifiers (decision tree, naive Bayes, logistic regression, SVM, random forest, k-NN) and data handling; the marks sit in training set, k-NN, test-set evaluation, random forest and normalization.

Introduction

Not asked since 2022

Definition. Classification is supervised learning in which a model learns from labelled examples to assign a new pattern to one of a fixed set of classes.

Key points.

A classifier maps a feature vector $x$ to a class label $\omega_i$, using a decision rule learned from training data.
Learning is supervised, because every training pattern comes with its known class.
The classifier is judged by how well it generalises to unseen patterns, not by its training accuracy.
The output is a discrete label, unlike regression, which predicts a continuous value.

Application of classification

Definition. Classification applications are real problems where inputs must be sorted into categories automatically.

Key points.

Spam filtering classifies e-mail as spam or not spam.
Medical diagnosis classifies scans or test results as disease present or absent.
Character, face and fingerprint recognition classify images into letters or identities.
Credit scoring, speech recognition and fault detection are further examples.

Types of classification

Definition. Classification is binary when there are two classes and multiclass when there are more than two.

Key points.

Binary classification separates two classes, such as spam and not spam, with one decision boundary.
Multiclass classification assigns one of $C>2$ classes, such as digits 0 to 9.
Multiclass problems are solved by one-vs-rest (C classifiers) or one-vs-one ($C(C-1)/2$ classifiers), or by natively multiclass methods such as k-NN and decision trees.
In multilabel classification one pattern may carry several labels at once.

Decision tree

Definition. A decision tree is a tree classifier in which each internal node tests a feature, each branch is an outcome of the test, and each leaf gives a class.

Key points.

The tree is built top-down by choosing at each node the feature that best splits the data (ID3 uses information gain, CART uses Gini index).
Entropy is $H=-\sum p_i\log_2 p_i$ and information gain is the entropy drop after a split.
Splitting stops when a node is pure or no features remain.
Trees are easy to read but overfit, so pruning is used to cut weak branches.

Naive Bayes

Definition. Naive Bayes is a probabilistic classifier that applies Bayes' theorem with the naive assumption that features are conditionally independent given the class.

Formula. $P(\omega\mid x)\propto P(\omega)\prod_{j=1}^{d}P(x_j\mid\omega)$; predict the class with the largest value.

Key points.

Bayes' theorem gives $P(\omega\mid x)=\dfrac{P(x\mid\omega)P(\omega)}{P(x)}$, and $P(x)$ is the same for all classes so it is ignored.
The independence assumption turns a hard joint probability into a product of simple ones.
It trains fast and works well on text and small data.
A zero count wipes out the product, so Laplace smoothing is added.

Logistic regression

Definition. Logistic regression is a linear classifier that models the probability of class 1 as the sigmoid of a linear function of the features.

Formula. $P(y=1\mid x)=\dfrac{1}{1+e^{-(w^Tx+b)}}$

Key points.

The sigmoid squeezes any real value into the range 0 to 1, so the output reads as a probability.
The class is 1 if the probability exceeds 0.5, which gives a linear decision boundary $w^Tx+b=0$.
The weights are learned by maximum likelihood, usually with gradient descent.
Despite its name it is a classifier, not a regressor.

Support vector machine

Definition. A support vector machine finds the separating hyperplane that maximises the margin between two classes.

Key points.

The hyperplane is $w^Tx+b=0$ and the margin width is $2/\lVert w\rVert$, so maximising the margin means minimising $\lVert w\rVert$.
The training points lying on the margin are the support vectors, and they alone fix the boundary.
A soft margin with penalty $C$ allows some misclassified points when data overlap.
The kernel trick (polynomial, RBF) handles non-linear data by implicitly mapping it to a higher dimension.

Random forest

Definition. A random forest is an ensemble of many decision trees, each trained on a bootstrap sample with random feature selection, whose outputs are combined by voting.

Key points.

Bagging draws a bootstrap sample (random sampling with replacement) of the training set for each tree.
At every split only a random subset of features (about $\sqrt d$) is considered, which makes the trees different from each other.
Training grows each tree fully, and prediction takes the majority vote of all trees (average for regression).
Advantages are high accuracy, less overfitting than one tree and an out-of-bag error estimate; limitations are lower interpretability and more memory and time.
Applications include medical diagnosis, credit risk, image and remote-sensing classification.

Asked: [7 marks] (Nov 2023) Write a detail note on Random Forest.

K Nearest Neighbour classifier and variants

Definition. k-NN classifies a pattern by finding its k nearest training patterns under a distance measure and assigning the majority class among them.

Formula. Density estimate: $p(x)=\dfrac{k}{nV}$, where $V$ is the volume of the smallest region around $x$ containing $k$ of the $n$ samples. Euclidean distance: $d(x,y)=\sqrt{\sum_i (x_i-y_i)^2}$. Posterior: $P(\omega_i\mid x)=k_i/k$.

Steps.

Step 1: Choose k and a distance metric; store all n labelled training patterns.
Step 2: For the test pattern x, compute its distance to every training pattern.
Step 3: Sort the distances and pick the k smallest (the k neighbours).
Step 4: Density estimation: take V as the volume of the sphere reaching the kth neighbour, p(x) = k/(nV).
Step 5: Classification: count the neighbours of each class, k_i, and assign x to the class with the largest k_i (majority vote).

Key points.

k-NN is a lazy, non-parametric method: it keeps the whole training set and does no training.
In k-NN estimation the count $k$ is fixed and the volume $V$ adapts, so the estimate is smooth in sparse regions and sharp in dense ones.
The rule $k_i/k$ estimates the posterior, and choosing the largest is the k-NN rule; $k=1$ is the nearest neighbour rule.
Small $k$ is noisy and overfits, large $k$ over-smooths; choose odd $k$ by validation to avoid ties.
The metric matters (Euclidean, Manhattan, Minkowski), so features should be normalised first.
Variants: weighted k-NN (closer neighbours vote more, weight $1/d^2$), condensed and edited NN, and k-NN regression (average of neighbours).

Example. With $n=100$, $k=5$ and $V=0.2$, $p(x)=5/(100\times0.2)=\mathbf{0.25}$. If $k=3$ neighbours have labels A, A, B, then $x$ is assigned to A.

Answer frame. Open with the k-NN principle and density formula; draw a 2-class scatter with a circle around x holding k points; write the five steps, then the majority-vote rule; close with the choice of k and distance metric.

Asked: [7 marks] (Dec 2020, Nov 2023) Write an algorithm for k-Nearest neighbour estimation. How does K-Nearest Neighbor work? Explain with KNN estimation and KNN rules.

Efficient algorithms for nearest neighbour classification

Definition. Efficient nearest neighbour algorithms reduce the cost of searching the training set, which is $O(nd)$ per query in brute force.

Key points.

A k-d tree splits the space by one feature at a time, so a query visits only nearby regions in about $O(\log n)$ time for low dimensions.
Branch-and-bound search skips whole groups of points whose lower-bound distance already exceeds the best distance found.
Partial distance computation stops adding terms once the running sum passes the current best.
Approximate methods such as hashing trade a little accuracy for large speed-ups in high dimensions.

Different approaches to prototype selection

Definition. Prototype selection keeps a small representative subset of the training set that gives nearly the same classification accuracy.

Key points.

It cuts storage and search time of nearest neighbour classifiers.
Condensed nearest neighbour (CNN) keeps only points needed to classify the rest correctly, and mostly retains boundary points.
Edited nearest neighbour (ENN) removes noisy or misclassified points and smooths the boundary.
Clustering-based methods replace each cluster by its centroid (prototype), for example with k-means.

Combination of classifiers

Definition. Combining classifiers merges the decisions of several classifiers into one final decision that is more accurate than any single member.

Key points.

Majority voting picks the class chosen by most classifiers; weighted voting gives better classifiers more say.
Averaging or product of posterior probabilities combines soft outputs.
Bagging trains the same learner on bootstrap samples; boosting trains learners in sequence, each focusing on earlier errors.
Diverse, individually accurate members give the largest gain, and random forest is a standard example.

Training set

Definition. The training set is the collection of labelled patterns $\{(x_i,\omega_i)\}$ from which a classifier learns its parameters.

Key points.

Each training pattern is a feature vector paired with its correct class label, so training is supervised.
The classifier adjusts its parameters (weights, tree splits, stored prototypes) to fit the training set.
It must be representative of real data, cover all classes and be large enough for the number of features.
Class imbalance biases the classifier towards the majority class, so classes should be balanced or reweighted.
Too small or noisy a set causes overfitting: high training accuracy but poor test accuracy.
The data is split into a training set (about 60-80%), a validation set for tuning and a test set that is never used for learning.
Data sets for pattern recognition are collections of such patterns, such as the Iris, MNIST and UCI repository sets, used to build and compare classifiers.
A classifier is a model that maps features to a class; its variants include k-NN, decision tree, Bayes, SVM and neural classifiers.

Example. For spam detection, each of 1000 e-mails is a vector of word counts with the label spam or not spam; the Bayes classifier estimates $P(\text{word}\mid\text{class})$ from these 1000 rows.

Answer frame. Open with the definition; draw a box diagram Training set -> Learning algorithm -> Classifier, with Test set -> Classifier -> Predicted class; develop points 1-6; close with why it is relevant to pattern recognition: the quality of the training set fixes the quality of the classifier. For "any two", pair Training set with Classifier and variants (points 8, then k-NN, tree, SVM lines).

Asked: [14 marks] (Nov 2023) Write a short note on any two: i) Data sets for pattern ii) Training set iii) Classifier and variants iv) FCM

Test set

Definition. The test set is a held-out set of labelled patterns, unseen in training, used to estimate how well the classifier generalises.

Formula. From the confusion matrix (TP, FP, FN, TN): $\text{Accuracy}=\dfrac{TP+TN}{TP+TN+FP+FN}$, $\text{Precision}=\dfrac{TP}{TP+FP}$, $\text{Recall}=\dfrac{TP}{TP+FN}$, $F=\dfrac{2PR}{P+R}$, error rate $=1-\text{accuracy}$.

Key points.

Evaluation is needed because accuracy on the training set is optimistic; only unseen data shows generalisation.
In the train-test split the data is divided (for example 70:30), the classifier is trained on one part and scored on the other.
In k-fold cross-validation the data is cut into k parts, each part is the test set once, and the k scores are averaged; leave-one-out is the case $k=n$.
The confusion matrix tabulates true and predicted classes and is the source of all other metrics.
Precision is the fraction of predicted positives that are correct, and recall is the fraction of actual positives found; the F-measure is their harmonic mean and suits imbalanced data.
The ROC curve plots true positive rate against false positive rate over thresholds, and a larger area under it (AUC) is better.
A large gap between training and test accuracy signals overfitting.

Example. TP=40, FN=10, FP=5, TN=45: accuracy $=85/100=0.85$, precision $=40/45=0.89$, recall $=40/50=0.80$, $F=\mathbf{0.84}$, error rate $=0.15$.

Answer frame. Open with why a classifier must be tested on unseen data; draw the 2x2 confusion matrix; explain split and cross-validation, then the metrics with formulas; close with the worked example and the overfitting remark.

Asked: [7 marks] (Jun 2020, Dec 2020) How do we evaluate the performance of a classifier?

Standardization and normalization

Definition. Normalization rescales feature values to a common range so that no feature dominates a distance or learning rule because of its units.

Formula. Min-max: $x'=\dfrac{x-x_{min}}{x_{max}-x_{min}}$ (range 0 to 1). Z-score (standardization): $x'=\dfrac{x-\mu}{\sigma}$ (mean 0, standard deviation 1).

Key points.

Features such as salary and age differ in scale, so unscaled distances in k-NN or clustering are dominated by the larger one.
Min-max keeps the shape of the data but is sensitive to outliers; z-score copes better with outliers.
Gradient-based learners (logistic regression, neural nets) converge faster on scaled data.
The $\mu$, $\sigma$, min and max are computed on the training set only and reused on the test set.

Example. Data 5, 10, 15, 20, 50: min-max gives 0, 0.11, 0.22, 0.33, 1. With $\mu=20$ and $\sigma=15.81$, z-scores are -0.95, -0.63, -0.32, 0, 1.90.

Asked: [7 marks] (Nov 2023) What do you understand by normalization? Explain with example.

Last-minute revision

Classification: supervised learning that assigns a pattern to one of a fixed set of classes.
Naive Bayes: $P(\omega\mid x)\propto P(\omega)\prod P(x_j\mid\omega)$.
Logistic regression: $P(y=1\mid x)=1/(1+e^{-(w^Tx+b)})$.
SVM: maximum-margin hyperplane, margin $2/\lVert w\rVert$, kernel trick for non-linear data.
Random forest: bagging plus random feature choice, majority vote of trees.
k-NN: $p(x)=k/(nV)$; classify by the majority among k neighbours; odd k, normalised features.
Prototype selection: CNN keeps boundary points, ENN removes noise.
Training set learns, validation set tunes, test set only evaluates.
Accuracy $=(TP+TN)/N$, precision $=TP/(TP+FP)$, recall $=TP/(TP+FN)$, $F=2PR/(P+R)$.
Min-max $=(x-min)/(max-min)$; z-score $=(x-\mu)/\sigma$.

Memory hooks

Train to learn, validate to tune, test to judge.
Precision = "of what I called positive, how many are right"; recall = "of all positives, how many I found".
k-NN is lazy: no training, all the work happens at query time.
Random forest = Bagging + Random features + Ballot (vote).
Min-max squeezes to 0-1; z-score centres at 0.

Coverage checklist

introduction: covered
application of classification: covered
types of classification: covered
decision tree: covered
naïve bayes: covered
logistic regression: covered
support vector machine: covered
random forest: Q3 (Nov 2023)
K Nearest Neighbour Classifier and variants: Q2 (Dec 2020, Nov 2023)
Efficient algorithms for nearest neighbour classification: covered
Different Approaches to Prototype Selection: covered
Combination of Classifiers: covered
Training set: Q1 (Nov 2023)
test set: Q5 (Jun 2020, Dec 2020)
standardization and normalization: Q4 (Nov 2023)

Account

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

How unit 2 is examined

Introduction

Application of classification

Types of classification

Decision tree

Naive Bayes

Logistic regression

Support vector machine

Random forest

K Nearest Neighbour classifier and variants

Efficient algorithms for nearest neighbour classification

Different approaches to prototype selection

Combination of classifiers

Training set

Test set

Standardization and normalization

Last-minute revision

Memory hooks

Coverage checklist