Transcript Pattern Recognition

Pattern Recognition
Why?
• To provide machines with perception & cognition
capabilities so that they could interact independently
with their environments.
Pattern Recognition
• a natural ability of human
• based on some description of an object, such
description is termed Pattern.
Lecture #1
COMP 527 Pattern Recognition
1
Patterns and Pattern Classes
• Almost anything within the reach of our five senses can
be chosen as a pattern:
– Sensory patterns: speech, odors, tastes
– Spatial patterns: characters, fingerprints, pictures
– Temporal patterns: waveforms, electrocardiograms, movies
– Conceptual recognition for abstract items
(We will limit ourselves to deal with only physical objects/
events, but NOT abstract entities, say, concepts.)
• A pattern class is a group of patterns with certain
common characteristics.
Lecture #1
COMP 527 Pattern Recognition
2
Pattern Recognition
• Pattern Recognition is the science to assign an
object/event of interest to one of several prespecified
categories/classes based on certain measurements or
observations.
• Measurements are usually problem dependent.
E.g. weight or height for basketball players/jockeys
color for apples/oranges
• Feature vectors represent measurements as
coordinates of points in a vector space (feature space).
Lecture #1
COMP 527 Pattern Recognition
3
Pattern Recognition Systems
PR systems
Mathematical
Deterministic
Lecture #1
Structural
Statistic
Syntactic
COMP 527 Pattern Recognition
Linguistic
4
Statistical Pattern Recognition
• Taps into the vast and thorough knowledge of statistics
to provide a formal treatment of PR.
• Observations are assumed to be generated by a state of
nature
– data can be described by a statistical model
– model by a set of probability functions
• Strength: many powerful mathematical “tools” from
the theory of probability and statistics.
• Shortcoming: it is usually impossible to design
(statistically) errorfree systems.
Lecture #1
COMP 527 Pattern Recognition
5
Example: OCR
Lecture #1
COMP 527 Pattern Recognition
6
Major Steps
STEP
INPUT
OUTPUT
REMARKS
Feature
Raw data
Feature vectors Discriminative,
Extraction
invariant
Model building Feature vectors Math models Generalized,
accurate
classification Feature vectors Decided class Optimal, fast
+ class models
Lecture #1
COMP 527 Pattern Recognition
7
Raw Features: Example
Lecture #1
COMP 527 Pattern Recognition
8
Feature Extraction: OCR Example
Lecture #1
COMP 527 Pattern Recognition
9
Feature Extraction
Objectives: To remove irrelevant information and extract
distinctive, representative information of the objects.
• discriminative
• invariant
• data compression => dimension reduction
It is not easy!
Lecture #1
COMP 527 Pattern Recognition
10
Data Modeling
To build statistical models for describing the data.
• Parametric models
– single probability density function: e.g. Gaussian
– mixture density function: e.g. Gaussian mixture model
(GMM)
– hidden Markov model --- may cope with data of different
duration/length
• Nonparametric models
– k-nearest neighbor
– Parzen window
– neural network
Lecture #1
COMP 527 Pattern Recognition
11
Training
Training Data :
• Model is “learned” from a set of training data
• Data collection - should contain data from various
regions of the pattern space.
• Do you know the whole pattern space?
Training Algorithm : can be iterative.
• When to stop training?
Generalization : Models trained on a finite set of data
should also generalize well to unseen data.
• How to ensure that?
Lecture #1
COMP 527 Pattern Recognition
12
Supervised vs. Unsupervised
Supervised PR
• Representative patterns from each pattern class under
consideration are available.
• Supervised learning.
Unsupervised PR
• A set of training patterns of unknown classification is
given.
• Unsupervised learning.
Lecture #1
COMP 527 Pattern Recognition
13
Classification
Classification of N Classes: can be thought as partitioning the
feature space into N regions, as nonoverlapping as possible, so
that each region represents one of the N classes. Often called
DecisionTheoretic Approach
Decision Boundaries: the boundaries between the class regions in
the feature space.
Discriminant Functions: mathematical functions to describe the
decision boundaries.
Types of Classifiers: depending on the functional form of the
decision boundary, classifiers may be categorized into:
– Linear classifier
– Quadratic classifier
– Piecewise classifier
Lecture #1
COMP 527 Pattern Recognition
14
Decision Boundary
Lecture #1
COMP 527 Pattern Recognition
15
Summary
• Three main components: features, data model, and
recognition algorithm.
• Make sure you find out a good set of features to work
with before you build data models.
• Data modeling requires knowledge of statistics and
optimization.
• Recognition requires classifier design (i.e. the
discriminant functions), search, and algorithm design.
• Evaluation involves testing on unseen test data which
must be large enough in order to claim statistical
significance.
Lecture #1
COMP 527 Pattern Recognition
16