<mark id="oztn4"></mark>
0
| 本文作者： 奕欣 | 2017-10-10 11:14 | 專題：KDD 2017 |
雷鋒網 AI 科技評論按：在KDD 2017上，香港科技大學計算機系博士生趙歡作為第一作者的論文 Meta-Graph Based Recommendation Fusion over Heterogeneous Information Networks 被 research track接收并做口頭報告。經雷鋒網 AI 科技評論邀請，趙歡為雷鋒網獨家供稿，分享了團隊此項研究的核心思想、算法框架及實驗結果。
本文主要介紹 KDD 2017 的一篇有關推薦系統的論文：「Meta-Graph Based Recommendation Fusion over Heterogeneous Information Networks」 這篇論文被KDD 2017的research track接收并做口頭報告(錄取率8.6%)。作者包括：
第一作者趙歡，香港科技大學計算機系博士生，研究方向為「異構網絡與推薦系統」；
第二作者姚權銘，香港科技大學計算機博士生，研究方向為「機器學習優化算法研究」，2016 Google Fellowship 獲得者；
第三作者李健達，香港科技大學碩士畢業生，本科畢業于上海交通大學。
第四作者宋陽秋，香港科技大學助理教授，研究方向為「知識圖譜、文本數據挖掘和自然語言處理」；
第五作者李迪麟，香港科技大學正教授，研究方向為「信息檢索，推薦系統，移動數據管理」。
在這個信息爆炸的時代，推薦系統不僅能幫助用戶更快地獲取感興趣的信息，同時也能創造巨大的商業價值，目前全球主要的互聯網公司都會有專門的推薦團隊來從事推薦算法的研究，旨在提升自己的業務效果。
傳統的推薦系統中，最常見的方法就是「協同過濾」，典型的例子就是我們在電商網站見到的「購買該商品的用戶也購買了/也在看」。協同過濾方法一般包括兩種方式，即基于用戶和基于商品的協同過濾，以及矩陣分解 (Matrix Factorization)。自從 2007 年 Netflix 百萬大獎的推薦系統比賽以來，矩陣分解的方法開始變得流行。盡管矩陣分解可以獲得不錯的推薦效果，但也有明顯的問題：
1）稀疏性(Sparsity)。現實生活里的評分矩陣往往非常稀疏，因為單個用戶評分的商品是非常少的；
2）冷啟動(Cold Start)。新產生的用戶和商品往往都沒有評分。
上述兩種情況都會嚴重影響矩陣分解的預測準確性。
除了這兩個基本的問題以外，矩陣分解還有一個更嚴重的問題：它很難適應現在的推薦系統。因為當下的推薦系統需要處理的特征并非只有評分信息，而是各種各樣的信息（稱作 Side Information），比如商品的描述，圖片，用戶的好友關系等。我們可以看圖 1 的例子，這是 Yelp 上一個餐館的詳情頁。
圖 1：Yelp 上的一個詳情頁，Royal House
從圖中，我們可以看到，除了評分信息之外，還有餐館的地理位置，用戶上傳的圖片，評論等信息。顯然，在給用戶推薦餐館的過程中，這些信息都非常重要，但它們又很難融入到現有的矩陣分解的模型中。因此，我們需要一個全新的框架來解決這樣的問題。這是我們此次 KDD 工作的核心思想：「我們用 HIN 來對 side information 進行建模，同時設計了一套有效的算法框架，從而獲得更好的推薦效果」。
異構信息網絡 (Hetegeneous Information Network 以下簡稱 HIN），是由 UIUC 的 Han Jiawei 和 UCLA 的 Sun Yizhou 在 2011 年的 VLDB 論文中首次提出 [1]。
簡單地理解，HIN 就是一個有向圖，圖中的節點和邊都可以有不同的類型，如下圖，是一個從上面 Yelp 詳情頁抽取出來的 HIN。節點可以代表不同類型的實體，比如 user, review, restaurant 等, 邊代表不同類型的關系，比如 Check-in, Write, Mention 等。
利用 HIN，我們就可以將各種各樣的 side information 統一起來，接下來我們將介紹如何在 HIN 這個框架下完成我們的推薦過程。
在Sun Yizhou的VLDB2011的論文中，除了提出HIN，同時也提出了meta-path，用來計算兩個節點之間的相似度。meta-path就是一個節點的sequence，節點與節點之間由不同類型的邊連接，也就是不同的關系。
比如從上圖中的HIN，我們可以設計meta-path：
它表示的意義就是兩個用戶在同一個餐館簽到。
我們可以提取一條meta-path的實例：
那我們可以衡量
和 Bar Louie 之間的相似度，當有越多的meta-path實例來連接
和 Bar Louie，它們之間的相似度就越大，我們也會可以給
推薦 Bar Louie。我們可以發現，這條 meta-path 正好對應我們熟悉的「基于用戶的協同過濾」，即經常去 Royal House 的人也會去 Bar Louie。
從這個例子我們可以看出，對于推薦系統來說，HIN和meta-path有兩個好處：
1) 非常完美地將各種side information融入到一個統一的模型；
2）利用meta-path，可以設計出各種各樣的推薦策略，除了推薦準確性提升之外，還能提供「可解釋性」。
當然，在計算節點相似度這個任務上，meta-path也有自己的問題：「無法處理復雜的關系」。比如兩個用戶之間有如下連接性。
對應到圖上的實例，
和 
分別給 Royal House 寫了一個評論，不僅給了五星好評，還在評論里同時提到了這里的「Seafood」，可以說這兩個用戶對餐館的偏好非常相似。但是這樣一種相似性，meta-path 無法對其進行建模。為了解決這個問題，有兩篇論文 ( KDD 16 [2] 和 ICDE 16 [3]) 提出了一種更為通用通用的結構: meta-graph（也叫 meta-Structure）。相比 meta-path 要求必須是 sequence 的結構，meta-graph 只要求「一個起點和一個終點，中間結構并不限制」，這樣大大提升了靈活性。因此，在我們的 KDD 論文中，我們采用了 meta-graph 這樣一種結構，來計算用戶和商品之間的相似度。在實踐中，我們可以設計 
條 meta-graph，從而得到多種商品和用戶之間的相似度，也就是 
個相似度矩陣。
通過HIN和mega-graph，我們完美地將各種各樣的side information統一到一個框架中。接下來的問題就是「如何設計更好的推薦算法」。在這個論文里，我們用到了「MF + FM」的框架，簡單來說: 分別對
個相似度矩陣進行矩陣分解，得到
組用戶和商品的隱式特征，然后將所有的特征拼起來，使用分解因子機進行訓練和評分預測。
對于一個樣本，即用戶-商品對，我們分別可以得到
組特征，每組的維度為
（在矩陣分解的時候，我們設定秩為
）。那么我們就可以拼出下圖中所以的一個維度為
的特征向量。
Factorization Machine (FM) [4] 是 2010 年在 ICDM 上提出一種模型，由于可以對特征之間的高階關系進行建模，以及對二階參數進行低秩分解，因而在評分預測這個推薦任務上取得了非常好的效果。在實踐中，我們一般使用二階關系：
其中，
是一階參數，
是二階參數。為了學出
和
，我們使用了 Least Squared loss：
一般在 FM 的訓練過程中，往往也會加上
和
的正則項來防止過擬合，用的最多的就是 
。但是，在我們的工作中，由于我們會設計多條 meta-graph，并不是每條 meta-graph 都有用，為了自動選擇出有用的 meta-graph，我們放棄了
，而選擇
，也稱作 group lasso。在我們的算法框架中，我們是以 meta-graph 為單位來構造用戶和商品的隱式特征的，因此，每條 meta-graph 對應一組用戶和商品的隱式特征。一旦某條 meta-graph 沒有用，那么它對應的一組特征都應該被去掉，這就是我們采用 group lasso 來做正則項的動機。
使用 group lasso 正則項之后，目標函數優化就變成了一個非凸非光滑（non-convex, non-smooth）的問題，我們使用了鄰近梯度算法（proximal gradient）算法來求解它。
以上就是我們的算法框架，接下來，我們將通過部分實驗結果，來證明我們算法的優勢。
我們使用了 Yelp 和 Amazon 這兩個數據集，這兩個都是非常經典的推薦系統數據集，同時也包含了豐富的 side information。數據的具體統計數據，可以參看我們的論文，這里只展示我們用到的 meta-graph，如下圖。在 Yelp 上，我們設計了 9 條 meta-graph，在 amazon 上，我們設計了 6 種 meta-graph。
在推薦系統中，我們一般用
來評估評分預測的好壞，越小意味著推薦效果越好。
其中，
是實際評分，
是預測評分，
是 test set 的個數。
在實驗中，我們和一些常見的方法相比，包括基于矩陣分解和基于HIN的方法。具體結果如下圖：
上圖中，RegSVD 和 FMR 是基于矩陣分解的方法，HeteRec [5] 和 SemRec [6] 分別是 WSDM14 和 CIKM15 上的兩篇論文，在 HIN 上用 meta-path 來進行推薦，FMG 是我們的算法。另外，CIKM-Yelp 和 CIKM-Douban 兩個數據集是 CIKM15 的作者 Shi Chuan 提供給我們的。根據上圖，我們有以下發現：
在所有的數據集上，FMG 打敗了所有的方法，推薦效果取得了不同程度的提升，證明了我們算法的有效性。
在 CIKM-Yelp 和 CIKM-Douban 這兩個數據集，我們使用和 CIKM15 一樣的 meta-path，依然取得了 4.2% 和 3.2% 的提升，進一步證明在 HIN 這個框架下，我們推薦算法的有效性。
在兩種基于 HIN 的方法中，我們發現 SemRec 比 HeteRec 的效果好不少。除去推薦算法的差異，一個重要的不同就是，在 SemRec 中，作者設計了 U→?←U→B 這樣形式的 meta-path，而在 HeteRec，作者使用了 U→B←?→B 這樣形式的 meta-path。在我們的算法中，最終選擇出來有效的 meta-graph，大多就是 U→?←U→B 這樣的形式。這個發現非常有意思，說明通過「用戶協同」的推薦結果效果會更好一些。這個發現也和現實生活中對應，我們獲取感興趣的商品或者餐館，除了興趣本身之外，更多的時候是通過朋友圈里好友推薦而發現。它反過來也能解釋 SemRec 好于 HeteRec。
除了推薦效果的比較，我們還做了其他很多實驗，有興趣的讀者可以去閱讀我們的論文，在這里就不做贅述了。
最后，給我們的論文做一個簡單的總結。近些年，由于移動互聯網和大數據的發展，現在的推薦系統面臨豐富side information場景，傳統的基于矩陣分解的方法已經很難再發揮作用，而基于人工設計的特征工程又極其費勁。通過HIN和meta-graph，我們提供了一種簡單有效的框架，既能夠非常靈活地利用side information來提升推薦效果，同時，還能利用人工設計的meta-graph來保留必要的語義信息，從而對推薦結果提供一定的「可解釋性」。通過實驗，我們也證明了這個框架的有效性。
這個論文的代碼和數據也已經公布到Github上： https://github.com/HKUST-KnowComp/FMG 。
Sun Yizhou et.al., PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks. VLDB 2011
Huang Zhipeng et.al., Meta Structure: Computing Relevance in Large Heterogeneous Information Networks. KDD 2016
Fang Yuan et.al., Semantic Proximity Search on Graphs with Metagraph-based Learning. ICDE 2016
Rendle et.al., Factorization Machines. ICDM 2010
Yu Xiao et.al., Personalized Entity Recommendation: A Heterogeneous Information Network Approach. WSDM 2014
Shi Chuan et.al., Semantic Path based Personalized Recommendation on Weighted Heterogeneous Information Networks. CIKM 2015
雷峰網特約稿件，未經授權禁止轉載。詳情見轉載須知。
專題
