On Distributed Quantization for Classification

Osama A. Hanna, Yahya H. Ezzeldin, Tara Sadjadpour, Christina Fragouli, Suhas N. Diggavi

TL;DR

Most data compression focuses on reconstructing a signal as accurately as possible, but this paper argues that if your goal is classification, reconstruction is a waste of bits. By focusing on decision boundaries rather than signal fidelity, the authors develop distributed quantization schemes that achieve the same accuracy as traditional methods while using less than half the communication bandwidth.

What Problem Does This Paper Address?

In the world of the Internet of Things (IoT) and distributed sensing, we often have multiple sensors (nodes) collecting data that must be sent to a central "brain" for classification. Think of a set of medical sensors monitoring a patient or a group of cameras watching a factory floor.

The bottleneck is the communication constraint. Sending high-precision, raw data is expensive in terms of power and bandwidth. To solve this, we use quantization—mapping continuous values to a small set of discrete bits.

Traditionally, quantization is designed for reconstruction: making the received signal look as much like the original as possible (minimizing "distortion"). However, if the central node only needs to know "is this a gesture A or B?", it doesn't need a perfect picture. It only needs the details that distinguish A from B. This paper addresses the gap in designing distributed quantizers specifically for this classification task, where features are split across different, non-communicating nodes.

Methods

The authors tackle the problem from three angles: theoretical complexity, greedy algorithms, and deep learning.

  1. Complexity Analysis: They first prove that finding the absolute optimal distributed quantizer for classification is NP-hard and hard to approximate. This justifies the need for the heuristic and learning-based approaches that follow.
  2. Greedy Boundary Insertion (GBI): This is a data-driven algorithm that iteratively adds quantization boundaries. Instead of placing boundaries where data is most dense (the standard approach), GBI places them where they most reduce misclassification. A key innovation here is the "Purity Criterion"—a tie-breaking rule that favors boundaries that make it easier for future iterations to separate classes.
  3. Neural Representations (NN-REG & NN-GBI):
    • NN-REG: The authors train a neural network with a custom "quantization loss" term. This nudges the network to naturally output values close to discrete levels (like -1 and +1), making them easy to quantize without the "dead gradient" problem that usually breaks backpropagation in discrete systems.
  4. NN-GBI: A hybrid approach where they first learn a continuous representation, apply the GBI algorithm to find the best boundaries, and then fine-tune the whole system.

Datasets

The researchers evaluated their methods on two distinct types of data:

  • sEMG Dataset: Surface electromyographic signals from 8 sensors used to identify 6 different hand gestures. They simulated a distributed setup with 4 nodes, each handling 2 sensors.
  • CIFAR-10: A classic image classification benchmark (10 classes). To simulate a distributed environment, they split each 32x32 image into four quadrants, with each node seeing only one quadrant.

Key Insights and Ideas

  • The Boundary is Everything: Traditional quantization (like k-means) puts more "resolution" where the data is. Classification-aware quantization puts more resolution near the decision boundaries. If a data point is far from the boundary, the classifier doesn't need much detail to get it right.
  • Decomposability Matters: A centralized classifier might work great, but you can't always "split" its logic across independent sensors. The authors focus on quantizers that work locally at each node while still serving a global classification goal.
  • Reconstruction is a Distraction: The results for CIFAR-10 are particularly striking. Methods like VQ-VAE, which are world-class at reconstructing images, perform poorly at classification when bit budgets are very low because they spend their "bit budget" on textures and colors that don't help distinguish a "dog" from a "truck."

Key Results

  • Massive Bit Savings: On the sEMG gesture dataset, the proposed NN-GBI method achieved 97.3% accuracy using only 4 bits per encoder. For comparison, the reconstruction-based k-means approach only reached 66.7% with the same bit budget.
  • Efficiency Gains: On CIFAR-10, to reach ~50% accuracy, a centralized VQ-VAE required 200 bits. The authors' proposed methods achieved over 70% accuracy with only 12 bits total (3 bits per quadrant).
  • Performance Floor: Even at extremely low rates (1-2 bits per sensor), the classification-aware approach maintained usable accuracy, whereas traditional methods often collapsed toward random guessing.

Limitations and Future Work

  • Rectangular Constraints: The GBI algorithm creates rectangular (axis-aligned) quantization regions. While the neural network pre-processing helps "warp" the data to fit this, exploring more complex, non-rectangular distributed boundaries remains an open challenge.
  • Pretrained Dependency: The current framework assumes the classifier at the central node is pretrained and fixed. Future work could look at "end-to-end" joint optimization where the classifier and the distributed quantizers are trained simultaneously from scratch.
  • Scalability: While GBI is polynomial-time, its quadratic complexity relative to the number of training samples might require stochastic approximations (which the authors suggest) for truly massive datasets.

Summary updated

Abstract

We consider the problem of distributed feature quantization, where the goal is to enable a pretrained classifier at a central node to carry out its classification on features that are gathered from distributed nodes through communication constrained channels. We propose the design of distributed quantization schemes specifically tailored to the classification task: unlike quantization schemes that help the central node reconstruct the original signal as accurately as possible, our focus is not reconstruction accuracy, but instead correct classification. Our work does not make any a priori distributional assumptions on the data, but instead uses training data for the quantizer design. Our main contributions include: we prove NP-hardness of finding optimal quantizers in the general case; we design an optimal scheme for a special case; we propose quantization algorithms, that leverage discrete neural representations and training data, and can be designed in polynomial-time for any number of features, any number of classes, and arbitrary division of features across the distributed nodes. We find that tailoring the quantizers to the classification task can offer significant savings: as compared to alternatives, we can achieve more than a factor of two reduction in terms of the number of bits communicated, for the same classification accuracy.
BibTeX
@article{hanna2020distributed,
  author = {Osama A. Hanna and Yahya H. Ezzeldin and Tara Sadjadpour and Christina Fragouli and Suhas N. Diggavi},
  title = {{On Distributed Quantization for Classification}},
  journal = {IEEE J. Sel. Areas Inf. Theory},
  year = {2020},
  url = {https://openreview.net/forum?id=N-GXRzayLDh},
}

Loading related content...

Figure