導讀
本文在明確“推薦系統個體多樣性優化”主題後，由整體架構出發，清楚闡述了在召回層、規則層、多樣性層的優化細節。在MMR 和 DPP算法部分既有原理也有實踐，最後用圖表方式展示出了效果對比，並且結合自身業務特點做了針對性的距離設計。
背景
在推薦系統中，衡量系統好壞的指標，除了相關性之外，多樣性也是重要的指標之一。但多樣性和相關性之間往往存在一些矛盾的地方，本文從業務指標的角度，探討了多樣性和相關性之間如何權衡的思想方法，介紹了多樣性算法的落地實踐方案，最終達到了通過多樣性手段提升業務指標的目的。
1. 多樣性算法的意義和難點
推薦系統中，準確度一直是衡量系統好壞最重要的指標，大多數的工作都是在研究如何提高準確度。然而，推薦結果的質量是通過多個維度來衡量的，越來越多研究表明，僅依賴準確度的推薦已經不能對用戶的體驗和滿意度有所提升，反而容易促進信息繭房的產生。於是，如何在準確性和多樣性之間進行權衡和協同優化，從而提高業務的整體數據指標成為了現在推薦系統的又一個優化方向。
在實踐中，我們總結了多樣性算法落地的幾個難點：
1）模型的優化目標模糊
眾所周知，各種用戶行為（點擊、轉化、停留、分享等等）都可以作為優化準確度的目標，我們可以明確的收集用戶的行為作為模型的目標標籤，從而設計模型並優化。因為多樣性本身是一個集合統計量，很難找到直接的用戶行為來作為模型優化的目標。
2）業務指標和多樣性指標的衝突
業務關注的指標（轉化率、停留時長等）和多樣性指標並不是簡單的正向或者負向的關係。如果單純為了提高多樣性指標而做多樣性，反而會導致最終結果與業務目標偏離，使推薦的質量下降。
綜上所述，我們在58部落推薦系統的多樣性實踐中，排除了單純使用多樣性指標作為評估算法好壞的方法。結合部落的業務特點，我們定下了這樣的目標：把多樣性作為一個提高業務指標的手段，通過多個業務指標和多樣性指標來綜合評估算法的效果，最終達到兩種指標共同提升，進而提高用戶體驗的目的。
58部落的多樣性算法實踐
在多樣性算法的研究中，通常把多樣性分成兩種：
基於個體用戶的多樣性，旨在避免給單一用戶推薦相似的物品，從而提高用戶體驗和增加用戶滿意度；
基於全部用戶的多樣性，旨在優化長尾的物品分發效果；
因為我們現階段的主要目標是針對個體用戶體驗，所以選擇了基於個體用戶的多樣性作為實踐方向。
1. 推薦系統架構圖
推薦系統在線分層架構圖
為了保證推薦數據的多元化，我們在三個地方進行了優化：
1）召回層：從數據源提供多樣性的候選集合，通過提高粗排候選池中主題、類別和作者的覆蓋度來保證數據源的多樣化；
2）規則層：在相關性損失不大的情況下，通過提高精排候選池中主題和類別的覆蓋度來保證進入精排數據的多樣化；
3） 多樣性層：對數據統一做多樣化處理，保證數據輸出多樣化。
數據決定了效果的上限，而算法只是逼近這個上限。在多樣性層，只是儘可能保證了精排後的數據多樣性，由於結果受精排候選池數據多樣性的影響，所以如果能在召回層數據源保持候選集合的多樣性，效果會更好。
2. 數據源多樣化
2.1 召回層多樣化的實現
召回層架構圖
在召回階段，我們採用的是多路召回。為了保證數據多樣性，通過增加若干多樣性的召回策略來豐富數據源，例如：
通過多樣性算法，獲取用戶個性化和多樣化的主題、類別、作者進行召回，以保證召回兼顧多樣性和相關性；
通過一些長尾、時間、驚喜的召回分路，來增加數據新穎性和多樣性；
通過一些基於關係、屬性的協同召回分路，提高數據多樣性。
通過增加多樣性和新穎性召回，粗排候選池中的數據基於主題的覆蓋度提高了120%左右，基於類別覆蓋度提高了100%左右。
2.2 規則層多樣化的實現
規則層架構圖
我們推薦的數據是多種異構類型的實體，因此進入精排前（規則層）會對類型進行分桶處理。每種類型從粗排到精排都要經過一個數據截取階段，主要截取指標一般是粗排的相關性分數。為了防止截斷操作破壞召回層對數據源所做的多樣性優化，我們通過對該類型的粗排結果先按照類別進行分桶，然後在做多樣性控制。最後對各種類型進行比例調整、數據補充以及一些必要的過濾。在相關性影響不大的情況下提高精排數據的多樣性。
因為規則層多樣性算法是按照類型分桶，因此不受多種異構類型的實體混排的影響，適合於各種多樣性算法。
規則層添加多樣性算法干預之後，精排候選池中的數據基於主題的覆蓋度提高了80%左右，基於類別覆蓋度提高了70%左右。
規則層加入多樣性後的線上ctr和uvctr轉化效果，如下圖：
規則層算法效果對比
從上圖可以看出，就而言，各個算法差異度並不是很大，和表現略好。就而言，算法表現稍微好一點。規則層主要是通過多樣性算法替換之前的啟發式規則，使據源多樣性自動化。
3. 基於重排序方法的多樣層
算法調參，我們主要參考三個業務指標：
pvctr表示pv點擊率；uvctr表示uv點擊率；avgpv表示人均展示數。
對於多樣性算法應用的場景，在規則層單類型上使用了常用的多樣性算法，binomal，EE,DPP,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時，按比例放大矩陣的對角線，其相反的效果是使所有項更相似。
隨著集合的增長，小集合的概率增大，而大集合的概率減小。由於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矩陣運算庫實現的，這個庫是目前嘗試過程中效率比較高的庫。
工程實現上，主要參考論文中提到的使用
<code>exp(αr_u )/<code>
代替Ru，通過對多樣性和相關性進行調節，
<code>α=θ/((2(1-θ)) )/<code>
論文中提到的保證半正定性就行修正
<code>S_ij=(1+⟨f_i,f_j ⟩)/2/<code>
在我們應用中影響並不是很大，主要是我們的相似度矩陣是自定義的。
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 recommendation lists through topic diversification. WWW2005
2. J. Carbonell and J. Goldstein. The use ofMMR, diversity-based reranking for reordering documents and producingsummaries. SIGIR 1998
3. Jennifer Gillenwater Alex Kulesza Ben Taskar. Near-Optimal MAP Inference forDeterminantal Point Processes. NIPS 2012
4. Mark Wilhelm, Ajith Ramanathan, AlexanderBonomo, Sagar Jain, Ed H. Chi, Jennifer Gillenwater. Practical DiversifiedRecommendations on YouTube withDeterminantal Point Processes. CIKM’18 2018
5. Laming Chen, Guoxin Zhang, Hanning Zhou. FastGreedy MAP Inference for Determinantal PointProcess to Improve RecommendationDiversity. NeurIPS 2018
6. Caoys,CSDN博主.Determinantalpoint process 入門.csdn,2019
作者簡介：
劉發帥，58趕集集團，資深算法工程師
周建斌，58趕集集團，算法架構師，技術委員會委員
