#

tmall在《Multi-Interest Network with Dynamic Routing for Recommendation at Tmall》开放了它们的召回算法。在matching stage上，提出了Multi-Interest Network with Dynamic routing (MIND)来处理用户的多样化兴趣。特别的，还基于capsule routing机制设计了一个multi-interest extractor layer，用于聚类历史行为和抽取多样化兴趣。另外，我们还开发了一种称为”label-aware attention”的技术来帮助学习具有多个向量的用户表示 。目前的效果要好于state-of-the-art的其它推荐方法。并在天猫APP的移动端主页上部署，会处理主要的在线流量。

1.介绍

tmall APP的主页如图1(左）所示，它占据着tmall APP的半数流量，并会部署RS来展示个性化的商品来满足客户个性化需求。

图1

由于数十亿规模的users和items，tmall的推荐过程设计包括两部分：matching stage和ranking stage。对于这两阶段，建模用户兴趣和发现可以捕获用户兴趣的用户表示(user representation)非常重要，以便能支持对items的高效检索来满足用户兴趣。然而，由于用户的多样化兴趣的存在，在tmall上建模用户兴趣是很有意义的（non-trivial）。平均上，数十亿用户访问tmall，每个用户每天会与成百上千个商品交互。交互的商品趋向于属于不同类目，可以表示用户兴趣的多样性。例如，如图1(右)所示，不同用户根据它们的兴趣来说是不同的，相同的用户也可能对不同类型的items感兴趣。因此，捕获用户的多样化兴趣的能力变得十分重要。

已经存在的推荐算法会以不同方式建模和表示用户兴趣。CF-based方法可以通过历史交互items[22]或隐因子[17]来表示用户兴趣，可以承受稀疏性问题或计算需要。deep learning-based方法通常以低维embedding vectors来表示用户兴趣。例如，youtube DNN[7]从用户过往行为中转换得到固定长度的vector，它对于建模多样化兴趣可能是个瓶颈，因为在tmall上，它的维度必须很大，以便能表示海量的interest profiles。DIN[31]使用attention机制，使得单个用户对于不同的items会有不同用户表示，这样可以捕获多样化的用户兴趣。然而，采用attention机制也使得它对于海量items的大规模应用来说是在计算上是不可行的，因为它需要为每个item重新计算用户表示(user representation)，这使得DIN只适用于ranking stage。

在本paper中，我们主要关注在matching stage上为用户建模多样化兴趣的问题。为了克服已存在方法的限制，我们提出了MIND来学习用户表示，它可以在matching stage上影响用户的多样化兴趣。为了infer用户表示向量，我们设计了一个新的layer，它称为“multi-interest extract layer”，该layer会利用“dynamic routing”[21]机制来自适应地将用户历史行为聚合成用户表示(user repesentation)。dynamic routing的过程被看成是软聚类（soft-clustering），它会将用户的历史行为聚合成许多聚类(clusters)。每个历史行为的cluster会进一步根据一个特定兴趣，被用于infer用户表示的向量。这种方式下，对于一个特定用户，MIND会输出多个表示向量，它们表示共同表示用户的多样化的兴趣。用户表示向量只会被计算一次，并被用于matching stage来从海量items中检索相关items。该方法的主要贡献有：

• 1.为了捕获用户行为的多样化兴趣，我们设计了multi-interest extractor layer，它可以利用dyniamic routing来自适应地将用户历史行为聚合成用户表示向量。
• 2.通过使用由multi-interest extractor layer和一个新提出的label-aware attention layer生成的用户表示向量(vectors)，我们构建一个DNN来做个性化推荐。对比已存在的方法，MIND在多个公开数据集上和天猫上的效果要好一些。
• 3.为了在tmall上部署MIND，我们构建了一个系统来实现整个pipline，包括：data collecting、model training和online serving。部署的系统可以极大提升Tmall APP的ctr。

2.相关工作

深度学习推荐。受CV和 NLP的deep learning的成功启发，我们尝试了许多deep learning-based的推荐算法。除了[7,31]，还有许多其它deep模型。NCF[11]、DeepFM[9]、DMF[27]会构建由许多MLP组成的神经网络来建模users和items间的交互。[23]提供一种可捕获许多特征的united and flexible network来解决top-N序列推荐。

User Representation。在推荐系统中，将users表示为vectors很常见。传统的方法会将用户偏好组合成由感兴趣的items[4,12,22]、keywords[5,8]和topics[29]的vectors。随着分布式表示学习的出现，user embeddings可以通过NN获得。[6]使用RNN-GRU来从时序阅读文档中学习user embeddings。[30]从word embedding vectors中学习user embedding vectors，并将它们应用于推荐学术微博上。[2]提出了一种新的CNN-based模型来显式学习和利用user embeddings。

Capsule Network。“胶囊（Capsule）”的概念，对一小部分neurons组合输出一整个vector，首次由2011年Hinton[13]提出。用于替代BP，dynamic routing[21]被用于学习capsules间连接的权重，通过利用EM算法[14]来克服多种缺陷并达到较好的accuracy。它与CNN有两个主要不同之处，使得capsule networks可以编码在part和whole间的关系，这在CV和NLP中是很先进的。SegCaps[18]证明，capsules可以成功建模目标的局部关系（spatial），比传统CNNs要好。[28]研究了文本分类的capsule网络，并提出了3种策略来增强效果。

3.方法

3.1 问题公式化

工业界RS的matching stage的目标，从海量item池子I中，为每个用户\(u \in U\)检索一个items子集，使得该子集包含数千个items，每个item与用户兴趣相关。为了达到该目标，由RS生成的历史数据收集来构建一个matching模型。特别的，每个实例可以通过一个tuple \((I_u, P_u, F_i)\)进行表示，其中:

• \(I_u\)表示与用户u交互的items集合（也称为：用户行为(user behavior)）
• \(P_u\)是用户u的基础profiles（比如：gender和age）
• \(F_i\)是target item的特征（比如：item id和category id）

MIND的核心任务是，学习一个函数，来将原始特征（raw features）映射到用户表示上，它可以公式化为：

…(1)

其中，\(V_u = (\vec{v}_u^1, \cdots, \vec{v}_u^K) \in R^{d \times K}\)表示用户u的表示向量，d是维度，K是表示向量的数目。当K=1时，只使用一个表示向量，如同Youtube DNN一样。另外，target item i的表示向量通过一个embedding function获取：

…(2)

其中，\(\vec{e}_i \in R^{d \times 1}\)表示item i的表示向量，\(f_{item}\)的细节会在”Embedding &Pooling Layer”这节详述。

当学习到用户表示向量和item表示向量，top N候选items会根据打分函数进行检索：

…(3)

其中，N是在matching stage中检索出的items的预定义数目。

3.2 Embedding & Pooling Layer

图2 MIND总览。MIND会使用用户行为、用户profile特征作为输入，输出用户表示向量(vectors)以便在matching stage时做item检索。input layer的ID特征通过embedding layer被转换成embeddings，每个item的embeddings(item_id, cat_id, brand_id都会有embedding)会进一步通过一个pooling layer进行平均。用户行为embeddings被feed给multi-interest extractor layer，它会生成interest capsules。通过将interest capsules与user profile embedding进行拼接，并通过一些ReLU layers将concatenated capsules进行转换，可以获得用户表示向量(vectors)。在训练期间，一个额外的label-aware attention layer被引入到指导训练过程。在serving时，多个用户表示向量通过一个ANN查询方式被用于检索items。

如图2所示，MIND的输入包含了三个groups：user profile \(P_u\)，user behavior \(I_u\)，label item \(F_i\)。每个group包含了许多类别型特征（categorical id features），这些id features具有极高的维度。例如，item ids的数目是数十亿的，因而，我们会采用广泛使用的embedding技术来将这些id features嵌入到低维dense vectors（a.k.a embeddings）中，这会极大减小参数数目，并减缓学习过程。对于来自\(P_u\)的id features(gender、age等)，相应的embeddings会进行拼接（concatenated）来形成user profile embedding \(\vec{p}_u\)。对于item ids、以及其它类别型ids（brand id, shop id等），对于来自\(F_1\)的冷启动items[25]，它已经被证明是有用的[25]，相应的embeddings会进一步通过一个average pooling layer来形成label item embedding \(\vec{e}_i\)。最后，对于来自user behavior \(I_u\)的items，相应的item embeddings被组合来形成user behavior embedding \(E_u = \lbrace \vec{e}_j, j \in I_u \rbrace\)。

3.3 Multi-Interest Extractor Layer

我们认为，通过一个表示向量来表示用户兴趣，这对于捕获用户多样化兴趣是个瓶颈，因为我们必须将与用户的多样化兴趣相关的所有信息压缩到一个表示向量中。因而，关于用户的多样化兴趣的所有信息，是混合在一起的，对于matching stage来说这会造成错误的item检索。作为替代，我们采用多个表示向量来单独表示用户的不同兴趣。通过该方法，用户的多样化兴趣在matching stage中会被单独对待，对于每个方面的兴趣，使得item检索更精准。

为了学习多种表示向量，我们会使用聚类过程来将用户的历史行为group成一些clusters。在一个cluster中的items被认为是相互更接近的，可以表示用户兴趣的某个特定方面。这里，我们会设计multi-interest extractor layer来对历史行为进行聚类和并对生成的聚类进行inferring表示向量。由于multi-interest extractor layer的设计受最近提出的dynamic routing[13,14,21]的启发，我们首先回顾必要的基础，以便使该paper可以自圆其说。

3.3.1 Dynamic Routing

我们简短介绍capsules表征学习的dynamic routing[21]，这是表示向量的一种新的neural units形式。假设我们有两层capsules，我们将第一层看成是low-level capsules，将第二层的capsules看成是high-level capsules。dynamic routing的目标是，给定low-level capsules，以迭代方式计算high-level capsules的值。在每轮迭代中，给定的low-level capsules \(i \in \lbrace 1, \cdots, m \rbrace\)，它相应的向量为：

high-level capsules \(j \in \lbrace 1, \cdots, n \rbrace\)，它相应的向量为：

在low-level capsule i和high level capsule j之间的routing logit \(b_{ij}\)，可以通过以下公式计算（注：hinton paper中的\(\hat{u}_{j \mid i}\)在此处被展开，\(S_{ij}\)即hinton paper中的\(W_{ij}\)）：

…(4)

其中，\(S_{ij} \in R^{N_h \times N_l}\)表示要学习的bilinear mapping matrix。T表示transpose。

有了routing logits，对于high-level capsule j的候选向量(candidate vector)，可以（注：\(w_{ij}\)即hinton paper中的\(c_{ij}\)耦合系数）：

…(5)

其中，\(w_{ij}\)表示连接low-level capsule i和high-level capsule j的权重，可以通过在routing logits上执行softmax计算得到：

…(6)

最后，使用一个非线性”squash”函数来获得high-level capsules的vectors：

…(7)

\(b_{ij}\)的值被初始化为0, routing process通常会重复三次以便收敛。当routing完成时，high-level capsule的值\(\vec{c}_j^h\)是确定的，可以被当作是next layers的inputs。

3.3.2 B2I Dynamic Routing

简单来说，capsule是一种新型neuron，它由一个vector表示，而非在普通神经网络中使用的一个标量（scalar）。vector-based capsule被认为是能够表示一个实体的不同属性，在其中，一个capsule的方向(orientation)可以表示一个属性（property），capsule的长度被用于表示该属性存在的概率(probability)。相应的，multi-interest extractor layer的目标是，为用户兴趣的属性（properties）通过学习得到表示(representations)以及学习是否存在相应的兴趣(representations)。在胶囊(capsules)和兴趣表示(interest representations)间的语义关联启发我们将行为/兴趣表示（behavior/interest representations）看成是行为/兴趣胶囊（behavior/interest capsules），并使用dynamic routing来从behavior capsules中学习interest capsules。然而，原始routing算法是为图像数据而提出的，并不能直接应用到处理用户行为数据上。因此，我们提出了Behavior-to-Interest(B2I) dynamic routing来自适应地将用户行为聚合到兴趣表示向量(interest representation vectors)中，它与原始的routing算法有三个不同之处：

1.Shared bilinear mapping matrix.

在原始版本的dynimic routing中，每个(low-level capsules, high-level capsules) pair，会使用一个单独的bilinear mapping matrix；我们的版本则会使用固定（fixed）的bilinear mapping matrix S来替换，这是由于两方面的考虑：

• 一方面，用户行为是变长的，对tmall用户来说，范围从几十到几百不等，因而，使用固定的bilinear mapping matrix是可泛化推广（generalizable）的
• 另一方面，我们希望interest capsules位于相同的向量空间中，但不同的bilinear mapping matrice会将interest capsules映射到不同的向量空间上。从而，routing logit可以通过以下公式计算：

…(8)

其中：

• \(\vec{e}_i \in R^d\)表示behavior item i的embedding
• \(\vec{u}_j \in R^d\)表示interest capsule j的向量。
• bilinear mapping matrix \(S \in R^{d \times d}\)是跨每个(behavior capsules, interest capsules) pairs间共享的。

2.随机初始化routing logits

由于使用共享的bilinear mapping matrix S，将routing logits初始化到0可能会导致相同初始化的interest capsules。接着，后续的迭代可能会陷入这样的情形，不同的interest capsules在所有时刻都会相同。为了消除该现象，我们会使用高斯分布\(N(0, \sigma^2)\)来抽样一个random matrix来初始化routing logits，使得初始的interest capsules相互间都不同，这与K-means聚类算法相类似。

3.动态兴趣数(Dynamic interest number)

由于不同用户的interest capsules的数目会有不同，我们引入一个启发式规则来为不同用户自适应调整K值。特别的，用户u的K值可以通过下式进行计算(注：\(\mid I_u \mid\)表示用户行为item数)：

…(9)

对于那些具有更少兴趣的users，调整interest capsules数目的策略，可以节省一些资源（包括计算资源和内存资源）。

整个dynamic routing过程如算法1所示。

算法1

3.4 Label-aware Attention Layer

通过多兴趣抽取层（multi-interest extractor layer），从用户的行为embeddings可以生成许多的interest capsules。不同的interest capsules表示用户兴趣的不同方面，相关的interest capsule被用于评估在指定items上的用户偏好。因而，在训练期间，我们设计了一个label-aware attention layer，它基于缩放点积注意力（scaled dot-product attention）[24]机制，可以让target item选择要使用哪个interest capsule。特别的，对于一个target item，我们会计算每个interest capsule和target item embedding间的兼容性（compatibilities），并计算一个关于interest capsules的加权求和来作为该target item的用户表示向量，其中，一个interest capsule的权重由相应的兼容性（compatibility）所决定。在label-aware attention中，label是query，interest capsules是keys和values，如图2所示。user u对于item i的output vector，可以计算如下：

其中：

• pow表示element-wise指数操作符(exponentiation oprator)，pow(x,y)表示x的y次幂；
• p是一个可调参数，用于调节attention分布。当p接近0时，每个interest capsule趋向于接收偶数(even)attention。当p大于1时，随着p的增加，该值会大于点乘，会接受越来越多的权重。考虑到极限的情况，当p无穷大时，attention机制会变成一种hard attention，它会选中具有最大attention的值，并忽略其它。在我们的实验中，我们发现：使用hard attention会导致更快的收敛。

其它：

• \(\vec{e}_i\)表示target item i的embedding
• \(V_u\)：用户u的表示向量，共由K个interest capsules组成
• \(\vec{v}_u\)：user u对于item i的output vector

3.5 Training & Serving

有了user vector \(\vec{v}_u\)和label item embedding \(\vec{e}_i\)，我们可以计算user u和label item i间的概率：

…(10)

接着，对于训练MIND的整个目标函数为：

…(11)

其中，D是包含user-item交互的训练数据集。由于items数目的规模为数十亿，(10)的分母的sum操作在计算上是不可行的。因而，我们使用sampled softmax技术[7]来使目标函数可追踪，并使用Adam optimizer来训练MIND。

在训练后，除了label-aware attention layer外的MIND网络可以被用于user representation mapping函数：\(f_{user}\)。在serving时，用户的行为序列和user profile会feed给\(f_{user}\)函数，为用户生成多个表示向量。接着，这些表示向量通过一个近似最近邻（ANN）方法[15]被用于检索top N个items。对于matching stage，具有与user representation vectors最高相似度的那些items，可以被检索并组合候选items的最终集合。请注意，当一个用户具有新动作时，他的行为序列、以及相应的user representation vectors也会被更改，因而，MIND可以在matching stage上用于实时个性化召回。

3.6 与已存在方法的联系

这里，我们比较了MIND与其它两种已存在方法的关系，展示了相似之处和不同之处。

Youtube DNN. MIND和Youtube DNN都使用深度神经网络来建模用户行为数据并生成用户表示，都被用于在matching stage上检索海量item。然而，Youtube DNN只使用一个vector来表示一个用户，而MIND使用多个vectors。当在算法1中K的值为1时，MIND退化成Youtube DNN，而MIND可以看成是Youtube DNN的泛化（generalization）。

DIN. DIN可以捕获用户的多样化兴趣，MIND和DIN具有相似的目标。然而，这两种方法在达成该目标以及应用上各不相同。为了处理多样化兴趣，DIN会在item级别使用一个attention机制，而MIND使用dynamic routing来生成interest capsules，并在interest level考虑多样性。再者，DIN关注在ranking stage处理上千的items，而MIND会解耦inferring用户表示和衡量user-item兼容性，使它应用于在matching stage上海量items的召回。

4.实验

4.1 离线评估

4.2 超参数分析

在本节中，我们在Amazon Books数据集上做了关于multi-interest extractor layer和label-aware attention layer的超参数的实验。

routing logits的初始化

对于在multi-interest extractor layer中的routing logits，我们采用随机初始化，它与K-means中心点的初始化类型，其中，初始簇心的分布对于最终的聚类结果有很强的影响。由于routing logits是根据高斯分布\(N(0, \sigma^2)\)进行初始化的，我们会关于\(\sigma\)的不同值是否会导致不同的收敛，从而影响效果。为了研究\(\sigma\)的影响，我们使用3个不同的\(\sigma\)值：0.1, 1, 5来初始化routing logits \(b_{ij}\). 结果如图3所示，3个值的每条曲线几乎重叠。该观察表明MIND是对\(\sigma\)值是健壮的。对于实际应用，我们使用\(\sigma=1\)。

图3 超参数的影响。上部展示了MIND使用不同\(\sigma\)的结果；下部展示了MIND中p越大，效果越好

在label-aware attention中的power数。正如前所述，在label-aware attention中的power number p控制着每个兴趣在组合的label-aware interest representation中的的比例。我们对p从0到\(\infty\)做了比较，结果如图3所示。很明显，p=0的效果要比其它要差。原因是，当采用p=0时，每个兴趣具有相同的attention，因而，组合起来的兴趣表示(interest representation)等到兴趣的平均，与label无关。如果\(p \ge 1\)，attention scores与兴趣表示向量和target item embeddings间的相似度成比例，这使得组合兴趣表示是一个关于兴趣的加权求和。结果表明，随着p的增大，效果会越好，因为与target item更相似的兴趣的表示向量会获得更大的attention。当\(p = \infty\)时，它会变为一个hard attention scheme。通过该scheme，与target item接近的兴趣表示会主导着组合兴趣表示，从而使得MIND收敛更快，效果更好。

4.3 在线实验

通过部署MIND在tmall主页上处理真实流量持续一周，我们开展在线实验。为了公平比较，所有方法在matching stage阶段进行部署，并采用相同的ranking过程。我们使用CTR来衡量online serving流量的效果。

有两种baseline方法进行在线实验。一个是item-based CF，它服务在线流量中的matching算法占居主要地位。另一个是Youtube DNN。我们在一个A/B test框架中部署了所有要比较的方法，它们feed给ranking stage并给出最终推荐。

图4

实验结果如图4所示。很明显MIND的效果要好于item-based CF和youtube DNN，这表示MIND生成了一个更好的user representation。另外，我们做出了以下观察：

• 1) 通过长期实践的优化，item-based CF的效果要好于YouTube DNN，它也超过具有单个兴趣的MIND算法。
• 2) 另一个显著的趋势是，MIND的效果会随着抽取的兴趣数的增加而变好（从1到5）。
• 3) 当抽取的兴趣数为5时，MIND的效果达到峰值，这之后，CTR保持数据，兴趣数达到7的提升可以忽略。
• 4) 使用动态兴趣数(dynamic interest number)的MIND与具有7个兴趣的MIND效果相当。

从上述观察来看，我们可以做出一些结论。

• 首先，对于Tmall，用户兴趣的最优数目是5-7, 这可以表示用户兴趣的平均多样性（diversity）。
• 第二，动态兴趣数机制并不能带来CTR增益，但在实验期间，我们意识到该scheme可以减少serving的开销，这有利于tmall这样的大规模服务，在实际上更易接受。

总之，在线实验验证了MIND对于建模多样化兴趣的效果，并能极大提升整体RS。

4.4 案例研究

4.4.1 耦合系数

在behavior capsules和interest capsules间的耦合系数，可以量化行为和兴趣级的等级关系。在这一节，我们将这些耦合系数可视化，来展示兴趣抽取过程的可解释性。

图5

图5展示了从tmall日活用户中随机抽取的两个用户相关的耦合系数，每一行对应于一个interest capsule，每一列对应于一个behavior。它展示了用户C(上)与4个类别的商品（耳机(headphones)、小吃(snacks)、手提包(handbags)、衣服(clothes)）有交互，每个商品都在一个interest capsule上具有最大解耦系数，并形成了相应的兴趣。而用户D(下)只在衣服上(clothes)有兴趣，因而，从行为中看到该用户具有3个细粒度的兴趣(毛衣(sweaters)、大衣(overcoats)、羽绒衣(down jackets))。关于该结果，我们证实了user behaviors的每个类都可以聚类在一起，并形成相应的兴趣表示向量。

4.4.2 item分布

图6

在serving时，与user兴趣相似的items通过最近邻搜索进行检索。我们基于相应兴趣的相似度，对这些通过单个兴趣召回的items的分布进行可视化。图6展示了图5中提到的相同用户(user C)的item分布。该分布分别通过两种方法获取，其中上面的轴4展示了基于MIND通过4个兴趣召回的items，而最下面的轴展示了基于Youtube DNN的结果。items根据它们与兴趣的相似度分散在轴上，通过最大最小归一化法归一化到0~1, 并围绕在0.5附近。上面的一个点指的是在一定范围内的组成的items，因而每个点的大小(size)表示了在相应相似度中items数目。我们也展示了从所有候选中随机选中的一些items。正如所预料的，通过MIND召回的items与对应的兴趣强相关，而Youtube DNN则会与items的类目更宽泛些，它们与用户行为具有较低相似度。

5.系统部署

图7

当用户加载Tmall APP时，推荐请求会被发送给Tmall Personality Platform，该server集群会将一大堆插件式模块进行集成，并作为在线推荐进行服务。用户最近的行为会通过Tmall Personality Platform进行检索到，并将它发送给User Interest Extractor，它是实现MIND的主模块，用于将用户行为转换成多个user interests。接着，Recall Engine会搜索与user interests最近的embedding vectors相关的items。由不同兴趣触发的items会被合成候选items，并通过用户兴趣的相似度进行排序。从海量item池中选择上千个候选items的整个过程通过User Interest Extractor和Recall Engine来完成，整个过程小于15ms，由于基于MIND的serving的高效性，在items范围和系统响应时间间的tradeoff，这些候选items的top 1000可以通过Ranking Service（它会使用一堆特征来预测ctr）进行打分。最终，Tmall个性化平台会完成最终展示给用户的推荐结果item列表。User Interest Extractor和Ranking Service在Model Training Platform上会使用100 GPUs进行训练，训练过程会执行8个小时。受益于Model Training Platform的高性能，用于预测服务的深度网络会每天更新一次，可以保证最新的商品被计算和被曝光。

参考

• 1.https://arxiv.org/pdf/1904.08030.pdf

Charles L.等2008在《Novelty and Diversity in Information Retrieval Evaluation》中提出了alpha-NDCG：

4.评估框架

probability ranking principle (PRP)构成了信息检索研究的基石。principle如下：

如果一个IR系统对每个query的response是：关于documents的一个ranking，它的顺序按相关度递减，该系统对用户的整体效率应最大化。

PRP通常被解释成一个新检索算法：估计每个文档的相关度概率，并进行排序。我们采用一个不同的视角，开始将PRP定义解释成：通过IR系统来最优化一个objective function。

假设：

• q：是一个query. 该query是隐式（implicit）并且是确定的（fixed）。
• u：为一个想根据q获取信息的用户
• d：为一个与u交互可能相关/不相关的 document
• R：是一个关于相关性的二元随机变量

为了应用PRP，我们估计：

在归纳和问答社区常指到“信息点（information nuggets）”。我们：

• 将用户信息建模成一个nuggets集合\(u \subseteq N\), 其中\(N = \lbrace n_1, \cdots, n_m \rbrace\)表示可能的nuggets空间。
• 将一个文档中出现的信息会被建模成一个 nuggets集合：\(d \subseteq N\)。

我们解释了一个nugget的概念，将它的通用含义扩展到包含关于一个document的任意二元属性。由于在归纳和问答中很常用，一个nugget可以表示一个信息片段。在QA示例中，一个nugget可以表示成一个答案。然而，一个nugget可以表示其它二元属性，比如：主题。我们也使用nugget来表示某特殊网站一部分的一个页面、一个关于不间断电力供应的特定事实、一个跟踪包裹的表格、或大学主页等。

如果一个特定document它包含了用户所需信息的至少一个nugget，那么则是相关的:

对于一个特定的nugget \(n_i\)：

• \(P(n_i \in u)\)表示用户信息包含\(n_i\)的概率，
• \(P(n_i \in d)\)表示document包含了\(n_i\)的概率

这些概率会被估计，用户信息需要独立于文档，文档需要独立于用户信息。相互间唯一的连接是：nuggets集合。

传统上，对于u和d的特定样本，相应的概率会被估计为0或1；也就是说：\(P(n_i \in u) = 1\)表示：\(n_i\)满足u的认知；否则不满足。相似的，\(P(n_i \in d) = 1\)表示：\(n_i\)可以在d中找到，否则不是。这种传统建模过分强调了这些待评估质量的确定性。采用一个更宽松的视角，可以更好建模真实情况。人工评估者在judgements上有可能是不一致的。来自隐式user feedback的要关评估可能不总是精准的。如果一个分类器被应用到人工羊honr，我们可以利分分类器本身提供的概率。

5. CUMULATIVE GAIN MEASURES

我们接着应用之前章节中的结果，使用nDCG来计算gain vectors。在过去一些年，当有评估分级相关度值(graded relevance values)时，nDCG已经作为标准evaluation measure。由于graded relevance values随前面的框架提出，使用nDCG看起来很合适。

计算nDCG的第一步是，生成一个 gain vector。当我们直接从等式(6)直接计算一个 gain vector时，简化该等式如下：

。。。

丢掉常数\(\gamma \alpha\)，它对于相对值没有影响，我们定义了gain vector G的第k个元素：

…(7)

对于我们的QA示例，如果我们设置\(\alpha = \frac{1}{2}\)，表2中列出的document会给出：

注意，如果我们设置:\(\alpha = 0\)，并且使用单个nugget来表示主题，等式7的gain vector表示标准的二元相关性。

计算nDCG中的第二步是：计算cumulative gain vector：

对于我们的QA示例有：

在计算CG后，会应用一个 discount到每个rank上来惩罚在ranking中较低的documents，来反映用户访问到它们需要额外的努力才行。一个常用的discount是\(log_2(1+k)\)，尽管其它discount functions也是可能的，并且有可能更好的反映user effort[20]。我们定义DCG如下：

对于我们的QA示例：

最后一步会通过使用一个“ideal” gain vector来归一化discounted cumulative gain vector。然而，CG和DCG也会被用来直接作为 evaluation measures。在我们的研究中，[3]中表明CG/DCG要比nDCG的用户满意度要好。然而，我们在结果中包含了normalization，后续会更进一步探索。

5.1 计算Ideal Gain

理想顺序是：能最大化所有国evels上的cumulative gain。在第3.2节中，我们提出，对表表2的documents的理想顺序背后的直觉。对于这些 documents, 理想的顺序是：a-e-g-b-f-c-h-i-j。相关的ideal gain vector为：

ideal gain vector是：

ideal discounted cumulative gain vector是：

理论上，ideal gain vector的计算是NP-complete。给定等式7的gain定义，最小化顶点覆盖（minimal vertex covering）可能会减小到计算一个 ideal gain vector。为了转换vertex covering，我们会将每个 vertext映射到一个 document。每个edge对应于一个 nugget，每个nugget会出现在两个 documents中。使用\(\alpha=1\)时的ideal gain vector会提供最小的vertex covering。

实际上，我们发现，使用一个greedy方法来计算ideal gain vector足够了。在每个step上，我们会选择具有最高gain value的document，断开任意的连接（ties）。如果我们从而遇到ties，该方法会计算ideal gain vector。如果ties出现，gain vector可能不是最优的。

5.2 \(\alpha\)-nDCG

计算nDCG的最终step是：我们会通过ideal discounted cumulative gain vector来归一化cumulative gain:

对于我们的QA示例：

在IR evaluation measures中很常见，nDCG会在一个queries集合上计算，对于单个queries会对nDCG值采用算术平均。nDCG通常会在多个检索depths上上报，与precision和recall类似。

我们的nDCG会通过在等式7中定义的gain value来对novelty进行rewards。否则，它会遵循nDCG的一个标准定义。为了区分nDCG的版本，我们将它称为\(\alpha-nDCG\)，在计算gain vector时会强调参数\(\alpha\)的角色。当\(\alpha=0\)时，\(\alpha-nDCG\) measure对应于标准nDCG，匹配的nuggets数目会用到graded relevance value。

• 1.https://plg.uwaterloo.ca/~gvcormac/novelty.pdf

Yu. A. Malkov等人在paper《Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs》中提出了HNSW，我们来看下：

介绍

随着信息资源的快速增长，在可扩展和高效相似搜索数据结构方面的需求越来越大。信息搜索的一种常用方法是：K-Nearest Neighbor Search(K-NNS)。K-NNS假设你具有一个已定义好的关于数据元素之间的距离函数（distance function），目标是：为一个query从数据集中寻找K个具有最小distance的elements。在许多应用中使用这样的算法，比如：非参数化机器学习算法、大规模数据集中的图片特征匹配、语义文档检索。K-NNS的一种naive方法是：计算query与数据集中的每个element的距离，并选择具有最小距离的elements。不幸的是，naive方法的复杂度与所存储的elements的总数是成线性增长的，这使得它在大规模数据集上是不可行的。因而，需要开发更快、可扩展的K-NNS算法。

由于“维数灾难”，当只有考虑相对低维的数据时，K-NNS的exact方法可以提供一个较大的搜索加速。为了克服该问题，提出了近似最近邻搜索（Approximate Nearest Neighbors Search (K-ANNS) ），它允许存在一小部分的错误（errors），从而放宽exact search的条件。inexact search(recall)的质量被定义成(true NN数目/K数目)的比值。最流行的K-ANNS解法有：基于树的近似版本[6,7]、LSH[8,9]、以及PQ(乘积量化：product quantization)[10-17]。在高维数据集上，邻近图K-ANNS算法由于良好的表现最近变得流行起来。然而，在低维或聚类数据上，邻近图路由（proximity graph routing）的幂律扩展（power-law scaling）会造成严重性能下降。

在本paper中，我们提出了Hierarchical Navigable Small World（Hierarchical NSW, HNSW），一种基于增量K-ANNS结构的新的完全图，可以提供更好的对数复杂度扩展（logarithmic complexity）。主要贡献有：

• 图的入点节点（enter-point node）的显式选取（explicit selection）
• 通过不同尺度(scales)将连接(links)进行分离
• 使用一个高级的启发法（heuristic）来选择neighbors

可选的，HNSW算法可以被看成是一种使用邻近图（proximity graphs，而非链表）的概率型跳表结构（probabilistic skip list structure）的扩展。效果评估表明，针对常用指标空间(general metric space)提出的该方法，效果要好于只应用于向量空间的state-of-the-art方法。

2.相关工作

2.1 近似图技术

图算法的大多数研究中，搜索（searching）会采用在kNN graphs中的贪婪路由（greedy routing）的形式。对于一个给定的邻近图(proximity graph)，我们会从某些enter point(可以随机、或者由一个独立算法提供)上开始搜索，并迭代遍历该graph。在遍历的每个step上，算法会检索query和当前base node的neighbors间的距离，接着选择可以最小化该距离的adjacent node作为下一个base node，并可以继续跟踪最好的已发现neighbors。当满足一些停止条件时(比如：距离计算的数目)，该search会终止。链接到一个k-NN graph中最近的neighbors，作为Delaunay graph（它可以保证一个基础的贪婪图遍历的结果总会是最近邻）的一个简单近似。不幸的是，如果没有先验信息，Delaunay graph不能被有效构建，但可以通过只使用在所存elements间的距离来得到最近邻从而进行近似。结果表明，使用这样的近似的邻近图（proximity graph）方法，效果完全要好于其它k-ANNS技术（比如：kd-trees和LSH）。

k-NN graph方法的主要缺点有：

• 1) 在routing过程期间，steps的数目与dataset size成幂律(power law)比例
• 2) 全局连通（global connectivity）的一个可能loss，在聚类数据上会导致很差的搜索结果。

为了克服这些问题，提出了许多混合方法，它们使用只适用于vector data的辅助算法(auxiliary algorithms)，通过一个粗粒度搜索（coarse search），来为enter point寻找更好的candidates。

在[25,26,30]中，作者提出了称为NSW（Navigable Small World）一个邻近图K-ANNS算法（也称为MSW: Metricized Small World），它使用可导航图（navibable graphs）（比如：在贪婪遍历期间，hops数与network size成对数或多重对数比例）。NSW graph通过以随机顺序的方式连续插入元素，将它们与M个最近的neighbors(来自之前插入元素）进行双向连接。M个最近neighbors可以使用该结构的搜索过程被找到。到该elements最近neighbors的连接（links）会在构建开始时插入，并在network hubs间进行桥接（bridges），从而保持全图连通性，并允许在greedy routing期间，hops数成对数比例扩展。

NSW structure的构建阶段可以通过高效并行化，无需全局同步（global synchronization）以及在accuracy上的没有影响，对于分布式搜索系统是一个好的选择。NSW方法在一些datasets上能达到SOTA的效果，然而，由于整体的多项对数复杂度扩展（polylogarithmic complexity scaling），该算法仍被证实在一些低维数据集上效果会下降（在这些数据集上，NSW会输给tree-based算法）。

2.2 NSW模型

关于greedy graph routing成对数和多重对数比例的networks被称为：NSW networks。这样的networks是复杂网络理论中一个重要主题，目标是理解真实网络信息中的底层机制，以便将它们用于scalable routing和distributed similarity search。

第一项工作是，paper[34]的navigable networks的spatial models作为社交网络模型，用于著名的米尔格拉姆实验。…

另一个知名的navigable networks是：scale-free models，它可以复制真实网络的一些特性，可用于routing应用[35]。…

上述的NSW算法使用一个更简单的，之前未知的navigable networks模型，允许分散化图构建，很适合任意空间的数据。[44]中建议，NSW network的机制可以作为大规模神经网络的navigability：相似的模型可以描述small brain networks的增长，而模型会预测在大规模神经网络中观察到的high-level features。然而，NSW模型也会得到在routing过程中polylog的搜索复杂度。

3.动机

提升NSW搜索复杂度的方式，可以通过routing process的分析来标识，它在[32,44]中被研究。routing可以被划分成两个阶段：“缩小（zoom-out）”和 “放大（zoom-in）”。greedy算法在”zoom-out”阶段从一个低degree node开始遍历graph，同时node的degree会增加，直到该node links length的特征半径达到距离该query的scale。在后者发生之前，一个node的平均degree可以相对较小，这会产生一个停留在很远的（distant）false local minimum上的递增概率。

你可以在NSW上避免上述问题，它从一个具有最大degree的node（好的candidates是那些插入到NSW结构中的first nodes）开启搜索，直接到该搜索的”zoom-in”阶段。测试表明，该setting中心会像起始点一样，实质增加成功在结构内路由的概率，并能在低维数据上提供更好的性能。然而，在单个greedy search上它仍只有一个多项式复杂度的扩展，对比起Hierarchical NSW它在高维数据上表现更差。

在NSW中一个single greedy search的多项式复杂度扩展(polylog scaling)的原因是：距离计算(distance computation)的总数，与greedy算法的平均数目和greedy path上nodes的平均度跳数乘积成比例。hops scales的平均数目是对数扩展的，而在greedy path上的平均degree也是对数扩展的，因为：

• 1) greedy search趋向于遍历和网络增长相同的hubs
• 2) hub connections的平均数目会随网络size的增加而对数增长

因而，我们会获得关于结果复杂度的一个总多项式依存。

Hierarchical NSW算法的思想是：将links根据它们的length scale分离到不同的layers上，接着以multilayer graph的形式进行search。在该case中，我们只需为每个element评估一个固定数目的connections（独立于networks size），从而允许一个log scalability。在这样的structure中，搜索会从upper layer开始（它具有最长的links）（即：“zoom-in”阶段）。该算法会贪婪地遍历upper layer中的elements，直到到达一个local minimum（见图1的演示）。接着，该search会切换到lower layer（它具有更短的links）；然后从在前一layer上具有local minimum的element进行restart，并重复该过程。在所有layers中的每个element上的connections的最大数目是常量，这样可以允许在NSW网络路由中进行一个log scaling复杂度。

图1 HNSW思想的图解。search会从top layer的一个element开始（红色部分）。红色箭头表示greedy算法的方向，从entry point到该query（绿色部分）

生成这样一个分层结构(layered structure)的一种方式是：通过引入layers，使用不同length scales来显式设置links。对于每一个element，我们会选择一个整数level l：它定义了该element所属layer的最大layer。对于在一个layer中的所有elements，会增量构建一个邻近图（proximity graph）（例如：graph只包含”short” links，它近似于Delaunay graph）。如果我们设置一个关于l的指数衰减概率（例如：根据一个几何分布），我们会获得在该structure中layers的期望数目的一个log scaling。该search过程是一个迭代式greedy search：它从top layer开始，在zero layer完成。

当我们合并来自所有layers的connections时，该structure变得与NSW graph相似（在该case中，可以被放置的l相当于在NSW中的node degree）。对比NSW，HNSW构建算法不需要在插入前进行shuffle——因为它的随机化（stochasticity）可以使用level randomization来达到，从而真正允许增量索引（incremental indexing），即使数据分布随时间变化（尽管插入顺序的轻微变更会影响效果，这是因为只有部分determenistic construction过程）。

HNSW的思想与著名的1D概率跳表结构非常相似，可以使用它的术语进行描述。与skip list的主要不同是：我们可以通过使用proximity graphs替代linked list来生成结构。HNSW方法可以使用相同的方式来做出分布式近似搜索／重叠结构（distributed approximate search/overlay structures）。

对于element insertion期间邻近图的connections的选择，我们会利用一个启发法：它会考虑上候选elements间的距离，来创建不同的（diverse）connections（在SA-tree中使用相似的算法来选择tree children），而非只选择最近的neighbors。该启发法会从nearest element开始检查candidates（相对于插入的element）；只有当该candidate比base element（已插入）更接近时（对比起任意已经连接的candidates），会创建到该candidatate的一个connection（详见第4节）。

当候选数目足够大时，该启发法允许获得exact relative neighborhood graph（精准的亲属邻居图）作为一个subgraph，通过只使用nodes间的距离来得到Delaunay graph的一个最小subgraph。relative neighborhood graph很轻易地保持全局连接的component，即使在高度聚类数据中（见图2）。注意，对比起exact relative neighborhood graph，启发法会创建额外edges，允许控制connections数目，这对于搜索性能很重要。对于1D数据的case，通过只使用与elements间距离相关的信息，启发法允许获得exact Delaunay subgraph，这使得从HNSW到1D probalilistic skip list算法有一个直接转换。

图2 为两个孤立clusters选择graph heighbors所使用的heuristic启发法。一个新的element会被插入到Cluster 1的边界上。该element的所有最近邻都会属于Cluster 1, 从而忽略在clusters间的Delaunay graph的edges。当插入的element最接近\(e_2\)时，对比起Cluster 1的其它element，该heuristic会从Cluster 2选择element \(e_2\)，来保持全局连通。

HNSW proximity graph的基础变种也在[18]中被使用，对于proximity graph searching被称为“sparse neighborhood graph”。相似的启发法也是FANNG算法的一个关注点。

4.算法描述

网络构建算法（算法1）通过连续插入存储的elements到graph结构中来进行组织。对于每个插入的element，会随机选中一个integer maximum layer l，并使用一个指数衰减概率分布（通过\(m_L\)参数归一化，详见算法1的第4行）。(说明：element更容易落到较高level上)

算法1:

input:

• hnsw: multilayer graph
• q: 新的element
• M: 已确立的connections数目
• \(M_{max}\)：每个payer上每个element的最大connections数目
• efConstruction：动态候选列表(danamic candidate list)的size
• \(m_L\)：level generation的归一化因子

输出：

• 插入element q更新后的hnsw

整个插入过程如下：

• 1.插入过程的第一阶段：从top layer开始，并贪婪地遍历该graph，以便在该layer上找到与插入的element q最近的ef个neighbors。
• 2.之后，该算法从下一layer继续搜索，使用从前一layer已发现最近的neighbors作为enter points，重复该过程。

在每个layer中，最近的neighbors会被算法2(greedy search算法的一个变种，它是[26]算法的一个更新版本）所发现。为了在一些layer \(l_c\)上获得近似的ef个最近的neighbors，会在搜索期间维护一个关于ef个已发现最近的elements（在enter points初始填充）动态列表W。该list会在每个step被更新：通过评估在list中之前未评估的最近的element的neighborhood，直到list中的每个element的neighborhood被评估。对比起限制distance计算的数目，HNSW的停止条件具有一个优点——它允许抛弃用于评估的candidates，从而避免搜索结构的膨胀。正如在NSW中，该list会通过两个优先级队列进行仿真来追求更好性能。与NSW的区别在于：

• 1）enter point是一个固定参数
• 2) 作为更换multi-searches的数目的替代，搜索质量会通过一个不同参数ef来搜索（它在NSW中被设为K）

算法2

在搜索的第一阶段，ef参数被设置为1(简单贪婪搜索），以避免引入额外参数。

当搜索达到layer no.<=l的layer时，构建算法的第二阶段会被初始化。第二阶段在两点上有不同：

• 1) ef参数会从1增加到efConstruction，以便控制greedy search过程的recall
• 2) 在每一layer上，已发现的最近的neighbors也会被作为candidates，用于inserted element的connections

算法3

从candidates中选择M个neighbors有两个方法可以考虑：

• 简单法：到最接近的elements的简单连接（算法3），
• 启发法：会考虑上candidate elements间距离，用来创建不同方向（diverse directions）的连接（算法4）。如第3节

算法4

该heuristic具有两个额外参数：

• extendCandidates：（缺省为false），它会扩展candidate set，只对极度聚集的数据有用
• keepPrunedConnections：允许每个element具有固定数目的connection

当被插入的elements的connections在zero layer被确立时，插入过程终止。

在HNSW中所使用的这种K-ANNS search算法如算法5所示。它大致等价于对于layer l=0的一个item的插入算法。不同之处是，在ground layer发现的最接近的neighbors（被当成candidates用于connections）会随搜索结果返回。搜索质量通过ef参数控制（对应于construction算法的efConstruction）。

算法5

4.1 construction参数的影响

construction参数\(m_L\)和\(M_{max()}\)会负责维护在所构建graphs的small world navigability。将\(m_L\)设置为0､并且将\(M_{max()}\)设置为M会生成directed k-NN graphs，它具有幂律（power-law）的搜索复杂度。将\(m_L\)设置为0､并且将\(M_{max()}\)设置为无穷大会导致生成NSW graphs，它具有polylog的复杂度。最终，将\(m_L\)设置成非零值，会产生受控的hierarchy graphs，它通过引入layers允许log搜索复杂度。

为了达到最优的效果，不同layers上的neighbors间的overlap必须很小。为了减小overlap，我们必须减小\(m_L\)。然而，同时，减小\(m_L\)会产生在每层上的greedy search的平均hop数的增加，这会对效果产生负面影响。这会导致\(m_L\)参数最优值的存在。

关于最优的\(m_L\)，一种简单选择是1/ln(M)，这对应于skip list参数\(p=1/M\)，层间的overlap具有一个平均single element。在Intel Core i& 5930K CPU上模拟得到，\(m_L\)的选择是个合理选项（见图3,在10M随机数据, d=4的vectors）。另外，该图展示了使用选择connections的heuristic，在低维数据上，当将\(m_L\)从0开始增加时会有一个大的加速，

4.2 复杂度分析

5.性能评估

HNSW算法通过nmslib c++实现，它是一个功能性NSW实现。由于该library的限制，为了达到一个更好的性能，HNSW实现使用定制的距离函数以及C-style的内存管理，这避免了不必要的隐式寻址，并允许在图遍历时进行高效的硬件／软件prefetching。

5.1 与base NSW的对比

5.2 欧氏空间中的对比

5.3 在general spaces上的对比

5.4 使用PQ的对比

参考

https://arxiv.org/pdf/1603.09320.pdf

1.介绍

计算高维向量间的欧氏距离，在许多应用中是一个基本需求。尤其是最近邻搜索问题中被广泛使用。由于维度灾难，最近邻搜索相当昂贵。在D维欧氏空间\(R^D\)上，该问题是：在一个n维vectors的有限集合\(Y \subset R^D\)，寻找element \(NN(x)\)，可以最小化与query vector \(x \in R^D\)间的距离：

…(1)

许多多维索引方法，比如KD-tree或其它branch&bound技术，被提出来减小搜索时间。然而，对于高维空间，发现这样的方法比起brute-force距离计算（复杂度O(nD)）并没有更高效多少。

一些算法文献通过执行ANN（近似最近邻）搜索来解决该问题。这些算法的关键点是：”只”寻找具有较高概率的NN，来替代概率1. 大多数研究都在欧氏距离上，尽量最近有研究在其它metrics上提出[10]。在本paper中，我们只考虑欧氏距离，它可以适用于许多应用。在本case中，一个最流行的ANN算法是欧氏局部敏感哈希算法（E2LSH），它在有限假设的搜索质量上提供了理论保证。它已经被成功用于local descriptors和3D object indexing。然而，对于真实数据，LSH还是通过启发法来执行，会利用vectors的分布。这些方法包括：randomized KD-trees、hierarchical k-means，这两种方法在FLANN选择算法上有实现。

ANN通常会基于search quality和efficiency间的trade-off来进行比较。然而，该trade-off并不能说明indexing结构的内存需要。在E2LSH的case上，内存的使用要比original vectors更高。另外，E2LSH和FLANN需要基于exact L2距离（如果访问速度很重要，它需要在主存中存储indexed vectros）来执行一个final re-ranking step。该constraint会严重限制可被这些算法处理的vectors的数目。最近，研究者们提出了受限内存使用的方法。该问题的关键是涉及大量数据，例如：在大规模场景识别[17]中，需要索引数百万到数十亿的图片。[17]中通过单个global GIST descriptor来表示一个图片，该descriptor可以被映射到一个short binary code上。当使用无监督时，会学到这样的mapping，以便在embedded space中由hamming距离定义的neighborhood可以影响在原features的欧氏空间中的neighborhood。欧氏最近邻的搜索接着被近似成：通过codes间的hamming距离的最近邻搜索。在[19]中，spectral hashing（SH）的效果要好于由RBM、boosting和LSH生成的binary codes。相似的，Hamming embedding方法[20]会在Bag-of-features的图片搜索框架中使用一个binary signature来重新定义quantized SIFT或GIST descriptors。

在本paper中，我们使用quantization来构建short codes。目标是使用vector-to-centroid distances来估计距离，例如：query vector是没有被量化的（quantized），codes只被分配给database vectors。这会减小quantization noise，进而提升搜索质量。为了获得精确的距离，quantization error必须被限制。因此，centroids的总数目k必须足够大，

例如：对于64-bit codes使用\(k=2^{64}\)。这会抛出一些问题：如何学到密码本（codebook）以及分配一个vector？

• 首先，要学到该quantizer所需的样本量很大，比如：k的许多倍。
• 第二，该算法本身的复杂度很高。
• 最后，地球上的计算机内存量不足以存储表示centroids的floating point。

hierarchical k-means(HKM)提升了learning stage、以及assignment过程的efficiency。然而，前面提到的限制仍存在，特别是：内存使用以及learning set的size。另一个可能是scalar quantizers，但他们提供了更差的quantization error特性。对于均匀向量分布，lattice quantizers提供了更好的quantization特性，但该条件在现实vectors中很难满足。特别的，这些quantizers执行在indexing任务上要比k-means更差。在本paper中，我们只关注product quantizers。据我们所知，这样的semi-structured quantizer从没有在任何最近邻搜索方法中考虑。

我们的方法有两个优点：

• 首先，可能的distances的数目要比competing Hamming embedding方法要更高，因为在这些技术中使用的Hamming space只允许少量distinct distance。
• 第二，作为byproduct方法，我们可以获得一个expected squared distance的估计，它对于e-radius搜索或者lowe’s distance ratio criterion来说是必需的。

在[20]使用Hamming space的动机是，高效计算距离。注意，然而，计算Hamming距离的最快方法之一，包含了使用table lookups。我们的方法会使用相同数目的table lookups，来产生相当的效率。

对于非常大的数据集，对所有codes与query vector进行遍历比较开销相当大。因此，引入一个modified inverted file结构来快速访问最相关vectors。会使用一个粗粒度量化器(coarse quantizer)来实现该inverted file结构。其中，对应于一个cluster(index)的vectors会被存储在一个相关列表中。在该list中的vectors通过short codes（通过product quantizer计算得来）来表示，被用于编码对应于聚类中心的其它vector。

我们的方法的关注点是：在两种vectors上进行验证，称为local SIFT和global GIST descriptors。通过SOTA对比，我们的方法要好于之前的技术（比如：SH， Hamming embedding以及FLANN）。

2.背景知识：quantization、product quantizer

关于vector quantization有大量文献提供。在本节，我们聚焦在相关概念上。

A. Vector quantization

Quantization是一个分解性过程（destructive process），它在信息论中被大量研究。它的目标是，减小representation space的基数（cardinality），特别是当输入数据是real-valued时。

正式的：一个quantizer是一个函数q，它将一个D维向量\(x \in R^D\)映射到vector q(x)上：

其中：

• index set \(I\)是假设是有限的：\(I=0, \cdots, k-1\)。
• reproduction values \(c_i\)：表示centroids。
• reproduction values C的集合：称为size k的codebook。

vectors映射到一个给定index i上的集合\(V_i\)，被称为一个(Voronoi) cell，定义为：

…(2)

一个quantizer的k个cells形成了\(R^D\)的一个划分（partition）。通过定义可知：在同一cell \(V_i\)上的所有vectors，可以通过相同centroid \(c_i\)来构建。一个quantizer的quality通常通过input vector x和它的reproduction value \(q(x)\)间的MSE来进行测量：

…(3)

其中，\(d(x,y)=\| x-y \|\)是x和y的欧氏距离，\(p(x)\)是随机变量X的概率分布函数。对于一个专门的概率分布函数，等式(3)数值上使用Monte-Carlo sampling进行计算，作为在一个大数据集样本\(\|q(x)-x\|^2\)上的平均。

为了让quantizer是最优的，必须满足L1oyd optimality condition的两个特性。

• 1. vector x必须被quantized到它最近的codebook centroid，根据欧氏距离：

…(4)

作为结果，cells通过超参数来限定。

• 2. 重构值(reconstruction value)必须是在Voronoi cell上vectors的期望值：

…(5)

Lloy quantizer，它对应于k-means cluster算法，通过迭代式分配一个training set的vectors给centroids、并将这些已分配vectors的centroids进行re-estimating的方式来寻找一个接近最优的codebook。

下面，我们会假设两个Lloyd conditions成立，正如我们使用k-means来学习该quantizer。注意，然而，k-means只会根据quantization error来找一个local optimum。

下面会使用到的另一个quantity是：当构建一个由通过相应的centroid \(c_i\)得到的cell \(V_i\)的vector时，获得的均方失真\(e(q,c_i)\)。通过\(p_i=P(q(x)=c_i)\)来表示一个vector被分配给centroid \(c_i\)的概率，它可以通过下式计算：

…(6)

注意，MSE可以通过这些quantities来获得：

…(7)

存储index value（没有进一步处理（entropy coding））的内存开销，是\(log_2 k\) bits。因此，使用一个k的2阶很方法，因为通过quantizer生成的code以binary memory的方式生成。

B. Product quantizers

假设我们考虑一个128维的vector，例如，SIFT descriptor [23]。一个quantizer会产生64-bits codes，例如，每个component只有0.5 bit，包含了\(k=2^{64}\)的centroids。因此，使用Lloyd算法或HKM并不重要，因为所需的样本数据、以及学习该quantizer的复杂度是：k的数倍。为了表示k个centroids要存储\(D \times k\)的floating point值是不可能的。

product quantization是一个高效的解决该问题的解法。它是source coding中的常用技术，允许选择要进行联合量化(quantized jointly)的components的数目（例如，24个components的groups可以使用强大的Leech lattice来量化）。

input vector x被split成m个不同的subvectors \(u_j, 1 \leq j \leq m\)，维度为\(D^* = D/m\)，其中D是m的倍数。这些subvectors会使用m个不同的quantizers进行单独量化。一个给定vector x因此根据如下进行映射：

…(8)

其中：

• \(q_j\)是低复杂度的quantizer，它与第j个subvector有关。
• subquantizer \(q_j\)与index set \(I_j\)、codebook \(C_j\)、以及相应的reproduction values \(c_j,i\)有关。

product quantizer的reproduction通过product index set \(I=I_1 \times \cdots \times I_m\)的一个element进行标识。codebook因此被定义成Cartesian product：

…(9)

以及该set的centroid是m个subquantizers的centroid的拼接（concatenation）。从现在开始，我们假设，所有subquantizers具有相同的有限数目\(k^*\)的reproduction values。在该case中，centroids的总数由下式给定：

…(10)

注意：在极端情况下(m=D)，一个vector x的所有components是被完全独立量化的。这时，product quantizer就变成了一个scalar quantizer。其中，与每个component有关的quantization function是不同的。

一个product quantizer的力量是：使用多个centroids的小集合（它们与subquantizers有关）来生成一个更大的centroids集合。当使用Lloyd算法学习该subquantizers时，会使用有限数目的vectors，在某种程度上，codebook仍会采用数据分布来表示。学习该quantizer的复杂度为： m X 对\(k^*\)个具有\(D^*\)的centroids执行k-means聚类的复杂度。

对codebook C显式存储效率不高。相反，我们会存储所有subquantizer的\(m \times k^*\)个centroids，例如：\(m D^* k^*=k^* D\)个floating points值。对一个element进行量化需要\(k^* D\)个floating point操作。表1总结了与k-means、HKM、product k-means对应所需的资源。product quantizer很明显是唯一可以被用于当k为大值时可以进行内存索引的方法。

表1

当选择一个常数值\(k^*\)，为了提供较好的量化属性，通常每个subvector都应具有一个可对比的energy。确保该特性的一个方法是：通过将该vector乘以一个随机正交矩阵来进行quantization。然而，对于大多数vector types，这并不是必需的，也不推荐，因为连续的components通常通过construction来关联，并可以更好地与相同的subquantizer一起被量化。由于subspaces是正交的，与product quantizer的平方失真（squared distortion）为：

…(11)

其中，\(MSE(q_j)\)是与quantizer \(q_j\)相关的失真（distortion）。图1展示了MSE是一个关于不同\((m, k^*)\)tuples的code length的函数，其中code length为\(l = m log_2 k^*\)，如果\(k^*\)是2的幂。该曲线通过一个128维SIFT descriptors的集合获得，详见第V部分。你可以观察到，对于固定数目的bits，最好使用一个小数目的subquantizers以及更多centroids，要比使用许多subquantizers和更少centroids的要好。当m=1的极端情况下，product quantizer会成为一个常规的k-means codebook。

图1

\(k^*\)的值越高，会增加quantizer的计算开销，如表1所示。它们也会增加存储centroids（\(k^* \times D floating point值\)）的内存使用量，当centroid look-up table不再fit cache内存时，这会进一步降低效率。在这种情况下m=1，超过16 bits来保存这样的开销可追踪将承受不起。使用\(k^*=256\)和\(m=8\)通常是一个合理的选择。

3.使用quantization进行搜索

最近邻搜索依赖于query vector与database vectors间的distances，或者squared distances。这节引入的方法会使用source coding技术的精髓，基于quantization indices的vectors进行比较。我们首先解释了被用于计算distances的product quantizer性质。接着我们提供了一个在distance estimation error上的统计边界，并提出了一个refined estimator来计算squared Euclidean distance。

A.使用quantized codes来计算distances

假设我们考虑query vector x和database vector y。我们提出两种方法来计算它们间的近似欧氏距离：对称法（symmetric）和非对称法（asymmetric）。见图2.

图2 sym和asym的距离计算。对于左图，距离d(x,y)通过d(q(x),q(y))来估计；对于右图，距离d(x,y)通过d(x,q(y))来估计。通常，距离上的MSE受限于quantization error

SDC（Symmetric distance computation）：

vectors x和y通过它们各自的centroids q(x)和q(y)来表示。距离d(x,y)通过\(d(x,y) \triangleq d(q(x), q(y))\)近似，它使用一个product quantizer来高效获取：

…(12)

其中，\(d(c_{j,i}, c_{j,i'})^2\)是从一个与第j个subquantizer相关的lookup table中读取。每个lookup table包含了centroids pairs \((i,i')\)间所有的squared distances，或者\((k^*)^2\)的squared distances。

ADC（Asymmetric distance computa）

database vector y通过q(y)表示，但query x不会被编码。距离d(x,y)通过\(\hat{d}(x,y) \triangleq d(x,q(y))\)来近似，它使用decomposition进行计算：

…(13)

其中：

• squared distances： \(d(u_j(x), c_{j,i})^2: j=1 \cdots m, i= 1 \cdots k^*\)，是在search之前计算好的。

对于最近邻搜索，我们在实际中不会计算均方根（square roots）：square root函数是单调递增的，squared distances会生成相同的vector ranking。

表II总结了涉及到vector x与dataset Y中搜索k个最近邻的不同steps的复杂度。可以看到，SDC和ADC具有相同的query准备开销，它不依赖于dataset size n。当n很大时（\(n > k^* D^*\)）， 大多数开销操作是公式12和等式13的求和。对于搜索k个最小elements在该表中的复杂度为：当elements是任意顺序时，对于\(n >> k\)的平均复杂度。

表2

SDC比ADC好的一个优点是：限制与queries相关的内存使用量，因为query vector通过一个code定义。这在大多数情况没啥太大意义，因而你可以使用一个asym版本，它对于一个相似复杂度可以获得一个更低distance distortion。后续部分我们主要关注ADC。

4.非穷举搜索（non-exhaustive search）

使用PQ的最近邻搜索很快（对于每个距离计算，只需要m个加法），并且可以极大减小内存需求。另外，该search是穷举（exhaustive）的。该方法在global image description的内容上仍然是可扩展的。然而，如果每张图片通过一个local descriptors集合描述，穷举搜索是禁止的，因为我们需要检索数十亿descriptors并执行多个queries。

为了避免穷举搜索，我们会组合一个IVF系统（inverted file system），并使用asynmmetric distance computation（IVFADC）。一个inverted file会对对descriptors进行量化，并在相应的lists中存储图片索引，见图5的“coarse quantizer”。这会允许快速访问图片索引的一小片，这对于非常大规模的搜索是很成功的[26]。除了只存储图片索引外，我们会为每个descriptor添加一个small code，这在[20]中首次这样做。这里，我们会使用一个product quantizer来对vector和它相应的coarse centroid间的不同之处进行编码，见图5。该方法可以极大加速search，每个descriptor只需很少的额外bits/bytes开销。再者，它对search accuracy的提升很微小，因为对残差（residual）进行编码要比对vector自身编码更精准。

图5

A.Coarse quantizer，局部定义了product quantizer

与“Video-Google”[26]方法相似，通过使用k-means学到一个codebook，这会带来一个quantizer \(q_c\)，被称为“coarse quantizer”。对于SIFT descriptors，与\(q_c\)相关的centroids数目为\(k'\)，通常范围为k’=1000 ~ 1,000,000。对比在第3节中使用的product quantizers的k来说较小些。

除了coarse quantizer外，我们会采用一个与[20]提出的相似的strategy，例如，一个vector的description通过一个code（由一个product quantizer获得）重定义。然而，为了解释由coarse quantizer提供的信息，例如，centroid \(q_c(y)\)与一个vector y相关，product quantizer \(q_p\)被用于编码residual vector：

…(28)

对应于在Voronoi cell中的offset。对比vector自身，residual vector的energy很小。该vector通过下式近似：

…(29)

它通过tuple \((q_c(y), q_p(r(y)))\)表示。通过与“二进制表示”类比发现，coarse quantizer提供了最高有效位（most significant bits），而product quantizer的code相当于最低有效位（least significant bits）。

d(x,y)的估计值（其中x是query，y是database vector），可以通过x和\(\ddot{y}\)间的距离 \(\ddot{y}(x,y)\)对比：

…(30)

通过\(q_{p_j}\)定义了第j个subquantizer，我们使用以下decomposition来有效计算该estimator：

…(31)

与ADC的做法相类似，对于每个subquantizer \(q_{p_j}\)，在partial residual vector \(u_j(x-q_c(y))\)与\(q_{p_j}\)所有centroids \(c_{j,i}\)间的距离是预先计算好并进行存储好的。

在residual vectors集合上学到的product quantizer通过一个learning set收集到。尽管该vectors被coasrse quantizer量化到不同indexes上，生成的residual vectors被用于学习一个唯一的product quantizer。我们假设：当在所有Voronoi cell上的residual的分布是边缘的时，相同的product quantizer是精准的。这可能会为该方法给出差的结果（该方法包含了learning，并为每个Voronoi cell使用一个不同的product quantizer）。然而，这在计算上开销很大，需要存储\(k'\)个product quantizer codebooks，例如：\(k' \times d \times k^*\)的浮点值，它对于\(k'\)的公共值来说内存过大(memory-intractable)。

B. indexing结构

我们使用coarse quantizer来实现一个inverted file结构作为一个lists数组： \(L_1 \cdots L_{k'}\)。如果\(y\)是到index的vector dataset，与\(q_c\)的centroid \(c_i\)相关的list \(L_i\)，会存储集合\(\lbrace y \in Y: q_c(y) = c_i \rbrace\)。

在inverted list \(L_i\)，一个entry对应于y，包含了一个vector identifier以及被编码的residual \(q_p(r(y))\)：

表3

由于intered file结构，identifier字段是overhead。依赖于要存储的vectors的特性，identifier不必是唯一的。例如，为了通过local descriptors来描述图片，image identifiers可以替代vector identifiers，例如，所有相同图片的vectors具有相同的identifier。因此，一个20-bit field足够标识来自100w数据集中的一个图片。该内存开销可以使用index压缩进一步减小，它可以将存储该identifier平均开销减小到8bits，取决于参数。注意，一些几何信息可以被插入到该entry中，如[20]中提出的。

C. Search算法

该inverted file是非穷举（non-exhaustive）版本的核心。当搜索一个vector x的最近邻时，inverted file提供了Y的一个子集，用于估计距离：只\(q_c(x)\)对应的inverted list \(L_i\)会被扫到。

然而，x和它的最邻近并没有被量化到相同的centroid上，而是在附近一个centroid上。为了解决该问题，我们使用多个assignment策略[29]。该query x会被分配到w个indexes上（而非单个），它对应于在\(q_c\)的codebook中x的w个最近邻。所有相应的inverted lists都会被扫描到。多个assignment不会被应用到database vectors，因为这将增加内存使用。

图5给出了一个关于一个database是如何被index和search的总览。

Indexing一个vector y的过程

• 1) 将y量化到\(q_c(y)\)
• 2) 计算residual：\(r(y) = y - q_c(y)\)
• 3) 将\(r(y)\)量化到\(q_p(r(y))\)，对于product quantizer来说，相当于将\(u_j(y)\)分配给\(q_j(u_j(y))\)，其中\(j=1 \cdots m\)
• 4) 添加一个new entry到\(q_c(y)\)对应的inverted list中。它包含了vector (或image) identifier以及binary code（product quantizer的indexes）。

Searching

一个query x的最近邻包含了：

• 1) 将x量化到在codebook \(q_c\)中的w个最近邻。为了简明，在下两个step，我们会通过将r(x)表示与w assignments相关的residuals。这两steps会被应用到所有的w assignments中。
• 2) 对于每个subquantizer j和每个centroid \(c_{j,i}\)，计算squared distance \(d(u_j(r(x)), c_{j,i})^2\)
• 3) 计算在r(x)间的squared distance，以及inverted list的所有indexed vectors。使用在前一step计算的subvector-to-centroid distances，这包含了对m个looked-up values求和；
• 4) 基于estimated distances选择x的K个最近邻。这可以通过维护一个固定容量的Maxheap结构来高效实现，它可以存储K个最小值。在每次距离计算后，只有point identifier被添加到该结构，如果它的距离在Maxheap的最大距离之下。

只有step 3依赖于database size。通过与ADC进行对比，将x量化到\(q_c(x)\)的求和step 包含了在D维vectors间计算\(k'\)个距离。假设inverted lists是balanced，那么需要解析\(n \times w/ k'\)个entries。因此，search要比ADC更快，下一节将介绍。

5. NN Search的评估

分析SDC、ADC、IVFADC的参数影响。我们的方法会对比三个SOTA方法：spectral hashing、hamming embedding、FLANN。最终评估复杂度和加速。

略

参考

• 0.Product quantization for nearest neighbor search

faiss中有IVF的概念。其实就是inverted file (IVF)。它在2003的《Video Google: A Text Retrieval Approach to Object Matching in Videos》中提出。我们来看下，该paper有两段提及，我们来看下：

一、

文本检索系统通常需要采用一些标准steps。文档首先被解析成words。接着，words通过它们的stems来表示，例如：“walk”、”walking”、”walks”会使用stem ‘walk’来表示。第三，会使用stop list来拒绝常用words，比如：”the”、”an”，它们很常见。剩余words接着会被分配一个唯一的id，每个document会通过一个vector来表示，该vector的components由该文档中所包含的words的词频组成。除了components会以多种方式加权外，在google的case中，一个web page的weighting取决于web pages链接到特定页的数目。上述所有steps都在实际检索前完成，在语料中的所有文档会表示成vectors集合，通过一个inverted file进行组织来更高效的检索。一个inverted file的结构类似于一个理想的book index。在corpus中每个word都有一个entry，它会跟一个该word出现的所有文档（以及在该文档中的位置）的list。

一个text会通过计算词频向量进行检索，并返回最近向量（通过角度）的文档。

二、目标检索(object retrieval)

实现-使用inverted files：在一个经典的文件结构中，所有words会存储在它们出现的文档中。一个inverted file结构，会为每个word生成一个entry（hit list），并存储在所有文档中该word的出现次数。在我们的case中，inverted file会为每个可视化的word生成一个entry，它会存储所有matches，例如：在所有帧中相同word的出现次数。document vector是非常稀疏的，使用一个inverted file可以使得检索非常快。在2GHz的pentium上使用matlab实现，查询一个4k frames的database只需要0.1秒。

三、faiss IVF

上面提到的都是IR中的inverted file。关于faiss IVF，Chris McCormick在它的blog中有提到，我们可以看下：

Inverted File Index(IVF) 是pre-filtering技术，以便你无需对所有vectors做exhaustive search。实现相当简单：首先，你使用聚类(比如：kmeans)将数据集聚类生成较大数目（比如：100个）的数据分区(partitions)。接着，在query时，你会将你的query vector与partition centroids进行对比，（例如：找到10个最近的聚类），接着你只在这些分区上对vectors进行搜索。

在IR中，”inverted index”指的是文本搜索索引，它会将词汇表中的每个词映射到数据文档中的所有位置。看起来有点像textbook的索引，将words映射到page numbers，因而称为inverted index。

然而，在我们的上下文中，该技术的意思是，使用k-means聚类将数据集进行划分，以便你可以重定义你的搜索（只需搜索部分分区，忽略其它）。

在构建index时，使用聚类将数据集聚到多个partitions上。在dataset中的每个vector会属于这些clusters/partitions的其中之一。对于每个partition，你都具有一个属于它的所有vectors的list（被称为：inverted file lists）。你具有关于所有这些partition centroids的一个matrix，它会被用于找出哪些partitions会进行search。

按这种方式划分数据集并不完美，因为如果一个query vector落到离它最近cluster的外面，那么它的最近邻很可能停留在多个附近的cluster上。解决该问题的简单方法是，搜索多个partitions。搜索多个附近的partitions很明显会花费更多时间，但它会给出更好的accuracy。

在搜索时，你可以比较你的query vector与所有partition centroids来找到离它最近的partition。可以配置多少个。一旦你发现了这些centroids，你只需从这些partitions中选择dataset vectors，使用product quantizer来进行KNN search。

需要注意一些术语：

• verb “probe”指的是，选择partitions进行search。代码中你会看到index参数”nprobe”意味着：有多少partitions进行probe。
• Faiss的作者喜欢使用术语：Voronoi cells（而非“dataset partitions”）。一个Voronoi cell指的是，属于一个cluster的space区域。也就是说，它会包含在space中的所有points（vector与某个cluster的centroid会比其它clusters更接近）。

4.faiss doc上的解释

Inverted list objects & scanners

faiss实现了two low-level APIs来泛化inverted list存储。这对于以key-value数据库存储lists很有用。

• InvertedLists抽象类定义了inverted lists是如何从搜索代码被访问的。任意提供该interface的对象可以被用来保存lists。
• InvertedListsScanner提供了细粒度的访问，因为scanning function可以在用户提供的id和code tables上被调用

4.1 IndexIVF回顾

IndexIVF类(以及它的子类)可以被被用于Faiss的所有大规模应用中。它会将input vectors聚类成nlist个groups（nlist是IndexIVF的一个field）。在add时，一个vector会被分配一个groups。在search时，与query vector最相似的groups会被识别出，并进行穷举扫描（exhaustively scan）。

因而，IndexIVF具有两个components：

• quantizer（也称为：coarse quantizer）index。给定一个vector，quantizer index的search function会返回该vector所属的group。当使用nprobe>1的结果进行search时，它会返回与query vector最接近的nprobe个groups（nprobe是IndexIVF的一个field）。
• InvertedLists对象。该object会将一个group id（\(0 \cdots nlist-1\)）映射到一个(code, id) pairs序列上.

4.2 InvertedLists对象

• Codes：指的是一个常量size(code_size)的byte strings。例如，36维的IndexIVFFlat具有的code_size=36 * sizeof(float) = 144 bytes。
• Ids：64-bit integer（负值是保留的，因此有用位只有63bits）

实际上，codes和ids会以两个独立的arrays返回，因为一些applications只需要其中之一，并且memory alignement是不同的。

4.2.1 search方法

该object有有三个相关的方法：

/// get the size of a list
size_t list_size(size_t list_no);

/// @return codes    size list_size * code_size
const uint8_t * get_codes (size_t list_no);
void release_codes (const uint8_t *codes) const;

/// @return ids      size list_size
const idx_t * get_ids (size_t list_no);
void release_ids (const idx_t *ids) const;

通过get_codes(以及get_ids)获得的指针需要通过release_codes(以及release_ids)来释放。如果你喜欢RAII，InvertedLists::ScopedCodes（以及InvertedLists::ScopedIds）会有用。

有一个额外的prefetch_lists方法，它会通过search方法被用来通知InvertedLists对象：一些inverted lists会在不久被用到。

因此，search过程的调用顺序如下：

search(v) {
    list_nos = quantizer->search(v, nprobe)
    invlists->prefetch(list_nos)
    foreach no in list_nos {
        codes = invlists->get_codes(no)
        // linear scan of codes
        // select most similar codes 
        ids = invlists->get_ids(no)
        // convert list indexes to ids
        invlists->release_ids(ids)
        invlists->release_codes(codes)
    }
}

4.2.2 add()方法

添加vectors需要有对InvertedLists对象的read-write权限。这通过add_entries方法提供。其它方法update_entries和resize被用于扩充（bulk）操作，比如，merging、 splitting、removing elements。

4.3 InvertedLists对象的行为

4.3.1 内存管理

如果own_invlists为true，InvertedLists对象通过IndexIVF的destructor被删除。缺省的，ArrayInvertedLists对象会在IndexIVF实例化时被构建，own_invlists被设置为true。缺省的invlists可以被replace_invlists所替代，用户必须决定所属关系(ownership)。

4.3.2 Threading

只读操作允许多线程访问。一些注释关于并发读写操作。

4.3.3 I/O

InvertedLists对象不需要和index object一起存储。如果不是这样，index object只包含处理外存（external storage）的所需信息。

4.4 Build-in InvertedLists类

InvertedLists类主要考虑可扩展性而设计。然而，在Faiss中有两个InvertedLists classes。

4.4.1 ArrayInvertedLists

这是一个std::vector<std::vector<…> >。这是最简单的in-RAM inverted lists实现，开销很少，add时间很快。它有一个特殊状态（status），因为当一个IndexIVF被构建时它会被自动实例化，因此这些vectors会被马上add。

4.4.2 OnDiskInvertedLists

该inverted list data被存储到磁盘的一个内存映射文件上（memory-mapped file）。会存在一个间接表（indirection table），它将list ids映射到file上的offset。 由于data是memory-mapped，没必要显式地从disk上取数据。然而，prefetch函数很有用，可以用上分布式文件系统的并发读。

有意思的是，通过将IO_FLAG_MMAP flag设置为read_index，一个“normal” IndexIVF可以被加载进一个OnDiskInvertedLists中。这使得它可以加载任意数目的indexes，无需担心是否满足RAM。

4.5 InvertedListScanner对象

Inverted list scanning可以在Faiss之外被控制。这使得没必要实现list访问函数作为回调，这不是惯例。

为了支持它，Faiss提供了：

• encode_vector函数：它可以将inverted list codes计算成一个array中，用来放到不受faiss管理的inverted lists
• InvertedListScanner对象：可以通过IndexIVF类获得。它会扫描lists、或计算单个query-to-code distance。

该访问非常low-level，但用户具有对scanning的total control，无需实现像InvertedLists对象的回调。

4.6 Encoding vectors

为了编码vectors，calling code应：

• 对该vector进行quantize，来寻找要存到哪个inverted list
• 调用encode_vectors来实际编码它

两个函数会进行batch操作以便提高效率。

以下是一个简化代码，它会将nb vectors存储到xb中，来定制inverted lists：

// size nb
idx_t *list_nos = ... ; 
// find inverted list numbers 
index_ivf.quantizer->assign (nb, xb, list_nos);

// size index->code_size * nb
uint8_t *codes = ...; 
// compute the codes to store
index->encode_vectors (nb, xb, list_nos, codes);

// populate the custom inverted lists 
for (idx_t i = 0; i < nb; i++) {
      idx_t list_no = list_nos[i]; 
      // allocate a new entry in the inverted list list_no
      // get a pointer to the new entry's id and code
      idx_t * id_ptr = ... 
      uint8_t * code_ptr =  ...
      // assume the vectors are numbered sequentially
      *id_ptr = i; 
      memcpy (code_ptr, codes + i * index->code_size, index->code_size);
}

详见test_lowlevel_ivf.cpp (add)

4.7 Searching

为了执行search，存在一些loop levels。

以下是执行query的简化代码。它会查询在index中np个vectors xq。

// size nprobe * nq
float * q_dis =  ...
idx_t *q_lists = ...
// perform quantization manually
index.quantizer->search (nq, xq, nprobe, q_dis, q_lists); 

// get a scanner object
scanner = index.get_InvertedListScanner();

// allocate result arrays (size k * nq), properly initialized
idx_t *I = ...
float *D = ...

// loop over queries
for (idx_t i = 0; i < nq; i++) {
    // set the current query
    scanner->set_query (xq + i * d);

    // loop over inverted lists for this query
    for (int j = 0; j < nprobe; j++) {
        // set the current inverted list
        int list_no = q_lists[i * nprobe + j];
        scanner->set_list (list_no, q_dis[i * nprobe + j]);

        // get the inverted list from somewhere
        long list_size = ...
        idx_t *ids = ....
        uint8_t *codes = ....
        // perform the scan, updating result lists
        scanner->scan_codes (list_size, codes, ids, D + i * k, I + i * k, k); 
   }
   // re-order heap in decreasing order
   maxheap_reorder (k, D + i * k, I + i * k);
}

参考

• Video Google: A Text Retrieval Approach to Object Matching in Videos

• http://mccormickml.com/2017/10/22/product-quantizer-tutorial-part-2/

• https://github.com/facebookresearch/faiss/wiki/Inverted-list-objects-and-scanners