一、前言
本文是作者在1688進行新人紅包發放的技術方案總結，基於該技術方案的論文《Spending Money Wisely: Online Electronic Coupon Allocation based on Real-Time User Intent Detection》已經被CIKM2020接收，歡迎交流指正！
關於作者
李良偉：阿里巴巴算法工程師，郵箱 [email protected]
孫劉誠: 阿里巴巴高級算法工程師，郵箱 [email protected]
二、背景介紹
用戶權益（包括現金紅包、優惠券、店鋪券、元寶等，圖-1）是電商平臺常用的用戶運營手段，能夠幫助平臺促活促轉化。 圍繞著權益的技術優化也層出不窮[1,2,3,4,5]。
圖-1: 1688新人紅包
紅包發放作為一種營銷手段，其ROI是我們非常關心的一個指標，因為它直接反映了在有限的預算內紅包為整個平臺促活促成交的能力。優化紅包發放的ROI要求我們把紅包發到最合適的用戶手上。而判斷哪些用戶適合領到紅包需要我們在真正發紅包之前判斷當前用戶的意圖。舉例來講，一個購買意圖非常明確、無論是否有紅包都會下單的用戶顯然不適合領到紅包；相反，紅包對一個猶豫不決、貨比三家的用戶很有可能起到“臨門一腳”的作用。
隨著1688業務的快速發展，每天都會有大量的平臺新用戶湧入，其中有很多用戶在整個阿里經濟體的數據都十分稀疏，基於常規手段，我們很難對這種“陌生”的用戶進行精準刻畫。然而，只要一個用戶進入了APP，或多或少都會和平臺產生相互作用（滑動，點擊等），這種在端上實時產生的數據能夠幫助我們對用戶尤其是新用戶的實時意圖進行精準捕捉，進而完成紅包發放的決策。
本文將介紹我們基於端智能的用戶意圖識別和智能權益發放方案。
三、技術方案
從數學的角度，權益發放是一個帶約束的優化問題。優化目標是關心的業務指標（GMV，買家數，轉化率等），約束一般是預算約束，有時也會有其他約束比如發放疲勞度約束、單個用戶領取紅包金額約束等。
按照之前提到的先識別用戶意圖再進行權益發放這一思路，我們提出了一個two-stage的求解方案。在第一階段，我們基於端智能技術[6]，根據用戶實時行為數據，通過瞬時意圖識別網絡(Instantaneous Intent Detection Network, IIDN) 識別出用戶當前意圖；在第二階段，我們將優化問題建模成一個多選項揹包問題(Multiple-Choice Knapsack Problem, MCKP),並運用[7]提到的primal-dual框架求解。在這裡，我們強調我們關於IIDN的兩個創新點：
1.IIDN最主要檢測的用戶意圖是下單意圖，但是實踐發現在新人當中，用戶下單的比例是比較小的，這樣我們在進行下單意圖識別的時候會面臨一個類別不均衡的問題(下單:不下單 = 1:10甚至更低)，這樣的類別偏差會降低常見的分類器的分類效果[8]。為了解決這一問題，受到ESMM[11]和seq2seq[10]啟發，我們引入了一個輔助任務：停留意圖識別。我們隨後會從理論上驗證這一做法
2.我們採用encoder-decoder的結構，靈活地處理序列化的輸入和輸出
第一階段：瞬時意圖識別
圖-2: IIDN結構
圖-2是IIDN的整體結構,它由Embedding Layer, LSTM layer, Attention Layer, Encoder和Decoder五部分組成。接下來分別介紹。
Embedding Layer
模型的輸入主要是實時用戶特徵和紅包特徵，用戶特徵包括實時特徵（端上收集到的：點擊、加購等）、歷史特徵（用戶核身、年齡等），紅包特徵現在只加入了面額。這些特徵是高度異質的，需要進行一步處理把它們映射到相同的向量空間中。我們採用[9]提到的嵌套技術，把原始的異質特徵映射為長度固定的向量，並把該向量作為後續結構的輸入。
LSTM Layer
我們紅包發放的業務邏輯是：用戶在詳情頁產生瀏覽行為並返回landing page的時候觸發決策模型，判斷給該用戶發放紅包的面額（0元代表不發放）。由於用戶通常會產生一系列的詳情頁瀏覽行為，因此我們收集到的數據也是高度序列化的。為了更好地描述序列化數據當中的時間依賴關係，我們在特徵抽取環節採用了Long Short Term Memory (LSTM) 來捕捉這種序列化信息。
Attention Layer
對於LSTM產出的序列化的feature map，我們使用注意力機制抽取當中的局部和全局依賴關係。我們將LSTM每層的輸出都通過Attention計算權重並參與最終的結果計算。這樣的好處是模型不僅關注LSTM最終層輸出，還會關注逐層的輸出結果，從而增加模型對於輸入信息的感知能力。
Encoder
由於用戶實時特徵的序列長度不固定，而紅包特徵和用戶歷史特徵是靜態的固定特徵，我們需要一種機制來進行有效的特徵融合。受到Natural Language Generation (NLG) 當中語句生成的啟發，我們採用一種seq2seq的結構：包括encoder和decoder，我們將在下一小節介紹decoder。這裡encoder將之前產生的所有feature map作為輸入，通過全連接層產生一個固定長度的向量，這個向量囊括了進行用戶意圖識別的一切信息，並作為之後decoder進行意圖識別的依據。
Decoder
Decoder被用來輸出最終的意圖識別結果。在最開始，我們的模型只輸出用戶下單的概率，但是隨著業務的深入，我們發現類別不均衡這一問題給結果預測造成了不小的干擾。在提高預測精度的實踐當中，我們發現了一個有趣的現象：如果在進行下單率預估的時候在特徵中加入用戶在這次瀏覽之後是否離開這一信息，預測精度會有很大的提升。這引發了我們的思考：用戶離開和用戶下單之間存在什麼樣的關係。隨後我們又做了一個實驗：進行用戶離開意圖識別，並在特徵中加入了用戶兩小時內是否下單這一特徵。實驗結果表明加入是否下單這一特徵並不能給離開率預估的任務帶來增益。這樣的實驗結果其實是符合邏輯的：用戶能夠下單的前提是用戶一定要留在APP內不離開，前者的發生在邏輯上需要依賴後者的發生，因此在進行下單率預估的時候加入是否離開能夠為模型提供一定的信息增益；相反，用戶是否離開更多取決於用戶當前的心態以及APP能否很好地承接他，用戶是否下單並不能影響用戶是否離開。我們可以認為：
由上式可以很自然地推導出下式：
可以看到，在進行下單率預估的時候（P的計算），用戶停留意圖識別（S的計算，或者說離開意圖，二者等價）將可以用來作為輔助任務提升預測效果。我們的實驗也驗證了這點。
儘管在我們這一任務當中，我們只需要預測停留意圖和下單意圖，但是在之後擴展的場景中，更多意圖也可以被識別：比如用戶去往搜索的意圖，用戶去往新人專區的意圖等。所有意圖其實都像下單意圖和停留意圖一樣存在一個邏輯上的先後關係（至少所有意圖的產生都依賴於用戶不離開），這樣的關係使得我們想到了機器翻譯當中語句生成：後一個單詞的生成依賴於前一個單詞的預測，這啟發了我們在encoder-decoder的基礎上採用seq2seq的思想：decoder會先生成S，並在此之上生成P。這樣做有兩個好處：
1.在一定程度上緩解了我們一開始提到類別不均衡問題：儘管不是所有用戶都下單，但是所有用戶一定會離開APP，離開意圖識別並不存在類別不均衡的問題
2.我們這一套意圖識別框架可以擴展到無限多的意圖識別當中，只要提供先驗的邏輯先後關係
我們使用普通的RNN完成每一個意圖的識別。
loss設計
全局的loss是由停留意圖識別和下單意圖識別兩個任務的loss相加得到：
其中CE表示交叉熵：
第二階段：求解MCKP
根據第一階段得到的實時意圖$P$和$S$，我們在這一階段完成紅包的最終發放。我們將這一問題建模成一個多選項揹包問題，我們作以下定義：
1.j用來索引紅包，表示第j個紅包，i用來索引用戶，表示第i個用戶
2.c_j表示第$j$個紅包的面額
3.x_{ij} = 1當且僅當第i個用戶被髮到了j紅包
4.\gamma 表示用戶停留興趣閾值，我們只給那些停留意圖足夠低的用戶發紅包，停留意圖如果不夠低我們認為他還會繼續瀏覽，因此這次先不發放紅包
5.P_{ij}、S_{ij}分別表示第$i$個用戶領取到第$j$個紅包以後的下單率和停留率
6.B表示全局預算約束
運用以上的定義，紅包發放問題可以被寫作：對於任意的用戶，滿足S_{ij} <= gamma，我們求解以下最優化問題：
為了求解以上問題，我們採用[7]提到的primal-dual框架。定義alpha和beta_j分別是相關的對偶變量，據此框架我們可以在線求解以上問題。具體來講，x_{ij}可以根據以下公式求得：
通過上式求得的x_{ij}和j，我們就得到了最終的分配方案。
四、系統部署
目前在集團做端智能首推jarvis平臺，在這裡給相關同學點贊，在最開始的時候沒少麻煩jarvis同學解決問題。運用jarvis，我們可以收集端上實時數據並將深度模型部署到端上。我們主要是將IIDN部署到端上，MCKP決策模型由於需要考慮全局最優，所以放在了服務端。
圖-3: 系統大圖
圖-3是我們整體的系統架構，每一個用戶在詳情頁回退到landing page的時候會觸發決策模型，IIDN首先根據端上採集到的行為數據識別出用戶的下單和停留意圖，隨後該意圖會被推送到服務端參與最終的紅包決策。我們這套系統在日常線上持續生效，同時還參與了0331商人節，助力買家數的提升。
五、實驗
實驗設置
我們從1688客戶端收集數據，用到的特徵如下表：
實驗分為兩部分：離線實驗和在線實驗。離線實驗主要驗證IIDN對於意圖的識別效果，驗證指標是AUC和logloss；在線實驗主要驗證我們二段式建模對於紅包發放的效果，主要的驗證指標是增量買家成本 (increment cost, ic)，它被用來衡量每帶來一個增量買家需要消耗的成本，計算公式如下：
離線實驗
在離線實驗環節，我們分別使用以下方法進行下單意圖識別，並進行比較：
1.Logistic Regression (LR)
2.Gradient Boosting Decision Tree (GBDT)
3.DNN + RNN [12]
4.IIDN-single-LSTM （單層LSTM）
5.IIDN-non-attention （無Attention機制，使用簡單的全連接）
6.IIDN-non-auxiliary-task (沒有輔助任務的IIDN)
7.IIDN離線結果如下表：
可以看到IIDN達到最高的AUC和最低的Logloss，這證明了IIDN的合理性。
在線實驗
我們主要和另外三個發放方案做比較：
1.不發：該桶所有用戶均不發紅包
2.全發：該桶所有用戶均發紅包
3.uplift：我們採用廣告營銷當中常用的uplift方案，對每一個用戶發放使他轉化率提升最大的面額，同時該面額帶來的轉化率提升需要大於一定的閾值，否則不發放紅包
在線效果如下表：
可以看到儘管全發桶帶來的轉化率提升最明顯，但是它也帶來了最大的增量買家成本。我們提出的方案不僅相對自然轉化率提升了25.7%，同時也比全發桶的增量買家成本減少了44.3%，這證明了我們方案的優越性。
模型分析
學習曲線
圖-4: 學習曲線
圖-4展示了不同方法的學習曲線，可以看到LSTM, Attention以及停留意圖識別任務均可以起到加速模型訓練的效果。
單調性分析
正常來講，紅包面額越大，對於用戶的刺激作用也越大，用戶下單率曲線應該是一條關於紅包面額單調遞增的曲線，我們實驗得到的曲線如下圖：
圖-5: 單調性曲線
可以看到所有模型基本呈現單調性，其中IIDN更加符合真實情況。
六、參考文獻
1. 競爭網絡下的智能紅包發放(ATA)
2. 花錢，我們是認真的 -- 基於用戶權益敏感與大規模分組揹包的紅包發放算法(ATA)
3. 2018雙11：用戶來而未購？用戶購買意圖識別與驚喜紅包新玩法(ATA)
4. 社交營銷（1）：雙11蓋樓，紅包有多少，樓有多高！| 基於社交裂變的C2C紅包智能投放(ATA)
5. 商家增長引擎系列二：全生命週期商家建模與直通車智能紅包(ATA)
6. Jarvis端上算法平臺介紹(ATA)
7. Agrawal, Shipra, Zizhuo Wang, and Yinyu Ye. "A dynamic near-optimal algorithm for online linear programming." Operations Research 62.4 (2014): 876-890.
8. Chen, Ken, Bao-Liang Lu, and James T. Kwok. "Efficient classification of multi-label and imbalanced data using min-max modular classifiers." The 2006 IEEE International Joint Conference on Neural Network Proceedings. IEEE, 2006.
9. Guo, Long, et al. "Buying or browsing?: predicting real-time purchasing intent using attention-based deep network with multiple behavior." Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019.
10. Sutskever, Ilya, Oriol Vinyals, and Quoc V. Le. "Sequence to sequence learning with neural networks." Advances in neural information processing systems. 2014.
11. Ma, Xiao, et al. "Entire space multi-task model: An effective approach for estimating post-click conversion rate." The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval. 2018.
12. Wei, Ermo, Drew Wicke, and Sean Luke. "Hierarchical approaches for reinforcement learning in parameterized action space." 2018 AAAI Spring Symposium Series. 2018.
延伸閱讀
延伸閱讀《阿里巴巴B2B電商算法實戰》點我購買
推薦語：本書是阿里巴巴CBU技術部（1688.com）深耕B2B電商15年的經驗總結。阿里巴巴B2B在戰略形態上經歷了信息平臺、交易平臺和營銷平臺的升級迭代，本書聚焦營銷平臺商業形態背後的算法和技術能力，試圖從技術和商業互為驅動的視角闡述技術如何賦能業務，並結合阿里巴巴集團在基礎設域和算法創新上的沉澱，打造出智能B2B商業操作系統。