您現在的位置是:首頁 > 武術

廣告深度學習計算:召回演算法和工程協同最佳化的若干經驗

  • 由 慈谷0BF 發表于 武術
  • 2022-04-15
簡介還是拿TopK和索引扁平化模型來舉例子,TopK 的最佳化中透過預篩選來降低問題規模的思路,和全庫模型中透過數學上的等價變換來進行計算最佳化的思路,在許多最佳化問題上都能應用

怎麼理解分位數

「來源: |智慧推薦系統 ID:gh_f8ba0cf49ce0」

背景

阿里媽媽展示廣告召回大多采用 Tree-based Deep Model(以下簡稱TDM)模型,它透過對候選廣告的聚類,構造了深達十餘層的二叉樹索引,並使用 beam search 在此索引上進行檢索[1]。由於線上服務的 latency 約束及當時的硬體算力限制使我們不能直接對整個候選集(百萬甚至千萬量級)進行模型打分。

隨著近幾年硬體(GPU & ASIC)的發展,我們在模型上的計算能力有了很大提升。於是,演算法同學從擴大打分量和提升模型複雜度的兩個方向對目前的模型進行了升級。第一個方向是進行全庫打分,即拋棄索引結構,用相對簡單的雙塔模型一次性給所有廣告打分;第二個方向誕生了索引扁平化專案,保留樹結構索引的同時將其扁平化,減少 beam search 的深度並增加寬度,同時引入 attention 計算,增加了打分模型的複雜度。

這些給工程最佳化提出了很高的要求,也帶來很大挑戰。首先,模型大小和計算量的暴增,使得打分的廣告數成倍增長,模型的複雜度也大大增加,例如索引扁平化模型中,單次打分消耗的浮點計算次數(FLOPs)就要比原 TDM 模型增長約十餘倍。其次,模型中引入了一些非典型的非數值計算(比如TopK和beam search),這些計算如果只使用TensorFlow原生運算元會帶來效能熱點,使 latency 過長(數十上百毫秒)無法滿足線上服務的要求。

本文主要分享我們是如何透過系統和演算法的協同設計,逐一解決這兩個模型在上線過程中的工程難點,為廣告召回業務迭代開啟新的空間。

路徑一: 全庫模型

1。 模型結構介紹

由於每一次使用者 page view 模型計算需要處理所有的廣告,對於線上系統來說打分量過於巨大(百萬至千萬量級),只能採用相對簡單的模型結構,這裡我們選用了經典的雙塔模型結構:使用者特徵和廣告特徵分別經過DNN得到特徵向量,用這兩個向量的內積表示匹配程度,並由TopK從中選出最大的那部分。由於廣告特徵都是固定的,所以廣告所在那一路的 DNN 可以在離線提前算完,線上模型直接拿到所有廣告的向量作為常量模型引數。如下圖所示。

廣告深度學習計算:召回演算法和工程協同最佳化的若干經驗

此模型最大的效能挑戰來自於 TopK。由於規模達到了數百萬,如使用 TF 原生 TopK 運算元,其實現並不適合我們的資料特點,latency 將高達數十 ms,不滿足線上服務的要求。第二個挑戰來自於內積,它是全模型計算量和訪存量最大的部分,對於它的處理也相當重要。

2。 對於 TopK 的最佳化

總體思路

首先,我們調研了 TF 的原生 TopK 運算元(即tf。math。topk())的 GPU 實現。它是由若干 RadixSort 組成,其時間複雜度也的確與輸入規模n成線性,如下表所示。

廣告深度學習計算:召回演算法和工程協同最佳化的若干經驗

觀察到在我們問題中 k(500or1000) 是遠遠小於 n(100W-1000W) 的,可以設定一個閾值,並透過篩選的方式過濾掉大部分資料來減少計算量。例如,我們可以選取千分之一的分位數過濾,這樣就相當於將問題規模縮減了1000倍。此篩選操作主要是一個 elementwise 比較加很小規模資料的搬運,在GPU上並行會非常快(在1000W的規模上也不會超過1ms),而這個分位數可以透過

取樣+排序

來進行粗略的估計。雖然這一過程會帶來一定的 overhead,但相比於其帶來的收益,此 overhead 可以說微乎其微。

篩選演算法

對於資料取樣的數量,既不能太多,也不能太少。太多會給排序帶來很大的 overhead;太少則分位數粒度太粗且不準。通常,我們選取的取樣數會在滿足分位精度條件的基礎上儘可能小,同時要求取樣數大於等於k,原因如下:

我們選作閾值的分位數是估計出來的,並不是準確值,所以可能存在經過此閾值篩選出的個數實際上小於k,從而導致後續 TopK 出錯。當這種 badcase 出現時,我們的做法是不斷選取下一個分位數(即經排序的樣本的下一個)再進行篩選,直到篩選出的個數大於等於k。為保證此迴圈能夠正確的結束,我們需要保證樣本個數s大於等於k。這樣,只要當閾值取到第k個之後,就能保證一定有足夠的數被篩選出來(即前k個樣本)。

同樣,為了降低這一 badcase 出現的機率,我們可以適當放寬此閾值。在實踐中,我們的做法是將閾值的分位數放寬到了 k/n 的兩倍,即選取第 2ceil(k/ns)+1 大的樣本作為閾值。根據 order statistics,第k個的樣本的機率分佈滿足如下公式:

廣告深度學習計算:召回演算法和工程協同最佳化的若干經驗

下圖顯示了均勻分佈上的1000個樣本,1倍分位閾值(第二大樣本)和2倍分位閾值(第三大樣本)篩選出來的個數的分佈情況。左圖為機率密度函式 PDF,右圖為累積分佈函式 CDF。橫座標是篩出的比例,即篩選出的個數除以n。可計算出在 k=1000,n=1000W 的情況下,即橫座標為 k/n=0。0001 時,此方法能將badcase發生機率降低30倍。

廣告深度學習計算:召回演算法和工程協同最佳化的若干經驗

與原生TopK效能對比

我們透過TF原生op搭建了一個子圖,它不依賴任何 custom op 的實現,並且能在 GPU 上高效的執行。為了匹配 TF 原生的 TopK 運算元的語義,我們透過 tf。while() 實現了對高維輸入的支援。

下圖顯示了 batchsize=8 的不同尺寸下,原生 TF 實現和我們的最佳化演算法的效能對比。我們的最佳化演算法相比原生算計效能有了成倍的提升,且在越大的尺寸上優勢越明顯。

廣告深度學習計算:召回演算法和工程協同最佳化的若干經驗

相較於現在常規使用的向量檢索框架(例如 Faiss),這種基於 TF 的做法相對靈活,在百萬千萬的數量級上也有不錯的效能。在一千萬的規模上,我們的 TopK 演算法能達到視訊記憶體頻寬理論上限的10%左右,並且隨著問題規模的擴大這一指標能繼續提升(Faiss中的 WarpSelection 演算法能做到16%,但k的大小受到GPU暫存器數量的限制[2])。當然,對於 GPU 上類似 WarpSelection 的 state-of-art 的 TopK 演算法,我們也能很容易的遷移進TF裡來。

3。 對於內積的最佳化

Batching

當 batchsize 大於1的時候,這裡的內積表現為矩陣乘。TF (v1。15)原本用的 cublasSgemmEx 介面並不能在 fp16 型別的 GEMM 上啟用 TensorCore,修改成 cublasGemmEx 可以解決這一問題。在 m=8 時,獲得約 20%~40% 不等的效能提升,實測 latency 見下表。

廣告深度學習計算:召回演算法和工程協同最佳化的若干經驗

觀察到在 TensorCore 的加持下,當 batch 從1到8增大時,latency 幾乎沒怎麼變,也就是增大 batchsize 可以顯著提升內積這部分的計算效率。不過考慮到線上 latency 的約束,batchsize 還是需要控制在合理範圍之內,實踐中,我們就將其控制在8以下。

我們測試了 batching 帶來的收益。對於一百萬左右規模的模型,在線上可以容許的 latency 範圍內,按 batchsize=8 做 batching 可以將有效服務容量提升約3倍。

關於 INT8 量化

內積部分的訪存在整個模型計算中的佔比達到60%以上,不做 batching 時,更是高達90%。為進一步減少訪存,我們嘗試將這個 GEMM 用 INT8 量化。這裡有一個問題需要注意,在 cublasLt 介面中,INT8 GEMM 的輸入矩陣需要遵循特殊的記憶體排列格式,A矩陣和C矩陣遵循 CUBLASLT_ORDER_COL32 格式而B矩陣需要遵循 CUBLASLT_ORDER_COL4_4R2_8C 格式,因此需要再計算前後進行 transform 操作。

幸運的是,B矩陣(即廣告向量的矩陣),是一個常量,它的 transform 過程可以被 constant fold,從而避免很多訪存開銷。對與C矩陣,可以將它的 transform 與一個定製的近似 TopK 的運算元進行融合,降低 transform 的開銷。而A矩陣的 transform 是無法避免的。

需要注意的時,上文中所描述的利用分位數篩選的 TopK 演算法對資料的區分度是有要求的。如果資料的區分度不夠大,這個篩選演算法就不能有效地約減問題規模,會拖慢後面尋找真實 TopK 的過程的效率。而內積部分使用 INT8 量化的話有可能會導致這個問題,需要對量化演算法進行調整和校準。

關於 cache 的利用

另一個節省訪存的做法就是充分利用 cache。在內積計算的過程中,大部分的訪存都集中在對廣告向量的讀取上,如果我們能讓這個 constant 常駐快取記憶體的話,就可以大幅減少記憶體訪問。

GPU 的快取太小,不太適合進行快取常駐,而目前湧現的眾多人工智慧ASIC就擁有相對來說大得多的快取,例如平頭哥的含光800晶片,更適合這樣的最佳化。同時這些晶片在矩陣乘等密集計算上的算力相比 GPU 也毫不遜色。但由於這些晶片支援的運算元可能不那麼全面,某些定製的量化演算法和 TopK 之類的計算就需要被 offload 到 CPU 端進行,此過程中會造成 PCIE 傳輸的 overhead。

路徑二:索引扁平化模型

1。 模型結構介紹

此模型將原本 TDM 模型中十餘層的二叉樹索引壓縮到了三四層,第一層展開為數千節點,之後每一層按照十幾的度展開。我們從第二層開始進行 beam search ,總共經過若干輪模型打分以及 TopK 的篩選,每次模型打分的數量在數萬,如圖所示。

廣告深度學習計算:召回演算法和工程協同最佳化的若干經驗

相比於 TDM 模型,打分輪數減少了2~3倍,而每輪打分的廣告數擴充了4~6倍。為了拿到更精準的打分結果,演算法上在原來 TDM 的打分模型 DNN 的基礎上引入了使用者的序列特徵與廣告特徵交叉進行 multi-head attention 的計算。這種結構在廣告系統上用的相當廣泛,如精排的 DIEN 模型中就有應用[3]。這裡的挑戰主要有兩個,一是如何在TF裡用表示樹型索引的結構並在這種表示上高效的進行beam search所需的操作;二是高達數萬的廣告候選集的大小會在乘法效應的作用下影響所有的運算元,如何管控它帶來的計算資源(尤其是訪存)的膨脹。

2。 樹索引的設計

排他索引

由於廣告的索引是一棵完全樹的結構,同時從線上推理的角度看,它並不會變化,因此是一個 const。因此,我們設計了一個高效的完全數樹(complete tree)結構的表示,節省空間的同時還能實現高效的子節點的查詢。將一棵樹的節點按層序遍歷編號,然後從0號節點開始,在一個數組中依次記錄下每個節點的子節點編號中最小的那個,直到葉子節點為止,最後再在陣列末尾加上整棵樹的節點個數。這樣一來,對於一棵樹的表示 {a0, a1, a2, a3 。。。},整數區間[ai,ai+1) 就表示編號為i的節點的子節點編號。在這種表示下,查詢一個節點的子節點的時間複雜度為O(1)。例子:下圖中的樹就能表示成:{1, 5, 8, 10, 11, 13},節點1的子節點就是區間 [5, 8)={5, 6, 7}。

廣告深度學習計算:召回演算法和工程協同最佳化的若干經驗

非排他索引:ragged tensor

上述資料結構只能表達樹的結構,也就是排他的索引:每兩個聚類之間不能存在交集。如果演算法上放寬這條限制,索引結構就會變成圖,上述的資料結構就無能為力了。這種情況下,我們可以使用TF原生的 ragged tensor 來表示這個索引,即第i行表示第i個節點的子節點序號。在這種表示下,對子節點的查詢可以透過 gather+flat+unique 來進行。這樣做的效率會低於上一節中的資料結構,但由於索引計算的佔比不大,效能差異尚可以接受。

3。 訪存最佳化

在最佳化的過程中,我們發現主要瓶頸都集中在視訊記憶體頻寬上。此模型對視訊記憶體頻寬的佔用達到90%以上,觸及天花板。為了減少訪存頻寬,我們運用了下面三種圖最佳化的手段,透過數學上的等價變換,儘可能減少中間結果大小。

交換 broadcast 與 transpose

廣告深度學習計算:召回演算法和工程協同最佳化的若干經驗

這樣 elementwise multiply + transpose 的結構出現在 attention 中,這裡的 elementwise multiply 包含一個隱式的 broadcast,使得之後的 transpose 所要移動的記憶體量增加了L倍。這裡我們可以交換這兩個op的位置,先做 transpose,這樣可以避免隱式 broadcast 帶來的記憶體膨脹的問題。

核函式近似與交換矩陣乘順序

廣告深度學習計算:召回演算法和工程協同最佳化的若干經驗

一般來說,對於 linear 或者 elementwise 的op,我們會比較容易做數學上的變換從而進行各方面最佳化。注意到 attention 中存在 softmax(AB) 的結構,它是一個核函式,可以表示成內積形式。因此我們將原本的 softmax(AB)*C 近似替換成了f(A)*f(B)C[4]。由於這裡A矩陣較大的,而B和C矩陣較小,我們可以根據矩陣乘的結合律按照 f(A)(f(B)*C) 的順序計算,從而保證中間結果也維持在了較小的規模。

拆分 tile+concat+matmul

廣告深度學習計算:召回演算法和工程協同最佳化的若干經驗

DNN 第一層的 matmul 是整個模型中最大的op,它是輸入是由兩個兩部 concat 而來的。第一部分的 batchsize 是1,而第二部分的 batchsize 高達數萬,而在 concat 前會將前者複製多份(tile操作),從而使其 batchsize 與後者保持一致。觀察到 tile,concat,matmul 都是線性操作,因此可以將這個過程進行線性變換,將兩個部分分開計算後再合併,這樣就避免了第一部分的複製操作,節省了大量的計算和記憶體資源。

4。 Beam Search 寬度的調節

由於訪存的消耗都與打分量成正比,最直接有效進行最佳化的方式就是控制打分量,也就是 beam search 的寬度。最終選出的廣告只有數百個,而目前 beam search 的寬度在數萬的級別,相當於只選出了前幾十分之一。考慮到縮小打分量可能會影響召回的效果,所以我們考察了召回率隨之變化的情況,如下表。可見即使將寬度縮小一半(表上從15W縮減到7。5W),召回率也不會相差太多。

廣告深度學習計算:召回演算法和工程協同最佳化的若干經驗

在我們的架構設計中,beam search 寬度可以由上游請求中的引數決定(作為模型輸入傳進來),這樣業務可以實時對效果和水位進行調整 tradeoff。這相當於提供了無需替換模型就進行降級的能力。

總結

本文詳細介紹了我們是如何解決召回新模型上線過程中的工程問題的。這離不開與演算法同學的通力合作。其中很多問題都需要工程和演算法的協同最佳化:比如 TopK 的篩選對區分度的需求需要量化演算法來保證;再比如索引扁平化模型中 att 結構的選擇和需要從效果和計算資源兩方面進行考量的。

我們認為相比於解決上述問題的具體方法,如何得到這些方法的思路更為重要。還是拿TopK和索引扁平化模型來舉例子,TopK 的最佳化中透過預篩選來降低問題規模的思路,和全庫模型中透過數學上的等價變換來進行計算最佳化的思路,在許多最佳化問題上都能應用。希望本文的讀者能從這些思路中有所收穫。

引用

[1] Zhu, Han, et al。 “Learning tree-based deep model for recommender systems。” Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining。 2018。

[2] Johnson, Jeff, Matthijs Douze, and Hervé Jégou。 “Billion-scale similarity search with gpus。” IEEE Transactions on Big Data (2019)。

[3] Zhou, Guorui, et al。 “Deep interest network for click-through rate prediction。” Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining。 2018。

[4] Choromanski, Krzysztof, et al。 “Rethinking attention with performers。” arXiv preprint arXiv:2009。14794 (2020)。

更多幹貨請點選:

【免費下載】2021年8月熱門報告盤點&下載

多目標排序在快手短影片推薦中的應用實踐。pdf

如何打造標準化的資料治理評估體系?

大資料驅動的因果建模在滴滴的應用實踐

聯邦學習在騰訊微視廣告投放中的實踐

如何搭建一個好的指標體系?

2021年中國資料中臺研究報告

強化學習在招聘推薦冷啟動中的應用實踐

如何利用NLP與知識圖譜處理長句理解?

【乾貨】電商知識圖譜構建及搜尋推薦場景下的應用

推薦系統架構與演算法流程詳解

【實踐】微博推薦演算法實踐與機器學習平臺演進。pdf

某影片APP推薦詳解(萬字長文)

資料分析從理念到實操白皮書。pdf

嗶哩嗶哩推薦策略分析與思考

關注我們

廣告深度學習計算:召回演算法和工程協同最佳化的若干經驗

Top