在這個信息多到快要爆炸的時代，推薦系統(tǒng)在其中承擔(dān)了重大的責(zé)任。不僅能讓用戶更快地獲取有用的信息，同時也給廠商帶來了另一中的推廣方式，為廠商創(chuàng)造巨大的商業(yè)價值，現(xiàn)在許多的互聯(lián)網(wǎng)公司都會有自己的目推薦團隊來從事推薦算法的研究，旨在提升自己的業(yè)務(wù)效果。

　　傳統(tǒng)的推薦系統(tǒng)中，最常見的方法就是「協(xié)同過濾」，典型的例子就是我們在電商網(wǎng)站見到的「購買該商品的用戶也購買了/也在看」。協(xié)同過濾方法一般包括兩種方式，即基于用戶和基于商品的協(xié)同過濾，以及矩陣分解 （Matrix Factorization）。自從 2007 年 Netflix 百萬大獎的推薦系統(tǒng)比賽以來，矩陣分解的方法開始變得流行。盡管矩陣分解可以獲得不錯的推薦效果，但也有明顯的問題：

　　1）稀疏性（Sparsity）。現(xiàn)實生活里的評分矩陣往往非常稀疏，因為單個用戶評分的商品是非常少的；

　　2）冷啟動（Cold Start）。新產(chǎn)生的用戶和商品往往都沒有評分。

　　上述兩種情況都會嚴(yán)重影響矩陣分解的預(yù)測準(zhǔn)確性。

　　除了這兩個基本的問題以外，矩陣分解還有一個更嚴(yán)重的問題：它很難適應(yīng)現(xiàn)在的推薦系統(tǒng)。因為當(dāng)下的推薦系統(tǒng)需要處理的特征并非只有評分信息，而是各種各樣的信息（稱作 Side Information），比如商品的描述，圖片，用戶的好友關(guān)系等。我們可以看圖 1 的例子，這是 Yelp 上一個餐館的詳情頁。

　　圖 1：Yelp 上的一個詳情頁，Royal House

　　從圖中，我們可以看到，除了評分信息之外，還有餐館的地理位置，用戶上傳的圖片，評論等信息。顯然，在給用戶推薦餐館的過程中，這些信息都非常重要，但它們又很難融入到現(xiàn)有的矩陣分解的模型中。因此，我們需要一個全新的框架來解決這樣的問題。這是我們此次 KDD 工作的核心思想：「我們用 HIN 來對 side information 進行建模，同時設(shè)計了一套有效的算法框架，從而獲得更好的推薦效果」。

　　算法框架

　　預(yù)備知識

　　異構(gòu)信息網(wǎng)絡(luò) （Hetegeneous Information Network 以下簡稱 HIN），是由 UIUC 的 Han Jiawei 和 UCLA 的 Sun Yizhou 在 2011 年的 VLDB 論文中首次提出 ［1］。

　　簡單地理解，HIN 就是一個有向圖，圖中的節(jié)點和邊都可以有不同的類型，如下圖，是一個從上面 Yelp 詳情頁抽取出來的 HIN。節(jié)點可以代表不同類型的實體，比如 user， review， restaurant 等， 邊代表不同類型的關(guān)系，比如 Check-in， Write， Mention 等。

?

　　利用 HIN，我們就可以將各種各樣的 side information 統(tǒng)一起來，接下來我們將介紹如何在 HIN 這個框架下完成我們的推薦過程。

　　從meta-path到meta-graph

　　在Sun Yizhou的VLDB2011的論文中，除了提出HIN，同時也提出了meta-path，用來計算兩個節(jié)點之間的相似度。meta-path就是一個節(jié)點的sequence，節(jié)點與節(jié)點之間由不同類型的邊連接，也就是不同的關(guān)系。

　　比如從上圖中的HIN，我們可以設(shè)計meta-path：

　　它表示的意義就是兩個用戶在同一個餐館簽到。

　　我們可以提取一條meta-path的實例：

　　那我們可以衡量和 Bar Louie 之間的相似度，當(dāng)有越多的meta-path實例來連接和 Bar Louie，它們之間的相似度就越大，我們也會可以給推薦 Bar Louie。我們可以發(fā)現(xiàn)，這條 meta-path 正好對應(yīng)我們熟悉的「基于用戶的協(xié)同過濾」，即經(jīng)常去 Royal House 的人也會去 Bar Louie。

　　從這個例子我們可以看出，對于推薦系統(tǒng)來說，HIN和meta-path有兩個好處：

　　1） 非常完美地將各種side information融入到一個統(tǒng)一的模型；

　　2）利用meta-path，可以設(shè)計出各種各樣的推薦策略，除了推薦準(zhǔn)確性提升之外，還能提供「可解釋性」。

　　當(dāng)然，在計算節(jié)點相似度這個任務(wù)上，meta-path也有自己的問題：「無法處理復(fù)雜的關(guān)系」。比如兩個用戶之間有如下連接性。

?

　　對應(yīng)到圖上的實例， 和 分別給 Royal House 寫了一個評論，不僅給了五星好評，還在評論里同時提到了這里的「Seafood」，可以說這兩個用戶對餐館的偏好非常相似。但是這樣一種相似性，meta-path 無法對其進行建模。為了解決這個問題，有兩篇論文 （ KDD 16 ［2］ 和 ICDE 16 ［3］） 提出了一種更為通用通用的結(jié)構(gòu)： meta-graph（也叫 meta-Structure）。相比 meta-path 要求必須是 sequence 的結(jié)構(gòu)，meta-graph 只要求「一個起點和一個終點，中間結(jié)構(gòu)并不限制」，這樣大大提升了靈活性。因此，在我們的 KDD 論文中，我們采用了 meta-graph 這樣一種結(jié)構(gòu)，來計算用戶和商品之間的相似度。在實踐中，我們可以設(shè)計 條 meta-graph，從而得到多種商品和用戶之間的相似度，也就是 個相似度矩陣。

　　推薦過程： 矩陣分解（MF） + 分解因子機（Factorization Machine）

　　通過HIN和mega-graph，我們完美地將各種各樣的side information統(tǒng)一到一個框架中。接下來的問題就是「如何設(shè)計更好的推薦算法」。在這個論文里，我們用到了「MF + FM」的框架，簡單來說： 分別對個相似度矩陣進行矩陣分解，得到組用戶和商品的隱式特征，然后將所有的特征拼起來，使用分解因子機進行訓(xùn)練和評分預(yù)測。

　　對于一個樣本，即用戶-商品對，我們分別可以得到組特征，每組的維度為（在矩陣分解的時候，我們設(shè)定秩為）。那么我們就可以拼出下圖中所以的一個維度為的特征向量。

　　Factorization Machine （FM） ［4］ 是 2010 年在 ICDM 上提出一種模型，由于可以對特征之間的高階關(guān)系進行建模，以及對二階參數(shù)進行低秩分解，因而在評分預(yù)測這個推薦任務(wù)上取得了非常好的效果。在實踐中，我們一般使用二階關(guān)系：

　　其中，是一階參數(shù)，是二階參數(shù)。為了學(xué)出 和，我們使用了 Least Squared loss：

　　特征選擇： Group Lasso

　　一般在 FM 的訓(xùn)練過程中，往往也會加上和的正則項來防止過擬合，用的最多的就是 。但是，在我們的工作中，由于我們會設(shè)計多條 meta-graph，并不是每條 meta-graph 都有用，為了自動選擇出有用的 meta-graph，我們放棄了，而選擇，也稱作 group lasso。在我們的算法框架中，我們是以 meta-graph 為單位來構(gòu)造用戶和商品的隱式特征的，因此，每條 meta-graph 對應(yīng)一組用戶和商品的隱式特征。一旦某條 meta-graph 沒有用，那么它對應(yīng)的一組特征都應(yīng)該被去掉，這就是我們采用 group lasso 來做正則項的動機。

　　使用 group lasso 正則項之后，目標(biāo)函數(shù)優(yōu)化就變成了一個非凸非光滑（non-convex， non-smooth）的問題，我們使用了鄰近梯度算法（proximal gradient）算法來求解它。

　　以上就是我們的算法框架，接下來，我們將通過部分實驗結(jié)果，來證明我們算法的優(yōu)勢。

　　實驗結(jié)果

　　數(shù)據(jù)集和評估標(biāo)準(zhǔn)

　　我們使用了 Yelp 和 Amazon 這兩個數(shù)據(jù)集，這兩個都是非常經(jīng)典的推薦系統(tǒng)數(shù)據(jù)集，同時也包含了豐富的 side information。數(shù)據(jù)的具體統(tǒng)計數(shù)據(jù)，可以參看我們的論文，這里只展示我們用到的 meta-graph，如下圖。在 Yelp 上，我們設(shè)計了 9 條 meta-graph，在 amazon 上，我們設(shè)計了 6 種 meta-graph。

?

　　在推薦系統(tǒng)中，我們一般用來評估評分預(yù)測的好壞，越小意味著推薦效果越好。

　　其中，是實際評分，是預(yù)測評分，是 test set 的個數(shù)。

　　推薦效果

　　在實驗中，我們和一些常見的方法相比，包括基于矩陣分解和基于HIN的方法。具體結(jié)果如下圖：

?

　　上圖中，RegSVD 和 FMR 是基于矩陣分解的方法，HeteRec ［5］ 和 SemRec ［6］ 分別是 WSDM14 和 CIKM15 上的兩篇論文，在 HIN 上用 meta-path 來進行推薦，F(xiàn)MG 是我們的算法。另外，CIKM-Yelp 和 CIKM-Douban 兩個數(shù)據(jù)集是 CIKM15 的作者 Shi Chuan 提供給我們的。根據(jù)上圖，我們有以下發(fā)現(xiàn)：

　　在所有的數(shù)據(jù)集上，F(xiàn)MG 打敗了所有的方法，推薦效果取得了不同程度的提升，證明了我們算法的有效性。

　　在 CIKM-Yelp 和 CIKM-Douban 這兩個數(shù)據(jù)集，我們使用和 CIKM15 一樣的 meta-path，依然取得了 4.2% 和 3.2% 的提升，進一步證明在 HIN 這個框架下，我們推薦算法的有效性。

　　在兩種基于 HIN 的方法中，我們發(fā)現(xiàn) SemRec 比 HeteRec 的效果好不少。除去推薦算法的差異，一個重要的不同就是，在 SemRec 中，作者設(shè)計了 U→?←U→B 這樣形式的 meta-path，而在 HeteRec，作者使用了 U→B←?→B 這樣形式的 meta-path。在我們的算法中，最終選擇出來有效的 meta-graph，大多就是 U→?←U→B 這樣的形式。這個發(fā)現(xiàn)非常有意思，說明通過「用戶協(xié)同」的推薦結(jié)果效果會更好一些。這個發(fā)現(xiàn)也和現(xiàn)實生活中對應(yīng)，我們獲取感興趣的商品或者餐館，除了興趣本身之外，更多的時候是通過朋友圈里好友推薦而發(fā)現(xiàn)。它反過來也能解釋 SemRec 好于 HeteRec。

　　總結(jié)

　　近些年，由于移動互聯(lián)網(wǎng)和大數(shù)據(jù)的發(fā)展，現(xiàn)在的推薦系統(tǒng)面臨豐富side information場景，傳統(tǒng)的基于矩陣分解的方法已經(jīng)很難再發(fā)揮作用，而基于人工設(shè)計的特征工程又極其費勁。通過HIN和meta-graph，我們提供了一種簡單有效的框架，既能夠非常靈活地利用side information來提升推薦效果，同時，還能利用人工設(shè)計的meta-graph來保留必要的語義信息，從而對推薦結(jié)果提供一定的「可解釋性」。通過實驗，我們也證明了這個框架的有效性。