deepmind在《Emergence of Locomotion Behaviours in Rich Environments》提出了PPO。我们来看下:

1.介绍

2.使用Distributed PPO进行大规模增强学习

我们在增强学习上关注的点是,在丰富的仿真环境上使用连续state和action spaces。我们的算法在多个任务变种上是健壮的,可以有效扩展到其它领域。我们将轮流介绍每个issues。

使用PPO的Robust policy gradients

深度学习算法基于大规模、高吞吐的optimization方法,在离散和低维action spaces中(比如:Atari games和三维导航(3D navigation))可以产生state-of-the-art的结果。作为对比,许多之前的工作都是基于连续动作空间的,关注一些可对比的小问题。大规模、分布式的optimization较少广泛使用,相应的算法也很少被开发。我们发布了一个robust policy gradient算法,很适合高维连续控制的问题,可以使用分布式计算扩展到许多更大的领域上。

Policy gradient算法为连续控制(continuous control)提供了一个吸引人的范式。他们通过根据stochastic policy \(\pi_{\theta}(a \mid s)\)的参数\(\theta\)直接最大化rewards的期望和:

\[J(\theta) = E_{\rho_{\theta}(\tau)} [\sum_t \gamma^{t-1} r(s_t, a_t)]\]

该期望会对应于由policy \(\pi_{\theta}\)和系统动态性(dynamics) \(p(s_{t+1} \mid s_t, a_t)\)两者所联合生成的trajectories\(\tau=(s_0,a_0,s_1,\cdots)\)的分布:

\[\rho_{\theta}(\tau) = p(s_0) \pi(a_0 | s_0) p(s_1 | s_0, a_0) ...\]

\(\theta\)对应的目标函数的梯度是:

\[\nabla_{\theta} J = E_{\theta} [\sum_t \nabla_{\theta} log \pi_{\theta}(a_t | s_t)(R_t - b_t)]\]

其中:

  • \[R_t = \sum_{t'=t} \gamma^{t'-t} r(s_{t'}, a_{t'})\]
  • \(b_t\)是一个baseline(它不依赖于\(a_t\)或者future states和actions)。该baseline通常会选择\(b_t = V^{\theta} (s_t) = E_{\theta} [R_t \mid s_t]\)。

实际上,期望的future return通常近似于使用一个sample rollout,\(V^{\theta}\)通过一个学到的近似\(V_{\phi}(s)\)和参数\(\phi\)来替代。

Policy gradient的estimates可以有很高的variance,算法对于超参数的设置很敏感。有许多方法可以使得policy gradient算法更健壮。一种有效的measure是:采用一个trust region constraint,可以限制policy update的任意更新量(amount)。采用该思想的一种流行算法是:TRPO(trust region policy optimization)。在每个迭代中,给定当前参数\(\theta_{old}\),TRPO会收集一个(相对较大)的batch数据,并优化surrogate loss:

\[J_{TRPO}(\theta) = [ \sum_t \gamma^{t-1} \frac{\pi_{\theta}(a_t | s_t)}{\pi_{\theta_{old}}(a_t | s_t)} A^{\theta_{old}}(a_t, s_t)]\]

它会服从一个constraint:policy被允许更改多少,以KL divergence的方式表示:

\[KL[\pi_{\theta_{old}} | \pi_{\theta}] < \delta\]

\(A^{\theta}\)是advantage function,可以通过\(A^{\theta}(s_t, a_t) = E_{\theta}[R_t \mid s_t, a_t] - V^{\theta}(s_t)\)得到。

PPO算法可以被看成是一个依赖于一阶梯度的TRPO的近似版本,它可以更方便地使用RNNs,并可以用在一个大规模分布式setting中。trust region constraint通过一个正则项来实现。使用的正则项系数依赖于该是否先前违反了constraint。算法1展示了PPO算法的伪代码。

算法1 PPO

在算法1中,超参数\(KL_{target}\)是在每个iteration上policy的期望变更。如果在policy上的实际变更很低、或者大大超过target KL,归一化项\(\alpha > 1\)可以控制着KL-正则参数的调整(例如:落在区间\([\beta_{low} KL_{target}, \beta_{high} KL_{target}]\)之外)。

分布式PPO(DPPO)进行可扩展增强学习

为了在丰富的、仿真环境上达到较好性能,我们实现了一个分布式版本的PPO算法(DPPO),数据的收集和梯度计算在workers间是分布式的。我们使用同步更新和异步更新进行实验,发现平均梯度和将以同步方式使用会导致更好的结果。

原始的PPO算法会使用完整的rewords求和来估计advantages。为了使用RNN及batch updates,同时支持可变长的episodes,我们会遵循与[2]相似的策略(strategy),并使用一个长度为K的空间的截断BPTT(truncated backpropagation through time)。这使得它很自然地(虽然不是必须)使用K-step returns来估计advantage,例如:我们会在相同的K-step windows对rewards求和,并在K-steps后对value function进行bootstrap:\(\hat{A}_t = \sum_{i=1}^{K} \gamma^{i-1} r_{t+i} + \gamma^{K-1} V_{\phi}(s_{t+k} - V_{\phi}(s_t)\)

John Schulman[20]的公开提供的PPO实现对于核心算法增加了一些修改。它们包含了对inputs、rewards、以及在loss中的一个额外项(它会惩罚对于较大违反trust region constraint的情况)的normalization。我们采用在分布式setting中相似的augmentations,但发现在跨多个workers间对多个统计进行sharing和synchronization需要一些注意。我们的分布式实现(DPPO)采用tensorflow,参数在一个parameter server中,workers会在每个gradient step后同步它们的参数。伪码和详情在附件中提供。

A.DPPO

A.1 算法详情

DPPO算法的伪码在算法2和算法3中提供。W是workers的数目;D会为workers的数目设置一个阀值,它们的gradients必须被提供来更新参数。M,B是在给定一个batch的datapoints,使用policy和baseline updates的sub-iterations的数目。T是在参数更新被计算之前每个worker收集的data points的数目。K是用于计算K-step returns和truncated BPTT的time steps的数目。

算法2:

算法3:

normalization

根据[20]我们会执行以下的normalization steps:

  • 1.我们会通过减mean并除以标准差,将observations(或者 states \(s_t\))进行归一化。。。
  • 2.我们会通过一个正在运行的关于标准差的estimate对reward进行缩放(scale),在整个实验过程中进行聚合
  • 3.我们会使用关于advantages的per-batch normalization

跨workers共享算法参数

在分布式setting中,我们发现,对于跨workers的data normalization来说共享相关统计很重要。Normalization在数据收集(collection)期间使用,统计会在每个environment step之后被本地更新。当一次迭代完成时,统计的本地变改(local changes)在数据收集(collection)后被应用到全局统计中。随时间变化(time-varying)的正则化参数\(\lambda\)也会跨workers共享,但更新会基于本地统计(它基于对每个worker在本地计算的平均KL)来决定,通过使用一个调整参数\(\hat{\alpha} = 1+(\alpha-1)/K\)由每个worker单独使用。

额外的trust region constraint

当KL超过期望变更的一个特定margin时(),我们也会采用一个额外的罚项。在我们的分布式实现中,该criterion会在一个per-worker basis上进行测试和应用。

参考

阿里在paper《Deep Session Interest Network for Click-Through Rate Prediction》中提出了基于session的ctr预测模型,我们可以借鉴一下:

0.

大多数已经存在的研究会忽略序列内在的结构:序列由sessions组成,其中sessions是发生时间内独立的用户行为。我们可以观察到:在每个session中的用户行为是同度同质的,不同sessions间差异很大。基于此观察,提出了新的CTR模型:DSIN,它可以利用在行为序列中的用户多个历史sessions。我们首先使用self-attention机制以及bias encoding来抽取每个sessions的用户兴趣。接着,我们应用Bi-LSTM来建模:用户兴趣是如何在sessions间演化和交互的。最后,我们使用local activation unit来自适应学习多个session interests对target item的影响。实验表明:DSIN效果要好于state-of-the-art模型。

1.介绍

如图1所示,从真实工业界应用中抽样得到的一个用户,我们将它的行为序列分为3个sessions。sessions按如下原则进行划分:时间间隔超过30分钟[Grbovic and Cheng, 2018]。该用户在session 1内主要浏览长裤(trousers),在session 2中浏览戒指(finger rings),在sessions 3内浏览大衣(coats)。图1的现像很普遍。它表明:一个用户通常在一个session内有一个明确唯一的意图,而该用户开启另一个session时会发生剧烈变化

图1 真实应用中的一个关于sessions的demo。图片下的数字表示当前item上点击时间与首个item点击时间之间的时间间隔,以秒计。原则上,Sessions以超过30分钟进行划分.

受上述观察的启发,我们提出了DSIN(Deep Session Interest Network)来在CTR预测任务上,通过利用多个历史sessions来建模用户序列行为。DSIN有三个关键部分。

  • 首先,将用户序列行为划分成sessions
  • 接着,使用self-attention network以及bias encoding来建模每个session。Self-attention可以捕获session行为(s)的内在交互/相关,接着抽取每个session的用户兴趣(s)。这些不同的session interests可能相互间相关,接着遵循一个序列模式。
  • 最后,我们使用Bi-LSTM来捕获交互、以及用户多个历史session interests的演进。由于不同session interests对于target item具有不同的影响,最终我们设计了local activation unit根据target item来聚合他们,形成该行为序列的最终表示。

主要贡献:

  • 我们强调用户行为在每个session中高度同质,不同sessions差异很大。
  • 设计了一个self-attention network以及bias encoding来获得每个session的精准兴趣表示。接着我们使用Bi-LSTM来捕获历史sessions间的顺序关系(sequential relationship)。最后,考虑到不同session interest在target item上的影响,我们使用local activation unit来聚合。
  • 两组比较实验。表明DSIN效果更好。

2.相关工作

2.1 CTR

2.2 Session-based推荐

session的概率常被序列化推荐提及,但很少出现在CTR预测任务中。Session-based推荐受益于用户兴趣在sessions上动态演化的启发。GFF使用关于items的sum pooling来表示一个session。每个item具有两种表示,一个表示自身,另一个表示session的上下文(context)。最近,RNN-based方法被应用于session-based推荐中来捕获在一个session中的顺序关系。基于此,Li 2017提出了一个新的NARM(attentive neural networks framework)来建模用户的序列化行为,并能捕获用户在当前session中的主要目的。Quadrana 2017提出的Hierarchical RNN依赖于RNNs的latent hidden states跨用户历史sessions的演化。另外,Liu 2018 的RNNs使用self-attention based模型来有效捕获一个session的long-term和short-term兴趣。Tang 2018使用CNN、Chen 2018使用user memory network来增强序列模型的表现力。

3.DSIN

3.1 BaseModel

本节主要介绍BaseModel所使用的:

  • feature representation,
  • embedding,
  • MLP以及loss function。

特征表示

CTR预测任务中统计了大量信息特征。总共使用了三大组:User profile、item profile、User Behavior。每组包含了一些稀疏特征:

  • User Profile包含了gender、city等;
  • Item Profile包含了:seller id、brand id等;
  • User Behavior包含了用户最近点击的item ids等

注意,item的side information可以进行拼接来表示自身。

Embedding

MLP

Loss Function

3.2 模型总览

在推荐系统中,用户行为序列包含了多个历史sessions。用户在不同sessions上兴趣不同。另外,用户的session interests相互间有顺序关联。DSIN提出了在每个session上抽取用户的session interest,并捕获session interests间的顺序关系。

图2 DSIN模型总览。在MLP layers前,DSIN主要由两部分组成。一部分是sparse features,另一部分处理用户行为序列。自顶向上,用户行为序列S首先被划分成sessions Q,它接着会加上bias encoding,并使用self-attention来抽取session interests I。有了Bi-LSTM,我们将session interests I和上下文信息进行混合作为hidden states H。session interests I和hidden states H的Vectors受target item的激活,User profile和item profile的embedding vectors被拼接在一起,进行flatten并被feed到MLP layers中进行最终预测

如图2所示,DSIN在MLP前包含了两部分。一部分是从User Profile和Item Profile转向后的embedding vectors。另一部分是对User Behavior进行建模,自顶向上具有4个layers:

  • 1) session division layer,会将用户行为序列划分为sessions
  • 2) session interest extractor layer:会抽取用户的session interests
  • 3) session interest interacting layer:会捕获session interests间的顺序关系
  • 4) session interest activating layer:会对与target item有关的session interests使用local activation unit

最后,session interest activating layer的最终输出、以及User Profile和Item Profile的embedding vectors被feed给MLP做最终预测。以下述章节中,我们会引入这4个layers。

1.Session Division Layer

为了抽取更精准的用户的session interests,我们将用户行为序列S划分成sessions Q,其中第k个session为:

\[Q_k = [b_1; \cdots; b_i; \cdots; b_T] \in R^{T \times d_{model}}\]

其中:

  • T是我们在该session中的行为数
  • \(b_i\)是在该session中的用户第i个行为

相邻行为间存在的user sessions的划分,会遵循该原则:时间间隔超过30分钟

2.Session Interest Extractor Layer

在相同session中的行为,相互之间强相关。另外,用户在session中的偶然行为会使得该session interest偏离它的原始表示(original expression)。为了捕获在相同session中的行为间的内在关系,并减少这些不相关行为的效果,我们在每个session中使用multi-head self-attention机制。我们也对self-attention机制做了一些改进来更好地达到我们的目的。

2-1 Bias Encoding

为了利用sequence的顺序关系,self-attention机制会应用positional encoding到input embeddings中。另外,sessions的顺序关系,以及在不同表示子空间中存在的bias需要被捕获。因而,我们在position encoding的基础上提出了bias encoding(BE):

\[BE \in R^{K \times T \times d_{model}}\]

其中BE中的每个元素被如下定义:

\[BE_{(k,t,c)} = w_k^K + w_t^T + w_c^C\]

…(2)

其中:

  • \(w^K \in R^K\):是session的bias vector
  • k:是sessions的索引
  • \(w^T \in R^T\):是在session中position的bias vector
  • t:是在sessions中行为的索引
  • \(w^C \in R^{d_{model}}\):是在behavior embedding中unit position的bias vector
  • c:是在behavior embedding中unit的index

在加上bias encoding后,用户的behavior sessions Q按如下方式更新:

\[Q = Q + BE\]

…(3)

2-2 Multi-head Self-attention

在推荐系统中,用户的点击行为受许多因素(颜色、风格、价格等)的影响。Multi-head self-attention可以捕获不同表示子空间的表示。数学上,假设:

\[Q_k = [Q_{k1}; \cdots; Q_{kh}; \cdots; Q_{kH}]\]

其中:

  • \(Q_{kh} \in R^{T \times d_h}\):是\(Q_k\)的第h个head
  • H是heads的数目
  • \[d_h = \frac{1}{h} d_{model}\]

\(head_h\)的输出如下计算:

\[head_h = Attention(Q_{kh} W^Q, Q_{kh} W^K, Q_{kh} W^V) \\ =softmax(\frac{Q_{kh} W^Q W^{K^T} Q_{kh}^T}{\sqrt{d_{model}}}) Q_{kh} W^V\]

…(4)

其中,\(W^Q, W^K, W^Q\)是线性矩阵。

接着不同heads的vectors被拼接到一起被feed到一个feed-forward network中:

\[I_k^Q = FFN(Concat(head_1, \cdots, head_H) W^O)\]

…(5)

其中,\(FFN(\cdot)\)是feed-forward network,\(W^O\)是线性矩阵。我们也在相继使用了residual connections和layer normalization。用户的第k个session的兴趣\(I_k\)按如下方式计算:

\[I_k = Avg(I_k^Q)\]

…(6)

其中,\(Avg(\cdot)\)是average pooling。注意,在不同sessions间self-attention机制中的weights是共享的。

3.Session Interest Interacting Layer

用户的session interests会持有带上下文的顺序关系。建模动态变化会增强session interests的表示。Bi-LSTM在捕获顺序关系是很优秀的(此处有疑问?? self-attention也能捕获顺序关系,感觉有些多此一举),很天然地可应用于在DSIN中建模session interest的交互。LSTM cell的实现如下:

\[i_t = \sigma(W_{xi} I_t + W_{hi} h_{t-1} + W_{ci} c_{t-1} + b_i) \\ f_t = \sigma(W_{xf} I_t + W_{hf} h_{t-1} + W_{cf} c_{t-1} + b_f) \\ c_t = f_t c_{t-1} + i_t tanh(W_{xc}I_t + W_{hc} h_{t-1} + b_c) \\ o_t = \sigma(W_{xo} I_t + W_{ho} h_{t-1} + W_{co}c_t + b_o) \\ h_t = o_t tanh(c_h)\]

…(7)

其中,\(\sigma(\cdot)\)是logistic function,其中: i,f,o,c分别是:input gate、forget gate、output gate、cell vector,它们具有与\(I_t\)相同的size。权重矩阵的shapes可以通过下标来表示。Bi-direction意味着存在forward和backward RNNs,hidden states H按如下方式计算:

\[H_t = \overrightarrow {h_{ft}} \oplus \overleftarrow {h_{bt}}\]

…(8)

其中,\(\overrightarrow {h_{ft}}\)是forward LSTM的hidden state,\(\overleftarrow {h_{bt}}\)是backward LSTM的hidden state。

4.Session Interest Activating Layer

与target item更相关的用户的session interests,对于用户是否点击该target item的影响更大。用户的session interests的weights需要根据target item进行重新分配。Attention机制(再做一次attention)会使用在source和target间的soft alignment,被证明是一个很有效的weight allocation机制。与target item相关的session interests的自适应表示可以如下计算得到:

\[a_k^I = \frac{exp(I_k W^I X^I)}{\sum\limits_k^K exp(I_k W^I X^I)} \\ U^I = \sum\limits_k^K a_k^I I_k\]

…(9)

其中\(W_I\)具有相应的shape。相似的,session interests的自适应表示会混杂着与target item相关的上下文信息,如下计算:

\[a_k^H = \frac{exp(H_k W^H X^I)}{\sum\limits_k^K exp(H_k W^H X^I)} \\ U^H = \sum\limits_k^K a_k^H H_k\]

…(10)

其中\(W_H\)具有相应的shape。User Profile和Item Profile的Embedding vectors,\(U^I\)和\(U^H\)会被拼接到一起,flatten,然后feed给MLP layer。

4.实验

略.

参考

#

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)映射到用户表示上,它可以公式化为:

\[V_u = f_{user}(I_u, P_u)\]

…(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获取:

\[\vec{e}_i = f_{item}(F_i)\]

…(2)

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

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

\[f_{score}(V_u, \vec{e}_i) = \underset{1 \leq k \leq K}{max} \vec{e}_i^T \vec{e}_u^k\]

…(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\),它相应的向量为:

\[\vec{c}_i^l \in R^{N_l \times 1}, i \in \lbrace 1,\cdots,m \rbrace\]

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

\[\vec{c}_j^h \in R^{N_h \times 1}, j \in \lbrace 1, ..., 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}\)):

\[b_{ij} = (\vec{c}_j^h)^T S_{ij} \vec{c}_i^l\]

…(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}\)耦合系数):

\[\vec{z}_j^h = \sum\limits_{i=1}^m w_{ij} S_{ij} \vec{c}_i^l\]

…(5)

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

\[w_{ij} = \frac{exp (b_{ij})}{ \sum\limits_{k=1}^m exp (b_{ik})}\]

…(6)

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

\[\vec{c}_j^h = squash(\vec{z}_j^h) = \frac{\| \vec{z}_j^h \|^2}{ 1 + \| \vec{z}_j^h \|^2} \frac{\vec{z}_j^h}{ \| \vec{z}_j^h \|}\]

…(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可以通过以下公式计算:
\[b_{ij} = \vec{u}_j^T S \vec{e}_i, i \in I_u, j \in \lbrace 1, \cdots, \rbrace\]

…(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数):

\[K_u' = max(1, min(K, log_2(|I_u|)))\]

…(9)

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

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

a1.png

算法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,可以计算如下:

\[\begin{align} \vec{v}_u & = Attention (\vec{e}_i, V_u, V_u) \\ & = V_u softmax(pow(V_u^T \vec{e}_i, p)) \end{align}\]

其中:

  • 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间的概率:

\[Pr(i | u) = Pr(\vec{e}_i | \vec{v}_u) = \frac{exp(\vec{v}_u^T \vec{e}_i)}{ \sum_{j \in I} exp(\vec{v}_u^T \vec{e}_j)}\]

…(10)

接着,对于训练MIND的整个目标函数为:

\[L = \sum\limits_{(u,i) \in D} log Pr(i|u)\]

…(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.png

图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.png

图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分布

7.png

图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.png

图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的高性能,用于预测服务的深度网络会每天更新一次,可以保证最新的商品被计算和被曝光。

参考

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\)间的距离:

\[NN(x) = \underset{y \in Y}{argmin} \ d(x,y)\]

…(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)上:

\[q(x) \in C = \lbrace c_i; i \in I \rbrace\]

其中:

  • 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,定义为:

\[V_i \triangleq \lbrace x \in R^D : q(x)=c_i \rbrace\]

…(2)

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

\[MSE(q) = E_x[d(q(x), x)^2] = \int p(x) d(q(x),x)^2 dx\]

…(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,根据欧氏距离:
\[q(x)=\underset{c_i \in C}{argmin} \ d(x,c_i)\]

…(4)

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

  • 2. 重构值(reconstruction value)必须是在Voronoi cell上vectors的期望值
\[c_i = E_x [x | i] = \int_{v_i} p(x | x \in V_i) x dx\]

…(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\)的概率,它可以通过下式计算:

\[e(q,c_i) = \frac{1}{p_i} \int_{v_i} d(x,q(x))^2 p(x) dx\]

…(6)

注意,MSE可以通过这些quantities来获得:

\[MSE(q) = \sum\limits_{i \in I} p_i e(q, c_i)\]

…(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因此根据如下进行映射:

\[\underbrace{x_1, \cdots, x_{D^*}}_{u_1(x)}, \cdots, \underbrace{x_{D-D^*+1}, \cdots, x_D}_{u_m(x)} \rightarrow q_1(u_1(x)), \cdots, q_m(u_m(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:

\[C = C_1 \times \cdots \times C_m\]

…(9)

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

\[k = (k^*)^m\]

…(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)为:

\[MSE(q) = \sum\limits_j MSE(q_j)\]

…(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来高效获取:

\[\hat{d}(x,y) = d(q(x), q(y)) = \sqrt{ \sum\limits_j d(q_j(x), q_j(y))^2}\]

…(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进行计算:

\[\hat{d}(x,y) = d(x,q(y)) = \sqrt{ \sum\limits_y d(u_j(x), q_j(u_j(y)))^2}\]

…(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:

\[r(y) = y - q_c(y)\]

…(28)

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

\[\ddot{y} \triangleq q_c(y) + q_p (y - q_c(y))\]

…(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)\)对比:

\[\ddot{d}(x,y) = d(x,\ddot{y}) = d(x-q_c(y), q_p(y-q_c(y)))\]

…(30)

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

\[\ddot{d}(x,y)^2 = \sum\limits_j d(u_j(x - q_c(y)), q_{p_j}(u_j(y-q_c(y))))^2\]

…(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。最终评估复杂度和加速。

参考