Introduction
Bilinear pooling, which calculates the outer product of local feature vectors, is a powerful technique for fine-grained image classification and texture recognition. By capturing complex second-order statistics, it excels at distinguishing subtle differences between categories. However, its primary drawback is the "curse of dimensionality": an input feature of dimension $d$ results in a bilinear feature of dimension $d^2$. For a standard 512-channel layer, this leads to over 262,000 dimensions, causing significant memory overhead and increasing the risk of overfitting.
While existing solutions like Random Maclaurin (RM) and Tensor Sketch (TS) attempt to approximate these features in lower dimensions, they face practical hurdles. RM requires massive projection matrices to maintain accuracy, while TS relies on sparse operations and Fast Fourier Transforms (FFTs) that perform poorly on modern GPUs. This paper introduces Shifted Random Maclaurin (SRM) and its evolution SRM+, designed to be both mathematically compact and computationally efficient on GPUs.
The FCBN Architecture
The authors integrate their proposed pooling methods into a Fast and Compact Bilinear Network (FCBN), which supports end-to-end training. The pipeline, illustrated below, demonstrates how local features are transformed into a compact representation while maintaining the benefits of matrix normalization.
Shifted Random Maclaurin (SRM and SRM+)
The core innovation is the "circular shift" trick. Standard RM approximates bilinear features by taking two random projections and multiplying them element-wise. SRM improves this by circularly shifting the second projection $K$ times. This generates $K$ different approximations for the price of one, reducing estimation variance by 40-50% with negligible extra computational cost.
SRM+ further refines this by working directly with the normalized bilinear matrix. Modern research indicates that matrix square root normalization is vital for performance. SRM+ is compatible with fast Newton-Schulz (NS) iterations for matrix square roots and requires only a single random projection, making it even faster than standard RM.
Comparative Analysis
Compared to other state-of-the-art bilinear pooling methods, FCBN offers a unique combination of desirable properties. As shown in the table below, it is the only method that is simultaneously compact, fast in pooling, supports normalization, and is fast in normalization.
Experimental Results
The authors evaluated FCBN on four benchmarks: CUB-200-2011 (birds), FGVC-Aircraft, MIT-67 (indoor scenes), and the Describable Texture Dataset (DTD).
- Efficiency and Speed: SRM+ is significantly faster than standard RM+. For a 4,000-dimensional feature, SRM+ takes only 7ms compared to RM+'s 29ms.
- Accuracy: On the CUB dataset, FCBN achieved 85.6% accuracy with only 4,000 dimensions. This matches the performance of Improved Bilinear Pooling (IBP), which requires a massive 262,000 dimensions.
- Variance Reduction: Theoretical proofs and empirical results confirm that SRM consistently achieves lower variance than RM, leading to more stable and accurate learning.
Conclusion and Future Work
Shifted Random Maclaurin provides a "free lunch" for variance reduction in bilinear pooling by leveraging circular shifts. While highly effective, the authors noted potential overfitting at very high shift factors ($K=8$) on certain datasets. Future research may explore more advanced projection types, such as sparse or quantized projections, and test the FCBN framework on modern backbones like Vision Transformers (ViTs).
Summary updated