The Role of Codeword-to-Class Assignments in Error-Correcting Codes: An Empirical Study
This addresses a controversy in machine learning literature by demonstrating that assignment policies matter for performance, though it is incremental as it builds on existing ECC methods.
The paper tackles the problem of codeword-to-class assignments in error-correcting codes for multiclass classification, showing that similarity-preserving assignments improve generalization performance by making predefined codebooks problem-dependent without altering other properties.
Error-correcting codes (ECC) are used to reduce multiclass classification tasks to multiple binary classification subproblems. In ECC, classes are represented by the rows of a binary matrix, corresponding to codewords in a codebook. Codebooks are commonly either predefined or problem dependent. Given predefined codebooks, codeword-to-class assignments are traditionally overlooked, and codewords are implicitly assigned to classes arbitrarily. Our paper shows that these assignments play a major role in the performance of ECC. Specifically, we examine similarity-preserving assignments, where similar codewords are assigned to similar classes. Addressing a controversy in existing literature, our extensive experiments confirm that similarity-preserving assignments induce easier subproblems and are superior to other assignment policies in terms of their generalization performance. We find that similarity-preserving assignments make predefined codebooks become problem-dependent, without altering other favorable codebook properties. Finally, we show that our findings can improve predefined codebooks dedicated to extreme classification.