论文阅读——Where to Go Next- A Spatio-Temporal Gated Network for Next POI Recommendation

Where to Go Next: A Spatio-Temporal Gated Network for Next POI Recommendation

下一步该何去何从：用于下一个 POI 推荐的时空门控网络

Abstract

下一个兴趣点 (POI) 推荐对用户和 POI 持有者都有很大价值，但这是一项具有挑战性的任务，因为极其稀疏的用户签到数据中包含复杂的顺序模式和丰富的上下文。最近提出的嵌入技术在通过对上下文信息进行建模来缓解数据稀疏问题方面显示出了有希望的结果，并且循环神经网络（RNN）已被证明在顺序预测中是有效的。然而，现有的下一个 POI 推荐方法分别训练嵌入和网络模型，无法充分利用丰富的上下文。在本文中，我们提出了一种新颖的统一神经网络框架，名为 NeuNext ，它利用 POI 上下文预测来通过联合学习（joint learning）来协助下一个 POI 推荐。具体来说，提出了 时空门控网络（STGN）来为下一个 POI 推荐中的用户长期和短期偏好建模个性化序列模式。在POI上下文预测中，利用POI侧丰富的上下文来构建图，并增强相邻POI之间的平滑性。最后，我们 联合训练 POI 上下文预测和下一个 POI 推荐，以充分利用标记和未标记数据。对真实世界数据集的大量实验表明，我们的方法在准确性和 MAP 方面优于其他 POI 推荐方法。

1 Introduce

文章介绍了一下基于地理的社交网络（LBSN）吸引了很多用户去分享自己的足迹和是首选兴趣点（POIs），这些信息提供了了解用户对POIs偏好的机会，这对于帮助用户探索周围环境具有很大的价值，也有利于POI持有者向目标客户投放广告进行营销。

重要的挑战：

数据稀疏性（Data Sparsity）：数据稀疏问题对下一步的 POI 推荐影响更大，因为稀疏数据会导致序列较短，从而难以捕获用户的序列模式。此外，POI推荐的数据过去都是二元隐式的而非显式的，用户行为的规律性不利于被发现和利用。

顺序模式（Sequential Pattern）：与POI推荐相比，下一个POI推荐，即为用户推荐近期访问的POI，除了考虑用户的偏好之外，还考虑了用户签到的顺序信息。顺序模式有

2个含义

，一方面，用户在特定的时间做特定的动作，如午饭时间去餐厅。另一方面，用户的行为之间存在一定的时间顺序，从而导致POI的特定顺序，这也反映了不同用户的个性化偏好。

各种上下文（Various Contexts）：包括时间上下文，地理影响，用户社会影响，辅助元数据信息例如文本描述，等等。事实上，可用的上下文通常受到数据集的限制 。作者只使用时间间隔、距离间隔和附近的 POI 作为 POI 上下文。这些可以对顺序信息和协作信息进行建模的上下文是自然可用的。

目前的文献中，潜在因素模型和马尔科夫链等方法已经广泛应用于序列数据分析和推荐。最近，RNNs已成功用于对序列数据进行建模，并成为最先进的方法。然而没有一个推荐方法同时考虑临近项目之间的时间和地理距离，这使得下一个POI推荐不同于其他顺序任务。最近人们做出了一些努力来扩展 RNN，以对动态时间和距离间隔进行建模。

作者这里主要介绍了ST-RNN[1]模型，它尝试扩展 RNN 来对时间和空间上下文进行建模，以进行下一个位置预测。为了对时间上下文进行建模，ST-RNN 在每个 RNN 单元的时间窗口中对多重签入进行建模。同时，ST-RNN 采用特定于时间和特定于距离的转换矩阵来分别表征动态时间间隔和地理距离。然而，存在一些挑战阻止 ST-RNN 成为下一个 POI 推荐的最佳解决方案。首先，ST-RNN 可能无法正确建模邻居签入的空间和时间关系。 ST-RNN 在 RNN 内的单元隐藏状态之间采用时间特定和距离特定的转换矩阵。由于数据稀疏性，ST-RNN 采用线性插值将时间间隔和地理距离分别划分为离散箱，而不是学习每个可能的连续时间间隔和地理距离。其次，ST-RNN 是为了短期利益而设计的，并没有很好地考虑长期利益。贾纳赫等人。第三，由于 ST-RNN 在固定时间段内对多个元素进行建模，因此很难针对不同应用选择合适的时间窗口宽度。

[1] Q. Liu, S. Wu, L. Wang, and T. Tan, “Predicting the next location: A recurrent model with spatial and temporal contexts,” in Proc. 30th AAAI Conf. Artif. Intell., 2016, pp. 194–200.

最近，半监督学习（SSL）旨在利用未标记的数据来提高整体学习偏好。

在本文中 ，作者提出了一种新颖的统一神经网络框架，名为 NeuNext，从未标记的上下文数据和标记的签到数据中联合学习 POI 嵌入和网络模型，以提高下一个 POI 推荐性能。所提出的 NeuNext 框架由两部分组成：下一个 POI 推荐和 POI 上下文预测。 NeuNext 联合优化标记签入数据的监督损失以及标记数据和未标记上下文数据的无监督损失，以减轻数据稀疏性，并旨在利用未标记的数据提高下一个 POI 推荐性能。与之前的工作不同的是 ，NeuNext 中上下文的嵌入是与下一个 POI 推荐联合训练的。

贡献：

模型 NeuNext

联合模拟

了各种上下文和用户的顺序访问模式，是第一个采用

混合嵌入和循环神经网络技术

进行下一个 POI 推荐的工作。

我们提出了一种增强的长期短期记忆方法，名为

STGN

，分别对用户的短期和长期顺序偏好进行建模。

所提出的方法已在大规模现实世界数据上进行了评估，以用于下一个 POI 推荐。我们的实验结果表明，我们的方法在不同指标（例如准确性和 MAP）方面优于最先进的方法。

2 RELATED WORK

本章从一般POI推荐、下一个POI推荐以及利用神经网络进行推荐三个方面对相关工作进行了综述。

3 PROBLEM FORMULATION AND FRAMEWORK OVERVIEW

问题陈述：介绍了文章重要的符号含义和输出的介绍。

LSTM：作者在他们的方法中使用基本的LSTM模型。

总体框架：

NeuNext 中有两个部分：下一个 POI 推荐捕获用户的访问顺序模式，POI 上下文预测增强 POI 和上下文之间的平滑性。该模型的基本输入是用户 POI 签到序列。

Next POI Recommendation. 通过增强长期短期记忆提出了一种新的时空门控网络，名为 STGN，具有两对时间门和距离门，分别对用户的长期和短期偏好进行建模。

POI Context Prediction. 对于用户签到历史中的每个POI，使用Skipgram模型来预测POI在POI上下文图上的上下文。获得 POI 的上下文后，Skipgram 的目标是优化使用 POI 的嵌入来预测上下文的对数损失。

Joint Learning. NeuNext 根据基于共享 POI 嵌入的两类目标函数联合训练，以推荐下一个 POI 并预测 POI 的上下文。目标函数包括标记签到数据的监督损失和用于增强 POI 和上下文之间的平滑性的无监督损失或正则化惩罚。 NeuNext 通过优化上述两个损失的总和来联合训练，这将学习更好的 POI 嵌入。

4 OUR APPROACH

本章主要介绍了框架的细节，包括STGN及其变体，用于学习顺序偏好、POI 上下文预测和联合学习。

4.1 Next POI Recommendation

使用LSTM用于下一个POI推荐，xtx_t 代表用户最后访问的 POI，可以用来了解用户的短期兴趣。而ct−1c_{t-1} 包含用户历史访问过的POI信息，反映了用户的长期兴趣。然而，短期兴趣在多大程度上决定下一步要去哪里，很大程度上取决于上一个POI和下一个POI之间的时间间隔和地理距离。

提出的时空门控网络模型中，作者使用时间门和距离门来控制上次访问的 POI 对下一个 POI 推荐的影响。此外，时间门和距离门还可以帮助在单元状态ctc_t中存储时间和距离间隔，从而记住用户的长期兴趣。这样，便可以利用时间和距离间隔同时对用户的短期兴趣和长期兴趣进行建模。

作者在LSTM上添加了2对时间门和距离门，分别表示为T1t,T2t,D1t,D2tT1_{t},T2_{t}, D1_{t}, D2_{t}。第一对用于控制最近访问的POI对下一个POI的影响；第二对用于捕获时间和距离间隔来建模用户的长期兴趣。

基于LSTM，添加的时间门和距离门的等式如下：

修改方程式(4),(5),(6):

T1tT1_t可以看作是考虑时间间隔的输入信息过滤器，D1tD1_t 可以看作是另一个考虑距离间隔的输入信息过滤器。我们添加一个新的单元状态 c^t\hat c_t 来存储结果，然后转移到隐藏状态 hth_t 并最终影响下一次推荐。沿着这条线，c^t\hat c_t 由时间门 T1tT1_t 和距离门 D1tD1_t 以及输入门 iti_t 根据当前建议进行过滤。

细胞状态ctc_t用于记忆用户的总体兴趣，即长期兴趣。作者设计了时间门和距离门来控制细胞状态ctc_t更新。 T2tT2_t 首先记住△tt\triangle t_t，然后转移到 ctc_t，进一步转移到 ct+1,ct+2,...c_{t+1},c_{t+2},... ,所以 T2tT2_t 帮助存储 △tt\triangle t_t 来模拟用户的长期兴趣。以类似的方式，D2tD2_t 记忆 △dt\triangle d_t 并传输到单元状态 ctc_t 以帮助建模用户的长期兴趣。这样，ctc_t不仅可以记住用户历史访问过的POI的顺序，还可以记住邻居POI之间的时间和距离间隔信息，从而捕获用户的长期兴趣。 对距离间隔建模可以帮助捕获用户的总体空间兴趣，而对时间间隔建模有助于捕获用户的周期性访问行为。

为什么设置两个时间门和两个距离门来区分长短期影响？

通常情况下，最近访问过的、距离较短的 POI 对选择下一个 POI 的影响应该更大。为了将这些知识融入到设计的门中，我们在等式（7）和（9）中添加了约束 Wxt1≤0W_{x_{t1}}≤0 和 Wxd1≤0W_{x_{d1}}≤0 。因此，如果△tt\triangle t_t 更小，则根据等式(7) T1tT1_t 将会更大。类似地，如果△dt\triangle d_t 更短，则根据式（9），D1tD1_t 会更大。例如，如果xtx_t与下一个POI之间的时间和距离间隔较小，则xtx_t更好地表明短期兴趣，因此其影响力应该增加。如果 △tt\triangle t_t 或 △dt\triangle d_t 较大，则xtx_t 对新细胞c^\hat c 的影响较小。在这种情况下，短期利益是不确定的，所以我们应该更多地依靠长期利益。

4.2 Variation of Coupled Input and Forget Gates

受[15]的启发，我们提出了STGN的另一个版本，名为STGCN，以减少参数数量并提高推荐性能。 STGCN 使用耦合输入和遗忘门，而不是单独决定忘记什么以及添加哪些新信息，如图 5 所示。具体来说，我们删除了遗忘门，并修改了等式： (11) 和 (12) 至

[15] K. Greff, R. K. Srivastava, J. Koutn ık, B. R. Steunebrink, and J. Schmidhuber, “LSTM: A search space odyssey,” IEEE Trans. Neural Netw. Learn. Syst., vol. 28, no. 10, pp. 2222–2232, Oct. 2017.

4.3 POI Context Prediction

由于图可以表示各种类型的交互和关系，因此在 POI 上下文预测中，我们使用广泛用于编码数据之间距离的亲和图来定义 POI 上下文图，将上下文信息编码为实例之间的亲和度。为任意两个POI创建边是一个巨大的工程，所以我们在POI上下文图中设置一个超参数r，以当前POI为圆心，r为半径绘制一个圆形区域。将圆形区域内的POI分类为当前POI的邻居集合，然后将当前POI与其邻居连接起来生成边。如图6，根据中心POI点vbv_b和vdv_d分别绘制两个圆cbc_b和cdc_d。作者在本文中利用Skipgram模型[45]（预测图上的上下文），来建立无监督损失函数，作为正则化。给定一个实例及其上下文，通过实例的嵌入来最小化预测上下文的对数损失。

[45] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean, “Distributed representations of words and phrases and their compositionality,” in Proc. 26th Int. Conf. Neural Inf. Process. Syst., 2013, pp. 3111–3119.

在训练Skipgram模型时，使用流行的负采样方法来采样(vi,vc,γ)(v_i,v_c,\gamma),当γ=1\gamma=1代表正对，否则为负，在我们最小化将(vi,vc)(v_i,v_c)对分类为二进制标签γ\gamma的交叉熵损失之后：

因此，负采样的 POI 上下文侧的无监督损失可以写为：

定义分布p(vi,vc,γ)p(v_i,v_c,\gamma) 的抽样过程遵循[46]处理POI上下文图中的实值边权重并合并负样本。具体来说，我们首先在GG中均匀采样一个根据半径构建的随机游走序列，然后在所有POI中随机采样一个POI并添加到路径中。如果采样的 POI 没有邻居，则会创建另一条路径。否则，对采样 POI 的剩余邻居进行随机采样，直到它们形成长度为 ll 的路径，其中 ll 是最大路径长度。然后，我们从长度大于1的路径中以概率pp采样正对，确保正对中的两个POI可以同时出现在同一个窗口中。窗口大小用ww表示。以概率 (1−p)(1-p)，我们统一破坏上下文以采样负对。根据上述采样过程，形成一条长度为4的路径，如图6 所示。当w=3w = 3时，(va,vd)(v_a,v_d)为正对。

[46] Z. Yang, W. W. Cohen, and R. Salakhutdinov, “Revisiting semisupervised learning with graph embeddings,” in Proc. 33rd Int. Conf. Mach. Learn., 2016, pp. 40–48.

4.4 Joint Learning

NeuNext的完整损失函数如下：

请注意，我们针对两个目标联合训练模型的方式是使用小批量 Adam 执行 SGD（随机梯度下降）。使用[47]中描述的投影算子来满足等式(7)中的约束Wt1≤0W_{t1}≤ 0 和等式（9）中的约束 Wd1≤0W_{d1}≤0 。如果训练过程中 Wt1>0W_{t1} > 0，则设置 Wt1=0W_{t1} = 0。参数 Wd1W_{d1} 也以同样的方式设置。

最后，我们对一批 POI 上下文(vj,vc,γ)(v_j,v_c,\gamma)进行采样去采取另一个梯度步骤来优化无监督损失 LC\mathcal L_C。我们重复上述过程来近似权重因子λ\lambda。

5 EXPERIMENT

数据集：CA、SIN、Gowalla、Brightkite

评估函数：Accuracy@K，MAP

baseline：FPMC-LR、PRME-G、GE、RNN、LSTM、PACE、ST-RNN、HST-LSTM