題目： Personalized Recommendations using Knowledge Graphs: A Probabilistic Logic Programming Approach（一種概率邏輯編程方法）
論文鏈接：
代碼：

想法

（1）推薦系統(tǒng)就是求出user和item的特征表示，最后通過一個公式來解決預(yù)測問題！
（2） wikifier or an entity linker
（3）真的很難理解，后面基本都是原地翻譯的！看不下去，未來再回來看吧

創(chuàng)新點(diǎn)

• 元路徑的數(shù)目首先是不需要定的，超參數(shù)優(yōu)化！
• 將外部知識用到ProPPR是首次。
• 這里通過ProPPR根據(jù)歷史數(shù)據(jù)來得到seedset！ 之后才用于推薦！！！

ABSTRACT

難點(diǎn)

content-based 和 CF結(jié)合是趨勢，最近已經(jīng)有工作集中到用外在的KGs來補(bǔ)充content-based推薦系統(tǒng)

我們

我們使用多用途的概率邏輯系統(tǒng)（ProPPR）的三種方法來制作基于KG的推薦系統(tǒng)。 模型最簡單EntitySim，僅僅使用了圖的連接； 之后擴(kuò)展該模型到TypeSim，也用了實體的類型來增強(qiáng)它的泛化能力； 之后，開發(fā)一個基于潛在因素模型的圖表，GraphLF。

同時我們也證明了，在解決冷啟動和數(shù)據(jù)稀疏問題時，KG有很大的優(yōu)勢，但是有更多的數(shù)據(jù)時，KG graph反而變的冗余。

數(shù)據(jù)集： Yelp、MovieLens-100K

Keywords：基于知識圖的推薦; 概率邏輯編程; 基于圖的矩陣分解

1. 介紹

社交方法最適合解決用戶多而項目相對較少的問題，基于內(nèi)容的最適合解決冷啟動和長尾的設(shè)定。 而一個重要的方向就是如何利用外在的知識來提高基于內(nèi)容的推薦系統(tǒng)。

與基于元路徑來推斷用戶對item的方法不同， 我們的方法將問題表述為一個概率推理和學(xué)習(xí)任務(wù)，提出了三種建議的方法。 而且在其中，許多像特定的元路徑或者是元路徑的長度的工程問題被消除，這樣可以使得系統(tǒng)能夠發(fā)現(xiàn)元路徑方法的更多變體。

EntitySim，最簡單的方法，方法是學(xué)習(xí)用戶在內(nèi)容上的偏愛，并利用KG的連接結(jié)構(gòu)來做出預(yù)測。

TypeSim，在某些情況下，還可以獲得關(guān)于內(nèi)容的類型信息。因此本方法基于EntitySim但是額外的建立了Type流行度和Type相似性模型。 與【27】中相似，【27】也使用類型優(yōu)化路徑選擇

GraphLF：最復(fù)雜的模型提出,是一個潛在的因子分解模型知識圖,和類型無關(guān)， 即它不需要鍵入類型KG

除此之外，本論文中用實驗證明，隨著密度的變化，圖連接結(jié)構(gòu)就足夠了，類型圖反而是冗余的。 更大的數(shù)據(jù)密度下，甚至KG本身就是冗余的。 簡單的方法反而效果很好。

2. Related Work

HeteRec_p提出了KGs來增強(qiáng)推薦系統(tǒng)，從而實現(xiàn)很好的效果。

HyPER系統(tǒng)：最近另一個使用多種信息源的是HyPER系統(tǒng)，里面作者展示了如何推薦使用概率軟邏輯框架。他們創(chuàng)建了規(guī)則來模擬CF風(fēng)格推薦，比如user-based CF中， 梅開三度： 第一度： 使用公式$SimilarUsers(u_1,u_2)\wedge Rating(u_i,i)?Rating(u_2,i)$來推斷，其中$$SimilarUsers(u_1,u_2)$表示的是$u_1$和$u_2$在$k$-nearest 鄰居算法離線計算下兩人是相似的； 第二度： 如果朋友網(wǎng)絡(luò)是可用的，可以利用$Friends(u_1,u_2)\wedge Rating(u_i,i)?Rating(u_2,i)$；梅開三度：如果其它的評分預(yù)測算法比如矩陣分解（MF）可用，然后，他們利用這些規(guī)則歸納出一個集成推薦程序$Ratin{g}_{MF}(u,i)?Rating(u,i)$和$?Ratin{g}_{MF}(u,i)??Rating(u,i)$。 最后，在訓(xùn)練階段，他們使用PSL框架學(xué)習(xí)每個規(guī)則的權(quán)重，該權(quán)重隨后用于預(yù)測測試集中的評分。

和HyPER系統(tǒng)類似，提出了一個 Markov Logic Networks,在該網(wǎng)絡(luò)中，使用貝葉斯網(wǎng)絡(luò)來創(chuàng)建一個hybrid推薦器。 而我們則是使用了外部知識后通用概率推理系統(tǒng)。

而在基于KG的方法中，都是添加各種特殊目的或者是特定領(lǐng)域的知識圖， 或者是添加社交網(wǎng)絡(luò)，計算最相近的鄰居。 使用他人的評級來推薦自己的。

2.1 HeteRec_p

目的是使用metapaths來找到用戶對沒有評級的items的親和度。首先定義什么是元路徑：
Meta-path:

A是node types，R是關(guān)系集合。 之后給定一個meta-path P， 我們使用PathSim的變體—User Preference Diffusion來計算user i和item j在P上的相似度。 所以當(dāng)給定L條原路徑后，可以生成作者定義的L個user-item矩陣${\tilde{R}}^{\left(1\right)},{\tilde{R}}^{\left(2\right)}\dots {\tilde{R}}^{\left(L\right)}$! 每一個${\tilde{R}}^{\left(q\right)}$都可以使用使用低秩矩陣逼近技術(shù)被近似分解為${\tilde{U}}^{(q)}?{\tilde{V}}^{(q)}$。 之后整體模型被表示為$r\left(u_i,v_j\right)={\sum }_{q\in L}{\theta }_q{\hat{U}}_i{}^{(q)}?{\hat{V}}_j^{(q)}$ ，其中前面的參數(shù)是path q的學(xué)習(xí)權(quán)重。

為了個性化推薦，他們會根據(jù)用戶的興趣對其進(jìn)行聚類，之后推薦函數(shù)會定義為：

其中，$C$表示用戶的聚類，$sim(C_k,u_i)$給出一個相似度評分在user i和$k^{th}$聚類之間， 同樣的，前面的參數(shù)是學(xué)習(xí)的權(quán)重。

雖然很好，但是它需要很多超參數(shù)設(shè)定，比如元路徑的數(shù)目、cluster的數(shù)量還有一個包含了實體和連接類型的豐富KG。

3. PROPOSED METHOD

3.1 Preliminaries

Entity是一個可以映射到知識庫和本體的通用的詞來表示句子或者短語。 如果要使用Wikipedia等通用知識庫，需要使用wikifiler和entity linker。

HIN是異構(gòu)信息網(wǎng)絡(luò)，和KGs的區(qū)別是有實體和鏈接的類型映射函數(shù)。
Heterogeneous Information：

V和E是實體和鏈接； 而A和R是實體類型和鏈接類型
這其中需要注意的是： 有兩個函數(shù)$?$和$\psi$可以映射出實體和關(guān)系的類型！但是并未在圖中展示

本文中使用的是寬松版的HIN，也就是有些點(diǎn)沒有類型映射。 如果類型丟失，則只有EntitySim和GraphMF可用。

同樣使用binary user feedback。 如果評分矩陣entry $R_{i,j}$為1就是有行為，否則無行為。

3.2 Running Example

下面我們根據(jù)三個Users來理解知識庫的作用。

（必須得知道這個，后面會用到）從歷史記錄來看，Alice看過了Saving Private Ryan and The Terminal，兩個都使得Steven Spielberg as the Director and Tom Hanks as an Actor。根據(jù)知識庫的設(shè)定 。 而且知識庫也提供了國家和發(fā)行時間得信息。 同樣的，我們也知道Bob和Kumar也看了這兩個電影。 除了看之外，我們還可以包括用戶的動作，比如“回顧”或“喜歡”，如果有的話。鑒于用戶過去的觀看歷史，我們可能想要知道他們觀看新電影Bridge of Spies的可能性。 除此之外，movies之間也是有聯(lián)系的，比如兩者可能是續(xù)集關(guān)系。

3.3 Recommendation as Personalized PageRank

隨機(jī)游走策略就是讓某點(diǎn)按照一定的概率順著各條路徑行走（包括回到自己），在多次游走穩(wěn)定后，這種游走會產(chǎn)生許多沒有意義信息。 比如我們只想要產(chǎn)生user-movie的，而不想產(chǎn)生movie的director-genre-actors。
在上述方法中，沒有控制行走。行走的最終結(jié)果僅由鏈路結(jié)構(gòu)和起始節(jié)點(diǎn)決定。然而最近方法在學(xué)著如何在圖上行走。 通過學(xué)習(xí)一個權(quán)重向量$w$,這個給了一個特征向量${?}_{uv}$在圖$u?>v$中的一個邊，計算邊的力量為$f(w,{?}_{uv})$。
在訓(xùn)練階段，學(xué)習(xí)$w$被認(rèn)為是一個帶有約束的優(yōu)化問題。PageRank正示例節(jié)點(diǎn)的計算值大于負(fù)示例節(jié)點(diǎn)的計算值。而在我們的例子中，積極的例子你用戶看過的電影，消極的例子則是用戶沒看過或者是差評的電影。

3.4 Learning to Recommend using ProPPR

ProPPR代表了Programming with Personalized PageRank，是一個一階概率邏輯系統(tǒng)，接受一個在結(jié)構(gòu)和語義上與邏輯程序和許多facts相似的program，輸出一個entities的排序列表，這些實體根據(jù)facts answer program。ProPPR根據(jù)查詢證明圖(下文解釋)中的個性化PageRank過程對查詢的可能答案進(jìn)行評分。下面將解釋如何進(jìn)行推薦。

首先我們會根據(jù)用戶的歷史數(shù)據(jù)得到用戶感興趣的一組，我們把它稱為seedset。 接下來我們將會將seedset作為該用戶隨機(jī)游走的種子傳入到ProPPR程序中。如上圖展示的， ProPPR程序有三條規(guī)則。 第一規(guī)則表明了如果U已經(jīng)評價了M，M和實體X連接，X和E是相關(guān)的，那么實體E屬于用戶U的seedset； 規(guī)則二，如果兩個實體是一樣的，那么兩個實體被定義為相關(guān)的； 規(guī)則三，如果X和另一個實體Z連接，而Z和E相關(guān)，那么X和E也是相關(guān)的。 最后一條規(guī)則是遞歸的，也就是說可以無限延長。 **Link**和*Type*（isEntity, isItem and isUser）消息形成了我們實例中的知識圖譜。 從知識圖譜中取樣的ProPPR的格式在圖3中。 為了找到屬于Alice的seedset，我們將發(fā)出查詢$Q=seedset(Alice,E)$給ProPPR。 （這里需要注意的是，種子集不是開始的節(jié)點(diǎn)，而是經(jīng)過查詢用戶歷史數(shù)據(jù)后得到的感興趣的一組nodes）

找用戶的seedset

ProPPR以圖搜索的方式執(zhí)行推理。給定像圖2的LP程序和一個查詢集Q，ProPPR開始創(chuàng)建圖像$G$，叫做proof graph。每個圖中的節(jié)點(diǎn)代表一個有待驗證的條件列表。 根節(jié)點(diǎn)$v_0$就是$Q$，然后它遞歸地給$G$添加節(jié)點(diǎn)和邊： 讓$u$成為表單[$R_1,R_2,...,R_k$]的結(jié)點(diǎn)，其中$R_{?}$是它的謂詞。 如果ProPPR能在數(shù)據(jù)庫中找到與$R_1$匹配的fact，然后相應(yīng)的變量就有了界限，$R_1$就會被從列表中移除。 否則，ProPPR在表單$S?S_1,S_2,...,S_l$de LP中尋找規(guī)則，其中$S$匹配$R_1$，如果它發(fā)現(xiàn)了這樣一個規(guī)則，它將創(chuàng)建一個新節(jié)點(diǎn)，其中R1替換為S的主體， $v=[S_1,S_2,...,S_l,R_2,...R_k]$，并且連接$u$和$v$。

在實際運(yùn)行中，$v_0$是seedset(Alice, E)，然后連接到經(jīng)過Rule 1得到的v1=[reviewed(Alice,M), link(M,X), related(X,E), isEntity(E)]； 之后，ProPPR將使用訓(xùn)練（歷史）數(shù)據(jù)為 reviewed 創(chuàng)建兩個節(jié)點(diǎn)v2和v3 [link(Saving Private Ryan,X), related(X,E), isEntity(E)]and[ link(The Terminal,X), related(X,E), isEntity(E)]來代替Saving Private Ryan 和 The Terminal ， 并稱為 M。 ProPPR將使用規(guī)則等等從知識圖中替換X和**related(X,E)**直到它到達(dá)一個謂詞都被替換的節(jié)點(diǎn)。這些節(jié)點(diǎn)是應(yīng)答節(jié)點(diǎn)，因為它們表示原始查詢的完整證明。用于到達(dá)這些節(jié)點(diǎn)的變量綁定可用于回答查詢。例如：

注意，這樣的圖構(gòu)造可能是無限的。因此，ProPPR使用近似接地機(jī)制及時構(gòu)建近似圖，在時間$O(\frac{1}{{\alpha }_{\in }})$，其中$\in$是一個大約的錯誤，$\alpha$是重置參數(shù)。一旦構(gòu)建了這樣一個圖，ProPPR將運(yùn)行一個個性化的PageRank算法，起始節(jié)點(diǎn)為$v_0$，并根據(jù)其PageRank得分對答案節(jié)點(diǎn)進(jìn)行排序

圖2程序的輸出是用戶U的實體的排序列表，其中前K個將會被存儲到U的種子集。 請注意，個性化PageRank評分將那些可以從用戶評價了電影出發(fā) ，有多條短路徑可以到達(dá)的實體排名靠前，相反，相對較遠(yuǎn)的或者是并沒有太多的路徑可以到達(dá)的實體排名靠后。

預(yù)測

在生成每個user的種子集后，我們下一步驟就是訓(xùn)練模型來預(yù)測。 一種方法我們使用圖4中的PRoPPR程序， 它表明如果一個實體E屬于U的種子集，那么用戶U可能喜歡一個電影M，U喜歡E，并且E和另一個實體X相關(guān)，這出現(xiàn)在電影M中（Rule 4）。 謂詞isApplicable為每個用戶控制訓(xùn)練和測試信息。在訓(xùn)練期間，它列出了積極和消極的訓(xùn)練例子，在測試階段，為每個用戶的測試。謂詞related的定義與前面一樣是遞歸的。對于謂詞likesEntity的定義，請注意術(shù)語**{l(U,E)}。這對應(yīng)于用于標(biāo)注使用該規(guī)則的邊的特性。舉個例子，如果規(guī)則是調(diào)用U = Alice和E = Tom Hanks**,那么這個特征就是l(Alice, Tom Hanks)，在訓(xùn)練階段，ProPPR從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)該特征的權(quán)重。在預(yù)測階段，ProPPR使用特征習(xí)得的權(quán)值作為邊緣的權(quán)值。注意，每個user-item pair的這些學(xué)習(xí)權(quán)值與從圖2的種子集生成程序中獲得的排名無關(guān)，因為這些權(quán)值是特定于預(yù)測函數(shù)的。

訓(xùn)練階段，ProPPR使方案的基礎(chǔ)類似于前面討論過的種子集代。EntitySim的一個例子 grounding在圖5中描述，其中Bridge Of Spies和Captain Phillips在Alice的測試?yán)拥募现?#xff0c;我們可能還有其他測試Alice的例子，但如果它們不能用規(guī)則證明(或超過一定的近似誤差)，它們將不會出現(xiàn)在 grounding。ProPPR遵循類似于Backstrom等人在[3]中提出的程序來訓(xùn)練隨機(jī)步行者。通過學(xué)習(xí)一個權(quán)重向量$w$,這個給了一個在圖$u?>v$中的一個邊的特征向量${?}_{uv}$，計算邊的力量為$f(w,{?}_{uv})$。權(quán)值和特征向量的函數(shù)。也就是穿過邊的概率 $P(v\mid u)\propto f\left(\mathbf{w},{\mathbf{\Phi }}_{uv}\right)$. 我們的方法使用$f\left(\mathbf{w},{\mathbf{\Phi }}_{uv}\right)=e^{w?{\mathbf{\Phi }}_{uv}}$.
在訓(xùn)練階段，學(xué)習(xí)$w$被認(rèn)為是一個帶有約束的優(yōu)化問題。PageRank正示例節(jié)點(diǎn)的計算值大于負(fù)示例節(jié)點(diǎn)的計算值。

其中，是用w得到的邊權(quán)計算得到的PageRank向量p。ProPPR所使用的公式6的優(yōu)化函數(shù)是標(biāo)準(zhǔn)的正負(fù)對數(shù)損失函數(shù)，而不是[3]中使用的成對損失函數(shù)。為了學(xué)習(xí)w，我們使用AdaGrad[8]來代替[3]中使用的準(zhǔn)牛頓方法和[26]中使用的SGD。將AdaGrad使用的初始學(xué)習(xí)率和正則化參數(shù)μ設(shè)為1。關(guān)于ProPPR的詳細(xì)描述，請讀者參閱[26]和[25]。

3.5 Approach 2: TypeSim

EntitySim方法只使用知識圖鏈接來了解用戶的偏好，然而，回想一下，我們實際上使用的是一個異構(gòu)信息網(wǎng)絡(luò)，除了鏈接信息之外，我們還知道實體的“類型”。例如，我們知道New
York City的類型是City，Tom Hanksis的類型是Actor。為了利用這些額外的類型信息，我們將EntitySim方法擴(kuò)展為typesim方法，如圖6所示。

TypeSim模型通過使用p(T)來學(xué)習(xí)實體類型提供的總體可預(yù)測性，從而對規(guī)則10中每個節(jié)點(diǎn)類型的普遍流行程度進(jìn)行建模。例如，類型actor的節(jié)點(diǎn)可能比類型Country的節(jié)點(diǎn)更深入地了解用戶的偏好。注意，學(xué)習(xí)權(quán)重不是針對用戶的，因此它的權(quán)重是由所有用戶共享的。與規(guī)則10類似，在規(guī)則9中，模型學(xué)習(xí)實體本身提供的整體可預(yù)測性，獨(dú)立于使用p(E)的用戶。例如，史蒂文·斯皮爾伯格導(dǎo)演的電影可能比其他不太知名的導(dǎo)演的電影更受歡迎。Type-Sim也使用規(guī)則11和12建模兩種類型之間的一般遍歷概率。例如，與country→Movie相比，Actor→Movie在圖表上的遍歷更具預(yù)測性。這些權(quán)重被納入到規(guī)則7所示的entitysimas的預(yù)測規(guī)則中。

3.6 Approach 3: GraphLF

協(xié)作過濾(CF)最成功的類型之一是潛在因子(LF)模型[15]。他們試圖發(fā)現(xiàn)描述每個對象的隱藏維度，從而將用戶和項目映射到相同的特性空間，以提高推薦性能。Koren等人在[15]中指出，對于電影來說，潛在因素可能衡量明顯的維度，如喜劇與戲劇，動作的數(shù)量，或兒童取向，以及定義不太明確的維度，如角色發(fā)展的深度，或古怪，甚至無法解釋的維度。對于用戶來說，每個因素衡量的是用戶對在相應(yīng)因素中得分較高的電影的喜愛程度。奇異值分解(Singular Value Decomposition, SVD)是生成推薦LF模型的常用方法之一。SVD方法在每個隱藏維度上為用戶和項目分配值，同時在預(yù)測和實際評級矩陣上最小化損失函數(shù)。
協(xié)同過濾方法的主要吸引力在于，它們不需要任何關(guān)于用戶或物品的知識，只根據(jù)評級矩陣進(jìn)行預(yù)測。類似地，基于潛在因素的CF模型的主要吸引力在于，它們基于評分?jǐn)?shù)據(jù)開發(fā)用戶和項目的一般表示，這些評分?jǐn)?shù)據(jù)更一般化，通常在原始數(shù)據(jù)中無法識別。

鑒于我們可以訪問通過不同實體連接條目的KG，我們在本文中提出的第三種方法，GraphLF，集成了潛在因子分解和基于圖的推薦。圖7定義了整個規(guī)則集。其主要規(guī)則是潛因子相似性SIMLF規(guī)則(17)和(18)的定義。本質(zhì)上，兩個輸入實體X和Y的SIMLF是通過首先選擇一個維度，然后測量x和y 伴隨著 d的值來測量的。如果兩個X和Y的值都很高，那么它們的相似度評分也會很高。一個實體X和維度的值，val(X,D)在訓(xùn)練階段從數(shù)據(jù)中學(xué)習(xí)，如規(guī)則(18)中定義的那樣。
注意，規(guī)則(16)中兩個相關(guān)實體related(X,Y)相關(guān)性的遞歸定義現(xiàn)在如何改變，以解釋它們之間除了存在聯(lián)系之外的潛在因素相似性。此外，原來的預(yù)測規(guī)則在rule(13)中已經(jīng)更改，以使用用戶和實體之間的新關(guān)聯(lián)評分。本質(zhì)上，規(guī)則(14)中related(U,E)的定義用用戶和屬于其種子集的實體之間的潛在因子相似性simlf (U,E)替換了先前的謂詞LikesEntity (U,E)。因此，模型不再學(xué)習(xí)每個user-entity對的權(quán)重，而是沿著每個維度分別學(xué)習(xí)用戶和實體的權(quán)重。
同樣需要注意的是，與type sim 和 heterec_p不同，GraphLF是類型無關(guān)的。類型并不總是可用的，特別是在像Wikipedia圖這樣的通用圖的情況下。因此，類型不可知是一個理想的屬性，可以提高其對廣泛數(shù)據(jù)域的適用性。

3.7 Model Complexity

讓n是用戶的數(shù)量和m是items的。即不同實體的數(shù)量和類型。那么，本文提出的每種方法所學(xué)習(xí)的參數(shù)個數(shù)表征的模型復(fù)雜性如下所示:

• EntitySim-O(n)：在這種方法中，我們每個用戶-實體對學(xué)習(xí)一個參數(shù)。然而，通過這些規(guī)則，我們限制從該用戶的種子集中選擇實體，該種子集的大小是常數(shù)。
• TypeSim-O(n+e+$t^2$)：除了學(xué)習(xí)EntitySim的這些參數(shù)外，它還學(xué)習(xí)每個實體和類型的+t權(quán)重。此外，它還學(xué)習(xí)導(dǎo)致附加參數(shù)的類型對之間的類型關(guān)聯(lián)。
• GraphLF-O(n+m+e):對于每個用戶、實體和項目，我們學(xué)習(xí)與潛在維度相對應(yīng)的固定數(shù)量的權(quán)重
  在典型領(lǐng)域中，我們期望$t?m$，因此，從參數(shù)的數(shù)量來看，EntitySimis本文提出的模型中最簡單的，graphlfi是本文提出的模型中較為復(fù)雜的

4. EXPERIMENTS AND RESULTS

4.1 Datasets

4.3 Performance Comparison on Yelp and IM100K

4.5 Effect of Dataset Density on Performance

總結(jié)

以上是生活随笔為你收集整理的（十四）【RecSys 2016】Personalized Recommendations using Knowledge Graphs: A Probabilistic【看不懂】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。