--- title: "On the Classification of Patterns by the Karhunen-Loeve Orthogonal System Without Supervisor" authors: - "Shingo Tomita" - "Shoichi Noguchi" doi: "" url: "https://ijcai.org/proceedings/1971/44" pdf: "https://ijcai.org/proceedings/1971/0044.pdf" venue: "Proceedings of the Second International Joint Conference on Artificial Intelligence" year: 1971 pages: "424-427" track: "" keywords: --- # On the Classification of Patterns by the Karhunen-Loeve Orthogonal System Without Supervisor Shingo Tomita, Shoichi Noguchi *Proceedings of the Second International Joint Conference on Artificial Intelligence*, pages 424-427. ## Abstract In this paper we show how the pattern samples generated from the unknown asymmetric finite mixture distribution are dichotomized by the Karhunen-Loeve orthogonal system in the optimal wa y. We introdu ce the concept of the difference of features of two categories and prove that decreasing the error proba b ilit y of dichotom y is equal to increasing the difference of features of two categ o ries. And it can be shown that the maximum difference of features obtained by the KL system is equivalent t o that which is obtained by the Ba y es soluti o n. Moreover it can be pro ved that there exists a dichotom y which converges to the Bayes s o lution by increasing the number of samples. ## Full text ## 1. Introduction Let us explain the outline of the Karhunen­ Loeve orthogonal system. Let a pattern on the N-dimensional space ~ be X and a normal and orthogonal system on ~ be a. · Then a pattern X is expanded by a as follows : Let the mean square of coeffi c ients of X be ~.ll(a) · E [ i!ca/ 1 · ()1·1,2, .. ,N), where E[*l· 5·dG(X) is the distribution of patterns . Suppose that all !.~~<a)'s are ordered as follows: The sum, ~(a, m) - r )lm&l S)l(a)' is defined as a quantity of features extracted by a 1 , a 2 , .. ,am. Let the autocorrelation of a set of patterns X be E [XXT 1, then an eigenvalue A~ and the eigenvector t, corresponding to /\~ is obtained by the equation E[XXT1 t 11 = /\ 11 t 11 Let the normal and orthogonal system be t · (t 1 , t 2 , .. , tN), then :;>-.,.= ~.ll(t) and S (t,m) · Max~~ (a,m) I \fa} are proved respectively. The above normal and orthogonal system is called the Karhunen-Loeve orthogonal system or simply (1) the KL system. ## 2. Classification without supervisor Let an asymmetric finite mixture distribution of patterns be G(X)·PF (X/ w 1 )+ qF (X I w 2 ), where q+pz l,p,q ) 0, and w 1 and w 2 are the given two categories. Let the two vetcors and two matrices be defined as follows : Suppose that Rank E[XXT1 · N, then there exists a matrix S such that SE[XXT1 ST · I, where I is an unit matrix. Let all the patterns generated from the distrubution G(X) transform by S, and denote them by the same symbol {X l , then T T E[XX / w 1 1 · I+ 2qD, E[XX I w 2 1 · I-2pD. The two quantities of features corresponding to w 1 and w 2 extracted by the KL system are proved to be the eigenvalues of E[XXT J w 1 1 and E[XXTI w 2 1, respectively, so A ~l) and )\<;> are two quantities of features corresponding to w 1 and w 2 . A~ is obtained by the following equati~n. 12l (i=l,2: )lml, 2, . ·, (i) N). Let Dt,=).,lll ()1=1, 2, ... , N) and)\~r} ·.· J>.N. In order to classify a set of given patterns into two true categories, we introduce a parameter to evaluate the extent of the correct classification and adopt the parameter f such that s> = the difference of features. Although the mixture distrubution G(X) is given, f is not determined uniquely in general. But if G(X) is identifiable ~ is determined uniquely. · So we obtain the following theorm. Theor4!!m 1 If the asymmetric finite mixture distribution G(X) is identifiable, then the difference of features ~ is determined uniquely by G(X). * * Let w 1 and w 2 be two sets of patterns which are decided by some dichotomy, then the conditional probability P(w. j w~ ) satisfies the J l following formula: * * * * P(w 1 J w 1 ) + P(w 2 J w 1 ) · P(w 1 1 w 2 )+P(w 2 1 w 2 )·1. * * Moreover let p and q be defined as follows: * * * * * q · P (w 2 J w 1 ) + P(w 1 1 w 2 ). If p ) 1 then q is defined as an evaluated error value, if * * p ( 1, then p is defined as an evaluated error value. * * For a set of pattern wi, P(X I wi)· P(X I w 1 ) * * P(w 1 J wi) + P (X lw 2 ) P(w 2 I w 1 ), then we have * * * F(X I wi)·F(X I w 1 ) p(w 1 J wi)+F(X I w 2 )p(w 2 J wi). T * T Consequently, E[XX I wi] · E[XX I w 1 J + E[XXTI w 1 p(w I w* )·········(1) 2 2 i * * For two sets of patterns w 1 and w 2 , the difference of features is defined as follows s>*- :r~-1 ( )\:(1)\_ ~;2))2 ' A"J is where )\*;i) is the eigenvalue of the T * autocorrelation E[XX I wi 1 and ordered in the following way : .,.11) vice versa. From the formula (1), we obtain the important * relation between ~ and ~ such that ~··ll-q*l~ If two dichotomies are executed, then two * ** difference of features ~ and f are decided * ** respectively. And let q , q be evaluated ** * * ** error probabilities, then ~ - f ·(q -q >i> Theorem 2 Let the following condition be A. Condition A: G(X) is identifiable and Y is not zero. ** * ** * Then ~ > ~ if and only if q < q under the condition A. If the dichotomy to get the maximum difference of features is equal to decreasing the evaluated error value q* into zero, then P(w 1 Jwj *) · ~ ij or 1 - ¢ ij · Theorem 3 Let the condition A be satisfied. Then .E (wi I w; ) · ~ ij * if and only if P(X I wi) · P(X I wj ) . From the result of theorem 3, it is possible to estimate the true distributions corresponding to each given category, if it is possible to * decrease the evaluated error value q into zero. Let the ideal decision function be d(X) ·P(w 1 ( X) * -P(w, I X) and a decision function be d (X) · * * * ·P(w 1 I X) - P(w 2 I X) when w 1 and w 2 are given. Suppose that the specified two sets of patterns J\ )\ are w 1 and w 2 which are obtained by some dichotomy, and let the difference of features and the decision function corresponding 1\ " " and w 2 be ~ and d(X), respectively. J\ to w 1 J\ + "' "' If d(X) · \_d(X), then P(w 1 ) + 0, P(w 2 Then the following theorem is obtained. Theorem 4 + 0. Suppose that the condition A is satisfied. Then ~ · ~ if and only if d(X)·!d(X). Let the true distance of means between the two categories w 1 and w 2 be - r · II E [X I w 1 1 - E [X I w 2 1 II , and a "' "' distance of means between w 1 and w 2 be * * "' r · II E[X[w 1 1- E[Xiw 2 111 where II 1\ is a norm of a vector. Then r "'· I 1-q"' I r . Theorem 5 Suppose that the condition A is sat i sfied and E[X I w 1 1 + E[X I w 2 1. Let the symmetric finite mixture distribution G(X) be defined as the special form such that The two mean vectors corresponding to w 1 and w 2 are defined respectively as follows : E[X I w 1 1 · J XdF(X-CO, E[X I w 2 1 · ~ XdF(XHI), where ol is an unknown parameter. * * Let the mean vector of wi be E[X I w. 1, then "' * ]. * E[X I wi1 · E[X I w 1 1p(w 1 J wi) + E[ X I ~ 2 1p(w 2 j wi). Suppose that the specified vector 0{ is defined as follows Then from the theorem 5, the following corollary is obtained. (3) * * + Corollary 51 : ~ · ~ if and only if · a · \_0(. Suppose that the distribution G(X) satisfies the following condition B. Condition B : For any small E > 0, there exists a large positive number K such that T where X · (x 1 , x 2 , .. . , xN). Let a set of finite patterns be 1 X()l)] Zn+l or \ x<-n). x<-n+l) ·.·· x<n)} and { x (J)} Zn+l satisfy the following condition. Condition C : For any small E.) 0, there exists a large integer n such that for some positive number A, where X(-n)T · (-K, -K, ·· , -K), X(n)T. ( K, K, · · , K ) · The autocorrelation of 1 X(ll) } Zn+l is defined as follows : E[XXT1 is a symmetric matrix, so there exists a normal matrix S(n) such that s<n) E[XXT1(n)S(n)T · I . Let all patterns i X()l)} Zn+l transform by S (n), and denote them by the same symbol ~ X (.ll ) } Zn+l, and two sets of patterns which are obtained by a d . h f I X(ll ) l 2n+l be *(n) and *(n) l.C otomy rom l r w 1 w 2 respectively . "' The aut ocorrelation of a set of patterns wi is defined as follows : *(n) *(n ) Let the difference of features w 1 , w 2 be f*(n) and win), win) be ~ (n), respectivel y , where w~n) satisfies the following equation : P(win) I w:(n)) + P(wt) I w:(n)) · 1. Then the following theorm is obtained . Theorem 6 Suppose that all the conditions A, B and C are satisfied. Then - (ii) Let the maximum difference of features be defined as follows : Then As the summary, we obtain the final conclusions as follows~ - (A) If the asymmetric finite distribution of patterns is identifiable, increasing the difference of features is equivalent to decreasing the error probability of classifi­ cation, and obtaining the maximum differnce of features is equivalent to estimating the true distrubutions of given categories. - (B) To obtain the maximum difference by some dichotomy is equivalent to getting the Bayes solution and to getting the maximum distance of means between two categories, if the two means of categories are not equal. - (C) There exists a dichotomy with probability one to get the maximum difference of features by incresing the number of samples and this dichotomy converges to the . Bayes solution with probability one. ![Image](https://ijcai.org/proceedings/1971/fulltext/44/image_000000_c5502927a2d84553627a023b7078f4a51b200d9e7d41eb276616753a0c399ba0.png) Table 1 | ex | !.0 | :z.o | 1.0 | 0.'15 | 0.5 | o.~s | |----------|-----------|--------|-------|---------|--------|----------| | Di" | 'Tl 0 | !~.0 | 'd.o | 4.5 | 2.0 | o.s | | E.* | 0.01::2. | 0.057 | 0.103 | o:~so | o.s'!~ | o. ~t.?> | | ~ IIIClt | l. l:\'7? | 1.q1o | I.SH | 1.3~1 | I. lot | o.'13S | ## 3. Results on a computer Let a 2-dimensional normal distribution with the mean vector M.and the covariance matrix~. be N(X:M., :2:,.) and the mixture of two normal distributions be G(X) · pN(X:~+~, I) + qN(X:M. T T -~.I), where M. ·(1,1), ~ · (~. 0), Ol>O and I is an unit matrix of 2X 2. To compare our method with a classification with teacher, the decision function d(X) by the Bayes law is adopted as follows In this case, the decision function d(X) is reduced as follows : d(X) · log~+ (X-~~:Q~X-MJT·· ............. (2) The dichotomy is as follows : If d(X)~O, then x·w 1 ; if d(X)<O, then XE- w 2 . To simulate the mixture of normal distributions, random numbers are generated from the normal distribution with mean value zero and the variance value one . The uniform distribution with the interval [0,1) is used, and the classification based on theorem 6 and the formula (2) are executed on a digital computer. The results on a computer are shown Fig. 1 and 1 Table 1 in the case of p ·q - 2 and M · 800, where M is the number of samples. In Fig. 1 and Table 1, four symbols are as follows C :Classification with teacher based on d(X) . * C : Classification without teacher based on the theorem 6. Uiv: Divergence reported by Kullback( 4 ) . * t Absolute error rate. ## 4. Conclusion Utlizing the concept of the Karhunen-Lo~ve orthogonal system which extracts the maximum difference of features of patterns, the algorithm of classification for patterns generated from an unknown asymmetric finite mixture distribution is obtained, and this one is proved to become the Bayes solution. As a concrete example, random numbers generated from the 2-dimensional mixture of normal distributions are used and good results are obtained on a digital computer. ## Reference - (1) S. Watanabe Wily, 1969. Knowing and Guessing, - (2) K. Fukunage, etc. : Application of the Karhunen-Lo~ve expansion to feature selection and ordering, IEEE Trans. C-19 (1970) . - (3) D.B. Cooper, etc. : On suitable condition for statistical pattern recognition without supervision, SIAM. Appl. Math. 17 (1969). - (4) S. Kullback : Information theory and statistics, Dover, 1968 . ## References 1. S. Watanabe Wily, 1969. Knowing and Guessing, (2) 2. K. Fukunage, etc. : Application of the Karhunen-Lo~ve expansion to feature selection and ordering, IEEE Trans. C-19 (19 70 ) . 3. D.B. Cooper, etc. : On suitable condition for statistical pattern recognition without supervision, SIAM . Appl. Math. 17 (1969). 4. S. Kullback : Information theor y and statistics, Dover, 1968 .