An Information-Theoretic Explanation for the Adversarial Fragility of AI Classifiers

Hui Xie, Jirong Yi, Weiyu Xu, Raghu Mudumbai

TL;DR

This paper argues that the "adversarial fragility" of AI classifiers is an unavoidable side effect of their need to compress high-dimensional input data to generalize. By modeling classifiers as communication decoders, the authors prove that models robust to random noise are mathematically destined to be vulnerable to small, targeted perturbations, and they propose a defense strategy based on reconstructing inputs from predicted labels to detect inconsistencies.

What Problem Does This Paper Address?

AI classifiers often exhibit a baffling contradiction: they are remarkably robust to random noise (like static in an image) but can be completely derailed by "adversarial attacks"—tiny, calculated tweaks to an input that are invisible to humans but force the model to output a specific wrong label.

While various theories exist (e.g., the "linearity" of models or the "curvature" of decision boundaries), there is no consensus on why this fragility seems to be a universal property of AI. The authors address this by proposing a unifying "compression hypothesis." They argue that because a good classifier must ignore irrelevant features to generalize, it inherently reduces the dimensionality of the input. This very act of compression creates the mathematical "room" for adversarial attacks to hide.

Methods

The authors frame the problem using an analogy to the standard Shannon model of a communication system. In this view, a classifier is a decoder trying to recover a "message" (the label) from a noisy "signal" (the input).

Comparison between a communication system and an AI classifier.

Key methodological components include:

  • The Compression Hypothesis: They assume the classifier output is a function of a highly compressed intermediate variable $z$ with dimension $M$, where $M$ is much smaller than the input dimension $N$.
  • Information-Theoretic Proofs: Using tools like the Moore-Penrose inverse and concentration of measure on the Grassmannian, they prove that for linear compression functions, the magnitude of a successful adversarial attack can be significantly smaller than the magnitude of random noise required to flip a label. Specifically, the gap is related to the ratio $\sqrt{M/N}$.
  • Nonlinear Extension: They extend this logic to nonlinear classifiers by analyzing the Jacobian matrix of the compression function, showing that the vulnerability persists as long as the model performs significant dimension reduction.
  • Consistency-Based Defense: They propose a defense mechanism that "decompresses" the classifier's output using a generative model and compares this reconstruction to the original input. If the two don't match (low correlation), an attack is detected.
The proposed consistency check defense.

Datasets

The paper primarily focuses on theoretical proofs, but it validates the defense using a voice recognition task:

  • Source Data: Sentences randomly selected from Charles Dickens' A Tale of Two Cities.
  • Models: The Mozilla DeepSpeech (v0.1.1) speech-to-text engine.
  • Generative Model: The Pico2wave Linux text-to-speech (T2S) engine was used as the "decoder" to reconstruct audio from the predicted text.
  • Attack Method: Nicholas Carlini’s adversarial attack script for DeepSpeech.

Key Insights and Ideas

  • Fragility as a Feature, Not a Bug: The paper suggests that adversarial vulnerability isn't necessarily a result of poor training or specific architectures, but a fundamental mathematical consequence of dimension reduction. To be good at generalizing, a model must be fragile.
  • The Dimensionality Gap: The core "aha moment" is the mathematical demonstration that an attacker only needs to perturb the input in the specific low-dimensional subspace that the classifier actually "sees." Because this subspace is so small compared to the total input space, the required perturbation can be tiny.
  • Analysis-by-Synthesis: The proposed defense turns the classifier's "blindness" against the attacker. While the classifier might be fooled by a small tweak, a generative model tasked with recreating the entire input from the label will produce something that looks nothing like the adversarially-tweaked original.

Key Results

  • Theoretical Bound: The authors show that for a classifier with input dimension $N$ and compressed dimension $M$, an adversarial attack can be roughly $\sqrt{N/M}$ times smaller than the random noise the model can tolerate.
  • Experimental Validation: In the audio experiments, adversarial perturbations were generated at a power level of ~35 dB SNR relative to the signal. While these successfully fooled DeepSpeech into transcribing completely different sentences, the consistency check (cross-correlation) easily distinguished them.
  • Detection Performance: As shown in Figure 4 (below), clean signals (blue circles) typically showed high correlation with their reconstructions, while adversarial signals (red triangles) consistently fell below the detection threshold.
Cross-correlation results showing clear separation between clean and adversarial audio samples.

Limitations and Future Work

  • Generative Model Quality: The defense relies heavily on having a high-quality generative model (like a GAN or T2S engine) that can accurately "decompress" the label. For many complex domains, such models are difficult to design.
  • Computational Overhead: Running a generative model for every classification step adds significant latency and computational cost.
  • Generalization of Theory: While the linear case is proven rigorously, the nonlinear case relies on assumptions about the Jacobian matrix that may not hold for all neural network architectures.
  • Future Directions: The authors suggest that the main challenge moving forward is designing robust generative models that can implement this defense for general AI systems beyond audio and simple images.

Summary updated

Abstract

We present a simple hypothesis about a compression property of artificial intelligence (AI) classifiers and present theoretical arguments to show that this hypothesis successfully accounts for the observed fragility of AI classifiers to small adversarial perturbations. We also propose a new method for detecting when small input perturbations cause classifier errors, and show theoretical guarantees for the performance of this detection method. We present experimental results with a voice recognition system to demonstrate this method. The ideas in this paper are motivated by a simple analogy between AI classifiers and the standard Shannon model of a communication system.
BibTeX
@inproceedings{xie2019information,
  author = {Hui Xie and Jirong Yi and Weiyu Xu and Raghu Mudumbai},
  title = {{An Information-Theoretic Explanation for the Adversarial Fragility of AI Classifiers}},
  booktitle = {ISIT},
  year = {2019},
  url = {https://openreview.net/forum?id=R0NxBkByxZ},
}
Figure