結(jié)合服務(wù)相似性的Bandit智能推薦模型

周禮亮 李 濤

(中國電子科技集團(tuán)公司航空電子信息系統(tǒng)技術(shù)重點實驗室 四川 成都 610036)

0 引 言

Web服務(wù)是一種具有統(tǒng)一標(biāo)準(zhǔn)的、平臺無關(guān)的網(wǎng)絡(luò)資源服務(wù)提供方式,因為其部署簡單、調(diào)用方便等特性,在電子商務(wù)、分布式計算等領(lǐng)域都有著廣泛的應(yīng)用。隨著計算機(jī)技術(shù)的發(fā)展,互聯(lián)網(wǎng)中的Web服務(wù)也日益豐富[1]。目前,關(guān)于Web服務(wù)的推薦已有大量研究。

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

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

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

1 相關(guān)研究

1.1 基于強化學(xué)習(xí)的推薦算法

強化學(xué)習(xí)是一種能夠適應(yīng)環(huán)境的機(jī)械學(xué)習(xí)方法,它的特點在于利用智能體(Agent)在環(huán)境交互中的反饋進(jìn)行模型訓(xùn)練[2-3]。強化學(xué)習(xí)以其在復(fù)雜非線性系統(tǒng)中表現(xiàn)出優(yōu)秀的性能被廣泛應(yīng)用于四類領(lǐng)域:過程控制、任務(wù)調(diào)度、機(jī)器人設(shè)計、游戲[4]。

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

1.2 移動服務(wù)推薦

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

2 完全由終端集群組成的無線移動環(huán)境下的服務(wù)推薦方法

在算法設(shè)計的過程中,除充分考慮終端內(nèi)Web服務(wù)選擇的準(zhǔn)確度和效率外,還應(yīng)當(dāng)兼顧終端間信息的傳遞效率。為保證信息在終端間傳遞的高效性,終端內(nèi)Web服務(wù)的推薦應(yīng)具有較低的時間和空間復(fù)雜度。

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

2.1 初始評分的計算

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

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

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

(1)

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

2.2 評分的調(diào)整與更新——UCB算法

在初始評分已存在的情況下,推薦時就可以直接選擇評分最高的服務(wù)。但這種方法存在一個明顯的缺陷:部分服務(wù)在初始化時利用的評分信息很少,其評分等于或接近于所有終端產(chǎn)生的所有評分的均值,導(dǎo)致這部分終端在推薦時很難被選中,由此埋沒了部分潛在的適合服務(wù)。為了解決此問題,本項目使用強化學(xué)習(xí)算法對評分進(jìn)行適當(dāng)?shù)恼{(diào)整。

UCB算法基于兩個觀測:

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

(2)

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

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

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

(3)

(4)

(5)

2.3 服務(wù)的選擇策略

(6)

2.4 算法流程

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

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

輸出:推薦的服務(wù)target。

fori=1 toNdo

if 當(dāng)前終端未對第i個終端進(jìn)行評分 then

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

end if

end for

fori=1 toNdo

end for

fori=1 toNdo

end for

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

returntarget

推薦算法完成后,需要請發(fā)出推薦請求的終端給出評分,以作為反饋數(shù)據(jù)更新算法。如果數(shù)據(jù)集中已經(jīng)包含了對服務(wù)的評分,則可以使用評分進(jìn)行預(yù)訓(xùn)練。

2.5 分析和討論

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

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

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

3 實驗與結(jié)果分析

3.1 數(shù)據(jù)集

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

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

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

得到原始數(shù)據(jù)后,服務(wù)記錄將隨機(jī)放入不同終端中。

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

3.2 評價指標(biāo)的選擇

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

在上述算法中,將K取不同的值并進(jìn)行重復(fù)實驗,得到不同的評分平均值及標(biāo)準(zhǔn)差。最終可以繪制出評分平均值和標(biāo)準(zhǔn)差關(guān)于K值的曲線圖并進(jìn)行分析。

3.3 結(jié)果分析

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

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

(a) 集中式結(jié)構(gòu)

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

表1 實驗結(jié)果

3.4 分析和討論

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

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

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

4 結(jié) 語

本文以具體的無線應(yīng)用場景為目標(biāo),分析總結(jié)了常見的推薦系統(tǒng)算法,提出結(jié)合服務(wù)相似性的Bandit智能推薦模型。該系統(tǒng)使用了強化學(xué)習(xí)中的UCB算法并增加了隨機(jī)采樣過程。該算法時間和空間復(fù)雜度較低,能適應(yīng)無線移動環(huán)境下惡劣的通信條件。由于終端內(nèi)部的推薦算法和終端間的數(shù)據(jù)傳輸策略相對獨立,該算法的遷移也非常簡單方便。本文通過實驗?zāi)M了場景中的終端在集中式、層次式、分布式體系結(jié)構(gòu)下的服務(wù)推薦過程,推薦消耗的時間和推薦準(zhǔn)確度令人滿意。

本文提出的結(jié)合服務(wù)相似性的Bandit智能推薦模型更注重節(jié)點內(nèi)部的Web服務(wù)推薦,節(jié)點之間的服務(wù)推薦采用SimBet算法與PROHET路由算法相結(jié)合的尋找策略。在未來的工作中,將考慮結(jié)合推薦的上下文環(huán)境和移動自組織網(wǎng)絡(luò)結(jié)構(gòu)的特點對節(jié)點之間的路由算法進(jìn)行進(jìn)一步優(yōu)化。