要約する論文の基礎情報

URL : https://link.springer.com/article/10.1007/s13042-017-0762-9
keyword：レコメンデーション, 評価法のサーベイ, 有用性, 多様性, 新規性, 意外性, など
掲載雑誌/会議：International Journal of Machine Learning and Cybernetics volume 10, pages813–831 (2019)
引用数：76 @ 2021/9/27

要約者の自己紹介・補足・コメント

（株）つくばAI活用支援センターの内田匠です。

本要約における、私の補足・コメントはカッコつきクエスチョンマークで記載しています(補足コメントはこのように記載します？)。
また、本要約ではすべての内容を網羅しませんので、より詳しくは原著をご確認くださいませ。

それでは、以降から要約に入ります。

概要

レコメンデーションの評価法は大きくオンライン評価とオフライン評価に分かれるが、特にこのサーベイ研究ではオフライン評価を中心に扱い、Utility(有用性？), Novelity(新規性？), Diversity(多様性？), Unexpectedness(意外性？), Serendipity(？), Coverage(網羅性？)などのコンセプトごとにレコメンダーシステムの評価指標を整理している。

本サーベイが注意するように、これらのコンセプトはそれぞれの研究論文が用いた用語にすぎず、構造的な分類ではない。
そのため、本サーベイの3章"Categorization and relationships among the concepts"では、これらの関係性を整理し、分類方法を提案している。

古典的な推薦精度指標（RMSE, ROC)だけでレコメンダーシステムを評価すると、「ユーザーがすでに知っている人気アイテムばかりが推薦され、ユーザーの新しい発見には寄与しない」という問題は以前から指摘されていた。
この問題を解決するのが、Novelityなどの新しい評価方法のコンセプトであり、2019年までの段階で検討されている評価指標を把握する点で有用な論文と思われる。

評価指標の各コンセプト

Utility(有用性？)

本来はユーザーにとって役に立つことであり、多くの場合は推薦結果に対するユーザーの反応から計算される指標である。
以降ではそれを計算する関数を$\text{util}()$と表記する。

Error metrics(誤差指標？)

映画のレビュースコアログを用いたレコメンダーシステムなどでよく採用される指標。
ユーザー$u$への推薦リストを$R_u$とし、レコメンダーシステムのレビュースコアの推定値を$p(i)$、実際のレビュースコアを$r(i)$とした時、誤差指標MAE、RMSEは以下のように計算される。

\text{util}(R_u) = \text{MAE} = \frac{\sum_{i \in R_u} p(i) - r(i)}{|R_u|}

\operatorname{util}(R_u)=\text{RMSE}=\sqrt{\frac{\sum_{i \in R_u}(p(i)-r(i))^{2}}{|R_u|}}

Precision and Recall (推薦リスト内に正解アイテムが含まれているか？)

推薦リストにユーザーが利用したアイテムが含まれているかを評価する。
以下の$R_u$はユーザー$u$への推薦アイテムリスト、$C_u$が実際にユーザー$u$が利用したアイテム集合。

$$
\text { util }(R_u)=\text { precision }=\frac{|C_u \cap R_u|}{|R_u|}
$$

$$
\operatorname{util}(R_u)=\text { recall }=\frac{|C_u \cap R_u|}{|C_u|}
$$

この他にもROC曲線を定義して、その下側面積(AUC)で評価する場合もある。

Ranking score

推薦リストのアイテムの並び順を考慮した評価指標。
代表的なものとして、[breese;1998] (サーベイでは[Herlocker;2004]を引用しているが、[Herlocker;2004]はテキストブックであり、そこではRanking-scoreは[breese;1998]が提案したと引用していた。このため、本要約では[breese;1998]と書き換えている)が提案した下記の指標がある。
なお、下記の式では、$d$はレーティングスコアの中央値(median)、$\alpha$は推薦リストの順位に応じて重みを減少させる半減期(half-life)パラメータである。

$$
\operatorname{util}(R_u)=\operatorname{rank}(R_u)=\sum_{j=1}^{|R_{\mu}|} \frac{\max (r(i_j)-d, 0)}{2^{\frac{j-1}{\alpha-1}}}
$$

BREESE, J. S., HECKERMAN, D., AND KADIE, C. 1998. 
Empirical analysis of predictive algorithms for collaborative filtering. 
In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UAI-98). G. F. Cooper, and S. Moral, Eds. Morgan-Kaufmann, San Francisco, Calif.,43–52.

Utility-based metrics for online evaluation

これまではオフライン評価において提案されている Utility の評価指標を紹介してきたが、オンライン評価で用いられる指標について述べる。

Click-through-rate(CTR)は、推薦リストをユーザーがクリックした確率である。
最も一般的な指標であり、多くの研究でもこれが採用されている。

Retention(維持？)も、代表的なオンライン指標である。
そのアイテムの継続的な利用、あるいはシステム全体の継続的な利用を評価する。
いわゆるサブスクリプションモデルと呼ばれるビジネスモデルでは、月額課金などの料金プランをとることから、顧客の継続的な利用は重要な指標となる。
A/Bテストを用いて、AB間の差を評価することが多い。

Novelity(新規性？)

Novelityのコンセプトについて紹介する。
Novelityはユーザーが知らないアイテムを推薦する性能であり、以下の3つのレベルに分けられる。

Life level

そのユーザーがその人生を通して知らなかったアイテムを推薦する性能。
System level

そのレコメンダーシステムを搭載しているシステムログ内で、そのユーザーが利用したことがなかったアイテムを推薦する性能。
Recommendation list level

一つの推薦リスト内で、推薦されているアイテムの間に十分な違いがあること。

この要約では、上記の３つのlevelのうち、System levelのNovelity指標をいくつか紹介する。

System level のNovelty指標($\operatorname{nov}(R_u)$)として、[Nakatsuji;2010]は以下の指標を提案した。
以下の式では、$H_u$はユーザー$u$の過去に経験したアイテム集合、$d$を任意の距離関数、$\operatorname{class}(i)$はアイテム$i$が属する任意のクラスとする。

$$
\operatorname{nov}(R_u)=\sum_{i \in R_u} \min _{j \in H_u} d(\operatorname{class}(i), \operatorname{class}(j))
$$

Nakatsuji M, Fujiwara Y, Tanaka A et al (2010) 
Classical music for rock fans? Novel recommendations for expanding user interests. 
In: Proceedings of the 19th ACM international conference on Information and knowledge management (CIKM ‘10). ACM, New York, NY, USA, pp 949–958

多くのユーザーが利用している人気アイテムを推薦しないことをNovelityとして評価する指標も提案されています。
全レコードにおけるあるアイテム$i$が締める割合を${pop}_i$とした時、[Zhang;2012]は以下のようにNovelityを評価した。

$$
\operatorname{nov}(R_u)=\sum_{i \in R_u} \frac{\log_2 \operatorname{pop}(i)}{|R_u|}
$$

Zhang Y, Séaghdha D, Quercia D, Jambor T (2012) 
Auralist: introducing serendipity into music recommendation. 
In: WSDM’12. ACM, New York, NY, USA, pp 13–22

Diversity(多様性？)

一つの推薦リスト内のアイテムの多様性を評価する指標をDiversityと呼ぶ。
以降では、Diversity指標を$\operatorname{div}(R_u)$と表記する。

[Ziegler;2005]はアイテム$i,j$間の距離（非類似度）を$d(i,j)$として任意に定義(たとえば、映画のあらすじ文章ベクトルのコサイン距離など)した上で、Diversityを以下のように定義した。(原著の論文では、Intra-List Similarityと名付けている)

$$
\operatorname{div}(R_u)=\sum_{i \in R_u} \sum_{j \in R_u i \neq j} d(i, j)
$$

Ziegler C, McNee S, Konstan J, Lausen G (2005) 
Improving recommendation lists through topic diversification. 
In: WWW’05. ACM, New York, NY, USA, pp 22–32

さらに、同じ推薦リストに掲載されているアイテム$i,j$の順位をそれぞれ$k,l$とし、順位の近さ/遠さに応じた割引関数$disc(k)disc(l|k)$を導入する評価指標を[Vargas;2011]が提案している。
そこで提案された順位を考慮したDiversityの評価指標の一つが以下である。

$$
\operatorname{div}(R_u)=\sum_{k=1}^{|R_u|} \sum_{l=1}^{|R_u|} \operatorname{disc}(k) \operatorname{disc}(l \mid k) d(i_k, i_l)
;;;;;;;; \forall i_k \neq i_l
$$

Vargas S, Castells P (2011) 
Rank and relevance in novelty and diversity metrics for recommender systems. 
In: RecSys’11. ACM, New York, NY, USA, pp 109–116

Unexpectedness(意外性？)

Unexpectendnessは多くの論文で言及されているコンセプトですが、その明確な定義はありません。
ただ、明らかなアイテムの推薦を回避し、ユーザーに驚きをもたらすものです。
以降ではUnexpectendnessの計算関数を$\operatorname{unexp(R_u)}$と記載します。

Primitive recommender based unexpectedness

基本的な(Primitive)レコメンダーシステムをベースにして、それでは推薦できなかったアイテムを推薦する性能をUnexpectednessとして評価する考え方です。
例えば、[Ge;2010]では基本的なレコメンダーシステムによる推薦リストを${PM}_u$とした時、以下のようにそれに含まれないアイテムを評価する以下のモデルを提唱した。
なお、式の $\backslash$ は左の集合の要素のうち、右の集合に含まれない集合を表す。
(以下の式は原著の[Ge;2010]の記載内容に準拠)

$$
\mathrm{unexp}(R_u)=\mathrm{RS}_u \backslash \mathrm{PM}_u
$$

Ge M, Delgado-Battenfeld C, Jannach D (2010) 
Beyond accuracy: evaluating recommender systems by coverage and serendipity. 
In: Proceedings of the fourth ACM conference on recommender systems (RecSys ‘10). ACM, New York, NY, USA, pp 257–260

[Adamopoulos;2014]は上記の指標を拡張して、以下の式を提案した。
$E_u$はそのユーザーの過去に利用したアイテムなどの、そのユーザーにとって既知のアイテム集合である。
また${PM}$に添え字$u$がなくなっているのは、[Adamopoulos;2014]が$PM$に人気ランキングを採用したためである。
$U$はユーザー集合を表す。
(以下の式は原著の[Adamopoulos;2014]の記載内容に準拠)

$$
\mathrm{unexp}(R_u)=\sum_u \frac{|R S_u \backslash(E_u \cup P M)|}{|U|}
$$

Adamopoulos P, Tuzhilin A (2014) 
On unexpectedness in recommender systems: or how to better expect the unexpected. 
ACM Trans Intell Syst Technol 5(4):Article 54

Non Primitive recommender based unexpectedness

基本的なレコメンダーシステムを前提としない Unexpectedness の指標計算方法としては、
[Kaminskas and Bridge;2014]が提案した指標がある。
まず、ユーザーの利用した二つのアイテム$i,j$に対して、$\operatorname{PMI}(i,j)$を以下のように定義する。(PMIはPoint-wise Mutual Informationの略称)
なお、以下の式の$p(i)$は全てのユーザーについて、アイテム$i$が利用される確率を表す。
（$p(i,j)$は全てのユーザーについて、$i,j$の両方を利用したことがある確率を表す？）

$$
\operatorname{PMI}(i, j)=-\frac{\log _{2} \frac{p(i, j)}{p(i) p(j)}}{\log _{2} p(i, j)}
$$

[Kaminskas and Bridge;2014]は、あるユーザーの過去に利用したことのあるアイテム集合を$H_u$とした場合、unexpectednessとして以下の2種類を定義した。

$$
\operatorname{unexp}(R_u)=\sum_{i \in R_u} \sum_{j \in H_u} P M I(i, j)
$$

$$
\operatorname{unexp}(R_u)=\sum_{i \in R_u} \max _{j \in R_u} \operatorname{PMI}(i, j)
$$

Kaminskas M, Bridge D (2014) 
Measuring surprise in recommender systems. 
In: Workshop on recommender systems evaluation: dimensions and design (REDD 2014), October 10, 2014, Silicon Valley, USA

Serendipity(？)

Serendipity について言及する論文は増えているが、その定義は複雑である。
例えば、"a lucky finding or a satisfying surprise"というニュアンスを含むコンセプトであり、"represent items that the users would difficultly find"とも言及させれている。
このように、Serendipityとは、noveltyやunexpetednessやutilityなどの複数のコンセプトが混じり合ったものと考えられる。
以降では Serendipity の計算関数を $\operatorname{ser}(R_u)$ とする。

様々な $\operatorname{ser}(R_u)$ が提案されているが、例えば[Murakami;2008]は、ユーザー$u$にとって unexpectedなアイテムの集合を $\operatorname{UNEXP}_u = R_u \backslash {PM}_u$ と定義した上で、Serendipityを以下のように定義した。

$$
\operatorname{ser}(R_u)=\frac{\sum_{i \epsilon {UNEXP}_u} \text { utility }(\mathrm{i})}{|R_u|}
$$

Murakami T, Mori K, Orihara R (2008) 
Metrics for evaluating the serendipity of recommendation lists. 
In: Proceedings of the 2007 conference on new frontiers in artificial intelligence (JSAI’07). Springer, Berlin, Heidelberg, pp 40–46

Coverage(網羅性？)

Coverageはこれまでの言及してきた他のコンセプトとは違い、推薦可能な範囲を評価する指標である。
例えば、[Ge;2010]は推薦候補となるアイテムの集合を$I$とし、
そのレコメンダーシステムによって推薦されたアイテムの集合を$I_p$とした場合、
Coverageを以下のように定義した。

$$
\operatorname{cov}=\frac{|I_{p}|}{I}
$$

$$
\operatorname{cov}=\frac{|\sum_{j=1 . . n} I_{L}^{j}|}{|I|}
$$

Ge M, Delgado-Battenfeld C, Jannach D (2010) 
Beyond accuracy: evaluating recommender systems by coverage and serendipity. 
In: Proceedings of the fourth ACM conference on recommender systems (RecSys ‘10). ACM, New York, NY, USA, pp 257–260

Categorization and relationships among the concepts

これまでに紹介した、レコメンダーシステムの評価の各コンセプトは構造的に分類されているわけではない。
ここでは、それぞれの関係性について検討する。

（このサーベイ研究では複数の観点からいくつかの分類方法が検討されているが、本要約ではその紹介は割愛するので、原著を確認してください）

Conclusion

本サーベイの貢献は以下の通りである。

レコメンダーシステムの評価法について、25の研究をレビューし、utility, novelty, diversity, unexpectedness, serendipity, unexpectedness などの評価コンセプトについて整理した。
上記のコンセプトについて、いくつかの観点から分類はそれぞれの関係について論じた。
最後にレコメンダーシステムの評価方法の研究について、今後の3つのチャレンジについて指摘する。(1)数多く提案される評価法のコンセプトを整理する必要がある；(2)レコメンダーシステムがユーザーの満足度に及ぼす要因；(３)オフラインとオンライン評価の結果の違いを埋めること。

以上で、サーベイ研究 "How good your recommender system is? A survey on evaluations in recommendation" の要約を終えます。

要約内容に間違いがあれば、コメントでご指摘いただけますと助かります。
それでは、この要約が何かの役に立てば幸いです。