PaperlayerView exact revision on arXiv

Source-linked AI summary

Is Attention Better Than Matrix Decomposition?

Zhengyang Geng, Meng-Hao Guo, Hongxu Chen, Xia Li, Ke Wei, Zhouchen Lin

arXiv:2109.04553v2cs.CVcs.LG

TL;DR

The paper examines whether self-attention is necessary for encoding long-distance dependencies and models global context as low-rank recovery. It turns matrix-decomposition optimization into Hamburger modules, which match or outperform attention across semantic segmentation and image generation when gradients are handled carefully.

  • Problem

    The paper asks whether hand-crafted self-attention is irreplaceable for modeling global context and long-distance dependencies.

  • Method

    The paper formulates global context learning as low-rank recovery and turns matrix-decomposition optimization algorithms into computational graphs for Hamburger modules.

  • Results

    Hamburgers perform competitively with state-of-the-art attention models, set records on PASCAL VOC and PASCAL Context segmentation, and surpass attention modules for ImageNet generation.

  • Takeaways & Limitations

    Matrix decomposition can provide a light global-context module with O(n) complexity for semantic segmentation and image generation.

  • Takeaways & Limitations

    Direct BPTT through Hamburger’s iterative optimization produces unstable gradients that harm performance, motivating one-step gradients.

Abstract

from arXiv · show

As an essential ingredient of modern deep learning, attention mechanism, especially self-attention, plays a vital role in the global correlation discovery. However, is hand-crafted attention irreplaceable when modeling the global context? Our intriguing finding is that self-attention is not better than the matrix decomposition (MD) model developed 20 years ago regarding the performance and computational cost for encoding the long-distance dependencies. We model the global context issue as a low-rank recovery problem and show that its optimization algorithms can help design global information blocks. This paper then proposes a series of Hamburgers, in which we employ the optimization algorithms for solving MDs to factorize the input representations into sub-matrices and reconstruct a low-rank embedding. Hamburgers with different MDs can perform favorably against the popular global context module self-attention when carefully coping with gradients back-propagated through MDs. Comprehensive experiments are conducted in the vision tasks where it is crucial to learn the global context, including semantic segmentation and image generation, demonstrating significant improvements over self-attention and its variants.

1 INTRODUCTION

The paper asks whether hand-crafted attention is indispensable for global context and proposes Hamburgers, which derive global-information architectures from matrix-decomposition optimization.

  • The paper questions whether hand-crafted attention is irreplaceable for modeling global context after self-attention demonstrated strong long-distance dependency modeling.
  • Hamburger models context discovery as low-rank recovery and uses matrix decomposition to factorize learned representations into sub-matrices that reconstruct a low-rank signal.
  • The approach includes Vector Quantization, Concept Decomposition, and Non-negative Matrix Factorization as matrix-decomposition foundations.
  • The method uses truncated backpropagation through time, or one-step gradients, instead of directly applying full BPTT to differentiate iterative optimization.
  • Hamburger performs competitively with state-of-the-art attention models, sets records on PASCAL VOC and PASCAL Context segmentation, and surpasses attention modules for ImageNet GAN generation.
  • The paper reports that optimization-designed Hamburger has O(n) complexity and surpasses various attention modules across semantic segmentation and image generation.

2 METHODOLOGY

The methodology replaces hand-crafted self-attention with global context modules designed from matrix-decomposition optimization. Hamburger factorizes representations, reconstructs low-rank structure, and uses one-step gradients to address unstable backpropagation through iterative optimization.

  • 2.1 WARM UP: Matrix decomposition recovers latent structure by factorizing observed representations into dictionary and code matrices, with noise discarded from the low-rank reconstruction.The recovered matrix satisfies rank(X̄) ≤ r, where r is much smaller than the feature dimensions.
  • 2.1 WARM UP: The paper formulates global context discovery as an optimization objective whose solving algorithm becomes the computational graph of a global information module.The objective combines reconstruction loss with regularization terms for dictionary D and codes C.
  • 2.2 PROPOSED METHOD: Hamburger applies linear lower and upper transformations around matrix decomposition, which computes a low-rank reconstruction and functions as a global nonlinearity.The lower transformation maps input Z into feature space, the decomposition recovers latent structure, and the upper transformation maps the extracted signal to the output.
  • 2.2 PROPOSED METHOD: VQ, CD, and NMF provide alternative matrix-decomposition implementations based mainly on matrix multiplications, with O(ndr) complexity versus O(n^2d) for self-attention.They also avoid forming self-attention’s large n × n intermediate matrix, assuming r ≪ n.
  • 2.3 ONE-STEP GRADIENT: The main optimization challenge is unstable gradient propagation through the iterative decomposition, making direct BPTT harmful to Hamburger’s performance.The analysis motivates retaining the dominant last-step term as a one-step gradient rather than backpropagating through the full iteration history.
  • 2.3 ONE-STEP GRADIENT: The one-step gradient linearly approximates BPTT as t →∞ and reduces differentiation time and space complexity from O(t) to O(1).The paper reports that adding more gradient terms performed worse than using one step, which was acceptable for backpropagation through matrix decompositions.

3 EXPERIMENTS

Experiments evaluate Hamburger through ablations, efficiency comparisons, semantic segmentation, and image generation. Results show that its matrix-decomposition design can improve performance while keeping global-context modeling efficient.

  • Ablation Experiments: Removing matrix decomposition causes the most severe performance decay, while both lower and upper linear transformations contribute additional performance.Even parameter-free matrix decomposition improves performance, and the upper transformation contributes particularly substantially.
  • Ablation Experiments: r = 8 performs well, indicating that Hamburger can model global context with a small latent dimension.There is no simple linear relation between d and r and mIoU, although d = 8r is satisfactory.
  • Ablation Experiments: K = 6 is enough for CD and NMF, while K = 1 is acceptable for VQ; typically, 3–6 steps are sufficient.Using the same K during training and testing is recommended, and few iterations act as cheap early stopping.
  • A Close Look at Hamburger: Hamburger concentrates representation energy into the largest singular values while preserving informative details through the skip connection.This produces the truncated spectrum associated with low-rank reconstruction and is presented as a behavior of Hamburger in the network.
  • Semantic Segmentation: Hamburger achieves considerable improvements over previous state-of-the-art attention modules on PASCAL VOC and PASCAL Context semantic segmentation.The benchmark uses ResNet-101 with output stride 8 and compares against state-of-the-art attentions.
  • Image Generation: HamGAN-strong improves FID by over 5% while being 15% faster overall and 3.6× faster for the context module than YLG.The comparison uses the same training settings and TPUv3 platform; reported speeds are 1.54, 1.31, and 1.65 iterations per second for HamGAN, YLG, and neither module.

4 RELATED WORK

Attention mechanisms have become widely used for global information discovery, while related work also explores their interpretations, applications, and computationally efficient alternatives.

  • Attention mechanisms generate target weights adaptively according to requests, with dot-product self-attention as a prominent architecture.
  • Researchers explain attention through long-range dependencies, visual-scene decomposition, part–whole relationships, object interactions, and environmental dynamics.
  • Interpretations of attention include biological inspiration, visualization and attacks on attention weights, non-local operations, diffusion models, and expectation-maximization-like models.
  • Efficient-attention methods commonly approximate the post-softmax QK correlation matrix with products of smaller matrices to reduce memory and computation.
  • Matrix decomposition in deep learning has primarily been used to factorize network weights, including softmax, convolutional, and embedding layers.

5 CONCLUSION

The conclusion presents Hamburger as a low-rank, optimization-designed global-context module based on matrix decomposition, emphasizing interpretability, efficiency, and careful gradient handling.

  • Hamburger formulates global-context learning as low-rank recovery and turns a matrix-decomposition optimization algorithm into a network computational graph.
  • Hamburger learns global context by denoising and completing inputs while rescaling spectrum concentration.
  • Concept Decomposition reconstructs the representation as X̄ = DC after alternating dictionary normalization and coefficient updates.

C PROOF OF PROPOSITIONS

The proof analyzes an optimization-inspired recurrent model and establishes convergence properties for its iterative updates and fixed point.

  • The iterations of F have linear convergence.
  • F is a contraction mapping with respect to h for arbitrary fixed x.
  • The sequence {h_t} is Cauchy, and F admits a unique fixed point h* under arbitrary given x.
  • Differentiating the fixed-point equation establishes the existence of the implicit function h*(x).

D DATASETS

The experiments use PASCAL VOC, PASCAL Context, and ILSVRC 2012 to evaluate vision tasks involving semantic segmentation and image generation.

  • PASCAL VOC contains 10,582 training, 1,449 validation, and 1,456 test images spanning 20 foreground classes and background.
  • PASCAL Context contains 4,998 training and 5,105 validation images with 59 foreground classes and background.
  • ILSVRC 2012 contains 1.3M training samples and 50k test images across 1,000 object classes, with images resized to 128 × 128.

E.1 ABALATION EXPERIMENTS

The ablation experiments evaluate Hamburger under segmentation and image-generation settings, using matched backbones, training procedures, and established evaluation protocols. The experiments also specify the placement and measurement of the global context module.

  • Evaluation: Computational measurements report MACs with torchprofile and average inference time over repeated runs on an NVIDIA TITAN Xp GPU.Real-time cost uses an input tensor Z ∈R1×512×128×128 and averages 20 repeats of 100 runs.
  • Architectures: Semantic-segmentation experiments use dilated ResNet-101 with output stride 8 and reduce backbone channels from 2048 to 512 before adding Hamburger.The setup uses dilated convolution to preserve spatial detail and enlarge the receptive field.
  • Optimization: Segmentation training applies synchronized batch normalization, ImageNet initialization, momentum SGD, and a poly-learning-rate schedule.The reported setup uses fine-tuning from ImageNet pre-training and dataset-specific hyperparameters.
  • Architectures: ImageNet generation experiments match SAGAN and YLG architectures, placing NMF Hamburger at 32×32 resolution in both generator and discriminator.The shared setup includes spectral normalization, conditional batch normalization, and class projection.
  • Optimization: HamGAN is trained with Adam and TTUR using the same training settings as the corresponding SAGAN and YLG baselines.Generated-image quality is evaluated with FID, where lower values indicate higher fidelity.

F FURTHER RESULTS FROM ABLATION EXPERIMENTS

The ablations examine initialization, temperature, and optimization iterations for matrix-decomposition global-context modules, while motivating low-rank recovery as a way to model global context. Small numbers of optimization steps and suitable initialization are generally favored.

  • Initialization: Random initialization is generally effective across NMF, CD, and VQ, whereas learned initialization performs worst because back-propagated gradients can impede backbone training.Warm starts benefit CD with unit-vector dictionaries; random initialization achieves 77.8(77.6) for NMF when sampling Cij from Uniform(0, 1).
  • Temperature: Lower temperature is recommended for VQ and CD, but reducing it further increases training variance without additional gains.As T approaches 0, VQ and CD solutions become closer to the original optimization problem.
  • Iterations: More optimization iterations, including fully converged solutions, perform worse than small iteration counts; K from 1 to 8 provides satisfactory performance.The authors interpret small K as early stopping for the optimization algorithm.
  • Low-rank motivation: Low-rank modeling treats repeated low-level structures as a smaller set of high-level concepts, helping separate global information from local detail and incorrect information.The proposed formulation decomposes representations into a low-rank global-information matrix and a noise matrix, then uses optimization to recover the clean signal subspace.

H MISCELLANEOUS

The discussion compares matrix-decomposition choices, explains why NMF performs well in the reported setting, and qualifies the current Hamburger design as primarily illustrative rather than fully practical.

  • Design rationale: The selected MD models and early stopping were chosen to validate the generality of the approach rather than because they are optimal low-rank models.The authors emphasize that several simple, established MD models can work when gradients are handled carefully.
  • Model comparison: Matrix-decomposition performance may depend on prior modeling, optimization-solution quality, and how well the optimization algorithm supports backward gradients.These factors are presented as possible explanations for differences among MD models.
  • Model comparison: NMF outperforms VQ and CD on the reported tasks and datasets, possibly because nonnegative backbone representations suit NMF’s latent-structure modeling.The discussion also identifies NMF’s multiplicative-update rule as a practice-tested optimization algorithm.
  • Scope: The current Hamburger version is described as more illustrative than practical, and the authors state that it has not been pushed to its limit.The paper uses it to experimentally examine low-rank formulation, decomposition, optimization-driven methods, and one-step gradients.

I FUTURE WORKS

The future-work agenda focuses on understanding gradients and smoothing, learning better global-context representations, and extending matrix decomposition to richer structures, data types, and optimization settings.

  • Model structure: Open directions include learning task-specific low-rank structures, adding positional and locality information, and extending decomposition beyond low-rank assumptions.The current MD models do not explicitly encode positional information or locality in their objectives.
  • Scaling and extensions: The framework could incorporate learned optimizers, nested-optimization analysis, and advanced structured decomposition for large-scale vision, point-cloud, and video models.These directions target faster MD solving, better solutions, and Transformer-like architectures across high-resolution modalities.
  • Scaling and extensions: Equivariance is another proposed direction, because translation- and rotation-equivariant systems can improve network performance and speed training convergence.The discussion frames symmetry as a way to encode predictable effects of data transformations in representations.
  • Optimization and gradients: Future work should determine when the approximate One-Step Gradient matches or outperforms the exact gradient, since extra noise may help or harm optimization.The proposed behavior depends on loss landscapes, network architectures, datasets, and optimizer ability to escape sharp minima.
  • Optimization and gradients: The paper calls for better understanding of how attention and Hamburger modules are trained, including possible optimization-based or implicit formulations of attention.The discussion connects this question to reported training-dynamics observations in Transformer models.
  • Representation learning: Future studies should clarify how global context improves representations and provide mathematical analysis of fusion mechanisms such as Hamburger’s skip connection.The authors distinguish modeling global context from the ultimate goal of learning better representations.
  • Context operators: The paper proposes abstracting context operators by identifying common properties across attention-related methods, such as smoothing representations or rescaling spectral concentration.This agenda seeks a category of operators defined by minimal mathematical properties.
  • Context operators: Future work should balance context-module smoothing because repeated low-rank operations without skip connections can produce rank collapse.The paper notes a possible theoretical link between attention and matrix-decomposition models.
Loading 2109.04553v2…