Pattern Recognition^{1}

Dokuz Eylül University Computer Engineering Department 19 February 2001 – 8 June 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. especially the chapters that explain “classifiers based on Bayes decision theory.” The book is available, for example, at http://www.amazon.com. However, you do not need to buy since it’s not necessarily easy to understand as it is. I pick up some of the topics and edited them in my way.

□ Contents:

1. What is Pattern Recognition?

⋆ Hand-written character recognition as an example. ⋆ Feature extraction.

2. Principal Component Analysis (PCA):

How many features are enough?

3. Sammon Mapping:

What a high-D feature space look like?

4. How can we observe multi-dimensional feature space?

5. To minimize classification error:

Bayesian Classifier.

6. Feature Generation by Linear Transforms.

(Pattern Recognition) 3

□ What is Pattern Recognition?

A typical example:

• Character recognition:

characters as an example of patterns.

How can we recognize them?

• By taking all pixels as inputs?

• By some shape information? e.g.

∗ area within boundary;

∗ degree of how boundary curve. These are called features.

Feature space:

• l features forms feature vector x = (x_{1}, x_{2}, ⋯, x_{l})

for each object to be recognized.

• straight line separates the classes ⇓ in more general

separation by hyper-plane

In short:

• pattern recognition is a classifier □ Examples of feature to recognize characters:

• Perimeter:

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

• Area:

Measure the area enclosed by a boundary by counting the number of pixels.

• Roundness ratio: r = P^{2}/4πA.

• Number of holes

• Bending energy:

– defined at a point n as

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

where k_{i} is the curvature of the boundary defined as:

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

and

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

when we measure the length of the boundary at a point by the number of pixels n between this point and the origin of the curve.

• Number of corners:

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

□ Principal Component Analysis (PCA)

⋯ A method of dimension reduction.

In the context of Pattern Recognition, a method to reduce the number of features without losing efficiency.

• Two dimensional cases:

Suppose we have N data pairs:

(x_{i}, y_{i}) i = 1, 2, ⋯, N  (5)

In the context of Pattern Recognition, we have N data with two features.

Our objective is to find a and b that maximize the variance of the projections of these N points on the line

a(x − x̄) + b(y − ȳ) = 0  (6)

where x̄ and ȳ are the average of x_{i} and y_{i}, respectively.

Then

z_{i} = ax_{i} + by_{i}  (7)

is called principal component of x_{i} and y_{i}.^{2}

In the context of Pattern Recognition, two features x_{i} and y_{i} are said to be reduced to one feature z_{i}.

2 Yet another interpretation of z_{i} is a weighted sum of x_{i} and y_{i}. For example, x_{i} and y_{i} are point of homework assignment and final exam of student i and z_{i} is the evaluation.

(Pattern Recognition) 6

Such (a, b) is known to be the eigenvector^{3} of the matrix:

( \begin{matrix}s_{xx} & s_{xy} \\ s_{yx} & s_{yy} \end{matrix} )  (8)

where s_{xx} and s_{yy} are variance of x and y respectively and s_{xy} = s_{yx} are covariance of x_{i} and y_{i}^{4} . That is,

λ = \frac{s_{xx} + s_{xy} ± \sqrt{s_{xx}^{2} + s_{xy}^{2} + s_{yy}^{2} − s_{xx}s_{yy}}}{2}  (10)

and

(a, b) = (\frac{s_{xx} − s_{yy} ± \sqrt{s_{xx}^{2} + s_{xy}^{2} + s_{yy}^{2} − s_{xx}s_{yy}}}{2s_{xy}}, 1) (11)

• Generalization to n-dimensional cases:

and eigenvalue of the matrix A.

\frac{∑_{i=1}^{N}(x_{i} − x̄)^{2}}{N} and \frac{∑_{i=1}^{N}(x_{i} − x̄)(y_{i} − ȳ)}{N} (9)

respectively.

3 If the transform of a vector x by a matrix A changes just a length of x by λ then x and λ are called eigenvector

4 Variance of x_{i} and covariance of x_{i} and y_{i} are defined as

(Pattern Recognition) 7

□ Sammon Mapping (J. W. Sammon, 1969)

• Assume N points are given in the n-D space.

• Calculate distance matrix R (N × N) whose i-j element is the Euclidean distance between the i-th and j-th point.

• Also think of a tentative N points in the 2-D space that are located at random at the beginning.

• The distance matrix Q is calculated in the same way as R.

• Then the error matrix P = R − Q is defined.

• Search for the locations of N points in the 2-D space that minimizes the sum of element P.

This is an optimization problem which we can solve by GA, that is,

• N points in n-D space ⇒ N points in 2-D space with the distance relation being preserved as much as possible; or

• The n-D distances are approximated by 2-D distances with a minimal error.

(Pattern Recognition) 8

□ GA Implementation of Sammon Mapping □ 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  (12)

• 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})}  (13)

where the denominator is:

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

(Pattern Recognition) 11

• 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 the fact 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 about A, since probability p(A) = 1/3.

Try to apply Bayesian rule, if you agree

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

Then the conditional probabilities of the data, that is, “C will be executed” under the condition that A, B, and C will be free tomorrow, respectively, are

p(D|A) = 1/2  (15)
p(D|B) = 1  (16)
p(D|C) = 0  (17)

(Pattern Recognition) 13

• 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^{5} ;

– p(ω_{i}|x)

⋆ a posteriori probabilities.

Furthermore

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

– p(x|ω_{i})

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

5 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

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

□ The Bayesian Classifier:

Definition 1 (The Bayesian Classifier) classify x to the class ω_{i} such that p(ω_{i}|x) takes the maximum value.

• Two-class case

⋆ if p(ω_{1}|x) > p(ω_{2}|x), then classify x to ω_{1}  (18)
⋆ if p(ω_{1}|x) < p(ω_{2}|x), then classify x to ω_{2}  (19)

· An example:

If we assume p(ω_{1}|x) = N(0, 1/2), p(ω_{2}|x) = N(1, 1/2)^{7} , and p(ω_{1}) = p(ω_{2}) = 1/2, then how is our classification like?

The region where p(ω_{1}|x) > p(ω_{2}|x) is the region where

\frac{p(x|ω_{1})p(ω_{1})}{p(x)} > \frac{p(x|ω_{2})p(ω_{2})}{p(x)}  (20)

Since p(x) > 0 and p(ω_{1}) = p(ω_{2}), the region is where

p(x|ω_{1}) > p(x|ω_{2})  (21)

holds. Now assume the two Gaussian distribution cross at x = x_{0}, we can conclude:

⋆ if x < x_{0} then classify x to class ω_{1}, and vice versa.

7 N(μ, σ^{2}) = \frac{1}{\sqrt{2π}σ} exp −\frac{(x − μ)^{2}}{2σ^{2}}

□ Probability of Misclassification: In the previous example:

• The probability of misclassifying x of ω_{2} to ω_{1} is

∫_{−∞}^{x_{0}} p(x|ω_{2})dx,  (22)

and the probability of misclassifying x of ω_{1} to ω_{2} is

∫_{x_{0}}^{∞} p(x|ω_{1})dx.  (23)

Therefore the total error probability is

∫_{−∞}^{x_{0}} p(x|ω_{2})dx + ∫_{x_{0}}^{∞} p(x|ω_{1})dx.  (24)

• But usually feature space is multidimensional and so

∫_{R_{1}} p(x|ω_{2})dx + ∫_{R_{2}} p(x|ω_{1})dx  (25)

is a more general expression of the equation (24).

• A generalization to M-class problem.

– Assume that

R_{j} : j = 1, 2, ⋯ M.  (26)

is the region of the feature space assigned to class ω_{j}.

– Then the probability that a feature vector x that belongs to ω_{k} lies in R_{i} (i ≠ k) (i.e., misclassify x of ω_{k} to ω_{i}) is:

p_{e} = M ; ∑ ; i=1 ∫_{R_{i}} p(x|ω_{k})dx  (27)

– But usually, some errors are not so important as others, and λ_{ki}, importance of the error where x of ω_{k} to ω_{i} ^{8} , is weighted as:

r_{k} = M ; ∑ ; i=1 λ_{ki} · ∫_{R_{i}} p(x|ω_{k})dx ^{9}  (28)

and the goal is to determine R_{j} such that

r = M ; ∑ ; i=1 r_{k} · p(ω_{k})
= M ; ∑ ; i=1 ∫_{R_{i}} M ; ∑ ; k=1 λ_{ki} · p(x|ω_{k})p(ω_{k})dx  (29)

is minimized.

– This is achieved if each of the integrals is minimized.

(to continue)

8 In other words, λ_{ki} is a penalty term corresponding to a misclassification of x that belongs to ω_{k} lies in R_{j} 9 Here, ∫_{R_{i}} p(x|ω_{k})dx is the probability of a feature vector from ω_{k} being classified in ω_{i}.

– Hence the following formula holds and called Likelihood Ratio Test.

Test 1 (The Likelihood Ratio Test) Assign x to R_{i} if

M ; ∑ ; k=1 λ_{ki} · p(x|ω_{k})p(ω_{k}) < M ; ∑ ; k=1 λ_{kj} · p(x|ω_{k})p(ω_{k})  (30)

for ∀j ≠ k.

– The two-class (M = 2) case:

· Assign x to ω_{i} if

λ_{11}p(x|ω_{1})p(ω_{1}) + λ_{21}p(x|ω_{2})p(ω_{2})

< λ_{12}p(x|ω_{1})p(ω_{1}) + λ_{22}p(x|ω_{2})p(ω_{2}) (31)

That is,

(λ_{21} − λ_{22})p(x|ω_{2})p(ω_{2}) < (λ_{11} − λ_{11})p(x|ω_{1})p(ω_{1}) (32)

If we assume λ_{ij} > λii, · Assign x to ω_{i} if

\frac{p(x|ω_{1})}{p(x|ω_{1})} > \frac{p(ω_{2})}{p(ω_{1})} · \frac{(λ_{21} − λ_{22})}{(λ_{12} − λ_{11})}  (33)

(to continue)

If two classes are equiprobable p(ω_{1}) = p(ω_{2}) and λ_{11} = λ_{22} = 0, then

Assign x to ω_{1} if

p(x|ω_{1}) > p(x|ω_{2}) · \frac{λ_{21}}{λ_{12}}  (34)

Furthermore if the importance of two misclassification is the same, that is, λ_{12} = λ_{21} = 1, then

p(x|ω_{1}) > p(x|ω_{2})  (35)

This is equivalent of the equation (18).

□ Decision Surfaces and Discriminant Functions: — to partition the feature space into M regions.

• If regions R_{i} and R_{j} are contiguous

p(ω_{i}|x) − p(ω_{j}|x) = 0  (36)

determines the surface that partition R_{i} and R_{j},

• Or, if necessary, using a monotonic function f(x)^{10} , we define:

g_{i}(x) = f(p(ω_{i}|x))  (37)

and we can say

⋆if g_{i}(x) > g_{j}(x) for ∀j ≠ i, classify x to ω_{i}. (38)

Hence

g_{ij} ≡ g_{i}(x) − g_{j}(x) = 0  (39)

determines the decision surfaces separating contiguous regions and called discriminant function.

10 e.g., f(x) = ln(x) for the Gaussian distribution.

(Pattern Recognition) 20

□ Bayesian Classification for 2-d Gaussian pdf:

• l-dimensional Gaussian distribution

p(x) = \frac{1}{(2π)^{l/2}|Σ|^{1/2}} exp(−\frac{1}{2}(x − μ)^{T}Σ^{−1}(x − μ) (40)

where

·Σ = ( \begin{matrix}σ_{1}^{2} & σ_{12} & ⋯ & σ_{1l} \\ σ_{21} & σ_{2}^{2} & ⋯ & σ_{2l} \\ & & ⋯ \\ σ_{l1} & σ_{l2} & ⋯ & σ_{l}^{2} \end{matrix} )  (41)

· x = (x_{1}, x_{2}, ⋯, x_{l}); · μ is a l-dimensional vector whose i-th element μ_{i} is the mean value of x_{i}; · σ_{i}^{2} is the variance of x_{i}; · σ_{ij} is the covariance between x_{i} and x_{j}; · |Σ| is determinant of the matrix Σ; · Σ^{−1} is inverse matrix of Σ^{11} ; · x^{T} is transverse of vector x^{12} .

A = ( \begin{matrix}a & b \\ c & d \end{matrix} )  (42)
|A| = ad − bc  (43)
A^{−1} = \frac{1}{ad − bc} ( \begin{matrix}d & −b \\ −c & a \end{matrix} )  (44)
x^{T} = ( \begin{matrix}x_{1} \\ x_{2} \end{matrix} )  (45)

11 If we assume then and 12 That is, when x = (x_{1}, x_{2})

• 2-dimensional Gaussian

We can calculate l = 2 version from the equation (40) as:

p(x_{1} , x_{2}) = \frac{1}{2πσ_{1}σ_{2}\sqrt{1 − ρ^{2}}} · exp\{(−\frac{1}{2(1 − ρ^{2})} ·

((\frac{x_{1} − μ_{1}}{σ_{1}})^{2} − 2ρ(\frac{x_{1} − μ_{1}}{σ_{1}})(\frac{x_{2} − μ_{2}}{σ_{2}}) + (\frac{x_{2} − μ_{2}}{σ_{2}})^{2})\}

(46)

where ρ is correlation coefficient defined as:

ρ = \frac{σ_{12}}{σ_{1}σ_{2}}  (47)

Exercise 1:

1. Derive the equation (46) from the equation (40).

2. By giving your own set of five parameters: μ_{1}, μ_{2}, σ_{1}, σ_{2}, and σ_{12}

Draw the Gaussian surface on (x_{1}, x_{2}) coordinate. Then explore a couple of configurations of these five parameters.

(Pattern Recognition) 22 (Pattern Recognition) 23

□ Examples of Decision Surface in 2D Feature Space: The equation (46) with taking the function ln as f(·) in the equation (37), we obtain our discriminating function g_{i} as:

g_{i}(x) = ln(p(x|ω_{i})p(ω_{i}))
= ln p(x|ω_{i}) + ln p(ω_{i})
= −\frac{1}{2}(x − μ_{i})^{T}Σ_{i}^{−1}(x − μ_{i}) + ln p(ω_{i}) + c_{i}
= −\frac{1}{2}x^{T}Σ_{i}^{−1}x + \frac{1}{2}x^{T}Σ_{i}^{−1}μ_{i} − \frac{1}{2}μ_{i}^{T}Σ_{i}^{−1}μ_{i}

+\frac{1}{2}μ_{i}^{T}Σ_{i}^{−1}x + ln p(ω_{i}) + c_{i}

(48)

where

c_{i} = −(l/2) ln(2π) − (1/2) ln |Σ_{i}|  (49)

(Pattern Recognition) 24

• Example 1 When

Σ_{i} = ( \begin{matrix}σ_{i}^{2} & 0 \\ 0 & σ_{i}^{2} \end{matrix} )

g_{i} = \frac{x_{1}^{2} + x_{2}^{2}}{−2σ_{i}^{2}} + \frac{μ_{i1}x_{1} + μ_{i2}x_{2}}{σ_{i}^{2}} − \frac{μ_{i1}^{2} + μ_{i2}^{2}}{−2σ_{i}^{2}} + ln p(ω_{i}) + c_{i} (50)

⋆ Hence, under this kind of two distributions, the decision surface is a circle.

(Pattern Recognition) 25

• Example 2 When

Σ_{i} = ( \begin{matrix}σ_{i1}^{2} & 0 \\ 0 & σ_{i2}^{2} \end{matrix} )

g_{i} = \frac{σ_{i2}^{2}x_{1}^{2} + σ_{i1}^{2}x_{2}^{2}}{−2σ_{i1}^{2}σ_{i2}^{2}} + \frac{σ_{i2}^{2}μ_{i1}x_{1} + σ_{i1}^{2}μ_{i2}x_{2}}{σ_{i1}^{2}σ_{i2}^{2}}
− \frac{σ_{i2}^{2}μ_{i1}^{2} + σ_{i1}^{2}μ_{i2}^{2}}{−2σ_{i1}^{2}σ_{i2}^{2}} + ln p(ω_{i}) + c_{i} (51)

⋆ This kind of two distributions construct a quadratic decision surface. ⋆ If expanded to l > 2 case, then it is called hyper-quadratic.

• Exercise 2: When p(ω_{1}) = p(ω_{2}), μ_{1} = (0, 0), and μ_{2} = (1, 0), obtain decision surface in the following two cases.

(1) Σ_{1} = ( \begin{matrix}0.10 & 0 \\ 0 & 0.15 \end{matrix} ) , Σ_{2} = ( \begin{matrix}0.20 & 0 \\ 0 & 0.25 \end{matrix} )

(2) Σ_{1} = ( \begin{matrix}0.10 & 0 \\ 0 & 0.15 \end{matrix} ) , Σ_{2} = ( \begin{matrix}0.15 & 0 \\ 0 & 0.10 \end{matrix} )

□ An expansion to l-D Feature space:

Our discriminant function now is the equation (48), i.e.,

g_{i} = −\frac{1}{2}x^{T}Σ_{i}^{−1}x + \frac{1}{2}x^{T}Σ_{i}^{−1}μ_{i} − \frac{1}{2}μ_{i}^{T}Σ_{i}^{−1}μ_{i}

+\frac{1}{2}μ_{i}^{T}Σ_{i}^{−1}x + ln p(ω_{i}) + c_{i}

(52)

We have discussed that this gives a quadratic decision surface.

But if we assume here:

∀Σ_{i} = Σ  (53)

That is, all the variance matrices are identical, then the first and the last term do not contribute to g_{i} − g_{j}, and we can re-define g_{i} as:

g_{i} = \frac{1}{2}x^{T}Σ_{i}^{−1}μ_{i} + \frac{1}{2}μ_{i}^{T}Σ_{i}^{−1}x − \frac{1}{2}μ_{i}^{T}Σ_{i}^{−1}μ_{i} + ln p(ω_{i}) (54)

And we can simplify the equation (54) as:^{13}

g_{i} = w_{i}^{T}x + w_{i0}  (55)

by putting

w_{i} = Σ^{−1}μ_{i}  (56)

and

w_{i0} = ln p(ω_{i}) − \frac{1}{2}μ_{i}^{T}Σ_{i}^{−1}μ_{i}  (57)

Hence our new g_{i} is a linear function of x and the decision surfaces determined by g_{i} − g_{j} = 0 are hyper-planes instead of the previous quadratic surfaces.

\frac{1}{2}x^{T} w_{i} + \frac{1}{2}w_{i}^{T} x = w_{i}^{T} x.

13 Since w_{i}^{T} = Σ^{−1}μ_{i} and Σ is symmetric, we obtain w_{i}^{T} = μ_{i}^{T} (Σ^{−1})^{T} = μ_{i}^{T} (Σ^{T})^{−1} = μ_{i}^{T} Σ^{−1}. And we conclude:

Note that x^{T} is a raw vector and w_{i} is a column vector. Hence, x^{T} w_{i} = w_{i}^{T} x holds.

□ Further two assumptions for simplification: • When Σ = σ^{2}I:

g_{i} − g_{j} = (\frac{1}{σ^{2}}μ_{i}^{T}x + w_{i0}) − (\frac{1}{σ^{2}}μ_{j}^{T}x + w_{j0})
= \frac{1}{σ^{2}}(μ_{i}^{T} − μ_{j}^{T})x + w_{i0} − w_{j0}  (58)

Here, we put

w^{T} = μ_{i}^{T} − μ_{i}^{T}  (59)

Then,

σ^{2}(g_{i} − g_{j}) = w^{T}x + σ^{2}(w_{i0} − w_{j0})
= ⋯ (see next page!)
= w^{T}(x − x_{0})  (60)

where

x_{0} = −\frac{1}{2}(μ_{i} + μ_{j}) − σ^{2} · ln\{\frac{p(ω_{i})}{p(ω_{i})}\} · \frac{μ_{i} − μ_{j}}{∥μ_{i} − μ_{j}∥^{2}} (61)

(Pattern Recognition) 29

In equation (60)

σ^{2}(w_{i0} − w_{i0}) = σ^{2}( ln p(ω_{i}) − \frac{1}{2} \frac{1}{σ^{2}}μ_{i}^{T} μ_{i}) − σ^{2}( ln p(ω_{j}) − \frac{1}{2} \frac{1}{σ^{2}}μ_{j}^{T} μ_{j})
= σ^{2}((ln p(ω_{i}) − ln p(ω_{j})) − \frac{1}{2}(μ_{i}^{T} μ_{i} − μ_{j}^{T} μ_{j}))
= σ^{2} ln \frac{p(ω_{i})}{p(ω_{j})} − \frac{1}{2}(∥μ_{i}∥^{2} − ∥μ_{j}∥^{2})
= (μ_{i} − μ_{j})^{T} − σ^{2} · ln \frac{p(ω_{i})}{p(ω_{j})} · \frac{(μ_{i} − μ_{j})^{T} (μ_{i} − μ_{j})}{(μ_{i} − μ_{j})^{T} (μ_{i} − μ_{j})}
= (μ_{i} − μ_{j})^{T} (−\frac{1}{2}(μ_{i} + μ_{j}) − σ^{2} · ln \frac{p(ω_{i})}{p(ω_{j})} · \frac{μ_{i} − μ_{j}}{∥μ_{i} − μ_{j}∥^{2}} )
≡ w^{T} x_{0}  (62)

Hence, from

σ^{2}(g_{i} − g_{j}) = w^{T} (x − x_{0}) = 0  (63)

we can conclude:

σ^{2}(μ_{i} − μ_{j})^{T} (x − x_{0}) = 0  (64)

- The point x_{0} is on the vector (μ_{i} − μ_{j}) and the location depends on σ^{2} and p(ω_{i})/p(ω_{j}), that is,

· If p(ω_{i}) > p(ω_{j}), then the hyper-plane is located closer to μ_{i}.

· If σ^{2} is small w.r.t. ∥μ_{i} − μ_{j}∥, then the location of the hyper-plane is insensitive.

(Pattern Recognition) 31

• Non-diagonal Covariance Matrix Σ

- As in the previous assumption we obtain:

g_{i} − g_{j} = w^{T}(x − x_{0})  (65)

where

w^{T} = μ_{i}^{T} − μ_{i}^{T}  (66)

and

x_{0} = −\frac{1}{2}(μ_{i} + μ_{j}) − σ^{2} · ln\{\frac{p(ω_{i})}{p(ω_{i})}\} · \frac{μ_{i} − μ_{j}}{∥μ_{i} − μ_{j}∥_{Σ^{−1}}^{2}} (67)

- Here, we refer ∥x∥_{Σ^{−1}} ≡ (x^{T}Σ^{−1}x) to Σ^{−1} norm of x.

- The decision hyper-plane is no longer orthogonal to μ_{i}−μ_{j} but to its linear transformation Σ^{−1}(μ_{i} − μ_{j}). · Under non-diagonal Σ, the Σ^{−1} norm □ Classification by the distance from the mean:

Recall that we classify x to ω_{i} such that g_{i} is maximized,

⇓ then it implies

• for diagonal Σ = σ^{2}I, minimize

d_{E} ≡ ∥x − μ_{i}∥  (68)

• for no-diagonal Σ, minimize

d_{M} ≡ (x − μ_{i})^{T}Σ^{−1}(x − μ_{i})  (69)

which is called Mahalanobis distance.

Note that:

• d_{E} = const. ⇒ hyper-sphere

• d_{M} = const. ⇒ hyper-ellipse □ Diagonalization of Variance Matrix:

— to learn the shape of the ellipses

Σ can be diagonalized by a unitary transform Φ as:

Σ = Φ^{−1}ΛΦ.  (70)

where Φ^{T} = Φ^{−1} because Φ is unitary, and Λ is the diagonal matrix whose elements are the eigenvalues of Σ. Φ has eigenvectors of Σ as its column, that is,

Φ = (ν_{1}ν_{2} ⋯ ν_{l}).  (71)

From (69) and (70), our hyper-ellipse becomes

(x − μ_{i})^{T}Φ^{−1}ΛΦ(x − μ_{i}) = const.  (72)

If we define x′ = Φx here,

x′ = ν_{k}^{T}x  (73)

implies the projections of x onto each eigenvector, and (72) becomes our familiar hyper-ellipse formula:

\frac{(x′_{1} − μ′_{i1})}{λ_{1}} + \frac{(x′_{2} − μ′_{i2})}{λ_{2}} + ⋯ + \frac{(x′_{l} − μ′_{il})}{λ_{l}} = const. (74)

(Pattern Recognition) 34

Thus, all points having the same Mahalanobis distance from a specific point are located on an ellipse.

(Pattern Recognition) 35

• Exercise 3: About a two-class, two dimensional Bayesian classifier where p(ω_{1}) = p(ω_{2}), μ_{1} = (0, 0), μ_{2} = (1, 0), and

Σ_{1} = Σ_{2} = Σ = ( \begin{matrix}1.1 & 0.3 \\ 0.3 & 1.9 \end{matrix} )

calculate the followings.

(1) Obtain d_{M} of x = (1.0, 2.2) from μ_{1} and μ_{2}, respectively.

(2) Should x classified to ω_{1} or ω_{2}?

(Compare the result when we use d_{E} instead of d_{M}.

(3) Obtain the ellipse when we suppose const. = 1.

(x − μ_{i})^{T}Σ^{−1}(x − μ_{i}) = 1, i = 1, 2.

(4) Calculate eigenvalues λ_{1} and λ_{2}, and eigenvectors ν_{1} and ν_{2} of Σ.

(5) Obtain Φ and Λ and ascertain Σ = Φ^{−1}ΛΦ.

(6) Obtain the projected ellipse (x − μ_{i})^{T}Φ^{−1}ΛΦ(x − μ_{i}) = 1, i = 1, 2.

(Pattern Recognition) 36

□ What to do with unknow pdf? So far we have studied known pdf p(x|ω_{i}) with its known parameter which is not of usual case. Usually,

· Pdf is known but some parameters are unknown; or · underlying pdf should be estimated from the available data.

□ Non-parametric pdf Estimation — Histogram approximation of unknown pdf.

• 2-D case:

(1) x-axis is divided into successive bins of length h.

(2) If N is the total number of samples and k_{N} of them are located inside a bin then pdf is approximated by

p(x) ≡ p(x̂) ≈ \frac{1}{h}\frac{k_{N}}{N}  (75)

for

|x − x̂| ≤ \frac{h}{2}  (76)

• l-D case:

In the same way as 2-D case, l-dimensional space is divided into hypercubes with length of side h whose volume is h^{l}.

- Assume we have N feature vectors:

x_{i} = (x_{i1}, x_{i2}, ⋯, x_{il}), i = 1, 2, ⋯, N.  (77)

and a function ϕ(x_{i}):

ϕ(x_{i}) = \{ \begin{matrix}1 & for |x_{ij}| ≤ 1/2 \\ 0 & otherwise. \end{matrix}  (78)

This is referred to as Parzen Windows (to continue)

Then

p(x) ≡ p(x_{i}) ≈ \frac{1}{h^{l}} (\frac{1}{N} N ; ∑ ; i=1 ϕ(\frac{x_{i} − x}{h}))  (79)

in which ∑ ϕ(·) implies the number of points falling inside the hypercube with length of side h centered at x_{i}, the point where the pdf is to be estimated, that is to say, ∑ ϕ = k_{N}. In short:

p(x) ≈ \frac{1}{h^{l}} (\frac{k_{N}}{N} )  (80)

- How to determine h and N. h: starting with a certain h, modify it iteratively to min-

imize misclassification error. (typically ranging from 0.1 to 0.8)

N: If N is appropriate for the 2-D version, the n-D version needs N^{n} samples.

• The likelihood ratio test using the Parzen Windows:

Assign x to ω_{1} if

\frac{\frac{1}{N_{1}h^{l}} ∑_{i=1}^{N_{1}} ϕ(\frac{x_{1}−x}{h})}{\frac{1}{N_{2}h^{l}} ∑_{i=1}^{N_{2}} ϕ(\frac{x_{2}−x}{h})} > \frac{p(ω_{2})}{p(ω_{1})} · \frac{(λ_{21} − λ_{22})}{(λ_{12} − λ_{11})}  (81)

□ k Nearest Neighbor Density Estimation (kNN)

While in the Parzen windows h is fixed, here in kNN it is k_{N} that is fixed.

• k Nearest Neighbor pdf:

When the volume of the hypercube^{14} around the point x, which includes k_{N} = k (fixed) out of a total of N samples, is V (x) then the pdf is estimated as:

p(x) = \frac{k}{NV (x)}  (82)

Note that the lower the density of samples the larger the volume V , and vice versa.

• The likelihood ratio test:

Assign x to ω_{1} if

\frac{N_{2}V_{2}}{N_{1}V_{1}} > \frac{p(ω_{2})}{p(ω_{1})} · \frac{(λ_{21} − λ_{22})}{(λ_{12} − λ_{11})}  (83)

the hypersphere.

14 Instead of hypercube, we might compute its Euclidean distance from all the training vectors of the different classes, that is, compute radius of the hypersphere centered at x that contains k points from ω_{i}. Then V (x) is the volume of

□ The Nearest Neighbor Density Estimation (k=1)

Algorithm 1 (The k Nearest Neighbor) Given an unknown feature vector x and a distance measure like Euclidean or Mahalanobis distance:

1. Out of the N training vectors, identify the k (an odd integer) nearest neighbors, irrespective of class.

2. Out of these k samples, identify the number of vectors k_{i} that belong to class ω_{i} i = 1, 2, ⋯ M. (∑ k_{i} = k).

3. Assign x to ω_{i} with the maximum k_{i}.

• The simplest version is when k = 1. This called Nearest Neighbor Algorithm (NN). Then:

x is assigned to its nearest neighbor class.

• kNN is no more the Bayesian classification but

P_{B} ≤ P_{NN} ≤ P_{B}(2 − \frac{M}{M − 1}P_{B}) < 2P_{B} (84)
P_{B} < P_{kNN} ≤ P_{B} + \sqrt{\frac{2P_{NN}}{k}}  (85)

are known, where P_{B} and P_{kNN} is misclassification error probabilities of Bayesian and kNN classifier, respectively.

(to continue)

And when P_{B} ≪ 1, we obtain that

P_{NN} ≈ 2P_{B}  (86)

and

P_{3NN} ≈ P_{B} + 3P_{B}^{2}  (87)

When P_{B} = 0.01, for example,

P_{3NN} − P_{B} ≈ 0.00003  (88)

Further, as k becomes large, kNN tends to the Bayesian classifier.

Definition 1 (Voronoi Tesselation) When k = 1, N training vectors x_{i} (i = 1, 2, ⋯, N) define a partition of the l-D feature space into N regions:

R_{i} = {x|d(x, x_{i}) < d(x, x_{j})} i ≠ j.  (89)

R_{i} contains all points that are closer to x_{i} than any other point.

□ Thought Experiments

• You have (one dimensional) 100 positive valued training samples created following^{15} :

p(x|ω_{1}) = x exp(−x^{2}/2)  (91)

and the other 100 following

p(x|ω_{2}) = 2x exp(−x^{2})  (92)

but you don’t know both of the function from which data are created.

(1) Classify a feature vector x produced at random.

(2) For each set of 100 data, observe the histogram with various value of h.

(3) Observe the histograms by changing N_{1} and N_{2} from

10 to 1000.

p(x) = \frac{x}{σ^{2}} exp(−\frac{x^{2}}{2σ^{2}} .)  (90)

15 This is the Rayleigh pdf defined as

(Pattern Recognition) 43

• For two sets of (2-dimensional) 100 data each drawn from

p(x|ω_{1}) = \frac{1}{2π} exp(−(x − μ_{1})^{T}(x − μ_{1}))  (93)
p(x|ω_{2}) = \frac{1}{2π} exp(−(x − μ_{2})^{T}(x − μ_{2}))  (94)

where μ_{1} = (1, 1) and μ_{2} = (3, 3).

(1) Classify a randomly cleated feature vector x using the Parzen windows.

(3) Try 3NN Algorithm for i) hypercube of length h; ii) hypersphere of radius r iii) a hyper ellipsoid

(3) Each of the above three cases, try to use likelihood ratio test.

• Create 100 training data following 3-dimensional Gaussian distribution with

Σ = ( \begin{matrix}0.3 & 0.1 & 0.1 \\ 0.1 & 0.3 & −0.1 \\ 0.1 & −0.1 & 0.3 \end{matrix} )  (95)

where μ_{1} = (0, 0, 0) and μ_{2} = (1/2, 1/2, 1/2).

(1) Classify a randomly cleated feature vector x using i) the Parzen windows; ii) 3NN Algorithm iii) NN Algorithm

(2) Try to use likelihood ratio test.

□ Parameter Estimation under Known pdf

- Assume that we have 100 data:

3.2, 2, 8, 5.4, 6.2 ⋯  (96)

that are drawn from p(x|ω_{i}), a pdf for a class i.

- Sometimes

· We don’t have no information as for pdf, which we have studied in the previous section. or · We know the function form but not parameters, which we are going to study in this section.

• Maximum Likelihood Estimation:

- For a data set

x = (x_{1}, x_{2}, ⋯, x_{N}),

when likelihood that x is drawn from the pdf with parameter θ is expressed as p(x; θ), we might say “p(x; θ_{1}) is more likely than p(x; θ_{2}).”

- Then which θ gives most likely p(x; θ)?

(to continue)

(Pattern Recognition) 45

- Under an assumption of independence between the different sample,

p(x; θ) ≡ p(x_{1}, ⋯, x_{N}) = N ; ∏ ; k=1 p(x; θ)  (97)

- To answer the question, likelihood function is defined as

l(θ) = N ; ∏ ; k=1 p(x_{k}; θ)  (98)

- The necessary condition of the most likely θ = θ_{ML} is

\frac{∂ ∏_{k=1}^{N} p(x_{k}; θ)}{∂θ} = 0  (99)

- Or sometimes more conveniently taking logarithm

L(θ) = ln N ; ∏ ; k=1 p(x_{k}; θ)  (100)

called loglikelihood function,

- and θ_{ML} is obtained from

\frac{∂L}{∂θ} = ∑ \frac{1}{p(x_{k}; θ)} · \frac{∂p(x_{k}; θ)}{∂θ}  (101)

Exercise

1. We now have 100 positive values

2.4, 5.6, 3.2 ⋯

and we know they are drawn from

p(x; θ) = θ^{2}x exp(−θx)  (102)

called Erlang pdf, but we don’t know the value of θ. Then what θ is the most likely value for the given 100 data?

2. We have 100 data drawn from N(μ, 1). What is the most likely estimate for μ?

• Maximum a posteriori pdf estimation

- For a data set X = (x_{1}, ⋯, x_{N}) θ, which is thought as a random variable here, is estimated its value on the condition that the data X has occurred.

Since

p(θ|X) = \frac{p(θ)p(X|θ)}{p(X)}  (103)

θ_{MAP} is estimated from

\frac{∂}{∂θ} p(θ|X) = \frac{∂}{∂θ} p(θ)p(θ|X) = 0  (104)

- The difference between ML and MAP is that the latter involves p(θ). Therefore if p(θ) is uniform distribution or if p(θ) has a large variance, the Both are the same or almost the same. But in general the two estimation yield a different results.

(to continue)

Example:

Assume we have 100 data from Gaussian pdf with unknown μ and we know μ is from Rayleigh pdf:

p(μ) = \frac{μ exp(−μ^{2}/2σ_{μ}^{2})}{σ_{μ}^{2}}  (105)

Estimate μ_{MAP}.^{16}

Yet Another Example:

Assume x_{1}, x_{2}, ⋯, x_{N} are data from Gaussian pdf with known σ and unknown μ, that is,

p(x_{k}; μ) = \frac{1}{\sqrt{2π}σ} exp\{−\frac{(x_{k} − μ)^{2}}{2σ^{2}}\}  (108)

and μ is known to be Gaussian distributed around the value μ_{0}, that is,

p(μ) = \frac{1}{\sqrt{2π}σ_{μ}} exp\{−\frac{(μ − μ_{0})^{2}}{2σ_{μ^{2}}}\}  (109)

Estimate μ_{MAP}.^{17}

μ_{MAP} = \frac{Z}{2R}(1 + \sqrt{1 + \frac{4R}{Z^{2}}}).  (106)
Z = \frac{1}{σ^{2}} ∑_{k=1}^{N} x_{k}, and R = \frac{N}{σ^{2}} + \frac{1}{σ_{μ}^{2}} .  (107)
μ_{MAP} = \frac{μ_{0} + (σ_{μ}^{2}/σ^{2}) ∑_{k=1}^{N} x_{k}}{1 + (σ_{μ}^{2}/σ^{2})N}  (110)

16 The answer is where 17 The answer is which can be interpreted as μ_{MAP} = μ_{0} when σ_{μ}^{2}/σ^{2} ≫ 1. I thank Lalehan for pointing this out!

□ Unknown pdf shortly revisited

• Maximum Entropy Estimation:

- Determine p(x) such that entropy

H = − ∫_{x} p(x) ln p(x)dx  (111)

is maximized.

• Estimation as a sum of known pdf:

- Assuming each sample x is drawn from any of the J pdfs with the probability p_{j}.

p(x) = J ; ∑ ; j=1 p(x|j)p_{j}  (112)

————————————————————————–

⋆ This concludes the course of this semister. ⋆ Thank you very much for your interest and atendance. ⋆ See you.