郑 磊

(中国西南电子技术研究所, 成都 610036)

0 引言

随着互联网技术快速发展，用户可以同时与诸多领域中的事件交互，例如电子商务(用户购买物品)[1]、教育(用户注册MOOC课程)[2]，以及社交和协作平台(用户在Reddit的群组中发帖)[3]。同一用户可能在一段时间内与不同的事件进行交互，这些相互作用也会随着时间发生变化。随着时间变化，交互创建了一个用户和物品之间的时域交互网络。准确实时地推荐物品，以及预测用户状态的变化是需要解决的基本问题。例如，预测学生何时会退出 MOOC课程对于制定早期干预措施非常重要[4]；预测用户何时会在Reddit和维基百科等社交平台上进行恶意评论[5]，以确保平台安全性和完整性等。

表示学习又被称为学习实体的低维嵌入，是一种可以表示用户和物品的属性演化的方法。然而生成动态嵌入方法面临如下挑战：

1) 大多数现有方法仅在用户采取行动时为用户生成嵌入。但是，考虑当日进行购买并且其嵌入已更新的用户。如果在第二天、一周甚至一个月后返回平台，嵌入将保持不变。因此，无论该用户何时返回，都会对其做出相同的预测和建议。然而，用户的意图会随着时间而改变，因此其嵌入需要更新(投影)到当前查询时刻。如何随着时间的推移准确预测用户和物品的嵌入轨迹成为一个难点。

2) 实体既具有不随时间变化的静止特性，又具有演化特性。现有的方法在生成嵌入时通常仅考虑两者之一。然而，必须在一个统一的框架中考虑上述2种特性，以利用这2种不同的信息。

3) 许多现有方法通过对每个用户对应的所有物品进行评分来预测用户与物品的交互信息。这类方法具有线性时间复杂度，在具有数百万个物品的场景中不实用。然而，需要设计在常量时间内可以给用户推荐物品的方法。

基于上述挑战，本文提出一种在时域交互网络中预测动态嵌入轨迹的方法(UICRNN)，它学习时域交互网络中生成的所有用户和物品的嵌入轨迹。当用户采取行动时，用户和物品的嵌入被更新，投影算子将预测用户未来的嵌入轨迹。

对用户和物品通常采用2种嵌入方式：静态嵌入和动态嵌入。静态嵌入表示实体长期静止，而动态嵌入表示实体时刻变化。使用UICRNN进行学习，上述2种嵌入用于交互关系轨迹的生成。这使UICRNN不但能够根据用户的静态属性进行预测，而且可以根据用户的动态属性进行预测。

UICRNN由2个主要操作组成：更新操作和投影操作。更新操作由2个循环神经网络(recurrent neural network，RNNs)来生成用户和物品的嵌入。通过把2个RNNs进行耦合连接，使其可以明确地结合用户和物品之间的相互依赖关系。每次交互后，用户端RNN通过使用物品嵌入更新用户嵌入。同样地，物品RNN使用用户嵌入更新物品嵌入。UICRNN模型还能够合并交互的特征向量，例如，Reddit帖子文本[6]。UICRNN具有很强的扩展性，它可以通过为每个实体训练一个RNN来处理多种类型的实体类型。

UICRNN使用了投影操作预测用户未来的嵌入轨迹。直观地讲，自从用户上次与任何物品交互以来，用户的嵌入会在短时间内发生轻微变化，而在很长时间后可能会发生显著变化。因此，UICRNN训练了一个时域注意力层，在之前的交互经过一段时间后投影用户的嵌入。嵌入过程在很长一段时间后会发生显著变化，然后使用投影的用户嵌入来预测用户最有可能与之交互的物品。

此外，大多数现有模型通过逐步处理交互，然后从一系列其他的交互关系中学习嵌入，以增加时间顺序来保持交互之间的时间依赖性。这使得此类方法无法扩展到具有数百万次交互的真实数据。因此，本文提出了一种批处理方案，通过创建独立交互的训练批次来训练模型，这样每个批次中的交互可以并行处理。为此，从交互网络中迭代地选择独立的边集。在每个批次中，每个用户和物品最多出现一次，并且每个用户和物品的基于时域排序的交互是单调递增的，确保在时间序列上的一致性。

本文的主要贡献如下：

1)新模型：提出了一种用户-物品耦合循环神经网络，称为UICRNN。其由2个循环神经网络来生成用户和物品的嵌入。训练了一个时域注意力层，在交互经过一段时间后投影用户的嵌入。

2) 新方法：提出了一种新的嵌入方法，可以学习用户和物品的嵌入轨迹，还可以学习投影算子，预测用户的嵌入轨迹以及预测未来的交互。此外，提出了一种有效的批处理训练方案来创建独立但时间一致的训练数据批次，这有助于训练所提出的UICRNN模型。

3) 有效性：在未来交互预测和用户状态变化预测时，UICRNN优于6种最先进的算法。预测未来交互行为的准确率至少提高42.91%，预测用户状态变化的准确率平均提高了15.79%

1 相关工作

本节讨论与本文研究问题密切相关的工作，涵盖如下3个领域的内容。

深度循环推荐模型。近期，主要工作采用循环神经网络RNN和其变体长短期记忆网络LSTM(long short-term memory)或门控循环单元GRU(gate recurrent unit)来构建推荐系统。Wu等[7]使用RNNs从层次型网络生成动态用户和物品的嵌入。Beutel等[8]和Zhu等[9]学习如何将特征融合到嵌入中。Zhao等[10]将用户的偏好和文本情感特征转化为注意力信息，并结合不同的LSTM模型来预测用户的轨迹。然而，大多数方法有2个主要缺点：使用物品的one-hot向量作为输入以更新用户嵌入，仅包含物品id，忽略物品的当前状态；只为用户生成动态嵌入，而不为物品生成动态嵌入。

动态协同进化模型。最近一些研究使用点过程建模[11-12]和基于RNN的建模[13-14]协同学习用户和物品表示。这些模型的基本思想类似于UICRNN，即学习用户和物品嵌入的相互影响。然而，UIRCNN与这些模型的主要区别在于，训练一个投影操作来随时预测用户嵌入，输出物品嵌入而不是交互的概率，并使用批处理来训练模型。

时域网络嵌入模型。在时域网络中，一些相关的研究同时为节点生成嵌入(用户和物品)。Nguyen等[15]使用随时间增加的随机游走来生成嵌入，但它会生成节点的最终静态嵌入。同样，文献[16]生成一个来自交互图的用户和物品的最终嵌入，需要为每个新生成的边重新创建动态嵌入。另一些主流的算法[17-18]从图快照的序列中学习嵌入，但不适用于连续交互的场景。Xu等[19]利用分层注意机制来捕捉时间敏感的用户潜在偏好，并融合上下文信息以得出用户在给定时间内不同位置的投影概率。还有一些研究从节点之间的持久连接中学习嵌入[20-21]，但这些连接在交互网络中不存在，因为边代表瞬时交互。

2 用户-物品耦合循环神经网络

在本节中，提出了用户-物品耦合循环神经网络(UICRNN)，它可以从用户-物品交互的顺序序列中学习用户和物品的嵌入轨迹。时域用户-物品的交互关系记为Sr= (ur,ir,tr,fr)。在时刻tr，用户ur和物品ir的发生一次交互Sr。每个交互都有一个相关的特征向量fr。表1列出了所使用的符号。为了方便使用符号，将在本节的其余部分去掉下标r的标注。其中，加粗的符号表示向量。

所提模型UICRNN可以学习用户和物品的嵌入轨迹，其中，更新操作使用交互来更新用户和物品的交互状态，投影操作可以利用前一个观察到的状态和经过的时间来预测用户的未来嵌入。当观察到用户和物品的下一次交互时，它们的嵌入会再次更新。

表1 相关符号及说明

2.1 嵌入方法

每个用户和物品都包含2个嵌入：静态嵌入和动态嵌入，使用这2种嵌入方式来编码实体的长期静态属性及其动态属性。

静态嵌入：不会随着时间变化的嵌入，所以将其用于表达静态属性，比如用户的长期兴趣。使用one-hot向量作为所有用户和物品的静态嵌入。

动态嵌入：给每个用户u和物品i分配一个动态嵌入，在t时刻分别表示为u(t)∈Rn和i(t)∈Rn。Rn表示欧几里得空间。这些嵌入会随着时间的推移而变化，从而可以将它们随时间变化的行为和属性进行建模。用户和物品的动态嵌入序列称为其轨迹。

接下来描述更新和投影操作，将描述如何预测未来的交互项嵌入。

2.2 嵌入更新操作

在更新操作中，用户u和物品i在t时刻的交互S=(u,i,t,f)用于生成它们的动态嵌入u(t)和i(t)。图1给出了更新操作。

图1 UICRNN原理图

如图1所示，UICRNN使用2个循环神经网络进行更新。用户RNNU可以跨用户共享，以更新用户嵌入；物品RNNI在所有物品之间共享，以更新物品嵌入。RNNU和RNNI的隐藏状态分别表示用户嵌入和物品嵌入。

上述2个RNN是相互耦合的。当用户u与物品i交互时，RNNU通过使用在时间t之前的物品i的嵌入i(t-)作为输入，更新嵌入u(t)。i(t-)表示物品i在t前一时刻与其他用户交互后生成的物品嵌入。这一设计决策与使用物品的one-hot向量来更新用户嵌入形成了对比，one-hot向量具有以下2个缺点：

1) one-hot向量仅包含有关物品id的信息，而不包含物品的当前状态。

2) 当真实数据集有数百万个物品时，one-hot 向量的维度会非常大，使得模型难以训练和扩展。

相反，使用物品的动态嵌入，可以反映物品的当前状态，从而产生更有意义的动态用户嵌入且编码简洁更易于训练。出于同样的考虑，RNNI通过使用动态用户嵌入u(t-)更新物品i的动态嵌入i(t)，使嵌入之间相互依赖。形式化表示如式(1)(2)所示：

W3(u)·f+W4(u)·Δu)

(1)

W3(i)·f+W4(i)·Δi)

(2)

其中，Δu表示用户u之前与任意物品i交互的时间，Δi表示物品i之前与任何用户u交互的时间。f为相互作用的特征向量。W1(u)，…，W4(u)表示RNNU的参数矩阵，W1(i)，…，W4(i)表示RNNI的参数矩阵。σ是非线性的sigmoid函数。这些矩阵被训练用于预测下一个交互中的嵌入，将在第2.4节中解释。

2.3 嵌入投影操作

本节解释了嵌入投影算子，它预测了用户未来的嵌入轨迹，通过在未来的一段时间内投影用户的嵌入来实现。

图2给出了投影用户嵌入轨迹的主要思想。投影操作预测用户在t时刻进行最后一次交互后，经过一段时间后的嵌入。如图2所示，在时间t后的短持续时间Δ1，用户u的投影嵌入u*(t+Δ1)接近于先前得到的嵌入u(t)。随着Δ>Δ2>Δ1时间的推移，嵌入将投影到更远的u*(t+Δ2)和u*(t+Δ)。当在t+Δ时刻观察到下一个交互时，用户的嵌入将使用更新操作更新为u(t+Δ)。

图2 投影操作示意图

投影操作需要2个输入：在时刻t的用户u的嵌入和时间间隔Δ。通过Hadamard乘积[22]将时间纳入投影嵌入中，将嵌入和时间连接起来，并通过线性层提取特征。神经网络对多个输入进行拼接，但对相关的交互进行建模是低效的，而本文所提投影方法创建了一个时域注意力向量，提升了建模效率。

具体做法是使用线性层(被表示为参数矩阵Wp)将Δ转换为时间背景向量w∈Rn，其中w=WpΔ。使用均值0的高斯分布来初始化Wp。然后将投影嵌入作为时间上下文向量与之前嵌入的元素作逐元素乘积，如式(3)所示：

u*(t+Δ)=(1+w)*u(t)

(3)

向量1+w作为一个时间注意向量来缩放过去的用户嵌入。当Δ为0时以及w为0时，投影嵌入与输入嵌入向量相同。Δ值越大，投影嵌入向量与输入嵌入向量的差异越大，投影嵌入向量随时间的投影距离越远。此外，本文发现单个线性层投影嵌入的效果最好，因为它等价于嵌入空间中的一个线性变换。

2.4 预测物品嵌入

用户u在t时刻与物品i交互，然后在t+Δ时刻与物品j交互。问题在于到达t+Δ时刻之前，如何预测用户u会与哪个物品交互?训练UICRNN，使用u的投影嵌入u*(t+Δ)来做出这个预测。

一个关键的设计为：UICRNN直接输出一个物品的嵌入向量j*(t+Δ)，而不是用户u和物品i之间的交互概率。这样做的优点是将推理时间的计算从线性时间复杂度减少到常数时间复杂度。大多数现有的输出交互概率的方法[23-24]均需要经过神经网络向前传递|I|次(一个物品一次)，以找到概率得分最高的物品，但是时间代价非常昂贵。相比之下，UICRNN仅需要一次向前传递，并输出一个预测的物品嵌入。然后，通过使用局部敏感哈希技术[25]，可以在接近常数的时间复杂度内返回最接近该嵌入的物品。为了维护局部敏感哈希的数据结构，将在一个物品的嵌入被更新时更新该数据结构。

训练UICRNN来最小化L2正则化损失函数，该损失函数为||j†(t+Δ)-[j～，j(t+Δ-)]||2，可以衡量预测物品的嵌入与真实物品的嵌入之间的不同。其中，预测物品的嵌入为j†(t+Δ)，真实物品的嵌入为[j～，j(t+Δ-)]。[x，y]表示向量x和y的拼接，上标“-”表示在该时间之前的嵌入。

使用在时间t+Δ之前的物品i(用户u之前交互的物品)的嵌入i(t+Δ-)和投影的用户嵌入u*(t+Δ)来进行该预测。考虑i(t+Δ-)有2个原因：① 物品i可能与其他用户在时间t和t+Δ之间交互，因此嵌入包含最近的信息；② 用户u经常与同一物品i连续交互(即i=j)，包含之前的物品嵌入有助于此类预测。使用物品i的静态和动态嵌入来预测物品j的静态和动态嵌入。预测采用全连接线性层，如式(4)所示：

j†(t+Δ)=W1·u*(t+Δ)+W2·u～+

W3·i(t+Δ-)+W4·i～+B

(4)

其中，参数矩阵W1，…，W4和偏置向量B构成线性层。

训练模型。在每次交互时，UICRNN最小化预测物品嵌入和真实物品嵌入之间的L2距离，并进行训练。计算出的总损失如式(5)所示：

Loss=∑(u,i,t, f)∈S||j†(t) -[i～,i(t-)]||2+

λU||u(t)-u(t-)||2+λI||i(t)-i(t-)||2

(5)

第一个损失项使预测的嵌入误差最小化，添加后两项是为了正则化损失，并防止用户和物品的连续动态嵌入变化太大。λU和λI是缩放参数，以确保损失在同一范围内。

2.5 训练数据批处理方案

本节介绍所提并行化训练数据的批处理方案。在训练期间保持交互之间的时域依赖性很重要。使用单个RNN的现有方法将用户分成不同的批次然后并行处理。因为这些方法使用物品的one-hot向量作为输入，可以使用标准的时间反向传播机制进行训练。然而，在UICRNN中，耦合的RNN能够合并物品的嵌入来更新用户嵌入。与同一物品交互的2个用户之间将创建相互依赖关系，防止简单地将用户分成单独的批次。

大多数现有方法也使用2个耦合的RNN[23-24]按顺序逐一处理所有交互。但是，由于训练过程非常缓慢，因此无法扩展到大量交互。基于此，本文提出一种新的批处理数据方案来训练UICRNN。

创建训练满足要求的批次具有一定难度，包含2个挑战：每个批次中所有的交互应该并行处理；按索引的递增顺序处理批次应该保持交互的时间顺序，应该生成与任何批次均不相同的嵌入。

为了克服上述挑战，通过选择交互网络的独立边集来创建每个批次，即同一批次中的2个交互不共享任何共同的用户或物品。UICRNN迭代执行以下2个操作：选择操作和减少操作。在选择操作中，通过选择最大的边集来创建一个新批次。在减少操作中，从网络中删除选定的边。UICRNN迭代执行这2个操作，直到图中没有边。每个批次都可以并行化，并且按顺序处理批次可以保持顺序依赖关系。

在实现过程中，将每个交互Sr分配给一个批次Bk，其中k∈[1,|I|]。初始化|I|个空批次(在最坏的情况下，每个批次只有一次交互)。迭代基于时域排序的交互序列{S1，…，S|I|}，每个交互被添加到批次Bk中。设maxBatch(e,r)是具有最大索引的批次，该批次具有涉及实体e的交互(此处e表示用户u或物品i)，交互的最大编号为r。然后，将交互Sr+1分配给索引为max{1+maxBatch(u,r),1+maxBatch(i,r)}的批次。创建批次的复杂性为O(|S|)，即交互次数是线性的，因为每个交互仅使用1次。

本文提出的批处理方案确保每个用户和物品在每个批次中最多出现一次，因此每个批次都可以并行化。此外，每个用户和每个物品的第r次和r+1次交互分别分配给批次Bk和Bl，k

3 实验及分析

在多个数据集上进行实验，并与6个基准方法进行比较，验证了UICRNN在未来交互预测和用户状态变化预测上的有效性。

3.1 实验设置

在前τ%(不同的任务所设置的τ不同)的交互数据上训练模型，用后τv%的交互数据作为验证集，用最后剩余的交互数据作为测试集。将所有方法的动态嵌入维数和静态嵌入的维数设置为128，所有算法都运行了50个epochs。

基准方法。实验中比较了UICRNN与6个相关算法，这6个算法属于3个类别(在相关工作中已介绍)：① 深度循环推荐模型。在这一类别中，与RRN[7]、LatentCross[8]、Time-LSTM[9]和标准LSTM[9]进行了比较。这些算法是推荐系统中主流的算法，可以生成动态的用户嵌入。② 动态协同进化模型。与主流的深度协同进化模型DeepCoevolve[14]进行了比较。③ 时域网络嵌入模型。比较了算法CTDNE[15]，该算法从时域网络中生成嵌入，当它生成静态嵌入时，会在添加每条边之后生成新的嵌入。

实验中使用如下2个公开的数据集进行实验。

1) Redditpost数据集。这一数据集由用户一个月内在subreddits[2]上发布的帖子组成。实验选择了 1 000个最活跃的subreddits作为物品，然后选用 10 000个最活跃的用户，产生了 672 447次交互。将每篇文章的文本转换为一个表示其LIWC(linguistic inquiry and word count)类别[26]的特征向量。

2) Wikipedia edits数据集。这个公共数据集收集了对维基百科页面[3]在1个月内进行的编辑操作。实验中选择1 000个编辑操作最多的页面作为物品，每个编辑作为用户进行了至少5次编辑操作(共8 227个用户)。产生了 157 474个交互作用。与Redditpost数据集类似，将编辑文本转换为LIWC特征向量。

3.2 未来交互预测

预测任务定义为：给定到t时刻的所有交互，预测用户u将在t时刻与哪个物品交互。

使用前80%的数据进行训练，后10%的数据进行验证，最后的10%进行测试。用MRR(mean reciprocal rank)和recall@10来衡量算法的性能，MRR是倒数排名的平均值，recall@10表示物品交互预测的前十的置信度中，正确预测所占的比例。对于每一次交互，需要计算数据集中所有物品的置信度排名。

表2显示了UICRNN与6种主流方法的性能。可以观察到，在基准方法中，RRN在Redditpost和Wikipedia edits数据集中表现较好。CTDNE生成静态嵌入，所以其性能较低。在Wikipedia edits数据集上，UICRNN在指标MRR上至少提升42.91%。在Reddit数据集上，UICRNN在recall@10上至少提升14.05%。

表2 未来交互预测实验

3.3 状态改变预测

在本实验中，任务是预测交互是否会导致用户状态变化，特别是在如下2个案例中：预测用户是否会被禁止和预测学生是否会退出课程。用户被禁止或退出之前，用户的标签为“0”，他们最后一次的交互标签为“1”。对于未被禁止或未退出的用户，标签始终为“0”。这是一项极具挑战性的任务，因为只有不到1%的标签是“1”。

本实验使用如下3个公开的数据集进行实验。

1) Reddit bans。属于Reddit post数据集，带有来自Reddit被禁止用户的真实标签。在672 447次交互中包含了366个真实标签，约占0.05%。

2)Wikipedia bans。属于Wikipedia edits数据集，带有被禁用户的公开真实标签[3]。在157 474次交互中有217个正例标签，约占0.14%。

3) MOOC student drop-out。这个公共数据集由学生在MOOC在线课程[1]上完成的行为组成，例如观看视频、提交答案等。该数据集由7 047名用户与98个物品(视频、答案等)进行交互，产生超过411 749次交互，有4 066个辍学事件，约占0.98%。

在本实验中，在前60%的交互数据上训练模型，在余下数据中选择20%的交互数据进行验证，并在最后20%的交互数据上进行测试，使用AUC(areaunder the curve)评估模型。对于基准方法，在训练数据上，使用动态用户嵌入作为输入训练逻辑回归分类器。

表3将UICRNN在3个数据集上的性能与基准模型进行比较。可以发现，在预测所有数据集的用户状态变化时，UICRNN的性能比其他基线平均高出至少15.79%。在用户禁用预测任务中，UICRNN比RRN(最接近的对比基线)至少高出2.22%，而在学生辍学任务中，它比RRN高出35.48%。UICRNN在各种数据集上表现均为最佳。原因在于：其他基准没有考虑动态嵌入，导致训练数据少的时候无法充分抽取用户和物品之间的关系。

表3 用户状态改变预测实验

3.4 运行时间

本节将UICRNN的运行时间与基准算法进行比较。 从结果的相似性看，DeepCoevolve最接近UICRNN，因为前者也训练了2个相互耦合的RNN，而其他方法只训练一个RNN。图3显示了Reddit数据集一个epoch的运行时间(以分钟为单位)，可以发现UICRNN比DeepCoevolve快9.25倍。同时，UICRNN的运行时间与其他仅使用一个 RNN的基线相当。由于使用了所提出的批处理训练方法，UICRNN能够与非相互耦合模型所用相似时间进行模型训练。

图3 运行时间柱状图

此外，还发现没有使用所提批处理方案的 UICRNN需要43.53 min完成训练，而使用所提批处理方案的UICRNN仅需要5.1 min完成训练。 因此，所提批处理方案可以产生8.4倍的加速。

3.5 鲁棒性测试

在本实验中，通过改变训练数据的百分比并比较算法在未来交互预测任务中的性能，证明UICRNN的鲁棒性较强。

对于下一个物品的预测，将训练数据百分比设置为10%～80%。在每种条件下，将训练数据的后10%作为验证集，然后再选择数据集中剩下部分的10%作为测试集。这样做是为了比较不同测试数据大小下算法的性能。图4和图5显示了随着训练数据量的增加，2个数据集上所有算法MRR的变化。

图5 在Reddit数据集上的鲁棒性测试曲线

实验结果表明，UICRNN始终明显优于其他基准模型。说明了UICRNN在不同的数据集以及不同的训练数据大小的情况下，鲁棒性较强。主要原因在于：其他基准没有考虑动态嵌入，且训练方案较差，导致训练数据少的时候无法充分抽取用户和物品之间的关系。而UICRNN同时考虑静态嵌入和动态嵌入，并且对批处理训练进行了改进，在精确度和鲁棒性上有了巨大提升。此外，可以发现UICRNN的性能是稳定的，并且在数据点之间变化不大。

4 结论

提出了UICRNN的耦合递归神经网络模型，从一系列时间交互中学习用户和物品交互关系的动态嵌入。UICRNN学习预测用户和物品的未来嵌入，使它对未来用户和物品交互以及用户状态变化提供更好的预测性能。此外，提出了训练数据并行化批处理方法，使UICRNN比类似的基准具有更快的训练速度。

未来的工作主要包括：由于单个用户和物品学习嵌入昂贵，故可以学习用户和物品组的交互关系轨迹以减少参数的数量；聚集相似的实体表示轨迹；根据用户可能交互的物品设计新物品。