因子分解機模型研究綜述?

趙衎衎,張良富,張 靜,李翠平,陳 紅

1(中國人民大學 信息學院,北京 100872)

2(數(shù)據(jù)工程與知識工程教育部重點實驗室(中國人民大學),北京 100872)

隨著云計算、大數(shù)據(jù)、物聯(lián)網(wǎng)等技術(shù)的迅猛發(fā)展,互聯(lián)網(wǎng)的各類服務(wù)應用層出不窮,數(shù)據(jù)規(guī)模呈現(xiàn)指數(shù)級增長.根據(jù)國際數(shù)據(jù)集團 IDC的 2012年報告顯示:到 2020年,全球數(shù)據(jù)總量預計將達到 2011年的 22倍,即35.2ZB[1].雖然大數(shù)據(jù)中蘊含著豐富的價值和巨大的潛力,但同時也使得信息過載問題越發(fā)嚴重.在此背景下,推薦系統(tǒng)誕生.作為解決信息過載問題的有效方法,推薦系統(tǒng)已經(jīng)成為學術(shù)界和工業(yè)界的關(guān)注熱點并得到廣泛應用,形成了眾多相關(guān)研究成果.一般地,推薦系統(tǒng)從用戶歷史數(shù)據(jù)中自動學習用戶的需求和興趣,通過多樣化的推薦算法從海量數(shù)據(jù)中挖掘出用戶感興趣的項目(如信息、服務(wù)和物品等).目前,推薦系統(tǒng)已經(jīng)在很多領(lǐng)域得到成功應用,包括電子商務(wù)(亞馬遜、阿里巴巴、京東等)、信息檢索(如 Google、百度等)、社交網(wǎng)絡(luò)服務(wù)(如Facebook、QQ、微博等)、位置服務(wù)(如Foursquare、Yelp、大眾點評等)、新聞推薦(如今日頭條、Google news等)、電影推薦(如Netflix、豆瓣等)等[2].

從信息過濾的角度來看,傳統(tǒng)的推薦系統(tǒng)主要分為基于內(nèi)容推薦系統(tǒng)、協(xié)同過濾推薦系統(tǒng)和混合推薦系統(tǒng).其中,最經(jīng)典的算法非協(xié)同過濾算法莫屬,而矩陣分解在重要問題上出色的預測能力,讓其成為協(xié)同過濾算法中應用最為廣泛的模型.在矩陣分解模型中,數(shù)據(jù)被組織為用戶-物品矩陣,矩陣中每個值被編碼成0/1或真實評分,以表示用戶與物品間的交互行為.矩陣分解模型的目標在于從用戶-物品矩陣中分別學習每個用戶和物品的隱因子向量,最終學習得到的這種隱因子向量可用于近似重建可觀察的交互值,并預測缺失或未知交互值.

在更多上下文特征可獲取的今天,隨著多種上下文特征引入建模,傳統(tǒng)矩陣分解方法的擴展研究快速展開,使其能夠?qū)⒏嗌舷挛囊蛩匾肽Ｐ?然而大多數(shù)基于上下文特征的分解方法都有其特定的應用場景,相比傳統(tǒng)的矩陣分解模型而言,算法泛化能力大大降低.在此背景下,文獻[3]提出了著名的因子分解機模型.

因子分解機(factorization machines,簡稱FM)是一個通用的模型,其在Movielens數(shù)據(jù)集上的數(shù)據(jù)組織形式如圖1所示,每個數(shù)據(jù)實例中的所有特征(用戶、電影、當前用戶對其他電影評分、觀看時間、當前用戶觀看的上一部電影)被組織成一個向量Xi,并對應一個目標值yi,特征之間互相平等.憑借該模型,Rendle在KDD Cup 2012中分別取得Track1第2名和Track2第3名的成績.與原有的分解方法相比,該模型將特征工程的一般性與分解模型的優(yōu)越性相融合.它能夠通過特征工程模擬絕大多數(shù)的特定分解模型,如 SVD++[4],FPMC[5],timeSVD++[6],BPTF[7],PITF[8]等.

Fig.1 Data organization example of FM on Movielens dataset圖1 基于Movielens的FM數(shù)據(jù)組織示例

本文首先對因子分解機模型進行溯源,探討因子分解機模型和其他流行的基于上下文的分解方法的關(guān)系,指出因子分解機模型能夠通過其強大的泛化能力自然地模擬這些特定場景下的分解算法;然后綜述近年來涌現(xiàn)的針對不同問題的各種因子分解機模型的變種,從模型的準確性及性能角度出發(fā),將其分為基于準確性的優(yōu)化和基于性能的擴展;接著,從獨立于問題模型的角度綜述適用于因子分解機模型求解的代表性優(yōu)化方法,指出每種優(yōu)化方法的優(yōu)勢和不足;最后,本文分析了現(xiàn)有因子分解機模型仍然存在的問題,針對這些問題,提出了可能的解決思路,并對未來研究方向進行了展望.

本節(jié)第 1節(jié)對因子分解機模型的提出進行溯源,指出分解方法如何從傳統(tǒng)矩陣分解一步步發(fā)展為因子分解機模型.第 2節(jié)綜述現(xiàn)有因子分解機模型及其變種.第 3節(jié)綜述現(xiàn)階段適用于因子分解機模型求解的代表性優(yōu)化算法.第 4節(jié)對因子分解機模型研究目前仍存在的問題進行分析,指出可能的解決思路,并對未來的研究方向進行展望.最后,在第5節(jié)總結(jié)本文.

1 因子分解機模型溯源

矩陣分解模型作為推薦算法的研究熱點,已經(jīng)在推薦系統(tǒng)相關(guān)領(lǐng)域得到大規(guī)模的應用.該算法的核心思想是:把推薦問題轉(zhuǎn)化為矩陣完全分解問題,把稀疏用戶評分矩陣映射到給定的用戶集合和項目集合,通過矩陣運算預測缺省評分,反映用戶對項目的潛在偏好,按照用戶對未評分項目的預測評分值對用戶進行推薦[9].矩陣分解算法能夠有效降低高維數(shù)據(jù)稀疏性,并且對噪聲和冗余不敏感,擁有良好的可擴展性,但是可解釋性較差,計算復雜度高[10].

傳統(tǒng)的矩陣分解算法有奇異值分解(SVD)[11]、非負矩陣分解(NMF)[12]、概率矩陣分解(PMF)[13]等.這些算法的共同特點是將高維矩陣分解成為 2個或多個低維矩陣的乘積形式,便于在一個低維空間研究高維數(shù)據(jù)的性質(zhì).PureSVD[14]直接對用戶評分矩陣做 SVD分解,未知值采用 0值填充,可以快速獲取用戶對項目預測評分.但是SVD允許分解出現(xiàn)負值,這在物理上缺乏可解釋性.與SVD相比,NMF可以保證分解所得矩陣的每個元素均是正值,這使得NMF具有直觀的物理意義.不同于SVD和NMF,PMF從概率的角度預測用戶評分,假設(shè)用戶和商品的特征向量矩陣都符合高斯分布,基于這個假設(shè),把用戶偏好問題轉(zhuǎn)換為概率組合問題,從更深層次討論了矩陣分解的概率解釋.

在大數(shù)據(jù)時代移動設(shè)備智能化的今天,上下文因素的獲取變得極為容易,例如用戶的人口統(tǒng)計信息、物品的本身屬性、時間、位置、社交網(wǎng)絡(luò)等.早在2005年,文獻[15]研究指出,把上下文信息融入推薦系統(tǒng)將有利于提高推薦精確度.因此,研究者考慮基于豐富的上下文信息提升傳統(tǒng)用戶-物品矩陣分解模型的準確率.文獻[16]把位置上下文引入推薦系統(tǒng),引入高維SVD(HOSVD),很好地處理了用戶-位置-活動三維張量.文獻[6]把時間上下文引入建模,提出一種timeSVD++算法,提高預測用戶電影評分的精準度.文獻[17]將聯(lián)合PMF(UPMF)引入上下文廣告推薦,把用戶評分矩陣分解為用戶、廣告和網(wǎng)頁特征矩陣的乘積.

上述推薦算法分別將不同的上下文因素融入分解模型中,提高了特定場景下的推薦精準度,然而這種基于特定上下文特征的分解方法其泛化能力較低,沒有一個方法能將大多數(shù)上下文特征以特征工程的方式融入分解模型中去.在此背景下,文獻[3]提出了著名的因子分解機模型.接下來,第1.1節(jié)將對因子分解機模型的數(shù)據(jù)組織形式和模型表達式進行說明.在后續(xù)章節(jié)中,給出如何使用因子分解機模型模擬其他特定模型.

1.1 標準因子分解機模型

假設(shè)一個預測問題的訓練數(shù)據(jù)D=(X,y),其中,X∈?n×p表示當前數(shù)據(jù)集D有n個實例,每個實例由一個維度為p的稀疏向量組成,y∈?n則表示n個實例對應的真實標簽,(Xi,yi)表示第i個實例Xi對應標簽為yi.

FM能夠?qū)斎胗柧毤疍=(X,y)不同特征間的交互進行分解建模,其d階交互模型表示見公式(1).

然而,隨著特征交互階數(shù)的增加,模型參數(shù)規(guī)模成指數(shù)級增長,導致計算復雜度不可接受.通常在實際應用時,二階FM模型已有較好的表現(xiàn),故稱二階FM為標準FM模型.將公式(1)簡化為標準FM,其表達式見公式(2).

與多項式回歸的不同之處在于:特征的兩兩交互并不由一個獨立的參數(shù)wj,j′來建模,而是使用兩個分解的隱因子向量來估計交互參數(shù)wj,j′的值,即有,這使得FM能夠在高稀疏數(shù)據(jù)上有較好的表現(xiàn).

1.2 矩陣分解與因子分解機模型

假設(shè)當前訓練數(shù)據(jù)包含m個用戶和n個物品的交互.對于傳統(tǒng)矩陣分解,構(gòu)造用戶-物品交互矩陣Rm×n,通過矩陣運算預測缺省評分,完成對用戶隱因子矩陣U和物品隱因子矩陣V的學習:

然而,這種最基本的矩陣分解思想在實際情況下并不能很好地度量用戶和物品的交互.用戶之間是具有差異性的,例如有的用戶偏向給出物品較高的評分.同樣的,這種情況也會出現(xiàn)在物品中.通過對公式(3)加入用戶/物品和全局偏置項,得到一個更加合理的分解模型:

同樣地,使用上述例子構(gòu)建基于標準 FM 模型的訓練集,形成一個指示矩陣X∈R|U|×|V|,每個數(shù)據(jù)實例x由|U|+|V|維稀疏向量構(gòu)成.假設(shè)當前數(shù)據(jù)實例表示用戶u與物品i的交互,則該向量x僅第u和|U|+i個位置為1,其他均為0:

在這種情況下,FM與矩陣分解模型表達式相同:

1.3 SVD++與因子分解機模型

假設(shè)訓練集由m個用戶、n個物品以及上下文特征L組成,其中,特征L不為0的列數(shù)為c.標準FM數(shù)據(jù)組織格式可表示如下:

基于上述場景,標準FM模型可表示如公式(6):

如果{l1,l2,…,lm}表示用戶對物品的隱式反饋特征,那么公式(7)前5項與完整SVD++模型完全相同.

1.4 兩兩交互張量分解與因子分解機模型

假設(shè)訓練數(shù)據(jù)包含3類特征,分別為用戶、物品和物品對應的標簽,與第1.3節(jié)中應用場景類似,其FM數(shù)據(jù)組織形式可表示如下:

兩兩交互張量分解模型(pairwise interaction tensor factorization,簡稱PITF)可表示如公式(7):

從上式可以看出:與標準FM模型相同特征共享隱因子向量不同,PITF中,每個特征在與不同類別特征交互時,其對應的隱因子參數(shù)是不同的.

1.5 支持向量機與因子分解機模型

假設(shè)訓練數(shù)據(jù)中,每個數(shù)據(jù)實例包含p維特征,基于線性核的支持向量機可表示如公式(8):

顯然可見,線性核支持向量機與一階 FM 模型(不存在特征間兩兩交互)具有相同表達式.繼而,使用非奇次多項式核替代線性核,支持向量機在特征二階交互時可以表示為公式(9):

由公式(9)可知,多項式核使得支持向量機能夠?qū)μ卣鏖g更高階的交互進行建模.與標準FM相比,兩個模型都能夠?qū)μ卣鏖g高階交互進行建模,不同之處在于:多項式核 SVM 所有的交互參數(shù)都是完全相互獨立的,這點與多項式回歸相同;而標準 FM 的交互參數(shù)通過分解學習得到,并且由于每個特征對應的隱因子參數(shù)在與任何其他特征交互時是共享的,因此進一步降低了模型復雜度.此外,通常對非線性核 SVM,需要轉(zhuǎn)化為其對偶問題進行求解;而標準FM可以直接進行優(yōu)化.

除去上述分解模型,標準 FM 還能高度模擬其他特定上下文分解模型,例如 FPMC(factorizing personalized markov chains)[5]、BPTF(Bayesian probabilistic tensor factorization)[7]、TimeSVD++[6]、最近鄰模型[18]以及基于用戶(物品)屬性上下文模型[19,20].

2 因子分解機模型研究進展

雖然FM已經(jīng)被廣泛應用于預測、推薦等領(lǐng)域,且通常都能夠獲得較好的結(jié)果,然而在具體實踐中仍存在大量挑戰(zhàn).從模型的準確率和效率性能兩個方向出發(fā),FM存在的問題可總結(jié)如下.

· 在準確率方面

(1) 一般具體的 FM 模型的應用中取二階交互,即特征的交互僅限兩兩相互交互建模.雖然理論上可以證明隨著交互度的增加,FM模型的時間復雜度呈線性增長趨勢,但是由于 FM數(shù)據(jù)表示的高維稀疏性,其高階交互的線性時間復雜度在現(xiàn)實應用中亦難以接受;

(2) 神經(jīng)網(wǎng)絡(luò)在特征的高階非線性交互建模及高階特征表示方面具有較好的效果,而標準 FM 在特征的低階交互建模方面有一定的優(yōu)勢,兩者的融合必定會取得更好的模型性能;

(3) FM 的成功很大程度源于它對特征間的交互行為進行了建模,這種交互的加入更加符合事物的規(guī)律,有效地提升了算法的性能.然而在現(xiàn)實生活中,并不是所有的特征交互都能得到正向的增益,噪音特征的加入甚至會損害模型的準確性,因此,如何對特征交互加以甄別,進一步提升算法的性能和效率,仍是一個巨大挑戰(zhàn);

(4) 由于FM表達式的整體非凸性,標準 FM基于梯度的優(yōu)化,其步長及正則化超參的選擇都會影響到模型訓練的收斂.如何規(guī)避此類超參初值選擇對模型收斂的影響、如何重構(gòu)模型使得其目標函數(shù)整體呈現(xiàn)凸優(yōu)化,有一定的困難;

(5) 在標準FM中,所有特征之間相互平等,類別和層次信息無法得到體現(xiàn).如何將這些信息融入模型,進一步提升模型性能,是一個問題.

· 在模型訓練效率和性能方面

由于FM模型和數(shù)據(jù)組織形式的高維稀疏性,在大數(shù)據(jù)環(huán)境下:一方面,更多的上下文特征不斷涌入;另一方面,數(shù)據(jù)規(guī)模不斷增加.兩者共同導致因子分解機的模型復雜度增加和訓練數(shù)據(jù)增長,傳統(tǒng)的單機環(huán)境已無法滿足其需求(內(nèi)存無法全部存儲且計算效率低下).因此,如何對模型的學習進行擴展以提高其效率變得尤為迫切.

針對上述問題,研究者從不同角度給出了解決方案.

2.1 模型準確性提升

2.1.1 高階交互

文獻[3]提出:標準 FM 模型可以適用于任意階特征交互場景,其模型表達式如公式(1)所示.然而,一般情況下只使用d=2,即兩兩特征交互.原因有二.

· 其一,同階交互時,在建模當前特征在與其他特征的交互過程中,當前特征對應的分解隱因子向量是共享的.然而當存在多階特征交互時,不同階特征對應的隱因子向量是不共享的,模型的參數(shù)增長量會隨著特征維度的大小線性增長.由于因子分解機模型將用戶、物品本身也作為特征平等對待,因此在實際工業(yè)環(huán)境下,其特征維度會非常之大.當特征的高階交互存在時,模型參數(shù)的增長會非常迅速,導致存儲及計算資源指數(shù)級增加,限制了模型的推廣.例如,假設(shè)特征維數(shù)維m,不同階分解所得隱向量的維度均為k,忽略全局偏置和單個特征對應權(quán)重.當d=3時,與兩兩特征交互相比,新增模型參數(shù);

· 其二,文獻[3,21-23]僅給出了二階特征交互下模型的4種優(yōu)化策略——隨機梯度下降、坐標下降、馬爾可夫蒙特卡洛法和基于自適應正則的隨機梯度下降算法.

一般地,高階交互的加入能夠使模型的性能進一步提高.針對標準 FM 模型在高階交互中存在的問題,研究者給出了自己的方案.

文獻[24]直接擴展二階因子分解模型至三階,并沿用二階的交互項表達式變換技巧對三階交互項進行了優(yōu)化.相比原始的三階交互,時間復雜度降低.最后使用隨機梯度下降學習得到最終模型.然而,該三階模型依然未解決能夠向更高階通用擴展的問題,且模型復雜度依然隨階按倍數(shù)增長.相似的,文獻[25]提出一種三階因子分解模型,與標準因子分解機模型不同,作者使用 ANOVA核建模特征間的三階交互,使用坐標下降法對三階ANOVA核因子分解機模型優(yōu)化.

與上述只達到三階交互的模型不同,文獻[26]提出一種任意高階共享因子分解模型.作者同樣使用了ANOVA核對其進行重構(gòu).ANOVA核通常被用來建模特征間的交互,與因子分解機模型的交互項相似.ANOVA核的特性使得高階的 ANOVA核可以遞歸轉(zhuǎn)化為對應的低一階交互核.因此,作者使用非齊次 ANOVA核的特性,遞歸地從高到低建模不同階特征交互過程,在該核中,同一特征的隱因子向量在不同階的特征交互中是可共享的.此外,不同階的交互對模型的影響可使用權(quán)重參數(shù)建模.就如何高效地優(yōu)化高階共享因子分解機模型,作者提出了一種動態(tài)規(guī)劃算法,用于計算不同階交互對模型的貢獻值和計算梯度.由于核的遞歸特性,該動態(tài)規(guī)劃算法能夠避免許多重復性計算.此外,作者使用基于隨機梯度和坐標下降這兩種優(yōu)化算法對模型進行了優(yōu)化.

文獻[27]提出一種基于多任務(wù)多視圖(multi-task multi-view)的高階因子分解機模型.多任務(wù)多視圖學習假設(shè)一個大的任務(wù)能夠分解為多個子任務(wù),每個子任務(wù)則由多個視圖構(gòu)成.其最終目標則是根據(jù)所有子任務(wù)中的訓練集信息,利用多個視圖的交互,學習得到一個非線性的分類或回歸模型.在多任務(wù)多視圖中,整個任務(wù)可以看做一個張量,每個視圖和子任務(wù)為張量的一個維度.然而,由于訓練數(shù)據(jù)的稀疏性,無需物理構(gòu)建一個張量訓練集合.作者首先摒棄了直接使用單個參數(shù)來建模某個特定交互,轉(zhuǎn)而采用使用 CP分解(canonical polyadic decomposition),大大降低了參數(shù)規(guī)模.進而分析若直接使用多視圖交互建模,最終只能得到一個基于滿(最高)階交互的非線性模型的限制,通過給每個視圖中添加一個常量為 1的列,使得不同視圖間的交互可以由原來的滿階交互變?yōu)閺囊浑A到滿階的不同階交互并存.與標準高階 FM 的不同階交互由不同參數(shù)負責相比,這種基于多任務(wù)多視圖的高階FM的不同階交互的參數(shù)是共享的.這種機制大大減少了參數(shù)的規(guī)模,與上述基于ANOVA核的高階FM有異曲同工之妙.最后,由于多任務(wù)維度的存在,經(jīng)過基于坐標下降的CP分解,該維度生成與其他視圖的交互隱因子矩陣對應的特定任務(wù)權(quán)重矩陣.即,用戶針對不同的任務(wù)(話題)具有不同的喜好程度(權(quán)重).

文獻[28]在文獻[27]的基礎(chǔ)上提出一種新的基于多視圖的結(jié)構(gòu)因子分解機模型.在文獻[27]中,一個視圖中僅包含一項實體,由一個向量表示,且視圖間實體不存在重疊.而在文獻[28]中,作者改變思路,文中每個視圖可包含若干項實體,因此,視圖以一個向量的形式存在,且不同實體間允許存在實體重疊.由于不同視圖間存在實體重疊,因此該重疊的實體在進行 CP分解時,所生成的隱因子矩陣可共享.此外,作者采用了與文獻[27]中相同的技巧,使得同一視圖內(nèi)可進行不同階交互隱因子共享.

文獻[29]提出多視圖分解機(multi-view machine,簡稱MVM),與文獻[27]類似,作者使用基于CP分解的多視圖來完成高階FM的建模,并且采用與之相同的技巧完成不同階的交互隱因子的共享.此外,作者認為:并非所有的高階交互都是有其物理意義的,且高階交互通常難以解釋,因此,作者提出通過對原始的全部視圖進行分割,形成多個視圖集合,使用MVM對多個視圖集合分別學習的方法來降低交互階數(shù).在CP分解過程中,使用隨機梯度下降法來優(yōu)化目標函數(shù).最后,作者基于Spark完成了MVM的分布式實現(xiàn).

2.1.2 神經(jīng)網(wǎng)絡(luò)與因子分解機

隨著神經(jīng)網(wǎng)絡(luò)和深度學習的興起,研究者考慮如何將因子分解機與神經(jīng)網(wǎng)絡(luò)相結(jié)合,提高最終模型的性能.文獻[30,31]提出使用神經(jīng)網(wǎng)絡(luò)完成用戶/物品特征隱因子表示和學習,然后將其串聯(lián)成一個單獨特征向量,最后基于該特征向量使用標準FM完成模型的訓練.與文獻[30,31]先神經(jīng)網(wǎng)絡(luò)學習特征表示后因子分解機訓練模型的方式不同,文獻[32-36]均利用因子分解機模型作為神經(jīng)網(wǎng)絡(luò)的輸入進行特征的高階非線性交互建模.其中,文獻[32]提出一種基于因子分解機和神經(jīng)網(wǎng)絡(luò)的高階非線性特征交互模型,簡稱 FNN.具體地,在使用神經(jīng)網(wǎng)絡(luò)進行點擊率預測時,FNN并未直接使用稀疏的0-1向量特征,而是考慮先利用標準FM基于隨機梯度下降法預訓練得到模型所包含的全局偏置、每個特征對應的一階權(quán)重和二階交互因子向量,然后將上述全部模型參數(shù)作為隱含層的輸入,使用神經(jīng)網(wǎng)絡(luò)方法生成最終模型.該方法能夠?qū)藴?FM 模型所生成的參數(shù)進行高階非線性交互,提升神經(jīng)網(wǎng)絡(luò)方法的預測能力.與文獻[32]類似,文獻[33]提出一種神經(jīng)網(wǎng)絡(luò)與非線性因子分解機模型的混合模型NLFM.NLFM基于標準 FM模型的全部參數(shù)(除去全局偏置參數(shù)),使用神經(jīng)網(wǎng)絡(luò)完成后續(xù)的訓練.然而,與FNN將模型參數(shù)作為隱含層的輸入不同,NLFM首先將模型參數(shù)輸入一個嵌入層,生成并輸出標準FM模型中每個特征對應的一階交互和與其他特征之間的二階交互,然后將嵌入層的輸出作為隱含層的輸入,進而利用神經(jīng)網(wǎng)絡(luò)完成訓練.為了提高最終模型預測能力,文獻[33]進一步提出使用堆棧去噪自動編碼器對原始用戶/物品及其上下文特征進行降維,降低數(shù)據(jù)稀疏度.在生成的高級特征基礎(chǔ)上,使用 NLFM 進行模型訓練.與文獻[32,33]不同,文獻[34-36]僅對特征的交互因子使用神經(jīng)網(wǎng)絡(luò)方法進行高階非線性交互建模.其中,文獻[34]基于Wide&Deep網(wǎng)絡(luò),結(jié)合因子分解機和深度學習,提出一種基于深度網(wǎng)絡(luò)的因子分解機模型DeepFM進行廣告點擊率預測.具體地,DeepFM對共享二階交互因子矩陣分別采用標準FM和深度神經(jīng)網(wǎng)絡(luò)建模二階特征交互和高階特征交互,然后基于因子分解機模型輸出和深度神經(jīng)網(wǎng)絡(luò)輸出結(jié)果的和完成最終的預測.文獻[35]研究了稀疏輸入數(shù)據(jù)情況下的推薦問題,基于因子分解機提出了一種神經(jīng)因子分解機模型 NFM.NFM 保持因子分解機模型的全局偏置和特征的一階權(quán)重形式不變,將特征交互因子作為嵌入層,在嵌入層上增加一個雙線性交互池化操作,即因子分解機模型特征二階交互部分,然后將池化的輸出作為隱含層的輸入實現(xiàn)特征間的高階非線性交互.值得注意的是:雙線性交互池化操作的加入,使得 NFM 能在更少隱含層的情況下獲得更好的預測能力,而且參數(shù)更少,訓練更加容易.文獻[36]通過擴展 NFM 模型提出一種注意力因子分解機模型 AFM,通過將注意力機制引入雙線性交互池化操作中,進一步提升NFM的表示能力和可解釋性.

2.1.3 交互特征選擇

在標準FM模型中,特征間的交互涵蓋整個特征集.然而在真實場景下,有些特征是不相關(guān)的,它們的交互是沒有任何物理意義且不可解釋的,甚至由于噪音特征的引入損害了預測結(jié)果.換言之,并非所有的特征交互都會對最終的預測值起到正向增益的效果.基于此,研究者提出對特征交互進行選擇以提升模型性能和效率.

文獻[37]提出了一種基于梯度Boosting的貪婪的特征交互選擇方法,并與標準FM模型整合為一個統(tǒng)一的框架——GBFM.具體地,在每次迭代中,使用一個貪婪的梯度Boosting方法選擇一組交互特征,基于上一步預測與真實值的殘差來優(yōu)化所選交互特征的隱因子向量.在特征選擇過程中,作者采用一種多層貪婪啟發(fā)式算法,在每層總是選擇使得目標下降最快的一類特征.實驗證明,GBFM 很好地提升了模型的性能.然而,這種基于梯度Boosting的特征交互選擇是有問題的:迭代的交互特征選擇機制意味著不同次迭代可能選擇重復的特征,但重復特征在不同次迭代所對應的隱因子向量是不同的,從而一定程度上導致模型參數(shù)規(guī)模的增大,使得訓練效率降低.

與迭代的貪婪特征選擇機制不同,文獻[38]僅僅考慮選擇有用的用戶和物品之間的交互.具體地,作者首先將標準FM模型中的交互隱因子矩陣按照特征劃分為用戶隱因子矩陣和物品隱因子矩陣,通過矩陣變換重構(gòu)標準 FM 模型;然后在損失函數(shù)中分別對用戶和物品隱因子矩陣加組稀疏正則項,達到移除無關(guān)用戶和物品特征的效果;最后使用塊坐標下降學習得到用戶和物品隱因子矩陣.這種特征選擇方法最大的問題在于:它限制了FM模型基于特征工程的強大泛化性,導致上下文特征無法參與建模.

文獻[39]認為基于梯度Boosting和稀疏正則的方法在大規(guī)模高階特征交互選擇時是不可行的,提出一種可進行任意階交互特征選擇的貝葉斯回歸因子分解機模型.具體地,使用超圖來表示特征間的任意階交互關(guān)系,其中:特征為頂點,特征的任意階交互子集為超邊,交互特征選擇由隨機超圖上的先驗分布指導完成.與上述兩種方法相比,該方法具有更強的泛化性.

2.1.4 概率模型

在標準 FM模型中,作者首先給出了包括隨機梯度下降[3]和交替最小二乘[21](坐標下降)在內(nèi)的兩種優(yōu)化策略.這兩種策略在優(yōu)化時,其超參的初始值都需要用戶指定.然而,由于FM模型的非凸性,這種隨機指定超參的方式很可能會使得模型陷入一個局部最優(yōu)解;而 FM 模型在真實環(huán)境下因為模型參數(shù)高維且數(shù)據(jù)規(guī)模巨大,訓練一次是非常耗時的.因此,得到一個局部最優(yōu)解再重新訓練,這無疑是不可接受的.在不考慮對模型本身不作出修正時,研究者考慮從概率模型角度出發(fā),得到一個無需手動指定超參的概率FM模型.

文獻[22]率先提出一個概率FM模型,該模型在標準FM概率圖模型基礎(chǔ)上添加了一層對超參的超先驗:對除了全局偏置外所有模型參數(shù)的正太分布所對應的平均值添加高斯超先驗,對所有模型參數(shù)的正太分布所對應的準確率添加伽馬超先驗,最后利用吉布斯抽樣和共軛先驗分布求得模型最優(yōu)參數(shù).文獻[40]提出一個基于非線性上下文協(xié)同過濾方法:高斯過程FM(GPFM),GPFM能夠無縫利用用戶對物品的顯式和隱式行為.具體地,作者使用高斯過程,對每一個用戶生成高斯先驗,針對用戶的顯式和隱式行為生成高斯似然,在此基礎(chǔ)上計算得到邊緣似然,最終使用隨機梯度下降對負的對數(shù)邊緣似然最小化函數(shù)進行優(yōu)化,得到最優(yōu)模型參數(shù).文獻[41]認為文獻[22]中所提數(shù)據(jù)服從正態(tài)分布,對于某些使用整數(shù)評分的場景是不合適的,且在選擇隱因子向量維度時需要進行交叉驗證,這無疑是非常耗時的.基于這兩個問題,作者對整數(shù)評分場景使用伽馬分布,并使用一個伽馬過程自動搜尋一個理想的隱因子向量維度,該過程并不需要交叉驗證.文獻[42]首先提出在點擊率預測這種高度稀疏數(shù)據(jù)上利用拉普拉斯分布代替?zhèn)鹘y(tǒng)的高斯分布.與高斯分布相比,拉普拉斯分布更加適合于高維稀疏數(shù)據(jù)并辨別度量相關(guān)特征的關(guān)系.由于拉普拉斯分布是非平滑的,基于貝葉斯推論的 FM 模型難以優(yōu)化,而拉普拉斯分布能夠使用混合高斯分布來模擬,最終使用馬爾可夫蒙特卡洛方法對基于拉普拉斯分布的稀疏FM模型進行優(yōu)化.

2.1.5 凸優(yōu)化及在線學習

為了從根本上解決標準FM模型的非凸問題并保持保證兩階特征交互矩陣的低秩特性,研究者給出了多種方案[43-46].文獻[43]提出一種針對二階特征交互因子矩陣改進的凸因子分解機模型 CFM.具體地,CFM 保持標準FM模型的一階特征權(quán)重參數(shù)不變,將原有的二階特征交互因子矩陣V∈?p×k重構(gòu)為Z∈?p×p.雖然表面上Z的參數(shù)規(guī)模大于V,但是CFM并不物理存儲Z,而是通過矩陣特征分解的方式將對稱矩陣Z分解為多個秩為1的矩陣的和.相比標準FM模型需要指定二階特征交互隱因子矩陣V的維度k,CFM在最終的優(yōu)化目標函數(shù)中使用核范數(shù)保證分解的低秩特性,無需用戶手動設(shè)置.文獻[44]將標準FM模型中的全局偏置參數(shù)糅合至特征的一階權(quán)重,形成一個增廣向量,并對二階特征交互隱因子矩陣采用與文獻[43]類似的表示.不同的是:文獻[43]對所有的特征二階交互進行建模并采用塊坐標下降的方法對目標函數(shù)進行優(yōu)化;而文獻[44]僅考慮不同特征間的二階交互(不考慮順序),采用 Hazan算法對模型參數(shù)進行更新.總結(jié)文獻[43,44]可知:兩者僅對二階特征交互隱因子矩陣進行變換,最終得到一個一階特征權(quán)重參數(shù)和二階特征交互隱因子矩陣分別優(yōu)化的凸因子分解機模型.基于上述文獻,文獻[45]進一步提出一種可在線學習的凸因子分解機模型 OCCFM.OCCFM 將因子分解機中的全局偏置、一階特征權(quán)重和二階特征交互隱因子矩陣等所有模型參數(shù)全部糅合,形成一個增廣參數(shù)矩陣,文獻[46]采用與之相同的凸因子分解機模型表示.在模型優(yōu)化時,對所有模型參數(shù)統(tǒng)一進行更新.由于因子分解機模型獨特的數(shù)據(jù)結(jié)構(gòu)表示,隨著越來越多上下文特征的加入,其參數(shù)規(guī)模不斷增加,導致模型面臨所有分解方法都存在的巨大挑戰(zhàn)——新數(shù)據(jù)到來后模型參數(shù)的更新.巨大的參數(shù)規(guī)模和訓練數(shù)據(jù)集合,使得模型的全量更新所消耗的計算資源和時間是不可接受的,而且線下的更新方式勢必導致用戶體驗變差.因此,如何對因子分解模型進行在線更新成為研究熱點.文獻[45,46]在凸因子分解機模型基礎(chǔ)上分別使用在線條件梯度和 FTRL(follow the regularized leader)兩個經(jīng)典的在線凸優(yōu)化方法完成模型的學習.

2.1.6 層次信息引入

在標準FM模型中,并不存在類別信息,所有特征之間是平等的.同一特征與任意其他特征的同階交互,其對應的隱因子向量是共享的,這種共享機制極大地減少了參數(shù)規(guī)模.然而這種設(shè)置并不符合實際情況,一些研究者認為:當特征在與不同類別特征交互時,應該使用不同的隱因子向量.因為隱因子向量刻畫了兩類特征交互的內(nèi)涵,而不同的類別特征交互其所具備的物理含義很可能是全不同的.基于這種假設(shè),文獻[8]提出一種基于因子分解的個性化標簽推薦方法,作者使用用戶、標簽和物品這 3類特征,分別對(用戶-物品)、(用戶-標簽)和(標簽-物品)這3類交互進行因子分解,得到了較好的推薦效果.在文獻[8]的基礎(chǔ)上,文獻[47]提出了一種通用的基于類別上下文的因子分解機模型 FFM,針對同一特征與不同類別間特征的同階交互使用不同的特征隱因子向量,并給出一種并行思路,應用至點擊率預測中.相較于標準FM模型,雖然FFM有效地提高了模型準確率,但是模型的參數(shù)規(guī)模也成倍增加.假設(shè)訓練數(shù)據(jù)中存在f類不同特征,總的特征維度為p,每個特征的二階交互隱因子向量維度為k,那么標準 FM 模型參數(shù)規(guī)模為p(k+1)+1,FFM 的參數(shù)規(guī)模為p(fk+1)+1,其中,1<

與上述泛化的基于不同類別特征交互的隱因子向量來刻畫類別層次信息不同,文獻[49]聚焦移動廣告點擊率預測場景,利用場景中不同類別隱含的層次信息和重要度信息構(gòu)建樹狀訓練集劃分,實現(xiàn)數(shù)據(jù)實例與不同類別的交互.

2.1.7 其他應用場景

針對標準 FM 本身存在的問題和挑戰(zhàn),上述研究分別從一個或多個角度進行了優(yōu)化研究.如何將因子分解機模型應用至具體不同場景下不同問題下,也有研究者給出了多樣的解決方案.

文獻[50]提出同時使用兩個因子分解機模型來同時分別建模用戶興趣(是否轉(zhuǎn)發(fā)某條推特)和發(fā)現(xiàn)推特中的話題,兩個模型之間可以通過不同的共享機制聯(lián)系,作者共提出 3種不同的共享機制,包括特征共享、隱式空間共享和隱式空間正則化(距離).文獻[51]將因子分解機模型應用至跨領(lǐng)域協(xié)同過濾中,這種方法通過連接其他領(lǐng)域和目標領(lǐng)域的特征,使得模型能夠充分利用其他領(lǐng)域的信息來補充當前領(lǐng)域上下文,以提高目標領(lǐng)域的推薦性能.受文獻[52]針對矩陣基于層次上下文相似度分割的啟發(fā),文獻[53]認為,基于似上下文環(huán)境的數(shù)據(jù)實例建模能夠提高模型精度,提出利用數(shù)據(jù)集中隱含的層次信息,多次隨機構(gòu)造多顆決策樹.在每個層次節(jié)點的訓練集劃分時,使用當前節(jié)點上所有的訓練集基于隨機梯度下降或坐標下降法進行訓練,然后利用K-means聚類算法對當前節(jié)點對應類別生成的隱因子向量進行聚類劃分,得到多個聚類中心,按照聚類中心,將當前訓練數(shù)據(jù)分割分發(fā)至下一層.重復上述過程.在測試階段,使用多個隨機決策樹生成值的平均作為最終的預測結(jié)果.文獻[54-56]將用戶之間的信任度、相似度和相互關(guān)注等信息融入因子分解機模型特征向量中,提高推薦準確率.一般地,標準FM模型用于推薦、預測等領(lǐng)域,然而針對排序場景,模型并未給出相應的優(yōu)化,因此,文獻[57]提出結(jié)合Learning-to-Rank的因子分解機模型,針對AUC度量方法進行直接優(yōu)化.受文獻[58]的BPR排序理論影響,文獻[59]提出基于 AUC度量方法的排序因子分解機模型,在進行負例選擇時,作者利用隱式反饋和內(nèi)容信息提出一種自適應的采用算法,其主要思路是:相同類別中,用戶對有過歷史行為的物品比未有過歷史行為的物品有更高的評分.然而,AUC度量并不適合于Top-N推薦任務(wù).基于AUC的排序使得在度量錯誤的排序時,無論其處在Top-N推薦列表的頂部或底部具有一樣的影響力.這種設(shè)定是不符合常理的.文獻[60]認為,在Top-N推薦列表的頂部具有比在底部更高的正確率是非常重要的,而能達到這種排序效果的度量方法有 NDCG和 MRR.因此,提出了LambdaFM,直接基于NDCG和MRR等排序度量方法進行優(yōu)化,對處在不同排序位置的物品對賦予不同的權(quán)重,并提出3種采樣策略.文獻[61]提出一種基于Boosting的排序因子分解機模型,其主要思想是:在每次迭代時,生成一個新的排序因子分解機模型用于優(yōu)化上一步的殘差,其中,每步的排序模型基于 Learning-to-Rank優(yōu)化.此外,作者維護了一個權(quán)值向量用于對每一對物品對進行動態(tài)權(quán)值分配,主要是對當前表現(xiàn)較差的物品對賦予更高的權(quán)值,以達到糾正的效果.

2.2 模型性能提升

FM現(xiàn)在已經(jīng)被廣泛地應用于預測、推薦等領(lǐng)域,特征工程和分解模型的結(jié)合,使得它通常能獲得較好的性能[3,21,50,51,54].然而模型獨有的特征組織形式導致它在大規(guī)模數(shù)據(jù)集下,傳統(tǒng)的單機環(huán)境已無法滿足其需求.因此,模型的擴展應運而生.目前,針對因子分解機模型的擴展研究主要集中在兩個方面:數(shù)據(jù)/參數(shù)形式重組和分布式擴展.

在數(shù)據(jù)重組方面,文獻[62]基于標準模型提出一種不改變單機環(huán)境,而是針對模型底層數(shù)據(jù)的組織特征重新建立新的模型,不但有效地降低了底層數(shù)據(jù)的存儲,而且提高了模型的計算效率.文獻[28]也使用了同樣的技巧,以提升其提出的基于多視圖的結(jié)構(gòu)因子分解機模型.與改變底層數(shù)據(jù)組織、提升模型訓練效率不同,文獻[63]認為:在真實工業(yè)環(huán)境中,其所能獲得的特征維度之高直接造成了昂貴的存儲和計算代價,這大大阻礙了快速推薦在計算資源有限設(shè)備(如移動設(shè)備)上的應用.因此,作者提出離散化因子分解機(DFM),將原模型的實數(shù)型特征交互因子矩陣改為布爾型.相較之下,布爾型因子矩陣具有低存儲、可快速計算等優(yōu)點,然而在原優(yōu)化方案下,取值范圍的縮小必然導致模型性能的下降.為此,作者提出一種特殊的離散參數(shù)優(yōu)化方案來學習布爾因子矩陣.實驗結(jié)果表明:DFM在保證良好模型準確率的同時,能16倍加速于FM.

在分布式擴展方面,文獻[64]基于Map-Reduce對標準FM模型進行了實現(xiàn).文獻[65]首次提出使用基于異步隨機梯度下降的參數(shù)服務(wù)器框架來實現(xiàn)模型的分布式擴展.為了進一步提高模型計算效率和性能,作者對模型本身進行了兩方面的優(yōu)化:首先,作者認為,針對所有特征的隱因子向量使用相同維度是不必要的,浪費了存儲和計算資源,針對數(shù)據(jù)集中出現(xiàn)頻率低的特征,可以適當?shù)亟档蛯碾[因子向量維度,就此,作者提出一種基于頻繁度的啟發(fā)式方法度量隱因子向量維度;第二,在正則化項部分,作者加入了稀疏正則項和基于特征出現(xiàn)頻率自適應的正則項進一步提高了模型效率和性能.與文獻[65]類似,文獻[66]在基于 Map-Reduce的參數(shù)服務(wù)器框架下對標準 FM 模型進行了優(yōu)化.所不同的是,優(yōu)化方法使用了一種分布式坐標下降算法.為了減少服務(wù)器和worker端的通信代價并減少參數(shù)更新沖突,作者提出一種啟發(fā)式數(shù)據(jù)劃分策略.與主從分布式框架不同,文獻[67,68]提出一種環(huán)形的分布式框架.該框架摒棄了服務(wù)器端,使得集群中僅存在兩類節(jié)點:調(diào)度節(jié)點和worker節(jié)點.其中:調(diào)度節(jié)點負責響應模型調(diào)度請求,存儲全局變量;worker節(jié)點則負責模型的更新和存儲.基本思想是:在數(shù)據(jù)分發(fā)時,調(diào)用Spark接口將整個訓練集按照既定數(shù)據(jù)分發(fā)策略平均分發(fā)至每一個worker節(jié)點,然后進行模型訓練.訓練時,令每個worker節(jié)點各自獨立保存一部分模型參數(shù),使用各個節(jié)點的子數(shù)據(jù)集對保存的模型參數(shù)進行更新,最終得到與客戶端節(jié)點相同數(shù)目的相互獨立的部分模型.然而由于 FM 數(shù)據(jù)組織形式的高維稀疏性,將數(shù)據(jù)分發(fā)至每個worker,數(shù)據(jù)稀疏性愈發(fā)嚴重.如果僅使用每個worker節(jié)點上的子數(shù)據(jù)集對自身的模型進行更新,最終學習得到的模型準確率無法保證.因此,作者設(shè)計了一套環(huán)形的模型調(diào)度機制.這種調(diào)度機制允許每個worker節(jié)點不但可以更新它本身存儲的模型,還可以更新不屬于它的其他worker節(jié)點的模型.即:節(jié)點在更新完模型后,將模型推送至它的原始保存節(jié)點,然后通過調(diào)度函數(shù),節(jié)點選擇另一個新的從未更新過的模型,從所屬節(jié)點拉取該模型,繼續(xù)使用子數(shù)據(jù)集對新模型更新.在下一個模型選擇時,優(yōu)先考慮同一機器上其他節(jié)點(每個核可表示一個節(jié)點).另外,為避免頻繁的模型調(diào)度,每個模型在一個節(jié)點上的學習基于多次迭代完成.模型訓練結(jié)束后,在模型預測階段,利用已經(jīng)學習得到的多個模型對每個測試實例進行獨立預測,對多個模型預測的結(jié)果采用多數(shù)投票的方法進行合并.相比主從分布式框架,該環(huán)形分布式系統(tǒng)能夠有效地減少節(jié)點間的通信頻度和規(guī)模.與上述對標準FM模型的優(yōu)化不同,文獻[69]使用參數(shù)服務(wù)器框架實現(xiàn)了基于領(lǐng)域的因子分解機模型的分布式擴展,分別與 All-Reduce、類 Map-Reduce等分布式實現(xiàn)進行了對比.文獻[29]對提出的多視圖分解機模型進行了基于Spark平臺的分布式實現(xiàn).

總結(jié)FM模型的3種不同分布式底層框架,給出不同框架的詳細比較如表1和圖2所示.按照架構(gòu)分類,基于 Map-Reduce/Spark和參數(shù)服務(wù)器的分布式屬于主從式架構(gòu),環(huán)形分布式則屬于端到端的架構(gòu).主從式架構(gòu)中必須包含一個或多個服務(wù)器節(jié)點,最新的模型參數(shù)全部存儲于服務(wù)器節(jié)點,參數(shù)的更新計算則由worker節(jié)點完成.然而,端到端的結(jié)構(gòu)中并不存在服務(wù)器節(jié)點,因此模型參數(shù)的存儲和更新均由各個 worker節(jié)點完成.相比Map-Reduce/Spark,參數(shù)服務(wù)器的服務(wù)器組機制能夠極大地分擔通信壓力.在通信方面,Map-Reduce/Spark和參數(shù)服務(wù)器框架在每次迭代時,服務(wù)器與worker節(jié)點間都必須進行參數(shù)傳遞,不同之處在于:Map-Reduce/Spark結(jié)構(gòu)需要廣播整個參數(shù)空間至每個worker節(jié)點,參數(shù)服務(wù)器架構(gòu)則只需傳送與worker節(jié)點上數(shù)據(jù)對應的參數(shù)即可.而環(huán)形分布式框架由于模型參數(shù)和數(shù)據(jù)在同一節(jié)點,只有worker間進行模型交換時才會進行必要的參數(shù)傳遞.綜上所述,Map-Reduce/Spark通信代價最大,參數(shù)服務(wù)器框架次之,環(huán)形分布式最小.在參數(shù)更新同/異步方面,若由于數(shù)據(jù)劃分不均衡,同步更新中有些節(jié)點計算快,有些節(jié)點計算慢,由此產(chǎn)生的等待時延會大大降低訓練效率.因此一般情況下,異步更新效率要高于同步更新.在模型學習完成時,主從式框架最終只產(chǎn)生一個模型.然而在環(huán)形分布式架構(gòu)下,每個節(jié)點都會產(chǎn)生一個獨立的部分模型,在模型應用階段,使用多個部分模型獨立預測每個實例,根據(jù)場景不同,利用投票表決或求平均的方式得到最終預測結(jié)果.

Table 1 Comparison of different distributed frameworks表1 不同分布式框架對比

Fig.2 Architecture of different distributed frameworks used in FM model圖2 FM模型不同分布式系統(tǒng)框架圖

3 因子分解機模型優(yōu)化算法

本節(jié)將綜述適用于求解因子分解機模型的優(yōu)化算法.為便于描述,我們首先將約束優(yōu)化因子分解機模型的損失函數(shù)統(tǒng)一形式.假設(shè)訓練集(x,y)∈D,我們使用y?(x|Θ)表示因子分解機模型表達式,則模型參數(shù)的優(yōu)化問題通常通過定義損失函數(shù)來使得訓練集D的損失和最小來完成.即有:

為避免模型訓練時產(chǎn)生過擬合,向上述優(yōu)化目標中加入正則項函數(shù)R(Θ):

針對具體的任務(wù),可選擇不同的優(yōu)化算法.因子分解機模型在分類和回歸場景中都有較好的表現(xiàn),這里以回歸和二分類問題為例.

· 在回歸問題中,其損失函數(shù)通常定義如下:

· 在二分類問題中,其損失函數(shù)可如下定義:

其中,σ(x)為 logistic 函數(shù).

目前,針對FM模型的優(yōu)化有4種優(yōu)化學習算法,分別是隨機梯度下降、交替最小二乘法、基于自適應正則項值的隨機梯度下降和MCMC.下面我們將對這4種算法分別進行剖析.

3.1 隨機梯度下降

隨機梯度下降算法是眾多機器學習算法中最常用的優(yōu)化算法,在不同損失函數(shù)下均能有較好的表現(xiàn)以及較低的計算復雜度、存儲復雜度等特性.它的具體思路是每次從訓練集中隨機選擇一個樣本來更新模型參數(shù).

再次回顧標準FM模型如公式(2)可知,模型共包含3類參數(shù):w0,w,V.雖然FM模型在整體上表現(xiàn)出非凸性,但是在優(yōu)化每一個參數(shù)Θ={w0,w1,wi,…,V1,1,…,V1,f,…,Vi,f}時,目標函數(shù)可看做凸函數(shù).

在隨機梯度下降算法中,每一步每個參數(shù)的更新都可表示為

其中,η∈?+表示每次迭代的學習速率.

針對不同的任務(wù)場景下不同損失函數(shù)梯度的計算是不同的.在回歸問題中有:

對于二分類問題:

具體到每一個參數(shù),其相對模型表達式的偏導可表示為

算法1給出了FM模型在隨機梯度下降算法下的詳細優(yōu)化過程.

算法1.隨機梯度下降法.

輸入:訓練集D,迭代次數(shù)T,隱因子維度k,正則化項參數(shù)λ,學習速率η,初始化參數(shù)σ;

輸出:FM模型參數(shù)Θ=w0,w,V.

通過分析隨機梯度下降可知,學習速率η的選取對目標函數(shù)的收斂影響非常大.其中:如果η過大,則會導致算法不收斂;若η選擇過小,則會導致算法收斂過慢,嚴重影響模型訓練效率.因此,如何設(shè)置適當大小的η,是隨機梯度下降優(yōu)化算法成功的關(guān)鍵所在.

3.2 交替最小二乘法

基于訓練數(shù)據(jù)實例的迭代,隨機梯度下降算法沿著損失函數(shù)梯度下降的方向小步地行進來完成損失函數(shù)的最小化.與隨機梯度下降優(yōu)化不同,交替最小二乘法采用最小化每一個模型參數(shù)的方法來完成優(yōu)化.具體地,在固定其他參數(shù)不變的情況下,每次更新一個參數(shù),使當前參數(shù)沿著梯度方向?qū)ふ移渥顑?yōu)解,每個參數(shù)的最優(yōu)解可通過使其偏導為0得到.

為了方便取得最優(yōu)解,這里我們確定公式(11)中的正則化項采用L2范數(shù).然而在標準FM模型中,假設(shè)訓練集D共n個數(shù)據(jù)實例,每個數(shù)據(jù)實例包含p維特征,那么在隱因子向量維度為k時,共有1+p+kp個模型參數(shù).若為每一個模型參數(shù)都給定一個獨立的正則化項系數(shù),這無疑大大增加存儲和計算復雜度.通過對同一類模型參數(shù)采用相同正則項系數(shù)的方法,可大大簡化這一過程.因此,公式(11)可進一步表達如公式(18):

假設(shè)當前任務(wù)為回歸問題,通過對損失函數(shù)在模型參數(shù)θ下求偏導并令偏導為 0,得到θ最優(yōu)解.在標準 FM模型中,其具有多線性特點,即:對任意模型參數(shù)θ∈Θ,標準 FM 模型可以寫成兩個函數(shù)gθ和hθ線性組合的方式,獨立于參數(shù)θ:

其中,hθ即當前參數(shù)相對模型表達式的偏導數(shù):

基于上述表述,模型參數(shù)θ*的最優(yōu)解可表示如公式(21):

在固定其他參數(shù)的前提下,使用公式(21)對每個模型參數(shù)θ進行更新,多次迭代直至收斂,即可完成對所有模型參數(shù)的優(yōu)化.通過分析參數(shù)更新公式(21)可知,其中最耗時計算部分主要集中在以下兩個式子:

從公式(22)可以看出,在每次更新一個參數(shù)時,都需對y-y?(x)重新計算.而在更新參數(shù)V時,hθ(x)也需要進行復雜的重新計算完成.為了提高訓練效率,可通過預計算的方式避免上述部分的重復計算.

令e和q分別表示如下:

則針對參數(shù)Vl,f的計算可簡化為

算法2給出了FM模型在交替最小二乘算法下的詳細優(yōu)化過程.

算法2.交替最小二乘法.

輸入:訓練集D,迭代次數(shù)T,隱因子維度k,正則化項參數(shù)λ,學習速率η,初始化參數(shù)σ;

通過分析交替最小二乘可知:相比隨機梯度下降,一個顯著的優(yōu)勢在于交替最小二乘中不存在學習速率η的選取,但是正則項超參λ仍然會影響模型的優(yōu)化,好的正則項系數(shù)的搜索是十分耗時的.

3.3 基于自適應正則的隨機梯度下降

在隨機梯度下降和交替最小二乘中,一般正則項超參λ的設(shè)置由用戶手動完成,若選擇不好,則導致模型的欠擬合或過擬合.嚴格來說,一個好的正則項超參λ需要經(jīng)過昂貴的搜索得到.為克服這一缺點,基于自適應正則項的隨機梯度下降算法被提出[23].該方法能夠避免最佳正則化項系數(shù)的網(wǎng)格搜索過程,具體地,通過對模型參數(shù)Θ與正則化項系數(shù)λ使用交替最小二乘固定其中一個、優(yōu)化另一個的方法來達到正則化項系數(shù)λ的自適應.

通常,理想正則化項系數(shù)λ*的選取使用驗證集的方法.即,將訓練集D分割成不相交的兩部分:D=DT∪DV.首先,使用給定的正則化常數(shù)λ,在DT上完成模型參數(shù)Θ的優(yōu)化;然后,在驗證集DV評估學習到的模型參數(shù)Θ的質(zhì)量.由于訓練集DT和驗證集DV不相交,因此學習得到的模型參數(shù)Θ在驗證集上的評估質(zhì)量能夠充分說明其在更大數(shù)據(jù)集上的有效性.

根據(jù)上述描述,為得到優(yōu)化的正則化項系數(shù)λ*,可構(gòu)建損失函數(shù)如公式(26):

在這個嵌套損失函數(shù)中,最外面的優(yōu)化目標是通過在驗證集上最小化損失來決定最佳正則化項系數(shù)λ*.但這個損失并不直接取決于正則化項系數(shù),而是依賴訓練集上模型參數(shù)Θ的學習情況,即有公式(27):

對于這種嵌套的損失函數(shù),一個直接優(yōu)化上述目標的方法就是使用交替最小二乘法,其中,參數(shù)分為兩類:一類是模型參數(shù)Θ,一類是正則化項系數(shù)λ.然而這種方法是有問題的——在固定模型參數(shù)時,正則化項系數(shù)λ并不會顯式出現(xiàn)在公式(26)中.

為了解決上述問題,一個比較巧妙的方法是,Θt+1的值依賴于λ,因此可以利用模型參數(shù)更新公式對上述式子進行改進:

基于上述改進,優(yōu)化目標函數(shù)(26)轉(zhuǎn)化為公式(29):

正則化項系數(shù)λ在驗證集DV上的更新見公式(30):

在清楚了模型參數(shù)更新及正則化項系數(shù)更新梯度后,算法3給出了FM模型在基.于自適應正則化隨機梯度下降的詳細優(yōu)化過程.

算法3.基于自適應正則化的隨機梯度下降算法.

輸入:訓練集D,迭代次數(shù)T,隱因子維度k,學習速率η,初始化參數(shù)σ;

輸出:FM模型參數(shù)Θ=w0,w,V.

3.4 馬爾可夫蒙特卡洛法

隨機梯度下降和交替最小二乘算法使用點估計?y的方法學習出模型參數(shù)Θ;而馬爾可夫蒙特卡洛法(MCMC)則是基于貝葉斯推論,通過抽樣的方法來生成?y的分布.與隨機梯度下降和交替最小二乘法相比,MCMC允許將超參放入模型中一起進行優(yōu)化,避免了費時的最優(yōu)超參搜索過程.而這種將超參加入模型優(yōu)化的方法需要我們將標準FM的概率圖模型(圖3(a)所示)擴展為基于超參超先驗的FM概率圖模型,如圖3(b)所示.

Fig.3 Comparison of the probabilistic interpretation of standard factorization machines (left) to Bayesian factorization machines (right) extended by hyperpriors圖3 標準FM概率模型與基于超先驗的貝葉斯FM概率模型對比

具體地,基于吉布斯采樣的MCMC方法下,FM模型中每個參數(shù)的條件后驗分布可表示如下:

觀察 MCMC下每個參數(shù)的條件后驗分布,可以發(fā)現(xiàn),其與交替最小二乘法優(yōu)化公式十分的相似.即:當α=1且μ=0 時,有.兩種方法的不同之處在于:MCMC從參數(shù)的后驗分布進行采樣,而交替最小二乘法則使用其期望值.

在FM模型的MCMC推論中,假設(shè)先驗參數(shù)μθ服從標準正太分布,而λθ和α服從Gamma分布,可得:

其中,Θ0:={μ0,γ0,αλ,βλ,α0,β0}用來描述超先驗分布.

基于上述表示,超參的值可以通過從其相應的條件后驗分布中采樣自動獲得:

其中,

算法4給出了FM模型在MCMC下解決回歸i的詳細優(yōu)化過程.若想將其擴展到二分類任務(wù)的解決,則需要將正態(tài)分布的映射到伯努利分布.這樣,MCMC算法就能預測一個實例屬于正類或者負類的概率.

算法4.馬爾可夫蒙特卡洛算法.

輸入:訓練集Dtr,測試集Dte,迭代次數(shù)T,隱因子維度k,初始化參數(shù)σ;

輸出:測試集Dte上預測結(jié)果.

通過對MCMC方法分析可知MCMC的正則項超參ΘH是抽樣選取的,為此引進了新的超先驗參數(shù)Θ0.但是,超先驗參數(shù)的數(shù)目要小于正則化項超參的數(shù)量.另外,更重要的一點在于:相比隨機梯度下降和交替最小二乘算法,MCMC對于超先驗參數(shù)Θ0的選擇不敏感.即使該參數(shù)選擇不好,FM模型也能得到較好的結(jié)果.

3.5 4種優(yōu)化算法比較

本節(jié)綜述了FM模型常用的4種優(yōu)化學習方法,分別是隨機梯度下降法、交替最小二乘法、基于自適應正則的隨機梯度下降法和馬爾可夫蒙特卡洛法.下面我們從時間復雜度、空間復雜度、適用任務(wù)場景、超參數(shù)類型這4個方面對上述方法總結(jié)說明,見表2.其中,Nz(X)表示訓練集中所有不為0特征的總個數(shù).由于每次迭代時參數(shù)的更新計算通過遍歷一次訓練集即可完成,因此 4種優(yōu)化方法在時間復雜度上是一致的.然而在存儲復雜度上,各個優(yōu)化算法所需的存儲空間是不同的.兩類隨機梯度下降算法下的 FM 優(yōu)化只需要存儲模型中每一個參數(shù)的迭代更新值,故其存儲復雜度為常數(shù)級.與上述梯度更新相比,交替最小二乘法和馬爾可夫蒙特卡洛方法除去 1+p(k+1)大小內(nèi)存用于參數(shù)的存儲外,還需要O(nk)的內(nèi)存去存儲預計算結(jié)果.在適用任務(wù)場景中,使用不同損失函數(shù)或分布的 4種優(yōu)化方法都能勝任常見的回歸或分類問題.在超參類型上,隨機梯度下降需用戶自定義的超參最多,包括學習速率、分布初始化參數(shù)和正則化項系數(shù).基于自適應正則化的隨機梯度下降和馬爾可夫蒙特卡洛法將正則化項系數(shù)作為參數(shù)糅合到模型中進行共同學習,避免了最優(yōu)正則化項系數(shù)的搜索過程,模型學習過程更加健壯.而除了隨機梯度下降,其他 3種優(yōu)化方法都不存在學習速率的指定,也使得模型的優(yōu)化更加穩(wěn)定.

Table 2 Comparison of different optimization methods表2 不同優(yōu)化方法對比

4 存在問題及未來研究方向

4.1 存在問題

在第 2節(jié)給出了因子分解機模型在準確性提升和性能加速兩個方面取得的研究進展,然而仍存在以下幾點不足.

(1) 模型準確性方面

現(xiàn)有對FM模型準確性提升的工作基本從低階到高階交互、神經(jīng)網(wǎng)絡(luò)與FM的結(jié)合、好的交互特征選擇、概率模型推導、凸優(yōu)化模型、在線學習、層次信息引入以及具體場景分析等 8個方面展開.在高階交互方面,基于更高階特征交互的FM模型固然能夠進一步挖掘特征之間的相互關(guān)聯(lián),從而提升模型準確率,然而FM的高階交互會導致模型可解釋性進一步降低,并可能進一步放大噪音特征對模型準確性的影響.在神經(jīng)網(wǎng)絡(luò)與 FM的結(jié)合方向,現(xiàn)有結(jié)合方案可分為兩類:① 將標準FM模型作為神經(jīng)網(wǎng)絡(luò)的輸入,以便于后續(xù)利用神經(jīng)網(wǎng)絡(luò)完成特征的更高階非線性交互;② 同時使用標準FM模型和神經(jīng)網(wǎng)絡(luò)分別完成特征的低階和高階交互建模,未來可考慮與其他更多類型神經(jīng)網(wǎng)絡(luò)的結(jié)合以適應不同的應用場景.在交互特征選擇領(lǐng)域,已有的工作多是基于標準FM模型展開的,存在可擴展性較低以及模型參數(shù)規(guī)模并未因為特征選擇而減小等問題.針對FM模型的在線學習,現(xiàn)有工作基于凸 FM模型展開,分別利用流行的凸優(yōu)化學習算法在線條件梯度和 FTRL完成模型的更新.然而這種單機在線學習算法已無法適用于大規(guī)模參數(shù)和數(shù)據(jù)集的場景.最后,在層次信息引入上,研究者從樹狀層次特征引入和不同類別特征交互使用不同隱因子向量/權(quán)重兩個角度展開來提高模型準確性,但是依然存在拘泥于特定場景、模型規(guī)模指數(shù)級增加及無法適用于高階特征交互建模等問題.

(2) 模型效率方面

現(xiàn)有針對 FM 模型的分布式擴展工作已有多種方案,然而挑戰(zhàn)依然存在.按照分布式框架的不同,可分為Map-Redce/Spark、參數(shù)服務(wù)器框架和環(huán)形分布式框架.基于Map-Reduce/Spark平臺的擴展既有高階FM模型,也有標準 FM 算法,最大的短板在于全局模型需存放于一個服務(wù)器節(jié)點且模型傳輸時通信開銷巨大,導致其在模型規(guī)模龐大的真實生產(chǎn)環(huán)境中無法應用.基于參數(shù)服務(wù)器框架的擴展目前僅限于標準 FM 模型,相比 Map-Reduce/Spark架構(gòu),通信開銷更少,模型存儲也不再限制于一個服務(wù)器節(jié)點.然而由于模型的高維性,多次迭代下通信開銷依然巨大.在此背景下,基于環(huán)形分布式的二階FM模型被提出,優(yōu)勢在于通信開銷和頻次進一步減小,但稍顯劣勢之處在于單個節(jié)點上存儲的模型規(guī)模有所增加.從上述描述可以看出:標準 FM 模型的分布式擴展已趨于成熟,然而基于FM的高階交互、特征選擇、凸模型以及在線學習等多種模型變種的分布式擴展依然存在瓶頸,有待進一步完善.

4.2 未來研究方向

針對上述因子分解機模型研究中依然存在的問題,對其未來研究方向進行探討.

(1) 模型準確性研究

在高階模型可解釋性方面:一方面,可借助特征選擇算法降低高階建模時所需的特征數(shù)目,從而降低交互階數(shù),并剔除噪音、冗余和不相關(guān)特征;另一方面,對所有特征的相關(guān)性進行分析,使用多個高階FM模對每組特征完成交互建模,最終根據(jù)任務(wù)場景,利用加權(quán)平均或投票表決的方式進行預測.

在神經(jīng)網(wǎng)絡(luò)與FM模型的結(jié)合方面,現(xiàn)有研究神經(jīng)網(wǎng)絡(luò)部分都是基于傳統(tǒng)神經(jīng)網(wǎng)絡(luò)或向傳統(tǒng)神經(jīng)網(wǎng)絡(luò)中加入注意力機制,后續(xù)研究可從神經(jīng)網(wǎng)絡(luò)部分入手,考慮 FM 模型與其他高級神經(jīng)網(wǎng)絡(luò)類型如長短期記憶網(wǎng)絡(luò)LSTM的結(jié)合,可用于在流式數(shù)據(jù)中挖掘用戶的長期和短期興趣,提升推薦結(jié)果質(zhì)量.

在交互特征選擇方面,研究目標大致可分為兩個方向:① 考慮擴展基于標準 FM 的交互特征選擇至高階FM 模型,與現(xiàn)有高階交互研究相結(jié)合,不僅可以達到降低模型參數(shù)規(guī)模的目標,而且提高了模型準確性和可解釋性;② 考慮采用現(xiàn)有流行方法高效的選擇好的交互特征,如可利用神經(jīng)網(wǎng)絡(luò)基于原始數(shù)據(jù)完成特征的表示學習,利用強化學習思想選擇.

在FM模型的在線學習方面,有兩個基本問題需要考慮:其一,假設(shè)新進數(shù)據(jù)特征維度不變,即不存在新特征的加入,這種情況下,如何利用新進數(shù)據(jù)增量更新已有模型;其二,假設(shè)新進數(shù)據(jù)中存在新用戶、新物品和新的上下文特征,那么如何基于已有模型較小調(diào)整甚至不改變的情況下學習得到新的模型.現(xiàn)有工作都是以特征維度不變?yōu)榍疤嵴归_的,后續(xù)的研究方向可從3個方向入手:① 利用其他已有的在線學習方法完成FM模型及其變種的增量更新;② 擴展單機環(huán)境下FM模型的在線學習方法至分布式環(huán)境下,以適應真實生產(chǎn)環(huán)境下的大規(guī)模參數(shù)和數(shù)據(jù)集;③ 考慮新的特征加入條件下,利用矩陣運算達到基于已有模型的較小調(diào)整甚至不改變情況下更大規(guī)模新的模型的學習.

在層次信息引入方面,現(xiàn)有工作主要存在特定場景特殊分析、模型規(guī)模指數(shù)級增長以及不適用于高階特征交互建模等短板.因此,未來可考慮提出一種通用的層次特征建模方法,使得 FM 模型能夠利用這種層次的特征有效提高模型的表達能力,如結(jié)合神經(jīng)網(wǎng)絡(luò)和注意力機制,使得特征間的高階交互建模得以實現(xiàn),并利用注意力機制學習得到不同類別特征交互的強度.

(2) 模型效率研究

現(xiàn)有針對 FM 模型效率提升主要分為基于數(shù)據(jù)/參數(shù)重組和基于分布式兩種.其中,由于分布式優(yōu)化在大數(shù)據(jù)環(huán)境下的高效性使其成為主流研究方向,得到較多關(guān)注.然而多數(shù)工作都是基于標準 FM 模型展開的,在變種FM模型,如高階交互、特征選擇等方面僅僅做了簡單的分布式實現(xiàn).在FM模型的增量更新方面,目前仍無相關(guān)研究.因此,如何針對上述兩個方向進行分布式擴展是非常值得關(guān)注的.

5 總 結(jié)

作為一種通用的分解模型,因子分解機模型能夠取得較好的預測和推薦結(jié)果,近年來在機器學習領(lǐng)域得到了廣泛的應用和關(guān)注,取得了諸多研究成果.本文首先從分解模型的演化角度說明了傳統(tǒng)的矩陣分解模型如何一步步進化到基于特定上下文的分解方法,進而得到本文綜述重點——通用因子分解機模型,并通過因子分解機模型與其他流行的特定分解模型的相互關(guān)聯(lián)性說明了因子分解機模型強大的泛化性;然后,從因子分解機模型的準確性和性能兩方面出發(fā),說明標準因子分解機模型存在的不足,并給出近年來研究者針對這兩個方面所存在問題的優(yōu)化方案;接著,從獨立于問題模型的角度綜述了FM模型常用的4種優(yōu)化方法,并指出各個優(yōu)化算法的優(yōu)勢和不足;最后指出了現(xiàn)有因子分解模型研究中存在的不足和未來可能的研究方向.