矩陣分解與圖計算框架_數據分析師

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

1:SGD(Stochastic Gradient Descent)隨機梯度下降的公式推導

設評分矩陣R中的每個不為0的元素為R_ui,所有的不為0的元素對應的下標對(u,i)組成的集合為S,我們認為存在一個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的打分預估值就是p_u*q_i,整個預測的誤差可以記為

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

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

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

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

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

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

2:SGD的一個例子說明

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

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

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

現在我計算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,其中η表示學習率,就是平時我們說的梯度下降時的步長,取η=0.05 于是有

可見,通過這一次對于p_1的梯度下降, p_1對應的向量從隨機產生的

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

新的對于R_11的估計誤差為

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

3:用圖計算框架來解SGD

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

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

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

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

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

4:通過逐步減小參與計算的數據量加速

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

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

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

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

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

5:結論

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