改進的哈希學習高效推薦算法

應文杰，桑基韜

北京交通大學 計算機與信息技術學院，北京100044

1 引言

個性化推薦技術由于能為用戶推薦感興趣的內容，提高用戶體驗，進而增強用戶粘性以及用戶的忠誠度，已經得到許多大型互聯網公司（如Amazon、Alibaba、Baidu等）的廣泛關注和深入研究[1-2]。然而，隨著互聯網的快速發展，各行各業的數據都呈現爆炸式的增長。例如，截止到2018 年10 月，Taobao 平臺上已經有超過5 億的用戶和10 億的商品。因此，推薦系統也面臨著數據存儲和檢索效率等挑戰[3-5]。

哈希學習通過保持原始空間中的近鄰關系將原始數據映射成二進制碼的形式。有效地減少數據存儲開銷，加快相似性檢索效率而廣泛地應用于信息檢索、計算機視覺、推薦系統等領域[6-10]。最近，一些基于哈希學習的推薦方法被應用于提高推薦系統的效率[11-15]。這些方法的核心是將用戶評分矩陣看作用戶與項目之間的相似性矩陣，通過分解相似性矩陣來得到用戶和項目的低維二進制表示。然后在二進制空間計算用戶和項目之間的漢明距離，距離越小表示相似性越大，用戶對項目越感興趣。由于這種二進制表示，實值向量空間的內積操作被二進制空間中的位運算所取代。因此，即使采用線性掃描，時間復雜度也能得到顯著降低[3，13]。

然而，現存的基于哈希學習的推薦方法普遍存在一個問題，它們忽略了用戶評分與相似性不等價問題。一般而言，用戶評分系統都默認為等級評分（如豆瓣電影評分為1到5的等級），而哈希碼在二進制空間的相似性區間一般為正負對稱的離散區間。因此，現存的哈希推薦方法一般采用規范化的方式直接將評分映射相似性區間。這種方式是非常粗暴的，它忽略了隱藏在評分信息下用戶和項目的自身特點。比如有些用戶喜歡給高分，而有些用戶喜歡給低分，有些項目更受歡迎，而有些項目不受歡迎[16]。

本文提出了一種改進的哈希推薦方法。它通過移除用戶和項目自身的偏置將用戶評分映射到正負對稱的相似性區間。如圖1 所示，首先，計算所有用戶和項目相對于評分系統均值的偏置，在移除偏置之后，將用戶評分映射到相似性區間。然后，分解相似性矩陣得到用戶和項目的二進制碼，在二進制空間計算用戶與項目之間的相似性。最后，預測用戶評分時加上對應的偏置將相似性映射到評分區間。通過這種方式，很好地緩解了用戶評分與相似性不等價問題。同時，在分解相似性矩陣時，以保持相似性為目標，提出了兩種結構損失來構建目標函數。實驗部分，分析了三個數據集的評分分布，解釋了偏置項處理的合理性，在三個真實的數據集上進行實驗，對比了幾個代表性方法，本文方法能實現更高的檢索精度。

總結了本文的貢獻如下：

（1）通過移除用戶和項目的偏置，將用戶評分映射到相似性區間，很好地解決了用戶評分與相似性不等價的問題。

（2）以最小化相似性損失為目標，提出了兩種方式來構建目標函數，并在實驗中對兩種方式進行了對比分析。

（3）在三個真實的數據集上的實驗結果表明，與幾個代表性方法對比，本文方法能實現更高的檢索精度。

2 相關工作

目前，基于矩陣分解的推薦方法依然是最受歡迎的方法之一，大多數基于哈希的推薦方法都建立在矩陣分解基礎上[2-3，13]。在這部分，回顧了傳統的矩陣分解推薦方法和離散矩陣分解推薦方法。

2.1 實值矩陣分解

推薦系統方法包括基于內容推薦，協同過濾推薦以及兩者結合的方法[17-21]。目前，協同過濾技術已經成為了主流的方法，尤其是矩陣分解的協同過濾推薦[22-25]。矩陣分解方法通過分解用戶評分矩陣得到用戶與項目的隱語義表示，然后在向量空間計算用戶對項目的評分[16，25]。FuckSVD[26]分解用戶評分矩陣，在低維的向量空間來表示用戶和項目，通過向量內積來計算用戶對項目的偏好。然而，完全基于向量表示來計算用戶對項目的評分是不明智，因為有的用戶喜歡給高評分，有的用戶喜歡給低評分[16]。因此，Paterek等[27]提出了一種帶偏置的矩陣分解方法BiasSVD。考慮了用戶自身的評分特點以及項目受歡迎的程度。為了解決冷啟動問題，Paterek 等[28]提出了一種結合內容感知和隱反饋信息的矩陣分解方法SVD++。郭寧寧等[29]人提出一種融合社交網絡特征的協同過濾推薦算法，引入評分以外的信息來提高推薦的性能。雖然，矩陣分解的方法在推薦系統中已經取得了很好的表現。然而，面對日益增長數據，推薦系統的效率也面臨著巨大的挑戰[3，13]。

2.2 離散矩陣分解

哈希技術通過將原始數據映射為低維的二進制碼表示，從而減少數據存儲，加速相似性查詢效率得到了廣泛的關注和深入的研究[30-34]。

早期的基于哈希的矩陣分解推薦通常是一個“兩階段”的學習過程[13]。Zhou 等人[3]提出的離散協同過濾方法將二進制碼的學習過程分為兩個獨立的階段：實值優化和二進制量化。在實值優化階段，通過丟棄離散約束分解矩陣得到連續解。在量化階段，通過最小化實值的量化損失來獲得二進制碼。Zhang等[11]提出了一種基于余弦相似性度量的方式來分解用戶評分矩陣進而得到用戶和項目的二進制碼。Liu等[12]提出了一種基于內容感知的矩陣分解方法，通過加入內容信息，很好地克服了冷啟動問題。

圖1 改進的哈希推薦方法設計流程

Zhang等[13]人指出兩階段方法由于放松二進制約束而引起的誤差會導致性能差的問題，因此提出了一種離散協同過濾方法。為了解決帶約束的離散化優化問題，它將原始問題轉化為兩個子問題。在離散化優化階段，提出了一種離散梯度下降算法，同時采用SVD 分解方法來保持位平衡和位不相關約束來保證哈希碼的有效性。Lian 等[14]在離散協同過濾基礎了提出了一個結合內容感知的離散協調過濾方法。Zhang等[15]提出了一個基于深度學習的方法，采用深度信念網絡來學習用戶和項目的二進制表示。由于二進制碼表示，實值向量空間的內積操作被二進制空間中的位運算所取代。因此，線性掃描的時間復雜度也能得到了明顯降低[3，11]。

3 本文方法

假定系統中的用戶數量為n，項目數量為m，用戶對項目的評分構成稀疏的評分矩陣R ∈Rn×m，其中Rij表示用戶ui對項目vj的評分。哈希后的用戶空間為B:{b1,b2,… ,bn}∈{-1,1}r，×n哈 希 后 的 項 目 空 間 為D:{d1d,2, …,dm}∈{-1,1}r×，m其中r 是哈希碼的長度。tr(?)表 示 矩 陣 的 跡，||?||F表 示 矩 陣 的Frobenius 范 數，sgn(?)為符號函數，輸入大于等于0 時輸出1，反之輸出-1。1表示全為1的列向量。

3.1 模型

基于用戶評分矩陣Rij，離散矩陣分解推薦方法通過分解用戶評分矩陣得到用戶和項目的二進制碼。如果用戶ui對項目vj評分越高，那么用戶bi與項目dj的漢明距離越小，相似性越大。其中，bi與dj的相似性定義如下[3]：

其中，I(?)為指示函數，如果條件成立則返回1，否則返回0。由式（1）定義可知，當用戶與項目的向量內積越大，相似度越大，反之越小。另外，為了最大化哈希碼的信息熵和方差，定義位平衡B1=0,D1=0和位不相關約束BBT=nIr×r,DDT=mIr×r來保證每一位哈希碼的有效性。因此，現存的離散矩陣分解方法通常建立如下目標函數：

在大多數評分系統中，Rij為1～5 的等級評分，而∈{-r,-r+2,… ,r-2,r}。因此，現存的方法大多都對原始用戶評分Rij∈[min s,max s]進行規范化處理Rij=2r(Rij-r)/(max s-min s)-r[13-15]。然而，這種方式忽略了隱藏在評分信息下面的用戶和項目的自身特點。比如，有些用戶喜歡給高分，有些用戶喜歡給低分，有些項目更受歡迎，而有些項目不受歡迎[16]。直接映射處理無法挖掘潛藏在評分信息下的用戶和項目的特點。因此，提出了基于偏置的方式將用戶評分矩陣映射到正負對稱的相似性區間。

在式（3）中，根據每個用戶，項目以及評分系統的特點，將評分矩陣映射到了正負對稱的相似性區間。很好地緩解了評分與相似性不等價問題，同時挖掘了用戶與項目自身的特性。而然，的內積值與哈希碼的長度有關，因此，只需要將相似性Sij歸一化到[-r,r]。最終，目標函數如下：

其中，Sij∈[-r,r]為用戶ui與項目vj的相似性。

問題4 本質上是一個帶約束的離散化優化問題，直接優化是一個NP 難問題[35-36]。因此分別定義了兩個 約 束 空 間 Φ={X ∈Rr×n|X1=0,XXT=nIr×r} 和Ω={Y ∈Rr×n|Y1=0,YYT=mIr×r}。通過放松哈希碼的位平衡和位不相關約束得到一般化的目標函數：

其中，dist( )B,D,X,Y 表示{B,D}與{X,Y}之間的距離。本文提出了兩種度量方式如下：

值損失度量：分別衡量兩個矩陣中所有元素對應之間的誤差：

相似性損失度量：衡量兩個矩陣乘積之后相似性矩陣中所有元素對應之間誤差：

由tr(BBT)=tr(XXT)=nr、tr(DDT)=tr(YYT)=mr，可得，式（6）對應的值損失目標函數：

類似的，式（7）對應的相似性損失目標函數：

其中，式（8）和式（9）中的ρ ≥0,ρ1≥0,ρ2≥0 是調節參數。值得注意的是，可以通過設置一個很大的調節參數來強制dist(B,D,X,Y)→0。

3.2 學習

針對不同損失度量得到的目標函數式（8）和式（9），學習算法的過程類似，這里詳細介紹了相似性損失目標函數的學習過程。對于式（9），采用交替求解如下四個子問題：

B-問題：在這個問題中，固定D,X,Y，B-問題轉化為最小化目標函數：

其中，κi表示用戶ui的所有評分項目集合。

哈希碼的求解過程是一個離散優化問題，早期的方法放松哈希碼的離散約束來解決一個近似的優化問題，但這導致難以獲得高質量的哈希碼[35]。因此，Liu 等人[35]提出一種離散優化方法，同之前的工作一致[13，15]，采用離散坐標下降優化算法來更新每一位哈希碼。用bik表示bi的第k 位哈希碼，bikˉ表示除第k 位剩下的哈希碼，在固定bikˉ不變的時候，bik的更新規則如下：

D-問題：在這個問題中，固定B,X,Y，D-問題轉化為最小化目標函數：

其中，κj表示項目vj的所有評分用戶集合。同B-問題類似，D的更新規則如下：

X-問題：在這個問題中，固定B,D,Y，關于X 的目標函數如下：

為了保證X 的位平衡和位不相關約束，采用SVD分解求解式（14），記P=( BTDYT)T，X的更新規則如下：

其中，Ub和Vb分別是矩陣的左右奇異值是對應0 奇異值的特征向量基于[Vb1]斯密特正交化獲得[13]。

Y-問題：在這個問題中，固定B,D,X，關于Y 的目標函數如下：

4 算法分析

算法1 總結了整個優化過程，下面分析算法的復雜度和收斂性。

算法1

輸入：評分矩陣{Rij|i,j ∈κ}，哈希碼長度r，調節參數ρ

輸出：用戶哈希碼B ∈{±1}r×n，項目哈希碼D ∈{±1}r×m，偏置項

p=max(Sij),q=min(Sij)

Sij=(Sij-p)/(p-q)*2r+r

初始化：隨機初始化X,Y，B=sgn(X),D=sgn(Y)循環

直到收斂

4.1 復雜度

分析了算法的時間和空間復雜度。對于空間復雜度，算 法1 需 要O(|κ|)來 存 儲 稀 疏 的 評 分 矩 陣，需 要O(r.max(m,n))來存儲用戶和項目的哈希碼，其中r 是哈希碼的長度。另外，需要少量的空間O(m+n)來存儲用戶和項目的偏置信息。因此，整個算法的空間復雜度是線性的。

算法1 的時間復雜度包括預處理和四個子問題。預處理過程需O(κ)來完成評分到相似性的映射。對于B-問題，需要O(r2|κi|Ts)來計算用戶的哈希碼，其中Ts是更新一位哈希碼的時間。類似的D-問題需要O(r2|κj|Ts)來計算項目的哈希碼。對于X-問題需要O(r2(m+n))來進行SVD 分解和斯密特正交化，類似的Y-問題也需要O(r2(m+n))。假設算法需要迭代T 步收斂，那么整個算法的時間復雜度為O(Tr2((|κi|+|κj|)Ts+m+n))。因此，算法的樣本時間復雜度趨于線性。

現有的方法的核心過程大多是分解相似性矩陣，本文的方法相比于DCF多了一個預處理過程-評分到相似性的映射，該過程的復雜度與用戶評分數量是線性關系。由于BCCF、PPH 直接放松了哈希碼的離散約束來解決一個近似的優化問題，因此它們不涉及X-問題和Y-問題。相比而言，BCCF、PPH 多了一個連續值到哈希碼的量化過程。總的來說，算法1 的時間復雜度同三個代表性方法相當。

4.2 收斂曲線

如圖2 所示，給出了算法在Movielens-10M 數據集上目標函數與哈希碼長度比值的收斂曲線。從圖2 中可以看出算法在20 次迭代左右收斂，且收斂效果與哈希碼的長度正相關。算法的收斂速度非常快，尤其是前面幾次迭代。算法收斂性的理論分析與EM 算法的收斂性證明類似，詳細的收斂性分析參見文獻[13]。

圖2 目標函數收斂曲線

5 實驗

實驗中，在三個標準數據集上，對比了三個有代表性的哈希推薦方法BCCF、PPH、DCF。其中BCCF 和PPH 為兩階段哈希方法，PPH 采用余弦相似性度量，DCF 直接離散優化獲得哈希碼。所有的實驗運行在16 Intel Xeon CPU和64 GB RAM平臺。

5.1 數據集

使用如下三個標準數據集：

MovieLens-10M：這個數據集包括71 567 個用戶，10 681 部電影和107個評分信息。所有的評分在0.5～5之間，以0.5為間隔。

Douban：這個數據集包括129 490個用戶，58 541部電影和16 830 839 個評分信息。所有得評分在1～5 之間，以1為間隔。

Epinions：這個數據集來自于40 163個用戶對139 738部電影的664 824 個評分。所有的評分在1～5 之間，以1為間隔。

為了驗證本文的方法適合不同評分密度的數據，選擇了三個不同評分密度的數據集。同之前的工作一樣[14-15]，過濾了評分信息不足50 個的用戶，使得每個用戶都有可觀察的評分信息用于訓練和測試。對于每個用戶，選擇80%的評分信息作為訓練數據，剩下的20%作為測試數據。總結了過濾處理后的數據集如表1。實驗中，對數據集進行了5 次同樣比例的隨機劃分，并取5次實驗結果的均值來評估所有的方法。

表1 過濾后的數據集

5.2 評分分布

為了分析移除偏置的合理性，對三個數據集的評分分布進行了統計分析。如圖3 所示，發現三個數據集的用戶評分以3 到4 分所占的比例最多，兩端的比例相對較少評分分布大致服從正態分布。這表示，大多數用戶的評分具有一定的習慣，即存在一個評分平衡點，同時所有的評分是在這個平衡點上下浮動。因此，一個基本的假設就是將用戶均值以及項目均值相互作用看作是平衡點，偏離平衡點偏差則通過哈希碼之間的相似性來擬合。

圖3 三個數據集的用戶評分數據分布

5.3 評價指標

采用了如下三個常用的評價指標：

NDCG：折扣累計損失（DCG）是廣泛用于評價排序質量的指標。NDCG 則是對折扣累計損失歸一化的結果。NDCG 關注于算法獲得的哈希碼對保持用戶對項目的偏好排序的結果。NDCG計算如下：

其中，K 為排序靠前的K 個項目，ri是算法預測第i個偏好的項目的得分，而rj則是由用戶評分信息得到的第j個偏好的項目的得分。因為排序越靠前的項目得分權重越大，而且rj是實際用戶評分排序后的結果，所以NDCG的分母一定大于分子，即NDCG在0到1之間，越大說明保持用戶偏好排序的效果越好。

RMSE：平方根損失誤差是用來評價算法預測的評分與用戶的實際評分的偏差，不保持評分之間的排序關系。RMSE計算如下：

其中，κ 是所有可觀察的評分集合，yk為預測評分，y?k為真實評分。

Precision、Recall、F1：精度、召回率、F1 值是常用的分類指標。在這里，用于評價算法在預測用戶對項目是否喜歡的二類問題上。它們的計算公式如下：

對于每一個用戶，設置預測評分5 分以上的項目構成集合，實際評分為5分的項目構成集合。

5.4 實驗結果

5.4.1 對比實驗

同以往的工作一樣[3，13-15]，使用NDCG 和F1指標，對比了本文的方法同其他三個代表性的方法。

在表2 中，報告了不同方法在三個數據集上的NDCG@10 精度，可以看出本文的方法有一定的優勢，尤其是較短哈希碼長度下，相對于DCF 方法大約有1%～3%的提升。而且，OUR-S 在短哈希碼下的表現更顯著。在表3 中，展示了不同方法的F1 值，可以看出本文方法在大多數情況下優于其他方法，在8 bit 哈希碼下，本文的方法表現優越，相對于DCF 方法大約有3%～5%的提升。另外，在圖4 中展示了不同方法在不同哈希碼長度下的NDCG@K 隨K 的變化曲線，圖5 中展示了召回率-精度變化曲線，從圖中可以看出，本文的方法保持一致的優勢，尤其是在Douban數據集上。

5.4.2 相似性損失與值損失區別

對于兩種不同損失度量方式，大多數情況下相似性損失度量OUR-S 優于值損失度量OUR-V。如圖6 所示，在NDCG@5 指標下相似性損失度量依然優于值損失度量，而且在短哈希碼下這種優勢較為顯著。這表示相似性損失度量可以用較短的哈希碼就能獲得較優的結果。為了探究其中的原因，分析了兩種度量的RMSE指標。如圖7 所示，相似性損失度量相比于值損失度量，在預測評分上更準確，這說明相似性損失度量能更好地擬合用戶評分，保持用戶與項目之間的相似性。

6 總結

本文發現現存的大多數哈希推薦方法在處理用戶評分信息與相似性關系上過于粗暴，沒有挖掘評分信息下潛在的用戶和項目的特點。因此，提出了用一個偏置項來保留這種特點，通過去偏置將用戶評分映射到相似性區間，很好地緩解了用戶評分與相似性不等價的問題。在構建目標函數時，提出了兩種度量方式來構建目標函數，并在實驗中分析了兩種方式的區別，相似性損失度量優于值損失度量，尤其是在短哈希碼下。然而，本文沒有考慮推薦系統中的冷啟動問題[28，37]，沒有引入用戶評分以外的信息，探究評分以外的信息對算法性能的影響是一個值得思考的問題，也是下一步要研究的工作。

表2 不同方法在三個數據集上的NDCG@10值%

表3 不同方法在三個數據集上的F-measure值%

圖4 不同方法在不同哈希碼長度下的NDCG@K值(K=2,4,6,8,10)

圖5 不同方法在不同哈希碼長度下的召回率-精度曲線

圖6 兩種度量方式在不同哈希碼長度下的NDCG@5值

圖7 兩種度量方式在不同哈希碼長度下的RMSE值