商品推薦系統(tǒng)中的效用估計

朱啟杰

摘 要： ??在零售商的角度，通常希望推薦系統(tǒng)的推薦產(chǎn)品能使商家的收益最大化。在以期望收益最大化為目標(biāo)的產(chǎn)品組合優(yōu)化模型中，商品效用是必不可少的參數(shù)。論文主要探究推薦系統(tǒng)中商品效用的估計方法，通過評估由商品效用計算得到的商品被點擊概率，來驗證效用估計的準(zhǔn)確性。通過數(shù)值試驗，將單值排序模型預(yù)估的點擊概率與通過MNL模型估計商品效用計算的點擊概率進(jìn)行對比，結(jié)果證明MNL模型估計的商品效用具備與單值排序模型相當(dāng)?shù)臏?zhǔn)確率。此外，論文進(jìn)一步構(gòu)建了神經(jīng)網(wǎng)絡(luò)模型估計商品效用，并且另外構(gòu)建了一個直接計算商品點擊概率的attention選擇模型作為對比。結(jié)果證明使用神經(jīng)網(wǎng)絡(luò)模型代替MNL來估計商品效用，能夠更進(jìn)一步提升效用預(yù)估的準(zhǔn)確性。

關(guān)鍵詞： ?推薦系統(tǒng)；產(chǎn)品組合優(yōu)化；MNL；神經(jīng)網(wǎng)絡(luò)；效用估計

中圖分類號： ?G 206

文獻(xiàn)標(biāo)志碼： ??A

Utility Estimation in Recommendation System

ZHU Qijie

（Antai College of Economics & Management， Shanghai Jiao Tong University， Shanghai 200030， China）

Abstract： ?From the retailer's perspective， it is usually hoped that the recommended products of the recommendation system can maximize the profit of the assortment. In the assortment optimization model aiming at maximizing expected revenues， product utility is an indispensable parameter. This article mainly explores the estimation method of product utility in the recommendation system， and verifies the accuracy of utility estimation by evaluating the click probability of the product calculated by the product utility. Through numerical experiments， the estimated click probability of the point-wise model is compared with the click probability calculated by the product utility estimated by the MNL model. The result proves that the product utility estimated by the MNL model has a good accuracy. In addition， this paper further builds a neural network model to estimate the utility of goods， and additionally builds an attention choice model that directly calculates the click probability of goods as a comparison. The results prove that using neural network model instead of MNL to estimate the utility of the commodity can further improve the accuracy of the utility prediction.

Key words： ??recommender system; assortment; Multinominal Logit Model; neural network; utility estimation

本文選擇機(jī)票訂單點擊數(shù)據(jù)作為研究數(shù)據(jù)集，首先建立機(jī)器學(xué)習(xí)模型預(yù)測單個產(chǎn)品的用戶點擊概率，選擇被點擊概率最高的商品作為被點擊的商品的預(yù)測；另一方面，本文選擇經(jīng)典的MNL（Multinomial Logit）模型作為選擇模型，該模型使用特征的線性組合來估計商品的效用，根據(jù)該模型估計的商品效用，選擇效用最高的商品作為被點擊的商品的預(yù)測；為了解決一些線性模型存在的缺陷，本文構(gòu)建了一種神經(jīng)網(wǎng)絡(luò)模型，使用其代替MNL模型估計商品效用，后續(xù)步驟不變，依然選擇效用最高的商品作為被點擊的商品的預(yù)測；最后，本文將構(gòu)建一種考慮商品之間交互作用的預(yù)測模型（attention選擇模型），用于與前述模型進(jìn)行比較。本文通過實驗證明，通過估計效用的方式估計商品被點擊的概率能夠取得不錯的準(zhǔn)確率，且使用復(fù)雜模型代替線性模型可以使準(zhǔn)確率得到一定的提升。

1 文獻(xiàn)綜述

近年來，深度學(xué)習(xí)被廣泛運用于推薦系統(tǒng)領(lǐng)域的研究中。基于深度學(xué)習(xí)的算法主要分為兩類：一類是通過算法進(jìn)行特征提取，另一類是通過算法直接計算用戶對產(chǎn)品的點擊概率。第一類算法主要是通過類似于自然語言處理中獲取詞向量的方式獲取產(chǎn)品在空間上的向量表示，如Perozzi等人提出了DeepWalk模型，該模型利用用戶的點擊序列構(gòu)建圖，在圖中隨機(jī)游走獲得產(chǎn)品的點擊序列，再利用Skip-Gram以及Hierarchical Softmax等算法獲取產(chǎn)品的向量表示；Wang等人提出了構(gòu)建帶權(quán)重的圖的方法獲得產(chǎn)品的點擊序列，在訓(xùn)練產(chǎn)品的向量的同時訓(xùn)練其他產(chǎn)品所屬類別特征的向量，該方法能夠在一定程度上解決冷啟動問題。第二類算法將用戶與產(chǎn)品作為輸入，通過計算得到用戶點擊相關(guān)產(chǎn)品的概率，如Rendle等人提出FM模型，該模型除線性部分外，使用了特征之間的交互信息，可以很好地解決部分參數(shù)因數(shù)據(jù)稀疏的原因無法學(xué)習(xí)的問題；Juan等人提出FFM模型，該模型在FM模型的基礎(chǔ)上做了一定的改進(jìn)，每個特征不再只由單個向量表示，在與不同的特征交互時，根據(jù)交互特征的類型使用不同的語義向量，在保持參數(shù)量大致相同的同時，加快了訓(xùn)練速度，提升了訓(xùn)練效率與準(zhǔn)確率；Cheng等人提出了Wide&Deep模型，該模型結(jié)合了傳統(tǒng)的線性模型與神經(jīng)網(wǎng)絡(luò)各自的優(yōu)勢，平衡模型的記憶能力與泛化能力，取得了較好的效果。

另一方面，以往也有大量關(guān)于顧客選擇模型以及對應(yīng)的產(chǎn)品組合問題的研究。Vulcano等學(xué)者通過使用EM算法代替最大似然估計，估計MNL模型的參數(shù)，并通過實驗說明了在收益管理領(lǐng)域使用選擇模型是可行的，并且在實際場景下能夠取得理想的收益；Davis等學(xué)者證明了基于MNL的產(chǎn)品選擇問題，在多種限制條件下，均可轉(zhuǎn)化為線性規(guī)劃問題求解；Gallego等學(xué)者提出了針對嵌套的產(chǎn)品組合問題的一種近似算法，該算法能自提升速度的同時保證結(jié)果的有效性；Feldman等學(xué)者則通過線上對比實驗比較了機(jī)器學(xué)習(xí)的算法以及基于MNL模型的產(chǎn)品組合優(yōu)化算法，后者比前者取得了更高的收益。

2 算法模型

2.1 MNL選擇模型

MNL模型假定顧客與給定的商品產(chǎn)生關(guān)聯(lián)、產(chǎn)生效用，并且顧客最終只會購買效用最高的商品。在MNL模型中，顧客t對商品j的效用如下式所示：

Ujt=Vjt+εt

其中，Vjt為效用估計函數(shù)根據(jù)特征輸出的效用估計值，為一確定值，而εt則為一個服從Gumbel分布的獨立同分布變量。在MNL模型中，為了關(guān)聯(lián)顧客與商品之間的特征，一般使用線性組合的方式以計算效用：

Vjt=∑ K k=1 wk xj，t，k

其中，xj，t，k代表了顧客t與商品j的各種特征，而wk則表示各個特征的權(quán)重。假設(shè)商品總集合為N={1， …， n}，該集合包含了產(chǎn)品組合中所有可選擇的商品，除了這n個商品，再假設(shè)有一編號為0的商品選項，該選項代表顧客沒有點擊購買商品組合任何一個商品。在本文中，我們將不失一般性地假設(shè)對任意顧客t，V0t=0?；谝陨霞僭O(shè)，在MNL模型中，對任意顧客t，將產(chǎn)品組合StN推薦給顧客，顧客點擊產(chǎn)品組合中任意商品j∈St的概率為：

Pjt （St，Vt）= exp（Vjt） 1+∑i∈Stexp（Vit）

根據(jù)上式可以得出，任意商品的點擊購買概率既與商品和用戶本身的屬性特征相關(guān)，同時也與產(chǎn)品組合中的其他商品相關(guān)。

在MNL模型中，各個特征的權(quán)重wk通常使用極大似然估計獲得。假定歷史點擊數(shù)據(jù)D={（St，Xt，zt ）：t=1，2，…，T}，其中Xt={Xjt：j∈St}，Xjt={xj，t，k，k=1，…，K}，zt表示顧客最終點擊商品的編碼，若顧客未點擊任何商品則zt=0。根據(jù)歷史點擊數(shù)據(jù)，通過極大似然估計得到權(quán)重：

W=argmaxw LL（W|D）

其中

LL（W|D）=∑ T t=0 lg exp（Vzt t） 1+∑i∈Stexp（Vit）

W={wk：k=1，…，K}

由于數(shù)據(jù)量較大，本文采用梯度下降的方法求解權(quán)重。

根據(jù)上述算法可知，MNL選擇模型通過線性組合的簡單形式計算商品效用，該模型參數(shù)量少、速度快并且具備可解釋性，但在另一方面，該模型僅考慮了特征對商品效用的一階的線性影響，并未考慮特征的高階影響以及特征之間的交互作用，若使用一些基于深度學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)模型，則可以在一定程度上解決這一類的問題。

2.2 神經(jīng)網(wǎng)絡(luò)選擇模型

在估計商品效用時，一些隱式的特征交互通常會對商品效用產(chǎn)生影響。比如顧客通常會在冬季點擊購買外套，在夏季點擊購買T恤，這是商品種類與時間兩種因素對商品效用的交互影響；若再考慮年齡要素，年輕人通常會更喜歡潮流的服飾，而中老年人則通常偏好于成熟穩(wěn)重的衣物。商品的效用可能還包括商品種類、時間以及消費者年齡三種因素之間的三階交互影響。為了更好地學(xué)習(xí)到高階特征以及特征之間的交互作用，本文將采用神經(jīng)網(wǎng)絡(luò)模型估計商品效用。

本文所采用的模型大致如圖1所示，模型的基本架構(gòu)使用了Guo等人提出的DeepFM模型。模型的輸入主要分為兩種類型的特征：連續(xù)特征以及離散的類別特征。連續(xù)特征的取值具備實際意義，可以進(jìn)行大小比較以及加減運算；而類別特征的取值通常無實際意義，一般的做法是對類別特征采用獨熱編碼（One-Hot Encoding）進(jìn)行預(yù)處理，經(jīng)過獨熱編碼處理的數(shù)據(jù)只有0與1兩種取值。

由于我們希望模型能夠同時學(xué)習(xí)到不同特征之間的低階以及高階的交互，因此模型分為因子分解機(jī)（FM）與深度神經(jīng)網(wǎng)絡(luò)（DNN）兩個部分。這里假定經(jīng)過預(yù)處理的輸入為X={xi：i=1，…，N}。

在FM部分，對于每個輸入xi，模型都會賦予其一個參數(shù)wi以及一個隱向量vi，wi表示xi的一階線性影響，而vi則用于計算特征之間的交互作用。FM部分主要通過不同特征對應(yīng)的隱向量vi之間的內(nèi)積來計算特征之間的二階交互作用，在輸入端數(shù)據(jù)十分稀疏的情況下，這種做法比給每一對輸入特征的交互作用單賦予一個參數(shù)來計算交互作用更為有效以及可靠。這是因為若對每一對輸入特征的交互作用單賦予一個參數(shù)，則只有這一對特征均不為0的情況下，該參數(shù)才能被學(xué)習(xí)；而在使用隱向量的方法時，在對應(yīng)特征以及任意其他特征不為0的情況下，該特征對應(yīng)的隱向量的參數(shù)都可以被學(xué)習(xí)。FM部分的輸出為：

y1=∑ N i=1 wi xi

y2=∑ N-1 i1=1 ∑ N i2=i1+1 〈vi1，vi2〉xi1xi2

其中，y1表示特征的一階線性作用，y2表示特征的二階交互作用。

在DNN部分，將所有不為0的輸入按順序找到每一個輸入所對應(yīng)的隱向量vi，在將隱向量乘對應(yīng)的輸入后，通過向量拼接得到輸入a（0）=［v1，v2，…，vK］。這里a（0）的維度為d×K，其中d表示隱向量的維度，K表示預(yù)處理前特征的總個數(shù)。DNN部分為一個前饋神經(jīng)網(wǎng)絡(luò)，由于神經(jīng)網(wǎng)絡(luò)具備自動學(xué)習(xí)特征交互能力，模型該部分用于學(xué)習(xí)特征之間的高階交互作用，前饋神經(jīng)網(wǎng)絡(luò)的計算方式如下：

a（l+1）=σ（W（l） a（l）+b（l））

其中，a（l）為神經(jīng)網(wǎng)絡(luò)上一層的輸出，W（l）為l層的權(quán)重參數(shù)，b（l）為l層的偏移參數(shù)，a（l+1）為輸出，σ為激活函數(shù)。模型的DNN部分的輸出y3=a（L+1），L為前饋神經(jīng)網(wǎng)絡(luò)的總層數(shù)。

模型計算的效用為V=w0+y1+y2+y3，w0為偏置項。與MNL模型計算一樣，假設(shè)V0t=0，通過Pjt（St，Vt）= exp（Vjt） 1+∑i∈Stexp（Vit） 計算顧客點擊產(chǎn)品組合中任意商品j∈St的概率。沿用MNL模型相同的損失函數(shù)，通過梯度下降的方式估計模型參數(shù)。

2.3 考慮商品交互作用的attention選擇模型

對于商品集合中每個商品點擊概率預(yù)測的問題，目前的最優(yōu)做法是通過神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)對商品特征進(jìn)行編碼，將每一個候選集中的商品通過神經(jīng)網(wǎng)絡(luò)生成一個可以代表該商品所有特征的向量，再使用attention等方法將不同的商品間的交互特征結(jié)合進(jìn)來，最終輸出候選集中每個商品被點擊的概率。

在本次研究中，為了更好地評估通過效用估計的商品點擊概率的準(zhǔn)確性，防止因為使用不同的網(wǎng)絡(luò)結(jié)構(gòu)影響到結(jié)果的準(zhǔn)確性，因此在這個部分使用的神經(jīng)網(wǎng)絡(luò)模型依然為前述的神經(jīng)網(wǎng)絡(luò)模型，僅去除最后的輸出層，將最后的隱層拼接作為網(wǎng)絡(luò)學(xué)習(xí)到的商品的向量表示。

在這里，假設(shè)商品i的向量表示為di，通過attention的方法計算不同商品之間的交互作用，最終得到商品i的輸出向量oi=∑Nj=1wijdj。這里wij計算的是商品j對商品i的輸出向量的貢獻(xiàn)，其計算方式為：

wij= cij ∑Nj=1cij

其中，

cij=vT （Wq di+Wv dj）

在這里，Wq， Wv∈Rd×d， di， v∈RN。最后，每個商品通過前饋神經(jīng)網(wǎng)絡(luò)得到對應(yīng)的輸出，再使用前述相同的方式計算每個商品被點擊的概率。

該模型充分考慮了產(chǎn)品組合中不同商品的相互交互作用，是目前最優(yōu)的選擇模型構(gòu)建思路，但也由于其考慮到了其他商品對于單個商品的影響，沒有估計單個商品產(chǎn)生的效用，因此無法與優(yōu)化模型相結(jié)合來得到最優(yōu)產(chǎn)品組合。

3 數(shù)值實驗

本文的實驗數(shù)據(jù)來源于全球分銷系統(tǒng)Amadeus收集的機(jī)票預(yù)訂數(shù)據(jù)。在顧客預(yù)訂機(jī)票時，顧客進(jìn)行一些搜索，系統(tǒng)返回不同的航班信息，顧客選擇點擊這些航班中的一個。本文選擇部分?jǐn)?shù)據(jù)集，共16861條數(shù)據(jù)作為訓(xùn)練集，1000條數(shù)據(jù)作為測試集，每條數(shù)據(jù)含三十個備選航線。每條航線包含數(shù)值特征與類別特征，如表1所示。出于法律上的原因，數(shù)據(jù)并未包含乘客的相關(guān)信息。

對于中轉(zhuǎn)時間、總價格以及飛行時間等連續(xù)型變量，數(shù)值的取值范圍過大，若單個特征對應(yīng)數(shù)值過大，很可能會直接影響模型結(jié)果。因此，對中轉(zhuǎn)時間，總價格以及飛行時間三個變量，計算每個變量在所有樣本中的最大值max以及最小值min，采用歸一化的方式進(jìn)行預(yù)處理，加快模型的收斂速度：

x′= x-min max-min

對于出發(fā)時間以及到達(dá)時間，將時間特征投影到極坐標(biāo)，00：00（0分鐘）對應(yīng)0，24：00（1440分鐘）對應(yīng)2π。根據(jù)時間的特性可知，兩個時間對應(yīng)的角度夾角越小，則表示這兩個時間越接近，因此采用計算sin與cos的方式轉(zhuǎn)換對應(yīng)的時間特征：

xsin=sin ?x 1440 ×2π

xcos=cos ?x 1440 ×2π

本文使用上述仿真數(shù)據(jù)，采用了LightGBM、MNL選擇模型、神經(jīng)網(wǎng)絡(luò)選擇模型以及attention選擇模型4種模型對用戶可能點擊的商品進(jìn)行預(yù)測。

LightGBM是一種基于分類回歸樹的梯度提升樹改進(jìn)算法，在本次研究中，將所有訓(xùn)練數(shù)據(jù)中的所有商品作為樣本，使用每個商品被點擊的概率作為標(biāo)簽，訓(xùn)練LightGBM模型。在測試階段，對商品候選集里的所有商品都預(yù)測一個點擊概率，選擇預(yù)測概率最高的商品作為預(yù)測的被點擊對象。

MNL選擇模型、神經(jīng)網(wǎng)絡(luò)選擇模型的訓(xùn)練過程與LightGBM不同，其輸入為產(chǎn)品組合中的一個商品，通過模型計算商品的效用，最后將產(chǎn)品組合中所有商品的效用進(jìn)行歸一化處理，計算產(chǎn)品組合中每個商品的點擊概率，并通過梯度下降的方式訓(xùn)練模型。在測試階段，使用模型估計商品候選集中每個商品的效用，選擇效用最高的商品作為預(yù)測的被點擊對象。

Attention選擇模型的輸入是一個產(chǎn)品組合，其中的每個商品通過網(wǎng)絡(luò)被編碼為一個向量，再通過這些向量計算交互因素，最終通過歸一化的方式輸出商品在該產(chǎn)品組合中被點擊的概率。在測試階段，選擇被點擊概率最高的商品作為預(yù)測的被點擊對象。

本次實驗的評價指標(biāo)為被點擊概率top K商品的被點擊率，實驗結(jié)果如表2和圖2所示。由表2可以看出，盡管MNL模型結(jié)構(gòu)簡單，擬合能力不強，但通過其預(yù)估的商品效用具備一定的準(zhǔn)確性，通過效用計算的被點擊概率能夠取得與LightGBM模型相近的結(jié)果，并且MNL模型還具備可解釋性以及高效快速等優(yōu)勢。而使用神經(jīng)網(wǎng)絡(luò)模型來估計效用，同樣也是根據(jù)效用來推薦商品，其表現(xiàn)明顯好于MNL模型，說明優(yōu)化模型的結(jié)構(gòu)、考慮更多特征的交互能夠顯著提升效用估計的準(zhǔn)確性。最后，使用attention選擇模型的表現(xiàn)則略微好于前述估計單個商品效用的模型，說明在該場景下，前述模型對于商品效用的估計還是比較準(zhǔn)確的，可以通過將效用估計和優(yōu)化模型結(jié)合的方式來確定最優(yōu)的產(chǎn)品組合。

4 總結(jié)

本文從如何進(jìn)行產(chǎn)品組合推薦才能使得商家期望收益最大化這一背景出發(fā)，對如何準(zhǔn)確估計商品對顧客產(chǎn)生的效用這一問題進(jìn)行了探究。本文使用了LightGBM、MNL選擇模型、神經(jīng)網(wǎng)絡(luò)選擇模型以及attention選擇模型4種模型，通過數(shù)值實驗，得到了如下結(jié)論：（1）通過線性模型估計的商品效用可以取得令人滿意的準(zhǔn)確率，并且線性模型還具備可解釋性等優(yōu)勢。（2）通過神經(jīng)網(wǎng)絡(luò)來估計商品效用，能夠解決線性模型存在的問題，大大提升了估計的準(zhǔn)確性，并且通過其計算得到的商品點擊概率與attention選擇模型相比差距不大。因此，使用神經(jīng)網(wǎng)絡(luò)模型估計商品效用具備一定的實際意義，可以將其運用于產(chǎn)品組合優(yōu)化模型中，這對商家的推薦系統(tǒng)如何進(jìn)行商品推薦具備一定的參考意義。

參考文獻(xiàn)：

［1］ ?MCFADDEN D. Conditional logit analysis of qualitative choice behavior［J］. 1973.

［2］ GUO H， TANG R， YE Y， et al. DeepFM： a factorization-machine based neural network for CTR prediction［J］. arXiv preprint arXiv：1703.04247， 2017.

［3］ MOTTINI A， ACUNA-AGOST R. Deep choice model using pointer networks for airline itinerary prediction［C］//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017： 1575-1583.

［4］ KE G， MENG Q， FINLEY T， et al. Lightgbm： a highly efficient gradient boosting decision tree［C］//Advances in neural information processing systems. 2017： 3146-3154.

［5］ PEROZZI B， AL-RFOU R， SKIENA S. Deepwalk： online learning of social representations［C］//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2014： 701-710.

［6］ MIKOLOV T， CHEN K， CORRADO G， et al. Efficient estimation of word representations in vector space［J］. arXiv preprint arXiv：1301.3781， 2013.

［7］ WANG J， HUANG P， ZHAO H， et al. Billion-scale commodity embedding for e-commerce recommendation in alibaba［C］//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM， 2018： 839-848.

［8］ RENDLE S. Factorization machines［C］//2010 IEEE International Conference on Data Mining. IEEE， 2010： 995-1000.

［9］ JUAN Y， ZHUANG Y， CHIN W S， et al. Field-aware factorization machines for CTR prediction［C］//Proceedings of the 10th ACM Conference on Recommender Systems. ACM， 2016： 43-50.

［10］ ?CHENG H T， KOC L， HARMSEN J， et al. Wide & ?deep learning for recommender systems［C］//Proceedings of the 1st workshop on deep learning for recommender systems. ACM， 2016： 7-10.

［11］ VULCANO G， VAN RYZIN G， CHAAR W. Om practice—choice-based revenue management： an empirical study of estimation and optimization［J］. Manufacturing & Service Operations Management， 2010， 12（3）： 371-392.

［12］ DAVIS J， GALLEGO G， TOPALOGLU H. Assortment planning under the multinomial logit model with totally unimodular constraint structures［J］. Work in Progress， 2013.

［13］ GALLEGO G， TOPALOGLU H. Constrained assortment optimization for the nested logit model［J］. Management Science， 2014， 60（10）： 2583-2601.

［14］ FELDMAN J， ZHANG D， LIU X， et al. Taking assortment optimization from theory to practice： evidence from large field experiments on alibaba［J］.

［15］ FRIEDMAN J H. Greedy function approximation： a gradient boosting machine［J］. Annals of Statistics， 2001： 1189-1232.