Pattern
Recognition
Perceptron (“single-layer perceptron”)
• simple NN for
linearly separable
patterns only
error correcting learning
y(n) = sgn w (n)x(n)
T
w(n + 1) = w(n) + d (n) − y(n)x(n)
if x(n) C1
+ 1 ak
d ( n) = {
if x(n) C2
− 1 ak
AIDP, M.Oravec, ICSM FEI STU
Linear and nonlinear separability
2 regions separated by hyperplane
p
w x − = 0
i =1
i i
Class C2
hyperplane
Class C1
Separating boundary
Linear separability – 2D inputs, 2 classes
AIDP, M.Oravec, ICSM FEI STU
Linear and nonlinear separability
Class C1
Class C1
Class C2
Class C2
Linearly separable patterns Nonlinearly separable patterns
(decision surfaces are hyperplanes)
AIDP, M.Oravec, ICSM FEI STU
linear and nonlinear separability
• Minsky a Papert 1969
• Perceptron is not able
to separate even XOR
(exclusive or) logical A B A XOR B
function! 0 0 0
0 1 1
• NN were dead… 1 0 1
1 1 0
• 1986: PDP group, MLP,
backpropagation
algorithm
AIDP, M.Oravec, ICSM FEI STU
• Good illustration of an ANN for data
classification
• http://playground.tensorflow.org
AIDP, M.Oravec, ICSM FEI STU
Typical application areas
• Machine vision
• Character recognition (OCR)
• Computer aided diagnosis
• Speech recognition
• Face recognition
• Biometrics
Pattern • Image Data Base retrieval
• Data mining
Recognition) • Bioinformatics
The task:
• Assign unknown objects – patterns –
into the correct class. This is known as
classification.
AIDP, M.Oravec, ICSM FEI STU
o Features: These are measurable quantities obtained from
the patterns, and the classification task is based on their
respective values.
o Feature vectors: A number of features
𝑥1 , . . . , 𝑥𝑝 ,
constitute the feature vector
𝑇
𝑥 = 𝑥1 , . . . , 𝑥𝑝 ∈ 𝑅𝑝
Feature vectors are treated as random vectors.
AIDP, M.Oravec, ICSM FEI STU
An example: medical image
classification
a graph of the mean
value of the intensities
of objects from their
standard deviation
AIDP, M.Oravec, ICSM FEI STU
class A Mean and
standard
class B deviation are
features
• To which class does a new image (*) belongs? With greater
probability to A
• classifier - with its decision boundary it divides the space of flags
into areas of classes A, B
• Here it is a linear decision boundary (straight line) obtained from
training patterns
AIDP, M.Oravec, ICSM FEI STU
• The classifier consists of a set of functions, whose values,
computed at x , determine the class to which the corresponding
pattern belongs
• Classification system overview
Patterns
sensor
feature
generation
feature
selection
classifier
design
system
evaluation
AIDP, M.Oravec, ICSM FEI STU
Watanabe defines a pattern as
opposite of a chaos; it is an entity,
vaguely defined, that could be given a
name.
• For example, a pattern could be a fingerprint
Pattern, image, a handwritten cursive word, a human
face, or a speech signal.
pattern Given a pattern, its
recognition/classification may consist
recognition of one of the following two tasks:
• 1) supervised classification (e.g., discriminant
analysis) in which the input pattern is identified
as a member of a predefined class,
• 2) unsupervised classification (e.g., clustering)
in which the pattern is assigned to a hitherto
unknown class.
AIDP, M.Oravec, ICSM FEI STU
The design of a pattern recognition system
essentially involves the following three
aspects:
1) data
2) data 3) decision
Design of a acquisition and
preprocessing,
representation, making.
pattern
recognition
system Learning from a set of examples (training
set) is an important and desired attribute
of most pattern recognition systems.
AIDP, M.Oravec, ICSM FEI STU
• The four best known approaches for
pattern recognition are:
1) template matching,
Approaches 2) statistical classification,
for pattern 3) syntactic or structural matching,
4) neural networks.
recognition These models are not
necessarily independent and
sometimes the same pattern
recognition method exists with
different interpretations.
Attempts have been made to
design hybrid systems.
AIDP, M.Oravec, ICSM FEI STU
1) Template Matching
Matching is a generic operation in pattern recognition which is used to determine
the similarity between two entities (points, curves, or shapes) of the same type.
In template matching, a template (typically, a 2D shape) or a prototype of the
pattern to be recognized is available.
• The pattern to be recognized is matched against the stored template while taking into account all
allowable pose (translation and rotation) and scale changes.
• The similarity measure, often a correlation, may be optimized based on the available training set.
Often, the template itself is learned from the training set.
Disadvantages
• if the patterns are distorted due to the imaging process, viewpoint change, or large intraclass
variations among the patterns.
AIDP, M.Oravec, ICSM FEI STU
2) Statistical Classification
Each pattern is represented in terms of p features or measurements and is viewed as
a point in a p-dimensional space.
The goal is to choose those features that allow pattern vectors belonging to different
categories to occupy compact and disjoint regions in a p-dimensional feature space.
Given a set of training patterns from each class, the objective is to establish decision
boundaries in the feature space which separate patterns belonging to different
classes.
• In the statistical decision theoretic approach, the decision boundaries are determined by the probability
distributions of the patterns belonging to each class, which must either be specified or learned
• One can also take a discriminant analysis-based approach to classification: First a parametric form of the
decision boundary (e.g., linear or quadratic) is specified; then the best decision boundary of the specified
form is found based on the classification of training patterns.
AIDP, M.Oravec, ICSM FEI STU
3) Syntactic (Structural) Matching
• hierarchical perspective where a pattern is viewed as being composed of simple subpatterns which
are themselves built from yet simpler subpatterns
• The simplest/elementary subpatterns to be recognized are called primitives and the given complex
pattern is represented in terms of the interrelationships between these primitives.
• In syntactic pattern recognition, a formal analogy is drawn between the structure of patterns and
the syntax of a language.
– The patterns are viewed as sentences belonging to a language, primitives are viewed as the
alphabet of the language, and the sentences are generated according to a grammar. Thus, a
large collection of complex patterns can be described by a small number of primitives and
grammatical rules. The grammar for each pattern class must be inferred from the available
training samples.
– Suitable, if the patterns have a definite structure which can be captured in terms of a set of
rules,
• such as EKG waveforms, textured images, and shape analysis of contours
– Difficulties which primarily have to do with the segmentation of noisy patterns (to detect the
primitives) and the inference of the grammar from training data.
AIDP, M.Oravec, ICSM FEI STU
4) Neural Networks
• massive parallel computing systems
• huge number of simple processors (neurons)
• huge number of connections
• learning, generalization, adaptability, fault tolerance, distributed representation
• artificial neuron
• the ability to learn the complex relationships between inputs and outputs
• nonlinearity
• simple learning algorithms
• nonlinear algorithms for
– Feature extraction
– classification
• good hardware implementation
• boom of deep networks
AIDP, M.Oravec, ICSM FEI STU
Pattern Recognition Models
AIDP, M.Oravec, ICSM FEI STU
STATISTICAL PATTERN
RECOGNITION
AIDP, M.Oravec, ICSM FEI STU
Statistical pattern recognition
• input pattern: p-dimensional input vector
• pattern represented by m features (m-dimensional feature
vector)
• determination of decision boundaries uses known methods
of statistical decision theory
• Two modes of operation of the pattern recognition system:
– training (learning)
– classification (testing))
AIDP, M.Oravec, ICSM FEI STU
Model of statistical pattern recognition
• preprocessing
• dimensionality reduction
– „the curse of dimensionality“ - number of trainings points is exp. function of
the feature dimension
– „peaking phenomenon" - for a fixed training. the set of features can degrade
the activity of the classifier (the number of training points is small due to the
number of features)
• feature extraction
• feature selection
• classification
AIDP, M.Oravec, ICSM FEI STU
Pattern recognition systems
• One-stage system, direct classification
x1
x2
input classifier decision
...
xp
• Two-stage system
x1 y1
x2 feature
input decision
...
classifier
...
extraction
xp ym
AIDP, M.Oravec, ICSM FEI STU
Pattern recognition systems
• One-stage system, direct classification
Pattern Preproces class
Classifica-
dim=p sing dim=p tion
Many methods from 1st
part of semester ☺
• Two-stage system (feature extraction + classification)
Pattern Class
Preproces Feature Feature Classifica-
dim=p sing extraction selection tion
dim=p dim=p dim=m
m<p
Many methods from 1st
part of semester ☺ AIDP, M.Oravec, ICSM FEI STU
FEATURE EXTRACTION
AIDP, M.Oravec, ICSM FEI STU
Feature extraction
• feature extraction
• feature – the most important property of data
Data Feature
space space
transformation
dim: p dim: m=p
dim: m<p
decorrelation
dimensionality reduction
AIDP, M.Oravec, ICSM FEI STU
❖Principal Components Analysis
(The Karhunen – Loève transform):
➢ The goal: Given an original set of m measurements x
m
compute y
y = AT x
for an orthogonal A, so that the elements of y are optimally
mutually uncorrelated.
That is
E y (i ) y ( j ) = 0, i j
➢ Sketch of the proof:
Ry = E y y = E A x x A = AT Rx A
T T T
AIDP, M.Oravec, ICSM FEI STU
• If A is chosen so that its columns a i are the orthogonal
eigenvectors of Rx, then
R y = AT Rx A =
where Λ is diagonal with elements the respective
eigenvalues λi.
• Observe that this is a sufficient condition but not
necessary. It imposes a specific orthogonal structure on
A.
➢ Properties of the solution
• Mean Square Error approximation.
Due to the orthogonality of A:
m
x = y (i )a i , y (i ) = a i x
T
i =0
AIDP, M.Oravec, ICSM FEI STU
− Define −1
xˆ = y (i )a i
i =0
− The Karhunen – Loève transform minimizes the
square error:
m
2
E x − xˆ = E y (i )a i
2
i =
− The error is:
E x − xˆ
2
=
m
i =
i
It can be also shown that this is the minimum mean
square error compared to any other representation of x
by an ℓ-dimensional vector.
AIDP, M.Oravec, ICSM FEI STU
− In other words, x̂ is the projection of x into the
subspace spanned by the principal ℓ eigenvectors.
However, for Pattern Recognition this is not the
always the best solution.
AIDP, M.Oravec, ICSM FEI STU
Example-computation of PCA (KLT)
AIDP, M.Oravec, ICSM FEI STU
PCA (KLT)
• Lindsay I Smith: A tutorial on Principal Components Analysis, 2002, http://www.cs.otago.ac.nz/cosc453/student_tutorials/principal_components.pdf
AIDP, M.Oravec, ICSM FEI STU
CLASSIFICATION
AIDP, M.Oravec, ICSM FEI STU
Statistical pattern recognition – decision making
process
• classifier proposal - classification according to what
information we have about class-conditional densities
– if all densities are known (but this is rare)
• Bayes' optimal rule
– if the densities are known, but some of their parameters are
not known
• parametric decision problem - unknown parameters are estimated
– if the densities are not known
• nonparametric problem
• either probability densities are estimated (eg Parzen window)
• or direct construction of the decision boundary from the training data
• e.g. k-nearest neighbor rule
• MLP is also a nonparametric method for constructing a decision boundary
AIDP, M.Oravec, ICSM FEI STU
Various approaches to statistical pattern recognition
AIDP, M.Oravec, ICSM FEI STU
Frequently
used
classifiers
AIDP, M.Oravec, ICSM FEI STU
Illustration of decision boundaries
• Data:
AIDP, M.Oravec, ICSM FEI STU
Illustration of decision boundaries
AIDP, M.Oravec, ICSM FEI STU
Statistical pattern recognition – decision making
process
• classifier proposal - classification according to what
information we have about class-conditional densities
– if all densities are known (but this is rare)
• Bayes' optimal rule
– if the densities are known, but some of their parameters are
not known
• parametric decision problem - unknown parameters are estimated
– if the densities are not known
• nonparametric problem
• either probability densities are estimated (eg Parzen window)
• or direct construction of the decision boundary from the training data
• e.g. k-nearest neighbor rule
• MLP is also a nonparametric method for constructing a decision boundary
AIDP, M.Oravec, ICSM FEI STU
K-NN RULE
k-Nearest Neighbour Rule
AIDP, M.Oravec, ICSM FEI STU
❖ The Nearest Neighbor Rule
➢ Choose k out of the N training vectors, identify the k
nearest ones to x
➢ Out of these k identify ki that belong to class ωi
➢ Assign x → i : ki k j i j
➢ The simplest version
k=1 !!!
➢ For large N this is not bad. It can be shown that:
if PB is the optimal Bayesian error probability, then:
M
PB PNN PB (2 − PB ) 2 PB
M −1
AIDP, M.Oravec, ICSM FEI STU
PB - probability of error of optimal
Bayes classifier
2 PNN
➢ PB PkNN PB +
k
➢ k → , PkNN → PB
➢ For small PB:
PNN 2 PB
P3 NN PB + 3( PB ) 2
AIDP, M.Oravec, ICSM FEI STU
❖ Voronoi tesselation
Ri = x : d ( x, x i ) d ( x, x j ) i j
AIDP, M.Oravec, ICSM FEI STU
Voronoi tessellation
◼ 2D case ◼ 3D case
AIDP, M.Oravec, ICSM FEI STU
kNN
◼ nice presentation:
http://courses.cs.tamu.edu/rgutier/cs790_w02/l8.pdf
AIDP, M.Oravec, ICSM FEI STU
kNN
http://courses.cs.tamu.edu/rgutier/cs790_w02/l8.pdf
AIDP, M.Oravec, ICSM FEI STU
kNN
http://courses.cs.tamu.edu/rgutier/cs790_w02/l8.pdf
AIDP, M.Oravec, ICSM FEI STU
kNN
http://courses.cs.tamu.edu/rgutier/cs790_w02/l8.pdf
AIDP, M.Oravec, ICSM FEI STU
Other nice solutions:
◼ ensemble learning
◼ SVM (support vector machine)
◼ neural networks
AIDP, M.Oravec, ICSM FEI STU
Other nice solutions: ensemble learning
AIDP, M.Oravec, ICSM FEI STU
Other nice solutions: ensemble learning
AIDP, M.Oravec, ICSM FEI STU
Other nice solution: SVM
◼ SVM
❑ https://www.youtube.com/watch?v=9NrALgHFwTo
❑ https://www.youtube.com/watch?v=ndNE8he7Nnk
AIDP, M.Oravec, ICSM FEI STU
Other nice solutions: NN
◼ Once again: good illustration of an ANN for data
classification ☺
❑ http://playground.tensorflow.org
AIDP, M.Oravec, ICSM FEI STU
