在搜尋、推薦、廣告等需要進行大規模排序的場景，級聯排序架構得到了非常廣泛的應用。以阿里的線上廣告系統為例，按順序一般包含召回、粗排、精排、重排等模組。粗排在召回和精排之間，一般需要從上萬個廣告集合中選擇出幾百個符合後鏈路目標的候選廣告，並送給後面的精排模組。粗排有很嚴格的時間要求，一般需要在10～20ms內完成打分。在如此巨大的打分量以及如此嚴格的RT需求下，粗排是如何平衡算力、RT以及最後的打分效果呢？本文將為大家分享粗排技術體系以及粗排最新進展COLD，目前COLD排序系統已經在阿里定向廣告各主要業務落地並取得了巨大的線上效果提升。
本文的分享，主要圍繞下面幾點展開：
粗排的發展歷史粗排的最新進展COLD粗排技術的總結與展望01
粗排的發展歷史
首先和大家分享下粗排的發展歷史。
1. 粗排的背景
什麼是粗排？一般的話，一個大型的工業級排序系統都會採用多階段的排序架構，通常會包含四部分：召回、粗排、精排和重排。以阿里巴巴定向廣告為例，召回的規模一般是千萬左右，而粗排打分規模一般是一萬以上，精排和重排的規模一般是上百左右。粗排是處於召回和精排的一箇中間階段，目標是在滿足算力RT約束的情況下，從上萬個廣告集合中選擇滿足後鏈路需求的候選廣告集合。
粗排和精排有兩點不同：
算力和RT的約束更嚴格：粗排的打分量遠高於精排，同時有更嚴格的延遲約束，阿里巴巴定向廣告的要求是10-20ms解空間問題更嚴重：粗排和精排訓練的時候使用的都是展現樣本，但是線上打分環節粗排打分候選集更大，打分階段距離展現環節更遠，因此粗排階段打分集合的分佈和展現集合差距相比精排更大，解空間問題也更嚴重。2. 粗排的兩大技術路線
粗排的技術路線其實就是解決粗排一般該怎麼迭代的問題，由於粗排是處於召回和精排之間的一個模組，因此粗排本身的迭代會受到前後鏈路的制約，因此需要站在整個鏈路的視角來看待這個問題。縱觀整個鏈路，粗排一般存在兩種技術路線：集合選擇和精準值預估。
① 集合選擇技術
集合選擇技術是以集合為建模目標，選出滿足後續鏈路需求的集合的方法，該技術路線在召回非常典型，這其實也非常符合粗排的定位。該方法優點是算力消耗一般比較少，缺點是依賴於對後鏈路的學習，可控性較弱。
什麼叫可控性？也就是說如果希望進行一些調整的話，由於這種方式依賴於透過資料迴流對後鏈路進行學習，而資料迴流往往比較慢，同時對資料量也有要求，可能需要後面鏈路的這些策略調整影響到比較大的流量之後，粗排才可以學習到，因此這種方式可控性比較弱，是偏被動的一種方式。
這種技術路線有以下常見的幾種方法：
多通道方法：類似於召回，針對不同的目標構建不同的通道，然後分別選出不同的集合，然後再進行合併選擇。Listwise方法：一般是直接建模集合的損失，典型演算法如LamdaMART。為了更好理解listwise演算法，這裡提一下pointwise演算法和pairwise演算法，pointwise演算法一般是點估計的方式，訓練過程只考慮單條樣本；而pairwise演算法訓練過程中會考慮當前樣本和其它樣本的相互關係，會構造這樣的pair，並在訓練的過程中引入這方面的pairwise loss，訓練目標可能是正pair排在負pair的前面；Listwise更近一步，在訓練的時候會考慮整個集合，會希望整個集合的指標如NDCG等達到最大化，如LamdaMART演算法。序列生成方法：直接做集合選擇。一般包含集合評估器和集合生成器，演算法過程如下：首先，用評估器對所有的item進行打分並選擇一個得分最高的，作為集合中的第一個商品。接下來，再挑選第二個商品，把第一個商品和所有可能的第二個商品進行組合，並用評估器進行打分。之後，選擇得分最高的集合，並持續使用類似於貪心的方式不斷的搜尋，最終得到一個最優的集合。② 精準值預估技術
精準值預估技術直接對最終系統目標進行精確值預估，其實也就是pointwise的方式。
以廣告系統為例，建模的目標一般是ECPM，即
ECPM=pCTR*bid
利用預估技術預估pCTR，然後預估bid，最終根據ECPM來進行排序，在粗排的話就是取排序的分最高的topK作為最終的集合。這種方式的優點是可控性強，因為是直接對整個目標進行建模，如果建模方式做了調整的話，可以直接調整排序公式，調整預估模型，對整個鏈路的掌控力更強。缺點就是算力消耗比較大，而且預估越準確，算力消耗也越大。
3. 粗排的技術發展歷史
粗排在工業界的發展歷程可以分成下面幾個階段：
① 最早期的第一代粗排是靜態質量分，一般是統計廣告的歷史平均CTR，只使用了廣告側的資訊，表達能力有限，但是更新上可以做到很快。
② 第二代粗排是以LR為代表的早期機器學習模型，模型結構比較簡單，有一定的個性化表達能力，可以線上更新和服務。
其中①②可以合稱為“粗排的前深度學習時代（2016年以前）”。
向量內積模型相比之前的粗排模型，表達能力有了很顯著的提升，其優點：
內積計算簡單，節省線上打分算力User向量和Ad向量離線計算產出，因此可以做的非常複雜而不用擔心線上RT問題雙塔結構的user側網路可以引入transformer等複雜結構對使用者行為序列進行建模然而仍然有許多問題：
模型表達能力仍然受限：向量內積雖然極大的提升了運算速度，節省了算力，但是也導致了模型無法使用交叉特徵，能力受到極大限制。模型實時性較差：因為使用者向量和廣告向量一般需要提前計算好，而這種提前計算的時間會拖慢整個系統的更新速度，導致系統難以對資料分佈的快速變化做出及時響應，這個問題在雙十一等場景尤為明顯。存在冷啟動問題，對新廣告、新使用者不友好迭代效率：user向量和item向量的版本同步影響迭代效率。因為每次迭代一個新版本的模型，分別要把相應user和item向量產出，其本身迭代流程就非常長，尤其是對於一個比較大型的系統來說，如果把user和item都做到了上億的這種級別的話，可能需要一天才能把這些產出更新到線上，這種迭代效率很低。針對向量內積模型的問題，也有很多相關的改進，典型的如下面這個方法。
向量版Wide&Deep模型，deep部分仍然是向量內積結構，wide部分引入基於人工先驗構造的user和ad的交叉特徵，一定程度上克服了向量內積模型無法使用交叉特徵的問題。然而該方法仍然有一些問題，wide部分是線性的，受限於RT的約束，不能做的過於複雜，因此表達能力仍然受限。
另外一個典型的改進方法是向量內積模型的實時化， user向量透過線上打分實時產出，ad向量仍然離線產出，但是更新頻次增加。
透過實時打分，可以引入實時特徵，實時性加強。然而實時打分使向量內積模型的RT和算力優勢減弱，user模型處於RT的約束不能設計的很複雜，而且該方法還引入了新的打分模型和ad向量版本不一致的問題。
④第四代COLD，下一代粗排框架（2019）-算力感知的線上輕量級的深度粗排系統。下面將詳細介紹該模型。
02
粗排的最新進展COLD
前面粗排的相關工作僅僅把算力看做系統的一個常量，模型和算力的最佳化是分離的。我們重新思考了模型和算力的關係，從兩者聯合設計最佳化的視角出發，提出了新一代的粗排架構COLD ( Computing power cost-aware Online and Lightweight Deep pre-ranking system )。它可以靈活地對模型效果和算力進行平衡。COLD沒有對模型結構進行限制，可以支援任意複雜的深度模型。這裡我們把GwEN ( group-wise embedding network ) 作為我們的初始模型結構。它以拼接好的特徵embedding作為輸入，後面是多層全連線網路，支援交叉特徵。當然，如果特徵和模型過於複雜，算力和延時都會難以接受。因此我們一方面設計了一個靈活的網路架構可以進行效果和算力的平衡。另一方面進行了很多工程上的最佳化以節省算力。
總結為以下幾點：
基於演算法-系統Co-Design視角設計，算力作為一個變數與模型進行聯合最佳化模型結構沒有限制，可以任意使用交叉特徵工程最佳化解決算力瓶頸線上實時系統，實時訓練，實時打分，以應對線上分佈快速變化1. 模型結構
① 特徵篩選
精簡網路的方法有很多，例如網路剪枝 ( network pruning)、特徵篩選 ( feature selection)、網路結構搜尋 ( neural architecture search)等。我們選擇了特徵篩選以實現效果和算力的平衡，當然其他技術也可以進行嘗試。具體來說，我們把SE (Squeeze-and-Excitation) block引入到了特徵篩選過程中，它最初被用於計算機視覺領域以便對不同通道間的內部關係進行建模。這裡我們用SE block來得到特徵重要性分數。假設一共有M個特徵，ei表示第i個特徵的embedding向量，SE block把ei壓縮成一個實數si。具體來說先將M個特徵的embedding拼接在一起，經過全連線層並用sigmoid函式啟用以後，得到M維的向量s：
這裡向量s的第i維對應第i個特徵的重要得分，然後再將s_i乘回到e_i，得到新的加權後的特徵向量用於後續計算。
在得到特徵的重要性得分之後，我們把所有特徵按重要性選擇最高的top K個特徵作為候選特徵，並基於GAUC、QPS和RT指標等離線指標，對效果和算力進行平衡，最終在滿足QPS和RT要求情況下，選擇GAUC最高的一組特徵組合，作為COLD最終使用的特徵。後續的訓練和線上打分都基於選擇出來的特徵組合。透過這種方式，可以靈活的進行效果和算力的平衡。
注意Se Block僅用於特徵篩選階段，線上模型不包含該結構。
② 基於scaling factor的結構化剪枝
此外COLD還會進行剪枝，做法是在每個神經元的輸出後面乘上一個gamma，然後在訓練的loss上對gamma進行稀疏懲罰，當某一神經元的gamma為0時，此時該神經元的輸出為0，對此後的模型結構不再有任何影響，即視為該神經元被剪枝。
在訓練時，會選用迴圈剪枝的方式，每隔t輪訓練會對gamma為0的神經元進行mask，這樣可以保證整個剪枝過程中模型的稀疏率是單調遞減的。
這種剪枝方法在效果基本不變的情況下，粗排GPU的QPS提升20%。
最終模型是7層全連線網路。
2. 工程最佳化
為了給COLD使用更復雜的特徵模型開啟空間，工程上也進行了很多最佳化。在阿里定向廣告系統中，粗排的線上打分主要包含兩部分：特徵計算和網路計算。特徵計算部分主要負責從索引中拉取使用者和廣告的特徵並且進行交叉特徵的相關計算。而網路計算部分，會將特徵轉成embedding向量，並將它們拼接進行網路計算。
① 並行化
為了實現低時延高吞吐的目標，平行計算是非常重要的。而粗排對於不同的廣告的計算是相互獨立的，因此可以將計算分成並行的多個請求以同時進行計算，並在最後進行結果合併。特徵計算部分使用了多執行緒方式進一步加速，網路計算部分使用了GPU。
② 行列轉換
特徵計算的過程可以抽象看做兩個稀疏矩陣的計算，一個是使用者矩陣，另一個是廣告矩陣。矩陣的行是batch_size，對於使用者矩陣來說batch_size為1，對於廣告矩陣來說batch_size為廣告數，矩陣的列是featue group的數目。常規計算廣告矩陣的方法是逐個廣告計算在不同feature group下特徵的結果，這個方法符合通常的計算習慣，組合特徵實現也比較簡單，但是這種計算方式是訪存不連續的，有冗餘遍歷、查詢的問題。事實上，因為同一個feature group的計算方法相同，因此可以利用這個特性，將行計算重構成列計算，對同一列上的稀疏資料進行連續儲存，之後利用MKL最佳化單特徵計算，使用SIMD (Single Instruction Multiple Data)最佳化組合特徵運算元，以達到加速的目的。
對於COLD來說，絕大部分網路計算都是矩陣乘法，而NVIDIA的Turning架構對Float16和Int8的矩陣乘法有額外的加速，因此引入Float16計算對提升效能非常必要 。但是Float16會損失計算精度，特別是在sum-pooling的情況下，數值有可能超出Float16的範圍。為了解決這個問題，一種方式是使用BN。但是BN本身的引數範圍也有可能超過Float16。因此只能使用混合精度的方式，對於BN層使用Float32，而後面的層使用Float16。另一種方式是使用引數無關的歸一化方式，例如log函式。但是log函式不能處理負數，並且輸入值接近0的時候會輸出絕對值較大的數字。因此我們設計了一種分段平滑函式，我們叫做linear_log來解決這個問題。
從函式影象可以看出，linear_log函式可以將Float32的數值處理到一個比較合適的範圍。所以如果我們將linear_log函式放到第一層，那麼就可以保證網路的輸入引數在一個比較小的範圍內。具體實踐上，linear_log函式對COLD模型的效果基本沒有影響。使用Float16以後，CUDA kernel的執行效能有顯著提升，同時kernel的啟動時間成為了瓶頸。為了解決這個問題，我們使用了MPS (Multi-Process Service)來解決kernel啟動的開銷。Float16和MPS技術，可以帶來接近2倍的QPS提升。另外，使用阿里自研的含光800NPU專有硬體，替代原來的GPU，QPS進一步提升約1倍。
3. 線上服務架構
COLD沒有限制模型的結構，訓練和線上打分都是實時化的，可以帶來以下兩個優點：
線上學習的引入使COLD與向量內積模型相比，可以更及時的響應資料分佈的變化，對新廣告冷啟動也更為友好。實時架構對於模型迭代和線上A/B測試都更有利。向量內積模型由於使用者向量和廣告向量需要提前計算好，線上A/B測試也更為困難。實時架構也使COLD模型可以更快的更新，避免了向量內積模型的更新延遲問題。4. 實驗結果
這裡COLD模型使用了7層全連線的網路結構。離線評估指標除了GAUC之外，還包含了top-k recall，用於評估粗排和精排的對齊程度。
其中top k候選集合和top m候選集合均為粗排的輸入打分集合。top k集合是粗排選出的，而 top m集合是精排選出的，排序指標是eCPM(eCPM = pCTR*bid)。這裡的精排模型是DIEN。我們使用QPS (Queries Per Seconds, which measures the throughput of themodel) 和RT (return time, which measures the latency of model)來評估系統性能的影響。
① 模型效果評估
離線效果評估可以看到COLD在GAUC和Recall上都優於向量內積模型。線上效果上，COLD與向量內積模型相比在日常CTR +6.1%,RPM + 6.5%。雙十一CTR+9.1%，RPM+10.8%，提升顯著。
② 系統性能評估
從上面表格可以看到，向量內積模型的系統性能最好，而精排的DIEN的系統性能最差，COLD則在兩者之間取得了平衡。
COLD在得到特徵重要性分數以後，會選出不同的候選特徵，並基於離線指標進行特徵選擇。第二個表列了幾組供選擇的特徵，可以看到COLD是考慮效果和系統性能以後的折中。
Table 5表明，工程最佳化上引入Float16和MPS最佳化以後，QPS提升了1倍，效果顯著。
5. COLD的進一步發展
那麼COLD的後面進一步怎麼發展？答案是與精排進行更加深度的整合。目前粗排和精排都是各自獨立迭代的，這樣會造成一個前後不一致的問題，會帶來一個鏈路的內耗。而且粗排和精排維護兩套流程的話，本身維護成本也很高，尤其是像阿里巴巴定向廣告這邊，業務多而且複雜。另外，COLD和精排一樣都是非常實時化的架構，這使得粗排和精排進行更深度的聯動成為可能。
具體如何進行更加深度的整合呢？這裡我們直接將粗排和精排的生產流程合二為一，聯合訓練，共享部分引數。另外也會藉助特徵蒸餾的方式，使用精排訓練過程中的得分來指導粗排。在這個基礎上，嘗試引入精排參競日誌，對於未展現樣本藉助精排得分進行輔助學習。為什麼引入精排參競日誌？其實前面提到過，因為粗排除了RT還有一個就是解空間的問題，粗排本身見到的集合比精排更多，但是它本身模型的能力卻比精排更弱。所以為了緩解這個問題，引入精排參競日誌，這部分日誌本身是沒有label的，可以利用精排在這些label上進行打分，透過蒸餾的方式來引導粗排進行學習。為什麼說這種方式在一定程度上能緩解解空間的問題？其實是建立在精排的模型能力比粗排更強，這個強很大程度體現在精排對交叉特徵的利用上，在這種情況下，對於很多沒有展現的user和item的pair對，精排相比於粗排其實是可以給出更精確的預估的，在這個前提下，藉助精排更精確的預估分數，然後對粗排進行指導，在一定程度上是可以緩解解空間問題的。
這種方案的好處是將粗排和精排的流程合二為一，粗排精排模型一起訓練，一起產出，這樣可以提升粗排和精排的對齊程度，解決前面提到的因為前後鏈路不一致造成的鏈路損耗問題。另外引入精排參競日誌，在一定程度上也能緩解解空間問題。而且還有一個好處就是降低運維成本，減少了訓練資源，提升我們的迭代效率。
03
粗排技術的總結與展望
最後做一下總結，目前整個粗排基本已經全面邁向深度學習時代，而且深度學習時代的粗排主要存在向量內積和COLD兩種主流技術路線。沒有最好的演算法，只有最合適的演算法。不管是COLD還是向量內積，其實都有它適合的場景。有的團隊在向量內積這條路線上持續迭代，其實也是受到本身算力RT的一些限制，包括本身工程團隊等各方面因素的影響。而且很多團隊的精排也還是向量內積結構，粗排就沒有必要升級到COLD了。
最後，展望一下粗排會怎麼發展。粗排未來會存在兩種可能的路線。
一個是粗排精排化，也就是說精排技術持續向粗排遷移，粗排和精排的界限逐漸模糊，走向更深層次的整合和一體化。其實可以看到，粗排的迭代歷程本身其實就是一個粗排精排化的過程，一般很多技術如向量內積，都是先在精排落地拿到效果後，再逐漸向粗排遷移。而且算力也會更深度的參與到整個模型的迭代過程中，未來可能的話甚至不會再分粗排和精排，精排本身可能會在引入算力作為一個約束的情況下，透過AutoML等方式，產出多個不同算力版本的子模型，粗排只是其中一個，跟隨精排自動升級和迭代，從而實現全鏈路算力和效果的平衡。甚至算力足夠大的話，可以不需要粗排了，直接用精排打分就可以了。
另外其實還存在另外一條路，就是迴歸集合選擇的本質，以產出符合後鏈路需要的集合為目標，真正以集合為物件進行建模。這裡需要清楚粗排的目標是什麼？粗排的目標是選出後鏈路需要的集合。而目前粗排精排化的迭代思路其實是在做ranking，但是粗排其實只需要一個top k的集合，集合內部無序就可以了。而粗排精排化這種方式消耗了很大一部分算力在TopK的內部排序上，很多算力消耗在Top1和Top2怎麼排好，從計算角度來看是一種資源浪費。當然這條技術路線還比較新，目前還在探索中。但是這個方向是一個很有希望的方向，因為它迴歸了粗排的本質，直接面向粗排的最終目標，因此在算力的利用率和最終的天花板上是更高的。