譚海寧 姚 迪 畢經(jīng)平③ 向 徐 楊 嘯

(*中國(guó)科學(xué)院大學(xué) 北京100049)

(**中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京100190)

(***盲信號(hào)處理國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室 成都610041)

0 引言

隨著各種具有定位服務(wù)的移動(dòng)設(shè)備的普及,基于位置服務(wù)的移動(dòng)社交網(wǎng)絡(luò)(location-based social network,LBSN)發(fā)展迅速,具有位置信息的用戶數(shù)據(jù)呈爆發(fā)式增長(zhǎng),如Foursqure、Yelp、美團(tuán)等電商服務(wù)平臺(tái)[1-2]。有效地利用具有位置信息的用戶數(shù)據(jù),探索用戶興趣點(diǎn)(point of interest,POI)已經(jīng)成為移動(dòng)社交網(wǎng)絡(luò)數(shù)據(jù)挖掘領(lǐng)域的重要研究方向。其中,由于推薦系統(tǒng)是解決信息過(guò)濾和個(gè)性化服務(wù)問(wèn)題的主要手段之一,其在用戶位置挖掘服務(wù)中發(fā)揮著重要作用,面向用戶興趣點(diǎn)的推薦方法研究也成為移動(dòng)社交網(wǎng)絡(luò)挖掘領(lǐng)域的重中之重[3-5]。

興趣點(diǎn)表示用戶感興趣的已經(jīng)訪問(wèn)或?qū)?huì)訪問(wèn)的地理位置[1-2,6-7]。推薦的潛在興趣點(diǎn)表示用戶在將來(lái)某個(gè)時(shí)間點(diǎn)可能會(huì)訪問(wèn)的地理位置。作為面向位置服務(wù)的移動(dòng)社交網(wǎng)絡(luò)數(shù)據(jù)挖掘領(lǐng)域的重要分支,POI 推薦可以預(yù)測(cè)用戶行為和興趣演化趨勢(shì),對(duì)城市交通的規(guī)劃和商業(yè)模式的探索具有重要的現(xiàn)實(shí)意義。POI 推薦有著廣泛的應(yīng)用,例如大眾點(diǎn)評(píng)網(wǎng)站的餐廳推薦[4]、旅游路線規(guī)劃[5]、城市交通事件預(yù)警[8-9]等。

當(dāng)前大多數(shù)的POI 推薦方法都假設(shè)POI 數(shù)據(jù)是同分布的,將POI 數(shù)據(jù)看成一個(gè)整體進(jìn)行用戶POI興趣的挖掘工作,比如STRNN[1]、DeepMove[10]、STLSTM[11]等。這些方法將用戶的簽到POI 數(shù)據(jù)看成一個(gè)整體,沒(méi)有考慮軌跡數(shù)據(jù)的城市不均衡特性,缺乏對(duì)城市之間共性信息和城市本身特殊性信息進(jìn)行區(qū)分的個(gè)性化建模,這樣導(dǎo)致在數(shù)據(jù)匱乏的城市,由于POI 歷史記錄少,對(duì)用戶進(jìn)行推薦難度大、效率低。本文分析了Foursqure 收集的截止到2014 年1月的用戶簽到POI 數(shù)據(jù)的全球位置數(shù)據(jù)。從數(shù)據(jù)分布可以看出受到采集手段、隱私保護(hù)等因素的影響,用戶POI 簽到數(shù)據(jù)在城市之間分布極其不均衡。北美、歐洲及各大洲沿海發(fā)達(dá)城市POI 數(shù)據(jù)分布比較集中,其他城市POI 數(shù)據(jù)分布非常稀疏。

因此,亟需探索如何在數(shù)據(jù)匱乏的城市進(jìn)行POI 推薦的有效方法[12-14]。針對(duì)如何解決數(shù)據(jù)匱乏的問(wèn)題,有少量的工作通過(guò)關(guān)聯(lián)相關(guān)用戶在目標(biāo)城市外的歷史信息進(jìn)行推薦,比如JIM[15]和JFT[16]。這些工作都是基于源城市和目標(biāo)城市之間存在共同用戶的前提下,將關(guān)聯(lián)用戶在源城市的行為信息進(jìn)行遷移,完成關(guān)聯(lián)用戶在目標(biāo)城市的POI 興趣發(fā)現(xiàn)和推薦任務(wù)。這類方法受限于事先設(shè)定的影響因素,無(wú)法對(duì)隱含因素進(jìn)行建模,并且在城市之間的信息共享受共同用戶這一假設(shè)制約,導(dǎo)致推薦方法應(yīng)用范圍受限,推薦效果不佳。

本文為了緩解數(shù)據(jù)分布不均衡等因素給POI 推薦帶來(lái)的影響,借助于元學(xué)習(xí)[17]的思想,通過(guò)將數(shù)據(jù)豐富城市的泛化共性移動(dòng)知識(shí)進(jìn)行學(xué)習(xí)并遷移應(yīng)用到數(shù)據(jù)匱乏城市的POI 推薦任務(wù)中。與此同時(shí),由于采集的POI 數(shù)據(jù)的時(shí)間點(diǎn)并不是嚴(yán)格規(guī)整的,即并不是按照固定的時(shí)間間隔進(jìn)行采集,這就造成POI 數(shù)據(jù)之間時(shí)間間隔的不確定性。傳統(tǒng)的序列化建模方法將時(shí)間間隔分割成不同的時(shí)間槽或者直接按照先后順序進(jìn)行建模,忽略了POI 序列之間的連續(xù)時(shí)間信息,因此序列推薦效果受到嚴(yán)重制約。文獻(xiàn)[18]在其工作Neural-ODE 中指出了在序列化推薦任務(wù)中,連續(xù)時(shí)間建模對(duì)推薦效果的性能有明顯提升,并提出了可以進(jìn)行連續(xù)時(shí)間建模的新的深度網(wǎng)絡(luò),即神經(jīng)常微分方程。神經(jīng)常微分方程使用神經(jīng)網(wǎng)絡(luò)參數(shù)化隱藏狀態(tài)的導(dǎo)數(shù),而不是直接參數(shù)化隱藏狀態(tài)。這里參數(shù)化隱藏狀態(tài)的導(dǎo)數(shù)就類似構(gòu)建了連續(xù)性的層級(jí)與參數(shù),而不再是離散的層級(jí)。因此參數(shù)也是一個(gè)連續(xù)的空間,不需要再分層傳播梯度與更新參數(shù),這樣可以更加高效地進(jìn)行連續(xù)時(shí)間建模。本文受神經(jīng)常微分方程[18]的啟發(fā),提出了基于元學(xué)習(xí)的時(shí)空神經(jīng)常微分方程(meta-learning based ordinary differential nural network,ML-ODE)進(jìn)行有效的POI 推薦。

本文的主要貢獻(xiàn)如下。

(1) 借助于神經(jīng)常微分方程實(shí)現(xiàn)了對(duì)POI 數(shù)據(jù)的連續(xù)時(shí)間序列建模,可以忽略傳統(tǒng)方法對(duì)輸入數(shù)據(jù)的時(shí)間間隔的約束。

(2) 在神經(jīng)常微分方程中融入時(shí)空注意力機(jī)制,借助注意力機(jī)制衡量不同時(shí)刻的簽到行為與用戶偏好的相關(guān)性,進(jìn)而獲得不同簽到行為的權(quán)重系數(shù)。

(3) 提出了基于元學(xué)習(xí)機(jī)制的POI 序列推薦框架,實(shí)現(xiàn)了將泛在共性移動(dòng)知識(shí)從數(shù)據(jù)豐富城市遷移到數(shù)據(jù)匱乏城市。

(4) 在真實(shí)數(shù)據(jù)集上進(jìn)行了大量實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,本文提出的POI 推薦算法可以有效地對(duì)數(shù)據(jù)匱乏城市的目標(biāo)用戶進(jìn)行POI 推薦。

本文結(jié)構(gòu)如下:第1 節(jié)介紹了面向位置社交網(wǎng)絡(luò)POI 推薦的相關(guān)工作,包括基于矩陣分解和基于深度學(xué)習(xí)的相關(guān)方法;第2 節(jié)介紹了本文使用的基本符號(hào)和相關(guān)問(wèn)題定義,并詳細(xì)描述了本文提出的POI 推薦框架ML-ODE;第3 節(jié)通過(guò)實(shí)驗(yàn)對(duì)本研究中提出的方法進(jìn)行了有效驗(yàn)證,并報(bào)告相關(guān)的實(shí)驗(yàn)結(jié)果;第4 節(jié)對(duì)本文的工作進(jìn)行了總結(jié)并展望該技術(shù)的未來(lái)發(fā)展方向。

1 相關(guān)工作

本節(jié)詳細(xì)介紹了目前主流的面向位置社交網(wǎng)絡(luò)的POI 推薦方法以及與神經(jīng)常微分方程相關(guān)的最新研究成果。目前,POI 推薦方法主要可以分為面向單城市的POI 推薦方法和跨城市的POI 推薦方法。

面向單城市的POI 推薦方法,主要有FPMC[19]、STRNN[1]、DeepMove[10]、AT-LSTM[20]等。FPMC 通過(guò)引入基于馬爾可夫鏈的個(gè)性化轉(zhuǎn)移矩陣,進(jìn)行時(shí)間信息和用戶的長(zhǎng)期興趣偏好的捕捉,同時(shí)為了解決轉(zhuǎn)移矩陣的稀疏局限性,引入了矩陣分解模型,可以減少參數(shù)并提高POI 推薦效果。但是由于馬爾可夫鏈的不同影響因素之間的獨(dú)立性假設(shè),并且受矩陣分解類方法冷啟動(dòng)的影響,該類方法具有一定的局限性。STRNN 通過(guò)擴(kuò)展循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural network,RNN)[21]提出了一種時(shí)空循環(huán)神經(jīng)網(wǎng)絡(luò)模型,該方法通過(guò)引入時(shí)間轉(zhuǎn)移矩陣和空間距離轉(zhuǎn)移矩陣分別建模局部時(shí)間上下文和空間上下文,通過(guò)設(shè)置不同的窗口確定恰當(dāng)?shù)臅r(shí)空上下文鄰居,分別計(jì)算時(shí)間距離tdis和空間距離ldis來(lái)作為轉(zhuǎn)移矩陣的輸入,規(guī)整后統(tǒng)一輸入循環(huán)神經(jīng)網(wǎng)絡(luò)。DeepMove 提出了一種基于注意力機(jī)制的多模態(tài)循環(huán)神經(jīng)網(wǎng)絡(luò),首先通過(guò)門(mén)控循環(huán)單元(gated recurrent unit,GRU)層建模用戶即時(shí)偏好;其次通過(guò)歷史注意力機(jī)制模塊對(duì)用戶的歷史偏好進(jìn)行建模;最后通過(guò)整合多層注意力機(jī)制提升用戶移動(dòng)模式預(yù)測(cè)效果。AT-LSTM 在長(zhǎng)短期記憶網(wǎng)絡(luò)(long short-term memory,LSTM)的基礎(chǔ)上借助注意力機(jī)制進(jìn)行時(shí)空信息長(zhǎng)期偏好和短期偏好的捕捉,提升了推薦效果。

該類方法將用戶的簽到POI 數(shù)據(jù)看成一個(gè)整體,沒(méi)有考慮軌跡數(shù)據(jù)的城市不均衡特性,缺乏對(duì)城市之間共性和城市本身特殊性的區(qū)分性建模,這導(dǎo)致在數(shù)據(jù)匱乏的城市POI 推薦效率低下。

面向跨城市POI 推薦的方法主要有JIM[15]、STLDA[22]、CTLM[23]等。文獻(xiàn)[15]提出了一種可以用于跨城市的POI 推薦的圖模型JIM,通過(guò)聯(lián)合考慮POI 內(nèi)容、check-in 時(shí)間、POI 地理位置以及POI 的流行度等因素,實(shí)現(xiàn)跨城市推薦。ST-LDA 是JIM 工作的擴(kuò)展,增加了對(duì)用戶在不同城市的興趣漂移因素的建模,通過(guò)疊加用戶的自身興趣偏好和用戶在某城市的興趣偏移實(shí)現(xiàn)對(duì)目標(biāo)用戶的個(gè)性化POI 推薦。文獻(xiàn)[23]提出了一種基于共同話題遷移學(xué)習(xí)模型的跨城市POI 推薦模型,該方法將城市的POI按照各自屬性信息分為城市間共有類(common topics)和城市內(nèi)私有類(city-specific topics),將用戶在別的城市與共有類的交互信息遷移到目標(biāo)城市。

該類方法都是基于源城市和目標(biāo)城市之間存在共同用戶的前提下,將關(guān)聯(lián)用戶在源城市的行為信息進(jìn)行遷移,導(dǎo)致推薦方法應(yīng)用范圍受限,推薦效果不佳。

神經(jīng)常微分方程在模型訓(xùn)練的過(guò)程中,不使用其他RNN 以及卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural network,CNN)等直接參數(shù)化隱藏狀態(tài)的處理方式,直接使用神經(jīng)網(wǎng)絡(luò)參數(shù)化隱藏狀態(tài)的導(dǎo)數(shù)。因此,神經(jīng)常微分方程的參數(shù)可以看成一個(gè)連續(xù)的空間,不再需要分層進(jìn)行梯度傳播并更新參數(shù)。目前針對(duì)神經(jīng)常微分方程的工作還相對(duì)較少,主要有面向時(shí)序序列建模的Neural-ODE[18,24]、GRU-ODE[25]等。文獻(xiàn)[18]提出神經(jīng)常微分方程N(yùn)eural-ODE,這是一種新的深度神經(jīng)網(wǎng)絡(luò),借助于常微分方程實(shí)現(xiàn)對(duì)序列數(shù)據(jù)的連續(xù)建模。GRU-ODE 結(jié)合Neural-ODE 和GRU 進(jìn)行時(shí)間序列的連續(xù)性建模,根據(jù)輸入離散的時(shí)間點(diǎn)觀察值,通過(guò)GRU-Bayes 模塊更新Neural-ODE 之間的隱狀態(tài)向量。

該類方法目前還沒(méi)有用來(lái)建模POI 數(shù)據(jù),并且不能直接遷移應(yīng)用于跨城市POI 推薦應(yīng)用中。

針對(duì)現(xiàn)存POI 推薦方法存在的問(wèn)題,本文提出了基于神經(jīng)常微分方程的跨城市POI 推薦方法,將數(shù)據(jù)豐富城市的泛化共性行為知識(shí)遷移到數(shù)據(jù)匱乏的目標(biāo)城市,不僅緩解了目標(biāo)城市的數(shù)據(jù)匱乏問(wèn)題,也實(shí)現(xiàn)了對(duì)序列數(shù)據(jù)的連續(xù)性建模。

2 時(shí)空神經(jīng)常微分方程

本節(jié)將介紹所提出的面向數(shù)據(jù)匱乏環(huán)境的下一個(gè)POI 推薦方法。

2.1 基本定義

對(duì)位置社交網(wǎng)絡(luò)中的用戶進(jìn)行POI 推薦時(shí),通常用數(shù)值或者向量來(lái)表示網(wǎng)絡(luò)中的實(shí)體。例如,在描述用戶簽到數(shù)據(jù)時(shí),簽到地點(diǎn)用經(jīng)緯度數(shù)值二元組進(jìn)行記錄,時(shí)間用數(shù)值進(jìn)行記錄,用戶的屬性信息也會(huì)轉(zhuǎn)換成屬性向量進(jìn)行表示。本文研究的問(wèn)題是如何構(gòu)建一個(gè)合適的用戶POI 興趣學(xué)習(xí)模型,借助用戶的歷史簽到記錄,為其更好地進(jìn)行POI 推薦。在詳細(xì)描述POI 推薦算法之前,先給出一些基本的符號(hào)解釋和定義。

定義1興趣點(diǎn)(POI)[22]。在位置社交網(wǎng)絡(luò)中,一個(gè)興趣點(diǎn)表示某一地理位置,通常由一對(duì)地理經(jīng)緯度坐標(biāo)以及相關(guān)的屬性信息表示。

定義2簽到行為(check-in activity)[22]。在位置社交網(wǎng)絡(luò)中,用戶u的簽到行為記錄可以看成一個(gè)三元組,這里可以形式化為

定義3簽到序列(check-in sequence)。在位置社交網(wǎng)絡(luò)中,某用戶u的簽到序列由該用戶一系列的歷史簽到行為構(gòu)成,可以形式化為

其中,k表示用戶u的歷史簽到行為總數(shù)。為了方便,所有用戶的歷史簽到序列可以形式化為

這里,U表示用戶集合。

定義4下一個(gè)POI 推薦(next POI recommendation)。給定用戶簽到數(shù)據(jù)匱乏的目標(biāo)城市集合D=,用戶簽到數(shù)據(jù)豐富的源城市集合S=S′1,S′2,S′3,…,S′N,滿足:

本文的目標(biāo)是為目標(biāo)城市D′m中的用戶u推薦其下一個(gè)可能感興趣的,可以將推薦過(guò)程形式化為

其中,f表示POI 推薦模型,θ表示模型相關(guān)參數(shù),模型整體框架圖如圖1 所示。

圖1 面向數(shù)據(jù)匱乏環(huán)境的下一個(gè)POI 推薦框架

2.2 基于時(shí)空注意力機(jī)制的神經(jīng)常微分方程

本小節(jié)將介紹提出的基于注意力機(jī)制的時(shí)空模型ST-ODE。如圖2 所示,在給定用戶u的一條軌跡,ST-ODE 首先獲取每一條簽到記錄的表征向量,然后通過(guò)時(shí)空神經(jīng)常微分方程建模軌跡序列的時(shí)空影響,最后通過(guò)時(shí)空注意力機(jī)制獲取u在tk+1時(shí)刻的狀態(tài)向量。接下來(lái),將分別介紹簽到行為表征、時(shí)空神經(jīng)常微分方程以及時(shí)空注意力機(jī)制3 個(gè)模塊。

2.2.1 簽到行為表征

在表征模塊中,利用一個(gè)嵌入層獲取簽到行為序列中每一個(gè)簽到行為的表征向量,如圖1 所示。在特征層面,僅考慮POI 的類別、POI 位置以及時(shí)間戳3 類特征,即(ck,lk,tk)。其中ck表示該簽到行為所在POI 的所屬類別,lk表示該P(yáng)OI 的所在位置,由經(jīng)緯度坐標(biāo)表示,tk表示發(fā)生該簽到行為的時(shí)間點(diǎn)。

(1) 針對(duì)POI 類別屬性ck,引入矩陣Ec∈,其中,N表示POI 的類別數(shù),dc表示POI 類別表征向量的維度,這里矩陣Ec在多個(gè)城市之間進(jìn)行共享。

(2) 針對(duì)POI 地理位置屬性lk,引入矩陣El∈?M×dl,其中,M表示POI 的個(gè)數(shù),dl表示POI 位置屬性表征向量的維度,通過(guò)經(jīng)緯度坐標(biāo)位置的Geo-Hash 編碼來(lái)初始化POI 矩陣El。

(3) 針對(duì)時(shí)間戳tk,引入矩陣,其中168 表示將一周分成168 個(gè)時(shí)間槽(7 ×24 h),每一個(gè)時(shí)間槽的表征向量維度為dt。

針對(duì)每一條簽到記錄,將3 類特征的表征向量進(jìn)行拼接,可以獲得長(zhǎng)度為d的表征向量rk,其中,d=dc+dl+dt作為后續(xù)時(shí)空神經(jīng)常微分方程的輸入。

2.2.2 時(shí)空神經(jīng)常微分方程

在進(jìn)行連續(xù)時(shí)間序列建模方面,本文借鑒文獻(xiàn)[25]中的GRU-ODE 方法,如圖2 所示。針對(duì)輸入的簽到記錄表征向量rk,通過(guò)基于GRU 的ODE層進(jìn)行簽到行為之間的連續(xù)時(shí)間狀態(tài)傳播(傳播層,Prop-ODE),即將隱狀態(tài)hk-1從時(shí)刻tk-1轉(zhuǎn)移到時(shí)刻tk,可以形式化為

圖2 基于時(shí)空注意力機(jī)制的神經(jīng)常微分方程框架圖

通過(guò)一層GRU 層在觀察點(diǎn)進(jìn)行簽到行為的更新(更新層,Update-GRU)。針對(duì)用戶斷斷續(xù)續(xù)的簽到行為,需要在觀察到簽到行為的時(shí)間點(diǎn)對(duì)隱狀態(tài)進(jìn)行更新。在本更新層中,針對(duì)給定的簽到行為的表征向量rk,在時(shí)間點(diǎn)tk,可以通過(guò)式(2)進(jìn)行更新。

其中,ht-k和ht+k表示在時(shí)刻tk經(jīng)歷更新層前后的隱狀態(tài)。在本文中,GRU 沿用文獻(xiàn)[26]的工作,具體的公式推導(dǎo)過(guò)程在這里不再贅述。

由上述時(shí)空神經(jīng)常微分方程可以看出,構(gòu)造目標(biāo)函數(shù)時(shí)主要分為兩部分。在Prop-ODE 層,需要考慮經(jīng)過(guò)傳播后的隱狀態(tài)與觀察值之間的分布差異,這里損失函數(shù)可以表示為

其中,f表示一個(gè)全連接層將隱狀態(tài)向量hk轉(zhuǎn)換成一個(gè)D維向量,pPre表示根據(jù)隱狀態(tài)向量推斷的該時(shí)刻在所有POI 上的概率分布,vk∈?D×1表示當(dāng)前觀察點(diǎn)的的one-hot 表征向量。

用ppost表示在應(yīng)用Update-GRU 之后預(yù)測(cè)的概率分布,則損失函數(shù)可以定義為

2.2.3 時(shí)空注意力機(jī)制

從直覺(jué)上來(lái)說(shuō),并非所有的歷史簽到都與用戶的下一步行為密切相關(guān),即需要更加注意用戶信息偏好。但是,標(biāo)準(zhǔn)的神經(jīng)常微分方程GRU-ODE 網(wǎng)絡(luò)無(wú)法檢測(cè)其輸入的哪一部分對(duì)下一個(gè)POI 推薦至關(guān)重要。因此本文引入注意力機(jī)制,并提出了一種基于時(shí)空注意力的神經(jīng)常微分網(wǎng)絡(luò)來(lái)解決上述問(wèn)題。時(shí)空注意力機(jī)制旨在捕獲下一步用戶行為與過(guò)去簽到行為之間的不同關(guān)聯(lián)度。通過(guò)使用注意力機(jī)制,ST-ODE 還可以幫助選擇用戶喜好的代表性簽到行為,并為他們分配不同的權(quán)重。因此,可以更好地集成用戶的歷史簽到行為表征,以有效地描述用戶的興趣偏好。

如圖2 所示,引入矩陣H∈?d×k包含ST-ODE在所有評(píng)估點(diǎn)的隱狀態(tài)向量,這里d表示隱狀態(tài)向量的維度,k表示用戶簽到序列的長(zhǎng)度。ST-ODE 借助于注意力權(quán)重向量α來(lái)進(jìn)行歷史軌跡隱狀態(tài)向量{ht+i} 的整合,可以形式化為

其中,αi表示第i條記錄與下一步的簽到行為的匹配程度,可以通過(guò)下式進(jìn)行權(quán)重矩陣的計(jì)算:

其中,g(ht+i,eu) 為注意力函數(shù),本文使用點(diǎn)積注意力來(lái)進(jìn)行注意力的計(jì)算,可以形式化為

式中,eu表示用戶u的上下文向量。本文根據(jù)用戶訪問(wèn)過(guò)的POI 的類別(category)信息進(jìn)行eu的初始化,,wi表示類別權(quán)重,ei,c表示在第i條簽到行為所在POI 的類別表征向量。在訓(xùn)練過(guò)程中,將其和參數(shù)進(jìn)行同步更新。這里損失函數(shù)的構(gòu)建與在2.3 節(jié)中的在目標(biāo)城市進(jìn)行調(diào)優(yōu)的損失函數(shù)一樣,可以形式化為

具體推導(dǎo)過(guò)程參照2.3 節(jié),對(duì)一個(gè)含有K條記錄的用戶u來(lái)說(shuō),ST-ODE 的整體損失可以定義為

其中,γ和τ表示加權(quán)目標(biāo)函數(shù)的權(quán)重參數(shù)。

將ST-ODE 模型整體算法總結(jié)如算法1 所示。

2.3 移動(dòng)行為知識(shí)遷移機(jī)制

本小節(jié)將介紹提出的基于元學(xué)習(xí)的移動(dòng)知識(shí)遷移方法,借助于元學(xué)習(xí)將數(shù)據(jù)豐富城市的移動(dòng)行為知識(shí)遷移到數(shù)據(jù)匱乏城市。

城市的移動(dòng)行為模式隨著時(shí)間的推移而發(fā)生變化,并且城市與城市之間也各不相同。但是,不同城市之間的用戶也存在著諸多的共性,比如大家在上午都習(xí)慣于打卡咖啡店,在打卡完運(yùn)動(dòng)場(chǎng)之后可能更喜歡打卡餐廳。所以,可以將來(lái)自于多個(gè)城市的共性行為知識(shí),比如空間鄰近性和時(shí)間依賴性等,遷移到目標(biāo)城市。

圖3 為基于元學(xué)習(xí)的時(shí)空常微分方程的參數(shù)更新過(guò)程。將? 作為時(shí)空神經(jīng)常微分方程的參數(shù)集合,因此? 的相關(guān)參數(shù)中便隱含了時(shí)空移動(dòng)知識(shí)。所以只需要傳遞更新參數(shù)? 便可以實(shí)現(xiàn)共性行為知識(shí)的遷移。這里沿用元學(xué)習(xí)的思想來(lái)進(jìn)行ST-ODE 的參數(shù)學(xué)習(xí),針對(duì)式(11),可以通過(guò)式(12)進(jìn)行初始參數(shù)的更新。

圖3 基于元學(xué)習(xí)的參數(shù)優(yōu)化框架圖

其中,?0為ST-ODE 的參數(shù)初始值,Lsi(f?) 表示ST-ODE 在源城市數(shù)據(jù)集Si上的訓(xùn)練損失值。如在框架圖中的每個(gè)源城市中,本文將會(huì)迭代更新參數(shù)。比如在數(shù)據(jù)集Si中,按照式(13) 進(jìn)行參數(shù)更新。

由于模型的目標(biāo)是為數(shù)據(jù)匱乏城市的用戶進(jìn)行POI 推薦,所以需要針對(duì)目標(biāo)城市進(jìn)行參數(shù)優(yōu)化。首先直接將在基于元學(xué)習(xí)的初始參數(shù)學(xué)習(xí)機(jī)制中學(xué)習(xí)到的初始參數(shù)?0遷移到目標(biāo)城市Di;其次,在參數(shù)優(yōu)化過(guò)程中,根據(jù)ST-ODE 的輸出時(shí)刻tk+1的狀態(tài)向量hk+1,可以通過(guò)式(14)計(jì)算用戶下一時(shí)刻tk+1會(huì)訪問(wèn)某候選POIvi的概率。

其中,f() 表示表征函數(shù),獲取POI 的相關(guān)特征的表征向量,pvi表示用戶在POIvi上的概率值。

在推薦過(guò)程中,通過(guò)argmaxv(p) 為用戶推薦最有可能訪問(wèn)的POIv。在訓(xùn)練過(guò)程中,參照BPR-Loss的個(gè)性化排名損失訓(xùn)練方式[27]進(jìn)行推薦任務(wù)損失函數(shù)的構(gòu)建:

其中,v+表示用戶訪問(wèn)過(guò)的POI;v-表示到目前為止用戶沒(méi)有訪問(wèn)過(guò)的POI;σ表示非線性函數(shù),即σ(x)=1/(1+e-x)。因此在目標(biāo)城市的參數(shù)訓(xùn)練過(guò)程中,損失函數(shù)可以重新定義為

同時(shí),在目標(biāo)城市中,參數(shù)?Di的更新過(guò)程可以改寫(xiě)為

在實(shí)際的更新參數(shù)過(guò)程中根據(jù)情況進(jìn)行多次迭代,最終獲得具有普適性的初始參數(shù)。知識(shí)遷移部分算法如算法2 所示。

2.4 復(fù)雜度分析

基于時(shí)空神經(jīng)常微分方程的推薦方法是否能夠進(jìn)行實(shí)際應(yīng)用的關(guān)鍵在于算法的時(shí)間復(fù)雜度,在這里對(duì)ML-ODE 的時(shí)間復(fù)雜度進(jìn)行詳細(xì)分析。在對(duì)多個(gè)時(shí)間序列進(jìn)行批處理過(guò)程中,對(duì)所有時(shí)間序列的觀測(cè)時(shí)間進(jìn)行排序,對(duì)于每個(gè)唯一時(shí)間點(diǎn)tk,創(chuàng)建一個(gè)具有觀測(cè)值的時(shí)間序列的列表用于后續(xù)模塊。ML-ODE 的時(shí)空開(kāi)銷主要存在于表征向量獲取以及推薦排名兩部分。在表征向量獲取方面,MLODE 的主循環(huán)在時(shí)序列表唯一的時(shí)間點(diǎn)上進(jìn)行迭代,在Prop-ODE 步驟中,針對(duì)單個(gè)列表,傳播所有隱藏狀態(tài),時(shí)間復(fù)雜度為O(|?Prop-ODE|),這里|?Prop-ODE| 表示Prop-ODE 模塊的參數(shù)量,Update-GRU 更新和損失計(jì)算也是僅對(duì)在特定具有觀測(cè)值的時(shí)間序列執(zhí)行,時(shí)間復(fù)雜度為O(|?Update-GRU|),| ?Update-GRU| 表示Update-GRU 模塊的參數(shù)量;在推薦排名部分,時(shí)間復(fù)雜度為O(d2),這里d表示表征向量的維度為常量,因此ML-ODE 的整體時(shí)間復(fù)雜度為O(|?|),|?|表示狀態(tài)向量獲取模塊的整體參數(shù)量,可以應(yīng)用于較大規(guī)模POI 推薦任務(wù)中。

3 實(shí)驗(yàn)與結(jié)果分析

本節(jié)將詳細(xì)介紹實(shí)驗(yàn)的數(shù)據(jù)集及相關(guān)實(shí)驗(yàn)過(guò)程,對(duì)比不同推薦模型和方法在公開(kāi)數(shù)據(jù)集上的POI 推薦效果,并詳細(xì)分析各類模型的性能表現(xiàn)。

3.1 數(shù)據(jù)來(lái)源

本文使用的數(shù)據(jù)集來(lái)自于Foursqure[28]。Foursqure 是在位置社交網(wǎng)絡(luò)領(lǐng)域的一個(gè)大規(guī)模的社交網(wǎng)站,允許用戶在不同的地理位置進(jìn)行簽到行為(check-ins),本文使用2012 年9 月到2013 年9 月之間Foursqure 公開(kāi)的去隱私化的用戶全球規(guī)模簽到數(shù)據(jù)集。據(jù)統(tǒng)計(jì),這個(gè)數(shù)據(jù)集包含33 278 683 條用戶簽到數(shù)據(jù),涵蓋用戶量為266 909,POI 數(shù)量為3 680 126(涉及全球77 個(gè)國(guó)家中的415 個(gè)城市)。在這415 個(gè)城市中,每個(gè)城市至少包含10 000 以上的簽到數(shù)據(jù)。本文列舉了幾個(gè)在實(shí)驗(yàn)過(guò)程中整理的城市簽到數(shù)據(jù)樣例,如表1 所示。圖4 和圖5 展示了數(shù)據(jù)集統(tǒng)計(jì)表中東京和舊金山(SF)的城市POI分布熱力圖,可以看出城市間之間POI 分布極不均衡。

圖4 東京POI 分布熱力圖

圖5 舊金山POI 分布熱力圖

表1 城市簽到數(shù)據(jù)統(tǒng)計(jì)

在實(shí)驗(yàn)評(píng)估過(guò)程中,按照用戶的平均簽到條目數(shù)來(lái)區(qū)分?jǐn)?shù)據(jù)豐富城市和數(shù)據(jù)匱乏城市,在這里分別指定洛杉磯(LA)和舊金山為數(shù)據(jù)匱乏城市,其余城市劃分為數(shù)據(jù)豐富城市。為了驗(yàn)證本文方法在數(shù)據(jù)匱乏區(qū)域的效果,在數(shù)據(jù)匱乏城市只使用1 個(gè)月的POI 數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。除此之外,在實(shí)際評(píng)估過(guò)程中,按照7 ∶1 ∶2 的比例劃分訓(xùn)練集、驗(yàn)證集和測(cè)試集。

3.2 對(duì)比方法

本文實(shí)驗(yàn)中選取了目前比較流行的效果較好的POI 推薦模型,主要通過(guò)命中率(HR)和歸一化折損累計(jì)收益(NDCG)等指標(biāo)來(lái)進(jìn)行各類算法的實(shí)驗(yàn)對(duì)比,下面概述在本文中對(duì)比的主流算法。

MF-BPR[27]:該算法提出了一種基于貝葉斯的改進(jìn)矩陣分解模型,主要是通過(guò)貝葉斯的個(gè)性化排序來(lái)優(yōu)化MF[29],通過(guò)建模用戶訪問(wèn)過(guò)的POI 數(shù)據(jù)來(lái)建模用戶與POI 的隱式關(guān)系。

CML[30]:該算法將度量學(xué)習(xí)(metric learning)與協(xié)同過(guò)濾(collaborative filltering)進(jìn)行結(jié)合來(lái)解決用戶物品推薦的問(wèn)題,提出了協(xié)同度量學(xué)習(xí)模型,學(xué)習(xí)用戶和物品之間潛在關(guān)系的同時(shí)評(píng)估用戶和用戶、物品和物品之間的相似性,借助用戶隱式評(píng)價(jià)進(jìn)行Top-K 推薦。

PRME[15]:該算法使用針對(duì)推薦的排序度量嵌入方法對(duì)用戶的個(gè)性化簽到序列進(jìn)行建模,此模型整合了簽到的序列信息、個(gè)人偏好和地理影響,以提高推薦性能。

STRNN[1]:該算法在循環(huán)神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)上增加了時(shí)間敏感性,捕捉在簽到行為之間的時(shí)間和空間位置信息變化。

DeepMove[10]:該算法在循環(huán)神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)上增加了用戶興趣注意力機(jī)制,考慮用戶簽到序列時(shí)序關(guān)系的基礎(chǔ)上還考慮了用戶的長(zhǎng)期興趣。

ST-LSTM[11]:該算法是LSTM 的變式,在LSTM中增加了時(shí)間和距離兩種門(mén)限機(jī)制來(lái)捕捉用戶簽到行為序列之間的時(shí)空關(guān)系進(jìn)行POI 推薦。

GRU[26]:該算法也是循環(huán)神經(jīng)網(wǎng)絡(luò)的一種,可以看成是LSTM 變體,結(jié)構(gòu)更加簡(jiǎn)單,主要解決了RNN 網(wǎng)絡(luò)中的長(zhǎng)依賴問(wèn)題。

ST-ODE:該算法是ML-ODE 的弱化版本,在不使用元學(xué)習(xí)機(jī)制下,應(yīng)用時(shí)空神經(jīng)網(wǎng)絡(luò)常微分方程進(jìn)行推薦,旨在比較分析元學(xué)習(xí)機(jī)制在該任務(wù)中是否有效。

Single-FT:該算法是ML-ODE 的變式,與MLODE 參數(shù)優(yōu)化機(jī)制不同的是,Single-FT 利用單個(gè)源城市對(duì)目標(biāo)城市時(shí)空模型的初始化參數(shù)進(jìn)行更新。

Multi-FT:該算法也是ML-ODE 的變式,與MLODE 參數(shù)優(yōu)化機(jī)制不同的是,Multi-FT 將多個(gè)源城市的數(shù)據(jù)進(jìn)行混合之后無(wú)差別地對(duì)目標(biāo)城市的時(shí)空模型進(jìn)行初始化參數(shù)更新。

No-ATT:該算法也是ML-ODE 的變式,與MLODE 不同的是,No-ATT 不使用時(shí)空注意力機(jī)制進(jìn)行隱狀態(tài)的聚合,直接使用ST-ODE 的最后輸出隱狀態(tài)作為推薦模塊的輸入。

ML-ODE:該算法是本文提出的基于元學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)常微分方程,將神經(jīng)網(wǎng)絡(luò)常微分方程用于時(shí)空關(guān)系挖掘。除此之外,借助元學(xué)習(xí)進(jìn)行初始參數(shù)的優(yōu)化和學(xué)習(xí),實(shí)現(xiàn)在數(shù)據(jù)匱乏城市的POI 推薦任務(wù)。

可以看出,在比較的方法中,MF-BPR 和CML是推薦系統(tǒng)領(lǐng)域比較通用(general)的模型,應(yīng)用比較廣泛。而STRNN、DeepMove 和ST-LSTM,都是要根據(jù)簽到序列的上下文信息(context-aware)進(jìn)行時(shí)空關(guān)系挖掘的推薦模型。在后期的實(shí)驗(yàn)評(píng)估過(guò)程中將會(huì)詳細(xì)地分析各類模型在POI 推薦任務(wù)上的表現(xiàn)。

3.3 評(píng)價(jià)指標(biāo)

在性能對(duì)比實(shí)驗(yàn)中,采用兩種推薦指標(biāo)來(lái)評(píng)估推薦模型的性能:命中率(HR@N) 和 歸一化累計(jì)增益(NDCG@N)。

其中,GT表示所有的測(cè)試集合,NumberOfHits@N表示推薦列表的Top-N 子集中屬于測(cè)試集合個(gè)數(shù)的總和。

這里DCG表示折損累計(jì)增益,是在累計(jì)增益CG的基礎(chǔ)上引入了位置影響因素,計(jì)算公式如下:

可以看出,推薦的相關(guān)性越多,DCG值越大,相關(guān)性強(qiáng)的排在推薦列表前面的話,推薦效果越好,DCG值越大。在式(19)中,IDCG表示推薦系統(tǒng)針對(duì)某一用戶返回的最好推薦列表,即假設(shè)返回結(jié)果按照相關(guān)性排序,最相關(guān)的結(jié)果排在最前面的情況下的DCG值。由定義可以看出NDCG的值為(0,1]。

3.4 推薦任務(wù)

表2 是各種對(duì)比方法在HR@5、HR@10、NDCG@5 以及NDCG@10 指標(biāo)上的實(shí)驗(yàn)結(jié)果?？梢钥闯霰疚姆椒ㄅc其他對(duì)比方法相比在推薦任務(wù)方面表現(xiàn)更佳,下面對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行詳細(xì)分析。

表2 各類方法在POI 推薦任務(wù)上的結(jié)果統(tǒng)計(jì)

(1)上下文信息的重要性。由實(shí)驗(yàn)結(jié)果可以看出,利用時(shí)空上下文信息的方法(如PRMF、STRNN、DeepMove、ST-LSTM、ST-ODE 等)在推薦任務(wù)上要優(yōu)于沒(méi)有利用上下文信息的方法(MF-BPR 和CML)?？梢钥闯錾舷挛男畔⒃谕扑]任務(wù)中起著至關(guān)重要的作用,有助于模型捕捉用戶簽到行為時(shí)空上的序列關(guān)系,提升推薦效果。文獻(xiàn)[31]也通過(guò)大量的實(shí)驗(yàn)論證了上下文信息對(duì)POI 推薦的重要性。

(2)神經(jīng)網(wǎng)絡(luò)的優(yōu)勢(shì)。由實(shí)驗(yàn)結(jié)果可以看出,基于矩陣分解的方法(如MF-BPR 和PRME)在推薦效果上欠佳,而基于神經(jīng)網(wǎng)絡(luò)的方法(如STRNN、GRU、DeepMove、ST-LSTM、ST-ODE 等)在推薦任務(wù)上要更好?？梢钥闯鰡渭兊木仃嚪纸夥椒ㄔ诓蹲接脩舻母唠A關(guān)系上效果較差,而神經(jīng)網(wǎng)絡(luò)由于可以建模用戶更高階的潛在關(guān)系,推薦效果要優(yōu)于傳統(tǒng)的矩陣分解方法。

(3)連續(xù)時(shí)間建模的優(yōu)勢(shì)。由實(shí)驗(yàn)結(jié)果可以看出,將簽到行為序列看成等間隔進(jìn)行建模的方法(如STRNN 和DeepMove)在推薦效果上要略遜于時(shí)間敏感的推薦方法(如ST-LSTM 和ST-ODE),簽到行為的時(shí)間依賴也是用戶興趣點(diǎn)推薦不可忽視的因素。并且本文提出的基于Neural ODEs 的方法可以建模連續(xù)時(shí)間序列,從實(shí)驗(yàn)結(jié)果可以看出,ST-ODE進(jìn)一步提升了時(shí)間敏感類方法在POI 推薦上的性能。

(4)時(shí)空注意力機(jī)制的優(yōu)勢(shì)。由實(shí)驗(yàn)結(jié)果可以看出,借助于時(shí)空注意力機(jī)制的ML-ODE 在推薦效果上要優(yōu)于不使用注意力機(jī)制的No-ATT 方法,主要原因在于時(shí)空注意力機(jī)制對(duì)用戶偏好的權(quán)重進(jìn)行了更好地建模,并克服了在長(zhǎng)時(shí)間序列傳播過(guò)程中的知識(shí)損失,提升了POI 推薦效果。

(5)知識(shí)遷移的必要性。根據(jù)表2 針對(duì)知識(shí)遷移的必要性進(jìn)行實(shí)驗(yàn)論證,通過(guò)ML-ODE 的幾個(gè)進(jìn)階版本進(jìn)行對(duì)比實(shí)驗(yàn)。ST-ODE 僅利用目標(biāo)城市的數(shù)據(jù)進(jìn)行訓(xùn)練,即沒(méi)有基于元學(xué)習(xí)機(jī)制進(jìn)行參數(shù)的初始化。Single-FT 是利用單個(gè)源城市對(duì)目標(biāo)城市的參數(shù)進(jìn)行更新。Multi-FT 是將多個(gè)源城市的數(shù)據(jù)進(jìn)行混合之后無(wú)差別地對(duì)目標(biāo)城市的時(shí)空模型進(jìn)行初始化更新。由實(shí)驗(yàn)結(jié)果可以看出,將多個(gè)城市視為不同的推薦任務(wù)來(lái)借助元學(xué)習(xí)進(jìn)行初始參數(shù)學(xué)習(xí)的ML-ODE 方法具有更加優(yōu)異的表現(xiàn),NDCG@10在兩個(gè)城市的性能提升均超過(guò)了25%。Multi-FT 的方法較Single-FT 表現(xiàn)更好,可能是由于多個(gè)城市數(shù)據(jù)混合之后在一定程度上緩解了由于數(shù)據(jù)分布差異性對(duì)學(xué)習(xí)移動(dòng)知識(shí)的通用性的影響。除此之外,ML-ODE比Multi-FT 表現(xiàn)更佳,說(shuō)明了元學(xué)習(xí)框架在知識(shí)遷移方面的優(yōu)勢(shì),通過(guò)多任務(wù)的分解可以更好地學(xué)習(xí)模型的初始化參數(shù)。

3.5 模型參數(shù)設(shè)置

本小節(jié)將詳細(xì)描述ML-ODE 各種參數(shù)的設(shè)置情況并分析其對(duì)模型性能的影響。在ML-ODE 對(duì)比實(shí)驗(yàn)中,對(duì)所有方法都是采用5 折交叉驗(yàn)證,并且中間狀態(tài)傳播過(guò)程中的隱狀態(tài)維度均設(shè)置為50。在參數(shù)訓(xùn)練過(guò)程中,dropout 的取值范圍為[0,0.1,0.2,0.3],weight decay 的取值范圍為[0.1,0.03,0.01,0.003,0.001,0.0001,0],learning rate 的取值范圍為[0.001,0.003,0.0001]。通過(guò)5 折交叉驗(yàn)證,每次留20%的驗(yàn)證數(shù)據(jù)集對(duì)上述參數(shù)訓(xùn)練的ML-ODE 參數(shù)進(jìn)行評(píng)估,模型表現(xiàn)最優(yōu)時(shí)的dropout值為0.2,weight decay 的值為0.001,learning rate 的值為0.003。

除此之外,在進(jìn)行Top-N 推薦任務(wù)的過(guò)程中,通過(guò)將參數(shù)N在取值范圍[1,5,10,15,20,25,30,35,40,45,50]內(nèi)進(jìn)行變化,觀察不同模型的表現(xiàn)情況,實(shí)驗(yàn)結(jié)果如圖6～圖9 所示?？梢钥闯瞿Ｐ驮贜的取值范圍內(nèi)表現(xiàn)均優(yōu)于其他對(duì)比實(shí)驗(yàn)方法。同時(shí),相較于HR@ N 指標(biāo),ML-ODE 在NDCG@ N 上的提升效果更加明顯。將圖8 和圖9 進(jìn)行對(duì)比發(fā)現(xiàn),在舊金山數(shù)據(jù)集上,ML-ODE的NDCG@N的提升效果更加明顯。在洛杉磯數(shù)據(jù)集上也發(fā)現(xiàn)了類似現(xiàn)象,說(shuō)明在排序結(jié)果中,高關(guān)聯(lián)度的結(jié)果出現(xiàn)在更靠前的位置,具有更高的累計(jì)增益值。

圖6 在舊金山數(shù)據(jù)集上的HR@N 結(jié)果

圖7 在舊金山數(shù)據(jù)集上的NDCG@N 結(jié)果

圖8 在洛杉磯數(shù)據(jù)集上的HR@N 結(jié)果

圖9 在洛杉磯數(shù)據(jù)集上的NDCG@N 結(jié)果

4 結(jié)論

針對(duì)興趣點(diǎn)推薦,本文提出了一種基于元學(xué)習(xí)的時(shí)空Neural ODEs 模型(ML-ODE)。首先,利用基于時(shí)空神經(jīng)常微分方程的時(shí)空關(guān)系學(xué)習(xí)模塊進(jìn)行用戶的時(shí)空興趣建模。其次,在模型中借助基于貝葉斯的更新模塊根據(jù)用戶的簽到記錄對(duì)時(shí)空神經(jīng)常微分方程預(yù)測(cè)的用戶隱狀態(tài)進(jìn)行更新,更好地學(xué)習(xí)用戶簽到行為的時(shí)空序列依賴。除此之外,借助于元學(xué)習(xí)機(jī)制進(jìn)行時(shí)空神經(jīng)常微分方程的參數(shù)初始化學(xué)習(xí),在進(jìn)行參數(shù)初始化的過(guò)程中,有效地將數(shù)據(jù)豐富城市的移動(dòng)行為知識(shí)進(jìn)行遷移,提升模型在數(shù)據(jù)匱乏城市的POI 推薦效果。最后,在真實(shí)的公開(kāi)LBSNs 數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果有效地驗(yàn)證該方法的推薦效果,并證明了ML-ODE 在HR@N 和NDCG@N 指標(biāo)上相比當(dāng)前先進(jìn)的興趣點(diǎn)推薦技術(shù)有了明顯提高。

在未來(lái)的工作中,將進(jìn)一步考慮高效的面向稀疏POI 簽到數(shù)據(jù)的POI 推薦方法,并將從以下幾個(gè)方面進(jìn)行嘗試:(1)結(jié)合分布式機(jī)器學(xué)習(xí)技術(shù),將ML-ODE 進(jìn)行分布式算法擴(kuò)展,結(jié)合GPU、TPU 等高效計(jì)算方式,讓分析超大規(guī)模POI 數(shù)據(jù)成為可能;(2)解決ML-ODE 動(dòng)態(tài)更新問(wèn)題,在實(shí)際應(yīng)用場(chǎng)景中,用戶的簽到行為是動(dòng)態(tài)變化的,而目前大多數(shù)的推薦方法都是建立在離線靜態(tài)POI 簽到數(shù)據(jù)上,所以對(duì)網(wǎng)絡(luò)中動(dòng)態(tài)POI 簽到行為進(jìn)行合理化建模,實(shí)現(xiàn)合理的在線參數(shù)更新機(jī)制,值得更多的關(guān)注;(3)計(jì)劃引入用戶的長(zhǎng)期興趣偏好,或者結(jié)合主題模型等用戶長(zhǎng)期興趣建模方法,進(jìn)一步提升興趣點(diǎn)推薦系統(tǒng)的性能。