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

• URL: http://arxiv.org/abs/2011.00144v1
• Date: Fri, 30 Oct 2020 23:35:18 GMT
• Title: Integer Programming-based Error-Correcting Output Code Design for Robust Classification
• Abstract summary: 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. Our work leverages the advances in IP solvers to generate codebooks with optimality guarantees.
• Score: 4.7464518249313805
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting [21.347076448562863]
  Coded computing has emerged as a powerful paradigm for mitigating the impact of straggling workers in distributed computing systems.<n>General Coded Computing (GCC) formulates coded computing through a natural end-to-end mean-squared error loss.<n>We establish theoretical performance under two complementary straggler regimes.
  arXiv  Detail & Related papers  (2026-08-28T22:18:22Z)
• Coset Ensemble Decoder for Quantum Error Correction with Algorithm-Hardware Co-Design [16.143601808851162]
  quantum error correction (QEC) continuously extracts and decodes error syndromes in real time.<n>A critical component in QEC is the decoder, a classical subsystem that must simultaneously deliver high logical accuracy and ultra-low latency.<n>This paper presents a novel algorithm-hardware co-design that improves the accuracy-latency trade-off over existing approaches.
  arXiv  Detail & Related papers  (2026-06-09T16:37:13Z)
• Optimal Circuit Synthesis of Linear Codes for Error Detection and Correction [11.02232592575343]
  Fault injection attacks deliberately inject faults into a device via physical channels to disturb its regular execution.<n>We formalize the optimal code circuit problem (OptiCC) based on two domain-specific minimization objectives on individual inputs and parity size.<n>We then propose a novel algorithm CiSC for solving OptiCC, prioritizing the minimization of individual inputs.
  arXiv  Detail & Related papers  (2026-04-04T06:46:43Z)
• Toward Uncertainty-Aware and Generalizable Neural Decoding for Quantum LDPC Codes [0.9453554184019106]
  Quantum error correction (QEC) is essential for scalable quantum computing.<n>We propose textbfQuBA, a Bayesian graph neural decoder that integrates attention to both dot-product and multi-head.<n>We further develop textbfSAGU textbf(Sequential Aggregate Generalization under Uncertainty), a multi-code training framework with enhanced cross-domain robustness.
  arXiv  Detail & Related papers  (2025-10-05T01:08:39Z)
• Exploiting Discriminative Codebook Prior for Autoregressive Image Generation [54.14166700058777]
  token-based autoregressive image generation systems first tokenize images into sequences of token indices with a codebook, and then model these sequences in an autoregressive paradigm.<n>While autoregressive generative models are trained only on index values, the prior encoded in the codebook, which contains rich token similarity information, is not exploited.<n>Recent studies have attempted to incorporate this prior by performing naive k-means clustering on the tokens, helping to facilitate the training of generative models with a reduced codebook.<n>We propose the Discriminative Codebook Prior Extractor (DCPE) as an alternative to k-means
  arXiv  Detail & Related papers  (2025-08-14T15:00:00Z)
• Contrastive ECOC: Learning Output Codes for Adversarial Defense [2.07180164747172]
  This paper introduces three models for automated codebook learning based on contrastive learning.<n>Our proposed models demonstrate superior robustness to adversarial attacks compared to two baselines.
  arXiv  Detail & Related papers  (2025-08-14T09:50:50Z)
• Approximate Size Targets Are Sufficient for Accurate Semantic Segmentation [52.239136918460616]
  Extending binary class tags to approximate relative object-size distributions allows off-the-shelf architectures to solve the segmentation problem. A straightforward zero-avoiding KL-divergence loss for average predictions produces segmentation accuracy comparable to the standard pixel-precise supervision. Our ideas are validated on PASCAL VOC using our new human annotations of approximate object sizes.
  arXiv  Detail & Related papers  (2025-03-10T06:02:13Z)
• Fundamental thresholds for computational and erasure errors via the coherent information [1.4767596539913115]
  We propose a framework based on the coherent information (CI) of the mixed-state density operator associated to noisy QEC codes. We show how to rigorously derive different families of statistical mechanics mappings for generic stabilizer QEC codes in the presence of both types of errors.
  arXiv  Detail & Related papers  (2024-12-21T18:30:30Z)
• Gaussian Mixture Vector Quantization with Aggregated Categorical Posterior [5.862123282894087]
  We introduce the Vector Quantized Variational Autoencoder (VQ-VAE) VQ-VAE is a type of variational autoencoder using discrete embedding as latent. We show that GM-VQ improves codebook utilization and reduces information loss without relying on handcrafteds.
  arXiv  Detail & Related papers  (2024-10-14T05:58:11Z)
• Zero-Shot Class Unlearning in CLIP with Synthetic Samples [0.0]
  We focus on unlearning within CLIP, a dual vision-language model trained on a massive dataset of image-text pairs. We apply Lipschitz regularization to the multimodal context of CLIP. Our forgetting procedure is iterative, where we track accuracy on a synthetic forget set and stop when accuracy falls below a chosen threshold.
  arXiv  Detail & Related papers  (2024-07-10T09:16:14Z)
• A Hard-to-Beat Baseline for Training-free CLIP-based Adaptation [121.0693322732454]
  Contrastive Language-Image Pretraining (CLIP) has gained popularity for its remarkable zero-shot capacity. Recent research has focused on developing efficient fine-tuning methods to enhance CLIP's performance in downstream tasks. We revisit a classical algorithm, Gaussian Discriminant Analysis (GDA), and apply it to the downstream classification of CLIP.
  arXiv  Detail & Related papers  (2024-02-06T15:45:27Z)
• GEC-DePenD: Non-Autoregressive Grammatical Error Correction with Decoupled Permutation and Decoding [52.14832976759585]
  Grammatical error correction (GEC) is an important NLP task that is usually solved with autoregressive sequence-to-sequence models. We propose a novel non-autoregressive approach to GEC that decouples the architecture into a permutation network. We show that the resulting network improves over previously known non-autoregressive methods for GEC.
  arXiv  Detail & Related papers  (2023-11-14T14:24:36Z)
• Label Encoding for Regression Networks [9.386028796990399]
  We introduce binary-encoded labels (BEL), which generalizes the application of binary classification to regression. BEL achieves state-of-the-art accuracies for several regression benchmarks.
  arXiv  Detail & Related papers  (2022-12-04T21:23:36Z)
• CLAWSAT: Towards Both Robust and Accurate Code Models [74.57590254102311]
  We integrate contrastive learning (CL) with adversarial learning to co-optimize the robustness and accuracy of code models. To the best of our knowledge, this is the first systematic study to explore and exploit the robustness and accuracy benefits of (multi-view) code obfuscations in code models.
  arXiv  Detail & Related papers  (2022-11-21T18:32:50Z)
• Robust Vector Quantized-Variational Autoencoder [13.664682865991255]
  We propose a robust generative model based on Vector Quantized-Variational AutoEncoder (VQ-VAE) In order to achieve robustness, RVQ-VAE uses two separate codebooks for the inliers and outliers. We experimentally demonstrate that RVQ-VAE is able to generate examples from inliers even if a large portion of the training data points are corrupted.
  arXiv  Detail & Related papers  (2022-02-04T05:51:15Z)
• One Loss for All: Deep Hashing with a Single Cosine Similarity based Learning Objective [86.48094395282546]
  A deep hashing model typically has two main learning objectives: to make the learned binary hash codes discriminative and to minimize a quantization error. We propose a novel deep hashing model with only a single learning objective. Our model is highly effective, outperforming the state-of-the-art multi-loss hashing models on three large-scale instance retrieval benchmarks.
  arXiv  Detail & Related papers  (2021-09-29T14:27:51Z)
• Ensemble Learning using Error Correcting Output Codes: New Classification Error Bounds [2.0242396022517752]
  We present new bounds on classification error rates for the error-correcting output code (ECOC) approach in machine learning. These bounds have exponential decay complexity with respect to codeword length and theoretically validate the effectiveness of the ECOC approach.
  arXiv  Detail & Related papers  (2021-09-18T16:47:57Z)
• Learning by Minimizing the Sum of Ranked Range [58.24935359348289]
  We introduce the sum of ranked range (SoRR) as a general approach to form learning objectives. A ranked range is a consecutive sequence of sorted values of a set of real numbers. We explore two applications in machine learning of the minimization of the SoRR framework, namely the AoRR aggregate loss for binary classification and the TKML individual loss for multi-label/multi-class classification.
  arXiv  Detail & Related papers  (2020-10-05T01:58:32Z)
• Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
  Partial-label learning (PLL) is a typical weakly supervised learning problem, where each training instance is equipped with a set of candidate labels among which only one is the true label. Most existing methods elaborately designed as constrained optimizations that must be solved in specific manners, making their computational complexity a bottleneck for scaling up to big data. This paper proposes a novel framework of classifier with flexibility on the model and optimization algorithm.
  arXiv  Detail & Related papers  (2020-02-19T08:35:15Z)
• Learning Autoencoders with Relational Regularization [89.53065887608088]
  A new framework is proposed for learning autoencoders of data distributions. We minimize the discrepancy between the model and target distributions, with a emphrelational regularization We implement the framework with two scalable algorithms, making it applicable for both probabilistic and deterministic autoencoders.
  arXiv  Detail & Related papers  (2020-02-07T17:27:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.