AI010303 Pattern Recognition Module 4

MODULE 4

Syllabus

Algorithm-Independent Machine Learning- Lack of Inherent Superiority of Any Classifier,

Bias and Variance, Resampling for Estimating Statistics, Resampling for Classifier Design,
Estimating and Comparing Classifiers

Algorithm-Independent Machine Learning

Algorithm-independent machine learning refers to the study of the general properties and
principles of learning systems without focusing on a specific algorithm (like SVM, decision
tree, etc.).It examines what makes learning possible and how to evaluate it—regardless of the
model used.

Goals:

• Understand how learning performance depends on data, noise, and bias—not just
algorithm choice.
• Develop ways to evaluate, compare, and improve classifiers that are independent of
their inner workings.

Lack of Inherent Superiority of Any Classifier

The “No Free Lunch (NFL)” Theorem:

There is no single classifier that performs best for all problems.

Each classifier makes assumptions about the underlying data distribution (called inductive
bias).
If those assumptions match the true distribution, the classifier performs well — otherwise, it
performs poorly.

Explanation:

• Each classifier (e.g., Bayesian, k-NN, SVM, neural network) has its strengths and
weaknesses.

1
AI010303 Pattern Recognition Module 4

• For some data distributions, a linear classifier is best; for others, a nonlinear one is
required.
• Hence, performance depends on the data, not on the classifier alone.

No Free Lunch Theorem shows that in the absence of assumptions we should not prefer any
learning or classification algorithm over another

Ugly Ducking Theorem:

The Ugly Duckling Theorem states that in the absence of assumptions there is no privileged or
“best” feature representation, and that even the notion of similarity between patterns depends
implicitly on assumptions which may or may not be correct.
Find a principled measure the similarity between two patterns, given some representation: the
number of predicates (rather than the number of features) the patterns share.
The Theorem forces us to acknowledge that even the apparently simple notion of similarity
between patterns is fundamentally based on implicit assumptions about the problem domain.

2
AI010303 Pattern Recognition Module 4

Minimum Description Length

Algorithmic complexity — also known as Kolmogorov complexity, algorithmic entropy, ...
— seeks to quantify an inherent complexity of a binary string (we shall assume both classifiers
and patterns are described by such strings).
The minimum description length (MDL) principle states that we should minimize the sum of
the model’s algorithmic complexity and the description of the training data D with respect to
that model, i.e.,

Thus we seek the model h∗ that obeys h∗ = arg minK (h,D)

It can be shown theoretically that classifiers designed with a minimum description length
principle are guaranteed to converge to the ideal or true model in the limit of more and more
data.
However, such derivations cannot prove that the principle leads to superior performance in the
finite data case; to do so would violate the No Free Lunch Theorems.
The minimum description length principle states that simple models (small K(h)) are to be
preferred, and thus amounts to a bias toward “simplicity”.
It is found empirically that classifiers designed using the minimum description length principle
work well in many problems

Overfitting avoidance and Occam’s razor

To avoid overfitting can be applied regularization, pruning, inclusion of penalty terms,
minimizing a description length, and so on.
The No Free Lunch results throw such techniques into question: If there are no problem-
independent reasons to prefer one algorithm over another, why is overfitting avoidance nearly
universally advocated? (but frequent empirical “successes”)
Occam’s razor: in pattern recognition, one should not use classifiers that are more complicated
than are necessary, where “necessary” is determined by the quality of fit to the training data.

3
AI010303 Pattern Recognition Module 4

The frequent empirical “successes” of Occam’s razor imply that the classes of problems
addressed have certain properties:
What might be the reason we explore problems that tend to favor simpler classifiers?
Principle of satisficing:
• Human cognition: through evolution, we have had strong selection pressure on our
pattern recognition apparatuses to be computationally simple (require fewer neurons,
less time, ...).
• Pattern recognition: Design methodology itself imposes a bias toward “simple”
classifiers; we generally stop searching for a design when the classifier is “good
enough”

Bias and Variance

Two main sources of error affect a model's performance: Bias and Variance.

• Bias: Error due to simplifying assumptions in the model (underfitting).

• Variance: Error due to sensitivity to fluctuations in the training data (overfitting).

Total Expected Error = Bias² + Variance + Irreducible Noise

Bias
• The difference between the average prediction of the model and the true value.
• High bias = model is too simple (underfitting).
Variance
• The variability of model predictions for different training sets.
• High variance = model is too complex (overfitting).
Irreducible Noise
• Random noise in the data that cannot be modeled by any classifier.
Bias-Variance Tradeoff:
• Increasing model complexity → decreases bias but increases variance.
• Goal: Find the balance that minimizes total error.

4
AI010303 Pattern Recognition Module 4

Resampling for Estimating Statistics

Resampling Method is a statical method that is used to generate new data points in the dataset
by randomly picking data points from the existing dataset. It helps in creating new synthetic
datasets for training machine learning models and to estimate the properties of a dataset when
the dataset is unknown, difficult to estimate, or when the sample size of the dataset is small.
Two common methods of Resampling are :
1. Cross Validation
2. Bootstrapping
1. Cross-Validation
Cross-Validation is used to estimate the test error associated with a model to evaluate its
performance.
Validation set approach:
This is the most basic approach. It simply involves randomly dividing the dataset into two
parts: first a training set and second a validation set or hold-out set. The model is fit on the
training set and the fitted model is used to make predictions on the validation set.

Validation Set Approach in Resampling Method

Leave-one-out-cross-validation:
LOOCV is a better option than the validation set approach. Instead of splitting the entire
dataset into two halves, only one observation is used for validation and the rest is used to fit
the model.

5
AI010303 Pattern Recognition Module 4

Leave one out of cross-validation

k-fold cross-validation
This approach involves randomly dividing the set of observations into k folds of nearly equal
size. The first fold is treated as a validation set and the model is fit on the remaining folds. The
procedure is then repeated k times, where a different group each time is treated as the validation
set.

K-fold Cross-validation
6
AI010303 Pattern Recognition Module 4

2. Bootstrap
Bootstrap is a powerful statistical tool used to quantify the uncertainty of a given model.
However, the real power of Bootstrap is that it could get applied to a wide range of models
where the variability is hard to obtain or not output automatically.
Challenges:
Algorithms in Machine Learning tend to produce unsatisfactory classifiers when handled
with unbalanced datasets.
For example, Movie Review datasets
Total Observations : 100
Positive Dataset : 90
Negative Dataset : 10
Event rate : 2%
The main problem here is how to get a balanced dataset.
Challenges with standard ML algorithms:
Standard ML techniques such as Decision Tree and Logistic Regression have a bias towards
the majority class, and they tend to ignore the minority class. They tend only to predict the
majority class, hence, having major misclassification of the minority class in comparison with
the majority class.
Evaluation of the classification algorithm as measured by a confusion matrix.

Confusion Matrix
The confusion matrix is a valuable tool for understanding the strengths and weaknesses of a
classification model and identifying areas for improvement.

7
AI010303 Pattern Recognition Module 4

Handling Approach:
• Random Over-sampling:
It aims to balance class distribution by randomly increasing minority class examples
by replicating them.
For example –
Total Observations : 100
Positive Dataset : 90
Negative Dataset : 10
Event Rate : 2%
• We replicate Negative Dataset 15 times
Positive Dataset: 90
Negative Dataset after Replicating: 150
Total Observations: 190
Event Rate : 150/240= 63%
• SMOTE (Synthetic Minority Oversampling Technique) synthesizes new minority
instances between existing minority instances. It randomly picks up the minority class
and calculates the K-nearest neighbor for that particular point. Finally, the synthetic
points are added between the neighbors and the chosen spot.
• Random Under-Sampling:
It aims to balance class distribution by randomly eliminating majority class examples.
For Example –
Total Observations : 100
Positive Dataset : 90
Negative Dataset : 10
Event rate : 2%

We take 10% samples of Positive Dataset and combine it with Negative Dataset.

Positive Dataset after Random Under-Sampling : 10% of 90 = 9

Total observation after combining it with Negative Dataset: 10+9=19

Event Rate after Under-Sampling : 10/19 = 53%

8
AI010303 Pattern Recognition Module 4

• When instances of two different classes are very close to each other, we remove the
instances of the majority class to increase the spaces between the two classes. This
helps in the classification process.
• Cluster-based Over Sampling:
K means clustering algorithm is independently applied to both the class instances such
as to identify clusters in the datasets. All clusters are oversampled such that clusters of
the same class have the same size.
For Example –
Total Observations : 100
Positive Dataset : 90
Negative Dataset : 10
Event Rate : 2%

Majority Class Cluster Before Resampling:

• Cluster 1: 20 Observations
• Cluster 2: 30 Observations
• Cluster 3: 12 Observations
• Cluster 4: 18 Observations
• Cluster 5: 10 Observations
Minority Class Cluster:
• Cluster 1: 8 Observations
• Cluster 2: 12 Observations
• After oversampling all clusters of the same class have the same number of
observations.
Majority Class Cluster:
• Cluster 1: 20 Observations
• Cluster 2: 20 Observations
• Cluster 3: 20 Observations
• Cluster 4: 20 Observations
• Cluster 5: 20 Observations
Minority Class Cluster:
• Cluster 1: 15 Observations
• Cluster 2: 15 Observations

9
AI010303 Pattern Recognition Module 4

Resampling for Classifier Design

When we design a classifier, we must train, tune, and test it.
However, in most real-world problems, we have limited data.
If we use all data for training, we won’t have enough left to test generalization.
If we keep too much for testing, the model might not learn well.
Resampling techniques solve this problem by reusing the available data efficiently for both
training and validation.
They help:
• Design better classifiers (by tuning parameters).
• Avoid overfitting.
• Estimate generalization performance.

Purpose
Resampling is used not only to estimate performance but also to guide the design process.
It helps in:
1. Model Selection – Choosing the best type of classifier (e.g., SVM, Decision Tree, k-
NN).
2. Parameter Selection – Tuning hyperparameters (e.g., number of neighbors k, tree
depth, regularization constant).
3. Feature Selection – Choosing which features to include.
4. Performance Estimation – Determining how well the classifier generalizes.

Common Resampling Techniques for Classifier Design

1. Holdout Method
• The simplest resampling method.
• Split data into two parts:
o Training set: used to build the model (usually 70–80% of data).
o Test set: used to evaluate performance (usually 20–30%).
Advantages:
• Simple and fast.
Disadvantages:
• The result depends heavily on how the data is split.

10
AI010303 Pattern Recognition Module 4

• May give misleading estimates if the split is unbalanced (e.g., one class dominates in
training).
Example:
Out of 100 samples, use 70 for training, 30 for testing.
If accuracy = 85% on test data, that’s your estimate — but it might vary if you split differently.

2. k-Fold Cross-Validation
• The data is divided into k equal parts (folds).
• The classifier is trained on (k−1) folds and tested on the remaining one.
• Repeat k times, each time using a different fold for testing.
• The average performance across all folds is used as the performance estimate.
Typical choice: k = 5 or 10.
Advantages:
• Every data point is used for both training and testing.
• Reduces variance in performance estimate.
• Efficient use of limited data.
Disadvantages:
• Computationally more expensive (must train k times).
Example:
For 10-fold cross-validation on 100 samples:
• Train on 90 samples, test on 10 → repeat 10 times.
• Average accuracy from all 10 tests → final performance measure.

3. Leave-One-Out Cross-Validation (LOOCV)

• A special case of k-fold with k = N (the number of samples).
• Each sample is used once as the test set; all others form the training set.
Advantages:
• Very accurate and nearly unbiased estimate.
• Uses almost all data for training.
Disadvantages:
• Computationally expensive.
• High variance if data is noisy.
Example:
For 100 samples, build 100 models — each time leaving one sample out for testing.

11
AI010303 Pattern Recognition Module 4

4. Bootstrap Resampling
• From the original dataset of size N, draw N samples with replacement to form a
bootstrap sample.
o Some points appear multiple times; some not at all.
• On average, about 63.2% of samples are included in the bootstrap training set, and
36.8% are left out (used for testing).
Steps:
1. Create many bootstrap samples (e.g., 100–1000).
2. Train the classifier on each sample.
3. Evaluate performance on the excluded samples.
4. Average results → performance estimate.
Advantages:
• Works well for small datasets.
• Estimates variance of the performance.
Disadvantages:
• Some bias due to duplicate samples.

Using Resampling for Model Selection and Parameter Tuning

Resampling is extremely helpful for choosing model parameters.
We can systematically try different parameter values and use resampling to estimate which
one performs best.
Example: Selecting k in k-NN
1. Choose possible k values (e.g., 1, 3, 5, 7, 9).
2. For each k, perform 10-fold cross-validation on the training data.
3. Compute average classification accuracy.
4. Pick the k with highest accuracy.
5. Train final classifier with that k on full training data.
6. Test on final test set.
Example: Choosing Regularization Constant in SVM
• Use cross-validation to test various C (and kernel) values.
• Select the one minimizing cross-validation error.

12
AI010303 Pattern Recognition Module 4

Nested Cross-Validation

When we use cross-validation for both tuning and testing, we risk information leakage (the
test data indirectly influences model choice).
To avoid this, we use nested cross-validation:

• Outer loop: splits data for final testing.

• Inner loop: performs cross-validation within the training data to tune parameters.

Result: unbiased estimate of generalization performance.

Advantages of Resampling in Classifier Design

• Makes efficient use of limited data.
• Enables fair model selection and parameter tuning.
• Provides unbiased performance estimates.
• Helps avoid overfitting to the training data.
• Enables comparison between models on a consistent basis.

Comparing Classifiers
After estimating performance, we often want to compare two or more classifiers to decide
which one performs better.
However, a small difference in accuracy may not be statistically significant — it could be
due to random chance.
Hence, we use statistical hypothesis tests to compare classifiers fairly.

Hypothesis Testing Framework

• Null Hypothesis (H₀): Both classifiers perform equally well (difference due to
chance).
• Alternative Hypothesis (H₁): One classifier performs significantly better.
We reject H₀ only if there’s strong evidence that the difference is real (p-value < 0.05).

Statistical Tests for Classifier Comparison

1. Paired t-Test
Used when both classifiers are evaluated on the same resampled datasets (e.g., same folds in
cross-validation).
Procedure:

13
AI010303 Pattern Recognition Module 4

1. Perform k-fold cross-validation for both classifiers using the same folds.
2. Let e1i and e2i be the error rates on fold i for classifiers 1 and 2.
3. Compute the difference for each fold:

4. Compute mean and standard deviation of these differences.

5. Compute t-statistic:

where dˉ = mean of differences, sd = standard deviation.

6. Compare with critical t-value for (k−1) degrees of freedo

2. McNemar’s Test
Used when both classifiers are evaluated on the same test set and give discrete predictions.
Let:
• n11: Both correct
• n00: Both wrong
• n10: Classifier 1 correct, Classifier 2 wrong
• n01: Classifier 1 wrong, Classifier 2 correct
We only care about disagreements (n10 and n01).
McNemar’s statistic:

If χ2>3.84, difference is significant at 95% confidence.

Advantages:
• Simple and distribution-free.
• Best for paired test results.

14
AI010303 Pattern Recognition Module 4

3. Cross-Validated Paired t-Test

When using k-fold CV, results across folds are correlated (not independent).
A corrected t-test can be used to adjust for this correlation.
Corrected t-statistic:

where ntest and ntrain are the number of samples in test and train folds.

4. Nonparametric Tests
If the performance measures do not follow a normal distribution (common in practice),
we use nonparametric tests such as:
• Wilcoxon Signed-Rank Test (paired samples)
• Friedman Test (for comparing more than two classifiers)

Example
Suppose two classifiers A and B are tested on 100 samples.
Classifier Correct Wrong Accuracy
A 90 10 90%
B 93 7 93%

At first glance, B looks better.

But we can apply McNemar’s test to check if 3% improvement is statistically significant.
If the test shows χ² < 3.84, the difference is not significant, meaning both classifiers perform
roughly the same.

15