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 16 881 http www engr sjsu edu knapp HCIRODPR PR home htm Pattern Recognition for HCI Richard O Duda 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 16 881 DISPLAY Dlin MIT Feature Vectors Generally there are several features required to make a classification These features xi can be assembled into a vector Any object to be classified is represented by a point in n dimensional feature space x1 x x2 x 3 16 881 x2 x x3 x1 MIT Joint Gaussian Distribution Density function entirely determined by mean vector and correlation matrix Curves of constant probability are ellispoids p x 16 881 1 2 m x2 m x1 1 exp x m T K 1 x m 2 K MIT Pattern Recognition Model There are two major elements required for pattern recognition A feature extractor A classifier Raw data Feature extractor x1 x2 xn 16 881 Classifier Category 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 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 x2 x m2 m1 x3 16 881 m3 x x m2 x1 m3 m1 m3 Minimum Class MIT Distance Metrics or Norms Euclidean two norm Manhattan metric Infinity norm 16 881 Euclidean Manhattan ui u2 2 i u ui i u max ui Infinity MIT 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 m1 diagram m2 16 881 m4 m3 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 1 r x m C x m 2 16 881 T r m2 C2 r m3 C3 r Minimum x m1 C1 Class 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 Alin DISPLAY Blin DISPLAY Clin DISPLAY Dlin 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 1 2 Compute dist r 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 MultiDimensional 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 ST ST ST ST 16 881 ST MIT Defining the Normal Population Five 2 level factors in L12 Temperature Mosquito incense Cigarettes Oil burning Cooking Outer factors Window open closed Three different rooms Injection molding machine on off room C 16 881 MIT Stage II Diagnosis Test under system under normal and fire conditions Three normal conditions BBQ1 BBQ2 Nothing Three types of artificial fire Results 16 881 r about 1 4 for BBQ r near 100 for fires MIT Data from Tests Temperature sensors alone take too long Smoke sensors alone cannot distinguish a BBQ from a fire Smoke Sensor Output Temperature Sensor Output 12 310 Normal 305 BBQ 1 300 BBQ2 295 Fire 1 290 Fire 2 285 Fire 3 10 Normal 8 BBQ 1 BBQ2 6 Fire 1 4 Fire 2 2 Fire 3 0 280 Time 16 881 Smoke Concentration Temperature K 315 Time MIT Stage III Improve the System Control factors Use sensor Don t use sensor Applied to