The mahalanobis distance in Character Recognition Authored by Dan Frey 31 July 98 This sheet explores the use of the Mahalanobis Distance in character 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 bc and d defined as matrices of 1s and Os 10011 10001 A:10001 B=11110 C:=10000D=10001 10001 10001 1000 Stretch the letters out into a vector of " features" k+5-5.ceil Reverse the letters. This makes the plots easier to read Alink =Alink =0 Blink=Blink =0 Clink =Clin =0 Dlink=Dlin =0
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 Alink := A k+ 5-5� ceil� � k � �, ceil� � k � � Blink := B k+ 5-5� ceil� � k � �, ceil� � k � � Ł 5 ł Ł 5 ł Ł 5 ł Ł 5 ł Clink := C k+ 5-5� ceil� � k � �, ceil� � k � � Dlink := D k+ 5-5�ceil� � k � �, ceil� � k � � Ł 5 ł Ł 5 ł Ł 5 ł Ł 5 ł Reverse the letters. This makes the plots easier to read. Alink := Alink = 0 Blink := Blink = 0 Clink := Clink = 0 Dlink := Dlink = 0 1
Define a function that will display the vector of features as a matrix DISPLAY(Llin): =I for iE 1.5 forj∈1.5 Here are a couple of plots that show what the Cononical letters look like DISPLAY(Alin) DISPLAY( Blin) DISPLAY(Clin) DISPLAY(DIin)
Define a function that will display the vector of features as a matrix DISPLAY(Llin) := for i ˛ 1.. 5 for j ˛ 1.. 5 Li, j ‹ Llini+ 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. op: =1.training_population ot: =0.01 How much random noise is superposed onto the pixels APOP:[21oum1.0.)-)Am]+mom23.)mhepuate BPoP P=[(2- loor runif( 1,0, 2)1)-1) Blin]+morm(25, 0, od) been switched from positive to negative with POPOp a 50/50 probability, then [(2. floorfrunif(1,0, 2)1)-1)-Clin] morm(25, 0, ou superposed with white DPOP 20o02)-),bim]+mwm(230 Here is an example of a fuzzed up a and a fuzzed up b DISPLAYAPOP(s) DISPLAYBPOP3)
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 st := 0.01 How much random noise is superposed onto the pixels. Æ æ �������������fi APOP pop := Ø º(2�floor(runif(1, 0, 2) 1) - 1)�Alinø ß + rnorm(25, 0,st) These populations have Æ æ �������������fi been switched from BPOP pop := Ø º(2�floor(runif(1, 0, 2) 1) - 1)�Blinø ß + rnorm(25, 0,st) positive to negative with Æ æ �������������fi a 50/50 probability, then CPOP pop := Ø º(2�floor(runif(1, 0, 2) 1) - 1)�Clinø ß + rnorm(25, 0,st) superposed with white Æ æ �������������fi noise. DPOP pop := Ø º(2�floor(runif(1, 0, 2) 1) - 1)�Dlinø ß + rnorm(25, 0,st) 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 cOvA cvar ( APO oPTn ()m MEANA mear (Apop nI COVB BPOP BPOP MEANB BPOP COVC : cvar(CPOP CPOP MEANC : mean (CPOP COVD DPOP DPOP MEAND =me DPOP The classifier will use the inverse of the covariance matrix, so let's compute it ahead of time INVCOVA=COVA INVCOVB= COVB INVCOVC= COV INVCOVD= COVD
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º Ø (APOPT) Ænæ ,(APOPT) Æmæø ß MEANA := mean Ø º(APOPT) Ænæ ø ß n, m n COVB := cvar Ø º(BPOPT) Ænæ ,(BPOPT) Æmæø ß MEANB := mean Ø º(BPOPT) Ænæ ø ß n, m n COVC := cvar Ø º(CPOPT) Ænæ ,(CPOPT) Æmæø ß MEANC := mean Ø º(CPOPT) Ænæ ø ß n, m n COVD := cvarº Ø (DPOPT) Ænæ ,(DPOPT) Æmæø ß MEAND := mean Ø º(DPOPT) Æ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)
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).INVCOVA(L-MEANA MDB <(L-MEANB).INVCOVB (L-MEANB) MDC <(L-MEANC). INVCOVC (L-MEANC) MDD←(L- MEAND)· INVCOVD( L- MEAND) A" if(MDA MDB). (MDA MDC) (MDA MDD) B"if(MDB MDC). (MDB MDD) otherwise C if(MDC MDD) "D" otherwise 6
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
est the classifier o =0.6 How badly should the letters be fuzzed tests:=10000 How many times should you test the classifier test=1. tests Answe and←rmif(1,0,4)1 Make the four letters equally likely to appear "A"if0≤rand≤1 within the test batch B"ifl<rand≤2 "D"if3<rand≤4 Create a batch of letters corresponding to the desired correct answers and appropriatel fuzzed up. This will be the batch of data to test our classifier Lest= [(2-floorfrunif(1, 0, 2)1)-1 lin]+morm(25,0, a) if Answer rest ="A" (2-floorfrunif( 1, 0, 2)1)-)-Blin]+ morm(25,0, o) if Answerest="B" (2-floorfrunif( 1,0, 2)-)-Clin]+morm(25, 0, o) if Answertest ""CN RIGHT: =Class(L At sigma=0.6, the Mahalanobis classifier is right about 94% of the time! you do as well in classifying the letters? Also note how fast the Mahalanobis classifier operates
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 Answertest := 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. �������������fi Ltest := Ø º(2�floor(runif(1, 0, 2) 1) - 1)�Alinø ß + rnorm(25, 0,s) if Answertest = "A" �������������fi Ø(2�floor(runif(1, 0, 2) 1) - 1)�Blinø ß + rnorm(25, 0,s) if Answertest = "B" º �������������fi Ø(2�floor(runif(1, 0, 2) 1) - 1)�Clinø ß + rnorm(25, 0,s) if Answertest = "C" º �������������fi Ø(2�floor(runif(1, 0, 2) 1) - 1)�Dlinø ß + rnorm(25, 0,s) if Answertest = "D" º RIGHTtest := (Class(Ltest) = Answertest) 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= 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 DISPLAY DISPLA Y2) Answer1-(Answ Answer2(Answ=D) Cs(Amw=-]=℃ (Answ=l "D" DISPLA DISPLA Answer(Answ=l Answer(Answ=l) Class3(Answal)y/ (Answ=l)
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) Answer1�(Answ=1) = "C" Answer2�(Answ=1) = "D" ClassØ º L 1� (Answ=1) ß ø = "C" ClassØ º L2� (Answ=1) ß ø = "D" DISPLAY L( 3) DISPLAY L( 4) A Answer3�(Answ=1) = "A" A Answer4�(Answ=1) = "A" ClassØ º L3� (Answ=1) ß ø = "A" ClassØ º L4� (Answ=1) ß ø = "A" 8