636
KDD論文解讀 | 想要雙11搶單快？靠這個技術提速9MS
6月29日，阿裏巴巴在杭州召開2017天貓雙十一發布會，宣布啟動：雙11超級IP計劃。今年晚會將由北京衛視、浙江衛視、深圳衛視三台同時直播。淘寶直播、優酷等在內的多家平台同步跟上，讓澳門、香港、新加坡等地也能同步收看天貓雙11晚會，相信今年的雙11一定會成為舉世矚目的全球狂歡節。
同時，為2016雙11提供技術支持的團隊也首次曝光了其研究成果，通過CLOSE排序算法，2016雙11CPU的使用率降低了約45%，搜索的平均延遲下降了約30%（平均的搜索latency從33ms下降到24ms），同時CLOES本身帶來的GMV提升了近1%。相關論文《Cascade Ranking for Operational E-commerce Search》也被國際數據挖掘頂會KDD 2017收錄。
該論文設計並實現了一種級聯式電商搜索方式：它的主要思想是將一次排序分成遞進的多個階段，各階段使用逐漸複雜的特征去得到逐漸準確的結果。在靠前階段使用簡單特征過濾顯然不合要求的結果，在靠後階段使用複雜特征辨別難以區分的結果。除此以外，算法結合電商場景的特殊性，嚴格限製了引擎的響應時間以及返回商品的數量，以保證用戶的搜索體驗。
離線實驗和在線實驗均驗證了算法的正確性以及有效性，對比傳統的方法能提升準確率的同時大幅提升了計算性能；在去年雙11，在新增了大量準確又耗時的計算特征(包括強化學習和深度學習特征)的情況下，算法極大的保證了引擎的效率，使排序對引擎的壓力下降40%，同時使排序效果有較大提升。
KDD 2017將於8月13日召開
針對這篇論文，阿裏妹公布獨家技術解讀：
淘寶的搜索係統無疑是全球最大的電商搜索係統。“最大”這裏包括商品量、用戶量，包括引導的成交額、點擊成交量，還包括引擎的訪問次數、訪問QPS…這樣一個搜索引擎，所需要麵對的訪問壓力也是巨大的，尤其在“雙十一”等大促場景，壓力更是平時的數倍。
另外一般搜索引擎的目標主要是引導點擊，而在電商中，排序的結果更希望引導的是成交量和成交額。因此我們的搜索係統、排序方案需要考慮多種實際問題。首先是在有限計算資源情況下，如何拿到更好的排序結果；其次是怎樣保證用戶的搜索體驗，包括結果返回時間、返回商品量等；最後是怎麼保證電商場景下的多目標，包括點擊、成交量和成交額。
學術界和工業界都有大量learningto rank方麵的研究，均期望能通過機器學習，為用戶給出更優的排序結果。然而絕大部分相關工作都集中在如何提升排序的質量，卻並不關係排序的效率，而太低效的排序方案在實際的工業在線應用中，往往是不可接受的。
淘寶搜索和其他類似應用主要采取的解決方案是使用一種“兩輪排序方案”：在第一輪使用非常簡單的特征去得到一個小的候選集；第二輪在小的集合上做複雜的排序。可是這種啟發式的方案並不能保證性能與效果的取舍是最優的。基於以上考慮，我們需要一種全新的、工業可用的、能更合理平衡效率與性能的排序方案。
論文受圖像中快速目標檢測算法的啟發，發現並不是引擎中的每個商品都需要全部特征參與計算、排序——一些基本特征能幫助過濾掉大多數商品；逐漸複雜的特征過濾逐漸難以區分好壞的商品；全部特征排序剩餘商品。基於這樣的思想，論文提出了一種多輪級聯排序方法Cascade model in a Large-scale OperationalEcommerce Search application（CLOES）。
CLOES主要采用了一種基於概率的cascade learning方法，將排序分為多輪計算；將排序效果和CPU的計算量作為優化目標，一起建立數學模型，同時優化。除了考慮性能與效率，算法還考慮了用戶的搜索體驗，保證用戶在輸入任何一個query後都能在限製時間內得到足夠的返回結果。最後CLOES還考慮了電商場景的特殊性，保障了多目標的平衡與可調整。
平衡性能與效率的排序
（Query-Dependent Trade Off Between Effectiveness and Efficiency）
論文最重要的部分就是怎麼樣去平衡一個排序算法的性能和效率，那麼我們主要使用的方法是cascade learning，即將一次排序拆分成多個遞進階段(stage)，每個階段選用逐漸複雜的特征去過濾一次商品集合。同時我們使用learning to rank設定，將排序問題轉化為一個二分類問題，預估每個商品的點擊率。
如圖所示，我們記一個商品x(表示為一個k維向量)在Query q下，能通過第j個stage的概率為，其中表示sigmoid函數。那麼一個商品最終能被點擊的概率為能通過所有stage的概率之積:
我們通過極大似然估計去擬合樣本，使用負的log似然來表示損失函數，那麼基礎的損失函數可以表示為L_1。L_1關注的是排序的準確性：
如果直接使用上述模型，確實可以直接降低引擎的負載，但是仍然存在2點用戶體驗上的問題：一是對於某些query（特別是hot query），可能計算latency仍然會非常高；二是某些query（一般是長尾query）下，返回給用戶的結果特別少。那麼為了解決這2個問題，我們進一步的增加了2個約束：單query下的latency不能超過100（隻是舉例，不一定是100）ms；返回給用戶的結果數不能小於200。那麼很自然的，我們會想到使用類似SVM的loss形式：
在離線驗證了算法效果後，我們在雙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）。
搜索對於電商來說是最大的流量入口，搜索排序的質量對用戶的體驗、對商家的收入、對平台的效率都會起到至關重要的作用。未來淘寶搜索會繼續以用戶的搜索體驗為主要目標，為用提供能更優質、更能滿足用戶個性需求的排序結果。
本文出自阿裏技術公眾號，原文鏈接
最後更新：2017-07-19 11:32:30