進階隐式矩陣分解——探讨如何實作更快的算法

<b>以下為譯文：</b>

<b></b>

<b>階隐式矩陣分解</b><b></b>

該算法通過求解項目因子<b>y</b>直接計算使用者因子<b>xu</b>： 

其中<b>cu</b>是使用者喜好置信度的向量，<b>pu</b>是使用者是否傾聽了藝術家的二進制偏好。項目因子以相同的方式構造，并且算法在計算項目因子和使用者因子之間疊代，直到其收斂。

其中，處理ytcuy+λi項是造成運算慢的原因。當用n個因子計算時 - 建構該矩陣相對于非零項的複雜度是o（n2），解這個方程也是o（n3），并且必須每個使用者都要進行相同的處理。矩陣的稀疏性或因子的數量決定了運算時間的長短。

<b>使用</b><b>conjugate</b>

gradient<b>（共轭梯度）方法加快速度</b><b></b>

共轭梯度法可以在任何二次疊代中最小化任何二維二次函數 – 不論起始點在哪（點選選擇一個新點）。與非線性共轭梯度方法不同，它也不必為了找到适當的步長而進行線路搜尋，因為可以直接計算确切的最佳步長。

這裡很酷的是，我們甚至不需要在這種情況下建立ytcuy+λi矩陣，更不用說解決它了。所有需要的是将該矩陣乘以目前搜尋方向 -這裡不使用原始論文中的技巧實作每個使用者矩陣處理，公式為：ytcuy = yty

+ yt（cu-i）y以及預計算所有使用者的yty矩陣。

在python中對這個算法的完整實作是：

def alternating_least_squares_cg(cui, factors, regularization=0.01, iterations=15):

users, items = cui.shape

     # 初始化随機因子

    x

= np.random.rand(users, factors) * 0.01

    y

= np.random.rand(items, factors) * 0.01

     cui, ciu = cui.tocsr(), cui.t.tocsr()

     for iteration in range(iterations):

least_squares_cg(cui, x, y, regularization)

least_squares_cg(ciu, y, x,

regularization)

     return x, y

    def least_squares_cg(cui, x, y, regularization, cg_steps=3):

users, factors = x.shape

    yty = y.t.dot(y) + regularization * np.eye(factors)

    for u in range(users):

# 從前次疊代開始

x = x[u]

        # 計算 r = ytcupu - (ytcuy.dot(xu), 不用計算ytcuy

r = -yty.dot(x)

for i, confidence in nonzeros(cui, u):

r += (confidence - (confidence - 1) * y[i].dot(x)) * y[i]

        p = r.copy()

rsold = r.dot(r)

            for it in range(cg_steps):

# 計算ap = ytcuyp 而不是 ytcuy

ap = yty.dot(p)

                ap += (confidence - 1) * y[i].dot(p) * y[i]

            # 标準cg更新

alpha = rsold / p.dot(ap)

x += alpha * p

r -= alpha * ap

rsnew = r.dot(r)

p = r + (rsnew / rsold) * p

rsold = rsnew

x[u] = x

<b>測量代碼的速度和精度</b><b></b>

共轭梯度方法的速度确令人感到興奮。為了測試準确性，我隻是計算每次疊代的訓練損失，并與我使用cholesky求解器在每次疊代得到确切解決方案的原始實作進行比較。因為我們隻是在同一損失函數上比較優化方法，訓練損失足以證明每個方法實際上是收斂的。在具有100個因子的last.fm資料集上運作此操作的結果是：

論文中建議在每次疊代使用2個共轭梯度步長，但我發現使用3時與論文的結果更接近。事實上，在10次疊代之後，損失基本上與cholesky求解器相同。

在我的筆記本電腦上，每次疊代時間的基準測試顯示，随着因子數量的增長，速度有了大幅提升：

每次疊代使用3個共轭梯度步長，這個代碼的速度是50因子數時的3倍，是250因子時速度的19倍。事半功多倍的結果令人興奮不已。

<a href="https://promotion.aliyun.com/ntms/act/ambassador/sharetouser.html?usercode=lwju78qa&amp;utm_source=lwju78qa">數十款阿裡雲産品限時折扣中，趕緊點選領劵開始雲上實踐吧！</a>

文章原标題《<b>faster implicit matrix factorization</b>》，作者：<b>ben frederickson</b>，譯者：伍昆