阿里提出電商搜索全局排序方法,淘寶無線主搜GMV提升5%
作者: AI科技園
2019-10-23 10:09:15
[ 聞蜂導讀 ] AI 前線導讀:AI 前線本周帶來第 35 篇論文解讀,本期要解讀的論文來自阿里巴巴,主題是:電商搜索全局排序方法。

一個好的排序算法可以為電商帶來銷量的巨大提升,如果你也是這一領域的開發者,希望阿里巴巴的這篇論文解讀對你能有所啟發。

1. 前言

搜索排序的傳統方法是通過各種方法對商品進行打分,最后按照每個商品的分數進行排序。這樣傳統的搜索排序方法就無 法考慮到展示出來的商品之間相互的影響。類似地,傳統的針對單個商品估計 ctr、cvr 的方法也都基于這樣一個假設:商品 的 ctr、cvr不會受到同時展示出來的其他商品 (我們稱為展示 context) 的影響。而實際上一個商品的展示 context 可以影響到 用戶的點擊或者購買決策:假如一個商品周邊的商品都和它比較類似,但是價格卻比它便宜,那么用戶買它的概率不會 高;反之如果周邊的商品都比它貴,那么用戶買它的概率就會大增。

如果打破傳統排序模型展示 context 沒有影響的假設,該如何進行排序呢?為此,我們首次提出了一種考慮商品間相互影響的全局排序方法。我們將電商排序描述成一個全局優化問題,優化的目標是反應用戶滿意度的商品成交額:GMV(Gross Merchandise Volume)。準確地說,全局排序的優化目標是最大化 GMV 的數學期望。計算 GMV 的數學期望需要知道商品 的成交概率,而商品的成交概率是彼此相互影響的,因此我們又提出了考慮商品間相互影響的成交概率估計模型。

首先, 我們提出了一種全局特征擴展的思路,在估計一個商品的成交概率時,將其他商品的影響以全局特征的形式加入到概率估 計模型中,從而在估計時考慮到了其他商品的影響。然后,我們進一步提出了通過 RNN 模型來精確考慮商品的排序順序對 商品成交概率的影響。通過使用 RNN 模型,我們將電商排序變成了一個序列生成的問題,并通過 beam search 算法來尋找 一個較好的排序。我們在淘寶無線主搜索平臺上進行了大量的實驗,相對于當時的淘寶無線主搜算法,取得了GMV 提升 5% 的效果。

2. 全局排序方法

全局排序階段的輸入是要排序的 N 個商品,輸出則是 N 商品的排序結果。

我們用 S = (1, … , N) 表示基礎排序輸出的 top?N 商品序列;O 表示 S 的全排列集合,o = (o1, … , oN ) ∈ O 表示 S 的一個排列;另外,用 di 表示商品 i 在排序 o 中的位置,即 odi = i;c(o, i) 表示商品 i 在排序 o 中的展示 contex 全局排序 t,具體定義后面會分情況討論;

v(i) 表示商品 i 的價值。

我們將目標定義為本次搜索產生的 GMV,于是在給定 c(o, i) 的情況下,就有:

阿里提出電商搜索全局排序方法,淘寶無線主搜GMV提升5%

全局排序的最終目標就是找到一個期望收益最大的排序:

阿里提出電商搜索全局排序方法,淘寶無線主搜GMV提升5%

尋找這個最優排序需要解決兩個問題:

  • 問題 1. p(i|c(o, i)) 這個概率如何去準確地估計;
  • 問題 2. 尋找 o∗是個組合優化的問題,暴力搜索的時間復雜度是 N! 的,需要找到合理高效的近似算法。

問題 1 是提高效果的關鍵,估計得越準,后面組合優化的效果越明顯,反之則會導致第二步的組合優化沒有意義。從理論上講,c(o, i) = (o1, … , oN ) 是 i 的完整的展示 context,但是如果完整地考慮展示 context,問題 2 的組合優化復雜

度很難降低下來。為了能更高效求解問題 2,需要對 c(o, i) 進行適當地簡化。根據對 c(o, i) 的簡化程度,我們把全局排序模型分成了兩類,分別在下面介紹。

2.1 全局特征擴展

電商搜索全局排序方法

第一類模型只利用展示 context 的商品集合信息,而不去深究真實的展示 context 的順序,即 c(o, i) = S ? {i}。直觀上理

解,第一類模型假設用戶在判斷是否購買商品 i 的時候,只記得他看過所有的商品集合 S,而不在意 S 中商品的出現順序。

這種情況相當于用戶知道自己的挑選集合,從中比較和挑選出最想購買的商品。我們將商品 i 本身的特征成為局部特征 fi,l。這時可以把商品 i 的局部特征 fi,l 與其他候選商品的局部特征進行比較,得到這個商品的特征與候選集合其他商品比較的結果,并且把這些比較的結果作為包含全局信息的特征加入到 p(i|c(o, i)) 的預測中。

以價格特征為例,我們會按照價格緯度對 S 排序,將商品 i 的價格位次均勻地歸一化成 [0, 1] 之間的一個值(最貴的價格變成變成 1,最便宜的價格變成 0),這樣 i 的價格特征就擴展出了i 的價格全局特征。

通過上述的方式可以對 fi,l 的每一維按照其位次擴展,得到相應的全局特征 fi,g,最終我們將局部和全局特征拼接起來作為考慮了展示 context 的商品 i 的特征 fi = (fi,l, fi,g)。這時展示 context 通過特征擴展而加入到模型中來,幫助模型預測成交概率 p(i|c(o, i))。

在第一類模型的假設下,問題 2 的組合優化就變得很簡單了。商品集合是靜態的,因此各個商品的成交概率能分別獨立計算出來。

但是 DNN 計算出的 p(i|c(o, i)) 沒有考慮到商品 i 的排序位次,應該根據根據 position bias 對 p(i|c(o, i)) 做一個修正,即 p(i|c(o, i))bias(di)。對于求解問題 2 來說,我們不需要具體知道 bias(di) 的值,只需要知道 bias 隨著位置從前往后依次降低就可以了,因為這時只要按照 v(i)p(i|c(o, i)) 從高到低對商品進行排序,就一定能得到收益最大的排序。

2.2 排序序列生成

第二類模型不僅僅考慮展示 context 的商品集合信息,還精確地考慮到排在 i 之前的商品的順序。與第一類模型類似,展示 context 的商品集合信息還是通過擴展全局特征的方式加入到了每個商品的特征中,即 fi = (fi,l, fi,g)。但是與第一類模型不同,計算 p(i|c(o, i)) 時,第二類模型還考慮了排在 i 前面的真實順序,即 p(i|c(o, i)) = p(i|o1, o2, . . . , odi−1),這樣問題 1 變成了一個序列概率估計的問題,最直觀的方法就是用 RNN 來計算 p(i|c(o, i))。

與第一類模型不同的是,由于我們考慮了排在 i 之前的商品的順序,前面商品的排序變化會影響商品 i 的成交概率。這時就不能分別獨立計算每個商品的收益了,因為商品 i 的收益要受到排在它前面的商品的影響;而在最終排序確定之前,無法知道商品 i 之前的排序是什么,而且我們的目標就是去確定這樣一個最優的排序。同時,正是因為只考慮了排在 i 之前的商品順序,使得我們可以從前往后一步一步地排序,每一步選擇排在當前位置的商品。

為了便于理解,可以先看一種簡單的情況:分位排序。

所謂分位排序是指在排序時先將收益最大的一個商品排到第一位,然后條件在第一個商品之上,重新計算剩余商品的收益,并選出收益最大的商品排到第二位,依次類推。很明顯分位排序是一種貪婪的算法。beam search 算法可以理解為貪婪算法的擴展,beam search 在每一步搜索的時候會保留收益最大的 k 個序列,一直到最后一步,再返回最好的一個序列。

原始的 RNN 模型解決不好長距離依賴的問題:當我們計算第 20 個位置的商品成交概率時,排在頭 4 位的商品幾乎就沒有任何影響了。而排在前面的商品由于是用戶最先看到的,一般會有較深的印象,對后面商品的影響不應該被忽略。為了使模型有能力考慮到長距離和對排序位置的依賴,我們設計了一種新的 attention 機制加入到 RNN 的網絡中。

通過這種引入 attention 并且加入位置 embedding 的方式,模型可以根據數據自動學習不同位置 attention 該如何調節以得到更好的預測結果。直觀來看,模型的結構圖如下:

阿里提出電商搜索全局排序方法,淘寶無線主搜GMV提升5%

3. 實驗效果

3.1 成交概率估計

阿里提出電商搜索全局排序方法,淘寶無線主搜GMV提升5%

其中 DNN 是只使用 fi,l 作為特征的 baseline。reDNN 是使用全局特征 fi = (fi,l, fi,g) 的 DNN 全局排序模型,miRNN 是 RNN 全局排序模型,miRNN+attention 是增加了我們的 attention 機制的 RNN 模型。

3.2 淘寶無線主搜線上 A/B 測試

使用 miRNN 和 miRNN + attention 模型做排序,算法的時間分別是Θ(kN 2) 和Θ(kN 3),其中 N 是被排序的商品數,k 是 beam search 算法的 beam size 參數。對于淘寶搜索這樣的大規模的搜索平臺來說,這樣的復雜度顯然是太高了。

不過我們可以在 baseline 排序的基礎上,只對排在最前面的 N 個商品進行排序,只要 N 取得不大,計算量就是可以承擔的。同時,因為排在前面的商品對效果的影響最大,對這些商品重新排序的收益也比較大。

我們對比了不同 N 和 k 下,本文提出的各種全局排序方法的 GMV 增長(反應模型效果),搜索引擎 latency(反應計算負擔)的增長曲線:

阿里提出電商搜索全局排序方法,淘寶無線主搜GMV提升5%
阿里提出電商搜索全局排序方法,淘寶無線主搜GMV提升5%
阿里提出電商搜索全局排序方法,淘寶無線主搜GMV提升5%
阿里提出電商搜索全局排序方法,淘寶無線主搜GMV提升5%

最終效果總結:GMV、搜索引擎 Latency 想對于 baseline DNN 的增長:

阿里提出電商搜索全局排序方法,淘寶無線主搜GMV提升5%

結論

我們首次提出了考慮商品間相互影響的電商全局排序方法,并在淘寶主搜索上取得了明顯的效果。目前最大的問題就是 RNN 的方法效果雖然更好一些,但是帶來的計算負擔太大,如何減少計算量將是重要的研究方向。

更多關注微信公眾號:jiuwenwang

  • 驗證碼: 看不清?點擊更換 看不清? 點擊更換
  • 意見反饋
    意見反饋
    返回頂部
    黑龙江快乐十分出号统计