Improving Error-Correcting Output Coding Using Kernel Methods

Classification is one of the basic tasks in machine learning, which is widely applied in various realms such as image processing, voice recognition, medical diagnose, system identification and control, natural language processing, protein secondary structure (PSS) prediction, and financial risk analysis. The theory, algorithm, and application are becoming more and more significant in the artificial intelligent research domain.A lot of classification learning methods are emerging into our view, especially after the invention of Statistics Learning Theory (SLT). Recently, however, more and more research begins to focus on multi-class problems rather than binary-class ones as it did in the past. There are reasons for such phenomenon in the view of both theory and application. The research of binary-class problems has matured in theoretically, for example the development of binary class Support Vector Machines (SVMs) and the theory of boundary. The mathematical model of binary class problems is also easy to be demonstrated. In the view of application, more and more attention is paid to multi-class ones, for the reasons that in the real world a significant number of the tasks are multi-class problems, such character recognition, and Electronic Cardiograph Signal (ECG) abnormality recognition.Some of the well known binary classification learning algorithms can be extended to handle multi-class problems. Recently it becomes a general approach to combine a set of binary classifiers to solve a multi-class problem. Dietterich and Bakiri presented a typical framework of this approach, which is known as error-correcting output coding (ECOC), or output coding in short. The idea of ECOC enjoys a significant improvement in many empirical experiments.This paper presents two approaches to improve the multi-class classification accuracy by employing the idea of large margin in statistical learning theory and the kernel trick.(1) This paper modifies the cost function of ECOC based on the empirical loss and the structural loss. In the conventional ECOC framework, all the base classifiers are trained independently, and the final hypothesis is also ignored in the training process. In such framework, the training and the final hypothesis is thus inconsistent. In this paper, however, we consider all the base classifiers in a single global loss function. Suchimprovement can boost the multi-class accuracy though the learning burden becomes heavier.(2) The second modification is to weight the output of base classifiers before combining them. A global loss function is also generated, in term of these weights based on the structural loss and the empirical loss, as they are considered in support vector machines. Such modification allows us to implement nonlinear decoders by employing the kernel trick. In fact, in the conventional ECOC framework, the base classifiers, which are derived from different training sets and thus are different in significance, are considered equally. Such strategy ignores the difference between the base classifiers before decoding process. Thus weighting the base classifiers should improve the accuracy of the final hypothesis.The two approach are both derived from the idea of ECOC and STL, as a consequence they have some enjoyable properties,(1) The algorithms remain frameworks, which means we can apply various of different functions, different base classifiers and different encoding and decoding matrixes.(2) The global loss function is a convex one. A lot of new optimization techniques can be applied to solve such problems. Further more, this property can assure a global minimum.(3) Kernel methods are still applicable, which allow us chose various kernel functions according the structure of the data, and thus boost the generalizability.In order to evaluate the performance of the algorithms presented in this thesis, we conduct several experiments on the following platforms,(1) Datasets in UIC Repository.(2) RoboCup soccer game platform.(3) Object recognition using color information.The experimental results show that our algorithms can boost the prediction accuracy of multi-class classifiers in wide-range applications.