02 youtube官網網頁版優化設計與分析論文(多樣性算法在58部落的實踐和思考)

,XQUAD,PM2,Bayes，MMR，在多樣性層多種異構類型的實體上常用算法并不是合適，因為58部落物品類型多樣而且異構，很難用單一的向量生成方法把異構物品放在一個稠密空間度量，而且不同類型的實體興趣分布重疊度并不是很高，所以我們使用了基于自定義距離的MMR,DPP算法以及不是基于距離的EE算法。

3.1 多樣性架構圖

多樣性層架構圖

限于篇幅、業務結合的重要性、時效性等原因，下面重點介紹MMR和DPP這兩種算法在工程實踐中的應用。

3.2  MMR 的原理

MMR 的原理的全稱為MaximalMarginal Relevance，是一種以減少冗余、保證相關的貪心排序算法。在推薦場景體現在，給用戶推薦相關商品的同時，保證推薦結果的多樣性。公式：

S是已經選擇的文檔有序集合,一般是相關性排序結果;

R表示下一個候選文檔；

Di表示下一個候選文檔;

Dj表示S中的文檔;

sim函數：是相似度度量函數，例如相似度；

表示候選文檔與查詢文檔的相關性；

表示該文檔與已有文檔的相似性最大值；

 權重系數，調節推薦結果相關性與多樣性。

作為一種貪婪算法，同樣是每次計算出公式中最大值，放入有序結果集，同時從候選集中刪除選中的物品，然后更新參數，進而進行下一輪繼續選擇，直到結果集中數據量滿足需要或者沒有數據可選擇為止。

實現流程

MMR算法流程圖

實驗效果

MMR參數效果對照圖

 工程實現問題

距離計算的時候，我們的實現是當前文檔與已選文檔之間的平均距離，來避免使用最大距離而導致推薦結果中后續加入的文檔之間有高的相似性。

物品之間相似度函數的定義，可以根據論文里提到的用相似度。但是這樣就要求候選列表之間必須要有一個統一的物品向量，以保證該向量是anything-to-anything。因為推薦結果有多種類型，并且是異構的，這種情況下相似度并沒有很好的可解釋性。我們的做法是使用和業務結合的自定義距離，下文會詳細介紹自定義距離。

3.3 DPP的原理

全稱determinantal point process，是在一個離散的點集的冪集上定義的概率分布。是隨機采樣得到的一個子集，對于任意，有

公式中變量含義：

Y 行列式點過程隨機采樣得到的一個隨機子集;

是Y的任意子集;

表示中所有元素在采樣中被命中的概率;

 k是一個的實對稱方陣，也是被稱為的核矩陣，每個元素 可以認為是集合中第個元素之間的相似度，與采樣概率成反比。可以看做物品與用戶的相關性，和采樣概率成正比。

Ka 是K的主子式，階數是中元素個數。

行列式點過程，通過下圖可以形象的描述：

行列式點過程示意圖

表示物品i、j同時被采樣出來的概率。從公式可以看出，越是相似的物品，被同時采樣出來的概率就越小。

該算法思路是把重排序問題看成一個子集選擇問題，目標是從原始數據集合中選擇具有高質量但又多樣化的的子集，通過DPP來保持高質量和多樣性的平衡。DPP是一個性能較高的概率模型，通過行列式將復雜的概率計算簡單化。DPP還可以理解為一個抽樣的過程，兩個元素作為子集被抽取的概率與單一元素被抽取的概率以及這兩個元素的相似度有關。

DDP實現方案

 第一種是Google提出一種基于窗口的重排序方案，論文中提到的核矩陣構建方案是：

Dij表示物品i、j 的距離， 是自由變量。當a=1時，等價于標準RBF內核。當

隨著集合的增長，小集合的概率增大，而大集合的概率減小。由于a>1時，可能導致L非半正定，為了保證每次計算的核矩陣半正定，論文對核矩陣做了一個映射，計算L的特征分解并用0代替任何負的特征值。

同時也提出了基于深度格拉姆核矩陣的深度學習模型優化方法，減少網格搜索參數的復雜度。

第二種是賓夕法尼亞大學提供的方案，該方案是一個通用的DDP最大后驗推斷求解方案，但是每獲取一個物品，都要經過計算而重新構建核矩陣，延遲不太樂觀。

第三種是Huhu視頻提出最大后驗推斷解決方案，該論文提出了一種改進的貪心算法能夠快速的求解以解決傳統MAP時間復雜度很高的問題：

通過構造 

的次模函數把MAP求解問題轉化為次模函數最大化為題。并通過貪心算法來解決次模函數最大化帶來的NP-hard問題。

每次選擇商品添加到結果集中Yg中，Yg初始化為空集，直到滿足條件為止，商品需要滿足下面的等式：

由于計算行列式復雜度較高，論文對的進行Cholesky分解，初始化為空，并通過一些列轉化得到：

作者又提出了增量更新，通過推導（具體推導過程請參考原論文）得到最終增量更新公式：

我們實現了三種方案，方案二延遲較大，無法應用到線上。方案一我們實現的簡單模式，是直接計算行列式，延遲比方案三大。方案三沒有核矩陣就行修復，會出現排序結果小于預期數據量的情況。實際應用中，結合數據量的需求以及效率，我們最終選擇的是第三種hulu提出的實現方案。

DPP實現流程

DPP算法流程圖

實驗效果

DPP參數變化對應效果圖

為了保證幾個指標在同一張圖中相互對比，圖中把pvctr和avgpv進行一定程度的放大和縮小。從上圖可以看出，逐漸調整多樣性參數, pvctr在變大，在0.7左右的時候達到最高。uvctr和人均瀏覽數穩定提高，說明隨著多樣性的增加會吸引不點擊的人產生點擊行為，并且會使得人們瀏覽更多的內容，并且uvctr在0.7的時候達到最高點，在0.7時的時候效果最好。DDP每條曲線最后一個參數值都很低，是因為在0.999的時候，在構建核矩陣的時候a的值變得很大，在經過指數變化，導致很多核矩陣的值為最大值，矩陣不滿秩，數據只返回幾個，屬于非正常情況，各種指標都下降，這也是算法調試過程中需要避開的點。

工程實現問題

實現上，我們主要使用EJML這個高效的開源的Java矩陣運算庫實現的，這個庫是目前嘗試過程中效率比較高的庫。

工程實現上，主要參考論文中提到的使用

exp(αr_u )

代替Ru，通過對多樣性和相關性進行調節，

α=θ/((2(1-θ)) )

論文中提到的保證半正定性就行修正

S_ij=(1+⟨f_i,f_j ⟩)/2

在我們應用中影響并不是很大，主要是我們的相似度矩陣是自定義的。

DPP主要優化點在效率，我們采用huhu視頻的優化方案，通過增量求解的方式代替遍歷求行列式的方式，平均100個物品整個重排序過程延遲只有4ms。

核矩陣的構建，因為我們需要一個可解釋性比較強并且能和業務結合比較緊密的自定義距離，因此相似度矩陣、核矩陣也是自定義。

采用窗口的方式對整個列表分批排序。針對次模函數性質，小的數據集排斥性比大的數據集更大，采用窗口效果更好。

針對DPP調參，首先固定自定義距離參數，找到一個合適的，然后固定，循環調節距離參數，網格搜索的方式優化參數。

 由于核矩陣不滿秩，導致返回數據量可能會小于預期的數據量，在對業務影響不大的情況下，可以正常使用。如果對返回數據量有嚴格要求，需要考慮對核矩陣進行修正，可以參考類似google提出的核矩陣修正方式，同時會對延遲有一點影響，延遲大概增加一倍。

3.4 多樣性層算法效果對比圖

原始算法、MMR和DPP效果對比

多樣性層主要考慮穩定性以及時效性，我們主要流量在兩個隱式多樣性算法MMR和DDP，而我們原始算法是通過啟發式規則進行控制的。通過對比最優參數下的算法，發現DDP整體效果上好于MMR，并且相對于原始算法都有很大程度提升。下表表示兩個算法相比原始算法變化。

指標\算法MMR

DDP

pvctr+3.4%+5.8%

vvctr

+5.4%+7.9%

avgpv

+4.2%+6.0%

                                各算法業務指標變化圖  

自定義距離

為了可解釋性更強以及更緊密的融合業務，我們使用了自定義的距離，自定義距離好處如下：

 可解釋性比較強，自定義的距離偏向于人可理解的目的，使距離更可解釋;

和業務結合更緊密，自定義的距離使用業務相關的信息緊密結合業務;

通用性比較強，可以在不同異構實體間使用，其他距離無法做到這一點.

我們實踐過的自定義距離如下：

1.  杰卡德距離/漢明距離

這種自定義距離實現方式，采用漢明-杰卡德距離平鋪近似法

自定義距離-杰卡德/漢明距離

就是構造和業務結合的漢明向量,先求出漢明距離，然后通過杰卡德相似度做歸一化。

2. 自定義距離-樹模型距離

自定義樹模型的距離是通過樹狀分層衰減，自頂而下結合業務實現的

自定義距離-樹模型

樹的葉子節點，就是距離的散點值。

我們嘗試了以上三種自定義距離方式，從可解釋性、業務結合性以及線上實驗效果來看，樹模型是目前效果最適合的。

總結與展望

推薦系統多樣性的好壞有很多評估的方面，本文不單純用多樣性指標來衡量算法的好壞，同時還基于業務指標綜合考慮多樣性結果，把多樣性和業務關注的指標進行權衡，最終實現了通過多樣性算法提升業務指標的目的。在工程實現上，本文從召回、規則、重排序多個層面分別介紹了為達到多樣性的目的而做的算法嘗試，特別是最重要的重排序階段，我們基于MMR和DDP算法，在計算效率上進行了優化，并且針對業務數據的特點，對距離進行定制化改造，滿足了從多維度衡量物品相似度的業務需求。

目前多樣性的實踐就文獻中的效果來說，學習式的多樣性算法效果大于非學習式的，顯式的大于隱式的，然而多類別異構實體的關系并不是那么直觀，后續我們會結合業務特點進行嘗試。另外基于強化學習的多樣性算法也是多樣性研究的一個方向，目前我們已經再做相關嘗試。

參考文獻：

1.  C.-N. Ziegler, S.M. McNee, J.A. Konstan andG. Lausen. Improving re買粉絲mendation lists throu

很赞哦!（5）