# Integer Programming-based Error-Correcting Output Code Design for Robust Classification

arXiv: https://arxiv.org/abs/2011.00144 · HTML: https://mlsanity.com/paper/2011.00144/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2020.

## Built on by (most cited first, 2 of 2)

- [The Role of Codeword-to-Class Assignments in Error-Correcting Codes: An Empirical Study](https://mlsanity.com/paper/2302.05334/) (2023)
- [Improved Robustness Against Adaptive Attacks With Ensembles and Error-Correcting Output Codes](https://mlsanity.com/paper/2303.02322/) (2023)

## Abstract (arXiv)

Error-Correcting Output Codes (ECOCs) offer a principled approach for combining simple binary classifiers into multiclass classifiers. In this paper, we investigate the problem of designing optimal ECOCs to achieve both nominal and adversarial accuracy using Support Vector Machines (SVMs) and binary deep learning models. In contrast to previous literature, we present an Integer Programming (IP) formulation to design minimal codebooks with desirable error correcting properties. Our work leverages the advances in IP solvers to generate codebooks with optimality guarantees. To achieve tractability, we exploit the underlying graph-theoretic structure of the constraint set in our IP formulation. This enables us to use edge clique covers to substantially reduce the constraint set. Our codebooks achieve a high nominal accuracy relative to standard codebooks (e.g., one-vs-all, one-vs-one, and dense/sparse codes). We also estimate the adversarial accuracy of our ECOC-based classifiers in a white-box setting. Our IP-generated codebooks provide non-trivial robustness to adversarial perturbations even without any adversarial training.