Recsys2014の発表から現在のRecommend Systemの問題点を読み取る

集合知プログラミング

Recsys 2014 Tutorial - The Recommender Problem Revisited

Recsys 2014 Tutorial - The Recommender Problem Revisited
仕事でRecommenderに関わっているのでRecsys2014の最初の発表を読んで現在の問題点を再確認したいという気持ちで、内容を起こしてみます。途中に出てくる数式の理解および書き写しが大変なので、概要だけ書きます。また意味を理解するためには「機械学習の手法」と「Recommend」に対する知識をそれなりに必要とされます。

The Recommender Problem

• Recommendは古くから"過去の行動履歴"、"他のUserとの関係性"、"アイテムの類似度"、"Context"に基づいてどのようにUserがアイテムを好むかを自動的に予測する便利な関数を作る事である。
• RecommendationはDataを基に前処理、モデルの学習、テストおよびValidation評価をする一般的なデータマイニング問題としてみなすことが可能。
• 機械学習以外の側面として、UserInterface、Systemの要件定義、セレンディピティ、多様性、気づき、説明などの要素がある。
• セレンディピティは直接求められていないものを探す。Userが既に知っているアイテムを紹介してはいけず、Userを興味に近しい領域に拡張させる
• 様々なカテゴリジャンルのアイテムを表示する事が多様性と気づきである(意訳)

Collaborative Filterling (CF) Traditional Methods

• 協調フィルタリングには似ているUserベースでの予測をするものと(Personalized)、全てのUserの平均でのやり方がある(Not Personalized)。
• 手頃な手法でRecommendを作ることは簡単だが精度を改善することは難しい。手頃な手法と精度の間にはビジネス価値に大きな差がある。
• User-Baseの協調フィルタリングはターゲットしたいアクティブUserを見つけて、近似関数によりUserを識別し、似ているUserが好むアイテムを見つけて、予測をして、TopNのアイテムをRecommendする。
• Item-Baseの協調フィルタリングはターゲットしたいUserが持っているアイテムを探し、他のUserが過去に持っているアイテムのみを使ってどれほど似ているかを計算し、最も似ているk個を選択しRecommendする。
• ほとんどの場合良い結果が期待される。次のことにできれば挑戦したい。user/itemの相互作用は1%以下なのでDataがsparseになる。NNはUserとアイテムの両面での数を多く必要とする。

Model-Based Collaborative Filterling

• Memory-Basedの手法は予測のために全てのUser-Itemののデータベースを利用する。またNNのような統計学技術を必要とする。
• Model-Basedの手法は最初にUserのModelを作成する。例えばBayesian Network、Clustering、Rule-base approace、Classification、Regression、LDA等。
• Netfilix PrizeでのModel-Basedから学んだことはとても高い精度であり、改善の精度が10%あったこと。
• 2007年のPrizeではTop2のアルゴリズムがSVD(RMSE:0.8914)、RBM(RMSE:0.8990)であった。Lnear BlendはRMSE:0.88であった。※ SVD(Singular Value Decomposition)、RBM(Restricted Boltzmann Machine)
• 使用中のModelもSVD++とRBMの両方を使用したアンサンブル学習である。期待される改善にエンジニアリングの努力の価値はないので、他の問題に焦点を当てている。

Clustering

• UserのClusterを行い、それぞれのClusterに対して物理参照を計算する。UserはClusterのレベルに応じたrecommendationを受け取る。
• LSH(locality-sensitive Hashing)は高次元の似ているアイテムをグルーピングするHashing関数。主なアプリケーションはNN(Nearest-neighbors)
• その他の興味深いClustering手法、k-means、affinity propagation、spectral clustering、LDA、Non-parametric Bayesian Clustering。

Association Rules & Classifiers

• 過去の購入記録は関連するアイテムとして解釈される。Recommendされる内容は自信をもって薦めることができる最小のものに限られる。実装と実行を早くしたい。
• Classifiersは正例、負例を使ってモデルを作成する。アイテムの特徴ベクトル、顧客の趣味嗜好、アイテム間の関係がinputに用いられる。例としてLogistic Regression、Bayesian Networks、SVM、決定木等。
• Classifiersは協調フィルタリング、コンテンツベースフィルタリングの両方で使われる。良い点は応用が効き、他の手法と連結して精度改善することが可能。悪い点は関連する訓練データが必要、オーバーフィットするので正則化が必要。

Limitaion of Collaborative Filtering

• Cold Start : 十分な他のUserが既にシステムの中に存在し、新しいアイテムも必要とする。
• Popularity Bias : ユニークな興味に対してrecommendするのが難しい。人気商品が推薦される傾向にあり、Tailに存在するアイテムが出なくなる。

Content-Based Recommendation(CB)

• WebPageやネットニュースの記述などのText-Basedの商品、記述されたアイテムの特徴(keyword等)によってrecommendする方法などがある。
• User Modelは似ている方法で構成される。User ModelはNeural NetworkやNaive Bayesなどの技術に基づいて分類される。

Pros/Cons CB Approach

• CBの良い点 : 他のUserデータを必要としない、Cold-StartやSparsityの問題が無い、ユニークな趣味嗜好のUserに対してアプローチや不人気商品に対してアプローチできる、コンテンツの特徴をリストすることで説明を強化できる。
• CBの悪い点 : コンテンツが測定可能な特徴としてencodingされなければならない、Userはコンテンツの特徴の学習可能な機能として表現される、serendipityの改良は難しい、簡単にオーバーフィットする。

Hybrid Approaches Hybridzation Methods

• Hybridさせた方が精度が良さそう(意訳)
• weighted、Switching、Mixed、Feature Combination、Cascade、Feature augmentation、Meta-levelなどの複合手法がある。(詳細は省略)

Ranking

• Recommendationはソートされたアイテムリストとして表現されている。RecommendationはRanking問題として理解されなければならない。人気は明白なベースラインである。いろいろな特徴が加えることが可能。
• RMSEは使用できない。
• 例として2つの特徴(人気と予測Rate)を利用した線形モデルをRankingとするものがある。

Learning to rank

• 機械学習の問題 : ゴールは訓練データからRanking Modelを構築すること。
• 訓練データは完全な順序もしくは2値判断(関連する、しない)である可能性がある。
• Rankの結果は数学的なスコアによって削減されたアイテムの順序である。
• Rankingを学習することはPersonalizationの重要な要素となる。
• classification問題の一般的なものとして扱うことができる。
• metricsを利用したrankingの測定の質として、Normalized Discounted Cumulative Gain、Mean Reciprocal Rank(MRR)、Fraction of Concordant Pairs(FCP)などがある。
• これらの測定に対して直接機械が学習したモデルを最適化させることは難しいが、最近の研究されたモデルは直接最適化させている。
• アプローチとしてPointwise,Pairwiseがある。
• Pointwise : 個人に関連するかどうかを定義した損失関数を最小化する、回帰や分類に基づいたRanking Score、通常の回帰/Logistic回帰/SVM/GBDTなどがある。
• Pairwise : pair-wiseの選択に基づいた損失関数、Goalはランキング内の転置数を最小化する、Ranking問題は2値分類問題に変換される、RankSVM/RankBoost/RankNet/Frank
• その他にListwiseという手法がある。(詳細は省略)

Similarity as Recommendation

• Graph-Based Similarityの例としてSimRankというものがある。
• Similarityは異なる次元を参照することが可能。metadataやタグの類似、再生行動履歴の類似、評価履歴の類似等
• それらをアンサンブルで結合する。重み付けは既存のレスポンスにより回帰から学習される。もしくはMABが調査/開発する。

Deep Learning for Recommendation

• SpotifyはRecurrent Networkを利用してる

Recurrent Neural Networks for Collaborative Filtering | Erik Bernhardsson

• その他のDeep LearningによるContents-BaseのRecommendationは以下のURLから確認することができる。

Recommending music on Spotify with deep learning – Sander Dieleman

• 少しのCF情報が適用な時にColdStartな新しいタイトルのアプリケーション。
• audio信号を入力としたmel-spectrogramを利用する。
• 40の見えない要素を予測するためにdeep neural networkを学習する。
• Networkの構成は4つの畳み込みlayerをつくる。(意味が良くわかりませんでした)

Social and Trust-based Recommenders

• 近接するSocialのuserに人気なアイテムを推薦する。近接するSocail = 信頼である。
• AlgorithmとしてAdvogato/Appleseed/MoleTrust/TidalTrustなどがある。
• 他のSocialの利用として友人関係は異なる手法のCFに与えることができる。user-userの類似度をSocial networkの情報に置き換えるとか、Social Connectionを機械学習のオブジェクト的な正則化としての関数で使う等。
• Userを個人属性によってカテゴリ化、Demographicのクラスに基づいた推薦をすることが目的。
• Demographicのグループはmarketing reserchからできる。Demographicの技術は人と人の関連性を形成する。

Page Optimization

• Pageの構成を考える。Userがより良く見る部分に良いコンテンツを配置したい。
• 正確度と多様性、新しい発見と継続、深さとカバー率、新鮮さと安定性、推薦とタスクなどの比較がある。
• コンテンツを一緒に配置するためには異なる要素の結合が必要。Navigational / Attention Model、Personalized Relevance Model、Diversity Model

Tensor Factorization & Factorization Machines

• N-Dimensional Model(User,Item,Time等)
• FM(Factorization Machines)

MAB Explore/Exploit

• Personalization Algorithmの手法を構築するときに重要な問題の一つはトレードオフをどのように扱うか。
• Exploitation : Userの今の状況を知っていることでのマネタイズ。Exploration : Userについてもっと知る機会として相互作用を利用する事。
• このようなトレードオフに対応するために通知され最適な戦略を必要とする。Solution : 手頃な候補のセットを選択し、それらの情報を集めるために十分である事をuserに見せる。
• Multi-Armed Bandits 可能な戦略や候補をあたえられた時、ポテンシャルを最大限に良くするarmを選択する。(この辺はBanditsアルゴリズムを勉強しないとよく分からない)
• 基本的なstrategyはE - Greedyであり、Recommender Systemに適用するためにはarmを選択することは、アイテムの選択とアルゴリズムの選択を意味する。
• よりよいstrategyは平均だけでは無く、分散も考慮している。Upper Confidence Bound, Thompson Sampling