稀疏化的因子分解機(jī)

郭少成，陳松燦

線性回歸模型因?yàn)槠漭^好的泛化性能及相對(duì)簡(jiǎn)單快速的求解方法而受到廣泛關(guān)注，并已成為統(tǒng)計(jì)機(jī)器學(xué)習(xí)中一類(lèi)最基本的方法[1]。雖然上述線性模型在現(xiàn)實(shí)中有廣泛應(yīng)用。但只有當(dāng)問(wèn)題的輸入呈線性關(guān)系時(shí)，它才會(huì)有較好的效果。另一方面，線性模型本身缺乏對(duì)輸入變量間關(guān)系的探索機(jī)制。由此自然地轉(zhuǎn)向考慮含有二階交叉項(xiàng)的線性模型(此處線性相對(duì)參數(shù)而言)。含有二階交叉項(xiàng)的線性模型考慮了輸入特征間的相互關(guān)系。因此，當(dāng)輸入數(shù)據(jù)的特征間呈非線性關(guān)系，特別是二次關(guān)系時(shí)，其性能優(yōu)于一般的線性模型。

推薦系統(tǒng)近年來(lái)廣受關(guān)注[2]，廣義上的推薦系統(tǒng)就是給用戶推薦物品的系統(tǒng)，它還可具體到一些特定領(lǐng)域，如音樂(lè)、書(shū)籍等。推薦系統(tǒng)的主要任務(wù)是根據(jù)用戶的歷史行為記錄去預(yù)測(cè)用戶未來(lái)可能會(huì)購(gòu)買(mǎi)的物品。從本質(zhì)上說(shuō)就是探索用戶與用戶間以及用戶與物品間的關(guān)系，也就是變量與變量間的關(guān)系。針對(duì)推薦系統(tǒng)，最近S. Rendle等[3]提出了一個(gè)新的二階交叉項(xiàng)模型：因子分解機(jī)(FM)。在FM中，每個(gè)變量xi都對(duì)應(yīng)著一個(gè)在隱空間的k維的向量vi, xi和xj的交叉項(xiàng)系數(shù)等于xi和xj的內(nèi)積，當(dāng)輸入數(shù)據(jù)非常稀疏時(shí)，一般的二階交叉模型無(wú)法學(xué)習(xí)到有效的交叉項(xiàng)系數(shù)。而FM分解了交叉項(xiàng)系數(shù)，這個(gè)特性使得FM能學(xué)習(xí)到數(shù)據(jù)中隱藏的變量間相互關(guān)系[3-4]。因此，F(xiàn)M特別適用于稀疏數(shù)據(jù)。

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

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

Simon等[7]在GL的基礎(chǔ)上提出了基于Sparse Group Lasso（SGL）的線性回歸模型。與GL相同的是它們都對(duì)變量進(jìn)行分組，與GL不同的是,SGL在GL的基礎(chǔ)上，繼續(xù)選擇組內(nèi)重要特征。 因此，SGL能同時(shí)實(shí)現(xiàn)組間稀疏和組內(nèi)稀疏, 而GL只實(shí)現(xiàn)了組間稀疏。SGL結(jié)合了Lasso和GL的優(yōu)點(diǎn)，當(dāng)待求變量存在結(jié)構(gòu)稀疏信息時(shí)，僅使用Lasso會(huì)丟失結(jié)構(gòu)信息，而僅使用GL又會(huì)導(dǎo)致求得冗余的解。基于上述事實(shí)，SGL既保留了GL的結(jié)構(gòu)信息，又具有Lasso的高效特征選擇的能力。

從另一角度看，當(dāng)輸入的數(shù)據(jù)非常稀疏而k選擇較大值時(shí)，F(xiàn)M容易過(guò)擬合。此時(shí)，SGL的組內(nèi)稀疏能通過(guò)特征選擇控制k的大小。而且，不同的特征由于重要程度的不同，其對(duì)應(yīng)的分解向量v的維度也應(yīng)當(dāng)不同，所以，組內(nèi)稀疏在一定程度上通過(guò)特征選擇對(duì)不同維度特征自適應(yīng)了最優(yōu)的k值。

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

1 因子分解機(jī)

1.1 目標(biāo)函數(shù)

FM的基本模型如下：

式(1)也可變形為

FM的目標(biāo)函數(shù)如下：

1.2 優(yōu)化方法

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

式中：η是學(xué)習(xí)率，表示每次梯度更新的步長(zhǎng)。對(duì)于最小平方損失函數(shù)有:

將式(2)對(duì)各個(gè)參數(shù)求導(dǎo)可得[12]：

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

2 基于SGL的因子分解機(jī)

2.1 目標(biāo)函數(shù)

本文通過(guò)對(duì)損失函數(shù)添加SGL的正則項(xiàng)以期望得到含有結(jié)構(gòu)稀疏性質(zhì)的解向量, SGL-FM的目標(biāo)函數(shù)如下:

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

2.2 優(yōu)化方法

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

2.2.1 FOBOS算法

FOBOS是一種基于迭代優(yōu)化的算法框架，主要用來(lái)求解含有正則項(xiàng)的目標(biāo)函數(shù)的優(yōu)化問(wèn)題，特別是一些不可微的正則項(xiàng)如:、（Group Lasso）、等[11]，相比于直接用次梯度計(jì)算，使用FOBOS算法得到的模型具有更好的預(yù)測(cè)性能和更符合問(wèn)題先驗(yàn)的稀疏結(jié)構(gòu)[11]。

式中：gft為在t時(shí)刻損失函數(shù)關(guān)于權(quán)重的梯度,為t時(shí)刻的學(xué)習(xí)率，是在式(10)迭代中正則項(xiàng)前的系數(shù)，在具體算法實(shí)現(xiàn)中，通常設(shè)置。步驟1）等價(jià)于標(biāo)準(zhǔn)的無(wú)正則項(xiàng)梯度下降過(guò)程，式(10)中結(jié)果是在第一步結(jié)果基礎(chǔ)上進(jìn)行了微調(diào)，一方面希望新的結(jié)果盡可能靠近第一步的結(jié)果，另一方面還需要盡可能最小化。

2.2.2 利用FOBOS算法求解SGL-FM

根據(jù)FOBOS算法，首先將SGL-FM的目標(biāo)函數(shù)分為兩部分:

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

圖1 樹(shù)結(jié)構(gòu)的SGLFig. 1 SGL can be represented as tree structures

由文獻(xiàn)[13]，我們?cè)谒惴?中直接給出了優(yōu)化式(13)的具體流程。并在算法2中給出了利用FOBOS算法優(yōu)化SGL-FM的完整流程。

算法1 樹(shù)結(jié)構(gòu)正則項(xiàng)的優(yōu)化算法

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 %迭代次數(shù)

2) 隨機(jī)排列所有訓(xùn)練樣本

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

4) 取出樣本xi

5) 根據(jù)式(12)執(zhí)行隨機(jī)梯度下降

6) 根據(jù)算法1優(yōu)化式(13)

7) end for

8) end for

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)設(shè)置與實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證算法的性能，在3個(gè)推薦系統(tǒng)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，數(shù)據(jù)的基本信息如表1所示，其中Movielens的兩個(gè)數(shù)據(jù)均為電影評(píng)分?jǐn)?shù)據(jù), Last.fm為音樂(lè)推薦數(shù)據(jù)，所有數(shù)據(jù)均采用One-Hot-Encoding編碼方式。本文將所有數(shù)據(jù)均劃分70%作為訓(xùn)練集，30%作為測(cè)試集。

表1 實(shí)驗(yàn)數(shù)據(jù)Table 1 Experimental datasets

實(shí)驗(yàn)不僅對(duì)比了SGL-FM、FM、L1-FM和GLFM等方法。還加入了線性模型Lasso和一般的二階回歸模型（SEC-REG）作為基準(zhǔn)對(duì)比方法。

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

實(shí)驗(yàn)以均方根誤差（RMSE）作為評(píng)價(jià)準(zhǔn)則，其計(jì)算公式為

式中：na表示線性項(xiàng)系數(shù)和二階項(xiàng)系數(shù)矩陣中所有分量的個(gè)數(shù)，即；nz表示這些分量中零元素個(gè)數(shù)。

3.2 性能與稀疏度分析

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

圖2 Movielens 100 k實(shí)驗(yàn)結(jié)果Fig. 2 Results on movielens 100 k

圖3 Movielens 1 m實(shí)驗(yàn)結(jié)果Fig. 3 Fig 2. results on movielens 1 m

圖4 Last.fm實(shí)驗(yàn)結(jié)果Fig. 4 Results on last.fm

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

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

3.3 收斂性分析

當(dāng)采用隨機(jī)梯度優(yōu)化這種算法時(shí)，算法的收斂性是常常需要考慮的問(wèn)題，由于FM的特殊性，其目標(biāo)函數(shù)關(guān)于待求參數(shù)非凸[3]，原始文獻(xiàn)[3]中并沒(méi)有給出收斂性證明，但是實(shí)驗(yàn)結(jié)果表明，F(xiàn)M是收斂的，圖6給出了本文提出的算法和FM在兩個(gè)數(shù)據(jù)集上的迭代過(guò)程，可以看出，所有算法均穩(wěn)定收斂。而且本文提出的SGL-FM，L1-FM以及GLFM具有更快的收斂速率，這是由于SGL-FM等去除了噪音的干擾，因而收斂更快。

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

4 結(jié)束語(yǔ)

考慮到因子分解機(jī)特殊的二階特征結(jié)構(gòu)，本文結(jié)合了GL和Lasso的優(yōu)點(diǎn)，提出了基于Sparse Group Lasso的因子分解機(jī)。同時(shí)，作為SGL-FM的特例，我們還導(dǎo)出了L1-FM和GL-FM。不同于一般的二階模型和一般的FM，SGL-FM的目標(biāo)函數(shù)非凸且非光滑，本文引入了FOBOS算法來(lái)優(yōu)化該問(wèn)題。SGL-FM不僅獲得了比FM更稀疏的解，節(jié)省了內(nèi)存空間，更能通過(guò)去除噪音特征，從而提升性能，實(shí)驗(yàn)結(jié)果也證明了這一點(diǎn)。

[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.