基于游覽行為和逆向強化學習的游客偏好學習

宣 聞,常 亮

(桂林電子科技大學 廣西可信軟件重點實驗室,廣西 桂林 541004)

利用旅游推薦技術為用戶提供個性化服務并提高推薦性能和游客滿意度,是當前智慧旅游領域研究的熱點之一。在旅游推薦中,理解游客的行為模式,學習游客偏好是非常重要的。當前的旅游推薦技術主要根據游客游覽展品的評分、簽到數據、訪問的頻次等數據作為游客對游覽展品喜好程度的評判依據。但是,具體景區內部,如博物館、主題公園等,通常無法獲得游客針對游覽點或展品的具體評分數據,因此不能對游客進行細粒度偏好學習,從而也不能獲得針對特定景區內部的游覽推薦。并且許多推薦算法需要大量的游客數據來訓練,從而學習出游客偏好再進行推薦,然而展館內部的游客數據較為稀缺、不完整,因此,無法根據有限的游客數據學習出精準的偏好。鑒于此,為了在游客數據較少的情況下獲得游客更加真實、細粒度的偏好,提出一種基于游覽行為和逆向強化學習的偏好學習方法。首先,通過物聯網和移動傳感器技術采集游客在特定景點內的各個游覽點的拍照次數、游玩時間等游覽行為數據;然后,針對采集到的行為數據設計逆向強化學習算法,基于獲取到的真實數據進行細粒度偏好學習。

1 研究現狀

1.1 位置感知技術

目前最常見的定位技術是GPS(global positioning system)全球定位系統,它通過衛星發射的基準信號來工作,但是在有建筑物遮擋的情況下,就無法運用GPS精準定位,因此GPS也被稱為室外定位系統[1];在室內定位技術中,WiFi(wireless fidelity)部署成本低,但是,目前的WiFi定位技術需要通過預先測量來提供相對應的接入點(APs)、傳播參數(PPs)以及地圖上的具體位置,這個預先測量的過程既耗時又費力[2];Wang等[3]使用射頻識別(radio frequency identification,簡稱RFID)技術來實現細粒度室內定位,該系統利用RFID的多路徑效應進行精確定位,通過合成孔徑雷達(synthetic aperture radar,簡稱SAR)提取多路徑的配置文件,采用動態時間規劃技術確定RFID 標簽的位置,從而實現定位,但是RFID需要標簽和讀寫器,部署成本較大,不適合在大型場合使用。iBeacon是蘋果公司于2013年9月發布的新一代室內定位技術,具有低功耗藍牙(bluetooth low energy,簡稱BLE)的通訊功能,它可以向周圍發送自己特有的ID,同時根據iBeacon設備所發出的廣播信號強度的變化,對智能手機和iBeacon之間的距離進行計算,得出距離最近的iBeacon設備,從而實現定位。iBeacon具有成本低、功耗低、跨平臺、易安裝部署等優點,在室內定位中具有較大的優勢[4-5]。

1.2 用戶偏好評估和應用

眾多的社交媒體提供了豐富的數據信息,可用于獲取游客的歷史位置并分析他們的偏好,從而為游客提供個性化的推薦服務,因此,基于位置的社交網絡在游客偏好學習在旅游推薦中得到了廣泛的應用。Yuan等[6]提出基于位置-時間-序列的方法,利用基于位置的社交網絡數據集從空間和時間兩個方面對用戶的偏好進行建模,然后用時間和空間特征結合的方式對用戶的個人偏好進行預測。Zhu等[7]提出了一種基于語義模式和偏好感知的挖掘方法,首先將位置分為不同的類型,從而進行位置識別,然后從游客的位置軌跡、語義軌跡、位置的流行程度和用戶熟悉度4個方面為每位用戶進行建模,從而獲取用戶偏好并推薦興趣點。Wang等[8]提出基于上下文感知的用戶偏好預測算法,構建了云模型,將分類信息引入用戶和位置的相似性估計中,當用戶在一個新景點時,通過新景點的類別和訪問過該景點的用戶類別,預測用戶的偏好。Zhu等[9]在基于位置的社交網絡數據集上構建了旅游推薦的系統架構,并對每位用戶的移動模式進行建模,最后根據產生的興趣點進行推薦。

盡管上述的方法都可以學習游客的偏好,但是仍存在以下問題:首先,現有的游客偏好學習方法大多使用基于位置的社交網絡數據集,而基于位置的社交網絡數據集中,位置僅到景區級別,因此只能學習出游客對景區級別的粗粒度偏好,從而進行粗粒度的旅游景點推薦;其次,現有方法僅考慮了游客的位置、簽到等數據信息,卻未考慮到游客訪問展品的先后順序對游客偏好的影響。此外,在游客實際旅游的過程中,不會一直共享自己的位置信息,因此最后收集到的游客簽到的數據集僅包含了游客一部分的位置信息,從而導致數據稀疏,對游客偏好的學習不全面,無法對景區內部景點進行細粒度的推薦。

1.3 逆向強化學習

逆向強化學習(inverse reinforcement learning,簡稱IRL)是一種通過專家數據學習出回報函數的技術,它首先通過馬爾科夫決策過程(Markov decision process,簡稱MDP)對應用場景進行建模,然后利用相關算法進行學習。吳恩達等[10]通過觀察該領域的專家示例來學習用戶偏好,從而學習到背后的回報函數,這個逆向強化學習的方法被稱為學徒學習。Ratliff等[11]將評估回報函數轉化為特征到回報的線性映射問題,在這種線性映射下,最優的策略與專家策略十分接近,此方法稱為最大邊際規劃方法。但是基于最大邊際規劃方法的主要問題是會產生歧義,比如有很多不同的回報函數會導致相同的專家策略。為了解決這個問題,Ziebart等[12]提出基于最大熵的逆向強化學習方法,即在已知專家軌跡的情況下,求解產生軌跡分布的概率模型。上述方法雖然能夠學習出回報函數,但是所需的數據量較大,需要較多的數據進行不斷地迭代才能訓練出較為準確的回報函數。Babes等[13]提出的極大似然逆向強化學習方法,與前面的算法相比,優勢在于可以在數據較少的情況下訓練出回報函數。Massimo等[14]提出基于用戶與項目的交互來學習用戶偏好方法,該方法將極大似然逆向強化學習運用于學習用戶對項目的偏好上,最后學習出用戶偏好;2018年,Massimo等[15]在之前方法的基礎上,提出一個基于上下文用戶行為模型的方法,該方法對用戶的軌跡進行分類對于每個分類都產生一個基于上下文用戶行為模型,最后將用戶的軌跡與得出的行為模型相結合,從而學習出用戶的偏好。上述2個方法均考慮到在用戶與項目交互的過程中現場所產生的行為對偏好的影響。

2 預備技術

對游客在室內展館的游覽行為進行馬爾科夫決策過程建模。首先,簡單介紹了運用iBeacon進行數據采集的整體流程,然后詳細介紹了馬爾科夫決策過程建模過程,并對相關評估函數進行簡要說明。

2.1 數據收集

場景布置在室內展館。首先,給游客的智能手機上安裝導覽App,同時在展館入口處、展館內部的每一個展品都布置iBeacon,用于獲取游客的位置信息,游客數據采集過程如圖1所示。游客智能手機上的導覽App通過手機照相機、加速度傳感器來接收iBeacon所發送的信號,從而收集游客多種游覽行為數據(比如拍照、停留時間等)。iBeacon設備就是利用低功耗藍牙(BLE)通信協議向周圍發送自己特有的設備ID;在iBeacon協議數據中,包含了Minor和Major兩種標識符。在應用場景中,將iBeacon設備進行分組,其中Major用來識別iBeacon設備屬于哪一組,Minor用來標識同一組內的不同iBeacon設備,即Minor設置為展館內部展品的ID,Major設置為展品所屬的分區,因此可以通過Minor和Major兩種標識的結合來對游客當前游覽展品的位置信息進行定位。

圖1 游客行為數據的采集

智能手機中的應用程序接收到iBeacon設備廣播信號,然后智能手機讀取傳感器數據并監聽拍照廣播,最后通過無線網絡將采集的數據上傳至系統服務器。當有游客進行拍照時,智能手機中的應用程序會立即檢測到拍照行為的發生,隨后向系統服務器發送廣播;系統服務器根據接收拍照廣播的次數和iBeacon的位置標識統計出游客在某展品的拍照次數,并存儲游客行為數據。如圖2所示,收集數據的日志中包含了游客與iBeacon交互的時間戳序列,用戶的行為加速度數據和瀏覽展品的標識。

2.2 馬爾科夫決策模型構建

通過馬爾科夫決策過程MDP模型對游客在室內展館的游覽行為進行建模,馬爾科夫決策過程可以用一個五元組(S,A,p,r,γ)來表示,其五要素的定義如下:

定義1狀態s表示游客當前瀏覽展品的記錄,其狀態空間為S。

例如:游客剛進入展館,狀態默認為s0,其中s0=?;當游客瀏覽了展品a1時,則游客的狀態變為s1,其中s1={a1};游客下一個瀏覽了展品a2,則游客的狀態變為s2,其中s2={a1,a2},以此列推S={s0,s1,s2,…}。

定義2動作a表示在狀態s下,游客下一個將要瀏覽的展品,其動作空間為A。

定義3狀態轉移概率p(st+1|st,at)表示從狀態st通過動作at轉移到狀態st+1的概率,其中,st∈S,at∈A。

例如,游客瀏覽展品記錄s1的情況下,接下來想要瀏覽展品a2或者展品a3,那么狀態轉移概率可定義為p(s2|s1,a2)=0.5,p(s3|s1,a3)=0.5。

定義4r(st,at)表示回報函數,是在游客當前瀏覽展品記錄st下,瀏覽展品at后所能獲得的回報,其中,st∈S,at∈A。這個回報值與游客偏好值成正比,也就是說游客對展品at的偏好越高,那么回報值也就越高。為了方便計算,定義r(st,at)≤1。

定義5γ∈[0,1]代表折扣因子,用來計算累積的回報。

游客與展館內展品的交互過程可看作一個馬爾科夫決策過程,如圖3所示。

圖3 馬爾科夫決策過程模型

游客從進入展館內開始,瀏覽記錄默認為s0。當瀏覽展品a1時,會有相應的拍照次數和停留時間;將拍照次數和停留時長作為特征值加入回報函數中,計算出回報值r1,并更新游客瀏覽記錄s1;然后游客瀏覽下一個展品a2,以相同的方式計算出回報值r2,游客瀏覽記錄相應地變為s2,一直交互下去,因此游客瀏覽時的交互序列如式(1)所示,其中s0,s1,…,st-1,st∈S。

馬爾科夫性是指下一個時刻游客瀏覽的展品記錄st+1,只取決于當前時刻游客瀏覽過的展品記錄st和正在瀏覽的展品at,其他所有的歷史瀏覽過的展品記錄都可以被丟棄。如式(2)所示,其中p(st+1|st,at)為游客瀏覽展品的轉移概率:

而在各狀態下如何選擇動作at的這一規則是由策略π決定的,見定義6。

定義6策略(policy)定義為π:S→A,代表游客瀏覽展品記錄的狀態空間到游客下一個瀏覽展品的行為映射。通過式(3)可知,策略π是指在給定狀態s時,動作集上的條件概率分布,即策略π可以在每個狀態s上指定一個動作的概率,也就是策略π可以根據游客瀏覽展品的記錄s來決定下一步推薦給游客的展品a:

例如,一個游客瀏覽展品的策略為π(a2|s1)=0.3,π(a3|s1)=0.7,這表示游客在瀏覽記錄s1的情況下,瀏覽下一個展品a2的概率為0.3,瀏覽展品a3的概率為0.7,顯然游客瀏覽展品a3的可能性更大。

在給定策略π和馬爾科夫決策過程模型的基礎上,就可以確定一條游客游覽展品的交互序列τ:

游客瀏覽展品的交互序列所能獲得的累積回報為G(τ),總回報G(τ)如式(5)所示,其中rt表示游客瀏覽的第t個展品所獲得的回報。

因此,目標就是學習出一個最優策略π*,使得累積回報值G(τ)達到最大。但是,在當前求得的策略π下,假設從狀態s1出發,游客的瀏覽展品狀態序列可能如圖4所示。

圖4 游客瀏覽展品狀態序列示意圖

此時,在策略π下,利用式(5)可以計算出累積回報G(τ);通過圖4可知,游客瀏覽展品的交互狀態序列存在多種可能性,所以此時計算出來的G(τ)也存在多種可能值,因此無法通過累積回報G(τ)評估當前策略π是否最優,但是累積回報的期望是一個確定值,可以用來評估。因此在一個狀態s下,基于特定策略π,做出行為a得到累積回報的期望值可由式(6)得到:

因此,當Q值達到了最大即Qmax時,所求的策略π為最優。

但是現實中很多情況下回報函數是未知的,用戶瀏覽某個展品時,未必會給出反饋,因此,很多時候回報函數難以定義。針對此問題,可采用逆向強化學習算法來解決,根據已有的游客瀏覽展品相關軌跡示范數據學習出對應的回報函數。

3 基于逆向強化學習的游客行為偏好學習

3.1 逆向強化學習

逆向強化學習是一個未知回報函數的馬爾科夫決策過程(MDP ),可以用一個四元組(S,A,p,γ)來表示。當專家在完成某項任務時,其動作往往是最優或者接近最優,那么可以假設,當所有的策略π所計算出的累積回報期望無限接近于專家策略所計算出的累積回報期望時,可以認為專家示例所學到的回報函數即為所需要的回報函數。因此,逆向強化學習可以從專家示例中學習到回報函數,也就是在已知狀態S、行為A、狀態轉移概率為p的條件下,從已有的游客瀏覽展品相關軌跡數據中反推出相對應的回報函數。也就是使算法產生的游客瀏覽展品軌跡與已有的游客瀏覽展品軌跡相近,這等價于在某個回報函數下求解最優策略π*,在該策略下產生的軌跡與已有的游客軌跡相近,當策略達到最優時,游客軌跡的累積回報達到最大,所學到的回報函數也達到最優。

因為回報函數r(st,at)未知,所以可利用函數逼近的方法對其進行參數逼近,其逼近形式為

式(7)中,?=(?1,?2,…,?d)T,?:S×A→Rd為數量有限并且固定有界的特征基函數,d為特征基的個數,?i為每個狀態的特征向量。θ=(θ1,θ2,…,θd)表示各個特征基之間的權重向量。通過這樣的線性表示,可以對權重進行調整,從而改變回報函數值。逆向強化學習的目標是學習出權重向量θ,從而計算出回報函數Rθ(s,a)。

在應用的場景中,一共有15個展品,首先統計在當前狀態s下,某展品的拍照次數ms和停留時間ys(以s為單位)2種游客行為特征。然后,將回報函數定義為瀏覽展品時所產生的瞬時回報與在該狀態下游客瀏覽展品時的拍照次數和停留時間所產生的回報之和。為了便于計算,將拍照次數和停留時間所產生的回報通過式(8)將數據歸一化,其中:x*代表當前狀態下的拍照次數或者停留時間的值,min和max代表在所有狀態下拍照次數或者停留時間的最小值和最大值;

則在當前狀態下的回報函數可表示為

將已有的游客瀏覽軌跡處理成“狀態-動作-行為特征”序列。假設有N個游客軌跡數據D={ζ1,ζ2,…,ζN},每條軌跡數據長度為H,則一組軌跡數據序列可表示為ζi=((s1,a1,m1,y1),(s2,a2,m2,y2),…,(sH,aH,mH,yH)),其中sH∈S,aH∈A。將每條軌跡數據長度H定義為15。例如,一個游客u的瀏覽軌跡為ζu=((s1,a2,m1,y1),(s2,a4,m2,y2),…,(s15,a1,m15,y15)),則代表游客u在狀態s1下瀏覽了展品a2,其中在展品a2的拍照次數為m1,停留時間為y1;然后瀏覽了展品a4,其中在展品a4的拍照次數為m2,停留時間為y2,以此類推。逆向強化學習整體過程如圖5所示。首先,游客在狀態s下,選擇動作a所能獲得的回報R(s,a)往往是未知的,因此需要通過專家示例(已有的相關游客瀏覽展品的軌跡數據)來學習到背后的回報函數。而在學習過程中,加入了拍照次數、停留時間2種游客行為特征來進行訓練;最后通過逆向強化學習算法,學習出回報函數Rθ(s,a)。

圖5 逆向強化學習過程示例圖

3.2 最大似然逆向強化學習

根據Babes等[13]提出的最大似然逆向強化學習(maximum likelihood inverse reinforcement learning,簡稱MLIRL)算法并結合游客行為特征(拍照次數、停留時間)來學習θ。最大似然逆向強化學習算法與貝葉斯逆向強化學習[16]類似,采用了一種概率模型,通過θ創建一個值函數,然后假設專家在單個操作選擇級別隨機化;與最大熵逆向強化學習類似[12],在已知專家軌跡的情況下,求出產生該軌跡分布的最大似然模型;與策略匹配類似,它使用梯度方法求得用戶行為策略,并在訓練的過程中,用戶行為策略不斷向專家策略靠近。因此,最大似然逆向強化學習融合了其他逆向強化學習模型的特點,且可在專家軌跡較少情況下對回報函數進行估計,通過專家軌跡尋找出最大似然模型,并不斷對初始的回報函數進行調整,通過梯度不斷優化策略π。因此,在一個狀態s下,做出行為a得到累積回報期望可表示為

在MDP中,動作定義為下一個瀏覽的展品,所以動作空間并不大,因此采用玻爾茲曼分布作為策略,可表示為

在此策略下,基于已有的游客瀏覽展品相關軌跡示范數據的對數似然估計函數可表示為

因此,最大似然逆向強化學習算法是通過梯度上升的方法求出函數中θ的最大值,即θ=argmaxθL(D|θ)。

在給定的馬爾科夫決策模型中,通過已有的游客瀏覽展品相關軌跡示范數據得到的最優回報函數可能存在多個;而MLIRL算法可以對觀測到的行為分配較高的權重,對于未觀測到的值分配較低的權重,從而解決回報函數不唯一的問題。MLIRL算法即極大似然逆向強化學習(maximum likelihood inverse reinforcement learning,簡稱MLIRL)如下所示。

4 實驗

4.1 實驗條件

客戶端應用程序使用的是Android studio開發,JDK1.7版本,運行在Android智能手機系統版本6.0.1。相關應用程序運行在JetBrains PyCharm上。15個基于CC2541的iBeacon。

4.2 實驗環境

應用場景布置在一個具有15個展品的室內展館,每個展品都提前安裝了iBeacon。本研究邀請了35名年齡段在20～22周歲的女大學生作為志愿者參觀展館,并且進入展館前在他們的智能手機中裝上采集數據App。同時,給每個志愿者發一份調查問卷,便于后期處理的時候獲取他們對展品的真實偏好。

4.3 參數設置

在實驗中,將折扣因子γ設置為0.6。在MLIRL算法中,將參數β設置為0.75,步長λt=1/。

4.4 實驗結果分析

4.4.1 游客偏好學習

利用調查問卷的形式獲取游客對展品的實際偏好排名。表1為選取的35位女大學生對15個展品的平均偏好排名。

表1 游客對15個展品偏好平均排名

若MDP模型得出的志愿者對某個展品偏好排名與調查問卷中的排名一致,則定義平均偏好準確率為n/m;其中,n為MDP模型中學習出志愿者展品偏好排名與調查問卷中排名一致的總個數,m為總的展品數。

將35位志愿者的軌跡數據進行訓練,從而得出志愿者的平均偏好準確率分布,結果如圖6所示,其中,將僅包含了游客瀏覽點的數據記為原始數據。將原始數據訓練出來的結果與每個瀏覽點加入游客行為特征(拍照次數和停留時間)的數據訓練出來的結果做對比。

圖6 平均偏好學習準確率

從圖6可看出,隨著人數的增加,軌跡數的增長,游客的平均偏好準確率呈現出不斷上升的趨勢。加入游客行為特征(拍照次數和停留時間)的數據與原始數據相比,在每個瀏覽點中加入游客的行為特征所學習出的游客偏好性能比之前更好,準確率提高更快,且在人數達到35個時,游客平均偏好準確率達到53.3%,這也表明在真實軌跡較少情況下,該算法在結合了游客行為特征,能夠較好地從游客的軌跡中學習出年齡段在20～22周歲的女學生對展品的平均偏好。在實際應用中,隨著游客人數的增加、展館展品的增多,本方法對游客偏好的學習比傳統的調查問卷方式更有優勢,軌跡數越多,偏好學習的結果也會更加全面、客觀。

4.4.2 游客行為特征對偏好學習的影響

在實驗中,主要加入了2種游客行為特征:拍照次數和展品游玩時間。為了驗證哪種特征對實驗的效果影響更大,分別加入一種特征來測試,最后通過展品偏好準確率來驗證。圖7為分別在加入拍照次數和停留時間特征的情況下的偏好學習準確率。從圖7可看出,隨著游客人數的增加,軌跡數的增多,游客在展品的游玩時間對偏好學習的影響更大,而拍照次數相對就小一些。

圖7 游客行為特征對實驗效果的影響

4.4.3 基于逆向強化學習的游客偏好學習模型參數化

在實驗中,參數的取值會對模型的準確率產生一定影響。因此,為了提高模型的準確率,對折扣因子γ取不同值來對比模型的準確率,如表2所示。

表2 準確率對比

折扣因子γ代表了未來的回報相對于當前的回報的重要程度,當γ=0時,代表只考慮當前的回報,不考慮長期回報;當γ=1時,長期回報和當前回報同等重要;通過表1可知,并不是γ越大越好,當γ=0.6和γ=0.7時,偏好學習的準確率最高,為53.3%。

5 結束語

針對在景區內中難以獲取游客細粒度偏好的問題,提出一種基于現場游覽行為感知和逆向強化學習的游客偏好學習方法。利用物聯網與移動傳感器技術相結合采集了游客在特定景區內的游覽行為數據,即拍照次數和停留時間。將游客在每個展品的拍照次數和停留時間作為行為特征,將游客行為特征與逆向強化學習相結合,從而實現從較少的游客數據中學習出游客細粒度的偏好。實驗結果表明,在真實的場景下,該方法能夠在少量游客游覽行為數據的情況下有效學習出游客的細粒度偏好。但是在實際游覽過程中,天氣的狀況、氣溫的變化、人群的密集度等多種特征都會影響游客的偏好,因此將來可以綜合性的考慮這些因素,更有效地學習出游客細粒度的偏好。