# Deep Neural Networks Classification via Binary Error-Detecting Output Codes
## 1 Introduction  
Deep learning methods play a pivotal role in the latest breakthroughs in several tasks, outperforming the previous state-of-the-art approaches. Many tasks require solving a multi-class classification problem where an input space is mapped to an output space with more than two classes (patterns). The multi-class classification problem can be decomposed into several binary classification tasks. The most common approaches are one-versus-all (OVA), one-versus-one (OVO), and error-correcting output coding (ECOC) [1, 2]. OVA reduces classifying \(K\) classes into \(K\) binary classifiers. The \(i\)-th binary classifier is trained using all the data of class \(i\) as positive examples and all the data from the other classes as negative examples [3]. An unknown example is classified to the class based on the classifier, which produces the maximal output. In the OVO approach, \(K(K\)-\(1)/2\) binary classifiers are constructed [4]. Each \(ij\)-th binary classifier uses the data from class \(i\) as positive examples and the data from class \(j\) as negative examples. An unknown example is classified to the class based on the simple voting scheme [5] using the Decision Directed Acyclic Graph [6] or probabilistic coupling method [7]. In ECOC [8], coding matrix \(M\in\{-1,1\}\) is utilized. The coding matrix has a size of \(K\times N\), where \(K\) is the number of classes (codewords), and \(N\) is the number of binary classifiers (bits of the codewords). Each row of \(M\) corresponds to one class (codewords), and each column of \(M\) is used to train a distinct binary classifier. When making inferences about an unknown example, the \(N\) binary classifiers' output is compared to the \(K\) codewords, usually using the Hamming distance. For example, a codeword with minimal distance is a class label. While OVA and OVO methods divide multi-class classificationproblems into a fixed number of binary classification problems, ECOC allows each class to be encoded as an arbitrary number of binary classification problems. Neural networks can be naturally extended to a multi-class problem using multiple binary neurons. The prevailing approach uses the one-hot (one-per-class) output encoding in combination with the softmax function. In one-hot encoding, each class is represented by a vector with a length equal to the number of categories. One-hot encoding vector for class \(i\) consists of all zeros except for the \(i\)-th component, which contains the value of 1. It is, therefore, an OVA classification scheme, although the output units share the same hidden layers [9]. The softmax function constrains all one-vs-all output nodes to sum to 1, making them interpretable as a probability distribution and helps training to converge faster. However, one-hot encoding has several limitations. The number of output neurons in the neural network is equal to the number of classes. Each output neuron requires a unique set of weights which dramatically increases the number of parameters in models. It can be computationally infeasible as the number of classes increases. Furthermore, computing softmax probabilities can be very expensive due to the large sum in the normalizing constant of softmax when the number of classes is large, e.g., tens of thousands or millions [10]. The one-hot encoding schema also assumes a flat label space, ignoring the existence of rich relationships among labels that can be exploited during the training. In large-scale datasets, the data do not span the whole label space, but lie in a low-dimensional output manifold [11]. In this paper, we propose to use binary coding (i.e., coding where an arbitrary number of zeros and ones can be used) as the target coding instead of one-hot encoding. Although our work relates to ECOC [8] in the sense of using error-correcting output coding, it differs in two ways. First, we do not use the divide and conquer approach to partition the multi-class problem into an ensemble of multiple binary classification problems [8; 12]. Instead, we train the whole codewords at the same time.