Dependency Relationship Based Decision Combination in Multiple Classifier Systems

1 Introduction

Generally, two directions have been developed in the area of character and pattern recognition for improving clas­ sification performance. One is to improve the classifica­ tion performance of a classifier itself. The other one is to improve a multiple classifier system which consists of a set of classifiers and a decision combination method. Although a number of classifiers are available, none of them is as good as expected. The major difficulty comes from the fact that although a number of features in di­ versified forms are available, but it is not easy to lump them together into a single classifier. The multiple clas­ sifier system is motivated from the assumption that a number of complementary features or classification al­ gorithms can facilitate the classification performance, if they are used simultaneously. This research idea in com­ bining multiple decisions seems to be promising.

·This work is partly supported by the Notepad Consor­ tium and the Offline Consortium.

tTo whom all the correspondence should be addressed. He also works for Samsung Electronics, Co.

Many studies in multiple classifier systems have fo­ cused on the fact that a classifier corresponds to an ex­ pert in multiple experts group. They conducted a study about the methodology of integrating multiple decisions from different classifiers[Mandler and Schuermann, 1988; Hull et al., 1990; Suen et al., 1990; Xu et al., 1992; Franke and Mandler, 1992; Huang and Suen, 1993; Ho, 1992; Ho et al., 1994]. Although many studies have been conducted for better combining multiple decisions, most of them did not focus on dependency relationship among classifiers. Instead, they considered multiple clas­ sifiers as being independent.

As seen in previous studies, if the highly dependent inferior classifiers are added to a multiple classifier sys­ tem, and they have equal weights, then the classification performance of it can be degraded and biased b~ so~e of those decision combination methods. The motivatiOn of this paper is to overcome the shortage of previous studies.

It is desirable to construct a multiple classifier system in which classifiers complement each other for better per­ formance, and to combine multiple decisions by using the dependency relationship, if necessary. In this paper, we will provide some methods in identifying the dependency relationship, and in combining multiple decisions, using Bayesian formalism.

To identify dependency relationship of a classifier from K classifiers, we should consider all the possible cases of lower order subdistributions from the definition of prod­ uct approximation by Lewis[Lewis, 1959]. Because that requires enormous computations and storage spaces, we will approximate K-dimensional distribution with the K - 1 first-order dependency distributions by consid­ ering only the classification results of classifiers, and by using two identification methods proposed. Two meth­ ods are considered for the work. One of them depends on the principle of maximizing mutual information by Chow[Chow and Liu, 1968], and the other one is to use maximally measured association. The first-order depen­ dencies identified are used in order to combine multiple decisions, using Bayesian formalism.

All the classifiers were created by Hidden Markov Models (HMMs). The HMMs have been used as a frame­ work of on-line cursive script recognition[Sin et al., 1994] and can model well for both variations of temporal se­ quences and spatial movements. Also, they were used as components of a multiple classifier system. A number of multiple classifier systems are applied to totally un­ constrained on-line numerals and the English alphabet recognition.

In our experiment, we will apply a number of decision combination methods to combine multiple decisions in multiple classifier systems, and to compare their classifi­ cation performances each other. In particular, several combinations of multiple classifiers for demonstrating the effects of highly dependent classifiers will be carried out, and then tested by decision combination methods proposed.

2 Related Works

A number of studies related to the idea of using mul­ tiple classifiers for improving classification performance will be described. The researches of combining multiple decisions are divided according to the types of classifi­ cation results. These types include measurement scores of classes, rankings of classes, and single top choice of classes. From the measurement scores of classes, we can assign a ranking to each class by ordering classes as to their scores. Single top choice of a class is chosen by the best measurement score or by the first ranked.

Decision combination methods based on the measure­ ment scores are averaged Bayes classifier[Xu et al., 1992] and an integration of multiple classification results us­ ing fuzzy integral[Tanahi and Keller, 1990] or fuzzy logic. In case of single top choice, there are voting methods[Suen et al., 1990; Franke and Mandler, 1992; Xu et al., 1992], the use of Bayesian formalism un­ der an independence assumption[Xu et al., 1992], the use of Dempster-Shafer formalism used in evidential reasoning[Mandler and Schuermann, 1988; Franke and Mandler, 1992; Xu et al., 1992], and Behavior-Knowledge Space (BKS)[Huang and Suen, 1993]. In particular, in the use of Bayesian formalism by Xu et al.[Xu et a/., 1992], they assume that the classifiers are independent because they use independent feature sets or they are trained independently. This approach happens to cause a problem when they are not independent. Ho et al.[Ho, 1992; Ho et. a/., 1994] support the use of rankings and have studied the decision combination methods using such rankings from multiple classifiers which include the highest rank methoo, Borda count method, and logistic regression. Borda count method is well known one of social choice functions used in our experiment. In this paper, we concentrate on the type of ranking decisions due to the advantages of rankings.

Lewis[Lewis, 1959] tackled a problem of approximat­ ing a nth-order· binary distribution by a product of sev­ eral of its component distributions of lower order using the idea of extension by Hartmanis. He showed that the product approximation, under suitably restricted conditions, had the property of minimum information. The approximation method was based on an informa­ tion measure for the closeness of two distributions and on the criterion of maximum entropy. Two or more pro­ posed approximations could be compared and the best one be selected without any knowledge of actual dis­ tribution beyond that given by the approximations. In order words, the process of comparison consists of select­ ing that approximation containing the greatest amount of correlation. However, the problem of selecting a set of component distributions of a given complexity to com­ pose the best approximation remained unsolved.

Chow et al.[Chow and Liu, 1968] studied to solve the unsolved problem by Lewis and to best approximate an nth-order distribution by a product of n -1 second-order component distributions. A method was presented to approximate optimally an n-dimensional discrete prob­ ability distribution by a product of second-order distri­ butions, or the distribution of the first-order tree depen­ dencies. To find an optimum set of n - 1 first-order dependency relationship among n variables, a procedure was derived to yield an approximation of a minimum dif­ ference in information. An optimal procedure was on the basis of maximizing the mutual information between two variables and Maximum Weight Spanning Tree (MWST) algorithm by Kruskal.

3 Multiple Classifier Systems

A Multiple Classifier System (MCS) consists of a set of classifiers and a decision combination method[Ho, 1992]. In this paper, a set of classifiers is built based on a HMM structure and a few stochastic modeling methods[Sin et a/., 1994; Sin and Kim, 1994]. The HMM structure is left-to-right transitionary and consists of 8 state nodes and only left-to-right arcs. In order to create classifiers consisting of HMMs modeled from training data, we use a few stochastic modeling methods which are standard modeling (i.e. Baum-Welch algorithm), duration model­ ing, and nonstationary modeling. One HMM was mod­ eled to represent one class at training. Although they have the same HMM structure, they would be differ­ ent classifiers if they are modeled by different modeling methods.

The graphical representations of stochastic modeling methods are shown in Figure 1 by focusing on transition probabilities at state nodes. Standard modeling method is easy and takes a short time to train the HMMs, but it does not properly model duration information of a pattern. Duration modeling method supplements such a weakness of standard modeling method, but it takes a long time to train. Nonstationary modeling method is proposed by Sin et al.[Sin and Kim, 1994] for overcoming the weakness of duration modeling method which does not properly consider the duration information. Their approach is based on the idea that the duration in a state node should be modeled as a function of duration period, and by that idea it can properly consider the duration information. This method has an advantage of the best modeling for typical patterns, but it takes a very long time to train and it has a disadvantage of the worst modeling for unusual patterns. A MCS is a good choice why there are no complete stochastic modeling methods for improving the classification performance.

For the recognition of numerals and the English alpha­ bet characters, a classifier consists of 10 HMMs, or 26 HMMs, or 26 HMMs which are stochastically modeled for respective domain problem and assigns a likelihood score as to degree of match to each HMM for a given input. So, we have to convert the likelihood scores of HMMs into the rankings of classes modeled to HMMs before combining multiple decisions.

In this paper, a number of MCSs are constructed. One of them consists of three classifiers shown in Figure 2 which are based on the HMMs trained by three stochas­ tic modeling methods. It is called by Base-type in our experiment. And the others are constructed by adding

the highly dependent inferior or superior classifier to the previous three classifiers which is respectively denoted by St80ut, Du80ut, and NS80ut. The highly depen­ dent classifier is made by faking one of the previous three classifiers.

Multiple decisions from individual classifiers of MCS will be combined according to a combining rule assigned to Decision Combinator and a winner class will be de­ cided or not. The input of all classifiers are 16-directional chain codes in common. But different stochastic model­ ing methods cause classifiers to classify differently for a given input. The output of each classifier is converted as the rankings of classes, and then they are used as the input of Decision Combinator. Any classifier producing the rankings of classes can join into our MCS.

Only classifiers producing valid decisions take part in a process of Decision Combinator. Also, only classes having valid rankings are used in decision combination. Under those constraints, Decision Combinator includes a number of decision combination methods available in this paper. They are voting methods, some of social choice functions, BKS method, the uses of Bayesian for­ malism under an independence assumption and depen­ dency relationship among classifiers.

4 Dependency Relationship Based Decision Combination

On the assumption that multiple classifiers are indepen­ dent, the use of Bayesian formalism is proposed by Xu et al.[Xu et al., 1992]. In this paper, since an inde­ pendence assumption would not be appropriate if some highly dependent classifiers join in multiple classifiers, we focus on the dependency relationship among clas­ sifiers. We will propose some methods for identifying the dependency relationship and combining multiple de­ cisions, using Bayesian formalism. We will denote a set of classes by {M1, · · ·, MM }, a set of classifiers by C= {C1, ···,CK}, and an input pattern by x.

4.1 Identifying the Dependency Relationship

In order to build a K-dimensional joint probability dis­ tribution in a direct way, we can use K-dimensional sam­ ples observed. But when the K becomes larger and each classifier takes one of a set of M distinct classes, it re­ quires much computation and massive storage of the or­ der of MK, and that is impractical in theoretical view­ points. In other way, which is based on the chain rule of probability, we can express the joint probability dis­ tribution in terms of conditional probabilities:

In considering the dependency relationship, we assume that it is determined by the observations of outputs of individual classifiers given the same inputs. With K classifiers, the precise dependency relationship should be determined by considering maximum K - 1 order depen­ dencies by the definition of chain rule, since we do not know in advance the exact order of dependency relation­ ship among them. When K classifiers are applied to the same input x, K events, Ck(x) = Mj, k = 1, · · ·, K and j = 1, · · · , M, will happen. Basing on the fact that it is desirable to consider first-order dependency relationship rather than to assume independence of classifiers, we will approximate the joint probability distribution with most appropriate second-order conditional probabilities based on the first-order dependency relationship:

Then the problem is how to identify an optimal set of first-order dependencies from classification results of classifiers. Our approaches to tackle that problem are to use two methods. One is to maximize the mutual infor­ mation and the other one is to maximize the measures of association between classifiers.

Mutual Information

When we approximate K -dimensional distribution with a set of K -1 first- and second-order component distribu­ tions, we should identify the first-order dependence dis­ tribution such that the relative entropy, I( P( C), Pt( C)), of unknown true distribution P( C) and the first-order dependence distribution Pt(C) from a set of all possible first-order dependence trees is as small as possible[Lewis, 1959; Chow and Liu, 1968]. When the relative entropy is zero, we assure that a couple of distributions involved are equal.

From the expression of I(P(C), Pt(C)), mm1m1zmg the relative entropy is equivalent to maximizing the sum ofmutual information (i.e. L:f=l M(Cj,Ci(i))) between a classifier Cj and a classifier C ;(j) · A classifier C;(j) is the parent of a classifier Cj in first-order dependency relationship. A root node in a dependence tree does not have a parent node. A H(C) means an entropy of distri­ bution C and Cj is a component of C. The definition of mutual information is described in [Chow and Liu, 1968; Gallager, 1968] and the average mutual information by Gallager means the mutual information by Chow et al. which is used in this paper. To obtain the maximum sum of mutual information over all classifiers, we as­ sign each classifier to a node of a possible dependence tree and assign the quantity of mutual information to a branch weight of the dependence tree. And then, we compute a maximum weight spanning tree over all the possible dependence trees and finally identify an optimal set of first-order dependencies from that tree.

Measures of Association

While the mutual information contains the average amount of uncertainty to be resolved between two dis­ tributions, the measures of association measure the strength of association between two distributions from sampling data: For applying some coincidence measures such as correlation coefficient in numerical data to quali­ tative nominal data classes, we will use some measures of association as criteria of statistical dependence. While the correlation coefficient represents the degree of linear dependence between numeric data, our classifiers out­ put non-numerical nominal data classes. Therefore, the correlation coefficient is not appropriate to identify the dependency relationship of our classifiers.

In computing measures of association in statistics, there are Cramer's Value, i.e. V, and Contigency Coeffi­ cient, i.e. CC, computed from Pearson x 2 statistic, En­ tropy symmetric measure, i.e. E·ym, from reduction in uncertainties in predicting the relationship between two classifiers, and Lambda symmetric measure, i.e. >.·ym, as an index of predictive association[Hays and Winkler, 1971]. They are non-negative real values. We think that those measures represent the degree of depencence rela­ tionship between classifiers. For expressing those mea­ sures, let N be the number of input samples, I be the number of output classes by classifier i, J be the number of output classes by classifier j, O;j or n;j be the num­ ber of observed outcomes from classifiers i and j, ni+ be L:J=l n;j, n+i be 'L:[=1 n;i , and E;j be the number of ex­ pected outcomes from classifiers i and j, that is n;+;'+i .

We can assign the values of those measures to branch weights of possible dependence tree, as in case of mutual information. To identify an optimal set of first-order dependencies using one of the measures of association is to maximize the total sum of values of measures of association used using MWST algorithm and to select a dependence tree having such maximum sum from all the possible dependence trees. Although those measures have different scales, they coincide in an optimal set of first-order dependencies in our experiment.

4.2 The use of Bayesian Formalism

With an optimal set of first-order dependencies, single confusion matrices, and pairwise joint confusion matrices, we can compute the group con­ fusion probabilities of each output class to every class at test stage. For each class M;, using Bayesian theorem and an optimal set of first-order dependencies, P(C) = Ilf= 1 P(CjJC;(i)), have we

From the above expression, if we remove constant terms,

with 11 as a constant that ensures that 2::~1 Bel(M;) = 1. If a classifier C;cn is null, a classifier Ci is the root node of dependence tree. In this case, P(:x E M;ICi(:x) = Mi, C;cn(:x) = M;cn) is approximated by P(:x E M;JCi = Mj)· Finally, depending on those Bel(M;) values, we can classify :x into a class accord­ ing to the decision rule E(:x) given below:

5 Analysis of Some Empirical Results

An Base-type Multiple Classifier System (MCS) con­ sists of only original three classifiers (see Figure 2). For demonstrating the effects of highly dependent classifiers to combining multiple decisions, we have built a number of MCSs by adding the highly dependent classifier to the Base-type MCS by faking one of its component classi­ fiers. For example, "St80ut faker!' MCS consists of orig­ inal three classifiers and the one created by faking St80ut classifier. We apply them to totally unconstrained on­ line numerals and the English alphabet recognition.

Besides voting methods with absolute majority princi­ ple and simple majority principle, some of social choice functions are implemented[Hwang and Lin, 1987]. Social choice functions include Condorcet function, Borda func­ tion, and Nanson function (also called by Borda elimina­ tion method with the lowest Borda score). These func­ tions have been widely used to choose the winner based on group consensus from ranking decisions of alterna­ tives in the area of group decision support systems.

No training stage is required for applying voting meth­ ods and some of social choice functions, but it is needed for applying BKS method and some methods in Bayesian formalism. With training data, we use 4088 items of numerals written by 13 writers, 37 49 items of the En­ glish lowercases written by 19 writers, and 2464 items of the English uppercases written by 19 writers. And with test data, there are 988 items of numerals written by 10 writers, 1684 items of the English lowercases written by 9 writers, and 1169 items of the English uppercases written by 9 writers. The writers of the test data are dif­ ferent from those of the training data. The sign words in following tables are defined in Section 3. The sign word "?" means a rejection and contains the number of samples rejected. The recognition rates are computed in percentage from the rank of the winner matched with the input label class. The recognition rates of classifiers for test data in application problems are shown in Table 1.

From the experimental results of test numerals (see Table 1 and Table 2), the recognition rates of voting methods and social choice functions are lowered when inferior Du80ut or superior NSBOut classifiers are faked and added. The extent of degradation in recognition rates is larger when an inferior classifier is faked and added. There is hardly difference in classification per­ formance among some methods of Bayesian formalism. Although one of classifiers in Base-type MCS is faked and added, the recognition rates of BKS method are un­ changed. The recognition rates of dependency relation­ ship based decision combination methods show a little higher than those of an independence assumption based decision combination in use of Bayesian formalism, but that is not statistically significant by t-test at signifi­ cance level 0.1.

From the experimental results of test lowercases (see Table 1 and Table 3), the recognition rates of voting methods and social choice functions are lowered when in­ ferior St80ut or superior NSBOut classifiers are faked and added. The extent of degradation in recognition rates is much larger when an inferior classifier is faked and added. The recognition rates of dependency relation­ ship based decision combination methods show higher than those of an independence assumption based deci­ sion combination in use of Bayesian formalism by 0.5 - 1.4 %. The improved correctness of a Base-type MCS by the dependency relationship is statistically significant by t-test at significance level 0.05, and in case of a St80ut faked MCS, its improved correctness is significant by t­ test at significance level 0.005, and in case of a NSBOut MCS, its improved correctness is significant by t-test at significance level 0.1. We will describe one example to perform t-test in a StBOut faked MCS to verify whether the improved correctness by considering the dependency relationship is statistically significant or not . Like the case of numerals, the recognition rates of BKS method are unchanged.

• H 0 : The average correctness of dependency rela­ tionship based decision combination (i.e. Mut. Inf. Bay.) is equal or less than that of an independence assumption based decision combination (i.e. Indep. Bayes.) . (i.e. J.LD :S 0 and Dis difference)
• H a : An alternative to H O· (i .e. J.LD > 0)
• Let n be the number of writers,

where

and

• We can reject H o with 8 degrees of freedom because of T = 3.51180 > to.oo5 = 3.355. It means that the average correctness of dependency relationship based decision combination is improved with 99.5% of belief interval.

From the experimental results of test uppercases (see Table 1 and Table 4), the recognition rates of voting methods and social choice functions are a little lowered when inferior NSBOut or superior Du80ut classifiers are faked and added. The extent of degradation in recog­ nition rates is larger when an inferior classifier is faked

and added. The improved correctness of a NSBOut faked MCS by the dependency relationship is statistically sig­ nificant by t-test at significance level 0.05. and in case of a Du80ut faked MCS, its degraded correctness is in­ significant by t-test at significance level 0.1. Like the case of numerals, the recognition rates of BKS method are unchanged.

They are the straightforward instances of problems before mentioned. Therefore, it is problematic to add simply any classifiers to existing multiple classifier sys­ tem and to apply voting methods or some of social choice functions. The classification performance of BKS method is also lowered by adding classifiers.

From the analysis of some empirical results, we come to some conclusions:

• The classification performance of a Base-type MCS is almost superior to that of individual classifiers.
• Voting methods and social choice functions show similar behaviors in combining multiple decisions.
• All the combination methods in Bayesian formalism almost outperforms the other combination methods.
• Incorporating the dependency relationship into Bayesian formalism helps improving the classifica­ tion performance of a MCS, especially when the highly dependent inferior classifiers are added to it. Some empirical results for lowercase significantly support our assertion by showing statistically signif­ icant t-test results.
• It is problematic to add simply any classifiers or to combine multiple decisions without considering the dependency relationship among classifiers. Because the highly dependent inferior classifiers can degrade the classification performance of a MCS, if voting methods or some of social choice functions are used.
• The classification performance of BKS method is unchanged when one of component classifiers are faked and added.

6 Conclusion and Further Works

In order to prove the effectiveness of dependency rela­ tionship for combination of multiple decisions, and for construction of multiple classifier systems, we proposed a couple of methods for identifying an optimal set of first­ order dependencies approximated from sampling data, and a decision combination method of multiple decisions in Bayesian formalism, using the first-order dependencies identified. This research applied the proposed methods to totally unconstrained on-line numerals and the En­ glish alphabet recognition. The results suggest that the dependency relationship should be considered not only for combining multiple decisions, but also for construct­ ing multiple classifier systems.

Further studies should examine both the robust crite­ ria for identifying the dependency relationship correclty, and the good approximation method( s) for obtaining the dependency relationship of a group of classifiers with the high-order dependency relationship. These proposed ideas will play important roles in resolving the following questions: how many classifiers are chosen?, what kind of classifiers should be used?, how a subset of classifiers is selected dynamically?, and how multiple decisions are combined?

Acknowledgments

The authors wish to thank Bongkee Sin for providing the classification results of three individual classifiers St80ut, Du80ut, and NS80ut which form the basis of the experiments performed. The authors would also like to thank the anonymous reviewers for their helpful com­ ments.