In order to overcome difficulties in improving classification performance using only a single classifier, the idea of combining multiple classifiers, as an alternative, has emerged from an assumption that two heads are better than one. The main task of combining multiple classifiers in parallel is how to combine their decisions (i.e., classification results). Although many decision combination methods have been proposed for combining multiple classifiers, most of them have not focused on dependencies among classifiers. They mainly combined multiple decisions on the basis of an independence assumption. Therefore, the performance of combining multiple classifiers tends to be degraded and biased, in case of adding highly dependent classifiers. Huang and Suen proposed Behavior-Knowledge Space (BKS) method, as an advanced study, which would no longer require the independence assumption. However, it is well known that for an application of the BKS method to the combination of K classifiers, storing and estimating a (K+1) st-order probability distribution composed of a decision variable and K decisions is exponentially complex and is unmanageable in theoretical analysis even for small K. Therefore, an approximation scheme is needed.
To overcome such weaknesses and obtain robust performance, it is desirable that combining multiple classifiers be performed in a probabilistic way based on the product approximation of the (K+1)st-order probability distribution, without the independence assumption. Chow and Liu as well as Lewis proposed the approximation scheme of a high order probability distribution with a product of second-order distributions considering first-order tree dependency. In their approximation scheme, a dependency provides a theoretical basis on the identification of an optimal approximation of the high order probability distribution, using the measure of closeness proposed by Lewis. However, often we face cases in which a decision is based more than two other classifiers. In such cases, first-order dependency approximation would not be suitable to estimate the high order probability distribution properly. Therefore, in this thesis a new method is proposed to optimally approximate the (K+1)st-order probability distribution with a product of kth-order dependencies, or (k+1)st-order distributions, where 1 ≤ k ≤ K. This method extends the work of Chow and Liu to higher order dependency. An optimally approximated distribution with the product of kth-order dependencies is applied to a Bayesian formalism for combining multiple decisions in a probabilistic way.
In this thesis, a framework is proposed for combining multiple decisions based on dependence relationship among classifiers. This framework optimally identifies a product set of $k$th-order dependencies for the product approximation of the (K+1)st-order distribution from training samples using a systematic dependency-directed approach, and probabilistically combines multiple decisions by the identified product set using the Bayesian formalism. Therefore, as the decision combination methods based on the framework take weaker assumptions than the independence assumption based combination methods, and require smaller storage needs and computational complexity than the BKS method. Furthermore, the decision combination methods cope with the higher order dependency in a systematic way. These are the advantages of the proposed framework. A new algorithm for an optimal product set of second-order dependencies was devised in the framework. This algorithm can be easily expanded and adapted to kth- order dependency.
For demonstrating the superior performance of the framework, some experiments on the recognition of handwritten numerals collected from KAIST and a standardized CENPARMI data base respectively, and English characters collected from KAIST, were conducted using multiple classifiers. Various sets of multiple classifiers were constructed in each application domain and evaluated by the various decision combination methods. That is, the dependency-based decision combination methods in the framework were compared with the previous methods such as majority voting, Borda count method, the BKS method, and the independence assumption based Bayesian method. The experimental results showed that the forced recognition rates of the dependency-based decision combination methods were superior to those of the previous methods. Particularly, the performance considered the dependency outperformed others in recognition accuracy, when the highly dependent classifiers were added.
단 하나의 인식기만을 사용하여 인식 성능을 향상시키는데 있어서 어려움을 극복 하기 위하여, 대안으로서 다수 인식기를 결합하는 아이디어가 둘이 하나 보다 더 낳다는 가정을 바탕으로 등장하였다. 다수 인식기를 동시에 결합하는 것의 주요한 작업은 그들의 인식 결과인 결정을 어떻게 결합하는가이다. 다수 인식기를 결합 하기 위하여 많은 결정 결합 방법론이 제안되었지만, 대부분은 인식기 간의 의존 관계에 초점을 두지 않고,주로 독립 가정을 기반으로 다수 결정을 결합하였다. 그러므로, 다수 인식기 결합의 성능은 매우 의존적인 인식기가 추가되는 경우에 저하되거나 편향되는 경향이 있다. 이에 개선된 방법으로, Huang과 Suen은 독립 가정을 필요로 하지 않는 Behavior-Knowledge Space (BKS) 방법을 제안하였다. 그러나, K개 인식기의 결합에 이 BKS 방법을 적용하기 위하여 한 결정 변수와 K개 인식기 결정으로 구성된 (K+1)차 확률 분포를 저장하고 계산하는 것은 작은 K에도 불구하고, 이론적인 분석에서 기하학적으로 복잡하고 관리할 수 없다는 것이 잘 알려져 있다. 그러므로, 근사하는 방법이 필요하다.
이러한 단점을 극복하고 강한 성능을 얻기 위하여,다수 인식기 결합이 독립 가정 없이,(K+1)차 확률분포의 곱근사에 기반한 확률적인 방법으로 수행된다는 것은 바람직하다. Lewis는 물론, Chow와 Liu도 고차 확률 분포를, 1차 트리 의존관계를 고려한 2차 분포의 곱으로 근사하는 방법을 제안하였다. 이 근사 방법에서, 의존 관계는 Lewis가 제안한 친밀도(measure of closeness)를 사용하여 고차 확률분포의 최적인 근사를 결정하는데 있어서 이론적인 근거를 제공한다. 그러나, 실제로는 한 결정이 둘 이상의 다른 인식기에 기초하는 경우가 자주 발생한다. 이러한 경우에, 1차 의존관계에 의한 근사 방법은 고차 확률 분포를 근사하는데 적절하지 않게된다. 따라서,본 논문에서는 (K+1)차 확률분포를 k차 의존관계,또는 (k+1)차분포의 곱으로(1 ≤ k ≤ K),최적으로 근사하는 새로운 방법이 제안된다. 이 방법은 Chow와 Liu의 연구 결과를 고차 의존관계 까지 확장한 것 이다. k차 의존관계의 곱으로 최적으로 근사된 분포는 확률적인 방법으로 다수 결정을 결합하기 위하여 베이지안 방법론에 적용된다.
본 논문에서는 인식기 간의 의존 관계를 기반으로 다수 결정을 결합하기 위한 방법론이 제안된다. 이 방법론은 체계적인 의존관계 지향적 방법을 사용하여 훈련 데이타로부터 (K+1)차 분포의 곱 집합을 최적으로 결정하고, 결정된 곱 집합에 의하여 다수 결정을, 베이지안 방법론을 사용하여 확률적으로 결합한다. 그러므로,이 방법론에 기반한 결정 결합 방법은 독립 가정을 기반한 결합 방법 보다 더 약한 가정을 취하므로써 독립 가정에 의한 문제점을 극복하고,BKS방법 보다는 더 작은 저장량과 계산 복잡도를 요구한다. 아울러, 체계적인 방법으로 고차 의존관계를 다룰 수 있게 된다. 이러한 점들이 제안된 방법론의 장점이다. 이 방법론을 위하여 2차 의존관계에 의한 최적인 곱 근사를 결정하는 알고리즘을 제안하였으며, 이 알고리즘은 k차 의존관계에 대해서도 쉽게 확장, 적용할 수 있다.
제안된 방법론의 우수한 성능을 보여주기 위하여,각각 KAIST와 표준 CENPARMI 데이타베이스로부터 수집한 필기 숫자의 인식, 그리고 KAIST에서 수집한 영문 문자 인식에 관한 실험을, 다수 인식기를 사용하여 실행하였다. 다양한 다수 인식기 집합이 각 응용영역에서 만들어지고,다양한 결정 결합 방법에 의하여 평가되었다. 즉, 제안된 방법론에 있는 의존관계 기반의 결정 결합 방법이 다수 투표 방법, Borda 카운트 방법,BKS 방법,독립 가정을 기반한 베이지안 방법 등과 같은 기존의 방법들과 비교되었다. 실험한 결과는 의존관계 기반의 결정 결합 방법의 인식률 성능이 기존의 것 보다 더 우수함을 보여 주었다. 특히, 매우 의존적인 인식기가 추가되는 경우에, 의존관계를 고려한 성능이 인식 정확도에 있어서 다른 것 보다 더 우수하였다.
