長いので2回に分ける
##概要と読む動機
2012年10月投稿，2013年4月採択の推薦システムのサーベイ論文
最新の技術動向の流れを確認したくて読むことにした
著者らもこのサーベイは過去のものと違い，有名な手法ではなく推薦システムのの進化に焦点を当てると述べているので期待がもてる
##推薦システムのサーベイ論文について
イントロに書かれている内容の気になったところをメモ
- 近年の推薦システムの適用領域について
- 初期の推薦システムの方式について
- 協調フィルタリングの評価について
- ハイブリッドシステムのサーベイ
- http://link.springer.com/article/10.1023/A:1021240730564
- 2002年の論文，当時はあまり使われなかった
- 近年Social Networksを通して人気が出てきている
- 次世代の推薦システムのための注目すべきポイント
##この論文のポイント
- 推薦システムの進化に焦点をあてる
- 推薦システムの進化を理解するために重要であると著者が感じた課題のみを論じる
- relavantな手法については特に紹介せず，以下の３つについて中心に述べる
- traditional web
- social web
- presently progress ( Interner of things )
- 推薦システム分野におけるよい読み物とするためにいくつかの伝統的なトピックを加える
- 最初の推薦システムである k-Nearest Neighbors algorithm
- cold-start 問題
- similarity measure
- 推薦システムの評価
- 残りの部分でこれまでのサーベイ論文では論じられていない最新のトピックについて取り扱う （これは後半に書きます）
- social information
- social filtering, followers, followed, trust, reputation, credibility, content-based filtering of social data, social tagging, taxonomies
- recommending to grouos of users
- explaining recomendations
- location-aware recommender systems
- bio-inspired approad
- social information
- 最近出てきている新たな課題について論じる．
- プライバシーポリシー
- セキュリティ
- P2P
- Internat of things
- RFID data, health parameter, surveillance data, teleoperation telepresence, etc
2. Methodology
このサーベイ論文でどのように論文を選んだか？
- 300の論文を選択
- 300の論文から300の重要語を選択
- 語-論文行列を作り，そこから語のネットワークを作った
- エッジが短い語の間は関係性が高い
- ノードの大きさは重要性を表す
####どのようにして引用文献を選んだか？
- word graphですごく目立った語を重要なトピックと判断し，それに関する論文
- 歴史的な貢献が大きいと判断した論文（古くて沢山引用されている論文)
- 引用回数が多い論文
- カンファレンス，Workshopに比べてImpact Factorが高い論文誌の論文を引用する
- 古い論文より新しい論文を引用する
3. Recommender systems foundations
foundations
#####推薦システムで考慮すべき点
- 推薦システムを適用するサービス内で活用できるデータの種類
- 用いるフィルタリングアルゴリズム
- 選択するモデル
- 直接ユーザのデータを用いるメモリベースか，データからモデルを生成するモデルベースか？
- その他のテクニックを採用するか
- 確率的アプローチ，ベイジアンネットワーク，最近傍アルゴリズムなど
- データのスパースさとスケール可能性
- システムのパフォーマンス
- 並べ方
- 評価したい点
- novelty, coverage and precision
#####よく使われるpublic database
filtering algotithm
- collaborative filtering
- ユーザにコンテンツを評価させ，評価情報が十分に溜まったとき，同じような評価行動をしているユーザが高く評価しているコンテンツを推薦する
- 最も広く使われている手法はk-近傍アルゴリズムである
- demographic filtering
- 性別，年齢，居住地などから推薦する
- content-based filtering
- ユーザが過去に選択したコンテンツを元に推薦する
- コンテンツ間の類似性を元に，コンテンツから類似したコンテンツを推薦する．
- hybrid filtering
- CFとdemographicを使う，もしくはCFとcontent-basedを用いる
- bioinspiredもしくはproblistic methodが大抵元になっている
- genetic algorithm, fuzzy genetic, neaural networks, Bayesian networks, clustering, latent features
#####メモリベースとモデルベース
- メモリベース
- 評価をユーザ-アイテム行列として用いる
- 事前の評価を用いてアイテムへの評価を決める
- ユーザ間もしくはアイテム間の類似度を用いる
- モデルベース
- 推薦システムに用いるデータを統計モデル等でモデル化し，推薦結果を生成する
- ナイーブベイズ，ニューラルネットワーク，ファジーシステム，遺伝的アルゴリズム，latent feature, 因子分解など
- 推薦システムに用いるデータを統計モデル等でモデル化し，推薦結果を生成する
スパース性における次元削減
- 因子分解
- LSIとSVDの組み合わせ
- SVDは精度いいけど計算は時間がかかる
- オフライン実験ならいいけど，データの更新に弱い
クラスタリング
精度向上やコールドスタート問題に対する対策として使われる
- itemをクラスタリングする
- itemとuserをクラスタリングする(bi-clustering)
- tagging, social link, trustにおいてSNSにおけるクラスタリングが有効であると報告されている
#####基盤記述をまとめた図
cold start
評価値データなのど不足により，有益な推薦結果が作れない問題
- new community problem
- 推薦システムが出来たばっかりの時に評価値データが少ない
- new item problem
- 評価値のない新しいアイテムがシステムに追加されたとき
- new user problem
- 評価値が一定数貯まるまでユーザに適切が推薦ができない
対応としては評価値以外のデータを推薦で使えるように加えなければならない
そのためHybrid Filteringでよく話題になる
気になったものを以下にメモ
- association ruleを用いたハイブリッドフィルタリング
- キーワード情報とデモグラ情報でCFを作る
- latent featureを用いたもの
- filterbotを用いたもの
The k nearest neighbors recommendation algorithm
協調フィルタリングで用いられる推薦ロジック
ユーザ間のkNNはそれぞれのユーザのアイテムに対する評価で
アイテム間のkNNはそれぞれのアイテムが受けている評価で類似度を計算する
推薦方法
- 類似性指標を選ぶ
- 類似したユーザをk人選ぶ
- 類似したユーザが評価したアイテムについて，評価値の平均を取ったり，重みづけ和をとったりしてTop-nを選んで推薦する
k = 3で平均をとっている時の例
#####類似性指標について
伝統的にPeason, cosineなどの統計的な類似性指標が使われているが，
近年推薦システムに適した指標がいくつか提案されている
- http://dl.acm.org/citation.cfm?id=1831931
-
http://dl.acm.org/citation.cfm?id=2064272
- 後述のSING
- http://dl.acm.org/citation.cfm?id=1361689
また cold-startに特化したものもある
#####欠点
- コールドスタートとスパースさに弱い
- スケーラビリティが低い
- ユーザ数が増えれば増えるほど計算が遅くなる
Similarity measures
traditional metrics
- Peason correlation (CORR)
- cosine (COS)
- adjusted cosine (ACOS)
- constrained correlation (CCORR)
- Mean Squared Differences (MSD)
- Euclidean (EUC)
new metrics
- JMSD
- MSDによる数値情報と，Jaccardによる非数値情報を組み合わせて計算する
- SING
- メモリベース協調フィルタリングに特化した類似指標
- ユーザ間，アイテム間の情報ではなく，全ユーザの評価情報を用いて計算する
- http://dl.acm.org/citation.cfm?id=2064272
- GEN
- 遺伝的アルゴリズムに基づいた類似性指標
- 新しいデータに対しても適切に更新される
- http://www.sciencedirect.com/science/article/pii/S0950705111001146
- TRUST
- ユーザの信頼度を評価値データから得る
- http://dl.acm.org/citation.cfm?id=1498256
metricの評価
- この論文のフレームワークを用いて評価
traditional metricsより，new metricsのほうが様々な指標で有効である．
#####cold start
- PIP
- cold start問題を考慮したヒューリスティックな類似性指標
- http://dl.acm.org/citation.cfm?id=1296682
- UEROR
- error-reflected modelを用いてユーザの初期の評価とその誤り率を予測する
- http://dl.acm.org/citation.cfm?id=1985174
コールドスタートに対して評価するために，MovieLensのデータから20−30レビューしているユーザのレビューを5-20取り除いた
yraditional metricsよりnew metricsのほうが有効である
4. Evaluation of recommender systems results
#####代表的な評価手法
- prediction metrics
- Mean Absolute Error (MAE)
- Root of Mean Square Erorr (RMSE)
- set recommendation metrics
- Precision
- Recall
- Receiver Operationg Characteristic (ROC)
- rank recommendation metrics
- half-life
- discounted cumulative gain
- diversity metrics
- diversity
- novelty
ほとんどの研究ではprediction metricsばかりが論じられており，その数値を向上させることに目が向けられているが
近年diversity, noveltyが提案され注目されている．
cross validation
- ramdom subsumpling
- k-fold cross validation
- leave-one-out cross validation
- cold startの時に使う
- http://dl.acm.org/citation.cfm?id=2107834
評価のフレームワーク
- Herlicker et al. (1999) [92]
- http://dl.acm.org/citation.cfm?id=312682
- similarity weight, significance weighting, variance weighting, selecting neighborhood, rating nomalization
- Hernandez and Gaudisi (2008) [95]
- http://dl.acm.org/citation.cfm?id=1383762
- どのような推薦システムも２つのサブシステムからなる
- ユーザをガイドする
- 有益なアイテムを提供する
- Antunes et al. [12] (2012)
- http://dl.acm.org/citation.cfm?id=2089128
- システムのライフサイクルの中で評価は進化していくという仮定に基づく
現在の推薦システムの評価フレームワークには２つの欠点がある．
- 定型化ができていない
- 指標自体はしっかりと定義されている
- 詳細な実行方法が定まっておらず，似た事件でも違う結果を出してしまうことがある．
- 洗練性と信頼性という側面からの評価指標の標準化がなされていない
###4.1 Quality of the predictions
define
U : set of Users
I : set of items
p{u,i} : the prediction of item i on user u
r{u,i} : the rating of user u on item i
Ou : ユーザuが評価しており，予測もされているアイテムの集合
Cu : ユーザuが評価しておらず，Neighbourのだれかが評価しているアイテムの集合
Du : ユーザuが評価していないアイテム
#####MAE
#####RMSE
Coverage
###4.2 Quality of the set of recommendations
Xu : set of recommendations to user u
Zu : set of n recommendations to user u
θ : relevancy threshold
n : Assuming that all users accept n test recommendations
Precision
Recall
F1
4.3 Quality of the list of recommendations
pi : i番目の推薦アイテム
α: ユーザががレビューしそうなアイテムの数
d : default rating
k : 評価したアイテムのランク
half-life (HL)
discounted cumulative gain (DCG)
4.4 Novelty and diversity
diversity
推薦リスト内での多様性
novelty
ユーザの知識との多様性
4.5 Stability
推薦結果の安定性について
例えば、あるアイテムに対する評価が日によって違ってたらまずいよねっていう話
Pk(u,i) : ある時点におけるユーザuのアイテムiの評価値
4.6 Reliability
(サーベイ論文は(12)が誤植)
この予測結果はどのぐらい信頼出来るかという指標
(prediction value, reliability) とすると
(4.0, 0.9) , (4.5, 0.1) では恐らく前者が選ばれるのではないだろうか？という話
そのアイテムへの評価値はどれぐらい信頼性があるだろうか？
max, min : rateの定義域