Efficient Codebook and Factorization for Second Order Representation Learning

Pierre Jacob, David Picard, Aymeric Histace, Edouard Klein

TL;DR

This paper introduces Joint Codebook and Factorization (JCF), a method that makes high-performance "second-order" image representations practical for large-scale tasks. By combining mathematical factorization with a shared-projector codebook strategy, the authors achieve state-of-the-art image retrieval results while dramatically reducing the memory and computational overhead typically associated with bilinear pooling.

What Problem Does This Paper Address?

In computer vision, "first-order" representations (like Global Average Pooling) are standard but often fail to capture the complex interactions between features. "Second-order" methods, such as Bilinear Pooling, capture these interactions by computing the outer product of feature vectors, leading to much richer representations—especially for fine-grained tasks (e.g., distinguishing between bird species).

However, second-order methods face a "dimensionality explosion." A 512-dimensional feature vector becomes a 262,144-dimensional representation when squared. While "factorization" techniques can compress this, they often lose the benefits of codebook pooling (grouping similar features together before aggregating). Previous attempts to combine codebooks with second-order features resulted in models so massive they were "unreasonably large" for practical use. The authors aim to bridge this gap: providing the richness of second-order codebooks with the efficiency of first-order models.

Methods

The authors propose a two-step optimization to keep the model compact:

  1. Joint Codebook and Factorization (JCF-N): Instead of computing a massive covariance matrix and then projecting it, they use a rank-one factorization. They learn a projection matrix for each of the $N$ entries in a codebook. This allows the model to pool "like with like" (e.g., pooling "eye" features separately from "wing" features) without the quadratic memory cost.
  2. Sharing Projectors (JCF-N-R): This is the core innovation. The authors hypothesize that the projection matrices for different codewords are not all independent. Instead of learning $N$ unique projectors, they learn a small set of $R$ "basis" projectors. Each codeword then learns a linear combination of these shared bases.
  3. Standard approach: $O(d \cdot D \cdot N)$ parameters.
  4. JCF-N-R approach: Reduces this by a factor of $R/N$, where $R$ is much smaller than $N$.

The assignment to the codebook is handled via a "soft-max" over cosine similarities between extracted features and the learned codewords.

Datasets

The model was evaluated on three standard image retrieval benchmarks:

  • Stanford Online Products (SOP): A large-scale dataset of 120k images across 22k classes of furniture and home goods.
  • CUB-200-2011: A fine-grained dataset featuring 200 species of birds.
  • Cars-196: A fine-grained dataset featuring 196 classes of cars.

Key Insights and Ideas

  • Codebooks Prevent "Destructive Averaging": Global pooling often mashes unrelated features together, diluting the signal. Codebooks ensure that second-order statistics are only calculated over semantically similar regions.
  • Redundancy is an Opportunity: The most "aha" moment is the realization that we don't need a unique mathematical "lens" (projector) for every single cluster in the codebook. By sharing a pool of projectors, we can achieve nearly the same accuracy with a fraction of the parameters.
  • Task Agnosticism: Because the method focuses on the representation layer rather than a specific loss function, it can be dropped into various architectures (the authors tested it with VGG16 and ResNet50).

Key Results

The JCF model consistently outperformed existing state-of-the-art (SOTA) methods:

  • Stanford Online Products: JCF-32 achieved 77.4% Recall@1, surpassing the previous SOTA (HTL at 74.8%).
  • CUB-200-2011: JCF-32 reached 60.1% R@1, a significant jump over the previous best of 57.1%.
  • Efficiency: The "shared" version (JCF-32-8) used 4x fewer parameters than the full JCF-32 while still beating or matching almost all previous SOTA methods on SOP and CUB.

Limitations and Future Work

  • Sensitivity to Variety: On the Cars-196 dataset, the shared projector version (JCF-32-8) saw a significant performance drop compared to the full model (74.2% vs 82.6%). The authors suggest that the high visual variety in cars (colors, shapes, angles) might require more unique projections than birds or furniture do.
  • Linearity: The current sharing mechanism uses a simple linear projection. Future work could explore non-linear recombinations of the shared projectors to capture even more complex feature relationships.
  • Codebook Size: While 32 codewords worked well, the scaling behavior for much larger codebooks (e.g., 128 or 256) in even more complex datasets remains an open question.

Summary updated

Abstract

Learning rich and compact representations is an open topic in many fields such as object recognition or image retrieval. Deep neural networks have made a major breakthrough during the last few years for these tasks but their representations are not necessary as rich as needed nor as compact as expected. To build richer representations, high order statistics have been exploited and have shown excellent performances, but they produce higher dimensional features. While this drawback has been partially addressed with factorization schemes, the original compactness of first order models has never been retrieved, or at the cost of a strong performance decrease. Our method, by jointly integrating codebook strategy to factorization scheme, is able to produce compact representations while keeping the second order performances with few additional parameters. This formulation leads to state-of-the-art results on three image retrieval datasets.
BibTeX
@inproceedings{jacob2019efficient,
  author = {Pierre Jacob and David Picard and Aymeric Histace and Edouard Klein},
  title = {{Efficient Codebook and Factorization for Second Order Representation Learning}},
  booktitle = {ICIP},
  year = {2019},
  url = {https://openreview.net/forum?id=sRcmt2oxf8},
}

Loading related content...

Figure