我们来看下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

我们来看下gravityR&D提出的《SESSION-BASED RECOMMENDATIONS WITH RECURRENT NEURAL NETWORKS》。

2.相关工作

2.1 session-based的推荐

推荐系统领域的大多数工作主要关注于建模：当提供一个用户id时，可以为它构建一个明确的user profile。在该setting中，相应的文献主要是MF方法和基于近邻的模型。这些方法可以在session-based recommendation中采用；当缺失user profile时，一个很自然的解决方案是：item-to-item推荐方法。在该setting中，会从提供的session数据中预计算好item-to-item的相似度矩阵，也就是说：经常在sessions中一起被点击的这些items，被认为是相似的。相似矩阵接着在session期间被简单用于：为一个当前用户所点击的项推荐最相似的items。该方法被证明是有效的，并被广泛使用。这些方法只能说明用户的最近点击行为，实际上忽略了过去点击的行为。

对于session-based推荐，一些不同的方法有：Markov决策过程（MDP: Markov Decision Processes）。MDP是顺序随机决策问题的模型。

一个MDP被定义成一个4元组 \(<S, A, Rwd, tr>\)，其中：

• S是状态集(state)
• A是动作集(action)
• Rwd是一个reward函数
• tr是状态转移函数

在推荐系统中，动作(action)等价于推荐，最简单的MPDs本质上是一阶Markov链，其中下一个推荐可以根据item间的转移概率被简单计算。在session-based推荐中使用Markov链的主要问题是：当尝试包含所有可能的用户选择序列时，状态空间很快变成不可管理。

通用因子分解框架（GFF: General Factorization Framework）的扩展版本可以使用session data进行推荐。它会通过将这些事件进行求和（sum）来建模一个session。它使用两种类型的隐表示：一种用于表示item自身，另一种用于将item表示成一个session的部分。session接着被表示成关于part-of-a-session的item表示的feature vectors的平均。然而，该方法不会考虑任何在session中的顺序。

2.2 Deep learning推荐

最近在神经网络文献中的一个相关方法，它使用受限波尔茨曼机（RBM）进行CF计算(Salakhutdinov et al., 2007)。在该工作中，一个RBM被用于建模user-item交互并执行推荐。该模型已经被证明是最好的CF模型之一。Deep模型已经被用于从非结构化内容中（比如：音乐、图片）抽取特征，接着被一起用于更通用的CF模型。在(Van den Oord et al.2013) 中，使用一个CNN来从音乐文件中抽取特征，接着被用在一个因子模型中（factor model）。最近(Wang et al.2015)引入了一个更通用的方法，它使用一个深度网络来从任意类型的items中抽取通用内容特征，这些特征接着被合并到一个标准的CF模型中来增强推荐效果。该方法看起来特别有用，尤其是在没有足够多的user-item交互信息时。

3.使用RNN的推荐

RNN可以建模变长序列数据。在RNN和传统前馈深度模型间的主要不同之处是，在构成网络的units中存在一个内部隐状态(hidden state)。标准RNN会更新它们的隐状态h，它使用以下的更新函数：

\[h_t = g(W x_t + U h_{t-1})\]

…(1)

其中:

• g是一个平滑边界函数（比如：使用一个logistic sigmoid函数）
• \(x_t\)是在时间t上unit的input
• 给定它的当前状态\(h_t\), 一个RNN会输出：关于该序列的下一个元素的一个概率分布

GRU是一个关于一个RNN unit的更精巧的模型。它的目标是，解决梯度消失问题(vanishing gradient problem)。GRU gate本质上会学习何时(when)以及多大（how much）进行更新unit的hidden state。GRU的activation是一个在之前activation和候选activation \(\hat{h_t}\)上的线性插值。

\[h_t = (1-z_t) h_{t-1} + z_t \hat{h}_t\]

…(2)

其中update gate为：

\[z_t = \sigma(W_z x_t + U_z h_{t-1})\]

…(3)

其中，cadidate activation函数\(\hat{h}_t\)以相似方法进行计算：

\[\hat{h}_t = tanh(W x_t + U(r_t \odot h_{t-1}))\]

…(4)

最后，reset gate的\(r_t\)为：

\[r_t = \sigma(W_r x_t + U_r h_{t-1})\]

…(5)

3.1 定制GRU模型

图1: 网络的通用结构。一次只处理事件流中的一个事件(event)

我们在我们的模型中使用GRU-based RNN来进行session-based推荐。网络的输入是该session的实际状态(state)，而输出为在session中item的下一个事件（event）。到目前为止，该session的state可以是item的实际event或在session中的events。在前面的case中使用1-of-N的编码，例如，输出向量的长度实际为items数目，只有在对应于实际item的位置上为1，其它为0。后面的setting中会使用一个关于这些表示（representations）的加权和，如果events在更早前发生，那么它会降权（discounted）。出于稳定，输出向量接着会被归一化（normalized）。我们期望这会有帮助，因为它增强了记忆效应（memory effect）：而非常局部顺序限制(very local ordering constraints)的增强则并不能被RNN的更长期记忆所捕获。我们也实验了其它方法： 通过增加一个额外的embedding layer，但1-of-N encoding的效果更好。

该网络的核心是：GRU layer(s)、以及额外的feed-forward layers（可以在最后一层和output间进行添加）。输出为items的预测偏好，例如，在session中对于每个item成为下一个被推荐的似然。当使用多个GRU layers时，前一layer的hidden state是下一layer的input。该input也可以可选地被连接到在网络中更深的GRU layers上，我们发现这确实能提升性能。整体架构如图1所示，它描述了单个event在events时间序列中的表示（representation）。

由于推荐系统并不是RNN的主要应用领域，我们修改了基础网络让它更好地适合推荐任务。我们也考虑到实际点以便我们的解决方案可以应用到一个现实环境上。

3.1.1 session-parallel mini-batches

NLP任务中的RNN通常使用in-sequence mini-batches。例如，很常用的是使用一个slide window来滑过句子中的词，并将这些window化的片段相互挨着来构成mini-batches。这种方法对于我们的任务来说不合适，因为：

• (1) sessions的长度可能非常不同，甚至比句子还要更不同：一些sessions可能只有2个events，而其它可能有上百个；
• (2) 我们的目标是，捕获一个session在时序上的演进，因此将它们分割成片段可能会没有意义

因此，我们使用session-parallel mini-batches。首先，我们为该sessions创建一个顺序（order）。接着，我们使用前X个sessions的第一个event来形成首个mini-batch的input（期望的output为我们的active sessions的第二个events）。第二个mini-batch会从第二个events来生成，自此类推。如果sessions的任意一个结束，下一个可提供的session会补上它的位置。Sessions被认为是相互独立的，因此，当该切换发生时，我们会重置（reset）合适的hidden state。如图2所示。

图2: session-parallel mini-batch creation

3.1.2 在output上进行sampling

当items数目很大时，推荐系统特别有用。对于一个中级规模（medium-sized）的网上商店来说，它的items范围可能是成千上万，但对于一个更大网络来说，可能有上百万items。在每一step为每个item计算一个score，会让算法与items数和events数的乘积成比例增长。这在实际上是不可行的。因此，我们必须对output进行抽样，只对items某个子集计算score。这也只有一些权重会被更新。除了期望的output之外，我们需要为一些负样本计算scores，并修改权重以便期望的output的排序更靠前。

对于一个任意missing event的天然解释是，用户不知道该item的存在，因而没有任何交互。然而，如果某用户不知道该item并选择不与之交互，是因为她不喜欢（dislike）该item，这种情况的概率很低。item越流行，用户越可能知道它，因此一个missing event更可能会传达dislike的意味。因此，我们应根据它们的流行度成比例抽样。我们并不会为每个训练样本（training example）生成独立(separate)的抽样（samples），而是选择：使用从该mini-batch中的其它训练样本的items来当成负样本。该方法的好处是，我们可以通过跳过抽样（sampling）来进一步减小计算时间。另外，这也可以从实现侧受益，可以让该代码更简单些，以便进行更快的矩阵操作。同时，该操作也是一个基于流行度的抽样（popularity-based sampling），因为一个item成为该mini-batch中的其它训练样本的似然概率（likelihood），与它的流行度成正比。

3.1.3 ranking loss

推荐系统的核心是items的相关度排序（relevance-based）。尽管该任务可以被解释成一个分类任务，l2r方法通常要好于其它方法。ranking可以是pointwise，pairwise和listwise。pointwise ranking会独立的估计items的score或者rank，它的loss定义的目的是相关items的rank应较小(low)。pairwise ranking会比较一个positive和一个negative item pairs的score或rank，该loss会增强：positive item的rank应低于negative item的rank。Listwise ranking使用所有items的scores和ranks，并比较它们的顺序。由于它包含了排序（sorting），通常计算开销更大，并不常使用。同时，如果只有一个相关item（例如：在我们的case中）——listwise ranking可以通过pairwise ranking进行解决。

我们在我们的解决方案中包含了一些pointwise和pairwise ranking losses。我们发现，pointwise ranking对于网络不是稳定的（见第4节）。pairwise ranking losses在其它方法更胜一筹。我们使用以下的两个：

• BPR：Bayesian Personalized Ranking (Randle et al., 2009)是一个矩阵因子方法，它使用pairwise ranking loss。它会比较一个positive和一个sampled negative item的score。这里，我们比较了positive item与一些sampled items的scores，并使用它们的平均作为loss。在一个session中对于某个结定点的该loss定义如下：

\[L_s = - \frac{1}{N_s} \cdot \sum\limits_{j=1}^{N_s} log(\sigma(\hat{r}_{s,i} - \hat{r}_{s,j}))\]

其中，\(N_s\)是sample size，\(\hat{r}_{s,k}\)是在item k上在该session的给定点的score，i是期望的item（在session中下一item），j是负样本（negative samples）。

• TOP1: 该ranking loss由我们提出。它是关于相关项的相对rank的正则近似。相关item的相对rank由\(\frac{1}{N_s} \cdot \sum\limits_{j=1}^{N_s} I\lbrace \hat{r}_{s,j} > \hat{r}_{s,i} \rbrace\)给定。我们使用一个sigmoid来近似\(I\lbrace \cdot \rbrace\)。这的最优化可以修改参数，以便i的score能高些。然而，这是不稳定的，因为特定positive items也扮演着负样本的角色，因为scores趋向于变得增长更高。为了避免这种情况，我们希望强制负样本的scores在零周围。这是对negative items的scores的一种自然期望。因而，我们添加到一个正则项到该loss中。很重要的是，在相同范围内的该term作为相对rank很重要，。最终的loss function如下所示：

\[L_s = \frac{1}{N_s} \cdot \sum\limits_{j=1}^{N_s} \sigma(\hat{r}_{s,j} - \hat{r}_{s,i}) + \sigma(\hat{r}_{s,j}^2)\]

4.实验

我们在两个数据集上，对rnn与其它流行的baslines进和对比。

第一个数据集是RecSys Challenge 2015. 该数据集包含了一个商业网站的click-streams，有时以购买事件结尾。我们会使用该比赛的trainset，只保留点击事件。我们过滤掉了长度为1的session。该网络使用〜6个月的数据进行训练，包含了7,966,257 sessions，在37,483个items上的31,637,239 clicks。我们使用后续天的sessions进行testing。每个session被分配给trainset或testset两者之一。由于CF方法的天性，我们会从testset中过滤出那些item点击并不在trainset中的点击。长度为1的Session也会从testset中移除。在预处理后，对于testset，我们留下了大约15324个session，它具有71222个events。该数据集被称为RSC15.

第二个数据集从Youtube-like OTT视频服务平台上收集。我们收集了在一段时间内关于观看vidio的events。只有特定范围会被归到该collection中：最近2个月。在这段时间内，每个视频后的屏幕左侧会提供item-to-item的推荐。这些items由不同算法选择得到，它们受用户行为的影响。预处理阶段与其它数据集相似，会过滤非常长的sessions，因为它们可能由机器生成。训练数据包含了所有，上述周期的最后一天。具有300w的sessions，具有在33w视频上的13w的watch events。testset包含了之前提的，具有~3.7w的sessions，~18w的watch events。该数据集被称为“VIDEO”。

评估（evaluation）通过挨个提供一个session的events，并确认下一event中该item的rank来完成。GRU的hidden state在一个session完成后会被重置为0. items通过它们的score以降序排序，在该list中它们的位置就是它们的rank。对于RSC15数据集, trainset中所有37483个items会被排序。然而，这对于VIDEO数据集是不现实的，因为items的数目很大。这里我们会对期望的item vs. 最流行的30000 items进行排序。这对于evaluation会有很小的影响，很少被访问的items经常获得较低分数。同时，基于流行度的预过滤在实际的推荐系统中很常见。

由于推荐系统一次只会推荐很少的items，一个用户可能选取的实际item应与在列表中的头几个items之中。因此，我们主要的评估指标是recall@20，也就是说，在所有test cases中，所期望item在top20之内的cases的比例。recall不考虑item的实际rank，只需要topN之内即可。这会建模实际场景，其中没有强调推荐，不关心绝对顺序。recall也通常与重要的online KPIs(比如：CTR)相关。第二个在实验中使用的metric是MRR@20 (Mean Reciprocal Rank)。这是关于所期望items的相互排序（reciprocal ranks）的平均。如果该rank超过20, 则reciprocal rank被置为0. MRR会解释该item的rank，在推荐顺序比较关注的情况下，这指标是重要的。（例如：低rank的items只会在滑动后可见）

4.1 Baselines

我们比较了该网络与一些其它baselines。

• POP： 流行度预测，总是推荐训练集中最流行的items。它通常在特定领域内是一个较强的baseline。
• S-POP：该baseline会推荐当前session的最流行items。推荐列表会在session期间随着items获得更多events而进行变化。使用全局流行度值可以突破束缚。该baseline在该领域很强，有较高的重复性。
• Item-KNN：与实际item相似的Item可以通过该baseline被推荐，相似度的定义通过他们sessions向量间的cosine相似度来定义，例如：在sessions中两个items的共现次数，除以各自单个items出现所在的sessions数目的乘积的平方根。可以进行正则化，避免较少访问items的高相似度。该baseline是在实际系统中最常用的item-to-item解决方案，它提供给推荐系统这样的setting：观看了该item的其它人也会观看这些item。尽管它很简单，但它通常是一个较强的baseline。
• BPR-MF：BPR-MF是一个常用的MF方法。它会为一个pairwise ranking目标函数通过SGD进行最优化。矩阵分解不能直接应用到session-based推荐上，因为新的sessions不会具有预计算好的特征向量。然而，我们可以通过使用在session中出现过的item的feature vectors的平均向量来克服这个问题。换句话说，在一个可推荐item和session的items间的特征向量的相似度进行求平均。

参考

https://arxiv.org/pdf/1511.06939.pdf

我们来看下lightgbm的paper：《LightGBM: A Highly Efficient Gradient Boosting Decision Tree》。

1.

GBDT是流行的机器学习算法，只有少量的高效实现，比如：XGBoost和pGBRT。尽管在这些实现中采用了许多工程优化，但当特征维度很高、数据size很大时，其效率和可扩展性仍不能令人满意。其中一个主要原因是，对于每个特征，他们需要扫描所有数据样本来估计所有可能划分点的信息增益（information gain），这是非常耗时的。为了解决该问题，我们提供了两个新技术：基于梯度的单边采样（GOSS: Gradient-based One-Side Sampling）、独有特征打包（EFB: Exclusive Feature Bundling）。有了GOSS，我们可以使用小梯度来排除大量的样本，只使用剩余部分来估计信息增益。我们通过证明，由于更大梯度的数据样本，通常在计算信息增益时扮演更重要角色，GOSS使用更小的data size即可以获得相当精准的关于信息增益的估计。有了EFB，我们可以将多个独有特征（比如：他们很少会同时采用非零值）进行打包，以减小特征数。我们证明了，发现最优的独有特征bundling是一个NP-hard问题，但一个贪心算法可以达到相当好的近似（这样可以有效减少特征数，同时不伤害split点决策的accuracy）。我们将这种带GOSS和EFB机制的GBDT称为LightGBM。我们的实现在多个公共数据集上做了实验，LightGBM可以加速常用的GBDT训练过程达20倍，而几乎保持相同的accuracy。

1.介绍

由于高效，精准，可解释性强，GBDT被广泛使用。GBDT在许多机器学习任务上都达到了state-of-art的效果。最近几年，随机大数据的出现，GBDT面临着新挑战，尤其是在accuracy和efficiency的权衡上。GBDT的常见实现，需要对每个特征进行扫描所有数据样本来估计所有可能划分点的信息增益。因此，他们的计算复杂度与特征数、以及样本数成比例。这使得这些实现在处理大数据时非常耗时。

为了解决该挑战，一个简单的想法是，减少数据样本数、以及特征数。然而，这被证明是非常有意义（non-trivial）的。例如，如何为GBDT执行数据采样是不明确的。有一些工作开展会根据它们的权重来采样数据，以加速boosting的训练过程[5,6,7]。但它们不能直接被应用在GBDT中，因为在GBDT中根本没有抽样权重(sample weight)。为此，我们提出了两种新技术。

GOSS。在GBDT中对于数据样本没有原始权重（native weight），我们注意到不同梯度的数据样本在计算信息增益时扮演着不同的角色。特别的，根据信息增益的定义，这些带着更大梯度的（例如：under-trained样本实例）样本实例会在计算信息增益时贡献更多。因此，当对这些数据样本做下采样(down-sampling)时，为了保持信息增益的accuracy，我们最好保留这些带有大梯度的样本（例如：比一个预定义阀值要更大，或者在top百分比间），并只随机drop掉那些小梯度的样本实例。我们证明了，这样的处理比均匀随机抽样（uniformly random sampling）可以产生更精准的增益估计，特别是当信息增益的值具有具有较大范围时。

EFB。在真实应用中，尽管具有大量特征数，但特征空间相当稀疏，这提供给我们一个设计一个几乎无损的方法的可能性，来减小有效特征数。特别的，在一个稀疏特征空间中，许多特征是（几乎）独有的，例如，他们很小同时采用非零值。这些样本包含了one-hot特征（例如：文本挖掘中的one-hot词表示）。我们可以很安全地对这些独有特征进行捆绑（bundle）。q我们设计了一个高效算法，它通过会将最优bundling问题缩减到一个图着色问题（graph coloring problem：通过将特征看成是顶点，如果每两个特征间相互排斥就添加一条边），通过一个常数近似率的贪心算法来解决该问题。

我们将这个带有GOSS和EFB的新GBDT算法称为LightGBM。

2.前提条件

2.1 GBDT和它的复杂度分析

GBDT是一个关于决策树的ensemble模型，它会顺序式进行训练。在每轮迭代中，GBDT会通过拟合负梯度（被称为：残差 residual errors）来学习决策树。

GBDT的主要开销在学习决策树中，学习决策树时最耗时的部分，是发现最佳的分割点（split points）。一种最流行的算法是，pre-sorted算法【8，9】，它会在pre-sorted特征值上枚举所有可能的分割点。另一种流行的算法是，histogram-based算法【10,11,12】，如算法1所示。histogram-based算法会将连续特征值进行分桶成(buckets)离散bins，并在训练期间使用这些bins来构建特征的histograms。由于histogram-based算法在内存消耗和训练速度上都更高效，我们基于它进行开发。

算法1､2:

如算法1所示，histogram-based算法会基于特征的histograms去发现最佳split points。它会花费O(#data x #feature)的时间复杂度来进行histogram building，以及花费O(#bin x #feature)来进行split point finding。由于#bin通常要比#data更小很多，histogram building会决定着计算复杂度。如果我们可以缩减#data数或者#feature数，我们将能够实质上加速GBDT的训练。

2.2 相关工作

在文献中有相当少的GBDT实现，包含XGBoost[13], pGBRT[14], scikit-learn[15], R的gbm[16]。sklearn和R-gbm实现使用的是presorted算法，而pGBRT实现了histogram-based算法。XGBoost支持两种实现（pre-sorted和histogram-based）。如[13]所示，XGBoost的效果要好于其它工作包。因而，我们使用XGBoost作为我们实验中的baseline。

为了缩减训练数据的size，常用的方法是对数据样本进行下采样。例如，在[5]中，如果数据样本的权重小于一个固定阀值，它们将会被过滤。SGB[20]会在每轮迭代中使用一个随机子集来训练弱学习器（weak learners）。在[6]中，抽样率在训练过程中会动态调整。然而，除了SGB外的所有其它工作都基于AdaBoost，不能直接应用于GBDT，因为它们对于在GBDT中的数据样本实例来说没有原始权重(native weights)。尽管SGB可以被用于GBDT，但它通常会降低accuracy，因而不是一个理想选择。

相同的，为了缩减特征数，很自然地会过滤弱特征[22,23,7,24]。这通常可以通过PCA或投影来完成。然而，这些方法高度依赖于：假设这些特征包含大量冗余，这在实践中并不总是成立（特征通常会根据它们的独特贡献被设计，移除任意之一都会在一定程序上影响训练的accuracy）。

在实际应用中的大规模数据集通常是相当稀疏的。GBDT会使用pre-sorted算法，通过忽略零值特征来缩减训练开销【13】。而histogram-based GBDT不会对稀疏优化解决方法有影响。原因是，histogram-based算法需要为每个数据样本检索特征的bin值（根据算法1），不管特征值是零或非零。我们更推荐histogram-based算法，它可以有效消除这样的稀疏特性。

为了解决之前的局限性，我们提出了两个新技术：GOSS、EFB。

3 GOSS

3.1 算法描述

在AdaBoost中，sample weight被当成是一个关于数据样本实例重要性的指示器（indicator）。然而，在GBDT中，不存在天然的sample weights，因而像AdaBoost提出的sampling方法不能直接用。幸运的是，我们注意到，对于在GBDT中的每个数据样本，它们的梯度可以为我们提供有用信息来进行数据抽样。也就是说，如果一个实例与一个小梯度有关，该样本的training error很小，并已经过良好训练。一个简单的想法是，抛弃这些小梯度的数据样本。然而，这样做可能会改变数据分布，进而伤害所学模型的accuracy。为了避免该问题，我们提出了一个新方法称为：GOSS。

GOSS会保留所有带大梯度的样本，并在小梯度样本上进行随机抽样。为了对数据分布的影响进行补偿，当计算信息增益时，GOSS会为带小梯度的数据样本引入一个常数乘子（见算法2）。特别的，GOSS首先会根据它们梯度的绝对值来对数据样本进行排序，接着选取top a x 100%的样本。接着它会从其余数据中随机抽样 b x 100%的样本。最后，当计算信息增益时，GOSS会通过一个常数\(\frac{1-a}{b}\)对小度数抽样数据进行放大。通过该方法，我们可以更关注under-trained样本实例，而不需要过多更改原始数据分布。

算法2:

3.2 理论分析

GBDT使用决策树来学习从输入空间\(X^s\)到梯度空间\(\mathcal{G}\)的函数。假设，我们具有一个训练集\({x_1,...,x_n}\)，n独立同分布(i.i.d.)，其中每个\(x_i\)是一个在空间\(X^s\)上的s维向量。在gradient boosting的每轮迭代中，关于loss函数的负梯度会根据模型的输出被表示为\({g_1, ..., g_n}\)。决策树模型会在最具信息量的特征上分割每个节点（使用最大信息增益）。对于GBDT，信息增益通常会通过在进行分割之后的variance来进行衡量，如下定义。

定义 3.1: 假设O是在决策树的一个确定节点上的训练数据集。在该节点上，分割特征j在点d中的variance gain，定义如下：

\[V_{j|O}(d) = \frac{1}{n_O}()\]

其中，。

定理 3.2

4. EFB

在本部分，我们提出了一种新方法来有效缩减特征数。

算法3,4

高维数据通常非常稀疏。特征空间的稀疏性提供我们一个可能性来设计近科目无损的方法来缩减特征数。特别的，在一个稀疏特征空间中，许多特征相互排斥，例如，他们不会同时采用非零值。我们可以安全地将这些相互排斥的特征打包成单个特征（我们称之为一个“exclusive feature bundle”）。通过一个精心设计的特征扫描算法，我们可以从feature bundles中构建相同的feature histograms来作为从单个特征中计算的histograms。在这种方法中，histogram building的复杂度可以从O(#data x #feature)变为O(#data x #bundle)，其中，#bundle « #feature。接着，我们可以在对accuracy无伤的情况下极大加速GBDT的训练。接着，我们会详细展示是如何得到的。

有两个要点要解决。第一个是，决定哪些特征应一起进行加包。第二个是如何构建bundle。

定理 4.1：将特征划分为更小数目的exclusive bundles问题是一个NP-hard问题。

证明：我们会将图着色问题（graph coloring problem）应用到我们的问题上。由于图着色问题是NP-hard的，我们可以推导我们的推论。

给定关于图着色问题的任意样本 \(G = (V,E)\)。我们以如下方式构建一个样本实例。采用关联矩阵G的每一行作为一个feature，接着使用\(\mid V \mid\)个特征来获取一个instance。很容易看到，在我们的问题中，特征的一个exclusive bundle对应于相同颜色的一个顶点集，反之即然。

对于第1个要点，定理4.1证明了：发现最优的bundling策略是一个NP-hard问题。这意味着，在多项式时间内发现一个准确的解是不可能的。为了发现一个好的近似算法，我们首先将optimal bundling问题精减为图着色问题。通过将特征看成是顶点、如果两两特征不相互排斥则在上面添加边。我们使用一个贪心算法来为图着色生成bundles来生成合理的好结果（具有一个常数近似几率）。接着，我们注意到，通常有相当少的特征，尽管它们并不是100%相互排斥的，很少同时采用非零值。如果我们的算法可以允许一定比例的冲突，我们可以获得一个更小数目的feature bundles，并进一步提升计算效率。通过简单计算，随机污染一定比例的特征值会影响训练accuracy，最多达到\(O([(1-\gamma)n]^{-2/3})\)，其中\(\gamma\)是在每个bundle中的最大冲突然袭击。因此，如果我们选择一个相对小的\(\gamma\)，我们会在accuracy和efficiency上达到较好的平衡。

其于上述讨论，我们为exclusive feature bundling设计了一个算法来，如算法3所示。首先，我们使用一个带权重边来构建一个graph，它们有weights以应于特征间的总冲突。第二，我们通过在图中的度对特征进行降序排序。最后，我们在有序列表中确认每个特征，接着给它们分配一个已存在具有较小冲突的bundle（通过\(\gamma\)控制），或者创建一个新bundle。算法3的时间复杂度是\(O(#feature^2)\)，它在训练前仅会处理一次。当特征数不是非常大时，该复杂度是可接受的，但如果有数百万特征时仍会有问题。为了进一步提升效率，我们提出一种更有效的排序策略(ordering strategy)，无需构建graph：通过非零值的数目排序，这与通过degree的方式排序相似，因为更多非零值通常会产生更高的冲突率。由于我们只会更改算法3的排序策略，新算法的细节会被忽略以免重复。

对于第二个要点，我们需要一种好方法来将相同bundle中的features合并，以便能缩减相应训练复杂度。关键点是确认原始特征值可以从feature bundles中被确认。由于histogram-based算法会存储离散bins，而非特征的连续值，我们可以通过让排斥特征(exclusive features)落在不同的bins上。这可以通过添加offsets到特征的原始值中来完成。例如，假设我们在一个feature bundle中有两个features。最初，feature A的取值为[0, 10)，feature B的取值为[0, 20)。我们接着添加一个offsets为10到feature B中，以便重定义的features取值为[10,30)。这之后，可以安全地合并features A和B，并使用一个范围为[0,30)的feature bundle来替换原始的features A和B。详细情况见算法4.

EFB算法可以将多个排斥特征bundle到更少的dense features上，它可以有效避免不必要的零特征值计算。实际上，我们也可以优化最基本的histogram-based算法，通过为每个特征使用一个表来记录非零值数据来忽略零值。通过扫描该表的数据，对于一个特征，histogram building的开销会从O(#data)变更为O(#non zero data)。然而，该方法需要额外的内存和计算开销来维持这些在整个树增长过程中的per-feature tables。我们在LightGBM中将该优化实现作为一个基本功能。注意，该最优化不会与EFB冲突，因为在当bundles很稀疏时，我们仍可以使用它。

5.实验

本部分，我们会展示实验结果。我们使用了5个不同公共数据集。这些数据集如表1所示。其中，Microsoft Learning to Rank [LETOR]数据集包含了30K的网络搜索queries。该数据集所用的features大多数是dense numerical features。Allstate Insurance Claim数据集和Flight Delay数据集都包含了许多one-hot coding features。最后两个数据集来自于KDD CUP 2010和KDD CUP 2012. 我们直接使用来自NTU的获胜方案的features，它包含了dense和sparse features，这两个数据集都非常大。我们可以使用它们来直接测试算法。

表1

我们的实验环境是Linux server，它具有两个E5-2670 v3 CPUs(共24个核)以及256GB内存。所有实验都在多线程上运行，线程数固定在16个上。

5.1 总体比较

我们在下面提出了总的比较。XGBoost和没有GOSS和EFB的LightGBM(称为lgb_baseline)被用于baselines。对于XGBoost，我们使用两个版本，xgb_exa(pre-sorted算法)和xgb_his（histogram-based算法）。对于xgb_his，lgb_baseline，以及LightGBM，我们使用leaf-wise的树增长策略。对于xgb_exa，由于它只支持layer-wise的增长策略，我们为xgb_exa调整参数，以便让它像其它方法一样增长相似的树。接着，我们朝着在speed和accuracy间更好平衡的方向，为所有数据集调参。我们为Allstate，KDD10和KDD12设置a = 0.05, b=0.05, 为Flight Delay和LEFTOR设置a=0.1, b=0.5. 我们EFB中设置\(\gamma=0\)。所有算法会运行固定迭代次数，我们从该迭代中使用最好的score来获取accuracy结果。

表2

训练时间和测试accuracy在表2和表3中。从这些结果看，我们可以看到LightGBM是最快的，并且几乎与baselines维持着相同的accuracy。xgb_exa是基于pre-sorted算法的，它会比histogram-based算法要慢很多。通过比较lgb_baseline，LightGBM在AllState、Flight Delay、LETOR、KDD10和KDD12数据集上要快21x，6x，1.6x，14x和13x。由于xgb_his相当耗费内存，它在KDD10和KDD12数据集上不能成功运行，会out-of-memory。在其它数据集上，LightGBM会更快，直到在Allstate数据集上能达到9x加速。 加速的计算是通过每轮迭代的训练时间计算得到的，是由于所有算法会在相同迭代数上收敛。为了演示总的训练过程，我们展示各自在图1和图2上，基于wall clock time的训练曲线。

表3:

在所有数据集上，LightGBM可以达到几乎相同的test accuracy作为baselines。这意味着GOSS和EFB在带来大的加速时并不会伤害accuracy。这与第3.2节和第4节的理论分析相一致。

5.2 GOSS分析

首先，我们研究了GOSS的加速能力。从表2中LightGBM和EFB_only的比较来看，我们可以通过使用10%-20%的数据，看到GOSS可以带来接近2x的加速。GOSS可以只使用抽样数据就可以学到trees。然而，它会在整个数据集上保留一些计算，比如：指导预测和计算梯度。这样，我们就可以发现，整个加速与抽样数据的比例是非线性相关的。然而，由GOSS带来的加速仍非常大，该技术可以应用到不同数据集上。

第二，通过比较随机梯度增强（SGB：Stochastic Gradient Boosting），我们评估了GOSS的accuracy。不失一般性，我们使用LETOR数据集进行测试。我们通过选择在GOSS中不同的a和b来调参抽样比例，并为SGB使用相同的整体抽样比例。我们通过使用early stopping来运行这些settings直到收敛。结果如表4所示。我们可以看到，当使用相同的抽样比例（sampling ratio）时，GOSS的accuracy总是好于SGB。这些结果与在3.2节中讨论一致。所有实验演示了GOSS是一个比stochastic sampling更高效的sampling方法。

表4:

5.3 EFB分析

通过比较lgb_baseline和EFB_only，我们确认了EFB对于加速的贡献。结果如表2所示。这里，我们不允许在bundle finding process(例如：\(\gamma=0\))中有冲突。我们发现EFB可以帮助达到在这些大规模数据集上更大的加速。

注意，lgb_baseline对于稀疏特征有优化，EFB可以通过一个较大因子达到训练加速。由于EFB会将许多稀疏特征（one-hot features和隐式exclusive features）合并到更少的特征中。然而，EFB在维持非零数据表上，对于在树学习过程中的每个特征，不会有额外开销。再者，由于许多之前孤立的特征会捆绑到一起，它可以增加spatial locality，并极大提升cache hit rate。因此，在效率上的整体提升是显著的。有以上分析后，EFB是一个非常有效的算法，可以利用在histogram-based算法上的sparse特性，它可以为GBDT训练过程带来一个极大加速。

参考

https://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree.pdf

我们来看下standford的Aditya Grover的《node2vec: Scalable Feature Learning for Networks》。

1.介绍

node2vec是一种半监督算法，用于在网络中的可扩展特征学习。受之前NLP中工作[21]的启发，我们会使用SGD对一个定制的基于图的（graph-based）目标函数进行优化。直觉上，该方法会返回特征表示，对于在d维空间内的节点，会对它们的网络邻节点的似然进行最大化。我们使用2-order的随机游走来为顶点生成（抽样）网络邻节点。

我们的关键贡献是，为一个顶点的网络邻节点定义了一个灵活的概念。通过选择一个合适的概念，node2vec可以学到网络表示，它们可以基于现在的网络角色，或者属于的社群来进行组织。我们通过开发一个有偏的随机游走（biased random walks）的族谱，它可以有效探索一个给定顶点的邻居分布。结果算法很灵活，提供可调参数给我们以对搜索空间进行控制，而不是之前的方法[24,28]进行严格搜索（rigid search）。相应的，我们的方法可以建模网络等价物。参数管理着我们的搜索策略，具有一个直观解释，会让walk朝着不同的网络搜索策略进行偏移。这些参数在一个半监督学习中，只使用很小比例的带标注数据（labeled data）就可以直接学到。

我们也展示了单独节点的特征表示如何被扩展成节点对（pairs of nodes。比如：边）。为了生成边的特征表示，我们将将学到的特征表示与简单的二元操作相组合。这种组合（compositionality）将node2vec引入到关于节点（或者是边）的预测任务上。

我们的试验集中在两个关于网络的公共预测任务上：一个多标签分类任务，其中每个节点被分配一或多个标签；一个链接预测任务，其中给定一个节点对，预测该边是否存在。我们将node2vec与state-of-art的特征学习方法[24,28]进行对比。并从现实中不同领域中的网络进行实验，比如社交网络，信息网络，以及系统生物学网络。对比起state-of-art的方法，实验演示了nod2vec在多标签分类上要好26.7%，在链接预测的任务上要好12.6%。该算法展示了有竞争力的效果，即使只有10%的带标签数据，对于噪声或缺失边的情况下一样健壮。计算上，node2vec的主要过程是并行化的，它可以扩展到带有数百万节点的大网络上，只需要几个小时的计算量。

该paper主要贡献是：

• 1.提出了nod2vec，一种用于网络特征学习的高效的扩展算法，可以通过一种显著的network-aware，neighborhood preserving objectives，使用SGD方法进行高效优化。
• 2.我们展示了node2vec如何适应在网络科学中已确立的准则，提供了在发现表示上的灵活性，并有不同的等价物。
• 3.我们基于neighborhood preserving objectives，扩展了node2vec以及其它特征学习方法，将节点扩展到节点对，来基于边的预测任务。
• 4.在多个真实数据集上，在多标签分类和链接预测上评估node2vec。

2.

在NLP的表征学习的最近进展上，有新方法对离散目标（比如：词）进行特征学习。特别的，Skip-gram模型是目标就是学习连续的特征向量，通过优化一个(neighborhood preserving likelihood objective). 该算法的处理如下：扫描一个文档的词，对于每个词，它的目标是将它进行嵌入，以便该词的特征可以预测邻近词（例如：在一些上下文窗口中的词）。词的特征表示通过使用SGD、negative sampling对likelihood objective进行优化学习得到。skip-gram目标函数是基于分布式假设：有相似上下文的词，趋向于具有相近的意思。也就是说，相似的词趋向于出现在具有相似词邻居的上下文内。

受skip-gram模型的启发，最近的研究确立了一种网络的类比法，将一个网络表示成一个“文档（document）”。相同的方法是，一个有序的词序列，节点序列需要从底层网络上进行采样，将一个网络转化成一个有序的节点序列。然而，对于节点来说，存在许多可能的抽样策略，会从而学到不同的特征表示。事实上，正如我们展示的，对于所有网络和所有预测任务来说，没有明确可胜出的抽样策略可以适用所有场景。以前的方法的主要缺点是，在从一个网络上进行抽样节点时缺乏灵活性。我们的算法node2vec克服了该限制，通过设计一种灵活的目标函数，它不会绑定一个特定的抽样策略，提供参数来调节探索的搜索空间（见第3节）。

最终，对于基于节点和基于边的预测任务，存在许多监督特征学习方法[15,17,31,39]。这些架构直接最小化loss function，使用多层非线性转换来产生更高的accuracy，但扩展开销高，因为训练时间长。

…

3.特征学习框架

我们将网络特征学习看成是一个极大似然优化问题。给定一个网络\(G = (V, E)\)。我们的分析是普适性的，可以应用于任何有向（无向）、加权（不加权）的网络。假设：\(f: V -> R^d\)是映射函数，将节点映射到特征表示。这里的d是特征表示的维度。f是一个size为\(\|V\| \times d\)的参数矩阵。对于每个源节点（srouce node）\(v \in V\)，我们定义了\(N_S(u) \subset V\)作为节点u的一个网络邻节点，它通过邻节点采样策略S来生成。

我们扩展了Skip-Gram架构来处理该网络。我们对下面的目标函数进行最优化，它会基于它的特征表示，对一个节点u的一个网络邻节点\(N_S(u)\)的log概率进行最大化，f给定：

\(max_f \sum_{u \in V} log Pr(N_S(u) | f(u))\) …(1)

为了让最优化变得可处理，我出做出了两个标准假设：

• 条件独立性。我们通过假设：给定源节点的特征表示，观察到一个邻节点的似然，与观察到其它邻节点是独立的：

\[Pr(N_s(u) | f(u)) = \prod_{n_i \in N_S(u)} Pr( n_i | f(u))\]

• 特征空间的对称性。一个源节点和它的邻节点在特征空间中具有对称性的相互影响。因而，我们建模每个（源节点-邻节点）pair的条件似然建模成一个softmax unit，它由它们的特征点积进行参数化：

\[Pr(n_i | f(u)) = \frac{exp(f(n_i)\cdot f(u))} {\sum_{v \in V} exp(f(v) \cdot f(u))}\]

有了以上假设，等式一的目标可以简化为：

\(max_{f} \sum_{u \in V} [ -log Z_u + \sum_{n_i \in N_S(u)} f(n_i) \cdot f(u) ]\) …(2)

每个节点的分区函数：\(Z_u = \sum_{v \in V} exp(f(u) \cdot f(v))\)，对于大网络来说计算开销很大，我们可以使用负采样[22]来对它做近似。我们使用SGA（ascent）对等式(2)进行优化.

基于skip-gram的特征学习方法，最早源自于NLP上下文学习。文本本身是线性的，一个邻词可以很自然地使用一个在连续词汇上的滑动窗口进行定义。而对于网络，是非线性的，因而需要更丰富。为了解决这一点，我们提出了一个随机过程，它会对给定源节点u抽样许多不同的邻节点。\(N_S(u)\)不局限于它的立即邻节点（immediate neighbors），具体取决于抽样策略S，有不同的结构。

3.1 经典搜索策略

图1

我们将对一个源节点的邻节点进行抽样的问题看成是一种局部搜索（local search）。图1展示了一个图，其中，给定一个源节点u，我们的目标是生成(抽样)它的邻节点\(N_S(u)\)。重要的是，为了比较不同的抽样策略S，我们将邻节点集合\(N_S\)的size限制为k个节点，接着为单个节点u抽样多个集合。总体上，有两种极限抽样策略来生成k个节点的邻节点集合\(N_S\)：

• 广度优化抽样（BFS：Breadth-first Sampling）: 邻节点\(N_S\)被限制到关于源节点的立即领节点上（immediate neighbors）。例如：在图1中，对于一个邻节点的size为 k=3, BFS抽样的节点为：\(s_1, s_2, s_3\)。
• 深度优化抽样（DFS：Depth-first Sampling）：邻节点包含了从源节点开始在增加的距离上按顺序抽样的节点。在图1中，DFS抽样\(s_4, s_5, s_6\)

BFS和DFS表示了根据搜索空间进行探索的两种极限情况。

特别的，在网络上的节点的预测任务通常会是两种类型相似度的混合（shuffle）：同质（homophily）等价 和结构（structural）等价。在同质假设下，节点高度交错连接，并且属于同网络聚类或社群，在embedding上更紧密（例如：图1中的节点\(s_1\)和u属于相同的网络社群）。相反的，结构等价假设下，在网络上具有相似结构角色的节点，应该在embedding上更紧密（例如：节点u和\(s_6\)在图1上分演扮演着相应社群中心的角色）。更重要的是，不同于同质等价，结构等价不强调连通性；在网络中的节点可以离得很远，但它们仍具有相近的网络结构角色。在真实世界中，这些等价概念并是排斥的；网络通常具有两者的行为。

我们观察到，BFS和DFS的策略在处理表示时扮演着重要角色，它影响着上述两种等价。特别的，BFS抽样的邻节点会导致embedding与结构等价更紧密。直觉上，我们注意到，为了探明结构等价，通常会对局部邻节点进行精准的描述。例如，基于网络角色（桥接：bridges、中心：hubs）的结构等价可以通过观察每个节点的立即节点(immediate neighborhoods)观察到。通过将搜索限制到邻近节点，BFS达到了这种characterization， 并且获得了关于每个节点的邻近点的微观视角。另外，在BFS中，在抽样邻节点上的节点趋向于重复多次。这很重要，对于。

3.2 node2vec

基于上述观察，我们设计了一种灵活的邻节点抽样策略，它允许我们在BFS和DFS间进行平衡。我们通过开发一种灵活的有偏随机游走（biased random wolk）过程，它可以以BFS和DFS的方式来探索邻节点。

3.2.1 随机游走

给定一个源节点u，我们进行模拟一个固定长度为l的随机游走。\(c_i\)表示在walk中的第i个节点，从起点\(c_0=u\)开始。节点\(c_i\)通过下面的方式生成：

\[P(c_i=x | c_{i-1}=v) = \begin{cases} \frac{\pi_{vx}}{Z} , if(v,x) \in E \\ 0 , otherwise \end{cases}\]

其中\(\pi_{vx}\)是未归一化的节点v和x间的转移概率，而Z是归一化常量。

3.2.2 搜索偏差\(\alpha\)

对我们的随机游走进行bias的最简单方法是，基于一个静态边权重\(w_{vx}\)（例如: \(\pi_{vx} = w_{vx}\)）来抽样下一个节点（无权重图则\(w_{vx}=1\)）。然而，该种情况不能解释网络结构，并指导搜索过程来探索不同类型的网络邻居。另外，不同于BFS和DFS两个极端，我们的随机游走会兼容两者。真实网络中通常也是两者混合。

图2: 在node2vec中的随机游走过程说明。该walk会从t到v进行转移，并在node v准备出去的下一步进行评估。边的labels表示搜索的bias \(\alpha\)

我们定义了一个2阶随机游走，它具有两个参数p和q来指导walk：考虑到一个随机游走，它穿过边(t,v)，现在留在节点v上（图2）。该walk需要决定，在下一步它会评估在边(v,x)上由v产生的转移概率\(\pi_{vx}\)。我们设置未归一化转移概率为\(\pi=\alpha_{pq}(t,x) \cdot w_{vx}\)，其中：

\[\alpha_{pq}(t,x) = \begin{cases} \frac{1}{p} , if d_{tx}=0 \\ 1 , if d_{tx}=1 \\ \frac{1}{q} , if d_{tx}=2 \end{cases}\]

其中，\(d_{tx}\)表示在节点t和x上的最短路径距离。注意，\(d_{tx}\)必须是{0, 1, 2}其中之一，因而，两个参数都是必须的，可以充分指导该walk。

直觉上，参数p和q控制着该walk从起始节点u进行探索和离开邻节点的快慢。特别的，该参数允许我们的搜索过程（近似）在BFS和DFS间进行插值，从而影响不同节点等价的紧密关系。

返回（Return）参数：p。参数p控制着在walk中立即访问一个节点的似然。将它设置成一个高值(> max(q,1))，可以确保我们在下两步内对一个已经访问节点进行抽样的可能性变得很小。（除非在walk内的下一个节点没有其它邻居）。这种策略鼓励适度探索，避免在抽样时存在二跳内重复（2-hop redundancy）。另一方面，如果p很小（<min(q,1)），它将导致该walk会回溯(backtrack)一个step（见图2），并且这会让该walk“局部”上保持与起始节点u的接近。

入出（In-out）参数：q。参数q允许搜索在“inward”和”outward”节点间区分。回到图2, 如果q>1, 随机游走会偏向于更接近节点t的节点。这样的walk会根据在walk中各自的起始节点获得一个关于底层graph的局部视图，近似的BFS行为感觉上我们的抽样在一个小的局部内的节点组成。

作为对比，如果 q < 1, 该walk更趋向于访问那些离节点t更远的节点。这样的行为受DFS影响，它会鼓励outward探索。然而，这里的一个基本不同是，我们在随机游走框架内完成DFS-like的探索。因而，被抽中的节点不需要对到给定节点u的距离进行增加才行，反过来，我们受益于对随机游走的回溯预处理和优秀的采样效率。注意，通过将\(\pi_{v,x}\)设置成关于一个在walk t内前继节点的函数，随机游走是2阶markovian。

随机游走的好处。比起纯BFS/DFS方法，随机游走有许多好处。随机游走在时间和空间需求上的计算很高效。在图中为每个节点存储它的立即邻节点的空间复杂度为\(O(\|E\|)\)。对于二阶随机游走，会存储在每个节点的邻节点间的交叉连接，这会引发一个空间复杂度为\(O(a^2 \|V\|)\)，其中\(a\)是该graph的平均度，它通常对于现实网络来说很小。比起经典的基于搜索的抽样策略，随机游走的其它核心优点是它的时间复杂度。特别是，通过引入在抽样生成过程中的图连通性，随机游走提供了一个很便利的机制，通过复用跨不同源节点间的样本，来增加有效抽样率。通过模拟一个长度l>k的随机游走，得益于随机游走的马尔可夫性，我们可以为l-k个节点一次生成k个样本。因而，每个样本的有效复杂度为\(O(\frac{1}{k(1-k)})\)。例如，在图1中，我们抽样一个长度为l=6的随机游走 {\(u, s_4, s_5, s_6, s_8, s_9\)}，它会产生\(N_S(u)=\left s_4, s_5, s_6 \right\)，\(N_S(s_4)=\left s_5, s_6, s_8 \right\)，以及\(N_S(s_5)=\left s_6, s_8, s_9 \right\)。注意，在整个过程中，样本复用可能引入一些bias。然而，我们观察到它可以极大提升效率。

3.2.3 node2vec算法

算法1

node2vec的伪代码，详见算法一。在任何随机游走中，由于起始节点u的选择，会有一个隐式偏差（implicit bias）。由于我们为所有节点学习表示，我们会为每个节点通过模拟r个固定长度为l的随机游走来对该bias进行补偿（offset）。在该walk的每一个step，会基于转移概率\(\pi_{vx}\)进行抽样。对于二阶马尔可夫链，转移概率\(\pi_{vx}\)可以被预计算好，因而，当模拟随机游走时，节点的抽样可以很有效地在O(1)时使用alias sampling完成。node2vec的三个阶段（phases），即：预处理计算转移概率、随机游走模拟、使用SGD进行优化，是按顺序进行的。每个phase可以并行化和异步执行，从而做到node2vec整体可扩展性。 node2vec的一个实现：http://snap.stanford.edu/node2

3.3 学习边特征

node2vec算法提供了一个半监督方法来学习网络中节点的丰富特征表示。然而，我们通常对涉及节点对（pairs of nodes）的预测任务感兴趣，而非单个节点。例如，在链接预测上，我们在网络中的两个节点间预测一个链接是否存在。由于我们的随机游走在底层网络上天然地基于节点间的连通结构，我们可以使用一个bootstrap方法来将它们扩展到节点对的特征表示，而非单个节点的特征表示。

给定两个节点u和v，我们定义了一个二元操作o，在相应的特征向量f(u)和f(v)，为了生成一个表示g(u,v)，比如：\(g: V \times V -> R^d^'\)，其中\(d'\)是pair(u,v)的表示的size。我们希望我们的操作对于任意节点对可以进行定义，即使一条边在pair间不存在，因为这样做可以使表示对于连接预测有用，我们的测试集包含了true edges和false edges（不存在）。我们对于操作符o的一些选择，以便\(d'=d\)，由表1归纳的。

实验

略

node2vec: Scalable Feature Learning for Networks