The Mahalanobis Distance in Character Recognition Authored by Dan Frey 31 July 98 This sheet explores the use of the Mahalanobis Distance in character recognition. It defines a letters A, B, C, and D. It creates a population of distorted letters to train a classifier. It creates a test population of letters to test the classifier. It allows you to compete against the Mahalanobis classifier. ORIGIN := 1 Every matrix and vector in this sheet will begin with index number 1. Here are the Canonical letters A B C and D defined as matrices of 1s and 0s ? 0 0 1 0 0 ? ? 1 1 1 1 0 ? ? 0 1 1 1 0 ? ? 1 1 1 1 0 ? ? ? ? ? ? ? ? ? ? 0 1 0 1 0 ? ? 1 0 0 1 1 ? ? 1 0 0 0 1 ? ? 1 0 0 0 1 ? A := ? 1 0 0 0 1 ? B := ? 1 1 1 1 0 ? C := ? 1 0 0 0 0 ? D := ? 1 0 0 0 1 ? ? 1 1 1 1 1 ? ? 1 0 0 1 1 ? ? 1 0 0 0 1 ? ? 1 0 0 0 1 ? ? ? ? ? ? ? ? ? ? 1 0 0 0 1 ? ? 1 1 1 1 0 ? ? 0 1 1 1 0 ? ? 1 1 1 1 0 ? Stretch the letters out into a vector of "features". k := 1.. 25 Alin k := A k+ 5-5? ceil ? ? k ? ? , ceil ? ? k ? ? Blin k := B k+ 5-5? ceil ? ? k ? ? , ceil ? ? k ? ? ? 5 ? ? 5 ? ? 5 ? ? 5 ? Clin k := C k+ 5-5? ceil ? ? k ? ? , ceil ? ? k ? ? Dlin k := D k+ 5-5?ceil ? ? k ? ? , ceil ? ? k ? ? ? 5 ? ? 5 ? ? 5 ? ? 5 ? Reverse the letters. This makes the plots easier to read. Alin k := Alin k = 0 Blin k := Blin k = 0 Clin k := Clin k = 0 Dlin k := Dlin k = 0 1 Define a function that will display the vector of features as a matrix DISPLAY(Llin) := for i ∈ 1.. 5 for j ∈ 1.. 5 L i, j ← Llin i+ 5?( j-1) L Here are a couple of plots that show what the Cononical letters look like. DISPLAY Alin( ) DISPLAY Blin( ) DISPLAY Clin( ) DISPLAY Dlin( ) 2 Create a population of fuzzed up letters training_population := 300 Size of the training population. Has to be bigger than the number of pixels. pop := 1.. training_population s t := 0.01 How much random noise is superposed onto the pixels. ? ? ?????????????→ APOP pop := ? ? ( 2?floor ( runif(1, 0, 2) 1 ) - 1 ) ?Alin ? ? + rnorm(25, 0, s t ) These populations have ? ? ?????????????→ been switched from BPOP pop := ? ? ( 2?floor ( runif(1, 0, 2) 1 ) - 1 ) ?Blin ? ? + rnorm(25, 0, s t ) positive to negative with ? ? ?????????????→ a 50/50 probability, then CPOP pop := ? ? ( 2?floor ( runif(1, 0, 2) 1 ) - 1 ) ?Clin ? ? + rnorm(25, 0, s t ) superposed with white ? ? ?????????????→ noise. DPOP pop := ? ? ( 2?floor ( runif(1, 0, 2) 1 ) - 1 ) ?Dlin ? ? + rnorm(25, 0, s t ) Here is an example of a fuzzed up A and a fuzzed up B. DISPLAY APOP 5 ? ? ( ) DISPLAY BPOP 3 ? ? ( ) 3 Compute Statistics of the Training Population To create a Mahananobis distanace classifier, we need to deternime the mean and cavariance matrices from the population of letters. n := 1.. 25 m := 1.. 25 COVA := cvar ? ? ( APOP T ) ? n ? , ( APOP T ) ? m ? ? ? MEANA := mean ? ? ( APOP T ) ? n ? ? ? n, m n COVB := cvar ? ? ( BPOP T ) ? n ? , ( BPOP T ) ? m ? ? ? MEANB := mean ? ? ( BPOP T ) ? n ? ? ? n, m n COVC := cvar ? ? ( CPOP T ) ? n ? , ( CPOP T ) ? m ? ? ? MEANC := mean ? ? ( CPOP T ) ? n ? ? ? n, m n COVD := cvar ? ? ( DPOP T ) ? n ? , ( DPOP T ) ? m ? ? ? MEAND := mean ? ? ( DPOP T ) ? n ? ? ? n , m n The classifier will use the inverse of the covariance matrix, so let's compute it ahead of time. - 1 - 1 INVCOVA := COVA INVCOVB := COVB - 1 - 1 INVCOVC := COVC INVCOVD := COVD 4 I think it's interesting to note that the "mean" appearance of the letter A is incomprehensible as an A. The reason is that we had an equal number of positive images and negative images of A. The same applies to all the other letters. And yet the classifier successfully identifies the letter A because it has a map of the correlations within the letter A. DISPLAY MEANA( ) 5 Define the Classifier Here is the classifier function. It is very simple. You send it a letter (L) as an argument. It computes the Mahalanobis distance from the letter to the class A, B, C, and D. Finally, it classifies L as the letter with the smallest Mahalanobis distance. Class(L) := MDA ← (L - MEANA) T ?INVCOVA ?(L - MEANA) MDB ← (L - MEANB) T ?INVCOVB?(L - MEANB) MDC ← (L - MEANC) T ?INVCOVC?(L - MEANC) MDD ← (L - MEAND) T ?INVCOVD?(L - MEAND) "A" if (MDA < MDB)?(MDA < MDC)?(MDA < MDD) otherwise "B" if (MDB < MDC)?(MDB < MDD) otherwise "C" if (MDC < MDD) "D" otherwise 6 Test the Classifier s := 0.6 How badly should the letters be fuzzed up. tests := 10000 How many times should you test the classifier test := 1.. tests Answer test := rand ← runif(1, 0, 4) 1 Make the four letters equally likely to appear "A" if 0 ≤ rand ≤ 1 within the test batch. "B" if 1 < rand ≤ 2 "C" if 2 < rand ≤ 3 "D" if 3 < rand ≤ 4 Create a batch of letters corresponding to the desired correct answers and appropriately fuzzed up. This will be the batch of data to test our classifier. ?????????????→ L test := ? ? ( 2?floor ( runif(1, 0, 2) 1 ) - 1 ) ?Alin ? ? + rnorm(25, 0, s) if Answer test = "A" ?????????????→ ?( 2?floor ( runif(1, 0, 2) 1 ) - 1 ) ?Blin ? ? + rnorm(25, 0, s) if Answer test = "B" ? ?????????????→ ?( 2?floor ( runif(1, 0, 2) 1 ) - 1 ) ?Clin ? ? + rnorm(25, 0, s) if Answer test = "C" ? ?????????????→ ?( 2?floor ( runif(1, 0, 2) 1 ) - 1 ) ?Dlin ? ? + rnorm(25, 0, s) if Answer test = "D" ? RIGHT test := ( Class ( L test ) = Answer test ) mean(RIGHT) = 0.905 At sigma=0.6, the Mahalanobis classifier is right about 94% of the time! Can you do as well in classifying the letters? Also note how fast the Mahalanobis classifier operates. 7 Try Your Hand at Classification Answ 1 := Take a guess at which letter is represented in the following four graphs. When you're done, change the varaible "Answ" to 1 and the answers will display. Did you get it right? Did the MD C DISPLAY L 1 ( ) classifier? D DISPLAY L 2 ( ) Answer 1?(Answ=1) = "C" Answer 2?(Answ=1) = "D" Class ? ? L 1? (Answ=1) ? ? = "C" Class ? ? L 2? (Answ=1) ? ? = "D" DISPLAY L 3 ( ) DISPLAY L 4 ( ) A Answer 3?(Answ=1) = "A" A Answer 4?(Answ=1) = "A" Class ? ? L 3? (Answ=1) ? ? = "A" Class ? ? L 4? (Answ=1) ? ? = "A" 8