快手風控算法（高效整數規劃求解）

2023-10-26 06:53:21 1

機器之心專欄

作者：快手社區科學部

在本文中，快手的研究者們提出了一種新的 HTE 預估方法——多元因果森林模型，並且結合高效的整數規劃求解算法，效果顯著優於業界常用的幾種樹模型方法。
在智能營銷場景下，比如美團的滿減優惠券，淘寶的購物紅包等，需要形成系統化的營銷決策。基於此類場景，快手為了實施更細粒度的營銷決策，提出了一種新的多元因果森林模型。基於快手億級別的用戶量，快手社區科學部設計了資源分配並行算法，高效產出智能營銷決策。為了解決多元因果模型的評估問題，該研究利用隨機匹配的思想，提供了一個供業界參考的方法。最後，通過線下仿真實驗和線上真實 A/B 實驗，驗證了 LBCF 算法的有效性，該技術已經申請中國發明專利，並在快手智能營銷業務中獲得廣泛應用。
異質性因果效應 (HTE) 是因果推斷理論需要解決的核心問題，其概念最初來源於醫療領域。HTE 是指對於同一種幹預手段，對不同受眾的影響因人而異，在計算廣告、個性化治療、個性化教育以及公共政策等領域都有廣泛的應用。為理解其概念，舉個智能營銷領域的例子，對於同一補貼力度的營銷手段，某些受眾會立即轉化，而某些受眾可能根本不會轉化，如何準確區分出這些受眾便是 HTE 需要解決的問題。近年來，學術界不斷湧現新的 HTE 方法，其中史丹福大學經濟學教授 Susan Athey 等人提出的因果森林模型【1】因其良好的可解釋性和出色的效果在業界獲得逐步認可。
論文連結：https://arxiv.org/abs/2201.12585論文代碼：https://github.com/www2022paper/WWW-2022-PAPER-SUPPLEMENTARY-MATERIALS
大規模智能營銷算法
多元因果森林模型
智能營銷要研究的核心問題是，用戶對不同補貼額度的轉化效果差異有多大？這些不同的補貼額度可以被看作是因果推斷中的 treatments，所以場景驅使研究者去研究用戶在不同 treatments 下的轉化效果，即需要多元因果模型。以樹為基礎的模型具有良好的解釋性並且在機器學習中展現了很好的效果，在本文中，該研究主要考慮以樹模型為基礎的 HTE 預估方法。該方法可以應用於任何需要預估 HTE 的領域，本文僅以智能營銷場景為例進行闡釋。
本文提出的多元因果森林模型，模型結構如圖 2(示意的例子)，該模型結構有兩個優點：第一，單一一個模型能夠同時處理任意種幹預手段，否則，幾種幹預手段就需要維護相應數量的二元因果森林模型；第二，HTE 的定義要求各幹預手段對應一致的特徵子空間，該模型結構保證了這一點，這對準確估計 HTE 至關重要。
圖 2 多元因果森林模型 (註：圖 2 中的 Age，Inc. 等數據僅為了示意說明)
為此，該研究重新設計了因果森林的分裂準則，在每一次對樹節點進行分裂時，不但強調不同節點間的異質性，即節點間分裂(Inter Split)，同時也強調節點內不同幹預手段的異質性，即節點內分裂(Intra Split)。從計算複雜度來說，在尋找一個樹節點的特徵分裂點時，Inter Split 可以快速一次性預先計算出分裂所需數據，而 Intra Split 依賴於樹節點間分裂的結果，因此 Intra Split 每次都需要重新計算分裂數據，極其低效。為了平衡算法的效率和效果，該研究採用了兩步走的分裂算法：
第一步通過 Inter Split 選擇 top N 個備選特徵分裂點；第二步通過 Intra Split 從 N 個備選中選擇一個最終的特徵分裂點。
資源分配並行算法
解決了用戶彈性的預估問題之後，在智能營銷領域輸出營銷決策時，我們經常需要去回答，在有限的資源約束下如何去實現最優分配。為此，該研究把智能營銷中的資源分配問題建模成了有約束的整數規劃數學模型，如圖 3。但是，快手億級別的用戶量導致決策變量數目巨大，很多目前開源的求解器不能滿足性能的需求，會存在內存溢出等問題。
圖 3 整數規劃數學模型
為此，該研究設計了可並行的 Dual Gradient Bisection(DGB)算法，如圖 4。該算法在不損失解質量的情況下，實現了億級用戶量的分鐘級求解。限於篇幅，這裡簡單描述下求解思路，詳細的可以參閱論文和附錄 code。
第一步，利用線性鬆弛技術，把圖 3 的整數規劃數學模型簡化成易於求解的線性規劃問題，可以證明鬆弛後的線性規劃問題的解集至多只在預算臨界處有一個非整數解。第二步，通過拉格朗日乘子把有約束問題轉化為無約束問題。第三步，由於該問題滿足強對偶條件，研究者對該問題進行對偶轉化，由此得到了一個關於拉格朗日乘子的單變量分段函數，並且可以證明該分段函數為閉區間上的凸函數。第四步，通過圖 4 的 DGB 算法，研究者可以在並行系統上高效求出。第五步，代回對偶問題，便可依次求解出所有決策變量的值。
圖 4 可並行的 DGB 算法
多元因果模型評估
因為無法觀測到因果模型的反事實結果(Counterfactual Outcome)，因此，如何評估因果模型的線下效果成了業界亟待解決的問題，常用的評估方法有 AUUC/Qini Curve 等，但這些更適合評估二元因果模型；對於多元因果模型的預估結果，也只能是先把多元結果拆解成許多二元結果，之後再進行分別評估。
本文利用隨機控制實驗 (RCT) 數據，基於 Treatment Matching 的思想，提供了整體收益對比的方法。核心方法是：在 RCT 數據中找出 Policy Treatment 和 RCT Treatment 匹配的那些樣本，需要指出的是，對於這些匹配樣本，我們是可以觀測到其真實結果的。其次，可以證明這些匹配樣本的均值是其各列期望的好的估計。最後，利用各列的期望值，我們可以計算出多元因果模型的整體收益，收益越高，模型越好。
效果展示
為了公平的對比算法效果，首先，該研究利用 Ye Tu 等人在 WWW 2021 公開的仿真數據集【2】，與業界主流的以樹為基礎的因果模型進行了線下對比，如圖 5，橫軸是數據集噪聲的強弱，縱軸是研究者關注的核心指標的收益，可以看出，LBCF 效果最好，CT.ST 和 CF.DT 次之。
圖 5 線下仿真實驗
進一步，該研究在快手的真實智能營銷場景下部署了 LBCF 算法，進行了兩周的 A/B 實驗，如圖 6，結果也證明了該算法的有效性，與 CT.ST 和 CF.DT 算法相比，收益分別提高了 0.92 和 2.48 個百分點。
圖 6 線上 A/B 實驗
總結
在本文中，快手的研究者們提出了一種新的 HTE 預估方法——多元因果森林模型，並且結合高效的整數規劃求解算法，效果顯著優於業界常用的幾種樹模型方法。同時，對於業界棘手的因果效應離線評估問題，研究者們也創新地給出了一個可行的解決方案。研究者們希望本文的工作能夠引起機器學習愛好者們的關注，以更廣泛地應用因果推斷技術在各自的實際業務中。
參考文獻
[1] Susan Athey, Julie Tibshirani and Stefan Wager. Generalized Random Forests. Annals of Statistics, 2019.
[2] Ye Tu, Kinjal Basu, Cyrus DiCiccio, Romil Bansal, Preetam Nandy, Padmini Jaikumar, and Shaunak Chatterjee. 2021. Personalized Treatment Selection using Causal Heterogeneity. In Proceedings of the Web Conference 2021. 1574–1585.
,