達觀資料周顥鈺：想寫出人見人愛的推薦系統，先了解經典矩陣分解技術
網路中的資訊量呈現指數式增長，隨之帶來了資訊過載問題。推薦系統是大資料時代下應運而生的產物，目前已廣泛應用於電商、社交、短視訊等領域。本文將針對推薦系統中基於隱語義模型的矩陣分解技術來進行討論。
NO. 1 評分矩陣、奇異值分解與Funk-SVD
對於一個推薦系統，其使用者資料可以整理成一個user-item矩陣。矩陣中每一行代表一個使用者，而每一列則代表一個物品。若使用者對物品有過評分，則矩陣中處在使用者對應的行與物品對應的列交叉的位置表示使用者對物品的評分值。這個user-item矩陣被稱為評分矩陣。 
上圖即為評分矩陣的一個例子。其中的？表示使用者還沒有對物品做出評價，而推薦系統最終的目標就是對於任意一個使用者，預測出所有未評分物品的分值，並按分值從高到低的順序將對應的物品推薦給使用者。
說到矩陣分解技術，首先想到的往往是 特徵值分解（eigendecomposition） 與 奇異值分解（Singular value decomposition，SVD） 。
對於 特徵值分解 ，由於其只能作用於方陣，因此並不適合分解評分矩陣這個場景。
而對於 奇異值分解 ，其具體描述為：假設矩陣M是一個m*n的矩陣，則一定存在一個分解 
Line"/> ，其中U是m*m的正交矩陣，V是n*n的正交矩陣，Σ是m*n的對角陣，可以說是完美契合分解評分矩陣這個需求。其中，對角陣Σ還有一個特殊的性質，它的所有元素都非負，且依次減小。這個減小也特別快，在很多情況下，前10%的和就佔了全部元素之和的99%以上，這就是說我們可以使用最大的k個值和對應大小的U、V矩陣來近似描述原始的評分矩陣。
於是我們馬上能得到一個解決方案：對原始評分矩陣M做奇異值分解，得到U、V及Σ，取Σ中較大的k類作為隱含特徵，則此時M(m*n)被分解成U(m*k) Σ(k*k)V(k*n)，接下來就可以直接使用矩陣乘法來完成對原始評分矩陣的填充。但是實際上，這種方法存在一個致命的缺陷——奇異值分解要求矩陣是稠密的。也就是說SVD不允許待分解矩陣中存在空白的部分，這一開始就與我們的問題所衝突了。
當然，也可以想辦法對缺失值先進行簡單的填充，例如使用全域性平均值。然而，即使有了補全策略，在實際應用場景下，user和item的數目往往是成千上萬的，面對這樣的規模傳統SVD演算法O(n^3)的時間複雜度顯然是吃不消的。因此，直接使用傳統SVD演算法並不是一個好的選擇。（達觀資料周顥鈺）
既然傳統SVD在實際應用場景中面臨著稀疏性問題和效率問題， 那麼有沒有辦法避開稀疏問題，同時提高運算效率呢？
實際上早在06年，Simon Funk就提出了Funk-SVD演算法，其主要思路是將原始評分矩陣M（m*n）分解成兩個矩陣P（m*k）和Q（k*n），同時僅考察原始評分矩陣中有評分的項分解結果是否準確，而判別標準則是均方差。
即對於矩陣M(m*n)，我們想辦法將其分解為P(m*k)、Q(k*n)，此時對於原始矩陣中有評分的位置MUI來說，其在分解後矩陣中對應的值就是
那麼對於整個評分矩陣而言，總的損失就是 
只要我們能想辦法最小化上面的損失SSE，就能以最小的擾動完成對原始評分矩陣的分解，在這之後只需要用計算M’ 的方式來完成對原始評分矩陣的填充即可。（達觀資料周顥鈺）
這種方法被稱之為 隱語義模型（Latent factor model，LFM） ，其演算法意義層面的解釋為通過 隱含特徵（latent factor） 將user興趣與item特徵聯絡起來。
對於原始評分矩陣R，我們假定一共有三類隱含特徵，於是將矩陣R（3*4）分解成使用者特徵矩陣P（3*3）與物品特徵矩陣Q（3*4）。考察user1對item1的評分，可以認為user1對三類隱含特徵class1、class2、class3的感興趣程度分別為P11、P12、P13，而這三類隱含特徵與item1相關程度則分別為Q11、Q21、Q31。
回到上面的式子
可以發現使用者U對物品I最終的評分就是由各個隱含特徵維度下U對I感興趣程度的和，這裡U對I的感興趣程度則是由U對當前隱含特徵的感興趣程度乘上I與當前隱含特徵相關程度來表示的。
於是，現在的問題就變成了如何求出使得SSE最小的矩陣P和Q。
NO. 2 隨機梯度下降 法
在求解上文中提到的這類無約束最優化問題時， 梯度下降法（Gradient Descent） 是最常採用的方法之一，其核心思想非常簡單，沿梯度下降的方向逐步迭代。梯度是一個向量，表示的是一個函式在該點處沿梯度的方向變化最快，變化率最大，而梯度下降的方向就是指的負梯度方向。
根據梯度下降法的定義，其迭代最終必然會終止於一階導數（對於多元函式來說則是一階偏導數）為零的點，即駐點。對於可導函式來說，其極值點一定是駐點，而駐點並不一定是極值點，還可能是鞍點。另一方面，極值點也不一定是最值點。下面舉幾個簡單的例子。
上圖為函式 
。從圖中可以看出，函式唯一的駐點 （0，0）為其最小值點。
上圖為函式 
。其一階導數為 
，從而可知其同樣有唯一駐點（0，0）。從圖中可以看出，函式並沒有極值點。
上圖為函式 
。從影象中可以看出，函式一共有三個駐點，包括兩個極小值點和一個極大值點，其中位於最左邊的極小值點是函式的最小值點。
上圖為函式 
。其中點 （0，0，0）為其若干個鞍點中的一個。
從上面幾幅函式影象中可以看出梯度下降法在求解最小值時具有一定的侷限性，用一句話概括就是，目標函式必須是凸函式。關於凸函式的判定，對於一元函式來說，一般是求二階導數，若其二階導數非負，就稱之為凸函式。對於多元函式來說判定方法類似，只是從判斷一元函式的單個二階導數是否非負，變成了判斷所有變數的二階偏導數構成的 黑塞矩陣（Hessian Matrix） 是否為半正定矩陣。判斷一個矩陣是否半正定可以判斷所有特徵值是否非負，或者判斷所有主子式是否非負。
回到上面funk-svd的最優化問題上來。經過一番緊張刺激的計算之後，可以很遺憾地發現，我們最終的目標函式是非凸的。這就意味著單純使用梯度下降法可能會找到極大值、極小值或者鞍點。這三類點的穩定性按從小到大排列依次是極大值、鞍點、極小值，考慮實際運算中，浮點數運算都會有一定的誤差，因此最終結果很大機率會落入極小值點，同時也有落入鞍點的概率。而對於極大值點，除非初始值就是極大值，否在幾乎不可能到達極大值點。
為了從鞍點和極小值點中脫出，在梯度下降法的基礎上衍生出了各式各樣的改進演算法，例如動態調整步長（即學習率），利用上一次結果的動量法，以及 隨機梯度下降 法 （StochasticGradient Descent， SGD） 等等。實際上，這些優化演算法在當前最火熱的深度學習中也佔據著一席之地，例如adagrad、RMSprop，Adam等等。而本文則將主要介紹一下 隨機梯度下降 法。（達觀資料周顥鈺）
隨機梯度下降 法主要是用來解決求和形式的優化問題 ，與上面需要優化的目標函式一致。其思想也很簡單，既然對於求和式中每一項求梯度很麻煩，那麼幹脆就隨機選其中一項計算梯度當作總的梯度來使用好了。
具體應用到上文中的目標函式
SSE是關於P和Q的多元函式，當隨機選定U和I之後，需要列舉所有的k，並且對 
，以及 
求偏導數。整個式子中僅有 
這一項與之相關，通過鏈式法則可知
在實際的運算中，為了P和Q中所有的值都能得到更新，一般是按照線上學習的方式選擇評分矩陣中有分數的點對應的U、I來進行迭代。
值得一提的是，上面所說的各種優化都無法保證一定能找到最優解。有論文指出，單純判斷駐點是否是區域性最優解就是一個NPC問題，但是也有論文指出SGD的解能大概率接近區域性最優甚至全域性最優。
另外，相比於利用了黑塞矩陣的牛頓迭代法，梯度下降法在方向上的選擇也不是最優的。 牛頓法相當於考慮了梯度的梯度，所以相對更快。而由於其線性逼近的特性，梯度下降法在極值點附近可能出現震盪，相比之下牛頓法就沒有這個問題。
但是在實際應用中，計算黑塞矩陣的代價是非常大的，在這裡梯度下降法的優勢就凸顯出來了。 因此，牛頓法往往應用於一些較為簡單的模型，如邏輯迴歸。而對於稍微複雜一些的模型，梯度下降法及其各種進化版本則更受青睞。（達觀資料周顥鈺）
NO. 3 基於Funk-SVD的改進演算法
到這一步為止，我們已經能通過SGD找到一組分解方案了，然而對於填充矩陣的FunkSVD演算法本身而言，目前這個形式是否過於簡單了一些呢？
實際上，在Funk-SVD被提出之後，出現了一大批改進演算法。本文將介紹其中某些經典的改進思路。
1 正則化
對於所有機器學習演算法而言， 過擬合 一直是需要重視的一個問題，而加入正則化項則是防止過擬合的經典處理方法。對於上面的Funk-SVD演算法而言，具體做法就是在損失函式後面加入一個L2正則項，即
其中，λ為正則化係數，而整個求解過程依然可以使用 隨機梯度下降 來完成。
2 偏置
考察式子 
可以發現這個式子表明使用者U對物品 I 的評分全部是由U和I之間的聯絡帶來的。 然而實際上，有很多性質是使用者或者物品所獨有的。比如某個使用者非常嚴苛，不論對什麼物品給出的分數都很低，這僅僅與使用者自身有關。
又比如某個物品非常精美，所有使用者都會給出較高的分數，這也僅僅與物品自身有關。因此，只通過使用者與物品之間的聯絡來預測評分是不合理的，同時也需要考慮到使用者和物品自身的屬性。於是，評分預測的公式也需要進行修正。不妨設整個評分矩陣的平均分為σ，使用者U和物品I的偏置分別為 
和 
，那麼此時的評分計算方法就變成了
同時，誤差E除了由於M‘計算方式帶來的變化之外，也同樣需要加入U和I偏置的正則項，因此最終的誤差函式變成了
3 隱式反饋
對於實際的應用場景中，經常有這樣一種情況：使用者點選查看了某一個物品，但是最終沒有給出評分。
實際上，對於使用者點選檢視物品這個行為，排除誤操作的情況，在其餘的情況下可以認為使用者被物品的描述，例如貼圖或者文字描述等所吸引。這些資訊我們稱之為隱式反饋。事實上，一個推薦系統中有明確評分的資料是很少的，這類隱式資料才佔了大頭。
可以發現，在我們上面的演算法當中，並沒有運用到這部分資料。於是對於評分的方法，我們可以在顯式興趣+偏置的基礎上再新增隱式興趣，即
其中N(U)表示為使用者U提供了隱式反饋的物品的集合。這就是svd++演算法。
此時的損失函式也同樣需要加上隱式興趣的正則項，即 
4 對偶演算法
在上面的svd++中，我們是基於使用者角度來考慮問題的，很明顯我們同樣可以基於物品的角度來考慮問題。具體來說就是 
其中 N(I)表示為物品I提供了隱式反饋的使用者的集合。類似地，在損失函式中也需要加上隱式興趣的正則項。
在實際運用中，可以將原始的svd++得到的結果與對偶演算法得到的結果進行融合，使得預測更加準確。然而相比起物品的數目，使用者的數目往往是要高出幾個量級的，因此對偶演算法在儲存空間和運算時間的開銷上都將遠高於原始的svd++， 如何在效率和準確度之間找到平衡也是一個需要思考的問題。 （達觀資料周顥鈺）
NO. 4 請因子分解機
矩陣分解的思想除了直接應用在分解評分矩陣上之外，其思想也能用在其他地方，接下來介紹的 因子分解機（FactorizationMachine，FM） 就是一個例子。
對於經典的邏輯迴歸演算法，其sigmoid函式中的項實際上是一個線性迴歸
在這裡我們認為各個特徵之間是相互獨立的，而事實上往往有些特徵之間是相互關聯、相互影響的。 因此，就有必要想辦法捕捉這些特徵之間的相互影響。 簡單起見，先只捕捉二階的關係，即特徵之間兩兩之間的相互影響。具體反映到迴歸公式上，即為
具體來說就是使用 
來描述 
，對於w而言，其中可學習的項就對應了評分矩陣中有分值的項，而其他由於資料稀疏導致難以學習的項就相當於評分矩陣中的未評分項。這樣一來，不僅解決了資料稀疏性帶來的二階權重學習問題，同時對於引數規模，也從 
級別降到了O(kn)級別。
NO. 5 與DNN的結合
深度學習無疑是近幾年來最熱門的機器學習技術。注意到隱語義模型中，隱含特徵與深度學習中的embedding實際上是一回事，那麼是否有可能借助DNN來幫助我們完成矩陣分解的工作呢？
實際上，在YouTube的文章《Deep neural networks for YouTube recommendations》中，就已經有了相關技術的應用。
上圖是YouTube初排模型的圖示。具體的流程為：首先通過nlp技術，如word2vec，預訓練出所有物品的向量I表示；然後對於每一條使用者對物品的點選，將使用者的歷史點選、歷史搜尋、地理位置資訊等資訊經過各自的embedding操作，拼接起來作為輸入，經過MLP訓練後得到使用者的向量表示U；而最終則是通過 softmax 函式來校驗U*I的結果是否準確。
相比於傳統的矩陣分解演算法，使用DNN能為模型帶來非線性的部分，提高擬合能力。另一方面，還可以很方便地加入各式各樣的特徵，提高模型的準確度。（達觀資料周顥鈺）
NO. 6 矩陣分解的優缺點
矩陣分解有如下優點：
-
能將高維的矩陣對映成兩個低維矩陣的乘積，很好地解決了資料稀疏的問題；
-
具體實現和求解都很簡潔，預測的精度也比較好；
-
模型的可擴充套件性也非常優秀，其基本思想也能廣泛運用於各種場景中。
相對的，矩陣分解的缺點則有：
-
可解釋性很差，其隱空間中的維度無法與現實中的概念對應起來；
-
訓練速度慢，不過可以通過離線訓練來彌補這個缺點；
-
實際推薦場景中往往只關心topn結果的準確性，此時考察全域性的均方差顯然是不準確的。
NO. 7 總結
矩陣分解作為推薦系統中的經典模型，已經經過了十幾年的發展，時至今日依然被廣泛應用於推薦系統當中，其基本思想更是在各式各樣的模型中發揮出重要作用。 但是對於推薦系統來說，僅僅有一個好的模型是遠遠不夠的。影響推薦系統效果的因素非常之多。 想要打造一個一流的推薦系統，除了一個強大的演算法模型之外，更需要想方設法結合起具體業務，不斷進行各種嘗試、升級，方能取得最終的勝利。
參考文獻
【1】Simon Funk, http://sifter.org/~simon/journal/20061211.html
【2】Koren, Yehuda, Robert Bell, and Chris Volinsky. "Matrix factorization techniques for recommender systems." Computer 42.8 (2009).
【3】Jahrer, Michael, and Andreas Töscher. "Collaborative filteringensemble." Proceedings of the 2011 International Conference on KDD Cup 2011-Volume 18 . JMLR. org, 2011.
【4】Rendle, Steffen. "Factorizationmachines." Data Mining (ICDM), 2010 IEEE 10th International Conference on . IEEE, 2010.
【5】Covington, Paul, Jay Adams, and Emre Sargin. "Deep neural networks for youtube recommendations." Proceedings of the 10th ACM Conference on Recommender Systems . ACM, 2016.
關於作者：
周顥鈺，達觀資料演算法工程師，負責達觀資料個性化推薦系統的研發與優優化，研究推薦系統中的機器學習演算法及其具體應用，對各種機器學習演算法有濃厚興趣。