矩陣分解與圖計(jì)算框架_數(shù)據(jù)分析師

矩陣分解是推薦系統(tǒng)常用的手段,經(jīng)常用來做用戶偏好預(yù)測.在當(dāng)下的推薦系統(tǒng)中,我們得到用戶對于物品的評分矩陣往往是非常稀疏的,一個有m個用 戶,n個商品的網(wǎng)站,它所收集到的m*n用戶評分矩陣R可能只有不到萬分之一的數(shù)據(jù)非零.矩陣分解算法常用來構(gòu)造出多個矩陣, 用這些矩陣相乘的結(jié)果R’來擬合原來的評分矩陣R，目標(biāo)是使得到的矩陣R’在R的非零元素那些位置上的值盡量接近R中的元素，同時對于R中非零值進(jìn)行補(bǔ) 全.我們定義R和R’之間的距離,把它作為優(yōu)化的目標(biāo),那么矩陣分解就變成了最優(yōu)化問題,而這類最優(yōu)化問題常用梯度下降的方法來求出一個局部最優(yōu)解。最近 我們就對于這個問題進(jìn)行了一下預(yù)研，發(fā)現(xiàn)用分布式圖計(jì)算框架來解決這類問題比較方便流暢,尤其是在矩陣非常稀疏的時候..

1:SGD(Stochastic Gradient Descent)隨機(jī)梯度下降的公式推導(dǎo)

設(shè)評分矩陣R中的每個不為0的元素為R_ui,所有的不為0的元素對應(yīng)的下標(biāo)對(u,i)組成的集合為S,我們認(rèn)為存在一個K維的隱空間,用戶偏好在隱空間可以表示為一個m k的矩陣P,物品偏好在隱空間表示為一個k n的矩陣Q. P是m k的矩陣,每一行p_u表示用戶u在K維隱空間上的偏好, Q是k n的矩陣,每一列表示是的是物品i在K維空間上的特性. 第u個用戶的偏好可以記為p_u ,是一個1 k的向量,第i個商品的偏好記為q_i,是一個k 1的向量,用戶u對于物品i的打分預(yù)估值就是p_u*q_i,整個預(yù)測的誤差可以記為

(1)式可以理解為對于所有有預(yù)測的數(shù)據(jù)記錄,評分預(yù)測值和實(shí)際值的差值平方和,通常用這個做為最初的損失函數(shù)(loss function).我們希望任何一個p_u, q_i的值都不能過大,這樣容易出現(xiàn)過擬合的現(xiàn)象,所以我們給(1)加上一個正則化項(xiàng),于是(1)式變?yōu)?/span>

其中分別是p_u,q_i 的二范數(shù),之所以選擇二范數(shù)是因?yàn)槲覀冋J(rèn)為用戶偏好，物品特性這些維度上的分值分布是符合正態(tài)分布的，這種情況下常使用二范數(shù)，即向量所有元素的平方和. （對于L0,L1,L2的深入探討詳見參考資料1）.我們的目標(biāo)就是找到矩陣P和矩陣Q,使得(2)的值最小.因?yàn)?2)是左邊是個連續(xù)函數(shù),所以極值出 現(xiàn)在梯度為0的時候,所以我們可以通過求梯度的方法得到使得L最小的Q和P

(3)式就是L對于p_u的梯度R(u)表示所有用戶u評價過的物品,從(3)式中可以看出,一個用戶的在K維空間的向量,只和用戶自身的以及他 評價過的物品的K維空間上的向量有關(guān).(3)的結(jié)果是一個K維的向量,每個位置上的元素對應(yīng)的是用戶u在K維空間的向量對應(yīng)的梯度值 類似地,我們可以得到

通過對于(3) (4)兩個式子的對比我們可以發(fā)現(xiàn)它們的形式是一致的,唯一不同的就是p,q呼喚了位置,一個是在所有的用戶點(diǎn)上通過相鄰物品點(diǎn)的值進(jìn)行計(jì)算 (i∈R(u)),一個是在所有的物品點(diǎn)上通過相鄰用戶點(diǎn)的值進(jìn)行計(jì)算(u∈R(i)) .和(3)式的計(jì)算結(jié)果類似,(4)式也是一個K維的向量,每個位置上的元素對應(yīng)的是物品i在K維空間的值對應(yīng)的梯度值. 如果我們把學(xué)習(xí)率記為

整個迭代的過程可以看作在一個K維超空間的曲面上尋找極值點(diǎn)的過程,每一步都尋找一個比之前更低的一個位置,如下圖所示,圖中的θ1,θ2可以認(rèn) 為相當(dāng)于P和Q,差別就是一個是值,一個是矩陣,但是他們都是某個凸函數(shù)的輸入值.從另一個角度來說,一個值也可以看成是一個1 * 1的矩陣,如果P和Q退化為一個1 * 1的矩陣的話,那就是θ1,θ2了.

上面的說法直接理解可能比較抽象,我們用一個例子來說明.圖1說明了梯度下降就是在一個超空間的曲面上尋找一個點(diǎn)，這個點(diǎn)對應(yīng)的J(θ),即損失 函數(shù)(loss function)最小，步長η就是上圖每條線段的長度，-?L/?Pu表示了接下來往哪個方向走。圖一表示的是一個梯度下降的過程得到了全局最優(yōu)解。但 是這個情況還是比較少見的，更多的是像圖二中的情況，得到一個局部最優(yōu)解。為了避免出現(xiàn)局部最優(yōu)解比較差的情況，我們通常可以多次隨機(jī)地初始化Q和P矩 陣，相當(dāng)于是選擇不同的初始點(diǎn)開始進(jìn)行梯度下降，選擇一個損失函數(shù)(loss function)最小的那一次對應(yīng)的P,Q值作為梯度下降的結(jié)果。

2:SGD的一個例子說明

下圖是我目前得到的一個評分文件,3列的含義分別是UID:User ID,IID:Item ID,score:用戶評分.可以看到一共有3個用戶,4個物品.

他們可以構(gòu)成一個3 * 4的評分矩陣矩陣.我現(xiàn)在取k=2,要把它們分解成為一個3 2的P矩陣和一個2 4的Q矩陣.

首先初始化P和Q矩陣,一般都用符合正態(tài)分布的隨機(jī)數(shù)X~N(0,1)來填充矩陣.

現(xiàn)在我計(jì)算u=1時的?L/?Pu,取λ的值為1 首先計(jì)算u=1,i=1這個評分記錄帶來的梯度分量,即u=1,i=1時的的值,這時

然后計(jì)算u=1,i=2這個評分帶來的梯度分量:

所以,u=1時的梯度為

剛才提到的迭代公式: p_u=p_u-η ?L/?Pu,其中η表示學(xué)習(xí)率,就是平時我們說的梯度下降時的步長,取η=0.05 于是有

可見,通過這一次對于p_1的梯度下降, p_1對應(yīng)的向量從隨機(jī)產(chǎn)生的

我們來驗(yàn)證一下這個變化是否是的預(yù)估的值更加準(zhǔn)確了 原來對于R_11的估計(jì)誤差為

新的對于R_11的估計(jì)誤差為

確實(shí)比原來有提升.按照上述步驟分別更新所有P矩陣中的p_i,然后用更新好的P矩陣,用公式(4)中的方法更新Q,再用更新好的Q第二次更新P.這種迭代方法最終可以使得|R-P Q|的值縮小,當(dāng)|R-P Q|在下一輪迭代的過程中不再變小時,我們就認(rèn)為在當(dāng)前的學(xué)習(xí)率η下,P,Q已經(jīng)得到了局部最優(yōu)解.

3:用圖計(jì)算框架來解SGD

通過剛才的演示你可以發(fā)現(xiàn),每次某個用戶的K維向量需要更新的時候,只有這個用戶評分過的商品對應(yīng)的K維向量會參加運(yùn)算, 和其他的元素?zé)o關(guān).而且整個評分矩陣在現(xiàn)實(shí)應(yīng)用中往往是非常稀疏的.這種計(jì)算過程和數(shù)據(jù)分布的特點(diǎn)使得這類問題用圖計(jì)算框架來解決比起傳統(tǒng)的 mapreduce過程更加流暢高效. 對于表1的評分矩陣我們可以用一個二部圖來表示它,每個點(diǎn)分別表示一個用戶或者一個物品,用戶對于物品的評分就是用戶點(diǎn)和物品點(diǎn)之間邊的屬性,這個二部圖 如圖三.  圖三:根據(jù)評分矩陣生成二部圖

 圖四:每個點(diǎn)的K維向量初始化后的效果演示.

 圖五:SGD第一步數(shù)據(jù)在圖計(jì)算框架中的傳輸演示.

正如上文說的,我們要初始化Q和P矩陣,實(shí)際上就是在每個點(diǎn)上初始化一個K維的數(shù)組,這個數(shù)組表示了這個點(diǎn)的在K維空間的映射結(jié)果. . 用圖計(jì)算框架來做SGD遵循以下步驟來進(jìn)行迭代: 第零步:初始化,生成可以表達(dá)Q矩陣,P矩陣和評分矩陣的圖數(shù)據(jù)結(jié)構(gòu)(如圖四),令L=0 第一步,每個用戶節(jié)點(diǎn)接受邊上的值以及每個和這個用戶評過分的物品的K維向量,如圖五所示. 第二步,每個用戶點(diǎn)根據(jù)自己每條邊上傳來的值計(jì)算條邊和邊上的鄰居造成的梯度分量,將這些梯度分量相加,得到這輪迭代的梯度值. 第三步,每個用戶點(diǎn)將自己得到的梯度值,根據(jù)公式p_u=p_u-η ?L/?Pu更新自己的K維向量,也就是P矩陣得到了更新. 第四步,每個物品點(diǎn)接受邊上的評分值以及每個和對于這個物品進(jìn)行過評分的所有用戶的K維向量. 第五步, 每個物品點(diǎn)根據(jù)自己每條邊上傳來的值計(jì)算條邊和邊上的鄰居造成的梯度分量,將這些梯度分量相加,得到這輪迭代的梯度值. 第六步, 每個物品點(diǎn)將自己得到的梯度值,根據(jù)公式q_i=q_i-η ?L/?qi更新自己的K維向量,也就是Q矩陣得到了更新. 第七步,根據(jù)檢測當(dāng)前的L值是否比上次的L小,如果是,回到第一步繼續(xù)迭代.如果否則表示迭代介紹,按順序遍歷圖中的用戶和物品節(jié)點(diǎn),讀取每個節(jié)點(diǎn)的K維向量,組合后輸出矩陣Q和P.

 圖六:用SGD做矩陣分解流程圖

4:通過逐步減小參與計(jì)算的數(shù)據(jù)量加速

在上面的介紹中我們可以看到整個的迭代都是矩陣Q和矩陣P不斷變化,使得P*Q的結(jié)果接近R的過程。對于某些用戶和物品節(jié)點(diǎn)而言,這些點(diǎn)的K維向量很快就收斂到了我們的目標(biāo)值,即對于這些用戶節(jié)點(diǎn)而言,

對于某些點(diǎn),誤差值在迭代開始沒幾輪的時候就達(dá)到了目標(biāo)范圍,這個某些點(diǎn)提前結(jié)束迭代的功能對于物品節(jié)點(diǎn)也成立.這些點(diǎn)可以不用參加之后的迭代,在基于spark的圖計(jì)算框架graphx提供了這樣功能的函數(shù)：

mapReduceTriplets(sendMsg, mergeMsg, Some((newVerts, activeDir))

這個函數(shù)是GraphX中最核心的一個函數(shù)，表示對于圖中的所有以兩個點(diǎn)一條邊組成的三元組Triplets進(jìn)行一次數(shù)據(jù)傳輸與計(jì)算，具體過程 為：sendMsg，相當(dāng)于map，應(yīng)用于每一個Triplet上，生成一個或者多個消息，消息以Triplet關(guān)聯(lián)的兩個頂點(diǎn)中的任意一個或兩個為目標(biāo) 頂點(diǎn)；mergeMsg，相當(dāng)于reduce，應(yīng)用于每一個Vertex上，將發(fā)送給每一個頂點(diǎn)的消息合并起來。（對于內(nèi)存式圖計(jì)算框架graphx更詳 細(xì)的介紹可以見參考資料2），前面的兩個參數(shù)別是在”think like vertex”的情況下每個點(diǎn)對于鄰居節(jié)點(diǎn)發(fā)出的信息sendMsg和對于自己的鄰居發(fā)給自己的信息的處理函數(shù)mergeMsg .而第三個參數(shù)確定了滿足一定條件的點(diǎn)參與這一次的圖的迭代. GraphX針對這種應(yīng)用場景進(jìn)行了較為深層的優(yōu)化 沒有更新的頂點(diǎn)在下一輪迭代時不需要向鄰居重新發(fā)送消息。因此，mapReduceTriplets遍歷邊時，如果一條邊鄰居點(diǎn)值在上一輪迭代時沒有更 新，則直接跳過，避免了大量無用的計(jì)算和通信。 這樣做的好處是，隨著收斂的點(diǎn)越來越多,每輪迭代參與計(jì)算的點(diǎn)越來越少,每次迭代需要的通訊和計(jì)算開銷都變小了,每次迭代的時間也逐步減小,如下圖所示:

圖七:在Netflix數(shù)據(jù)集上用SGD做矩陣分解耗時圖 整個的算法效果可以從上圖中看到的，隨著迭代次數(shù)增加，整個每次迭代參與的用戶和物品點(diǎn)變少，耗時迅速減少，整個算法很快就收斂了，這正是使用圖計(jì)算框 架，尤其是經(jīng)過底層優(yōu)化后的圖計(jì)算框架（比如graphx）的優(yōu)勢所在。更詳細(xì)的介紹巨型圖的存儲以及基于分布式圖存儲，圖計(jì)算框架并行計(jì)算時的通信方式 的優(yōu)化可以看參考資料3，4。

5:結(jié)論

對于很多的迭代問題，尤其是涉及到矩陣分解的問題，使用圖計(jì)算框架如graphx比起使用傳統(tǒng)的mapreduce不論是在編碼效率還是執(zhí)行速度 上都有著有明顯的優(yōu)勢。圖計(jì)算框架不僅僅是用來解決“圖”，即所謂網(wǎng)絡(luò)科學(xué)的問題，它在傳統(tǒng)的大規(guī)模機(jī)器學(xué)習(xí)領(lǐng)域也有這廣泛的應(yīng)用場景。除了文中演示的矩 陣分解問題，概率圖模型（如PLSA，LDA）用圖計(jì)算框架也可以完成。據(jù)說google的圖計(jì)算框架pregel承擔(dān)了google20%的計(jì)算任務(wù)， 可惜它沒有開源，不能一看究竟。開源圖計(jì)算框架的性能提升，應(yīng)用場景擴(kuò)展有著很多潛力供將來深入挖掘