導語：
上次給大家分享了本系列文章第一篇《【科普篇】推薦系統之矩陣分解模型》，第一篇用一個具體的例子介紹了MF是如何做推薦的。今天給大家帶來第二篇《【原理篇】推薦系統之矩陣分解模型》，第二篇講的是MF的數學原理，包括MF模型的目标函數和求解公式的推導等，敬請閱讀。
上一篇我們用一個簡單的例子講述了矩陣分解(Matrix Factorization, MF)是如何做推薦的，但沒有深入到算法的細節。如果想編寫自己的代碼實作MF，那麼就需要了解其中的細節了。本文是MF系列的第二篇文章，主要介紹了顯式矩陣分解和隐式矩陣分解的數學原理，包括模型思想、目标函數、優化求解的公式推導等，旨在為需要了解算法細節的同學提供參考。
1.顯式資料和隐式資料
MF用到的使用者行為資料分為顯式資料和隐式資料兩種。顯式資料是指使用者對item的顯式打分，比如使用者對電影、商品的評分，通常有5分制和10分制。隐式資料是指使用者對item的浏覽、點選、購買、收藏、點贊、評論、分享等資料，其特點是使用者沒有顯式地給item打分，使用者對item的感興趣程度都展現在他對item的浏覽、點選、購買、收藏、點贊、評論、分享等行為的強度上。
顯式資料的優點是行為的置信度高，因為是使用者明确給出的打分，是以真實反映了使用者對item的喜歡程度。缺點是這種資料的量太小，因為絕大部分使用者都不會去給item評分，這就導緻資料非常稀疏，同時這部分評分也僅代表了小部分使用者的興趣，可能會導緻資料有偏。隐式資料的優點是容易擷取，資料量很大。因為幾乎所有使用者都會有浏覽、點選等行為，是以資料量大，幾乎覆寫所有使用者，不會導緻資料有偏。其缺點是置信度不如顯式資料的高，比如浏覽不一定代表感興趣，還要看強度，經常浏覽同一類東西才能以較高置信度認為使用者感興趣。
根據所使用的資料是顯式資料還是隐式資料，矩陣分解算法又分為兩種[4,6]。使用顯式資料的矩陣分解算法稱為顯式矩陣分解算法，使用隐式資料的矩陣分解算法稱為隐式矩陣分解算法。由于矩陣分解算法有衆多的改進版本和各種變體[4,5,6,7,8,9,10,11]，本文不打算一一列舉，是以下文将以實踐中用得最多的矩陣分解算法為例，介紹其具體的資料原理，這也是spark機器學習庫mllib中實作的矩陣分解算法[4,6]。從實際應用的效果來看，隐式矩陣分解的效果一般會更好。
2.顯式矩陣分解
在本系列第一篇文章中，我們提到，矩陣分解算法的輸入是user對item的評分矩陣(圖1等号左邊的矩陣)，輸出是User矩陣和Item矩陣(圖1等号右邊的矩陣)，其中User矩陣的每一行代表一個使用者向量，Item矩陣的每一列代表一個item的向量。User對item的預測評分用它們的向量内積來表示，通過最小化預測評分和實際評分的差異來學習User矩陣和Item矩陣。
圖1
2.1 目标函數
為了用數學的語言定量表示上述思想，我們先引入一些符号。設rui 表示使用者u 對item i 的顯式評分，當rui >0時，表示使用者u 對item i 有評分，當rui =0時，表示使用者u 對item i 沒有評分，xu 表示使用者u 的向量，yi 表示item i 的向量，則顯式矩陣分解的目标函數為：
其中xu 和yi 都是k 維的列向量，k 為隐變量的個數，
是所有xu 構成的矩陣，
為所有yi 構成的矩陣，N 為使用者數，M 為item數，λ為正則化參數。
在上述公式中，
為使用者向量與物品向量的内積，表示使用者u 對物品i 的預測評分，目标函數通過最小化預測評分和實際評分rui 之間的殘差平方和，來學習所有使用者向量和物品向量。這裡的殘差項隻包含了有評分的資料，不包括沒有評分的資料。目标函數中第二項是L2正則項，用于保證數值計算穩定性和防止過拟合。
2.2 求解方法：
求解X 和Y 采用的是交替最小二乘法(alternative least square, ALS)，也就是先固定X 優化Y ，然後固定Y 優化X ，這個過程不斷重複，直到X 和Y 收斂為止。每次固定其中一個優化另一個都需要解一個最小二乘問題，是以這個算法叫做交替最小二乘方法。
(1)Y 固定為上一步疊代值或初始化值，優化X ：
此時，Y 被當做常數處理，目标函數被分解為多個獨立的子目标函數，每個子目标函數對應一個使用者。對于使用者u ，目标函數為：
這裡面殘差項求和的個數等于用于u 評過分的物品的個數，記為m 個。把這個目标函數化為矩陣形式，得
其中，
表示使用者u 對這m 個物品的評分構成的向量，
表示這m 個物品的向量構成的矩陣，順序跟Ru 中物品的順序一緻。
對目标函數J關于xu 求梯度，并令梯度為零，得：
解這個線性方程組，可得到xu 的解析解為：
(2) X 固定為上一步疊代值或初始化值，優化Y：
此時，X 被當做常數處理，目标函數也被分解為多個獨立的子目标函數，每個子目标函數對應一個物品。類似上面的推導，我們可以得到yi 的解析解為：
其中，
表示n 個使用者對物品i 的評分構成的向量，
表示這n 個使用者的向量構成的矩陣，順序跟Ri 中使用者的順序一緻。
2.3 工程實作
當固定Y 時，各個xu 的計算是獨立的，是以可以對xu 進行分布式并行計算。同理，當固定X 時，各個yi 的計算也是獨立的，是以也可以對yi 做分布式并行計算。因為Xi 和Yu 中隻包含了有評分的使用者或物品，而非全部使用者或物品，是以xu 和yi 的計算時間複雜度為O(k2nu+k3)其中nu 是有評分的使用者數或物品數，k 為隐變量個數。
3.隐式矩陣分解
隐式矩陣分解與顯式矩陣分解的一個比較大的差別，就是它會去拟合評分矩陣中的零，即沒有評分的地方也要拟合。
3.1 目标函數
我們仍然用rui 表示使用者u 對物品i 的評分，但這裡的評分表示的是行為的強度，比如浏覽次數、閱讀時長、播放完整度等。當rui >0時，表示使用者u 對物品i有過行為，當rui =0時，表示使用者u 對物品i沒有過行為。首先，我們定義一個二值變量pui 如下：
這個pui 是一個依賴于rui 的量，用于表示使用者u 對物品i 是否感興趣，也稱為使用者偏好。當使用者u 對物品i 有過行為時，我們認為使用者u 對物品i感興趣，此時pui =1；當使用者u 對物品i 沒有過行為時，我們認為使用者u 對物品i 不感興趣，此時pui =0。
模型除了要刻畫使用者對物品是否感興趣外，而且還要刻畫感興趣或不感興趣的程度，是以這裡的隐式矩陣分解還引入了置信度的概念。從直覺上來說，當rui >0時，rui 越大，我們越确信使用者u 喜歡物品i ，而當rui =0時，我們不能确定使用者u 是否喜歡物品i ，沒有行為可能隻是因為使用者u 并不知道物品i 的存在。
是以，置信度是rui 的函數，并且當rui >0時，置信度是rui 的增函數；當rui =0時，置信度取值要小。論文中給出的置信度cui 的表達式為：
當rui >0時，cui 關于rui 線性遞增，表示對于有評分的物品，行為強度越大，我們越相信使用者u 對物品i 感興趣；當rui =0時，置信度恒等于1，表示對所有沒有評分的物品，使用者不感興趣的置信度都一樣，并且比有評分物品的置信度低。用xu 表示使用者u 的向量，yi 表示item i 的向量，引入置信度以後，隐式矩陣分解[6]的目标函數為：
其中xu 和yi 都是k 維的列向量，k 為隐變量的個數，
是所有xu 構成的矩陣，
為所有yi 構成的矩陣，N 為使用者數，M 為item數，λ為正則化參數。目标函數裡的内積用于表示使用者對物品的預測偏好，拟合實際偏好pui，拟合強度由cui 控制。并且對于pui =0的項也要拟合。目标函數中的第二項是正則項，用于保證數值計算穩定性以及防止過拟合。
3.2 求解方法
目标函數的求解仍然可以采用交替最小二乘法。具體如下：
(1)Y 固定為上一步疊代值或初始化值，優化X ：
此時，Y 被當做常數處理，目标函數被分解為多個獨立的子目标函數，每個子目标函數都是某個xu 的函數。對于使用者u ，目标函數為：
把這個目标函數化為矩陣形式，得
其中，
為使用者u 對每個物品的偏好構成的列向量，
表示所有物品向量構成的矩陣，Λu 為使用者u 對所有物品的置信度cui 構成的對角陣，即：
對目标函數J 關于xu 求梯度，并令梯度為零，得：
解這個線性方程組，可得到xu 的解析解為：
(2) X 固定為上一步疊代值或初始化值，優化Y：
此時，X 被當做常數處理，目标函數也被分解為多個獨立的子目标函數，每個子目标函數都是關于某個yi 的函數。通過同樣的推導方法，可以得到yi 的解析解為：
其中，
為所有使用者對物品i 的偏好構成的向量，
表示所有使用者的向量構成的矩陣，Λi 為所有使用者對物品i 的偏好的置信度構成的對角矩陣，即
3.3 工程實作
由于固定Y 時，各個xu 的求解都是獨立的，是以在固定Y 時可以并行計算各個xu，同理，在固定X時可以并行計算各個yi 。
在計算xu 和yi 時，如果直接用上述解析解的表達式來計算，複雜度将會很高。以xu 的表達式來說，Y Λu YT 這一項就涉及到所有物品的向量，少則幾十萬，大則上千萬，而且每個使用者的都不一樣，每個使用者都算一遍時間上不可行。是以，這裡要先對xu 的表達式化簡，降低複雜度。
注意到Λi 的特殊性，它是由置信度構成的對角陣，對于一個使用者來說，由于大部分物品都沒有評分，以此Λi 對角線中大部分元素都是1，利用這個特點，我們可以把Λi 拆成兩部分的和，即
其中I為機關陣，Λu - I 為對角陣，并且對角線上大部分元素為0，于是，可以重寫為如下形式：
分解成這兩項之後，第一項Y YT 對每個使用者都是一樣的，隻需要計算一次，存起來，後面可以重複利用，對于第二項，由于Λu - I 為對角線大部分是0的對角陣，是以計算Y (Λu - I )YT 的複雜度是O(k2nu)。其中nu 是Λu - I 中非零元的個數，也就是使用者u 評過分的物品數，通常不會很多，是以整個Y ΛuYT的計算複雜度由O(k2M) 降為O(k2nu)。由于M>>nu，是以計算速度大大加快。對于xu 表達式的Y Λu Pu這一項，則應Y ( Λu Pu) 這樣計算，利用Pu 中大部分元素是0的特點，将計算複雜度由O(kM ) 降低到O(knu)。通過使用上述數學技巧，整個xu的計算複雜度可以降低到O(k2nu+k3)，其中nu是有評分的使用者數或物品數，k 為隐變量個數，完全滿足線上計算的需求。
4.增量矩陣分解算法
無論是顯式矩陣分解，還是隐式矩陣分解，我們在模型訓練完以後，就會得到訓練集裡每個使用者的向量和每個物品的向量。假設現在有一個使用者，在訓練集裡沒出現過，但是我們有他的曆史行為資料，那這個使用者的向量該怎麼計算呢？當然，最簡單的方法就是把這個使用者的行為資料合并到舊的訓練集裡，重新做一次矩陣分解，進而得到這個使用者的向量，但是這樣做計算代價太大了，在時間上不可行。
為了解決訓練資料集以外的使用者(我們稱之為新使用者)的推薦問題，我們就需要用到增量矩陣分解算法。增量矩陣分解算法能根據使用者曆史行為資料，在不重算所有使用者向量的前提下，快速計算出新使用者向量。
在交替最小二乘法裡，當固定Y 計算xu 時，我們隻需要用到使用者u 的曆史行為資料rui 以及Y 的目前值，不同使用者之間xu的計算是互相獨立的。這就啟發我們，對于訓練集以外的使用者，我們同樣可以用他的曆史行為資料以及訓練集上收斂時學到的Y，來計算新使用者的使用者向量。下面的圖2表示了這一過程。
增量矩陣分解
設使用者曆史行為資料為Pu={Pui }，訓練集上學到的物品矩陣為Y，要求解的使用者向量為xu，則增量矩陣分解算法求解的目标為：
這個目标函數跟第3節中固定Y 時求解xu 的目标函數是一樣的，但有兩個不同點：
(1)這裡的Y 是不需要疊代的，它是MF在訓練集上收斂時得到的Y；
(2)使用者的曆史行為資料Pu 要過濾掉在Y中沒出現過的物品。由于Y 是固定的，我們不需要疊代，直接通過xu 的解析表達式求解xu，即：
式中的所有符号和上一節相同。
事實上，增量矩陣分解的目标函數中的Y 也不一定要是MF在訓練集上學出來的，隻要Y 中的每個向量都能表示對應物品的特征就行，也就是說，Y 可以是由其他資料和其他算法事先學出來的。矩陣分解的增量算法在圖文推薦系統中有着廣泛應用，具體的應用将在下一篇文章中介紹。
5.推薦結果的可解釋性
好的推薦算法不僅要推得準确，而且還要有良好的可解釋性，也就是根據什麼給使用者推薦了這個物品。傳統的ItemCF算法就有很好的可解釋性，因為在ItemCF中，使用者u 對物品i 的預測評分R (u, i ) 的計算公式為
其中N(u ) 表示使用者u 有過行為的物品集合，ruj 表示使用者u 對物品j 的曆史評分，sji 表示物品j 和物品i 的相似度。在這個公式中，N(u ) 中的物品j 對R(u, i ) 的貢獻為ruj sji，是以可以很好地解釋物品i 具體是由N(u) 中哪個物品推薦而來。那對于矩陣分解算法來說，是否也能給出類似的可解釋性呢？答案是肯定的。
以隐式矩陣分解為例，我們已經推導出，已知物品的矩陣Y 時，使用者u 的向量的計算表達式為：
假設物品i 的向量為yi，那麼使用者u 對物品i 的預測評分為：
令
并把Y Λu Pu 展開來寫，則的表達式可以寫成
其中，
可以看成是物品j 和物品i 之間的相似度，
可以看成是使用者u 對使用者j的評分，這樣就能像ItemCF那樣去解釋N(u )中每一項對推薦物品i 的貢獻了。從sji 的計算表達式中，我們還可以看到，物品j 和物品i 之間的相似度sji 是跟使用者u 有關系的，也就是說，即使是相同的兩個物品，在不同使用者看來，它們的相似度是不一樣的，這跟ItemCF的固定相似度有着本質上的差別，MF的相似度看起來更合理一些。
6.小結
(1)根據使用者行為資料的特點，矩陣分解又分為顯式矩陣分解和隐式矩陣分解兩種；
(2)在顯式MF算法中，使用者向量和物品向量的内積拟合的是使用者對物品的實際評分，并且隻拟合有評分的項；
(3)在隐式MF算法中，使用者向量和物品向量的内積拟合的是使用者對物品的偏好(0或1)，拟合的強度由置信度控制，置信度又由行為的強度決定；
(4)在隐式MF中，需要使用一些數學技巧降低計算複雜度，才能滿足線上實時計算的性能要求；
(5)對于有行為資料，但不在訓練集裡的使用者，可以使用增量MF算法計算出他的使用者向量，進而為他做推薦；
(6)MF算法也能像ItemCF一樣，能給出推薦的理由，具有良好的可解釋性。
| 智能推薦 個性化推薦技術與産品社群 |