RecSys'21の論文紹介 - Towards Unified Metrics for Accuracy and Diversity for Recommender Systems

December 23, 2021

この記事は情報検索・検索技術 Advent Calendar 2021の23日目の記事です．

この記事では今年のRecSys¹で発表された「Towards Unified Metrics for Accuracy and Diversity for Recommender Systems」² という論文について紹介します．推薦タスクにおける精度と多様性を同時に測る統一的な指標を提案している論文で，実際の推薦システムでも最近は推薦の多様性の重要視されてきていると思いますが，そういったことを考えるのにヒントになるかもしれません．なお，記事中の図は論文からの引用になります．

サマリー

推薦システムのための精度と多様性を同時に評価するための指標αβ-nDCGを提案しています．
指標を提案するにあたって，まず推薦システムにおける評価指標が満たすべき公理を考え，提案指標や先行研究で提案されてきた指標がそれらの公理を満たしているかどうかを検証しました．検証の結果，提案指標のみがすべての公理を満たすことを示しました．
推薦タスクの実験で用いられるデータセットを使い，提案指標が指標として望ましい性質を有していることを実験においても確認しました．

研究背景

上位n件の推薦タスクにおける手法をオフラインで評価するとき，PrecisionやRecall, nDCGなどといった，情報検索の分野で培われた評価指標が今もよく使われます．しかし，最近はこういった指標だけで手法の良し悪しを評価するのではなく，セレンディピティや新規性，多様性といった，適合・非適合以外の観点で手法を評価するニーズが出てきています．

こうした背景から，多様性などを測るための指標がこれまで提案されてはきましたが，研究者は精度と多様性，どちらを最適化するかというジレンマに陥っていました．そこで，この研究では精度と多様性の評価を統一した指標を提案することで，ジレンマの解決を試みています．

提案指標

著者らが提案する評価指標はαβ-nDCGというもので，精度と多様性を同時にいい塩梅に評価できる指標です．論文の内容を事細かに説明しているととても長くなってしまうので，今回はまず指標の概要を掴んでもらうことを目的に，詳細な議論は飛ばし，一部自分なりの解釈で補足を行いつつ提案指標の説明をしていきたいと思います．

まずは提案指標の名称の中にある，nDCGという指標についての振り返りから入ります．

nDCG

nDCGはnormalized Discounted Cumulative Gainの略で，検索や推薦結果のランキングを評価するための指標です．上位K件におけるnDCGを数式にすると式(1)のようになります．

nDCG@K = \frac{DCG@K}{IDCG@K} \tag{1}

DCGをIDCG(Ideal DCG)，つまり理想的なDCGで割って正規化しています．DCGは式(2)で定義されます．

DCG@K = \sum_{k=1}^K \frac{G(u, i)}{\log_2 (k+1)} \tag{2}

$G(u,i)$ はユーザ $u$ に対してアイテム $i$ を提示したときの利得になります． DCGはなるべく利得の高いアイテムを上位に表示しようという意図を表しています． $G$ はたとえばAmazonのレビューのような，明示的フィードバックがある場合はその評価値を，クリックしたかどうかといった暗黙的フィードバックの場合は0,1のバイナリ値を利得として設定したりします．この論文では明示的フィードバックがある場合の推薦タスクを考え，ユーザ $u$ がアイテム $i$ と関連しているか(= ユーザがアイテムに興味があるか)どうかの確率 $P$ を利得とします(式(3))．

G(u,i) = P(R=1,u,i) \tag{3}

提案指標のαβ-nDCGはざっくり言うと，この確率 $P$ の中に推薦結果の多様性を入れ込もうというものです．そこで，次にαβ-nDCGのベースとなっているα-nDCG³という，検索(not 推薦)における精度と多様性を考慮した指標について説明します．

α-nDCG

α-nDCGでは多様性を考えるのに，まずアイテムのアスペクト $a$ という，アイテムを表現する何らかのカテゴリデータを考えます．映画の例だと $a_{action},a_{comedy},a_{drama},\dots,a_{romance}$ のようなジャンルがアスペクトとして考えられます． α-nDCGでは $P$ は式(4)のように定義されます．

P(R=1,u,i) = 1 - \sum_{\phi=1}^c {1 - P(a_{\phi} \in u) \times P(a_{\phi} \in i)} \tag{4}

$c$ はアスペクトの総数， $P(a_{\phi} \in u)$ はユーザ $u$ がアスペクト $a_{\phi}$ に興味がある確率を表します．要するにユーザ $u$ とアイテム $i$ のアスペクトが被っていれば被っているほど， $P$ が大きくなります．

式(4)をベースに，続いてαβ-nDCGを考えていきます．

αβ-nDCG

推薦システムではアイテムのアスペクトの強弱の程度はユーザの興味関心に影響を受けるよね，という考えから，αβ-nDCGでは式(4)の $P(a_{\phi} \in i)$ を $P(a_{\phi}|u,i)$ に変えます(式(5))．たとえば同じホラー映画でも，ユーザによってホラー映画がどの程度好きかは異なるので， $P(a_{horror}|u_1,i_1)=1$ になったり $P(a_{horror}|u_2,i_1)=0.5$ になったりすることを考えようということです．

P(R=1,u,i) = 1 - \sum_{\phi=1}^c {1 - P(a_{\phi}|u,i) \times P(a_{\phi}|u)} \tag{5}

$P(a_{\phi}|u,i)$ はアイテム $i$ がアスペクト $a_{\phi}$ においてユーザ $u$ の興味を満足させる確率と解釈でき，式(6)のように定義されます．

P(a_{\phi}|u,i) = \left\{ \begin{array}{ll} 0 & (a_{\phi} \notin i) \\ \alpha(u,i) & (\nexists r_{u,i} \text{ and } a_{\phi} \in i) \\ \beta(u,r_{u,i}) & (\exists r_{u,i} \text{ and } a_{\phi} \in i) \\ \end{array} \right. \tag{6}

$\alpha(u,i)$ はユーザの評価がないときの確率で，評価がない場合に単に観測していないだけか，もしくは本当に適合していないか分からないので，その曖昧さを表現する関数です． $\beta(u,r_{u,i})$ はユーザの評価に対する確信度合いを表しています． $\alpha$ や $\beta$ の定義は色々考えられますが，論文ではいったん定数か，パーソナライズしないシンプルな式を定義としています．

次に，冗長性と新規性を考慮するために，ポジション $k$ の時点でユーザはまだアスペクト $a_{\phi}$ を持つアイテムを探したいと思っているかどうかを推定します．ポジション $k$ までのランキングを $S = \vec{i}[0, \dots, k-1]$ とすると，推定式は式(7)のようになります．

P(a_{\phi}|u,S) = P(a_{\phi}|u) \prod_{i \in S} {1 - P(a_{\phi}|u,i)} \tag{7}

ポジション $k$ より上位の検索結果でアスペクト $a_{\phi}$ についてユーザが満足している場合， $P(a_{\phi}|u,S)$ は小さくなります． αβ-nDCGは式(5)の $P(a_{\phi}|u)$ を $P(a_{\phi}|u,S)$ に置き換えて，これを利得として用います(式(8))．

P(R_k=1,u,i,S) = 1 - \sum_{\phi=1}^c {1 - P(a_{\phi}|u,i) \times P(a_{\phi}|u,S)} \tag{8}

以上がαβ-nDCGの骨子になります．ここから各関数の推定をどのように行うかなどの議論はあるのですが，今回はその辺は割愛して，推薦評価の指標として満たすべき公理を満たしているかどうかの分析に移ります．

公理的分析

ここでは精度と多様性を同時に測る評価指標が満たすべき公理を考え，提案指標であるαβ-nDCGや先行研究の指標がこれらの公理を満たすかどうかの分析を行います．論文で述べられている公理は以下の8つになります．ここでは大まかな公理の意味だけを載せ，厳密な定義は論文に譲りますが，いずれも納得できる公理かと思います．

Priority Inside Aspect: 2つのアイテムのアスペクトに違いがない場合，評価の高いアイテムが上位にランクされている方が良い
Deepness Inside Aspect: アイテムのアスペクトに違いがない場合，ランキングの上の方でアイテムをスワップする方が，ランキングの下の方でアイテムをスワップするよりも推薦の質は下がる
Non Priority on Saturated Aspects: ユーザの興味が充足されたアスペクトを持つアイテムの優先順位は下がる
Top Heaviness Threshold: トップにある関連アイテムを見るほうが，ランキングn位以降の関連アイテムすべてを見るより良い，という閾値nが存在する
Top Heaviness Threshold Complementary: トップにある関連アイテムを見るより，ランキングm位以降の関連アイテムすべてを見る方が良い，という閾値mが存在する
Aspect Relevance: アイテムに対するレーティングが同じ場合，ユーザがより興味のあるアスペクトのアイテムを提示する方が良い
Prefer More Aspect Contribution: ユーザの興味がより充足していないアスペクトを持つアイテムを提示する方が良い
Missing Over Non-Relevant: ユーザが非適合を表明しているアイテムより，ユーザの興味が充足されていないアスペクトを持っていて，かつ未観測のアイテムを提示する方が良い

αβ-nDCGはこれらの公理すべてを満たすように作られており，先行研究で提案されてきたその他の指標はいずれもはすべては満たすことはできてません(結果は割愛)．このことから，αβ-nDCGは適合性と多様性を同時に測る評価指標として望ましい性質を有していると言えます．

実験

公理的分析により提案指標は望ましい性質を持っていることが分かりましたが，実際のデータセットを使ったときにどのように振る舞うかは自明ではありません．そこで，ここでは協調フィルタリングのデータセット(MovieLens)を用いて，ランキングを変更したときの評価指標の振る舞いをシミュレートします．実験は3種類行われていますが，そのうち1つである順位相関の実験について紹介します．

順位相関の実験

前章で定義した公理から，データセットからユーザに対する理想のランキングというのを計算できます．理想のランキングを出発地点に，ランキングのアイテムを交換していくと，ランキングのスコアは下がっていくはずです．このとき，評価指標の値もランキングと同様に下がっていけば，その評価指標はランキングのスコアを表す良い指標と言えます．そこで，理想のランキングのアイテムを交換していき，ランキングのスコアの低下と評価指標の低下に相関があるかを見ます．

交換の方法は次の3通りを試してみます．

ランクが上のアイテムと下のアイテムを交換する．最初に1番上のアイテムと1番下のアイテムを交換，次に2番目同士のアイテムを交換，というように続ける．
冗長なアスペクトのアイテムに交換する．ユーザの興味が充足されているアスペクトを持つアイテムに交換していく．
ユーザの最も興味のあるアスペクトではなく，他のアスペクトを持つアイテムから提示していくようにアイテムを交換する．

図1が実際のランキングのスコアと，各指標との相関係数を表しています．図中の青が提案指標であるαβ-nDCGで，αβ-nDCGが唯一，すべての実験においてランキングのスコアと高い相関を示しています．

図1: 実験結果．左が実験1，中央が実験2，右が実験3の結果．

公理的分析ではαβ-nDCGが適合性と多様性を同時に測る評価指標として望ましい性質を有していると述べましたが，実験によってこの考えがサポートされる形となりました．他にも2つ実験が行われていますが，興味のある方は是非論文を読んでみてください．

感想

以上，駆け足でしたが論文紹介でした．

普段自分は推薦のモデル自体を考えることが多いので，評価指標の提案という主旨の論文は新鮮で面白かったです．と同時に，次のようなことも思いました．

良い推薦は良いゴールから: 実務では時間や仕様の制約などから，既成の評価指標の最適化をゴールとして選択することが多いかもしれませんが，この論文のように最適化すべきものは何か？という点からタスクを考え直すことが大事だなと思いました．
評価指標は実際の価値の代替でしかない: 論文中の実験にあったように，実際のランキングの価値と評価指標の値は必ずしも相関するとは限りません．自分たちが計測しているのはあくまで価値を代替した尺度であり，真の価値との差があることを認識しつつ，その差を埋めていけるように努力する必要があるなと思いました．

推薦システムに関する国際会議( https://recsys.acm.org/ )↩
本記事執筆時点ではオープンアクセスとなっており，誰でも読むことができます↩
https://dl.acm.org/doi/abs/10.1145/1390334.1390446 ↩