タイトルの論文を読んでみたので、内容に関する雑なメモです。
tl;dr;
- レコメンド機能を実装する際にユーザーをEmbeddingを使用して表現することがあるが、多くの場合1つのEmbeddingを使用していた
- 複数のEmbeddingを使用してユーザーの興味を表現することで推薦の精度を改善した
論文
著者
Aditya Pal, Chantat Eksombatchai, Yitong Zhou, Bo Zhao, Charles Rosenberg, Jure Leskovec (Pinterest Inc.)
背景
Pinterest (月間3億5000万アクティブユーザー、20億のビジュアルブックマークがなされる)では、推薦は非常に重要な機能と言えます。具体的には、
- ホーム画面のフィードのアイテム
- eコマースサイトへリンクする商品推薦
- 検索結果表示
- 広告
- pinボード
などで推薦機能は活用されており、ユーザーとアイテムの数が膨大なことからも重要になっているようです。 特にパーソナライズを行うことが重要となり、これにはユーザーに関する潜在表現が重要になっています。
このような場合にembeddingが使用されることがあるかと思いますが、ユーザーは複数の興味関心を持っているのに対し、アイテムに関してはembeddingは1つの側面を表現していると考えられるため、何らかのアプローチが必要と考えているようです。
Embeddingに関する考え方
この仕組みの肝になってくるのは推薦に使用するEmbeddingの考え方だと思いますので、そのへんを中心に整理します。
問題意識
従来研究の多くが、concatするなどしてEmbeddingを単一にしていました。 これは、大きく異なるトピックであっても空間内で距離が近づいてしまう恐れをはらんでいます。
また、ユーザーの興味関心は複数に渡ることが考えられますが、それらを単純に足し合わせるだけでは全く異なるトピックにたどり着いてしまうことも考えられます。
複数のEmbeddingを使う
ユーザーを表現するために複数のEmbeddingを使うアプローチも過去にありますが、その多くはEmbeddingの種類を固定するかEmbeddingの種類に上限を設けるようなアプローチになっていたようです。 つまり、ユーザーの興味関心の数がわからない以上、そのトピックを固定あるいはキャップすることになり、適切にユーザーを表現できないと考えられます。
実際、あるユーザーの閲覧履歴に関して、画像の種類とpinのEmbeddingのコサイン類似度を見るとそれほど相関がないことがわかり、ユーザーは複数の興味関心を持っており、それらを統合して考えることは難しそうに思われます。
そこでEmbedding自体を、凝集型階層的クラスタリングward法で分類することでトピックの異なるEmbeddingを区別することを考えます。 これによってEmbeddingをトピックごとに分割します。
ユーザーEmbeddingの求め方
いま、ユーザーのアクション（ここではpinを打ったりクリックしたりする情報）が時系列的に得られているとし、個別のpinにはすでに Embeddingが計算されているとします。*1
ユーザーのアクションとpinのEmbeddingを使って、ユーザーの次にアクションを起こす対象のEmbeddingが予測できれば良さそうです。 そのEmbeddingを求められれば、それをユーザーのEmbeddingと考えることでそのの近傍探索によって興味関心のあるpinを探索できると考えられます。
ここで、ユーザーの過去の行動のEmbeddingを教師なし分類することを考えます。 今回はk-means（k=3）で分類することを考えると、最新のユーザーアクションの対象のpinのembeddingをユーザーEmbeddingとしたときに比べて98%精度が向上したそうです。
時間的局所性
また、ユーザーの興味関心は時間とともに変化するものと考えられます。 ユーザーの最新の興味関心は時間的に新しい部分のEmbeddingを、長期的な興味関心を正しく把握するためには過去60-90日を考慮したEmbeddingを使用することが望ましいと考えられます。
推薦の際にもこれらを組み合わせて考えることが望ましいと考えられます。
PinnerSage
動作
ユーザーEmbeddingの算出の流れとしては、大まかに下記のような流れになっているようです。
- 過去90日間のユーザーのアクションピンを少数のクラスターに分類
- 各クラスタに対してメドイドベースの表現を計算
- 各クラスタのユーザにとっての重要度スコアを計算
アクションピンを少数のクラスターに分類
ユーザーのアクションに関するpinに関して、Ward法を使用した階層化クラスタリングによって分類しているようです。 K-means等も検証したそうですが、今回のケースではベンチマークがこちらの方が良かったようです。
メドイドベースの表現を計算
次にクラスタを表現するEmbeddingを計算しています。 クラスタに含まれるpin Embedding を使用して、LSTM等の複雑なモデルで計算しても良いのですが、それだと推定されたEmbeddingが空間上でクラスタから離れたところに行ってしまう恐れがあります。
そんなわけもあって、メドイドを使用してクラスタのEmbeddingを計算しています。 クラスタを構成する各要素からの距離が最小になるような"代表pin"を求め、それをクラスタのEmbeddingとしているようです。
重要度スコアを計算
最後にユーザーにとってのクラスタの重要度を計算します。
上記のように時間が近い方が優先されるように算出されます。
システム構成
実際の仕組みについて確認します。 構成としては下記のようになっているようです。
オンライン推論としては、ANN（Approximate Nearest Neighbor）検索を使用して動作しているようです。 index schemeとしてHNSWが一番うまくいったと書かれているんですが、この辺あんまり良く分かってないです…
推薦候補のアイテムについては、多数の重複するアイテムが存在しています。 また、一部品質の低いもの（大量のテキスト、画像の解像度が低いなど）もあり、推薦に適していないものもあります。 それらは別のモデルを使用してフィルタリングすることで、対応しています。
Searving
過去90日間のデータを収集して行う計算については、デイリーのMapReduceのバッチ処理によって計算しています。 一方、直近20件のアクションについてはイベントベースのストリーミングを使用して収集し、オンラインで処理して推論に使用します。
評価
A/Bテスト
ランダムに実験群と対照群に分けて検証した結果が下記の表らしいです。
クリックとpinの総量(Volume)、ユーザーのエンゲージメント率(Propensity)ともに向上していることが確認できます。
オフラインテスト
推薦のアイテムの収集に関する評価結果は下記の表のようになっています。
ここで
- Rel：観測されたアクションピンのうち、推薦ピンとのコサイン類似度が高い(0.8以上)ものの割合
- Recall：推薦セットの中で発見されたアクションピンの割合
となっています。 Ward法かつimportanceの係数が0.01(大きすぎも小さすぎもない)値が最も評価が良くなっています。
次に、ランキングに関する評価は下記の表の様になっています。
ここで
- R-Prec：top-kのうち実際にアクションされたものの割合
- Rec. Rank : ランキング上位に実際にアクションされたものが含まれていた割合
となっています。 ここでも、提案手法が良い評価となっていることが確認できます。
感想
ユーザーをどう表現するかという点について考察された論文でした。 推薦のアイテムのトピックが多岐に渡る際には、ユーザーを多面的に捉えるために複数のEmbedding で表現したほうが良いかもしれない、という感じですかね。
興味深い論文でした。
