Characteristics and Organizing Capability of Statistical Organizer

Introduction

In the self-organizing system, there are two typical organizers: the non-statistical and sta­ tistical, The non-statistical organizer is re­ presented by Perceptron type procedure. The properties of this organizer, such as the capa­ bility of the information processing and the concrete method for the organization are reported in several papers. Although this system shows high capability in information processing, it has some disadvantages as follows:

(a) If the input patterns are not linearly separable, the organizing procedure does not converge and

Shoichi Noguchi and Juro Oizumi

Research Institute of Electrical Communication Tohoku Univ, , Sendai Japan

to check the linear separability, numerous trials are sometimes required,

(b) Even though the patterns are linearly separa­ ble, numerous trials and large memories are also sometimes required.

In contrast to the disadvantages of non- statistical method, the statistical method has many merits from the practical point of view,

These merits are summarized as follows: The system can be organized in an optimal way even when the input patterns are not linearly separable. (b) the organization of the system can be made quickly by the analogue technique, Several kinds of the statistical organizers have been developed,

However, the capability of the organizer to process information should be further investigated. From this standpoint, we took the theoretical evaluation of the statistical organizer into con­ sideration. We introduced some new concepts of the information processing capacity and the per­ cent information processing capacity, as in the case of the nonstatistical organizers. The organizing capability of each organizer is evaluated by these concepts,

The problems which are taken into considerations are (1) the organizing capability of the typical organizers, (2) the relation between the organizing capability and the information which is utlized for the system organization, (3) the relation of the organizing capability between the linear organizer and the nonlinear one, and (4) the properties of ·multi-category organizer,

l. The Properties .of the Typical Statistical Organizers(l)

In this section, two typical organizers, the Bayesian organizer and the regression organizer are taken into consideration in order to make clear the general behaviors of the statistical organizer, Our basic assumptions are as follows: (a) The patterns are classified into two categories, I and II.

• M (b) Both categories have a member of --z- sample patterns, respectively, (We can also extend our analysis with slight modification to the various cases of different sample patterns in each category,)
• (c) Each pattern is represented by anN dimen-

sional vector X and each X is distribut~d ac:c:ording to multivariat;-normal distribution N (fl.. , ~) (j = 1, 2) (l::.j is an N dimensional unknown ~Jet;; and 1:; is anN x N unknown matrix) and

(d) The sample covariance matrix is assumed to be full rank.

1. 1. The Bayesian Organizer

In this model, the fundamental principle is to find i which minimizes Cx(i) when the input pattern X is applied; where

and X.(ij j) is a loss function assigned to this system.

Estimating the mean and the covariance matrix by unbiased estimators, one obtains the decision function which decides the region of classification into I, R1 and into II, R2 as follows:

'i(j) (j = 1, 2) are the sample means fer each category, and§. is a sample covariance matrix.

l. 2. The Regression Organizer

In this system, we. assign the desired Rftput Y~j) to each pattern ~J) (j = 1, 2, a = 1""- 2 -) and organize the weight vector Wand the threshold W 0 so as to minimize the following Q function;

The optimum values, Wand W 0 are obtained by

u = 4:~ (Y (j) _ Y)(x(jLx> -]a a ~-

and§. is a sample covariance matrix. The final decision function which decides the region of classification into I, R1 and into II, R2 is obtained by

l. 3. The Properties of the Bayesian Organizer

If the sample pattern is applied to the decision function, the distribution of this output is approxi­ mated by the un.inormal distribution:

We define a new parameter db by

This parameter db means the measure of the separation of two categories. 2 The distribution of this parameter is a kind of T distribution derived by Hotelling. (2)

The probability density function of db is obtained by

where

The relation between the correct recognition probability Rb and db is given by

1. 4. The Properties of the Regression Organizer

If the input patterns are applied to this system, the distribution of the output is approximated by the uninormal distribution N(fL· , T). (j = l, 2); The assignment of the desired 1 output y~)is an im_portant problem. However putting YU) = 1 and y(aC! = -1 pr-oved to be an optimum assignment.

~ In this case, fij and Tare given by

"" M t -1 fil = 4Q ~ § , ~ Mrt-lr fi = --o v o 2 4-- -

A new parameter dr is defined by

The correct recognition probability is obtained by

After ~ome ~anipulations, it is pr~ved that .~ is the un1que e1genvalue of the followmg equatwn,

where

and B = S + d, d t - -o -o-o

We obtain the important relation between db and dr by 4d

Substituting this relation in (1. 15), we obtain the foll?wing probability density function of d , when Y ( ) = 1 and Y ( 2) = -1 · r a a '

where B(x) is a Beta function.

This is a kind of noncentral Beta distribution.

l. 5. The Organizing Capability and the Information Processing Capacity of the Organizer

The probability density function of the correct classification is determined theoretically as the function of M, N, (1::!-\- l!:_ 2 ) and~ for each organ­ izer. But in order o have an insight in the gross, we simplify the problem by considering the representative parameters of the distribution.

where \ and d are the mean value of each distribution db fnd dr , respectively.

We define two concepts, the information process­ ing capacity I (b) and percent processing capacity n I~b-)-..l.:(a~"ll:J..o) of the Bayesian organizer by the following equations:

and

This means the pattern processing capacity for one dimension. The same definition is also adopted in other organizers as discussed in the . following section.

1. 6. The Organizing Capability of the Bayesian and the Regression Organizer

By the definition of Rb and R , these are obtained finally as follows: r

As the typical cases, we consider the following problems.

(1) The pattern is distributed according to N(Q, ~). (2) The pattern is distributed according to

for II, respectively;

For the first case, we obtain

These results imply that

The information processing capacity and the per­ cent information processing capacity are given by

and

For the second case, we obtain

and

1, 8. Computer Simulations

In our simulations, the normal random patterns distributed according to N(Q, ,!!) are adopted first, (!!.is an unit matrix). Every point on the curve is obtained by the mean value of the ten trials.

Figures (1) and (2) show the theoretical curves and the experimental results of the mean recognition rate vs. M/N for the Bayesian organizer and the regression organizer, respectively.

The results of the computer simulations show good agreement with those of the theoretical curves, The same results are also obtainei when the patterns are distributed according to N(z .AJ..

1 ~ 1 ) . for I category and to N(- 2 AJ., ~ 1 ) for II, respectively.

2, The Relation between the Organizing Capability and the Total Information Which is Utlized for the System Organization

We consider the effect on the organizing capability by the information which is utlized for the system organization. In this section, the Bayesian deci­ sion rule is adopted as the basic principle for the system organization, so the mean values and the covariance matrices of the sampled patterns are only utlized for the organization, The decision function is organized so as to be the admissible linear function. ( 3)

The assumptions for the input pattern are the same as in the Section 1 except the assumption for the covariance matrices, Consider the typical case in which the covariance matrices ~1 and ~2 have the following relation.

We put

and

where each C. is some constant. The rank of ~li 1 and ~2i are equal to Ni ·

In this section, the system is organized with the partial information such as the unbiased esti­ mators of dj~ and ~h , respectively. These are denoted by~ N)) and .§.u · The information contained in the matrices:!:!:, ~, s; and Q are not utlized,

The admissible linear decision function g(~) is obtained as follows:

The output of g(X) is approximated by the uni­ normal distribution with the mean wtx 1 + W and the covariance matrix !Yt§.t"Y{, if~ -b-;; longs 0 to I. The average correct recognition robability in this system is given by f (tl !Yt§.l !Y) for the pattern belonging to I, and by ~(t2J !Yt§. 2 !Y) for the pattern be longing to II.

Putting t.J WS.W = y. (i = 1, 2), it is proved 1 --11 after some calculations that y~ is proportionally 1 distributed according to the sum of the noncentral F distributions. The mean value n of yf and y~ of y~ are

obtained, respectively, as follows:

By the definition of the information processing capacity, In, in this organizer becomes:

The mean recognition ability R is approximately given as follows if M, N >> 1 : D

As typical examples, consider the following cases, (i) t = t , V. = 0 (i = 1, 2), L:· are the same as Eq. ~2. dan d- 1 (2:3) and N1 = N; 1 = --- = Nm = -tk:

-2 -2 We obtain Yl and y 2 for each case as follows;

where

The re suits obtained by these analyses show the very interesting fact that if the distributions of both patterns have the covariance matrices as Eq. (2. 2) and (2. 3), the organizing capability of this system is limited to max (Ni/ N). The relation between the organizing capability and the total information which is utilized to organize the system is obtained by Eq. (2. 16) for the case (ii). This result implies that the information processing capacity decreases to rh- and the curve Rn vs. MfN decreases more loosely with the increase of m,

The minimum distance classifier is the most extreme case stated above, In this organizer, the information contained in the covariance matrix is not utilized at all and the decision is based only upon the difference of the means of two dis­ tributions, The information processing capacity becomes zero in this organizer.

The theoretical curves for Rn vs, MfN are given in Fig. 3 for the typical cases of m with computer simulations.

3. The Relatio.n of the Organizing Capability between the Linear Organizer and the Nonlinear Organize r!4)

As is well known, the optimum Bayesian organizer be comes the quadratic form if the patterns belong to N(J:j· ~j) (j = 1, 2) and the covariance matrices are different, Because the general consideration of the organizing properties, when~\: ~2 , is very complicated, we treat the simple case where A. 2 L: 2 = L: 1 as a first step. The relation of the organizing capability between the linear organizer and the nonlinear organizer are made clear in the following discussions, We investigate the characteristics of the linear admissible organizer and the optimum nonlinear organizer ' separately and then summarize them, The assumptions for the pattern are the same as ·in the Section 1 except that the covariance matrices are different, We assume that L: 2 = L: and that A. 2 is known,

3.1. The. Pr.opertie s of the Admissible Linear Organizer

Assigning the loss function X.(i I j) as 1 - 0 .. and minimizing the system loss, the admissibfJ linear decision function g(~) is obtained as follows;

Considering that the output of gQ9 is distributed approximately according to uninormal distribu­ tion, the recognition probability RL is given as follows:

Af 1 1 . . . d h M - N - 1 ter ca cu atwns, 1t 1s prove t at N ( l M l ) -"d . d. .b d d. 2 - 2 2 b 1s 1str1 ute accor 1ng M>.. +1 _,.... to noncentral F distribution and the mean of db is obtained as follows;

The mean recognition ability R is obtained as follows; L ·

The analysis given here shows that the influence of>.. is slight; RL becomes minimum at>.. = 1 and shows a slight increase with a change of>... The relation between RL and MfN when 'f = 0 is given in Fig. 4 with some computer simulations.

3. 2. The Properties of the Optimum Nonlinear Organizer

Consider the properties of the optimum nonlinear organizer, assuming the same input patterns as in Section 3. 1 :

We consider the case >..) 1, but the same results are also true for >.. < 1.

The basic decision function is obtained as follows:

where ~(j) (j = 1, 2) are the sample means and~ is the same as Eq. (3. 2).

The approximate distribution of g(X) is theoreti­ cally obtained for both cases when~ belongs to I or to II, respectively. These are expressed as the sum of the distribution functions.

Substituting the mean values for these functions, the mean recognition ability R of this organizer . b . d N 1s o ta1ne ·

This is the first stage approximation of the capability of this organizer.

After troublesome derivations, RN is obtained as

and \.f is the same as Eq. (3. 5). _ M When 'f = 0, the relation between RL and IN is obtained in Fig. 5 with the computer simula­ tions.

3. 3. ThEl Re l_a.tion oj t.h.e O.rga.n.i~iJ+g Capability between. the Linea.r Organizer and the Nonlinear Organizer

By the analyses obtained in Sections 3. 1 and 3. 2, the organizing capability of the nonlinear organ­ izer also shows the same information processing capacity, In= 1. But it must be mentioned, however, that the number of the weighting e le­ ment which is required to organize the system is N(N+l)/2. In the derivation of~, it is im­ portant to mention that the dimension of the input pattern N is adopted instead of the number of the weighting element.

The improvement of the organizing capability compared to the linear case is quite poor when X. 2 is near one, although this situation is improved rapidly with the increase or the decrease of x_2. The theoretical results and the computer simula­ tions show that the organizing capability of the linear and the nonlinear organizer are nearly the same if 0. 8 < X. 2 .C:::: l. 2 .

From these considerations, it is important to develop the useful nonlinear organizer for the case where x_2;::::_ l.

4. The Organizer for R Category Problem

The organizer decribed in the previous section is chiefly suitable fitted for the two-category problem.

Because of its complexity for the final decision, it is not always suitable for the multi-category classification. In order to improve this point, two multi-category organizers, the modified fisher organizer and the modified regression organizer, are considered.

The organizing capability of these organizers are evaluate<l theoretically and experimentally. The basic assumption for the input patterns is the same as for Section 1 except that the number of the category is increased to R and the number of the pattern belonging to each category is M/R. The set of the category are composed of~ , w 2 ,

..... wR·

It should be mentioned that the organization of the classifier described in this section has no relation to the distribution but, for simplicity, the case ~ 1 = ~ 2 = . . . . = ~R = ~ is considered.

4. l. The Modified Fisher Organizer

In this system, the classifier organizes the decision function for each category. Thus, ther e are R organizers. The input patterns are assumed to b e distributed according to N{J:j , ~j ), respectively. (j = 1""'- R). The linear function for each categorizer is organized to make the following function F j maximum under the constraint such that ~/§.f{j = C : where

Using the m e thod of Lagrange multiplier, and after some calculations, the decision function g{JS) for each category is obtained as follows:

and

By this organization, the pattern is classified into the categorylA)s if gi(JS) (i = lvR) shows the minimum value at i = S .

The. correct recognition probability of this organ­ ize r is obtained by calculating the conditional probability P(i I l) such that

After some calculations, P(i I 1) is approximated by the following equation

where

Thus the average recognition ability RF is approximated by

As the most typical case, we consider a two­ category problem, assuming that both patterns belong to the same distribution N(O, ~ ). In this case, we obtain - -

By the definition of the information processing capacity, we obtain

and

The analysis obtained here can also be extended to the R-category problem and we obtain as follows:

It should be mentioned that the information processing capacity for one weighting element is also one in this organizer, as in other cases dis­ cussed in the previous sections. The theoretical curve for this example is given in Fig. 6.

4 . 2. Modified Regression Classifier

We have already discuss e d the regression organ­ izer for a two-category problem in the Section 1. This method can be straightly extended to an R­ category problem.

We set the optimal super surface for each wj so that! Yf· t ~ + W 0 j I becomes minimum o~ the aver­ age under the constraint such that I "Yfj ~ · I = C. After some calculations, it is proved thal the same decision functions are obtained for each category as shown by Eq. (4. 2).

From this consideration, the results obtained in the previous section are also true for this organizer .

5. Conclusion ·

The properties and the organizing capability of the statistical organizer are analysed systemati­ cally by means of the information processing capacity and p e rcent information processing capacity.

So far as these concepts are concerned, we found that the Bayesian organizer and the regression organizer show the same organizing capability in the first stage approximation and the information processing capacity becomes 1 for both cases. The relation between the organizing capability and the total information which is utilized for the system organization is studied for some typical cases.

As one of these results, we obtain the interesting fact that if the distributions of both patterns belong to N(J:j, ~) (j = 1, 2), the information proce·ssing capacity is limited to max(NifN), where Ni is the rank of the subcovariance matrix which is utilized to organize the classifier. The relation of the organizing capability between the linear classifier and the nonlinear classifier is obtained when the ~atterns are distributed according to N(J: 1 , X. ~ ) and N(J: 2 , ~ ) respectively.

The effect of x.2 on the organizing capability is discussed. So long as the admissible linear organizer is adopted, the variation of the organ­ izing capability is slight with the change of X.. Although the optimal nonlinear Bayesian organ­ izer shows a higher organizing capability than the linear organizer, the improvement of its capability is poor as long as X. 2 is near 1. This situation can be improved rapidly, however, with the increase or the decrease of x.2.

For the R-category problem, two typical organ­ izers -the modified fisher organizer and the modified regression organizer - are studied. The organizing capability of these organizers ar e also evaluated by means of the information processing capacity.

Both organizers show the same organizing capa­ bility for the R-category problem with In= R . This implies that the organizers can treat R .N patterns correctly. But the number of the weight­ ing element required for the system organization is also R ·N. In order to check the theoretical results, seve ral kinds of computer simulation ar e made for the organizing capability and the infor­ mation processing capacity for each organizer using the random patterns. These r esults coin­ cide well with our theoretical results.

Reference

1. S. Noguchi, K. Nagasawa and J. Oizumi "Fundamental Consideration on Statistical Recognizer" Proceeding of the Hawaii Inter­ national Conference on System Science 1968 - Jan.
2. ( 2) T. W. Ander son " An Introduction to Multi­ variate 'Statistical Analysis" John Wiley & Sons, Inc ..

1. T. W. Anderson and R. P. Bahadur "Classification into Two Multivariate Normal Distributions With Different Covariance Matrices" Ann. of Math. Stat. val. 33. 1962
2. M. Sato, S. Noguchi and J. Oizumi "Classification Capability of Statistical Linear Recognition Function (I)" The Record of Electrical and Communication Engineering Conversazione, Tohoku Univ. , Sendai, Japan Vol. 37, No. 2, 1968

RN ( 0 /o)

100 ~----~~~~..!..._~~__:

: theoretical curve

0 : A 2 = 4 I N = 16

X : A 1 = 1-9 6 · N = 8

SOL-----------~------------~------------

M/N

1

0

2

______ N=1;}A2= 4

1 ;} A 2 = 1· 96