Fast and Compact Bilinear Pooling by Shifted Random Maclaurin

Tan Yu, Xiaoyun Li, Ping LiAAAI 2021 · DOI

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.

The architecture of the proposed Fast and Compact Bilinear Network (FCBN).

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.

Comparison of FCBN with other bilinear pooling methods across key performance and architectural criteria.

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

BibTeX
@inproceedings{yu2021fast,
  author = {Tan Yu and Xiaoyun Li and Ping Li},
  title = {{Fast and Compact Bilinear Pooling by Shifted Random Maclaurin}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i4.16435},
}
Figure