Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

おすすめ商品を見つけ出すフィルタリングのメモ

More than 1 year has passed since last update.

はじめに

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層ボルツマンマシンに似てるのでは?と思いました.

arsware
受託開発とシステムエンジニアリングサービス(SES)を中心とした少数精鋭エンジニアチームです
http://www.arsware.co.jp/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away