TL;DR
When using pre-trained deep neural networks as feature extractors, bigger isn't always better for distance-based classification. This paper demonstrates that segmenting high-dimensional feature vectors into smaller subvectors and performing independent nearest-neighbor searches—then aggregating the results via a majority vote—significantly improves classification accuracy over using the full vector at once.
What Problem Does This Paper Address?
Transfer learning has become the standard for solving niche AI problems. Instead of training a massive model from scratch, we use a pre-trained Deep Neural Network (DNN) to extract "features" (high-dimensional vectors) and then use a simple classifier like $k$-Nearest Neighbors ($k$-NN) to categorize them.
However, there is a catch: DNNs are usually trained on massive, general datasets (like ImageNet). When you apply those features to a specific, different task, a large portion of the feature vector might be "useless" or irrelevant noise for that specific task. In high-dimensional spaces, this noise accumulates, causing the standard Euclidean distance to fail—a phenomenon often related to the "curse of dimensionality." The authors investigate whether we can mitigate this by breaking the vector apart.
Methods
The authors propose a technique called $c$-segmentation.
- Splitting: A feature vector of dimension $d$ is split into $c$ equal-sized segments (subvectors) of dimension $d/c$.
- Independent Search: For a new test sample, a $k$-NN search is performed independently within each of the $c$ subspaces using a dictionary of known examples.
- Voting: Each subspace "votes" for a class based on its local nearest neighbor.
- Aggregation: The final classification is determined by a majority vote across all $c$ segments.
This is mathematically similar to the structure of Product Quantization (PQ), but notably, the authors show that the benefit comes from the segmentation itself, even without the data compression typically associated with PQ. They provide a rigorous mathematical framework using large deviation theory to show that if information is "sparse" (concentrated in a few coordinates), segmentation allows the "signal" to outvote the "noise."
Datasets
The researchers evaluated their method using three different DNN architectures across four datasets:
- Feature Extractors: Inception V3 (2,048 dimensions), SqueezeNet (1,000 dimensions), and a model trained on AudioSet (1,280 dimensions).
- Vision Datasets:
- CIFAR10: Low-resolution images (32x32) very different from the high-res images used to train the DNNs.
- ImageNet1 & ImageNet2: Subsets of 10 classes each, sampled from ImageNet but specifically excluding classes used during the initial DNN training.
- Audio Dataset: A subset of 10 classes from AudioSet (e.g., "cat," "fireworks," "snoring").
Key Insights and Ideas
- The "Noise" Problem: In high dimensions, if two classes differ only in a few coordinates, the cumulative noise from the thousands of other "matching" coordinates can easily overwhelm the Euclidean distance, leading to misclassification.
- Robustness through Voting: By segmenting the vector, the "correct" coordinates are isolated into specific segments. While the "noisy" segments might return random results, the "informative" segments will consistently vote for the correct class, allowing the signal to win the majority vote.
- Zero Computational Cost: Surprisingly, this method doesn't increase the number of operations or memory usage. Calculating the distance of one 1,000-D vector is computationally equivalent to calculating the distances of ten 100-D vectors.
- Alternative to $k$: The authors suggest that increasing the number of segments ($c$) can be viewed as an alternative to increasing the number of neighbors ($k$) to achieve better robustness.
Key Results
The experiments consistently showed that an intermediate number of segments ($c > 1$) yielded the best results.
- Inception V3 on CIFAR10: Accuracy improved from 85.19% ($c=1$, the baseline) to 87.81% ($c=16$).
- SqueezeNet on CIFAR10: A significant jump from 68.39% ($c=1$) to 74.72% ($c=20$).
- AudioSet: The best performance was found at $c=40$, where 1-NN accuracy rose from 60.5% to 72.4%.
In almost every scenario, the "naive" approach of using the full vector ($c=1$) was outperformed by a segmented approach. However, if $c$ becomes too large (e.g., $c=256$), accuracy begins to drop again as the segments become too small to contain meaningful patterns.
Limitations and Future Work
The authors acknowledge that their current study focuses on non-parametric methods like $k$-NN. While $k$-NN is excellent for "incremental learning" (adding new classes or examples on the fly), it isn't always the most powerful classifier.
Future Work includes: * Testing whether vector segmentation provides similar boosts to other downstream classifiers like Support Vector Machines (SVMs) or Logistic Regression. * Exploring more sophisticated ways to determine the optimal number of segments ($c$) automatically based on the dataset properties.
Summary updated