Pattern Recognition Techniques - Complete

Study Guide
UNIT-1: Introduction to Pattern Recognition Systems (9
Hours)
1. Basics of Probability

Key Definitions

 Probability: Measure of likelihood that an event will occur (value between 0 and 1)
o 0 = impossible event
o 1 = certain event
 Experiment: Process that produces outcomes (e.g., rolling a die)
 Sample Space (S): Set of all possible outcomes
 Event (E): Subset of the sample space

Fundamental Rules

1. Non-Negativity: P(A) ≥ 0 for any event A

2. Total Probability: P(S) = 1 (entire sample space)
3. Complement Rule: P(A') = 1 - P(A)

Random Variables

 Discrete Random Variable: Takes distinct, countable values

o Example: Coin toss (0 or 1), die roll (1-6)
o Uses Probability Mass Function (PMF): P(X = x)
 Continuous Random Variable: Takes any value within an interval
o Example: Height, weight, temperature
o Uses Probability Density Function (PDF): p(x)
o Note: P(X = a) = 0 for continuous variables

2. Independence of Events

Definition

Two events A and B are independent if the occurrence of one doesn't affect the other:

 P(A∩B) = P(A) × P(B) (for independent events)

Product Rule

 Independent events: P(A∩B) = P(A) × P(B)

 Dependent events: P(A∩B) = P(A) × P(B|A) = P(B) × P(A|B)
3. Conditional and Joint Probability

Conditional Probability

P(A|B) = P(A∩B) / P(B)

 Probability of A given that B has occurred

Joint Probability

P(A∩B) = Probability that both A and B occur together

Bayes' Theorem

P(A|B) = [P(B|A) × P(A)] / P(B)

 Foundation of Bayesian classification

4. Machine Perception

General Pipeline

1. Sensing: Capture raw data (camera, microphone, sensors)

2. Preprocessing: Remove noise, enhance contrast, standardize input
3. Segmentation: Isolate object of interest from background
4. Feature Extraction: Convert raw input into numerical features
5. Classification: Assign pattern to a class using decision rules

Example: Animal Sorting System

 Goal: Classify cat vs dog from images

 Features: Ear shape, eye spacing, fur texture, tail shape, body proportion
 Sensor: Camera or image acquisition system

5. Pattern Recognition Systems

Definition

The act of taking raw data and making a decision based on the category or class of the
pattern.

Types

1. Classification: Predefined classes are known

o Example: Spam/Not Spam, Digit Recognition (0-9)
2. Clustering: Classes not predefined; system groups data naturally
o Example: Customer segmentation

System Types by Approach

 1. Statistical (StatPR): Based on probability and statistical models
o Examples: SVM, Naive Bayes, Gaussian classifiers
2. Syntactic (SyntPR): Uses structural relationships
o Examples: Handwriting recognition, text recognition
3. Neural (NeurPR): Inspired by biological neurons
o Uses learning-based methods

6. The Design Cycle

Steps in Order

1. Data Collection: Gather representative training and testing samples

2. Feature Selection: Choose discriminative, simple, noise-resistant features
3. Model Choice: Select appropriate classifier based on data characteristics
4. Training: Use labeled data to optimize model parameters
5. Evaluation: Measure performance using accuracy, error rate, confusion matrix

Key Considerations

 Generalization: System should work on novel input, not just training data
 Computational Complexity: Trade-off between ease and performance

7. Learning and Adaptation

Supervised Learning

 Definition: Teacher provides category labels for training data

 Goal: Learn mapping function Y = f(X)
 Types:
o Classification: Predict discrete/categorical output
o Regression: Predict continuous numerical output

Unsupervised Learning

 Definition: No labels provided; system finds patterns

 Goal: Restructure input data into features or groups
 Example: Clustering similar data points

Reinforcement Learning

 Definition: Agent learns by interacting with environment

 Components:
o Agent: Learns optimal behavior
o Environment: System agent operates in
o State (S): All possible situations
o Action (A): All possible actions
o Reward (R): Feedback from environment

8. Minimum-Error-Rate Classification
Bayes Decision Rule

 Objective: Minimize probability of error

 Rule: Decide ω₁ if P(ω₁|x) > P(ω₂|x); otherwise decide ω₂
 Error: P(error|x) = min[P(ω₁|x), P(ω₂|x)]

Zero-One Loss Function

 Loss = 0 if decision is correct

 Loss = 1 if decision is incorrect
 Minimizing risk = maximizing posterior probability

9. Classifiers and Discriminant Functions

Multicategory Case

Set of discriminant functions g₁(x), g₂(x), ..., gᶜ(x)

 Assign x to class ωᵢ if gᵢ(x) > gⱼ(x) for all j ≠ i

Common Forms

 gᵢ(x) = P(ωᵢ|x) (posterior probability)

 gᵢ(x) = p(x|ωᵢ)P(ωᵢ) (likelihood × prior)
 gᵢ(x) = ln p(x|ωᵢ) + ln P(ωᵢ) (log form)

10. Decision Surfaces

Definition

Boundaries that separate different decision regions in feature space

 Decision region Rᵢ: All points x assigned to class ωᵢ

Two-Category Case

 Single discriminant function: g(x) = g₁(x) - g₂(x)

 Decide ω₁ if g(x) > 0; otherwise decide ω₂
 Decision boundary: g(x) = 0

11. Normal Density and Discriminant Functions

Univariate Normal Distribution

p(x) = (1/√(2πσ²)) exp[-(x-μ)²/(2σ²)]

 μ = mean
 σ² = variance
Multivariate Normal Distribution

p(x) = (1/((2π)^(d/2)|Σ|^(1/2))) exp[-½(x-μ)ᵀΣ⁻¹(x-μ)]

 μ = mean vector
 Σ = covariance matrix
 d = dimensionality

Different Cases for Normal Classifiers

Case 1: σᵢ² = σ² (Equal Variances)

 Result: Linear decision boundaries

 Classifier: Linear machine
 Decision surface: Hyperplane perpendicular to line joining means

Case 2: Σᵢ = Σ (Equal Covariances)

 Result: Linear decision boundaries

 Property: Hyperplane generally not perpendicular to line joining means

Case 3: Arbitrary Covariances

 Result: Quadratic decision boundaries

 Surfaces: Hyperellipsoids, hyperparaboloids, hyperspheres, etc.

UNIT-2: Parameter Estimation Methods (9 Hours)

1. Parameter Estimation Overview

Problem Statement

Given:

 Class-conditional density p(x|ωⱼ) with known parametric form

 Training data D = {x₁, x₂, ..., xₙ}

Find: Best parameter values θ = (μ, Σ) for the distribution

Main Approaches

1. Maximum Likelihood (ML): Parameters are fixed but unknown

2. Bayesian Estimation (BE): Parameters are random variables with known priors

2. Maximum Likelihood Estimation (ML)

Core Concept
Find parameter values that maximize the likelihood of observing the training data: θ̂ = arg
max p(D|θ)

Likelihood vs Probability

 Probability: p(x|θ) as function of x (θ fixed)

 Likelihood: p(x|θ) as function of θ (x fixed)

ML Process

1. Likelihood Function: p(D|θ) = ∏p(xₖ|θ)

2. Log-Likelihood: ln p(D|θ) = Σln p(xₖ|θ)
3. Maximization: ∂ln p(D|θ)/∂θ = 0

ML for Gaussian Distribution

Unknown Mean μ, Known Variance σ²

θ̂ = μ̂ = (1/n)Σxₖ (sample mean)

Unknown Mean μ and Variance σ²

 μ̂ = (1/n)Σxₖ (sample mean)

 σ̂² = (1/n)Σ(xₖ - μ̂)² (sample variance)

Multivariate Case: Unknown μ, Known Σ

μ̂ = (1/n)Σxₖ

Multivariate Case: Unknown μ and Σ

 μ̂ = (1/n)Σxₖ
 Σ̂ = (1/n)Σ(xₖ - μ̂)(xₖ - μ̂)ᵀ

3. Maximum A-Posteriori (MAP) Estimation

Concept

Incorporates prior knowledge about parameters: θ̂ = arg max p(D|θ)p(θ)

Relationship to ML

 If p(θ) is uniform → MAP = ML

 If p(θ) has structure → MAP ≠ ML

MAP for Gaussian with Prior on Mean

If μ ~ N(μ₀, σ₀²), then: μ̂ = (nσ₀²x̄ + σ²μ₀)/(nσ₀² + σ²)

4. Bayesian Estimation
Philosophy

 Parameters θ are random variables with prior p(θ)

 Use data D to convert prior to posterior p(θ|D)
 Estimate distribution, not point estimate

Bayes Rule for Parameters

p(θ|D) = p(D|θ)p(θ)/p(D)

BE Solution

p(x|D) = ∫p(x|θ)p(θ|D)dθ

Main Steps

1. Compute posterior: p(θ|D) ∝ p(D|θ)p(θ)

2. Compute predictive: p(x|D) = ∫p(x|θ)p(θ|D)dθ

Recursive Bayesian Learning

p(θ|D₁,D₂,...,Dₙ) ∝ p(xₙ|θ)p(θ|D₁,D₂,...,Dₙ₋₁)

 Online/incremental learning approach

5. Bias and Variance

Unbiased Estimator

E[θ̂] = θ

ML Estimates

 μ̂ is unbiased: E[μ̂] = μ
 σ̂² is biased: E[σ̂²] = ((n-1)/n)σ²

Unbiased Variance Estimator

σ̂²ᵤₙᵦᵢₐₛₑᵈ = (1/(n-1))Σ(xₖ - μ̂)²

6. Problems of Dimensionality

Curse of Dimensionality

 Training examples needed grow exponentially with dimensions

 High-dimensional spaces are mostly empty
 Distance measures become less meaningful

Solutions
 1. Dimensionality Reduction: Project to lower dimensions
2. Feature Selection: Choose subset of relevant features

7. Component Analysis and Discriminants

Principal Component Analysis (PCA)

Objective

Find linear transformation that preserves maximum information (variance)

Steps

1. Center data: x̃ ₖ = xₖ - x̄
2. Form covariance matrix: C = (1/n)Σx̃ ₖx̃ ₖᵀ
3. Compute eigenvalues/eigenvectors: Cuₖ = λₖuₖ
4. Select top K eigenvectors: Project onto principal components
5. Transform data: y = UᵀK(x - x̄ )

Properties

 Minimizes reconstruction error

 Captures directions of maximum variance
 Orthogonal transformation

Applications

 Eigenfaces: Face recognition using PCA

 Dimensionality reduction: Compress high-dimensional data

Linear Discriminant Analysis (LDA)

Objective

Find projection that maximizes class separation

Key Matrices

 Within-class scatter: Sᵩ = Σᵢ Σⱼ (xⱼ - μᵢ)(xⱼ - μᵢ)ᵀ

 Between-class scatter: Sᵦ = Σᵢ nᵢ(μᵢ - μ)(μᵢ - μ)ᵀ

Solution

Solve generalized eigenvalue problem: Sᵦuₖ = λₖSᵩuₖ

PCA vs LDA

 PCA: Preserves data variance (unsupervised)

 LDA: Maximizes class separation (supervised)
  When to use: LDA better with large training sets, PCA better with small sets

8. Expectation-Maximization (EM)

Purpose

Parameter estimation when data is incomplete or has hidden variables

EM Steps

1. Initialization: Choose initial parameter values θ⁰

2. E-Step: Compute expected values of hidden variables
3. M-Step: Update parameters using expected values
4. Convergence: Repeat until θ converges

Mixture of Gaussians Example

Model

p(x) = Σₖ πₖN(x|μₖ, Σₖ)

E-Step

Compute responsibilities: γₖ = πₖN(x|μₖ, Σₖ)/Σⱼ πⱼN(x|μⱼ, Σⱼ)

M-Step

 Update means: μₖ = Σᵢ γᵢₖxᵢ/Σᵢ γᵢₖ

 Update covariances: Σₖ = Σᵢ γᵢₖ(xᵢ - μₖ)(xᵢ - μₖ)ᵀ/Σᵢ γᵢₖ
 Update weights: πₖ = (1/n)Σᵢ γᵢₖ

9. Hidden Markov Models (HMM)

Components

1. States: Hidden states {s₁, s₂, ..., sₙ}

2. Observations: Observable outputs {o₁, o₂, ..., oₘ}
3. Transition probabilities: A = {aᵢⱼ} = P(sⱼ|sᵢ)
4. Emission probabilities: B = {bᵢₖ} = P(oₖ|sᵢ)
5. Initial probabilities: π = {πᵢ} = P(s₁ = sᵢ)

Three Fundamental Problems

1. Evaluation: Given model λ and observation sequence O, find P(O|λ)

2. Decoding: Given model λ and observations O, find most likely state sequence
3. Learning: Given observations O, find model parameters λ

Applications

 Speech recognition
  Natural language processing
 Bioinformatics (gene sequence analysis)
 Financial modeling

Markov Assumption

P(sₜ₊₁|s₁, s₂, ..., sₜ) = P(sₜ₊₁|sₜ)

 Future state depends only on current state, not history

Key Formulas Summary

Probability

 Bayes' Rule: P(A|B) = P(B|A)P(A)/P(B)

 Product Rule: P(A∩B) = P(A)P(B|A)

Gaussian Distribution

 Univariate: p(x) = (1/√(2πσ²))exp[-(x-μ)²/(2σ²)]

 Multivariate: p(x) = (1/((2π)^(d/2)|Σ|^(1/2)))exp[-½(x-μ)ᵀΣ⁻¹(x-μ)]

Parameter Estimation

 ML Mean: μ̂ = (1/n)Σxᵢ
 ML Variance: σ̂² = (1/n)Σ(xᵢ - μ̂)²
 Unbiased Variance: s² = (1/(n-1))Σ(xᵢ - μ̂)²

PCA

 Covariance Matrix: C = (1/n)Σ(xᵢ - x̄ )(xᵢ - x̄ )ᵀ

 Principal Components: Cuᵢ = λᵢuᵢ

This comprehensive guide covers all major concepts from both units. Focus on understanding
the intuition behind each method, when to use each approach, and practice working through
the mathematical derivations.