多樣性算法在58部落的實踐與思考

指導閱讀

在明確了“推薦系統的個體多樣性優化”這壹主題後，本文從整體架構上清晰地闡述了召回層、規則層和多樣性層中的優化細節。在MMR和DPP算法中，既有原理也有實踐。最後通過圖表展示效果對比，根據自身業務特點進行有針對性的距離設計。

背景

在推薦系統中，除了相關性，多樣性也是衡量系統好壞的重要指標之壹。然而，多樣性和相關性之間往往存在壹些矛盾。從業務指標的角度，探討了如何權衡多樣性和相關性的思維方法，介紹了多樣性算法的實用方案，最終通過多樣性手段達到改善業務指標的目的。

1.多樣性算法的意義和難點

在推薦系統中，準確率壹直是衡量系統好壞的最重要指標，大部分工作都在研究如何提高準確率。然而，推薦結果的質量是由多個維度來衡量的。越來越多的研究表明，基於準確度的推薦並不能提高用戶的體驗和滿意度，反而容易促進信息繭的出現。因此，如何平衡和優化準確性和多樣性，從而提高業務的整體數據指標，成為了推薦系統的另壹個優化方向。

在實踐中，我們總結了多樣性算法的幾個難點:

1)模型的優化目標是模糊的。

眾所周知，各種用戶行為(點擊、轉化、停留、分享等。)可以作為優化精度的目標。我們可以清晰地收集用戶行為作為模型的目標標簽，從而設計和優化模型。因為多樣性本身就是壹個集合統計量，很難找到直接的用戶行為作為模型優化的目標。

2)業務指標和多樣性指標之間的沖突

業務關註指標(轉換率、停留時間等。)和多樣性指標不是簡單的正或負。如果單純為了提高多樣性指數而做多樣性，會導致最終結果與商業目標產生偏差，降低推薦質量。

綜上所述，在58部落推薦系統的多樣性實踐中，我們排除了單純用多樣性指標作為評估算法的方法。結合部落的業務特點，我們設定的目標是:以多樣性作為提升業務指標的手段，通過多個業務指標和多樣性指標綜合評估算法的效果，最終達到兩個指標共同提升的目的，從而提升用戶體驗。

58部落多樣性算法的實踐

在分集算法的研究中，分集通常分為兩種類型:

基於個人用戶的多樣性，旨在避免向單壹用戶推薦相似的商品，從而改善用戶體驗，增加用戶滿意度；

基於所有用戶的多樣性，旨在優化長尾商品的分發效果；

因為我們現階段的主要目標是個人用戶體驗，所以選擇基於個人用戶的多樣性作為實踐方向。

1.？推薦的系統架構圖

推薦系統的在線層次結構圖

為了確保推薦數據的多樣性，我們在三個地方進行了優化:

1)召回層:從數據源提供多樣化的候選集，通過提高粗糙候選池中主題、類別、作者的覆蓋率，保證數據源的多樣性；

2)規則層:在相關性損失很小的情況下，通過提高精細排序候選池中主題和類別的覆蓋率，保證進入精細排序池的數據的多樣性；

3)?多樣性層:對數據進行統壹和多樣化處理，保證數據輸出的多樣化。

數據決定了效果的上限，算法只是逼近這個上限。在多樣性層，盡可能只保證精細排序後的數據多樣性。由於結果受精行候選池的數據多樣性的影響，如果能在召回層的數據源中保持候選集的多樣性會更好。

2.數據來源多樣化

2.1召回層多樣化的實現

回憶層架構圖

在召回階段，我們采用了多渠道召回。為了保證數據的多樣性，通過增加壹些不同的召回策略來豐富數據源，比如:

通過多樣性算法，獲取用戶個性化、多樣化的話題、類別和作者進行召回，保證召回兼顧多樣性和相關性；

通過壹些長尾、時間、驚喜回憶，增加數據的新穎性和多樣性；

通過壹些基於關系和屬性的協同召回分支，提高了數據的多樣性。

通過增加多樣性和新穎性召回，粗候選池中數據的覆蓋率提高了約120%，基於類別的覆蓋率提高了約100%。

2.2實現規則層的多樣化

規則層架構圖

我們推薦的數據是各種異構的實體，所以在進入細行(規則層)之前，會對類型進行分桶處理。每種類型都要經歷壹個從粗排到細排的數據攔截階段，主要攔截指標壹般是粗排的相關分值。為了防止截斷破壞召回層對數據源所做的多樣性優化，我們先將這類粗排列的結果按類別分成桶，然後控制多樣性。最後，調整各種類型的比例，補充數據，做壹些必要的篩選。在相關性不大的情況下，提高細行數據的多樣性。

由於規則層多樣性算法是按類型分桶的，所以不受各種異構類型實體混合排列的影響，適用於各種多樣性算法。

在規則層加入多樣性算法的幹預後，精細排序候選池中數據的覆蓋率基於主題提高了80%左右，基於類別提高了70%左右。

常規圖層添加多樣性後的online ctr和uvctr的變換效果如下圖所示:

規則層算法的效果比較

從上圖可以看出，在差異方面，各算法都不是很大，性能略勝壹籌。總的來說，算法執行得稍微好壹點。規則層主要是用多樣性算法代替以前的啟發式規則，從而自動化數據源的多樣性。

3.基於重排序方法的多樣化圖層

對於算法參數調整，我們主要參考三個業務指標:

Pvctr表示pv點擊率；Uvctr代表uv點擊率；Avgpv代表人均觀展次數。

對於應用多樣性算法的場景，在規則層的單壹類型中使用了常見的多樣性算法，如binomal、EE、DPP、XQUAD、PM2、Bayes和MMR，但是常見的算法並不適合多樣性層中的各種異構類型的實體，因為58個部落具有多樣性和異構性，很難用單壹的向量生成方法來度量稠密空間中的異構項，並且不同類型的實體的興趣分布的重疊程度不是很高。

3.1分集架構圖

多樣性層架構圖

限於篇幅、業務組合的重要性、時效性等原因，下面重點介紹MMR和DPP在工程實踐中的應用。

3.2?MMR？的原則

MMR原理的全稱是MaximalMarginal Relevance，是壹種減少冗余、保證相關性的貪婪排序算法。在推薦場景下，我們可以在保證推薦結果多樣性的同時，向用戶推薦相關產品。公式:

s是所選文檔的有序集合，壹般是相關排序的結果；

r代表下壹個候選文檔；

Di代表下壹個候選文檔；

Dj代表s中的文檔；

Sim函數:是壹個相似性度量函數，比如相似度；

表示候選文檔和查詢文檔之間的相關性；

表示文檔和現有文檔之間的最大相似性；

？權重系數，調整推薦結果的相關性和多樣性。

作為壹種貪婪算法，它也是每次計算公式中的最大值，放入有序的結果集中，同時從候選集中刪除選中的項，然後更新參數，然後在下壹輪繼續選擇，直到結果集中的數據滿足需要或者沒有數據可供選擇。

實現進程

Mmmr算法流程圖

實驗效果

MMR參數效果對比圖

為了統壹算法流程，我們對原論文中公式中的和進行了換位。為了保證在同壹張圖中比較幾個指標，圖中的和有壹定程度的放大和縮小。從圖中可以看出，多樣性參數是逐漸調整的，逐漸降低，達到當時的最高點，因為越小，結果越趨於相關。並且人均觀看次數穩步上升，說明隨著多樣性的增加，會吸引壹部分人點擊，他們會瀏覽更多的內容，在家時效果最好，在家時達到最高點。

？工程實現問題

在計算距離時，我們實現了當前文檔與所選文檔之間的平均距離，避免使用最大距離造成推薦結果中後續文檔之間的高相似度。

文章間相似度函數的定義可以基於文中提到的相似度。但這要求候選列表之間必須有壹個統壹的項目向量，以確保該向量是任意對任意的。因為存在許多類型的推薦結果，並且它們是異構的，所以在這種情況下，相似性不是很好解釋的。我們的做法是用壹個自定義的距離結合業務，下面會詳細介紹。

3.3 DPP的原則

行列式點過程的全稱是定義在離散點集的冪集上的概率分布。是隨機抽樣的子集，對於任何壹個，都有

公式中變量的含義:

y？行列式點過程隨機抽樣得到的隨機子集；

是y的任意子集；

表示命中樣本中所有元素的概率；

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

Ka？是k的主主公式，階是其中元素的個數。

下圖可以形象地描述決定點過程:

決定點過程示意圖

表示項目I和J同時被抽樣的概率。從公式中可以看出，相似項越多，同時被抽樣的概率越小。

該算法的思想是將重排序問題視為子集選擇問題，目標是從原始數據集中選擇高質量但多樣化的子集，通過DPP保持高質量和多樣性之間的平衡。DPP是壹種高性能的概率模型，通過行列式簡化了復雜的概率計算。DPP也可以理解為壹個采樣過程，兩個元素被抽取為子集的概率與單個元素被抽取的概率以及兩個元素之間的相似度有關。

DDP實施方案

？第壹個是Google提出的基於窗口的重新排序方案。文中提到的核矩陣構造方案是:

Dij表示項目I和j之間的距離，它是自由變量。當a=1時，相當於標準的RBF核。當...的時候

矩陣的非對角線被縮小，這基本上對應於使所有項目多樣化。當a & gt1，矩陣的對角線按比例放大，起到了讓所有項目更相似的反效果。

隨著集合的增長，小集合的概率增大，大集合的概率減小。由於壹個& gt在1，L可能是非半正定的。為了保證核矩陣每次都是半正定的，本文對核矩陣進行映射，計算L的特征分解，用0代替任意負特征值。

同時提出了壹種基於深度Gram核矩陣的深度學習模型優化方法，降低網格搜索參數的復雜度。

第二種是賓夕法尼亞大學提供的方案，是DDP最大後驗推斷的壹般解決方案，但是每得到壹項都要通過計算來重構核矩陣，延遲不容樂觀。

三是部落虎視頻提出的最大後驗推斷解決方案。針對傳統地圖時間復雜度高的問題，提出了壹種改進的快速求解的貪婪算法:

靠施工？

映射的子模函數轉化為子模函數最大化問題。並采用貪婪算法解決子模函數最大化帶來的NP難問題。

每次選擇壹個乘積並添加到結果集Yg，Yg被初始化為壹個空集，直到滿足條件，該乘積需要滿足以下等式:

由於計算行列式的復雜度很高，本文將其分解為Cholesky，初始化為空，通過壹些列變換得到:

作者還提出了增量更新，並通過推導得到最終的增量更新公式(具體推導過程參考原論文):

我們實現了三種方案，第二種方案延遲較大，無法應用於在線。我們在第壹種方案中實現的簡單模式是直接計算行列式，延時比第三種方案大。方案3可以不用核矩陣修復，排序結果會小於預期的數據量。在實際應用中，結合數據量和效率的需求，我們最終選擇了hulu提出的第三種實現方案。

DPP實施流程

DPP算法流程圖

實驗效果

DPP參數變化對應的效果圖

為了保證幾個指標在同壹張圖中相互比較，pvctr和avgpv都有壹定程度的放大縮小。從上圖可以看出，逐漸調整分集參數，pvctr越來越大，在0.7左右時達到最高。Uvtr和人均觀看次數穩步上升，說明隨著多樣性的增加，不點擊的人會被吸引去點擊，人們會瀏覽更多的內容。而且Uvtr在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的主要優化點是效率。我們采用虎虎視頻的優化方案，不遍歷行列式，整個100項的重排序過程平均延遲只有4 ms。

核心矩陣的構建，因為我們需要壹個更具可解釋性的、能與業務緊密結合的自定義距離，所以相似度矩陣和核心矩陣也是自定義的。

按窗口分批排序整個列表。根據子模函數的性質，小數據集比大數據集更具排他性，窗口效果更好。

針對DPP參數調整，首先固定用戶自定義的距離參數尋找合適的，然後循環固定和調整距離參數，通過網格搜索優化參數。

？由於核矩陣對秩不滿意，返回的數據量可能小於預期的數據量，可以正常使用，對業務沒有太大影響。如果對返回的數據量有嚴格的要求，我們需要考慮修改核矩陣。可以參考google提出的核矩陣修改方法，同時對延遲會有壹點影響，延遲大概會翻倍。

3.4差異層算法效果對比圖

原始算法、MMR和DPP的比較

多樣性層主要考慮穩定性和時效性。我們的主要流量在兩個隱式分集算法中，MMR和DDP，而我們的原始算法由啟發式規則控制。通過對最優參數下的算法進行比較，發現DDP的整體效果優於MMR，與原算法相比有了很大的提高。下表顯示了兩種算法與原始算法相比變化。

指示器\算法寄存器

數字數據處理器

pvctr+3.4%+5.8%

vvctr

+5.4%+7.9%

avgpv

+4.2%+6.0%

各算法業務指標變化圖？

自定義距離

為了更好地解釋和更緊密地整合業務，我們使用用戶定義的距離。用戶定義距離的好處如下:

？可解釋性強，自定義距離偏向於人能理解的目的，使距離更具可解釋性；

並且業務結合更加緊密，自定義距離利用業務相關信息緊密結合業務；

它是通用的，可以在不同的異構實體之間使用，這是在其他距離上無法做到的。

我們練習的自定義距離如下:

1.？賈卡德距離/漢明距離

這個自定義距離是通過Hamming-Jakad距離平鋪近似法實現的。

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

就是結合服務構造漢明向量，先計算漢明距離，再通過雅可比相似度歸壹化。

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

用戶自定義樹模型的距離通過樹狀分層衰減和自頂向下的業務組合實現。

自定義距離樹模型

樹的葉節點是距離的分散值。

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

總結與展望

評價推薦系統的多樣性有很多方面。本文不僅使用多樣性指數來衡量算法的好壞，而且基於業務指標綜合考慮多樣性結果，對多樣性和業務關註指標進行權衡，最終通過多樣性算法實現改善業務指標的目的。在工程實現方面，本文介紹了該算法試圖從召回、規則和重排序等方面實現多樣性，特別是在最重要的重排序階段。基於MMR和DDP算法，優化計算效率，根據業務數據特點定制距離，滿足從多維度度量項目相似度的業務需求。

目前，就文獻中的效果而言，學習多樣性算法比非學習算法更有效，且顯性比隱性更有效。但是多品類異構實體之間的關系就沒有那麽直觀了，以後我們會結合業務特點進行嘗試。另外，基於強化學習的多樣性算法也是多樣性研究的壹個方向，目前我們又進行了嘗試。

參考資料:

1.？C.-N .齊格勒，S.M .麥克尼，J.A .康斯坦和g .羅森。通過主題多樣化改進推薦列表。WWW2005

2.？j .卡波內爾和j .戈爾茨坦。使用基於多樣性的重排序方法對文檔進行重新排序並生成摘要。SIGIR 1998

3.？詹妮弗.吉倫沃特。亞歷克斯·庫勒薩？本·塔斯卡。確定點過程的近似最佳映射推斷。？奶頭？2012

4.？馬克·威廉，阿吉特·庫瑪爾·拉曼納森，亞歷山大·博諾莫，薩加爾·賈恩，艾德·h·齊，詹妮弗·吉倫沃特。YouTube上關於決定性點過程的實用多樣性推薦。CIKM'18 2018

5.？陳拉明，，周漢寧。提高推薦多樣性的決定性點過程的快速貪婪映射推理。NeurIPS 2018

6.？CSDN的博客作者Caoys。行列式頂點過程介紹。csdn，2019。

關於作者:

劉發帥，58趕集集團，高級算法工程師。

周建斌，58趕集集團，算法架構師，技術委員會委員。