Adaptive Error-Correcting Output Codes

1 Introduction

In machine learning and pattern recognition research, many issues can be formulated as multi-class learning problems. To address these problems, numerous approaches have been proposed, such as error-correcting output codes (ECOC) [Dietterich and Bakiri, 1995], boosting [Schapire, 1999] and random forests [Breiman, 2001]. Among others, ECOC represent a successful framework to combine a set of binary classifiers. Due to their simplicity and efficiency, ECOC methods have been widely used to face verification [Kittler et al., 2001], text recognition [Ghani, 2001], and digits classification [Zhou and Suen, 2005].

The ECOC framework includes two steps: coding and decoding. The coding strategies include one-versus-all [Nilsson, 1965], one-versus-one [Hastie and Tibshirani, 1998], discriminant ECOC (DECOC) [Pujol et al., 2006], ECOCoptimizing node embedding (ECOCONE) [Escalera and Pujol, 2006], and so on. Among them, one-versus-all and one-versus-one are problem-independent ECOC coding design strategies, whilst DECOC and ECOCONE are problemdependent. The commonly used decoding strategies are Hamming decoding [Nilsson, 1965] and Euclidean decoding [Hastie and Tibshirani, 1998]. Some researchers have introduced loss-based function [Allwein et al., 2000] or probabilities [Passerini et al., 2004; Dekel and Singer, 2002] in decoding. Recently, Escalera et al. [Escalera et al., 2010] proposed two novel ternary ECOC decoding strategies, β-density decoding and loss-weighted decoding, and showed their advantages over state-of-the-art decoding strategies. To the best of our knowledge, however, there is no work that attempts to integrate representation learning into the ECOC framework. That is, all the existing approaches train the binary classifiers in the original data space and combine them based on the applied decoding strategy, but no one aims to explore the intrinsic geometric structure of the data. Alternatively, learning intrinsic representation of high dimensional data may significantly benefit the classification accuracy.

To learn intrinsic representations of data, many dimensionality reduction approaches have been developed, under the assumption that the observed data reside on a low dimensional subspace or sub-manifold embedded in the original space. Traditional linear dimensionality reduction methods, such as principal components analysis (PCA) [Jolliffe, 1986] and linear discriminant analysis (LDA) [Fisher, 1936], have been widely used for finding a linear subspace of the data. However, they may fail to discover the intrinsic low dimensional structure when data lie on a nonlinear manifold. The kernel extension of linear dimensionality reduction methods usually work well on complex data, but seriously suffer from the high computational complexity problem on large scale data sets. Since the publication of two seminal manifold learning algorithms, isometric feature mapping (Isomap) [Tenenbaum et al., 2000] and locally linear embedding (LLE) [Roweis and Saul, 2000], a plenty of nonlinear manifold learning methods have been proposed. However, most of them are unsupervised and cannot deal with the out-of-sample problem easily [Bengio et al., 2003].

To combine the idea of representation learning and ECOC, we present an adaptive ECOC model in this paper. We consider the training of each binary classifier in the ECOC framework as a task, and reformulate the ECOC problem as a multiple correlated tasks learning problem. Furthermore, we learn a common subspace for all the data belonging to different classes, and perform classification of the learned binary classifiers in this subspace. Hence, our model simultaneously learns the informative representation of the data and the effective binary classifiers. More importantly, it builds a bridge between the ECOC framework and multi-task learning for the multi-class learning problems. Although the formulated model is not jointly convex with respect to the projection matrix and classifiers, a gradient descent optimization procedure with curvilinear search can be used to solve it, which is efficient and can deliver satisfactory classification results.

The rest of this paper is organized as follows: We introduce the ECOC framework in Section 2, and present the formulation and optimization of our model in Section 3. Experimental results on datasets from UCI machine learning repository and handwritten digits recognition are shown in Section 4. In Section 5, we conclude this paper with remarks.

2 Error-correcting output codes (ECOC)

In this section, we introduce the notation used in this paper at first, and then give a brief introduction to the ECOC framework.

2.1 Notation

We use boldface uppercase letters, such as A, to denote matrices, and boldface lowercase letters, such as z, to denote vectors. The ith row and jth column of a matrix A are defined as Ai∗ and A∗j, respectively. Aij denotes the element of A at the ith row and jth column. zi is the ith element of a vector z. We use AT to denote the transpose of A, and tr to denote the trace of A. |Acl| is the absolute value of Acl, and ‖A‖F is the Frobenius norm of A.

For ECOC based models, we use M ∈ {-1, 0, 1}C×L to denote the ECOC matrix, where L is the length of codewords. The ith row of M, Mi∗, presents the codeword of class i. And meantime, the columns of M present the partition of the classes, where a symbol '0' means no need to take into account the corresponding class during training the binary classifier. Consequently, each of the L base classifiers will be constructed according to the corresponding column of M. If Mcl = 1 (or -1), the samples associated with class c will be treated as the positive (or negative) class for the lth binary classifier. Mcl = 0 indicates that the samples associated with class c will not be used for constructing the lth classifier. We use wl and bl to denote the coefficients and the bias of the lth linear binary classifier. We define W = {w1, w2, . . . , wL}, and b = {b1, b2, . . . , bL}.

For multi-class classification problems, we are often given a set of samples {{Xi, yi} ∈ ℜD × ℜ1 , i = 1, 2, . . . ,N}, where yi ∈ {1, 2, . . . , C}, C is the number of classes and N is the number of samples. In this work, we consider the training of each binary classifier as a learning task, and denote Xl as the training data for task l, l = 1, 2, . . . ,L. Furthermore, we use yl to denote the class labels for the data in task l.

2.2 The ECOC framework

As mentioned above, the ECOC framework include two steps: coding and decoding. In the coding step, an ECOC matrix, M, is defined or learned from data. And then, the binary classifiers are trained according to the partition of the classes in each column of M. In the decoding step, all the test data are fed in the binary classifiers, and each classifier provides a unique vote as positive class or negative class. One decoding strategy, such as Hamming distance or lost-based decoding, can be used to decide to which class the test datum should belong.

Even though having been widely used in many applications, the ECOC framework suffers from two critical problems: the base classifiers are trained independently, that is, the binary classifiers cannot get help from each other; and the training is performed in the original space, and doesn't try to explore the intrinsic structure of the data. To address these two problems, in this paper, we present an adaptive ECOC model.

3 Adaptive ECOC (AECOC)

In this section, we introduce our model, AECOC, in detail, including its formulation, optimization and decoding. Further, we discuss the relationship between AECOC and existing multi-task learning approaches, and present the differences between them.

3.1 Formulation

Here, we assume all the data have a low-dimensional subspace representation. For the l-th task, the linear predictive function is derived from the subspace as follows

where wl ∈ ℜd is the linear weight vector, bl ∈ ℜ is the bias parameter, A ∈ ℜD×d is the linear transformation matrix that projects the input data onto the low-dimensional subspace, and d is the dimensionality of the subspace. The transformation matrix, A, has orthogonal columns such that A⊤A = I, where I is an identity matrix. To jointly learn the binary classifiers and the low dimensional representation of data, we conduct training by minimizing the following regularized loss function over the model parameters {A,wl, bl| l = 1, . . . ,L},

subject to the constraints A⊤A = I. Here, L(·, ·) is a general loss function, Reg(A) is a regularization term with respect to A, {αl}, 1 = 1, . . . , L and γ are tradeoff parameters. By conducting multi-task training, we expect the subspace representations can both capture the task specific discriminative information and benefit the learning of each binary classifiers.

In this work, we consider a least square loss function and a trace regularization, i.e.,

Here, the reason for that we use the trace regularization is to learn the intrinsic representation automatically from data.

Hence we get the following optimization problem

Below we show that the optimal wl, bl can be solved in terms of A from the optimization problem.

Lemma 1 The optimal {w∗ l , b∗l }Ll=1 that solve the optimization problem in Eq. (5) is given by

and

for l = 1, . . . , L, where H = I1 Nl 11⊤, 1 denotes a column vector of length Nl with all ones and Nl is the number of training data in task l.

Proof: Taking the derivatives of the objective function in Eq. (5) with respect to bl, and setting it to zero, we obtain

for l = 1, . . . , L. Substituting it back into Eq. (5), we have a new objective function as below

Then taking derivatives of this new objective function with respect to wl, and setting it to zeros, we obtain

Following Lemma 1, the objective function in Eq. (5) can be rewritten as below by replacing {wl, bl}

whereMl and zl are defined as

and

Hence the optimization problem in Eq. (5) can be equivalently re-expressed asmin

The problem above is a non-convex optimization problem. Nevertheless, the gradient of the objective function with respect to A can be easily computed, and it is

3.2 Optimization

The non-convex optimization problem (14) is generally difficult to optimize due to the orthogonal constraints. In this work, we use a gradient descent optimization procedure with curvilinear search [Wen and Yin, 2010] to solve it for a local optimal solution.

In each iteration of the gradient descent procedure, given the current feasible point A, the gradients can be computed using (15), such thatG=∇AL1(A). (16)

We then compute two skew-symmetric matrices

It is easy to see F⊤ = -F. The next new point can be searched as a curvilinear function of a step size variable τ, such as

It is easy to verify that Q(τ)⊤Q(τ) = I for all τ ∈ ℜ. Thus we can stay in the feasible region along the curve defined by τ. Moreover, d dτ Q(0) is equal to the projections of (-G) onto the tangent space Q = {A : A⊤A = I} at the current point A. Hence Q(τ)τ≥0 is a descent path in the close neighborhood of the current point. We thus apply a similar strategy as the standard backtracking line search to find a proper step size τ using curvilinear search, while guaranteeing the iterations to converge to a stationary point. We determine a proper step size τ based on the well-known BarzilaiBorwein (BB) step size [Barzilai and Borwein, 1988].

3.3 Decoding

After the optimization of A, we can obtain the binary classifiers based on Lemma 1. Specifically, given an unseen test datum, ˆx ∈ ℜD , we compute the prediction values using the binary classifiers as below

and output the predicted label sign(fl(ˆx)), where sign(·) is the signum function. Following this, any ECOC decoding strategy can be applied to obtain the predicted label of ˆx.

3.4 Kernel AECOC

So far we have only considered the linear case for AECOC. In this section, we will apply the kernel trick to provide a nonlinear extension of the algorithm presented above. The optimization problem for the kernel extension is essentially the same as problem (5), with the only difference being that the data point x is mapped to φ(x) in a reproducing kernel Hilbert space, where φ(·) denotes the feature map. Then the corresponding kernel function K(·, ·) satisfies K(x1, x2) = φ(x1)T φ(x2).

Suppose the p-th column of the projection matrix A in the reproducing kernel Hilbert space can be written as A∗p = ∑Ni=1 ωp i φ(xi). According to the representer theorem, we have φ(X)A = KΩ, where Ω = {ω1 , . . . , ωd } and d is the dimensionality of a low dimensional subspace of the reproducing kernel Hilbert space. Note that, since the dimensionality of the reproducing kernel Hilbert space may be infinity, the trace regularization needs to be changed to other regularization term, such as γΩT KLKΩ, where L is the so called graph Laplacian. However, for other optimization procedures, they are quite similar to that in the linear case. Hence, we omit the details here.

3.5 Relationship with existing multi-task learning approaches

In literature, several methods have been proposed for the multi-task learning problems. Some methods work on the assumption that task parameters lie in a low dimensional subspace, such that common features for all tasks are learned under a regularization framework [Argyriou et al., 2008; Liu et al., 2009]. Some other methods work on the assumption that tasks are clustered and parameters of tasks within a cluster lie close to each other, such that relationship between tasks are studied [Thrun and O'Sullivan, 1996; Xue et al., 2007; Kumar and III, 2012]. There also exist probabilistic models which attempt to learn full task covariance matrix and use it to learn the predictor functions [Zhang and Yeung, 2010].

In this paper, we propose an adaptive generalization of the ECOC framework, to deal with multi-class learning problems. Even though the formulation of our AECOC model is similar to previous multi-task learning approaches, the motivation and optimization of AECOC are both distinct from existing multi-task learning approaches. On one hand, we reformulate the ECOC model from the perspective of multi-task learning, which builds a bridge between the ECOC framework and multi-task learning models. On the other hand, we introduce a gradient descent optimization procedure with curvilinear search [Wen and Yin, 2010] to optimize the AECOC model, which is efficient and can deliver satisfactory results.

4 Experiments

To demonstrate the effectiveness and efficiency of our proposed model, AECOC, we compared it with some related works on 14 data sets from UCI machine learning repository 1 , and the USPS handwritten digits recognition application 2 . The details of the UCI data sets are shown in Table 1. The USPS data set includes 9298 samples from 10

1 http://archive.ics.uci.edu/ml/

2 http://www.cs.nyu.edu/∼roweis/data.html

classes of handwritten digits. The dimensionality of the data is 256. The compared methods include four state-of-the-all ECOC approaches, four classic dimensionality reduction approaches, one multi-task learning approach and one deep neural network model. For all the data sets, the features were normalized within [0, 1]. The average classification accuracy and standard deviation based on 5-fold cross validation are reported. In the following, we show the experimental results in detail.

4.1 Comparison to state-of-the-art ECOC approaches

In this experiment, we compared AECOC with four ECOC coding design methods. They are one-versus-one (OneVsOne) [Hastie and Tibshirani, 1998], one-versusall (OneVsAll) [Nilsson, 1965], discriminant ECOC (DECOC) [Pujol et al., 2006], and ECOC-optimizing node embedding (ECOCONE) [Escalera and Pujol, 2006]. Here, OneVsOne and OneVsAll are two problem-independent ECOC design strategies, while DECOC and ECOCONE are both problem-dependent design methods. Although any ECOC coding strategy can be used to formulate the AECOC model, for simplicity, we employed the OneVsOne coding design in this experiment. As mentioned in previous section, the training of each binary classifier was considered as a task, and all the tasks are correlated in the AECOC framework. For all the methods including AECOC, we used linear least square support vector machine (LSSVM) as base classifiers. The linear loss-weighted (LLW) decoding strategy [Escalera et al., 2010] was used for all the coding designs. Following the parameter settings of [Escalera et al., 2010], the regularization parameters, α, for all the compared ECOC methods were empirically tested and set to 12 . For AECOC, γ was set to 1, and αi's, i = 1, 2, . . . , L, were set to 0.1. This parameter setting might not be optimal for all the data sets. However, it's fair to use fixed parameters for all the compared methods, as weakness in the classification results will also be shared. Moreover, it's much easier for the replication of the experiments.

Table 2 shows the classification accuracies and standard deviations obtained on the UCI data sets, and the USPS data set. To evaluate the significance of the performance differences, we conducted the Friedman [Friedman, 1937; 1940] and the Nemenyi test [Nemenyi, 1963] as suggested by [Demsar, 2006], with a confidence value 0.05 on the classification results presented in Table 2. The statistical comparison results show that AECOC is significantly better than all the compared ECOC methods except for the OneVsOne coding design. However, in terms of the classification accuracy and the mean rank, we can see that AECOC improves the OneVsOne coding on most of the tested data sets.

4.2 Comparison to dimensionality reduction approaches

In this experiment, we compared AECOC with some classical dimensionality reduction methods, including principal components analysis (PCA) [Jolliffe, 1986], linear discriminant analysis (LDA), locality preserving projections (LPP) [He and Niyogi, 2003] and marginal Fisher analysis (MFA). Among them, PCA and LPP are unsupervised learning methods, while LDA and MFA are supervised methods. From the other viewpoint, PCA and LDA are global learning methods, whilst LPP and MFA are locality-based learning methods. Since the dimensionality of the LDA subspace is at most C - 1, the dimensionality of the targeted subspace for all the dimensionality reduction approaches was set to d = min{D - 1,C - 1}, where D is the dimensionality of the original data and C is the number of classes. Based on our empirical study, since LPP and MFA are localitybased dimensionality reduction approaches, 1-nearest neighbor classifier generally performs better than or comparable with ECOC methods in the learned subspace of LPP and MFA. Hence, we use 1-nearest neighbor classifier to evaluate the classification rates for all the dimensionality reduction approaches.

Table 3 shows the classification accuracies and standard deviations obtained on the UCI data sets and the USPS data set. To evaluate the significance of the performance differences, we conducted the Friedman [Friedman, 1937; 1940] and the Nemenyi test [Nemenyi, 1963] with a confidence value 0.05 on the classification results shown in Table 3. The statistical comparison results show that AECOC is significantly better than LPP, and at least comparable with other approaches. Moreover, we can see that, as the base classifiers in the AECOC model have effectively explored the distribution of the classes and each one benefits from the learned information of others, AECOC performs very well and delivers promising classification results on most of the data sets.

4.3 Comparison to multi-task learning and deep learning models

In this experiment, we compared AECOC with one state-ofthe-art multi-task learning model, called multi-task relationship learning (MTRL) [Zhang and Yeung, 2010], as well as a deep neural network model, called stacked denoising autoencoders (SDAE) [Vincent et al., 2010]. The code of MTRL can be found at the author's webpage 3 , while the deep learning toolbox is available at the GitHub website 4 . For MTRL and AECOC, we formulated both the models according to the one-versus-one ECOC coding design, where the training of each binary classifier was taken into account as a task. For SDAE, we used a four layer neural network. The numbers of units in each layer were D, D, d and C, respectively, where D, d and C are defined as same as the above subsection. The number of epoches for unsupervised pre-training and supervised fine-tuning were empirically set to 400 and 5000. Due to the high computational complexity of MTRL, we only implemented experiments on three small size UCI data sets, which include Dermatology, Iris and Wine.

Fig. 1 shows the accuracy obtained by each learning method. It is easy to see, AECOC outperforms the other two compared methods. Since the data size is small, the SDAE model cannot be trained sufficiently. Hence, it doesn't perform as well as AECOC and MTRL. Table 4 shows the training time of SDAE, MTRL and AECOC on the UCI data sets. We can see that the training of AECOC is very efficient. Basically, it has a computation cost of O(Nd2 +d3 ), where N is the number of training data and d is the dimensionality of the low dimensional subspace. This computational complexity is similar to that of SDAE, which is O(N). However, compared to those of AECOC and SDAE, both the time and space complexity of MTRL are much higher.

5 Conclusion

In this paper, we have proposed an adaptive generalization of the ECOC framework, called AECOC, for multi-class learning problems. Unlike traditional ECOC methods, in the model of AECOC, we consider the training of the binary classifiers as correlated tasks, and all the tasks are combined to solve a multi-class learning problem. Particularly, AECOC learns the base classifiers and the intrinsic representation of the data simultaneously, and builds a bridge between the ECOC framework and multi-task learning models. Extensive experiments on 14 data sets from UCI machine learning repository and the USPS handwritten digits recognition application demonstrate the superiority of AECOC over state-ofthe-art ECOC methods, dimensionality reduction methods, multi-task learning methods and deep learning methods. In future work, we will investigate the integration of the learning of ECOC coding design into the AECOC model, to further improve the performance of AECOC on multi-class learning problems.

3 http://www.comp.hkbu.edu.hk/ yuzhang/

4 https://github.com/rasmusbergpalm/DeepLearnToolbox

Acknowledgments

This work was partially supported by the Social Sciences and Humanities Research Council of Canada (SSHRC) and the Natural Sciences and Engineering Research Council of Canada (NSERC). The authors thank the reviewers for their insightful comments and constructive suggestions.