王瑋皓，陳松燦+

1.南京航空航天大學 計算機科學與技術學院，南京 211106

2.模式分析與機器智能工業(yè)和信息化部重點實驗室，南京 211106

1 引言

在信息過載時代，推薦系統(tǒng)是互聯(lián)網應用中不可或缺的算法。推薦系統(tǒng)根據用戶資料、購買記錄、商品屬性，以及時間、地點、天氣等上下文信息，為用戶推薦合適的產品或服務。從方法角度分類，推薦系統(tǒng)可以分為基于協(xié)同過濾的推薦、基于內容的推薦和兩者的混合方法。

推薦場景下，特征間的交互蘊含了重要信息，例如，一個用戶同時喜歡導演史蒂文·斯皮爾伯格和演員湯姆·漢克斯，那他很可能喜歡電影《拯救大兵瑞恩》。因子分解機（factorization machine，F(xiàn)M）[1]是近年發(fā)展出的一種有效的推薦系統(tǒng)模型，能夠捕捉輸入特征間的這種二階交互關系。相比對率回歸等線性模型，F(xiàn)M 本質上是二階非線性模型，它將二階系數表示成歐氏空間中對應嵌入向量的內積，提升了模型的泛化能力，能發(fā)現(xiàn)訓練時未同時出現(xiàn)的兩特征間的交互關系。FM 的輸入特征通常為圖1 的形式，是多個特征域的組合；輸出該特征組合下，用戶對商品的點擊率或評分等。結合不同的損失函數，F(xiàn)M 可以處理分類、回歸、排序等多種問題。其簡單的特征工程、優(yōu)越的性能、線性時間復雜度，使其自提出以來即被廣泛應用于大規(guī)模商業(yè)化的推薦系統(tǒng)。近年來對FM 的改進層出不窮，典型的如HOFM（higher-order factorization machines）[2]借助ANOVA（analysis of variance）核將二階FM 顯式地推廣至高階，DeepFM[3]、Wide&Deep[4]通過多層神經網絡隱式地建模高階特征交互。但這些方法大量增加了模型參數，帶來優(yōu)化困難和過擬合風險。另外，盲目地捕捉特征之間的高階交互會帶來大量無用信息，反而可能降低模型性能。AFM（attentional factorization machines）[5]引入注意力機制對不同的特征交互項賦予不同的重要性權重，但FM 中特征嵌入向量的內積已包含了此信息，因此這一改進的作用并不顯著。此外，推薦系統(tǒng)中用戶、商品等對象的交互呈冪律分布，即熱門商品和活躍用戶非常少。FM 將特征嵌入到歐氏空間，但平坦的歐氏空間不具有刻畫冪律分布和層次結構的能力，很大程度上限制了模型的表示能力。

Fig.1 Input feature of FM圖1 FM 的輸入特征

雙曲空間（hyperbolic space）是一種擁有負常曲率的黎曼流形空間。出于雙曲空間的幾何性質，它可被視為一種連續(xù)化的樹結構，近年來許多工作表明，相比平坦的歐氏空間，雙曲空間更適合于有著隱含層次結構的對象的嵌入表示。Krioukov 等人[6]在雙曲空間中研究了復雜網絡的結構；Nickel 和Kiela[7]首次在雙曲空間對詞匯進行低維嵌入，結果表明雙曲空間能夠捕捉詞匯概念之間的層次結構；Tay等人[8]將問題和回答嵌入到雙曲空間中，進行智能問答；Vinh等人[9]提出的雙曲空間矩陣分解方法（HyperMF）首次將用戶和商品嵌入到雙曲空間中，發(fā)現(xiàn)了用戶和商品間同樣存在層次結構?？偟膩碚f，如果將一組具有層次結構的對象嵌入到雙曲空間，那么對象間的相似性將由它們的雙曲距離決定，而層次結構則由對象到原點的距離（或稱之為雙曲范數）決定[10]。如圖2（a）所示，在雙曲空間中考察物種概念，那么“哺乳動物”這樣高層次的概念相對于“人類”和“猿”等具體物種，更靠近雙曲空間的原點，即雙曲范數較??；而這三個概念強相關，因此它們距離上相近。再如，“蜥蜴”和“人類”都是具體的物種，它們到原點的距離相等，但兩者差異較大，因而彼此距離較遠。推薦系統(tǒng)中，用戶、商品、屬性等特征本身可視為一個大規(guī)模的、符合冪律分布的異構網絡，具有層次結構。因此本文嘗試將這些特征嵌入到雙曲空間中，并以特征之間的雙曲距離衡量兩個特征的交互關系，進而導出了雙曲因子分解機（hyperbolic factorization machine，HFM）。

Fig.2 Hyperbolic space圖2 雙曲空間

本文主要貢獻包括：

（1）提出了基于雙曲空間距離度量的因子分解機HFM，推廣了FM；

（2）針對兩種不同的雙曲空間模型，提供了相應的基于黎曼梯度下降的優(yōu)化方法；

（3）在人工和真實數據集上的實驗結果表明，相比FM，HFM 不僅有效提升了性能，更重要的是能發(fā)現(xiàn)特征間隱含的層次關系，從而更具解釋性。

2 雙曲空間

針對雙曲空間，目前已有多種數學模型可刻畫，如龐加萊模型、雙曲面模型、克萊因模型等。這些模型本質上等價，但側重點各異。龐加萊模型在可視化嵌入對象的層次結構時相對清晰，而雙曲面模型避免了計算距離時的數值不穩(wěn)定。下面為完整起見，將分別加以介紹。

2.1 龐加萊模型

龐加萊模型（Poincaré model）[7]Pn=(Bn,gp) 是一個黎曼流形，其中Bn={x∈?n:||x||＜1}是開的n維單位球，‖· ‖ 表示歐氏空間的L2 范數。是其黎曼度量張量，ge表示歐氏空間的度量張量。龐加萊球Bn中任意兩點的測地線是一段正交于Bn邊界的圓弧（如圖2（b））。P 上的測地線距離函數，即該模型下任意兩點u,v∈Bn的雙曲空間距離為：

從上式中易得出雙曲空間的一些性質，如：（1）雙曲空間中u、v兩點的距離隨u和v的范數平滑地變化，且距離函數可微；（2）歐氏距離保持不變時，兩點的雙曲距離隨靠近單位球邊界的程度指數級增加；（3）一個點與原點的雙曲距離，隨該點靠近單位球邊界的程度指數級增加。

2.2 雙曲面模型

雙曲面模型又稱洛倫茲模型（Lorentz model）[10]。設u,v∈?n+1，定義洛倫茲標量積：

則雙曲面模型表示的n維雙曲空間可以寫成Ln=(Hn,gl)，其中是雙曲面的上半葉，gl(x)=diag(-1,1,…,1)是黎曼度量張量。注意到雙曲面上任一點x∈Hn滿足：

因此該流形的維度為n。L 上任意兩點u,v∈Hn的測地線距離為：

本質上龐加萊模型和雙曲面模型等價，但由于龐加萊模型在可視化時更方便，可以通過變換p:Hn→Pn，將雙曲面模型中的點映射到龐加萊模型中：

3 雙曲因子分解機

3.1 因子分解機

假設輸入特征是p維向量x∈?p，則二次多項式回歸模型的表達式為：

與二階多項式不同的是，F(xiàn)M 對二次系數wij進行了分解，即為每一維特征分量學習了一個歐氏空間上的嵌入向量vi，并以嵌入之間的內積作為刻畫特征二階交互xixj的二次系數，即：

其中，wb∈? 是偏置，wi∈? 是線性項系數。這樣，F(xiàn)M 一方面減少了模型參數數量，減輕過擬合風險；另一方面，可以發(fā)現(xiàn)在訓練時未出現(xiàn)的特征交互，提高了泛化能力。

3.2 雙曲因子分解機

Vinh 等人[9]將用戶和商品嵌入到龐加萊雙曲空間模型中，發(fā)現(xiàn)了用戶和商品間隱含的層次結構。例如，熱門商品被很多用戶購買，那么該商品與很多用戶存在連接關系，作為一個中心節(jié)點，它將被嵌入到雙曲空間的原點附近，這樣它幾乎與所有用戶的雙曲距離都相對較近。

考慮圖3 所示的數據集，用戶和商品之間的連線表示用戶對商品感興趣，商品和品牌之間的連線表示商品屬于該品牌，給定（用戶，商品，品牌）的特征組合（如圖1 的特征輸入形式），推薦系統(tǒng)需要判斷用戶是否對這件商品感興趣。不難發(fā)現(xiàn)特征間存在連接關系，即特征之間可構成一個異構網絡[11]，而FM中的二階交互系數可視為這一異構網絡上的邊權。事實上，這樣的異構圖存在著層次結構，例如四件商品都屬于“品牌X”，那么特征“品牌X”就是這些商品的中心節(jié)點。雙曲空間適合于具有層次結構對象的嵌入，將雙曲幾何引入推薦系統(tǒng)可以增強模型的表示能力，這就為提出雙曲因子分解機（HFM）提供了動機。為每一維特征xi學習一個雙曲空間中的嵌入向量vi，將HFM 定義為：

其中，dh(vi,vj)是特征嵌入向量vi和vj的雙曲距離，dh可取作龐加萊模型的距離度量式或雙曲面模型的距離度量式。分別將基于龐加萊模型和雙曲面模型的HFM 記為P-HFM 和L-HFM。m(·)稱為匹配函數，通過匹配函數可以控制交互系數的符號。m(·)可為對數函數、等值映射、取相反數或線性變換等，實驗發(fā)現(xiàn)m(·)取線性變換最佳，即：

其中，β,c∈? 是可訓練的標量參數。

Fig.3 Heterogeneous network of users,items and brand圖3 用戶、商品和品牌特征構成的異構網絡

3.3 目標函數與黎曼梯度下降

推薦系統(tǒng)中，瀏覽、收藏、購買等隱式反饋遠遠多于評分等顯式反饋，且隱式反饋更易獲取，因此選取基于隱式反饋的貝葉斯個性化排序（Bayesian personalized ranking，BPR）[12]作為模型的目標函數。BPR是一種排序損失函數，給定用戶u，用戶訪問過的商品i和另一個由負采樣得到的商品j構成的三元組(i,j,k)，其優(yōu)化目標是最大化用戶u喜歡商品i更甚于商品j的似然概率P(i?u j)。若HFM 對(u,i)組合特征的輸出為，對(u,j) 組合特征的輸出為，則，σ表示Sigmoid 函數。最終目標函數為：

采用Adam[13]算法對目標函數進行優(yōu)化。由于HFM 中特征分量的嵌入vi是雙曲空間中的模型參數，因此優(yōu)化時需要進行黎曼梯度下降（Riemannian gradient descent，RSGD）[14]。RSGD 可分解為三個步驟：（1）計算關于vi的歐氏梯度?El(vi)；（2）將其轉換為黎曼梯度?Rl(vi)；（3）根據黎曼梯度更新嵌入向量。

龐加萊模型中[7]，將歐氏梯度轉換為黎曼梯度只需乘上一個標量，即：

更新步驟為：

雙曲面模型的RSGD[10]相對復雜一些，首先將歐氏梯度轉換到黎曼梯度。

然后進行參數更新：

其中，hr=η?Rl(vi)，η為學習率。

需要注意的是，Adam 實質上是根據訓練過程中各參數梯度的累積，對各參數的學習率乘上自適應的修正系數。因此，根據式（6）或式（8）對vi的梯度進行轉換后，利用黎曼梯度更新這些參數學習率的修正系數，最后再按式（7）或式（9）進行更新。

迭代更新直至損失收斂，迭代時每一步的具體更新流程如算法1 所示。

算法1 雙曲因子分解機的Adam 優(yōu)化算法

4 實驗與分析

4.1 數據集及其劃分

在人工數據集和公開的真實數據集上進行了實驗：

（1）人工數據集如圖3 所示，詳細含義已在3.2 節(jié)介紹過。

（2）Amazon 數據集[15]包含電商網站上大量的購買記錄和商品的類目信息，使用了其中Sports、Toys、Automotive、Office 共4 個子集。如表1 用戶平均訪問數、商品平均訪問數兩列所示，該數據集的用戶-商品交互高度稀疏，能夠檢驗模型在稀疏數據上的性能。

（3）GoogleLocal 數據集[16]包含了美國各州用戶前往商鋪消費的記錄，以及商鋪的經營類型和經緯度信息，使用了Texas、California、Florida共3 個子集。

本節(jié)中“商品”指物品或商鋪，“訪問”指購買或消費行為。對于真實數據集，忽略訪問次數小于5 次的商品和用戶后，相關統(tǒng)計信息如表1 所示。將每個用戶的訪問記錄按時間排序，然后將每個用戶最后訪問的商品劃入測試集，前一個商品劃入驗證集，其余作為訓練集。

4.2 實驗結果與分析

基于PyTorch 實現(xiàn)了P-HFM 和L-HFM（代碼見https://github.com/heygrain/hfm），以及四種對比方法FM[1]、DeepFM[3]、AFM[5]和HyperMF[9]。對于DeepFM的深度網絡部分，為防止參數過多造成過擬合，設置兩個隱層單元數分別為32 和16，并按原文使用批歸一化（batch normalization）[17]和dropout[18]；對于AFM，設置注意力網絡隱層單元數為嵌入維數的一半，并按原文使用dropout；對于雙曲空間上的模型HyperMF、P-HFM、L-HFM，為雙曲空間嵌入向量單獨設定了學習率。

為展示HFM 的表示能力和有效性，在圖3 的人工數據集上進行了特征嵌入分析，為方便起見，這里取匹配函數m(dh)=-dh。圖3 表示用戶A、B都喜歡商品1、2，而用戶C、D都喜歡商品3、4，且商品1～4都屬于“品牌X”。訓練P-HFM 至收斂時，特征在雙曲空間中的嵌入如圖4（a），具有明顯的層次結構：商品1～4 都屬于“品牌X”，因此“品牌X”靠近雙曲空間的原點，與其他所有特征嵌入的雙曲距離都較?。挥脩鬉與B都喜歡商品1 和2，因而這4 個特征的嵌入聚在一起；同樣地，用戶C、D和商品3、4 也聚在一起。圖4（b）展示了Florida 數據集上的訓練結果，為清晰起見，只顯示了驗證集樣本的特征嵌入，同時未畫出經緯度特征的嵌入，發(fā)現(xiàn)店鋪經營類型作為高層級概念被嵌入到原點附近。以上兩例充分說明了HFM 能捕捉特征間的交互和層次結構。

Table 1 Statistics of datasets表1 數據集的統(tǒng)計信息

在真實數據集上進行實驗時，針對所有模型，Amazon 的4 個數據集的特征嵌入維數設為30，GoogleLocal 的3 個數據集的特征嵌入維數設為10，其他超參數在驗證集上用網格搜索的方式確定。

在測試集上使用命中率（hit ratio）HR@k評價模型，即對測試集中每個用戶隨機采樣99 個負樣本商品，并與該用戶實際訪問的商品一同輸入模型進行預測，按模型輸出值從大到小排序，若該用戶實際訪問商品排在前k則稱為命中，HR@k表示測試集的命中比例。表2 為k=5 的實驗結果，表3 為k=10 的實驗結果，星號表示本文提出的方法。

可以發(fā)現(xiàn)，L-HFM 在大多數情形下表現(xiàn)最優(yōu)，個別數據集上為次優(yōu)。P-HFM 的表現(xiàn)較L-HFM 稍有欠缺，原因是龐加萊模型的距離函數式中分母可能接近0，導致數值計算不穩(wěn)定。

與FM 相比，L-HFM 和P-HFM 的可學習參數數量幾乎一致，而L-HFM 性能更優(yōu)，說明雙曲空間更適合推薦場景下的特征嵌入。對于DeepFM，盡管控制了深度網絡的參數數量，過擬合仍無法避免，究其原因，一方面DeepFM 可能適合更大規(guī)模的數據，另一方面盲目引入高階交互帶來了大量無用信息。對于AFM，由于FM 的二次項系數已包含特征交互的重要性程度，因此再引入注意力機制賦予其重要性權重，帶來的性能提升有限。

與同樣采用雙曲距離度量的HyperMF 相比，PHFM 可視為HyperMF 的推廣，即當輸入特征為用戶ID 和商品ID 的one-hot 編碼，且wb=0,w1=w2=…=wp=0 時，P-HFM 退化為HyperMF。注意到在稀疏的Amazon 數據集上，HyperMF 的性能遠遠低于HFM，甚至低于FM，這是因為HyperMF 使用矩陣分解的方式學習商品和用戶在雙曲空間中的嵌入，只能利用有限的、稀疏的協(xié)同信息，無法利用商品特征、用戶資料、上下文等補充信息。而HFM 既利用了雙曲空間的優(yōu)勢，又繼承了FM 處理其他特征的便捷性，可以將其他信息囊括到輸入特征中，而無需改造模型本身，有效提高了用戶-商品交互十分稀疏情形下的模型性能。

4.3 參數敏感性分析

Fig.4 Learned feature embeddings圖4 學到的特征嵌入

Table 2 Results on test set with respect to HR@5表2 測試集上的HR@5 指標

Table 3 Results on test set with respect to HR@10表3 測試集上的HR@10 指標

嵌入維數是HFM的重要超參數，在Office和Automotive 數據集上考察嵌入維數對模型性能的影響，其他數據集上結果類似。圖5 繪制了隨嵌入維數的增加，模型性能的變化?？梢钥闯觯Ｐ托阅軐τ谇度刖S數不敏感。當嵌入維數足夠大時，增加嵌入維數不再提升模型性能。

5 結束語

考慮到推薦系統(tǒng)中用戶、商品、屬性等特征間存在層次結構，以及雙曲空間適合于具有層次結構對象的嵌入表示，本文在FM 的基礎上，提出了基于雙曲空間距離度量的HFM，以特征間的雙曲距離評估其二階交互，并針對龐加萊和雙曲面兩種雙曲空間模型，提供了相應的黎曼梯度下降優(yōu)化算法。實驗結果表明，在等量參數的情形下，HFM 獲得了比FM更好的性能，更重要的是能發(fā)現(xiàn)特征間隱含的層次結構，提供了部分可解釋性。

Fig.5 Hit ratio on validation set with respect to change of embedding dimensions圖5 驗證集上的命中率隨嵌入維數的變化