• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2018-01-17 09:07:36郭少成陳松燦
      智能系統(tǒng)學(xué)報(bào) 2017年6期
      關(guān)鍵詞:特征選擇正則二階

      郭少成,陳松燦

      線性回歸模型因?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.

      猜你喜歡
      特征選擇正則二階
      一類(lèi)二階迭代泛函微分方程的周期解
      剩余有限Minimax可解群的4階正則自同構(gòu)
      一類(lèi)二階中立隨機(jī)偏微分方程的吸引集和擬不變集
      二階線性微分方程的解法
      類(lèi)似于VNL環(huán)的環(huán)
      一類(lèi)二階中立隨機(jī)偏微分方程的吸引集和擬不變集
      Kmeans 應(yīng)用與特征選擇
      電子制作(2017年23期)2017-02-02 07:17:06
      聯(lián)合互信息水下目標(biāo)特征選擇算法
      有限秩的可解群的正則自同構(gòu)
      基于特征選擇和RRVPMCD的滾動(dòng)軸承故障診斷方法
      安溪县| 屏南县| 垣曲县| 贡觉县| 泗洪县| 峨眉山市| 元阳县| 宁蒗| 华容县| 东源县| 洪泽县| 平昌县| 温宿县| 七台河市| 宁阳县| 霞浦县| 嵩明县| 西林县| 荣成市| 沁阳市| 铅山县| 辽阳县| 中西区| 沾益县| 揭阳市| 文昌市| 泽州县| 镇康县| 永吉县| 资源县| 阿克苏市| 荥阳市| 凤阳县| 萨迦县| 沈阳市| 随州市| 梁平县| 牡丹江市| 余庆县| 镇雄县| 边坝县|