1
本 日 の 内 容 第 1 部 : RecSys 2010 概 要 第 2 部 : RecSys 2010 研 究 動 向 第 3 部 : RecSys 今 後 の 展 望 とおまけ 2
本 日 の 内 容 第 1 部 : RecSys 2010 概 要 3
The 4th ACM Conference on Recommender Systems, Barcelona, Spain 開 催 経 緯 Recommenders 06 Summer School in Bilbao, Spain The 1st Conference in Minneapolis, USA The 2nd Conference in Lausanne, Switzerland The 3rd Conference in New York, USA 4
募 集 トピック(CFPより 一 部 抜 粋 ) Conversational RecSys Context aware and multidimensional RecSys Evaluation of RecSys Group recommenders Machine learning and RecSys Recommendation algorithms Recommendation in social networks RecSys interface... 5
論 文 採 択 率 full paper 25 / 129 (19.4%) short paper 32 / 78 (41.0%) 6
ワークショップ (1/2) PRSTAT Practical Use of Recommender Systems, Algorithms, & Technology HetRec International Workshop on Information Heterogeneity and Fusion in Recommender Systems RecSysTEL Workshop on Recommender Systems for Technology Enhanced Learning RSWeb 2nd Workshop on Recommender Systems and the Social Web 7
ワークショップ (2/2) WOMRAD Workshop on Music Recommendation and Discovery USERSTI User Centric Evaluation of Recommender Systems and Their Interfaces CARS 2nd Workshop on Context Aware Recommender Systems & Challenge on Context Aware Movie Recommendation 8
本 日 の 内 容 第 2 部 : RecSys 2010 研 究 動 向 9
RecSys 2010 における 研 究 トピック 概 要 ソーシャルネットワークに 基 づく 推 薦 システム (9 件 ) コンテキストアウェア 推 薦 システム (1 件 +CARS 8 件 ) グループベース 推 薦 システム (3 件 ) 精 度 比 較 (3 件 ) 推 薦 精 度 以 外 の 評 価 指 標 (4 件 ) アルゴリズム (3 件 ) ユーザ 評 価 (2 件 ) 10
RecSys 2010 における 研 究 トピック 概 要 ソーシャルネットワークに 基 づく 推 薦 システム (9 件 ) コンテキストアウェア 推 薦 システム (1 件 +CARS 8 件 ) グループベース 推 薦 システム (3 件 ) 推 薦 精 度 以 外 の 評 価 指 標 (4 件 ) 11
ソーシャルネットワークに 基 づく 推 薦 システム 12
ソーシャルネットワークに 基 づく 推 薦 システム アイテム 推 薦 人 物 推 薦 コミュニティ 推 薦 13
ソーシャルネットワークに 基 づく 推 薦 システム アイテム 推 薦 14
アイテム 推 薦 に 関 する 研 究 T. Lappas et al.: Interactive Recommendations in Social Endorsement Networks. M. Jamali et al.: A Matrix Factorization Technique with Trust Propagation for Recommendation in Social Networks. 15
アイテム 推 薦 に 関 する 研 究 T. Lappas et al.: Interactive Recommendations in Social Endorsement Networks. 16
ソーシャル 推 奨 ネットワーク ユーザとアイテム 間 の 推 奨 関 係 を 表 したネットワーク 推 奨 17
推 奨 アイテムグループの 抽 出 共 通 ユーザ 推 奨 推 奨 アイテムグループ なぜ 多 くの 共 通 するユーザによって 推 奨 されているのか? 18
推 奨 アイテムグループへのタグ 付 け なぜ 多 くの 共 通 するユーザによって 推 奨 されているのか? カフェ カフェ おしゃれ 安 い おしゃれ リラッ クス 高 級 カフェ おしゃれ グループタグ 両 アイテムに 共 通 に 付 与 されたタグ 19
推 奨 アイテムグループの 推 薦 クエリ カフェ おしゃれ にマッチする 推 奨 アイテムグループを 推 薦 推 奨 ユーザ 数 :3 グループサイズ:2 推 奨 ユーザ 数 :4 グループサイズ:3 ソーシャルネットワーク 上 の 集 合 知 の 活 用 推 薦 結 果 が 理 解 可 能 20
ソーシャルネットワークに 基 づく 推 薦 システム 人 物 推 薦 21
人 物 推 薦 に 関 する 研 究 L. Pizzato et al.: RECON: A Reciprocal Recommender for Online Dating. J. Hannon et al.: Recommending Twitter Users to Follow Using Content and Collaborative Filtering Approaches. E. Baglioni et al.: A Lightweight Privacy Preserving SMS based Recommendation System for Mobile Users. P. Symeonidis et al.: Transitive Node Similarity for Link Prediction in Social Networks with Positive and Negative Links. 22
人 物 推 薦 に 関 する 研 究 L. Pizzato et al.: RECON: A Reciprocal Recommender for Online Dating. 23
相 互 推 薦 システムRECON ユーザプロファイルと 相 手 への 嗜 好 から 相 性 判 定 を 行 い, 相 性 の 良 い 人 物 を 推 薦 33 歳, 標 準 体 型 嗜 好 25~34 歳, 標 準 体 型 Ben Alice 30 歳, 標 準 体 型 Bob Amy 嗜 好 30~34 歳, 筋 肉 質 Charlie Carol 24
相 互 推 薦 システムRECON ユーザプロファイルと 相 手 への 嗜 好 から 相 性 判 定 を 行 い, 相 性 の 良 い 人 物 を 推 薦 33 歳, 標 準 体 型 嗜 好 25~34 歳, 標 準 体 型 Ben 30 歳, 標 準 体 型 Amy 嗜 好 30~34 歳, 筋 肉 質 25
ユーザプロファイルの 抽 出 メッセージ 履 歴 に 着 目 Alice 10 人 に メッセージ... どんな 人 にメッセージを 送 っているのか? 25~29 歳, 6 標 準, 4 30~34 歳, 1 細 身, 1 20~24 歳, 3 25~29 歳 で, 筋 肉 質 または 標 準 体 型 の 男 性 が 好 み? 筋 肉 質, 5 26
適 合 スコアの 算 出 Alice 男 性, 9 0.20 女 性, 1 Amy との 適 合 スコア 女 性 1/10 25~29 歳, 6 標 準, 4 30~34 歳, 1 細 身, 1 20~24 歳, 3 筋 肉 質, 5 30 歳 1/10 標 準 体 型 4/10 ave. = 0.20 27
相 性 スコアの 算 出 適 合 スコア Alice Amy Bob Ben Alice 0.20 0.67 0.47 Amy 0.00 0.72 0.53 Bob 0.72 0.45 0.15 Ben 0.40 0.60 0.00 Ben Amy Benとの 相 性 スコア Ben x x Ben ave. Amy 0.60 0.53 0.56 Alice 0.40 0.47 0.43 Bob 0.00 0.00 28
個 人 向 け 推 薦 と 相 互 推 薦 の 特 徴 の 違 い 個 人 向 け 推 薦 項 目 相 互 推 薦 個 人 次 第 推 薦 が 成 功 するか 相 互 に 依 存 消 極 的 明 示 的 な 詳 細 プロファイルの 公 開 積 極 的 長 期 的 暗 黙 的 な 嗜 好 抽 出 が 容 易 同 様 の 推 薦 結 果 が 他 の 多 くのユーザ にも 適 用 可 能 利 用 者 推 薦 システム の 利 用 期 間 推 薦 結 果 の 再 利 用 性 推 薦 システム におけるユーザ の 位 置 付 け 短 期 的 cold start 問 題 他 の 多 くのユーザ には 推 薦 される べきではない 利 用 者 でもあり, 推 薦 システムの 一 部 でもある 29
人 物 推 薦 に 関 する 研 究 J. Hannon et al.: Recommending Twitter Users to Follow Using Content and Collaborative Filtering Approaches. 30
Twittomender (http://twittomender.ucd.ie/) User Recommendation Twitter 上 のユーザプロファイル に 基 づき,フォローすべき ユーザを 推 薦 User Search 入 力 されたクエリに 基 づき, 関 連 するユーザの ランキングを 提 示 31
Twitterに 基 づくユーザプロファイリング followers (U T ) U T followees (U T ) 協 調 フィルタリング tweets (U T )......... followers tweets (U T )...... followees tweets (U T )...... 内 容 に 基 づくフィルタリング 32
Twitterに 基 づくユーザプロファイリング followers (U T ) followees (U T ) 協 調 フィルタリング tweets (U T )......... followers tweets (U T ) 実 験 では, U協 T 調 フィルタリングによる 推 薦 の 方 が 精 度 が 高 かったことを 確 認...... followees tweets (U T )...... 内 容 に 基 づくフィルタリング 33
ソーシャルネットワークに 基 づく 推 薦 システム コミュニティ 推 薦 34
コミュニティ 推 薦 に 関 する 研 究 V. Vasuki et al.: Affiliation Recommendation using Auxiliary Networks. 35
ソーシャルネットワークと アフィリエーションネットワーク ユーザ ユーザの ソーシャルネットワーク ユーザ コミュニティ アフィリエーションネットワーク λs A 36
コミュニティ 推 薦 ユーザ ユーザ 行 列 とユーザ コミュニティ 行 列 を 結 合 λs 37
コミュニティ 推 薦 ユーザ ユーザ 行 列 とユーザ コミュニティ 行 列 を 結 合 C λs A A T 0 38
コミュニティ 推 薦 ユーザ ユーザ 行 列 とユーザ コミュニティ 行 列 を 結 合 C λs A A T 2 3 0 katz(c;β)= β C β 2 C β 3 C... 39
グループベース推薦 40
グループベース 推 薦 に 関 する 研 究 L. Baltrunas et al.: Group Recommendations with Rank Aggregation and Collaborative Filtering. S. Berkovsky et al.: Group Based Recipe Recommendations: Analysis of Data Aggregation Strategies. M. Xie et al.: Breaking out of the Box of Recommendations: From Items to Packages. 41
グループベース 推 薦 に 関 する 研 究 L. Baltrunas et al.: Group Recommendations with Rank Aggregation and Collaborative Filtering. S. Berkovsky et al.: Group Based Recipe Recommendations: Analysis of Data Aggregation Strategies. 42
グループベース 推 薦 の 実 現 方 式 集 約 モデル 方 式 CF 集 約 モデル ユーザモデル CF 推 薦 候 補 CF 推 薦 候 補 CF 推 薦 候 補 推 薦 候 補 集 約 候 補 推 薦 アイテム 集 約 候 補 方 式 推 薦 アイテム ユーザモデル 43
重 み 付 けモデル 誰 の 嗜 好 を 重 視 するか? Pre-defined model Uniform model 均 等 に 重 み 付 け Interaction-based model Role based model 他 の 家 族 内 の 役 割 を 参 照 して 重 み 付 け 1 1 1 0.1 0.5 0.7 Heuristic model 常 識 的 に 定 義 Family-log model 家 族 内 の 活 動 度 に 基 づき 重 み 付 け 0.5 0.3 0.1 0.1 0.6 0.3 44
Extreme case heuristics 極 端 な 好 き 嫌 いがある 場 合 Least misery heuristics( 最 小 不 幸 法 ) 一 人 でも 大 嫌 いなメンバがいる 場 合 は 推 薦 しない 好 き! 大 好 き! 0 0 1 大 嫌 い! Most pleasure heuristics( 最 大 幸 福 法 ) 一 人 でも 大 好 きなメンバがいる 場 合 は 推 薦 する 大 好 き! 普 通 1 0 0 嫌 い! 45
Extreme case heuristics 極 端 な 好 き 嫌 いがある 場 合 Least misery heuristics( 最 小 不 幸 法 ) 一 人 でも 大 嫌 いなメンバがいる 場 合 は 推 薦 しない 好 き! 大 好 き! Most pleasure heuristics( 最 大 幸 福 法 ) 一 人 でも 大 好 きなメンバがいる 場 合 は 推 薦 する 大 好 き! 一 人 でも 大 嫌 いな 人 がいる 場 合, 大 嫌 い! 0 それを 0 推 薦 1 しないことによって 推 薦 システムに 対 する 信 頼 性 は 向 上 する 普 通 一 人 でも 大 好 きな 人 がいる 場 合, 嫌 い! 1それを 0推 薦 することによって, 0 他 のメンバにとってセレンディピティにつながる 46
ランク 集 約 手 法 A B A B C 1st 2nd 3rd C Average 2.7 1.3 2.0 Spearman footrule 順 位 間 の 距 離 が 最 小 となる 順 列 を 選 ぶ Least misery ( 最 小 不 幸 ) Borda count 順 位 スコア(1st 3, 2nd 2,...) に 応 じてランキング 8 6 4 47
グループ構成による 推薦精度の違い 図はL. Baltrunasらの論文より 2 3 4 データセット MovieLens 評価データ数 100,000 映画データ数 1,682 ユーザ数 943人 8 グループサイズ (a) ランダムグループ (b) 高類似度グループ グループ内の人数が多いほど グループ推薦の効果が低下するとはいえない 48
グループ推薦時の 精度向上率 個人向け推薦の精度と グループ推薦時の精度向上率との関係 個人向け推薦の精度が 低い場合 グループ向け 推薦がそれを補う形で 推薦精度の向上に寄与 個人向け推薦の精度 グループ内メンバの 嗜好が類似しているほど グループ向け推薦に対し満足 推薦精度 図はL. Baltrunasらの論文より グループ内メンバの類似度 49
コンテキストアウェア 推 薦 システム 50
コンテキストアウェア 推 薦 システム Rec Sys コンテキスト 事 前 フィルタリング Rec Sys コンテキスト 事 後 フィルタリング コンテキスト 統 合 モデリング 51
コンテキスト 事 前 フィルタリング 事 前 にコンテキストに 合 ったアイテム 集 合 を 選 択 し, そのアイテム 集 合 に 対 し, 情 報 推 薦 技 術 を 適 用 52
コンテキスト 事 後 フィルタリング 情 報 推 薦 技 術 により 推 薦 候 補 アイテム 集 合 を 選 び, そのアイテム 集 合 からコンテキストに 合 ったアイテムを 選 択 予 算 30,000 以 内 推 薦 候 補 35,000 60,000 18,000 25,000 53
コンテキスト 統 合 モデリング コンテキストを 含 めてユーザの 嗜 好 をモデル 化 し, そのモデルに 基 づいて 情 報 推 薦 を 実 行 コンテキスト 依 存 型 ユーザ 嗜 好 モデル c x 1 x 2 54
コンテキストアウェア 推 薦 システムに 関 する 研 究 A. Karatzoglou et al.: Multiverse Recommendation: N dimensional Tensor Factorization for Context aware Collaborative Filtering. 55
行 列 因 子 分 解 4 0 4 0 0 2 2 3 1 2 2 3 ユーザ - アイテム 行 列 を ユーザ 行 列,アイテム 行 列 に 分 解 し, ユーザとアイテムを 表 現 する 潜 在 的 特 徴 を 学 習 0 0 1 1 1 2 3 4 0 0 0 1 2 1 1 2 0 0 1 1 1 0 1 0 2 0 2 0 1 3 0 0 1 1 56
テンソル 因 子 分 解 による コンテキスト 統 合 モデリング アイテム I ユーザ S U C (1) 事 前 事 後 フィルタリングの 必 要 なし (2) 計 算 がシンプル (3) 多 次 元 でも 処 理 可 能 57
推 薦 精 度 以 外 の 評 価 指 標 58
推 薦 精 度 に 関 する 評 価 指 標 再 現 率 適 合 率 MAE (Mean Absolute Error) ndcg (Normalized Discounted Cumulative Gain) 順 位 相 関 係 数 必 ずしも 推 薦 精 度 の 高 い 推 薦 システムだけが 良 い 推 薦 システムとは 限 らない 59
ユーザ 満 足 度 の 観 点 に 基 づく 評 価 指 標 多 様 性 (Diversity) 安 定 性 (Stability) 被 覆 率 (Coverage) セレンディピティ (Serendipity) 60
推 薦 精 度 以 外 の 評 価 指 標 に 関 する 研 究 S. Castagnos et al.: Eye Tracking Product Recommenders' Usage. G. Adomavicius et al.: On the Stability of Recommendation Algorithms. M. Ge et al.: Beyond Accuracy: Evaluating Recommender Systems by Coverage and Serendipity. 61
推 薦 精 度 以 外 の 評 価 指 標 に 関 する 研 究 S. Castagnos et al.: Eye Tracking Product Recommenders' Usage. 62
多 様 性 (Diversity) 推 薦 リスト 内 類 似 度 に 基 づく 推 薦 リストがどの 程 度 多 様 なアイテムを 含 んでいるか 推 薦 リストA 推 薦 リストB 0.8 0.7 0.9 0.7 0.8 0.7 多 様 性 なし 0.1 0.2 0.1 0.2 0.3 0.1 多 様 性 あり ave. = 0.77 ave. = 0.17 63
多 様 性 (Diversity) 相 対 的 多 様 性 に 基 づく 注 目 アイテムに 対 し, 推 薦 リストがどの 程 度 多 様 であるか 注 目 アイテム 推 薦 リストA 推 薦 リストB 0.9 0.8 0.7 0.8 0.2 0.3 0.2 0.1 多 様 性 なし 多 様 性 あり 1 ave. = 0.2 1 ave. = 0.8 64
推 薦 精 度 以 外 の 評 価 指 標 に 関 する 研 究 G. Adomavicius et al.: On the Stability of Recommendation Algorithms. 65
安 定 性 (Stability) 推 薦 システムによる 嗜 好 予 測 がどの 程 度 一 貫 しているか Item1 Item2 Item3 Item4 Item5 Item6 Item7 Alice 4 2 1 Bob 4 2 1 3 5 5 1 Carol 4 2 1 5 3 5 1 Dave 4?? 4 4 5 5 Eve? 2? 4 4 5 5 66
安 定 性 (Stability) 推 薦 システムによる 嗜 好 予 測 がどの 程 度 一 貫 しているか Item1 Item2 Item3 Item4 Item5 Item6 Item7 Alice 4 2 1 4 4 5 1 Bob 4 2 1 3 5 5 1 Carol 4 2 1 5 3 5 1 Dave 4?? 4 4 5 5 Eve? 2? 4 4 5 5 67
安 定 性 (Stability) 推 薦 システムによる 嗜 好 予 測 がどの 程 度 一 貫 しているか Item1 Item2 Item3 Item4 Item5 Item6 Item7 Alice 4 2 1 4 4 5 1 5 Bob 4 2 1 3 5 5 1 Carol 4 2 1 5 3 5 1 Dave 4?? 4 4 5 5 Eve? 2? 4 4 5 5 新 しい 評 価 値 データが 入 る 前 と 後 とで 予 測 値 が 一 貫 しない 68
安 定 性 の 計 算 既 知 評 価 値 予 測 評 価 値 R 1 P 1 既 知 評 価 値 新 評 価 値 予 測 評 価 値 R 1 S R 2 = R 1 S P 2 = P 1 \S u i P u i P,, ui 1 2 69
推 薦 精 度 以 外 の 評 価 指 標 に 関 する 研 究 M. Ge et al.: Beyond Accuracy: Evaluating Recommender Systems by Coverage and Serendipity. 70
被 覆 率 (Coverage) 利 用 可 能 な 全 アイテムのうち, 推 薦 システムにより 推 薦 可 能 なアイテムの 割 合 推 薦 システムにより 予 測 可 能 なアイテム 集 合 Coverage I p I Item1 Item2 Item3 Item4 Item5 Alice 1 5 Bob 2 3 4 5 Carol 3 4 Dave 2 3 4 利 用 可 能 な アイテム 集 合 予 測 可 能 予 測 不 可 能 71
セレンディピティ(Serendipity) セレンディピティなアイテムは... ユーザの 手 では 発 見 できない,かつ 思 いがけないもの ユーザにとって 面 白 く, 価 値 があり, 有 用 であるもの 推 薦 システムによる 推 薦 集 合 (RS) 思 いがけないアイテム 集 合 UNEXP RS \ 有 用 性 u RS 0or1 i PM プリミティブな 推 薦 システムにより 推 薦 可 能 なアイテム 集 合 (PM) セレンディピティ SRDP N i 1 u RS / N i 72
第 2 章 まとめ ソーシャルネットワークに 基 づく 推 薦 システム (9 件 ) コンテキストアウェア 推 薦 システム (1 件 +CARS 8 件 ) グループベース 推 薦 システム (3 件 ) 推 薦 精 度 以 外 の 評 価 指 標 (4 件 ) 73
本 日 の 内 容 第 3 部 : RecSys 今 後 の 展 望 とおまけ 74
RecSys 2010 発 表 論 文 の 印 象 推 薦 手 法 技 術 的 に 高 度 なものではなくても, 既 存 技 術 を うまく 組 み 合 わせ, 新 しい 問 題 を 解 いている 既 存 課 題 である,cold start 問 題 に 強 い, データスパースネスに 強 い, という 点 を 主 張 する 論 文 が 多 い 評 価 実 験 実 用 場 面 を 踏 まえた, 様 々な 条 件 で 詳 細 な 実 験 を 行 っている 提 案 手 法 が 良 いという 評 価 だけではなく, どういう 場 面 で 有 効 かという 考 察 が 多 い 75
公 開 データセット MovieLens Data Sets http://www.grouplens.org/node/73 Dataset: DBLP http://kdl.cs.umass.edu/data/dblp/dblp info.html Epinions Dataset http://alchemy.cs.washington.edu/data/epinions/ Flixster Data Set http://www.sfu.ca/~sja25/datasets/ 76
今 後 の 展 望 種 々のデータの 取 得 がますます 容 易 に ユーザ 生 成 コンテンツ ソーシャルネットワーク(SNSベースの 推 薦 ) コンテキストデータ(コンテキストアウェア 推 薦 ) 推 薦 システム 利 用 形 態 が 多 様 化 個 人 からグループへ(グループベース 推 薦 ) 一 方 向 から 双 方 向 へ( 相 互 推 薦 ) 既 存 の 課 題 への 取 り 組 み cold start 問 題,データスパースネス 問 題 セレンディピティの 向 上 77
本 日 のまとめ 第 1 部 : RecSys 2010 概 要 第 2 部 : RecSys 2010 研 究 動 向 第 3 部 : RecSys 今 後 の 展 望 とおまけ 78