本文來自AI新媒體量子位（QbitAI）
這篇論文主要講述，去年雙11期間，淘寶搜尋在有限計算資源情況下，如何拿到更好的排序結果、保證使用者的搜尋體驗、以及點選、成交量和成交額等目标的完成。
實際的結果是，去年雙11當天，淘寶搜尋引擎的負載在最高峰也沒有超過70%，CPU的使用率降低了約45%，搜尋的平均延遲下降了約30%，同時帶來的GMV提升了近1%。
以下是這篇論文的詳細介紹。
《多層級聯學習在大型電商排序系統的應用（Cascade Ranking for Operational E-commerce Search）》
作者：劉士琛，肖非，歐文武，司羅
該論文設計并實作了一種級聯式電商搜尋方式：它的主要思想是将一次排序分成遞進的多個階段，各階段使用逐漸複雜的特征去得到逐漸準确的結果。在靠前階段使用簡單特征過濾顯然不合要求的結果，在靠後階段使用複雜特征辨識難以區分的結果。除此以外，算法結合電商場景的特殊性，嚴格限制了引擎的響應時間以及傳回商品的數量，以保證使用者的搜尋體驗。
離線實驗和線上實驗均驗證了算法的正确性以及有效性，對比傳統的方法能提升準确率的同時大幅提升了計算性能；在去年雙11，在新增了大量準确又耗時的計算特征(包括強化學習和深度學習特征)的情況下，算法極大的保證了引擎的效率，使排序對引擎的壓力下降40%，同時使排序效果有較大提升。
淘寶的搜尋系統無疑是全球最大的電商搜尋系統。“最大”這裡包括商品量、使用者量，包括引導的成交額、點選成交量，還包括引擎的通路次數、通路QPS…這樣一個搜尋引擎，所需要面對的通路壓力也是巨大的，尤其在“雙十一”等大促場景，壓力更是平時的數倍。
另外一般搜尋引擎的目标主要是引導點選，而在電商中，排序的結果更希望引導的是成交量和成交額。
是以我們的搜尋系統、排序方案需要考慮多種實際問題。首先是在有限計算資源情況下，如何拿到更好的排序結果；其次是怎樣保證使用者的搜尋體驗，包括結果傳回時間、傳回商品量等；最後是怎麼保證電商場景下的多目标，包括點選、成交量和成交額。
學術界和工業界都有大量learning to rank方面的研究，均期望能通過機器學習，為使用者給出更優的排序結果。然而絕大部分相關工作都集中在如何提升排序的品質，卻并不關系排序的效率，而太低效的排序方案在實際的工業線上應用中，往往是不可接受的。
淘寶搜尋和其他類似應用主要采取的解決方案是使用一種“兩輪排序方案”：在第一輪使用非常簡單的特征去得到一個小的候選集；第二輪在小的集合上做複雜的排序。可是這種啟發式的方案并不能保證性能與效果的取舍是最優的。基于以上考慮，我們需要一種全新的、工業可用的、能更合理平衡效率與性能的排序方案。
論文受圖像中快速目标檢測算法的啟發，發現并不是引擎中的每個商品都需要全部特征參與計算、排序——一些基本特征能幫助過濾掉大多數商品；逐漸複雜的特征過濾逐漸難以區分好壞的商品；全部特征排序剩餘商品。
基于這樣的思想，論文提出了一種多輪級聯排序方法Cascade model in a Large-scale Operational Ecommerce Search application（CLOES）。
CLOES主要采用了一種基于機率的cascade learning方法，将排序分為多輪計算；将排序效果和CPU的計算量作為優化目标，一起建立數學模型，同時優化。
除了考慮性能與效率，算法還考慮了使用者的搜尋體驗，保證使用者在輸入任何一個query後都能在限制時間内得到足夠的傳回結果。最後CLOES還考慮了電商場景的特殊性，保障了多目标的平衡與可調整。
論文最重要的部分就是怎麼樣去平衡一個排序算法的性能和效率，那麼我們主要使用的方法是cascade learning，即将一次排序拆分成多個遞進階段(stage)，每個階段選用逐漸複雜的特征去過濾一次商品集合。同時我們使用learning to rank設定，将排序問題轉化為一個二分類問題，預估每個商品的點選率。
如圖所示，我們記一個商品x(表示為一個k維向量)在Query q下，能通過第j個stage的機率為
，其中
表示sigmoid函數。那麼一個商品最終能被點選的機率為能通過所有stage的機率之積:
我們通過極大似然估計去拟合樣本，使用負的log似然來表示損失函數，那麼基礎的損失函數可以表示為
。
關注的是排序的準确性：
其中左邊項表示似然函數，影響模型的準确度；右邊項
表示正則項，一方面是防止過拟合，另一方面能預防特征相關導緻的ill-condition問題。
由于在實際的搜尋排序中，我們除了效果，性能也是不得不關注的部分，是以我們需要将系統的性能性能消耗也加到目标中。我們可以求CPU的總消耗等于每個stage下的性能消耗之和：
。其中
表示每個stage上需要計算的商品量的期望，
表示商品x能進入第j個stage的機率，
表示在第j個stage上的feature進行一次計算的總耗時。那麼我們得到一個新的loss
，
除了考慮排序的效果，兼顧了模型的計算量：
通過調整
，我們能調節系統的性能與效率。
越大，系統負載越低，但排序結果也越差；
越小，排序結果越好，但系統開銷越大。
如果直接使用上述模型，确實可以直接降低引擎的負載，但是仍然存在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）。通過最小化
，我們既能在有限的計算資源下得到更好的排序結果，又能兼顧使用者的搜尋體驗。
電商搜尋與網頁搜尋或者廣告有較大差別：我們關注的不僅是點選 ，成交量、成交額等名額同樣重要。然而如果我們将所有正樣本(點選和成交)一樣處理，由于點選樣本量遠大于成交樣本，那麼我們更像在學習一個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的相關技術；考慮更具互動性的搜尋，我們需要自然語言處理，知識圖譜等方面技術……淘寶搜尋會持續的優化使用者的購物體驗，同時希望貢獻更多優秀的算法、解決方面給工業應用及學術研究。
https://arxiv.org/pdf/1706.02093.pdf
— 完 —
原文釋出時間：2017-08-16