はじめに
Courseraの機械学習コースの中で紹介してくれる協調フィルタリングについて，自分の理解度確認と備忘を兼ねた記事としています．
「おすすめ機能」
コースで使用していた映画の評価に基づくおススメの映画を求めるという問題を考えてみる．
例えば，4人のレビュアーと5つの映画がありそれぞれ0から5までの6段階評価をしたとする．
| Movie | Alice(1) | Bob(2) | Carol(3) | Dave(4) |
|---|---|---|---|---|
| Love at last | 5 | 5 | 0 | 0 |
| Romance forever | 5 | ? | ? | 0 |
| Cute puppies of love | ? | 4 | 0 | ? |
| Nonstop car chases | 0 | 0 | 5 | 4 |
| Swords vs. karate | 0 | 0 | 5 | ? |
ところどころ**?となって抜けている部分がある．「?**の評価がそれぞれいくつになるか？」というのが問題となる．
問題の形式化
上表を以下のような式に落とし込む．
\begin{align}
n_u &= 4 \\ \\
n_m &= 5 \\ \\
r &= \left(\begin{matrix}
1 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 \\
1 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 \\
\end{matrix}
\right) \\
\\
y &= \left(\begin{matrix}
5 & 5 & 0 & 0 \\
5 & 0 & 0 & 0 \\
0 & 4 & 0 & 0 \\
0 & 0 & 5 & 4 \\
0 & 0 & 5 & 0 \\
\end{matrix}
\right)
\end{align}
それぞれ，$n_u$はユーザー数，$n_m$は映画の種類，$r(i,j)$はユーザ$j$が映画$i$を評価していると1になる2値行列，$y^{(i,j)}$はユーザ$j$が映画$i$を評価したレート値（評価していないのは$0$にしてある）になっている．
コンテンツベースフィルタリング
英語では，Content-based Filteringとなる？
オススメ機能（リコメンド機能）というのは，相関の高いものを提示することである．
上表の例を取り上げると，まず，映画にはアクションものや恋愛もの，SFなど色々な特徴がある．これらを全部挙げ尽くして1次式を作る．これが仮説関数$h_\Theta(x)$となり，そこで使うパラメータ$\Theta$を学習させるのが，コンテンツベースフィルタリングの学習方法である．
まず，必要な変数を定義する．
$\theta^{(j)}$をユーザー$j$のパラメータベクトル，$x^{(i)}$を映画$i$の特徴ベクトルとする．そうすると，$(\theta^{(j)})^T(x^{(i)})$が予測値となる．
ユーザー$j$のパラメータ$\theta^{(j)}$の最適化問題は以下のようになる．
\min_{\theta^{(j)}}\frac{1}{2}
\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2 + \frac{\lambda}{2}\sum_{k=1}^{n}(\theta_k^{(j)})^2
1つ目の$\sum$にある$i:r(i,j)=1$は，「$r(i,j)=1$となっている$i$」といういみである．
これから，全ユーザーのパラメータ$\theta^{(j)}$を最適化させるには
\min_{\theta^{(1)},\ \dots,\ \theta^{(n_u)}}
\frac{1}{2}\sum_{j=1}^{n_u}
\sum_{i:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2 + \frac{\lambda}{2}
\sum_{j=1}^{n_u}\sum_{k=1}^{n}(\theta_k^{(j)})^2
となる．しかし，映画の特徴ベクトル$x^{(i)}$の値が定まっていないため，以下のようなユーザーのパラメータ$\theta^{(j)}$から学習しなくてはならない．
\min_{x^{(1)},\ \dots,\ x^{(n_m)}}
\frac{1}{2}\sum_{i=1}^{n_m}
\sum_{j:r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2 + \frac{\lambda}{2}
\sum_{i=1}^{n_m}\sum_{k=1}^{n}(x_k^{(i)})^2
つまり，$x^{(i)}$と$\theta^{(j)}$を交互に最適化問題を解くことになる．
協調フィルタリング
英語では，Collaborative Filteringとなる．
上記のようにコンテンツベースフィルタリングでは，$x^{(i)}$と$\theta^{(j)}$を交互に求めていくことになるため，それを1度に解いてしまうというものである．コスト関数とすれば，
\begin{align}
J(x^{(1)}, \dots,x^{(n_m)},\theta^{(1)}, \dots,\theta^{(n_u)}) =
&\frac{1}{2}\sum_{(i,j):r(i,j)=1}((\theta^{(j)})^Tx^{(i)}-y^{(i,j)})^2 \\
&+ \frac{\lambda}{2}\sum_{i=1}^{n_m}\sum_{k=1}^{n}(x_k^{(i)})^2 + \frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^{n}(\theta_k^{(j)})^2 \\
\end{align}
となり，
\min_{\begin{matrix}
x^{(1)}, \dots,x^{(n_m)} \\ \theta^{(1)}, \dots,\theta^{(n_u)}
\end{matrix}}
J(x^{(1)}, \dots,x^{(n_m)},\theta^{(1)}, \dots,\theta^{(n_u)})
という最適化問題を組み立てることが出来る．
最小化させる値が多いだけで，問題なく勾配降下法を用いることが出来る．
まとめ
普段，ECサイトや広告で目にする「あなたにおすすめの商品」などのリコメンダシステムはこのようなフィルタリングを実装しているのだろうと思えるようになりました．協調フィルタリングに至っては，若干，2層ボルツマンマシンに似てるのでは？と思いました．