Final Project Questions
? Let’s take up to an hour to
– Review progress
– Answer questions
? Referencing sources in the term project
– Direct quotes -- Place in quotes or indent and
cite source in footnote or reference
– Extensive paraphrase -- Cite source at
beginning of chapter or section and explain
degree to which it was used in a footnote
– Common knowledge -- No reference req’d
16.881 MIT
Mahalanobis Taguchi System
Design of Systems which Rely on
Accurate Classification
=
?
16.881 MIT
Outline
? Review classification problems
? Introduce the Mahalanobis distance
? Demo on character recognition
? Mahalanobis Taguchi System (MTS)
? Case study on fire alarm system
16.881 MIT
Classification Problems
? Many systems function by classifying instances
into classes
– Character recognition
?Does R belong to A, B, C, ...?
– Fire detection
? Does this amount of smoke and heat indicate a fire or a BBQ?
– Air bag deployment
? Do these accelerometer inputs indicate a crash, a bumpy road,
a hard stop?
http://www-engr.sjsu.edu/~knapp/HCIRODPR/PR_home.htm
Pattern Recognition for HCI, Richard O. Duda
16.881
Department of Electrical Engineering, San Jose State University
MIT
Design Issues in
Classifier Systems
? What should be measured?
? How should measurements be processed?
? What is the criterion for demarcation?
? What are the consequences of error?
– Classified instance as A, but it isn’t A.
– Classified instance as not A, but it is.
16.881 MIT
Features
? Classification is made on the basis of
measured features
? Features should
– Be easy (or inexpensive) to measure or extract
– Clearly demarcate classes
?Examples
– Medical diagnosis
– Character recognition
DISPLAY( Clin) DISPLAY( Dlin)
16.881 MIT
Feature Vectors
? Generally, there are several features required to
make a classification
? These features x
i
can be assembled into a vector
? Any object to be classified is represented by a
point in n dimensional feature space
?
x
1
?
? ?
x =
?
x
2
?
? ?
?
x
3 ?
x
1
x
2
x
3
x
16.881 MIT
Joint Gaussian Distribution
? Density function entirely
determined by mean vector
and correlation matrix
? Curves of constant
m
x
2
x
1
probability are ellispoids
? ?
p(x) =
(
1
)
exp
?
?
1
(x ? m)
T
K
?1
(x ? m)
?
? ?
2
2 K
m
π
16.881 MIT
Pattern Recognition Model
? There are two major elements required for
pattern recognition
– A feature extractor
– A classifier
Raw data
Category
Feature
extractor
Classifier
x
1
x
2
x
n
16.881 MIT
Template matching
? Define a “template” for each class
? Choose class based on
– Maximum correlation or
– Minimum error
? What are the limitations?
16.881
DISPLAY( Dlin) DISPLAY( Dlin)
MIT
MIT16.881
Minimum Distance Classifiers
? Define a mean feature vector m for each class
? For any object, define the distance to each mean
? The object belongs to the “closest” class
? Distance defined by vector norms
x
1
x
2
x
3
m
1
m
3
m
2
x
xm ?
3
m
1
m
2
m
3
x
?
?
?
Minimum
Class
Distance Metrics or Norms
? Euclidean (two) norm ∑
=
i
i
2
2
uu
? Manhattan metric
u =
∑
u
i
i
? Infinity norm
u
∞
= max(u
i
)
Euclidean
Manhattan
Infinity
MIT 16.881
Linear Discriminants
? Discriminant function divides the regions
which determine class membership
? If Euclidean norm is used, boundaries will
be linear
? The set of boundaries will form a Voronoi
diagram
m
1
m
2
m
4
16.881
m
3
MIT
Limitations of Linear
Discriminate Functions
1.The features may be inadequate to
distinguish the different classes
2.The features may be highly correlated
3.The decision boundary may have to be
curved
4.There may be distinct subclasses in the data
5.The feature space may simply be too
complex
16.881 MIT
Mahalanobis Metric
? Normalized w.r.t variance and correlation
? A different covariance matrix C for each
class
x
Class
r
2
= (x ? m)
T
C
?1
(x ? m)
m
1
m
2
m
3
r
Minimum
C
3
r
r
C
2
C
1
16.881 MIT
Mahalanobis Advantages
? Scale invariance -- it doesn’t matter what
units the features are measured in
? Determines probability of membership if
population features are jointly Gaussian
? Can represent curved boundaries between
classes
? Works well on a wide class of problems
even when populations aren’t Gaussian
16.881 MIT
Case Study
Character Recognition
? Defined four letters
DISPLAY(Clin)
DISPLAY(Dlin)
DISPLAY(Alin)
DISPLAY(Blin)
? Created a population of 300 for training
? Inverted scale & fuzzed up
? MD classifier ~94% accurate under severe
conditions
16.881 MIT
Character Recognition
Conclusions
? Mahalanobis metric effective for simple
character recognition
–Fast
– 94% accurate under difficult conditions
? Requires substantial training set
– More than number of features
? Literature suggests it is competitive with
other approaches (neural nets)
16.881 MIT
Mahalanobos Taguchi System
Stage I -- Construct the Space
? Define the features to be measured
? Identify the normal population
? Collect data
? Compute & invert the correlation matrix
? Compute dist r
2
=
1
(x ? m)
T
C
?1
(x ? m)
k
? Determine the threshold value
– Use quality loss to trade off risks of type I and
type II error
16.881 MIT
Mahalanobos Taguchi System
Stage II -- Diagnosis
? Measure the features of the object to be
classified
? Compute the Mahalanobis distance
? Compare to the threshold value
– < threshold, then normal
– > threshold, then abnormal
16.881 MIT
Mahalanobos Taguchi System
Stage III -- Improve the System
? Estimate S/N ratio of the existing system
– What type of S/N ratio would you use for a
classification system?
? Use Robust Design to improve S/N or to
reduce the number of features required
16.881 MIT
Fire Alarm Case Study
Goals of the Design Effort
? Ensure effectiveness of alarm system
– Must detect fires reliably
– Must detect fires early
? Reduce number of false alarms
? Minimize number of sensors required
Kamoshita, Takashi, “Optimization of a Multi-
Dimensional Information System Using Mahalanobis
Taguchi System”, ASI Symposium, 1997.
16.881 MIT
Stage I -- Construct the Space
? Features (50 in all)
– Temperature (5), Smoke (5)
– Times (0, 30, 60, 90, 120 seconds)
? Use OAs to induce sample “normal” conditions
S T
S T
S T
S T
S T
16.881 MIT
Defining the “Normal” Population
? Five 2-level factors in L
12
– Temperature
– Mosquito incense
– Cigarettes
– Oil burning
– Cooking
? Outer factors
– Window open/closed
– Three different rooms
– Injection molding machine on/off (room C)
MIT16.881
Stage II -- Diagnosis
? Test under system under “normal” and
“fire” conditions
– Three normal conditions
? BBQ1
? BBQ2
? Nothing
– Three types of artificial fire
? Results
– r about 1-4 for BBQ
– r near 100 for fires
MIT16.881
Data from Tests
? Temperature sensors alone take too long
? Smoke sensors alone cannot distinguish a
BBQ from a fire
MIT16.881
Temperature Sensor Output
280
285
290
295
300
305
310
315
Time
Te
m
p
e
r
a
t
ur
e
(
K
)
Normal
BBQ 1
BBQ2
Fire 1
Fire 2
Fire 3
Smoke Sensor Output
0
2
4
6
8
10
12
Time
% S
m
o
k
e
C
o
n
c
en
t
r
at
i
o
n
Normal
BBQ 1
BBQ2
Fire 1
Fire 2
Fire 3
Stage III -- Improve the System
? Control factors
– Use sensor / Don’t use sensor
– Applied to all eight corner sensors
? Is additivity likely to apply?
? How might you reduce the # of tests?
16.881
S T
S T
S T
S T
S T
Fixed
Varied
Varied
MIT
Results of Improvement
? Sensors reduced from 10 to 4
S
S
S T
16.881
Effectiveness not compromised
0
5
10
15
20
25
0
10 20 30 40 50 60 70 80 90
100 110 120
Seconds After Ignition
M
a
ha
l
a
nobi
s
D
i
s
t
a
n
c
e
Fire (4 sensors)
Fire (10 sensors)
Indoor cooking
?
MIT
Proposed Case Study
Air Bag Deployment
? What makes a “good” air bag deployment
system?
? What would the feature vector be?
? What is a “normal population” in this
context?
? How would you set the threshold value?
? What kinds of tests would you run?
16.881 MIT
References
? Fukunaga, Keinosuke, Introduction to Statistical Pattern
Recognition, Academic Press, Boston, 1990.
? Hughen, James H., et. al., “Comparison of Mahalanobis
Distance, Polynomial, and Neural Net Classifiers”, SPIE
Applications of Artificial Neural Networks, 1990.
? Taguchi, Shin, and Rajesh Jugulum, “Mahalanobis-
Taguchi System: A Powerful Thinking for the New
Millennium”, Automotive Excellence, Winter, 1998.
16.881 MIT
References
? Kamoshita, Takashi, “Optimization of a Multi-Dimensional
Information System Using Mahalanobis Taguchi System”, ASI
Symposium, 1997.
? Duda, Richard O., Pattern Recognition for HCI, http://www-
engr.sjsu.edu/~knapp/HCIRODPR/PR_home.htm
16.881 MIT
Next Steps
? Next off-campus session
– Lecture 21
? You may wish to send me
– Progress reports
– Questions
16.881 MIT