稀疏化的因子分解機

郭少成，陳松燦

線性回歸模型因為其較好的泛化性能及相對簡單快速的求解方法而受到廣泛關注，并已成為統計機器學習中一類最基本的方法[1]。雖然上述線性模型在現實中有廣泛應用。但只有當問題的輸入呈線性關系時，它才會有較好的效果。另一方面，線性模型本身缺乏對輸入變量間關系的探索機制。由此自然地轉向考慮含有二階交叉項的線性模型(此處線性相對參數而言)。含有二階交叉項的線性模型考慮了輸入特征間的相互關系。因此，當輸入數據的特征間呈非線性關系，特別是二次關系時，其性能優于一般的線性模型。

推薦系統近年來廣受關注[2]，廣義上的推薦系統就是給用戶推薦物品的系統，它還可具體到一些特定領域，如音樂、書籍等。推薦系統的主要任務是根據用戶的歷史行為記錄去預測用戶未來可能會購買的物品。從本質上說就是探索用戶與用戶間以及用戶與物品間的關系，也就是變量與變量間的關系。針對推薦系統，最近S. Rendle等[3]提出了一個新的二階交叉項模型：因子分解機(FM)。在FM中，每個變量xi都對應著一個在隱空間的k維的向量vi, xi和xj的交叉項系數等于xi和xj的內積，當輸入數據非常稀疏時，一般的二階交叉模型無法學習到有效的交叉項系數。而FM分解了交叉項系數，這個特性使得FM能學習到數據中隱藏的變量間相互關系[3-4]。因此，FM特別適用于稀疏數據。

雖然對交叉項系數進行分解能顯著提升模型性能，但當k(因子分解維度)較大時，FM模型包含大量參數，為了避免過擬合，常常需要對目標函數添加正則化項。一種常用的正則化方法是添加范數。但是，對于高維數據，我們希望選出那些最具判別性的特征。通常的做法是向目標損失函數添加能夠誘導稀疏解的正則化項，通過優化正則化的目標函數來獲得稀疏解。比如在線性回歸中，向目標函數添加范數的正則項[5]，不僅能防止過擬合，還能起到特征選擇的作用。雖然，范數能獲得稀疏解，但是，這種稀疏并不包含結構信息。在FM中，其特征應當滿足這樣一種性質，即涉及同一個特征的線性項和二階項要么同時被選要么同時不被選，當該特征是噪音時，應當同時不被選，而當該特征是重要變量時，應當同時被選。而范數不能利用此先驗結構信息。

Group Lasso(GL) 是 M.Yuan 等[6]基于 Lasso 提出的用于對組變量進行特征選擇的方法，與Lasso不同的是，GL能同時選擇或者不選組內的所有變量。首先根據先驗知識將變量按照相關性劃分為不同組，從聚類角度看就是將同類變量劃分為同組，不同類變量劃分為不同組。在FM中，將關于特征xi的線性項系數ωi和其在隱空間的特征表示向量vi分在同組中，這樣，GL就能保證當xi是噪音時，ωi和vi同時不選，反之，則同時選擇。雖然GL能實現這種結構稀疏，但是，對于選中的組，并不是所有特征都是有用的。因此，GL的使用有非常大限制，有必要繼續選擇組內重要的特征。

Simon等[7]在GL的基礎上提出了基于Sparse Group Lasso（SGL）的線性回歸模型。與GL相同的是它們都對變量進行分組，與GL不同的是,SGL在GL的基礎上，繼續選擇組內重要特征。 因此，SGL能同時實現組間稀疏和組內稀疏, 而GL只實現了組間稀疏。SGL結合了Lasso和GL的優點，當待求變量存在結構稀疏信息時，僅使用Lasso會丟失結構信息，而僅使用GL又會導致求得冗余的解。基于上述事實，SGL既保留了GL的結構信息，又具有Lasso的高效特征選擇的能力。

從另一角度看，當輸入的數據非常稀疏而k選擇較大值時，FM容易過擬合。此時，SGL的組內稀疏能通過特征選擇控制k的大小。而且，不同的特征由于重要程度的不同，其對應的分解向量v的維度也應當不同，所以，組內稀疏在一定程度上通過特征選擇對不同維度特征自適應了最優的k值。

當前雖然已有一些關于FM的研究，如Mathieu等[8]在FM的基礎上進一步提出了高階因子分解機(階數≥3)，M. Li等[9]提出了分布式的FM以及W-S CHIN等[10]提出了針對二類分類問題的FM的優化算法并將其并行化。但是，它們并沒有探索FM的稀疏化機制。本文首次針對FM的二階特征結構提出了SGL-FM，而且，本文的方法也可以直接推廣到高階的FM中以探索高階FM的稀疏化機制。

1 因子分解機

1.1 目標函數

FM的基本模型如下：

式(1)也可變形為

FM的目標函數如下：

1.2 優化方法

目前已經有多種基于迭代的優化算法被提出用于優化FM，如MCMC, ALS[12]等。其中最常用的是隨機梯度下降法（SGD），即每次隨機選取一個樣本計算損失函數關于變量的梯度，之后用梯度更新待求變量，如此迭代便可優化目標函數。

式中：η是學習率，表示每次梯度更新的步長。對于最小平方損失函數有:

將式(2)對各個參數求導可得[12]：

基于式(5)～(7), 即可根據給定的樣本計算損失函數關于變量的梯度。

2 基于SGL的因子分解機

2.1 目標函數

本文通過對損失函數添加SGL的正則項以期望得到含有結構稀疏性質的解向量, SGL-FM的目標函數如下:

式中：將ωi和分為一組，共分為p組，其中表示同時選擇或同時不選ωi和vi，實現了組間稀疏。表示對選中的ωi和vi進一步進行特征選擇，實現了組內稀疏，而組內稀疏也相當于對各個維度自適應選擇最優k值。值得注意的是，范數均非光滑，且損失函數非凸。因此，目標函數非凸非光滑，而FM的目標函數非凸但光滑，因此，優化式(8)具有更大的挑戰, 不能照搬FM的優化方法。在下一節中，我們給出優化該目標函數的有效算法。實驗結果也表明，該算法能有效收斂。

2.2 優化方法

因為L1-FM和GL-FM均為SGL-FM的特例，給出SGL-FM的優化方法后，L1-FM和GL-FM的優化方法可以直接得到，因此本文僅關注SGLFM的優化。FM可以使用SGD算法優化，但是在SGL-FM中，由于范數和范數在零點不可微，雖然也可利用次梯度的方法迭代。但是，直接利用次梯度迭代很少能使變量達到不可微點[11]，也即很少會得到含有零元素的解向量，而在很多情況下零點才是目標函數的局部最小點。從另一個角度看，稀疏解能夠體現目標變量的結構信息。使用次梯度優化方法得到的結果相悖于我們期望的稀疏結果。所以，本文引入了前向后向切分算法(forward backward splitting, FOBOS)[11]來優化該問題。

2.2.1 FOBOS算法

FOBOS是一種基于迭代優化的算法框架，主要用來求解含有正則項的目標函數的優化問題，特別是一些不可微的正則項如:、（Group Lasso）、等[11]，相比于直接用次梯度計算，使用FOBOS算法得到的模型具有更好的預測性能和更符合問題先驗的稀疏結構[11]。

式中：gft為在t時刻損失函數關于權重的梯度,為t時刻的學習率，是在式(10)迭代中正則項前的系數，在具體算法實現中，通常設置。步驟1）等價于標準的無正則項梯度下降過程，式(10)中結果是在第一步結果基礎上進行了微調，一方面希望新的結果盡可能靠近第一步的結果，另一方面還需要盡可能最小化。

2.2.2 利用FOBOS算法求解SGL-FM

根據FOBOS算法，首先將SGL-FM的目標函數分為兩部分:

Liu等在文獻[13]中提出了一種有效算法用于求解含有樹結構信息的正則化問題。本文中的SGL是其中一種特例。如圖1所示，SGL的結構可以表示成p棵樹，每棵樹的根節點包含了第i維特征的一階系數ωi和其在隱空間的特征表示向量vi，子節點分別是其各個分量，SGL相當于對樹的每個節點都添加了范數的約束。

圖1 樹結構的SGLFig. 1 SGL can be represented as tree structures

由文獻[13]，我們在算法1中直接給出了優化式(13)的具體流程。并在算法2中給出了利用FOBOS算法優化SGL-FM的完整流程。

算法1 樹結構正則項的優化算法

1) for i = 1: p do

3) for j = 1: k+1

6) end if

7) end for

10) end if

11) end for

算法2 用于求解SGL-FM的FOBOS算法

1) for k=1:num_epoch %迭代次數

2) 隨機排列所有訓練樣本

3) for i = 1:num_samples %遍歷所有樣本

4) 取出樣本xi

5) 根據式(12)執行隨機梯度下降

6) 根據算法1優化式(13)

7) end for

8) end for

3 實驗與分析

3.1 實驗設置與實驗數據

為了驗證算法的性能，在3個推薦系統數據集上進行了實驗，數據的基本信息如表1所示，其中Movielens的兩個數據均為電影評分數據, Last.fm為音樂推薦數據，所有數據均采用One-Hot-Encoding編碼方式。本文將所有數據均劃分70%作為訓練集，30%作為測試集。

表1 實驗數據Table 1 Experimental datasets

實驗不僅對比了SGL-FM、FM、L1-FM和GLFM等方法。還加入了線性模型Lasso和一般的二階回歸模型（SEC-REG）作為基準對比方法。

所有方法的超參數均采用3折交叉驗證選取。FM、Lasso以及SEC-REG的所有正則化參數均從{0.000 01, 0.000 1, 0.001, 0.01, 0.1, 1}中選取，而SGL-FM、L1-FM和GL-FM的超參數均從{10-6, 10-5,10-4, 10-3}中選取。

實驗以均方根誤差（RMSE）作為評價準則，其計算公式為

式中：na表示線性項系數和二階項系數矩陣中所有分量的個數，即；nz表示這些分量中零元素個數。

3.2 性能與稀疏度分析

圖2～4 分別比較了各個算法在3個數據集上的RMSE和稀疏度隨著k的變化趨勢，可以看出，線性模型Lasso由于未探索變量間的關系，因此效果較差。而由于數據過于稀疏，二階模型SECREG的精度也差于因子分解機類算法。

圖2 Movielens 100 k實驗結果Fig. 2 Results on movielens 100 k

圖3 Movielens 1 m實驗結果Fig. 3 Fig 2. results on movielens 1 m

圖4 Last.fm實驗結果Fig. 4 Results on last.fm

比較SGL-FM與FM，可以看出在Movie-lens數據集上SGL-FM的稀疏度最高達到了20%，雖然FM有更多的參數，但是SGL-FM的性能與FM的性能非常接近，說明SGL-FM能進行有效的特征選擇。在Last.fm數據上，當k＞100時, SGL-FM的稀疏度達到了25%～30%, 雖然SGL-FM的參數更少，但是其性能要優于稀疏度等于0的FM，說明由于數據各個特征的分布不同，不同特征有各自最優的k值，SGL-FM通過特征選擇為各個維度自適應了最佳的k值，去除了冗余的組內特征。圖5 給出了在Last.fm數據集上，當k=100時，SGL-FM求出的特征表示向量所自適應的k值分布，從圖中可以看出，對于Last.fm數據，大部分特征的k值分布在50～70之間，從圖5中也可以看出，當k=60時，FM的效果最好，大于60時，FM的效果開始變差，這是因為參數過多，FM發生了過擬合。比較SGL-FM與GL-FM，SGL-FM由于既實現了組內稀疏又實現了組間稀疏，因此其性能優于只實現了組間稀疏的GL-FM。從稀疏度變化中也可以看出，相比于GL包含了太多的冗余組內特征，SGL能進一步地對組內特征做特征選擇，從而不僅提高稀疏度，更能提高模型的性能。比較SGL-FM與L1-FM，由于L1-FM不包含結構信息且對所有特征無差別選擇，因此，雖然L1-FM有更高的稀疏度，但是其性能比SGL-FM差。

圖5 SGL-FM在Last.fm上自適應的k值分布Fig. 5 The distribution of k selected by SGL-FM

3.3 收斂性分析

當采用隨機梯度優化這種算法時，算法的收斂性是常常需要考慮的問題，由于FM的特殊性，其目標函數關于待求參數非凸[3]，原始文獻[3]中并沒有給出收斂性證明，但是實驗結果表明，FM是收斂的，圖6給出了本文提出的算法和FM在兩個數據集上的迭代過程，可以看出，所有算法均穩定收斂。而且本文提出的SGL-FM，L1-FM以及GLFM具有更快的收斂速率，這是由于SGL-FM等去除了噪音的干擾，因而收斂更快。

圖6 各算法訓練和測試RMSE隨著迭代次數的變化Fig. 6 The training RMSE and testing RMSE w.r.t the iteration times

4 結束語

考慮到因子分解機特殊的二階特征結構，本文結合了GL和Lasso的優點，提出了基于Sparse Group Lasso的因子分解機。同時，作為SGL-FM的特例，我們還導出了L1-FM和GL-FM。不同于一般的二階模型和一般的FM，SGL-FM的目標函數非凸且非光滑，本文引入了FOBOS算法來優化該問題。SGL-FM不僅獲得了比FM更稀疏的解，節省了內存空間，更能通過去除噪音特征，從而提升性能，實驗結果也證明了這一點。

[1]RAO C R, TOUTENBURG H. Linear models[M]. New York: Springer, 1995: 3–18.

[2]ADOMAVICIUS G, TUZHILIN A. Context-aware recommender systems[M]. US: Springer, 2015: 191–226.

[3]RENDLE S. Factorization machines[C]//IEEE 10th International Conference on Data Mining. Sydney, Australia, 2010:995–1000.

[4]RENDLE S. Learning recommender systems with adaptive regularization[C]//Proceedings of the fifth ACM internation-al conference on Web search and data mining. Seattle, USA,2012: 133–142.

[5]TIBSHIRANI R. Regression shrinkage and selection via the lasso[J]. Journal of the royal statistical society, Series B(Methodological), 1996, 73(3): 267–288.

[6]YUAN M, LIN Y. Model selection and estimation in regression with grouped variables[J]. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2006,68(1): 49–67.

[7]SIMON N, FRIEDMAN J, HASTIE T, et al. A sparse-group lasso[J]. Journal of computational and graphical statistics,2013, 22(2): 231–245.

[8]BLONDEL M, FUJINO A, UEDA N, et al. Higher-order factorization machines[C]//Advances in Neural Information Processing Systems. Barcelona, Spain 2016: 3351–3359.

[9]LI M, LIU Z, SMOLA A J, et al. DiFacto: distributed factorization machines[C]//Proceedings of the Ninth ACM International Conference on Web Search and Data Mining. San Francisco, USA, 2016: 377–386.

[10]CHIN W S, YUAN B, YANG M Y, et al. An efficient alternating newton method for learning factorization machines[R].NTU:NTU,2016.

[11]DUCHI J, SINGER Y. Efficient online and batch learning using forward backward splitting[J]. Journal of Machine Learning Research, 2009, 10(12): 2899–2934.

[12]RENDLE S. Factorization machines with libfm[J]. ACM transactions on intelligent systems and technolog, 2012,3(3): 57.

[13]LIU J, YE J. Moreau-Yosida regularization for grouped tree structure learning[C]//Advances in Neural Information Processing Systems. Vancouver, Canada, 2010: 1459–1467.