[ML] 機器學習技法：第十五講 Matrix Factorization

ML：基礎技法學習
Package：scikit-learn
課程：機器學習技法
簡介：第十五講 Matrix Factorization

Basic Matrix Factorization

常數項 $x_0^{(l)}$ 被移除

1. 初始化 $\tilde{d}\times 1$ 維度的 $\left\{{\mathbf{w}}_m\right\},\left\{{\mathbf{v}}_m\right\}$
   通常為隨機產生，以免陷入 Local optimum
2. alternating optimization $E_{in}$ 直到收斂
1. 最佳化 ${\mathbf{w}}_1,{\mathbf{w}}_2,\cdots ,{\mathbf{w}}_M$
   更新 ${\mathbf{w}}_m$，利用 m-th-movie 的 $\{({\mathbf{v}}_n,r_{nm})\}$ 做 linear regression
2. 最佳化 ${\mathbf{v}}_1,{\mathbf{v}}_2,\cdots ,{\mathbf{v}}_N$
   更新 ${\mathbf{v}}_n$，利用 n-th-user 的 $\{({\mathbf{w}}_m,r_{nm})\}$ 做 linear regression

首先，先說明例子
共有 100,480,507 ratings，裡面有 480,189 users 對於 17,770 movies 進行評分
定義資料為 $\{({\tilde{\mathbf{x}}}_n=(n),y_n=r_{nm})\}$：第 n 個使用者對於第 m 部電影給予評分 r
在這比較特別的是 ${\tilde{x}}_n=(n)$ 是抽象的
只知道編號，不會知道其他任何資料，像是男女、高矮、胖瘦等
這種 feature 也叫做 categorical features
無任何數值的意義，只是種類，像是 ID, 血型, 喜好語言等，皆是此特性
目前學過的方法，可以直接處理的，只有 decision trees，其餘皆需要再轉換為 numerical
可以使用 binary vector encoding，像是血型
$$\begin{array}{cc}A=[1000{]}^T& B=[0100{]}^T\\ AB=[0010{]}^T& O=[0001{]}^T\end{array}$$ 所以將評分資料重新編碼，並且整合在一起，稱作
$$D=\{({\tilde{\mathbf{x}}}_n=BinaryVectorEncoding(n),{\mathbf{y}}_n=[r_{n1}??r_{n4}{r}_{n5}\cdots r_{nM}{]}^T)\}$$ 因為不見得使用者能對每部電影都有評分，所以 ${\mathbf{y}}_n$ 會有缺，也就是 ？ 項
考慮利用 $N-\tilde{d}-M$ 類神經網路莘取出特徵
將常數項 $x_0^{(l)}$ 移掉，比較簡單分析，也可以加入，模型略有變化而已

然而，tanh 是必要的嗎？
事實上因為 $\mathbf{x}$ 只會在一個維度上為 1，其他皆為 0
所以再多經過一次轉換並不是必須的，所以可改為線性
而且 ${\mathbf{y}}_n$ 可缺項，並將前後的權值重新命名為 ${\mathbf{V}}^T$ 和 $\mathbf{W}$，推導時會比較簡潔

$$\begin{array}{rl}h(\mathbf{x})& =({\mathbf{W}}_{\tilde{d}\times M}{)}^T{\mathbf{V}}_{\tilde{d}\times N}{\mathbf{x}}_{N\times 1}\\ h({\mathbf{x}}_n)& =({\mathbf{W}}_{\tilde{d}\times M}{)}^T\underset{\mathrm{\Phi }({\mathbf{x}}_n)}{\underbrace{{\mathbf{V}}_{\tilde{d}\times N}{{\mathbf{x}}_n}_{N\times 1}}}\\ & =({\mathbf{W}}_{\tilde{d}\times M}{)}^T{\mathbf{V}}_{\tilde{d}\times N}\left[\begin{array}{c}0\\ ⋮\\ 1\\ ⋮\\ 0\end{array}\right]\\ & =({\mathbf{W}}_{\tilde{d}\times M}{)}^T{\mathbf{v}}_n\\ \\ h_m(\mathbf{x})& ={\mathbf{w}}_m^T\mathrm{\Phi }(\mathbf{x})\\ h_m({\mathbf{x}}_n)& ={\mathbf{w}}_m^T\mathrm{\Phi }({\mathbf{x}}_n)\\ & ={\mathbf{w}}_m^T{\mathbf{v}}_n\end{array}$$ ${\mathbf{v}}_n$ 為 $\mathbf{V}$ 的 n-th column
從式子可看到 ${\mathbf{v}}_n$ 代表的是使用者的喜好
$h_m(\mathbf{x})$ 則是對於 m-th 電影的評分
${\mathbf{w}}_m^T{\mathbf{v}}_n$ 則為第 n 個使用者對於第 m 個電影的預測評分
所以事實上如下，是在將 $\mathbf{R}$ 矩陣，拆分為兩個矩陣 $\mathbf{V}$ 和 $\mathbf{W}$
$\mathbf{V}$ 為使用者對電影特性的喜好度，搞笑/恐怖/愛情....
$\mathbf{W}$ 為電影具備的特性，搞笑/恐怖/愛情....
這也是 Matrix Factorization 的由來

並由以上，可定義
$$\begin{array}{rl}{E}_{in}(\left\{{\mathbf{w}}_m\right\},\left\{{\mathbf{v}}_n\right\})& =\frac{1}{\sum _{m=1}^M|D_m|}\sum _{usernratedmoviem}(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n{)}^2\\ & \propto \sum _{usernratedmoviem}(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n{)}^2\\ & =\sum _{m=1}^M(\sum _{({\mathbf{x}}_n,r_{nm})\in D_m}(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n{)}^2)\cdots (1)\\ & =\sum _{n=1}^N(\sum _{(m,r_{nm})\in D_n}(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n{)}^2)\cdots (2)\end{array}$$ $D_m$ 表示第 m 部電影的所有使用者評價
$D_n$ 表示第 n 個使用者的所有電影評價
該如何 $\underset{\mathbf{W},\mathbf{V}}{min}{E}_{in}(\left\{{\mathbf{w}}_m\right\},\left\{{\mathbf{v}}_n\right\})$ 呢？
利用 alternating minimization 不就好了
固定 ${\mathbf{v}}_n$，求 ${\mathbf{w}}_m$，不就是求 $E_{in}$ 在 $D_m$ 的 linear regresson，同 (1) 式
固定 ${\mathbf{w}}_m$，求 ${\mathbf{v}}_n$，不就是求 $E_{in}$ 在 $D_n$ 的 linear regresson，同 (2) 式
交叉反覆求其 linear regression 的解，直到收斂，會收斂的原因來自 $E_{in}$ 的下限為 0
此做法也叫作 alternating least squares algorithm
記住，這邊並無常數項 $x_0^{(l)}$

Linear Autoencoder vs. Matrix Factorization

Linear Autoencoder ≡ 特別的 Matrix Factorization 其 $\mathbf{X}$ 為 complete
比較如下圖
Linear autoencoder 可參考 [ML] 機器學習技法：第十三講 Deep Learning

Stochastic Gradient Descent Matrix Factorization

較適用於龐大的資料

1. 初始化 $\tilde{d}\times 1$ 維度的 $\left\{{\mathbf{w}}_m\right\},\left\{{\mathbf{v}}_m\right\}$
   通常為隨機產生，以免陷入 Local optimum 
2. for $t=0,1,\cdots ,T$
1. 隨機從 $r_{nm}$ 挑出一個
2. 計算 residual ${\tilde{r}}_{nm}=(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n)$
3. SGD-update
   $$\begin{array}{rl}{\mathbf{v}}_n^{new}& \leftarrow {\mathbf{v}}_n^{old}+\eta \cdot {\tilde{r}}_{nm}{\mathbf{w}}_m^{old}\\ {\mathbf{w}}_m^{new}& \leftarrow {\mathbf{w}}_m^{old}+\eta \cdot {\tilde{r}}_{nm}{\mathbf{v}}_n^{old}\end{array}$$

SGD 可參考 [ML] 機器學習基石：第十一講 Linear Models for Classification
單個的錯誤如下式
$$err(usern,moviem,rating{r}_{nm})=(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n{)}^2$$ 因為是針對 n,m 隨機抽取，所以除 n,m 以外的 gradient 是為 0，無需 update
故對 n,m 取 gradient
$$\begin{array}{rl}{▽}_{{\mathbf{v}}_n}err& =2(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n)(-{\mathbf{w}}_m)\\ & =-2(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n){\mathbf{w}}_m\\ & \propto -(residual){\mathbf{w}}_m\\ {▽}_{{\mathbf{w}}_m}err& =2(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n)(-{\mathbf{v}}_n)\\ & =-2(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n){\mathbf{v}}_n\\ & \propto -(residual){\mathbf{v}}_n\end{array}$$ 將 ${\tilde{r}}_{nm}=(r_{nm}-{\mathbf{w}}_m^T{\mathbf{v}}_n)$
$$\begin{array}{rl}{\mathbf{v}}_n^{new}& \leftarrow {\mathbf{v}}_n^{old}-\tilde{\eta }\cdot (-2{\tilde{r}}_{nm}{\mathbf{w}}_m^{old})\\ & ={\mathbf{v}}_n^{old}+2\tilde{\eta }\cdot {\tilde{r}}_{nm}{\mathbf{w}}_m^{old}\\ & ={\mathbf{v}}_n^{old}+\eta \cdot {\tilde{r}}_{nm}{\mathbf{w}}_m^{old}\\ \\ {\mathbf{w}}_m^{new}& \leftarrow {\mathbf{w}}_m^{old}-\tilde{\eta }\cdot (-2{\tilde{r}}_{nm}{\mathbf{v}}_n^{old})\\ & ={\mathbf{w}}_m^{old}+2\tilde{\eta }\cdot {\tilde{r}}_{nm}{\mathbf{v}}_n^{old}\\ & ={\mathbf{w}}_m^{old}+\eta \cdot {\tilde{r}}_{nm}{\mathbf{v}}_n^{old}\end{array}$$ 但注意，若 ${\mathbf{w}}_m$ 和 ${\mathbf{v}}_n$ 初始值皆為 $\mathbf{0}$，則無法有任何更新的行為

若對演算法有足夠的了解，可依其實際做出改善
針對電影的例子，因理論上越接近現在的時間，越接近使用者的喜好
依 SGD 設計出改進方案，最後 $T{}^{\prime }$ 次的更新限定在從最近的資料挑選，不再是從全部挑選

總結

• Extraction Models
• 將特徵轉換包含在學習中，最後執行 linear model 
• 好處
• 簡單，無需再特別設計 features
• powerful
• 壞處 
• 難以最佳化，因為 non-convex
• overfitting，需要適當的 regularization/validation
• 種類
• Adaptive/Gradient Boosting
• [ML] 機器學習技法：第十一講 Gradient Boosted Decision Tree  
• 特徵轉換
• hypotheses $g_t$ 
• 方法
• functional gradient descent
• linear model
• weights $\alpha t$
• Neural Network/Deep Learning
• [ML] 機器學習技法：第十二講 Neural Network  
• 特徵轉換
• weights $w_{ij}^{(l)}$
• 方法
• autoencoder 初始化權重
• SGD (backprop) 更新權重
• linear model
• weights $w_{ij}^{(L)}$
• RBF Network
• [ML] 機器學習技法：第十四講 Radial Basis Function Network 
• 特徵轉換
• RBF centers ${\mu }_m$
• 方法
• k-means clustering 初始化中心點
• linear model
• weights ${\beta }_m$
• k Nearest Neighbor
• lazy learning
• [ML] 機器學習技法：第十四講 Radial Basis Function Network
• 特徵轉換
• ${\mathbf{x}}_n$-neighbor RBF
• linear model
• weights $y_n$
• Matrix Factorization
• 因是對稱互為特徵轉換 與 linear model
• user features ${\mathbf{v}}_n$
• movie features ${\mathbf{w}}_m$
• 方法
• SGD
• alternating leastSQR

程式碼

BinaryVectorEncoding

from sklearn import preprocessing
 
 
lb = preprocessing.LabelBinarizer()
 
lb.fit(['A', 'B', 'A', 'AB', 'O'])
 
print(lb.classes_)
# array(['A' 'AB' 'B' 'O'])
 
print(lb.transform(['A', 'B']))
# [[1 0 0 0]
#  [0 0 1 0]]

參考

sklearn.preprocessing.LabelBinarizer
sklearn.preprocessing.OneHotEncoder