螞蟻金服核心技術：百億特徵實時推薦算法揭秘
阿里妹導讀：本文來自螞蟻金服人工智能部認知計算組的基礎算法團隊，文章提出一整套創新算法與架構，通過對TensorFlow底層的彈性改造，解決了在線學習的彈性特徵伸縮和穩定性問題，並以GroupLasso和特徵在線頻次過濾等自研算法優化了模型稀疏性，在支付寶核心推薦業務獲得了uvctr的顯著提升，並較大地提升了鏈路效率。
0.綜述
在線學習(Online learning)由於能捕捉用戶的動態行為，實現模型快速自適應，進而成為提升推薦系統性能的重要工具。然而它對鏈路和模型的穩定性，訓練系統的性能都提出了很高的要求。但在基於原生TensorFlow，設計Online推薦算法時，我們發現三個核心問題：
- 一些資訊推薦場景，需要大量長尾詞彙作為特徵，需使用featuremap對低頻特徵頻次截斷並連續性編碼，但耗時且方法aggressive。
- 使用流式數據後，無法預知特徵規模，而是隨訓練逐漸增長。因此需預留特徵空間訓練幾天後重啟，否則會越界。
- 模型稀疏性不佳，體積達到數十GB，導致上傳和線上加載耗時長且不穩定。
更重要的是，在線學習如火如荼，當流式特徵和數據都被打通後，能按需增刪特徵，實現參數彈性伸縮的新一代訓練平臺成為大勢所趨。為了解決這些問題，從2017年底至今，螞蟻金服人工智能部的同學，充分考慮螞蟻的業務場景和鏈路，對TensorFlow進行了彈性改造， 解決了以上三大痛點，簡化並加速離線和在線學習任務。其核心能力如下：
- 彈性特徵伸縮體系，支持百億參數訓練。
- group_lasso優化器和頻次過濾，提高模型稀疏性，明顯提升線上效果。
- 模型體積壓縮90%，完善的特徵管理和模型穩定性監控。
在與業務線團隊的共同努力下，目前已在支付寶首頁的多個推薦場景全流量上線。其中某推薦位的個性化online learning桶最近一週相比線上多模型融合最優桶提升4.23% ， 相比隨機對照提升達34.67% 。 某個性化資訊推薦業務最近一週，相比DNN基準uv-ctr提升+0.77%，pv-ctr提升+4.78%，模型體積壓縮90%，鏈路效率提升50%。
1. 彈性改造及優勢
背景：在原生TensorFlow中，我們通過Variable來聲明變量，若變量超過了單機承載的能力，可使用partitioned_variables來將參數分配到不同機器上。 但必須指定shape，聲明後即不可改變，通過數組索引查找。
由於推薦系統中大量使用稀疏特徵，實踐中一般採取embedding_lookup_sparse一類的方法在一個巨大的Dense Variable中查找向量並求和，來代替矩陣乘法。開源Tensorflow限定了Variable使用前必須聲明維度大小，這帶來了兩個問題：
1）需要預先計算特徵到維度範圍內的int值的映射表，這一步操作通常在ODPS上完成。因為需要掃描所有出現的特徵並編號，計算非常緩慢；
2）在online learning場景下，為了容納新出現的特徵，需要預留一部分維度空間，並在線上不斷修改映射表，超過預留空間則需要重新啟動在線任務。
為了突破固定維度限制，實現特徵的動態增加和刪除，最樸素的優化想法是在TensorFlow底層實現模擬字典行為的Variable，並在此基礎上重新實現Tensorflow上層API。由此我們進行了優化，在server新增了基於HashMap的HashVariable，其內存結構如下：
在聲明該變量時，只需增加一句，其他訓練代碼皆不需改動：
每個特徵都通過hash函數映射到一個2的64次方大小的空間內。當需要計算該特徵時，PS會按需惰性創建並返回之。但其上層行為與原生TF一致。由於去掉了featuremap轉ID的過程，我們內部形象地將其稱為“去ID化”。在此之上我們實現了Group Lasso FTRL，頻次過濾和模型壓縮等一系列算法。
備註：彈性特徵帶來一個顯著的優勢：只要用足夠強的L1稀疏性約束，在單機上就能調試任意大規模的特徵訓練，帶來很多方便。我們的hashmap實現是KV化的，key是特徵，value是vector的首地址。
離線訓練優化
經過這樣的改造後，在離線批量學習上，帶來了以下變化：
在線訓練優化
online learning上，能帶來如下變化：
除了性能有明顯的提升之外，其最大的優勢是不需提前申請空間，訓練可以無縫穩定運行。
2. 特徵動態增刪技術
彈性架構，主要目的就是特徵優選，讓模型自適應地選擇最優特徵，進而實現稀疏化，降低過擬合。本節介紹特徵優選的兩個核心技術：
- 使用流式頻次過濾， 對特徵進入進行判定。
- 使用Group Lasso優化器，對特徵進行篩選和刪除。
2.1 Group Lasso 優化器
稀疏化是算法追求的重要模型特性，從簡單的L1正則化和Truncated Gradient[9]， 再到討論累積梯度平均值的RDA(Regularized Dual Averaging)[10]， 再到目前常見的 FTRL[2] 。 然而它們都是針對廣義線性模型優化問題提出的稀疏性優化算法，沒有針對sparse DNN中的特徵embedding層做特殊處理。把embedding參數向量當做普通參數進行稀疏化，並不能達到在線性模型中能達到的特徵選擇效果，進而無法有效地進行模型壓縮。
例如：當包含新特徵的樣本進入時，一個特徵對應的一組參數（如embedding size為7，則參數數量為7）被激活，FTRL判定特徵中的部分參數無效時，也不能安全地將該特徵刪除。如圖：
因此，在L1和L2正則的基礎上，人們引入L21正則(group lasso)和L2正則(exclusive sparsity)，分別表示如下：
L21早在2011年已經引入，它最初目的是解決一組高度關聯特徵（如男\女）應同時被保留或刪除的問題，我們創新地擴展到embedding的表示上，以解決類似的問題。
在L21中，由於內層L2正則將一個特徵的所有參數施加相同的約束，能將整組參數清除或保留，由此決定embedding層中的某些特徵對應的embedding向量是否完全刪除，提升模型泛化性。因此稱為group lasso。
而L12則正好相反，它迫使每組參數中的非0參數數量一致但值又儘可能不同，但使輸出神經元互相競爭輸入神經元，進而使特徵對目標更具區分性。
對於DNN分類網絡，底層表示要求有足夠的泛化性和特徵抽象能力，上層接近softmax層，需要更好的區分性。因此我們通常在最底層的embedding層使用group lasso。即如下的優化目標：
直接將L21正則項懲罰加入loss，模型最終也能收斂，但並不能保證稀疏性。因此Group lasso優化器參考了FTRL，將梯度迭代分成兩個半步，前半步按梯度下降，後半步微調實現稀疏性。通過調節L1正則項（即公式中的λ），能有效地控制模型稀疏性。
Group lasso是彈性計算改造後，模型性能提升和壓縮的關鍵。值得指出：
- 在我們實現的優化器中，Variable，以及accum和linear兩個slot也是KV存儲。
- L12和L21正則相結合的方法也已經有論文討論[8]，但我們還未在業務上嘗試出效果。
- 由於篇幅限制，本節不打算詳細介紹Group lasso的原理和推導
2.2 流式頻次過濾
討論完特徵動態刪除的方法後，我們再分析特徵的准入策略。
2.2.1 頻次過濾的必要性
在Google討論FTRL的文章1中提到， 在高維數據中大部分特徵都是非常稀疏的，在億級別的樣本中只出現幾次。那麼一個有趣的問題是，FTRL或Group FTRL優化器能否能刪除(lasso)極低頻特徵？
在RDA的優化公式中，滿足以下條件的特徵會被置0：
若在t步之前，該特徵只出現過幾次，未出現的step的梯度為0，隨著步數增大，滿足上述條件變得越來越容易。由此RDA是可以直觀處理極稀疏特徵的。 但對於FTRL，要滿足：
其中，
不僅和歷史梯度有關，還與歷史學習率和權重w有關。 因此FTRL雖然也能處理極稀疏特徵，但並沒有RDA那麼aggressive（此處還待詳細地分析其下界，Group FTRL與此類似）。
由於FTRL在設計和推導時並未明確考慮極低頻特徵，雖然通過增大λ，確實能去除大量極低頻特徵，但由於約束太強，導致部分有效特徵也被lasso，在離線實驗中被證明嚴重影響性能。其次，對這些巨量極低頻特徵，保存歷史信息的工程代價是很高昂的（增加幾倍的參數空間和存儲需求），如下圖：
因此我們提出，能否在實時數據流上模擬離線頻次過濾，為特徵提供准入門檻，在不降低模型性能的基礎上，儘量去除極低頻特徵，進一步實現稀疏化？
2.2.2 頻次過濾的幾種實現
注意： 由於默認的embedding_lookup_sparse對特徵執行了unique操作（特徵歸一化以簡化計算），因此在PS端是不可能獲取真實特徵和label頻次的。需要Python端對placeholder統計後，上傳給server端指定的Variable，優化器通過slot獲得該Variable後作出聯合決策。最naive的思路是模擬離線頻次過濾，對特徵進行計數，只有達到一定閾值後再進入訓練，但這樣破壞了數據完整性：如總頻次6，而閾值過濾為5，則該特徵出現的前5次都被忽略了。為此我們提出了兩種優化方案：
- 基於泊松分佈的特徵頻次估計
在離線shuffle後的特徵滿足均勻分佈，但對在線數據流，特徵進入訓練系統可看做泊松過程，符合泊松分佈：
其中n為當前出現的次數，t為當前的步數，λ為單位時間發生率，是泊松分佈的主要參數，T為訓練總步數。
為特徵最低門限（即最少在T時間內出現的次數）。
因此我們能通過前t步的特徵出現的次數n，將t時刻當做單位時間，則
。 根據泊松分佈，我們可以算出剩餘
時間內事件發生大於等於
次的概率
。 每次該特徵出現時，都可按該概率
做伯努利採樣，特徵在t步進入系統的概率用下式計算：
通過真實線上數據仿真，它能接近離線頻次過濾的效果，其λ是隨每次特徵進入時動態計算的。它的缺陷是：
- 當t越小時，事件發生在t內的次數的variance越大，所以會以一定概率誤加或丟棄特徵。
- 未來總的訓練步數T在在線學習中是未知的。
- 頻次過濾與優化器相分離，導致不能獲得優化器的統計信息。
- 動態調L1正則方案
在經典的FTRL實現中，L1正則對每個特徵都是一致的。這導致了2.2.1 中提到的問題：過大的L1雖然過濾了極低頻特徵，但也影響的了模型的性能。參考各類優化器（如Adam）對learning_rate的改進，我們提出：通過
特徵頻次影響L1正則係數，使得不同頻次的特徵有不同的lasso效果。
特徵頻次和基於MLE的參數估計的置信度相關，出現次數越低置信度越低。如果在純頻率統計基礎上加入一個先驗分佈（正則項），當頻率統計置信度越低的時候，越傾向於先驗分佈，相應的正則係數要更大。我們經過多個實驗，給出了以下的經驗公式：
其中c是懲罰倍數，
為特徵最低門限，這兩者皆為超參，
是當前特徵出現的頻次。
我們在線上環境，使用了動態調節L1正則的方案 。在uvctr不降甚至有些微提升的基礎上，模型特徵數比不使用頻次過濾減少75%，進而從實驗證明了頻次過濾對稀疏化的正向性。它的缺點也很明顯：特徵頻次和正則係數之間的映射關係缺少嚴謹證明。
頻次過濾作為特徵管理的一部分，目前還少有相關論文研究，亟待我們繼續探索。
3. 模型壓縮和穩定性
3.1 模型壓縮
在工程上，由於做了優化，如特徵被優化器lasso後，只將其置0，並不會真正刪除；在足夠多步數後才刪除。同時引入內存池，避免特徵的反覆創建和刪除帶來的不必要的性能損失。 這就導致在訓練結束後，模型依然存在大量0向量。導出時要進一步做模型壓縮。
由於引入了HashPull和HashPush等非TF原生算子，需要將其裁剪後轉換為原生TF的op。 我們將這些步驟統稱圖裁剪(GraphCut)， 它使得線上inference引擎，不需要做任何改動即可兼容彈性改造。由於有效特徵大大減少，打分速度相比原引擎提升50%以上。
我們將圖裁剪看做TF-graph的靜態優化問題，分為3個步驟：
- 第一遍遍歷Graph，搜索可優化子結構和不兼容的op。
- 第二遍遍歷，記錄節點上下游和元數據，裁剪關鍵op，並將Variable的非0值轉存至Tensorflow原生的MutableDenseHashTable。本步驟將模型體積壓縮90%。
- 拼接新建節點，重建依賴關係，最後遞歸回溯上游節點，去除與inference無關的子圖結構
我們實現了完整簡潔的圖裁剪工具，在模型熱導出時調用， 將模型從原先的8GB左右壓縮到幾百兆大小，同時保證模型打分一致。
3.2 模型穩定性和監控
online learning的穩定性非常重要。我們將線上真實效果，與實時模型生成的效果，進行了嚴密的監控，一旦樣本偏差過多，就會觸發報警。
由於需捕捉時變的數據變化，因而不能用固定的離線數據集評估模型結果。我們使用阿里流式日誌系統sls最新流入的數據作為評估樣本，以滑動窗口先打分後再訓練，既維持了不間斷的訓練，不浪費數據，同時儘可能高頻地得到最新模型效果。
我們對如下核心指標做了監控：
- 樣本監控： 正負比例，線上打分值和online-auc(即線上模型打分得到的auc)，產出速率，消費速率。
- 訓練級監控： AUC, User-AUC(參考備註)，loss, 模型打分均值（與樣本的正負比例對齊），異常信息。
- 特徵級管理： 總特徵規模，有效/0/刪除特徵規模，新增/插入/刪除的速率。
- 整體模型和調度：模型導出的時間，大小，打分分佈是否正常，是否正常調度。
- 業務指標：uvctr,pvctr(小時級更新，T+1報表)。
線上與訓練指標之間的對應關係如下表：
通過http接口，每隔一段時間發送監控數據，出現異常會及時產生釘釘和郵件報警。下圖是對9月20日到27號的監控，從第二張圖表來看，模型能較好的適應當前數據流的打分分佈。
User-AUC：傳統的AUC並不能完全描述uvctr，因為模型很可能學到了不同用戶間的偏序關係，而非單個用戶在不同offer下的點擊偏序關係。為此，我們使用了User-AUC，它儘可能地模擬了線上uvctr的計算過程，在真實實驗中，監控系統的uvctr小時報表，與實時模型輸出的User-AUC高度一致。
4. 工程實現和效果
目前算法已經在支付寶首頁的多個推薦位上線。推薦系統根據用戶的歷史點擊，融合用戶畫像和興趣，結合實時特徵，預估用戶CTR，進而提升系統整體點擊率。
我們以推薦位業務為例說明，其採用了經典的wide&deep的網絡結構，其sparse部分包含百級別的group(見下段備註1)。 一天流入約百億樣本，label的join窗口為固定時長。由於負樣本佔大多數，上游鏈路對正負樣本做了1：8的降採樣(見下文備註2)。
訓練任務採用螞蟻統一訓練平臺構建，並使用工作流進行定時調度，離線和在線任務的其他參數全部一致。Batchsize為512，每200步（即20萬樣本）評估結果，定時將模型通過圖裁剪導出到線上系統。當任務失敗時，調度系統會自動拉起，從checkpoint恢復。
該推薦業務的online learning桶最近一週相比線上多模型融合最優桶提升4.23% ， 相比隨機對照提升達34.67% 。 另一資訊推薦業務其最近一週，相比DNN基準uv-ctr提升+0.77%，pv-ctr提升+4.78%。實驗效果相比有較大的提升。
備註1： group embedding是將相似emb特徵分組，各自lookup求和後再concat，使得特徵交叉在更高層進行。其設計是考慮到不同group的特徵差異很大(如user和item)，不應直接對位求和。備註2： inference打分僅做pointwise排序，採樣雖改變數據分佈但不改變偏序關係，因此並未在訓練上做補償。5. 未來工作
彈性特徵已經成為螞蟻實時強化深度學習的核心要素。它只是第一步，在解決特徵空間按需創建問題後，它會帶來一個充滿想象力的底層架構，眾多技術都能在此基礎上深挖： 在工程上，可繼續從分鐘級向秒級優化，進一步提升鏈路實時性並實現模型增量更新； 在算法上，我們正在探索如樣本重要性採樣，自動特徵學習，在線線性規劃與DNN的結合，實現優化器聯合決策等技術。
由於在線學習是個複雜的系統工程，我們在開發和調優時遇到了大量的困難，涉及樣本回流，訓練平臺，模型打分，線上評估等一系列問題，尤其是穩定性，但基本都一一克服。為了保證線上結果穩定可信，我們在觀察和優化兩三個月後才發佈這篇文章，希望和業界同仁一起交流探討。
本文作者為螞蟻金服人工智能部認知計算組的基礎算法團隊，團隊涉及圖像、NLP、推薦算法和知識圖譜等領域，擁有定損寶和理賠寶等核心業務。閱讀更多 互聯網編程 的文章
