Faster R-CNN由Ross Girshick等人提出。

总览

在目标检测领域的最新进展来源于候选区域法（region proposal methods）以基于区域的卷积神经网络（region-based convolutional neural networks）的成功。尽管region-based CNN开销很大，但如果通过跨候选块（proposals）共享卷积，可以极大地减小开销。当忽略掉在候选区域（region proposals）上花费的时间时，Fast R-CNN通过使用极深网络已经达到了接近实时的准确率。现在，在主流的检测系统中，在测试时间上都存在着proposals的计算瓶劲。

候选区域法（Region proposal methods）通常依赖于开销低的特征以及比较经济的inference模式(schemes)。选择性搜索法（Selective Search）是其中一种最流行的方法之一，它会基于已经开发的底层特征(low-level features)，对超像素 (superpixels)进行贪婪式合并。当与其它有效的检测网络[paper 2]进行对比时，Selective Search方法会更慢些，在CPU的实现上每张图片需要2秒耗时。EdgeBoxes[6]方法提供了在proposal上的质量和速率上的最佳权衡，每张图片0.2秒。尽管如此，候选区域（region proposal）阶段步骤仍然会像该检测网络一样消耗相当多的运行时（running time）。

有人注意到，fast RCNN(fast region-based CNN)可以利用GPU，而在研究中使用的候选区域法(region proposal methods)则通常在CPU上实现，使得这样的运行时比较变得不公平。很明显，一种用于加速proposal计算的方法就是：在GPU上重新实现。这是一个有效的工程解决方案，但重新实现会忽略下游的检测网络（down-stream detection network），从而失去共享计算的机会。

本paper中展示了一种新方法：使用DNN来计算候选（proposals），来产生一个优雅并有效的解决方案，在给定检测网络的计算下，其中proposal计算的几乎没有开销。我们引入了新的Region Proposal Networks（RPNs）来在最新的目标检测网络[1][2]中共享卷积层。通过在测试时（test-time）共享卷积，计算proposals的边缘开销很小（例如：每张图片10ms）。

我们观察到，由region-based dectectors（例如：Fast R-CNN）所使用的卷积特征图，也可以被用于生成候选区域（region proposals）。在这些卷积特征（convolutional features）之上，我们通过添加一些额外的卷积层（conv layers）构建了一个RPN，这些layers可以对一个常规网格(regular grid)上的每个位置，同时对区域边界（region bounds）进行回归(regression)、以及生成目标得分（objectness scores）。RPN是这样一种完全卷积网络（FCN: fully convolutional network）[7]，它可以以end-to-end方式训练，特别适用于生成检测候选（detection proposals）。

图1: 多种scales和sizes下的不同模式（schemes）。(a) 构建图片和feature maps的金字塔，在所有scales上运行分类器 (b) 使用多个scales/sizes的filters，在feature map上运行 (c) 使用在回归函数中参照框(reference box)金字塔

RPN被设计成使用一个较广范围的比例（scales）和高宽比（aspect ratios）来高效地预测region proposals。对比于上面使用图片金字塔（图1，a）的方法或者过滤器金字塔（图1，b），我们引入了新的锚点边框“anchor” boxes，在多个不同尺度和高宽比的情况下充当参照（references）。我们的scheme可以被看成是一个对参照（references）进行回归的金字塔（图1,c），它可以避免枚举多个不同尺度和高宽比的图片或filters。当使用单尺度图片进行训练和测试时，该模型执行很好，并且能提升运行速度。

为了将RPN和Fast R-CNN目标检测网络进行统一，我们提出了一个training scheme，它可以轮流为region proposal任务和目标检测任务进行fine-tuning，并保持proposals固定。该scheme可以快速收敛，并生成一个使用卷积特征(可在任务间共享)的统一网络。

我们在PASCAL VOC benchmarks上进行综合评估，其中使用Fast R-CNN的RPNs准确率比使用Fast R-CNN的Selective Search(baseline)要好。同时，我们的方法没有Selective Search在测试时的计算开销——可以在10ms内有效运行proposals。使用昂贵的极深网络，我们的检测方法在GPU上仍然有5fps（包含所有steps）的帧率，这是一个在速率和准确率上实际可行的目标检测系统。我们也在MS COCO数据集上做了测试，并研究了在PASCAL VOC数据集上使用COCO数据进行提升。代码在：matlab code 和 python code。

该paper的预览版在此前有发布。在此之后，RPN和Faster R-CNN的框架已经被其它方法实现并实现，比如：3D目标检测[13], part-based detection[14], instance segmentation[15]，image captioning[16]。我们的快速有效目标检测系统已经在比如Pinterests等商业系统中使用。

在ILSVRC和COCO 2015比赛中，Faster R-CNN和RPN是在ImageNet detection, ImageNet localization, COCO detection, and COCO segmentation等众多领域第1名方法的基础。RPNs可以从数据中学到propose regions，这可以从更深和更昂贵特征中受益（比如101-layer residual nets）。Faster R-CNN和RPN也可以被许多其它参赛者使用。这些结果表明我们的方法不仅是一个有效的解决方案，也是一种有效方法来提升目标检索的准确率。

2.相关工作

候选目标（Object Proposals）法。在object proposal methods中有大量文献。可以在[19],[20],[21]中找到。广泛被使用的object proposal methods中包含了以下方法：

• 基于grouping super-pixels的方法（Selective Search, CPMC, MCG）
• 基于滑动窗口的方法（objectness in windows[24], EdgeBoxes [6])。

Object proposal methods被看成是dectectors之外独立的一个模块。

深度网络法：R-CNN法可以训练一个CNN的end-to-end网络来将proposal regions分类成目标类别（object categories）或是背景(background)。R-CNN主要扮演分类器的角色，它不会预测对象的边界（除了通过bounding box regression进行重定义）。它的准确率依赖于region proposal模块的性能。许多papers[25],[9],[26],[27]提出了使用深度网络来预测目标的bounding boxes。在OverFeat方法中[9]，会训练一个FC layer来为单个目标的定位任务预测box的坐标。FC-layer接着会转化成一个conv-layer来检测多个特定类别的目标。MultiBox方法[26],[27]会从一个最后一层为FC layer（可以同时预测多个未知类的boxes）的网络中生成region proposals，生成OverFeat方式下的单个box。这些未知类别的boxes可以被用于R-CNN的proposals。对比于我们的fully conv scheme，MultiBox proposal网络可以被用于单个图片的裁减或多个大图片的裁减。

。。。

3.Faster R-CNN

我们的目标检测系统，称为Faster R-CNN，由两个模块组成。第一个模块是深度完全卷积网络，它用于生成候选区域；第二个模块是Fast R-CNN检测器，它会使用这些候选区域。整个系统是一个统一的网络，使用了最近神经网络中的流行术语：attention机制，RPN模块会告诉Fast R-CNN模块去看哪里。在3.1节中，我们介绍了该网络的设计和属性。在3.2节中，我们开发算法来训练两个模块，并共享特征。

3.1 RPN

一个RPN会将一张图片（任意size）作为输入，输出一个矩形候选目标集合，每一个都有一个目标得分(objetness score)。我们使用一个完全卷积网络(fully conv network)将该过程建模，会在该部分描述。由于我们的最终目标是使用一个Fast R-CNN网络来共享计算，我们假设两个网络共享一个公共的卷积层(conv layers)集合。在我们的实验中，我们研究了ZF model[5]：它有5个共享的conv layers；以及VGG16 [3] ：它有13个共享的conv layers。

为了生成候选区域（region proposals），我们在由最后一个共享conv layer所输出的conv feature map上滑动一个小网络。该小网络会将一个在input conv feature map上的n x n的空间窗口作为输入。每个滑动窗口被映射到一个更低维的feature（ZF:256-d, VGG: 512-d）上。该feature会被fed进两个相邻的FC-Layer上——一个box-regression layer（reg），另一个是box-classification layer (cls)。在本paper中，我们使用n=3, 注意在输入图片上的有效接受域（effective receptive field）非常大(ZF: 171 pixels, VGG: 228 pixels)。该mini-network如图3(左）所示。注意，由于mini-network以滑动窗口的方式操作，FC-Layers会跨所有空间位置被共享。该结果很自然地使用一个n x n的conv layer进行实现，接着两个同级的1x1 conv layers（reg和cls）

3.1.1 Anchors

在每个滑动窗口位置上，我们同时预测多个候选区域（region proposals），其中每个位置的最大可能候选数量被表示成k。因而reg layer具有4k的输出，它可以编码k个boxes的坐标；cls layer输出2k个得分，它用来估计每个proposal是object还是非object的概率。k个候选(proposals)被相对参数化到k个参考框（reference boxes），我们称之为锚点（anchors）。一个anchor位于当前的滑动窗口的中心，与一个scale和aspect ratio（图3, 左）相关联。缺省的，我们使用3个scales和3个aspect ratios，在每个滑动位置上产生k=9个anchors。对于一个size=W x H（通常~2400）卷积特征图（conv feature map），总共就会有WHk个anchors。

平移不变的Anchors

我们的方法的一个重要属性是：平移不变性（translation invariant）， 对于该anchors、以及用于计算相对于该anchors的proposals的该functions都适用。如果在一个图片中移动一个object，该proposal也会平移，相同的函数应能预测在该位置的proposal。这种平移不变特征由方法5所保证。作为比较，MultiBox方法[27]使用k-means来生成800个anchors，它并没有平移不变性。因而，MultiBox不会保证：如果一个object发生平移仍会生成相同的proposal。

平移不变性也会减小模型的size。MultiBox具有一个(4+1) x 800维的FC output layer，其中我们的方法具有一个(4+2) x 9维的conv output layer，anchors数为k=9个。结果是，我们的output layer具有\(2.8 \times 10^4\)个参数(VGG-16: \(512 \times (4+2) \times 9\))，比MultiBox的output layer的参数（\(6.1 \time 10^6\)）要少两阶。如果考虑上特征投影层（feature projection layers），我们的proposal layers仍比MultiBox的参数少一阶。我们希望我们的方法在小数据集上（比如：PASCAL VOC）更不容易overfit。

图3:

Multi-Scal anchors as Regression References

关于anchors的设计，提供了一种新的scheme来发表多个scales（以及aspect ratios）。如图1所示，具有两个流行的方法来进行multi-scale预测。第一种方法基于image/feature 金字塔，比如：DPM和基于CNN的方法。这些图片以多种scales进行resize，在每个scale上计算feature maps（HOG或deep conv features）（如图1(a)所示）。该方法通常很有用，但耗时严重。第二种方法是在feature maps上使用多个scales（或aspect ratios）的滑动窗口。例如，在DPM中，不同aspect ratios的模型使用不同的filter sizes（比如：5x7和7x5）进行单独训练。如果该方法用于解决multi scales，它可以被认为是一个“过滤器金字塔（pyramid of filters）”（如图1(b)所示）。第二种方法通常与第一种方法联合被采纳。

作为比较，我们的基于anchor的方法构建了一个关于anchors的金字塔，它效率更高。我们的方法会进行分类和回归bounding boxes，使用multi scales和aspect ratios的anchor boxes。它只取决于单一尺度的图片和feature maps，以及使用单一size的filters（在feature map上滑动窗口）。我们通过实验展示了该scheme用于解决multiple scales和sizes的效果（表8）。

由于该multi-scale设计基于anchors，我们可以简单地使用在单一尺度的图片上计算得到的conv features，这也可以由Fast R-CNN detector来完成。multi-scale anchors的设计是共享特征的核心关键（无需额外开销来解决scales问题）。

3.1.2 Loss函数

为了训练RPN，我们为每个anchor分配一个二元分类label（是object、不是object）。我们分配一个正向label给两种类型的anchors：

• (i) 具有与一个ground truth box的IoU（Intersection-over-Union）重合率最高的anchor/anchors
• (ii) 具有一个与任意ground-truth box的IoU重合度高于0.7的anchor

注意，单个ground-truth box可以分配一个正向label给多个anchors。通常第二个条件足够决定正样本；但我们仍采用了第一个条件，原因是有些罕见的case在第二个条件下会找不到正样本。

假如它的相对所有ground-truth boxes的IoU ratio低于0.3, 我们分配一个负向label给一个非正anchor. 即非正，也非负的anchors对训练目标贡献不大。

有了上述定义，我们根据在Fast R-CNN中的多任务loss来最小化目标函数。一张图片的loss function如下所示：

\(L(\{p_i\}, \{t_i\}) = \frac{1}{N_{cls}} \sum_{i} L_{cls} (p_i, p^*) + \lambda \frac{1}{N_{reg}} \sum_i p_i^* L_{reg}(t_i, t_i^*)\) …(1)

这里，

• i表示在mini-batch中的一个anchor的索引
• \(p_i\)表示anchor i是object的预测概率。
• 如果该anchor为正，ground-truth label \(p_i^*\)是1;否则为0.
• \(t_i\)是一个向量，表示要预测的bounding box的4个参数化坐标
• \(t_i^*\)是与一个正锚点（positive anchor）相关的ground-truth box。
• \(L_{cls}\)是分类loss，它是关于两个类别的log loss。
• \(L_{reg}(t_i, t_i^*) = R (t_i - t_i^*)\)是回归loss，其中R是robust loss function（L1平滑）。
• \(p_i^* L_{reg}\)意味着regression loss当为正锚点时（\(p_i^*=1\)）激活，否则禁止（\(p_i^*=0\)）

两个项(term)通过\(N_{cls}\)和\(N_{reg}\)被归一化，通过一个参数\(\lambda\)进行加权。在我们当前实现中（释出的代码），等式(1)中的cls项通过mini-batch size进行归一化（例如：\(N_{cls}=256\)），reg项通过anchor位置的数目进行归一化（例如：\(N_{reg} ~ 2400\)）。缺省的，我们设置\(\lambda=10\)，接着cls和reg两项会被加权。通过实验我们发现，结果对于\(\lambda\)的值在一个宽范围内是敏感的（见表9）。我们也注意到，归一化（normalization）不是必需的，可以简化。

表9

对于bounding box回归，我们采用了以下的4坐标的参数化：

\[t_x = (x-x_a) / w_a, t_y = (y-y_s) / h_a\] \[t_w = log(w/w_a), t_h = log(h/h_a)\] \[t_x^*=(x^* - x_a)/w_a, t_y^*=(y^* - y_a) / h_a\] \[t_w^* = log(w^*/w_a), t_h^* = log(h^*/h_a)\]

…(2)

其中，x, y, w和h表示box的中心坐标、宽、高。变量x, \(x_a\)，以及\(x^*\)分别是预测box，anchor box，ground-truth box（y,w,h也类似）。这可以被认为是从一个anchor box到一个接近的ground-truth box的bounding-box regression。

然而，我们的方法与之前的基于RoI（Region of Interest）的方法不同，通过一种不同的方式达成bounding-box regression。bounding-box regression在由特定size的RoI上的features来执行，该regression weights被所有region sizes共享。在我们的公式中，用于回归的该features在feature maps上的空间size上(3x3)相同。为了应付不同的size，会学到k个bounding-box regressors集合。每个regressor负责一个scale和一个aspect ratio，k个regressors不会共享权重。由于anchors的这种设计，仍然能预测不同size的boxes，即使features是一个固定的size/scale。

3.1.3 训练RPNs

RPN可以通过BP和SGD以end-to-end的方式进行训练。我们根据”以图片为中心（image-centric）”的抽样策略来训练网络。从单个图片中提取的每个mini-batch，包含了许多正负样本锚点。它可以为所有anchors的loss functions进行优化，但会偏向主导地位的负样本。作为替代，我们在一个图片上随机抽取256个锚点，来计算一个mini-batch的loss函数，其中抽样到的正负锚点的比例为1:1。如果在一个图片中正样本数少于128个，我们将将该mini-batch以负样本进行补齐。

我们通过从一个零均值、标准差为0.01的高斯分布中抽取权重，来随机初始化所有new layers。所有其它layers（比如：共享的conv layers）通过ImageNet分类得到的预训练模型进行初始化。接着调整ZF net的所有layers，conv3_1以及来保存内存。我们在PASCAL VOC数据集上，对于mini-batches=60k使用使用learning rate=0.001，对于mini-batch=20k使用learning rate=0.0001. 我们使用一个momentum=0.9, weight decay=0.0005, 代码用Caffe实现。

3.2 为RPN和Rast R-CNN共享特征

我们已经描述了如何去训练一个网络来进行region proposal的生成，无需考虑基于region的目标检测CNN会使用这些proposals。对于检测网络，我们采用Fast R-CNN。接着，我们描述的算法会学到一个统一的网络，它由RPN和Fast R-CNN组成，它们会共享conv layers（如图2）。

图2

如果RPN和Fast R-CNN独立训练，会以不同的方式修改它们的conv layers。因此需要开发一个技术来允许在两个网络间共享conv layers，而非学习两个独立的网络。我们讨论了三种方式来训练特征共享的网络：

• (i) 交替训练（Alternating training）。在这种方案中，我们首先训练RPN，接着使用这些proposals来训练Fast R-CNN。 该网络会通过Fast R-CNN进行调参，接着被用于初始化RPN，然后反复迭代该过程。这种方案被用于该paper中的所有实验。
• (ii) 近似联合训练（Approximate joint training）。在这种方案中，RPN和Fast R-CNN网络在训练期间被合并到一个网络中，如图2所示。在每个SGD迭代过程中，forward pass会生成region proposals（当训练一个Fast R-CNN detector时，他们被看成是固定的、预计算好的proposals）。backward propagation会和往常一样进行，其中对于共享的layers来说，来自RPN loss的Fast R-CNN loss的后向传播信号是组合在一起的。该方案很容易实现。但该方案会忽略到关于proposal boxes坐标的导数（derivative w.r.t. the proposal boxes’ coordinates）, 也就是网络响应，因而是近似的。在我们的实验中，我们期望发现该求解会产生闭式结果，并减少大约25-50%的训练时间（对比alternating training）。该求解在python代码中包含。
• (iii) 非近似联合训练（Non-approximate joint training）。根据上述讨论，由RPN预测的bounding boxes也是输入函数。在Fast R-CNN中的RoI pooling layer会接受conv features，以及预测的bounding boxes作为输入，因而一个理论合理的BP解也与box坐标的梯度有关。这些梯度在上面的approximate joint training会被忽略。在非近似方法中，我们需要一个RoI pooling layer，它是box坐标的微分。这是一个非平凡问题，解可以通过一个”RoI warping” layer给出[15]。（超出本paper讨论范围）

4-step Alternating Training

在该paper中，采用了一个实用的4-step training算法来通过alternating优化来学习共享特征。在第一个step中，会如3.1.3节描述来训练RPN。该网络使用一个ImageNet-pre-trained模型来初始化，为region proposal任务来进行end-to-end的fine-tuning。在第二个step中，我们训练了一个独立的Fast R-CNN dectection网络，它会使用由第一步的RPN生成的proposals。该检测网络也使用ImageNet-pre-trained模型初始化。在此时，这两个网络不共享conv layers。在第三个step中，我们使用detector网络来初始化RPN training，但我们会固定共享的conv layers的能数，只对对于RPN唯一的layers进行fine-tune。最后，保持共享的conv layer固定，对Fast R-CNN的唯一layers进行fine-tune。这样，两个网络会共享conv layers，并形成一个统一网络。相类似的alternating training会运行很多次迭代，直到观察到不再有提升。

3.3 实现细节

我们在单一scale的图片上，训练和测试两个region proposal以及目标检测网络。我们re-scale这些图片，以至它们更短的边: s=600 pixels。Multi-scale特征抽取（使用一个图片金字塔image pyramid）可以提升accuracy，但不会有好的speed-accuracy的平衡。在re-scale的图片上，对于ZF和VGG nets来说，在最后一层conv layer上的总stride为16 pixels，在一个典型的PASCAL image上在resizing（~500x375）之前接近10 pixels。尽管这样大的stride会提供好的结果，但accuracy会使用一个更小的stride进行进一步提升。

对于anchors，我们使用3个scales，box areas分别为：\(128^2, 256^2, 512^2\)个pixels，3个aspect ratios分别为：1:1, 1:2, 2:1. 对于一个特定数据集，这些超参数并不是精心选择的，我们提供了消融实验。我们的解不需要一个图片金字塔或是过滤器金字塔来预测多个scales的regions，节约运行时间。图3(右）展示了在一个关于scales和sapect ratios范围内我们方法的能力。表1展示了对于每个anchor使用ZF net学到的平均proposal size。我们注意到，我们的算法允许预测比底层的receptive field更大。这样的预测是不可能的——如果一个object只有中间部分可见，仍能infer出一个object的其它部分。

该anchor boxes会交叉图片的边界，需要小心处理。在训练期间，我们忽略了所有交叉边界anchors（cross-boundary anchors），因而他们不会对loss有贡献。对于一个典型的1000x600的图片，共有20000 (~60x40x9)个anchors。由于忽略的cross-boundary anchors的存在，训练期每个图片有大约6000个anchors。如果boundary-crossing outliers在训练期被忽略，他们会引入大的、难的来纠正在目标函数中错误项，训练不会收敛。在测试期，我们仍应用完全卷积的RPN到整个图片上。这也会生成cross-boundary的proposal boxes，我们会将image boundary进行裁减。

表2

一些RPN proposals高度相互重叠。为了减小冗余，我们在proposal regions上基于它们的cls分值采用了NMS(non-maxinum suppression)。我们为NMS将IoU阀值固定为0.7，可以为每张图片留下2000个proposal regions。NMS不会对最终的检测accuracy有害，实际上会减小proposals的数目。在NMS后，我们使用top-N排序后的proposal regions进行detection。然后，我们使用2000个RPN proposals训练Fast R-CNN，但在测试时评估不同数目的proposals。

4.实验

4.1 PASCAL VOC

在PASCAL VOC 2007 detection benchmark上进行评估。该数据集包含了5k个trainval images，以及5k个test images，object类别超过20个。我们也提供了PASCAL VOC 2012 benchmark。对于ImageNet pre-trained network，我们使用ZF net的”fast”版本：它具有5个conv layers以及3个FC layers，以及公开的VGG-16 model：它具有13个conv layers以及3个FC layers。我们使用mAP（ mean Average Precision）进行评估detection，因为实际的目标验测的metric（而非关注目标的proposal proxy metrics）。

表2展示了使用不同region proposal methords的训练和测试结果。对于Selective Search(SS)[4]方法，我们通过”fast”模式生成了大约2000个proposals。对于EdgeBoxes（EB）[6]方法，我们通过缺省的EB setting将IoU设置为0.7来生成proposals。在Fast R-CNN框架下，SS的mAP具有58.7%，而EB的mAP具有58.6%。RPN和Fast R-CNN达到的完整结果为，mAP具有59.9%，仅使用300个proposals。使用RPN会比SS或EB生成一个更快的检测系统，因为共享卷积计算；更少的proposals也会减小region-wise FC layers的开销（表5）。

RPN上的Ablation实验。为了研究RPN作为proposal method的行为，我们做了一些ablation研究。首先，我们展示了在RPN和Fast R-CNN检测网络间共享卷积层（conv layers）的效果。为了达到这个，我们在第二个step后停止训练过程。使用独立的网络将结果减小到58.7%（RPN+ZF,unshared, 表2）。我们观察到这是因为在第三个step中，当detector-tuned features被用于fine-tune该RPN时，proposal质量会被提升。

接着，我们放开RPN对Fast R-CNN训练的影响。出于该目的，我们训练了一个Fast R-CNN模型，使用2000个SS proposals和ZF net。我们固定该detector，通过更改在测试时的proposal regions，来评估该detection的mAP。在这些ablation实验中，RPN不会与detector共享features。

在测试时，将SS替换成300 RPN proposals会产生mAP=56.8%。在mAP中的该loss是由于在training/testing proposals间的不一致性造成的。该结果会当成baseline。

评测

略，详见paper。

参考

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

Amazon在hogwild、hogbatch之后，提出了《BlazingText: Scaling and Accelerating Word2Vec using Multiple GPUs 》，利用多GPU来加速word2vec的训练。

介绍

Word2vec是流行的算法。原始google c实现、以及facebook fastText可以利用多核cpu架构来并行化。还有一少部分实现方式则利用GPU并行化，但会牺牲accuracy和可扩展性。本paper提出了BlazingText，一个使用CUDA高度优化的word2vec实现，可以利用多GPU进行训练。BlazingText可以在8GPU上达到43M words/sec的训练速度，达到了8线程CPU实现的9倍，并且对embeddings的质量影响很小。

word2vec的最优化通过SGD完成，它会进行迭代式求解；在每一个step，会选取一个词对（pair of words）：一个输入词和一个目标词，它们来自于window或一个随机负样本。接着根据选中的两个词来计算目标函数的梯度，然后基于该梯度值更新两个词的词表示（word representations）。该算法接着使用不同的word pair来处理下一次迭代。

SGD的一个主要问题是，它的顺序性；这是因为它在这一轮迭代的更新、与下一轮迭代的计算之间存在着依赖关系（他们可能遇到相同的词表示），每一轮迭代必须潜在等待前一轮迭代的更新完成。这不允许我们使用硬件并行资源。

然而，为了解决上述问题，word2vec使用Hogwild，它使用不同线程来并行处理不同的word pairs，并忽略任何在模型更新阶段中发生的冲突。理论上，对比起顺序运行，这会让算法的收敛率下降。然而，对于跨多线程更新不可能会是相同的词的这种情况，Hogwild方法已经得到验证能运行良好；对于大词汇表size，冲突相对较少发生，收敛通常不受影响。

Hogwild方法在多核架构上的成功，使得该算法利用GPU成为可能，GPU比CPU提供更强的并行化。在该paper中，我们提出了一种有效的并行化技术来使用GPU加速word2vec。

在深度学习框架中使用GPU加速，对于加速word2vec来说并不是好选择[6]。这些框架通常更适合于“深度网络（deep networks）”，它们的计算量主要由像卷积（conv）以及大矩阵乘法（large matrix multiplications）等重型操作主宰。而word2vec则是一个相对浅层的网络（shallow network），每一个training step包含了一个embedding lookup、梯度计算（gradient computation）、以及最终为word pair进行权重更新（weight updates）。梯度计算和更新涉及很小的点乘操作，使用cuDNN[7]或cuBLAS[8]并不能受益。

深度学习框架的限制导致我们探索CUDA C++ API。我们从头设计了训练算法，以便最优利用CUDA多线程能力，并且防止对GPU并行化的过度利用，从而不伤害输出的accuracy。

最终，我们开发了BlazingText，它处理文本语料的速率能达到数百万 words/sec，我们演示了使用多GPU来执行数据并行训练的可能性。我们对比了开源的工具与BlazingText之间的benchmark。

2.word2vec模型

word2vec有两种不同的模型架构：Contextual Bag-Of-Words (CBOW)以及Skip-Gram with Negative Sampling (SGNS) 。CBOW的目标函数是由给定上下文去预测一个词，而Skipgram则给定一个词去预测它的上下文。实际上，Skipgram会给出更好的效果，我们会在下面描述它。

给定一个大型训练语料，它由一个words序列\(w_1, w_2, ..., w_T\)组成。skipgram模型的目标是最大化log似然：

\[\sum_{t=1}^T \sum_{c \in C_t} log p(w_c | w_t)\]

其中，T是词汇表size，上下文\(C_t\)是围绕\(w_t\)的词的集合。给定\(w_t\)所观察到的一个上下文词\(w_c\)的概率可以使用上述的词向量进行参数化。假设我们给定一个得分函数s，它将(word, context)的pairs映射到得分\(s \in R\)。定义一个上下文词的概率的一个可能的选择是：

\[p(w_c|w_t) = \frac{exp(s(w_t,w_c))}{\sum_{j=1}^W exp(s(w_t,j))}\]

然而，这样的模型不适合我们的case中，因为它意味着，给定一个词\(w_t\)，我们只能预测一个上下文词\(w_c\)。

预测上下文词(context words)的问题可以通过构建独立的二分类任务集合来替代。接着，该目标是独立地预测上下文词是否出现。对于在位置t处的词，我们会考虑所有的上下文词作为正例，并从字典中随机抽样负样本。对于一个选中的上下文位置c，使用binary logistic loss，我们可以获取以下的negative log-likelihood:

\[log(1 + e^{-s(w_t,w_c)}) + \sum_{n \in N_{t,c}} log(1 + e^{s(w_t,n)})\]

其中\(N_{t,c}\)是从词汇表中抽取的负样本的一个集合。通过表示logistic loss function l：\(x \rightarrow log(1+e^{-x})\)，我们可以重写目标函数：

\[\sum_{t=1}^T \sum_{c \in C_t} [l(s(w_t,w_c)) + \sum_{n \in N_{t,c}} l(-s(w_t,n))]\]

对于在词\(w_t\)和它的一个上下文词\(w_c\)之间的scoring function s的一个天然参数化方案是，使用词向量（word vectors）。假设在词汇表中的每个词w，定义两个向量\(u_w in R^D\)和\(v_w \in R^D\)。这两个向量有时被称为是输入向量（input vector）和输出向量（output vector）。特别的，我们的向量\(u_{w_t}\)和\(u_{w_c}\)分别对应于词\(w_t\)和\(w_c\)。接着，score可以使用在该词与上下文向量间的点乘（dot product）来表示：\(s(w_t,w_c) = u_{w_t}^T v_{w_c}\)。

3.相关工作

一些已经存在的word2vec系统被限制在只能在单机CPU上运行，而一些使用多核cpu多节点来加速word2vec的方式则进行分布式数据并行训练。这些方法包含了Spark MLLib和Deeplearning4j。这些系统在每轮iteration后依赖reduce操作在所有executors间同步模型。将所有的word vectors跨节点广播（broadcast）的这种方式限制了可扩展性，因为通常网络带宽只比CPU内存要低一阶。另外，模型的accuracy会大幅下降，因为使用了更多节点来增加吞吐。

Intel的工作[11]展示了通过基于minibatching和shared negative samples的scheme可在多CPU节点上进行极强地扩展。该方法将level-1 BLAS操作转换成level-3 BLAS矩阵乘法操作，从而有效地利用现代架构的向量乘法/加法指令（vectorized multiply-add instructions）。然而，该方法仍不能利用GPUs，而且他们的实现只能在Intel BDW和KNL处理器上扩展良好，而这些处理器比GPU要昂贵，不会被主流的云服务平台所提供。借鉴他们提出的思想，我们可以通过一个minibatch共享negative samples，并使用高度优化的cuBLAS level-3矩阵乘法核（matrix multiplication kernels），但由于要进行乘法操作的矩阵size很小，CUDA核启动（kernel-launches）的开销会剧烈降低性能和可扩展性。

其它一些工作[12,13]已经利用像tensorflow, keras, theano等深度学习库，但展示出的性能要比fasttext的CPU实现要慢。由于word2vec的一轮迭代计算并不非常密集，需要使用一个很大的batch size来完全利用GPU。然而，对训练数据进行mini-batching会急剧降低收敛率，而如果batch size=1, 训练又会非常慢。

4. 使用CUDA进行GPU并行化

由于GPU架构比CPU cores提供了更强的（多好多阶）并行机制，word2vec看起来能很好地使用GPU进行加速，算法本身展示了可以通过异步SGD(asynchronous SGD)或Hogwild进行很好的并行化。然而，如果使用更多的并行化，不同线程之间在读取和更新词向量时可能会发生冲突，从而对accuracy产生大幅下降。因而，必须仔细考虑，如何在并行化级别上和同步机制间做好权衡。

深度学习框架没有像CUDA C++ API那样，提供在GPU的可扩展性与并行化之间的细粒度控制。有必要对算法设计进行大幅重构，从而允许最大化并行吞吐，而强制同步会阻止accuracy的降低。我们控制了以下两种方法来基于CUDA实现。

4.1 每个词一个线程块（one thread block per word）

原始的word2vec实现按顺序处理一个句子，例如：对于中心词\(w_t\)，它会考虑围绕中心词作为目标词的window size（ws）中的所有词，这意味着在\([w_{t-ws}, w_{t+ws}]\)所有的词向量，会在一个step中获得更新。相似的在下一step中，对于中心词\(w_t + 1\)，在范围\([w_{t-ws+1}, w_{t+ws+1}]\)内的所有向量都将被更新。这意味着，当处理一个句子时，一个词向量可以被修改2ws+1次，理想的，每个连续的step都应使用被前一step修改更新后的向量（updated vectors）。

从头设计一个CUDA程序需要我们对网格结构(grid)和线程块(thread blocks)做总体规划。在相同线程块中的线程可以相互进行同步，但如果属于不同线程块的线程不能相互通信，使得线程块相互独立。在该方法中，我们选择为每个词分配一个线程块，在一个块内的线程数可以是乘以32, 相当有效。随着在一个块内的线程数与向量维度（通常100）越来越接近，每个线程会映射到一个向量维度上，并做element-wise乘法操作。这种单独的乘法接着使用一个reduce kernel来计算任意2个给定向量间的点乘来进行有效求和。我们探索了一些并行reduction技术，最终使用采用一个高度优化过的completely unrolled reduce kernel。该算法设计采用并行机制能达到峰值，因为每个词会通过一个线程块进行独立处理，在线程块中的线程只有当执行reduce操作时会进行同步（synchronize）。然而，该方法会有一个主要缺点，它能极大地破坏embeddings的质量。不同的线程块可以独立的修改词向量，没有同步机制，它对于accuracy是有害的，因为随着窗口沿着句子进行滑动，每个向量可以更新2w+1次。这会产生大量线程覆盖写（overwrites）和非最新读取（stale reads）。

4.2 每个句子一个线程块

在之前章节讨论过，没有任何同步机制的词向量更新，可以充分利用CUDA并行机制，但是会由于竞争条件（race conditions），会降低embeddings的accurary。随着窗口沿着句子滑动，当处理后一个词时，应使用前面已经更新（updated）的词向量。因而，为了解决顺序依赖（sequential dependency），与前面的方法类似，该方法会将每个句子映射到一个CUDA线程块上，它会将该向量的每一维映射到一个线程上。因此，不同线程块相互并行处理句子，而在一个句子中，线程块会根据词进行循环来顺序更新向量。该方法仍会导致一些竞争条件（race conditions），但由于不同句子通常不会有许多词相同，它实际上不会造成收敛问题。

由于文本语料对于驻在GPU内存中来说可能很大，数据从磁盘到GPU中会流式化（streamed），并且许多句子会进行batch化，以分摊数据在CPU和GPU间传输的开销。为了评估accuracy和throughput间进行平衡，线程块、或者句子被并行处理的最优化数目，通过经验选择。并发处理越多勉励子，会增加throughput，但会产生accuracy的降低，因为不同线程块更新相同的词向量的机率会增加。

一些其它的最优化（optimizations），可以使该方法更有效。如果kernel的执行时间比数据传输时间要少，那么GPU会空闲等待下一batch的句子。为了避免这种情况，我们尝试通过使用多CPU线程和CUDA streams，将数据传输和在GPU上进行kernel execution的过程进行重叠（overlap），它允许数据传输到GPU时仍在忙着运行kernels，这样GPU时间不会空闲。我们使用多CPU线程来从磁盘读取数据，并准备下一batch的句子，它可以使用多个CUDA streams来并发传输数据给GPU。

我们将在第5节描述上述方法的实验。

4.3 在多GPU上的分布式训练

在多GPU分布式系统上扩展BlazingText是很关键的，因为在单GPU上训练一些工业界特别大的数据集时（数T），它仍可能花费数天时间。为了扩展BlazingText，我们探索了不同的分布式训练范式——模型并行化（model parallelism） 和 数据并行化（data parallelism）。由于向量维度通常很小，点乘的规模也不会很大，因而将向量的不同维量进行分布式，不会带来很多的性能增益。因而，我们使用数据并行化，当使用N个GPU时，我们将数据集等分为N份相等的shards。对于词汇表中的所有词，输入向量和输出向量的模型参数，会被复制到每个GPU上；每个设备接着独立处理它所拥有的数据分区，并更新它的局部模型（local model），然后与其它N-1个GPU周期性同步局部模型（local model）。

数据并行化要解决的主要问题是，如何在GPU间有效进行模型同步。它可以使用NVIDIA的NCCL库[15]来有效解决，该库提供了AllReduce方法，它可以基于GPU网络拓朴以一种最优的方法，来处理在GPU间的peer-to-peer数据传输。如果GPU没有通过相同的PCIe swith或者相同的IOH chip进行连接，那么数据会通过host CPU进行传输。由于模型参数的size可能是数百MB，同步机制可能开销很大，因而决定合理的同步间隔十分重要。频繁的同步将产生更好的收敛，但会减慢训练，反之亦然。出于简洁性，我们选择在每轮迭代后进行同步，并在后续会继续探索更有效的同步机制。

5.实验

我们使用上述提到的方法，为单GPU和多GPU系统进行最优化BlazingText。在本节中，我们会展示throughput（单位：百万 words/sec）和所学到的embeddings的accuracy（在标准word similarity和word analogy test上）。我们会对BlazingText和FastText CPU（没有subword embeddings的版本）实现进行benchmark。

硬件：所有的实验都在AWS p2.8xlarge GPU实例上运行，它具有8个NVIDIA K80 GPU卡，以及Intel Xeon CPU E5-2684 v4@2.3GHz 16核（32线程）。

软件：BlazingText使用C++编写，使用CUDA compiler：NVCC v8.0编译。

训练语料：我们使用两个不同语料进行训练：(1) 来自Wikipedia的包含1700w个词的Text8数据集[16]，(2) 一个十亿词的benchmark dataset[17]。

测试集：学到的embedding会在word similarity和word analogy任务上进行评估。对于word similarity，我们使用WS-353[18]，它是最流行的测试数据集。它包含了人工审核过的相似word pairs。词表示的评估通过根据cosine相似度对这些pairs进行排序，并使用Spearman’s rank相关系数进行评估。我们使用google analogy dataset来进行word analogy评估。

超参数：对于所有的实验，我们展示了使用CBOW和Skipgram算法（negative sampling）和FastText的缺省参数设置（dim=100,window size=5, sampling threold=1e-4, inital learning rate=0.05）。我们为Text8数据集使用20个epochs，One Billion Words Benchmark则使用10个epochs。

5.1 Throughput

图1

图1和图2展示了BlazingText on GPU和FastText on CPU的throughput以百万 words/sec测量。分别跨多GPU和多CPU运行，分别跑SKipgram和CBOW。当扩展到多GPU时，我们的实现达到了接近线性的加速。使用8个GPU，Skipgram可以达到1.32 亿 words/sec，而CBOW可以达到4.25 亿 words/sec，它比32线程的FastText要快3倍。如表1所示，跨多GPU扩展在accuracy上影响很小，因为我们的实现可以有效利用多GPU架构。随着在throughput和accuracy间进行平衡，我们进一步通过降低同步频率来增加throughput，只要accuracy的下降是可接受的。

图2

5.2 Accuracy

表1

我们评估了从fasttext实现以及我们的实现（随GPU数目不同）中训练得到的该模型，并在表1中展示了他们在word similarity和word analogy任务上的预测效果。为了确保我们的实现可以很好泛化，我们会使用2个不同的语料来训练模型——text8和1B words benchmark。

由于GPU并行化，为了消除随机性，我们运行每个实验多次（n=10），并展示了平均结果。如表1所示，BlazingText展示了在多GPU上的效果与FastText CPU上的效果相近。当使用4GPU时，性能几乎相同，在一些情况下比CPU版本要好。如你所料，预测的效果会随着使用更多GPU而减少，但在可接受范围内。对于相似度评估，使用8 GPUs会达到2%更差的accurary，但会比32 CPU线程超过3倍加速。

对于analogy评估，在多GPU和CPU上的不同更显著。在我们的实验中，我们主要关注可扩展性，因而当扩展到更多GPU时，我们不会增加同步频率。增量同步频率可以维持一个可接受的accuracy，但会在扩展性上可降，导致一个sub-linear scaling。然而，取决于终端应用，可以调整同步频率。

参考

• 1.https://www.researchgate.net/publication/320760204_BlazingText_Scaling_and_Accelerating_Word2Vec_using_Multiple_GPUs

在各种类型的DNN漫天飘的时代，周老师等提出了gcForest算法。以下是论文核心部分的介绍：

3. gcForest算法

gcForest算法引入了cascade forest结构，以及multi-grained scanning。

3.1 cascade forest结构

DNN中的表征学习几乎全依赖于对原始特征（raw features）进行layer-by-layer的处理。受该点的启发，gcForest使用了一个层叠（cascade）结构，如图2所示，每一级（level）cascade会接受由先前级（preceding level）处理后的信息，然后输出它的结果到下一级（next level）中。

图2:cascade forest结构。假设，cascade的每一级(level)只包含两个random forest（黑色）以及两个completely-random tree forests（蓝色）。假设要预测三个类；这样，每个forest将输出一个三维的分类向量，接着将他们串联起来对原始特征进行重新表征（ re-representation）。

每一级是一个决策树森林的ensemble（比如：一个ensemble of ensembles）。此处，我们引入了不同类型的forests来增强diversity，因为对于ensemble的构造来说diversity至关重要。出于简洁性，这里我们使用完全随林树森林（completely-random tree forests）以及两个随林森林（random forest）。每个completely-random tree forests只包含500个完全随机的树，通过对该树的每个节点上做split来随机选择一个feature、完全生长直到纯叶子（pure leaf：每个叶子节点只包含相同类的样本）来生成。相似的，每个随机森林包含了500棵树，通过随机选择\(\sqrt{d}\)个特征作为候选（candidate），并选择对于split后满足最好gini系数的候选（d为输入特征数）。每个forest上的树数目是一个超参数，会在后面1.3描述。

给定一个样本，每个forest为它将生成一个类分布的估计：通过统计不同分类训练样本在叶子节点上的百分比，接着在同一forest上对所有树做平均，如图3所示，其中红色会高亮出样本落到叶子节点的path。

图3: 类向量生成的展示。在叶子节点上不同的标记表示了不同的分类

估计得到的类分布（class distribution）形成了一个类向量（class vector），接着将它们与原始的特征向量进行串联作为cascade下一级的输入。例如，假设有三个类，接着，4个forests的每个都会产生一个三维的类向量；接着，下一级cascade会多接收12个（3x4）扩张特征。

注意，这里我们采用了类向量的最简形式，例如：样本落到的叶子节点上的类分布。结果表明，少量扩展的特征可以传达非常有限的扩张信息，当原始特征向量很高维时很可能被淹没。我们将在实验中展示，这样简单的特征扩展其实是有好处的。预期上如果有更多的扩展特征会收到更大的收益。实际上，显然更多特征可以被合并进去，强如：父节点的类分布表示着先验分布（prior distribution），兄弟节点（sibling nodes）表示着互补分布（complementary distribution）。

为了减小overfitting的发生，由每一个forest生成的类向量通过k-fold交叉验证产生。实际上，每个样本被用于K-1次训练，产生k-1个类向量，接着求平均产生最终的类向量作为下一级的扩展特征。在新一级后，整体cascade的效果会通过验证集被评估，如果没有大的效果增益，训练过程会终止；cascade levels的数目会被自动决定。注意，当考虑训练成本、或者有限计算资源时，使用训练误差（training error）而非交叉验证误差（cross-validation error）可以被用于控制cascade的生长。通过对比DNN（它的模型复杂度确定），gcFroest会自适应地决定它的模型复杂度。这允许它能应用于不同规模的训练数据，而非只限于大规模数据。

3.2 Multi-Grained Scanning

DNN在处理特征关系上很强大，例如，CNN在图片数据上很有效（其中原始像素间的空间关系是很重要的）；RNN对于序列型数据很有效（其中序列关系很重要）。受它们的启发，gcForest使用滑动窗口（sliding windows）来扫描原始特征。假设有400个原始特征，我们使用100个特征的window size。对于序列数据，可以通过对每隔一个特征进行窗口滑动来生成一个100维的特征向量；总共可以生成301个特征向量。如果原始特征具有空间关系，比如：在400个图片像素上的20x20的panel，接着一个10x10的window可以产生121个特征向量（比如：121 10x10 panels）。所有的特征向量从正负训练样本上被抽取（忽略正负），接着被用于生成像3.1所述的类向量：从相同size的window中抽取的样本会被用于训练一个completely-random tree forest和一个 random forest，接着生成的类向量被串联作为转换后的特征。如图4所示，假设存在3个类和使用100维的window，对应于一个400维的原始特征向量，会产生一个1806维的转换特征向量。

图4: 使用滑动窗口扫描进行feature re-representation。假设存在三个类，原始特征是400维，滑动窗口是100维。

对于从窗口中抽取的样本，我们会简单地为他们分配原始训练样本带有的label。这样，一些label分配本质上是不正确的。例如，假设原始训练样本是一个关于“car”的正样本图像；很明显许多被抽取的样本（extracted instances）不包含一个car，因而它们相当于会被不正确地标记成正样本。该方法实际上是与Flipping Output方法有关：这是一种用于ensemble中增强diversity的典型的输入特征操作法。

图4展示了滑动窗口的一个size。通过使用多个size的滑动窗口，会生成不同粒度的特征向量，如图5所示。

图5: gcForest的整体过程。假设要预测三个类，原始特征400维，使用三个不同size的滑动窗口。

图5归纳了gcForest的整体流程。对于m个训练样本，一个100个特征size的窗口会生成一个 (301 x m) 的100维训练样本的数据集。这些数据会被用于训练一个completely-random tree forest和一个random forest，每一个包含了500 trees。如果要预测三个类，会获得3.1节中描述的一个1806维的特征向量。转换的训练集接着被用于训练第一阶段（1st-grade）的cascade forest。

相类似的，对于每个原始的训练样本，size为200和300个特征的滑动窗口会分别生成1206维和606维的特征向量。转换后的特征向量，会与由前一级生成的类向量一起扩展，接着被用于训练第二阶段（2nd-grade）、第三阶段（3nd-grade）的cascade forests。该过程会重复，直到验证集效果收敛。换句话说，最终模型实际上是一个cascade of cascades，其中每个cascade包含了许多级(level)，每个level对应于一个粒度的scaning，例如：第一个cascade包含了从Level $ 1_A $到Level $ 1_C $ (A、B、C)三个level，如图5所示。注意，对于不同的任务，如果计算资源允许的话，用户可以尝试更多粒度。

给定一个测试样本，它会经过multi-grained scanning过程来得到相应的转换后的特征表示，接着经过cascade直到最后一个level。最终的预测会通过对最后一个level聚合4个3维类向量，使用聚合的最大值来得到最终分类。

表1总结了DNN和gcForest的超参数，其中，实验中使用了缺省值。

表1: 超参数和缺省值。粗体高亮超参数具有相当大的影响；“？”表示缺省值未知，或者对于不同的任务需要不同的设置

4.实验

4.6 Multi-Grained Scanning的影响

为了研究cascade forest structure和multi-grained scanning的贡献，表9对比了更可怕额cascade forest的gcForest在不同的数据集上的表现。结果表明当存在空间特征关系、或者序列特征关系时，multi-grained scanning可以明显提升效果。

4.7 Cascade Structure的影响

gcForest的最终模型结构是cascade of cascades，其中每个cascade包含了多个level，每个level对应于一个粒度的scanning，如图5所示。有许多其它可能的方式来利用多粒度（multi grain）的特征，比如：将所有特征连接起来，如图6所示。

图5: $gcForest_{conc}$变种，它会将多个grain的特征连接起来。假设有三个类要预测，原始特征是400维，使用三个size的滑动窗口。

表10比较了gcForest和$gcForest_{conc}$。

4.8 更大模型

结果表明，更大的模型趋向于提供更好的效果，由于计算资源因素，我们没有尝试更多的grains，forests，trees。

注意，计算设备对于更大的模型训练是很重要的，比如：GPUs 之于DNN。另一方面，一些新的计算设备，比如： Intel KNL of the MIC (Many Integrated Core)，可以为gcForest提供类似于GPU对DNN那般的潜在加速。另一方面，gcForest的一些组件，比如：multi-grained scanning，可以通过利用GPU来加速。另外，使用分布式计算还有大量优化空间。

参考

https://arxiv.org/pdf/1702.08835.pdf

我们来看下youtube RNN: Alex Beutel等提出的《Latent Cross: Making Use of Context in Recurrent Recommender Systems》。

1.介绍

对一个推荐(recommendation)的上下文（context）进行建模很重要，上下文包括：正搜索一个想看的视频的该用户、当前时间(the time of day)、位置(location)、用户设备等。在因子分解setting中提出了许多模型，比如：对位置进行张量分解[17]、对不同类型的用户动作进行(unfolding tensors)[46]、或者对时间进行人工特征工程。

随着深度学习的进展，在神经网络推荐系统(neural recommender systems)中，如何合并这些context feature很少直接被研究。之前在DNN推荐系统上的工作，就大量依赖将上下文建模成直接特征，或者具有一个多任务目标（multi-task objective）[11]，一个值得注意的例外是，利用RNN来建模时序模式(temporal patterns)【25,39,43】。在本paper中，我们会借鉴contextual CF文献和神经网络推荐系统文献。我们会探索在深度神经推荐系统中（特别是RNN模型中）如何利用context数据，并展示了流行的技术。

我们探索了在youtube RNN-based推荐系统中，利用context数据的能力。大多数生产环境中，我们具有大量重要的context数据：请求时间、观看时间、设备类型、网页端还是移动app端。在本paper中，首先，我们从理论上解释对将上下文建模成直接特征的限制，特别是使用前馈神经网络时（做为示例baseline: DNN）。我们接着提供了一种很容易使用的技术，在一个更复杂的RNN模型上合并这些特征，来产生对预测accuracy上的提升。

我们的贡献有：

• 一阶挑战（first-order）：我们展示了一阶神经网络来建模低秩关系的挑战
• 产品模型（Production Model）：我们描述了在youtube中如何来构建一个大规模的RNN推荐系统。
• Latent Cross: 我们提供了一个简单技术，称为：“Latent Cross”，来在我们的模型上以更有表达力的方式来包含context特征。特别的，latent cross会在context embedding和神经网络的hidden states间执行一个element-wise product。
• 经验结果：我们提供了经验结果来验证在推荐accuracy上的提升。

2.相关工作

我们做了许多相关研究的调查。见表1.

表1: 有关的推荐系统的关系：

上下文推荐(Contextual Recommendation)：大量研究集中于在推荐期间使用上下文数据。特别的，特定类型的上下文数据已经深入进行探索，其它类型都还比较抽象。例如，推荐中的时序动态性(temporal dynamics)已经被广泛探索[6]。在Netflix Price期间，Koren[29]在netflix数据集上发现了大量长范围的时序动态性（long-ranging temporal dynamics），并添加了时序特征到它的CF模型中以提升效果。研究者们也探索过在短时范围内（例如：session）的偏好是如何演进的【39】。更多通用的抽象已经被用于建模推荐的偏好演进，例如：点进程(point processes)[15]和RNN网络【43】。相似的，建模用户动作与人口属性数据也在概率模型、MF（矩阵分解）、TF（张量分解）、中被广泛探索，许多方法在MF和TF上构建了交叉学习(cross-domain)。像FM等方法[34]和其它上下文推荐[22,37,48]已经提供了这些CF方法的泛化。

神经推荐系统：随着NN的流行，推荐系统研究者开始应用DNN到推荐中。早期的迭代主要关注将CF的思想应用的神经网络中，比如：auto-encoder[36]或者 joint deep&CF模型[20]。另外也设计了更复杂的网络来合并更多类型的输入特征[11]。Cheng [7]在DNN模型外，通过一个线性模型来处理上下文的特征交叉。

最近使用RNN的推荐系统多了许多[21,25,39,43]。其中，[25,43]包含了时序信息作为特征，并在它们的模型中进行管理，[41]包含了通用的上下文特征。然而，在这些case中，这些特征都与输入进行拼接（concatenated），我们在后面会展示这样做的限制。[49]改进了LSTMs，通过用乘法来合并时序信息，但不能将它们泛化到其它上下文数据上。

二阶神经网络：本paper的一个主要点是，乘积关系(multiplicative relations)在神经推荐的重要性。这些二阶单元在神经网络中的许多地方出现。recurrent units(例如：LSTMs和GRUs)是通用的使用gating机制的二阶units，会使用element-wise乘法。更复杂的教程可以在[18]中找到。

另外，网络顶部用于分类的softmax layers是显式的bi-linear layers，它位于DNN产生的embedding与label classes的embeddings之间。该技术在多篇paper上被提及，包含DNN顶部的：user-item bi-linear layers[20,41,43,47]。

与本paper中描述的技术相似的是，乘法模型[27,44]。这些乘法结构大多数在NLP中被使用[14,27]。该NLP方法被应用于个性化建模中[40]（使用一个有些不同的数学结构）。最近, [25]提出的乘法技术，不仅用在上下文数据上，也直接用在用户层面上，它与TF方法相似。PNN[33]和NFM[19]将该思想放在了在输入侧采用将所有特征对进行乘积，接着对结果拼接(concatenating)或者平均(averageing)，然后传给一个前馈网络。这些模型的思想与我们类似，但区别是：我们更关注在上下文数据和用户动作间的关系，我们的latent crossing机制可以在整个模型中使用，我们演示了在一个RNN推荐系统中这些交叉的重要性。

更复杂的模型结构例如attention模型[3]，记忆网络(memory networks)[38]，元学习（meta-learning）[42]也依赖于二阶关系，正变得流行。例如：attention模型利用attention vectors来构建hidden states和一个乘法。然而，这些方法结构上更复杂，很难进行训练。相反的，latent cross技术很容易训练，在实践中很有效。

3.Preliminaries

假设，一个推荐系统有一个数据库 \(\varepsilon\)：它由事件e（events）构成，而e则由许多k元组(k-way tuples）组成。\(e_l\)表示tuple中的第l个值，\(e_{\bar{l}}\)表示在tuple中其它k-1个值。

表2:

例如，Netflix Prize setting中，使用三元组tuples \(e \equiv (i,j,R)\)，表示用户i对电影j有个评分R。我们可以在此基础上加上context信息(比如：时间和设备)：\(e \equiv (i,j,t,d)\)，表示用户i观看了视频j，在时间点t设备类型d上。注意，每个值即可以是离散化的类别型变量(比如在其中有N个用户，其中\(i \in I\))，也可以是连续型（比如：t是一个unix timestamp） 。连续型变量在预处理阶段被离散化很常见，比如：将t转换成event发生的天数。

有了该数据，我们可以构建推荐系统：在给定event的其它值时，预测event的一个值。例如：Netflix Prize说，一个tuple \(e=(i,j,R)\)，它使用(i,j)来预测R。从机器学习的角度，我们可以将我们的tuple e分割成特征x和label y，比如：\(x=(i,j)\)和label y=R。

我们可以进一步对推荐问题进行重设计（reframe）：预测在某个给定时间点，一个用户会观看哪个视频；定义了\(x=(i,t)\)以及\(y=j\)。注意，如果label是类别型随机值(比如：视频ID)，可以将它看成是一个分类问题；如果label是真实值（比如：rating），可以将它看成是一个回归问题。

在因子分解模型中，所有输入值被认为是离散的，接着被嵌入、然后进行乘积。当我们“嵌入”一个离散值时，我们就学到了一个dense latent表示，例如：用户i通过dense latent vector \(u_i\)进行描述，item j通过dense latent vector \(v_j\)进行描述。在矩阵分解模型中，预测总是基于内积\(u_i \cdot v_j\)。在张量分解（TF：tensor factorization)模型中，预测基于\(\sum\limits_r u_{i,r} v_{j,r} w_{t,r}\)，其中\(w_t\)是一个关于时间或其它上下文信息的dense vector embedding。FM[34]是这些类型模型的一个简洁抽象。出于简洁性，我们将\(\langle \cdot \rangle\)看成是一个多维的内积，例如：\(\langle u_i, v_j, w_t \rangle = \sum\limits_r u_{i,r} v_{j,r} w_{t,r}\)。

神经网络通常也会嵌入离散输入。也就是说，给定一个输入\((i,j)\)，网络的输入可以是\(x=[u_i;v_j]\)，其中\(u_i\)和\(v_j\)被拼接到一起，参数是可训练的（通过BP）。因而，我们将NN的形式定义为：\(e_l=f(e_{\bar{l}})\)，其中，该网络会采用tuple的所有值、而非一个值来当成输入，接着我们训练f来预测tuple的最后一个值。后续我们会将该定义展开，以允许模型来采用相关的之前事件来作为该网络的输入，正如在序列模型中一样。

4.一阶挑战

为了理解神经推荐系统是如何利用拼接特征（concatenated features）的，我们研究了一些典型的网络构建块。如上所述，神经网络（特别是前馈DNNs），通常会在一阶操作（first-order op）上构建。更准确的说，神经网络通常依赖于矩阵向量乘法（\(Wh\)），其中：W是一个通过学习得到的权重矩阵，h是一个input（可以是一个网络的input，也可以是前一layer的output）。在前馈网络中，FC layers可以以这种形式描述：

\[h_{\tau} = g(W_{\tau} h_{(\tau-1)} + b_{\tau})\]

…(1)

其中，g是一个element-wise操作（比如：一个sigmoid或ReLU），\(h_{(\tau-1)}\)是前一层的output，而\(W_{\tau}\)和\(b_{r}\)是要学的参数。我们将它认为是一个在\(h_{(\tau-1)}\)上的一阶单元（first-order cell），\(h_{(\tau-1)}\)是一个k维向量，不同的值会基于W的权重一起求和，而非相乘。

尽管神经网络可以使用多个layers来逼近任意函数，它们的核心计算与过去的CF的思想在结构上有很大不同。矩阵分解模型会采用通用形式\(u_i \cdot v_j\)，从不同类型的输入(users, items, time)产生模型学习低秩关系。这样的低秩模型在推荐系统中已经很成功，我们会问以下问题：使用一阶单元的神经网络如何去建模低秩关系？

4.1 建模低秩关系

为了测试一阶神经网络能否建模低秩关系，我们可以生成人工合成的低秩数据，并研究不同size的神经网络是如何拟合数据的。确切的说，我们可以考虑一个m-mode的tensor（相当于：m元组），其中它的每个维度(比如：元组i)都是size N。对于\(mN\)个离散特征，我们会使用下面的简单等式来生成长度为r的随机向量\(u_i\)：

\[u_i \sim \mathcal{N}(0, \frac{1}{r^{(1/2m)}} I)\]

…(2)

最后产生的结果数据(\(u_i\))是一个近似相同规格(它的均值为0, 经验方差接近为1)的rank为r的matrix或者tensor。例如，对于m=3，我们可以使用多个这些生成的embeddings（即：生成的matrix或tensor）来表示形式为(i, j, t, \(\langle u_i, u_j, u_t \rangle\))的events。

我们使用该数据来尝试拟合不同size的模型。特别的，我们会考虑这样一个模型：它使用离散特征进行嵌入同时拼接（concatenated）在一起做为输入。该模型只有一个hidden layer，它使用ReLU activation，接着跟最后一个线性层。该模型使用tensorflow编写，使用MSE训练，并使用Adagrad optimizer训练直到收敛。我们在训练数据和模型预测间使用Pearson correlation(R)来衡量并上报了模型的accuracy。我们使用Pearson相关系数，以便在数据的方差上有细微的不同可以认为是不变的。我们在训练数据中上报了accuracy，因为我们会测试这些模型结构对于拟合低秩模式的好坏程度（例如：是否可以从它进行泛化）。

为了建模低秩关系，我们希望看到，模型逼近单个乘法（它可以表示变量之间的交叉）的好坏程度。所有数据均使用N=100生成。对于m=2，我们会检查为让两标量(scalar)相乘hidden layer需要的大小；对于m=3，我们会检查为让三个标量相乘hidden layer需要的大小。我们会使用\(r \in \lbrace 1,2 \rbrace\)来观察，模型size随所需乘法数是如何增长。我们将每个离散特征作为一个20维向量进行嵌入，它比r大很多（但我们发现：模型的accuracy会与该size独立）。我们测试了hidden layers数目 \(\in \lbrace 1,2,5,10,20,30,50 \rbrace\)。

经验查找（Empirical Findings）。如表3和图2所示，我们发现，该模型会随着hidden layer的size增长，连续逼近数据。直觉上该网络正逼近乘法，一个更宽网络应给出一个更好的近似。第二，我们观察到，随着rank r从1增加到2，hidden layer size近似二倍可以达到相同的accuracy。这与我们的直觉很相近，随着r的增加，意味着增加了更多交叉。

表3:

更有趣的是，我们发现，对于r=1和m=2, 它会采用一个hidden layer size=5来获得一个“较高”的accuracy估计。考虑到CF模型通常会发现rank 200关系[28]，这直觉上建议，对于单个two-way关系的学习，真实世界模型需要非常宽的layers。

图2

另外，我们发现建模超过2-way的关系会增加逼近这种关系的难度。也就是说，当我们从m=2到m=3时，我们会发现该模型会需要一个宽度为5的hidden layer到一个宽度为20的hidden layer，来获取MSE=0.005或Pearson相关度=0.99.

总之，我们观察到ReLU layers可以逼近乘法交叉，但这样做还相当不够。这会激发模型的需求：是否可以更轻易来表达和处理乘法关系。我们将我们的关注点转向使用一个RNN做为baseline；它是一个更强的baseline，对比前馈DNN，它可以更好地表示乘法关系。

5.youtube RNN推荐

有了上述分析，我们描述了在Youtube RNN推荐上的提升。RNN看成是一个baseline模型，因为他们已经是二阶神经网络，比一阶模型要复杂很多。

我们会做个介绍，并在第6节描述如何利用上下文数据进行提升。

5.1 公式描述

在我们的setting中，我们会观察：user i已经观看了video j（该视频由user \(\phi(j)\)上传）的events，在时间t时（我们后续会引入额外的上下文特征）。为了建模用户偏好和行为的演进，我们使用一个RNN模型，其中模型的输入是：

• \(X_i=\lbrace e=(i,j,\phi(j),t) \in \epsilon \mid e_0 = i \rbrace\)：它表示用户的events集合。

我们使用\(X_{i,t}\)来表示用户\(X_i\)在在时间t之前的所有观看

\[X_{i,t} = \lbrace e = (i,j,t) \in \epsilon | e_0 = i \wedge e_3 < t \rbrace \subset X_i\]

…(3)

该训练模型的目标是为了生成顺序预测概率 \(Pr(j \mid i,t,X_{i,t})\)，即：user i根据给定时间t之前所有观看行为，会观看的video j。出于简洁性，我们会使用：

• \(e^{(\tau)}\)来表示在序列中的第\(\tau\)个事件，
• \(x^{(\tau)}\)用来表示对于\(e^{(\tau)}\)的转移输入，
• \(y^{(\tau)}\)表示尝试对第\(\tau\)个event所预测的label。

在上述示例中，如果：

• \[e^{(\tau)} = (i,j,\phi(j),t)\]
• \[e^{(\tau+1)} = (i,j',\phi(j'),t')\]

那么输入\(x^{(\tau)} = [v_j; u_{\phi(j)}; w_t]\)，它被用于预测\(y^{(\tau+1)} = j'\)，

其中：

• \(v_j\)是视频embedding
• \(u_{\phi(j)}\)是上传者embedding
• \(w_t\)是上下文embedding

当预测\(y^{\tau}\)时，我们当然不能使用对应event \(e^{(\tau)}\)的label作为输入，但我们可以使用\(e^{(\tau)}\)的上下文，它可以通过\(c^{(\tau)}\)来表示。例如：\(c^{(\tau)} = [w_t]\)。

5.2 Baseline RNN的结构

我们的RNN模型图如图1所示。RNN网络会建模一个动作序列。对于每个event \(e^{(\tau)}\)，该模型会采用一个step forward，处理\(x^{(\tau)}\)并更新一个hidden state vector \(z^{(\tau-1)}\)。为了更精准，每个event首先会通过一个神经网络\(h_0^{(\tau)} = f_i(x^{(\tau)})\)。在我们的setting中，这将会是一个identity函数或者fully-connected ReLU layers。

图1:

该网络的recurrent部分是一个函数\(h_1^{(\tau)}\)，\(z^{(\tau)} = f_r(h_0^{(\tau)}, z^{(\tau-1)})\)。也就是说，我们会使用一个recurrent cell，比如一个LSTM或GRU，它会采用state。

为了预测\(y^{(\tau)}\)，我们使用\(f_o(h_1^{(\tau-1)}, c^{(\tau)})\)，它是另一个可训练的神经网络可以产生在可能值\(y^{\tau}\)上的一个概率分布。在我们的setting中，该网络会采用RNN的output作为它的输入以及将来预测的上下文，最后会以一个在所有视频上的softmax layer做为结尾。该网络可以包含多个FC layers。

5.3 上下文特征

该模型成功的核心是，除了视频观看序列之外，会合并上下文特征。我们会讨论如何使用这些特征。

TimeDelta。在我们的系统中，有效对时间进行合并，对于RNN的accuracy很重要。历史上，时间上下文已经以多种方法合并给CF模型中。这里我们使用一种称为timedelta的方法：

\[\Delta t^{(\tau)} = log( t^{(\tau+1)} - t^{(\tau)})\]

…(4)

也就是说，当事件\(e^{(\tau)}\)发生时，到下一事件时或者到做出预测时有多久。这与[25]和[49]中对时间表示大致相同。

软件客户端：youtube视频会在多种设备上进行观看：在浏览器端、IOS、Android、Roku、chromecast，等等。将这些上下文看成是等价缺失的相关关联。例如，用户在手机端完整观看一个电影的可能性要比在一个Roku设备上更低。相似的，像trailers这样的短视频更可能在手机端观看。对软件客户端建模，特别是它是如何与观看决策相交互的，十分重要。

页面(Page)。我们也会记录一个观看初始来自于系统的哪个地方。例如，我们会区分是来自主页的观看（例如：home page watches），还是来自用户观看了一个视频后由推荐带来的观看(例如：Watch Next Watches)。这很重要，因为来自主页的观看可能对新内容更开放，而从一个之前观看后接着观看很可能归因于用户想对一个主题更深入。

Pre-Fusion和Post-Fusion。我们可以使用这些上下文特征，可以称为\(c^{(\tau)}\)，以两种方式作为直接输入。如图1所示，我们可以将context当成是在该网络底部的一个输入，或者与RNN cell的output进行拼接。我们将在RNN之前的context features包含机制称为“pre-fusion”，在RNN cell之后的context features包含机制称为“post-fusion”[12]。尽管很微妙，该决策对RNN的影响很大。尤其是，通过将pre-fusion中包含一个feature，该feature会在修改RNN的state期间影响预测。然而，通过在post-fusion期间包含一个特征，该特征可以更直接的影响在该step上的预测。

为了管理这个问题，当预测\(y^{(\tau)}\)时，我们通常会使用\(c^{(\tau)}\)作为一个post-fusion特征，并使用\(c^{(\tau-1)}\)作为一个pre-fusion特征。这意味着，\(c^{(\tau-1)}\)会影响RNN state，而\(c^{(\tau)}\)会用于预测\(y^{(\tau)}\)。接着，在下一step，当预测\(y^{(\tau-1)}\)时，\(c^{(\tau)}\)会是一个pre-fusion特征，它会从该time forward上影响RNN的state。

5.4 实现&训练

我们的模型在tensorflow上实现，并在多个分布式workers和parameter servers上进行训练。训练过程会使用提供的BP mini-batch SGD算法，或者Adagrad、ADAM。在训练期间，我们会使用：在\((t_0 - 7days, t_0]\)期间，监控最近100个观看行为，其中\(t_0\)是训练时间。这会对最近观看行为区分次序，因为：当学到的模型应用于线上流量时，该行为与预测任务更相似。

由于存在大量视频，我们会限定要预测的可能视频集合、以及所建模的这些视频的上传者数目。在以下实验中，这些集合的size范围从50w到200w。softmax layer，会覆盖候选视频的所有集合，在每个batch上可以使用sampled softmax使用2w个负例进行训练。我们会使用该sampled softmax在cross entropy loss上进行预测。

6.使用latent cross进行上下文建模

我们的baseline模型的描述已经很清楚了，使用上下文特征通常作为拼接输入到简单的FC layers中。然而，正如第4节所述，神经网络在对拼接输入特征间的交叉建模效率很低。这里我们提出了一种可选方案。

6.1 单个Feature

我们以单个context feature的一个示例开始。我们将使用时间作为一个示例版的context feature。我们不会将特征合并成另一个输入与其它相关特征进行拼接，我们会在网络中执行一个element-wise product。也就是说，我们会执行：

\[h_0^{(\tau)} = (1+w_t) * h_0^{(\tau)}\]

…(5)

其中，我们通过一个零均值的Gaussian分布对\(w_t\)进行初始化（注意：w = 0 是一个单位矩阵identity）。这可以被解释成：上下文在hidden state上提供了一个掩码(mask)或attention机制。然而，它也可以允许在输入选前watch和时间(time)间的低秩关系。注意，我们可以在RNN之后应用该操作：

\[h_1^{(\tau)} = (1+w_t) * h_1^{(\tau)}\]

…(6)

在[27]中提供的技术可以被看成是一种特殊case，其中乘法关系会在网络的高层(沿着softmax function)上被包含，来提升NLP任务。在这种情况下，该操作被认为是TF，其中一个modality对应的embedding由一个神经网络产生。

6.2 使用多种Features

在许多case中，我们会希望包含多个contextual feature。当包含多个contextual features时（比如：time t和device d），我们会执行：

\[h^{(\tau)} = (1+w_t + w_d) * h^{(\tau)}\]

…(7)

我们使用该公式出于以下几个原因：

• (1) 通过使用0均值高斯分布对\(w_t\)和\(w_d\)进行初始化，乘法项具有均值为1, 这样可以在hidden state上扮演着mask/attention机制
• (2) 通过一起添加这些项，我们可以捕获在hidden state和每个context feature间的2-way关系。这会遵循FM的设计。
• (3) 使用一个简单的加法函数很容易训练。

一个像\(w_t * w_d * h^{(\tau)}\)这样的更复杂函数，使用每个额外的contextual feature将可以极大地增加非凸性。相似的，我们可以很难通过训练来学习一个函数（\(f([w_t;w_d])\)），可能会得到更差的结果。包含这些特征的总览可以见图1.

效率（efficiency）：使用latent crosses的一个很大好处是，它的简洁性和计算效率。有了N个context features和d维的embeddings，latent cross可以以O(Nd)的复杂度被计算，不需要增加后续layers的宽度。

7.实验

7.1 比较分析

…

7.2 Youtube模型

第二，我们研究了生产模型的多个变种。

7.2.1 setup

这里我们使用用户观看行为的一个产品数据库，它比上述的setting要不严格些。我们的序列由被看过的视频、该视频的上传者组成。我们使用了一个更大的（百万级）的词汇表，它包含了最近流行的上传视频与上传者。

我们基于users和time，将数据集分成一个训练集和一个测试集。首先，我们将用户分割成两个集合：在训练集中90%的用户，测试集10%。第二，为了通过时间进行split，我们选择了一个时间cut-off \(t_0\)以及在训练期间只考虑在\(t_0\)之前的观看。在测试期间，我们会考虑\(t_0+4\)小时后的观看行为。相似的，视频的词汇表基于在\(t_0\)之前的数据。

我们的模型由embedding和对所有features进行拼接作为输入组成，接着跟一个256维的ReLU layer，一个256维的GRU cell，接另一个256维ReLU layer，接着feed给softmax layer。如前所述，我们使用在\((t_0 -7, t_0]\)期间的100个最近观看行为作为观察。这里，我们使用Adagrad优化器在多个workers和parameter servers上进行训练。

为了测试我们的模型，我们接着会measure MAP@k（mean-average-precision-at-k）。对于不在我们的词汇表中的观看行为，我们总是会将该预测标记为incorrect。MAP@k的评估分可以使用近似45000个观看来measure。

7.2.2 PV作为context

我们开始分析通过以不同方式合并Page带来的accuracy提升。特别的，我们比较了不使用Page，使用Page作为输入与其它输入进行拼接，并执行一个post-fusion latent cross With Page。（注意，当我们将page作为一个拼接特征包含进去后，在pre-fusion和post-fusion期间它都是拼接的）

如图3所示，使用Page与一个latent cross提供了最好的accuracy。别外，我们看到，使用latent cross和拼接输入在accuracy上不会提供额外提升，建议latent cross足够捕获相关信息，它可以通过使用该特征做为一个直接输入进行捕获。

图3

7.2.3 总提升

最后，我们测试了如何在完整产品模型上顶层添加latent crosses来影响accuracy。在这种case中，对于每个观看，模型都知道page、device type、time、视频观看时长、该观看行为离现在多久了（watch age）、uploader。特别的，我们的baseline Youtube模型会使用page、device、watch time、以及timedelta values作为pre-fusion拼接特征，也可以使用page、device、watch age作为post-fusion拼接特征。

我们测试了将timedelta和page作为pre-fusion的latent crosses，同时将device type和page作为post-fusion latent crosses。如图4所示，尽管所有这些特征已经通过拼接被包含进去，将它们做为latent crosses进行包含，对比起baseline可以提供提升。这也演示了：对于pre-fusion和post-fusion，使用多个features来一起工作的的能力，可以提供较强的accuracy提升。

8.讨论

下面有一些问题提出，期待后续解决。

8.1 DNN中的离散关系

许多paper关注点是：允许在特征间的多种交叉，我们发现NN也可以逼近离散交叉，该领域因子分解模型更难。例如，在[46]中，作者发现当user i在item j上执行一个action a时，\(<u_{(i,a)}, v_j>\)比\(<u_i,v_j, w_a>\)具有更好的accuracy。然而，一起发现这样的索引用户和actions，想做到效果好很困难，需要对数据的洞察。

与第4节中的实验相似，我们会根据模式 \(X_{i,j,a}=<u_{(i,a)},v_j>\)生成人造数据，并测试不同的网络结构对于在给定i,j,a并只有拼接特征作为独立输入来预测\(X_{i,j,a}\)是否ok。我们初始为\(u \in R^{10000}\)和\(v \in R^{100}\)作为向量，这样X是一个rank-1矩阵。我们和第4节使用相同的实验过程，为不同隐层和不同隐层宽度的网络测试Pearson相关度(R)。（我们使用learning rate=0.01的这些网络，比使用的learning rate要小10倍）。作为baseline，我们也测试了对于TF（\(<u_i, v_j, w_a>\)）对不同ranks的Pearson相关度。

如图5所示，在某些cases中，deep模型可以实现一个合理的高Pearson相关度，事实上可以逼近离散交叉。同时有意思的是，学习这些交叉需要深度网络使用宽的hidden layers，特别是对于数据size很大时。另外，我们发现这样的网络很难训练。

对比baseline TF的效果，这些数字很有意思。我们观察到因子模型可以合理逼近数据，但需要相当高的rank。（注意，即使底层tensor是满秩的，rank 100的因子分解足够描述它）然而，即使在这么高的rank上，TF模型比起DNN需要更少的参数，更容易训练。因此，随着在第5节中的结果，DNN可以逼近这些模式，但这么做很难，包含低秩交叉可以提供很容易训练的逼近。

8.2 二阶DNN

读这篇paper时，一个很自然的问题是，为何不尝试更宽的layers，让模型更深，或者更多二阶units，比如：GRUs和LSTMs？所有这些是合理的建模决策，但在我们的实验中，模型训练更难。该方法的一个优点是，很容易实现和训练，当配合使用其它二阶units（比如：LSTMs和GRUs）时，并且仍能提供明显的性能提升。

深度学习的成长趋势明显会使用更多二阶交叉。例如，常见的attention模型和记忆网络，如列表所示。而其它则更难被训练，我们相信该工作对神经推荐系统在方向上有一定的指导意义。

参考

https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/46488.pdf

google在2017年提出了一个Deep&Cross Network的模型：

1.介绍

在该paper中，提出了Deep&Cross Network(DCN)模型，它能对sparse和dense的输入进行自动特征学习。DCN可以有效地捕获关于有限阶（bounded degrees）上的有效特征交叉，学到高度非线性交叉，无需人工特征工程或暴力搜索（exhaustive searching）。并且计算代价低。

• 我们提出了一个新的cross network，它显式地在每个layer上进行特征交叉（feature crossing），可有效学习有限阶（bouned degrees）的特征交叉预测，无需人工特征工程和暴力搜索。
• 该cross network简单有效。通过设计，最高的多项式阶在每一layer递增，由layer depth决定。该网络包含了所有阶的交叉项（直到最高阶），它们的系数都不同。
• 该cross network内存高效，很容易实现。
• 我们的实验结果表明，比起接近相同阶的DNN，DCN具有更低的logloss，更少的参数。

2.DCN

本节描述了Deep & Cross Network模型。一个DCN模型会以一个embedding and stacking layer开始，接着并列连一个cross network和一个deep network。接着通过最后一个combination layer将两个network的输出进行组合。完整的DCN模型如图1所示。

图1: Deep & Cross Network

2.1 Embedding and Stacking Layer

输入数据带有sparse和dense feature。在大规模推荐系统的CTR预测中，输入几乎都是类别型特征（categorical features），比如：”country=usa”。这样的feature通常被编码成one-hot vectors，比如：”[0,1,0]”；然而，对于大的vocabularies，这通常会产生超高维度的特征空间。

为了减小该维度，我们使用一个embedding procedure来将这些二元features转换到关于真实值（real values）的dense vectors中（称为embedding vectors）。

\[x_{embed,i} = W_{embed,i} x_i\]

…(1)

其中\(x_{embed,i}\)是embedding vector，\(x_i\)是第i个category的二元输入，\(W_{embed,i} \in R^{n_e \times n_v}\)是对应的embedding matrix，会与网络中的其它参数一起进行优化，\(n_e, n_v\)分别是embedding size和vocabulary size。

最后，我们将embedding vectors，以及归一化稠密特征（normalized dense features）\(x_{dense}\)进行stack成一个vector：

\[x_0 = [ x_{embed,1}^T, ..., X_{embed,k}^T, X_{dense}^T]\]

…(2)

2.2 Cross Network

新的cross network的核心思想是，将显式特征（explicit feature）以一种有效方式进行交叉。cross network由多个cross layers组成，每一个layer具有以下的公式：

\[x_{l+1} = x_0 x_l^T w_l + b_l + x_l = f(x_l, w_l, b_l) + x_l\]

…(3)

其中:

• \(x_l, x_{l+1}\)是列向量（column vectors），分别表示来自第l层和第(l+1)层cross layers的输出；
• \(w_l, b_l \in R^d\)是第l层layer的weight和bias参数。

在完成一个特征交叉f后，每个cross layer会将它的输入加回去，对应的mapping function f：\(R^d \rightarrow R^d\)，刚好等于残差\(x_{l+1} - x_l\)。一个cross layer的可视化如图2所示。

图2: 一个cross layer的visualization

特征的高阶交叉（high-degree interaction）：cross network的独特结构使得交叉特征的阶（the degress of cross features）随着layer的深度而增长。对于第l层layer，它的最高多项式阶（在输入\(x_0\)上）是\(l+1\). 实际上，cross network由这些交叉项\(x_1^{\alpha_1} x_2^{\alpha_2} ... x_d^{\alpha_d}\)组成，对应的阶从1到l+1. 详见第3节。

复杂度分析：假设\(L_c\)表示cross layers的数目，d表示输入维度。那么，在该cross network中涉及的参数数目为：

\[d \times L_c \times 2\]

一个cross network的时间和空间复杂度对于输入维度是线性关系。因而，比起它的deep部分，一个cross network引入的复杂度微不足道，DCN的整体复杂度与传统的DNN在同一水平线上。如此高效（efficiency）是受益于\(x_0 x_l^T\)的rank-one特性，它可以使我们生成所有的交叉项，无需计算或存储整个matrix。

cross network的参数数目少，从而限制了模型的能力（capacity）。为了捕获高阶非线性交叉，我们平行引入了一个deep network。

2.3 Deep Network

Deep network是一个fully-connected feed-forward神经网络，每个deep layer具有以下的公式：

\[h_{l+1} = f(W_l h_l + b_l)\]

…(4)

其中：

• \(h_l \in R^{n_l}, h_{l+1} \in R^{n_{l+1}}\)分别是第l层和第(l+1)层hidden layer；
• \(W_l \in R^{n_{l+1} \times n_l}, b_l \in R^{n_{l+1}}\)是第l个deep layer的参数；
• \(f(\cdot)\)是ReLU function。

复杂度分析：出于简洁性，我们假设所有的deep layers具有相同的size。假设\(L_d\)表示deep layers的数目，m表示deep layer的size。那么，在该deep network中的参数的数目为：

\[d \times m + m + (m^2 + m) \times (L_d - 1)\]

2.4 Combination Layer

Combination Layer将两个network的输出进行拼接（concatenate），然后将该拼接向量（concatenated vector）feed 进一个标准的logits layer上。

下面是一个二分类问题的公式：

\[p = \sigma ( [x_{L_1}^T, h_{L_2}^T] w_{logits})\]

…(5)

其中:

• \(x_{L_1} \in R^d, h_{L_2} \in R^m\)分别是来自cross network和deep network的输出
• \(W_{logits} \in R^{d+m}\)是combination layer的weight vector，其中\(\sigma(x) = 1/(1+exp(-x))\)。

loss function是logloss，带有一个正则项。

\[loss = - \frac{1}{N} \sum_{i=1}^{N} y_i log(p_i) + (1-y_i) log(1-p_i) + \lambda \sum_{l} \| w_l \|^2\]

…(6)

其中 \(p_i\)是等式(5)计算得到的probabilities，\(y_i\)是true labels，N是输入的总数，\(\lambda\)是\(L_2\)正则项参数。

我们对两个network进行jointly train，在训练期间，每个独立的network会察觉到另一个。

3.Cross Network分析

在这一节，我们分析了DCN的cross network，以便于更有效地理解。我们提供了三个视角：多项式近似，泛化到FM，有效投影。为了简洁，我们假设：\(b_i = 0\)

概念：假设在\(w_j\)中的第i个元素是\(w_j^{(i)}\)。对于多索引（multi-index） \(\alpha = [\alpha_1, ..., \alpha_d] \in N^d\)，以及\(x = [x_1, ..., x_d] \in R^d\)，我们定义了：\(\| \alpha \| = \sum_{i+1}^d \alpha_i\)。

术语：交叉项\(x_1^{\alpha_1} x_2^{\alpha_2} ... x_d^{\alpha_d}\)的阶（degree）由\(\|\alpha\|\)定义。一个多项式的阶由它的项的最高阶决定。

3.1 多项式近似

根据维尔斯特拉斯逼近定理（Weierstrass approximation theorem），任意满足特定平滑假设条件下的函数，可以通过一个多项式进行逼近到一个特定的精度上。因而，我们从多项式近似的角度分析了cross network。特别的，cross network会以一种高效的、有表现力的、能更好地对现实世界数据集进行泛化的方式，近似相同阶的多项式类。

我们详细研究了一个cross network，将它近似成相同阶的多项式类（polynomial class）。假定\(P_n(x)\)表示n阶的多元多项式类（multivariate polynomial class）：

\[P_n(x)= \{ \sum_{\alpha} w_{\alpha} x_1^{\alpha_1} x_2^{\alpha_2} ... x_d^{\alpha_d} | 0 \le |\alpha| \le n, \alpha \in N^d \}\]

…(7)

在该类中的每个多项式具有\(O(d^n)\)个系数。只有\(O(d)\)个参数，cross network包含了在相同阶的多项式中的所有交叉项，每一项的系数与其它项各不相同。

理论 3.1: 一个l-layer的cross network，具有i+1个layer，定义成：\(x_{i+1} = x_0 x_i^T w_i + x_i\)。假设网络的输入是\(x_0 = [x_1, x_2, ..., x_d]^T\)，输出是\(g_l(x_0) = x_l^T w_l\)，参数是\(w_i, b_i \in R^d\)。接着，多元多项式\(g_l(x_0)\)会以下面的类进行重现（reproduce）：

\[\{ \sum_{\alpha} (w_0,...,w_l) x_1^{\alpha_1} x_2^{\alpha_2} ... x_d^{\alpha_d} | 0 \le |\alpha| \le l+1, \alpha \in N^d \}\]

其中：

• 其中 \(c_\alpha = M_\alpha \sum_{i \in B_\alpha} \sum_{j \in P_\alpha} \prod_{k=1}^{|\alpha|} w_{i_k}^{j_k}\), \(M_\alpha\)是一个与\(w_i\)独立的常数
• \(i = [i_1, ..., i_{|\alpha|}]\)和 \(j = [j_1, ..., j_{|\alpha|}]\)是多元索引（multi-indices）， \(B_{\alpha} = \{ y \in \{ 0, 1,...,l\}^{|\alpha |} | y_i < y_j \wedge y_{|\alpha|} = l \}\)，
• \(P_\alpha\)是indice \((\underbrace{1, ..., 1}_{\alpha_1 times} ... \underbrace{d, ..., d}_{\alpha_d times})\)的所有排列（permutations）的集合。

定理3.1的理论证明详见paper中的附录。举个例子，\(x_1 x_2 x_3\)的系数\(c_\alpha\)，其中\(\alpha = (1,1,1,0,...,0)\)。直到一些常数，其中\(l = 2, c_\alpha = \sum_{i,j,k \in P_\alpha} w_0^{(i)} w_1^{(j)} w_2^{(k)}\)；其中\(l=3, c_\alpha = \sum_{i,j,k \in P_\alpha} w_0^{(i)} w_1^{(j)} w_3^{(k)} + w_0^{(i)} w_2^{(j)} w_3^{(k)} + w_1^{(i)} w_2^{(j)} w_3^{(k)}\)

3.2 FM的泛化

cross network共享参数，类似于FM模型的参数共享，并扩展到了一个更深的结构上。

在FM模型中，特征\(x_i\)与一个 weight vector \(v_i\)相关联，交叉项\(x_i x_j\)的权重通过 \(<v_i, v_j>\)计算得到。在DCN中，\(x_i\)与标量\(\{ w_k^{(i)} \}_{k=1}^{l}\)有关，\(x_i x_j\)的权重是集合\(\{ w_k^{(i)}\}_{k=0}^l\)和\(\{ w_k^{(j)}\}_{k=0}^{l}\)的参数乘积。两种模型都会为每个特征学到一些与其它特征相互独立的参数，交叉项的权重是相应参数的一种特定组合。

参数共享（parameter sharing）不权使得模型更有效，也使模型可以泛化到未见过的特征交叉上，对噪声更健壮。例如，使用sparse features的数据集。如果两个二元特征\(x_i\)和\(x_j\)很少或者几乎从未在训练集中共现过，假设，\(x_i \ne 0 \wedge x_j \ne 0\)，接着，学到关于\(x_i x_j\)的权重不会带有对预测有意义的信息。

FM是一个浅层结构（shallow structure），受限于交叉项的阶是2. 而DCN可以构建所有的交叉项\(x_1^{\alpha_1} x_2^{\alpha_2} ... x_d^{\alpha_d}\)，其中阶 \(|\alpha|\)由一些常数决定，见理论3.1。因而，cross network扩展了参数共享的思想，将单个layer扩展到多个layer，并且有更高阶的交叉项。注意，与高阶FM不同的是，在cross network中的参数数目，只随着输入维度线性增长。

3.3 有效投影

每个cross layer会以一种有效方式，将在\(x_0\)和\(x_l\)间的所有pairwise交叉进行投影到输入维度上。

考虑到\(\tilde{x} \in R^d\)是一个cross layer的输入。cross layer首先隐式构建了\(d^2\)个关于\(x_i \tilde{x}_j\)的pairwise交叉，接着以一种内存高效的方式，隐式地将它们投影到维度d上。这种直接的方式会带来3次方开销。

我们的cross layer提供了一种有效的解决方式，将开销减小到维度d的线性开销上。考虑\(x_p = x_0 \tilde{x}^T w\)。事实上等于：

\[x_p^T = [x_1\tilde{x}_1 ... x_1\tilde{x}_d ... x_d\tilde{x}_1 ... x_d\tilde{x}_d] \left[ \begin{array}{ccc} w&0&...&0\\ 0&w&...&0\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&...&w \end{array} \right]\]

…(8)

其中，row vectors包含了所有\(d^2\) 个 \(x_i \tilde{x}_j\)的pairwise交叉，投影矩阵具有一个块对角化结构，其中：\(w \in R^d\)是一个列向量。

4.实验结果

在本节中，我们评估了CDN在多个数据集上的效果。

4.1 Criteo Display Ads数据集

Criteo Display Ads数据集用于预测点击率。具有13个integer features和26个categorial features。其中，每个category都具有一个很高的维度基数。对于该数据集，在logloss上提升0.001可以看成是巨大的提升。当考虑到在一个很大的用户基数时，在预测准确率（prediction accuracy）的一个小的提升，可以为公司带到来一个大的回报。数据包含了11GB的包含7天的用户日志（~41000,000条记录）。我们使用前6天的数据做为训练，并将第7天的数据随机划分成等size的validation和test set。

4.2 实现细节

DCN在tensorflow上实现，我们会讨论一些关于训练CDN的细节。

数据处理和embedding。实数型特征通过一个log转换进行归一化。对于类别型特征，会将这些特征嵌入到dense vectors中，维度为 \(6 \times (category \ cardinality) ^{1/4}\)。最后将所有的embedding结果拼接（concatenating）成一个维度为1026的向量。

优化(Optimization)：我们使用Adam optimizer，mini-batch进行随机优化。batch size=512. Batch normalization被应用于deep网络，gradient clip norm设置为100.

正则化：我们使用early stopping，我们未发现L2正则或dropout很有效。

超参数：我们基于一个grid search来在hidden layers的数目、size、初始learning rate以及cross layers的数目上进行探索。hidden layers的数目范围为2一5, hidden layers的数目从32到1024. 对于DCN，cross layers的数目从1到6.初始learning rate从0.0001依次递增调到0.001. 所有试验都使用early stopping，训练step为150000, 超过它可能会发生overfitting。

参考

https://arxiv.org/pdf/1708.05123.pdf