LoginSignup
65
61

More than 5 years have passed since last update.

@ysekkyin株式会社Gunosy

Recommender Systems survey - Knowledge-Based Systems (2013) 読んだ (1/2)

Last updated at Posted at 2013-08-07

長いので2回に分ける

概要と読む動機

2012年10月投稿，2013年4月採択の推薦システムのサーベイ論文
最新の技術動向の流れを確認したくて読むことにした
著者らもこのサーベイは過去のものと違い，有名な手法ではなく推薦システムのの進化に焦点を当てると述べているので期待がもてる

推薦システムのサーベイ論文について

イントロに書かれている内容の気になったところをメモ

この論文のポイント

  • 推薦システムの進化に焦点をあてる
  • 推薦システムの進化を理解するために重要であると著者が感じた課題のみを論じる
  • 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
  • 最近出てきている新たな課題について論じる．
    • プライバシーポリシー
    • セキュリティ
    • P2P
    • Internat of things
      • RFID data, health parameter, surveillance data, teleoperation telepresence, etc

2. Methodology

このサーベイ論文でどのように論文を選んだか？

  1. 300の論文を選択
  2. 300の論文から300の重要語を選択
  3. 語-論文行列を作り，そこから語のネットワークを作った

kobito.1375547166.008011.png

  • エッジが短い語の間は関係性が高い
  • ノードの大きさは重要性を表す

どのようにして引用文献を選んだか？

  • word graphですごく目立った語を重要なトピックと判断し，それに関する論文
  • 歴史的な貢献が大きいと判断した論文（古くて沢山引用されている論文)
  • 引用回数が多い論文
  • カンファレンス，Workshopに比べてImpact Factorが高い論文誌の論文を引用する
  • 古い論文より新しい論文を引用する

3. Recommender systems foundations

foundations

推薦システムで考慮すべき点
  • 推薦システムを適用するサービス内で活用できるデータの種類
  • 用いるフィルタリングアルゴリズム
  • 選択するモデル
    • 直接ユーザのデータを用いるメモリベースか，データからモデルを生成するモデルベースか？
  • その他のテクニックを採用するか
    • 確率的アプローチ，ベイジアンネットワーク，最近傍アルゴリズムなど
  • データのスパースさとスケール可能性
  • システムのパフォーマンス
  • 並べ方
  • 評価したい点
    • novelty, coverage and precision
よく使われるpublic database

kobito.1375550270.856598.png

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におけるクラスタリングが有効であると報告されている
基盤記述をまとめた図

kobito.1375626313.474298.png

cold start

評価値データなのど不足により，有益な推薦結果が作れない問題

  • new community problem
    • 推薦システムが出来たばっかりの時に評価値データが少ない
  • new item problem
    • 評価値のない新しいアイテムがシステムに追加されたとき
  • new user problem
    • 評価値が一定数貯まるまでユーザに適切が推薦ができない

対応としては評価値以外のデータを推薦で使えるように加えなければならない
そのためHybrid Filteringでよく話題になる
気になったものを以下にメモ

The k nearest neighbors recommendation algorithm

協調フィルタリングで用いられる推薦ロジック
ユーザ間のkNNはそれぞれのユーザのアイテムに対する評価で
アイテム間のkNNはそれぞれのアイテムが受けている評価で類似度を計算する

推薦方法
  1. 類似性指標を選ぶ
  2. 類似したユーザをk人選ぶ
  3. 類似したユーザが評価したアイテムについて，評価値の平均を取ったり，重みづけ和をとったりしてTop-nを選んで推薦する

kobito.1375634618.160160.png

k = 3で平均をとっている時の例

類似性指標について

伝統的にPeason, cosineなどの統計的な類似性指標が使われているが，
近年推薦システムに適した指標がいくつか提案されている

また 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
metricの評価

traditional metricsより，new metricsのほうが様々な指標で有効である．

kobito.1375772642.126958.png

cold start

コールドスタートに対して評価するために，MovieLensのデータから20−30レビューしているユーザのレビューを5-20取り除いた

kobito.1375782881.259718.png

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
評価のフレームワーク

現在の推薦システムの評価フレームワークには２つの欠点がある．

  • 定型化ができていない
    • 指標自体はしっかりと定義されている
    • 詳細な実行方法が定まっておらず，似た事件でも違う結果を出してしまうことがある．
  • 洗練性と信頼性という側面からの評価指標の標準化がなされていない

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

kobito.1375798103.450974.png

RMSE

kobito.1375797977.977683.png

Coverage

kobito.1375799684.297756.png

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

kobito.1375800039.585842.png

Recall

kobito.1375800149.836980.png

F1

kobito.1375800232.634226.png

4.3 Quality of the list of recommendations

pi : i番目の推薦アイテム
α: ユーザががレビューしそうなアイテムの数
d : default rating
k : 評価したアイテムのランク

half-life (HL)

kobito.1375800778.261524.png

discounted cumulative gain (DCG)

kobito.1375800937.501239.png

4.4 Novelty and diversity

diversity

推薦リスト内での多様性

kobito.1375801469.176232.png

novelty

ユーザの知識との多様性

kobito.1375802737.284973.png

4.5 Stability

推薦結果の安定性について
例えば、あるアイテムに対する評価が日によって違ってたらまずいよねっていう話

Pk(u,i) : ある時点におけるユーザuのアイテムiの評価値

kobito.1375802863.381846.png

4.6 Reliability

(サーベイ論文は(12)が誤植)

この予測結果はどのぐらい信頼出来るかという指標
(prediction value, reliability) とすると
(4.0, 0.9) , (4.5, 0.1) では恐らく前者が選ばれるのではないだろうか？という話
そのアイテムへの評価値はどれぐらい信頼性があるだろうか？

kobito.1375805235.134961.png

kobito.1375805680.991628.png

kobito.1375806170.530791.png

max, min : rateの定義域

65
61
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
65
61