Statistical Classifiers in Computer Vision
Computer Vision – TP13
Statistical Classifiers
M
i
g
u
e
l
T
a
v
a
r
e
s
C
o
i
m
b
r
a
Computer Vision – TP13 - Statistical Classifiers
Outline
•
Statistical Classifiers
•
Neural Networks
•
Support Vector Machines
2
Computer Vision – TP13 - Statistical Classifiers
Topic: Statistical Classifiers
•
Statistical Classifiers
•
Neural Networks
•
Support Vector Machines
3
Computer Vision – TP13 - Statistical Classifiers
Statistical PR
•
I
u
s
e
s
t
a
t
i
s
t
i
c
s
t
o
m
a
k
e
a
d
e
c
i
s
i
o
n
–
I
c
a
n
m
a
k
e
d
e
c
i
s
i
o
n
s
e
v
e
n
w
h
e
n
I
d
o
n
’
t
h
a
v
e
f
u
l
l
a
p
r
i
o
r
i
k
n
o
w
l
e
d
g
e
o
f
t
h
e
w
h
o
l
e
p
r
o
c
e
s
s
–
I
c
a
n
m
a
k
e
m
i
s
t
a
k
e
s
•
H
o
w
d
i
d
I
r
e
c
o
g
n
i
z
e
t
h
i
s
p
a
t
t
e
r
n
?
–
I
l
e
a
r
n
f
r
o
m
p
r
e
v
i
o
u
s
o
b
s
e
r
v
a
t
i
o
n
s
w
h
e
r
e
I
k
n
o
w
t
h
e
c
l
a
s
s
i
f
i
c
a
t
i
o
n
r
e
s
u
l
t
–
I
c
l
a
s
s
i
f
y
a
n
e
w
o
b
s
e
r
v
a
t
i
o
n
4
Computer Vision – TP13 - Statistical Classifiers
Features
•
F
e
a
t
u
r
e
F
i
•
F
e
a
t
u
r
e
F
i
w
i
t
h
N
v
a
l
u
e
s
.
•
Feature vector F with
M features.
•
Naming conventions:
–
E
l
e
m
e
n
t
s
o
f
a
f
e
a
t
u
r
e
v
e
c
t
o
r
a
r
e
c
a
l
l
e
d
c
o
e
f
f
i
c
i
e
n
t
s
–
F
e
a
t
u
r
e
s
m
a
y
h
a
v
e
o
n
e
o
r
m
o
r
e
c
o
e
f
f
i
c
i
e
n
t
s
–
F
e
a
t
u
r
e
v
e
c
t
o
r
s
m
a
y
h
a
v
e
o
n
e
o
r
m
o
r
e
f
e
a
t
u
r
e
s
5
Computer Vision – TP13 - Statistical Classifiers
Classifiers
•
A
C
l
a
s
s
i
f
i
e
r
C
m
a
p
s
a
c
l
a
s
s
i
n
t
o
t
h
e
f
e
a
t
u
r
e
s
p
a
c
e
•
Various types of classifiers
–
Nearest-Neighbours
–
Neural Networks
–
Support Vector Machines
–
Etc...
6
Computer Vision – TP13 - Statistical Classifiers
Distance to Mean
•
I can represent a
class by its mean
feature vector
•
To classify a new
object, I choose the
class with the closest
mean feature vector
•
Different distance
measures!
Euclidean
Distance
7
Computer Vision – TP13 - Statistical Classifiers
Possible Distance Measures
•
L1 Distance
•
Euclidean Distance
(L2 Distance)
L1 or
Taxicab
Distance
8
Computer Vision – TP13 - Statistical Classifiers
Gaussian Distribution
•
Defined by two
parameters:
–
Mean:
μ
–
Variance:
σ
2
•
Great approximation
to the distribution of
many phenomena.
–
Central Limit Theorem
9
Computer Vision – TP13 - Statistical Classifiers
Multivariate Distribution
•
For N dimensions:
•
Mean feature vector:
•
Covariance Matrix:
10
Computer Vision – TP13 - Statistical Classifiers
Mahalanobis Distance
•
Based on the
covariance of
coefficients
•
Superior to
the Euclidean
distance
11
Computer Vision – TP13 - Statistical Classifiers
K-Nearest Neighbours
•
Algorithm
–
Choose the closest K
neighbours to a new
observation
–
C
l
a
s
s
i
f
y
t
h
e
n
e
w
o
b
j
e
c
t
b
a
s
e
d
o
n
t
h
e
c
l
a
s
s
o
f
t
h
e
s
e
K
o
b
j
e
c
t
s
•
Characteristics
–
Assumes no model
–
Does not scale very
well...
12
Computer Vision – TP13 - Statistical Classifiers
Topic: Neural Networks
•
Statistical Classifiers
•
Neural Networks
•
Support Vector Machines
13
Computer Vision – TP13 - Statistical Classifiers
If you can’t beat it.... Copy it!
http://managementcraft.typepad.com/photos/uncategorized/brain.jpg
14
Computer Vision – TP13 - Statistical Classifiers
Biological Neural Networks
•
Neuroscience:
–
Population of
physically inter-
connected neurons
•
Includes:
–
B
i
o
l
o
g
i
c
a
l
N
e
u
r
o
n
s
–
C
o
n
n
e
c
t
i
n
g
S
y
n
a
p
s
e
s
•
The human brain:
–
100 billion neurons
–
100 trillion synapses
15
Computer Vision – TP13 - Statistical Classifiers
Biological Neuron
•
Neurons:
–
Have
K
inputs (
dendrites
)
–
Have 1 output (
axon
)
–
If the sum of the input
signals surpasses a
threshold
, sends an
action
potential
to the axon
•
Synapses
–
Transmit electrical signals
between neurons
16
Computer Vision – TP13 - Statistical Classifiers
Artificial Neuron
•
A
l
s
o
c
a
l
l
e
d
t
h
e
M
c
C
u
l
l
o
c
h
-
P
i
t
t
s
n
e
u
r
o
n
•
P
a
s
s
e
s
a
w
e
i
g
h
t
e
d
s
u
m
o
f
i
n
p
u
t
s
,
t
o
a
n
a
c
t
i
v
a
t
i
o
n
f
u
n
c
t
i
o
n
,
w
h
i
c
h
p
r
o
d
u
c
e
s
a
n
o
u
t
p
u
t
v
a
l
u
e
McCulloch, W. and Pitts, W. (1943). A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biophysics, 7:115 - 133.
17
Computer Vision – TP13 - Statistical Classifiers
Sample activation functions
•
Rectified Linear Unit (ReLU)
•
Sigmoid function
18
Computer Vision – TP13 - Statistical Classifiers
Artificial Neural Network
•
C
o
m
m
o
n
l
y
r
e
f
e
r
e
d
a
s
N
e
u
r
a
l
N
e
t
w
o
r
k
•
Basic principles:
–
One neuron can
perform a simple
decision
–
M
a
n
y
c
o
n
n
e
c
t
e
d
n
e
u
r
o
n
s
c
a
n
m
a
k
e
m
o
r
e
c
o
m
p
l
e
x
d
e
c
i
s
i
o
n
s
19
Computer Vision – TP13 - Statistical Classifiers
Characteristics of a NN
•
Network configuration
–
How are the neurons inter-connected?
–
We typically use
layers
of neurons (input,
output, hidden)
•
Individual Neuron parameters
–
Weights associated with inputs
–
Activation function
–
Decision
thresholds
How do we
find these
values?
20
Computer Vision – TP13 - Statistical Classifiers
Learning paradigms
•
We can define the network configuration
•
H
o
w
d
o
w
e
d
e
f
i
n
e
n
e
u
r
o
n
w
e
i
g
h
t
s
a
n
d
d
e
c
i
s
i
o
n
t
h
r
e
s
h
o
l
d
s
?
–
L
e
a
r
n
i
n
g
s
t
e
p
–
W
e
t
r
a
i
n
t
h
e
N
N
t
o
c
l
a
s
s
i
f
y
w
h
a
t
w
e
w
a
n
t
•
Different learning paradigms
–
Supervised learning
–
Unsupervised learning
–
Reinforcement learning
A
p
p
r
o
p
r
i
a
t
e
f
o
r
P
a
t
t
e
r
n
R
e
c
o
g
n
i
t
i
o
n
.
21
Computer Vision – TP13 - Statistical Classifiers
Learning
•
W
e
w
a
n
t
t
o
o
b
t
a
i
n
a
n
o
p
t
i
m
a
l
s
o
l
u
t
i
o
n
g
i
v
e
n
a
s
e
t
o
f
o
b
s
e
r
v
a
t
i
o
n
s
•
A
c
o
s
t
f
u
n
c
t
i
o
n
m
e
a
s
u
r
e
s
h
o
w
c
l
o
s
e
o
u
r
s
o
l
u
t
i
o
n
i
s
t
o
t
h
e
o
p
t
i
m
a
l
s
o
l
u
t
i
o
n
•
Objective of our learning step:
–
M
i
n
i
m
i
z
e
t
h
e
c
o
s
t
f
u
n
c
t
i
o
n
Backpropagation
Algorithm
22
Computer Vision – TP13 - Statistical Classifiers
Backpropagation
For more details
please study Dr.
Andrew Moore’s
excellent tutorials
http://www.cs.cmu.edu/~awm/tutorials.html
23
Computer Vision – TP13 - Statistical Classifiers
Feedforward neural network
•
Simplest type of NN
•
Has no
cycles
•
Input layer
–
Need as many
neurons as
coefficients of my
feature vector
•
Hidden layers
•
Output layer
–
Classification results
24
Computer Vision – TP13 - Statistical Classifiers
Topic: Support Vector Machines
•
Statistical Classifiers
•
Neural Networks
•
Support Vector Machines
25
Computer Vision – TP13 - Statistical Classifiers
Maximum-margin hyperplane
•
T
h
e
r
e
a
r
e
m
a
n
y
p
l
a
n
e
s
t
h
a
t
c
a
n
s
e
p
a
r
a
t
e
o
u
r
c
l
a
s
s
e
s
i
n
f
e
a
t
u
r
e
s
p
a
c
e
•
O
n
l
y
o
n
e
m
a
x
i
m
i
z
e
s
t
h
e
s
e
p
a
r
a
t
i
o
n
m
a
r
g
i
n
•
Of course that
classes need to be
separable in the first
place...
26
Computer Vision – TP13 - Statistical Classifiers
Support vectors
•
T
h
e
m
a
x
i
m
u
m
-
m
a
r
g
i
n
h
y
p
e
r
p
l
a
n
e
i
s
l
i
m
i
t
e
d
b
y
s
o
m
e
v
e
c
t
o
r
s
•
T
h
e
s
e
a
r
e
c
a
l
l
e
d
s
u
p
p
o
r
t
v
e
c
t
o
r
s
•
Other vectors are
irrelevant for my
decision
27
Computer Vision – TP13 - Statistical Classifiers
Decision
•
I
m
a
p
a
n
e
w
o
b
s
e
r
v
a
t
i
o
n
i
n
t
o
m
y
f
e
a
t
u
r
e
s
p
a
c
e
•
Decision hyperplane:
•
Decision function:
A
v
e
c
t
o
r
i
s
e
i
t
h
e
r
a
b
o
v
e
o
r
b
e
l
o
w
t
h
e
h
y
p
e
r
p
l
a
n
e
28
Computer Vision – TP13 - Statistical Classifiers
Slack
variables
•
M
o
s
t
f
e
a
t
u
r
e
s
p
a
c
e
s
c
a
n
n
o
t
b
e
s
e
g
m
e
n
t
e
d
s
o
e
a
s
i
l
y
b
y
a
h
y
p
e
r
p
l
a
n
e
•
Solution:
–
Use slack variables
–
‘Wrong’ points ‘pull’
the margin in their
direction
–
Classification errors!
29
Computer Vision – TP13 - Statistical Classifiers
But this doesn’t work in most
situations...
•
S
t
i
l
l
,
h
o
w
d
o
I
f
i
n
d
a
M
a
x
i
m
u
m
-
m
a
r
g
i
n
h
y
p
e
r
p
l
a
n
e
f
o
r
s
o
m
e
s
i
t
u
a
t
i
o
n
s
?
•
Most real situations face this problem...
30
Computer Vision – TP13 - Statistical Classifiers
Solution: Send it to hyperspace!
•
T
a
k
e
t
h
e
p
r
e
v
i
o
u
s
c
a
s
e
:
f
(
x
)
=
x
•
C
r
e
a
t
e
a
n
e
w
h
i
g
h
e
r
-
d
i
m
e
n
s
i
o
n
a
l
f
u
n
c
t
i
o
n
:
g
(
x
2
)
=
(
x
,
x
2
)
•
A
k
e
r
n
e
l
f
u
n
c
t
i
o
n
i
s
r
e
s
p
o
n
s
i
b
l
e
f
o
r
t
h
i
s
t
r
a
n
s
f
o
r
m
a
t
i
o
n
https://www.youtube.com/watch?v=3liCbRZPrZA
31
Computer Vision – TP13 - Statistical Classifiers
Typical kernel functions
32
Computer Vision – TP13 - Statistical Classifiers
Classification
•
Training stage:
–
Obtain kernel parameters
–
Obtain maximum-margin hyperplane
•
G
i
v
e
n
a
n
e
w
o
b
s
e
r
v
a
t
i
o
n
:
–
Transform it using the kernel
–
Compare it to the hyperspace
33
Computer Vision – TP13 - Statistical Classifiers
Resources
•
Andrew Moore, “Statistical Data Mining
Tutorials”,
http://www.cs.cmu.edu/~awm/tutorials.htm
l
•
C.J. Burges, “A tutorial on support vector
machines for pattern recognition”, in
Knowledge Discovery Data Mining, vol.2,
no.2, 1998, pp.1-43.
34
This content delves into the utilization of statistical classifiers within computer vision, particularly focusing on their application and significance in the field. The exploration spans various methodologies and techniques employed to enhance the efficiency and accuracy of classifiers when analyzing visual data. Through a detailed examination, this material aims to provide valuable insights into the role of statistical classifiers in advancing computer vision technologies and applications.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Computer Vision TP13 Statistical Classifiers Miguel Tavares Coimbra
Outline Statistical Classifiers Neural Networks Support Vector Machines Computer Vision TP13 - Statistical Classifiers 2
Topic: Statistical Classifiers Statistical Classifiers Neural Networks Support Vector Machines Computer Vision TP13 - Statistical Classifiers 3
Statistical PR I use statistics to make a decision I can make decisions even when I don t have full a priori knowledge of the whole process I can make mistakes How did I recognize this pattern? I learn from previous observations where I know the classification result I classify a new observation Computer Vision TP13 - Statistical Classifiers 4
Features Feature Fi Naming conventions: Elements of a feature vector are called coefficients Features may have one or more coefficients Feature vectors may have one or more features f F = i i Feature Fiwith N values. i i f F , 1 = ,..., f f 2 i iN Feature vector F with M features. F F F | 2 1 = | ... | F M Computer Vision TP13 - Statistical Classifiers 5
Classifiers A Classifier C maps a class into the feature space , true y K = ( , ) C x y Spain , false otherwise Various types of classifiers Nearest-Neighbours Neural Networks Support Vector Machines Etc... Computer Vision TP13 - Statistical Classifiers 6
Distance to Mean I can represent a class by its mean feature vector C = Feature Space 35 30 Spain Euclidean Distance F 25 To classify a new object, I choose the class with the closest mean feature vector Different distance measures! 20 Y Coordinate 15 10 Portugal 5 0 Porto -10 0 10 20 30 -5 -10 X Coordinate Computer Vision TP13 - Statistical Classifiers 7
Possible Distance Measures L1 Distance N = x 1 L1 or Taxicab Distance = L 1 ( ) ( ) S x v x N 1 Euclidean Distance (L2 Distance) N ( ) = x 1 2 = L2 ( ) ( ) S x v x N 1 Computer Vision TP13 - Statistical Classifiers 8
Gaussian Distribution Defined by two parameters: Mean: Variance: 2 Great approximation to the distribution of many phenomena. Central Limit Theorem 2 1 ( ) x u = ( ) exp f x 2 2 2 Computer Vision TP13 - Statistical Classifiers 9
Multivariate Distribution For N dimensions: Mean feature vector: Covariance Matrix: = F Computer Vision TP13 - Statistical Classifiers 10
Mahalanobis Distance Based on the covariance of coefficients Superior to the Euclidean distance Computer Vision TP13 - Statistical Classifiers 11
K-Nearest Neighbours Algorithm Choose the closest K neighbours to a new observation Classify the new object based on the class of these K objects Characteristics Assumes no model Does not scale very well... Computer Vision TP13 - Statistical Classifiers 12
Topic: Neural Networks Statistical Classifiers Neural Networks Support Vector Machines Computer Vision TP13 - Statistical Classifiers 13
If you cant beat it.... Copy it! Computer Vision TP13 - Statistical Classifiers 14 http://managementcraft.typepad.com/photos/uncategorized/brain.jpg
Biological Neural Networks Neuroscience: Population of physically inter- connected neurons Includes: Biological Neurons Connecting Synapses The human brain: 100 billion neurons 100 trillion synapses Computer Vision TP13 - Statistical Classifiers 15
Biological Neuron Neurons: Have K inputs (dendrites) Have 1 output (axon) If the sum of the input signals surpasses a threshold, sends an action potential to the axon Synapses Transmit electrical signals between neurons Computer Vision TP13 - Statistical Classifiers 16
Artificial Neuron Also called the McCulloch-Pitts neuron Passes a weighted sum of inputs, to an activation function, which produces an output value McCulloch, W. and Pitts, W. (1943). A logical calculus of the ideas immanent in nervous activity. Bulletin of Mathematical Biophysics, 7:115 - 133. Computer Vision TP13 - Statistical Classifiers 17
Sample activation functions Rectified Linear Unit (ReLU) Sigmoid function 1 =1 y + u e Computer Vision TP13 - Statistical Classifiers 18
Artificial Neural Network Commonly refered as Neural Network Basic principles: One neuron can perform a simple decision Many connected neurons can make more complex decisions Computer Vision TP13 - Statistical Classifiers 19
Characteristics of a NN Network configuration How are the neurons inter-connected? We typically use layers of neurons (input, output, hidden) Individual Neuron parameters Weights associated with inputs Activation function Decision thresholds How do we find these values? Computer Vision TP13 - Statistical Classifiers 20
Learning paradigms We can define the network configuration How do we define neuron weightsand decision thresholds? Learning step We train the NN to classify what we want Different learning paradigms Supervised learning Unsupervised learning Reinforcement learning Appropriate for Pattern Recognition. Computer Vision TP13 - Statistical Classifiers 21
Learning We want to obtain an optimal solution given a set of observations A cost function measures how close our solution is to the optimal solution Objective of our learning step: Minimize the cost function Backpropagation Algorithm Computer Vision TP13 - Statistical Classifiers 22
Backpropagation For more details please study Dr. Andrew Moore s excellent tutorials http://www.cs.cmu.edu/~awm/tutorials.html Computer Vision TP13 - Statistical Classifiers 23
Feedforward neural network Simplest type of NN Has no cycles Input layer Need as many neurons as coefficients of my feature vector Hidden layers Output layer Classification results Computer Vision TP13 - Statistical Classifiers 24
Topic: Support Vector Machines Statistical Classifiers Neural Networks Support Vector Machines Computer Vision TP13 - Statistical Classifiers 25
Maximum-margin hyperplane There are many planes that can separate our classes in feature space Only one maximizes the separation margin Of course that classes need to be separable in the first place... M , 1 + } 1 ( : ) x { f , 1 + } 1 { C = M { , ,..., }, V v v v v 1 2 M i Computer Vision TP13 - Statistical Classifiers 26
Support vectors The maximum- margin hyperplane is limited by some vectors These are called support vectors Other vectors are irrelevant for my decision Computer Vision TP13 - Statistical Classifiers 27
Decision I map a new observation into my feature space Decision hyperplane: = + w b x w , 0 ) . ( N, b Decision function: = + ( ) (( . ) ) f x sign w x b A vector is either above or below the hyperplane Computer Vision TP13 - Statistical Classifiers 28
Slack variables Most feature spaces cannot be segmented so easily by a hyperplane Solution: Use slack variables Wrong points pull the margin in their direction Classification errors! Computer Vision TP13 - Statistical Classifiers 29
But this doesnt work in most situations... Still, how do I find a Maximum-margin hyperplane for some situations? Most real situations face this problem... Computer Vision TP13 - Statistical Classifiers 30
Solution: Send it to hyperspace! Take the previous case: f(x) = x Create a new higher- dimensional function: g(x2) = (x, x2) A kernel function is responsible for this transformation https://www.youtube.com/watch?v=3liCbRZPrZA Computer Vision TP13 - Statistical Classifiers 31
Typical kernel functions Linear = + ( , ) . 1 K x y x y Polynomial = ) 1 + p ( , ) ( . K x y x y Radial-Base Functions 2 2 / 2 x y = ( , ) K x y e Sigmoid = ( , ) tanh( . ) K x y kx y Computer Vision TP13 - Statistical Classifiers 32
Classification Training stage: Obtain kernel parameters Obtain maximum-margin hyperplane Given a new observation: Transform it using the kernel Compare it to the hyperspace Computer Vision TP13 - Statistical Classifiers 33
Resources Andrew Moore, Statistical Data Mining Tutorials , http://www.cs.cmu.edu/~awm/tutorials.htm l C.J. Burges, A tutorial on support vector machines for pattern recognition , in Knowledge Discovery Data Mining, vol.2, no.2, 1998, pp.1-43. Computer Vision TP13 - Statistical Classifiers 34
