Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.  
strengths_and_weaknesses: Strengths:

1. 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. 

2. The proposed approach is neat, clever and elegant, leading to a simple and efficient solution. 

3. Experiments demonstrate the efficacy of the proposed algorithm.

4. The paper is well organised and presented. 

Weaknesses:

1.  Some claims can be better clarified or justified.

2. The improvement seems to be marginal with respect to other multi-class classification methods.
questions: This is an overall excellent work. Meanwhile, the following issues can be addressed.

1. 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." 

2. 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.

3. In Line 127, it is mentioned that "Since $L \approx k.$" Where is this condition from? Please clarify. 

4. It will be good to provide a formal computational complexity analysis for Algorithm 1. 

5. 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}$. 

Combining this result with Lemma 2, does this mean actually $\kappa_\tilde{\mathcal M}$=$\kappa_{\mathcal M}$ in this case? Please clarify. 

6. 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes a way to design dataset-independent error-correcting codebooks with good error-correcting properties.  

The 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.  
The algorithm proposed here scales better with the number of columns and yields good codebooks even when other algorithm become infeasible.

The 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.
strengths_and_weaknesses: # (A) Strengths

1. **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.  
 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.  
  

----
  

# (B) Weaknesses

1. **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.  
Since the proposed approach here is dataset-independent, I cannot immediately see why this approach would be favorable over Hadamard codebooks.


1. **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$).


1. **Some missing/unjustified "goals" in main Problem Formulation (Section 3).**
     - The authors claim that *"a good column separation is desirable in order to avoid correlations between the resulting hypotheses"*. I agree.  
However, 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.  
Ideally 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.
     - The authors also claim that *"every column in the codebook should result in a balanced binary classification problem"*.  
While I agree that this may help a codebook's error-correcting properties, its effect on an ECOC multiclass classification scheme is not *that* simple.  
On 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.  


---

# (C) Minor remarks

I don't expect a response on these issues but I advise fixing them.

1. 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]*.

1. References to the supplementary material ("SI") should at least refer to specific sections.

1. I believe the models used for the experiments should be briefly explained in the main manuscript and not only in the supplementary material.

1. Typos: 
   - 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".
   - Line 188: "pairs decides" => "pairs decide"
   - Line 192: redundant parenthesis ")"
   - Line 217: "than size" => "than the size"
   - Line 240: unclear what the double dashes mean.

1. Generally - it's unclear why you almost always consider codebooks where $k<L$.

1. Should probably have a more thorough discussion on the relations to *[Gupta and Amin 2021]* and the differences between the two papers.
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.  
At 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.  
A few specific issues:
    - 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.  
    - 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.   
    - The upper bound in Theorem 3 is hard to understand.
    - Unclear how $\tilde{l}$ is chosen/tuned in Step 5 of Algorithm 1.

1. 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.  
If that is indeed the case - why should we use the Greedy codebook?

1. 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?

1. In Table 1: 
    - Are these averages of several runs? How many? What is the STD?
    - 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]*

1. 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?

1. 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
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.
questions: The detailed questions follow:

1. This paper emphasizes that the previous approaches have the limitation ``the size of the codebook (i.e. number of columns L) is small".
How 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?

2. 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?

3. 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?

4. 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.

5. 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?

6. 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?

7. 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?

8. 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$.

limitations: Limitations are discussed above. I do not see any societal impact.
review_title: null

Meta-review: metareview: The paper furthers the understanding of designing codebooks in the context of using Error correcting codes for Multi-class problems. As opposed to continuous relaxation, the state of the art, it advocates a graph colouring approach which finally yields an alternative to codebooks. To the best of understanding the methodology will be hard to apply for large number of classes. Though the experimental results only show marginal improvement,  the methods does improve upon the state of the art.

confidence: Certain
Decision: Accept