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.

□ 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}
⋆ if p(ω_{1}|x) < p(ω_{2}|x), then classify x to ω_{2}

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)}  (9)

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

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

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.

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

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

(Pattern Recognition) 10

□ l-dimensional Gaussian distribution:

• What does it mean by Gaussian distribution of a vector x?

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

Assume we have p samples each of x_{i} has a value x_{ik} (k = 1, 2, ⋯, p) such as:

x_{1k} x_{2k} ⋯ x_{lk}
k = 1 3.2 7.4  9.4
k = 2 2.3 8.1  8.7
⋯
k = p 2.9 9.2  7.9
μ_{i}
σ_{i}^{2}

You may fill the blancs for μ_{i} and σ_{i}. Then you define the pdf as:

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

where

μ = (μ_{1}, μ_{2}, ⋯, μ_{l})

and

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

In summary, · 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.e.,

μ_{i} = \frac{p ; ∑ ; k=1 x_{ik}}{p}

· σ_{i}^{2} is the variance of x_{i}, i.e.,

σ_{i}^{2} = \frac{p ; ∑ ; k=1(x_{ik} − μ_{i})^{2}}{p}

· σ_{ij} is the covariance between x_{i} and x_{j}, i.e.,

σ_{ij} = \frac{p ; ∑ ; k=1(x_{ik} − μ_{i})(x_{jk} − μ_{j})}{p}

· |Σ| is determinant of the matrix Σ; · Σ^{−1} is inverse matrix of Σ^{5} ; · x^{T} is transverse of vector x^{6} .

A = ( \begin{matrix}a & b \\ c & d \end{matrix} )  (13)
|A| = ad − bc  (14)
A^{−1} = \frac{1}{ad − bc} ( \begin{matrix}d & −b \\ −c & a \end{matrix} )  (15)
x^{T} = ( \begin{matrix}x_{1} \\ x_{2} \end{matrix} )  (16)

5 If we assume then and

6 That is, when x = (x_{1}, x_{2})

• 2-dimensional Gaussian We can calculate l = 2 version from the Equation (11) as:

p(x_{1} , x_{2}) = \frac{1}{\sqrt{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})\}

(17)

where ρ is correlation coefficient defined as:

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

Excersise 2 Try the following two problems.

1. Derive the equation (17) from the equation (11).

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) 13

□ 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  (19)

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

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

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

and we can say

if g_{i}(x) > g_{j}(x) classify x to ω_{i}.  (21)

Hence

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

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

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

(Pattern Recognition) 15

□ Examples of Decision Surface:

• 1-D Gaussian case. The Equation (19) in 1-D Caussian cases leads:

p(ω_{1}|x) = p(ω_{2}|x)  (23)

That is,

\frac{1}{\sqrt{2π}σ_{1}} exp\{−\frac{(x − μ_{1})^{2}}{2σ_{1}^{2}}\} = \frac{1}{\sqrt{2π}σ_{2}} exp\{−\frac{(x − μ_{2})^{2}}{2σ_{2}^{2}}\}.  (24)

Solving this equation w.r.t. x you can obtain decision surface, actually a point in this case, x_{0}. ^{8} Excersise 3 Obtain the decision boundary x_{0} when the two classes follow the Gaussian distributions with N(1, \frac{1}{2}) and N(3, \frac{1}{2}) respectively.

• General Gaussian case. The Equation (11) with taking the function ln as f(·) in the Equation (20), 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}

where

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

8 See also the Eqations (9) and (10).

(Pattern Recognition) 16

• 2-D Gaussian case. Our discriminat function (25) for 2-D Gaussian pdf is

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

where

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

This is simplified

⋆ if

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

then

g_{i} = \frac{(x_{1} − μ_{1})^{2}}{−2σ_{1}^{2}} + \frac{(x_{2} − μ_{2})^{2}}{−2σ_{2}^{2}} − \frac{1}{2} ln(σ_{1}^{2}σ_{2}^{2}) + ln p(ω_{i}) − \frac{1}{2} ln(2π)  (28)

Note that the last two terms in the right hand side of the above equation will be cancelled when obtaining the border g_{i} − g_{j} = 0.

- This kind of two distributions construct a quadratic decision surface. · ellipsoid · hyperbola · parabola · pair of lines

- If expanded to l > 2 case, then it is called hyper-quadratic.

- If σ_{1} = σ_{2} holds in both Σ_{i} and Σ_{j} then the decision surface is a circle.

- Furthermore, if Σ_{i} = Σ_{j} holds then the decision surface is a straight line.

(Pattern Recognition) 17

Excersise 4 When p(ω_{1}) = p(ω_{2}), μ_{1} = (0, 0) and μ_{2} = (1, 1) obtain decision surface in the following four cases.

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

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

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

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

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

Excersise 5 When p(ω_{1}) = p(ω_{2}) again, but μ_{1} = μ_{2} = (0, 0) this time, obtain decision surface.

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

Excersise 6 When p(ω_{1}) = p(ω_{2}), what condition is needed for the border of two classes to be the following decision surface?

(1) ellipse;

(2) parabola;

(3) hyperbola;

(4) two straight lines.

(Pattern Recognition) 18

• Examples of border — from Excersise 4 and 5.

The equations of the above borders are: (1)

x_{1} + x_{2} = 1.

(2)

(x_{1} + 1)^{2} + (x_{2} + 1)^{2} = 4 − 0.2 ln(1/4).

(3)

15(x_{1} + 1)^{2} + 8(x_{2} + 3/2)^{2} = 93/2 − 6 ln(3/10).

(4)

x_{1}^{2} + 4x_{1} + 12x_{2} − 8 + 0.6ln(2/3) = 0.

(5)

(x_{1} + 1)^{2} − (x_{2} − 3/2)^{2} = 3/2.

(6)

(\sqrt{3}x_{1} + \sqrt{5})(\sqrt{3}x_{1} − \sqrt{5}) = 0.

(Pattern Recognition) 19

⋆ An example of more general case:

That is, our Σ is no more of the form

( \begin{matrix}σ_{1}^{2} & 0 \\ 0 & σ_{2}^{2} \end{matrix} )

but, instead, of the more general form

( \begin{matrix}σ_{1}^{2} & σ_{12} \\ σ_{21} & σ_{2}^{2} \end{matrix} ) .

Then the Equation (26) leads an equation of the form c_{1}x_{1}^{2} + c_{2}x_{2}^{2} + c_{3}x_{1}x_{2} + c_{4}x_{1} + c_{5}x_{5} + c_{6} = 0.

Excersise 7 When p(ω_{1}) = p(ω_{2}), μ_{1} = (0, 0) and μ_{2} = (1, 1) still holds, obtain decision surface in the following case.

Σ_{1} = ( \begin{matrix}0.3 & 0.1 \\ 0.1 & 0.4 \end{matrix} ) , Σ_{2} = ( \begin{matrix}0.5 & 0.3 \\ 0.3 & 0.2 \end{matrix} )

The border of the Excersise 7 will be 18x_{1}^{2} − 67x_{1}x_{2} − 52x_{2}^{2} = (11/10) ln 11.

Excersise 8 But how can we draw the graph of this equation?

□ Classification by distance from mean:

Recalling that we classify x to ω_{i} such that g_{i} is maximized, the Equation (25) implies we minimize:

(x − μ_{i})^{T} Σ^{−1}(x − μ_{i})  (29)

that is,

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

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

• for no-diagonal Σ, minimize

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

which is called Mahalanobis distance.

Note that:

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

• d_{M} = const. ⇒ hyper-ellipse

Excersise 9 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} )

answer the following questions.

(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}.

□ Diagonalization of Variance Matrix:

— to learn the shape of the ellipses

Definition

• Eigenvalue of Σ are λ’s that satisfy

|Σ − λI| = 0  (32)

• Eigenvector of Sigma are x’s that satisfy

Σx = λx  (33)

Then we have the following relation:

Σ = ΦΛΦ^{T}  (34)

where Λ is the diagonal matrix whose elements are the eigenvalues of Σ, Φ is a matrix whose columns are corresponing eignevectors of Σ, and due to its symmetry Φ^{T} = Φ^{−1}.

Hence, our ellipse d_{M} = c^{2} becomes:

(x − μ)^{T} ΦΛΦ^{T} (x − μ) = c^{2}.  (35)

This is interpreted as:

(X − μ)^{T} Λ(X − μ) = c^{2}  (36)

on the (rotated) new coordinate:

( \begin{matrix}X_{1} \\ X_{2} \end{matrix} ) = X = Φ^{T} x  (37)

where the ellipse has the equation of the form:

a_{1}X_{1}^{2} + a_{2}X_{2}^{2} = c

instead of the form:

a_{1}x_{1}^{2} + a_{2}x_{2}^{2} + a_{3}x_{1}x_{2} = c

(Pattern Recognition) 22

Excersise 10 When

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

answer the following questions.

(1) Obtain Eigenvalues of Σ.

(2) Obtain Eigenvectors of Σ.

(3) Solve the equation w.r.t. x_{1} and x_{2}.

x^{T} Σ^{−1}x = 1.

(4) Obtain Φ and Λ, and ascertain the relation:

Σ = Φ^{−1}ΛΦ.

(5) Obtain the equation of the projected ellipse w.r.t. X_{1} and X_{2}

x^{T} (ΦΛ^{−1}Φ^{T})x = 1

that is,

X^{T} Λ^{−1}X = 1.

(Pattern Recognition) 23

• Examples of border — from Excersise 10 Since now our Σ is

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

x^{T} Σx = (x_{1} x_{2}) ( \begin{matrix}0.95 & −0.15 \\ −0.15 & 0.55 \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \end{matrix} ) = ⋯ = 0.95x_{1}^{2} − 0.30x_{1}x_{2} + 0.55x_{2}.

So our ellipse is, e.g.,

0.95x_{1}^{2} − 0.30x_{1}x_{2} + 0.55x_{2} = 1.

In order to learn the shape of the ellipse we transform it with Σ = ΦΛΦ^{T} where

Φ = \frac{1}{\sqrt{10}} ( \begin{matrix}3 & 1 \\ −1 & 3 \end{matrix} )

and

Λ = ( \begin{matrix}1 & 0 \\ 0 & 2 \end{matrix} )

That is, our ellipse x^{T} Σ^{−1}x = 1 is expressed as x^{T} ΦΛ^{−1}Φ^{T} x = 1 where

x^{T} Φ = (x_{1} x_{2}) ( \begin{matrix}3 & −1 \\ 1 & 3 \end{matrix} ) /\sqrt{10} = (3x_{1} − x_{2} x_{1} + 3x_{2})/\sqrt{10}

and

Φ^{T} x = ( \begin{matrix}3 & −1 \\ 1 & 3 \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \end{matrix} ) /\sqrt{10} = (3x_{1} − x_{2} x_{1} + 3x_{2})/\sqrt{10}

Hence, if we use the new coordinate:

(X_{1} X_{2}) = (3x_{1} − x_{2} x_{1} + 3x_{2})/\sqrt{10}

our ellipse is

(X_{1} X_{2}) ( \begin{matrix}1 & 0 \\ 0 & 2 \end{matrix} ) ( \begin{matrix}X_{1} \\ X_{2} \end{matrix} ) = 1

That is

X_{1}^{2} + 2X_{2}^{2} = 1

(Pattern Recognition) 24

• From Excersise 9 and 10. · Points whose Mahalanobis distance is identical from center (mean) of the two classes respectively.

□ Pattern Classification by Neural Network

• We can use Neural Networks to classify for any number of features to any number of classes.

• What is Neural Networks?

– Neuron

– Synaps

– Synaptic weight and Transfer function

– Learning • Definition of variables:

– L layers of neurons.

– k_{r} neurons in the r-th layer. r = 1, 2, ⋯, L.

– M input neurons (k_{1} = M) and N output neurons (k_{L} = N).

– w_{ij}^{r}: weight from the j-th neuron in the r-th layer to the i-th neuron in the r-th layer.

– p training pairs: (x(μ), z(μ)), i = 1, 2, ⋯, p.

– y_{i}^{r}(μ): the output of the i-th neuron in the r-th layer when the μ-th training sample is given.

– fan-in’s to j-th neuron in the r-th layer when the μ-th training sample is

given.

h_{j}^{r}(μ) ≡ k_{r−1} ; ∑ ; k=1 w_{jk}^{r}y_{k}^{r−1}(i) + w_{j0}^{r} = k_{r−1} ; ∑ ; k=0 w_{jk}^{r}y_{k}^{r−1}(i),  (38)

where

y_{0}^{r−1} = 1

and

(y_{1}^{1}(μ), ⋯, y_{M}^{1}(μ)) = (x_{1}(μ), ⋯, x_{M}(μ)) = x(μ).

– Each output neuron’s error:

e_{i}(μ) ≡ y_{i}(μ) − z_{i}(μ), i = 1, 2, ⋯, N.  (39)

where (z_{1}(μ), ⋯, z_{N}(μ)) = z(μ)

– Error function to be minimized:

D = \frac{1}{2} p ; ∑ ; μ=1 N ; ∑ ; i=1 e_{i}(μ)^{2}  (40)

• An example of the notations - L = 3, M = k_{1} = 4, N = k_{3} = 3 and k_{2} = 2.

- e.g.

⋆ h_{2}^{2}(μ) = w_{21}^{1} · x_{1}(μ) + w_{22}^{1} · x_{2}(μ) + w_{23}^{3} · x_{3}(μ) + w_{24}^{1} · x_{4}(μ). ⋆ h_{2}^{3}(μ) = w_{21}^{2} · y_{1}^{2}(μ) + w_{22}^{2} · y_{2}^{2}(μ).

(Pattern Recognition) 28

□ Back Propagation

— Learning for multi-layered analog neural networks.

• The algorithm:

1. Initialization:

· Initialize all the weights with small random values.

2. Forward computations:

· For each of the training vectors

x(i), μ = 1, 2, ⋯, p

compute all the

y_{j}^{r}(μ) = f(h_{j}^{r}(μ))  (41)

for j = 1, 2, ⋯, k_{r} and r = 1, 2, ⋯, L.

3. Backward computations:

· For each μ = 1, 2, ⋯, p and j = 1, 2, ⋯, N compute

δ_{j}^{L}(μ) = e_{j}(μ)f′(h_{j}^{L}(μ)).  (42)

· Then compute

δ_{j}^{r−1}(μ) = e_{j}^{r−1}(μ)f′(h_{j}^{r−1}(μ))  (43)

for r = L, L − 1, ⋯, 2 and j = 1, 2, ⋯, k_{r} where

e_{j}^{r−1}(μ) = k_{r} ; ∑ ; k=1 δ_{k}^{r}(μ)w_{kj}^{r−1}.  (44)

4. Update the weights for r = 1, 2, ⋯, L and j = 1, 2, ⋯, k_{r}

w_{jk}^{r} [new] = w_{jk}^{r} [old] + △w_{jk}^{r}  (45)

where

△w_{jk}^{r} = −ϵδ_{j}^{r}(μ)y_{k}^{r}(μ).  (46)

until no change occurs during the training cycle of μ = 1, 2, ⋯, p.

(Pattern Recognition) 29

(⋆ Forward calculation in our previous toy example: From the bottom to top.)

y_{1}^{1}(μ) = x_{1}(μ), y_{2}^{1}(μ) = x_{2}(μ), y_{3}^{1}(μ) = x_{3}(μ), y_{4}^{1}(μ) = x_{4}(μ).

⇓

h_{1}^{2}(μ) = w_{11}^{1} · y_{1}^{1} + w_{12}^{1} · y_{2}^{1} + w_{13}^{1} · y_{3}^{1} + w_{14}^{1} · y_{4}^{1} from (38)

⇓ similarly h_{2}^{2}(μ).

⇓

y_{1}^{2} = f(h_{1}^{2}(μ)) from (41)

⇓ similarly y_{2}^{2}(μ).

⇓

h_{1}^{3}(μ) = w_{11}^{2} · y_{1}^{2} + w_{12}^{2} · y_{2}^{2} from (38) again

⇓

similarly h_{2}^{3}(μ) and h_{3}^{3}(μ).

⇓

y_{1}^{3} = f(h_{1}^{3}(μ)) from (41) again

⇓

similarly y_{2}^{3}(μ) and y_{3}^{3}(μ).

(Pattern Recognition) 30

(⋆ Backward calculation in our previous toy example: From the top to bottom.)

e_{1}^{(3)} = y_{1}^{3} − z_{1}(μ) from (39)

⇓

similarly e_{2}^{(3)}(μ) and e_{3}^{(3)}(μ).

⇓

δ_{1}^{3}(μ) = e_{1}^{(3)} · f′(h_{1}^{3}(μ)) from (42)

⇓

similarly δ_{2}^{3}(μ) and δ_{3}^{3}(μ).

⇓

e_{1}^{2}(μ) = δ_{1}^{3}(μ) · w_{11}^{2} + δ_{2}^{3}(μ) · w_{21}^{2} + δ_{3}^{3}(μ) · w_{31}^{2}

⇓

similarly e_{2}^{2}(μ) from (44).

⇓

δ_{1}^{2}(μ) = e_{1}^{2}(μ) · f′(h_{1}^{2}(μ)) from (43)

⇓ similarly δ_{2}^{2}(μ).

⇓

e_{1}^{1}(μ) = δ_{1}^{2}(μ) · w_{11}^{1} + δ_{2}^{2}(μ) · w_{21}^{1} e_{2}^{1}(μ) = δ_{1}^{2}(μ) · w_{12}^{1} + δ_{2}^{2}(μ) · w_{22}^{1} e_{3}^{1}(μ) = δ_{1}^{2}(μ) · w_{13}^{1} + δ_{2}^{2}(μ) · w_{23}^{1} e_{4}^{1}(μ) = δ_{1}^{2}(μ) · w_{14}^{1} + δ_{2}^{2}(μ) · w_{24}^{1}

from (44) again

⇓

δ_{1}^{1}(μ) = e_{1}^{1}(μ) · f′(h_{1}^{1}(μ)) from (43) again

⇓

similarly δ_{2}^{1}(μ), δ_{3}^{1}(μ), δ_{4}^{1}(μ).

• Rationale ⋆ Thought Experiment: 1-D weight

Modification:

w^{new} = w^{old} + △w  (47)

where

△w = −ϵ · \frac{dD}{dw}|_{w=w^{old}}  (48)

means that starting from w_{0}, w gradually approaches the point where D takes a minimum value with δw being decreased.

⋆ An example: XOR (revisited)

In this example,

D = \frac{1}{2}\{e_{1}^{(3)}\}^{2}
= \frac{1}{2}\{y_{i}^{(3)} − z_{i}\}^{2}
= \frac{1}{2}\{(f(h_{i}^{3}) − z_{i}\}^{2}
= \frac{1}{2}\{f(w_{11}^{2} · y_{1}^{2} + w_{12}^{2} · y_{2}^{2}) − z_{1}\}^{2}
= \frac{1}{2}\{f(w_{11}^{2} · f(h_{1}^{2}) + w_{12}^{2} · f(h_{2}^{2}) − z_{1}\}^{2}
= \frac{1}{2}\{f(w_{11}^{2} · f(w_{11}^{1} · y_{1}^{1} + w_{12}^{1} · y_{2}^{1}) + w_{12}^{2} · f(w_{21}^{1} · y_{1}^{1} + w_{22}^{1} · y_{2}^{1}) − z_{1}\}^{2}
= \frac{1}{2}\{f(w_{11}^{2} · f(w_{11}^{1} · x_{1} + w_{12}^{1} · x_{2}) + w_{12}^{2} · f(w_{21}^{1} · x_{1} + w_{22}^{1} · x_{2}) − z_{1}\}^{2}

You can see that D is a function of only all the weights (6-D in this case).

(Pattern Recognition) 33

⋆ Where are the definitions of δ_{j}^{r} and e_{j}^{r−1} in (43) and (44) from? We have studied that

D = \frac{1}{2} N ; ∑ ; i=1 e_{i}^{2}  (49)
= \frac{1}{2} N ; ∑ ; i=1(y_{i} − z_{i})^{2}  (50)
= \frac{1}{2} N ; ∑ ; i=1(f(h_{i}^{L}) − z_{i})^{2}  (51)

where

h_{i}^{r+1} = k_{r} ; ∑ ; k=1 w_{ik}^{r} · y_{k}^{r}  (52)

So, D is a function of all the w_{ik}^{r} and

\frac{∂D}{∂w_{jk}^{r}} = \frac{∂D}{∂h_{j}^{r+1}} · \frac{∂h_{j}^{r+1}}{∂w_{jk}^{r}}  (53)

holds. From (52)

\frac{∂h_{j}^{r+1}}{∂w_{jk}^{r}} = y_{k}^{r}  (54)

and we put

δ_{j}^{r+1} ≡ \frac{∂D}{∂h_{j}^{r+1}}  (55)

Since D is a function of h_{i}^{L} and

h_{i}^{r+1} = k_{r} ; ∑ ; k=1 w_{ik}^{r}f(h_{k}^{r}),  (56)

recursive use of this equation D can be expressed as a function of

k_{r} ; ∑ ; k=1 w_{ik}^{r}f(h_{k}^{r})

for any r. So δ_{i}^{r−1} is defined as

δ_{i}^{r−1} ≡ \frac{∂D}{∂h_{i}^{r−1}} = k_{r} ; ∑ ; i=1 \frac{∂D}{∂h_{k}^{r−1}} · \frac{∂h_{k}^{r}}{∂h_{k}^{r−1}} = k_{r} ; ∑ ; i=1 δ_{k}^{r} · \frac{∂h_{k}^{r}}{∂h_{k}^{r−1}}  (57)

Here,

\frac{∂h_{k}^{r}}{∂h_{k}^{r−1}} = \frac{∂(k_{r−1} ; ∑ ; m=1w_{km}^{r} · f(h_{m}^{r−1}))}{∂h_{k}^{r−1}} = w_{kj}^{r} · f′(h_{j}^{r−1})  (58)

(Pattern Recognition) 34

Hence,

δ_{i}^{r−1} = k_{r} ; ∑ ; k=1 δ_{k}^{r} · w_{kj}^{r} · f′(h_{j}^{r−1})  (59)

In conclusion, if we define

e_{j}^{r−1} = k_{r} ; ∑ ; k=1 δ_{k}^{r} · w_{kj}^{r}  (60)

we obtain

δ_{j}^{r−1} = e_{j}^{r−1} · f′(h_{j}^{r−1})  (61)

□ Linear Transformation — to reduce number of features.

• Discrete Fourier Transform (DFT)

y(k) = \frac{1}{\sqrt{N}} N−1 ; ∑ ; n=0 x(n) exp(−j \frac{2π}{N}kn)  (62)

· Inverse DFT

x(n) = \frac{1}{\sqrt{N}} N−1 ; ∑ ; k=0 y(k) exp(j \frac{2π}{N}kn)  (63)

- DFT transforms x(0), x(1), ⋯, x(N − 1) to y(0), y(1), ⋯, y(N − 1).

- For example, we can send transformed data y instead of real data x.

- The number of data is not reduced directly, but usually most of the energy lies in the low-frequency region.

- Matrix form of the transformation e.g. N = 4

\frac{1}{2} ( \begin{matrix}1 & 1 & 1 & 1 \\ 1 & j & −1 & −j \\ 1 & −1 & 1 & −1 \\ 1 & −j & −1 & j \end{matrix} )

• Kalhunen-Loeve Transform (KL)

K-L Transform is calculated from the correlation matrix R of the data, so that the n-th raw is the eigen vector of R corresponding to the n-th largest eigen value.

Excersise 11 Obtain the K-L Transform for the correlation matrix:

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

(Pattern Recognition) 36

• Hadamar Transform:

· For a 2^{n}-dimensional vector x (2^{n} feature vector), the transform and its inverse transform are:

y = H_{n}x, x = H_{n}y  (64)

where

H_{n} = H_{1} ⊗ H_{n−1}  (65)

and

H_{1} = \frac{1}{\sqrt{2}} ( \begin{matrix}1 & 1 \\ 1 & −1 \end{matrix} )  (66)

Here ⊗ denotes the Kronecker product for two matrices:^{9}

[A ⊗ B]_{ij} = A_{ij}B  (70)

• Haar Transform:

· For a 2^{n}-dimensional vector x:

(1) Define Haar function h_{k}(z), which is continuous and are defined in [0, 1] as follows:

- Decompose k into two integers p and q, such that

k = 2^{p} + q − 1, k = 0, 1, ⋯, L − 1  (71)

which is unique when

\{ \begin{matrix}q = 0 or 1 & if p = 0 \\ 0 ≤ p ≤ n − 1, 0 < q ≤ 2^{p} & if p ≠ 0 \end{matrix}  (72)
A = ( \begin{matrix}1 & 2 \\ 3 & 4 \end{matrix} )  (67)
B = ( \begin{matrix}5 & 6 \\ 7 & 8 \end{matrix} )  (68)
A ⊗ B = ( \begin{matrix}5 & 6 & 10 & 12 \\ 7 & 8 & 14 & 16 \\ 15 & 18 & 20 & 24 \\ 21 & 24 & 28 & 32 \end{matrix} )  (69)

9 for example, if and then we define

(Pattern Recognition) 37

- then Haar functions are

h_{0}(z) ≡ h_{00}(z) = \frac{1}{\sqrt{L}}  (73)

and

h_{k}(z) ≡ h_{pq}(z) = \frac{1}{\sqrt{L}} \{ \begin{matrix}2^{\frac{p}{2}} & if \frac{q−1}{2^{p}} ≤ z < \frac{q−\frac{1}{2}}{2^{p}} \\ −2^{\frac{p}{2}} & if \frac{q−\frac{1}{2}}{2^{p}} ≤ z < \frac{q}{2^{p}} \\ 0 & otherwise in [0, 1] \end{matrix}  (74)

(2) The k-th raw of the Haar transform matrix of order L = 2^{n} is:

z = \frac{m}{L}, m = 0, 1, 2, ⋯ L − 1.

Excersise 12 Obtain the 8 × 8 transform matrix.

· An example of n = 3, that is, L = 8.

k = 2^{p} + q − 1, k = 0, 1, ⋯, 7  (75)

where

\{ \begin{matrix}q = 0 or 1 & if p = 0 \\ 0 ≤ p ≤ 2, 0 < q ≤ 2^{p} & if p ≠ 0. \end{matrix}  (76)

So,

p=0 q=0 k=0
q=1  k=1
(0 < q ≤ 2) (k = 1 + q)
p=1 q=1 k=2
q=2  k=3
(0 < q ≤ 4) (k = 3 + q)
p=2 q=1 k=4
q=2  k=5
q=3  k=6
q=4  k=7

Hence,

k 0 1 2 3 4 5 6 7
p 0 0 1 1 2 2 2 2
k 0 1 1 2 1 2 3 4

Then the Haar functions are:

h_{1}(z) ≡ h_{01}(z) = \frac{1}{\sqrt{8}} \{ \begin{matrix}1 & if & −1 ≤ z < \frac{1}{2} \\ −1 & if & \frac{1}{2} ≤ z < 1 \end{matrix}  (77)

h_{2}(z) ≡ h_{11}(z) = \frac{1}{\sqrt{8}} \{ \begin{matrix}\sqrt{2} & if 0 ≤ z < \frac{1}{4} \\ −\sqrt{2} & if \frac{1}{4} ≤ z < \frac{1}{2} \\ 0 & otherwise in [0, 1] \end{matrix}  (78)

h_{3}(z) ≡ h_{12}(z) = \frac{1}{\sqrt{8}} \{ \begin{matrix}\sqrt{2} & if \frac{1}{2} ≤ z < \frac{3}{4} \\ −\sqrt{2} & if \frac{3}{4} ≤ z < 1 \\ 0 & otherwise in [0, 1] \end{matrix}  (79)

· · · · · ·

h_{7}(z) ≡ h_{24}(z) = \frac{1}{\sqrt{8}} \{ \begin{matrix}2 & if \frac{3}{4} ≤ z < \frac{7}{8} \\ −2 & if \frac{7}{8} ≤ z < 1 \\ 0 & otherwise in [0, 1] \end{matrix}  (80)

and

\begin{matrix}h_{0}(z) & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ h_{1}(z) & 1 & 1 & 1 & 1 & –1 & –1 & –1 & –1 \\ h_{2}(z) & \sqrt{2} & \sqrt{2} & −\sqrt{2} & −\sqrt{2} & 0 & 0 & 0 & 0 \\ h_{3}(z) & 0 & 0 & 0 & 0 & \sqrt{2} & \sqrt{2} & −\sqrt{2} & −\sqrt{2} \\ h_{4}(z) & 2 & –2 & 0 & 0 & 0 & 0 & 0 & 0 \\ h_{5}(z) & 0 & 0 & 2 & –2 & 0 & 0 & 0 & 0 \\ h_{6}(z) & 0 & 0 & 0 & 0 & 2 & –2 & 0 & 0 \\ h_{7}(z) & 0 & 0 & 0 & 0 & 0 & 0 & 2 & –2 \end{matrix}

Since

H_{ij} = \frac{1}{\sqrt{L}}h_{j}(\frac{j}{L}),  (81)

we obtain

H = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & −1 & −1 & −1 & −1 \\ \sqrt{2} & \sqrt{2} & −\sqrt{2} & −\sqrt{2} & & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \sqrt{2} & \sqrt{2} & −\sqrt{2} & −\sqrt{2} \\ 2 & −2 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & −2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & −2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 2 & −2 \end{matrix} )  (82)