IRGAN (SIGIR 2017)→GraphGAN (AAAI 2018)→CFGAN (CIKM 2018) を読んで GAN による購買予測/協調フィルタリングを学ぶ

CFGAN (CIKM 2018) を読もうと思ったら「そもそも発想としては IRGAN (SIGIR 2017) と GraphGAN (AAAI 2018) が先にあって……」と触れられていたので順に読むことにする．
そもそもタイムラインで「CFGAN がはじめて商品推薦に GAN を使っていてすごい」という風潮で取り上げられていて，「2018年まで誰も思いついていないとかまさかそんな馬鹿な話があるわけないだろう」と思ったのがきっかけ．

結論から言うと

商品推薦に GAN を用いるのは CFGAN が初出ではなく IRGAN が初出であり， GraphGAN でも実現している
CFGAN は IRGAN/GraphGAN における「真のデータを Generator がサンプリングしてしまうことで Discriminator が混乱して精度悪化を引き起こす」という問題に対して「離散的に点をサンプリングせずに連続なベクトルのサンプリングを行う」という方式を採用することで精度を改善した

この 2 点．

IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models (SIGIR 2017)

[1705.10513] IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models
SIGIR18 IRGAN Tutorial

概要

GAN で IR (Information Retrieval) を行う．IR は query $q$ に対して関連がある document $d$ を得るタスク．
読むまで「どのように Generator で document を生成するのだろうか」と思っていたらそういうわけではない．

Generator : query から document が生成される確率
- 真の確率 $p_{\textrm{true}}(d|q, r)$ は学習データで与えられているとする (というより関連のある pair $(q, d)$ が与えられている)
- $p_{\textrm{true}}(d|q, r)$ を模倣する $p_{\theta}(d|q, r)$ を学習したい
Discriminator : query に document が関連がある場合に 1 を返すような識別的な関数を学習したい
- $D(d|q)=\sigma(f_{\phi}(d, q))$

の 2 つを用意して

$J=\textrm{min}_{\theta} \textrm{max}_{\phi} \sum_{n=1}^N \mathbb{E}_{\sim p_{\textrm{true}}(d|q_n, r)} \log D(d|q_n) + \mathbb{E}_{d \sim p_{\theta}(d|q_n, r)} \log (1 - D(d|q_n))$

を学習する．
$\textrm{min}_{\theta} \textrm{max}_{\phi}$ の気持ちは

Discriminator は真に関連がある $(q_n, d)$ pair に高いスコアを振り， Generator が提示してくる $(q_n, d)$ pair に対して低いスコアを振るように頑張る
Generator はに対してなるべく関連がありそうなをサンプリングできるように頑張る
- もう少し丁寧に書くと $p_{\theta} (d|q, r)=\frac{\exp(g_{\theta}(q,d)/\tau)}{\sum_{j\in \mathcal{I}} \exp(g_{\theta}(q,d)/\tau)}$ という感じで $g_{\theta}$ を学習する必要がある
Discriminator および Generator は pair に対するなんらかの特徴ベクトルを受け取るニューラルネットワークで構築する
- あとで実験を行いますが特に Generator を linear なモデルにすると予測精度が低いままになってしまう．馬鹿な Generator では Discriminator の役に立たない．

という状態．

学習においては Discriminator は普通に勾配を求める． Generator はサンプリングが関係するので policy gradient based reinforcement learning を使う．

自分の解釈

ナイーブに考えると関連がある pair を正例，関連が無い pair を負例として識別的に Discriminator のみを学習すればいいわけですが， query と document それぞれが非常に大量にあり，かつ，関連がある pair が非常に少ない時，まさか全組み合わせを使って負例を作るわけにはいかないし，そもそも「関連がある」わけではないペアがすべて「関連がない」わけではなく， unobserved だけれども関連する pair も存在している．なので unlabeled なデータを使って Generator で効率的に識別面に近い負例を生成し， Discriminator の学習を補助している，という解釈でいる．

とはいえ Discriminator を Pre-train するという記述があってどうやって負例を作ったのかがわかっていない．実験の項を見ると関連度順に 0, 1, 2 とつけられたラベルと -1 の「関連度無し」というラベルについて 1 と 2 を関連するラベルとして，それ以外を unlabeled として扱っている．そもそもIRにおいて positive だけがある状態で学習する話がわかってない．情報系の素養が何もない．

実験

実験結果を見ると既存の手法を上回る精度を出している．
また，この枠組みは商品推薦にも使うことができる． IR タスクでは特徴ベクトルが与えられる状態でしたが query/document を user/item と読み替えて特徴ベクトルの代わりにそれぞれの latent vector (論文中では user/item matrix に対する matrix factorization) の内積を用いることで同じように実験ができる． Movielens と Netflix で実験して BPR (pairwise な loss を考えるやつ) を上回る精度を出している．よって少なくとも IRGAN によって GAN を用いた商品推薦が実現していることがわかる．

GraphGAN: Graph Representation Learning with Generative Adversarial Nets (AAAI 2018)

[1711.08267] GraphGAN: Graph Representation Learning with Generative Adversarial Nets
今度はグラフに対して GAN を行う．何を生成するかというと

Generator : vertex ( vertex ) から vertex に対して edge (枝) が存在する確率を返す関数
- 真の確率 $p_{\textrm{true}}(v|v_c)$ は入力におけるグラフにて vertex ペア $(v, v_c)$ 間に edge が存在しているかで表現されている
- $p_{\textrm{true}}(v|v_c)$ を模倣する $G$ を学習したい
Discriminator : $D(v,v_c;\theta_D)$ は vertex ペア $(v, v_c)$ 間に edge が存在しているかを識別する関数であり，vertex 間に枝があるかを学習させる

といったように

Generator は edge がありそうな vertex pair を返す
Discriminator は真に edge が存在する vertex pair かどうかを返す

を繰り返す(馬鹿みたいに考えるとグラフを丸暗記すればいいわけですが後述するように vertex の embedding/latent vector の内積で表現するのでそういうわけにはいかない)．
vertex を query と document として考え， edge を relevant として考えると IRGAN と同じ枠組みであることがわかる．

IRGAN の時と同様に

Discriminator $D(v, v_c) = \sigma(\mathbf{d}_v^T \mathbf{d}_{v_c})$ として $\mathbf{d}_v, \mathbf{d}_{v_c}$ を vertex ごとの k 次元の潜在表現pとして学習
Generator としてを vertex ごとの k 次元の潜在表現として学習
- この時，ナイーブに softmax を取るとグラフ構造を活かすことができないのでグラフ構造を反映して $v_c$ から Breadth First Search で tree を作ってそこにおける path を使って確率を構成する graph softmax を導入する (eq 7が追えてないので詳細は後日ちゃんと読む)
- さらに $G$ からのサンプリングを効率的にするために online sampling strategy を導入する

とする．

実験

実験は link predicton， Node Classification，それと Recommendation をやる．当然 vertex を user と item とみなせば link prediction は recommendation として考えられるため行うことができる．

IRGAN / GraphGAN における素朴な疑問

ここまで IRGAN と GraphGAN を読んできて一点分からないことがある．
Generator は「真にありそうなもの」を提示し， Discriminator はそれを reject しなければならない．もし Generator が「学習データにおいて relevant がある / edge がある」ものを引き当てた場合， Discriminator はそれに対して低いスコアをつけなければならない．
論文中でも「 Generator が真に学習できていたらそれは $p_{\textrm{true}}$ と区別がつかない」と書かれていてそれが理想なのだろうけど，しかし矛盾する事例を引き当てた場合は無視するのだろうか，もしくはそもそも引き当てることが少ないという前提なのだろうか，いう点が引っかかっていた．

CFGAN: A Generic Collaborative Filtering Framework based on Generative Adversarial Networks (CIKM 2018)

CFGAN: A Generic Collaborative Filtering Framework based on Generative Adversarial Networks

モチベーション

IRGAN と GraphGAN によって GAN による推薦が可能になったとはいえ，これらの手法は「要素を 1 つ離散的にサンプリングしてそれの真偽を問う」という手続きを取っているために問題がある．
なぜなら，真の要素を Generator がサンプリングしてしまった時， Discriminator は矛盾するラベル(同じ要素が true でもあり false でもある)を受け取って学習するために混乱してしまうからだ(思い浮かんだ疑問点で回収されて少しうれしい)．
実際にこれがどの程度起こっているか実験で確かめる．両モデルで推薦タスクを解いてみると epoch を増やすにつれ Generator と Discriminator の精度は上がるが，ある一定の epoch を超えると突如として Discriminator の精度が異常に悪化し始めることがわかる．同時に， Generator が真のデータをサンプリングしてしまう確率が非常に高くなっていることがわかる．これはすなわち

学習が進むことで Generator が賢くなって真の分布に近づく
それによって矛盾したデータを Discriminator が受け取る
Discriminator が混乱して精度が下がる
Generator に Discriminator からの信号が伝播しなくなり学習が止まる

という状態に陥っていることがわかる．

CFGAN

著者ら曰く， IRGAN/GraphGAN の問題点は Generator が離散的にサンプリングを行うことであるらしい．
そこで CFGAN では

Generator はユーザごとに
- $u$ の状態ベクトル $\mathbf{c}_u$ とランダムノイズ $\mathbf{z}^2$ を入力として，商品数 $n$ の次元を持つ購買ベクトル $\hat{\mathbf{r}}_u$ を生成する
- その後が購買していた商品の要素となるマスクベクトルと要素積を取る
  - これは既存の購買予測における「購買していた(学習対象の)要素に絞る」という観点と一致する
Discriminator は購買ベクトルが真であるか偽であるかを推定する
- この時，入力には真の購買ベクトル(購買履歴) $\mathbf{r}_u$ または Generator が生成した購買ベクトルをマスクしたもの $\hat{\mathbf{r}}_u \odot \mathbf{e}_u$ とユーザの状態ベクトル $\mathbf{c}_u$ とを連結したものを与える
- Generator / Discriminator ともに適当なニューラルネットワークで学習する

として Generator を連続的にサンプリングする．
しかし， $\mathbf{e}_u$ でマスクを取るならば全てについて $\hat{\mathbf{r}}_{ui} = 1$ となるような購買ベクトルを学習するのがもっとも単純な解であるが，それでは商品間の好みの関係が全く学習されない．
そこで，一部の購買していない商品をサンプリングし，それぞれ $j$ について

zero-reconstruction regularization : $\hat{\mathbf{x}}_u=\textrm{concat}(\hat{\mathbf{r}}_u \odot \mathbf{e}_u, \mathbf{c}_u)$ として $\hat{\mathbf{x}}_{uj}$ を 0 に近づける項を目的関数に追加して学習させる
partial-masking : $\mathbf{e}_u$ でマスクする時に $\mathbf{e}_{uj}=1$ として購買していない商品についても Discriminator に値を渡すことで学習させる

のという両方の工夫を行う．

実験

実験でSOTAという触れ込みで流れてきたけどこういう比較で SOTA を名乗っていいのかと思うような実験だった．そもそも movielens での現状の SOTA を並べて比較しているサイトがなかったり，皆がそれぞれの基準でデータのフィルタリングを行っているのでまともに比較ができないと思うのですが，140文字未満の論文ツイートだけ読んで論文を理解する人々に言ったところでどうしようもない話だった．
当初の疑問だった「矛盾したラベルはどうなのか」とう話は， CFGAN でも発生はしているがそれでも Discriminator はしっかり見分けていて学習がしっかり見分けている．これはベクトルをサンプリングしているからである(と著者は主張している)．多分ですが目的関数を計算する時に矛盾する一点のみではなく矛盾するベクトルかどうかで取り扱っているので後者の方が緩いから，とかそういうことだと思う．

糞糞糞ネット弁慶

読んだ論文についてメモを書きます．趣味の話は http://repose.hatenablog.com