We propose DrBoost, a dense retrieval ensemble inspired by boosting. DrBoost
is trained in stages: each component model is learned sequentially and
specialized by focusing only on retrieval mistakes made by the current
ensemble. The final representation is the concatenation of the output vectors
of all the component models, making it a drop-in replacement for standard dense
retrievers at test time. DrBoost enjoys several advantages compared to standard
dense retrieval models. It produces representations which are 4x more compact,
while delivering comparable retrieval results. It also performs surprisingly
well under approximate search with coarse quantization, reducing latency and
bandwidth needs by another 4x. In practice, this can make the difference
between serving indices from disk versus from memory, paving the way for much
cheaper deployments.

提出了一种名为 DrBoost 的密集检索集成算法，采用逐步训练的方式进行，具有相比标准密集检索模型更紧凑且性能相当的优势，尤其在粗量化下具有出乎意料的表现，可以通过降低延迟和带宽需求，实现更便宜的部署。

Boosted Dense Retriever

The wide applicability of kernels makes the problem of max-kernel search
ubiquitous and more general than the usual similarity search in metric spaces.
We focus on solving this problem efficiently. We begin by characterizing the
inherent hardness of the max-kernel search problem with a novel notion of
directional concentration. Following that, we present a method to use an $O(n
\log n)$ algorithm to index any set of objects (points in $\Real^\dims$ or
abstract objects) directly in the Hilbert space without any explicit feature
representations of the objects in this space. We present the first provably
$O(\log n)$ algorithm for exact max-kernel search using this index. Empirical
results for a variety of data sets as well as abstract objects demonstrate up
to 4 orders of magnitude speedup in some cases. Extensions for approximate
max-kernel search are also presented.

该论文研究了最大内核搜索的广泛适用性和与度量空间内相似度搜索相比更为普遍的问题，并提出了一种使用 Hilbert 空间中的 O (n log n) 算法直接索引任何对象集合的方法，而无需该空间中的显式特征表达，从而提供了第一个经过证明的 O (log n) 准确内核搜索算法。同时提供了适用于近似最大内核搜索的扩展方法。

快速精确 Max-Kernel 搜索

Fast Exact Max-Kernel Search

Mappings to structured output spaces (strings, trees, partitions, etc.) are
typically learned using extensions of classification algorithms to simple
graphical structures (eg., linear chains) in which search and parameter
estimation can be performed exactly. Unfortunately, in many complex problems,
it is rare that exact search or parameter estimation is tractable. Instead of
learning exact models and searching via heuristic means, we embrace this
difficulty and treat the structured output problem in terms of approximate
search. We present a framework for learning as search optimization, and two
parameter updates with convergence theorems and bounds. Empirical evidence
shows that our integrated approach to learning and decoding can outperform
exact models at smaller computational cost.

该论文介绍了一种基于近似搜索的学习框架，可以在较小的计算成本下优于精确模型，将结构化输出问题从精确模型转化为近似搜索的问题，并给出了两个收敛定理和界限的参数更新方法。