Andrew Ng機器學習課程筆記--week9(下)（推薦系統&協同過濾）

本周内容較多，故分為上下兩篇文章。

本文為下篇。

一、内容概要

1. Anomaly Detection

• Density Estimation
  • Problem Motivation
  • Gaussian Distribution
  • Algorithm
• Building an Anomaly Detection System（建立異常檢測系統）
  • Developing and Evaluating an Anomaly Detection System
  • Anomaly Detection vs. Supervised Learning
  • Choosing What Features to Use
• Multivariate Gaussion Distribution（多元高斯分布）
  • Multivariate Gaussion Distribution
  • Anomaly Detection using the Multivariate Gaussion Distribution

2. Recommender System

• Predicting Movie
  • Problem Formulation
  • Content Based Recommendations
• Collaborative Filtering(協同過濾)
  • Collaborative Filtering
  • Collaborative Filtering Algorithm
• Low Rank Matrix Factorization（低秩矩陣分解）
  • Vectorization（向量化）： Low Rank Matrix Factorization
  • Implementational Detail：Mean Normalization

二、重點&難點

Recommender System(推薦系統)

1.Predicting Movie

1）Problem Formulation

下面将以推薦電影為例來介紹推薦系統的實作。

movie	Alice	Bob	Carol	Dave
Love at last	5
Romance forever		?
Cute Puppies of love		4
nonstop car chases
swords & karate

上面的分數表示使用者對該電影的評分（0~5分，？表示未獲得評分資料）

為友善下面叙述，對如下符号進行說明：

• \(n_u\)：表示使用者數量
• \(n_m\)：表示電影數量
• r(i,j)：如果等于1則表示使用者j對電影i進行了評分
• \(y^{(i,j)}\)：表示使用者j對電影i的評分

上面例子中可以知道 \(n_u=4 \quad n_m=5 \quad y^{(1,1)}=5\)

2）Content Based Recommendations(基于内容的推薦)

• 1.擷取特征向量

  為了實作推薦，我們為每部電影提取出了兩個特征值，即x1（浪漫指數）和x2（動作指數）

					x1	x2
			0.9	0.1
				1.0
				0.99	0.01

由上表可知每部電影都可以用一組特征向量表示：

• 每一步電影都加上一個額外的特征，即 \(x_0=1\)
• 每部電影都有一個(3,1)的特征向量，例如第一部電影（Love at last）：\(x^{(1)}=[1,0.9,0.1]^T\)
• 對于所有資料我們有資料特征向量組為\(\{x^{(1)},x^{(2)},x^{(3)},x^{(4)},x^{(5)}\}\)

• 2.特征權重θ

  使用者j對電影i的評分預測可以表示為\((θ^j)^Tx^i=stars\)

• 3. 線性回歸預測

和線性回歸一樣，可以得到如下優化目标函數:

• 對單個使用者而言

\[\min_{θ^{(j)}}\frac{1}{2}\sum_{i;r(i,j)=1}((θ^{(j)})^Tx^{(i)}-y^{(i,j)})^2 + \frac{λ}{2}\sum_{k=1}^n (θ_k^{(j)})^2

\]

• 對所有使用者而言

\[\min_{θ^{(1)},...,θ^{(n_u)}}\frac{1}{2}\sum_{j=1}^{n_u}\sum_{i:r(i,j)=1}((θ^{(j)})^Tx^{(i)}-y^{(i,j)})^2 + \frac{λ}{2}\sum_{j=1}^{n_u}\sum_{k=1}^n (θ_k^{(j)})^2

應用梯度下降：

\[當k=0，θ_k^{(j)}:=θ_k^{(j)}-α\sum_{i:r(i,j)=1}( (θ^{(j)})^Tx^{(i)}-y^{(i,j)} )x_k^{(i)}

\[當k≠0，θ_k^{(j)}:=θ_k^{(j)}-α\sum_{i:r(i,j)=1}( (θ^{(j)})^Tx^{(i)}-y^{(i,j)} )x_k^{(i)}+λθ_k^{(j)}

2.Collaborative Filtering(協同過濾)

1）Collaborative Filtering

在之前的基于内容的推薦系統中，對于每一部電影，我們都掌握了可用的特征，使用這些特征訓練出了每一個使用者的參數。相反地，如果我們擁有使用者的參數，我們可以學習得出電影的特征。即由θ求出x。

\[\min_{θ^{(1)},...,θ^{(n_m)}}\frac{1}{2}\sum_{j=1}^{n_u}\sum_{i:r(i,j)=1}((θ^{(j)})^Tx^{(i)}-y^{(i,j)})^2 + \frac{λ}{2}\sum_{j=1}^{n_m}\sum_{k=1}^n (θ_k^{(j)})^2

注意累計符号的上限由\(n_u\)變成了\(n_m\)

但是如果我們既沒有使用者的參數也沒有電影的特征該怎麼辦？這時協同過濾就可以起作用了，隻需要對優化目标函數進行改進，如下：

\[J(x^{(1)},...,x^{(n_m)},θ^{(1)},...,θ^{(n_u)}) = \frac{1}{2}\sum_{(i,j):r(i,j)=1}((θ^{(j)})^Tx^{(i)}-y^{(i,j)})^2 \\ \quad\quad\quad\quad\quad\quad\quad +\frac{λ}{2}\sum_{j=1}^{n_u}\sum_{k=1}^n (θ_k^{(j)})^2 \\ \quad\quad\quad\quad\quad\quad\quad+ \frac{λ}{2}\sum_{i=1}^{n_m}\sum_{k=1}^n (x_k^{(i)})^2

對代價函數求偏導結果如下：

\[x_k^{(i)} := x_k^{(i)} - α(\sum_{j:r(i,j)=1}( (θ^{(j)})^Tx^{(i)}-y^{(i,j)} )θ_k^{(j)} +λx_k^{(i)} )

\[θ_k^{(j)} := θ_k^{(j)} - α(\sum_{i:r(i,j)=1}( (θ^{(j)})^Tx^{(i)}-y^{(i,j)} )x_k^{(i)} +λθ_k^{(j)} )

協同過濾算法使用步驟如下：

1. 初始 x (1) ,x (2) ,...,x (\(n_m\)) ，θ (1) ,θ (2) ,...,θ (\(n_u\)) 為一些随機小值
2. 使用梯度下降算法最小化代價函數
3. 在訓練完算法後，我們預測\((θ ^{(j)} )^ T x^{ (i)}\) 為使用者 j 給電影 i 的評分

3. Low Rank Matrix Factorization（低秩矩陣分解）

1）Vectorization（向量化）： Low Rank Matrix Factorizationv

（同樣的例子）很顯然我們可以得到評分矩陣Y

\[Y= \left[

\begin{array}{cccc}

5&5&0&0 \\

5&?&?&0 \\

?&4&0&? \\

0&0&5&4 \\

0&0&5&0 \\

\end{array}

\right] \]

推出評分

\[\begin{pmatrix}

(θ^{(1)})^T(x^{(1)}) &(θ^{(2)})^T(x^{(1)})& \cdots & (θ^{(n_u)})^T(x^{(1)}) \\

(θ^{(1)})^T(x^{(2)}) &(θ^{(2)})^T(x^{(2)})& \cdots & (θ^{(n_u)})^T(x^{(2)}) \\

\vdots & \vdots& \ddots & \vdots \\

(θ^{(1)})^T(x^{(n_m)}) &(θ^{(2)})^T(x^{(n_m)})& \cdots & (θ^{(n_u)})^T(x^{(n_m)}) \\

\end{pmatrix}

如何尋找與電影i相關的電影j呢？滿足\(||x^{(i)}-x^{(j)}||\)較小的前幾部影片即可。

2）Implementational Detail：Mean Normalization

假如增加了一個使用者marsggbo，他很單純，這5部電影都還沒看過，是以沒有評分資料，這是可以通過均值正則化來初始化資料，具體實作如下：

					Marsggbo
			？

此時的評分矩陣為

5&5&0&0&? \\

5&?&?&0&? \\

?&4&0&?&? \\

0&0&5&4&? \\

0&0&5&0&? \\

首先求出每行的均值（未評分不用計算）

\[μ=\left[

\begin{array}

2.5 \\

2 \\

2.25 \\

1.25

\end{array}

\right]→

Y= \left[

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&? \\

\right]

預測值為\((θ^{(j)})^T(x^{(i)})+μ_i\)，因為優沒有評分。是以化目的函數隻需要\(min\frac{λ}{2}\sum_{j=1}^{n_u}\sum_{k=1}^n (θ_k^{(j)})^2\),很顯然\(θ=\vec0\)，是以新增使用者評分資料可初始化為均值，即

5&5&0&0&2.5 \\

5&?&?&0&2.5 \\

?&4&0&?&2 \\

0&0&5&4&2.25 \\

0&0&5&0&1.25 \\

MARSGGBO ♥原創 2017-8-14