1.介绍

1.1 Voronoi Diagrams

定义:给定点集(points) ,点(point)的Voronoi region 是这样一个点集,它们到的距离要与P中其它任意点都要接近

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

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

点集P被称为Voronoi diagram的sites。

  • 当只有2个点时,,regions可以由垂直平分线定义,如图p1所示。
  • 当只有3个点时,, regions可以由三条垂直平分线定义:

图片名称

图p1

  • 更一般的,与点相关的Voronoi region,是由垂直平分线们定义的half-spaces的交叉:,它是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
  • 如果的最近邻,那边是一条Delaunay edge
  • 存在这样一个圆,它穿过,但不包含任意其它点 是一条Delaunay edge
  • 的外切圆为空 是Delaunay三角形

2.其它

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

2.3 Delaunay Graph

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

定义2.1:对应于f和的Voronoi cell (洛诺伊/泰森多边形)是以下集合:

表示一个极点(extreme point),如果它与一个非空Voronoi cell有关。

定义2.2:对应f和S的Delaunay Graph G是一个无向图,集点S满足,当且仅当.

在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]中的定义,例如:是extreme的,当且仅当x是在S的凸包边界(boundary of the convex hull)上。在二维情况下,edges形成了凸包边界,如图1所示。

2.4 Delaunay Graph上的Search

在Delaunay Graph上的搜过对于相似度搜索是很高效的【Morozov 2018】。在inner product的情况下,给定任意query vector ,我们从一个极点出发,接着移到与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 ,在X上相连,G是对应于f和一些S的Delaunay Graph,那么对于,在greedy search上的local maximum会从一个极点开始,也就是说,会满足:

其中是一个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

参考

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

Novelty

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

  • 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与用户历史中()之间的相似度。该metric如等式(7)所示。作者使用items的类目(classes)来对items间的距离进行measure。d是一个distance function,表示了item i的classes。该idea可以被推广到items的features或genres。metric如下:

…(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的变种,比如:,这与Zhang et al.[38]相似。

…(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间相似度。另外,意味着item i和j间的距离。然而,该指标看起来类似于intra-list similarity,不适合对novelty进行measure。

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

参考:

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以下。我们将它留给判别式学习,以便充分利用这种非线性。

…(1)

其中:

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

对于除了第一层外的其它层capsules,一个capsule的总输入是一个在所有“预测向量(prediction vectors)”的加权求和。这些预测向量来自于下层(layer below)的capsules,通过将在下层(layer below)中的一个capsule的输出乘以一个加权矩阵得到:

…(2)

其中,是耦和系数,它通过迭代式dynamic routing过程决定

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

…(3)

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

该agreement就是简单的点积。该agreement就好像被看成是:它是一个log似然,并且在为capsule i连接到更高层级capsules上的所有耦合系数计算新值之前,被添加到initial logit 中。

在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,

…(4)

其中:

  • 表示某个数字分类k出现
  • 会对于没出现的数字类别会降权(down-weighting) loss,从所有digit capsules的activity vectors的长度进行收缩(shrinking),从而停止初始化学习(initial learning)。 我们使用

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

4.CapsNet架构

图1 一个具有3 layers的简单CapsNet。该模型会与CNN (Chang 2015)进行比较。在DigitCaps中的每个capsule的activity vector的长度,表示每个数字类别(class)的一个实例的出现,并被用于计算分类loss。是一个在PrimaryCapsules中每个间的权重矩阵。

一个简单的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中,有个capsule outputs(每个output是一个8D vector),在 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()被初始化为0。因此,初始化时,一个capsule的output()会被等概率的()发送到所有的父胶囊(parent capsules())上,我们会使用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。

参考

阿里在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上的用户偏好为:

…(1)

其中:

  • 是用户u喜欢节点n的ground truth概率。
  • 是一个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首先会通过一个投影函数分配到一个不同的leaf node上。在leaf level上的红色节点(items)会被选中作为候选集

在corpus中的每个item被分配到树层次结构(tree hierarchy)上的一个的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个关于正例训练数据 pairs(它表示user 对target item 感兴趣),决定着模型M会为用户选择哪些non-leaf nodes来达到。为了替换之前单独学习M和T的方式,我们提出了一个全局loss函数来对M和T进行jointly learn。正如我们在实验中所见,对M和T进行jointly optimizing可以提升最终的推荐accuracy。

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

根据max-heap特性,所有的祖先节点(ancestor nodes)的用户偏好概率(注:每一层都有,构成一条路径),例如 应该为1,在其中是在level j上从一个节点到它的祖先节点(ancestor node)投影是在T上的最大level。为了拟合这样一个user-node偏好分布,全局loss函数被公式化成:

…(2)

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

算法1

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

推论1: 本质上是一个分配问题(assignment problem):在一个加权二分图中发现一个最大权值匹配。

证明:假如第k项item 被分配到第m个leaf node ,即:,以下的加权值可以被计算:

…(3)

其中:

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

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

其中是corpus size。因此,等于寻找V的最大权匹配(maximum weighted matching)。

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

我们不会将items直接分配给leaf nodes,作为替代,我们会自顶向下每隔d个levels会分配items。给定投影函数,我们将从level s到level d的的partial weight,表示为:

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

算法2

算法2中的第5行,我们使用一个greedy算法,它使用再平衡策略(rebalance strategy)来求解这个子问题(sub-problem)。每个item 会首先将最大权重被分配给在level l中的子节点。接着,为了保证每个子节点的分配不超过个items,会使用一个rebalance过程。为了提升tree learning的稳定性,以及促进整个框架的收敛,对于那些具有超过items的节点,我们优先将在level l中具有相同的assignment的这些节点,保持使用前一轮迭代(比如:)。被分配给该节点的其它items会以权重的降序进行排序,items的超出部分,会根据每个item权重的降序,被移到仍有富余空间的其它节点上。算法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中它的子节点的一个抽象。给定一个用户行为序列,其中是用户交互的第i个item,我们提出使用与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进行粗粒度描述

参考

microsoft在开放了inner product快速计算的方法:《Speeding Up the Xbox Recommender System Using a Euclidean Transformation for Inner-Product Spaces》。主要解决inner product top-k search问题,我们来看下:

介绍

在线服务数据的大量增长,对于更好的信息过滤信息提出了新的风险与挑战。在推荐系统中,包括:

  • (1) item目录(catalog)
  • (2) users
  • (3) 用户反馈(ratings)

推荐系统的目标是:为每个用户找到一个关于items的限定集合,使得它们具有最大可能的机会被该用户消费。现代推荐系统有两个主要部分:

  • 第一部分:学习阶段,基于user feedback的离线模型学习
  • 第二部分:检索阶段,对每个用户(在线)推荐items

该paper主要在第二阶段,推荐系统基于MF。特别的,对一个用户的推荐,我们引入了一个新方法来在运行时长(running time)和结果质量间做权衡。

MF是CF中最流行的方法。该方法要比其它近邻方法要好。在MF模型中,users和items通过latent feature vectors表示。Bayesian MF模型是Xbox推荐系统的核心,它每天会为数百万的用户提供游戏、电影、音乐推荐服务。在该系统中,users和items通过的低维向量表示。用户u通过向量表示,item i通过表示,它们间的匹配质量(match quaity)通过两个向量间的内积来表示。内积越高表示该用户越愿意消费该item。

检索问题:理想情况下,给定一个用户u(它由向量表示),所有item vectors 都会被检索。对于每个这样的item vector ,我们会计算它的匹配度,items根据它们的匹配度进行排序。在该列表中具有最高匹配度的该items会被选中来形成最终的推荐列表。然而,在有限搜索时间内,items的catalog通常因为太大而不能对所有内积进行穷举计算。

Xbox的catalog包含了上百万的items。如果使用线性扫描,每个推荐都需要数百万内积计算。user vectors会吸收上下文信息,这些信息只在用户有行为时(engagement)提供。因而,user vector的计算是实时(online)的。结果是,推荐的items列表的检索只能在线(online)执行,不能离线预计算。该任务构成了在online servers引入的单个最大密集计算任务。因此,该过程需要有个快速的替代方案。

我们的贡献:该paper展示了如何来极大地加速推荐检索过程。该最优化item-user match检索与一个近似搜索相关:对与user vector检索高内积(high inner product)的items,但没必要检索最高的。该方法会由多个构建块组成。首先,我们定义了一个新的转换(transformation),它将内积问题转换成一个Euclidean最近邻问题(第3节)。作为一个预处理过程,该转换会被应用到item vectors上。在item检索期间,另一个转换会被应用到user vector上。在转换后空间中的具有最小欧氏距离(Euclidean distance)的item会被检索到。为了加快最近邻搜索,会使用PCA-Tree数据结构与一个新的邻近增强法(neighborhood boosting scheme)(第4节)。

为了演示提出方法的效果,它被应用到一个Xbox推荐数据集上,以及公开的Yahoo Music dataset上。实验表明,在推荐质量推化以及检索时间提升的trade-off曲线(第5节)。另外,time-accuracy trade-offs由两个baseline方法组成,基于LSH和对于在MF近似推荐上的当前state-of-art方法。我们展示了我们的方法具有更高的加速。

概念:我们使用:

  • 小写字母表示scalars
  • 粗体小写字母表示vector
  • 粗体大写字母表示matrix

例如,x是scalar,x是vector,X是matrix。

给定一个向量,有:

  • 表示在维度i上的measure,具有:
  • norm通过来表示;欧氏空间中,
  • 我们通过来表示x和y间的内积dot product (inner product)。
  • 最终,我们使用来表示一个标量a与一个向量x进行拼接。

3.简化搜索问题(REDUCIBLE SEARCH PROBLEMS)

该paper的一个关键贡献是,在search problem间进行有效的简化。在该部分,我们对search problem的概念进行公式化,并展示了在已知变种间的有效简化。

我们将search problem定义为:

定义1:

一个search problem 包含了一个关于n个items的实例集合,一个query ,以及一个search function:

函数s用于:对于一个给定query q,检索在I中的某一item的索引。我们的目标是,对items使用 进行预处理,以便每个query都能有效得到结果。预处理函数g可以涉及到一个从某一domain到另一domain的转换,以便转换后的search problem可以在一个不同的domain上执行。以下的定义对search problems间的概念的简化做了公式化:

定义二

一个search problem 被简化成一个search problem ,其中,如果存在函数,那么:

该简化不会对g和h的运行时长做任何限制。注意,g只当成一个预处理step运行,而h会被应用到query时。这提出了一个要求:h必须有的运行时间。我们将该问题公式化为:

定义三

我们会说:,g和h的运行时间分别为

对于在中的一个query vector,我们会在该paper中考虑三个search problem:

  • MIP:在中的n个vectors上的最大内积(maximum inner product)。为
  • NN:在中n个vectors的最近邻(nearest neighbor),为()
  • MCS:在中n个向量的最大cosine相似度。()

它们的正式定义如下:

实例(Instance):一个包含n个item向量的矩阵 ,其中; 因此

查询(Query):一个vector ;

目标(objective):根据以下公式进行检索index:

其中i表示Y的第i列。

下一节展示了这三个问题间是如何进行转换的,可以使用:

来达成上述目标。

3.1 保序转换(Order Preserving Transformations)

当对三个向量进行一个内积比较时,vectors x、间不支持三角不等式(triangle inequality),因为这是在MIP中的情况。许多高效的搜索数据结构依赖于三角不等式,如果MIP可以被转换成使用欧氏距离的NN,这些数据结构立马变得可用。我们的第一个定理论声明是,通过使用比原始问题多一维Euclidian metric,MIP可以被简化到NN。

定理1

证明

假设:

对输入(input)预处理:

在query时:。因为:

我们有:

最终,和x是与index i相互独立的:

定理1是基础。在余下章节,我们会表述它的特性以及相关转换。

如果知道转化后的在一个mainifold上,如上,我们期望通过使用反向化简来恢复Y。然而,在常见case中,该transformation只可能通过再增加一维:

定理2

证明

输入的预处理:

在查询时:

我们有:

最终:

MIP搜索可以被嵌入到一个MCS search中,通过增加1维来实现:

定理3

证明

预处理(preprocessing)和查询转换(query transformation)与定理1相同。输入的预处理为:

,假设:

在query时:

最终:

然而,MCS可以通过归一化向量来简化MIP查询:

定理4

证明

输入预处理:

在query时:

最终:

我们的最终结果表明,一个NN search可以被转换成一个MCS search,通过增加1维来实现:

定理5

证明

与定理1中的简化相同。输入的预处理为:,以及

在query时:

加上定理1:

接下来,我们利用定理1来加速在Xbox中和其它基于MF的推荐系统的检索。

4.我们的方法

我们的解决方案基于两个部分:

  • 1.将问题简化到一个Euclidian search problem
  • 2.使用一个PCA-Tree来求解它。

简化过程(reduction)与定理1的定义非常相似,但会使用一个额外的平移(shift)和旋转(rotation),因此,MIP search problem会被简化到NN search,所有的vectors与它们的主成分(pricipal components)相对齐。

4.1 简化

我们首先根据定理1定义了第一个简化函数。假设:,以及:

…(2)

其中,当应用到Y上时,给定元素。这会将MIP化简到NN。由于NN在输入空间中(input space)对于平移(shift)和旋转(rotations)是不变的,我们可以使用PCA rotation来构成(compose)该转换(transformations),并且可保证一个等价的search problem。

我们对数据进行mean-center并进行rotate:假设是在第一次化简后的均值,并且是一个使用沿着它的列进行复制的矩阵。该中心数据矩阵的SVD为:

其中,数据项(data items)出现在的列中。矩阵W是一个的矩阵。的每一列定义了一个正交单位长度的特征向量(eigenvector),因此,每个定义了一个超平面,每个被投影到它上面。矩阵W是一个旋转矩阵,它会将这些vectors对齐到它的主成分(principal components)上。我们定义了中心旋转(centered rotation)作为我们的第二个转换:

…(3)

其成分(composition)为:

…(4)

仍定义了一个从MIP到NN的简化(reduction)。使用,为我们给出了一个关于输入向量的转换后集合,可以在其上执行一个Euclidian search。另外,在该转换后,该点会被旋转,因而它们的成分(compoments)会减小方差的阶数(order of variance)。接着,我们会使用一个PCA-Tree数据结构来索引在中的转换后的item vectors。我们将上述逻辑表述在算法1中。

算法1

4.2

参考