今回から4章の内容に入ってきます。
前回分はこちら↓↓
http://qiita.com/ru_pe129/items/9766d1cccb1e66c08bb9
すごい今更なのですが、私が書いている記事は直訳ではなく、僕の解釈やコメントが混ざっていることを考慮してください。もし誤りが合っても僕の誤りである可能性が高いです。また、勉強中の身なので、誤りに気づいたり疑問を持った場合には指摘してくださるととてもうれしいです。
さて、今回は4.1だけなのですが、とても長くなりました。。。ただ、数式も割と多めなので具体的な理解が出きると思います。
Chapter4 A Comprehensive Survey of Neighborhood-based Recommendation Methods
Nearest-Neighbor（近傍法）を用いた推薦はシンプルさ、効率、精度に優れており、ポピュラーな手法となっている。本章では近傍法を用いた推薦システムの特徴や応用例などを紹介する。
4.1 Introduction
オンライン市場の登場と普及により、消費者は非常に多くの商品にアクセスできる用になった。多くの商品に自由にアクセスできるようになったおかげでオンライン市場が大きく拡大した一方で、 消費者は多すぎる選択肢から自身のニーズに合った適切な選択肢を選ぶのが困難になっている 。こういった問題の一つのソリューションとして推薦システムを活用することが出来る。映画、音楽、CD、ジョーク、ウェブサイト、ニュースといった分野で推薦システムが活用されてきた。
推薦システムの問題は、ユーザーからのレスポンスを予測するすることとして定義づけることができる。レスポンスは3種類存在する。 スカラー（評価、rating）、バイナリー（like/dislike、interested/not interested）、unary（購入する、Webページを閲覧するといった行動） の3つである。そして、レスポンスの取得方法も二つに分けることが出来る。これまでにも紹介してきたように、 明示的なレスポンス と 暗示的なレスポンス が存在する。例えば、映画を見たときにユーザーが良し悪しを評価し、コメントを残すのは明示的なレスポンスである。一方、ユーザーが見た映画のジャンルや監督名、Webページを閲覧した時間などのユーザー自身に入力を強制しない、自然と提供される情報は暗示的なレスポンスとなる。
4.1.1 Formal Definition of the Problem
アイテム推薦の形式的な定義を行うために、いくつか言葉を定義しておく。
アイテム集合： $I$
ユーザーの集合： $U$
ユーザーがアイテムに対して与えうる評価の集合： $S$ （[like, dislike]や[1,2,3,4,5]といったもの）
ユーザーuによって評価されたアイテム集合： $I_{u}$
アイテムiを評価したユーザー集合： $U_{i}$
ユーザーuがアイテムiに対して行う評価： $r_{ui}$
ここで、各ユーザーは各アイテムに対して一つしか評価を行うことが出来ず、複数回異なった評価を行うことはできないという条件を加えておく。また、今回重要となるのはユーザーuとユーザーvの両者に評価されたアイテム集合と、アイテムiとアイテムjを評価したユーザー集合である。それぞれを $I_{uv}$ 、 $U_{ij}$ と表現することにする。
推薦システムにおけるもっとも重要な二つの課題は、最適なアイテムとトップN個のアイテムを推薦することである。まず最適なアイテムの推薦について考えてみよう。
あるユーザーuがもっとも興味を持ちそうなアイテムを、ユーザーuがまだ評価していないアイテムの中から発見することから始まる。ユーザーuがこれまでにつけた評価を利用可能であれば、ユーザーuが新しいアイテムiに対して与える評価を予測する関数$f(u,i)$を求める問題に帰着することが出来る。これを式にして表すと、 $f(u,i): U × I → S$ となる。この関数をあるアクティブユーザー$u_{a}$への推薦に利用する場合、以下の式で求まるアイテム$i^{*}$を推薦する。
i^{*} = argmax_{j\in I\\I_{u}} f(u_{a}, j)
一般的にユーザーuが行った評価の集合Rは、関数fを学習させる時に利用する訓練集合$R_{train}$と関数の精度を評価するためのテスト集合$R_{test}$に分割する。もっともポピュラーな評価指標は、MAE(Mean Absolute Error)とRMSE(Root Main Squared Error)である。
MAE(f) = \frac{1}{|R_{test}|}\sum_{r_{ui}\in{R_{test}}}|f(u,i)-r_{ui}|
RMSE(f)=\sqrt{\frac{1}{|R_{test}|}\sum_{r_{ui}\in{R_{test}}}(f(u,i)-r_{ui})^2}
評価を利用できない場合、たとえばユーザーの購入履歴しか分からない場合は評価予測を行うことは不可能である。そのような場合には、最適アイテムを推薦するタスクはあるアクティブユーザー$u_{a}$に興味がありそうなアイテムのリスト$L(u_{a})$を推薦するタスクとして解釈される。推薦の評価はアイテム集合Iを訓練集合$I_{trai}$とテスト集合$I_{test}$に分割することによって行う。ここで、$T(u)\subset{I_{u}\cap{I_{test}}}$をユーザーuが関係したアイテム（like, interestedなど）であると判断したテスト集合であると定義する。ユーザーのレスポンスがバイナリーの場合、T(u)としてカウントされるアイテムはlikeやinterestedの評価を受けたアイテムとなる。また購入リストやアクセスされたアイテムのみが得られる場合、これらのアイテムがT(u)に含まれることになる。このようなユーザーが与えた評価を推薦に用いることが出来ない場合の精度を評価する指標として、 Precision と Recall を用いる。
Precision(L) = \frac{1}{|U|}\sum_{u\in{U}}\frac{|L(u)\cap{T(u)}|}{L(u)}
Recall(L) = \frac{1}{|U|}\sum_{u\in{U}}\frac{|L(u)\cap{T(u)}|}{T(u)}
アイテムのリストL(u)を推薦する場合の欠点は、L(u)に含まれるアイテムがどれも一様にユーザーuが興味を持っているという仮定があることである。（おそらく、トップN個は区別されずに推薦されているケースを仮定している。）代替案として、L(u)の中のアイテムを「interestingness」という指標を用いて並べ替えるという方法がある。テスト集合が、各ユーザーuについてアイテム集合$I_{u}$のアイテム$i_{u}$をランダムに選択することによって作られたのであれば、アイテムのリストLは ARHR(Average Reciprocal Hit-Rank) という指標によって評価することができる。
ARHR(L) = \frac{1}{|U|}\sum_{u\in{U}}\frac{1}{rank(i_{u},L(u))}
$rank(i_{u},L(u))$はリストL(u)におけるアイテム$i_{u}$のランクを示す。もし$i_{u}$がL(u)に含まれていないのであれば、ランクは$\infty$として扱う。推薦システムに用いられる評価指標については8章で詳しく述べる。
4.1.2 Overview of Recommendation Approaches
推薦システムという研究分野が独立して現れてきたのは1990年代であるが、これまでに述べてきたように認知科学や情報検索と言った他の分野との深い関わりを持っている。そして、推薦システムの問題は一般的に、内容ベースでアプローチしていく方法と強調フィルタリングを用いてアプローチしていく方法の2つがある。
4.1.2.1 Content-based approaches
内容ベース（認知的）アプローチの基本的な考え方は、ユーザーが好んだアイテムと似た特徴を持ったアイテムを推薦するというものである。その特徴はベクトルによって表現出来ると考えられる。例えば、ニュースやWebページでは、各単語の Term Frequency-Inverse Document Frequency(TF-IDF) 値からなるベクトルとして表現されることが多い。さらに、各ユーザーの好みを表現するベクトル$\vec(X){u}$はアイテムリスト$I{u}$から得ることができ、ロッキオアルゴリズムによって計算される。
ロッキオアルゴリズムによって$\vec(X)_{u}$は以下の式によって更新される。
\vec(X)_{i} = \sum_{i\in{I_{u}}}r_{ui}\vec(X)_{i}
$\vec(X){i}$はアイテムiの特徴を表すベクトル、$r{ui}$はユーザーuがアイテムiに与えた評価である。したがって、上記の式は、ユーザーが高く評価したアイテムの特徴を強調し、低く評価したアイテムの特徴を小さくする式だと解釈することが出来る。したがって、この$\vec(X)_{u}$ともっとも類似度の高い特徴を持ったアイテムをユーザーuに推薦すれば良いことが分かる。類似度の指標としては コサイン類似度 や Minimum Description Length(MDL) が用いられる。
(MDLについてはこちら→ http://ja.wikipedia.org/wiki/%E6%9C%80%E5%B0%8F%E8%A8%98%E8%BF%B0%E9%95%B7)
3章でも述べたように、内容ベースの推薦システムは 分析に用いる情報が不足する 、分析に用いた情報に対して 特化しすぎて柔軟性がなくなる といった問題を抱えている。分析に用いる情報が不足するのは、プライバシーの問題でユーザーが情報提供を渋ったり、音楽や画像といった特徴を明確に定義することが難しかったりするからである。また、 内容の良し悪しを判断する事自体が難しい 。例えば、同じ出来事を扱ったニュース記事の良し悪しを判断することは容易ではない。用いられている単語も似たものになるため、先ほど説明した$\vec{X_{i}}$も類似したものになるだろう。柔軟性がなくなってしまうという問題については、内容ベースの推薦システムの特徴を表しているものである。この問題に対する解決方法ついては3章後半で述べた セレンディピティ の箇所を読んでいただきたい。
4.1.2.2 Collaborative filtering approaches
強調フィルタリングが内容ベースと異なる点は、ユーザーuに推薦を行う際に 他のユーザーの特徴や評価を利用する 点である。ユーザーuに似ているユーザーvがアイテムiに良い評価を与えたのであればユーザーuもアイテムiに良い評価を与えるだろうという考え方である。
強調フィルタリングは内容ベースが持ついくつかの限界を克服することができる 。例えば、あるユーザーuからフィードバックを得られない、もしくは得られていないジャンルのアイテムの推薦を可能にしている。また、アイテムが持つ情報に依存していないのも特徴であり、アイテムが推薦に悪影響を与える情報（表記ミスのようなもの？）を持っていた場合でも影響を受けない。また、内容ベースと違って、これまで ユーザーが興味を示してこなかったアイテムを推薦することができる ため、内容ベースに比べるとセレンディピティを実現しやすい。
強調フィルタリングは、 neighborhood（近傍法？？） と モデルベース の二つのグループに分けることが出来る。
近傍法を用いた場合、システムに蓄積された評価を推薦に直接利用する。そして、評価の利用方法には二つの種類がある。ユーザーベースとアイテムベースである。
ユーザーベースの場合、 ユーザーuがこれまでに行った評価と似たような評価を行ったユーザー（neighbor、好みが同じ人）が高評価を与えたアイテムを推薦する。 アイテムベースの場合、 評価したユーザーの組み合わせが似ているアイテムを推薦する。 例えば、ユーザーuはアイテムaを既に購入しているとする。そして、アイテムaとアイテムbには多くの共通したユーザーが良い評価を与えていたとする。このような場合、アイテムaとbは類似したアイテムであると見なしユーザーuにアイテムbを推薦する。。
モデルベースの場合、システムに蓄積された評価を直接用いるのではなく、これらの評価を利用して学習を行い、評価の予測モデルを作成する。具体的な手法としては、Baysian Clustering, Latent Semntic Analysis, Latent Dirichlet Allocation, Maximum Entropy, Boltzmann Machines, Support Vector Machines(SVM), Singular Value Decomposition(SVD)が挙げられる。最新のモデルベースの手法は５章で詳しく述べる。
4.1.3 Advantages of Neighborhood Approaches
最新のモデルベースは近傍法を用いたものよりも評価予測のタスクでは優れた結果を得られるという研究結果が報告されている。しかし、 正確な評価予測だけがユーザーの満足度を高めるわけではない ことにも留意したい。3章で述べたセレンディピティも一つの重要な要素である。
モデルベースの手法は ユーザーの嗜好を意味解釈して推薦に利用できる という長所もある。（意味解釈を人間に与えるというよりは、推薦結果に意味解釈が反映されているということだと思われる。）映画の推薦に例えると、具体的に「funny」「romantic」という特徴を直接抽出することができなくても、これらの映画が好きなユーザーを特定する。したがって、こういったユーザーに対してはfunnyでromanticな映画を推薦することが出来る。しかし、funnyでparodyでhorrorな映画の推薦は難しい。つまり、はっきりした概念で大きな枠組みでしか意味的解釈を推薦に適応することが出来ない。一方、近傍法を用いる場合、この様な細かい特徴づけが可能である。また、モデルベースではユーザーの嗜好に偏ったアイテムを推薦する可能性が高いが、近傍法ではまったく異なるジャンルのアイテムを推薦する場合がある。例えば、類似度の高いユーザvがユーザーuが知らないアイテムにたいしてすごく高い評価を与えていた場合、そのアイテムが推薦されるかもしれない。
近傍法を用いた場合のメリットは、
・ Simplicity：直感的で、調整するパラメータ（近傍としていくつ採用するか等）の種類も少ない
・ Justificability：ユーザーにとって推薦理由が解釈しやすい。推薦理由の説明の必要性は15章で述べる。
・ Efficiency：モデルベースと違って学習を必要としない
・ Stability：アイテムやユーザーが追加されても大きな影響を受けない。モデルベースの場合、これらが追加されれば再学習を行う必要があるだろう。
4.1.1 Objectives and Outline
4章の目的と今後の展開について述べられている。省略。
やっと終わりました。。。
割と3章との重複内容が多かった気がしますね。
今後も重複があるようですが、非常に基礎的なところ以外は復習としてまとめていくつもりです。