Abstract
To achieve a good trade-off between recognition accuracy and computational efficiency, it is often needed to reduce high-dimensional visual data to medium-dimensional ones. For this task, even applying a simple full-matrix-based linear projection causes significant computation and memory use. When the number of visual data is large, how to efficiently learn such a projection could even become a problem. The recent feature merging approach offers an efficient way to reduce the dimensionality, which only requires a single scan of features to perform reduction. However, existing merging algorithms do not scale well with high-dimensional data, especially in the unsupervised case. To address this problem, we formulate unsupervised feature merging as a PCA problem imposed with a special structure constraint. By exploiting its connection with k-means, we transform this constrained PCA problem into a feature clustering problem. Moreover, we employ the hashing technique to improve its scalability. These produce a scalable feature merging algorithm for our dimensionality reduction task. In addition, we develop an extension of this method by leveraging the neighborhood structure in the data to further improve dimensionality reduction performance. In further, we explore the incorporation of bipolar merging - a variant of merging function which allows the subtraction operation - into our algorithms. Through three applications in visual recognition, we demonstrate that our methods can not only achieve good dimensionality reduction performance with little computational cost but also help to create more powerful representation at both image level and local feature level.
Introduction
In modern computer vision, images are often represented using high-dimensional vectors such as Fisher Vectors or large histograms (e.g., 65,536 dimensions). While these representations provide high accuracy, they present significant challenges for computational efficiency and memory storage. Traditional dimensionality reduction techniques like Principal Component Analysis (PCA) require storing massive projection matrices and performing millions of multiplications per sample, which is often prohibitive for real-time systems or mobile devices.
This paper presents a scalable, unsupervised "feature merging" approach as an efficient alternative. By reframing feature merging as a constrained optimization problem, the authors provide a method to reduce data dimensionality using a simple lookup-and-sum strategy. This approach is orders of magnitude faster and more memory-efficient than PCA while maintaining comparable classification performance.
Methodology
The core innovation of this work is the theoretical connection established between optimal feature merging and PCA. The authors prove that finding the optimal merging matrix is equivalent to a PCA problem with specific structural constraints, which can be solved by performing $k$-means clustering on the features themselves.
Key Innovations
- PCA-Clustering Equivalence: The task of finding the best feature groups is transformed into a feature clustering problem, where each feature's values across all samples are treated as a data point.
- Scalability via Hashing: To handle massive datasets, the authors employ a hashing technique to create a "signature matrix." This allows clustering to be performed on a compressed version of the data, making the algorithm's complexity independent of the number of samples.
- Pseudo-supervised Kernel Alignment (PKA): To improve unsupervised merging, the authors use the "manifold assumption"—that neighboring samples in the original space likely belong to the same class—to generate pseudo-labels that guide the reduction process.
- Bipolar Merging: This extension allows for subtraction during the merging process, helping to handle negatively correlated features that might otherwise cancel each other out.
Experimental Results
The proposed methods were evaluated on several standard benchmarks, including Scene-15, Pascal VOC 2007, and Caltech-UCSD Birds-200-2011.
Efficiency and Accuracy Trade-offs
As shown in the experimental data, the Basic Merging (BSC) approach and its variants significantly outperform traditional methods in terms of resource usage. While PCA memory requirements can exceed 1GB for high-dimensional tasks, the merging approach typically requires less than 100KB.
In terms of speed, merging is essentially a "lookup table" operation, requiring only a single scan of features. Despite this efficiency, the accuracy remains competitive. On the Scene-15 dataset, the merging approach outperformed Hashing and was comparable to PCA, especially at higher reduced dimensions where PCA is prone to overfitting. Furthermore, when applied to high-dimensional local features (HDLF) on the Birds dataset, the method achieved a 6% improvement in mAP compared to standard lower-dimensional baselines.
Conclusion
This research demonstrates that unsupervised feature merging is a powerful and scalable tool for dimensionality reduction. By leveraging the connection between PCA and clustering, the authors provide a framework that balances the high accuracy of complex visual representations with the practical constraints of real-world computing environments. While some extensions like PKA introduce additional overhead for graph construction, the overall efficiency gains make this approach highly suitable for large-scale visual recognition tasks.
Summary updated