推薦システムの基本的な評価指標について整理してみた

t2sy

2017.6.16

Topics

再現率と適合率
ランク付けされた推薦の評価指標
推薦システムの評価指標
MAPとGMAPを比較してみる
おわりに

はじめまして、データサイエンスチームの t2sy です。
私が所属しているデータサイエンスチームでは、Python・Rなどを用いてデータ分析を行っています。また、Apache Sparkを用いた機械学習基盤を開発しており、中でも推薦システムでは、購買などの周期性を考慮した行列分解手法による推薦アルゴリズムを実装した新機能を近日リリース予定です。
この記事では、推薦システムの開発で用いている以下の基本的な評価指標についてご紹介した上で、MAP と GMAP の簡単な比較をご紹介します。推薦の多様性、セレンディピティやABテストについてはこの記事では触れません。

Recall
Precision
F-measure
AP
nDCG
MAP
GMAP

再現率と適合率

情報推薦と情報検索には類似性があり、情報検索における情報フィルタリングが一種の情報推薦とも考えることができます。従って、推薦システムの評価に再現率や適合率といった良く知られている評価指標を用いることができます。
適合文書の集合を A、システムが推薦した文書の集合を B とした場合、再現率 (Recall) と適合率 (Precision) は以下で表せます。
$Rec = \frac{|A \cap B|}{|A|}$
$Prec = \frac{|A \cap B|}{|B|}$
集合を図示してみるとより再現率と適合率の関係がイメージし易くなります。

推薦システムにおいて再現率は推薦漏れの少なさ、適合率は推薦誤りの少なさに対応します。
再現率と適合率は一般にトレードオフの関係にあり、総合的な判断をしたい場合には2つが統一された評価指標があると便利です。統一された指標には E-measure や F-measure があります。
F-measure は以下で表され、再現率と適合率のバランスのパラメータβ が 1 の場合に再現率と適合率の調和平均となります。これは F1 と呼ばれ広く知られています。
$F_\beta = \frac{ (\beta^2 + 1) Prec Rec}{\beta^2 Prec + Rec}$

ランク付けされた推薦の評価指標

再現率や適合率は順序を考慮しない評価指標で、ランク付けされた推薦を評価する場合はその順序性を考慮する必要があります。
順序性を考慮した代表的な評価指標として平均適合率 (Average Precision) があります。
ランク付けされた推薦において適合文書が見つかる度にその位置での適合率を求め、その算術平均を取った値が AP となります。R は適合文書の数です。
$AP = \frac{1}{R} \sum_{r=1}^{n} Prec(r) I(r)$
式中の I(r) は r位が適合文書の場合 1 、そうでない場合は 0 となる関数です。従って、適合文書の場合にのみ、その位置での適合率 Prec(r) を計算することに対応します。
平均適合率は単純に適合したか否かのみを考えるので二値適合性に基づく評価基準です。
より実際の推薦の評価では多くの場合、高く適合する高適合や部分的に一致する部分適合など適合性の度合いを考慮する多値適合性に基づく評価基準を用いるのが適切と考えられます。
nDCG (normalized Discounted Cumulated Gain) は多値適合性に基づく評価指標で、適合度に応じた価値を利得 (gain) として考え、ランクが下位になるほどその価値を下げる減損利得 (discounted gain) を導入し、その累積和を正規化した値です。
DCG (Discounted Cumulated Gain) は以下で表せます。g(r)はr位における利得です。
$DCG = \sum_{r=1}^{n} \frac{g(r)}{ \log_2 (r+1)}$
IDCG (Ideal DCG) を理想的推薦における減損利得の累積和としたとき、正規化された nDCG は以下となります。
$nDCG = \frac{DCG}{IDCG}$
上記以外の多値適合性に基づく評価指標に、平均適合率を拡張した Q-measure や GAP (Graded Average Precision) などがあります。

MAPとGMAPを比較してみる

Apache Spark には推薦システムや検索システムの評価指標として、org.apache.spark.mllib.evaluation.RankingMetrics に前述した precision や nDCG, MAP が実装されています。今回、MAP 実装に倣い GMAP を書いてみました。ε の値は 0.00001 としています。

lazy val geometricMeanAveragePrecision: Double = {
  val e = 0.00001
  val logAP = predictionAndLabels.map { case (pred, lab) =>
    val labSet = lab.toSet
    if (labSet.nonEmpty) {
      var i = 0
      var cnt = 0
      var precSum = 0.0
      val n = pred.length
      while (i < n) {
        if (labSet.contains(pred(i))) {
          cnt += 1
          precSum += cnt.toDouble / (i + 1)
        }
        i += 1
      }
      ln((precSum / labSet.size) + e)
    } else {
      ln(e)
    }
  }.mean()
  exp(logAP) - e
}

一部のユーザに極端に悪い推薦を返すような推薦システムをGMAPが検出できるかを、2つの簡単な人工データに対して MAP と GMAP を比較することで確認してみます。
まず、ある推薦システム (M1) が以下のような10人のユーザに5つの推薦を提示し、その内1つから2つが適合文書である場合を考えます。
List の各要素はユーザを表し2つの Array から成る Tuple型となっています。左の Array がシステムが提示した推薦文書ID、右の Array が適合文書IDです。

val predictionsAndLabels = List(
  (Array("a", "h", "j", "l", "p" ), Array("a", "b", "c")),
  (Array("t", "b", "f", "h", "k" ), Array("a", "b", "c")),
  (Array("x", "b", "d", "c", "a" ), Array("a", "b", "c")),
  (Array("f", "b", "c", "d", "y" ), Array("d", "e", "f")),
  (Array("a", "b", "c", "d", "e" ), Array("d", "e", "f")),
  (Array("p", "e", "m", "n", "f" ), Array("d", "e", "f")),
  (Array("h", "i", "a", "c", "e" ), Array("g", "h", "i")),
  (Array("o", "i", "g", "h", "k" ), Array("g", "h", "i")),
  (Array("a", "g", "e", "v", "x" ), Array("g", "h", "i")),
  (Array("z", "j", "a", "s", "q" ), Array("j", "k", "l"))
)

次に、別の推薦システム (M2) では最後のユーザにだけ適合文書が1つも含まれていない推薦を提示したとします。

val badPredictionsAndLabels = List(
  (Array("a", "h", "j", "l", "p" ), Array("a", "b", "c")),
  (Array("t", "b", "f", "h", "k" ), Array("a", "b", "c")),
  (Array("x", "b", "d", "c", "a" ), Array("a", "b", "c")),
  (Array("f", "b", "c", "d", "y" ), Array("d", "e", "f")),
  (Array("a", "b", "c", "d", "e" ), Array("d", "e", "f")),
  (Array("p", "e", "m", "n", "f" ), Array("d", "e", "f")),
  (Array("h", "i", "a", "c", "e" ), Array("g", "h", "i")),
  (Array("o", "i", "g", "h", "k" ), Array("g", "h", "i")),
  (Array("a", "g", "e", "v", "x" ), Array("g", "h", "i")),
  (Array("z", "x", "c", "q", "p" ), Array("j", "k", "l")) // bad recommendation
)

M1、M2に対する MAP と GMAP は以下のようになりました。

	MAP	GMAP
M1	0.369	0.320
M2	0.352	0.121

M1の推薦結果に対して MAPが 0.369、GMAP 0.320 となりました。MAP に対して GMAP はやや低い値ですが大きくは変わらない値と言えそうです。
一方、M2の推薦結果に対しては MAP は 0.352、GMAP が 0.121 となりました。MAPが約0.02 低下したのに対して、GMAP は約0.20 と大きく低下したことから、GMAP は一部のユーザに極端に悪い推薦を提示する推薦システムの検出に向いておりシステムの性能改善に役立つと考えられます。

おわりに

今回は推薦システムにおける基本的な評価指標をご紹介し、その中でロバストな推薦システムの開発に役立つ GMAP を Apache Spark に実装し簡単なデータで比較を行いました。
推薦システムの開発では、目指している方向性に対し適切な評価指標を用いて継続的にパラメータチューニングなどの改善を行うことが重要であると思います。
今回、紹介しきれなかった推薦システムの評価に関する内容として、統計的検定による2つ以上のシステム比較や、テストコレクションを用いた評価があります。
本記事を書くにあたり参考にさせて頂いた情報アクセス評価方法論では、これらの内容にも触れていますので興味を持たれた方は是非手にとっていただければと思います。

参考文献
1. Extending Average Precision to Graded Relevance Judgments
2. A Theoretical Analysis of NDCG Ranking Measures
3. Inferred AP : Estimating Average Precision with Incomplete Judgments
4. On GMAP: and other transformations.