Yury Malkov在《Approximate nearest neighbor algorithm based on navigable small world graphs》提出了NSW算法。

在了解NSW之前，我们先看下SW(small world)的定义，from wikipedia。

0.Small world

一个small-world network是一种graph。在该graph中，大多数nodes相互之间都不是neighbors，但对于任意给定的node的neighbors，这些neighbors很可能相互之间也是neighbors，大多数nodes可以通过一个较小数目的hops或steps从每个其它node来到达。特别的，一个small-world network被定义成这样一个网络：其中两个随机选中的nodes间的一般距离（typical distance）L，会与在该网络中与nodes N的数目成log比例增长，即：

\[L \propto log\ N\]

其中，聚集度（clustering coefficient）并不小。在社交网络场景中，这会导致Small world现象：陌生人间通过一个关于熟人的短链进行连接。许多经验图（empirical graphs）展示了small-world效应，包括：社交网络、wikipedia的wikis、基因网络、以及Internet的底层架构。在现代计算机硬件中的许多片上网络(network-on-chip)架构也受它的启发。

Ducan Watts 1998. 将一种特定类型的small-world networks定义成一类random graphs。他们注意到，graphs可以根据两个独立的结构化特征进行分类，称为：聚集度（clustering coefficient）、以及平均node-to-node距离（也被称为：平均最短路径长度）。纯随机图（purely random graphs），根据ER模型构建，会有一个很小的平均最短路径长度，以及一个较小的聚集度。Watts等发现：事实上许多实际网络具有一个较小的平均最短路径长度，以及一个要比random chance所期望的要高很多的一个聚集度。Watts等接着提出了一个新的graph模型，称为WS model，它具有：

• (i)一个较小的平均最短路径长度
• (ii) 一个大的聚集度

图0

SMall-world的性质

small-world趋向于包含团（cliques）、近团（near-cliques），它们表示子网络，这样的子网络中任意两个nodes间都有connections。这由较高的聚集度的定义性质产生。第二，大多数nodes pairs至少由一个短路径进行连接。这由较小的平均最短路径长度性质产生。一些其它性质也经常与small-world network相关。通常，在网络中存在过多的hubs-nodes，会具有大量connections（也被称为：较高的degree nodes）。这些hubs作为公共connections，作为与其它edges间短路径长度的中介。通过类比，航空公司的small-world network具有一个较小的mean-path length（例如：两个城市间，你可能必须花三或更少的航班），因为许多航班会通过hub城市进行路由。该性质通常通过考虑在网络中的nodes的比例（具有特定数目connections经过它们，即该network的degree分布）来进行分析。比起具有更大hubs的network会具有一个更大比例的高degree的nodes，因此，degree分布会在高degree值上被增强。也被称为是“宽尾分布（fat-tailed distribution）”。具不非常不同拓朴的graphs，可以作为small-world networks，只要他们满足上述两个必须的定义。

介绍

任意软件系统的可扩展性受它的数据结构的扩展性限制。大规模分布式系统，像Bittorrent 、Skype都基于分布式hash tables。后者的数据结构具有良好的可扩展性，但它们的搜索功能只限定于exact matching。该限制的提出是因为：当一个element value做出微小变更时，会导致在hash value上出来大的变化，使得hash-based方法很难应用于range search以及相似度搜索问题上。

然而，有许多应用（比如：模式识别、图片内容检索、机器学习、推荐系统、DNA序列相似发现、语义文档检索等）需要进行相似度搜索，而非exact matching。KNNS问题是相似度搜索的一个数学公式。被定义如下：

给定一个query \(q \in D\)（其中：D是所有可能对象的集合），我们需要从一个有限对象集合\(X \subseteq D\)中寻找k个最近的对象 \(P \subseteq X\)。两个对象\(o', o'' \in D\)的相近度或近似度可以定义成一个距离函数\(\delta(o', o'')\)。

KNNS问题的一个naive解法是：计算q与X中的每个element的距离函数\(\delta\)。这会导致线性搜索时间复杂度，使得它很难用于large size的datasets上。

我们的解法是：将数据结构表示成一个graph \(G(V,E)\)，其中来自X每个object \(o_i\)会与V中的一个顶点(vertex) \(v_i\)唯一关联。为query q搜索X中的最近elements的问题，就转化成了：在graph G中搜索一个vertices集合。

这为构建面向分布式相似度搜索（decentralized similarity search oriented）的存储系统带来了机遇，其中物理数据位置(physical data location)不依赖于内容(content)，因为每个数据对象可以被放置在任意一个物理机器上，可以通过links相互连接，就像p2p系统一样。

在具有metric objects的graphs中的基础顶点搜索算法(basic vertex search algorithms)之一是：贪婪搜索算法(greedy search)。它有一个简单实现，可以从任意顶点初始化。为了让该算法正确工作（总是返回精确结构），该网络必须包含Delaunay graph作为它的subgraph，它与Voronoi tessellation成对偶关系。然而，与Delaunay graph相关的主要缺点是：它需要知道metric space的内部结构，这会遭受维度灾难。再者，对于上述应用，不需要precise exactness的search。因此，发现exact的最近邻的问题，可以通过ANNS来替代，因而我们不需要支持whole/exact Delaunay graph。

具有log scalibility的graphs的greedy search算法，被称为NSW graphs，它们定义在Euclidean spaces上。注意，像paper[10]中的small world模型（不是navigable small world）不会有该特性。尽管在graph中有短路径（short paths），greedy算法不会趋向于寻找它们，在结束时具有幂次的搜索复杂度。构建一个NSW graphs的解法，是针对general spaces提出的，但他们通常更复杂，需要做采样、迭代、rewiring等。我们展示了small word的navigation特性可以通过一个更简单的技术来达到，无需对metric space内部结构的先验知识（例如：维度、数据的density分布）。

在本paper中，我们为该数据结构构建提出了一个简单算法，它基于一个NSW network拓朴，使用greedy search算法来做ANNS。graph G(V,E)包含了Delaunay graph的近似，具有long-range links以及small-world navigation特性。我们提出的search算法可以选择search的accuracy，无需修改结构。提出的算法不会使用坐标表示，不会假定Euclidean spaces的特性，因为它们只基于objects与query间的距离比较，因此原则上，可以应用于general metric(或non-metric) spaces的数据上。实验表明，对于欧氏数据只能很弱的维度依赖。

2.相关工作

kd-tree和quadra trees首先应用在kNN问题上。它们在2-3维数据表现良好（搜索复杂度接近O(logn)），但这些结构最坏case的分析有\(O(d^*N^{1-1/d})\)的复杂度，其中d是维度。

在[8]中提出了一个完全近邻搜索（exact-proximity search）结构，它使用Delaunay graph和greedy search算法。作者表示，在通用metric space中发现exact Delaunay graph是不可能的，为了保持search的exact，他依赖回溯（backtracking）。提出的数据结构在高维数据上的构建时间为\(O(n log^2n / log log n)\)、搜索时间为\(O(n^{1-\theta(1/log log n)})\)；在低维数据上为\(0 < \alpha < 1\)。

总之，当前没有方法能有效在高维指标空间上进行有效的exact NNS。背后的原因是维数灾难。为了避免维数灾难，仍在elements数目中保留对数开销，提出减少kNN问题解的需求，使它近似（近似kNN）。

有两种近似最近邻搜索的常用定义。

• 方法一：使用预定义的accuracy \(\epsilon(\epsilon-NNS)\)。它意味着，query和在结果中的任何element间的距离不超过\(1+\epsilon\) 乘以 query到它真正第k个最近邻的距离。这样的方法在[19-23]中有描述。
• 方法二：使用”recall”（true k最近elements的比例）来给出概率，保证找到离query最近的k个true closest的点。

一些结构(19-23)只能应用到欧氏空间（Euclidean space）。其它方法[24-31]则应用到通用指标空间(general metric spaces)上。更多详见[32-33]。

PI（排列索引）是一种有效的无分布算法，很适合通用指标空间。PI背后的思想是，将每个database object使用索引集合的排列进行表示，并通过与该object的距离进行排序。objects间的距离暗示着各自排列间的距离。PI对于高维数据集具有很高的precision和recall。

paper [26] 则构建一个概率化tree-like结构来在通用指标空间上进行ANNS，它基于最近邻的选择。该算法会模似现实数据。paper[27]则在构建算法时决定最近邻，在搜索时使用greedy算法。该算法的主要缺点是与dataset size的线性扩展性很差。两种算法都提供了很高的recall。

paper[9]使用NSW和greedy search算法来寻找最近邻。该算法依赖于link length概率\(r^{-\gamma}\)遵循幂律的random long-range links，其中\(\gamma\)对应navigation，2维lattice对应用结果纠正。为了具有NSW特性，link length分布必须具有一个指定值\(\gamma\)。在Voronet[35]中，Kleignberg的方法被扩展到任意2维数据上，通过构建一个二维的Delaunay三角化来替代regular lattic。在[13]中。。。

3.核心思想

structure S通过一个graph G(V,E)所表示的NSW network来构建。

• graph G(V,E)：表示的一个navigable small word网络，其中，来自集合X的objects是唯一映射到set V的vertices上，会通过structure S来构建。
• edge E的集合由sturecture构建算法来决定。

术语：

• vertex/element/object：由于每个vertex会唯一映射到集合X的一个element上，我们会交替使用术语“vertex”、”element”和”object”。
• friend：我们会使用术语“friends”来表示共享一个edge的vertices。
• friend list：vertices的列表会与vertex \(v_i\)共享一个公共edge，被称为vertex \(v_i\)的friend list。

我们会使用greedy search算法的一个变种作为base算法来进行k-NN search。它会遍历该graph，每次从一个element到另一个element，会选择一个离该query最近的未访问friend，直到它达到一个停止条件。见4.2节所述。

注意，在graph中的links（edges）有两个不同作用：

• 1) short-range links：一个子集，被用于Delaunay graph的一个近似，由greedy search算法所需
• 2) long-range links：另一个子集，它被用于greedy search的对数扩展（log scaling）。它负责contructed graph的NSW属性。

结构的表现如图1所示。

图1 structure的图表示。

• 圆（verticles）：是在metric space中的data
• 黑色的edges：是Delaunay graph的近似
• 红色的edges：是log scaling的long range links
• 箭头：表示greedy算法的样本路径，从entry point到query（绿色）。

该structure的构建基于所有elements上的连续插入。对于每个新进入的element，我们会发现离该structure最近的neighbors的集合（Delaunay graph 近似）。该set被连接到该element，反之亦然。随着越来越多的elements被插入到该structure，之前作为short-range links的links会变成long-range links，从而生成一个NSW。在该结构中的所有queries是独立的；它们可以并行完成，如果elements被随机放置到物理计算机节点上，处理query的负载可以跨物理节点共享。

4.搜索算法

4.1 basic greedy search算法

basic single NN搜索算法会以从一顶点到另一顶点的方式遍历graph G(V,E)上的edges。该算法有两个参数：query和vertex \(V_{entry\_point} \in V[G]\)，它是一个search的起始点（entry point）。从entry point开始，该算法会计算query q到当前vertex的friend list上的每个vertex的距离，接着选择具有最小距离的一个vertex。如果query和所选vertex间的距离小于当前距离（query和当前element），那么该算法会移到所选vertex上，它将变成新的current vertex。当它达到一个local minimum时，该算法会停止：一个vertex的friend list不包含这样的vertex（比起friend list上的vertex，该vertex与query更近）。该算法如下：

算法1

该element对于query \(q \in D\)都有一个local minimum：在该set X中的所有elements中的一个element，它与query q的距离真实最接近（true closet）、或者错误最接近（false closet，即一个error）。

如果structure中的每个element，都在它的voronoi neighbors的friend list中有保存，那么这会阻止false global minima的存在。维护这样的条件等价于构建Delaunay graph，它是Voronoi diagram的对偶(dual)。

结果表明，为一个未知metric space决定exact Delaunay graph是不可能的，因为我们不能避免false global minima的存在。对于上述定义的近似搜索的问题，它并不是个障碍，因为近似搜索不需要整个Delaunay graph。

注意，与在[19-23]中定义的ANN（其中它被表述成e-neighborhood）是有区别的。像[24-31]，在我们的sturcture中，对于算法NN结果和true NN结果间的距离绝对值没有限制。该结果保证是有概率的，意味着：只有寻找true最近邻的概率是有保证的。当数据分布高度倾斜，并且很难为所有regions定义value e时，使用这样的搜索有效性定义更便利。

4.2 k-NN搜索的修改版

在我们[36]的工作中，我们使用一种基于m个searches的series的k-NN搜索的简单算法，并返回它们的最佳结果。对于每个后续的search，找不到最邻近的概率会指数递减，无需重构建（reconstruction）就可以增强（boosting）该sturcture的accuracy。

在该部分，我们提出了一个更复杂版本的kNN算法，它有两个关键修改：

• 1) 使用了不同的stop condition：该算法会在与该queries最接近的、但之前未访问过的elements上进行迭代（例如：那些link list未被读到的elements）。当在下次迭代时它会停止，对该query的k个最近的结果不会变。简言之，该算法会继续以一种greedy的方式探索最接近elements的neighborhood，只要在每个step上它可以提升已知的k个closest elements。
• 2) 列表visitedSet：即之前被访问过的elements，它会被跨搜索序列共享，以便阻止无用的重复抽取。

算法2

有序列表TreeSet的使用，允许以与该query的接近顺序来保存评估过的elements，这可以很方便地从该set中抽取最近的elements，它在steps 6, 9, 20被需要。

如果m足够大，该算法会成为一个exhaustive search，假设entry points不会被重复使用。如果该网络的graph具有small-world属性，那么它可以选择一个随机vertex，无需任意metric计算，在随机steps数目（与dataset size的log成比例）后，这不会产生整体的log搜索复杂度。

5.数据插入算法

由于我们会构建一个Delaunay graph的近似（approximation），在构建算法(construction algorithm)细节上有很大的自由度。主要目标是：最小化false global minima的概率，并能保持links数目尽可能小。可以使用一些基于metric space拓朴的方法。例如，[13]中提出了构建近似Delaunay graph的方法：对于graph中的每个vertex所对应的一个固定数目的edges，通过最小化相应的Voronoi region的volume（通过monte-carlo法）的来构建。我们提出通过1-by-1的方式插入数据来生成该structure，并在每个step将它们相连接（使用在该sturcture中已经存在的f个closest objects）。我们的方法基于elements set（它们是Voronoi neighbors）和f个closest elements的交叉（intersection）。

该graph可以通过所有elements的顺序插入来构建。对于每个新进来的element，我们会从该sturcture中寻找与它相关的最近邻集合（Delaunay graph近似）。该set会与该element连接，反之即然。这种方法的一个优点是，使用general metric数据，以随机顺序到达的方式创建的一个graph，具有small word navigation特性，无需任何其它额外安排。

为了决定f个最近elements的集合，我们使用近似knn搜索算法(4.2节)，该算法会具有三个参数：

• object: 在该sturcture中被插入的element
• f: 连接的最近邻数目，正整数
• w: multi-searches的数目，正整数

首先，该算法决定了一个包含f个local closest elements的neighbors集合，它会使用K-NNSearch过程（4.2）节。在new_object之后，被连接到在set中的每个object，反之亦然。

算法3

5.1 参数选择

参数w影响着在构建算法中最近邻的accurate的测定。如4.2节，将w设置到一个大数目，等价于在structure中最近elements的exhaustive search，产生一个perfect recall。该思想是，将w设得足够大，以便recall接近1 (比如：0.95-0.99）。recall越小会产生一部分wrong links，这会公增加算法复杂度，而我们的实验表明，在插入时增加超过0.99的recall，对于search quanlity没有重大效果。测试已经表明，对于最优的recall，w会随dataset size变化很慢（成log关系），因此如果我们已经知道，对于一个好的recall的近似\(w_0\)，我们可以运行随机query tests，首先使用更大的m（比如：\(m=2*w0 + 10\)），假设：对于搜索结果为true k个最近邻来说，m足够大，那么，增加w，重复测试直到我们具有一个高的recall（例如：0.95-0.99）。操作复杂度与dataset size成log关系，因为它不会影响整个构建复杂度。

测试表明，对于Eucild数据(d=1,…, 20)，对于connect(f)的neighbors的数目的最优值是3d，使得内存消耗与维度成线性关系。f的值越小，可以被用来减小single search的复杂度，满足它的recall quality。

6.结果与讨论

6.2 small world navigation特性

为了验证small world navigation特性，对于不同维度Euclidean spaces上的点（见图2），我们会通过greedy search算法来测量搜索的平均path length。f的值被设置成3d。该图很明显地表明，greedy search的path length与dataset size成log依赖，表明提出的structure是一个navigable small word。注意，对于更高维度的依赖是更弱的。这不能归因于f的不同值，但可能是因为“拓朴直径”的减小。当greedy算法遇到long range links，它会选择该方向上与query接近的elements，并忽略其它方向，使得搜索准一维(quasi-one-dimensional)。

如果我们添加elements可以保证扩展set的volume（例如：非随机插入）、或者更新elements的links（删除那些不与任一最近f个elements相连的links），那么log复杂度会降低。这些事实表明，naivgable small world特性是基于Delaunay近似links的long-range links的（它在构建的开始被创建）。

图2

参考

Approximate nearest neighbor algorithm based on navigable small world graphs

1.介绍

1.1 Voronoi Diagrams

定义：给定点集(points) \(P=\lbrace p_1, \cdots, p_n \rbrace\)，点(point)\(p_i\)的Voronoi region \(V(p_i)\)是这样一个点集，它们到\(p_i\)的距离要与P中其它任意点都要接近\(p_i\)：

\[V(p_i) = \lbrace x \mid |p_i - x| \leq |p_j -x|, \ \ \forall 1 \leq i,j \leq n \rbrace\]

在P中具有超过一个最近邻的点集，是P的Voronoi Diagram：

• 具有两个最近邻的集合组成diagram的edges
• 具有三或更多最近邻的集合组成了diagram的verticles

点集P被称为Voronoi diagram的sites。

• 当只有2个点时，\(P=\lbrace p_1, p_2 \rbrace\)，regions可以由垂直平分线定义，如图p1所示。
• 当只有3个点时，\(P=\lbrace p_1, p_2 \rbrace\), regions可以由三条垂直平分线定义：

图p1

• 更一般的，与点\(p_i\)相关的Voronoi region，是由垂直平分线们定义的half-spaces的交叉：\(V(p_i) = \cap_{j \neq i} H(p_i, p_j)\)，它是convex多边形。

图p2

Voronoi region与points是1-to-1对应关系。大多数Voronoi vertices具有3阶。Voronoi faces可以是unbounded。

关于Voronoi region的性质，略。

1.2 Delaunay Triangulation

Delaunay三角化是Voronoi Diagram的直线对偶（straight-line dual）。注意：Delaunay edges不必跨过（cross）它的Voronoi duals。

图p3

它的性质有：

• D(P)的edges不会交叉
• 如果没有4个点共圆，D(P)是个三角形
• D(P)的boundary是P的convex hull
• 如果\(p_j\)是\(p_i\)的最近邻，那边\(\overline{p_i p_j}\)是一条Delaunay edge
• 存在这样一个圆，它穿过\(p_i\)和\(p_j\)，但不包含任意其它点 \(\Leftrightarrow\) \(\overline{p_i p_j}\)是一条Delaunay edge
• \(p_i, p_j, p_k\)的外切圆为空 \(\Leftrightarrow\) \(\triangle p_i p_j p_k\)是Delaunay三角形

2.其它

另外，百度的人在《On Efficient Retrieval of Top Similarity Vectors》中有delaunay graph有系统的整理。这里重新拿出来分享一下：

2.3 Delaunay Graph

Delaunay Graph在相似搜索中扮演着重要角色。\(l^2\)-Delaunay Graph的性质和构造，在文献中有介绍。我们可以将定义泛化成任意二元函数（binary function）中，包括inner product。

定义2.1：对应于f和\(x_i\)的Voronoi cell \(R_i\)（洛诺伊／泰森多边形）是以下集合：

\[R_i := \lbrace q \in X: f(x_i, q) \geq f(x,q) \ for \ all \ x \in S \rbrace\]

\(x \in S\)表示一个极点（extreme point），如果它与一个非空Voronoi cell有关。

定义2.2：对应f和S的Delaunay Graph G是一个无向图，集点S满足\(\lbrace x_i, x_j \rbrace \in G\)，当且仅当\(R_i \cap R_j \neq 0\).

在inner product space上一个关于Voronoi cells以及对应Delaunay Graph的示例如图1所示。不同颜色的区域对应着极点（红色点）的Voronoi cells。Delaunay Graph连接着极点（extreme points）。不同于指标相似度（例如：l2-norm），对应inner product一些数据点的Voronoi cells可能为空。通过定义2.2, 当它的Voronoi cell为空时，该数据点是孤立的（例如：没有入射边：incident edges）。如图1所示，有许多孤立点（蓝色点）。极点的比例总体上相对较小。根据定理2.1, 极点可以为任意非零query达到一个最大inner product score。

图1

极点的定义等价于paper[Barber]中的定义，例如：\(x \in S\)是extreme的，当且仅当x是在S的凸包边界（boundary of the convex hull）上。在二维情况下，edges形成了凸包边界，如图1所示。

2.4 Delaunay Graph上的Search

在Delaunay Graph上的搜过对于相似度搜索是很高效的【Morozov 2018】。在inner product的情况下，给定任意query vector \(q \in X\)，我们从一个极点出发，接着移到与q具有一个较大inner product的neighbor上。我们重复该step，直到获得一个这样的极点：它与q的内积要大于所有它的neighbors，我们会返回它。这样返回的local optimum实际上是global optimum。

通常，对于任意searching measure f，如果相应的Voronoi cells是相连的，那么通过greedy search返回的local optimum也是global optimum。证明明在Morozov 2018中有介绍。

定理2.1 假设f满足：对应于S的任意子集的Voronoi cell \(R_i\)，在X上相连，G是对应于f和一些S的Delaunay Graph，那么对于\(q \in X\)，在greedy search上的local maximum会从一个极点开始，也就是说，\(x_i \in S\)会满足：

\[f(x_i, q) \geq \overset{max}{x \in N(x_i)} f(x,q)\]

其中\(N(x_i) = \lbrace x \in S: \lbrace x_i, x \rbrace \in G \rbrace\)是一个global maximum。

假设定理2.1的该猜想（例如：连通的Voronoi cells）是有效的，我们认为，在Delaunay Graph上搜索可以找到global maximum。对于inner product的情况，很容易确认该猜想有效与否，因为关于内积的Voronoi cells可以为空，或者一个凸锥形（convex cone），因此他们是连通的。接着，我们可以宣禾水金，在内积的Delaunay Graph上的searching，S中的vector具有与query vector的最大内积。

3.Inner Product Delaunay Graph

尽管Delaunay Graph在相似度搜索上展示了它的潜力，Delaunay Graph在大规模和高维数据集上的直接构建是不可行的，因为在高维空间中edges数目会指数增长。为了解决该问题，实际算法通常会近似Delaunay Graphs。在这部分，我们会提出新的算法来在inner product space上构建approximate Delaunay Graph，称为“IPDG：Inner product Delaunay Graph”。这个算法有两个关键特性：

• i) edge selection只适用于inner product
• ii) 有两轮的graph construction

参考

• https://www.cs.jhu.edu/~misha/Spring16/11.pdf
• https://www.aclweb.org/anthology/D19-1527.pdf

Thiago Silveira等人在《How good your recommender system is?》中对Novelty概念做了个总结，我们来看下：

Novelty

novelty的概念通常涉及到：在推荐系统中有新(novel)的items。尽管一开始看起来很简单，但novelty在文献中有许多种定义。因此，为了让定义更简单，我们对novelty定义和指标划分成三个level，如下所示。Novelty指标被称为：\(nov(R_u)\)。

• level 1: Life level。在用户生命周期中一个item是novel的，也就是说，该用户从未在它的生命周期中听说过该item
• level 2: System level。根据用户的历史消费行为，该item对该用户是未知的
• level 3: Recommendation list level。在推荐列表中无冗余的items（Non-redundant）

Life level novelty

有一些作者将novelty定义在life level上。Kappoor et al.[19]将未知items（unknown）描述成：在用户的生命周期中从未消费或未知的items。Ricci et al.[29]则认为novel items应对用户未知。这些作者的定义看起来指的都是level 1 novelty，并进一步提出了一种假想的方法来measure novelty：询问用户是否知道该item。另外，Zhang et al.[38]认为，当提到预测时，从一个RS影响而消费的items会被推荐器考虑到。那么，在用户生命周期之前用户未知的items是novel items。

对于life level novelty进行measure而创建metrics是no-trivial的。对于level 1 novelty的一个合理metric是：考虑上超出系统上下文的信息，以便能measure用户是否已知。

System level novelty

system level novelty在文献中也有许多定义。一个用户的novel item可以认为是：该用户对该item完全不知或知道很少。Herlocker et al. [14]等将这样的items认为是：当一个RS预测items时，这种novelty items对用户来说是完全不知的，或者通过其它源未被发现的。另外，novelty也可以被定义成：推荐的item与用户已经消费的items相当不同[36]。最终，novelty也可以被定义成：对某用户的预测列表中未知items的比例[15]。实际上，这样的novel items定义只考虑了：当在用户的消费历史中观察到之前已消费items；在系统外消费的items不会被考虑其中。总之，即使作者使用了不同的话术，他们仍具有相同的意思：level 2的novelty意味着：当考虑上系统信息时，用户不知的items。

在文献中提出的大多数metrics的评估适用于level 2. Nakatsuji et al. [26]提出了一种metric，它会在推荐列表中计算novelty，认为是：在推荐列表中的items与用户历史中(\(H_u\))之间的相似度。该metric如等式(7)所示。作者使用items的类目(classes)来对items间的距离进行measure。d是一个distance function，\(class(i)\)表示了item i的classes。该idea可以被推广到items的features或genres。metric如下：

\[nov(R_u) = \sum\limits_{i \in R_u} min_{j \in H_u} d(class(i), class(j))\]

…(8)

Zhou et al.[40]指出的metric则会计算该用户在推荐列表中items的流行度（popularity）。等式(8)展示了novelty metric。例如：一个item的popularity(pop)可以通过有多少消费过它的用户数来计算。Zhang et al.[38]定义的novelty可以被认为是level 1, 该作者的metric与level 2有关，因为popularity通过消费该item的用户量来计算，会使用用户消费数据。因此，该items的novelty仍然是system level的。对于novelty所使用Popularity-based matrics在Ricci et al.[29]中提出。如等式(8)所示，该metric会简单计算一个推荐列表的novelty：通过在list中的items的popularity计算得到。另外作者也提供的metric的变种，比如：\(- log_2 \frac{pop(i)}{\| U \|}\)，这与Zhang et al.[38]相似。

\[nov(R_u) = \sum\limits_{i \in R_u} \frac{log_2 \ pop(i)}{| R_u |} \\ nov(R_u) = 1 - \frac{|pop(i)|}{|U|}\]

…(9) (10)

recommendation list level novelty

level 3指的是在推荐列表级别的novelty，也就是说，items不会被重复推荐。某种意义上，novelty被定义成在推荐列表中没有重复items，并不会涉及到用户信息。Adamopoulos et al. [1] 认为novelty与在推荐列表中的non-redundant items 有关。level 3可以认为是level 2的特例，其中在推荐列表中没有冗余items或重复items。

level 3的novelty指标衡量指的是在推荐列表中的items。不需要用户信息。等式（10）会计算在推荐列表中的items间相似度。另外，\(d(i,j)\)意味着item i和j间的距离。然而，该指标看起来类似于intra-list similarity，不适合对novelty进行measure。

\[nov(R_u) = \frac{1}{|R_u| - 1} \sum\limits_{j \in R_u} (1 - d(i,j))\]

另外，Vargas and Castells [36] 提出了一种不同的metric来measure推荐列表中的novelty。等式(11)展示了该metric。该metric会考虑items在ranked recommendation list中的items的位置，以便计算关于浏览完整个list的一个discount（\(disc(i_k)\)）。另外，该metric也会计算：当浏览时该用户已经看到过item的概率\(p(seen \| i_k)\)。由于该概率可能会/不会考虑用户的消费信息，该指标最适合level 2和level 3间novelty的划分。

\[nov(R_u) = \sum_{k=1}^{|R_u|} disc(k)(1-p(seen|i_k))\]

参考：

https://rd.springer.com/article/10.1007/s13042-017-0762-9

hinton在《Dynamic Routing Between Capsules》中提出了“dynamic routing”的概念。我们来看下这篇paper：

abstract

一个capsule是一组neurons，它的activity vector表示了一个特定类型的实体(entity)（比如：一个object或一个object part）的实例参数()。我们使用activity vector的长度(length)来表示实体存在的概率，使用它的方向(orientation)表示实体参数。在一个层级上的Active capsules通过转移矩阵为高级capsules的实例参数做出预测。当多个预测达到一致时，一个更高级别的capsule会变成active态。我们会展示：当训练完后，多层capsule系统会在MNIST上达到state-of-art的效果，它在识别高度重叠的数字上要比CNN要好。为了达到这样的结果，我们使用了一个迭代式routing-by-agreement机制：一个更低层级的capsule会偏向于将它的output发送到更高层级的capsules上，它的activity vectors会与来自低层级capsule的预测做一个大的点积。

1.介绍

人类视觉会通过使用一个关于注视点(fixation points)的细致判别序列，忽略掉不相关细节，来确保只有一小部分的光学阵列（optic array）在最高分辨率上被处理。内省（Introspection）对于理解以下情况效果很差：关于某个场景的知识有多少是来自该注视点序列，以及我们从单个fixation能得到多少知识。但在本paper中，我们将假设，比起单个已被识别的目标和它的属性，单个fixation会带给我们更多。我们假设，我们的multi-layer可视化系统会在每个fixation上创建一个类parse tree结构，我们会忽略：这些单个fixation parse trees是如何协调的。

parse trees通常会通过动态内存分配即时构建。然而，根据【hinton 2000】，我们假设：对于单个fixation，一个parse tree可以从一个确定的multi-layer神经网络（比如： 雕塑从一块岩石中中雕刻出）中雕刻出。每个layer将被划分成许多被称为“capsules”的neurons小分组，在parse tree中每个node会对应一个active capsule。通过使用一个迭代路由过程（iterative routing process），每个active capsule会选择在layer中的一个capsule，作为它在树中的父节点(parent)。对于一个可视化系统中越高层级，该迭代过程会解决将部件分配到整体(assigning parts to wholes)的问题。

在一个active capsule中的neurons的activities，可以表示出现在该图片中一个特定实体(entity)的多种属性。这些属性可能包含许多不同类型的实例参数，比如：pose（位置、大小、方向），deformation（变型）、velocity（速率）、albedo（反射率）、hue(色彩)、texture(纹理)等。一个非常特别的属性是，在图片中实例化实体(instantiated entity)的存在(existence)。表示存在的一个很明显的方式是，通过使用一个独立的logistic unit，它的输出是该实体存在的概率。在本paper中，我们会探索一个有意思的方法，它会使用实例参数向量的整体长度(overall length)来表示实体的存在，并强制向量的方向(orientation)来表示实体的属性。我们会确保：一个capsule的向量输出(vector output)的长度不能超过1，通过使用一个非线性（non-linearity）函数来确保向量在方向保持不变、在幅值上进行缩放。

事实上，一个capsule的输出就是一个向量，使得它可以使用一个很强大的dynamic routing机制，来确保capsule的输出发送到上层(layer above)的一个合适的父胶囊(parent)上。首先，该output会被路由到所有可能的父胶囊上，但它会通过总和为1的耦合系数进行缩减。对于某个capsule的每个可能的父胶囊，该capsule通过将它的output乘以一个权重矩阵计算得到一个“预测向量（prediction vector）”。如果该预测向量与某一父胶囊的输出具有一个大的点积(scalar product，注：标量积、点积、内积、向量的积 dot product = scalar product)，那么这就存在一个自顶向下的反馈（top-down feedback）：该feedback会增大与该父胶囊的耦合系数(coupling coefficient)，而对于其它父胶囊该系数则会降低。这样就增大了该capsule对该父胶囊的贡献，并进一步增大该capsule的预测向量与父胶囊的输出间的点积。这种类型的”routing-by-agreement”远比原始版本的通过max-pooling实现的routing机制要更有效的多。我们会进一步展示，我们的dynamic routing机制是实现该“解释消除(explaining away)”的一种有效方法，解释消除对于将高度重叠的目标进行分割是必须的。

CNN会使用所学到的特征检测器的平移副本（translated replicas）。这允许他们将在一个图片中某一位置获得的较好权重值(good weight values)的知识平移到另一位置上。这在图片解释中被证明是相当有用的。尽管我们使用vector-output capsules来替换CNNs的scalar-output feature detectors、以及使用routing-by-agreement来替代max-pooling，我们仍希望跨空间的复用学到的知识。为了达到该目标，我们让除了capsules的最后一层之外的所有层都是conv的。有了CNNs，我们可以让更高层级的capsules覆盖该图片的更大区域。不同于max-pooling，我们不会丢掉关于该实体在该区域内的准确位置信息。对于低级别的capsules，位置信息是由active capsule所进行“基于位置的编码(place-coded)”。随着结构的上升，在某个capsule的output vector的实值元素（real-valued components）中，越来越多的位置信息是”rate-coded”。从place-coding到rate-coding的转换，加上更高层capsules可以以更多自由度来表示更复杂实体，表明capsules的维度应随着结构的上升而增加。

2.一个capsule的inputs和outputs向量是如何计算的

有许多可能的方式来实现capsules的通用思想。该paper的目的并不是探索整个实现空间，而是提供一种可以运转良好的简单实现，并且能用上dynamic routing。

我们希望：一个capsule的output vector的长度用来表示：通过该capsule表示的实体在当前输入中出现的概率。因此，我们使用一个非线性的“压扁（squashing）”函数，来确保短向量长度收缩到几乎为0，长向量收缩到长度在1以下。我们将它留给判别式学习，以便充分利用这种非线性。

\[v_j = \frac{\| s_j \|^2}{ 1+ \| s_j \|^2} \frac{s_j}{\|s_j\|}\]

…(1)

其中：

• \(v_j\)是capsule j的向量输出
• \(s_j\)是它的总输入(total input)

对于除了第一层外的其它层capsules，一个capsule的总输入\(s_j\)是一个在所有“预测向量（prediction vectors）”\(\hat{u}_{j \mid i}\)的加权求和。这些预测向量来自于下层（layer below）的capsules，通过将在下层（layer below）中的一个capsule的输出\(u_i\)乘以一个加权矩阵\(W_{ij}\)得到：

\[s_j = \sum\limits_i c_{ij} \hat{u}_{j \mid i}, \hat{u}_{j|i} = W_{ij} u_i\]

…(2)

其中，\(c_{ij}\)是耦和系数，它通过迭代式dynamic routing过程决定。

在capsule i和在上层（layer above）中的所有capsules间的耦和系数，总和为1, 通过一个”routing softmax”来决定，该softmax的intial logits \(b_{ij}\)是关于capsule i与capsule j相耦合的log先验概率。

\[c_{ij} = \frac{exp(b_{ij})}{\sum_k exp(b_{ik})}\]

…(3)

该log先验(priors)可以同时与所有其它权重一起通过判别式学习学到。他们取决于两个capsules的位置(location)和类型(type)，但不会依赖于当前输入图片。接着通过对每个在上层(layer above)中capsule j的当前输出\(v_j\)，以及由capsule i做出的预测\(\hat{u}_{j \mid i}\)的一致性（agreement）进行measure，以对初始化的耦合系数进行迭代式地提升。

该agreement就是简单的点积\(a_{ij}=v_j \cdot \hat{u}_{j \mid i}\)。该agreement就好像被看成是：它是一个log似然，并且在为capsule i连接到更高层级capsules上的所有耦合系数计算新值之前，被添加到initial logit \(b_{ij}\)中。

在conv capsule layers上，每个capsule会将一个关于向量的local grid，并为grid中每个成员、以及对于每种类型的capsule使用不同的转换矩阵，输出到上层（layer above）中每种类型的capsule。

算法1 routing算法

3.数字存在性的margin loss

我们正使用实例向量的长度来表示一个capsule实体存在的概率。我们希望，对于数字类别k，当且仅当该数字出现在该图片上时，顶层（top-level） capsule会具有一个长的实例向量。为了允许多个数字，对于每个数字胶囊（digit capsule）k，我们使用一个独立的margin loss，\(L_k\)：

\[L_k = T_k max(0, m^+ - \| v_k \|)^2 + \lambda(1-T_k) max(0, \|v_k \| - m^-)^2\]

…(4)

其中：

• \(T_k=1\)表示某个数字分类k出现
• \(m^+=0.9\)和\(m^-=0.1\)
• \(\lambda\)会对于没出现的数字类别会降权(down-weighting) loss，从所有digit capsules的activity vectors的长度进行收缩(shrinking)，从而停止初始化学习(initial learning)。 我们使用\(\lambda=0.5\)。

total loss可以简单认为是所有数字胶囊的losses求和。

4.CapsNet架构

图1 一个具有3 layers的简单CapsNet。该模型会与CNN (Chang 2015)进行比较。在DigitCaps中的每个capsule的activity vector的长度，表示每个数字类别（class）的一个实例的出现，并被用于计算分类loss。\(W_{ij}\)是一个在PrimaryCapsules中每个\(u_i, i \in (1, 32 \times 32 \times 6)\)和\(v_j, j\in (1, 10)\)间的权重矩阵。

一个简单的CapsNet结构如图1所示。该结构是浅层的，只有两个卷积层和一个FC layer。

第一层Conv1

具有256个9x9的conv kernels，它的stride=1, 并使用ReLU activation。该layer会将像素强度转化到局部特征检测器的activities，接着被用于primary capsules的输入。

primary capsules是最低层的多维实体，从一个倒转图的角度看，将primary capsules激活(activating)对应于将渲染过程进行反转(inverting)。比起将实例部件(instantiated parts)组装成熟悉的整体的方式，这是一种非常不同类型的计算，capsules的设计很擅长这种计算。

第二层（PrimaryCapsules）

它是一个convolutional capsule layer，它使用：

• 32 channels的conv 8D capsules(例如：每个primary capsule包含了8个conv units，它具有9x9 kernel以及stride=2)。
• 每个primary capsule的输出会看到所有256 x 81 Conv units，它们的receptive fields与capsule中心位置重叠。
• 在总的PrimaryCapsules中，有\([32 \times 6 \times 6]\)个capsule outputs（每个output是一个8D vector），在\([6 \times 6]\) grid中的每个capsule会相互共享它们的权重。

你可以将PrimaryCapsules看成是Conv layer，其中等式1看成是它的block非线性函数。

最后一层(DigitsCaps)

对于每个digit类具有一个16D的capsule，这些capsules的每一个会接受来自在layer below中的所有capsules的输入。

我们会在两个连续的capsule layers间（比如：PrimaryCapsules和DigitCaps）进行路由（routing），由于Conv1的输出是1维的，在它的空间上没有方向取得一致(agree)。因此，在Conv1和PrimaryCapsules间不会使用routing。所有的routing logits(\(b_{ij}\))被初始化为0。因此，初始化时，一个capsule的output(\(u_i\))会被等概率的(\(c_{ij}\))发送到所有的父胶囊（parent capsules(\(v_0 \cdots v_9\))）上，我们会使用Adam optimizer及tensorflow中的初始参数，包含exponentially decaying learning rate来最小化等式(4)的margin losses的和。

4.1 重构成一个正则方法

我们使用一个额外的reconstruction loss来支持digit capsules将输入数字的实例参数进行编码(encode)。在训练期间，除了正确digit capsule的activity vector外，我们会遮住所有其它digit capsule的vector。接着，我们使用该activity vector来重构输入图片。digit capsule的输出被feed给一个decoder（它由3个FC layer组成，会如图2所示建模像素强度）。我们会对logitsic units的输出和像素强度间的微分平方和做最小化。我们使用乘0.0005将该reconstruction loss缩放，以便它在训练期间不会主导着margin loss。如图3所示，来自CapsNet的16D output的reconstructions是健壮的，它只保留重要细节。

图2 Decoder结构，用于将来自DigitCaps layer的representation重构成一个数字. 图片和Sigmoid layer的output间的欧氏矩离(euclidean distance)，在训练期间最小化。在训练期间，我们使用true label来重构target。

图3 一个使用3个routing迭代的CapsNet的样本MNIST test重构。(l,p,r)表示label，prediction和reconstruction。

5.Capsules on MNIST

我们在28x28 MNIST图片集上（它们会在每个方向上shift两个像素，并使用zero padding）执行训练。没有使用其它的数据扩增/变形(augmentation/deformation)。对于训练集和测试集，dataset分别具有60K和10K的图片。

我们使用单一模型进行测试，没有使用任何模型平均方法(model averaging)。Wan 2013使用ensembling、并将数据进行旋转和缩放进行数据扩充，达到了0.21%的test error。如果不使用这两者，仅能达到0.39%。我们在一个3 layer网络上获得了一个较低的test error (0.25%), 该结果之前只能在更深的网络上才能达到。表1展示了不同CapsNet设置在MNIST上的test error，并展示了routing和reconstruction regularizer的重要性。通过增强在capsule vector中的pose encoding，添加reconstruction regularizer可以增强routing的效果。

表1 CapsNet分类的test arruracy。

baseline是一个标准的CNN，它具有(256, 256, 128)三通道的三层conv layer。每个具有5x5 kernels，stride=1。最后的conv layers会通过size为328､129的两个FC layers。最后的FC layer会使用dropout、连接到一个10分类的softmax layer上，并使用cross entropy loss。baseline也会使用Adam optimizer在2-pixel shifted MNIST上训练。baseline被设计成：计算开销接近CapsNet，在MNIST上达到最好的效果。在参数数目上，baseline具有35.4M，而CapsNet具有8.2M参数，不使用reconstruction subnetwork会有6.8M参数。

5.1 一个capsule表示的独立维度(individual dimensions)

由于我们会将单个数字的encoding进行传递，并将其它数字置为0, 一个digit capsule的维度应学到：以该类的数字被实例化的方式跨越变种空间。这些变种（variations）包括笔划粗细、倾斜、宽度。他们也包含了特定数字的变种，比如：数字2的尾部长度. 我们可以看到，可以使用decoder网络来表示独立维度(individual dimensions)。在为正确的digit capsule计算activity后，我们可以feed一个该activity vector的扰动版本给decoder网络，并观察扰动是如何影响reconstruction的。这些扰动的示例如图4所示。我们发现，该capsule的某一维度(out of 16)几乎总是表示该数字的宽度。一些维度表示全局变种的组合，而其它维度则表示在该数字的一个局部上的变种。例如，对于数字6的上半部的长度，以及下半部圈的size，使用不同维度。

图4

5.2 仿射变换的健壮性

实验表明，对比一个传统的卷积网络，对于每个类，每个DigitCaps capsule会学到一个更健壮的表示。由于在手写数字上的倾斜、旋转、样式等上存在天然的变种，训练好的CapsNet必须对于训练数据的仿射变换有一定的健壮性。

为了测试CapsNet对于仿射变换的健壮性，我们在一个padded和translated MNIST训练集上训练了一个CapsNet和一个传统的CNN（maxpooling和dropout）。在该数据集上，每个样本是一个MNIST数字，随机放置在一个40x40像素的黑色背景上。我们接着在affNIST数据集上测试该网络，在该数据集上每个样本是一个随机进行小的仿射变换的MNIST数字。我们的模型不会使用仿射变换进行训练，而是使用在标准MNIST中可见的平移和自然变换。一个使用early stopping并且训练不够的CapsNet，可以在expanded MNIST测试集上达到99.23% accuracy，并在affNIST测试集上达到79%的accuracy。一个传统的CNN可以在expanded MNIST达到99.22%相近的accuracy，在affnist测试集上达到66%。

6.高度重叠数字的分割

dynamic routing可以被看成是一个并行注意力（parallel attention）机制，它允许在一个level上的每个capsule会留意一些在level below上的active capsules, 并忽略其它。这使得该模型可以识别在图片中的多个物体(objects)，即使物体(objects)有重叠。Hinton 2000提出了分割和识别高度重叠数字的任务，其它的(Goodfellow 2013等)已经在相同领域测试了他们的网络。routing-by-aggrement使它可以使用一个关于物体形状的先验来帮助分割（segmentation）。

6.1 MultiMNIST数据集

我们通过将一个数字置于另一个不同数字之上，来生成了MultiMNIST训练集和测试集。每个数字会在每个方向上shift最多4个像素生成一张36x36的图片。考虑到在28x28图片中的一个数字被限定在一个20x20的box中，两个数字的bounding box平均有80%部分有重合。对于在MNIST数据集中的每个数字，我们生成了1K的MultiMNIST样本。因此，训练集的size是60M，测试集size为10M。

6.2 MultiMNIST结果

我们的3 layer CapsNet模型，重新使用MultiMNIST训练数据进行训练，它会比我们的baseline CNN模型达到更高的测试分类accuracy。我们在高度重合数字对上达到相同的分类错误率5%，而Ba 2014的sequential attention模型在一个更简单的任务上（更低重合度）才能达到。在测试图片上，它由来自测试集的成对图片组成，我们将由capsules网络生成的两个最可能active digit capsules作为分类。在reconstruction期间，我们一次选中一个数字，并使用所选数字对应的capsule的activity vector来重构所选数字的图片（我们知道该图片，因为我们使用它来生成组合图片）。与我们的MNIST模型唯一的不同之处是，对于learning rate，我们增加了decay step的周期大于10x，因为训练数据集更大。

图5

重构（reconstructions）如图5所示，它展示了CapsNet可以将该图片划分成两个原始的数字。由于该分割（segmentation）并不在像素级别，我们观察到：模型可以正确处理重合（同时出现在两个数字中的一个像素），从而解释所有的像素。每个数字的position和style在DigitCaps中被编码。decoder已经学到了给定该encoding，来重构一个数字。事实上，尽管有重叠它仍能够重构数字，展示了每个digit capsule可以从PrimaryCapsules layer接收到的投票中选择style和position。

我们将两个最可能的active DigitCaps capsules进行编码，一次一个，来获取两个图片。接着，通过使用非零强度给每个数字来分配像素，我们可以为每个数字获得segmentation的结果。

7.其它数据集

我们使用7个模型的ensemble，每个模型通过在24x24 patches的图片上进行3个routing迭代，还在CIFAR10上测试了我们的capsule模型，并达到了10.6%的error。每个模型具有和MNIST上的简单模型相同的架构，除了使用三种颜色channels、以及使用64个不同类型的primary capsule外。我们也发现，它可以为routing softmaxes帮助引入一个“none-of-the-above”类型，因为我们不能期望具有10个capsules的最后一层来解释图片中的everything。当首次应用到CIFAR10时(zeiler 2013)，标准CNN达到10.6% test error。

Capsules与生成模型存在同样的一个缺点是，它可能解释在图片中的任何东西，因此，对比起在dynamic routing中使用一个额外的“孤类(opphan category)”时，当建模杂乱东西(clutter)时它会更好。在CIFAR-10中，背景更多变化，从而不能以一个合理size的网络来建模，这可以帮助解释为什么会有更差的效果。

我们也在smallNORB上测试了与MNIST相同的网络构架，它可以达到2.7%的test error rate，这基本上是state-of-the-art的效果。

另外，我们也在SVHN上训练了一个更小的网络。达到4.3%的test error。

参考

• https://papers.nips.cc/paper/6975-dynamic-routing-between-capsules.pdf
• https://www.youtube.com/watch?v=wC0rhjvst8I

阿里在2019又发布了一篇关于tdm（新的称为JTM）的paper:《Joint Optimization of Tree-based Index and Deep Model for Recommender Systems》, 我们来看下：

介绍

为了打破内积形式的限制，并使得任意的关于用户偏好的高级模型对于从整个语料中检索候选的方式在计算上变得可行，之前提出的TDM使用树结构作为index，可以极大提升推荐的accuracy。TDM使用一个树结构来组织items，树中的每个leaf node对应于一个item。TDM假设：每个user-node偏好是指在所有子节点的偏好中具有最大值的节点，就如同一个max-heap一样。在训练阶段，每个user-node偏好的预测模型用于拟合这种类max-heap的偏好分布。与vector kNN-based搜索（index结构需要内积形式）不同的是，在TDM中对偏好建模的形式没有任何限制。在预测时，由训练模型给出的偏好得分，会被用于在tree index中执行layer-wise beam search来检索候选items。在树索引中的beam search的复杂度是log(corpus size)，在模型结构上没有限制，这使得高级用户偏好模型在推荐中检索候选变得可行。

index结构在kNN-based搜索、tree-based方法中扮演着不同的角色。在kNN搜索中，user和item的向量表示会首先通过学习得到，接着建立vector search index。而在tree-based方法中，tree-index的结构(hierarchy)也会影响检索模型的训练。因此，如果对tree index和用户偏好模型进行联合训练是一个重要的问题。tree-based方法在学术上也是一个活跃的话题。在已经存在的tree-based方法中，会学到tree结构，以便在在样本/标签空间（sample/label space）中得到一个更好的结构(hierarchy)。然而，在tree-learning阶段，sample/label划分任务的目标与最终目标（比如：精准推荐）并不完全一致。index learning与prediction模型训练间的不一致，会导致整个系统达到一个次优的状态。为了解决该挑战，更好地将tree index和用户偏好预测相协调，我们的工作聚焦于：通过对一个统一的偏好measure进行最优化，来开发一种同时学习树层级结构（tree hierearchy）和用户偏好预测模型。该paper的主要贡献可以归纳为：

• 我们提出了一种joint optimization框架，为tree-based推荐学习树结构和用户偏好预测模型，其中，会对一个统一的performance measure(比如：用户偏好的accuracy)进行最优化
• 我们演示了提出的树结构学习算法，它等同于二分图(bipartite graph)的最大权匹配（max weighted matching）问题，并给出了一个近似算法来学习树结构
• 我们提出了一种新方法，它可以更好利用tree index来生成层次化用户偏好（hierarchical user representation），它可以帮助学到更精准的用户偏好预测模型。
• 我们展示了树结构学习和层次化用户表示两者可以同时提升推荐accuracy。这两个模块可以相互提升，来达到更大的效果提升。

本paper的其余部分如下方式组织：

• 在第2节，我们会比较一些大规模推荐方法来展示不同
• 在第3节，我们首先给出一个TDM之前工作的简短介绍，接着详细描述joint learning
• 在第4节，离线对比和在线A/B test实验结果对比
• 在第5节，结论

2.相关工作

• Youtube DNN
• Yahoo news RNN
• Label Partitioning for Sublinear Ranking (LPSR)
• Partitioned Label Trees (Parabel)
• Multi-label Random Forest (MLRF)
• FastXML

3.joint optimization

在本节中，我们首先给出了一个TDM的简单回顾。TDM使用一个tree hierarchy作为index，并允许高级深度模型作为用户偏好预测模型。接着，我们提出了关于tree-based index和deep模型的joint learning框架。它会选择性在一个全局loss function下最优化index和预测模型。提出了一个greedy-based tree learning算法来最优化index。在最后一个子节，我们会指定用于模型训练中的层次化用户偏好表示。

3.1 tree-based深度推荐模型

推荐系统需要返回给用户感兴趣的一个items候选集合。实际上，如何从一个大的item库中有效做出检索是个大挑战。TDM使用一棵树作为index，并提出了在该tree上的一个类max-heap的概率公式，其中对于每个非叶子节点n在level l上的用户偏好为：

\[p^{(l)}(n | u) = \frac{ \underset{n_c \in \lbrace n's \ children \ in \ level \ l+1 \rbrace}{max} {p^{(l+1)}(n_c | u)} }{\alpha^{(l)}}\]

…(1)

其中：

• \(p^{(l)}(n \mid u)\)是用户u喜欢节点n的ground truth概率。
• \(\alpha^{(l)}\)是一个layer归一化项

上述公式意味着：在一个节点上的ground truth的user-node概率，等于它的子节点的最大user-node概率除以一个归一化项。因此，在level l上的top-k节点，必须被包含在在level（l-1)的top-k节点的子节点中，在不损失accuracy的前提下，top-k的leaf items的检索必须被限制在每个layer的top-k节点上。基于这一点，TDM将推荐任务转换成一个层次化检索问题(hierarchical retrieval problem)。通过一个自顶向下的过程，候选items可以从粗到细被逐渐选中。TDM的候选生成过程如图1所示。

图1: Tree-based deep推荐模型 (a) 用户偏好预测模型。我们首先以层次化的方式在对应的layers上的节点上对用户行为进行抽象。接着，用户行为抽象和目标节点（target node）、以及与其它特征（比如：user profile）一起被用于模型的输入。 (b) 树结构(tree hierarchy)。每个item首先会通过一个投影函数\(\pi(\cdot)\)分配到一个不同的leaf node上。在leaf level上的红色节点(items)会被选中作为候选集

在corpus中的每个item被分配到树层次结构（tree hierarchy）上的一个\(\tau\)的leaf node上。non-leaf nodes可以被看成是一个关于子节点的更粗粒度的抽象。在检索时，为了进行打分，用户信息与节点组合在一起，首先会被向量化成一个用户偏好表示，作为深度神经网络M（例如：FC networks）的输入。接着，用户对该节点感兴趣的概率值通过模型M返回，如图1(a)所示。而对于检索top-k个items（leaf nodes）来说，会以level-by-level的方式执行一个自顶向下的（top-down）beam search策略，如图1(b)所示。在level l中，只有在level l-1上带有top-k概率的子节点被打分和排序来选择k个候选节点。该过程会一直持续，直到达到k个leaf items。

有了tree index，一个用户请求的整体检索复杂度，会从线性降到log(corpus size)，而对于偏好模型结构没有任何限制。这使得TDM会打破用户偏好建模的内积形式的限制（它通过引入vector kNN search index和特有的高级深度模型来检索整个corpus的候选），这可以极大提升推荐的accuracy。

3.2 Joint Optimization框架

根据检索过程，TDM的推荐accuracy会通过用户偏好模型M和tree index T的质量(quality)来决定。给定n个关于正例训练数据\((u_i, c_i)\) pairs（它表示user \(u_i\)对target item \(c_i\)感兴趣），\(T\)决定着模型M会为用户\(u_i\)选择哪些non-leaf nodes来达到\(c_i\)。为了替换之前单独学习M和T的方式，我们提出了一个全局loss函数来对M和T进行jointly learn。正如我们在实验中所见，对M和T进行jointly optimizing可以提升最终的推荐accuracy。

\(p(\pi(c_i) \mid u_i; \pi)\)表示：给定一个user-item pair \((u_i,c_i)\)，用户u在leaf node \(\pi(c_i)\)上的偏好概率。其中：\(\pi(\cdot)\)是一个投影函数，它将一个item投影到在T上的一个leaf node上。注意，投影函数\(\pi(\cdot)\)实际决定着在树中的item的层次结构，如图1(b)所示。模型M被用于估计和输出user-node偏好\(\hat{p}(\pi(c_i) \mid u_i; \theta, \pi)\)，其中\(\theta\)为模型参数。如果pair \((u_i, c_i)\)是一个正样本，根据多分类设置，我们具有ground truth偏好 \(p(\pi(c_i) \mid u_i; \pi) = 1\)。

根据max-heap特性，所有\(\pi(c_i)\)的祖先节点（ancestor nodes）的用户偏好概率(注：每一层都有，构成一条路径)，例如 \(\lbrace p(b_j(\pi(c_i)) \mid u_i; \pi)\rbrace_{j=0}^{l_{max}}\)应该为1，在其中\(b_j(\cdot)\)是在level j上从一个节点到它的祖先节点(ancestor node)投影，\(l_{max}\)是在T上的最大level。为了拟合这样一个user-node偏好分布，全局loss函数被公式化成：

\[L(\theta, \pi) = - \sum_{i=1}^n \sum_{j=0}^{l_{max}} log \hat{p} (b_j(\pi(c_i)) | u_i; \theta, \pi)\]

…(2)

其中：n为训练样本正例数，我们将在所有正训练样本上对预测的user-node偏好的负log概率进行求和，它们的祖先user-node pairs作为global empirical loss。

算法1

由于对投影函数\(\pi(\cdot)\)最优化是一个组合优化问题(combinational optimization)，它几乎不可能使用基于梯度的算法来同时优化\(\theta\)。为了解决它，我们提出了如算法1所示的joint learning framework。它可以根据用户偏好模型和tree hierarchy交替(alternativel)对loss function (2)进行最优化。在模型训练和树学习中，training loss的一致性，可以促进框架的收敛。实际上，如果模型训练和树学习两者可以同时减小(2)的值，算法1确实会收敛，因为\(\lbrace L(\theta_t, \pi_t)\rbrace\)是一个递减序列，最低界为0。在模型训练中，\(min_{\theta} L(\theta, \pi)\)是为了为每一layer学习一个user-node偏好模型。受益于tree hierarchy，\(min_{\theta} L(\theta, \pi)\)被转换成学习user-node偏好分布，因此可以使用任意的高级深度模型，它们可以通过流行的最优化算法：SGD、Adam等求解。在归一化用户偏好设定中，由于节点数会随着node level指数增加，使用NCE估计\(\hat{p}(b_j(\pi(c_i)) \mid u_i; \theta, \pi)\)，通过sampling策略来避免计算归一化项。树学习的任务是为了在给定\(\theta\)时求解\(min_{\pi} L(\theta, \pi)\)，它是一个组合优化问题。实际上，给定树结构，\(min_{\pi} L(\theta, \pi)\)等于发现在corpus C中items与T中的leaf nodes间的最优匹配。更进一步，我们有：

推论1： \(min_{\pi} L(\theta, \pi)\)本质上是一个分配问题(assignment problem)：在一个加权二分图中发现一个最大权值匹配。

证明：假如第k项item \(c_k\)被分配到第m个leaf node \(n_m\)，即：\(\pi(c_k) = n_m\)，以下的加权值可以被计算：

\[L_{c_k,n_m} = \sum\limits_{(u,c) \in A_k} \sum_{j=0}^{l_{max}} log \hat{p} (b_j (\pi(c)) \mid u; \theta, \pi)\]

…(3)

其中:

• \(A_k\)包含了所有正样本抽样对(u,c)
• \(c_k\)是target item c

如果我们将在T中的leaf nodes和在corpus C中的items看成是顶点(vertices)，将leaf nodes和items间的完全连接(full connection)看成是边（edges），我们可以构建一个加权二分图V，\(L_{c_k,n_m}\)是在\(c_k\)和\(n_m\)间边的权重。更进一步，我们可以学到，每个在items和leaf nodes间的assignment \(\pi(\cdot)\)，等于一个关于二分图V的matching。给定一个assignment \(\pi(\cdot)\)，total loss(2)可以通过下式计算：

\[L(\theta, \pi) = -\sum_{i=1}^{|C|} L_{c_i, \pi(c_i)}\]

其中\(\mid C \mid\)是corpus size。因此，\(min_{\pi} L(\theta, \pi)\)等于寻找V的最大权匹配(maximum weighted matching)。

对于分配问题，传统算法（比如：经典的匈牙利算法）很难应用于大语料上，因为它们具有很高复杂度。即使对于最简单的贪婪算法，它们会使用最大权\(L_{c_k,n_m}\)矩阵来贪婪地选择未分配对\((c_k,n_m)\)，该矩阵是一个大的权重矩阵，需要事先计算和存储，这是不可接受的。为了克服该问题，我们提出了一个segmented tree learning算法。

我们不会将items直接分配给leaf nodes，作为替代，我们会自顶向下每隔d个levels会分配items。给定投影函数\(\pi(\cdot)\)，我们将从level s到level d的\(L_{c_k, \pi(c_k)}\)的partial weight，表示为：

\[L_{c_k, \pi(c_k)}^{s,d} = \sum\limits_{(u,c) \in A_k} \sum_{j=s}^d log \hat{p}(b_j(\pi(c_k)) | u; \theta, \pi)\]

我们首先会根据投影函数\(\pi(\cdot)\)来发现一个分配(assignment)来最大化\(\sum\limits_{i=1}^{\mid C \mid} L_{c_i, \pi(c_i)}^{1,d}\)，该投影函数等价于分配所有items到level d的节点上。对于一个具有最大level=\(l_{max}\)的完全二叉树T（complete binary tree），每个level d上的节点，会分配不超过\(2^{l_{max}-d}\)的items。这是一个最大匹配问题（maximum matching problem），可以使用贪婪算法进行有效求解，因为如果d选得够好，对于每个item可能位置的数目会极大减小(比如：d=7时, 该数目为\(2^d=128\))。接着，每个item c对应在level d（\(b_d(\pi(c)))\)）上的祖先节点保持不变，我们接着相继最大化next d levels，递归直到每个item被分配到一个叶子节点后停止。提出的算法在算法2中详细介绍。

算法2

算法2中的第5行，我们使用一个greedy算法，它使用再平衡策略（rebalance strategy）来求解这个子问题（sub-problem）。每个item \(c \in C_{_i}\)会首先将最大权重\(L_c^{l-d+1,l}\)被分配给在level l中的\(n_i\)子节点。接着，为了保证每个子节点的分配不超过\(2^{l_{max}-l}\)个items，会使用一个rebalance过程。为了提升tree learning的稳定性，以及促进整个框架的收敛，对于那些具有超过\(2^{l_{max}-l}\)items的节点，我们优先将在level l中具有相同的assignment的这些节点，保持使用前一轮迭代（比如：\(b_l(\pi'(c))==b_l(\pi_{old}(c)))\)）。被分配给该节点的其它items会以权重\(L_{\cdot,n}^{(l-d+1,l)}\)的降序进行排序，items的超出部分，会根据每个item权重\(L_{c,\cdot}^{(l-d+1,l)}\)的降序，被移到仍有富余空间的其它节点上。算法2会帮助我们避免存储单个大的权重矩阵。另外，每个子任务可以并行运行，进一步提升效率。

3.3 层次化用户偏好表示

如3.1节所示，TDM是一个层次化检索模型，用来从粗到细的方式层次化地生成候选items。在检索时，会通过用户偏好预测模型M贯穿tree index执行一个自顶向下的（top-down）beam search。因此，在每个level中的M任务是异构的(heterogeneous)。基于此，一个关于M的特定层输入（layer-specific input），必须提升推荐的accuracy。

一系列相关工作表明【9,19,22,35,37-39】，用户的历史行为在预测用户兴趣时扮演着重要角色。另外，由于在用户行为中的每个item是一个one-hot ID特征，在deep model输入的生成上，常见的方法是首先将每个item嵌入到一个连续的特征空间上。一个non-leaf node是一个在tree hierarchy中它的子节点的一个抽象。给定一个用户行为序列\(c=\lbrace c_1, c_2, ..., c_m \rbrace\)，其中\(c_i\)是用户交互的第i个item，我们提出使用\(c^l = \lbrace b_l(\pi(c_1)), b_l(\pi(c_2)), \cdots, b_l(\pi(c_m)) \rbrace\)与target node、以及其它可能特征（比如：user profile）一起来生成M在layer l的input，来预测user-node偏好，如图1(a)所示。在这种方式中，用户交互的items的祖先节点被当成抽象的用户行为使用。训练M时，在对应的layer上，我们使用该抽象来替换原始的user-behavior序列。总之，层次化用户偏好表示带给我们两个优点：

• 层的独立性（layer independence）：对于不同layers来说，在layers间共享item embeddings，会像用户偏好的预测模型那样，在训练M时会带来在一些噪声（noises），因为对于不同layers来说targets是不同的。解决该问题的一个显式方法是，对于每一layer，将一个item与一个独立的embedding相绑定来生成M的输入。然而，这会极大增加参数的数目，使得系统很难优化和应用。我们提出的抽象用户行为会使用相应layer上的node embeddings来生成M的input，在训练时达到layer independence，无需增加参数的数目。
• 精准描述（Precise description）：M会以层次化方式贯穿tree index来生成候选items。随着所检索的level的增加，在每一level上的候选节点会以从粗到细的方式描述最终的推荐items，直到达到leaf level。提出的层次化用户偏好表示（hierarchical user representations）会抓住检索过程的本质，并在相应layer的nodes上给出一个关于用户行为的精准描述，这可以提升用户偏好的预测，通过减少因太过详细或太过粗粒度描述而引入的混淆(confusion)。例如，在upper layers中M的任务是粗粒度选择一个候选集，用户行为也会在训练和预测时在相同的upper layers上使用均匀的node embeddings进行粗粒度描述。

参考

• 1.https://arxiv.org/pdf/1902.07565.pdf
• 2.二分图/二部图、匈牙利算法