Separability of ternary codes for sparse designs of error-correcting output codes

Abstract

Error-correcting output codes (ECOC) represent a successful framework to deal with multi-class categorization problems based on combining binary classifiers. With the extension of the binary ECOC to the ternary ECOC framework, ECOC designs have been proposed in order to better adapt to distributions of the data. In order to decode ternary matrices, recent works redefined many decoding strategies that were formulated to deal with just two symbols. However, the coding step also is affected, and therefore, it requires to be reconsidered. In this paper, we present a new formulation of the ternary ECOC distance and the error-correcting capabilities in the ternary ECOC framework. Based on the new measure, we stress on how to design coding matrices preventing codification ambiguity and propose a new sparse random coding matrix with ternary distance maximization. The results on a wide set of UCI Machine Learning Repository data sets and in a real speed traffic sign categorization problem show that when the coding design satisfies the new ternary measures, significant performance improvement is obtained independently of the decoding strategy applied.

Introduction

In the literature, one can find several powerful types of binary classifiers. However, when one needs to deal with multi-class classification problems, many learning techniques fail to manage this information. Instead, it is common to construct the classifiers to distinguish between just two classes, and to combine them. In this sense, error-correcting output codes were born as a general framework to combine binary problems to address the multi-class problem. The strategy was introduced by Dietterich and Bakiri (1995). Based on the error-correcting principles (Dietterich and Bakiri, 1995) and because of its ability to correct the bias and variance errors of the base classifiers (Kong and Dietterich, 1995), ECOC has been successfully applied to a wide range of Computer Vision applications, such as face recognition (Windeatt and Ardeshir, 2003), face verification (Kittler et al., 2001), text recognition (Ghani, 2001) or manuscript digit classification (Zhou and Suen, 2005).

The ECOC technique can be broken down into two general stages: encoding and decoding. Given a set of classes, the coding stage designs a codeword¹ for each class based on different binary problems. The decoding stage makes a classification decision for a given test sample based on the value of the output code.

At the coding step, given a set of N classes to be learnt, n different bi-partitions (groups of classes) are formed, and n binary problems (dichotomizers) are trained. As a result, a codeword of length n is obtained for each class, where each bit of the code corresponds to the response of a given dichotomizer (coded by +1, −1, according to its class set membership). Arranging the codewords as rows of a matrix, we define a coding matrix M, where $M\in \{-1\text{,}1{\}}^{N\times n}$ in the binary case. The most well-known binary coding strategies are the one-versus-all strategy (Nilsson, 1965), where each class is discriminated against the rest of classes, and the dense random strategy (Allwein et al., 2002), where a random matrix M is generated maximizing the rows and columns separability in terms of the Hamming distance (Dietterich and Bakiri, 1995). In Fig. 1a, the one-versus-all ECOC design for a 4-class problem is shown. The white regions of the coding matrix M correspond to the positions coded by 1, and the black regions to −1. Thus, the codeword for class $c_1$ is $\{1\text{,}-1\text{,}-1\text{,}-1\}$. Each column j of the coding matrix codifies a binary problem learnt by its corresponding dichotomizer $h_i$. For instance, dichotomizer $h_1$ learns $c_1$ against classes $c_2\text{,}{c}_3$ and $c_4$, dichotomizer $h_2$ learns $c_2$ against classes $c_1\text{,}{c}_3$ and $c_4$, etc. An example of a dense random matrix for a 4-class problem is shown in Fig. 1c.

It was when Allwein et al. (2002) introduced a third symbol (the zero symbol) in the coding process that the coding step received special attention. This symbol increases the number of partitions of classes to be considered in a ternary ECOC framework by allowing some classes to be ignored. Then, the ternary coding matrix becomes $M\in \{-1\text{,}0\text{,}1{\}}^{N\times n}$. In this case, the symbol zero means that a particular class is not considered by a certain binary classifier. Thanks to this, strategies such as one-versus-one (Hastie and Tibshirani, 1998) and sparse random coding (Allwein et al., 2002) have been formulated in the ECOC framework. Fig. 1b shows the one-versus-one ECOC configuration for a 4-class problem. In this case, the grey positions correspond to the zero symbol. A possible sparse random matrix for a 4-class problem is shown in Fig. 1d. Recently, new improvements in the ternary ECOC coding demonstrate the suitability of the ECOC methodology to deal with multi-class classification problems (Pujol et al., 2006, Escalera et al., 2007). These recent designs use the knowledge of the problem-domain to learn relevant binary problems from ternary codes. The basic idea of these methods is to use the training data to guide the training process, and thus, to construct the coding matrix M focusing on the binary problems that better fits the decision boundaries of a given data set.

The decoding step was originally based on error-correcting principles under the assumption that the learning task can be modeled as a communication problem, in which class information is transmitted over a channel (Dietterich and Bakiri, 1995). During the decoding process, applying the n binary classifiers, a code is obtained for each data point in the test set. This code is compared to the base codewords of each class defined in the matrix M, and the data point is assigned to the class with the closest codeword. The most frequently applied decoding strategies are the Hamming (HD) (Nilsson, 1965) and the Euclidean (ED) decoding distances (Hastie and Tibshirani, 1998). With the introduction of the zero symbol, Allwein et al. (2002) showed the advantage of using a Loss-based function of the output margin of the base classifier. Recently, Escalera et al. (2008) proposed a loss-weighted strategy to decode, where a set of probabilities based on the performances of the base classifiers is used to weight the final classification decision. In Fig. 1, each ECOC codification is used to classify an input object X. The input X is tested with each dichotomizer $h_i$, obtaining an output $X_i\text{,}i\in \{1\text{,}..\text{,}n\}$. The final code $\{X_1\text{,}\dots \text{,}{X}_n\}$ of the test input X is used by a given decoding strategy to obtain the final classification decision. Note that in both, the binary and the ternary ECOC framework, the value of each position $X_j$ of the test codeword can not take the value zero since the output of each dichotomizer is $h_j\in \{-1\text{,}+1\}$, meaning the automatical increasing of distance/error.

To deal with multi-class categorization problems in the ternary ECOC framework, recent works redefined decoding strategies that were formulated to deal with just two symbols (Escalera et al., 2008, Allwein et al., 2002). However, the influence of the zero symbol to the error-correction capabilities and the design of the coding strategies have not been taken into account. In this paper, we formulate the ternary distance and the ternary error-correcting capabilities in the ternary ECOC framework. We propose a new sparse coding design based on maximizing the new ternary distance. We evaluate the methodology on a wide set of UCI Machine Learning Repository data sets and in a real Computer Vision problem: speed traffic sign categorization. The results show that when the new ternary distance is considered on sparse designs, significant performance improvement is obtained.

The paper is organized as follows: Section 2 overviews the ECOC random designs and presents a new sparse coding design based on ternary distance maximization. Section 3 presents the experimental results. Finally, Section 4 concludes the paper.