はじめに

P-Companion: A Principled Framework for Diversified Complementary Product Recommendation というAmazonがCIKM2020に投稿した論文について解説します。

論文を選んだ動機

E-Commerceサイトの推薦では、ユーザーが見ている商品詳細ページに対して、以下2種類の商品を推薦することが多いです。

substitute: 現在見ている商品と代替関係にある商品
complementary: 現在見ている商品と合わせて買われるような商品, 機能を補完する商品
具体的にいいますと、例えば、現在テニスラケットを見ているユーザーに対して、substiture, complementaryは以下のようなものです。
substiture: 別ブランドのテニスラケット / 同一ブランドだが性能のことなるテニスラケットなど
complementary: テニスボール / テニスラケットバック / テニスウェア
substitureはユーザーが現在探している商品を素早く表示することに対して、complementaryはユーザーが認知していなかった商品を一緒に購入してもらうことができ、売上増加に繋がります。

substituteの論文は読む機会が多いのですが、complementaryはまだ知識が足りないため、complementary系の論文を探していたところ、この論文の手法が面白かったので読みました。

どんなもの?

「co-purchase(一緒に買われる商品)が、常に補完商品になる」という仮定が成り立たないことを示し、その上でECサイト上のログから適切な補完関係にある商品ペアを取得する方法を示した。
新しい補完商品推薦手法: P-Companionを提案。この手法では関連性だけでなく多様性も考慮している。さらに、GNNで商品情報（商品名など）から商品ベクトルを作成することで、ログの少ない商品に対する推薦も可能にした（Cold-Start問題）
real-world dataset(おそらくAmazonのログ)でオフライン実験しベースラインよりもHitRate@10を7.1%改善し、有意であることを確認した。さらに、Amazonの実際の環境でABテストを行い、売上・利益ともに有意(p-value < 0.05)に改善することができた。

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

本論文では以下のポイントを考慮しています。

補完関係のasymmetricを考慮
多様性を考慮した
Cold-Start問題に対応した
以下で上記のポイントを考慮する必要性について述べます。

補完関係のasymmetricを考慮する必要性

商品間の補完関係は非対称(asymmetric)です。
例えば、カメラを購入したいユーザーにとってSDカードを推薦すると同時に購入される可能性がありますが（=補完関係が成り立つ）、逆にSDカードを購入したいユーザーは、同時にカメラを購入するケースは少ないでしょう。それは、SDカードを持っている人はカメラをすでに持っている可能性が高いからです。また、SDカードはゲームなど他の機器と一緒に使うこともありそうです。
補完関係を通常に類似関係だと考えてモデリングすると、asymmetricを考慮することができません。考慮するためには明示的に機構を組み込む必要があります。

多様性を考慮する必要性

以下の図のように、あるユーザーがテニスラケットを求めてるときに(テニスラケット=query product)、List2のようにテニスボールをたくさん推薦する必要はありません。むしろ、テニスラケットと一緒に使われる可能性が高いカテゴリの商品を幅広くユーザーに提示し、選択肢を広げることが求められます。

Cold-Start問題に対応する必要性

補完関係を学習させる際は、ECサイトで同一session内で一緒に購入された商品ペア(co-purchase)をもとに教師あり学習させるのですが、そのようなログはわずかです。特に、substitureは同時に見られた商品ペア(co-view)を学習データに使用するのですが、それよりも遥かにデータ数が少なくなります。
そのため、あるquery productに対して、co-purchaseデータが紐づかないことは多くあり、その場合うまく商品推薦できないことが知られています。この問題をcold-start問題と呼びます。

既存手法との比較

既存手法は以下のように、上記で上げた3つすべてのポイントを考慮できていませんでした。

Sceptre: 商品レビューからトピックモデリング手法によって補完商品を推定する手法。レビューがついている商品であれば推薦可能だが、本論文の手法は商品名・商品カテゴリから推定するため、比較的cold-start問題の考慮は限定的。また、他のポイントの考慮はできていない
- [1506.08839] Inferring Networks of Substitutable and Complementary Products
PMSC: 商品間の関係を制約をモデリングした手法。商品からベクトルを得るときは、Sceptreと同様にレビュー情報を使用したよう。そのため、Cold-startの対応は限定的。ただし、商品感の関係を制約し、asymmetricを考慮することはできている。
- A Path-constrained Framework for Discriminating Substitutable and Complementary Products in E-commerce

技術や手法のキモはどこ?

商品間の関係をグラフで表現するBehavior-based Product Graphを作成
データセットをクリーニングし補完関係ペアデータからノイズを除去した
以下3つのモジュールを用いて、asymmetricや多様性、Cold-Start問題を考慮した手法: P-Companionを提案
- GNNを用いて商品をベクトルに変換するProduct2Vecモジュール
- 補完関係カテゴリを推定するComplementary Type Transitionモジュール
- 補完カテゴリから推薦商品を推定するComplementary Item Predictionモジュール

Behavior-based Product Graph

まず、ユーザー行動履歴から商品間にある以下3タイプの関係を定義します

データセットのクリーニング

先行研究では、co-purchaseのデータをもとに学習していたが、co-purchaseとco-viewには重なりがあることを発見しました。つまり、co-purchaseの中に代替関係の商品も混ざっていることです。本論文では、約2年間のco-purchaseとco-viewのデータを調査したところ、20%ほどがco-purchaseにもco-viewにも入っていた商品ペアでした。そのため、そのままco-purchaseを学習データに使用すると本来co-purchaseを学習させるモデルに対して、20%はco-viewを推定させることになり、学習がうまくいきません。

本論文ではデータセットのクリーニング方法を検討するため、MTurkで人手によりco-view, co-purchase, purchase-after-viewのペアにsubstitutable, complementary, irrelevant を推定させた。そうすると、以下のグラフ(以降補完関係グラフ)から得られるペアは補完関係であることが、co-purchaseのみよりも30%高いことがわかりました。

上記の結果、この論文では以下のデータが得られました

34.8Kのカテゴリから24M商品が得られ、80Mの補完商品ペアが得られた

P-Companion

P-Companionは以下の3つのモジュールからなります。それぞれモジュールにおいてタスクを解くことで、全体でquery productから補完関係商品群を取得できるようになります。

GNNを用いて商品をベクトルに変換するProduct2Vecモジュール
補完関係カテゴリを推定するComplementary Type Transitionモジュール
補完カテゴリからquery productの補完商品を推定するComplementary Item Predictionモジュール

Product2Vecモジュール

Product2Vecでは商品を類似商品が近傍に位置するような空間に射影します。つまり、商品間の類似性や機能を保持したベクトルを作成します。このモデルにより得られたベクトルが商品ベクトルとなります。

以下のグラフ(以降代替商品グラフ)がもっとも類似性を表していることがMTurkの回答からわかっています。

これらの関係で近傍にある商品間は、射影先の空間でも近傍に位置するように学習します。具体的には、代替商品グラフをもとに、GNNで近傍が近くなるような埋め込みベクトルを得るように学習します。

まず、３層のFNNで商品のcatalog情報をある空間に埋め込み、$p$ 次元の初期ベクトルを得ます。ここで、$C_i$ は商品　$i$ のcatalog情報です。FFNではなくBERTなど大規模な学習をしたモデルを用いても良いです。商品情報からベクトルを求めることで、Cold-Start問題に対応します。

上記で得られた初期ベクトルをGATにいれ、以下の代替商品のグラフの近傍から情報を集約して最終的な商品埋め込みベクトルを計算します。

FFNとGATは以下のcontrastive lossを最小化するように最適化します。以下では、positive sample: $N_i$ , label $y_i = 1$ を距離 $\lambda - \epsilon$ 以内に位置するように、negative sample: $\hat{N}_i$ , label: $y_i = -1$ を$\lambda + \epsilon$ より遠くに位置するように埋め込みベクトル $\theta$ を作成するように最適化しています。

ここで、positive sampleは代替商品グラフの近傍であり、negative sampleは補完商品グラフにおけるのquery productとの近傍商品になります。negative sample ration は1です。さらに、商品埋め込みベクトルは128次元であり、マージンパラメータは$\lambda=1.0$, $\epsilon=1.0$ です。

Product2Vecで得られたベクトルは後述のComplementary Item Predictionで使用します

Complementary Type Transitionモジュール

Complementary Type Transitionモジュールでは、query productのカテゴリから補完カテゴリを$K$個推定します。Complementary Type Transitionモジュールは更に以下を考慮します。

query productのcomplementary productのasymmetric
補完商品の多様性

まず、query product $i$ と、補完関係グラフの近傍 $j$ それぞれのカテゴリ $w_i, w_j$ をとります。asymmetricを表現するため、それぞれのカテゴリに対する埋込ベクトルは別空間のもの $\phi_i, \phi^c_j \in \mathbb{R}^L$ を取ります。この埋込ベクトルは学習対象です。つまり、カテゴリ→ベクトルへ変換する辞書をqueryカテゴリ用と補完カテゴリ用の2つ用意します。
$\phi_i$ をencoder-decoderに入れ、queryカテゴリの空間から補完カテゴリの空間へ変換し、$\gamma_{w_i}$ を得ます。ここで、$h$は$L/2$ 次元のベクトルです。

encoder-decoderおよび、埋込ベクトルは以下のcontrastive lossで最適化されます。

補完カテゴリからComplementary Item Predictionモジュールでそのカテゴリにあった商品を推薦します。そのため、Complementary Type Transitionモジュールで得られた $K$ 個のカテゴリそれぞれから補完商品 $M$ 個が得られるため、多様性をコントロールすることができ、$K$ を大きくすることで多様性のある補完商品推薦が可能です。

Complementary Item Predictionモジュール

Complementary Item Predictionモジュールでは、query productに対応する補完カテゴリからProduct2Vecの空間(商品粒度)へマッピングします。

まず、Complementary Type Transitionモジュールでquery カテゴリベクトルを変換して得られた補完カテゴリへ $\gamma_{w_i}$ において、近傍となる補完カテゴリベクトル $\phi^c_{w_c}$ を得ます。具体的には、以下のように、ユークリッド距離が $\beta$ 以下の補完カテゴリベクトルを取得します。距離ではなく、近傍 $K$ 個の補完カテゴリを取得しても良いです。
得られた$K$ 個の補完カテゴリそれぞれを、以下のようにitem transition NNに入力して補完商品を表すベクトル $\theta_i^{w_c}$ を取得します。

このitem transtion NNは、同様に以下のcontrastive lossをもとに最適化します。

Complementary Type TransitionモジュールとComplementary Item Predictionモジュールは連結して動作することを期待しているため、これらは同時に学習させます。

$\alpha$ はハイパーパラメータであり、調節項です。実験ではは、 $\alpha=0.8$ とし、positive label: $y_{i, j}= 1$ は頻繁にco-purchaseされる商品、negative label: $y_{i, j} = -1$ は代替商品グラフの近傍商品からサンプリングします。negative samplingの割合は1:1です。また、カテゴリの埋め込みベクトルの次元は $L=64$ で、ロスのbaseとmarginはそれぞれ $\lambda=1.0, \epsilon=1.0$ です。

どうやって有効だと検証した?

以下2つの方法でモデルの有効性を検証しました。

Offline Experiment: Amazon.comから収集したデータセットをもとに先行研究と比較。そして多様性を上げることと性能との関係とCase-StudyとしてCold-Start問題に着目した性能比較、および実際に推定された補完カテゴリペアについて取り上げた。
MTurk: MTurkで推薦商品ペアを人手で評価して性能を検証し、人手でも十分な性能を立証
Online Experiment: 実際にAmazon.comに提案手法をだし、ABテストで性能を検証し、売上・利益ともに有意に改善された。

Offline Experiment

Amazon.comから収集したデータセットをもとにオフライン実験を実施しました。10以上の商品カテゴリからなる商品数24Mのデータセットです。これらのデータセットの全カテゴリと、Electornics, Groceryそれぞれの範囲でquery productをサンプリングしモデルを評価しました。

既存研究は以下の3つを上げています

Sceptre: 商品レビューからトピックモデリング手法によって補完商品を推定する手法
PMSC: 商品間の関係を制約をモデリングした手法
JOIE: Knowlege gprah emneddingに対する手法。本実験では、BPG部分にこの手法を適用したよう。
- It is designed for two-view knowledge graph embedding learning. We adapt JOIE to item-type views in BPG instead of entity-concept views in KG for complementary recommendation
- Universal Representation Learning of Knowledge Bases by Jointly Embedding Instances and Ontological Concepts | Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining
  評価方法は、平均Hit Rate@kを採用しました。top-k以内に正解商品がある割合を評価します。また、商品(Item)単位だけでなく、JOIEとP-Companionに関してはType(カテゴリ)予測をするため、Type単位のHitr Rateも計算した。

既存研究との比較は以下の通りで、P-Companionが先行研究と同等かそれ以上の性能が示されています。これらの性能差について、筆者は以下の2点が原因だと述べています。

P-Comapnionは直接補完商品を推定せず、まず補完カテゴリを推定する。その補完カテゴリは機能の抽象概念として考えられ、補完カテゴリの選定がより正確な推薦につながった。
補完関係をモデリングする際、P-Companionは多様性を考慮しており、複数の部分空間で補完商品を推定した。これにより、商品カテゴリ間の希釈や汚染を避けた。

さらに、多様性を検証するため補完商品選定時に使用する補完カテゴリ候補数$K$ を1, 3, 5, 6にに変化させたときの性能差を調べました。以下のテーブルから、多様性をもたせることが性能改善につながることがわかります。

続いて、Cold-Startの対応について調べました。co-purchaseの実績数が2未満であるquery productに対して、補完商品推薦をしたところ先行研究との比較結果は以下の通りとなり、P-Companionの性能が良いことを示しています。

さらに実際の商品推薦例は以下の通りとなっており、どのquery productに対しても意味のあった補完商品を推薦することができています。

そして、補完カテゴリ予測は以下のとおりであり、違和感はありません。さらに、これらのカテゴリをもとに候補商品を選定することで、特定のカテゴリによらず多様な商品推薦ができます。

MTurk

ユーザーの行動履歴だけでなく、人手による評価をおこないました。具体的には、MTurkでquery productと推薦商品のペアを見せ、以下の質問をしました。

query productを購入した場合に推薦商品を一緒に買うかどうか
5人のユーザーに対して3段階評価をしてもらました。結果は以下の通りです。ここで、Co-Purchaseは実際のAmazomn.comの行動履歴から収集した補完商品ペアです。テーブルから、P-Companionはtop-3の補完カテゴリそれぞれにおいて、実際に発生したペアとほぼ同等の評価を得ることができていることがわかります。つまり、P-Companionは多様な補完カテゴリから、さらに正確な補完商品を推薦できていることが分かります。

Online Experiment

Amazon.com において、2week A/Bテストを実施して提案手法の有効性を検証した。
sessionをランダムに振り分け、controlグループには過去に一緒に購入された商品を推薦する: Co-Purchaseを提示し、treatmentグループにはP-Companionで選定した商品を推薦した。
その結果、0.23%売上が向上し、0.18%の利益が改善した。これらはp-value < 0.05 であり、有意差がある結果だった。つまり、P-Companionはユーザーの購買体験を改善し、ユーザーの潜在的なニーズを満たすことができたことが示された。

議論はある?

補完商品はユーザーに応じて変化するため、パーソナライズすべきだろう。例えば、以前カメラを購入したユーザーがSDカードを見ているときにはカメラレンズや三脚を補完商品に表示しても良いが、カメラではなくゲーム機を購入したユーザーに対してはゲームソフトやコントローラーを推薦したほうが良いと考えられる。
推論時はまずquery productの補完カテゴリを近傍探索し、その後そのカテゴリにおける補完商品を近傍探索する。この二段階の処理は直列であるため、推論に時間がかかる。もしこの手法をベースにパーソナライズを検討するとリアルタイムに推論させるとなると速度が懸念である。

次読むべき論文は?

Personalized complementary product recommendation - Amazon Science
- 同じくAmazonの研究であり、この研究の後継。本手法をベースにパーソナライズすることで性能が改善したとのこと
- 解説記事を書きました → 論文解説: Personalized Complementary Product Recommendation
BLADE: Biased neighborhood sampling based graph neural network for directed graphs - Amazon Science
- asymmetricをロスに組み込むことで性能が改善したという手法
- 上記論文を紹介したAmazonのテックブログ: Biased graph sampling for better related-product recommendation - Amazon Science
- おそらく以下の論文をブラッシュアップしたものがBLADE。論文名は異なるが、著者が同じで公開日が早い。しかし、以下の論文のほうが補完商品推薦に専念していそう
  - [2211.11583] Recommending Related Products Using Graph Neural Networks in Directed Graphs
  - 上記論文を紹介したAmazonのテックブログ: Using graph neural networks to recommend related products - Amazon Science
Enhanced Multi-Relationships Integration Graph Convolutional Network for Inferring Substitutable and Complementary Items | Proceedings of the AAAI Conference on Artificial Intelligence
- 補完関係だけでなく、代替関係も同時にモデリングする手法。

まとめ

P-Companionと呼ばれる補完商品推薦の論文を紹介しました。
P-Companionでは、補完関係のasymmetricやCold-Start問題、多様性まで考慮することができます。この手法では以下3つのモジュールから構成されています。
- GNNを用いて商品をベクトルに変換するProduct2Vecモジュール
- 補完関係カテゴリを推定するComplementary Type Transitionモジュール
- 補完カテゴリから推薦商品を推定するComplementary Item Predictionモジュール
本論文ではオフライン実験だけでなく、人手による評価やA/Bテスト評価など様々な観点からP-Companionを評価しており、どの観点からでもP-Companionが既存手法よりも優れていることが分かりました。