Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining

• URL: http://arxiv.org/abs/2303.15311v1
• Date: Mon, 27 Mar 2023 15:18:32 GMT
• Title: Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining
• Authors: Nicholas Monath, Manzil Zaheer, Kelsey Allen, Andrew McCallum
• Abstract summary: We introduce an algorithm that approximates the softmax with provable bounds and that dynamically maintains the tree. In our study on datasets with over twenty million targets, our approach cuts error by half in relation to oracle brute-force negative mining.
• Score: 61.09807522366773
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Dual encoder models are ubiquitous in modern classification and retrieval. Crucial for training such dual encoders is an accurate estimation of gradients from the partition function of the softmax over the large output space; this requires finding negative targets that contribute most significantly ("hard negatives"). Since dual encoder model parameters change during training, the use of traditional static nearest neighbor indexes can be sub-optimal. These static indexes (1) periodically require expensive re-building of the index, which in turn requires (2) expensive re-encoding of all targets using updated model parameters. This paper addresses both of these challenges. First, we introduce an algorithm that uses a tree structure to approximate the softmax with provable bounds and that dynamically maintains the tree. Second, we approximate the effect of a gradient update on target encodings with an efficient Nystrom low-rank approximation. In our empirical study on datasets with over twenty million targets, our approach cuts error by half in relation to oracle brute-force negative mining. Furthermore, our method surpasses prior state-of-the-art while using 150x less accelerator memory.

Related papers

• SparseTem: Boosting the Efficiency of CNN-Based Video Encoders by Exploiting Temporal Continuity [15.872209884833977]
  We propose a memory-efficient scheduling method to eliminate memory overhead and an online adjustment mechanism to minimize accuracy degradation. SparseTem achieves speedup of 1.79x for EfficientDet and 4.72x for CRNN, with minimal accuracy drop and no additional memory overhead.
  arXiv  Detail & Related papers  (2024-10-28T07:13:25Z)
• A Fresh Take on Stale Embeddings: Improving Dense Retriever Training with Corrector Networks [81.2624272756733]
  In dense retrieval, deep encoders provide embeddings for both inputs and targets. We train a small parametric corrector network that adjusts stale cached target embeddings. Our approach matches state-of-the-art results even when no target embedding updates are made during training.
  arXiv  Detail & Related papers  (2024-09-03T13:29:13Z)
• Sparse-Inductive Generative Adversarial Hashing for Nearest Neighbor Search [8.020530603813416]
  We propose a novel unsupervised hashing method, termed Sparsity-Induced Generative Adversarial Hashing (SiGAH) SiGAH encodes large-scale high-scale high-dimensional features into binary codes, which solves the two problems through a generative adversarial training framework. Experimental results on four benchmarks, i.e. Tiny100K, GIST1M, Deep1M, and MNIST, have shown that the proposed SiGAH has superior performance over state-of-the-art approaches.
  arXiv  Detail & Related papers  (2023-06-12T08:07:23Z)
• Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization [60.91600465922932]
  We present an approach that avoids the use of a dual-encoder for retrieval, relying solely on the cross-encoder. Our approach provides test-time recall-vs-computational cost trade-offs superior to the current widely-used methods.
  arXiv  Detail & Related papers  (2022-10-23T00:32:04Z)
• Highly Parallel Autoregressive Entity Linking with Discriminative Correction [51.947280241185]
  We propose a very efficient approach that parallelizes autoregressive linking across all potential mentions. Our model is >70 times faster and more accurate than the previous generative method.
  arXiv  Detail & Related papers  (2021-09-08T17:28:26Z)
• Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More [7.484063729015126]
  We propose two effective log-linear time approximations of the cost matrix for optimal transport. These approximations enable general log-linear time algorithms for entropy-regularized OT that perform well even for the complex, high-dimensional spaces. For graph distance regression we propose the graph transport network (GTN), which combines graph neural networks (GNNs) with enhanced Sinkhorn.
  arXiv  Detail & Related papers  (2021-07-14T17:40:08Z)
• A Bop and Beyond: A Second Order Optimizer for Binarized Neural Networks [0.0]
  optimization of Binary Neural Networks (BNNs) relies on approximating the real-valued weights with their binarized representations. In this paper, we take an approach parallel to Adam which also uses the second raw moment estimate to normalize the first raw moment before doing the comparison with the threshold. We present two versions of the proposed: a biased one and a bias-corrected one, each with its own applications.
  arXiv  Detail & Related papers  (2021-04-11T22:20:09Z)
• FastLR: Non-Autoregressive Lipreading Model with Integrate-and-Fire [74.04394069262108]
  We propose FastLR, a non-autoregressive (NAR) lipreading model which generates all target tokens simultaneously. FastLR achieves the speedup up to 10.97$times$ compared with state-of-the-art lipreading model.
  arXiv  Detail & Related papers  (2020-08-06T08:28:56Z)
• Auto-Encoding Twin-Bottleneck Hashing [141.5378966676885]
  This paper proposes an efficient and adaptive code-driven graph. It is updated by decoding in the context of an auto-encoder. Experiments on benchmarked datasets clearly show the superiority of our framework over the state-of-the-art hashing methods.
  arXiv  Detail & Related papers  (2020-02-27T05:58:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.