今回は、KDD 2018で発表されたCTR (Click Through Rate) 予測に関する論文 Deep Interest Network for Click-Through Rate Prediction を紹介したいと思います。CTR予測は、広義では注目している行動を起こす確率予測であるので、レコメンドに関する論文と捉えることもできます。なお、1週間前くらいに Machine learning papers reading pitch #3 というイベントで、ATRank というリコメンドの汎用的な方法論の論文について紹介しましたが（資料はこちら）、著者らの所属は同じAlibabaです。（ただ著者は全く違います）

なお自前で再実装したものは、以下にあります。

概要
従来手法
提案手法
実験
まとめ
参考文献

概要

ユーザーの過去の行動履歴と提示したい広告間の関連性を考慮して、ユーザーの興味・関心を表現するベクトルを適応的に算出する仕組みを提案
スパースな入力データから効率的に学習する方法を提案（こちらに関しては今回の紹介からは省いています）
Amazon・MovieLensのデータセット、Alibabaの実際のディスプレイ広告のログを用いたオフラインの実験における精度向上、Alibabaのディスプレイ広告システムにおけるオンラインのA/Bテストにおける効果向上を確認

従来手法

ここ数年では、CTR予測でもDeep Learningに基づく方法が提案されています。典型的なCTR予測は、以下のようなテーブルデータを対象としたクリックするかどうかの分類問題であるので、過去にこのブログでも紹介したEntity Embeddingような方法を用いてモデリング可能です。

f:id:pompom168:20190629214018p:plain

それでは特徴量として、ユーザーの行動履歴を使用する場合はどうでしょうか。例えば、行動履歴を広告のクリック履歴とすると以下のようなデータとなります。ユーザーの行動特徴量は可変長のリストです。

f:id:pompom168:20190629215745p:plain

行動履歴を扱っている研究、例えばYoutubeのリコメンドの研究 [Covington et al. 2016] では、以下のようなEntity Embeddingの拡張とも捉えられるネットワークを提案しています。（図は今回紹介しているDeep Interest Networkの論文から引用）

行動の数だけあるEmbeddingベクトルのリストに対して、要素ごとに和を取り1つのベクトルに変換します。そして、行動特徴量以外の特徴量に関するEmbeddingベクトルと結合して後は全結合層を続けます。ここまでが従来手法です。

f:id:pompom168:20190629221148p:plain

提案手法

従来手法の問題点

従来の [Covington et al. 2016] などの方法では、ユーザーの行動は固定長のベクトルに変換されます。表示したい広告に関係なくユーザーに対して固定のベクトルです。これでユーザーの行動からその興味・関心を表現するベクトルが作成されているでしょうか？

例えば、過去１週間で靴と水着を買ったユーザーにゴーグルの広告をリコメンドしてクリックされたとします。これは直感的には、”水着を買った”という行動に影響を受けてゴーグルの広告をクリックしたと考えられます。つまり、ユーザーの過去の行動の一部だけがその後のアクション（広告のクリック）に影響しているという仮説が立てられます。よって、ユーザーの行動を単一の固定長ベクトルに変換するだけでは、不十分であると考えられます。

Deep Interest Network

Attentionに着目し、表示したい候補の広告が与えられるとユーザーの過去の行動との関連性を考慮して、ユーザーの行動から興味・関心を表現するベクトルを適応的に算出します。ネットワークの構造は以下です。

f:id:pompom168:20190629223947p:plain

Source (key/value) がユーザーの行動履歴、Target (query) が候補の広告のAttentionを導入しています。これにより、広告ごとに過去の行動の中で注目する度合いを制御して、ユーザーと広告の組み合わせごとに興味・関心を表現するベクトルを生成できます。

以下に実例を示します。図中の矢印の上下にある画像が過去に購入した商品、矢印の右側の画像が候補の広告です。候補の広告が女性用のコートであり、過去の行動の中では女性用の服の重みが大きくなっていて、それ以外の重みが小さくなっています。

f:id:pompom168:20190629225134p:plain

LSTMなどでは駄目なのか？

ユーザーの行動履歴などの系列データを扱うなら、LSTMなどの方法がまず思い浮かぶでしょう。著者らも試してみたようですが、性能の向上は見られなかったようです。理由としては、自然言語処理のような文法規則の下にあるテキストデータなどとは違い、行動データはそういった制約があるわけでなくノイズだらけのデータと言えるからです。（これは自分の業務での経験とも一致しています。。）

定式化

最後に一応定式化もしておきます。

Feature Representation

特徴量 $i$ のエンコードされたベクトルを $t_i \in R^{K_i}$ で表現します。ここで $K_i$ は特徴量 $i$ の取り得る値の数です。

$t_i [ j ]$ は $t_i$ の $j$ 番目の要素であり、 $t_i [ j ] \in \left\{ 0, 1 \right\}$ です。 $\sum_{j=1}^{K_i} t_i [ j ] = k$ であり、one-hotエンコーディングのときは $k = 1$ で、multi-hotエンコーディング（行動履歴特徴量のようなリスト）のときは $k > 1$ です。

Embedding

特徴量 $t_i$ に対するEmbeddingの辞書を $W^i = \left[ w_1^i, ..., w_j^i, ..., w_{K_i}^i \right] \in R ^{D×K_i}$ とします。ここで、 $w_j^i \in R^D$ です。one-hotエンコーディングの場合、 $t_i$ のEmbeddingは $e_i = w_j^i$ となります。multi-hotエンコーディングの場合、 $t_i [ j ] = 1$ となる $j \in \left\{ i_1, i_2, ..., i_k \right\}$ とすると、 $t_i$ のEmbeddingは $\left\{ e _ {i_1}, e _ {i_2},..., e _ {i_k} \right\} = \left\{ w _ {i_1} ^i, w _ {i_2} ^i,..., w _ {i_k} ^i \right\}$ となります。

Pooling layer and Concat layer

行動の数がユーザーによって異なるので、multi-hotエンコーディングの $t_i$ における非ゼロの数が異なり、Embeddingのリストの長さはユーザーごとに可変です。全結合層に接続するために、行動履歴特徴量のEmbeddingのリストを固定長のベクトルに変換します。今回は、要素ごとに和をとるpoolingレイヤを介して固定長のベクトルに変換します。

$e _ i = pooling (e _ {i_1}, e _ {i_2}, ..., e _ {i_k} )$

最後に、 $e _ i$ とone-hotエンコーディングの $t_i$ に対するEmbeddingを結合して、1つの密ベクトルを得ます。

MLP

Poolingと結合によって得た密ベクトルを入力として、全結合層を続けます。

Loss

負の対数尤度を目的関数とします。

$\displaystyle L = - \frac{1}{N} \sum_{(x, y) \in S} (y \log p(x) + (1 - y) \log (1 - p(x)))$

$N$ は学習データセットのサンプルサイズ、 $S$ は学習データセットの集合、 $x$ は入力特徴量、 $y \in \left\{ 0, 1 \right\}$ は正解ラベル、 $p(x)$ はソフトマックス関数に通した後のネットワークの出力でありクリックされる確率です。

Local activation unit

Lossまでが従来のネットワークの定式化でした。

Deep Interest Networkでは、表示したい広告に応じてユーザーの行動履歴から興味・関心を表すベクトルを適応的に算出します。候補の広告 $A$ が与えられると、ユーザーの興味・関心ベクトルを $\nu_U$ は以下のように計算されます。

$\nu_U (A) = f (\nu_A, e_1, e_2, ..., e_H) = \sum_{j=1}^{H} a(e_j, \nu_A) e_j$

ここで、 $e_1, e_2, ..., e_H$ はユーザー $U$ の行動履歴特徴量のEmbeddingのリストで、 $\nu_A$ は広告 $A$ のEmbeddingです。 $a$ はAttention weightを出力する順伝搬のネットワークです（Deep Interest Networkの図における右上のActivation weightを出力しているネットワーク）。そして、 $a$ によって出力されるAttention weightとEmbeddingの積によって得られるベクトルを、行動履歴に渡って和をとることでユーザー興味・関心を表現するベクトルを広告ごとに適応的に獲得します。

実験

データセット

公開されているAmazonとMovieLensのデータセット、非公開のAlibanaのディスプレイ広告システムのログで実験を行っています。例えばAmazonのデータセットはユーザーの商品のレビューデータであり、特徴量としては商品ID、カテゴリID、過去にレビューした商品IDのリスト、カテゴリIDのリストがあります。過去の行動として、 $(b_1, b_2,...,b_k,...,b_n)$ があったとすると、k個の行動からk+1個目の行動を予測する問題です。n-2個までの行動を学習データセットとして、テストではn-1個までの行動が与えられたとき最後の行動を予測します。

f:id:pompom168:20190630000634p:plain

評価値

2つの評価値を用いています。

1つは以下の式で計算されるユーザーごとのAUCの平均です。nはユーザーの数、#impressionは広告の表示回数なのですが、普通にユーザーごとのサンプルサイズです。

f:id:pompom168:20190630001141p:plain

もう1つは、RelaImprというベースラインに対する相対的な改善度合いを表す指標です。今回のベースラインは、従来手法などで紹介した [Covington et al. 2016] などのモデリングです。

f:id:pompom168:20190630001039p:plain

結果

比較手法やハイパーパラメータなどは論文を参照ください。

上の画像がAmazonとMovieLensでの結果、下の画像がAlibabaのログの結果です。両者ともDINというのが今回紹介した方法の結果です。DINにwithがついているものは、今回の記事では紹介しなかった学習方法の工夫も行った結果を表しています。

全てのデータセットにおいて、提案しているDINが最も評価値が良くなっています。AmazonとMovieLensでは、Amazonの方が改善幅が大きくなっていますが、これはAmazonの方が行動データが豊富であり、こういった豊富な行動データがある場合は顕著に提案手法が有効であることが述べられています。

f:id:pompom168:20190630001823p:plain

f:id:pompom168:20190630001833p:plain

またオンラインのA/Bテストにおいても、最大でCTRが10%、収益が3.8%向上したそうです。地味に一番の驚きはこのモデルを実際に運用していることであり、ユーザーのアクセスごとに数百単位の広告に対して10ms以内の予測を行っているそうです。こういったことが出来るということが、Alibabaの強さのような気がします。。。

まとめ

Attentionを用いて、ユーザーの興味・関心を表現するベクトルを表示したい広告に応じて適応的に算出する仕組みを提案した、Deep Interest Networkの論文を紹介しました。また、自前での実装も行い公開しました。

参考文献

[Covington et al. 2016] Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommendations. In Proceedings of the 10th ACM Conference on Recommender Systems. ACM, 191–198, 2016

sola

【論文紹介】Deep Interest Network for Click-Through Rate Prediction

概要