1 Introduction↩︎

Error Correcting Output Codes (ECOCs) offer an effective and flexible tool to combine individually trained binary classifiers for multiclass classification. Prior research [1], [2] has shown that ECOCs can provide high multiclass classification accuracy using simple but powerful binary classifiers (e.g., Support Vector Machines and Adaboost). On the other hand, extensive body of work has emerged in recent years showing that, when large amount of training data is available, deep learning models [3] outperform most multiclass classifiers. Still, further progress is needed for classification tasks when training data is limited or constrained, and model interpretability is preferred. In this paper, we consider the problem of ECOC-based multiclass classification, when individual binary classifiers are SVMs or deep learning models. We focus on the question of design of codebooks – along with optimality guarantees.

Importantly, our approach to codebook design is distinct from the prior literature, which approaches the problem using a continuous relaxation of the inherently discrete optimization problem, and solving the relaxed problem using nonlinear optimization tools [4]–[7]. In principle, this approach can be scaled to a large number of classes, but it does not provide any optimality guarantees. Another approach in the literature [1] casts the design problem as a propositional satisfiability problem that can be solved for using off-the-shelf SAT solvers. However, only a feasible solution may be readily computable using this approach. In contrast, we formulate the optimal codebook design problem as a large-scale Integer Program (IP), and exploit the structure of the problem to obtain a compact formulation that can be solved with modern IP solvers. Our resulting codebook has optimality guarantees. This also enables a systematic comparison with respect to several well-known fixed-size codebooks.

Our IP formulation is flexible in that it models various codebook (or coding matrix) generation criteria: (i) Sufficiently large Hamming distance between any pair of codewords (row separation); (ii) Uncorrelated columns (column separation); (iii) Relatively even distribution of data points across two classes (balanced columns); and (iv) Larger Hamming distance between pair of codewords whose corresponding classes are hard to separate from one another. These criteria are important not only for the nominal error correction performance, but also promote adversarial robustness. However, this initial formulation can quickly become intractable for a classification problem of more than 10 classes.

To address the abovementioned computational bottleneck, we exploit the inherent graph-theoretic feature of the constraints that pertain to selecting an appropriate subset of columns. In particular, we prove that the constraints modeling the pair of columns that do not satisfy column separation criterion can be replaced by a much smaller set formed by an edge clique cover of the underlying graph. This result allows us to reformulate our original problem into another IP with a substantially smaller set of constraints. A distinct advantage of our design approach is that it generates relatively small codebooks, which achieve a high nominal accuracy as well as robustness to adversarial perturbations [8]–[10]. In particular, we demonstrate that our IP-generated codebooks outperform the well-known codebooks such as one-vs-all and one-vs-one, and other dense or sparse designs. To evaluate the robustness of optimal codebooks to adversarial perturbations, we conduct experiments based on white-box attacks [11], [12]. Importantly, our codebooks achieve non-trivial robustness even without any adversarial training of the individual binary classifiers. Thus, our results suggest a strong potential of ECOCs for training robust classifiers.

The paper is organized as follows: Sec. 2 introduces the ECOC framework; Sec. 3 presents the design criteria for codebooks; Sec. 4 details our IP formulation; Sec. 5 provides computational experiments on numerous datasets; Sec. 6 outlines future work.

2 ECOCs for Classification↩︎

In the ECOC-based framework for \(k\)-class classification [1], each class is encoded with a unique codeword of length \(l\), resulting in a codebook (coding matrix) \(\mathcal{M}=(m_{ij})\) of size \({k\times l}\). For binary (resp. ternary) codes, the entries \(m_{ij}\) of the coding matrix \(\mathcal{M}\) belong to the set \(\{+1,-1\}\) (resp. \(\{+1,0, -1\}\)). The rows (resp. columns) of \(\mathcal{M}\) correspond to distinct classes (resp. binary classifiers or hypotheses). Figure 1 shows examples of two standard codebooks.

In the learning problem corresponding to every column in \(\mathcal{M}\), the set of training examples belonging to different classes \(C_1,\dots, C_k\) is partitioned into two groups: all examples from classes with entry \(+1\) represent the positive class, and all examples from classes with entry \(-1\) represent the other class. In the case of ternary codes, training examples with entry \({0}\) are not included in the training set and are considered irrelevant.

Let \(f_1(\cdot),\dots, f_l(\cdot)\) represent the learned binary hypotheses for the corresponding columns of \(\mathcal{M}\). For a learned hypothesis \(s \in \{1,\dots l\}\) and a test example \(x\), let \(f_{s_{+1}}(x)\) (resp. \(f_{s_{-1}}(x)\)) denote the output/score of the class \(+1\) (resp. class \(-1\)). Then, \[f_s(x) := \begin{cases} +1 & \text{if f_{s_{+1}}(x) > f_{s_{-1}}(x)}\\ -1 & \text{otherwise} \end{cases} \quad \forall s \in\{1,\dots,l\}.\] After evaluating \(x\) on all the \(l\) hypotheses, we obtain an encoding \(\vec{f}(x)= [ f_1(x),\dots, f_l(x)]\). To associate \(\vec{f}(x)\) with a class (i.e., a row of coding matrix \(\mathcal{M}\)), we can use a decoding scheme based on a similarity measure such as Hamming distance. Particularly, one can compute the Hamming distance \(d_H(\cdot,\cdot)\) between \(\vec{f}(x)\) and each codeword \(\mathcal{M}(r,\cdot)\) and select the class, denoted \(\hat{y}\), that corresponds to the minimum distance: \[\begin{align} &d_H(\mathcal{M}(r,\cdot), \vec{f}(x)) = \sum_{s=1}^{l} \bigg(\frac{1-\mathcal{M}(r,s) \times f_s(x)}{2} \bigg) \tag{1}\\ &\hat{y} =\; \underset{r}{\mathrm{argmin}} \;\; d_H(\mathcal{M}(r,\cdot), \vec{f}(x)). \tag{2} \end{align}\]

3 Codebook Generation Criteria↩︎

The final prediction accuracy of ECOC scheme introduced in Sec. 2 crucially depends on the error correction ability of the coding matrix \(\mathcal{M}\). To ensure low test error, the coding matrix must be chosen carefully. Below we introduce the key properties that serve as guidelines for our design of binary codes.¹

Row Separation: It is well-known that more separation between pairs of codewords (i.e., rows in the coding matrix \(\mathcal{M}\)) improves the error correction capability. Particularly, if every pair of distinct codewords has a hamming distance of at-least \(d\), then such a code can correct at-least \(\floor*{\frac{d-1}{2}}\) errors. Thus, we seek coding matrix with a high row separation between any pair of codewords.

Column Separation: Additionally, every pair of distinct columns in \(\mathcal{M}\) should be uncorrelated. The benefit of large column separation can be understood by drawing analogy with error correction in communication over a noisy channel. Encoding a signal and transmitting the codeword over a noisy channel is highly effective when the errors introduced during transmission are random. By maintaining a sufficiently large encoding, one can recover the original signal at the receiving end with high accuracy. Analogously, in our setup, if any two columns (classifiers) make errors in their predictions on the same inputs (i.e., their outputs are highly correlated), then the effectiveness of encoding in correcting errors will be reduced.

Balanced Columns: On the other hand, to prevent over-fitting of individual hypotheses, it is important to prioritize selection of columns for which the \(k\) class data points are evenly distributed across the two classes. This criterion is particularly relevant when the test examples are adversarially perturbed [13].

Data Distribution: Finally, in multi-class problems, some class pairs are more difficult to separate than others. This makes the prediction of these classes more vulnerable to adversarial attacks. Therefore, it is desirable to have larger Hamming distances among pairs of codewords corresponding to hard-to-separate class pairs. This hardness of separation can be estimated from the training data for different class pairs, either using the semantics of classes [5], or by calculating similarity measures between classes for small datasets  [6], [7], [14]–[16].

4 Integer Programming Formulation↩︎

In this section, we embed the abovementioned guidelines into a discrete optimization formulation for generating an optimal codebook.

To begin with, note that for a \(k-\)class problem a coding matrix can have at most \(({2^k} - 2)/2 = 2^{k-1} -1\) columns. However, such an exhaustive coding might be feasible only for a small \(k\) (2 to 5). As \(k\) increases, the number of binary classifiers that need to be trained for exhaustive coding increase exponentially. Practically, it is desirable to select a small subset (say of \(L\) columns) from \(2^{(k-1)}-1\) possible columns. This subset should be selected in accordance with the codebook generation criteria described in Sec. 3.

One way to formulate the column subset selection problem is to cast it as a propositional satisfiability problem, and solve it using an off-the-shelf SAT solver. For example, the authors in [1] considered the following problem for \(8\le k \le 11\): For a predefined number of columns \(L\) and some value \(\rho\), is there a solution such that the Hamming distance between any two columns is between \(\rho\) and \(L-\rho\)? However, this approach only leads to a feasible (not necessarily optimal) solution. In contrast, we present an Integer Programming (IP) problem that captures the design criteria in a more flexible manner and can be used to find an optimal codebook.

For sake of simplicity, we first consider the row and column separation criteria; the remaining criteria on balanced columns and data distribution can be addressed in our IP formulation, as discussed subsequently at end of this section. In its basic form our problem is the following: We want to find a solution which maximizes the minimum Hamming distance between any two rows (or the error-correcting property).

Let \(x_i\) denote the binary variable associated with each column \(i\) of the exhaustive code for \(i \in \{1,\dots 2^{k-1} -1\}\), i.e. the decision variable whether or not column \(i\) is selected in the final solution. Also, let \(x_{ij}\) be the binary variable which represents the outcome of AND operation between variables \(x_i\) and \(x_j\) for all distinct \(i,j\) pairs, i.e. \((i,j) \in \{1,\dots, 2^{k-1} -1\}^2| i < j\). Essentially, when \(x_{ij}=1\) means that columns \(i\) and \(j\) satisfy the column separation criterion. We can now write the IP formulation to generate an optimal codebook as follows:

In \(\mathcal{IP}1\), max-min objective can be simplified by introducing an auxiliary variable \(t\), where \(t = \min\;\; \{d_H^{1,2}(x_i),\; d_H^{1,3}(x_i),\; \dots ,\; d_H^{k-1, k}(x_i) \;\}\), and adding the corresponding constraints \(t \leq d_H^{1,2}(x_i) \;,\;t\leq d_H^{1,3}(x_i) \;,\; \dots \;, t\leq d_H^{k-1,k}(x_i)\). Eq. 3 ensures large column separation for \(x_{ij}=1\). Constraints 4 and 5 ensure that if \(x_{ij}=1\) then both columns \(i\) and \(j\) are included in the solution, i.e. \(x_i=1\) and \(x_j=1\). Conversely, Equation 6 ensures that if columns \(i\) and \(j\) are selected then \(x_{ij}=1\).

We note that in \(\mathcal{IP}1\) there are \(2^{k-1} -1 \approx \mathcal{O}(2^{k-1})\) binary variables for each column, and for each pair of columns there are \(2^{k-1} -1 \choose 2\) \(\approx \mathcal{O}(2^{2k-3})\) binary variables. Thus, the total number of binary variables are \(\mathcal{O}(2^{2k-3})\). Similarly, the total number of constraints are \(\mathcal{O}(2^{2k-1})\). For \(k=10\), this would entail solving an IP of approximately \(130,000\) variables and \(650,000\) constraints. Modern IP solvers like Gurobi and CPLEX can handle such problem instances.

However, for \(k>10\), the above optimization problem quickly becomes intractable. The main reason is that we have a binary variable \(x_{ij}\) for each pair of columns to capture the large column separation criterion; see 3 . We now propose a second formulation which does not involve a new variable for every pair of columns.

Let \(\mathcal{S}_p\) denote the set of all distinct pairs of columns in the exhaustive code \(\mathcal{M}\), i.e. \(\mathcal{S}_p = \{(i,j) \in \{1,\dots, 2^{k-1} -1\}^2 |\; i < j\}\) and \(|\mathcal{S}_p| = \binom{2^{k-1} -1}{ 2}\). We now consider two mutually disjoint subsets \(\mathcal{S}_p^{feas}\) and \(\mathcal{S}_p^{inf}\), such that \(\mathcal{S}_p = \mathcal{S}_p^{feas} \cup \mathcal{S}_p^{inf}\): the set \(\mathcal{S}_p^{feas}\) (resp. \(\mathcal{S}_p^{inf}\)) contains only those \(i,j\) pairs that satisfy (resp. do not satisfy) the column separation criterion 3 . Mathematically, we can write: \[\begin{align} {10} & \mathcal{S}_p && = \Big\{(i,j) \in \{1,\dots, 2^{k-1} -1\}^2 |\; i < j \Big \},\\ & \mathcal{S}_p^{feas} && = \Big\{(i,j) \in \{1,\dots, 2^{k-1} -1\}^2 |\; i < j \text{ and} \notag\\ & && \quad \quad \rho \leq d_H\big(\mathcal{M}(\cdot,i),\mathcal{M}(\cdot,j)\big)\leq (L-\rho) \Big \}, \\ & \mathcal{S}_p^{inf} && = \mathcal{S}_p \setminus \mathcal{S}_p^{feas}. \end{align}\] In this new representation, the constraint 3 is captured by the construction of \(\mathcal{S}_p^{feas}\), which eliminates the need of variables \(x_{ij}\) for column pairs. Similarly, we no longer need the constraints 4 , 5 and 6 . Now, for any \((i,j)\) pair of columns in the set \(\mathcal{S}_p^{inf}\), at-most one of the columns can be included in the final solution. This can be achieved by setting \(x_{ij} =0\) in 6 . Equivalently, for every \((i,j)\) pair in \(\mathcal{S}_p^{inf}\), it is sufficient to impose the constraint \(x_i + x_j -1 \leq 0\).

We can now write \(\mathcal{IP}1\) as the following equivalent form: \[\begin{align} {10} \boldsymbol{ \mathcal{IP}2:}& \max_{x_i} \; \min\;\; \{ && d_H^{1,2}(x_i),\dots , d_H^{k-1, k}(x_i) \;\} \notag\\ \text{s.t.} & \sum_{i=1}^{2^{k-1} -1 }x_i \leq && L \notag \\ & x_i + x_j \leq 1 \hphantom{\text{}} && \hphantom{MMM}\forall\; (i,j) \in \mathcal{S}_{p}^{inf} \label{ip2:inf}\\ & d_H^{s,t}(x_i) = &&\sum_{i=1}^{2^{k-1} -1}\Big( \frac{1- \mathcal{M}(s,\cdot) \times \mathcal{M}(t,\cdot)}{2} \Big)x_i \notag \\ & \hphantom{} && \hphantom{MMM} \forall\; (s,t) \in \{1, \dots, k \}^2 |\; s < t \notag\\ & x_i \in \{0, 1 \} && \hphantom{MMM} \forall\; i \in \{1, \dots, 2^{k-1} -1 \} \notag \end{align}\tag{7}\]

Since \(\mathcal{IP}2\) does not contain any \(x_{ij}\) variables, this formulation has significantly less number of variables and constraints in comparison to (\(\mathcal{IP}1\)). The computational complexity of \(\mathcal{IP}2\) is mainly governed by the size of \(\mathcal{S}_{p}^{inf}\), which determines the number of constraints in 7 . However, even in this new representation, the size of the set \(\mathcal{S}_{p}^{inf}\) becomes prohibitively large as \(k\) increases. Table [tbl:tab:constr], column 4 shows how quickly \(|\mathcal{S}_p^{inf}|\) increases with \(k\) for an appropriately chosen \(\rho\).

Fortunately, the constraints 7 for the set \(\mathcal{S}_p^{inf}\) can be represented on a graph \(\mathcal{G}_p^{inf}\), in which each node corresponds to a column \(x_i\) and each constraint \(x_i + x_j \le 1\) corresponds to an edge between the node \(i\) and node \(j\); see Figure 2 for an illustration.

In fact, the above graphical interpretation leads to a reduction in the number of constraints involving \((i,j)\) column pairs in the set \(\mathcal{S}_p^{inf}\). Before presenting this result, we recall that a clique is a set of nodes in a graph such that there is an edge between any two distinct nodes of this set. Proofs of all results are provided in the supplementary material.

From theorem 1, we obtain that for a clique of size \(n\), \(n(n-1)/2\) constraints of form \(x_i + x_j \leq 1\) between all \((i,j)\) node pairs in the clique can be substituted with a single constraint ?? . This constraint captures the requirement that out of all the columns in \(\mathcal{M}\) forming a clique, at most one can be present in a feasible solution. Before introducing our next result, we recall the following useful definition.

A given graph can have many possible edge clique covers; see for example Fig. 3. To reduce the size of the constraint set \(\mathcal{S}_p^{inf}\) as much as possible, we would need to find an edge clique cover of the smallest size. However, the minimum edge cover problem is known to be NP-hard [20]. Fortunately, several heuristics have been proposed to [17]–[19], [21] find edge clique cover of a graph, and they have been very effective in many practical applications. The heuristic [17] is particularly well-suited for large graphs – in practice, it shows a linear runtime in the number of edges. We therefore use this heuristic for our analysis.

We can further extend Collorary 1 to generate edge-clique-covers of very large graphs in a distributed manner using the following result:

Finally, using corollary 1 (or its extension lemma 1) we can reduce \(\mathcal{IP}2\) to the following integer program:

Finally, the last two criteria mentioned in Sec. 3 can be easily incorporated in \(\mathcal{IP}3\). Specifically, the requirement for balanced columns can be incorporated by setting the \(x_i\)’s violating this criterion to \(0\) in \(\mathcal{IP}3\). Equivalently, since each \(x_i \in \{0,1\}\) corresponds to whether a column is selected from the exhaustive code \(\mathcal{M}\), we can simply reduce \(\mathcal{M}\) by removing the unbalanced columns and then form \(\mathcal{IP}3\). In contrast to [6], in our formulation, the requirement for balanced columns further reduces the final problem size and complexity.

The remaining criterion of data distribution can be also incorporated by modifying the objective function. Previous works such as [5]–[7], pre-compute a similarity measure between every pair of classes (from training data) and use this computation to estimate the desirable class-pairwise hamming distances \(\hat{d}_{p,q}\). Finally, they optimize to obtain codebooks which attain these distance values. This can be easily incorporated in our formulation by changing the objective function 8 in \(\mathcal{IP}3\) to the following: \[\displaystyle \min_{x_i} \; \sum_{ (p,q) \in \{1, \dots, k\}^2| p < q} | d_H^{p, q}(x_i)- \hat{d}_{p,q}|. \label{ip3:new95obj}\tag{10}\]

5 Experiments↩︎

We run all our experiments on a system with a single 1080Ti Nvidia GPU, Intel Core i7-6800K CPU and 128 GB RAM. We use Gurobi as our IP solver.

Our computational experiments focus on solving \(\mathcal{IP}3\) which uses the edge-clique-cover approach to reduce the constraint set \(\mathcal{S}_p^{inf}\). Table [tbl:tab:constr] shows the reduction in size of set \(\mathcal{S}_p^{inf}\) as the number of classes \(k\) increases. Notably, for \(k \ge 15\) we achieve a reduction of more than two orders of magnitude, which demonstrates the advantage of using our approach. The last row shows the performance of generating the edge-cover on two different subgraphs obtained after partitioning the original graph, thus validating the lemma 1.

Thanks to the reduced constraint set, we can solve \(\mathcal{IP}3\) and obtain the optimality gap for different instances as shown in Table 2. \(f_{best}\) denotes the objective function value of the best solution and “Best Bound” denotes the best upper bound found by Gurobi. We obtain an optimal solution or a relatively small optimality gap. Thus, our formulation is tight and enables Gurobi to terminate quickly without exploring a large branch-and-bound tree. These results demonstrate our approach to codebook design indeed provides low optimality gaps.

We now evaluate the classification performance of our IP-generated codebooks in both natural and adversarial settings. We compare performance against various standard codebooks: 1-vs-all [22] and 1-vs-1 as well as Sparse and Dense codes generated using the procedure outlined in [2].²

5.1 Natural Classification Performance↩︎

Toy Dataset (2d): We generate a synthetic dataset of \(10\) classes where points in each class are sampled from a 2d Gaussian distribution. Here we use SVMs with Rbf kernels as our binary classifier for individual hypotheses in all our codebooks. Figure  5 shows the decision boundaries of all hypotheses for three codebooks along with the training set. The prediction accuracy on the test set is reported in Table 3. Our \(\mathcal{IP}3\) generated codebook easily outperforms other codebooks, and almost matches the accuracy of 1-vs-1. Note that this codebook only used \(L=20\) columns while 1-vs-1 used \(L=45\) columns. This highlights the benefit of ECOC theory: high accuracy can be achieved with a carefully chosen compact code-book.

Real-world Datasets (Small/Medium): We evaluate the performance of different codebooks on small to medium sized, real-world datasets. We consider Glass, Ecoli and Yeast datasets taken from UCI repository [23]. Details such as the number of samples, features and classes for each dataset are provided in the supplementary material. For Dense, Sparse, and IP generated codebook we set \(L = 2k\). We again use SVMs with Rbf kernel as the binary classifier for training different hypotheses in our IP-generated and other codebooks. We set aside 30% of the samples as our test set and used them to evaluate the performance of different codebooks. The final test set accuracies are reported in Table 4. Our codebook provides best accuracy on Ecoli and second-best accuracy on Glass and Yeast, thus providing best performance on an average.

We now evaluate the performance of different codebooks on real-world image datasets: MNIST and CIFAR10.

MNIST: We run two set of experiments: In the first set, we use SVMs (with both Linear and Rbf kernel) on PCA-transformed MNIST dataset (using 25 principal components). In the second set, we use binary Convolutional Neural Networks CNNs to train different hypotheses in our codebooks. Tables 5 and 6 provide the the test set accuracy of different codebooks from both sets of experiments.

We observe that in the case of Linear kernel our \(\mathcal{IP}3\) codebook outperforms all other codebooks except for 1-vs-1, which achieves relatively higher accuracy of around 92%. This is due to fact that the individual hypotheses of different codebooks (except 1-vs-1 ) are solving much harder problems with highly non-linear decision boundaries. On the contrary, 1-vs-1 solves only natural classification problems, where a linear separator can be expected do well. In using non-linear Rbf-kernel, both \(\mathcal{IP}3\) codebook and 1-vs-1 codebook achieve similar accuracy. On the other hand, when using CNNs our \(\mathcal{IP}3\) codebook provides best performance, indicating the benefit of using powerful binary classifiers in our ECOC approach.

CIFAR10: Since running SVMs on this dataset is expensive computationally, we resort to CNNs here. In particular, we use ResNet18 [24] as our binary classifier to train the individual hypotheses in different codebooks. As shown in Table 7, \(\mathcal{IP}3\) achieves the best performance. Note that our experiments on CIFAR10 should be viewed only in terms of evaluating the relative performance of different codebooks. We are aware that modern multi-output CNNs have achieved an accuracy of around 95% (or higher) on CIFAR10 dataset. However, recall that in this work our goal is to highlight the benefit of using ECOCs when working with binary classifiers.

5.2 Adversarial Robustness↩︎

We now evaluate the robustness of different codebooks against white-box attacks.³ For further comparison, we also evaluate the robustness of a naturally trained multiclass CNN with our IP-generated codebook in the final layer – this is somewhat similar to the recent approach in [25].⁴ However, note that all our binary hypotheses are naturally trained, i.e. without any adversarial training. We first discuss how to obtain the class probability estimates that are necessary to evaluate the adversarial robustness.

Recall from Sec. 2 the procedure of assigning a class to an input \(x\) using Hamming decoding. However, this decoding scheme in itself does not provide us with class probability estimates, which are essential for evaluating the robustness of an ECOC-based classifier with respect to white-box attacks [9], [11]. Particularly, we need probability estimates to compute the adversarial loss function. Furthermore, we need to be able to compute the gradients of the loss-function with respect to input \(x\). We adopt the procedure of calculating the class probability estimates for general codebooks, as proposed in [26], [27]. After evaluating an input \(x\) on each binary classifier, we obtain a probability estimate (or score⁵), denoted \(r_l(x)\), for each column \(l\) (i.e., binary classifier) in \(\mathcal{M}\). Let \(I\) denote the set of classes for which \(\mathcal{M}(\cdot,l) =1\) and \(J\) denote the set of classes for which \(\mathcal{M}(\cdot,l)=-1\). Then the class probability estimate for \(i \in \{1,\dots k\}\) on an input \(x\) is given as follows:

where differentiability with respect to \(x\) is maintained.

Using these estimates, we can compute a loss function (e.g, cross-entropy Loss) and then generate white-box PGD-attacks [11] to evaluate the robustness of the overall classifier. Note that we use the same differentiable class scores (or decoding scheme) for both prediction and to generate a white-box attack in order to prevent gradient-obfuscation [12], [28]. For all our experiments, we work with perturbations based on \(l_{\infty}\)-norm. In particular, for a given input \(x'\), the allowed set of perturbations are given by set:

MNIST: We run an \(l_{\infty}\)-norm based 100-step PGD attack with multiple values of \(\epsilon\) on different codebooks; Table 8 summarizes these results. In terms of the overall performance, our \(\mathcal{IP}3\)-generated codebook significantly outperforms all other codebooks except the Dense codebook. In this codebook, different pairs of codewords have different hamming distances, ranging from 8-14. On the other hand, in \(\mathcal{IP}3\), all codeword pairs have identical hamming distance of 10 as result of the max-min objective function 8 . This disparity in performance can therefore be mitigated by incorporating the underlying data distribution (via class pair similarity measures) using the objective function 10 . However, note that efficiently computing similarity measures for large image datasets is in itself a research problem. Finally, as we discuss in the next set of experiments, the performance of Dense codebook deteriorates as the data-distribution changes.

CIFAR10: Finally, we evaluate the robustness of different codebooks on CIFAR10 by running 30-step PGD attack; see table 9. In this case, our \(\mathcal{IP}3\) codebook outperforms all other codebooks including Dense codebook. Note that since the data-distribution changed from MNIST to CIFAR10, Dense codebook now shows lower performance than \(\mathcal{IP}3\), particularly for larger perturbations of \(\epsilon = 4/255\) and \(\epsilon= 8/255\).

Importantly, the adversarial accuracy achieved by our \(\mathcal{IP}3\) is by no means trivial as under the exactly same setting other codebooks like 1-vs-1, 1-vs-All, Sparse do not show any robustness. In similar setting, a multi-class CNN of similar network capacity also does not provide any robustness to adversarial perturbations. This highlights the impressive capability of ECOCs to handle adversarial perturbations even though the individual binary hypotheses are all nominally trained. Our approach provides robustness-by-design, and does not make any specific assumptions about the adversary model in the design of codebook.

6 Conclusion and Future Work↩︎

Our computational results validate the merit of our optimal codebook design approach. Importantly, our IP-based formulation achieves small (or zero) optimality gaps while maintaining tractability for reasonable problem sizes. This is possible mainly due the graph-theoretic viewpoint we adopted in applying the edge-clique-cover, which substantially reduced the constraint set of original IP formulation. In the nominal setting, our compact IP generated codebooks outperform commonly used standard codebooks on most datasets.

In the adversarial setting, our IP-generated codebooks achieve non-trivial robustness. This is surprising due to three main reasons: (1) We do not employ any adversarial training; (2) Most other codebooks (except Dense) do not exhibit any robustness even when they use more than twice the number of columns; (3) The robustness that we obtain is not simply because of the large network capacity. To the best of our knowledge, we are the first ones to report that adversarial robustness can be achieved by a careful codebook design approach, while only using nominally trained binary classifiers.

Our results provide guidance for further research in the use of ECOCs for robust classification. We plan to study the effect of robustifying the individual hypotheses. Another variant would be to use a combination of nominally and adversarially trained hypotheses. We plan to pursue these aspects in our future work.

References↩︎