【論文解説】 Personalized Complementary Product Recommendation

# はじめに

- 出典: WWW 2022

Personalized Complementary Product RecommendationというAmazonがWWW2022に投稿したshort論文を紹介します。

https://www.amazon.science/publications/personalized-complementary-product-recommendation

# 論文を選んだ動機
E-Commerceサイトの推薦では、ユーザーが見ている商品の代替商品だけでなく、一緒に買われる補完商品の推定も重要な分野です。[^1]

補完商品を推定する際は、ユーザーの情報を考慮することで性能があがることが考えられます。例えば、以前カメラを購入したユーザーがSDカードを見ているときにはカメラレンズや三脚を補完商品に表示しても良いでしょう。一方で、カメラではなくゲーム機を購入したユーザーに対しては、ゲームソフトやコントローラーを推薦したほうが良さそうです。つまり、ユーザーに応じて推薦する補完商品を変えることができる手法が望ましいです。

本論文では、ユーザーの購入履歴をもとに補完商品を推定する手法を提案しているため、気になって読みました。
# どんなもの?

- ユーザーの好みを考慮して推薦する補完商品を選定する問題設定。例えば、以下のようにあるユーザーがピンクが好きであればピンクの商品を、以前アダプターを購入していればノートPCスタンドを推薦したい。
- 本論文では先行研究をベースに、ユーザーの過去の購入履歴系列をTransformerでエンコードしたユーザー情報を取り入れることで、ユーザーの興味を考慮した補完商品推薦を実現
- ユーザー情報は候補商品を選定した後の部分のre-rankingモジュールで使用
- (おそらくAmazon.comから収集した)ECサイトのデータセットを用いたオフライン実験で、ユーザー情報を取り入れることの有効性を検証し、ユーザー情報なしと比べて大きく性能が改善された。

![figure_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/200359/43a959e5-1a75-ca5c-a010-0d6dd78d1449.png)

# 先行研究と比べてどこがすごい?

補完商品の先行研究として以下が挙げられる。
- CIKM2020  [Decoupled Graph Convolution Network for Inferring Substitutable and Complementary Items | Proceedings of the 29th ACM International Conference on Information & Knowledge Management](https://dl.acm.org/doi/10.1145/3340531.3412695)
	- 代替商品と補完商品を分けながら同時に学習するHeterogeneous Graph NN手法を提案。代替商品と補完商品を同時に扱うことで、相互影響を考慮することができる
- CIKM2020 [P-Companion | Proceedings of the 29th ACM International Conference on Information & Knowledge Management](https://dl.acm.org/doi/abs/10.1145/3340531.3412732)
	- 多様性とasymmetric, Cold-Startを考慮した論文。本論文のベース手法を提案している論文
	- 論文を解説した記事を以前出しました, [論文解説: P-Companion: A Principled Framework for Diversified Complementary Product Recommendation #MachineLearning - Qiita](https://qiita.com/haru-256/items/7ea7597b61a43f396061)
上記手法ではユーザー情報を考慮していなかった。本手法では、ユーザー情報を取り入れてパーソナライズされた商品推薦が可能になる。実験では、上記先行研究と直接比較していないが、ユーザー情報を考慮しない場合よりも性能が改善された。
# 技術や手法のキモはどこ?
提案手法は以下の3つの部分に分かれている。この中でユーザー情報を考慮するUser Behavior ModelingモジュールとPersonalized Re-Rankingモジュール部分がキモになる。
- 商品埋め込み表現を獲得するモジュール
	- Graph Attention Networkをもちいて、商品をあるベクトルで表現する。query productの近傍 $K$ 個の商品が補完商品推薦候補となる。
- User Behavior Modelingモジュール
	- ユーザーの購買商品系列をTransformerでencodingし、ユーザー情報を表す埋め込みベクトルを取得。
- Personalized Re-Rankingモジュール
	- query product ベクトル（ユーザーが現在見ている商品）と、推薦候補商品ベクトル, ユーザーベクトルを統合し、query productを見ているユーザーが推薦候補を購入するかどうかを推定する。

![figure_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/200359/6f5abeb6-83cf-df7e-6a00-ad52de4a7cce.png)

## 商品埋め込み表現を獲得するモジュール(GAT)

まず商品情報 $T$ をFNN(+ batch normalization)のuniversal embedding module $\phi(\cdot)$ をもちいて初期ベクトル $\hat{\theta}$ に変換する。商品情報には商品名やレビューなどを採用する。

![equation_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/200359/d9ff8211-7ff6-dd63-e14d-1adc0ba6d497.png)

その後、初期ベクトル $\hat{\theta}$ をGraph Attention Neural Network に入力し、近傍商品の情報を集約して商品ベクトル $\theta$ を取得する。

:::note warn
このとき使用するグラフをどう作るかは論文に記載がありませんでした。おそらく、商品 $i$ に対して補完関係にある商品を、 $i$ の近傍となるように作成したグラフだと思われます。補完関係ラベルの作り方についても記載はありませんでしたが、本論文と同じくAmazonから出ている先行研究 [P-Companion](https://dl.acm.org/doi/abs/10.1145/3340531.3412732) に基づいている可能性が高いです。
:::

universal embedding moduleとGATは、以下のロスを下に最適化される。ここで、$y={+1, -1}$ はそれぞれ $\theta_{+i}, \theta_{-i}$ に対応しており、商品 $i$ に対するpositiveとnegative商品です。つまり、positive商品については$i$ と $\lambda - \epsilon$ の距離以内に位置するように、negative商品は $\lambda + \epsilon$ より遠くに位置するように商品を埋め込むように学習する。
![equation_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/200359/f9da608e-cfdc-2ba3-8b5b-7a0842fcd8d3.png)


:::note warn
上記のロスでは $\hat{\theta}_i$ と記載されていますが、正しくはおそらくGATが出力した商品情報ベクトル $\theta_i$ のことだと思います。また、positiveとnegativeは論文に記載はありませんでしたが、positiveは商品 $i$ と補完関係にある商品、negativeはそれ以外だと思われます。ここのnegative samplingも先行研究 [P-Companion](https://dl.acm.org/doi/abs/10.1145/3340531.3412732) に基づいていそうです。
:::

推論時は、query product $i$ をこのモジュールでベクトルに変換し、そのベクトルと近傍にある商品 top-k を推薦候補商品として後述のre-rankingモジュールに入力する。

## User Behavior Modelingモジュール

User Behavior Modelingモジュールでは、ユーザーから埋め込みベクトルを作成します。まず、ユーザーが直近購入した商品の系列 $P= \{p_1, \dots, p_n\}$ を取得し、それぞれの商品を先程のuniversal embedding module $\phi(\cdot)$ で初期ベクトル $T = \{t_1, \dots, t_n\}$ に変換します。そして、それらの系列をTransformer Encoderに入力しユーザーのembeddingベクトルを得ます。

![equation_4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/200359/640e5a22-5bd3-4c5a-eb5a-233791264072.png)


このTransformer Encoderは、次のPersonalized Re-Rankingモジュールのロスで最適化されます。
## Personalized Re-Rankingモジュール
Personalized Re-Rankingモジュールでは、GATで選択した $K$ 個の候補商品を、User Behavior Modelingモジュールで抽出したユーザーベクトルをもとにrerankingします。これにより、ユーザーの好みを考慮した補完商品を推薦します。
具体的には、GATで得られた候補商品のベクトル $\theta_i$ をユーザーベクトル $u$ で重み付けしたベクトル $\theta_i \odot u$ に変換し、それらとの距離をもとにre-rankingします。学習時は、以下のロスをもとに最適化します。ここで、 $+c$ は 商品 $i$ と同一session内で購入した商品(=補完商品)であり、 $-c$ はそれ以外のランダムに選択されたnegative sampleです。

![equation_5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/200359/f0e485eb-94c1-159d-5177-120deed32057.png)


## Contrastive Learning
User Behavior Modelingモジュールは式(5)をもとに最適化しますが、それだけでは学習が不安定で性能が向上しません。それは、商品数に比べてユーザー数のほうが少なく、スパースのためです。そこで本論文ではcontrastive learningによる補助学習を行います。
まず、ユーザーが直近購入した商品の系列 $P= \{p_1, \dots, p_n\}$ をもとに、それらをランダムに並び替えたり、croppingするなどし、2つの別系列 $P_1, P_2$ を作成します。そしてこれらの系列からTransformerでそれぞれ $u_1, u_2$ というユーザーベクトルを得ます。contrastive learningではこれらの拡張したベクトルが類似しているように学習します。具体的には、以下のロスを最適化するように学習します。

![equation_6.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/200359/6cbf7c9e-ed90-97b6-3ade-23e2b0352c7c.png)


ここで、$S^{-}$ はnegative sampleであり同一バッチ内から選択されます (いわゆるin-batch negative sampling)。
## 統合学習

これら3つのモジュールは個々に学習するのではなく、個々のロスを線形結合した以下のロスで同時に学習します。 $\lambda_1, \lambda_2$ は調整項です。

![equation_7.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/200359/0a3f5f8b-08a6-658c-64ee-5aaf24c2d9c0.png)

# どうやって有効だと検証した?
以下のように実験し提案手法の有効性を検証しました。
- (おそらくAmazon.comで収集した)データセットに対して提案手法と、ユーザー情報を考慮していない単なるGATによる性能比較をOffline実験で確認しました。その結果提案手法の性能が良いことが示さました。
- また、Re-rankingする候補商品数の変化と商品・ユーザーそれぞれの埋め込みベクトルを作成するときに使用する特徴量とスコアの関係性を調査しました。Re-rankingする候補商品数を変化させても性能は変わらず、また商品・ユーザーそれぞれにおいてよりリッチな情報を入れることで性能が改善されました。
- さらに、ユーザ情報を考慮した場合としなかった場合の推薦商品の定性評価をおこない、定性的にも有効であることを確認しました。

:::note warn
先行研究との比較はありませんでした。
:::

## データセットと評価方法
データセットについてです。まずランダムにユーザーを10,000人選定し、そのユーザーが2020年6月から11月までの間に、同一session内で併売したsessionを収集します。また、先月からの購買履歴(2020年5月からのもの)をUser Behavior Modelingモジュールの入力系列としました。そして、10,000人のユーザーをランダムに8K/1K/1Kに分割しそれぞれ学習・検証・テストデータとしました。

評価はtop-kのHit Rateを使用しています。つまり、query productに対して得られたtop-kの推薦商品内にユーザーが併売した商品が含まれる割合を評価指標としています
## 定量評価
上記データセットにおける評価結果が以下のとおりです。
![table_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/200359/d06b3710-87d6-8f9f-18b2-9546b002d46e.png)


提案手法に加えて、以下4つの手法と比較しています。
- GAT: ユーザー情報を考慮しない手法
- Projection: 式(5)でアダマール積の代わりにユーザーベクトルと商品ベクトルを単に結合したもの
- GAT + Avg: ユーザーの購買履歴の商品埋込ベクトル系列を、単に平均化したベクトルをユーザーベクトルとしたもの
- GAT + Trans: ユーザーの購買履歴の商品埋込ベクトル系列をTransfomerでエンコーディングするが、contrastive learningによる補助学習はしないもの
テーブル1を見ると、提案手法が最もよく、最低でも10%程度性能が改善されたことが分かります。また、GAT vs 提案手法でユーザー情報を考慮することで性能が大きく改善していることが分かります。更に、GAT + Avg vs GAT + Trans でユーザーの購買系列の順番を考慮してエンコーディングすることの重要性が分かります。

:::note warn
GATは先行研究 [P-Companion](https://dl.acm.org/doi/abs/10.1145/3340531.3412732) と同様のモジュールを使用したと記載していますが、P-Companionは単に商品をGATでembeddingしただけでなく、他にも多くのモジュールが存在しています。そのため、ここでGATと呼んでいるものがP-Companion手法と同等なのか、単に商品をGATでベクトルに変換してその近傍商品を推薦する手法なのかはよくわかりません。
:::

:::note warn
上記でProjectionと記載されている手法は、式(5)でアダマール積の代わりにユーザーベクトルと商品ベクトルを単に結合したものと記載がありますが、それでは $[u, \theta_i]$ と $[u, \theta_{\pm c}]$ のユークリッド距離をみることになり、ユーザーごとに並びが変化しないのではと疑問に思っています。
:::

:::note info
GAT vs GAT + Avg をみるとユーザー情報を考慮しないGATのほうが性能が高いです。これはユーザー情報を適当に入れてしまうとかえって性能が悪くなるということです。実際にユーザー情報をといれるときは、まずはベースラインとしてユーザー情報を取り入れない手法の結果を見るべきだろうと感じました。
:::

## Re-rankingする候補商品とHit Rateの関係
Re-rankingする候補商品数(Re-rankingサイズ)とHit rateの関係を調査しました。
実験結果は以下の通りです。若干ですが候補商品数は少ないほど性能が良さそうです。しかし、あまりRe-rankingサイズで性能は変わりませんでした。
![figure_3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/200359/59a727ad-d205-d79c-8f4a-404169207b09.png)


:::note warn
提案手法はユーザー情報をRe-ranking stageで考慮しているため、候補商品数の変化は性能に大きく影響するだろうと考えていました。というのも、候補商品の中にユーザーの好みとマッチする商品が含まれなければ性能が向上しないためです。しかし、実験結果を見るとあまり候補商品数で性能が改善されず、疑問に思っています。
:::

## 商品とユーザーそれぞれのベクトルを取得するときに使用する特徴量とHit Rateの関係
GATによる商品ベクトルとTransformerによるユーザーベクトルを得るときに、それぞれに入力する特徴量とHit Rateの関係を調べました。調査結果はテーブル2のとおりです。
![table_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/200359/9ee361c9-0a69-0633-c401-fccf9bb93bdc.png)


まず、商品ベクトルは以下3つを試しています。
- one-hot: 商品カテゴリのone-hot encodingを入力にする。そのため、汎化性能はあまりない。
- BERT: 事前学習済みのBERTモデルに商品タイトルを入力して得られた商品ベクトル
- BERT + R: BERTで得られたベクトルに加え、reviewのスコアや価格、ブランドなどの商品情報を入力したもの

そして、ユーザーベクトルでは以下3つを試しています。
- Demo: サイトの滞在時間や購買頻度などの静的なユーザーのデモグラフィック情報
- Pur: ユーザーの購買商品の系列
- Pur + Demo: ユーザーの購買商品の系列に加えて、ユーザーのデモグラフィック情報
テーブル2の結果から、リッチな情報を入れることでより性能が改善することが分かりました。

## 定性評価

実際にユーザー情報に応じて推薦商品がどのように変わるかの定性評価を行いました。以下では、修正テープを見ているユーザーに対して、商品情報を考慮しない場合とした場合それぞれの推薦商品を出しています。

![figure_4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/200359/1cdc7e21-8ab8-559e-08be-aa65b18214f0.png)


ユーザー情報を考慮しない場合はコピー用紙や紙を多く推薦しています。対して、商品情報を考慮した場合は紙は出てきていません。これは、ユーザーが直近紙を購入したためです。よって、ユーザー情報を考慮することで、すでに購入されている商品は推薦しないことができており、ユーザー情報を考慮することができていそうです。

:::note info
上のユーザー情報を考慮しない推薦例はさほど悪くないのではと感じました。ユーザーが直近1-2日で用紙を買っているのであれば用紙はまだあるため必要ないですが、かなり前であれば推薦しても良さそうに感じました。
:::

# 議論はある?

- 提案手法はリランキング部分でユーザー情報を考慮していますが、候補商品選定段階でもユーザー情報を考慮すると良いのではと考えています。というのも、ユーザーに応じてquery productに対する補完商品カテゴリが変わると考えています。そのため、候補商品選定段階でユーザー情報を考慮しなければ、リランキング時にユーザーが求めている商品が少なくリランキングする余地があまりない可能性があります。
# 次読むべき論文は?
- [BLADE: Biased neighborhood sampling based graph neural network for directed graphs - Amazon Science](https://www.amazon.science/publications/blade-biased-neighborhood-sampling-based-graph-neural-network-for-directed-graphs)
	- asymmetricをロスに組み込むことで性能が改善したという手法
	- 上記論文を紹介したAmazonのテックブログ: [Biased graph sampling for better related-product recommendation - Amazon Science](https://www.amazon.science/blog/biased-graph-sampling-for-better-related-product-recommendation)
	- おそらく以下の論文をブラッシュアップしたものがBLADE。論文名は異なるが、著者が同じで公開日が早い。しかし、以下の論文のほうが補完商品推薦に専念していそう
		- [[2211.11583] Recommending Related Products Using Graph Neural Networks in Directed Graphs](https://arxiv.org/abs/2211.11583)
		- 上記論文を紹介したAmazonのテックブログ:  [Using graph neural networks to recommend related products - Amazon Science](https://www.amazon.science/blog/using-graph-neural-networks-to-recommend-related-products)
- [Enhanced Multi-Relationships Integration Graph Convolutional Network for Inferring Substitutable and Complementary Items | Proceedings of the AAAI Conference on Artificial Intelligence](https://ojs.aaai.org/index.php/AAAI/article/view/25532)
	- 補完関係だけでなく、代替関係も同時にモデリングする手法。
# まとめ
- ユーザー情報を考慮した補完商品推薦の論文を紹介しました。
-  提案手法は以下の3つのモジュールから構成され、購買履歴からユーザー情報を抽出し、リランキング部分で推薦商品をパーソナライズしています。
	- 商品埋め込み表現を獲得するモジュール: GATで商品をベクトルで表現する
	- User Behavior Modelingモジュール: ユーザーの購買商品系列をTransformerでencodingし、ユーザー情報を表す埋め込みベクトルを取得。
	- Personalized Re-Rankingモジュール: query product ベクトルと、推薦候補商品ベクトル, ユーザーベクトルを統合し、ユーザーに応じて推薦商品の並びを変える。
- オフライン実験でユーザー情報を考慮することの有効性を検証しました。

[^1]: 具体例は[以前の記事](https://qiita.com/haru-256/items/7ea7597b61a43f396061#%E8%AB%96%E6%96%87%E3%82%92%E9%81%B8%E3%82%93%E3%81%A0%E5%8B%95%E6%A9%9F)に記載しています。