ch-memorybase.tex

%!TEX root =  main.tex
%!TEX encoding = UTF-8 Unicode
\chapter{メモリベース型協調フィルタリング}
\label{chap:memorybase}

\termmain{メモリベース法}{memory-based method}とは，利用者DBを直接利用して，活動利用者の嗜好を推定する方法である．
機械学習の観点からは$k$近傍法 ($k$-nearest neighbor method)とみなせる．
この方法は，大きく\term{利用者間型メモリベース法}{user-user memory-based method}と\term{アイテム間型メモリベース法}{item-item memory-based method}とに分類できる．
どちらも，類似性を計算する点では共通しているが，利用者間型は，活動利用者と嗜好パターンが似ている利用者をまず見つけ，彼らが好むものを推薦する．
一方，アイテム間型では，活動利用者が好むアイテムと類似したアイテムを推薦する．これらの手法を順に紹介する．

\section{利用者間型メモリベース法}
\label{sec:user-user}
\index{利用者間型メモリベース法}\index{user-user memory-based method}

利用者間型メモリベース法の代表的な手法であるGroupLensの方法\cite{cscw:94:01}について述べる．
これは，協調フィルタリングの手順を自動化した先駆的研究である．
簡潔な手法だが，その予測精度は高く，多くの改良研究もなされている．
GroupLensは，当初は NetNews の記事を推薦するシステムであったが，現在は映画の推薦システム MovieLensとなっている．
この実験システムは，プロジェクトのホームページ\cite{misc:129} で公開されているので，推薦システムを体感するため利用してみてるとよいだろう．

レストランを探す場合のことを考えてみよう．
このとき，自分と食べ物の嗜好が似ている何人かの人に尋ねてみて，彼らの意見をもとにどの店で食事をするか決めたりすることがあるだろう．
GroupLensの方法は，こうした人のコミュニティでの「口コミ」による推薦の過程を，次の二段階で実現する．
\begin{description}
 \item[類似度の計算]
 利用者DB中の各標本利用者と活動利用者の嗜好の類似度を求める．
 類似度とは，嗜好パターンがどれくらい似ているかを定量化したものである．
 \item[嗜好の予測]
 活動利用者は知らないアイテムについて，それらのアイテムへの標本利用者の好みと，その標本利用者との間の類似度に基づいて，活動利用者がどれくらいそのアイテムを好むかを予測する．
\end{description}

%@@@ ch-cf  に問題の定式化の節を作成する
これらの段階について詳細に説明する前に，記号を定義する．
$n$人の全利用者の集合を$\calX=\cbr{1,\dotsc,n}$，$m$種類の全アイテムの集合を$\calY=\cbr{1,\dotsc,m}$とする．
評価値行列 $\bfR$ は利用者 $x\in\calX$ の，アイテム $y\in \calY$ への評価値$r_{xy}$ を要素とする行列である．
$r_{xy}$ は，評価済みなら評価値の定義域$\calR$のいずれかの値をとり，未評価なら欠損値「$\nan$」をとる．
例えば，5段階のスコアを用いた採点法（\ref{sec:explicitrating}節を参照）で獲得した嗜好データであれば，評価値の定義域は$\calR=\cbr{1,\dotsc,5}$となる．
活動利用者を添え字 $a$ で表す，すなわち，$r_{ay}$は活動利用者のアイテム$y$への評価値である．
また，利用者$x$が評価済みのアイテムの集合を$\calY_x=\cbr{y\mid y\in\calY, r_{xy}\ne\nan}$で表す．
活動利用者と標本利用者$x$の類似度は，共通に評価しているアイテムについてのPearson相関で測る．
\begin{equation}
\rho_{ax}=
\frac{\sum_{y\in\calY_{ax}}(r_{ay}-\bar{r}'_a)(r_{xy}-\bar{r}'_x)}%
{\sqrt{\sum_{y\in\calY_{ax}}(r_{ay}-\bar{r}'_a)^2}\sqrt{\sum_{y\in\calY_{ax}}(r_{xy}-\bar{r}'_x)^2}}
\label{eq:glsim}
\end{equation}
ただし，$\calY_{ax}$ は利用者$a$と$x$が共通に評価したアイテムの集合，すなわち，$\calY_{ax}=\calY_a\cap \calY_x$で，
${\bar{r}'}_x=\sum_{y\in \mathcal{Y}_{ax}}r_{xy}/|\calY_{ax}|$である．
なお，$|\calY_{ax}|\le1$，すなわち，活動利用者$a$と標本利用者$x$が共通に評価したアイテムが一つ以下ならば，Pearson相関は
計算できないので$\rho_{ax}=0$とする．
アイテム$y\notin\calY_a$の評価値は，式\eqref{eq:glsim}の類似度で重み付けした，各標本利用者のアイテム$y$への評価値の加重平均で予測する．
\begin{equation}
\hat{r}_{ay}=
\bar{r}_a+\frac{\sum_{x\in\calX_{y}}\rho_{ax}(r_{xy}{-}\bar{r}'_x)}{\sum_{x\in\calX_{y}}|\rho_{ax}|}
\label{eq:glscr}
\end{equation}
ただし，$\calX_y$はアイテム$y$を評価済みの利用者の集合で，$\bar{r}_{x}$は利用者$x$の全評価アイテムに対する平均評価値 $\bar{r}_x=\sum_{y\in\calY_x}r_{xy}/|\calY_x|$である．
なお，活動利用者がアイテム$y$を評価済みである$a\in\calX_y$である状況では，そもそも$\hat{r}_{ay}$の推定が不要になるので想定しなくてよい．
この式の第1項は，第2項が中間的な評価で0をとるので，それを補正するバイアス項である．
また，第2項の分子は上記の加重平均であり，分母は評価している利用者が多い，すなわち$|\calX_y|$が大きいと加重平均
が大きくなりやすい問題に対する正規化項である．
また，文献\cite{cscw:94:01}では，式\eqref{eq:glscr}の第2項のように，活動利用者と標本利用者が共に評価したアイテム$\calY_{ax}$上での評価値の平均$\bar{r}'_x$を用いている．
だが，現在のGroupLensプロジェクトでは，単純に評価済みアイテムの平均値$\bar{r}_x$を用いているとのことであり%
\footnote{J.~Riedlのメールより}，また，筆者の実験でも，どちらを用いても有意な差はみられなかった．
加えて，$\bar{r}_x$の方が，活動利用者が決まる前に事前に計算できる利点があるので，実際に利用するときには$\bar{r}_x$を用いる方が良いだろう．

\begin{table}
\centering
\caption{評価値行列$\bfR$の例}
\label{tab:exrate}
 \begin{tabular}{l@{\qquad}cccc}\toprule
\makebox[5zw]{} &
  \makebox[5zw]{1\,:\,親子丼} & \makebox[5zw]{2\,:\,牛丼} &
  \makebox[5zw]{3\,:\,海鮮丼} & \makebox[5zw]{4\,:\,カツ丼} \\\hline
1\,:\,山田 & 1      & 3      & $\nan$ & 3      \\
2\,:\,田中 & $\nan$ & 1      & 3      & $\nan$ \\
3\,:\,佐藤 & 2      & 1      & 3      & 1      \\
4\,:\,鈴木 & 1      & 3      & 2      & $\nan$ \\
\bottomrule
 \end{tabular}
\end{table}

ここで簡単な例を挙げよう．
表\ref{tab:exrate}はどんぶり専門店『丼兵衛』の評価値行列$\bfR$の例である．
4人の利用者は各行に対応し，4種類のアイテム(＝どんぶり)は列に対応する．
評価値は3段階の採点法，すなわち，$\calR=\cbr{1,2,3}$である．
この表は，利用者3の佐藤のアイテム2の牛丼の評価値は1で，嫌いであることを示している．
具体的に，活動利用者を田中，すなわち$a=2$とし，2\,:\,田中の1\,:\,親子丼への推定評価値$\hat{r}_{2,1}$を求めてみよう．

まず，式\eqref{eq:glsim}の相関係数を求める．
親子丼を評価済みの利用者，すなわち$\calX_1$に含まれる各利用者と活動利用者の間の相関係数を求める必要がある．
1\,:\,山田，3\,:\,佐藤，4\,:\,鈴木の3人とも親子丼を評価済みなので$\calX_1=\cbr{1,3,4}$の各利用者との相関係数を求める．
2\,:\,田中と1\,:\,山田の相関係数$\rho_{2,1}$は，共通に評価しているアイテムが2\,:\,牛丼だけで，1個以下なので$\rho_{2,1}=0$となる．
次に，2\,:\,田中と3\,:\,佐藤の間の相関係数を計算する．
この二人が共通に評価しているのアイテムは2\,:\,牛丼と3\,:\,海鮮丼なので$\calY_{2,3}=\cbr{2,3}$となる．
すると，これらのアイテムについての$\calY_{2,3}$上の平均評価値はそれぞれ
\begin{align*}
{\bar{r}'}_2 &=(\sum_{y=2,3}r_{2,y})/2=(1+3)/2=2 \\
{\bar{r}'}_3 &=(\sum_{y=2,3}r_{3,y})/2=(1+3)/2=2
\end{align*}
となり，相関係数は次式になる．
{\small\begin{align*}
\rho_{2,3}&=\frac{\sum_{y=2,3}(r_{2,y}-{\bar{r}'}_2)(r_{3,y}-{\bar{r}'}_3)}%
{\sqrt{\sum_{y=2,3}(r_{2,y}-{\bar{r}'}_2)^2}%
 \sqrt{\sum_{y=2,3}(r_{3,y}-{\bar{r}'}_3)^2}}\\
&=\frac{(1-2)(1-2)+(3-2)(3-2)}{\sqrt{(1-2)^2+(3-2)^2}\sqrt{(1-2)^2+(3-2)^2}}\\
&=1
\end{align*}}
同様に計算すると2\,:\,田中と4\,:\,鈴木の相関は$\rho_{2,4}=-1$となる．

次に推定評価値を計算する．まず，2\,:\,田中の全評価済みアイテム上の平均評価値を求める．
\[
\bar{r}_2=(\sum_{y=2,3}r_{2,y})/2=(1+3)/2=2 
\]
最後に，これまで計算した値を式\eqref{eq:glscr}に代入すると
{\small\begin{align*}
\hat{r}_{2,1}&=\bar{r}_2+
\frac{\sum_{x=1,3,4}\rho_{2,x}(r_{x,1}-{\bar{r}'}_x)}%
{\sum_{x=1,3,4}|\rho_{2,x}|} \\
&=2+\frac{0(1-3)+1(2-2)+(-1)(1-5/2)}{|0|+|1|+|-1|}\\
&=2.75
\end{align*}}
によって，2\,:\,田中の1\,:\,親子丼への推定評価値は$2.75$と計算できる．
この値は，最大値3にかなり近く，2\,:\,田中は1\,:\,親子丼が好きであると予測される．

%@@@ コサインを使った暗黙的評価の場合

\subsection{利用者間型メモリベース法の改良}

GroupLensの方法にはいろいろな改良が試みられている．
文献\cite{sigir:99:02}では，いろいろな改良を実験的に検証している．
全ての計算の前に，評価値 $r_{xy}$ から利用者$x$の平均評価値$\bar{r}_x$を引いて正規化しておくと予測精度は向上する．
これは，\ref{sec:explicitrating}節で述べたように，計測された評価値揺らぎや偏りがある．
肯定的でも否定的でもない評価値を$0$に正規化することで，こうした不整合が緩和されるためであろうと著者は考える．
利用者の近傍を使う改良もある．
ここでの近傍とは，式\eqref{eq:glsim}の相関が大きな，すなわち活動利用者と類似した嗜好をもつ利用者の集合のことである．
式\eqref{eq:glscr}の推定評価値は，アイテム$y$を評価済みの全ての利用者の評価に基づいているが，これを事前に計算した活動利用者の近傍のみに基づいて計算する．
実験によれば，近傍利用者数がある程度以上になると，それ以降は増やしても予測精度は向上しない．
よって，近傍利用者だけに計算を限定することで計算量を減らし，データベースの参照も抑制できるので，効率よく計算できるようになる．
ただし，モデルベース法のモデルほど頻繁にする必要はないが，近傍は定期的に更新しなくてはならないので，純粋なメモリベース法の利点は部分的には失われる．
また，新規の参加者については近傍を新たに計算する必要が生じ，脱退者が他の利用者の近傍利用者であれば予測精度の低下を招く．
以上の，二つの改良は，ほとんどのデータに対して有効なので，適用しておく方がよいだろう．
その他，この文献\cite{sigir:99:02}では，データが疎である問題に対処するため，活動利用者と標本利用者が共通に評価しているアイテムの数に応じて重み付けしたり，式\eqref{eq:glsim}のPearson相関の代わりに順位相関を使ったりすることは予測精度の向上に役立ったと報告している．

文献\cite{uai:98:01}にも，いくつかの改良が示されている．
その一つに，評価値の数が少ない場合に有効な\term{デフォルト投票}{default voting}がある．
利用者間の類似度は，共通に評価しているアイテム$\calY_{ax}$への評価に基づいて計算する．
しかし，そうしたアイテムが少ないか，全くない場合には，適切に類似度を評価できない．
例えば，利用者1と2の評価済みアイテム集合がそれぞれ$\calY_1=\cbr{1,2,3}$と$\calY_2=\cbr{1,4,5}$とする．
このとき，これら二人の類似度は共通して評価しているアイテム$1$に対する評価値$s_{1,1}$と$s_{2,1}$の二つの値だけに依存する．
このとき類似度は，共通に評価したアイテム数$|\calY_1\cap \calY_2|$は一つだけなので$0$となってしまう．
そのため，これらの利用者間の類似度は全く推薦の精度向上に寄与しない．
そこで，利用者1の$r_{1,2}$，$r_{1,3}$と，利用者2の$r_{2,4}$，$r_{2,5}$の評価値を活用する．
例えば，$r_{1,2}$の評価値は，利用者2の対応する値$r_{2,2}$があれば相関の計算に利用できる．
そこで，アイテム2の中立的な評価値，すなわち，全利用者のアイテム2への評価値の平均$\tilde{r}_y=\sum_{x\in\cal{X}_y} r_{xy}/|\calX_y|$をデフォルト投票値とし，$r_{2,2}$の値をこのデフォルト投票値で置き換える．
他のアイテムについても同様の置き換えをすると，アイテム集合$\calY_1\cup\calY_2=\cbr{1,2,3,4,5}$上でより適切に利用者間の類似度を評価できるようになる．
筆者の実験でも，一人あたりの評価値数が少ない状況でかなりの効果が確認された．
%また，$r_{xy}$の欠損を補うときに，アイテムの平均評価値$\tilde{r}_y$の代わりに，利用者$x$の全アイテム上の平均評価値$\bar{r}_x=\sum_{x\in\calYx_x}r_{xy}/|\calY_x|$も利用する実験も行ったが，あまり良い結果は得られなかった．
%しかし，どちらのデフォルト投票値が良くなるかは，データに依存するので，\ref{sec:recomtype}節の方法で予測精度を評価し，良い方を採用するとよいだろう．
この文献\cite{uai:98:01}では，最低や最高など両端に近い評価値をより重視する改良や，評価している利用者が少ないアイテムへの評価値を重視する改良などを提案している．

\ref{sec:rsyslimit}節で述べたように推薦システムが扱うデータは非常に疎である．
機械学習では，このような場合には，次元削減の前処理を実行することが多い．
代表的な方法に主成分分析\cite{eb:053:00,jpublist:077x,jb:021:00}がある．
GroupLensの方法では，各利用者は$m$個のアイテムへの評価値を要素とするベクトルで表される．
これをデータの分散に関する情報をできるだけ失わないように，$K< m$の$K$要素のベクトルで各利用者を表現するのが主成分分析である．
この$K$要素に情報を圧縮したベクトルで，利用者間の類似度を求める方法もよく用いられている\cite{ec:007,sigir:06:01}．
ただし，主成分分析は欠損値があると実行できないので，上記のデフォルト投票値やEMアルゴリズムなどによって適当に評価値行列$S$を補完する必要がある．

\section{アイテム間型メモリベース法}
\label{sec:item-item}
\index{アイテム間型メモリベース法}\index{item-item memory-based method}

GroupLensなどの利用者間型では，評価値行列$\bfR$の行ベクトル，すなわちある利用者のいろいろなアイテムへの嗜好を表すベクトルの類似度に基づいて，他の利用者の評価値を予測した．
一方，アイテム間型メモリベース法では，アイテムベクトル，すなわち，$\bfR$の列ベクトルの類似度を用いる．
これは，いろいろな人に同じような評価を受けるアイテムは似ていると考え，ある利用者が関心をもっているアイテムの類似アイテムにも，その利用者は関心をもつという仮定に基づいている．
簡単な方法としては，アイテムベクトルのコサイン\cite{ieeem:03:01}や，単純な共起性\cite{www:07:01}，Pearson相関などでアイテム間の類似度を測り，利用者が閲覧中や，買い物かごに入れている，もしくは，直近の利用履歴にあるアイテムと類似しているアイテムを推薦する．
これら方法によって，協調フィルタリングの枠組みで，一時的個人化（\ref{sec:plevel}節）\index{一時的個人化}\index{ephemeral personalization}をした推薦ができる．

GroupLensの方法と同様に加重平均を使う方法としては\cite{www:01:02}がある．
この方法では，活動利用者のアイテム$y$への推定評価値を次式で求める．
\begin{equation}
\hat{r}_{ay}=
\frac{\sum_{j\in\calY_a}\rho'_{yj}r_{aj}}{\sum_{j\in\calY_a}|\rho'_{yj}|}
\label{eq:iicf}
\end{equation}
ただし，${\rho'}_{yj}$はアイテム$y$と$j$の類似度である．
この方法は文献\cite{kdd:04:11}でも利用され，アイテム間の類似度行列と活動利用者自身の評価値があれば利用者DBを参照することなく，ローカルマシンだけで推薦を計算できる．
よって，ある程度のプライバシー保護（\ref{chap:privacy}章）も実現できる．
GroupLensの方法と同様に，$\calX_a$に含まれるアイテム全てではなく，${\rho'}_{kj}$がしきい値以上の近傍に計算を限定すると，予測精度を下げることなく，式\eqref{eq:iicf}の計算を高速化できる．
だが，近傍アイテムが重要なので，公開中の映画・コンサートなどのように推薦対象のアイテムが頻繁に入れ替わる\textbf{item churn}\index{item churn}という状況では，頻繁な近傍の更新が必要になってしまう．
この方法は，評価しているアイテム数が少ない利用者には推薦が早くできる．
利用者間型より予測精度はよいとの報告もある．
しかし，理論的根拠はないが，実験的には特定のアイテムに推薦が偏る傾向が強く\cite{sigchi:06:01}，多様性についてはアイテム間型は不利であるといわれている．

\section{メモリベース法に関するその他の研究}
\label{sec:other-memory-based}

\ref{sec:explicitrating}節でも述べたように，利用者の評価値には一貫性が低い問題がある．
そこで，McLaughlinら\cite{sigir:04:01}は，投票された評価値を隣接した評価値に配分する信念分配 (belief distribution) を利用したGroupLens法の拡張を示した．
利用者が指定した評価値に最も大きな重みを与えると共に，その周囲の評価値にも小さな重みの評価値を与える．
例えば，評価値4を利用者が指定したとき，評価値4には$0.6$の重みで，それに隣接する評価値3や5には$0.2$の重みがあると考える．
すなわち，ファジィ理論でのメンバーシップ関数のようなものである．
しかし，この重みの分配の割合は予測精度に大きく影響するが，この割合は調整は試行錯誤によって行わなければならない問題がある．

\ref{sec:explicitrating}節では，利用者から嗜好データを得るために，採点法や格付け法ではなく順位法を用いるなんとなく協調フィルタリング\cite{epublist:039}について述べた．
ここでは，順位法で得た嗜好順序を使って推薦する方法について述べる．
手法は非常に単純で，嗜好順序中のアイテムの順位をそのまま評価値とする．例えば，利用者$x$がアイテム 1，2，3，4 を好きなものから順に$3{\succ}2{\succ}4{\succ}1$と並べた場合，アイテム4の順位は2であり，$r_{x4}=2$ として扱う．
このとき，$r_{xy}$が小さいほど好きなことを表すので，式\eqref{eq:glscr}の$\hat{r}_{ay}$ が小さいものから順に推薦する．
また，順位法では評価は常に相対的なので，予測評価値も相対的な好みしか示さないことに注意しなくてはならない．
利用者ごとに整列したアイテム数が異なる場合には，嗜好順序の長さが一定ではない．
この場合は，嗜好順序の長さを$L$とし，この嗜好順序中のアイテム$y$の順位を$\mathrm{rank}_y$としたとき，$r_{xy}=\mathrm{rank}_y(m+1)/(L+1)$とする．
これは，嗜好順序に含まれる$L$個の対象が，$m$個の全対象から一様にランダムに選ばれたとしたときの，アイテム$y$の順位の期待値である．
著者の実験\cite{epublist:064}では，採点法で得た評価値を正規化するなどしても，順位法による嗜好データに基づく予測順序の精度の方が良かった．

GroupLensの方法では，利用者間の類似度は式\eqref{eq:glsim}のPearson相関で測っている．
実験的にはこの類似度でかなり良い予測精度が得られているが，理論的な根拠は弱い．
そこで，さらに予測精度を向上させるため，経験損失を最小にするようにこの類似度関数を学習する方法\cite{kdd:07:01}もある．
これにより予測精度は向上するが，\ref{sec:memory-model}節で述べたモデルベース法と同じ適応性の問題を生じてしまう．

純粋に理論的な観点から，Pennockら\cite{aaai:00:02}は，望ましい協調フィルタリングが備えるべき公理的性質について論じた．
\index{不可能性定理}\index{impossibility theorem}
これは，社会全体での意志決定を論じる社会選択の研究で著名なArrowの不可能性定理\cite{eb:040:00}のような考え方である．
四つの公理的性質として，全定義域と最小機能（universal domain and minimal functionality），全員一致（Pareto性，unanimity)，無関係な候補からの独立性（independence of irrelevant alternatives)，スケール不変性（scale invariance)を挙げている．
これらの，性質を満たす予測手法は最近傍法のみであることを示している．
実際の推薦システムで，これらの公理的性質が厳密に満たされなければならないわけではないが，こうした研究は推薦システムの手法の選択指針について参考になるであろう．