Gunosyデータ分析ブログ

Gunosyで働くデータエンジニアが知見を共有するブログです。

DeepなFactorization Machinesの最新動向 (2018)

はじめに

こんにちは。研究開発チームの関です。 最近毎週日曜日の恋するワンピースの更新を楽しみに生きています。好きなツッコミは「この船の航海士は誰？」です。 あと虹のコンキスタドールのベストアルバム「THE BEST OF RAINBOW」は皆さん買いましたか？ 健康にいいので毎日聞きましょう。

この記事はGunosy Advent Calendar 2018の22日目の記事です。 昨日はcou_zさんの「【年末年始に読みたい】Gunosyエンジニアが2018年に購入した書籍まとめ」でした。

皆さんFactorization Machinesは好きですよね。 予測モデル構築においてはXGBoostと並んでとりあえずやっておくべき手法として知られています。 今回のエントリではKDD2018で発表されたxDeepFMを読み解きながら、 DeepなFactorization Machineの現状について、特にネットワークアーキテクチャの発展を中心に見ていきたいと思います。

f:id:Y_sekky:20181222151016p:plain

Factorization Machines [Rendle, ICDM2010]とは

Factorization Machines (FM)は特徴量の交互作用をうまく計算できるモデルです。 例えば年齢を表す特徴量と、性別を表す特徴量があった場合、10代の男性というAND条件の特徴を年齢と性別の交互作用で表現します。 すべての交互作用について学習をしようとすると、重みの数が著しく増えますし、対応する学習データの数も少なくなります。困りますね。 そこでFactorization Machinesです。交互作用の重みを各特徴量に対応するベクトルの内積で表現することでやっていくことにしています。 具体的には以下の式ですね。

{ \displaystyle \hat{y}(\boldsymbol{x}) := w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle \boldsymbol{p_i}, \boldsymbol{p_j} \rangle x_i x_j}

FMといえばこの定義ですが、正確にはこれは2nd-order Factorization Machinesです。 なにが2nd-orderなのかといえば、変数の交互作用が x_i x_jと2つの変数となっています。 これが2次の交互作用なので2nd-orderです。理想的にはすべての変数に対して交互作用が存在する気がしますが、高次になると計算が大変で難しいです。

また最近では現実的に解けるHigh-OrderなFMも提案されていますが、高次にしても3次ぐらいまでしか精度が上がっていかないみたいです。 これはデータに潜在的に存在するノイズの原因で高次の学習はしんどいのでは、と言われています。

詳しい説明とか実装は、社会にいろいろなブログが存在するのでそちらを読んでください。*1

Deep LearningにおけるFactorization Machines

さて最小二乗法の3次元版として話題なDeep Learningの話です。*2 Deep Learningは原理的には変数の重み付け和と非線形変換を繰り返す手法なので、理想的には積んだ層の数だけ交互作用が考慮されているはずですね。 そういう意味ではDeep LearningはFactorization Machinesといえるかもしれません。 しかし残念ながらそう簡単にはいきません。

xDeepFM[Lian+, KDD2018]に紹介されていた手法をもとにDeepなFactorization Machinesの研究を追っていきます。

  • Factorization-machine suppoerted Neural Network (FNN) [Zhang+, ECIR2016]
  • Deep Crossing Network (DCN) [Shan+, KDD2016]
  • Wide & Deep [Cheng+, arXiv:1606.07792 (2016)]
  • Product-based Neural Network (PNN) [Qu+, ICDM2017]
  • DeepFM [Guo+, IJICAI2017]
  • Deep Cross Network (CrossNet) [Wang+, ADKDD2017]

Factorization-machine suppoerted Neural Network (FNN) [Zhang+, ECIR2016]

DeepなFactorization Machinesを考える上で一番基礎的だと考えられているモデルです。 内容としては普通の多層ニューラルネットですが、入力データを各変数ごとにEmbeddingしている点が特徴です。 広告データやウェブのデータは画像などと違いカテゴリカルな変数が多いので、それぞれを異なるものと考えてEmbedすることによって効率的に学習しようとしていると推測されます。

f:id:Y_sekky:20181221140709p:plain
FNNのアーキテクチャ[Zhang+, ECIR2016]

Deep Crossing Network (DCN) [Shan+, KDD2016]

FNNとほぼ同時期に提案されたDCNはほぼ同じアーキテクチャです。Microsoftのチームで広告のクリック率推定問題を扱っています。 異なるのは上に積まれているのが、ResNetだという点です。

ほぼ同時期で、同じようなアーキテクチャですが、Factorization Machinesの文脈ではよくFNNのほうが引用されています。 これはFNNがオープンなデータで実験しており、パラメータなども公開しているのに対して、 DCNは企業内の内部データに対する実験になっていた点があるのかなと思います。 一方で後発の論文での比較結果を見る限り上に積まれているのがResNetなので、FNNよりこちらのほうが精度が高いようです。

f:id:Y_sekky:20181221141636p:plain
DCNのアーキテクチャ [Shan+, KDD2016]

Wide & Deep [Cheng+, arXiv:1606.07792 (2016)]

これも同時期のモデルです。Googleのチームにより提案されています。 カテゴリカル変数をEmbedして扱うところまでは一緒なんですが、違うところは線形モデルを出力層でくっつけていることです。 こんなんで上手くいくの？って思っちゃうんですけどうまく行っちゃってます。上記FNN、DCNより強いです。 TensorflowにAPIがあってすぐ使えるのも魅力的ですね。

f:id:Y_sekky:20181221143028p:plain
Wide & Deep [Cheng+, 2016]

Product-based Neural Network (PNN) [Qu+, ICDM2017]

ここまで紹介してきた手法は高次な交互作用を扱っているんですが、 Embedしたベクトルの各要素同士の交互作用なので、変数Aと変数Bというような明示的な交互作用ではないです。 いうなればbit単位の交互作用を扱っているモデルといえます。 ですがWide&Deepで見られるように、低次元な特徴を出力にうまく反映させるのは難しいです。 これは深層学習全般にいえることで、 例えばCNNは画素の周辺の情報が重要でフィルタによって重要な情報が取れるという低次元な特徴のとり方をアーキテクチャに導入しています。 カテゴリカル変数は交互作用が重要ということをアーキテクチャに組み込めないかというのがPNNで考えていることです。

以下にアーキテクチャと式を示します。

f:id:Y_sekky:20181221151404p:plain
PNN [Qu+, ICDM2017]

{ \displaystyle \hat{y} = \sigma (\boldsymbol{W_3} \boldsymbol{l_2} + b_3)}

{\displaystyle \boldsymbol{l_2} = relu(\boldsymbol{W_2} \boldsymbol{l_1} + b_2)}

{\displaystyle \boldsymbol{l_1} = relu(\boldsymbol{l_z} + \boldsymbol{l_p} + b_1)}

{\displaystyle \boldsymbol{l_z} = (l_z^1, l_z^2,...,l_z^{D_1})}, {\displaystyle l_z^n = \boldsymbol{W_z^n} \odot \boldsymbol{z}}

{\displaystyle \boldsymbol{l_p} = (l_p^1, l_p^2,...,l_p^{D_1})}, \displaystyle l_p^n = \boldsymbol{W_p^n} \odot \boldsymbol{p}

\displaystyle \boldsymbol{z} = (\boldsymbol{z_1}, \boldsymbol{z_2}, ..., \boldsymbol{z_N}) \triangleq ( \boldsymbol{f_1} \boldsymbol{f_2}, ..., \boldsymbol{f_N}), \displaystyle \boldsymbol{f_i} \in \mathcal{R}^M

\displaystyle \boldsymbol{p} = \{ \boldsymbol{p_{i,j}} \}, i=1,..,N, j=1,...,N

\displaystyle \boldsymbol{p_{i,j}} = g(\boldsymbol{f_i}, \boldsymbol{f_j})

\displaystyle \boldsymbol{f_i} = \boldsymbol{W_0^i} \boldsymbol{x}[start_i:end_i]

工夫されているのが \boldsymbol{l_1}のところで、 \boldsymbol{l_z}と \boldsymbol{l_p}の和として表現されています。 \boldsymbol{l_z}は通常の入力変数の重み付け和ですが、 \boldsymbol{l_p}は \boldsymbol{p_{i,j}} = g(\boldsymbol{f_i}, \boldsymbol{f_j}) として \boldsymbol{p}が生成されるように2次の交互作用になっています。 g(\boldsymbol{f_i}, \boldsymbol{f_j})は内積、外積、もしくはその組み合わせを用いています。 つまり2次の交互作用を明示的にLayerとして定義していることになります。

f:id:Y_sekky:20181221152124p:plain
PNNの結果[Qu+, ICDM2017]

Criteoのデータセットによる結果はこのようになっておりまして、embedを積み上げたFNNより、明示的に2次の交互作用を入力したPNNのほうが良い結果となっています。 （IPNNは内積、OPNNは外積、PNN*は内積と外積の組み合わせです） 面白いですね。深層学習は特徴を自動で生み出すみたいなことはよく雑な文章で書かれますが、これを見る限り、やはりデータの気持ちをアーキテクチャで表現することは非常に大事だとわかります。 xDeepFMの著者はこのように明示的に交互作用を入力することをvector単位の交互作用と言っています。

DeepFM [Guo+, IJICAI2017]

次に紹介するモデルはWide & Deepの発展形といえばいいんでしょうか。

f:id:Y_sekky:20181221153318p:plain
DeepFM [Guo+, IJICAI2017]

FM層はFactorization Machinesと全く同等です。そしてFM層の上に層がなく直接出力層とつながっています。 つまり交互作用はより高次に学習させるより、そのまま出力につなげたほうがいいんじゃんという主張になっています。 こんなんでうまくいくのかという気持ちになるんですが、うまくいくんですねこれが。

f:id:Y_sekky:20181221153855p:plain
DeepFMの結果 [Guo+, IJICAI2017]

このような結果です。そもそもPNNよりLR+DNN(実質Wide & Deep)のほうが強いんですね、悲しいことです。 DNN+FMとDeepFMの違いはFMへの入力をembedするかどうかですね。 つまるところ明示的な交互作用に対して層を積んでいくのは相性が悪いのでしょうか？Deep Learningまるでわかりません。

Deep Cross Network (CrossNet) [Wang+, ADKDD2017]

こちらはADKDDにおけるGoogleのチームによる論文です。 高次の交互作用をどう考慮するか、という問題に対してより明示的にしたアーキテクチャを提案しています。

f:id:Y_sekky:20181221154535p:plain
CrossNetのアーキテクチャ [Wang+, ADKDD2017]

これだけだとよくわからないので、CrossLayerの式と概念図を示します。

\displaystyle \boldsymbol{x_{l+1}} = \boldsymbol{x_0}\boldsymbol{x_l}^T \boldsymbol{w_l} + \boldsymbol{b_l} + \boldsymbol{x_l} = f(\boldsymbol{x_l}, \boldsymbol{w_l}, \boldsymbol{b_l}) + \boldsymbol{x_l}

f:id:Y_sekky:20181221155121p:plain
Cross層のアーキテクチャ [Wang+, ADKDD2017]

つまり入力となる \boldsymbol{x_0}と各層の出力との積を入力とするアーキテクチャといえます。 明示的に入力変数との交互作用を考慮しようという意図があります。

f:id:Y_sekky:20181221155736p:plain
DCNの結果 [Wang+, ADKDD2017]

強い手法との比較ではないですが、シンプルなDNNに比べて良い結果がでており、高次の交互作用を明示的に設計することでよい学習ができていることが示唆されています。

xDeepFM [Lian+, KDD2018]

ようやく本エントリの本題である、xDeepFMの紹介に入ります。

コンセプト

ここまで紹介してきたDeepなFactorization Machinesを振り返ると以下のようなことが言えると思います。

  • vector単位での交互作用を用いると良い
  • 高次の特徴を学習するには明示的なアーキテクチャが必要
  • 明示的な交互作用は通常のDNN(暗黙的な高次特徴)と違う性質をもつ

これを踏まえ xDeepFMのコンセプトは以下となっています。

  • vector単位で明示的に高次の特徴を学習するアーキテクチャを提案
  • 暗黙的な高次特徴である通常のDNNと組み合わせて学習させる

Compressed Interaction Network (CIN)

vector単位で明示的に高次の特徴を学習するアーキテクチャとしてCINを提案しています。

f:id:Y_sekky:20181221162156p:plain
CINのアーキテクチャ [Lian+, KDD2018]

伝搬の式は以下のようになります。

\displaystyle \boldsymbol{X_{h, *}^k} = \sum_{i=1}^{H_{k-1}} \sum_{j=1}^{m} \boldsymbol{W_{i, j}^{k, h}} (\boldsymbol{X_{i,*}^{k-1}} \circ \boldsymbol{X_{j,*}^{0}})

ここで \boldsymbol{X^0} \in \mathcal{R}^{m \times D}であり、 i-th fieldを \boldsymbol{X^{0}_{i, *}} = \boldsymbol{e_i}として、embedされた特徴量が各fieldにはいることとします。 Dはembeddingの次元です。

\boldsymbol{X^k} \in \mathcal{R}^{H_k \times D}として、 H_kはk層目の次元数、 H_0 = mです。

\circはHadamard productです。 例としてこのようになります。 \langle a_1, a_2, a_3 \rangle \circ \langle b_1, b_2, b_3 \rangle = \langle a_1 b_1, a_2 b_2, a_3 b_3 \rangle

RNNに似ていますね。入力が各層にはいり、各層の出力が隠れ層のように振る舞っています。

そして各層の出力はsum poolingされ、シグモイド関数で出力されます。

\displaystyle p_i^k = \sum_{j=1}^D X_{i, j}^k, \displaystyle \boldsymbol{p^+} = [\boldsymbol{p^1, ..., \boldsymbol{p^T}}]

\displaystyle y= \frac{1}{1+\boldsymbol{p^{+T}} \boldsymbol{w}^o}

ではこれで高次の特徴を学習できているのかを見てみましょう。

f:id:Y_sekky:20181221164356p:plain
CINの結果 [Lian+, KDD2018]

シングルモデル同士の比較を行っています。 層の数が交互作用の次元です。CriteoのデータセットはLogrossはDNNのほうがいいですが、それ以外はCINがoverperformeしています。 Bing Newsのデータでは層の数が5層になっているのでかなり高次のデータを活用していることがわかりますね。いいことです。 このようにCINで明示的に高次の交互作用をvector単位で学習することができ、その結果良かったことがわかりました。

eXtreme Deep Factorization Machines (xDeepFM)

さてCINで高次の特徴をvector単位で明示的に学習できました。 これをimplicitな特徴と組み合わせましょう。そう、Wide & Deepですね。アーキテクチャを示します。

f:id:Y_sekky:20181221163909p:plain
xDeepFMのアーキテクチャ [Lian+, KDD2018]

壮大ですね。やっていくぞという気概を感じます。 CINと、通常のDNNに加えて線形モデルもくっついています。

ところでこのアーキテクチャの図なにかに似ていると思いませんか？

f:id:Y_sekky:20181222150822p:plain

似ていませんかそうですか。こちらからは以上です。

f:id:Y_sekky:20181221164714p:plain
xDeepFMの結果[Lian+, KDD2018]

結果です。すべてのデータセットでoverperformeしました。よかったですね。 つまり高次の交互作用については暗黙的なものと明示的なものを組み合わせると良いといえます。 一方でLayerの数はそこまで大きくないですね。最大でも4次の交互作用までしか考慮されていないといえそうです。

各アーキテクチャの実装

公式、非公式で各アーキテクチャの実装が公開されているので紹介しておきます。

DeepCTR

CTR予測系の各種手法を実装＆検証できるように公開しているリポジトリです。強いです。 なお実装については非公式実装です。

github.com

今回紹介した手法のなかでは以下の手法が公開されています。

  • FNN
  • Wide & Deep
  • PNN
  • DeepFM
  • CrossNet

Wide and Deep

公式です。というかTensorflowのAPIです

github.com

PNN

公式実装です。 github.com

xDeepFM

公式実装です。 github.com

まとめ

以上KDD2018のxDeepFMを読み解きながら、近年のDeepなFactorization Machinesの動向についてまとめてみました。 変数明示的に組み合わせたほうがよかったり、上に積んでもうまくいかなかったり、新鮮に感じる結果が多かったです。 Wide and Deepあたりのパラダイムはなんでもありという感じで気持ちがいいですね。 低次の特徴をいれたほうがいいというのは、RNNの勾配損失問題とかともなんか近いものを感じます。 もしかしたら、データと計算リソースが無限にあればこういう凝ったアーキテクチャとかもいらないのかもしれないですね。 このあたりの分野が今後どのように進展していくのかは注目していきたいと思います。

参考文献

  • [Lian+, KDD2018] Jianxun Lian, et al. "xDeepFM: Combining Explicit and Implicit Feature Interactions for Recommender Systems" KDD, 2018.
  • [Rendle, ICDM2010] Steffen Rendle. "Factorization Machines" ICDM, 2010.
  • [Zhang+, ECIR2016] Weinan Zhang, et al. "Deep Learning over Multi-field Categorical Data - A Case Study on User Response Prediction" ECIR, 2016.
  • [Shan+, KDD2016] Ying Shan, et al. "Deep Crossing: Web-Scale Modeling without Manually Crafted Combinatorial Features" KDD, 2016.
  • [Cheng+, arXiv:1606.07792 2016] Heng-Tze Cheng, et al. "Wide & Deep Learning for Recommender Systems" arXiv:1606.07792, 2016.
  • [Qu+, ICDM2017] Yanru Qu, et al. "Product-based Neural Network for User Response Prediction" ICDM, 2017.
  • [Guo+, IJICAI2017] Huifeng Guo, et al. "DeepFM: A Factorization-Machine based Neural Network for CTR Prediction" IJICAI, 2017.
  • [Wang+, ADKDD2017] Ruoxi Wang, et al. "Deep & Cross Network for Ad Click Predictions" "ADKDDD", 2017.

*1:すごく参考になりました: http://echizen-tm.hatenablog.com/entry/2016/09/11/024828

*2:現実には松尾先生が「Deep Learningは最小二乗法のおばけみたいなもの」といって、それをだれかがAIは最小二乗法の３次元化と解釈したらしいですね。 https://medium.com/@tokoroten/%E3%81%8A%E3%81%98%E3%81%95%E3%82%93%E3%81%AF%E4%BD%95%E6%95%85newspicks%E3%82%92%E8%AA%AD%E3%82%80%E3%81%AE%E3%81%8B-59ebb60543b0