矩陣分解與圖計算框架_數(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中非零值進行補 全.我們定義R和R’之間的距離,把它作為優(yōu)化的目標(biāo),那么矩陣分解就變成了最優(yōu)化問題,而這類最優(yōu)化問題常用梯度下降的方法來求出一個局部最優(yōu)解。最近 我們就對于這個問題進行了一下預(yù)研，發(fā)現(xiàn)用分布式圖計算框架來解決這類問題比較方便流暢,尤其是在矩陣非常稀疏的時候..

1:SGD(Stochastic Gradient Descent)隨機梯度下降的公式推導(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ù)(loss function).我們希望任何一個p_u, q_i的值都不能過大,這樣容易出現(xiàn)過擬合的現(xiàn)象,所以我們給(1)加上一個正則化項,于是(1)式變?yōu)?/span>

其中分別是p_u,q_i 的二范數(shù),之所以選擇二范數(shù)是因為我們認(rèn)為用戶偏好，物品特性這些維度上的分值分布是符合正態(tài)分布的，這種情況下常使用二范數(shù)，即向量所有元素的平方和. （對于L0,L1,L2的深入探討詳見參考資料1）.我們的目標(biāo)就是找到矩陣P和矩陣Q,使得(2)的值最小.因為(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呼喚了位置,一個是在所有的用戶點上通過相鄰物品點的值進行計算 (i∈R(u)),一個是在所有的物品點上通過相鄰用戶點的值進行計算(u∈R(i)) .和(3)式的計算結(jié)果類似,(4)式也是一個K維的向量,每個位置上的元素對應(yīng)的是物品i在K維空間的值對應(yīng)的梯度值. 如果我們把學(xué)習(xí)率記為

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

上面的說法直接理解可能比較抽象,我們用一個例子來說明.圖1說明了梯度下降就是在一個超空間的曲面上尋找一個點，這個點對應(yīng)的J(θ),即損失 函數(shù)(loss function)最小，步長η就是上圖每條線段的長度，-?L/?Pu表示了接下來往哪個方向走。圖一表示的是一個梯度下降的過程得到了全局最優(yōu)解。但 是這個情況還是比較少見的，更多的是像圖二中的情況，得到一個局部最優(yōu)解。為了避免出現(xiàn)局部最優(yōu)解比較差的情況，我們通?？梢远啻坞S機地初始化Q和P矩 陣，相當(dāng)于是選擇不同的初始點開始進行梯度下降，選擇一個損失函數(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)分布的隨機數(shù)X~N(0,1)來填充矩陣.

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

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

所以,u=1時的梯度為

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

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

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

新的對于R_11的估計誤差為

確實比原來有提升.按照上述步驟分別更新所有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:用圖計算框架來解SGD

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

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

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

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

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

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

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

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

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

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

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

5:結(jié)論

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