今回は、KDD 2020でResearch Best Paper Awardに選ばれた「On Sampled Metrics for Item Recommendation」という論文を読んだので、その内容を紹介します。この論文は、Google Researchに所属するWalid KricheneさんとSteffen Rendleさんによって執筆されました。二人とも推薦システムに関する多くの論文を執筆している方で、Streffen Rendleさんが2010年に提案した「Factorization Machines」を使ったことがある方も多いと思います。
本記事は、以下の目次に従って紹介していきます。
- Introduction
- Evaluating Item Recommendation
- Metrics
- Sampled Metrics
- Corrected Metrics
- Experiments
- Suggestions and Conclusion
1. Introduction
推薦システムでは、各ユーザに対して数万件のアイテムをランク付けする必要があります。そのため、ユーザ数や推薦候補となるアイテム (動画配信サービスにおけるコンテンツやECサイトにおける商品など)が多いサービスでは組み合わせが膨大となり多くの計算リソースが必要となります。しかし、実際のサービス上でユーザの目に触れるアイテム数は上位数件から数十件とかなり限定的です。このような特性を考慮して、機械学習モデルの評価・比較時には、ランキングのトップに重きをおいた評価指標が用いられています。最近の研究や社会実装の例では、ネガティブサンプリングを行うことでより小さなデータセット (Sampled Dataset)を作成し、モデルの評価を行うことで計算量を削減することが一般的となってきています。
本論文では、ランキングのトップに重きをおいた評価指標では、Sampled Datasetでの評価結果とExact Dataset (サンプリング前の全データ)での評価結果の間で一貫性が保たれないことを数式と実験の両方から示しました。また、どうしてもサンプリングを行わなくてはならない場合にバイアスを低減するためのCorrected Metricsを提案し、その性能を実験で示しています。
2. Evaluating Item Recommendation
本論文では、図1の定義に従って議論が進められます。各定義をもう少し具体的に確認していきます。まず、nは推薦対象となるアイテム数を表します。A (algorithm)は各種レコメンドアルゴリズムを表し、x (instance)はAで利用するユーザ情報やアイテム情報のような特徴量を表します。R(A, x)は、特徴量xの用いてアルゴリズムAを適用した場合に、アイテム集合nの中から関連するアイテムを返す関数を表します。
M (Metrics)は、R(A, x)で返された関連アイテムの集合から、スカラーの評価指標を計算します。実際の実験では、複数のxが存在し、その平均的な評価を行うことが多いと思います。そこで、xの集合を表すDを導入して、図1の下式でアルゴリズムの平均的な評価を一般化しています。
3. Metrics
3.1 評価指標の定義
ここで、rは推薦アイテムの集合内 (n)でのindexを表します。例えば、図1の例ではr=3, 5となります。評価指標の右下に記載されてる記号kはtop kを表します。例えば、Recall@kの場合は上位k件におけるRecallのスコアで定義されます。
レコメンドシステムの評価指標としては、AUC、Precision、Recall、Averave Precision、NDCGなどを用いることが多いと思います。本論文では、問題をより簡単に扱うために|R|=1、つまり推薦システムが関連があると予測するアイテム数を1つに絞った場合について考えます。そうすると、各種評価指標は、図2のようにより単純な形で表現できます。ここで、δ(condition)はcondition=Trueの時に1を、condition=Falseの時に0を返す関数を表します。
今回紹介したもの以外にも、いくつか評価指標が存在します。しかし、基本的に|R|=1で単純化した場合においては、今回の指標と同義になります。例えば、Reciprocal RankはAP、Hit RationはRecall、AccuracyはRecall@1とPrecision@1に対応します。
3.2 関連アイテムの位置rと評価指標の関係
図3は、関連アイテムのランクrによって各種評価指標がどのようなスコアを返すかをグラフで表したものです。右図は、左図のr=100までを拡大した図になります。グラフから、Average Precision、NDCS、Recall、Precisionはランキングのトップに重きをおいた指標であることがわかります。実際にr=1からr=2へのスコアの変化量と、r=2000からr=2001へのスコアの変化量を見るとランクとしては同様に一つ下がっただけですが、スコアの変化量は大きく異なります。また、RecallやPrecisionではkの値がカットオフのような働きをしていることが確認できます。一方で、AUCは他の指標と異なる振る舞いをしています。AUCはrに対して線形の関係があることが確認できます。つまり、r=1からr=2へのスコアの変化量と、r=2000からr=2001へのスコアの変化量が等しいことを示しています。
3.3 Toy Example
Toy Exampleでは、3つのレコメンドシステムを例に各評価指標がどのようなスコアを返し、どのレコメンドシステムが優れてると判断されるのかを確認しています。Toy Exampleではインスタンス数が5の場合 (|D|=5)について考えています。まず、各レコメンドシステムがどのようなアルゴリズムでランキングを生成するかを示します。
・Recommender A：全てのインスタンスに対して100を返すアルゴリズム
・Recommender B：2つのインスタンスに対して40を返し、3つのインスタンスは40より悪いランクを返すようなアルゴリズム
・Recommender C：1つのインスタンスに対して2を返し、4つのインスタンスは2より悪いランクを返すようなアルゴリズム
表1の結果を確認すると、AUCではRecommender Aが、その他の指標ではRecommender Cが優れたアルゴリズムだと判定されました。AUCは、図3で確認したようにランキングに対して線形にスコアが変化します。そのため、満遍なく上位のランクを推定できているRecommneder Aがもっとも高いスコアとなっています。一方で、その他の指標はランキングのトップに重きをおいた指標となっています。そのため、Recommender Cのように一つだけでもかなり高いランクを推定することができていれば、平均のスコアは高くなる傾向があります。
4. Sampled Metrics
4.1 Sampled Metricsの一貫性
Introductionでも述べたように、レコメンドシステムで利用するデータセットはとても膨大であることが多いです (nがかなり大きい)。加えて、レコメンド対象となるユーザの集合などを表すinstanceの集合 (D)も大きな値を取ることが多いため、ランキングのためにスコア付けする必要があるアイテム数はn×Dとなり、とても計算コストがかかります。
しかし、レコメンドの問題設定では少数の関連アイテムと多数の関連のないアイテムに分類されます。そこで、多数の関連のないアイテムからランダムにサンプリングすることでデータセット全体のサイズを小さくするネガティブサンプリングが一般的に用いられています。本論文では、ネガティブサンプリングを行って得られた関連のないアイテムの数をmと表します。
ネガティブサンプリングによって得られたデータセットでアルゴリズムを評価した際には、図4に記載されている関係性が満たされていることが期待されます。つまり、サンプリングの有無によらず評価が一致することが求められています。
4.2 Toy ExampleにSampled Metricsを適用
表2は、Toy Exampleで紹介した各アルゴリズムの優劣がSampled Metricsでも保たれるかを確認した結果です。各指標は、m=99とし1000回試行した時の平均と標準偏差を表しています。結果を確認するとAUC以外の指標では、結果の順序が保たれていないことがわかります。
図5から、ランキングのトップに重きをおいた指標では、mの値が小さい時により不安定になり、Exact Metricsと同様の順序を得るためには多くのサンプルが必要なことがわかります。一方でAUCはランクに対してスコアが線形の関係性なので、mに依存せずExact Metricsと同様の結果となっています。
4.3 サンプリング後のランクの分布
この節では、Sampled Metricsがどのような分布になるのかを見ていきます。まず、ここでも同様に問題を単純にするために|R^{~}|=1の場合について考えていきます。ここで、rは実際のアイテム集合内 (n)でのランクを表し、r^{~}はサンプリング後のアイテム集合 (m)でのランクを表します。ネガティブサンプリングによってrよりランクが高いアイテムが選ばれることもあるため、rとr^{~}は一致するとは限りません。図6の右上の例では、Exact Datasetでのランクrは3となりますが、Sampled Datasetでのランクr^{~}は2となります。
本論文では、ネガティブサンプリングは一様分布に従って行われるという仮定を置きます。すると、rより高いランクのアイテムが選ばれる確率は、図7の左下の式で表せます。データセット作成時には、この試行をm回行うので二項分布を用いて図7の真ん中下の式で表せます。すると、Metricsを表す表記Mを用いて、Sampled Metricsの期待値は右下の式で表すことができます。
図7に各Sampled MetricsがSample Sizeによって、どのように変化するかを表しています。Eaxctは紫線で表されており、これに近づくほど評価結果に一貫性が保たれるようになります。個々のMetricsについては次の節で確認していきます。
4.4 Sampled Metricsの期待値
図8のようにAUCの定義式を変形すると、rの線形関数で表せることがわかります。またSampled Metricsの場合もr^{~}が二項分布に従う仮定を用いて式変形を行うとサンプリング前のAUCと一致することが確認できます。このことからも、AUCがConsistent Metricsであることがわかります。
RecallやPrecisionのようにある値 (今回の場合はk)を境にMetricsの分布が変化するようなCut-off Metricsについてみていきます。今回はRecallについてSampled Metricsがどのようになるか数式で確認していきますが、Precisionの場合も同様の手順で確認することができます。図9のように、Recallの期待値を計算するためにサンプルサイズmについて足し合わせています。しかし、kがcut-offの役割を果たし、k以上のindexについては全て0となります。そのため、累積分布関数 (cumulative distribution function, CDF)を用いて表すことができます。この結果からもわかるように、Cut-off MetricsではExact MetricsとSampled Metricsの値が一致しません。
次にAverage Precisionについてみていきます。Average Precisionでは、rの値によって2つの場合が考えられます。まず、r=1のときはネガティブサンプリングによってr^{~}のランクは変化せず常に1なので、Average PrecisionのSampled Metricsも常に1となります。r>1の場合は、p(j<r)>0つまりrより上位のサンプルが確率的に選ばれるため、rとr^{~}は一致しません。この場合のSampled Metricsの期待値は図10のようにAUCを用いて表せます。AUCに関する項が0.0に近い時Sampled MetricsはExact Metricsと近くなります。実際にはAUCは1.0に近づくのでAUCに関する項を0.0に近づけるためにはサンプルサイズmを大きくする必要があります。
最後にサンプルサイズが小さい場合 (m=1)について考えてみます。この場合は、ネガティブサンプリング後のデータセットには「関連のあるアイテム」と「関連のないアイテム」が一つづつ含まれている状態となります (r^{~}={1, 2})。そのため、Sampled Metricsの期待値は、図11の上式のように表せます。ここでサンプリングが一様分布に従って行われるという仮定を用いて、式変形をするとrの線形関数で表すことができます。このことから、m=1の時はMetricsによらずrの線形関数で表せ、Exact MetricsとSampled Metricsが一致することが確認できます。
5. Corrected Metrics
Sampled Metricsでは多くの場合にExact Metricsと一貫性のある結果を得られないことをToy Exampleと数式から確認しました。この章では、ネガティブサンプリングを行ったデータセットを評価に用いるときにバイアスを低減する方法として2つのCorrected Metricsが提案されています。この章では、Corrected Metricsの定義を確認し、Experimentsの章で提案手法の検証結果を紹介します。
5.1 Unbiased Estimator of the Rank
Sampled Metricsでは、サンプリング後に観測されたランクr^{~}に対して、Exact Metricsを適用しています。しかし、多くの場合r^{~}は真のランクrを過小評価しており、そのことにより評価結果の一貫性が保たれなくなると考えられます。r~{~}は二項分布で表されるrの事前分布からサンプリングされた値に1を足したランクであるので、Exact Metricsに適用するバイアスが低減されたr^{~}を求めると図12の下式のように表せます。
5.2 Minimal Bias Estimator
もう一つのアプローチは、Sampled MetricsとExact Metricsの誤差を最小化するSampled Metrics (M^{~})を探すことでバイアスを低減する方法です。これは図13の上式のように表すことができ最小二乗問題として解くことができます。加えて、Bias-Variance Trade-offを調整するために正則化項を導入したものが図13の下式になります。この式では、一般的な正則化項と同様にγの値で調整することができます。
図14は提案された二つのCorrected Metricsがrの値によってどのように変化するかを表しています。左図はサンプルサイズm=100の場合を右図はm=10,000の場合を表しています。右図を見るとSampled Metrics (青線)よりCorrected Metricsの方がExact Metrics (ピンク線)に近い振る舞いをしていることがわかります。また、Corrected MetricsでもMinimal Bias Estimaterで推定したMetricsの方がよりExactに近くなっています。
6. Experiments
ここでは、Exact Metrics、Sampled Metrics、Corrected Metrics、それぞれが実際のデータセットでどのような結果になるかを確認します。今回の実験では以下の3点を確認することが目的になります。
- レコメンドアルゴリズムによって異なるランキングが生成されること
- Exact MetricsとSampled Metricsの間で結果に一貫性が保たれないこと
- Corrected Metricsを用いた評価結果は信用できるのか
6.1 実験条件
本論文は、以下の条件で実験を行っています。
・データセット：Movielens 1M
・Sample Size (m)：100
・Algorithm：
- recommender X：matrix factorization
- recommender Y：item-based collaborative filtering
- recommender Z：item-based collaborative filtering
本論文では、前述の通りExact MetricsとSampled Metricsで評価結果に一貫性が保たれないことを確認することが目的であり、Algorithmの優劣を評価することは目的ではないので個々のrecommenderの詳細については記述されていませんでした。一応論文のAppendixには補足がありました。
図15は各Recommenderがデータセットの各アイテムに対して付けたランクの分布を表しています。この結果を見るとRecommender Zは、3つの中でもっともランキング上位のfrequencyが高くなっていますが、多くのアイテムに対してかなり低いランクを付けている傾向があることがわかります。Recommender Xは、ランキング上位のfrequencyは他と比較して少し少ないですが、全体的に高いランクキング上位に偏った傾向がることがわかります。Recommender YはRecommender Xよりややランキング下位に偏った傾向があることがわかります。このことから実験の目的1の「レコメンドアルゴリズムによって異なるランキングが生成されること」が確認できました。
表3は、各Recommenderが生成したランキングに対して各評価指標を計算した結果を表しています。この結果を見るとExact Metricsで得られたRecommenderの優劣関係がSampled MetricsではAUC以外保たれていないことがわかります。Corrected Metricsの結果を確認するとExactとの優劣が保たれたいない場合もありますが、Sampled Metricsと比較してより妥当な結果を導けていることがわかります。このことから、実験の目的2「Exact MetricsとSampled Metricsの間で結果に一貫性が保たれないこと」と目的3「Corrected Metricsを用いた評価結果は信用できるのか」を確認することができました。
論文中では、より詳細な結果や他の検証方法についてまとめられているので、興味のある方はそちらを参照してください。
7. Suggestions and Conclusion
Recall、Precision、Average Precision、NDCGなどのようにランキングのトップに重きをおくような評価指標では、ネガティブサンプリングを行ったSampled Metricsを用いた場合にExact Metricsとの間に一貫性が保たれないことを数式と実験から示したました。そのため、Sampled Metricsを用いて意思決定をすることは間違った結果を招く可能性が高いため推奨しないと提案がありました。データセットのサイズがあまりにも大きい場合や他の理由で、どうしてもSampled Metricsを利用しなくてはならない場合は、本論文で提案されたCorrected Metricsで代用してバイアスを低減することが提案されています。
今回の論文では、サンプリングが一様分布に従っているなどの仮定を置き問題を単純化していました。しかし、実際の配信データなどを用いる時にはこのような仮定が満たされないことが多いため、より詳細な解析が求められます。この点については、論文内でもFuture Worksとして紹介されていました。
