機械学習のアレ

機械学習に関する怪しいメモやらあれこれその他メモやら

Restricted Boltzmann Machine for Collaborative Filtering

Restricted Boltzmann Machine for Collaborative Filtering

f:id:utool:20170617235951p:plain

RBMを用いて協調フィルタリングを行うことが出来ます。

これはNetflix Prizeなる情報推薦のコンペで好成績を収めたそうです。
要となることはRBMに関して、欠損データに関するノードを除外して用いるというだけです。


いろいろ定義

  • M

Mを値が存在するアイテムのラベル番号と定義しましょう。
上の図を例にするなら値が存在するデータは一つしかないのでM=\{1\}となります。

  • K

Kはデータのクラス(カテゴリ)を表した集合で、M=\{1,2,3,4,5\}のようになります

  • H

Hは隠れ変数それぞれのインデックス番号の集合です。上の図では隠れ変数は二個なのでH=\{1, 2\}となります。

  • \boldsymbol{v}

可視変数\boldsymbol{v}1-\mathrm{of}-K表現を用いています。

  • \boldsymbol{h}

隠れ変数\boldsymbol{h}は二値表現を用いています。

確率関数

\begin{align}
P\left(\boldsymbol{v}, \boldsymbol{h} \mid \boldsymbol{\theta}\right) = \frac{1}{Z}\exp\left( - E \right)
\end{align}

エネルギー関数

\begin{align}
E = - \sum_{i\in M}\sum_{j \in K} b_{i, j} v_{i, j} -\sum_{i \in V}\sum_{j \in Y}\sum_{k \in H} w_{i, j, k} v_{i, j} h_k - \sum_{k \in H}c_k h_k
\end{align}

ポテンシャル関数

\begin{align}
\Phi = \exp \left( \sum_{i\in M}\sum_{j \in Y} b_{i, j} v_{i, j} +\sum_{i \in V}\sum_{j \in Y}\sum_{k \in H} w_{i, j, k} v_{i, j} h_k + \sum_{k \in H}c_k h_k \right)
\end{align}

実験結果

Netflix Prizeのデータセットが合法的に手に入るか微妙なのでMovielensで代用しました。

Movielens 100k(ua.base, ua.test)

Type RMSE MAE
Softmax 1.16983 0.839767
Gaussian 1.04158 0.835285

いいのか悪いのかよくわからない…
もしかしたら欠損データに対応したノードを隠れ変数として扱って適当にサンプリングして補完すれば性能は上がるかもしれないです。

一応ソースコード
ML/RBMCF at master · utool-kc/ML · GitHub



特別付録: Softmax RBM

f:id:utool:20170617235942p:plain

エネルギー関数

\begin{align}
E = - \sum_{i\in V}\sum_{j \in Y} b_{i, j} v_{i, j} -\sum_{i \in V}\sum_{j \in Y}\sum_{k \in H} w_{i, j, k} v_{i, j} h_k - \sum_{k \in H}c_k h_k
\end{align}

ポテンシャル関数

\begin{align}
\Phi = \exp \left( \sum_{i\in V}\sum_{j \in Y} b_{i, j} v_{i, j} +\sum_{i \in V}\sum_{j \in Y}\sum_{k \in H} w_{i, j, k} v_{i, j} h_k + \sum_{k \in H}c_k h_k \right)
\end{align}

周辺確率

\begin{align}
P\left( \boldsymbol{v} \right) &= \sum_{\boldsymbol{h}}P\left( \boldsymbol{v}, \boldsymbol{h}  \right) \\
 &= \frac{1}{Z} \exp \left( \sum_{i \in M}\sum_{k \in K}b_{i, k} v_{i, k}  \right) \prod_{j \in H} \sum_{h_j=\{0, 1\}} \exp \left( \sum_{i \in M}\sum_{k \in K}w_{i, k, j}v_{i, k} + c_j \right) \\
 &= \frac{1}{Z} \exp \left( \sum_{i \in M}\sum_{k \in K}b_{i, k} v_{i, k}  \right) \prod_{j \in H} \left( 1 + \exp \left( \sum_{i \in M}\sum_{k \in K}w_{i, k, j}v_{i, k} + c_j \right) \right)
\end{align}

条件付き確率

 \begin{align}
P\left(\boldsymbol{v} \mid \boldsymbol{h} \right) &= \prod_{i \in M} P\left(v_{i,k} \mid \boldsymbol{h} \right) \\

P\left(v_{i, k} = 1 \mid \boldsymbol{h} \right) &= \frac{\displaystyle \exp\left( b_{i, l} + \sum_{j \in H} w_{i,k,j}h_j \right)} {\displaystyle \sum_{l \in K}\exp\left( b_{i, l} + \sum_{j \in H} w_{i,l,j}h_j \right)} \\

P\left(\boldsymbol{h} \mid \boldsymbol{v} \right) &= \prod_{j \in H} P\left(h_j \mid \boldsymbol{v} \right) \\

P\left(h_j \mid \boldsymbol{v} \right) &= \frac{\exp\left( h_j \left(\sum_{i \in M}\sum_{l \in K}w_{i, l, j}v_{i, l. j} + c_j\right) \right)} {\displaystyle 1 + \exp \left(\sum_{i \in M}\sum_{l \in K}w_{i, l, j}v_{i, l. j} + h_j\right) }
\end{align}


対数尤度関数の勾配

\begin{align}
\nabla b_{i, k} &= \frac{1}{N}\sum_{n=1}^N d_{i, k}^{(n)} &-& \sum_{\boldsymbol{v}}\sum_{\boldsymbol{h}} v_{i,k} P\left(\boldsymbol{v}, \boldsymbol{h}\right) \\

\nabla c_j &= \frac{1}{N}\sum_{n=1}^N \mathrm{Act}\left(c_j + \sum_{i\in V}\sum_{l\in K}w_{i,l, j}d_{i,l}^{(n)} \right) &-& \sum_{\boldsymbol{v}}\sum_{\boldsymbol{h}} h_j P\left(\boldsymbol{v}, \boldsymbol{h}\right) \\

\nabla w_{i,k,j} &= \frac{1}{N}\sum_{n=1}^N  d_{i,k}^{(n)} \mathrm{Act}\left(c_j + \sum_{i\in V}w_{i,k,j}d_{i,k}^{(n)} \right) &-& \sum_{\boldsymbol{v}}\sum_{\boldsymbol{h}} v_{i,k} h_j P\left(\boldsymbol{v}, \boldsymbol{h}\right) \\

\end{align}


\begin{align*}
\mathrm{Act}\left( x \right) = \mathrm{sigmoid}\left( x \right) = \frac{1}{1 + \exp(-x)}
\end{align*}

特別付録: Gaussian Bernoulli RBM

可視変数\boldsymbol{v} (-\infty, +\infty) 実数値を取るようなモデルです。

エネルギー関数

\begin{align}
E = \sum_{i\in V}\frac{\lambda_i v_i^2}{2} - \sum_{i\in V} b_{i} v_{i} -\sum_{i \in V}\sum_{j \in H} w_{i, j} v_{i} h_j - \sum_{j \in H}c_j h_j
\end{align}

ポテンシャル関数

\begin{align}
\Phi = \exp \left( -\sum_{i\in V}\frac{\lambda_i v_i^2}{2} + \sum_{i\in V} b_{i} v_{i} +\sum_{i \in V}\sum_{j \in H} w_{i, j} v_{i} h_j + \sum_{j \in H}c_j h_j \right)
\end{align}

エネルギー関数に2乗の項を追加したおかげで (-\infty, +\infty) 区間でポテンシャル関数の可視変数\boldsymbol{v}積分することが可能となります。

条件付き確率

隠れ変数を条件として与えた確率
 \begin{align}
P\left(\boldsymbol{v} \mid \boldsymbol{h} \right) &= \prod_{i \in M} P\left(v_i \mid \boldsymbol{h} \right) \\

P\left(v_i \mid \boldsymbol{h} \right) &= \frac{\displaystyle \exp\left( \frac{\lambda_i}{2 } \left(v_i - \frac{1}{\lambda_i} \left(b_i + \sum_{j \in H}w_{i,j}h_j \right) \right)^2 \right)} {\displaystyle \int_{\infty}^{\infty} \exp\left( \frac{\lambda_i}{2 } \left(v_i - \frac{1}{\lambda_i} \left(b_i + \sum_{j \in H}w_{i,j}h_j \right) \right)^2 \right)} \\
 &= \sqrt{\frac{\lambda_i}{2\pi}} \exp\left( \frac{\lambda_i}{2} \left(v_i - \frac{1}{\lambda_i} \left(b_i + \sum_{j \in H}w_{i,j}h_j \right) \right) ^2 \right) 
\end{align}
つまり、平均 \frac{1}{\lambda_i} \left(b_i + \sum_{j \in H}w_{i,j}h_j \right), 分散\frac{1}{\lambda_i}に従うガウス分布になります。


可視変数を条件として与えた確率
 \begin{align}
P\left(\boldsymbol{h} \mid \boldsymbol{v} \right) &= \prod_{j \in H} P\left(h_j \mid \boldsymbol{v} \right) \\

P\left(h_j \mid \boldsymbol{v} \right) &= \frac{\displaystyle \exp\left( h_j \left(\sum_{i \in M}w_{i, j}v_i + c_j\right) \right)} {\displaystyle 1 + \exp\left(\sum_{i \in M}w_{i, j}v_i + c_j \right)} 
\end{align}

周辺確率

\begin{align}
P\left( \boldsymbol{v} \right) &= \sum_{\boldsymbol{h}}P\left( \boldsymbol{v}, \boldsymbol{h}  \right) \\
 &= \frac{1}{Z} \exp \left( - \sum_{i \in M}\frac{\lambda_i v_i^2}{2} + \sum_{i \in M}b_i v_i  \right) \prod_{j \in H} \sum_{h_j} \exp \left( \sum_{i \in M}w_{i, j}v_i + c_j \right)
\end{align}

対数尤度関数の勾配

\begin{align}
\nabla b_i &= \frac{1}{N}\sum_{n=1}^N d_i^{(n)} &-& \sum_{\boldsymbol{v}}\sum_{\boldsymbol{h}} v_i P\left(\boldsymbol{v}, \boldsymbol{h}\right) \\

\nabla c_j &= \frac{1}{N}\sum_{n=1}^N \mathrm{Act}\left(c_j + \sum_{i\in V}w_{i,j}d_i^{(n)} \right) &-& \sum_{\boldsymbol{v}}\sum_{\boldsymbol{h}} h_j P\left(\boldsymbol{v}, \boldsymbol{h}\right) \\

\nabla w_{i,j} &= \frac{1}{N}\sum_{n=1}^N  d_i^{(n)} \mathrm{Act}\left(c_j + \sum_{i\in V}w_{i,j}d_i^{(n)} \right) &-& \sum_{\boldsymbol{v}}\sum_{\boldsymbol{h}} v_i h_j P\left(\boldsymbol{v}, \boldsymbol{h}\right) \\
\end{align}



\begin{align*}
\mathrm{Act}\left( x \right) = \mathrm{sigmoid}\left( x \right) = \frac{1}{1 + \exp(-x)}
\end{align*}


このパラメータは非負の制約があるうえ、学習が不安定でなおかつオーバーフローしやすいなる面倒な問題があります。ちゃんと学習できるらしいのですが困ったら固定値のほうがよさそう
\begin{align}
\nabla \lambda_i &= - \frac{1}{N}\sum_{n=1}^N \frac{\left(d_i^{(n)}\right)^2}{2} &+& \sum_{\boldsymbol{v}}\sum_{\boldsymbol{h}} \frac{v_i^2}{2} P\left(\boldsymbol{v}, \boldsymbol{h}\right)
\end{align}