眾所周知,ACM RecSys是推薦系統(tǒng)頂級國際會(huì)議,每年邀請?jiān)擃I(lǐng)域的著名學(xué)者及互聯(lián)網(wǎng)知名專家擔(dān)任主講嘉賓,議題涵蓋推薦算法、社會(huì)化推薦、用戶建模、機(jī)器學(xué)習(xí)和人機(jī)交互等前沿技術(shù)。
RecSys評委們對文章的篩選一向以“苛刻”著稱,每年只接受300篇左右,接受率約為20%。2012年,百度成為第一家參加RecSys的國內(nèi)公司;2013年,發(fā)表了題為“計(jì)算廣告和推薦系統(tǒng)”的主題演講;2014年,又有多篇論文發(fā)布,不斷向世界展示推薦技術(shù)的最新發(fā)展。
本文基于在RecSys 2014上百度大數(shù)據(jù)實(shí)驗(yàn)室發(fā)布的題為《智能因子分解機(jī)》的論文,深入解析了一種新型的智能因子分解機(jī)。它將因子自動(dòng)學(xué)習(xí)算法納入因子模型,以智能學(xué)習(xí)特征,替代人工特征工程,極大提升了因子分解機(jī)的應(yīng)用效率。經(jīng)過真實(shí)數(shù)據(jù)和人造數(shù)據(jù)驗(yàn)證,其有效性和效率皆優(yōu)于現(xiàn)階段其他方法,是百度在推薦技術(shù)上的又一突破。
推薦系統(tǒng)技術(shù)綜述
推薦技術(shù)在過去十幾年中取得了巨大發(fā)展,當(dāng)前業(yè)界的主流技術(shù)有兩種:傳統(tǒng)文本不感知方法和文本感知方法。
傳統(tǒng)的文本不感知方法,是在用戶物品評分矩陣基礎(chǔ)上建立模型,例如只考慮用戶與物品交互。其中,矩陣因子分解方法因其在處理相對較大數(shù)據(jù)集中的良好表現(xiàn)和有效性大受歡迎。這些方法利用低秩矩陣分解逼近用戶物品評分矩陣,并用它們來做更進(jìn)一步的預(yù)測。
而在真實(shí)情境中,許多輔助信息是可獲取的,并被證明在大數(shù)據(jù)集中特別有效。舉例來說,對于微博中的名人推薦問題,用戶與名人元數(shù)據(jù)(包括年齡、性別等)、名人的受歡迎程度、最近的用戶表現(xiàn),都能幫助系統(tǒng)做出更好的推薦。我們將輔助信息特征稱為文本感知推薦。文本感知因子分解機(jī)是目前最成功的文本感知推薦模型之一。因子分解機(jī)與所有特征兩兩互動(dòng),這樣,一個(gè)特定的特征隱向量被共享用來計(jì)算因式分解參數(shù)。
現(xiàn)有方法費(fèi)時(shí)費(fèi)力
至于利用輔助信息,目前的技術(shù)主流是因子分解機(jī)(FM)。FM是一個(gè)泛化的模型,一般采用雙向特征交互。在實(shí)際應(yīng)用中,有幾十個(gè)文本特征不足為奇,并且不是所有的交互都對評分預(yù)測有效。需要注意的是,因子分解機(jī)對所有文本特征變量的兩兩交互建立模型,交互特征權(quán)重計(jì)算時(shí)所有變量的隱向量被共享。
因?yàn)椴⒎撬薪换ザ加行В栽趯?shí)際使用時(shí)通常通過人工指定交互的特征和特征交互的階數(shù)。也就是說,人工制定配置,指定特征的交互和階數(shù),然后在給定的數(shù)據(jù)集上測試效果,必須通過嘗試大量的人工配置比較才能獲得較優(yōu)的效果。
但可選配置的數(shù)量是特征數(shù)的指數(shù)量級,并且評估每次配置時(shí)需要花費(fèi)大量時(shí)間訓(xùn)練并測試模型,費(fèi)時(shí)又費(fèi)力。此外,對于不同應(yīng)用,每次都需要重復(fù)這個(gè)過程,嚴(yán)重制約了使用FM的效率。
百度的“智能”在哪里
百度大數(shù)據(jù)實(shí)驗(yàn)室提出了一種新型智能因子分解機(jī)(GBFM),有效地解決了傳統(tǒng)人工特征選擇過程中費(fèi)時(shí)費(fèi)力的難題。智能因子分解機(jī)去除了因子在每個(gè)被加項(xiàng)共享一個(gè)參數(shù)的約束,使得模型具有更強(qiáng)的擬合數(shù)據(jù)能力,并通過控制特征選擇過程避免模型的過擬合。
相對于因子分解機(jī),它將因子的選擇過程嵌入算法求解過程中。算法每輪迭代,會(huì)自動(dòng)根據(jù)當(dāng)前模型,從所有特征中貪婪選擇一個(gè)最優(yōu)的作為因子加入并更新模型。
解構(gòu)智能因子分解機(jī)
在智能因子分解機(jī)中,特征因子的加入方式有兩種,一種是作為起始因子加項(xiàng),另一種是作為加項(xiàng)中的一個(gè)乘積項(xiàng),具體方式取決于模型對于交叉項(xiàng)的控制方式。
添加方式:因子添加方式不同,通過控制添加過程即可生成不同的因子分解機(jī)。
按照深度優(yōu)先的方式,優(yōu)先將加項(xiàng)的階數(shù)添加到指定最高階,然后生成一個(gè)新的加項(xiàng),直到滿足一定事先指定的條件(擬合精度或者最大加項(xiàng)條件)。
按照寬度優(yōu)先的方式,先生成初始(K=1)的加項(xiàng),然后生成高一階(K=2)的加項(xiàng),直到滿足一定事先指定的條件。
按照寬度和深度競爭的方式,每次添加特征嘗試深度和寬度方向,比較兩個(gè)方向添加的效果再?zèng)Q定。
窮舉選取最優(yōu)特征:對于每個(gè)特征,通過計(jì)算其加入模型后帶來的增益來選擇,例如增益為訓(xùn)練數(shù)據(jù)的擬合程度。通常,為了簡化計(jì)算,可固定已有模型,將特征加入后對其參數(shù)求解,獲得更新模型。在這種情況下,參數(shù)求解往往非常方便,在一些擬合目標(biāo)下甚至有閉式解。
盡管每次選擇需要計(jì)算所有特征,但可通過一次掃描所有訓(xùn)練數(shù)據(jù)來同時(shí)估算所有特征的相關(guān)統(tǒng)計(jì)量,根據(jù)這些統(tǒng)計(jì)量計(jì)算選擇最優(yōu)特征。
可并行實(shí)現(xiàn):智能因子分解機(jī)可以很容易地通過多線程和多個(gè)集群分布式來并行實(shí)現(xiàn),從而大幅提升速度。由于特征的統(tǒng)計(jì)量可以并行計(jì)算,這樣就能通過多線程分布到一個(gè)集群計(jì)算機(jī)上便于計(jì)算。
FM和智能因子分解機(jī)
技術(shù)對比
智能因子分解機(jī)與FM的最大區(qū)別在于,前者只考慮其中部分交互特征,而FM則對文本特征間的所有交互特征建模。舉例來說,假設(shè)現(xiàn)在有三個(gè)文本特征:用戶、物品、心情。在智能因子分解機(jī)中,只考慮(用戶,物品)和(用戶,心情)交互。如果(物品,心情)交互特征無效,那么在FM中,(物品,心情)對應(yīng)的隱向量的預(yù)估將會(huì)不準(zhǔn)確,對預(yù)測函數(shù)來說就是引入噪音。
另一個(gè)區(qū)別在于,智能因子分解機(jī)是逐步地學(xué)習(xí)隱特征矩陣,不被共享以計(jì)算其他因子分解的權(quán)重。例如,在第一步中選取(用戶,物品),第二步選取(用戶,心情),兩次用戶對應(yīng)的隱特征矩陣不一樣。相較FM它可能失去推廣性的優(yōu)勢,可將智能因子分解機(jī)當(dāng)作一個(gè)特征選擇算法,只對選取的特征建模。GBFM-Opt是GBFM的變體,經(jīng)過S步后訓(xùn)練程序停止,得到S交互特征并充分優(yōu)化。
最重要的區(qū)別是急劇降低了計(jì)算復(fù)雜度。傳統(tǒng)的FM每選一次特征的復(fù)雜度都為O(N),而特征選擇次數(shù)通常為指數(shù)級。智能因子分解機(jī)使用貪心特征篩選算法,計(jì)算復(fù)雜度為O(n · N),N為訓(xùn)練數(shù)據(jù)大小,n是層數(shù)。在每一層中,增益函數(shù)可通過掃描訓(xùn)練數(shù)據(jù)集來計(jì)算。按照增益計(jì)算方法,最優(yōu)特征篩選也可通過訓(xùn)練數(shù)據(jù)集一次運(yùn)行得到。通常,這里n?N,在雙向因子分解機(jī)中,n=2。因此計(jì)算成本為O(N)。
實(shí)驗(yàn)結(jié)果對比
我們將兩種模型在兩個(gè)數(shù)據(jù)集中展開實(shí)驗(yàn):一個(gè)是人造數(shù)據(jù)集,另一個(gè)是真實(shí)數(shù)據(jù)集,來自騰訊微博。
人造數(shù)據(jù)集:由于只有很小的公共數(shù)據(jù)集包含多種文本特征,我們創(chuàng)建了一個(gè)人造數(shù)據(jù)集進(jìn)行比較。數(shù)據(jù)產(chǎn)生過程為:假設(shè)有m個(gè)文本特征,從中選取部分兩兩交互特征,其隱向量服從均值為0方差為0.5的高斯分布,然后按類似FM的預(yù)測函數(shù)生成評分值,評分值被映射到1~5。
騰訊微博數(shù)據(jù)集:騰訊微博是中國最大的社交網(wǎng)絡(luò)之一,該數(shù)據(jù)集是為2012年KDD Cup而設(shè)計(jì)的。其中包含了兩個(gè)月內(nèi)230萬用戶的名人推薦記錄。系統(tǒng)在特定時(shí)間向用戶推薦一位名人,用戶的反饋為接受或拒絕。此數(shù)據(jù)集包含豐富文本信息,如用戶年齡、性別、物品屬性、時(shí)間信息等。此外,還能提取到會(huì)話信息,例如在此條推薦前的推薦記錄數(shù)量。將此數(shù)據(jù)集根據(jù)時(shí)間分成訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)。測試數(shù)據(jù)再進(jìn)一步被分為公開和非公開集合用來獨(dú)立評估。此數(shù)據(jù)集非常稀疏,平均每個(gè)用戶只有兩個(gè)正向記錄(接受推薦)。除此之外,測試數(shù)據(jù)中近70%的用戶在訓(xùn)練數(shù)據(jù)中沒有出現(xiàn)過。
對人造數(shù)據(jù)集,我們使用兩個(gè)指標(biāo)MAE和RMSE來衡量不同方法的預(yù)測質(zhì)量,值越小說明效果越好。對于騰訊微博數(shù)據(jù), MAP@k被用作指標(biāo),值越大說明效果越好。
在實(shí)驗(yàn)中,我們比較了FM、PMF(只用“用戶,物品”矩陣做出推薦)和百度提出的GBFM和GBFM-Opt四種方法。
根據(jù)實(shí)驗(yàn)結(jié)果,可得出以下結(jié)論。
運(yùn)用附加信息的重要性。FM、GBFM和GBFM-Opt的表現(xiàn)大大優(yōu)于PMF并不奇怪。它揭示了在文本感知推薦中運(yùn)用附加信息的重要性。在騰訊微博數(shù)據(jù)中更為重要,因?yàn)闇y試數(shù)據(jù)集中的大部分用戶在訓(xùn)練數(shù)據(jù)中并不存在,這意味著PMF根本無法處理它們。
GBFM能學(xué)習(xí)優(yōu)質(zhì)的交互特征,GBFM和GBFM-Opt模型均表現(xiàn)良好。在人造數(shù)據(jù)集中,就RMSE這個(gè)指標(biāo)來說,F(xiàn)M相比PMF減法降低了0.066,GBFM相比FM進(jìn)一步降低了0.026。由于人造數(shù)據(jù)是從部分雙向交互特征中產(chǎn)生的,這些結(jié)果表現(xiàn)了GBFM能學(xué)習(xí)優(yōu)質(zhì)的交互特征。
選取優(yōu)質(zhì)交互特征更好。對于騰訊微博的數(shù)據(jù),就 MAP@3來說,相較PMF,F(xiàn)M提高了2.25%。GBFM還能進(jìn)一步提高0.4%。此結(jié)果證實(shí)了選取優(yōu)質(zhì)交互特征比考慮所有雙向交互特征更好。
驗(yàn)證被選取的交互特征對推薦是否有效。GBFM-Opt的表現(xiàn)可用來證明被選取的交互特征對推薦是否有效。在兩個(gè)數(shù)據(jù)集中,都比GBFM表現(xiàn)更好。相較GBFM-Opt,GBFM優(yōu)化不充分,這可能是GBFM-Opt表現(xiàn)更優(yōu)的原因。騰訊微博數(shù)據(jù)更稀疏,特征學(xué)習(xí)更重要,這也解釋了GBFM-Opt為什么只比GBFM稍有改善。
總結(jié)
智能因子分解機(jī)提出了一種高效的交互特征篩選算法,相較于因子分解機(jī)算法,它將特征選擇算法與因子分解機(jī)融合在統(tǒng)一的框架中, 可自動(dòng)學(xué)習(xí)特征,替代人工特征工程,極大提升了因子分解機(jī)的應(yīng)用效率。在人造數(shù)據(jù)和真實(shí)數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果都證明,此方法的有效性優(yōu)于FM和現(xiàn)階段其他方法。
在今后的研究中,我們還有以下幾個(gè)有趣的方向值得討論:
- 在更多的數(shù)據(jù)集上嘗試智能分解機(jī)算法;
- 如何改進(jìn)特征學(xué)習(xí)算法;
- 如何有效處理除了離散特征外的其他特征。
夏粉:百度科學(xué)家,就職于百度大數(shù)據(jù)實(shí)驗(yàn)室(bdl.baidu.com),十年以上機(jī)器學(xué)習(xí)研究經(jīng)驗(yàn),曾在機(jī)器學(xué)習(xí)頂級會(huì)議ICML、NIPS 等發(fā)表多篇論文。