2020-ASRM: A Semantic and Attention Spatio-temporal Recurrent Model for Next Location Prediction
[1] Zhang X, Li B, Song C, et al. SASRM: A Semantic and Attention Spatio-temporal Recurrent Model for Next Location Prediction[C]//2020 International Joint Conference on Neural Networks (IJCNN). IEEE, 2020: 1-8.
文章目录
-
-
Abstract -
关键词 -
1 Introduction -
2 Related Work -
3 Preliminaries -
4 Semantic and Attention Spatio-temporal Recurrent Model -
A 特征嵌入和向量生成B 递归单元C 注意力D 预测
-
5 Experiments -
6 Conclusions
-
Abstract
Predicting user’s next location is of great importance for a wide spectrum of location-based applications. However, most prediction methods do not take advantage of the rich semantic information contained in trajectory data. Meanwhile, the traditional LSTM-based model can not capture the spatio-temporal dependencies well. In this paper, we propose a Semantic and Attention Spatio-temporal Recurrent Model (SASRM) for next location prediction. Firstly, the SASRM put forward a method for encoding semantic vectors and concatenating vectors (location, time and semantic vectors) as input to the model. To capture the spatio-temporal dependencies, we design a variant recurrent unit based on LSTM. Further, an attention layer is used to weight hidden state to capture the influence of the historical locations on the next location prediction. We perform experiments on two real-life semantic trajectory datasets, and evaluation results demonstrate that our model outperforms several state-of-the-art models in accuracy.
- 现有问题：1. 大多数预测方法并
没有充分利用轨迹数据中丰富的语义信息。2. 传统的基于LSTM的模型不能很好地捕捉时空相关性。 - 本文提出了一种语义和注意力时空循环模型(Semantic and Attention Spatio-temporal Recurrent Model，
SASRM)用于下一个位置预测。 - 方法（3个关键点）：首先，
对语义向量进行编码，并将向量(位置、时间和语义向量)连接起来作为模型的输入。为了捕捉时空相关性，我们设计了一个基于LSTM的变分递归单元。在此基础上，利用注意力层对隐藏状态进行加权，以获取历史位置对下一个位置预测的影响。 - 结果：在两个真实生活中的语义轨迹数据集上进行了实验，结果表明SASRM模型在accuracy上优于一些最先进的模型。
关键词
- Location Prediction
- Semantic Trajectory
- Attention
- LSTM
1 Introduction
- 具有丰富的时空语境信息的人的移动轨迹称为
语义轨迹。 语义信息: 例如位置上下文信息(例如餐馆、书店)，正在进行的活动上下文信息(打篮球、跳舞、唱歌)。基于语义轨迹的位置预测的三个挑战及本文的解决方法:1)如何将语义信息编码到预测模型中——解决方法：语义向量。2)如何有效地捕捉轨迹的时空相关性——解决方法：在LSTM的基础上设计变分递归单元（包含time gate和distance gate）。3)如何将历史信息融入回归式模型训练中——解决方法：注意力机制。
2 Related Work
介绍了传统的预测模型和基于神经网络的模型
传统的预测模型（HMM、MF…）基于神经网络的模型（Liu等人提出了ST-RNN (Spatial Temporal RNN)模型，利用RNN单元的时间特异性转移矩阵和距离特异性转移矩阵来增强模型接收时空信息的能力。Zhu等人生成了Time-LSTM模型，用于学习时间间隔的依赖关系。Zhao等人在Time-LSTM的基础上提出了STGN模型。他们设计了一个基于LSTM单元的门回归网络，通过添加时间门和距离门，提高了LSTM模型捕捉时空相关性的能力。…）不足：很少考虑语义、没有捕获到时空依赖性
3 Preliminaries
-
语义地点（Semantic Location）
与通常的地点表示类似，加上了文本信息。{r_k}^{u_i} = (u_i, l_k, t_k, c_k), 其中{u_i}表示User ID, {l_k}表示location，{t_k}表示time, {c_k}表示由LBS或用户提供的文本，包含了语义信息。 -
语义轨迹（Semantic Trajectory）:由语义地点构成的序列 -
LSTM知识如下：
LSTM是RNN的经典变体，用来解决RNN模型的梯度消失问题。与RNN相比，它能够捕捉序列信息的长期依赖性，具有良好的可扩展性。我们可以修改LSTM来提高模型在不同预测任务中的性能。
原LSTM公式见(1)-(6)。
4 Semantic and Attention Spatio-temporal Recurrent Model
语义和注意力时空循环模型(Semantic and Attention Spatio-temporal Recurrent Model，
SASRM)
SASRM模型包括四个主要部分：
- 特征嵌入和向量生成（feature embedding and vector generator）
- 递归单元（recurrent unit）
- 注意力（historical attention）
- 预测（prediction）
A 特征嵌入和向量生成
-
通过嵌入（
embedding）技术生成向量 -
{u_i}表示User ID, {l_k}表示location，{t_k}表示time。 {u_i}、 {l_k}、{t_k}可以
直接编码为嵌入向量 {b_{u_i}}、 {b_{l_k}}、{b_{t_k}}。三个嵌入权重矩阵{B_i}、 {B_k}、{B_k}被随机初始化。初始化公式如(7)-(9).
-
采用一种
语义信息向量嵌入方式sen2vec编码语义向量 -
对于一个包含语义的文本信息c_k，我们使用预先训练的词向量v_{g_k}来表示每个词w。首先，所有词向量v_{g_k}由a和p(w)加权，这里a是预定义参数，默认设置为0.0001。p(w)是该词在语料库中出现的频率。然后通过求和再平均获得向量v_{s_k}(
公式10)。如果p(w)较大(这个词出现了很多次)，向量v_{s_k}中相应的v_{g_k}所占的比例就会较小。这强调了个性化（personalized）的词汇对结果向量的影响。然后利用PCA (主成分分析)来找到\tilde S中的主成分标识\tilde u（公式11）并计算v_{c_k}(公式12)。标识符\tilde S是中间向量v_{s_k}的集合。然后通过v_{c_k}的线性变换得到嵌入向量b_{c_k}（公式13）。注意：最终得到的向量b_{c_k}将保持与{b_{u_i}}、 {b_{l_k}}、{b_{t_k}}相同的维数。自定义维度具有良好的训练效果，并且包含丰富的语义信息。
-
最终，b_{l_k}、 {b_{t_k}}和{b_{c_k}}将
连接起来作为递归层的输入向量。即x_k^S = concat(b_{l_k}, b_{t_k}, b_{c_k})
B 递归单元
▲ 受STGN[20]的启发，我们重新设计了基本的LSTM单元。
▲ 用time interval和distance interval同时接收时间间隔和距离间隔信息。STGN有多个门来捕捉时空依赖关系，而我们只设置一个时间门和一个距离门来获取主要的时空依赖关系。在实验中，我们探索了使用多个门(如STGN)或不使用门，但性能较差。所以我们只使用单独的门来捕获依赖项。时间间隔∆t等于t_{n+1}−t_n。距离间隔∆d等于d(l_{n+1}, l_n)， d(·,·)表示两个位置网格中心之间的地理距离。
▲ 用在SASRM中的递归单元如公式（15）-（23）所示：
-
i_n：input gate
f_n：forget gate
o_n：output gate -
W_i、W_f、W_{\tilde c}、W_o、W_{xt}、W_{xd}：输入向量x_k^S的权重向量
V_i、V_f、V_{\tilde c}、V_o：隐藏层输入向量h_{n-1}的权重向量
W_t、W_{to}、W_d、W_{do}：分别是time interval和distance interval的权重向量 -
b_i、b_f、b_{\tilde c}、b_o、b_{t}、b_{d}：gate向量的bias
-
{\tilde c}_n：中间记忆状态，被用来计算memory state c_n和\hat c_n
-
等式（18）用x_k^S和∆t计算time gate T_n
等式（19）用x_k^S和∆d计算distance gate D_n -
包含\Delta t_n和\Delta d_n依赖信息的记忆状态c_n可以通过公式（20）传递到c_{n+1}, c_{n+2}, …
-
\hat c_n被用来计算隐藏态h_n，见公式（23）
-
\Delta t_n和\Delta d_n参与到o_n的计算中，见公式（22）
⭐这些包含\Delta t_n和\Delta d_n信息的门捕获了用户轨迹中的时空依赖，可以帮助更好地预测用户的下一地点
C 注意力
B中循环单元的目的是捕捉复杂的序列信息和包含在当前的轨迹中的时空相关性。
一个注意力层被设计用来从历史记录中捕捉移动的规律性。它以历史隐藏状态作为输入，输出最相关的上下文向量。
在我们的注意力层中，隐藏态（hidden state）向量 由两个额外的注意力权重矩阵W_{s1}∈R^{e∗e}, W_{s2}∈R^{e∗1}和一个注意力深度d_r(隐藏态h_n的维数是e)加权 。
在公式(24)中，H^i表示需要加权的隐向量[h_{i−d_r}，···，h_{i−1}]部分。如图4和公式(25)所示，H^i用于计算对准加权向量（ alignment weight vector ）α_i。
- 根据对齐加权向量α_i，对H^i进行评分来找到一个新的上下文向量\bar {h_i}。在
公式(26)中，如果i大于注意力深度dr，则\bar {h_i}等于{α_i}^T \cdot H^i; 否则\bar {h_i}等于原隐藏向量h_i。新计算的\bar {h_i}与历史向量[h_{i−d_r}，···，h_{i−1}]相关，从而将历史信息纳入递归模型训练中，增强 历史信息 的作用。
D 预测
为了反映用户的个性化信息，我们添加了用户ID向量b_{u_i}。由于user ID在整个模型的训练过程中不随时间变化，所以它不是输入到循环结构中进行训练，而是添加到线性层的输出中。
- 式(27)表示一个将\bar {h_i}转换到N维向量o_k的线性变换(N为预测的总地点数)。
- 最后，我们将o_k和b_{u_i}相加，作为softmax的输入，得到向量y_k。见式(28)。
我们用交叉熵作为损失函数，用向量y_k计算每个最后地点l_{k+1}的损失值，J为损失值。
在训练中，我们使用RMSprop(随机梯度下降算法的一种变体)和时间反向传播算法(BPTT)来更新SASRM的参数。
5 Experiments
Datasets
-
2个
语义轨迹数据集：New York City(NY)、Los Angeles(LA)
♥注意：语义数据集中每个location有文本描述。 -
将城市划分为网格，每个网格表示一个地点。
Baseline methods
- MF
- LSTM
- SERM（丰富语义的神经网络，运用词袋方法编码语义向量）
- STGN
- SASRM*
性能评价
Acc@K
参数的影响
- 不同的hidden vector的大小
- 不同的grid size
6 Conclusions
⭐提出了一种语义和注意力时空递归模型(SASRM)用于下一个位置预测。
⭐在向量生成部分，我们采用sen2vec方法对语义向量进行编码，并将位置、时间和语义向量连接起来作为模型输入。
⭐递归单元部分，设计了一个基于LSTM的变体递归单元，以方便捕捉时空相关性。
⭐然后添加了一个注意力层，将历史信息整合到递归模型训练中。
🔺在两个真实生活中的语义轨迹数据集上的实验结果表明，SASRM在准确性上优于几个最先进的模型。
❀在未来的工作中，我们希望考虑如何将注意力机制与用户习惯相结合，进一步提高用户下一个位置的预测精度。