[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 的 \(\left \{ (\mathbf{v}_n,r_{nm}) \right \}\) 做 linear regression
    2. 最佳化 \(\mathbf{v}_1,\mathbf{v}_2,\cdots,\mathbf{v}_N\)
      更新 \(\mathbf{v}_n\)，利用 n-th-user 的 \(\left \{ (\mathbf{w}_m,r_{nm}) \right \}\) 做 linear regression
首先，先說明例子
共有 100,480,507 ratings，裡面有 480,189 users 對於 17,770 movies 進行評分
定義資料為 \(\left \{ (\tilde{\mathbf{x}}_n=(n),y_n=r_{nm})\right \}\)：第 n 個使用者對於第 m 部電影給予評分 r
在這比較特別的是 \(\tilde{x}_n=(n)\) 是抽象的
只知道編號，不會知道其他任何資料，像是男女、高矮、胖瘦等
這種 feature 也叫做 categorical features
無任何數值的意義，只是種類，像是 ID, 血型, 喜好語言等，皆是此特性
目前學過的方法，可以直接處理的，只有 decision trees，其餘皆需要再轉換為 numerical
可以使用 binary vector encoding，像是血型
$$ \begin{matrix} A=[1\ 0\ 0\ 0]^T & B=[0\ 1\ 0\ 0]^T \\ AB=[0\ 0\ 1\ 0]^T & O=[0\ 0\ 0\ 1]^T \end{matrix} $$ 所以將評分資料重新編碼，並且整合在一起，稱作
$$ D = \left \{ (\tilde{\mathbf{x}}_n=BinaryVectorEncoding(n),\mathbf{y}_n=[r_{n1}\ ?\ \ ?\ r_{n4}\ r_{n5}\ \cdots\ r_{nM}]^T)\right \} $$ 因為不見得使用者能對每部電影都有評分，所以 \(\mathbf{y}_n\) 會有缺，也就是 ？ 項
考慮利用 \(N-\tilde{d}-M\) 類神經網路莘取出特徵
將常數項 \(x_0^{(l)}\) 移掉，比較簡單分析，也可以加入，模型略有變化而已
然而，tanh 是必要的嗎？
事實上因為 \(\mathbf{x}\) 只會在一個維度上為 1，其他皆為 0
所以再多經過一次轉換並不是必須的，所以可改為線性
而且 \(\mathbf{y}_n\) 可缺項，並將前後的權值重新命名為 \(\mathbf{V}^T\) 和 \(\mathbf{W}\)，推導時會比較簡潔
$$ \begin{align*} 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{\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} \begin{bmatrix} 0\\ \vdots \\ 1\\ \vdots \\ 0 \end{bmatrix}\\ &=(\mathbf{W}_{\tilde{d}\times M})^T\mathbf{v}_n\\ \\ h_m(\mathbf{x})&=\mathbf{w}_m^T\Phi (\mathbf{x})\\ h_m(\mathbf{x}_n)&=\mathbf{w}_m^T\Phi (\mathbf{x}_n)\\ &=\mathbf{w}_m^T\mathbf{v}_n\\ \end{align*} $$ \(\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{align*} E_{in}(\left \{ \mathbf{w}_m \right \},\left \{ \mathbf{v}_n \right \})&=\frac{1}{\sum_{m=1}^{M}|D_m|}\sum _{user\ n\ rated\ movie\ m}(r_{nm}-\mathbf{w}_m^T\mathbf{v}_n)^2\\ &\propto \sum _{user\ n\ rated\ movie\ m}(r_{nm}-\mathbf{w}_m^T\mathbf{v}_n)^2\\ &= \sum_{m=1}^{M}\left ( \sum _{(\mathbf{x}_n,r_{nm})\in D_m}(r_{nm}-\mathbf{w}_m^T\mathbf{v}_n)^2 \right )\cdots (1)\\ &= \sum_{n=1}^{N}\left ( \sum _{(m,r_{nm})\in D_n}(r_{nm}-\mathbf{w}_m^T\mathbf{v}_n)^2 \right )\ \cdots (2) \end{align*} $$ \(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{align*} \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{align*} $$
SGD 可參考 [ML] 機器學習基石：第十一講 Linear Models for Classification
單個的錯誤如下式
$$ err(user\ n, movie\ m, rating\ r_{nm})=(r_{nm}-\mathbf{w}_m^T\mathbf{v}_n)^2 $$ 因為是針對 n,m 隨機抽取，所以除 n,m 以外的 gradient 是為 0，無需 update
故對 n,m 取 gradient
$$ \begin{align*} \triangledown_{\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 \\ \triangledown_{\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{align*} $$ 將 \(\tilde{r}_{nm}=(r_{nm}-\mathbf{w}_m^T\mathbf{v}_n)\)
$$ \begin{align*} \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{align*} $$ 但注意，若 \(\mathbf{w}_m\) 和 \(\mathbf{v}_n\) 初始值皆為 \(\mathbf{0}\)，則無法有任何更新的行為
若對演算法有足夠的了解，可依其實際做出改善
針對電影的例子，因理論上越接近現在的時間，越接近使用者的喜好
依 SGD 設計出改進方案，最後 \(T{}'\) 次的更新限定在從最近的資料挑選，不再是從全部挑選

總結


程式碼

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

留言

張貼留言