Coursea-吳恩達-machine learning學習筆記（十六）【week 9之Recommender Systems】

推薦系統：

舉例(預測電影評分)

使用者使用 0∼5 0 ∼ 5 星給電影打分，如下圖所示：

一些定義如下：

nu n u ：表示使用者數量；

nm n m ：表示電影數量；

r(i,j) r ( i , j ) ：如果使用者 j j 給電影ii打過分，則 r(i,j)=1 r ( i , j ) = 1 ；

y(i,j) y ( i , j ) ：當使用者 j j 給電影ii打過分，即 r(i,j)=1 r ( i , j ) = 1 時，用來表示使用者 j j 給電影ii的評分分值。

推薦系統問題就是給定 r(i,j) r ( i , j ) 和 y(i,j) y ( i , j ) ，關注所有沒有評分的地方并試圖預測；

推薦系統的主要工作是想出一種學習算法，能夠幫助我們自動填充缺失值，試圖預測使用者可能感興趣的電影，進行推薦。

第一種建構推薦系統的方法—-“基于内容的推薦”

假設每部電影有兩種特征，用 x1 x 1 和 x2 x 2 表示， x1 x 1 表示這部電影屬于愛情電影的程度， x2 x 2 表示這部電影屬于動作電影的程度，如下圖所示：

對于第一部電影來說，兩個特征值分别是 0.9 0.9 和 0 0 ，加上一個特征變量x0=1x0=1，則 x(1)=⎡⎣⎢10.90⎤⎦⎥ x ( 1 ) = [ 1 0.9 0 ] ， n n 表示特征變量數(不包括x0x0)，故 n=2 n = 2 ；

我們可以把每個使用者的打分預測當成一個獨立的線性回歸問題，對于每個使用者 j j ，學習參數θ(j)∈Rn+1θ(j)∈Rn+1，根據 (θ(j))Tx(i) ( θ ( j ) ) T x ( i ) 來預測使用者 j j 對電影ii的打分。

更正式的表達：

r(i,j) r ( i , j ) ：如果使用者 j j 給電影ii打過分，則為1，否則為0；

y(i,j) y ( i , j ) ：當 r(i,j)=1 r ( i , j ) = 1 時，表示使用者 j j 給電影ii的評分分值；

θ(j) θ ( j ) ：表示使用者 j j 的參數向量；

x(i)x(i)：表示電影 i i 的特征向量。

對于使用者jj和電影 i i ，預測評分為：(θ(j))Tx(i)(θ(j))Tx(i)；

m(j) m ( j ) ：表示使用者 j j 評分的電影數量；

為了學習θ(j)θ(j)，則：

minθ(j)12m(j)∑i:r(i,j)=1((θ(j))Tx(i)−y(i,j))2+λ2m(j)∑k=1n(θ(j)k)2 min θ ( j ) 1 2 m ( j ) ∑ i : r ( i , j ) = 1 ( ( θ ( j ) ) T x ( i ) − y ( i , j ) ) 2 + λ 2 m ( j ) ∑ k = 1 n ( θ k ( j ) ) 2

去掉 1m(j) 1 m ( j ) 不影響 θ(j) θ ( j ) 的最優化結果，是以，為了學習 θ(j) θ ( j ) ，則： J(θ(j))=minθ(j)12∑i:r(i,j)=1((θ(j))Tx(i)−y(i,j))2+λ2∑k=1n(θ(j)k)2 J ( θ ( j ) ) = min θ ( j ) 1 2 ∑ i : r ( i , j ) = 1 ( ( θ ( j ) ) T x ( i ) − y ( i , j ) ) 2 + λ 2 ∑ k = 1 n ( θ k ( j ) ) 2

為了學習 θ(1),θ(2),⋯,θ(nu) θ ( 1 ) , θ ( 2 ) , ⋯ , θ ( n u ) ，則： J(θ(1),⋯,θ(nu))=minθ(1),⋯,θ(nu)12∑j=1nu∑i:r(i,j)=1((θ(j))Tx(i)−y(i,j))2+λ2∑j=1nu∑k=1n(θ(j)k)2 J ( θ ( 1 ) , ⋯ , θ ( n u ) ) = min θ ( 1 ) , ⋯ , θ ( n u ) 1 2 ∑ j = 1 n u ∑ i : r ( i , j ) = 1 ( ( θ ( j ) ) T x ( i ) − y ( i , j ) ) 2 + λ 2 ∑ j = 1 n u ∑ k = 1 n ( θ k ( j ) ) 2

梯度下降法：

θ(j)k:=θ(j)k−α∑i:r(i,j)=1((θ(j))Tx(i)−y(i,j))x(i)k(for k=0) θ k ( j ) := θ k ( j ) − α ∑ i : r ( i , j ) = 1 ( ( θ ( j ) ) T x ( i ) − y ( i , j ) ) x k ( i ) ( f o r   k = 0 )

θ(j)k:=θ(j)k−α(∑i:r(i,j)=1((θ(j))Tx(i)−y(i,j))x(i)k+λθ(j)k)(for k≠0) θ k ( j ) := θ k ( j ) − α ( ∑ i : r ( i , j ) = 1 ( ( θ ( j ) ) T x ( i ) − y ( i , j ) ) x k ( i ) + λ θ k ( j ) ) ( f o r   k ≠ 0 )

注： ∂∂θ(j)kJ(θ(1),⋯,θ(nu))=∑i:r(i,j)=1((θ(j))Tx(i)−y(i,j))x(i)k+λθ(j)k ∂ ∂ θ k ( j ) J ( θ ( 1 ) , ⋯ , θ ( n u ) ) = ∑ i : r ( i , j ) = 1 ( ( θ ( j ) ) T x ( i ) − y ( i , j ) ) x k ( i ) + λ θ k ( j )

第二種建構推薦系統的方法—-“協同過濾”

這種算法能自行學習所要使用的特征。

假設我們并不知道每部電影的愛情成分和動作成分，如下圖：

我們采訪每位使用者，得到每個使用者是否喜歡愛情電影和動作電影：

如： θ(1)=⎡⎣⎢050⎤⎦⎥θ(2)=⎡⎣⎢050⎤⎦⎥θ(3)=⎡⎣⎢005⎤⎦⎥θ(4)=⎡⎣⎢005⎤⎦⎥ θ ( 1 ) = [ 0 5 0 ] θ ( 2 ) = [ 0 5 0 ] θ ( 3 ) = [ 0 0 5 ] θ ( 4 ) = [ 0 0 5 ]

θ(j) θ ( j ) 可以明确告訴我們每個使用者對不同題材電影的喜歡程度。

通過 θ(j) θ ( j ) 及 y(i,j) y ( i , j ) 可以推算出每部電影的特征值。

将問題标準化：

已知 θ(1),⋯,θ(nu) θ ( 1 ) , ⋯ , θ ( n u ) ，學習 x(i) x ( i ) ，使得

minx(i)12∑j:r(i,j)=1((θ(j))Tx(i)−y(i,j))2+λ2∑k=1n(x(i)k)2 min x ( i ) 1 2 ∑ j : r ( i , j ) = 1 ( ( θ ( j ) ) T x ( i ) − y ( i , j ) ) 2 + λ 2 ∑ k = 1 n ( x k ( i ) ) 2

已知 θ(1),⋯,θ(nu) θ ( 1 ) , ⋯ , θ ( n u ) ，學習 x(1),⋯,x(nm) x ( 1 ) , ⋯ , x ( n m ) ，使得 minx(1),⋯,x(nm)12∑i=1nm∑j:r(i,j)=1((θ(j))Tx(i)−y(i,j))2+λ2∑i=1nm∑k=1n(x(i)k)2 min x ( 1 ) , ⋯ , x ( n m ) 1 2 ∑ i = 1 n m ∑ j : r ( i , j ) = 1 ( ( θ ( j ) ) T x ( i ) − y ( i , j ) ) 2 + λ 2 ∑ i = 1 n m ∑ k = 1 n ( x k ( i ) ) 2

結合前兩種方法，得到協同過濾算法的代價函數：

J(x(1),⋯,x(nm),θ(1),⋯,θ(nu))=12∑(i,j):r(i,j)=1((θ(j))Tx(i)−y(i,j))2+λ2∑i=1nm∑k=1n(x(i)k)2+λ2∑j=1nu∑k=1n(θ(j)k)2 J ( x ( 1 ) , ⋯ , x ( n m ) , θ ( 1 ) , ⋯ , θ ( n u ) ) = 1 2 ∑ ( i , j ) : r ( i , j ) = 1 ( ( θ ( j ) ) T x ( i ) − y ( i , j ) ) 2 + λ 2 ∑ i = 1 n m ∑ k = 1 n ( x k ( i ) ) 2 + λ 2 ∑ j = 1 n u ∑ k = 1 n ( θ k ( j ) ) 2

算法目标為： minx(1),⋯,x(nm)θ(1),⋯,θ(nu)J(x(1),⋯,x(nm),θ(1),⋯,θ(nu)) min x ( 1 ) , ⋯ , x ( n m ) θ ( 1 ) , ⋯ , θ ( n u ) J ( x ( 1 ) , ⋯ , x ( n m ) , θ ( 1 ) , ⋯ , θ ( n u ) )

注：當用這種形式去學習特征量時，應摒棄 x0=1 x 0 = 1 和 θ0 θ 0 ， x∈Rn x ∈ R n ， θ∈Rn θ ∈ R n 。

協同過濾算法步驟：

1. 初始化 x(1),⋯,x(nm),θ(1),⋯,θ(nu) x ( 1 ) , ⋯ , x ( n m ) , θ ( 1 ) , ⋯ , θ ( n u ) 為小的随機值；

2. 用梯度下降法或其他進階優化算法，最小化代價函數( for every j=1,⋯,nu,i=1,⋯,nm f o r   e v e r y   j = 1 , ⋯ , n u , i = 1 , ⋯ , n m )

   x(i)k:=x(i)k−α(∑j:r(i,j)=1((θ(j))Tx(i)−y(i,j))θ(j)k+λx(i)k) x k ( i ) := x k ( i ) − α ( ∑ j : r ( i , j ) = 1 ( ( θ ( j ) ) T x ( i ) − y ( i , j ) ) θ k ( j ) + λ x k ( i ) )

   θ(j)k:=θ(j)k−α(∑i:r(i,j)=1((θ(j))Tx(i)−y(i,j))x(i)k+λθ(j)k) θ k ( j ) := θ k ( j ) − α ( ∑ i : r ( i , j ) = 1 ( ( θ ( j ) ) T x ( i ) − y ( i , j ) ) x k ( i ) + λ θ k ( j ) )

3. 對一個使用者(參數 θ θ )和一個電影(特征值 x x )，預測評分θTxθTx(即 (θ(j))Tx(i) ( θ ( j ) ) T x ( i ) )

協同過濾算法的向量化方法：

有五部電影的資料集如下圖：

将使用者評分存儲到矩陣中：

Y=⎡⎣⎢⎢⎢⎢⎢⎢55?005?4000?05500?4?⎤⎦⎥⎥⎥⎥⎥⎥ Y = [ 5 5 0 0 5 ? ? 0 ? 4 0 ? 0 0 5 4 0 0 5 ? ]

預測評分矩陣為：

⎡⎣⎢⎢⎢⎢⎢(θ(1))Tx(1)(θ(1))Tx(2)⋮(θ(1))Tx(nm)(θ(2))Tx(1)(θ(2))Tx(2)⋮(θ(2))Tx(nm)⋯⋯⋯(θ(nu))Tx(1)(θ(nu))Tx(2)⋮(θ(nu))Tx(nm)⎤⎦⎥⎥⎥⎥⎥ [ ( θ ( 1 ) ) T x ( 1 ) ( θ ( 2 ) ) T x ( 1 ) ⋯ ( θ ( n u ) ) T x ( 1 ) ( θ ( 1 ) ) T x ( 2 ) ( θ ( 2 ) ) T x ( 2 ) ⋯ ( θ ( n u ) ) T x ( 2 ) ⋮ ⋮ ⋮ ( θ ( 1 ) ) T x ( n m ) ( θ ( 2 ) ) T x ( n m ) ⋯ ( θ ( n u ) ) T x ( n m ) ]

若電影特征矩陣為 X=⎡⎣⎢⎢⎢⎢⎢(x(1))T(x(2))T⋮(x(nm))T⎤⎦⎥⎥⎥⎥⎥ X = [ ( x ( 1 ) ) T ( x ( 2 ) ) T ⋮ ( x ( n m ) ) T ] 使用者參數矩陣為 Θ=⎡⎣⎢⎢⎢⎢⎢(θ(1))T(θ(2))T⋮(θ(nu))T⎤⎦⎥⎥⎥⎥⎥ Θ = [ ( θ ( 1 ) ) T ( θ ( 2 ) ) T ⋮ ( θ ( n u ) ) T ]

則預測評分矩陣為 XΘT X Θ T ，這種方法叫作低秩矩陣分解。

尋找相關電影

對于每個電影 i i ，存在特征向量x(i)∈Rnx(i)∈Rn

尋找電影 i i 的關聯電影jj：

若 ∥x(i)−x(j)∥ ‖ x ( i ) − x ( j ) ‖ 很小 → → 電影 i i 和電影jj相似。

協同過濾算法實作細節：均值歸一化

如下圖，有一個使用者沒有給任何電影評分

在協同過濾算法中，目标為：

minx(1),⋯,x(nm)θ(1),⋯,θ(nu)12∑(i,j):r(i,j)=1((θ(j))Tx(i)−y(i,j))2+λ2∑i=1nm∑k=1n(x(i)k)2+λ2∑j=1nu∑k=1n(θ(j)k)2 min x ( 1 ) , ⋯ , x ( n m ) θ ( 1 ) , ⋯ , θ ( n u ) 1 2 ∑ ( i , j ) : r ( i , j ) = 1 ( ( θ ( j ) ) T x ( i ) − y ( i , j ) ) 2 + λ 2 ∑ i = 1 n m ∑ k = 1 n ( x k ( i ) ) 2 + λ 2 ∑ j = 1 n u ∑ k = 1 n ( θ k ( j ) ) 2

假設 n=2 n = 2 ， θ(5)∈R2 θ ( 5 ) ∈ R 2 ，由于使用者 5 5 沒有對任何電影評分，是以影響θ(5)θ(5)的唯一項為 λ2∑k=1n(θ(5)k)2 λ 2 ∑ k = 1 n ( θ k ( 5 ) ) 2 ，為了讓代價函數最小化，最終 θ(5)=[00] θ ( 5 ) = [ 0 0 ] ，是以預測使用者5對電影的評分時 (θ(5))Tx(i)=0 ( θ ( 5 ) ) T x ( i ) = 0 ，其對所有電影的評分均為 0 0 ，無法推薦。

均值歸一化可以解決這一情況。

Y=⎡⎣⎢⎢⎢⎢⎢⎢55?005?4000?05500?40?????⎤⎦⎥⎥⎥⎥⎥⎥Y=[5500?5??0??40??0054?0050?]計算每個電影評分均值 μ=⎡⎣⎢⎢⎢⎢⎢⎢2.52.522.251.25⎤⎦⎥⎥⎥⎥⎥⎥ μ = [ 2.5 2.5 2 2.25 1.25 ]

令 Y=Y.−μ=⎡⎣⎢⎢⎢⎢⎢⎢2.52.5?−2.25−1.252.5?2−2.25−1.25−2.5?−22.753.75−2.5−2.5?1.75−1.25?????⎤⎦⎥⎥⎥⎥⎥⎥ Y = Y . − μ = [ 2.5 2.5 − 2.5 − 2.5 ? 2.5 ? ? − 2.5 ? ? 2 − 2 ? ? − 2.25 − 2.25 2.75 1.75 ? − 1.25 − 1.25 3.75 − 1.25 ? ] 用該矩陣學習 θ(j) θ ( j ) 和 x(i) x ( i )

使用者 j j 對電影ii的評分預測為： (θ(j))Tx(i)+μi ( θ ( j ) ) T x ( i ) + μ i

本例中，因為 θ(5)=[00] θ ( 5 ) = [ 0 0 ] ，是以其對電影的評分為 μ=⎡⎣⎢⎢⎢⎢⎢⎢2.52.522.251.25⎤⎦⎥⎥⎥⎥⎥⎥ μ = [ 2.5 2.5 2 2.25 1.25 ]