yuya4's note

備忘録です。好きにアウトプットします。

Reciprocal Recommender Systems(相互推薦システム)の紹介

はじめに

この記事は、情報検索・検索エンジン Advent Calendar 2019の12日目のものです。初日から素晴らしい記事ばかり登場するので毎日胃が痛かったです 楽しませていただいております。

今年の9月にコペンハーゲンで開催された推薦システムについてのカンファレンスである RecSys 2019 に参加したのですが,そこで発表 (Neve 2019) を聞いて強く興味を持った Reciprocal Recommender Systems(相互推薦システム)について紹介することにします。

この記事は RecSys2019 の内容について紹介し合う以下の勉強会で私が発表した以下の資料をベースにサーベイしなおしてまとめたものです。

connpass.com

speakerdeck.com

Reciprocal Recommender System(相互推薦システム)とは

一般的に RSs(Recommender Systems; 推薦システム) とは,Amazon などの EC サービスのように,アイテム(商品)をユーザに一方的に推薦するようなシステムのことを指します。 一方で,TinderPairs などのオンラインデーティングサービスであったり,LinkedInWantedly などのビジネスSNS(広義の求人サービス)のように,サービス内のユーザを互いに推薦するシステムを RRSs(Reciprocal Recommender Systems; 相互推薦システム) と言います。

オンラインデーティングサービスと求人サービスでは問題設定が異なっていると感じるかもしれませんが,前者は(基本的に1)男性ユーザに対して女性ユーザを,女性ユーザに対して男性ユーザを相互に推薦するという構造であり,後者は個人ユーザ(いわゆる求職者)に対して企業ユーザ(いわゆるリクルータあるいは企業)を,企業ユーザに対して個人ユーザを相互に推薦するという構造であり,サービス内のユーザを互いに推薦しているという点において問題設定は近しいです。

従来の RSs では,基本的にユーザからアイテムへの嗜好(評価)のみに基づいて推薦が行われます。一方でRRSでは、ユーザどうしの相互の嗜好に基づいて推薦が行われます。ここが従来の RSs と RRSs の一番の違いです。

初めて RRSs が従来の RSs と明確に区別され,その性質について詳細に議論されたのは (Pizzato 2010) のようですが2,従来の RSs に比べて RRSs についてはまだまだ十分に研究が行われていません。

従来の推薦システム(RSs)と相互推薦システム(RRSs)の比較

従来の RSs に対して RRSs には,人気ユーザを不人気なユーザに推薦してしまった(もしくはその逆)際の影響や,受動的な(自分からはアクションしない)ユーザに対して受動的なユーザを推薦した際の影響など,追加で考慮すべき RRSs に特有な様々な問題が存在します。従来の RSs と RRSs の性質の違いについて「ユーザのプロフィールや好みについての情報」,「サービス内におけるユーザの役割」,「推薦システムの性能評価」という3つの観点における比較が (Pizzato 2012) にまとめられているので簡単に紹介します。

ユーザのプロフィールや好みについての情報

f:id:yu-ya4:20191211182745p:plain
Table 2 from (Pizzato 2012)

ユーザが明示的に提供するデータ

従来の RSs では通常,明示的なユーザのプロフィールは必須でなく,わざわざ自身の好みのアイテムについての詳細な情報をサービスに提供したがるユーザは少数です。さらには,ユーザは自分自身が一体何を必要としているのか,欲しているのかを分かっていないこともあります。そのため,ユーザが明示的に提供する自身のプロフィールや好みについての情報だけで十分な推薦を行うことは難しいです。また,情報の提供をユーザに強いることもサービスとして望ましくありません。

一方で RRSs においては,ユーザは積極的に自身のプロフィールや好みのユーザの情報を詳細に提供してくれる傾向にあります。ただ,ユーザは自身をより魅力的に見せるために,無自覚な場合も含めて,正しくない情報を提供してしまうことがあるのでその点を留意する必要があります。自身の好みについても,無自覚な場合も含めて,本当の好みを提供しているとは限りません(性格重視って書くけど実は顔と年収しか見ていない的な?)。

ユーザが明示的に提供するプロフィールや好みについての情報と,ユーザの本当の好みの間にギャップがあることを理解した上でシステムを設計するのは重要です。サービスを利用することで暗黙的に得られるユーザの好みについての情報を利用すれば,ある程度ユーザの本当の好みについて推定することが可能となります。そうすることで,ユーザにプロフィール情報の訂正を促したり,ユーザが自身では気づいていない本当の好みについて気づかせてあげたりといったことが可能となります。

行動履歴に基づく暗黙的な嗜好データ

サービス内でのユーザの行動履歴に基づいて得られる暗黙的な情報という点では,従来の RSs では良いサービスならばロイヤルユーザが何度も利用してくれるのでたくさんのデータが集められます。対照的に RRSs ではサービス内で結婚や転職などの目的が果たされるとユーザはほぼ永久にサービスに戻ってきません。ユーザの行動履歴を利用する場合はこの性質も考慮した設計にする必要があります。

サービス内におけるユーザの役割

f:id:yu-ya4:20191211182946p:plain
Table 3 from (Pizzato 2012)

「推薦の適切さ」の決定

従来の RSs において適切なアイテムが推薦されたかどうかというのはユーザの判断のみによって決定されていました。つまり,ユーザが推薦されたアイテムを購入すると決めたらその推薦は適切ですし,購入しないと決めたのならその推薦は適切でなかったということになります。一方で,RRSs においては適切なユーザが推薦されたかどうかというのは,推薦を受けたユーザ(subject)と推薦されたユーザ(object)の両方の判断によって決定されます。

また,RRSs を利用するユーザはこの事実を認識しており,サービス内でのユーザの行動にも影響を及ぼしています。たとえば,ものすごく好みのユーザが推薦されたとしても,そのユーザにとっては自分は好みではなく断られてしまうのではないかと恐れて推薦を受け入れないという行動に出ることがあります。

好意の「送り手」と「受け手」

従来の RSs においてはユーザが能動的にアイテムを探し,気に入ったものがあれば購入などのポジティブなアクション/好意をアイテムに対して行います。アイテムからユーザに対して好意を伝えたりすることはできません。つまり,ユーザは常に好意の送り手でありアイテムは常に受け手となります。しかし,RRSs ではユーザは状況に応じて送り手にも受け手にもなります。あるユーザが他のユーザの推薦を受けっとた際には,推薦されたユーザが自身のことを気に入ってくれるかということも考慮しつつ,そのユーザに興味があると伝えるかどうかを送り手として決定します。一方で,あるユーザから好意/興味があると伝えられたユーザは受け手となり,送り手のユーザは自分に興味があるということは既に分かっているため,単純に自分の好みだけに基づいてそのユーザに興味があると伝えるかどうか決定できます。

推薦システムの性能評価

f:id:yu-ya4:20191211183010p:plain
Table 4 from (Pizzato 2012)

性能指標

従来の RSs において推薦が適切であるかどうかは推薦に対するユーザの反応のみに着目した正解率で評価することが多いです。一方で,RRSs においては3つの観点で正解率を考えることができます。まず最初に,他のユーザの推薦を受け取り好意の送り手となるユーザに着目すると,推薦されたユーザの中にどれだけ好意を送ることにしたユーザがいたかという指標が考えられます。次に,送り手から好意を伝えられた受け手のユーザに着目すると,受け取った送り手の好意に対してどれだけの割合で好意を伝え返したかという指標を考えることができます。最後に,最終的に推薦された中からどれくらいの割合でユーザ間のマッチングが成立したかという指標も考えられます。

性能への期待値

推薦の精度の必要性,ユーザからの期待値も従来の RSs と RRSs では異なります。前者ではある程度精度が悪くとも(もちろん悪い体験には変わりないが)ユーザはアイテムを購入しないという判断をするだけです。また,たくさんの様々な良いアイテムを推薦してもらいたいと考えているので,多少良くないものでも受け入れてしまう(購入してしまう)こともあります。一方後者では,好意の送り手にとっては魅力的だが受け手にとって送り手が魅力的でないというような推薦が多くなってしまうと,送り手は何度も自分の好意が送り手に断られるというサービスとしてかなり悪い体験をしてしまうことになります。また,サービスの性質上ユーザは少数の(あるいはたった1人の)本当に自分に合ったユーザを探しています。そういう状況において精度の低い推薦をしてしまうことは比較的ユーザにとって受け入れがたいことです。

推薦されるコンテンツの偏り

従来の RSs においては,同じアイテムがたくさんのユーザに推薦されるということに何の問題もありません(在庫の問題とかはあるかもしれませんが)。一方で,RRSs において1人のユーザをたくさんのユーザに推薦してしまうと,そのユーザに送られる好意の数が増えすぎてユーザのキャパシティを超えてしまいます。その結果として,断られる好意の数が多くなってしまいます。逆に,あるアイテム/ユーザが全く推薦されないということを考えると,従来の RSs において本当にそのアイテムが良くないものなのであればそれがどのユーザに対しても全く推薦されないというのはサービスとしては良いことです(そのアイテムの販売者からしたら違うかもしれないが)。一方で,RRSs の場合を考えると,自分から積極的に好意を伝える送り手の役割をこなせるユーザが他のユーザに推薦されないことはサービスとして大きな問題はありませんが,あまり自分から好意を伝えられない受け身なユーザは他のユーザに推薦されないと永遠にマッチングという目的を果てせないことになります。また,受け身なユーザを受け身なユーザにだけ推薦しても両者ともに自分からは好意を送らないために問題となってしまいます。

セレンディピティ

セレンディピティについて,ユーザがあまり明示的に自分の好みを示さない従来の RSs においては受け入れられやすく,寧ろ目新しいアイテムに出会いたいというユーザはたくさんいます。一方で,ユーザが自分の好みをある程度明示的に提供している RRSs において,提供された情報とまったく異なるユーザを推薦してしまうことは悪い体験となりやすい。そのため,なぜユーザが明示的に提供している好みの情報と異なるユーザを推薦しているのかをユーザに理解してもらえるようなインタフェースが求められることになります。

システム構成

Reciprocal Recommender Systems の構成を抽象化すると以下のように表されます。

f:id:yu-ya4:20191212171609p:plain:w400

User A と User B の2群が存在するとします。まず,User A 群に所属する各ユーザから User B 群に所属する各ユーザへの一方向の嗜好を表現する User A to User B Preference Score をなんらかの手段で計算します。同時に,逆向きの嗜好を表現する User B to User A Preference Score も計算します。 次に,それら2つの Preference Score をなんらかの手段(Aggregation Function)で集約することで,双方向のマッチ度を表現する1つの Reciprocal Preference Score へと変換します。この Reciprocal Recommender Score に基づいて,ユーザごとに推薦を行います。

従来の RSs の場合だと,ユーザからアイテムへの一方向の Preference Score のみを計算して推薦を行いますが,RRSs では逆方向の Preference Score も計算して,最終的に推薦に使うスコアは双方向のスコアを考慮しているというのが大きな違いです。かなり単純な仕組みですが,実際のデータで検証すると双方向の嗜好を考慮した Reciprocal Preference Score を利用した推薦システムの方が良い性能が出ているそうです。

RRSs を実現する手法

最後に,実際に RRSs を実現する手法としてこれまで提案されてきたものをいくつか紹介します。

RECON, a content-based filtering algorithm for reciprocal recommendation

RECON: a reciprocal recommender for online dating.(Pizzato 2010) で提案された手法です。その名の通り,コンテンツベースのアルゴリズムであり,各ユーザの嗜好データと各ユーザのプロフィール情報の一致度合いから Preference Score を算出します。

あるユーザについて,過去に好意を送ったユーザ群と受け取った好意に対して好意を返したユーザ群から,体格や年齢,学歴などの属性の要素を抽出することで,ユーザごとの嗜好を表現するデータを作成します。次に,その嗜好を表現するデータとそれぞれのユーザのプロフィール情報のマッチ度を算出することで,あるユーザからその他のユーザへの Preference Score を算出します。

Aggregation Function としては調和平均を採用しています。

Reciprocal Collaborative Filtering (RCF), a collaborative filtering based algorithm

Reciprocal Reciprocal recommendation System for Online Dating.(Xia 2015) で提案された手法です。こちらもその名の通り,協調フィルタリングベースのアルゴリズムです。「同じユーザから好意を受け取ったか」「同じユーザに対して好意を送ったか」などの複数の観点で過去の行動履歴からユーザ間の類似度を算出し,あるユーザと似ている上位 k 件のユーザの嗜好データをもとに,Preference Score を算出します (k近傍)。

こちらも Aggregation Function としては調和平均を採用しています。

Latent Factor Reciprocal Recommender (LFRR)

RecSys2019 にて私が実際に発表を聞いて RRSs に興味を持つきっかけとなった Latent Factor Models and Aggregation Operators for Collaborative Filtering in Reciprocal Recommender Systems (Neve 2019) で提案されている手法です。

従来の RSs では数々の研究がなされてきて実績のある Latent Factor Model(潜在因子モデル)を利用しようとのことで, Matrix Factorization を適用しています。データの特性から学習には SGD(Stochastic Gradient Descent; 確率的勾配降下法)を選択しています。

f:id:yu-ya4:20191211185406p:plain:w300
Figure 1 from (Neve 2019)

また, Aggregation Function にはこれまで調和平均ばかりが採用されていましたが,この研究では Aggregation Function の比較実験が行われました。

実験の結果,精度としてはこれまでの手法とほぼ変わらないかそれ以上で,計算量は大幅に改善されたため実際のサービス運用を考えた場合十分有用なものであるという結論でした。

おわりに

この記事では,私が最近関心を持っている Reciprocal Recommender Systems(相互推薦システム)についての紹介を行いました。 記事を読んでいて感じたかもしれませんが,RRSs 特有の様々な問題に対して現在提案されている手法は比較的ナイーブなものが多いです。 実は,私は現在 RRSs に当てはまるサービスの開発に携わっているのですが,企業でサービスを改善するエンジニアをしていてもまだまだ学術的にも価値のあることができるのではないかと可能性を感じてワクワクしています。

あまり RRSs の研究が盛んでない背景には,生の公開されているデータセットが少ないことが1つの要因としてあるのではないかと思っています。 私の知る限り,オープンなデータセットは RecSys Challenge 2017(http://www.recsyschallenge.com/2017/) で題材とされた,ヨーロッパで展開されているビジネス SNS である XING のものくらいではないでしょうか3。 RRSs に当てはまるサービスのデータはその性質上,非常にセンシティブなものが多いですしオープンにするには様々な障壁があるのですが,適切な形で研究が進められ,パートーナー探しにおいてもシゴト探しにおいてもより良いマッチングが実現できる世界になっていけばいいのになと個人的に思っています。

推薦システムについてもっといろいろとディスカッションしたいなどと思っていただいた方は, 毎週木曜日に社内有志で行っている以下の勉強会とかに参加していただけると嬉しいです。 Twitter などでご連絡いただけると嬉しいです!

github.com

Refs

  • (Pizzato 2010) Luiz Pizzato, Tomek Rej, Thomas Chung, Irena Koprinska, and Judy Kay. 2010. RECON: a reciprocal recommender for online dating. Proceedings of the fourth ACM conference on Recommender systems P. 207-214.
  • (Pizzato 2012) Luiz Pizzato, Tomasz Rej, Joshua Akehurst, Irena Koprinska, Kalina Yacef, and Judy Kay. 2012. Recommending people to people: the nature of reciprocal recommenders with a case study in online dating. User Model User-Adap Inter (2013) 23: 447.
  • (Xia 2015) Peng Xia, Benyuan Liu, Yizhou Sun, and Cindy Chen. 2015. Reciprocal Reciprocal recommendation System for Online Dating. Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining P. 234-241. 

  • (Neve 2019) J Neve, I Palomares.2019. Latent Factor Models and Aggregation Operators for Collaborative Filtering in Reciprocal Recommender Systems Proceedings of the 13th ACM Conference on Recommender Systems, 219-227.

  1. 性別に関する問題は難しいと認識していますが,ここでは問題を簡単にするため,サービス内のすべてのユーザが男性ユーザと女性ユーザに分かれていて相互に推薦されるという枠組みで捉えさせてください。

  2. 違ったら教えてください。m( )m

  3. 他に知っていたら教えてほしいです。