Wantedly の Matching Squad でデータサイエンティストをしている関根( twitter: @ndnto, github: @hiroto0227 )です。Matching Squadでは主に企業とユーザーの理想的なマッチングを実現することを目的として、検索システム・推薦システムの改善を行っています。

モチベーション

去年の秋ごろに RecSys2020 に参加して最新の推薦システムの技術についてキャッチアップをしました。最近の傾向の一つとして、推薦システムはユーザーの関心の高い(適合度の高い)アイテムを推薦するだけではなく、 Diversity (多様性)や Novelty (新規性)を追求することで、ユーザーにより良いアイテムを推薦することがあるように感じました。

そこで、今回は推薦システムにおける Diversity 定義や、 Diversity のある推薦が求められている理由、さらには Diversity を高めるためのアルゴリズムについて、いくつか論文を参考にしながら紹介します。

[1] Bradley, Keith, and Barry Smyth. "Improving recommendation diversity." Proceedings of the Twelfth Irish Conference on Artificial Intelligence and Cognitive Science, Maynooth, Ireland. Vol. 85. No. 94. 2001.

[2] Kaminskas, Marius, and Derek Bridge. “Diversity, serendipity, novelty, and coverage: a survey and empirical analysis of beyond-accuracy objectives in recommender systems." ACM Transactions on Interactive Intelligent Systems (TiiS) 7.1 (2016): 1-42.

[3] Vargas, Saúl, et al. "Coverage, redundancy and size-awareness in genre diversity for recommender systems." Proceedings of the 8th ACM Conference on Recommender systems. 2014.

推薦システムにおける Diversity とは？

まず、推薦システムにおける Diversity とは何かについて説明します。推薦システムにおける Diversity は、「推薦結果として返すアイテムセット同士の類似度が低い」と定義されることが多いです。例えば映画推薦では、一度にホラー映画を3つ推薦したときよりも、ホラー映画, アクション映画, ロマンス映画を一つずつ推薦した時の方が Diversity の高い推薦と考えられます。

推薦システムの領域で Diversity について初めて言及されたのは、2001年に発表された”Improving recommendation diversity”[1]という論文でした。この論文ではユーザーの関心の高いアイテムを推薦することで、 Diversity がなくなってしまうことに問題を投げかけています。そして Diversity の定義付けを行い、ユーザーの関心を下げずに Diversity を高めるアルゴリズムを提案しています。

近年では、 Diversity の他にも推薦システムの性能評価を行う上で似たような指標がいくつか存在します。それぞれの定義は”Diversity, serendipity, novelty, and coverage: a survey and empirical analysis of beyond-accuracy objectives in recommender systems”[2]の論文を参考にしています。

• Coverage
• • 推薦可能なアイテムのうち、どれくらいのアイテムを推薦したか？
  • Coverage が高いほど、多くのアイテムが結果として返されるようになる。
• Novelty
• • 「 Novelty のあるアイテム」 = 「ユーザーが初めてみるようなアイテム」
  • ただ新しいアイテムを出せば良いのではなく、ユーザーにとって有益なアイテムであることが望ましい。
• Serendipity
• • 「Serendipity のあるアイテム」= 「ユーザーが驚くようなアイテムであり、さらにユーザーにとって有益なアイテム」
  • Serendipity については定義がいろいろあるが、「ユーザーの関心」+「新規性」+「意外性」と解釈される。

これらの指標は Diversity とも関連深い指標であり、論文ごとによって定義が異なることが多いです。自分は論文を複数読んでいて、それぞれの定義がごちゃごちゃになってしまうことがありました。

推薦システムで Diversity の高い推薦が必要な理由

推薦システムは情報検索システムの一部であり、[2]の論文によると Diversity については情報検索システムの分野ですでに議論されていたそうです。例えばユーザーが「アップル」と調べた時に、ユーザーの意図としては、企業の「apple」を指すのか、果物の「アップル」を指すのか分からない場合があります。その時にユーザーがどちらを意図しているか分からない時は多くの情報を出す方が望ましいと考えられていて、これが Diversity が情報検索システムや推薦システムで重要視されている理由の一つです。自分は、推薦システムでは検索クエリがない場合が多いため、Diversity は特に重要であると考えています。

また、推薦システムの問題の一つとして OverFitting 問題があります。 OverFitting 問題とは、推薦モデルがユーザーのフィードバックによって学習される場合、推薦モデルはユーザーの好みを反映しようとして、ユーザーが評価していないアイテムが推薦されなくなってしまうことです。

この問題の解決策の一つとして、Diversity を高める推薦が挙げられます。ここで重要なのが、Diversity をあげることと、ユーザーの好みへの適合度(Accuracy)はトレードオフの関係にあることです。ただ Diversity をあげるためならば、全てのアイテムをランダムにを返してあげれば良いが、それではユーザーの好みではないアイテムを多く推薦してしまい、ユーザーがサービスから離脱してしまうことが考えられます。したがって、「Accuracy をできるだけ下げずにどれだけ Diversity を上げられるか?」が論点となっています。

Dissimilarityを用いたDiversityの定義

次に、推薦システムで Diversity の重要性について初めて言及した”Improving recommendation diversity"[1]で定式化された Diversity の定義について説明します。この論文の3章では、Diversityを以下のように定義しています。

We define the diversity of a set of items, c1,...cn, to be the average dissimilarity between all pairs
of items in the result-set (Equation 2).

ここではSimilarityの反対の意味である Dissimilarity という言葉を用いていて、 Diversity は推薦結果の全てのアイテム同士の Dissimilarity の平均としています。式で表すと以下になります。

[2]の3章から引用。

cは推薦結果のアイテムであり、推薦結果の1からn番目までのアイテムの全てのペアに対してDissimilarity (1 - Similarity )を計算して、それの平均をとっています。

この指標は Similarity の計算方法に大きく影響を受けます。ドメインやサービス、またはサービス内の一つの機能ごとに、どういう類似コンテンツを載せたいのかによって、Similarity の計算方法を設計しなければいけません。RecSys2020の Netflix は、推薦する場所、ユーザー、Context などを考慮した上で Similarity を設計することが大事であると発表していました。この発表については @yu-ya4 さんが以下の記事でまとめていて参考になります。

アイテムのジャンルを用いたDiversityの定義

Diversity の定義の一例を紹介します。”Coverage, Redundancy and Size-Awareness in Genre Diversity for Recommender Systems”[3] では、Diversity の定義にジャンルを用いています。著者らはユーザーがどのようなアイテムを返した場合に Diversity を感じるのかを考え、アイテムのジャンル(映画の場合はホラーやアクションなど)の性質に注目しています。そして、推薦結果内のジャンルが多様化していたらユーザーが Diversity があると考えるのではないかと仮説を立てています。この論文では Diversity を定式化するために以下の三つの点が考慮される必要があると主張しています。

Genre Coverage

その名の通り推薦結果にどのくらいジャンルが含まれているかを表している。推薦結果により多様なジャンルが含まれる場合は Genre Coverage は高くなります。

Genre Redundancy

Redundancyは「冗長性」という意味です。例えば、推薦結果に全てのジャンルが含まれていたとしても、あるジャンルではアイテム数が多く、その他のジャンルではアイテム数が少ない場合、ユーザーはDiversityのある推薦とは感じません。したがって、Diversity のある推薦を行うためには、推薦結果に同じジャンルが何回も登場しないことが必要です。Genre Redundancy を低くすることで、冗長性のない推薦を行うことができ、Diversity を感じやすくなります。

Size-Awareness

Diversity のある推薦かどうかを判断するためには、推薦結果を返すアイテムサイズも重要になってきます。推薦結果のアイテムサイズが少ない場合は Genre Coverage は低くなることが考えられるので、アイテムサイズの変化に適応できるような指標であることが必要だと提案しています。

これら3つの条件を満たすために、この論文では Binomial Diversity という指標を提案しています。各ジャンルの生成確率は平等ではないため、各ジャンルの生成確率を全体のアイテムの中に各ジャンルのアイテムが含まれる数や、ユーザーの行動ログを用いて推定します。例えば、全てのアイテム内にアクション映画が多く含まれるのに、推薦結果にアクション映画が含まれていない場合は、重いペナルティを与えるためです。そうして得られたジャンルごとの生成確率を元に、推薦結果のアイテム内のジャンルの Coverage や NonRedundancy ( Redundancy の反対) を計算しています。計算式については省きますが、結論としては、 Diversity は推薦結果のアイテムサイズで正規化された Genre Coverage と Genre NonRedundancy の積で表されています。

この論文では、どうやったらユーザーが Diversity を感じるかを元に適切な指標を考えていて、ここで定義した Diversity を向上させる推薦のアルゴリズムを提案しています。

Diversityを高めるためのアルゴリズム

Maximal Marginal Relevance(MMR)

最後に、 Diversity を高めるためのアルゴリズムのナイーブな方法について紹介します。MMRは情報検索システムの分野で使用されることもある、 Re-Ranking 系のアルゴリズムです。Re-Ranking とはユーザーの関心との関連性を元にアイテムを絞り込んで、その絞り込んだアイテムを Diversity が大きくなるように再度並び替えるアルゴリズムです。 MMR は以下の式で表されます。([2]の2.2章: Increasing Diversityより参照)

1項目は関連性を表すスコアであり、2項目は推薦結果 R の中でのアイテムとの距離の平均を加えています。アイテムiが関連性が高かったとしても、その推薦結果内で似たようなアイテムが多い場合は、2項目の値が小さくなってしまいます。結果としてユーザーの関連性が高いアイテムであっても、推薦結果内に似たようなアイテムが多く存在する場合は全体のスコアが小さくなってしまうということです。α は Diversity をどれくらい重要視するかのパラメータとなっています。

まとめ・感想

推薦システムには Diversity が必要だとなんとなく感じてはいましたが、実際に複数の論文を読んで見ることで、Diversity が必要な理由を言語化することができました。推薦システムの Diversity を考える上で大切なことは、ユーザーの関心のあるアイテムを出すのを前提とした上で、Diversity をいかに高くするかを考えることだと思います。このトレードオフをどれくらい許容するかを決定することがさらに難しいことだと考えています。また、Diversity を語る上で欠かせないのが Similarity の設計です。自分の作成するサービスではどのアイテムを似ているとするかを考えて、そこから Similarity の求め方を決定する必要があります。

実際に Airbnb や Spotify などでは、Diversity の理論的な研究だけではなく、実際のシステムに Diversity を組み込む研究を行っています。Airbnb は KDD2020 で、推薦結果の上位の Diversity が低くなっていることを発見し、関連性と Diversity の両方を含めた損失関数を用いたモデルを提案しています。

Abdool, Mustafa, et al. "Managing Diversity in Airbnb Search." Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020.

また、 Spotify は WWW2020 で長期的にサービスを使うユーザーを増やすためには、Diversityのある推薦を行うことが必要だとしています。

Anderson, Ashton, et al. "Algorithmic effects on the diversity of consumption on spotify." Proceedings of The Web Conference 2020. 2020.

推薦結果の Diversity を高めることは、ユーザーの関心の低いアイテムが出てしまうことを許容してまでも、長期的にサービスを使用していく上で重要視されていることが分かります。

WantedlyでDiversityのある推薦を行おうとすると、例えば、募集一覧ページで見ることができる募集を多様化することなどが考えられます。ただ、多様化するといっても、どのような軸で多様化させるかを決定しなければいけません。様々な業界( IT業界, 農業, 自動車, ...)の募集を出すべきか、様々な職種(セールス, エンジニア, マーケター, ...)の募集を出すべきか、様々な地域の募集を出すべきか、いろいろな選択肢があると思っています。それらの選択肢の中で、ユーザーにとって有益な募集を出しつつも、多様化させる方法を考える必要があります。(ここが一番難しいところだと感じています。)
このような多様化を行うことによって、今まででは発見できなかったような面白い企業とカジュアルに出会える機会をユーザーに提供できるのではないかと考えています。Diversity のある推薦は、 Wantedly のようなビジネス SNS にとって有益であると考えているので、このような推薦のキャッチアップも行っていきたいと思います。