Scalable design of Error-Correcting Output Codes using Discrete Optimization with Graph Coloring
Authors: Samarth Gupta
Saurabh Amin
Venue: NeurIPS 2022 Accept (2022)
Keywords: Error-Correcting Output Codes
Graph Coloring
Discrete optimization
classification
transfer-learning

Abstract: We study the problem of scalable design of Error-Correcting Output Codes (ECOC) for multi-class classification. Prior works on ECOC-based classifiers are limited to codebooks with small number of rows (classes) or columns, and do not provide optimality guarantees for the codebook design problem. We address these limitations by developing a codebook design approach based on a Mixed-Integer Quadratically Constrained Program (MIQCP). This discrete formulation is naturally suited for maximizing the error-correction capability of ECOC-based classifiers and incorporates various design criteria in a flexible manner. Our solution approach is tractable in that it incrementally increases the codebook size by adding columns to maximize the gain in error-correcting capability. In particular, we show that the maximal gain in error-correction can be upper bounded by solving a graph-coloring problem.  As a result, we can efficiently generate near-optimal codebooks for very large problem instances. These codebooks provide competitive multi-class classification performance on small class datasets such as MNIST and CIFAR10. Moreover, by leveraging transfer-learned binary classifiers, we achieve better classification performance over transfer-learned multi-class CNNs on large class datasets such as CIFAR100, Caltech-101/256. Our results highlight the advantages of simple and modular ECOC-based classifiers in improving classification accuracy without the risk of overfitting.

Scalable design of Error-Correcting Output Codes using Discrete Optimization with Graph Coloring
Samarth Gupta
Saurabh Amin
Center for Computational Science & Engg. Massachusetts Institute of Technology, USA samart hgrmit t. edu
Laboratory for Information & Decision Systems Massachusetts Institute of Technology, USA amins@mit t. edu
Abstract
We study the problem of scalable design of Error-Correcting Output Codes (ECOC) for multi-class classification. Prior works on ECOC-based classifiers are limited to codebooks with small number of rows (classes) columns, and do not provide op- timality guarantees for the codebook design problem. We address these limitations by developing codebook design approach based Mixed-Integer Quadratically Constrained Program (MIQCP). This discrete formulation is naturally suited for maximizing the enror-correction capability of ECOC- classifiers and incorpo- rates various design criteria in flexible manner. Our solution approach is tractable in that incrementally increases the codebook size by adding columns maximize the gain in error-correcting capability. In particular, we show that the maximal gain error-correction can be upper bounded by solving a graph-coloring problem. As result, we can efficiently generate near-optimal codebooks for very large problem instances. These codebooks provide competitive multi-class classification performance on small class datasets such as MNIST and CIFAR10. Moreover, by leveraging transeer-learned binary classifiers, we achieve better classification performance over transfer-learned multi-class CNNs large class datasets such CIFART0O, 100, Caltech- 101/256. Our results highlight the advantages of simple and modular ECOC-based classifiers in improving classification accuracy without the risk of overfitting.
Introduction
Enror-correcting codes have found many applications in machine learning. Their use range from natural classification tasks [8, 24, 17, 21] including multi-label classification [11] robust classification [43, 46, 16] to federated learning [22] zero-shot learning [40] to life-long learning [20]. The seminal paper of [8] proposed the use of error-correcting output codes (ECOCs) for classification tasks. Their framework lead to significant activity on the design of ECOCs with variety of features; for c.g. the use of different class of encodings [7, 17, 39], hierarchical classifiers [14, 12], decoding schemes [2, 9] and accounting for the underlying Sata-distribution [49, 47, 30, 33]. However, a key challenge that remains to be addressed is a flexible and tractable approach for designing high-quality codebooks. Our paper addresses this challenge.
We tackle some of the limitations of prior works on solving the discrete codebook design problem. In particular, we depart from the classical approach that performs continuous relaxation of the discrete codebook design problem and attempts to solve the resulting non-linear optimization problem 49, 47, 33]. That approach has been shown to scale to large number of classes k. but under the limitation that the size of the codebook (i.e. number of columns L) small. However, with small I. codebooks do not fully exploit the error-correcting capability, which is the key motivation to use ECOCs in the first place. Besides, the continuous relaxation approach typically does not provide codebooks with strong optimality guarantees.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

We formulate the codebook design problem as a mixed integer quadratically constrained program (MIQCP) and develop a greedy algorithm efficiently solve this MIQCP. Each iteration of our algorithm adds new set of columns to the current codebook such that the gain in error-correcting capability is maximal. Importantly, we exploit a graph-coloring based upper-bound to accelerate the iterations of the greedy algorithm. Thus, our algorithm provides the flexibility to choose codebook size based on the desired level of final accuracy. The key advantage of our approach is that it easily scales to large problem instances (k 500). In comparison, the recent paper of [16] generates high-quality codebooks but only for & - 50. Thus, our approach can be maximally leverage the benefit of ECOCs in aforementioned applications of error-coreccingg codes for realistic problem instances.
Our main contributions are as follows: (i) In contrast to [8, 33, 49, 47, 16], we model the codebook design problem as an element-wise optimization problem (MIQCP formulation). (ii) We develop a solution approach using a greedy algorithm to solve large instances of the MIQCP with low-optimality gaps. (iii) We make a theoretical connection the vertex-coloring problem to upper bound the maximal gain in the error-correction which leads to faster iterations of the greedy algorithm. (iv) Our codebooks achieve very high classification accuracy similar to multi-class CNNs on datasets with small number of classes. (v) Finally, we show novel benefit of ECOCs with transfer-learning on large class datasets. Our codebooks outperform multi-class CNNs when trained with transfer-learning under both nominal and robust feature settings.
2 ECOC for Classification
The ECOC-based framework [8], encodes each class of k-class classification problem with unique codeword length L.. This encoding results in a codebook (coding matrix) M of size & x For binary codes: M E {+1,- _1] The rows (resp. columns) of .M correspond to distinct classes (resp. binary classifiers or hypotheses). Figure shows two example codebooks for a classification problem with classes. For every column in M binary classifier is trained over the training data, where all training data from classes with entry +1 (resp. entry -1) forms the positive class (resp. the other class).
f1
f2
fs
f4
f$
f1
f2
f4
fb
fo
C1
+1
C2
-1
+1
-1
-1
C2
-1
-1
+1
Cs
-1
-1
+1
-1
+1
+1
Cs
-1
-1
-1
-1
+1
C.
+1
-1
+1
-1
+1
Figure 1: Example codebooks and their corresponding binary classifiers for a 5-class classification
problem.
For test example æ, let hypotheses, where f, (x) E (+1,-1) A E {l...., LJ. This encoding F(x), where F(x) (z)),..... f( (=)). is then associated with class (i.e., row of coding matrix M). typically using decoding scheme based on a similarity measure such as Hamming distance. A common approach is to compute the Hamming distances dæs .): between F(x) and each codeword M(i, Vi {1,...,
fz(x) denote the predicted class of each of the learned binary
and predict the output class ÿ as the class with the minimum distance:
M(i.j) x fz
dh (M(..))
2
i argmin du (M(
Importantly, the final classification performance of the above ECOC procedure depends both the accuracy of the trained binary classifiers and the error-correcting capability of the codebook M. In particular this capability increases with the Hamming distances between rows; i.c. codebook with high pairwise Hamming distances across its rows has higher crror-correction capability.
Definition 1. Hamming distance of a codebook (denoted as k.) defined as the minimum hamming distance between any two distinct pair of codewords (or rows) in M.
RM (I.))((I...)))133
min d dH(M -), M(j.))
2

---

Proposition correct at-least KAy-i
Capability). A codebook M with hamming distance R.M, can always
errors.
Proof of proposition and all subsequent technical results are provided in supplementary information (SI).
3 Problem Formulation
For a k-class classification problem we want to find an optimal codebook of length L. Thus, we want to find the value of &o x L entries of codebook, where each (i. entry (denoted Tay) can take values in {+1, -1 such that the resulting codebook has high multi-class classification accuracy. To achieve high classification accuracy, take the following design criteria [8, 16] into consideration:
1. The crror-corretiing property increases with the Hamming distance between rows; therefore it is desirable have high Hamming distance between any pair of rows. We ensure this by maximizing the Hamming distance of the codebook (or the minimum of the row pairwise Hamming distances). For binary codebook of size h x L, analytical upper bound on this
objective is given by the well-known Plotkin's 's bound [37]:
Lk
1)k-1)
2.
The Hamming distance between any two pair of columns of the codebook must be at least 1 to avoid same columns and most k separation is desirable in order to avoid correlations between the resulting hypotheses (or binary classifiers). Due these reasons, constrain the Hamming distances between any distinct pair of columns between P1 and P2, where P1 2 and P2 I k 1.
avoid complementary columns. A good column
3. Finally we consider the balanced column criterion. This criterion allows to control the amount of imbalance in the resulting binary classification problem, i.e. the number of data-points in each of the two classes. This automatically ensures that no column has all entries as +1 or -. Importantly, while balanced columns help in improving the error-correcting capability, imbalanced columns often result in easier binary classification problems, especially when working with linear classifiers, thus promoting higher multi-class accuracy [2, 9, 41]. In SI, we further discuss the nuances of shaping this trade-off off in design of the codebook.
For notational convenience denote the set of row indices as N,, the set of column indices T, set of all pair of rows (or corresponding classes) PAs and the set of all pair of columns Py. Mathematically:
N 1, .......... k) PN { (1, E (I.....,k) = L) Pr = (1.3) (1....,4) (L......4) j <i}.
k} x {1, k} 1 < <
We can now formulate the element-wise codebook design problem based on the above design criteria as the following Integer program (IP1):
IP1: : max min {d (x).
(x:)
g1.3 (x),
H
....
k- (x)}
H
(1a)
s.t.
d (L
Σ
4 (1,)) PN
(1b)
5=1
P1 S 1 (k: Σ
Kij X x.iz) S p
(1.3) E PT
(1c)
i=1
7 S
MjJaj S7
VJET
(1d)
Tig E (+1,-1}
A ENX (1e)
The objective of IP1 is to maximize the minimum Hamming distances between different pairs of rows (la). Constraint (Ib) computes the Hamming distance between rows; (Ic) ensures that column separation lies in the desirable range [PI,Pe]; (Id) ensures that every column results in valid balanced binary classification problem, where n, the number of training samples in i-th class of the dataset, while y controls the degree of allowed imbalance; and finally (1c) ensures that zy takes integer values in {+1,- -1). The max-na max-min objective (la) can be simplified by introducing an auxiliary variable f, where f. == min (d))(x),,
(x), d (x),
d d --)((()))) and adding constraints
t < d)²(()) (z). S di 1--1, (x).
3

---

Note that (lb) and (Ic) contain bilinear terms and are non-com convex in nature. Thus IP1 can be categorized as a non-convex Mixed Integer Quadratic Constrained Program (MIQCP). IP1 cannot be solved directly (1b) and (1c) contains bilinear terms and therefore these constraints are linearized to get linear-relaxation of TP1. Fach bi-linear term is replaced with an auxiliary variable Zijpg- where Zijoy == Epg- Additional linear constraints known as McCormick-inequual ineuuliiieeuallitess [34] are then added to lower and upper bound Exjog. Further details about McCormick inequalities (including their derivation) are provided in supplementary information (SI). For the bilinear constraint 2ijoo Pig these inequalities are given by (2a) and (2b).
Lower:
Pijpy 2 Fig pp 1; Zijog 2 Dij + Ipp
(2a)
Upper:
Fijon S Vij
2g + 1; Zajoy
-Jij + Ipm +
(2b)
Also, (2a) and (2b) respectively provide convex lower and upper envelopes to the feasible set admitted by the bilinear constraint [1].
Lemma 1. McCormick relaxation IP1, denoted as MC(IPP)) tight:
{(zippe Tij. Fyg) E R x {+1, 1139 Ziipa #syzpa) = {Zzipe :ij: Fpa E IR x (+1, (2b).
Thanks to lemma 1, IP1 can now be solved by solving the MILP (i.e. MC(IP1)) obtained after replacing the bilinear terms in (Ib)-(1c) with the corresponding McCormick inequalities. Note that IP1 has L |Parl + k [Pyl= = L x (t) l (5) number of bilinear terms. If L = k, IP1 will have (1:)) number of bilinear terms. However in practice, linear programming (L.P)-ellxaation of MC(IP1) can be quite loose and hence even with the tight reformulation, TPI cannot be used to tractably solve the optimal codebook design problem (especially when L is large).
Therefore, instead of generating optimal codebooks by solving IP1 directly in one-shot, we next develop scalable greedy solution approach generate good-quality (near optimal) codebooks for large and L.
Proposed Solution Approach
In this section develop iterative greedy algorithm generate near-optimal codebooks i.e. codebooks with low-optimality gap. To develop our approach, we utilize the following monotonicity result of lemma 2.
Lemma 2. Let M and M be two binary error-correcting code of size xxl and k x (I+1) respectively, where 2 O, such that all columns in M are also in M, iee. M C M. Then, the Hamming distances (recall 1) of M and M satisfy: RM & implying that the error-correcting capability of M is at least as good as M.
This intuitive result serves as the starting point of our solution approach. In particular, from Lemma 2, we know that the eттor correcting capability of a codebook M of size k x I can be improved further by increasing the number of columns, i.c. adding I columns. Naturally, this improvement not only depends on i, but also on how the entries of the new columns are selected. Our solution approach progressively adds new columns to an existing codebook by solving a smaller integer program, denoted IP2; see figure 2. This integer program maximizes the hamming distance of the resulting codebook (i.e. its error-correcting capability), while ensuring that desired column separation for all (i.e. new and old columns) is achieved and the resulting codebook still remains valid binary error-correcting code with balanced columns.
i2
822
#12
Solve IP2
+ = (1,....,
(3)
Tai
T32
P+ = (U.0)
5x2
(1 (1..... x (1 (1....... 1i [i
(4)
8 x 4
8 x 6
3y
(5)
Figure 2: Adding new columns to an existing codebook
Before proceeding, we introduce new notation for mathematical convenience. Analogous to T. (resp. PT) let T denote the set of new columns (resp. Py denote the set of pair of new columns). Furthermore, let the entries of the new columns be denoted as æij. Mathematically these are defined in (3), (4) and (5) respectively. We are ready to present IP2 which takes a valid codebook M of size k x l and number of columns I to be added as inputs.

---

IP2: max min (i), (0), (+)}
(6a)
(x(00) = 2
1 + Σ M(irr) M(,)) + =Σ Big x mis
((, E Px (6b)
j=1
1
P1 S 2/
Σ
Tig x Ezg) P2
V(. EP (6c)
i=1
P1 S 1 (k: Σ
M(i,g) x x p2
A (6.)) 3 (1...., .fx x (6d)
- 7 - Σ ng S
VjEÝ
(6e)
TJj = [+1,-1}
ENx))
(6f)
The objective function (6a) maximizes the the error-correcting capability. Constraint (6b) computes the Hamming distance between pairs of rows (or classes) in the resulting codebook; (6c) ensures desired column separation between any pair of new columns; (6d) ensured desired separation between new columns and existing columns in input MM (6e) ensures that new columns are balanced and (6f) ensures that the new codebook is a binary codebook.
Notice the key difference between TP2 and IPI: since i & 1, the constraints (6d), which account for the majority of columns separation conditions in the resulting codebook are linear in E as the entries of .M are known. Further, the total number of bi-linear terms in row-separation constraints (6b) and column separation (between new columns) constraints (6c) are much smaller in number. These features of IP2 makes it solvable even for large by off-the-shelf IP solvers which typically employ branch-and-bout
(B&B) procedure.
It turns out that we can pre-compute good quality (potentially tight) upper-bound to IP2. In section 4.1, we explore two different ways to generate an upper bound to IP2. Our computational results show that a good upper bound can accelerate the termination of the B&B procedure for IP2. Since our greedy algorithm 4.2 relies on solving TP2 repeatedly to increase the error-correcting capability, the overall computational gain can be significant.
4.1 Upper Bound to IP2
The integer constraint (6f), Fyg E [+1,-1} in IP2 can be equivalently re-written as = = 1 and the resulting problem generate an upper bound by taking the Rank- semi-definite programming (SDP) relaxation of this quadratic program (for details see SI). The tightness of this relaxation is same taking the dual of aforementioned quadratic program (equivalently IP2), which is also a SDP and is dual to the Rank-1 SDP relaxation. However, solving the SDP-relaxation
be categorized as a continuous, non-convex quadratic program. We can
be expensive for large h even with modern first-order SDP cone solvers (for eg: SCS [36]). More importantly our computational experiments suggest that the SDP-relaxation does not provide good quality upper-bound to IP2.
We now discuss a second procedure to generate an upper bound to IP2. To begin with, note that the addition of ī columns to an existing codebook M, as done by IP2, can be equivalently viewed as the appending codewords (denoted as c;) of length I to each row i of the codebook M, see figure 3. For binary codes there are 2 possible distinct codewords of length 1, let the set of these codewords be denoted as C(T). Essentially in solving IP2, we seek to choose codewords from C(i), such that the codebook resulting from appending them to the existing rows of M maximally increases the error-correen correcccre capability. In particular, out of all (t) row pairs, IP2 tries to increase the hamming distance between row pairs which are at the minimum in the existing codebook, as these minimum hamming distance row pairs decide the error-correcting capability (recall proposition 1).
For given codebook M, we define the set of minimum distance row-pairs (denoted Exy) as:
EM
{ (b-j) E kk) x (1....,k)) k3] i < j and d (Mii, -), M.G -)) = =
(7)
For example. the minimum hamming distance between any two distinct pair of rows in the codebook shown in Figure is 4, and there are multiple row pairs for which the Hamming distance is 4. In
5

---

where 6; E C(I). For 1= ==2, 2:
62
+
C3
[+1,+1] C(2) = [+1,-]]
[+1,+1] [-1.-1]
Codebook M
Error-correcting Graph 9M of
Figure 3: Codebook M (left) and its corresponding error-correcting graph GM (right). Since 9M has a clique of size 5 (shown in bold edges), therefore chromatic number E(G > 5, thus GM cannot be colored with four colors (or codewords in C(2)). Therefore adding codewords of size will not result in improving the hamming distance of M.
general, for a codebook M of size k x I, we can represent the set EM as an undirected graph (denoted GM) with k-vertices, where vertex corresponds to row i in M V E {l..... ................. kj. For every (i.j) in EM, an edge is present between vertices and j in GM- We refer to graph Gm as the error-correcting graph of M. Mathematically,
9M (V, where V (1....,k)
Figure 3 illustrates codebook M and corresponding error-correcting graph 9M- This viewpoint enables us to make two important observations:
1. Increasing the hamming distance of row-pairs in EM by at least through addition of columns (or equivalently by appending codewords c;) to M, effectively increases the minimum hamming distance of the entire codebook by least
2. Any pair of distinct codewords in the set C(I) differ by at least and at most i.e.
1 < dh (c,, 0j) < [
4 Cz. Cj. E C(I), i + j.
These observations lead the following claim in proposition 2:
Proposition 2. For codebook M, if there exists an assignment of codeword o E C(i) to each vertex of graph Gm such that no two connected vertices receive the sume codeword, then the hamming distance of the codebook KMM can be increased by at least by adding codewords from C(I) the rows of M.
In fact the condition specified by proposition 2, can be easily verified by solving an instance of unique
the graph-coloring problem on GM. where each codeword E C(I) can be viewed color. Before proceeding further, we recall some useful definitions related to graph coloring. A proper-vertex coloring is assignment of colors to the vertices of graph so that two adjacent vertices have the same color.
Definition 2 (Chromatic number). The chromatic number of graph G, denoted as E(G) is the minimum number of colors required for a proper vertex coloring of the graph G.
Theorem 1. For any binary code M resulting from adding columns to existing binary code M, the following holds regarding the hamming distance (recall 1) Ka of the code M:
If the chromatic number of the graph GM, E(GM) greater than the size of the set of possible codewords C(I), i.e. E(GM) > [C(1)), then RM = KMM
In particular, for i {
NM +ī RM S RM -1-1
if E(GM) =2
if 3 S E(Gm) <
RM-
if E(GM) 25
Corollary 2. An upper bound IP2 provided by theorem or IP2 infeasible.
Since for a given M, theorem 1 provides a valid upper-bound to the hamming distance (or equivalently the error-correcting capability) of all codebooks resulting from adding columns to M, therefore
"Extension where i 3 is provided in SL.

---

Algorithm 1 Greedy
Time (in secs.)
50
0.063
1: Generate first column C₁ randomly.
100
0.148
2: M < C1 and start counter: =
150
0.099
200
0.165
3: while i < do
250
1.039
4: Compute 5(GM))
300
0.234
5: Compute upper bound to IP2 using ((GM) and i.
350
0.134
6: Solve TP2 with latest M, I and upper-bound.
400
1.921
0.813
7: Update M with the solution of IP2
0.852
8: i= i i
Table Avg. time taken to com- pute the chromatic number E(GM) for different
9: end while
10: return MM
automatically also provides an upper-bound to IP2. Further, the color- assigmmentttt can be used to generate (partial) feasible solution to TP2. Technical details of feasible solution generation provided in SI.
Note that the problem of computing the chromatic number of graph (or analogously solving the vertex-coloring problem) has been extensively studied in the literature. This includes heuristics such as DSATUR [4] and RLF [28], exact backtracking algorithms [26] and more recent integer programming based exact methods [18, 35, 32]. We solve our graph-coloring problem by formulating and solving it as an integer program (IP); please refer to SI for details. In table 1, report the average time needed to solve the vertex- coloring problem for various error-come prror-corecctng graphs 9M with different k. In almost all cases we are able to solve the graph-coloring problem extremely fast within 1-2 seconds. This is mainly due to the highly sparse structure of 9M as large number of nodes tend to have low or even zero-degree resulting from high diversity in row pair-wise Hamming distances.
4.2 Greedy Algorithm
We are now ready present our Greedy Approach (Algorithm 1) for generating a codebook of size k x L which is near-optimal feasible solution to our original codebook design problem. Initially, we randomly pick the first column of the codebook such that it is valid balanced binary classifier. Then, a second column added by solving IP2 with ī 1, this provides us with codebook of size k x 2 that satisfies all the design criteria. With this as our current codebook with two columns, we then continue to append more columns by again solving IP2. This procedure continued until we obtain a codebook with L columns.
Practically, is important keep ī reasonably small that the solution to IP2 in each iteration of Algorithm is obtained quickly. In the first few iterations, since M is small, therefore the number of column-separation constraints between the existing and new columns (6d) is small. Thus, for large i.e. 50, for first [log2 & iterations we solve IP2 with i = and use i > 2 in the subsequent iterations.
4.3 Flexibility in choosing the size of the codebook
For most ECOC design approaches in literature, one needs to pre-define L to solve the codebook- design and then train each of the binary classifiers. If the resulting multi-class performance is not satisfactory then the process repeated: increase L, resolve the codebook design problem and re-train all the columns in the new codebook. Naturally, this iterative design process is quite burdensome because of the computation effort spent on solving and training codebooks each iteration.
In a sharp contrast, our design approach does not require pre-specifying L as columns can be greedily added to build codebooks. In particular, we can start off with relatively small L, train the resulting columns and evaluate the multi-class performance. If required, we can then append more columns to the existing codebook by solving IP2, train the new columns and re-evaluate the multi-class performance. This procedure can be repeated until minimal or no improvement is observed. Importantly the computation effort spent in training previous columns is not wasted and one can stop anytime if the improvement in the multi-class classification performance is negligible. This flexibility also makes our approach dataset dependent to a certain extent [33]. Finally, we note that authors of [38, 39] have discussed choosing I. but their work is limited to problems with small k.
See SI for reason to choose [loga k7.

---

We next perform computational experiments to evaluate the performance of our greedy algorithm and subsequently evaluate the classification performance of the codebooks generated by the greedy algorithm.
5 Experiments
We use Gurobi-v9.1 our integer programming (IP) solver and run all our experiments on machine with Intel Core 17-6800K CPU, 32GB RAM and 1080Ti Nvidia GPU. We compute optimality gaps of codebooks generated by different approaches using Plotkin's 's Bound (PB). The gap is defined as: |PB- - // /heu, where Shea denotes the objective function value of the solution. Our code is
available at:
Gap (%)
I:
L
PB
IP1
Greedy
[16]
Dense (random)
Dense (best out of 10k)
IPI
Greedy
[16]
Dense (random)
(hest out of 10k)
12
24
11
12
7
9
18.18
8,33
8,33
85.7
44.4
32
14
12
20
40
21
14
19
12
15
50.0
10.53
10.53
75.0
40.0
24
48
23
22
22
13
18
13.64
13.64
66.7
38.8
25
18
21
11.54
32
64
33
29
29
20
24
13.79
13.79
65.0
37.5
36
72
37
33
32
23
27
12.12
13.62
60.9
37.0
36
30
10.81
13,89
51.8
44
88
45
39
29
33
12.50
15.38
55.2
24.2
48
96
49
43
43
33
37
13.95
13.95
48.5
32.4
Table 2: Comparison of IP1, Greedy (ours), Gupta and Amin 2021
[16] and Dense codebooks on
small problem instances. '''indicates that no solution is generated within time limit of 1800 secs.
L.
Jben Dense (random)
Gap (%)
Dense (best out of 10k)
Dense (random)
Dense
Greedy
[16]
Greedy
[16]
(best out of 10k)
50
100
51
44
44
34
38
15.9
15.9
50.0
34.2
100
200
101
88
75
80
14.77
34.7
26.3
150
300
151
134
117
123
12.68
29.0
22.7
200
400
201
181
160
168
11.04
25.6
19.6
250
500
251
226
205
212
11.06
22.4
18.4
300
600
301
270
249
237
11.48
20.9
17.1
350
700
351
314
295
303
11.78
18.9
15.8
400
800
401
360
340
349
11.38
17.9
14.9
450
900
451
401
384
395
12.46
17.4
14.2
500
1000
501
444
431
441
12.83
16.2
13.6
Table 3: Comparison of IP1, Greedy (ours), Gupta and Amin 2021 [16] and Dense codebooks on large problem instances.
We perform our first set of IP experiments on small problem instances (A: < 50) to provide a comparison between solving IP1 directly and our Greedy approach (Algorithm 1). Details regarding values of P1: P2: and their appropriate ranges are provided in SI. We benchmark against the approach of [16] and also against randomly generated Dense codes. The procedure generate Dense codes [2] is discussed in SI. We summarize our results in Table 2. Notice that for very small instances such as k = 12 and
16, IP1 able to generate good quality solution, however for slightly larger problem instances (say h = 20) the solution quality of IP1 deteriorates rapidly (the gap is around 50%); and finally for k 2 24, IP1 simply fails to even generate feasible solution. This highlights the intractability of IP1 to generate good quality codebooks. In contrast, our Greedy approach provides very high quality solutions. Note that for all cases, our greedy approach either matches or outperforms the column-subsed selection (CSS) approach of [16]. On very small instances i.e. & < 24, [16] provides competitive performance to our greedy approach. The reason behind this is because [16] provides tight IP formulation but at the cost of having exponential (22) number of binary variables. Their performance deteriorates after à 2 24 as they have to resort to random sampling to mitigate the computational expense of (22)) number of binary variables. It is not surprising that due to this exponential complexity, [16] ] is not tractable beyond > 50, as discussed next. Also, Dense codes consistently have very high gaps in comparison our Greedy Approach.
We evaluate the performance of our Greedy approach (Algorithm 1) on large problem instances, i.e. for k 2 50. These results are reported in Table 3. We observe that approach of [16] does not even provide feasible solution for k > 50. contrast, our greedy approach generates good quality solution for even A 500 while maintaining low optimality gaps. For all cases (k > 50) our gaps
8

---

are well below 15%. Thus our approach is significantly more tractable than of [16]. Interestingly, for k 2 350 Dense codes also provide competitive performance. To the best of our knowledge, we are the first to achieve such scalability with low optimality- gaaps for the codebook design problem.
5.1
Classification Performance
We now evaluate and benchmark the classification performance of our codebooks generated using greedy approach on different datasets. For each dataset, we generate codebooks of different sizes using the Greedy approach and compare it with other commonly used codebooks like 1-vs-All, 1-vs-1 [41], Hadamard and Dense codes [2]. For every codebook we train L binary classifiers corresponding to the columns of the codebook. We also benchmark against multi-class CNN. This multi-class CNN has the same architecture as the binary classifiers except for the size of the output layer. which is 2 for binary classifiers and k for multi-class CNN. For all experiments, we report average of 5 runs. Details regarding different datasets, model architectures, hyper-paramette parameters and training are provided in SI.
MNIST & CIFARIO: In our first set of classification experiments, we evaluate the performance on MNIST and CIFAR10 10 datasets (both with k = 10). Using Greedy approach we generate codebooks of size L = 5 and 10. The classification performance of different codebooks is reported tables 4 and 5 respectively. On MNIST, the improvement in accuracy with increase in L is small, since MNIST is a relatively casy classification task. However, on CIFAR1O, for which the underlying classification task is much harder than MNIST, obtain a 1.8% gain in accuracy the size of the codebook increases from L = 5 to L = 10. Further on CIFARIO 10, our compact greedy codebooks easily outperforms standard 1-vs-1 codebook which uses L = 45 binary classifiers by around 4.5% and also outperforms 1-vs-All codebook by more than 1%. For both datasets, Dense and Hadamard codebooks also provides high aceuracy, particularly Hadamard codebook MNIST dataset. In comparison to multi-class CNN, our greedy codebooks provides very similar accuracy on both datasets, with slightly lower accuracy on MÄIST but higher on CIFARIO.
Greedy (Ours)
Hadamand
I-
[16]
Multi-
10
15
L-
I 15
L 10
45
L -
L-
class
97.83 # 0.02
98.86 0,05
98.87 # 0.01
78.99
0.08
98.67 + 0.33
98.89 = 0.02
98.55 55
0.07
94.61 # 0.12
98.87
+ 0.01
98.25
0.04
98.92 0.04
Table 4: Accuracy on MNIST dataset.
Greedy (Ours)
Hodamard
I-ss-All
L-s--1
[10]
Donse
Multi-
5= 5
L=
== 15
6=
L
10
L
15
L=
L 45
L 15
A= 15
class
93.39 0.08
95.55 +0.06
95.57 0:02
74.65
0.05
95.14
0.03
95.46 0.02
94.40
0.14
90.86 0:09
95.57
0.02
95.14 +
0:03
95.36
Table 5: Accuracy on CIFARIO dataset.
CIFARI00 & 101/25: In the second set of experiments we evaluate the performance on large class datasets: CIFAR100, Caltech-101 and Caltech-256 with k 100, 101 257 respectively. Recall that, for these large class datasets, the approach of [16] cannot even generate feasible codebook. Thanks to our greedy algorithm, we can easily generate and evaluate our codebooks on these datasets. Note that the computational expense associated with the training of L. binary classifiers for each codebook can be large; however this is a general limitation of ECOC-based classifiers. Firstly, our work addresses this limitation by generating compact codebooks with low-optimality gaps. Secondly, we leverage the power of transfer learning to significantly reduce the training time of binary classifiers. More generally, another motivation to leverage transfer-learning is due to the fact that modern deep-Icarning models continue to get bigger in size by the day and thus transfer-lcarning has become even more effective in the face of limited compute and data availability. Our next results indeed demonstrate the additional benefit which ECOCs provide with transfer-learning to further improve classification accuracy.
For leanfin- we use models trained on ImageNet and replace the last fully-connected layer of 1000 classes with a fully connected DNN with 2 output classes for binary classifiers and & classes for multi-class classifier respectively. We then freeze the weights of all but the last fully-connected DNN. Interestingly, authors in [42] and [45] have recently shown that adversarially trained robust models provide better generalization in target domain over nominally trained models. Therefore for more comprehensive evaluation of our approach, use features from two different ResNet50 models trained on ImageNet. The first model has been pre- pre-trained nominally on the ImageNet dataset
Authors in [16] report an accuracy of 76.25% however for a fair comparison we re train their codebooks using our training procedure, resulting same accuracy as groedy, since the corresponding feet value both codebooks (Le. greedy and [16] is same.

---

while the second model has been trained adversarially with l2- no-m perturbations. More details on these individual models are provided in SI. The final multi-class accuracies of all the codebooks and multi-class CNN for both nominal and robust features are provided in tables 6, 7 and 8 respectively.
Type of
Greedy (Ours)
Hadamard
1-1s-All
Dense
Multi-
feature
7. 50
100
r. 200
50
I. - 100
1. - 127
I. 100
7. - 200
class
Nominal
60.62 0.30
61.65 +: 0.12
62.15 +
61.982
62.04 0.02
62.58 0.02
61.70 0.10
59.19 0.20
Robust
80.85 + 0.03
81,46 + 0.20
81.68 + 0.09
51.82 = 0.02
81.51 0.05
81.7 + 0.01
80.41 0.05
81.60 0.07
79.59 + 0.06
Table 6: Accuracy on CIFAR 100 dataset
Type
Greedy (Ours)
Hadamard
I-vs-All
Dense
Multi-
feature
L =
100
200
50
L = 100
L = 127
L 101
4. 200
class
Nominal
84,55 + 0.02
85.04 + 0.10
85.33 + 0.05
56.49 + 0.06
85.10 + 0.04
85.17 + 0.07
84.06 0.08
85.16 + 0.08
84.73 + 0.30
Robust
87.08 0.10
87.52 + 0.09
87.76 + 58.06
87.55
87.73 0.02
86.57 0.10
$7.50 0.10
86.39 0.12
Table 7: Accuracy on Caltech- 101 dataset
Type of
Gready (Ours)
Hadamard
I-v--All
Dense
Mulri-
feature
7- 100
Z- 200
300
L- 100
1. 200
L- 300
L- 511
L- 207
1- 300
class
Nominol
76.84 0.12
77.29 0.09
77.38
0.07
$2.94
0.08
75.784
77.4 0.06
77.41 0.00
75.01 0.00
77.01 76.23
0.18
Robust
77.06 0.07
77.44 1..33
77,55
0.08
33:25_ 0.05
75.90.L
0.04
77.51 1 0.03
77.53 1 0.05
76.52 1. 0.01
77.45 0.09
76.79 0.11
Table 8: Accuracy on Caltech-256 dataset
We observe that on all the three (large class) datasets, our greedy codebooks consistently outperform multi-class CNNs. For all cases, robust features indeed provide better accuracy over nominal features thus validating the hypotheses of [42, 45] in the context of ECOC-based classifiers. Importantly, our greedy codebooks provide even further improvement over multi-class CNNs in the robust feature setting.
On CIFARIOO, in the nominal setting our greedy codebook provides an improvement of around 3% over multi-class CNN and also outperforms other codebooks well, except 1-vs-All. In the robust setting, both greedy and Hadamard provides high accuracy and an improvement of 2% over multi-class CNN. On Caltech- greedy codebook provides an improvement of around 0.6% over multi-class CNN in nominal setting and around 1.4% in the robust feature setting. On Caltech-256 our greedy codebook provides gain of around 1% over multi-class CNN in both nominal and robust features setting; here the small gain in improvement with robust features over nominal features is consistent with the findings of [42].
It is important to note that Hadamard codes provide high accuracy only for large L, thus limiting their application large multi-class classification problems [5].
These classification results clearly demonstrate the benefit of using ECOC-based classifiers and further highlighting the merits of our element-wise codebook design approach. Importantly, our IP-based Greedy algorithm provides scalability while ensuring small optimality gaps. Further, the resulting codebooks generated, provide improved classification performance on large datasets like CIFAR 100, Caltech- 101/256. To the best of our knowledge, we are first to report such performance using ECOC-based classifiers. The greedy codebooks only provide a marginal improvement over Hadamard and Dense codes in terms of classification accuracy on large-class datasets. However, note that Hadamard codes only provide high accuracy when full Hadamard code of length L 2 210gg(()] is used. For much smaller L, Hadamard codes perform much worse than our greedy codebooks. Besides, as shown in [16), Dense codes are not robust to adversarial perturbations, but the proposed approach is likely to provide non-trivial adversarial robustness.
I Limitation:
6 Concluding Remarks, Future Work and Societal Impact
In this paper we developed a scalable approach to solve the discrete codebook design problem for large multi-class problem instances. Our approach generates near-optimal codebooks resulting in higher classification accuracy. As future work, we aim to extend our design approach to other settings, for example, when the cost of ciss-classification is different across different class-paing paiss. Our ECOC based approach is particularly well suited to handle such tasks as we can easily switch from global error-correctig property to class-pair wise error-correctigg property [33] with simple modifications. Another extension of our work would be to very large multi-class problems [5] and extreme multi-label (XML) classification problems. We do-not expect any negative societal impact other than that of general classification systems.
10

---

References
[1] Faiz. A. Al-Khayyal and James Falk. Jointly constrained biconvex programming. Mathematics of Operations Research, 8:273-286, 1983.
[2] Erin L. Allwein, Robert E. Schapire, and Yoram Singer. Reducing multiclass to binary: A unifying approach for margin classifiers. Journal of Machine Learning Research, 1:113-141, 2000.
[3] Rohit Babbar and Bernhard Schölkopf. Dismec: Distributed sparse machines for extreme multi-label classification. In Proceedings of the Tenth ACM International Conference Web Search and Data Mining, WSDM '17, page 721-729, New York, NY, USA, 2017. Association for Computing Machinery.
[4] Daniel Brélaz. New methods to color the vertices of graph. Commun. ACM, 22(4):251-256, apr 1979.
[5] M. Cissé, T. Artières, and Patrick Gallinari. Learning compact class codes for fast inference in large multi class classification. In Peter A. Flach, Tijl De Bie, and Nello Cristianini, editors, Machine Learning and Knowledge Discovery in Databases, pages 506-520, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
[6] Alberto Costa and Leo Liberti. Relaxations of multilinear convex envelopes: Dual is better than primal. Proceedings of the 11th International Conference on Experimental Algorithms, SEA'12, page 87-98, Berlin, Heidelberg, 2012. Springer- Verlag.
[7] Koby Crammer and Yoram Singer. On the learnability and design of output codes for multiclass problems. Machine Learning, 47(2):201-22 -233, May 2002.
[8] Thomas G. Dietterich and Ghulum Bakiri. Solving multiclass learning problems via error- correcting output codes. Journal of Artificial Intelligence Research, 2(1):263-286, January 1995.
[9] Itay Evron, Edward Moroshko, and Koby Crammer. Efficient loss-based decoding graphs for extreme classification. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 7233-7244, Red Hook, NY, USA, 2018. Curran Associates Inc.
[10] Li Fei-Fei, Rob Fergus, and Pietro Perona. Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories. Computer Vision and Image Understanding, 106(1):59- 70, 2007. Special issue on Generative Model Based Vision.
[11] Chung-Sung Ferng and Hsuan-Tien Lin. Multi-label classification with error-correctngg codes. Chun-Nan Hsu and Wee Sun Lee, editors, Proceedings of the Asian Conference on Machine Learning, volume 20 of Proceedings of Machine Learning Research, pages 281-295, South Garden Hotels and Resorts, Taoyuan, Taiwain, 14-15 Nov 2011. PMLR.
[12] Tianshi Gao and D. Koller. Discriminative learning of relaxed hierarchy for large-scale visual recognition. In International Conference Computer Vision, pages (072-2079, 2011.
[13] Assefaw Gebremedhin, Duc Nguyen, Md. Mostofa Ali Patwary, and Alex Pothen. Colpack: Software for graph coloring and related problems in scientific computing. ACM Transactions on Mathematical Software (TOMS), 40, 09 2013.
[14] G. Griffin and P. Perona. Learning and using taxonomies for fast visual categorization. IEEE Conference on Computer Vision and Pattern Recognition, pages 1-8, 2008.
[15] Gregory Griffin, Alex Holub, and Pictro Perona. Caltech-256 object category dataset. CalTech Report, 03 2007.
[16] Samarth Gupta and Saurabh Amin. Integer programming- -baed error-correcing output code design for robust classification. In Proceedings of the Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pages 7724-1734 PMLR, 27-30 Jul 2021.
Conference on Uncertuinty

---

[17] Venkatesan Guruswami and Amit Sahai. Multiclass learning, boosting, and aroo-cooreecing codes. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory, COI.T99,, pages 145-155, 1999.
[18] P. Hansen, M. Labbé, and D. Schindl. Set covering and packing formulations of graph coloring:
Algorithms and first polyhedral results. Discrete Optimization, 6(2):135 147, 2009.
[19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. arXiv preprint arXiv: 2015.
[20] Shen-Shyang Ho, Mathew Marchiano, Scott Zockoll, and Hieu Nguyen. An correccrre output code framework for lifelong learning without teacher. In 2020 JEEE 32nd International Conference on Tools with Artificial Intelligence (ICTAI), pages 249-254, 2020.
[21] Elad Hoffer, Itay Hubara, and Daniel Soudry. Fix your classifier: the marginal value of training the last weight layer. International Conference on Learning Representations, 2018.
[22] Hossein Hosseini, Hyunsin Park. Sungrack Yun, Christos Louizos, Joseph Soriaga, and Max Welling. Federated learning of user verification models without sharing embeddings. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 4328 4336. PMLR, 2021.
[23] Himanshu Jain, Venkatesh Balasubramanian, Bhanu Chunduri, and Manik Varma. Slice: Scalable linear extreme classifiers trained on 100 million labels for related searches. In WSDM '19 February / 11- 2019, Melbourne, VIC, Australia. ACM, February 2019.
[24] Eun Bac Kong and Thomas G. Dietterich. Error-correcting output coding corrects bias and variance. In In Proceedings of the Twelfth International Conference on Machine Learning, pages 313-321. Morgan Kaufmann, 1995.
[25] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[26] Marek Kubale and Boguslaw Jackowski. A generalized implicit enumeration algorithm for graph coloring. Commun. ACM, 28:412-418, 1985.
[27] Yann LeCun and Corinna Cortes. The mnist database of handwritten digits. 2005.
[28] Frank Thomson Leighton. A graph coloring algorithm for large scheduling problems. Journal of research of the National Bureau of Standards, 84 6:489-506, 1979.
[29] Jingzhou Liu, Wei-Cheng Chang. Yuexin Wu, and Yiming Yang. Deep learning for extreme multi-label text classification. In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '17, page 115-124, New York, NY, USA, 2017. Association for Computing Machinery.
[30] Mingxia Liu, Daoqiang Zhang, Songcan Chen, and Hui Xue. Joint binary classifier learning for based multi-class classification. IEEE Transactions Pattern Analysis and Machine Intelligence, 38(11): 2016.
[31] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. ArXiv, abs/1 706.06683, 2018.
[32] Enrico Malaguti, Michele Monaci, and Paolo Toth. An exact approach for the vertex coloring problem. Discrete Optimization, 8(2):174-190 2011.
[33] Miguel Ángel Bautista Martin, Oriol Pujol, Fernando De la Torre, and Sergio Escalera. Error- correcting factorization. IEEE Transactions on Puttern Analysis and Machine Intelligence, 40(10):2388-244 -20011 oct 2018.
[34] Garth P. Mccormick. Computability of global solutions to factorable nonconvex programs: Part
i convex underestimating problems. Math. Program., 10(1):147-175, dec 1976.
[35] Anuj Mehrotra and Michael A. Trick. A column generation approach for graph coloring. INFORMS Journal on Computing, 8:344-354, 1995.
12

---

[36] Brendan O'Donoghue, Eric Chu, Neal Parikh, and Stephen Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications, 169(3):1042-1068, June 2016.
[37] Morris Plotkin. Binary codes with specified minimum distance. IRE Trans. Inf. Theory, 6(4):445 450, 1960.
[38] Oriol Pujol, Sergio Escalera, and Petia Radeva. An incremental node embedding technique for correcting output codes. Pattern Recognition, 41:713-7255 02 2008
[39] Oriol Pujol, Petia Radeva, and Jordi Vitria. Discriminant ecoc: A heuristic method for applica- tion dependent design of eπrоr correcting output codes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(6):1007-1012 June 2006.
[40] Jie Qin, Li Liu, Ling Shao, Fumin Shen, Binghing Ni, Jiaxin Chen, and Yunhong Wang. Zero-shot action recognition with error-correcting output codes. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition (CVPR), July 2017.
[41] Ryan Rifkin and Aldebaro Klautau. In defense of one-vs-all classification. Journal of Machine Learning Research, 5:101-141, 2004.
[42] Hadi Salman, Andrew Iyas, Logan Engstrom, Ashish Kapoor, and Aleksander Madry. Do adversarially robust imagenet models transfer better? In H. Larochelle, M. Ranzato, R. Had- sell, M.F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 3533-3545. Curran Associates, Inc., 2020.
[43] Yang Song, Qiyu Kang, and Wee Peng Tay. Error-correcting output codes with ensemble diversity for robust learning in neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 35(1 1):9222-9729, May 2021.
[44] Jonathan S Turner. Almost all k-colorable graphs are easy to color. In: J. Algorithms, pages 0196-6774, 1988.
[45] Francisco Utrera, Evan Kravitz, N. Benjamin Erichson, Rajiv Khanna, and Michael W. Ma- honey. swversarially-traine deep nets transfer better: Illustration image classification. In International Conference on Learning Representations, 2021.
[46] Gunjan Verma and Ananthram Swami. Error correcting output codes improve probability esti- mation and adversarial robustness of deep neural networks. In Advances Neural Information Processing Systems 32, pages 8646-8656. 2019.
[47] Xiao Zhang, Lin Liang, and Heung- Yeung Shum. Spectral error correcting output codes for efficient multiclass recognition. In 2009 IEEE 12th International Conference on Computer Vision, pages 11 1111-1118, 2009.
[48] Ian En-Hsa Yen, Xiangru Huang, Pradeep Ravikumar, Kai Zhong, and Inderjit Dhillon. Pd- sparse: : A primal and dual sparse approach to extreme multiclass and multilabel classification. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 0069-3077, New York, New York, USA, 20 22 Jun 2016. PMLR.
[49] B. Zhao and F. Xing. Sparse output coding for large-scale visual recognition. In 2013 IEEE Conference on Computer Vision and Pattern Recognition, pages 3350-3357, 2013.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "yXXeGeg441", "reviewer": "Reviewer_t9cy", "summary": "To solve the problems of prior works (e.g., limited to codebooks with small number of rows (classes) or columns), the authors develop a codebook design approach based on a Mixed-Integer Quadratically Constrained Program (MIQCP). Correspondingly, a novel and efficient algorithm to solve large instances of the MIQCP is proposed, that is, it incrementally increases the codebook size by adding columns to maximize the gain in error-correcting capability.", "questions": "The detailed questions follow:\n\n1. This paper emphasizes that the previous approaches have the limitation ``the size of the codebook (i.e. number of columns L) is small\".\nHow do the authors judge whether $L$ is small? If $L<2k$, is $L$ small? To distinguish your work from previous works, can you give a sensible judgment criterion?\n\n2. Line 142: this paper emphasizes ``the error correcting capability ... by increasing the number of columns\". Does that mean that bigger $L$ is better? Does a very large $L$ have a negative effect on the classification performance? Is there a limit on the upper bound of $L$ in this paper?\n\n3. Given the codebook $\\mathcal{M}$, the training data and a test example $x$, how are the binary classifiers $f_1(x),\\ldots,f_L(x)$ determined or obtained?\n\n4. Are the parameters $\\rho_1$, $\\rho_2$ and $\\gamma$ in $\\mathcal{IP}$1 and $\\mathcal{IP}$2 given in advance? Does the choice of these parameters affect the classification performance? Do they affect the optimality of the algorithm? Moreover, in section 5, the specific values of the parameters $\\rho_1$, $\\rho_2$, and $\\gamma$ is not clear.\n\n5. For $\\tilde{l}\\in\\{1,2,3,4\\}$, the authors give the upper bounds of $\\kappa_{\\tilde{M}}$ in Theorem 3. For any $\\tilde{l}$, can you give a general expression with the detailed proof?\n\n6. For the computation in Table 1, is $\\mathcal{M}$ given in advance? What is the exact structure of $\\mathcal{M}$? Furthermore, is it possible that $\\mathcal{G}_{\\mathcal{M}}$ is not sparse?  If so, will the computation be slow?\n\n7. How to ensure that the proposed algorithm is near-optimal? Please give a detailed explanation. Moreover, is the codebook obtained by the proposed algorithm very close to the solution of $\\mathcal{IP}$1?\n\n8. In this paper, the $L$ is given in advance. Can an optimal $L$ in some sense (e.g., minimizing the classification error) be obtained? It would be great if the authors could develop an algorithm or give a theoretical guidance to derive an optimal $L$.\n", "limitations": "Limitations are discussed above. I do not see any societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is very well-written and easy to read. For the large multi-class problem instances, this paper propose a novel approach to effectively solve the codebook design problem.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "aqY6uBlGZRm", "reviewer": "Reviewer_WaNX", "summary": "This paper is about generating high-quality error-correcting output codes for multi-class classification. Based on the concept of Hamming distance of a codebook, it formulates this problem as solving a non-convex mixed integer quadratic constrained program. In addition to converting the bilinear constraints to linear ones, it proposes an iterative greedy approach and cleverly views the resulting sub-problem as a graph-coloring task, leading to an efficient solution. Experimental study on several datasets shows the computational advantage and effectiveness of the proposed work.  ", "questions": "This is an overall excellent work. Meanwhile, the following issues can be addressed.\n\n1. This work mentioned in several places that the proposed greedy approach is a \"near-optimal\" solution to the codebook design problem. It will be better to give a clear definition or criterion on the \"near-optimality.\" \n\n2. How to set the value of $\\rho_1$ and $\\rho_2$ in Eq.(1c)? What is their impact to the quality of the obtained codebook? This could be discussed in the experimental study.\n\n3. In Line 127, it is mentioned that \"Since $L \\approx k.$\" Where is this condition from? Please clarify. \n\n4. It will be good to provide a formal computational complexity analysis for Algorithm 1. \n\n5. In the last line of Theorem 3, it shows that $\\kappa_\\tilde{\\mathcal M}\\leq\\kappa_{\\mathcal M}$ if $\\xi({\\mathcal G}_{\\mathcal M})\\geq{5}$. \n\nCombining this result with Lemma 2, does this mean actually $\\kappa_\\tilde{\\mathcal M}$=$\\kappa_{\\mathcal M}$ in this case? Please clarify. \n\n6. The improvement over other methods in comparison seems to be marginal. Can the improvements pass the statistical significant test? ", "limitations": "The limitations and potential negative societal impact are discussed in Section 6. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Error-correcting output coding (ECOC) is an important mechanism in many tasks including multi-class classification. An advance in achieving high-quality large-scale ECOC design has both theoretical and practical significance. \n\n2. The proposed approach is neat, clever and elegant, leading to a simple and efficient solution. \n\n3. Experiments demonstrate the efficacy of the proposed algorithm.\n\n4. The paper is well organised and presented. \n\nWeaknesses:\n\n1.  Some claims can be better clarified or justified.\n\n2. The improvement seems to be marginal with respect to other multi-class classification methods.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UX5mhhTa_0a", "reviewer": "Reviewer_FwJk", "summary": "The paper proposes a way to design dataset-independent error-correcting codebooks with good error-correcting properties.  \n\nThe suggested approach (naturally) formulates a *discrete* optimization problem. Rather than solving the problem using continuous relaxations (like most of the existing literature), the authors follow a recent work *[Gupta & Amin 2021]* and use Integer Programming (IP) to solve the optimization problem. They solve that problem using a *greedy* algorithm that solves smaller IP problems until a codebook with the required amount of columns (bits) is obtained.  \nThe algorithm proposed here scales better with the number of columns and yields good codebooks even when other algorithm become infeasible.\n\nThe experimental setup establishes that the resulted codebooks are nearly optimal (in the sense of their minimal Hamming row distance) and are useful for classification setups.", "questions": "1. **Fixable readability issues.** Personally, I found Pages 4-6 difficult to read and hard to follow. In Page 6 I already felt lost and had to stop, re-read, and think for a few minutes until I realized what is happening.  \nAt this point it's probably trivial for the authors, but as a reader I think the connection to the graph coloring problem should be presented more carefully.  \nA few specific issues:\n    - I had a hard time understanding why would different vertices get the same codeword (Lines 209-210). It is worth stressing out that the discussed codewords are only the ones of length $\\tilde{l}$ that are being concatenated to the existing (full) codewords.  \n    - Proposition 2 is presented as a direct consequence of the two observations above it, but it is not completely clear how are they related. Also unclear why is this Proposition important or interesting.   \n    - The upper bound in Theorem 3 is hard to understand.\n    - Unclear how $\\tilde{l}$ is chosen/tuned in Step 5 of Algorithm 1.\n\n1. In Lines 300-301 and Table 4 it is reported that multiclass (Softmax) CNNs have a comparable performance to that of the Greedy codebook. If I understand correctly, this happens even though the traditional multiclass approach only requires one network while the ECOC approach here is implemented with $L$ networks.  \nIf that is indeed the case - why should we use the Greedy codebook?\n\n1. In Tables 5-7, it is reported that the Greedy codebook outperforms the multiclass approach significantly. Again, it seems like the greedy ECOC approach uses $L$ networks while the multiclass approach uses only a single network. If that is indeed the case - is this comparison even fair?\n\n1. In Table 1: \n    - Are these averages of several runs? How many? What is the STD?\n    - How should we expect the time to increase with $k$? What will happen if we use this approach for $k>10K$ like in extreme classification papers? *[See for instance \"Learning compact class codes for fast inference in large multi class classification\" by Cisse et al. 2012]*\n\n1. It seems odd that in Table 4 the performance of the greedy algorithm is the exact same as the performance of [Gupta and Amin 2021]. Is there a reason for it?\n\n1. In the classification performance experiments (Section 5.1): Which ECOC decoding scheme is used? Specifically, which decoding scheme is used for 1-vs-1? Do you ignore the prediction magnitudes? ", "limitations": "Addressed properly.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# (A) Strengths\n\n1. **Proposed algorithm improves upon an existing method.** The paper proposes an approach that solves the scalability issues of a recent work by *[Gupta and Amin 2021]*, by using graph coloring techniques instead of edge cover ones.  \n Both papers are rather unique in the sense that they tackle the codebook design problem using discrete methods instead of continuous relaxations, providing another perspective on designing codebooks.  \n  \n\n----\n  \n\n# (B) Weaknesses\n\n1. **Missing important/natural baseline for classification performance in Tables 4 and 7.** I would expect the experiments to compare to the performance of (truncated) Hadamard codebooks *[See for instance \"Fix your classifier\" by Hoffer et al. 2018]*. Hadamard codebooks should have almost optimal error-correcting properties and may be decent competitors to the suggested approach.  \nSince the proposed approach here is dataset-independent, I cannot immediately see why this approach would be favorable over Hadamard codebooks.\n\n\n1. **Missing baseline for error-correcting capabilities in Table 2.** I believe that Dense random codebooks should also be compared to the ones created using the proposed Greedy algorithm, since random codebooks usually exhibit good error-correcting capabilities (and specifically, a good minimum distance when $L\\ge k$).\n\n\n1. **Some missing/unjustified \"goals\" in main Problem Formulation (Section 3).**\n     - The authors claim that *\"a good column separation is desirable in order to avoid correlations between the resulting hypotheses\"*. I agree.  \nHowever, one should also consider the separation between the set of columns and the set of their binary complements. For instance, if there exists a pair of columns in the matrix such that one of them is the exact complement of the other, then they induce the same binary classification problem and will yield two completely correlated classifiers.  \nIdeally this should be part of the formulation and the subsequent integer programs. But at least it should be mentioned and/or its absence should justified.\n     - The authors also claim that *\"every column in the codebook should result in a balanced binary classification problem\"*.  \nWhile I agree that this may help a codebook's error-correcting properties, its effect on an ECOC multiclass classification scheme is not *that* simple.  \nOn the one side, imbalanced binary problems might suffer statistical drawbacks. But on the other side, imbalanced problems (in the sense of few classes vs. the rest) can be *much* easier to solve, especially when the basis classifiers are not very complex (e.g. linear models). This phenomenon can explain the historic success of OVA when compared to other ECOC schemes *[as was already pointed out by Allwein et al. 2000; see also Rifkin & Klautau 2004]*. Another paper *[Evron et al. 2018]* also pointed out that the column imbalance can actually be beneficial for learning.  \n\n\n---\n\n# (C) Minor remarks\n\nI don't expect a response on these issues but I advise fixing them.\n\n1. In Line 307 the authors say that the computational expense of training $L$ separate neural networks is an inherent limitation of ECOC classifiers, but there were already several of other papers that used ECOC as an output layer of a **single** neural network *[e.g. \"Beyond One-hot Encoding\" by Rodriguez et al. 2018]*.\n\n1. References to the supplementary material (\"SI\") should at least refer to specific sections.\n\n1. I believe the models used for the experiments should be briefly explained in the main manuscript and not only in the supplementary material.\n\n1. Typos: \n   - In many places (e.g., line 200&201) the authors write \"atleast\" or \"atmost\". I believe the correct forms are \"at least\" and \"at most\".\n   - Line 188: \"pairs decides\" => \"pairs decide\"\n   - Line 192: redundant parenthesis \")\"\n   - Line 217: \"than size\" => \"than the size\"\n   - Line 240: unclear what the double dashes mean.\n\n1. Generally - it's unclear why you almost always consider codebooks where $k<L$.\n\n1. Should probably have a more thorough discussion on the relations to *[Gupta and Amin 2021]* and the differences between the two papers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept