Transcript 2.4 Adaptive Classifiers

Biometric Authentication Systems
林維暘
中正大學 資訊工程學系
九十五學年度 第二學期
Agenda
§ 2.1 Introduction
§ 2.2 Design Tradeoffs
§ 2.3 Feature Extraction
§ 2.4 Adaptive Classifiers
Biometric Authentication
2
Introduction
• There is a rapidly increasing interest in the
development of commercial systems for
biometric authentication applications.
• The objective of a commercial system is to
satisfy security requirement while incurring
minimal cost.
• This chapter discusses system deployment
requirements as well as critical design tradeoffs.
Biometric Authentication
3
Agenda
§ 2.1 Introduction
§ 2.2 Design Tradeoffs
§ 2.3 Feature Extraction
§ 2.4 Adaptive Classifiers
Biometric Authentication
4
2.2 Design Tradeoffs
§ 2.2.1 Accuracy vs. Intrusiveness
§ 2.2.2 Recognition vs. Verification
§ 2.2.3 Centralized vs. Distributed
§ 2.2.4 Processing Speed
§ 2.2.5 Storage Requirements
§ 2.2.6 Compatibility between Feature
Extractor and Classifier
Biometric Authentication
5
2.2 Design Tradeoffs
• To evaluate a biometric system’s accuracy, the
most adopted metrics are
– False Rejection Rate (FRR)
– False Acceptance Rate (FAR).
Biometric Authentication
6
False Rejection Rate
• FRR, or miss probability, is the percentage of
authorized individuals rejected by the system.
• Sensitivity, a.k.a. True Positive Rate (TPR), is
the percentage that an authorized person is
admitted.
FRR = 1 - TPR
Biometric Authentication
7
False Acceptance Rate
• FAR, a.k.a. False Positive Rate (FPR), is the
percentage that unauthorized individuals are
accepted by the system.
• Specificity, a.k.a. True Negative Rate (TNR), is
the percentage that an unauthorized person is
correctly rejected.
FAR = FPR = 1 - TNR
Biometric Authentication
8
The ROC Curve
• A good authentication system should have both
low FRR and low FAR.
• Typically, the tradeoff is illustrated by so-called
Receiver Operation Characteristic (ROC) curves
or by the Detection Error Tradeoff (DET) curves.
• Tradeoff between FAR and FRR is adjusted by
varying the threshold.
Biometric Authentication
9
The ROC Curve
Biometric Authentication
10
The ROC Curve
Biometric Authentication
11
ROC and DET curves
DET curve
1
0.9
0.9
0.8
0.8
False Rejection Rate (FRR)
True Positive Rate (TPR)
ROC curve
1
0.7
0.6
0.5
0.4
0.3
0.7
0.6
0.5
0.4
0.3
0.2
0.2
0.1
0.1
0
-4
10
-3
10
-2
-1
10
10
False Acceptance Rate (FAR)
0
10
0
-4
10
Biometric Authentication
-3
10
-2
0
-1
10
10
10
False Acceptance Rate (FAR)
12
2.2.1 Accuracy vs. Intrusiveness
• Physiological characteristics (e.g.,
fingerprint and iris) generally provide
higher accuracy than behavioral features
(e.g., voice and signature).
– Behavioral features can change from daty to
day.
– Physiological characteristics always remain
the same.
Biometric Authentication
13
2.2.1 Accuracy vs. Intrusiveness
• If a security system makes users feel
uncomfortable, then it is intrusive.
• For low security level environments (e.g.
apartments, hotels), an intrusive system is
highly undesirable.
• On the other hand, intrusive systems are
commonly deployed in high security areas.
Biometric Authentication
14
2.2.1 Accuracy vs. Intrusiveness
Intrusiveness
Convenience
Error rate
Face
No
Good
10-1 ~ 10-3
Palm
No?
Middle
< 10-3
Fingerprint
Yes
Middle
10-2 ~ 10-6
Iris
Yes
Bad
< 10-6
Voice
No
Middle
10-1 ~ 10-2
Signature
No
Bad
10-1 ~ 10-3
Biometric Authentication
15
2.2.2 Identification vs. Verification
• Identification
– Search a database for an acceptable match
– Higher computational cost
– Higher error rate
• Verification
– Verify the identity of a user
– Greatly reduced FAR
– Slightly increased FRR
Biometric Authentication
16
2.2.3 Centralized vs. Distributed
• Three major components in a biometric
system
– Sensor
– Pattern matcher
– Controller
• These pieces can be configured in various
ways.
– Centralized
– Distributed
Biometric Authentication
17
Central
transaction
logging
Central
matcher
&
controller
Central
template
database
sensor
sensor
sensor
sensor
Centralized system architecture
user
18
Central
transaction
logging
Central
template
database
Central
controller
matcher
matcher
sensor
sensor
Local DB
Local DB
matcher
matcher
sensor
sensor
user
Local DB
Local DB
Distributed system architecture
19
2.2.3 Centralized vs. Distributed
Distributed System
Centralized System
Less communication loading More communication loading
Lower risk of system failure
Higher risk of system failure
Maintenance is more
complex
Less management issues
Biometric Authentication
20
2.2.4 Processing Speed
• If a gateway control system takes on hour
to process one entry request, it is useless
no mater how accurate it is.
• Fingerprint identification system
– 18 types of fingerprint features
– Error rate of 10-10 can be achieved
– Accuracy is usually sacrificed for speed
[198,295]
Biometric Authentication
21
2.2.5 Data Storage Requirements
• In most scenarios, the size of raw data is
too large to store.
• Raw data is compressed into feature
vectors with much smaller dimension.
– Pentland et al. [272] compress a 256 x 256
image to a 20-dimnesional feature vector.
• Application types dictate the system
architecture
– e.g., Central or local database
Biometric Authentication
22
2.2.6 Compatibility between
Feature Extractor and Classifier
• A recognition system involves mapping between
the following spaces.
– Instantiation space: A symbol is instantiated into an
object. A symbol may have different instantiations.
– Feature space: The mapping from instantiation space
to feature space is called feature extraction.
– Symbol space: The symbols represent classes of
objects. The mapping from feature space to symbol
space is called classification.
Biometric Authentication
23
Compatibility between Feature
Extractor and Classifier
• Feature extraction
– The most important stage in a recognition
system
– Represented by a mapping from instantiation
space x to feature space v.
x → v = f(x)
Biometric Authentication
24
Compatibility between Feature
Extractor and Classifier
• Classification
– The mapping from feature space to symbol
space
– A two-class classifier
• Discriminant function j(v)
• j(v) > 0 if feature vector is extracted from an
instantiation belonging to one class.
• j(v) < 0 if feature vector is extracted from an
instantiation belonging to the other class.
Biometric Authentication
25
Compatibility between Feature
Extractor and Classifier
• In order to design an effective system, one
needs to consider not only feature
extraction but also classification.
Raw Data
Feature
Extractor
(e.g. speech waveform,
fingerprint images, facial
images)
Pattern Classifier
Feature
Vectors
(e.g. neural networks)
Biometric Authentication
Classification Decisions
(e.g. ID of claimants, accept/reject)
26
Agenda
§ 2.1 Introduction
§ 2.2 Design Tradeoffs
§ 2.3 Feature Extraction
§ 2.4 Adaptive Classifiers
Biometric Authentication
27
2.3 Feature Extraction
§ 2.3.1 Criteria of feature extraction
§ 2.3.2 Projection methods for dimension
reduction
§ 2.3.3 Feature selection
§ 2.3.4 Clustering methods
Biometric Authentication
28
2.3.1 Criteria of Feature Extraction
• Data compression
– Only vital representations are extracted.
• Informative ness
– The characteristics essential for the intended
applications should be best described.
• Invariance
– The dependency on environmental conditions should
be minimized.
• Ease of processing
– A cost-effective implementation should be feasible.
Biometric Authentication
29
2.3.1 Criteria of Feature Extraction
• Two approaches are often adopted to
obtain compressed representation.
– Dimension reduction by projection onto linear
subspace
– Data clustering (Chapter 3)
Biometric Authentication
30
2.3.2 Projection Methods for
Dimension Reduction
• Principal Component Analysis (PCA)
– A mapping from Rn to Rm, n > m
– Mathematically, the PCA is to find a matrix W
such that
y = W x, where W is an mxn matrix
– The W is formed by the m eigenvectors
corresponding to the largest m eigenvalues
Biometric Authentication
31
2.3.2 Projection Methods for
Dimension Reduction
• Independent Component Analysis (ICA)
– ICA extracts components with higher-order
statistical independence.
– Kurtosis of a random variable is defined as
E[Y 4 ]
k (Y ) 
E[Y 2 ]2
Biometric Authentication
32
Independent Component Analysis
1. Gaussian:
k(y)
3
2. Uniform:
k(y)
1.8
3. Binary:
k(y)
1
Biometric Authentication
33
Independent Component Analysis
• PCA maximizes the second-order
covariance.
• ICP maximizes the fourth-order kurtosis.
– An advantage of using ICA is that kurtosis
function is scale invariant.
– The most discriminative independent
component
E[(wx ) 4 ]
min
w E[( wx ) 2 ]2
Biometric Authentication
34
Independent Component Analysis
• Mathematically, the ICA is to find a matrix
W such that
y = W x, where W is an mxn matrix
– y contains the m most discriminative
independent components.
– The W is formed by the m independent row
vectors wi, which can be extracted
sequentially.
Biometric Authentication
35
2.3.3 Feature Selection
• Sometimes, only a few selected features
would suffice.
– In Hong Kong stock market, only 33 stocks
are selected to calculate the Hang Seng index.
• Note that unlike dimension reduction,
there is no linear combination in the
feature selection.
Biometric Authentication
36
2.3.3 Feature Selection
• Fisher Discriminant Analysis
– Fisher discriminant J(xi) represents the ration of interclass distance to intra-class variance
( m1i  m 2i ) 2
J ( xi ) 
s 12i  s 22i
– m1i and m2i denote the means of xi belonging to class
1 and class 2, respectively.
– s1i and s2i denote the variances of xi belonging to
class 1 and class 2, respectively.
Biometric Authentication
37
2.3.3 Feature Selection
• Fisher Discriminant Analysis
– The value of J(xi) provides a simple mean for
feature selection.
– The selected features will correspond to the
indices with better discriminating capability.
Biometric Authentication
38
2.3.4 Clustering Methods: GMM
• Most biometric data cannot be adequately
modeled by a single–cluster Gaussian
model.
• Gaussian Mixture Model (GMM) provides
a more flexible model for describing the
distribution of biometric data.
– K-means or EM algorithms
– Optimal number of clusters
Biometric Authentication
39
Project-Then-Cluster
• We can adopt more sophisticated
strategies such as cluster-the-project or
project-then-cluster.
• Cluster-then-project
– A projection aimed at separating two classes,
each modeled by a GMM [404].
Biometric Authentication
40
PCA
2-dimensional space (x-space)
Model Selection
User Interaction + EM + MDL
•Cluster initialization
•Clustering in x-space
•Model validation
EM
(Probabilistic Clustering)
•Clustering in t-space
Gaussian Mixture Model
Page 27
Fig 2.7
An illustration of the project-then-cluster approach. Projection
of data from t-space to x-space, then after clustering in the lower-dimension
subspace, trace the membership information back to the t-space
Biometric Authentication
41
Agenda
§ 2.1 Introduction
§ 2.2 Design Tradeoffs
§ 2.3 Feature Extraction
§ 2.4 Adaptive Classifiers
Biometric Authentication
42
2.4 Adaptive Classifiers
§ 2.4.1 Neural networks
§ 2.4.2 Training strategies
§ 2.4.3 Criteria on classifiers
§ 2.4.4 Availability of training samples
Biometric Authentication
43
2.4 Adaptive Classifiers
• Statistical approach
– Each class is modeled by a normal
distribution
– Using prior probabilities, one can compute the
posterior probabilities of each person,
conditioned on an observation.
Biometric Authentication
44
2.4.1 Neural Networks
• A neural work is a simulation of the nervous
system that contains neuron unit communicating
with one another via axon connections.
• By combining a vast number of simple neurons,
it is possible to achieve a sophisticated task.
• Neural networks for biometric applications are
discussed in Chapter 5, 6, and 7.
Biometric Authentication
45
2.4.2 Training Strategies
• Neural networks can learn rules from a
collection of examples.
• The ability to learn from examples is a
major advantage of neural networks.
• Two types of learning:
– Supervised
– Unsupervised
Biometric Authentication
46
2.4.2 Training Strategies
• Supervised learning
– A neural network is provided with a training
set with labels (the “teacher values”).
– The parameters are determined so that the
system can produce answers as close as
possible to the teacher values
– e.g., OCR and speaker recognition
Biometric Authentication
47
2.4.2 Training Strategies
• Unsupervised learning
– Explore the underlying rules from an
unlabeled training set
– Used in the applications where teacher values
are expensive or difficult to obtain
Biometric Authentication
48
2.4.3 Criteria on Classifiers
• The performance metrics of a learning algorithm
– training accuracy: obtained from the training data
– generalization accuracy: obtained from the testing
data
• There is usually a distinction between training
and generalization accuracies.
• High training accuracy does not necessarily
yield good generalization accuracy.
Biometric Authentication
49
2.4.3 Criteria on Classifiers
• Invariance and noise resilience
– Minimize the dependency on environmental
conditions.
– Tolerate noise corruption because noise is
inevitable in practical applications.
Biometric Authentication
50
2.4.3 Criteria on Classifiers
• Cost-effective system implementation
– A cost-effective platform should be considered.
– Emphasis should also be placed on the
issues of system integration.
Biometric Authentication
51
2.4.4 Availability of Training Samples
• The availability of training data is of critical
concern.
• Solutions to the training sample deficiency
problem
– Conduct an intensive study on the nature of
the selected biometric.
– Virtual pattern generation
Biometric Authentication
52
Intensive study
• An example: fingerprint
– The relative positions between various
minutiae are the discriminative features.
– The resulting feature vectors could be
separated by simple classifiers.
– There is no need to use example to tell the
system which features should be extracted.
Biometric Authentication
53
Virtual pattern generation
• Create additional training samples
– 200 virtual images are generated from one
facial image
– Chimerical data
Biometric Authentication
54
2.5 Visual-Based Biometric Systems
Biometric Authentication
55
2.6 Audio-Based Biometric Systems
Biometric Authentication
56