# T-EMDE: Sketching-based global similarity for cross-modal retrieval

arXiv: https://arxiv.org/abs/2105.04242 · HTML: https://mlsanity.com/paper/2105.04242/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 46 of its 62 references that are in the map.
- First posted on arXiv 10 May 2021.

## Builds on (most cited first, 30 of 46)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Microsoft COCO: Common Objects in Context](https://mlsanity.com/paper/1405.0312/) (2014)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Faster R-CNN: Towards Real-Time Object Detection with Region Proposal Networks](https://mlsanity.com/paper/1506.01497/) (2015)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Visual Genome: Connecting Language and Vision Using Crowdsourced Dense Image Annotations](https://mlsanity.com/paper/1602.07332/) (2016)
- [Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling](https://mlsanity.com/paper/1412.3555/) (2014)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [LXMERT: Learning Cross-Modality Encoder Representations from Transformers](https://mlsanity.com/paper/1908.07490/) (2019)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Show, Attend and Tell: Neural Image Caption Generation with Visual Attention](https://mlsanity.com/paper/1502.03044/) (2015)
- [Bottom-Up and Top-Down Attention for Image Captioning and Visual Question Answering](https://mlsanity.com/paper/1707.07998/) (2017)
- [On the Properties of Neural Machine Translation: Encoder-Decoder Approaches](https://mlsanity.com/paper/1409.1259/) (2014)
- [Deep Visual-Semantic Alignments for Generating Image Descriptions](https://mlsanity.com/paper/1412.2306/) (2014)
- [VL-BERT: Pre-training of Generic Visual-Linguistic Representations](https://mlsanity.com/paper/1908.08530/) (2019)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [Stacked Cross Attention for Image-Text Matching](https://mlsanity.com/paper/1803.08024/) (2018)
- [Visual Transformers: Token-based Image Representation and Processing for Computer Vision](https://mlsanity.com/paper/2006.03677/) (2020)
- [Attention on Attention for Image Captioning](https://mlsanity.com/paper/1908.06954/) (2019)
- [Sparse Sinkhorn Attention](https://mlsanity.com/paper/2002.11296/) (2020)
- [Exploring Visual Relationship for Image Captioning](https://mlsanity.com/paper/1809.07041/) (2018)
- [A Comprehensive Survey of Deep Learning for Image Captioning](https://mlsanity.com/paper/1810.04020/) (2018)
- [Synthesizer: Rethinking Self-Attention in Transformer Models](https://mlsanity.com/paper/2005.00743/) (2020)
- [Visual Semantic Reasoning for Image-Text Matching](https://mlsanity.com/paper/1909.02701/) (2019)
- [Blockwise Self-Attention for Long Document Understanding](https://mlsanity.com/paper/1911.02972/) (2019)

## Abstract (arXiv)

The key challenge in cross-modal retrieval is to find similarities between objects represented with different modalities, such as image and text. However, each modality embeddings stem from non-related feature spaces, which causes the notorious 'heterogeneity gap'. Currently, many cross-modal systems try to bridge the gap with self-attention. However, self-attention has been widely criticized for its quadratic complexity, which prevents many real-life applications. In response to this, we propose T-EMDE - a neural density estimator inspired by the recently introduced Efficient Manifold Density Estimator (EMDE) from the area of recommender systems. EMDE operates on sketches - representations especially suitable for multimodal operations. However, EMDE is non-differentiable and ingests precomputed, static embeddings. With T-EMDE we introduce a trainable version of EMDE which allows full end-to-end training. In contrast to self-attention, the complexity of our solution is linear to the number of tokens/segments. As such, T-EMDE is a drop-in replacement for the self-attention module, with beneficial influence on both speed and metric performance in cross-modal settings. It facilitates communication between modalities, as each global text/image representation is expressed with a standardized sketch histogram which represents the same manifold structures irrespective of the underlying modality. We evaluate T-EMDE by introducing it into two recent cross-modal SOTA models and achieving new state-of-the-art results on multiple datasets and decreasing model latency by up to 20%.