孙运淼,林锋,周激流
(四川大学计算机学院,成都 610065)
随着移动场景时代的到来,移动设备与社交网络在全球范围内迅速普及、卫星定位与无线通信技术快速发展,不同场景中类型各异的大量移动对象得到了持续和广泛的有效追踪,海量的移动轨迹数据由此得到采集与存储。在这些移动轨迹数据中,蕴藏了指向环境特性、个体行为、社会规律等多方面的丰富信息,有着巨大的学术价值与应用前景。如何根据任务需要从中挖掘出有价值的潜在信息,已经成为了数据挖掘领域中的重要课题。
移动轨迹作为一种时间序列信息,具有数据规模大、规律周期长等特点;作为定位数据,又含有不可避免的误差;再加上对象的自主移动往往受到地理特性、交通规则、社会规律等环境因素的复杂限制,众多的挑战使得传统的移动轨迹研究方法难以高效、灵活地适用于当今海量、多样化的数据挖掘任务。
近年来,随着神经网络技术研究的发展和计算能力、训练数据等资源的丰富,基于深度神经网络的机器学习方法已经在关系分类、图像识别、自然语言处理等应用领域中获得了广泛应用,在诸多问题的标准测试集上都取得了出色的效果。
长短时记忆网络(Long Short-Term Memory,LSTM)是一种应用广泛的新型循环神经网络(Recurrent Neu⁃ral Network,RNN),与传统RNN同样是针对序列数据的处理任务而设计的。为了解决传统RNN中存在的梯度爆炸或耗散(gradient explosion/vanishing)、训练速度慢、远距离学习能力有限等问题,LSTM针对传统RNN中的隐含层单元做出了改进,引入了记忆单元和控制门的结构设计,从而优化了隐含层对输入信息的提取、存储和表达过程,以及错误信号的时域反传过程。与传统RNN相比,LSTM网络对长距离序列特征的学习能力更强、训练效率更高。
在语音、文本、时间序列等许多序列信息学习的领域中,LSTM网络都有着广泛的应用。2006年,文献[1]提出了基于双向LSTM网络的序列标注模型,用于处理未经预分段的连续语音信号序列。2013年,文献[2]提出了用于语音识别的深度LSTM网络,实现从语音信号序列到音素序列的映射,并在标准测试集上取得了state-of-the-art的成绩。文献[3]提出了基于多层LSTM的序列到序列(sequence to sequence)的机器翻译模型。文献[4]在该模型的基础上提出了改进,转而应用于句法分析任务中,并取得了state-of-the-art的成绩。文献[5]将LSTM网络用于检索式的问答系统(question answering system)中,学习问答语句间的匹配模型。文献[6]则提出了用于分析简短的程序代码并给出程序输出的深度LSTM模型,文中将程序代码视作字符序列输入,程序运行的正确结果作为训练目标,对于简单的数值运算程序,预测准确率可达99%文献[7]将LSTM网络与卷积神经网络(Convolutional Neural Networks,CNN)相结合,用于降水量的时空序列的预测。文献[8]将LSTM网络与CNN相结合用于图文转换,该模型首先利用CNN对图像输入进行特征提取,再利用LSTM实现从特征到文本输出的学习。文献[9]则提出了能够直接用于图像处理的4向LSTM网络,且在多个标准测试集上能够取得与传统的CNN方法相近的表现,证明了LSTM在图像处理领域同样有着巨大的潜力。
现有的研究和应用证明,LSTM网络在许多种针对大规模序列信息中的复杂关联和依赖的处理任务中,都能够取得优异的表现。因此,国内外许多研究人员将LSTM网络引入了轨迹数据处理的领域中,用于实现对车辆、行人等移动轨迹的识别或预测,并取得了出色的成果,本文对这些工作进行了简要回顾。
为了解决传统RNN中的梯度爆炸或耗散问题,文献[10]于1997年针对其隐含层单元结构做出了改进,提出了LSTM单元。使用LSTM单元的RNN网络,通常被称作LSTM-RNN网络或LSTM网络。随着相关研究的深入和应用领域的扩展,研究人员针对最初提出的LSTM单元结构提出了许多改进和变体,其中,使用最为广泛的一种结构如图1所示。
一个LSTM单元由一个专门的记忆单元(Memory Cell)和多个调节门(gate)组成其中,记忆单元使用其状态量(state)进行历史信息的存储,与之相连的常数错误传送结构(Constant Error Carousel,CEC)可以使得错误信号在时域反传(Back Propagation Through Time,BPTT)时实现无衰减传播,从而解决传统RNN中梯度爆炸或耗散的问题。输入门(Input Gate)和输出门(Output Gate)用于控制信息的流入与流出,遗忘门(Forget Gate)则用于决定是否重置记忆单元,这3个门的行为将通过上层单元的输出、上一时刻的自身输出以及记忆单元的状态量共同决定。将记忆单元状态量输入到这3个门的连接(图中虚线表示)被称为窥孔连接(Peephole Connections)。
图1 LSTM单元结构
(1)用h来表示整个LSTM隐含层单元的最终输出,c表示记忆单元的状态量,x表示输入数据那么一个LSTM单元对输入数据的处理过程可以表示如下:
(2)计算三个LSTM调节门的值
其中,i,f,o分别代表着输入门、遗忘门和输出门,Wmn,bn分别代表着从m到n的连接权值和n的偏置,σ代表着调节门的激活函数。如上所述,所有调节门的值除了受当前输入数据xt和上一时刻LSTM单元输出ht-1的影响外,还受上一时刻记忆单元值ct-1的影响,即窥孔连接。
(2)计算LSTM记忆单元的状态量更新
其中,⊙表示逐点乘积,t可以称作候选隐含层状态,实际等同于使用一个传统RNN隐含层单元处理将得到的输出。由上式可见,记忆单元的状态值更新取决于t和上一时刻的自身状态ct-1,并通过输入门和遗忘门分别对这两部分信息的流入进行调节。
(3)整个LSTM单元的最终输出为:
其中,σ通常选择Logistic Sigmoid函数,φ,ϕ通常选择tanh函数。这种独立的记忆单元结合多个调节门的设计,使LSTM单元获得了保存、读取、重置和更新长距离历史信息的能力。例如,如果输入门保持关闭(it=0),那么记忆单元不会受到新的输入数据的影响;如果与此同时遗忘门不作用(ft=1),那么记忆单元中的信息就能长时间的一直保存下去,并且通过开放输出门(ot=1)供给下层单元使用。
与传统RNN类似,LSTM网络也使用时域反传算法实现网络参数的训练。在传统RNN中,错误信号的影响随着时间间隔的增长而呈现指数级膨胀或压缩,即梯度爆炸或耗散问题。而在LSTM中,由于记忆单元的自连接边的设计,错误信号能够始终以1的权重在时域上实现稳定传送,因此称作恒定误差传送。
在文献[10]于1997年最初提出的LSTM单元结构中,只包含两个调节门:输入门和输出门。直到1999年,文献[11]才在此基础上引入了遗忘门的设计,允许了状态量的重置,避免其无限制地增长,为模型带来了清除无用的历史信息的能力。
2000年,文献[12]中提出,在调节门的控制中引入记忆模块的参与,可以更好地利用从历史序列中学习到的特征,因此提出了窥孔连接,将记忆单元的状态量也输送到各个调节门。
为了充分利用到整个序列的上下文信息,文献[13]在 2005年将 LSTM与双向 RNN(Bidirectional RNN,BRNN)结合,提出了双向LSTM(BLSTM)。
2014 年,文献[14]提出了 GRU(Gated Recurrent Unit),只包含用于捕捉短期依赖的重置门(Reset Gate)和用于捕捉长期依赖的更新门(Update Gate),并合并了LSTM中的记忆单元和候选隐含层状态。GRU普遍被视作是LSTM的一种简化版本,经实验证明与传统LSTM表现相近但效率更高,因此也成为了最流行的变体之一。
2014年,文献[3]首次将深度神经网络(Deep Neu⁃ral Network,DNN)的框架与LSTM相结合,提出了深度LSTM(deep LSTM)。2015 年,文献[15]和文献[16]分别提出了树状的和层次的LSTM模型,用于自然语言处理任务中。文献[7]在解决降水量的预测问题时,为了同时实现时间维度和空间维度的特征学习,将卷积神经网络(Convolutional Neural Network,CNN)中的卷积算子引入了LSTM的状态量更新过程中,提出了卷积LSTM(Convolutional LSTM,ConvLSTM)。
移动设备的普及和GPS定位技术的发展使得持续广泛的移动对象追踪成为可能,也产生了海量的移动轨迹数据资源。移动轨迹数据的处理有着巨大的研究价值与应用需求,却也面临着数据规模大、时间跨度长等等许多挑战。许多研究人员将LSTM网络作为高效的序列数据处理技术引入了这一领域,提出了任务需求和网络结构各异的大量应用。本文将选取LSTM网络在移动场景中的典型应用,按照移动对象和任务类型进行分类介绍。
文献[17]中采用LSTM网络处理车辆的移动轨迹信息,来实现对车辆行为的识别,用于解决智能交通领域中的驾驶环境检测问题。该算法专注于十字路口附近的交通场景,按照车辆对象的驶来方向和驶去方向(左、右转或直行)规定了12种不同的车辆行为标签,试图利用LSTM网络实现基于这些标签的分类。
算法使用KITTI数据集中的交通图像,映射到路面平面上得到车辆对象的移动轨迹数据,并从中选取出固定长度的输入序列,预提取出四种特征作为LSTM网络的真正输入:线性变化特征、角度变化特征、角度变化特征直方图、鸟瞰图坐标特征。为了更好地学习序列中的时域表征,文献中采用了3层LSTM的结构,如图2所示。
图2 车辆行为识别网络
首层输入的维度由特征数目和特征向量维度决定;在前两层的传播过程中,上述四种特征被分别处理,仅在最后一个LSTM层中,四种特征才得到融合;最后一个LSTM层则接入一个全连接层,最终输出一个代表着这个序列样本的分类概率的向量。
文献[18]同样借助LSTM网络来实现车辆移动轨迹的时域特征学习,用于构建一个由图像感知到行动决策的端到端的自动驾驶模型,网络设计如图3所示。
图3 车辆轨迹预测网络
文中采用全卷积网络(FCN)作为单个时间步中从图像帧到对象位置信息的编码器,编码结果即附近对象在单个时间步中的空间特征表示。经过编码的逐帧空间特征与传感器收集得到的速度和角度信息,以及前一时间步的自身行动决策共同作为网络输入,在时域传播中依序经过一个单层的LSTM网络,从而提取周围对象与自身的移动的时域特征,并做出对移动轨迹的预测,储存在LSTM网络的输出中,算法将其称作状态量(state)。这一代表着对附近车辆和自身做出的轨迹预测的状态量再经过一个全连接层,即可得到在当前移动环境下,各个驾驶决策的可行度。文中使用了真实数据集中的车辆驾驶决策分布作为训练的目标,从而实现基于移动轨迹预测的自动驾驶策略学习。
文献[19]设计了一种双向LSTM网络用于解决行人航位推算中的步态检测问题。该模型是针对室内的行人移动而设计的,使用由惯性测量单元(Inertial Mea⁃surement Unit,IMU)收集得到的角速度和加速度信息,用于表示一个行人在某一时刻的移动状态。移动状态的序列输入网络后,经由LSTM层完成时域特征的提取,最终给出步态标签的概率分布,例如前进、后退、奔跑、步行等。
文中采用了双向的RNN架构,一个完整的移动状态序列将从正反两个方向分别输入到两个独立的隐含层。这样一来,当网络对一组移动样本进行学习时,其反向移动也可以同时被学习到。实验证明,在一个由10个个体的10000个移动序列样本组成的数据集上,该模型的步态检测正确率可达98.5%。
文献[20]设计了一种复杂的LSTM网络用于解决行人的轨迹预测问题。考虑到行人移动的社会性,个体的移动轨迹可能受到同一场景中其他个体的影响。为了赋予LSTM网络捕捉不同个体的轨迹序列之间的依赖关系的能力,文章向传统的LSTM网络中引入了一种称作社会池化层(social pooling layer)的新型结构,将地理位置上邻近的多条轨迹序列各自的LSTM网络连接起来,彼此共享隐含层信息,从而更好的学习到行人轨迹的社会化特征,并用来对下一时刻做出更准确的预测。
首先,Social LSTM(S-LSTM)为场景中的每个行人分配一个传统的LSTM网络,通过学习自身的历史轨迹信息来预测未来的运动。LSTM网络具备储存和学习长距离信息的能力,可以比传统的RNN更好地捕捉到较长时间范围内的个体运动规律;然而对于行人轨迹之间的相互作用以及地理环境对轨迹的影响等社会性规律,这样相互独立的多个LSTM网络结构仍然无法有效的进行学习,因此文中进一步引入了社会池化层。
文中提出的社会池化层接受不同移动对象对应的多个LSTM网络的隐含层输出作为自身的输入,并按照空间范围内划分出的网格和每个移动对象所处的不同位置,对他们的隐含层信息进行池化,池化的结果将输出到下一时刻的LSTM网络,这样就将多个独立的LSTM网络在地理维度上连接在了一起,组成了一个大的S-LSTM网络。其中,算法基于划分的地理网格为移动对象规定了邻域范围,只有位于自身邻域范围内的邻居对象的隐含层信息才会接受该对象的池化;如果有多个邻居对象位于同一网格中,他们的隐含层信息则会被融合。这相当于对社会池化层加入了剪枝操作,限制了其复杂度,在允许邻近节点信息共享的同时,避免了远距节点间冗余的信息传递。
也就是说,不同于传统的独立LSTM网络,在SLSTM网络中,一个运动对象的LSTM层单元除了接收当前时刻的坐标输入和上一时刻的隐含层输入之外,还将通过池化层接收邻近对象的上一时刻隐含层信息作为输入,如图4所示。
图4 Social-LSTM网络
S-LSTM网络的输出,再与一个全连接层相连,得到代表坐标预测的高斯分布参数的矩阵,即可用于下一时刻移动坐标的解码。
在现有的研究中,移动轨迹数据处理主要采用的是GPS定位数据、从图像中识别进而映射得来的坐标或者与移动主体绑定的传感器数据作为网络输入,经过设计各异的LSTM网络实现时域特征的提取,再经过解码得到未来移动轨迹的预测值或移动模式的识别结果。然而,由于移动轨迹自身的数据特性,LSTM网络在这一领域的应用仍然面临着许多挑战:
(1)连续型数值变量
移动轨迹数据的处理通常以连续型数值变量作为对象,而以往的LSTM网络大都是针对离散型变量的处理而设计的。这也就要求在传统LSTM网络设计的基础上,针对连续变量的处理做出适应与改进。
(2)数据预处理
GPS定位数据中包含着不可避免的误差,因此,原始的轨迹数据通常要求首先经过预处理再用于LSTM网络的输入:对定位数据进行平滑去噪,提取出轨迹中的驻留点进而将轨迹转化为驻留点的序列,或直接对轨迹进行显式的特征提取。合适的预处理对于训练效率和效果而言至关重要,也是轨迹数据处理中的关键问题之一。
(3)空间维度特征
轨迹信息不仅具有时序特征,还包含着空间维度的特征,目前已有一些研究者提出了将CNN与RNN结合的网络设计。如何将时间与空间维度的特征学习结合起来,更好地实现对作为时空序列的轨迹信息的学习,也将是未来的研究热点之一。
(4)社会性特征
个体的移动受到环境因素的限制和其他个体的影响,具有社会性的特征和规律。丰富的大数据资源和计算能力使得基于多移动对象的轨迹社会性挖掘成为可能,同时也有着巨大的应用需求和价值。对于一个场景中大量移动对象的轨迹数据,如何实现高效的协同学习,也是极具潜力与挑战的研究课题。
[1]Graves Alex,Fernandez Santiago,Gomez Faustino,et al.Connectionist Temporal Classification:Labelling Unsegmented Sequence Data with Recurrent Neural Networks:International conference on Machine learning,2006[C].2006:369.
[2]Graves Alex,Mohamed Abdelrahman,Hinton Geoffrey E.Speech Recognition with Deep Recurrent Neural Networks:International Conference on Acoustics,Speech,and Signal Processing,2013[C].2013:6645.
[3]Sutskever Ilya,Vinyals Oriol,Le Quoc V.Sequence to Sequence Learning with Neural Networks:Proceedings of the 27th International Conference on Neural Information Processing Systems,2014[C].Montreal,Canada:MIT Press,2014:3104.
[4]Vinyals Oriol,Kaiser Lukasz,Koo Terry,et al.Grammar as a Foreign Language:Neural Information Processing Systems,2015[C].2015:2773.
[5]Wang Di,Nyberg Eric.A Long Short-Term Memory Model for Answer Sentence Selection in Question Answering:ACL,2015[C].2015.
[6]Zaremba Wojciech.Learning to Execute[J].Computing Research Repository,2015,1410.4615.
[7]Shi Xingjian,Chen Zhourong,Wang Hao,et al.Convolutional LSTM Network:a Machine Learning Approach for Precipitation Nowcasting:Neural Information Processing Systems,2015[C].2015:802.
[8]Karpathy Andrej,Feifei Li.Deep Visual-Semantic Alignments for Generating Image Descriptions:Computer Vision and Pattern Recognition,2015[C].2015:3128.
[9]Visin Francesco,Kastner Kyle,Cho Kyunghyun,et al.ReNet:A Recurrent Neural Network Based Alternative to Convolutional Networks[M].Translate.ed[S.l.]:[s.n.],2015.
[10]Hochreiter Sepp,Schmidhuber Jurgen.Long Short-Term Memory[J].Neural Computation,1997,9(8).
[11]Schmidhuber Juergen,Cummins F.Learning to Forget:Continual Prediction with LSTM:International Conference on Artificial Neural Networks,1999[C].1999:850.
[12]Gers F.A.,Schmidhuber J.Recurrent Nets That Time and Count:Proceedings of the IEEE-INNS-ENNS International Joint Conference on Neural Networks.IJCNN 2000.Neural Computing:New Challenges and Perspectives for the New Millennium,2000[C].2000:189.
[13]Graves Alex,Schmidhuber Jurgen.Framewise Phoneme Classification with Bidirectional LSTM and Other Neural Network Architectures[J].Neural Networks,2005,18(5).
[14]Cho Kyunghyun,Van Merrienboer Bart,Gulcehre Caglar,et al.Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation:Empirical Methods in Natural Language Processing,2014[C].2014:1724.
[15]Tai Kai Sheng,Socher Richard,Manning Christopher D.Improved Semantic Representations from Tree-Structured Long Short-Term Memory Networks:Meeting of the Association for Computational Linguistics,2015[C].Beijing,2015:1556.
[16]Li Jiwei,Luong Thang,Jurafsky Dan.A Hierarchical Neural Autoencoder for Paragraphs and Documents:In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing,2015[C].URL,2015:1106.
[17]Khosroshahi A.,Ohn-Bar E.,Trivedi M.M.,et al.Surround Vehicles Trajectory Analysis with Recurrent Neural Networks[J].2016 IEEE 19th International Conference on Intelligent Transportation Systems(Itsc),2016.
[18]Huazhe Xu,Yang Gao,Fisher Yu,et al.End-to-End Learning of Driving Models from Large-Scale Video Datasets[J].arXiv,2016,arXiv:1612.01079.
[19]Edel M.,Koppe E.,Ieee.An Advanced Method for Pedestrian Dead Reckoning using BLSTM-RNNs[M].Translate.ed New York:IEEE,2015.
[20]Alahi A.,Goel K.,Ramanathan V.,et al.Social LSTM:Human Trajectory Prediction in Crowded Spaces[M].Translate.ed New York:IEEE,2016:961