雙11當天，淘寶搜索如何讓CPU使用率降45%，GMV提1% | 論文

本文是阿里巴巴的一篇論文介紹投稿。這篇論文被收錄於2017國際知識發現與數據挖掘大會（KDD），主要在商品智能排序領域進行了研究。

這篇論文主要講述，去年雙11期間，淘寶搜索在有限計算資源情況下，如何拿到更好的排序結果、保證用戶的搜索體驗、以及點擊、成交量和成交額等目標的完成。

實際的結果是，去年雙11當天，淘寶搜索引擎的負載在最高峰也沒有超過70%，CPU的使用率降低了約45%，搜索的平均延遲下降了約30%，同時帶來的GMV提升了近1%。

以下是這篇論文的詳細介紹。

《多層級聯學習在大型電商排序系統的應用（Cascade Ranking for Operational E-commerce Search）》

作者：劉士琛，肖非，歐文武，司羅

該論文設計並實現了一種級聯式電商搜索方式：它的主要思想是將一次排序分成遞進的多個階段，各階段使用逐漸複雜的特徵去得到逐漸準確的結果。在靠前階段使用簡單特徵過濾顯然不合要求的結果，在靠後階段使用複雜特徵辨別難以區分的結果。除此以外，演算法結合電商場景的特殊性，嚴格限制了引擎的響應時間以及返回商品的數量，以保證用戶的搜索體驗。

離線實驗和在線實驗均驗證了演算法的正確性以及有效性，對比傳統的方法能提升準確率的同時大幅提升了計算性能；在去年雙11，在新增了大量準確又耗時的計算特徵(包括強化學習和深度學習特徵)的情況下，演算法極大的保證了引擎的效率，使排序對引擎的壓力下降40%，同時使排序效果有較大提升。

面臨的問題

淘寶的搜索系統無疑是全球最大的電商搜索系統。「最大」這裡包括商品量、用戶量，包括引導的成交額、點擊成交量，還包括引擎的訪問次數、訪問QPS…這樣一個搜索引擎，所需要面對的訪問壓力也是巨大的，尤其在「雙十一」等大促場景，壓力更是平時的數倍。

另外一般搜索引擎的目標主要是引導點擊，而在電商中，排序的結果更希望引導的是成交量和成交額。

因此我們的搜索系統、排序方案需要考慮多種實際問題。首先是在有限計算資源情況下，如何拿到更好的排序結果；其次是怎樣保證用戶的搜索體驗，包括結果返回時間、返回商品量等；最後是怎麼保證電商場景下的多目標，包括點擊、成交量和成交額。

已有方法的不足

學術界和工業界都有大量learning to rank方面的研究，均期望能通過機器學習，為用戶給出更優的排序結果。然而絕大部分相關工作都集中在如何提升排序的質量，卻並不關係排序的效率，而太低效的排序方案在實際的工業在線應用中，往往是不可接受的。

淘寶搜索和其他類似應用主要採取的解決方案是使用一種「兩輪排序方案」：在第一輪使用非常簡單的特徵去得到一個小的候選集；第二輪在小的集合上做複雜的排序。可是這種啟髮式的方案並不能保證性能與效果的取捨是最優的。基於以上考慮，我們需要一種全新的、工業可用的、能更合理平衡效率與性能的排序方案。

CLOSE排序演算法，平衡性能與效率，保障用戶體驗

論文受圖像中快速目標檢測演算法的啟發，發現並不是引擎中的每個商品都需要全部特徵參與計算、排序——一些基本特徵能幫助過濾掉大多數商品；逐漸複雜的特徵過濾逐漸難以區分好壞的商品；全部特徵排序剩餘商品。

基於這樣的思想，論文提出了一種多輪級聯排序方法Cascade model in a Large-scale Operational Ecommerce Search application（CLOES）。

CLOES主要採用了一種基於概率的cascade learning方法，將排序分為多輪計算；將排序效果和CPU的計算量作為優化目標，一起建立數學模型，同時優化。

除了考慮性能與效率，演算法還考慮了用戶的搜索體驗，保證用戶在輸入任何一個query后都能在限制時間內得到足夠的返回結果。最後CLOES還考慮了電商場景的特殊性，保障了多目標的平衡與可調整。

平衡性能與效率的排序（Query-Dependent Trade Off Between Effectiveness and Efficiency）

論文最重要的部分就是怎麼樣去平衡一個排序演算法的性能和效率，那麼我們主要使用的方法是cascade learning，即將一次排序拆分成多個遞進階段(stage)，每個階段選用逐漸複雜的特徵去過濾一次商品集合。同時我們使用learning to rank設定，將排序問題轉化為一個二分類問題，預估每個商品的點擊率。

我們通過極大似然估計去擬合樣本，使用負的log似然來表示損失函數，那麼基礎的損失函數可以表示為關注的是排序的準確性：

其中左邊項表示似然函數，影響模型的準確度；右邊項表示正則項，一方面是防止過擬合，另一方面能預防特徵相關導致的ill-condition問題。由於在實際的搜索排序中，我們除了效果，性能也是不得不關注的部分，因此我們需要將系統的性能性能消耗也加到目標中。我們可以求CPU的總消耗等於每個stage下的性能消耗之和：。其中表示每個stage上需要計算的商品量的期望，表示商品x能進入第j個stage的概率，表示在第j個stage上的feature進行一次計算的總耗時。那麼我們得到一個新的loss，除了考慮排序的效果，兼顧了模型的計算量：

通過調整，我們能調節系統的性能與效率。越大，系統負載越低，但排序結果也越差；越小，排序結果越好，但系統開銷越大。用戶體驗保障（Multiple Factors of User Experience）

如果直接使用上述模型，確實可以直接降低引擎的負載，但是仍然存在2點用戶體驗上的問題：1是對於某些query（特別是hot query），可能計算latency仍然會非常高；2是某些query（一般是長尾query）下，返回給用戶的結果特別少。那麼為了解決這2個問題，我們進一步的增加了2個約束：單query下的latency不能超過100（只是舉例，不一定是100）ms；返回給用戶的結果數不能小於200。那麼很自然的，我們會想到使用類似SVM的loss形式：

上述公式可以比較直觀的理解為當query下的latency小於100ms(N的值)的時候，loss為0；大於100ms時，loss為（latency-100）的線性倍數；返回結果數類似。然而該函數是非凸、不可導的，並不利於問題的求解。因此為了求解的方便，我們使用了一個凸近似函數modified logistic loss去逼近SVM loss，可以證明，該loss和hinge loss是幾乎一致的，當我們取一個較大的的時候：

綜上，我們考慮了用戶的2種體驗之後，最終的目標函數可以寫成下面形式：

其中表示期望返回給用戶的最少結果數（例如200），表示希望的最大latency（例如100ms）。通過最小化，我們既能在有限的計算資源下得到更好的排序結果，又能兼顧用戶的搜索體驗。商品場景下的多目標（Importance Factors of E-commerce Search）

電商搜索與網頁搜索或者廣告有較大區別：我們關注的不僅是點擊 ，成交量、成交額等指標同樣重要。然而如果我們將所有正樣本(點擊和成交)一樣處理，由於點擊樣本量遠大於成交樣本，那麼我們更像在學習一個CTR任務；這在我們想得到更高的成交額或GMV時是不合理的。因此我們為不同類型、不同價格的正樣本設置了不同的權重。更具體的，我們會區分樣本商品的log、點擊和成交，於是在表示準確的似然項上，做了如下修正：

在上式中，越大，成交樣本的權重更高；越大，價格因素的影響越大。權重的作用主要會體現在優化過程的梯度求解上。離線與在線驗證為了驗證演算法的有效性，我們隨機採樣了線上一天的日誌做交叉驗證，數據取自2016年10月底。我們主要考察的指標有2點：測試集上的AUC以及性能總消耗。對比的演算法有1，使用全部特徵做一次排序；2，使用簡單特徵做一次排序；3，線上使用的2-stage方法；4，CLOES演算法，取；5，CLOES演算法，取。

實驗結果如下表。從表中我可以看到使用全部特徵的準確率無疑是最高的，然後計算消耗也是最高的；線上使用的2-stage方法能顯著的降低計算效率的問題，只有方法1的30%，但是AUC也降低到0.76。我們主要對比的是現在線上使用的方法3—2-stage approach，使用了CLOES，在幾乎相同的計算消耗下，AUC能從0.76提升到0.80；在幾乎相同的AUC下，計算消耗能從30%進一步下降到18%。

在離線驗證了演算法效果后，我們在雙11前夕對演算法進行了上線，以期望降低引擎的計算壓力。上線期間的引擎CPU使用率以及平均搜索latency變化如下圖：可以看到CPU使用率從32%下降到18%；而平均的搜索latency從33ms下降到24ms，圖中有2條曲線分別表示引擎的2個集群。

需要注意的是，在引擎壓力大量下降的情況下，線上的排序指標，包括CTR和GMV是略上升的。

受益於CLOES，在雙11當天，引擎的負載在最高峰也沒有超過70%，CPU的使用率降低了約45%，搜索的平均延遲下降了約30%，同時CLOES本身帶來的GMV提升了近1%。考慮到其他因為性能改善而能上線的特徵（包括實時特徵和RNN特徵等），排序的CTR提升有10%-20%，同時成交量、GMV等指標也有大幅提升（指標對比基於標準A/B Test）。

其他的實驗結果以及演算法細節請見原文。

總結

搜索對於電商來說是最大的流量入口，搜索排序的質量對用戶的體驗、對商家的收入、對平台的效率都會起到至關重要的作用。未來搜索會繼續以用戶的搜索體驗為主要目標，為用提供能更優質、更能滿足用戶個性需求的排序結果。

從技術上，多種機器學習技術都會與搜索排序相關，例如：考慮到用戶的長期體驗，我們需要強化學習技術；考慮數據的分佈不一致等問題，需要counterfactual learning技術；考慮更好的個性化體驗，需要representation learning的相關技術；考慮更具交互性的搜索，我們需要自然語言處理，知識圖譜等方面技術……淘寶搜索會持續的優化用戶的購物體驗，同時希望貢獻更多優秀的演算法、解決方面給工業應用及學術研究。

論文下載

— 完 —

活動預告

加入社群

量子位AI社群7群開始招募啦，歡迎對AI感興趣的同學，加小助手微信qbitbot2入群；

此外，量子位專業細分群(自動駕駛、CV、NLP、機器學習等)正在招募，面向正在從事相關領域的工程師及研究人員。

誠摯招聘

量子位正在招募編輯/記者，工作地點在北京中關村。期待有才氣、有熱情的同學加入我們！相關細節，)對話界面，回復「招聘」兩個字。

量子位 QbitAI

վ'ᴗ' ի 追蹤AI技術和產品新動態