論文紹介: Rank and Relevance in Novelty and Diversity Metrics

秋から京都に会社のオフィスができて異動になり、以前から交流のあった id:syou6162 さんにご報告したところ、京都に拠点のあるIT企業の合同論文輪読会に誘っていただきました。

自分の担当回では推薦システムに関する次の論文を取り上げることにしたので、発表用のノートを兼ねて解説を公開します。

Rank and Relevance in Novelty and Diversity Metrics †

www.slideshare.net

推薦システムにおける Novelty, Diversity

Webサービスを利用していて、以下のような経験をした方は多いのではないでしょうか。

  • ECサイトで、すでに購入した商品と似たような商品ばかりがおすすめに表示される
  • 転職サイトで、提示されるおすすめ求人が互いに似たようなものばかりになる

使われるアルゴリズムにもよりますが、一般的な推薦システムではすでに評価・選択したのと似たようなアイテムが推薦されたり、推薦されるアイテムが互いに似通ったりしがちです。

しかし推薦システムの目的によっては、似たようなものを提示するのではなく、次のような性質が求められることがあります。

  • Novelty (新規性): 今まで見かけたことのない目新しいアイテムを推薦できること
  • Diversity (多様性): 互いに特徴が異なる複数のアイテムを一度に推薦できること

本論文では、推薦システムの出力の novelty や diversity についての評価指標を提案しています。 また提案指標を用いることで、各アルゴリズムの特徴を客観的に比較できることを実験で示しています。

用語

以下の解説では次の用語を使います。

  • ユーザ: 推薦システムの利用者
  • アイテム: 推薦システムがユーザに推薦する個々のもの (商品など)
  • ランキング: 一度の推薦でまとめて提示されるアイテムのリスト
  • レーティング: ユーザのアイテムに対する評価
    • Explicit (明示的) なレーティング: 5段階のスターなど
    • Implicit (暗黙的) なレーティング: クリックしたかどうかなど

先行研究と問題点

Novelty, Diversity の改善手法と評価指標

推薦システムの Novelty, Diversity を改善する手法は本論文以前にいくつか提案されています。

Novelty については、Zhou 2010 が協調フィルタリングとグラフのスコア伝播を用いた手法を提案しています。 この研究では評価指標として、ランキング中のアイテムの平均自己情報量 (各アイテムを評価したユーザの割合の対数) を用いています。 また Celma 2008 では、 アイテム間の類似関係によるアイテムの発見されやすさを考慮しています。

Diversity については、Ziegler 2005 が貪欲法により再ランキングを行う手法を提案しています。 また Zhang 2008 ではユーザの選好とアイテム間の類似度に基づく二次最適化問題を解くことで diversity の向上を試みています。 これらの研究では評価指標として、ランキング中のアイテム間相互の距離や非類似度を用いています。

評価における問題点

これらの先行研究について、本論文では次のような問題を指摘しています。

まず novelty, diversity に対する定義がそれぞれ異なっており、それらの関係性についてもあまり議論されていませんでした。 そのため各研究で独自の評価指標が用いられ、手法同士を客観的に比較することが困難でした。

またいくつかの研究では評価指標に次のような欠点がありました。

  • Ranking-unawareness: ランキング中のアイテムの順位変化による影響が考慮されていない
  • Relevance-unawareness: ユーザにとってのアイテムの関連度 (適合度) が考慮されていない

こういった問題に対して、本論文ではユーザの行動モデルを用いて novelty, diversity とその関係性を定義できると主張しています。 また、この行動モデルを用いて novelty, diversity の評価指標を一般化・定式化することを提案しています。

Discovery, Relevance, Choice に基づくランキング評価指標

Discovery, Relevance, Choice モデル

提案されるユーザ行動モデルは次のようなものです。 まず、次の3つのユーザとアイテムの関係を定義します。

  • Discovery (発見): アイテムがユーザに発見される (見られる, 知られる, etc.)
  • Relevance (関連): アイテムがユーザと関連する (好まれる, 役立つ, etc.)
  • Choice (選択): アイテムがユーザに選択される (クリックされる, 買われる, etc.)

ユーザとアイテムにこれらの関係が成立していることを、二値変数を用いて  seen=1,  rel=1,  choose=1 と表します。 またそれらの確率を  p(seen=1),  p(rel=1),  p(choose=1) あるいは  p(seen),  p(rel),  p(choose) のように表します。

例えばECサイトなら、ユーザにが閲覧した商品は  seen=1 であり、ユーザが欲しいと思う商品は  rel=1 であり、ユーザが購入した商品は  choose=1 とである、とみなせます。

ここで簡単のため次が成り立つとします。

  • アイテムがユーザに発見されるかどうか (discovery) と関連するかどうか (relevance) は独立である
  • ユーザは自分に関連する ( rel=1) アイテムを発見する ( seen=1) と必ずそれを選択する ( choose=1)
  • ユーザは自分に関連しない ( rel=0) アイテムは選択しない ( choose=0)

これにより次の式が成り立ちます。

 { \displaystyle
  p(choose) \sim p(seen) p(rel)
}

以降ではこのモデルを根幹として、アイテムの novelty やランキングの novlety, diversity をモデル化します。

ランキング評価指標の一般化

本論文が提案する一般化されたランキング評価指標は次の式で表されます。

 { \displaystyle
  m(R|\theta) = C \sum_{i \in R} p(choose|i,u,R) nov(i|\theta)
}

 nov(i|\theta) がアイテムの novelty であり、後ほど discovery, relevance, choice を用いてモデル化されます。  \theta はコンテキストと呼ばれる変数で、ユーザが発見済みのアイテム集合や、アイテムの人気や普遍性をモデルに組み込むために使われます。 これによりアイテムの novelty がユーザとアイテムの現在までの関係によって変化することをモデル化できます。

アイテムの novelty は  p(choose|i,u,R) によって重み付けされます。 つまり、どれだけ novelty の高いアイテムでも、それがユーザに選択されれる可能性が低ければランキングの評価に寄与しない、という条件をつけることができます。 これにより先行研究に対して指摘されていた rank-unawareness や relevance-unawareness の問題を克服することができます。

アイテムの Novelty

ここからは上述の一般化された評価指標から diversity, novelty を導くため、各項を具体的に定式化していきます。 まず  nov(i|\theta) の具体的なモデルとして、次の2種類が提案されます。

Popularity-based Novelty

ひとつは novelty を「ユーザがまだそのアイテムを発見していない可能性」とみなした次のモデルです。

 { \displaystyle
  nov(i|\theta) = 1 - p(seen|i,\theta)
}

 \theta には各アイテムを評価したユーザ数などが用いられます。 観測されたレーティング全体から  p(seen|i,\theta) を推定する方法は後ほど紹介します。

なお本論文では確率  1-p の代わりに情報量  -log(p) を使う方法も紹介されますが、実験では省略されるため割愛します。

Distance-based Novelty

もうひとつは novelty を「ユーザが既に発見したアイテムとの距離」とみなした次のモデルです。

 { \displaystyle
  nov(i|\theta) = \sum_{j \in \theta} p(j|choose,\theta,i) d(i, j)
}

 p(j|choose,\theta,i) \theta においてアイテム  i が選択された場合にアイテム  j が選択される確率であり、 d(i, j) はアイテム  i, k の距離 (または非類似度) です。

 \theta には、ユーザがランキングを閲覧する前に発見済みのアイテム集合や、ランキング中で対象アイテムの前に出現したアイテムの集合とします。 特に後者はランキングの diversity の評価指標を導くのに使われます。

ランキングの Novelty, Diversity

上記のモデルにより各アイテムの novelty を定式化できたので、次にこれを用いてランキングの novelty, diversity を定式化します。

Browsing モデル

ランキングを閲覧する際には、ランキング上位のアイテムほど選択されやすく、下位のアイテムは選択されにくくなると考えられます。 これは上記のモデルにおいて、  p(choose|i,u,R) i R 中での順位に依存すると考えることでモデル化できます。

ここで、アイテムとユーザの関連度  p(rel) はコンテキストの影響を受けない (ユーザの過去の行動やランキング中の他のアイテムに左右されない) と仮定すると、次の関係が導かれます。

 { \displaystyle
  p(choose|i,u,R) \sim p(seen|i,u,R) p(rel|i,u)
}

さらに、ランキング  R において順位  k のアイテム  i_k が発見される確率  p(seen|i_k,u,R) が、  k についての減少関数  disc(k) で表されると仮定すると、  p(choose|i_k,u,R) は次のように表されます。

 { \displaystyle
  p(choose|i_k,u,R) = disc(k) p(rel|i_k,u)
}

以上の仮定を導入したモデルを browsing モデルと呼びます。 Browsingモデルにおける  m(R|\theta) は次のように定式化されます。

 { \displaystyle
  m(R|\theta) = C \sum_{i_k \in R} disc(k) p(rel|i_k,u) nov(i_k|\theta)
}

実際の  disk(k) としては nDCG で用いられる  1/log(k+1) などをそのまま使うことができます。

さて、以上によりランキングの novelty, diversity は次のように計算できます。

ランキングの Novelty

ランキングの novelty の算出においては、ユーザがランキングを閲覧する以前に知りうる情報をコンテキストとして考えます。 すなわち  \theta には事前に観測されたレーティング等を与えることになります。

Popularity-based novelty を用いたランキングの novelty は次のようになります。 これを論文では expected popularity complement (EPC) と呼んでいます。

 { \displaystyle
  nov(R|u) = C \sum_{i_k \in R} disc(k) p(rel|i_k,u) (1 - p(seen|i_k))
}

Distance-based novelty を用いたランキングの novelty は次のようになります。 これを論文では expected profile distance (EPD) と呼んでいます。

 { \displaystyle
  nov(R|u) = C' \sum_{i_k \in R, j \in \mathbf{u}} disc(k) p(rel|i_k,u) p(rel|j,u) d(i_k, j)
}

ランキングの Diversity

ランキングの diversity の計算では、対象のランキングそのものの情報をコンテキストとして考えます。 すなわち  \theta \equiv R となります。

ランキングの diversity は次のようになります。 これを論文では Expected Intra-List Diversity (EILD) と呼んでいます。

 { \displaystyle
  div(R|u) = C' \sum_{i_k \in R, i_l \in R, l \neq k} C_k disc(k) p(rel|i_k,u) disc(l|k) p(rel|i_l,u) d(i_k, i_l)
}

レーティングによる Discovery, Relevance の推定

以上によりランキングの novelty, diversity を定式化できました。 実際にこれらを計算するためには、観測済みのレーティング等の情報を用いて  p(seen) p(rel) を推定する必要があります。 以下ではレーティングを関数  r : \mathcal{U} \times \mathcal{I} \to \mathcal{V} によって表します。

Discovery の推定

コンテキスト  \theta \equiv r のもとでアイテム  i が発見済みである確率  p(seen|i, r) の推定値は次のように求められます。

 { \displaystyle
  p(seen|i,r) = \frac{ | \{ u \in \mathcal{U} | r(u, i) \neq \varnothing \} | }{ | \mathcal{U} | }
}

論文では他のバリエーションについても述べていますが、ここでは割愛します。

Relevance の推定

 r が explicit なレーティングの場合、そのままでは確率  p(rel) として扱えないため、 g(u, i) = max(0, r(u,i) - \tau) ( \tau は微小な差異を無視するための定数) を用いて次のように変換します。

 { \displaystyle
  p(rel|i,u) = \frac{ 2^{g(u, i)} - 1 }{ 2^{g_{max}} }
}

論文では implicit なレーティングについても述べていますが、ここでは割愛します。

評価実験

本論文では diversity, novelty の向上手法ではなくその評価指標を提案しています。 そのため実験は「評価指標の評価」を行うためのものとなります。 実験では、提案指標を用いることで各種レコメンドアルゴリズムや novelty, diversity アルゴリズムの差異を客観的に捉えることができていることを示しています。

評価に用いられているデータセットは次のとおりです。

  • MovieLens 1M: 映画に対する5段階の explicit なレーティング
  • Last.fm: 楽曲アーティストに対する implicit なレーティング (視聴ログ)

比較対象の推薦アルゴリズムは次のとおりです。

  • MF: Matrix Factorization
  • CB: Content-Based Filtering
  • UB: User-Based Collaborative Filtering
  • AVG: Average Rate
  • RND: Random

これらに対して上記の EPC, EPD, EILD をランキング上位50件について計算した結果が次のグラフとなります。

f:id:yubessy:20181119162018p:plain

(† Figure 2. より)

Popularity-base vs. Distance-base

まずは popularity-base, distance-base の novelty によって各アルゴリズムがどう特徴づけられるかを見てみます。 グラフの上段は relevance を考慮せずに ( p(rel) = 1) 各指標を算出したものです。 ここからコンテンツベースのアルゴリズムとレーティングベースのアルゴリズムの違いが顕著に読み取れます。

Popurality-base のEPCではコンテンツベースのCBがレーティングベースのUB, MFよりもスコアが高いのに対し、Distance-base のEPD, EILDでは逆にCBのスコアが低くなっています。 このことから、提案指標で用いられる popularity-base, distance-base の novelty はそれぞれ各アルゴリズムの特徴を捉えるのに適していると言えそうです。

Relevance-awareness の効果

次に、提案指標により relevance-unawareness の問題に対処できることを示します グラフの下段が relevance を考慮した指標となっており、これを上段と比較するとその効果が見て取れます。

Relevance-unaware な指標ではAVG, RNDが高い novelty, diversity を示していたのに対し、 relevance-aware な指標ではMF, UBがそれらを上回っています。 このことから、 relevance を考慮することで diversity, noveltyが高くともユーザとの関連度が低いアルゴリズムを不当に高く評価しないようにできると言えます。

Relevance-aware な指標では、explicit なレーティングに対してはではMFがUBを上回っており、 implicit なレーティングに対してはそれが逆転しています。 これらは relevance を考慮しない場合は似たような値となっていたので、 relevance を考慮することで diversity, novelty があまり変わらないアルゴリズム同士の優位性を評価できると言えます。

Rank-awareness の効果

最後に、提案手法により rank-unawareness の問題に対処できることを示します。 これを示すには、同じランキングを様々な diversification 手法により再ランキングした結果を比較する必要があります。 実験ではMFの結果を次のような手法で再ランキングした結果を比較対象として取り上げています。

実験結果は次の表にまとめられています。

f:id:yubessy:20181119170102p:plain

(† Table 5. より)

Relevance を考慮した場合のみについて、いくつか結果を見てみます。 ベースラインとなるMFを上回るスコアを得ている手法はそれほど多くありませんが、IA-Select は全体的にベースラインを上回る結果を残しています。

順位によるディスカウントなしの場合 ( disc(k) = 1) とありの場合 ( disc(k) = 0.85^{k-1}) を比較すると、IA-Select は MovieLens, Last.fm の両方でスコアを上げていますが、MMR, NGD はスコアを下げていることもあります。 このことから、MMD, NGDでは元のランキングにおいて下位になっている relevance の低いアイテムが上位に浮上している可能性が考えられます。

このように、提案手法を用いることで rank-unaware な指標では発見できなかった各手法の特徴を発見できています。

おわりに

今回は特定の手法ではなく評価指標に関する論文を選んでみました。

検索や推薦などのシステムでは、ユーザがシステム求める性質が様々なので、それぞれの目的に応じて適切な指標を選ぶ必要があります。 本論文で提案される一般化された指標はそういった様々な場面で応用が効きそうです。

またユーザ行動モデルから評価指標を導く一連の考え方は、評価方法を新しく考える必要があるようなケースで参考になりそうです。