Pattern Recognition^{1}

Dokuz Eylül University Computer Engineering Department 24 October 2001 –

Akira Imada imada@cs.deu.edu.tr

1 I pick up some of the topics from the following book:

• S. Theodoridis, and K. Koutroumbas (1999) Pattern Recognition. Academic Press. which is available, for example, at http://www.amazon.com.

□ What is Pattern Recognition?

• A typical example:

– Hand-written character recognition: with inputs being pixel values.

• What else?

– Face recognition;

– Speech recognition;

– Robot’s eye/ear.

• Can we recognize them with fewer information?

– Yes!

– To recognize hand-written characters, e.g., ∗ Perimeter of the boundary:

P_{i} = N−1 ; ∑ ; i=1 ∥x_{i−1} − x_{i}∥ + ∥x_{0} − x_{1}∥.  (1)

∗ Area inside the boundary: A.

∗ Roundness ratio:

r = p^{2}/4πA.  (2)

∗ Bending energy (defined at a point n):

E(n) = \frac{1}{P} n−1 ; ∑ ; i=0 |k_{i}|^{2}  (3)

where k_{i} (curvature of boundary) is:

k_{n} = θ_{n+1} − θn, n = 0, 1, ⋯, N − 1.  (4)

and

θ_{n} = tan^{−1} \frac{y_{n+1} − y_{n}}{x_{n+1} − x_{n}}, n = 0, 1, ⋯, N − 1.  (5)

∗ Number of halls.

∗ Number of corners:

the number of points where the curvature k_{i} takes large values (infinity in theory)

– They are called features.

– Then, how many features are enough?

(Minimize the number of features.)

In short:

• pattern recognition is a classifier.

– Especially usfull for classification in high-dimensional feature space.

• Application:

– diagnosis.

– what else?

(Pattern Recognition) 4

□ Statistical Classification:

Bayes Decision Theory — for the design of classifiers.

Pattern Recognition is more or less statistical due to: – statistic variation of patterns;

– statistic nature of feature selection;

– noise in employing sensors.

So, the task is:

– to classify unknown patterns into the most probable class.

Then – what does “the most probable” means?

To answer this question:

– we study here the Bayesian Statistical Theory.

• When we classify an unknown pattern which is represented by a feature vector x, we consider M conditional probabilities:

p(ω_{i}|x) i = 1, ⋯, M  (6)

• Then we define “the most probable class” as the class ω_{i} which has the highest p(ω_{i}|x).

• We have the other possible statistical quantities:

p(ω_{i}), p(x|ω_{i}), p(x)

• The Bayesian rule gives a relationship of these quantities:

p(ω_{i}|x) = \frac{p(x|ω_{i})p(ω_{i})}{M ; ∑ ; k=1 p(x|ω_{k})p(ω_{k})}  (7)

where the denominator is:

M ; ∑ ; k=1 p(x|ω_{k})p(ω_{k}) = p(x).  (8)

• Example 1.

— to understand the Bayesian Rule

· We have two bags of no difference from its outlook. · One bag called R has 70 red balls and 30 blue balls. · The other bag called B has 30 red balls and 70 blue balls. · When we take one bag at random and pick up 12 balls, returning it to the bag at each time. · The result was 8 red balls and 4 blue one. · Then was the bag estimated to be R or B, and how probable the estimate is?

Clearly,

p(R) = p(B) = 1/2
p(D|R) = _{12}C_{8}(0.7)^{8}(0.3)^{4}
p(D|B) = _{12}C_{8}(0.3)^{8}(0.7)^{4}

So we obtain

p(R|D) = \frac{(0.7)^{8}(0.3)^{4}}{(0.7)^{8}(0.3)^{4} + (0.3)^{8}(0.7)^{4}} ≈ 0.97

(How big it is compared to our intuitive estimation!)

• Example 2.

· Three prisoners (A, B, and C) are in a prison.

· A knows that the two out of the three are to be executed tomorrow, and the rest becomes free. · A thought either one of B or C is sure to be executed. · Then, A asked a guard “even if you tell me which of B and C is executed, that will not give me any information as for me. So please tell it to me.” · The guard answers that C will. ⇒ data D · Now, A knows one of A or B is sure to be free.

Do you guess probability p(A|D) = 1/2? If this is correct, then the answer of the guard had given an information as for A, since probability p(A) = 1/3. You agree that

p(A) = p(B) = p(C) = 1/3.

Then, try to apply Bayesian rule, i.e., obtain the conditional probability of the data “C will be executed” under the condition that “A will be free tomorrow” And in the same way for B and C. They are:

p(D|A) = 1/2.
p(D|B) = 1.
p(D|C) = 0.

In conclusion:

p(A|D) = \frac{p(D|A)p(A)}{p(D|A)p(A) + p(D|B)p(B) + p(D|C)p(C)} = 1/3.

This shows probability did not change after the information!

• Now it’s clear that

– p(A) and so on are to be called ⋆ a priori probabilities;

– and p(A|D) and so on to be ⋆ a posteriori probabilities.

• In the same way,

– p(ω_{i}) is called ⋆ a priori probability^{2} ;

– p(ω_{i}|x)

⋆ a posteriori probabilities.

Furthermore

– p(x) is called ⋆ p.d.f. of x

– p(x|ω_{i})

⋆ class-conditional p.d.f.^{3} · which describes the distribution of the feature vectors x in each of the classes ω_{i}.

2 Usually given, but if unknown, it can be estimated as N_{i}/N where N_{i} is the number of training samples which belong to class ω_{i}, and N is the total number of training samples

3 This is also estimated from training data which will be explained later more in detail.