一種高效演算法的應用，將淘寶“有好貨”銷售總額提升2.75%
眾所周知，以淘寶為代表的電商平臺通常會設計複雜的推薦策略以達到提高使用者購買率的目的。然而目前的電商推薦系統通常僅依賴使用者自身的歷史購買行為為其作出推薦。
雖然已有大量研究表明使用者的購買行為會顯著受到朋友購買行為的影響（即社會推薦），電商平臺中所缺乏的可靠信任關係，成為社會推薦這一推薦策略成功落地的最大障礙。
為此，本文以阿里巴巴淘寶平臺上推薦系統所面臨的實際問題為例，探討如何推斷大規模圖中使用者間的信任關係。
以上圖為例，已知某些使用者之間存在相互信任的關係，例如家庭關係、同學關係以及同事關係等，如何推薦其他使用者之間的信任關係？
為解決該問題，我們提出了一個同時考慮關係之間的二元關聯關係以及三元關聯關係的因子圖模型，基於此近一步提出一個效果相當但效率提升1000倍以上的近似模型。
我們將提出的模型應用到了阿里巴巴淘寶平臺的實際業務場景中，A/B測試結果證明將模型所發現的信任關係應用到推薦系統中，能夠顯著優化電商平臺的一系列重要商業評價指標。
我們定義了四種信任關係型別：家人(Fa)、同學(Cl)、同事(Co)、朋友(Kn)。上圖展示了在已知使用者A與B之間的關係（以及使用者A與C之間的關係）的情況下，使用者B-C之間的關係型別的分佈。
圖中的實線表示已知的關係，虛線表示需要推斷的關係。從圖中可以觀察到，在大多數（開）閉三角形結構中，需要推斷的關係很大概率上跟其中一個已知的關係型別相同。
我們提出的因子圖模型能夠根據輸入資料自動學習圖中所列舉的（開）閉三角形結構在信任推斷問題中的重要程度。
上圖是我們建立的因子圖模型（Factor Graph Model）。每兩個使用者之間的關係都對應一個特徵向量 x 以及一個標籤y（分別對應下圖右側下方和上方兩個部分）。特徵因子函式f定義在一個關係的 x 和y上：
二元因子函式g和三元因子函式h分別定義在兩個相鄰和三個構成三角形的使用者關係上，分別反映了關係之間的二元關聯關係以及三元關聯關係：
其中是模型需要學的引數。
建立這樣一個因子圖模型之後，我們通過最大化似然函式得到優化目標：
其中Y^L表示所有已知標籤的集合，p(Y|G)定義為圖G中所有關係符合標籤集合Y的概率。我們將這個聯合概率建模成各個因子的乘積：
其中，Z表示全域性歸一化因子。我們使用梯度下降演算法來求解模型的引數，以求解為例，我們計算目標函式對該引數的偏導數：
上式右方的期望可以展開為：
在計算上式的期望時，我們需要計算邊緣概率p(yi, yj, yk)。我們使用迴圈置信傳播演算法（Loopy Belief Propagation）來近似該邊緣概率。通過梯度下降演算法，我們能得到因子圖模型的引數。最後根據模型的引數來推斷所有未知關係的標籤。我們把所提出的這種方法叫做eTrust。具體的演算法描述如下：
然而，在真實大規模圖資料上，迴圈置信傳播演算法求解效率極其低下，因此我們提出了一種新效果相當但效率提升1000多倍的近似演算法。我們用一個容易求解的概率來代替原本需要用迴圈置信傳播演算法求解的邊緣概率。
具體來說，在每一輪迭代時，將上一輪迭代推斷出的標籤資訊近似看做已知標籤，由此得到新的負對數的目標函式：
其中帶^的yj和yk表示上一輪推斷得到的標籤，全域性歸一化因子被區域性歸一化因子Zi所取代：
模型的引數仍然可以通過梯度下降法來得到，我們以引數為例給出其偏導數：
其中 
我們把提出的這種近似方法叫做eTrust-s。具體的演算法描述如下：
我們在阿里資料集以及另外3個公開的有關信任關係的資料集上驗證了我們提出的模型的效果以及效率。資料集的統計資訊如下：
我們的模型跟監督和半監督演算法的比較如下：
我們的模型跟無監督演算法的比較如下：
我們提出的eTrust-s相對於eTrust的效率比較如下：
eTrust-s模型在四個資料集上的因子分析以及收斂分析如下：
最後， 我們將eTrust-s模型在阿里巴巴真實使用者資料中所推斷出的信任關係應用到阿里巴巴線上推薦系統中，並對應用前與應用後的業務上進行了A/B測試。
應用了信任關係的推薦系統在淘寶商品搜尋場景中，在退貨率、差評率和中評率指標上相比於傳統的協同過濾推薦演算法分別降低了30.09%、45.45%和42.08%；在淘寶“有好貨”場景中，給銷售總額帶來了2.75%的提升。
