結合服務相似性的Bandit智能推薦模型

周禮亮 李 濤

(中國電子科技集團公司航空電子信息系統技術重點實驗室 四川 成都 610036)

0 引 言

Web服務是一種具有統一標準的、平臺無關的網絡資源服務提供方式,因為其部署簡單、調用方便等特性,在電子商務、分布式計算等領域都有著廣泛的應用。隨著計算機技術的發展,互聯網中的Web服務也日益豐富[1]。目前,關于Web服務的推薦已有大量研究。

個人終端本身并不提供Web服務,它只是接入了擁有大量服務的互聯網。除引入服務質量的概念外,服務推薦的過程本質上與傳統的商品推薦并無太大的不同。具體而言,個人終端的地理位置雖然會發生頻繁變化,但是用戶的需求在一定時間范圍內卻相對穩定;此外,傳統的CS架構在個人終端上仍有廣泛應用,對于推薦算法的執行過程,一般個人終端只完成復雜度較低的計算,而開銷較大的計算任務往往由服務器端完成。正因為如此,Web服務推薦的這種應用場景有局限性。

在某些無線移動環境下,終端無法與互聯網相連,服務都存在于終端本地中,而為了增加服務的可用性,往往將多個終端組織成一個局域網,這些終端既是服務的提供者,又是服務的使用者。這種情況下,服務的推薦就需要由各終端協作完成。此外,由于移動終端的計算能力有限,如果推薦算法中所有的計算完全由所有終端完成,則耗時較長,如果終端處于一個不斷變化的場景中,對推薦結果的實時性要求較高,則現有的服務推薦算法不能得到很好的應用。綜上所述,對于完全由終端集群組成的無線移動環境下的服務推薦問題,目前仍然缺少研究。本文將對完全由終端集群組成的無線移動環境下的服務推薦問題展開研究,設計出適合Web服務分布在多個終端中的無線分布式場景的服務推薦算法。

Web服務推薦方法按照對推薦模擬更新的方式的不同可以劃分為傳統推薦方法和智能推薦方法。在傳統推薦方法中,推薦結果由原始數據經過正向計算得到,當數據發生動態變化時,往往認為數據集發生了變化,需要重新計算推薦結果;而智能推薦方法往往會預定義一個智能體,它是獨立于數據的存在,數據只起到改變智能體參數的作用,當數據發生變化時,只需要對智能體進行更新即可。傳統推薦方法模型簡單,在靜態場景下有較高的效率,而在場景的不斷變化的前提下,服務對終端的效用并不能保持穩定,導致終端對服務的評分會時刻更新,如果使用傳統推薦方法則需要頻繁重新計算推薦結果,額外增加很多計算開銷。本著減少算法時間和空間復雜度的原則,智能推薦方法更適合動態變化的場景。進一步地,智能推薦方法又可分為監督學習、無監督學習和強化學習方法等,對于監督學習和無監督學習方法,一般需要給出全部的數據,模型訓練一次完成,處理推薦完成后終端做出的反饋有一定難度,而強化學習算法能根據環境中的反饋信息不斷地更新模型,所以智能推薦方法中的強化學習又更適合動態變化的場景。

1 相關研究

1.1 基于強化學習的推薦算法

強化學習是一種能夠適應環境的機械學習方法,它的特點在于利用智能體(Agent)在環境交互中的反饋進行模型訓練[2-3]。強化學習以其在復雜非線性系統中表現出優秀的性能被廣泛應用于四類領域:過程控制、任務調度、機器人設計、游戲[4]。

在將強化學習方法應用到推薦系統的過程中,Auer[5]提出了LinRel算法,該算法將物品的特征向量融入多臂老虎機模型。Li等[6-7]提出Lin UCB算法解決了UCB等MAB算法缺少推薦上下文信息的問題。文獻[8-9]使用協同過濾的思想對Lin UCB算法進行改進:對用戶和物品進行聚類,根據反饋調整這些聚類,并基于用戶聚類來完成物品的推薦。在推薦的應用問題方面,Li等[6]提出的Lin UCB算法被應用于Yahoo的個性化新聞推薦,提高推薦多樣性。Katzman等[10]提出的生存模型DeepSurv被應用于治療方案推薦系統。

1.2 移動服務推薦

移動推薦利用終端的歷史行為信息以及Web服務自身屬性為終端推薦他有可能感興趣的服務。與一般場景下的推薦系統類似,移動推薦主要包括協同過濾推薦、基于內容的推薦和基于數據挖掘的推薦系統及混合推薦系統等不同類型。其中,協同過濾推薦系統利用用戶歷史信息為用戶建模進而做出推薦[11-12],基于內容的推薦系統通過構造物品畫像,為用戶推薦與過去滿意的物品相似的物品[13],基于數據挖掘的推薦系統是將數據源進行處理[14-15],轉化為知識后,進而為用戶推薦。混合推薦系統則是綜合采用以上方法來實現推薦功能[16]。

2 完全由終端集群組成的無線移動環境下的服務推薦方法

在算法設計的過程中,除充分考慮終端內Web服務選擇的準確度和效率外,還應當兼顧終端間信息的傳遞效率。為保證信息在終端間傳遞的高效性,終端內Web服務的推薦應具有較低的時間和空間復雜度。

本文涉及的服務推薦的主要依據是評分矩陣S,本模型將使用各種手段,根據各種數據(例如服務的屬性、終端對推薦的反饋等)生成或修正終端m(m=1,2,…,M)對服務n(n=1,2,…,N)的評分smn,并根據評分作出推薦。服務推薦算法的流程如圖1所示。

2.1 初始評分的計算

在模型剛剛建立時,每個服務的評分數據是極為有限的,這時需要充分結合服務的屬性對評分進行擴充。但是,服務的屬性和其評分間的關系較為復雜,使用輕量級模型擬合效果難以令人滿意。但是可以肯定的是,一般情況下,用戶對相似的服務的評分也比較相近。因此,我們考慮使用相似服務的評分對缺失數據進行擴充。

首先,需要明確服務相似度的計算方法。我們使用服務的語義相似度來描述服務的相似程度:每個服務都有一段文本描述信息,服務之間的相似度就是這段描述信息的語義相似度:首先使用HanLP工具對服務描述信息進行分詞并計算其詞向量vi(i=1,2,…,N),那么服務i和服務j的服務相似度dij=vi·vj。

計算完相似度后,即可進一步計算擴充的數值。設第i個服務和第j個服務(i,j=1,2,…,N)之間的相似度為dij,特定終端t(t=1,2,…,M)已給出評分的服務集合為St。如果i∈St,則無須進行任何操作;而如果i?St,則需要使用終端t對其他服務的評分估計其對服務i的評分,計算公式為:

(1)

式中:η為相似度的閾值,也就是說當服務j和服務i的相似度過低時,服務j的評分不參與服務i的評分的估計。如果計算過程中發現式(1)的右端為0/0,即終端t未對除i以外的其他相似服務給出評分,則sti的取值為所有終端產生的所有評分的均值。

2.2 評分的調整與更新——UCB算法

在初始評分已存在的情況下,推薦時就可以直接選擇評分最高的服務。但這種方法存在一個明顯的缺陷:部分服務在初始化時利用的評分信息很少,其評分等于或接近于所有終端產生的所有評分的均值,導致這部分終端在推薦時很難被選中,由此埋沒了部分潛在的適合服務。為了解決此問題,本項目使用強化學習算法對評分進行適當的調整。

UCB算法基于兩個觀測:

觀測1如果一個服務已經被推薦了k次(獲取了k次反饋),該服務的評分:

(2)

下面開始計算真實得分和估計得分之間的差值Δ。從直觀上看,對于被選中的服務,多獲得一次用戶的反饋會使Δ變小,最終會小于其他沒有被選中的服務;對于沒被選中的服務,Δ會隨著輪數的增大而增大,最終會大于其他被選中的服務。

為了定量地計算Δ,需要使用如下假設:

假設1Chernoff-Hoeffding Bound假設[17]假設reward1,reward2,…,rewardn是在[0,1]之間取值的獨立同分布的隨機變量,用式(2)表示樣本均值,用p表示分布的均值,那么有:

(3)

(4)

(5)

2.3 服務的選擇策略

(6)

2.4 算法流程

對于每個終端,都使用一套獨立的UCB算法,算法流程為:

輸入:服務數N,各個服務推薦的次數T,評分矩陣R。

輸出:推薦的服務target。

fori=1 toNdo

if 當前終端未對第i個終端進行評分 then

當前終端對第i個終端的評分ri=average(R);

end if

end for

fori=1 toNdo

end for

fori=1 toNdo

end for

采樣target～p(prob1,prob2,…probN);

returntarget

推薦算法完成后,需要請發出推薦請求的終端給出評分,以作為反饋數據更新算法。如果數據集中已經包含了對服務的評分,則可以使用評分進行預訓練。

2.5 分析和討論

以上使用了UCB算法解決了服務的推薦問題,一個顯然的問題就是它的合理性。事實上,在強化學習中,當明確狀態空間、動作空間,而不明確狀態轉移空間時,存在著許多可行的算法。與UCB比較相似的是LCB算法,另一個比較常用的算法是策略梯度算法。下面將這兩種算法與UCB算法進行比較和分析。

對于策略梯度算法,一般來說,它相比UCB算法更加復雜、精巧,在許多場景下有廣泛的應用。具體來說,它的優勢主要體現在三點:第一,使用了隨機策略,這也就是說在其他條件完全一致時,推薦結果仍具有隨機性而不是唯一確定,這種特點運用在推薦系統中可以使推薦結果具有多樣性,增加推薦的驚喜度,但是在本文的應用場景中,節點充當了用戶的角色,而非真實的人,所以對驚喜度的需求并沒有商品推薦高;第二,推薦結果隨參數的變化是連續的,在UCB中,參數的微小變化如果引起了得分的最大值不同,則會導致結果發生突變,但是與上文關于LCB的分析類似,本場景中的推薦是一個長期的過程,并不需要模型迅速收斂,所以策略梯度在這一點上優勢也不明顯;第三,可以表示連續動作,而在本場景中,推薦服務的行為是一個離散的動作,所以從這個角度看,策略梯度的優勢也無法發揮。結合策略梯度中由于涉及神經網絡而帶來的復雜性,可以認為在本文的場景中使用策略梯度算法并不具有優勢。

綜合以上分析,可以看出在本文的場景中使用UCB算法是相對合理的。

3 實驗與結果分析

3.1 數據集

本實驗結合使用了數據集Book Crossing和Quality of Web Service(QWS)。其中,Book Crossing數據集由Cai-Nicolas Ziegler在2004年使用爬蟲程序從Book-Crossing圖書社區上采集得到,是Book-Crossing圖書社區的278 858個用戶對271 379本書進行的評分,包括顯式評分和隱式評分,用戶的年齡等人口統計學屬性(demographic feature)都以匿名的形式保存并供分析。QWS數據集由Guelph大學的Eyhab Al-Masri對公網上Web Service狀況進行數年研究后,使用Web Service Crawler Engine(WSCE)從UDDI、搜索引擎和服務門戶網站中收集Web服務,并對這些服務的十幾種QoS屬性進行度量得到。

但是,標準的Book Crossing數據集還不能滿足本項目的實驗要求,需要對標準數據集進行處理加工。本實驗中,終端數和服務數分別設置為100和100 000,所以從Book Crossing數據集中提取了部分讀者和圖書數據,提取時盡量選擇評分較多的讀者和圖書。

在服務推薦的過程中,需要提供服務的相關屬性用于計算服務間的相似度。而Book Crossing數據集圖書數據的字段中并不包含這些字段,所以本項目為每個圖書記錄都補一個類別數據、一個短文本數據和一個標簽數據。對于服務評價,需要由QWS數據集提供響應時間、可靠性等服務性能數據,但由于QWS數據集的記錄數不足100 000條,所以本項目根據已有數據的規律人為生成模擬數據,對該數據集進行擴充,并給每個服務分別配上其中一條記錄。

得到原始數據后,服務記錄將隨機放入不同終端中。

為了研究本文算法的適用范圍,本文分別模擬了100個終端處于集中式、層次式和分布式集群結構下的算法性能。由于服務間具有較強的語義關系,因此本文采用SimBet算法與PROHET路由算法相結合,并以終端之間的相似度作為權重的通信策略。

3.2 評價指標的選擇

本項目使用的離線評價方法為10次10折交叉驗證法。首先把數據集中的所有評分數據隨機均分成10份。然后將推薦算法運行10次,每次使用其中的9份數據建立模型,分別模擬每個終端發出請求,得出推薦結果。再使用剩下的1份數據評價推薦結果,如果算法推薦出的服務在剩下的1份數據中有相應的評分,則記錄下此評分。最后計算所有記錄下的評分的平均值,該評分越高表明推薦算法的效果越好。最終得到10次運行結果的平均值及標準差,其中平均值反映了推薦效果的整體好壞,標準差反映了推薦效果的穩定性。用本文設計的推薦方法和隨機推薦方法分別執行10次10折交叉驗證法,比較兩者最終得到的平均值及標準差。

在上述算法中,將K取不同的值并進行重復實驗,得到不同的評分平均值及標準差。最終可以繪制出評分平均值和標準差關于K值的曲線圖并進行分析。

3.3 結果分析

本實驗中,由于測試集數據過于稀疏,所以使用“統計測試集中所有評分在推薦系統模型中的UCB值,觀察評分和UCB值之間的相關性”的方法評價推薦系統的效果。

統計完成后,分別在集中式、層次式和分布式三種體系結構的前提下,對測試集中已有評分的所有服務,作出用戶真實評分關于服務UCB值的散點圖,如圖2所示。進一步計算兩個變量之間的相關系數,三種體系結構下的結果分別為0.961、0.949和0.935,這表明用戶真實評分數據和作為推薦依據的UCB值之間具有強相關關系。有理由相信,根據此UCB值計算出采樣概率并最終采樣服務推薦給用戶,在很大程度上能保證推薦的準確性。

(a) 集中式結構

除此之外,在集中式、分布式和層次式3種結構下推薦花費的平均時間如表1所示(不考慮節點之間的通信時延),結果顯示本文提出的推薦算法具有較高的性能,滿足應用場景的需求。

表1 實驗結果

3.4 分析和討論

本文算法的實際應用場景是由多個移動終端組成的集群,移動終端在計算能力、存儲空間等方面均受到限制。本文提出的結合服務相似性的Bandit智能推薦算法對UCB算法進行了改進,并取得了良好的效果:

(1) 簡化了算法計算流程,減少了算法的時間復雜度和空間復雜度:本算法僅需要保存各個服務的UCB值和2.2節式(5)中模型更新所需要的幾個變量,算法的空間復雜度為O(N)(N為服務數量);如2.4節所述模型更新的時間復雜度為O(1)。在3.3節的實驗結果方面在3種集群結構中本文算法的平均推薦時間花費均在50 ms以內也顯示了算法的高效性。

(2) 結合服務的語義相似度這一特征來改進UCB算法最終得到的推薦結果表明用戶真實評分數據和作為推薦依據的UCB值之間具有強相關關系。

4 結 語

本文以具體的無線應用場景為目標,分析總結了常見的推薦系統算法,提出結合服務相似性的Bandit智能推薦模型。該系統使用了強化學習中的UCB算法并增加了隨機采樣過程。該算法時間和空間復雜度較低,能適應無線移動環境下惡劣的通信條件。由于終端內部的推薦算法和終端間的數據傳輸策略相對獨立,該算法的遷移也非常簡單方便。本文通過實驗模擬了場景中的終端在集中式、層次式、分布式體系結構下的服務推薦過程,推薦消耗的時間和推薦準確度令人滿意。

本文提出的結合服務相似性的Bandit智能推薦模型更注重節點內部的Web服務推薦,節點之間的服務推薦采用SimBet算法與PROHET路由算法相結合的尋找策略。在未來的工作中,將考慮結合推薦的上下文環境和移動自組織網絡結構的特點對節點之間的路由算法進行進一步優化。