Applying Deep Learning To Airbnb Search (preprint) 読んだ

論文

[1810.09591] Applying Deep Learning To Airbnb Search

Airbnb における Search に Deep Learning を導入した話．「機械学習のシステムが既にあってそこにニューラルネットワークを導入したい人」に向けて書かれている．
論文調ではないのでまとめも箇条書き．

モデルの概要

既存の GBDT -> 4層 (中間層は32個，ReLU で活性化) の NN (17年4月) -> Lambdarank NN (17年6月) -> GDBT/FM NN (18年3月) -> Deep NN (18年6月) と段階的に本番環境に導入してきた
- 最初の NN は損失関数を二乗誤差にしていた
- Lambdarank NN : 損失関数を Lambdarank のそれにして学習した
- GBDT/FM NN : 既存の NN に対して以下の特徴量を追加したもの (なぜならそれらのモデルの出力は NN によるものと異なっていたため)
  - GBDT feature : それぞれの木においてどこの leaf に落ちたかを categorical feature として得る
  - FM feature : 32 次元に落とした Factorization Machine の出力を連続値として得る
- Deep NN : 4層 (195-127-83-1) の DNN．feature engineering はほとんど行っていない．
  - KDD 2018 | Customized Regression Model for Airbnb Dynamic Pricing や KDD 2018 | Real-time Personalization using Embeddings for Search Ranking at Airbnb の値も特徴量に入れている
  - 学習データを 1.7 億件まで増やすと training ndcg と test ndcg がほぼ一致するようになった (それより少ない時は training が高く， test が低かった)

失敗した試み

代表的なものをふたつ．

物件 ID (Listing ID)
- Listing ID を embedding して使ったところ overfitting してばかりで精度が下がった
  - 同じ Listing ID が重複して booking log として登場しないため
long view (多分ある listing を長い時間閲覧していること) と Booking probability をひとつのネットワークで同時に学習させる multi-task learning (最終層を 2 つにする)
- long view と booking にある程度の相関があったため
- また，long view には Listing ID が複数登場するため先程失敗した embedding も効くのではないか
- しかし実際には long view のみを改善し booking には変化が無かった
  - long view が発生するのは高価な物件，説明文が長い物件，珍しかったり面白い物件といったような booking に直接関係しない要素が原因だったため

Feature engineering

特徴量の値を [-1, 1] に変換する
- 正規分布のように分布していたら平均と標準偏差を使う
- べき乗則に従っているように見えたら中央値と log を使う
モデルの sanity check として特徴量の値を 2,3,4 倍としていった時に NDCG が変化しないかを見るといいらしい
位置情報は少し工夫する
- 物件の緯度軽度は検索時に表示されている地図の中央の緯度経度を基準に変換するだけでは値が中央によりすぎるので，その上で log を取る
  - 相対的な位置情報に変換することで特定の位置情報ではない特徴量が得られる
分布が連続にならない特徴量も組み合わせることで連続になる
- ひとつの例として，ある時点からの未来における予約率が特徴量として効きそう(人気の物件ほど速く予約が埋まる)が分布が連続ではないので困った
- 物件ごとに最低日数が設定されており，これが原因で分布がおかしくなっていた
- 物件ごとの平均利用日数と組み合わせることで分布が連続になった
より大域的な位置情報をどう扱うか
- level 12 の S2 cell で位置情報を取得する
- その上でクエリと組み合わせて Hash にする
  - 例えば "San Francisco" というクエリに対して Embarcadero のある物件の S2 cell が 539058204 だった場合 `{"San Francisco", 539058204}` を Hash 化して 71829521 という値を得る．これを categorical feature として用いる
  - ここの Hash についてはこれ以上の記述はなし

System engineering

パイプラインは Java で構成されている
GBDT 時代に CSV を受け渡していたパイプラインを使いまわしていたら学習時間のほとんどを CSV ファイルの変換に使っていることがわかったので Protobuf を使うよう再構築したところ学習も高速化されたので学習に用いるデータを一週間から一月に増やすことができた
モデルの学習は Tensorflow で行うがスコアリングは Java で独自に構築した NN ライブラリで行う

2018-11-12

IBIS 2018 行った

メモ

IBIS2018 | 第21回情報論的学習理論ワークショップ, 2018.11.4〜7, 札幌（かでる2.7・北大）
先月にアンダーライブツアー北海道シリーズで行ったばかり．札幌がちょうどいい気温だった．チュートリアルの日は特に晴れていて，北大内にあるセイコーマート2階のテラス席がとても気分が良かった．
会議以外だと円山動物園が想像以上に見応えがあって良かった．

チュートリアル

深層学習入門

「入門」と称して積分表現の話をするのかと怯えていたら本当に入門で終わった．

転移学習 : 基礎と応用

共変量シフトと密度比推定の話が良かった．

データ駆動型科学のための統計的推論法

ポスター発表でも selective inference が頻発していた．

クエリ可能な確率的組合せ最適化問題

連続緩和して解くみたいな話だった．
「この設定は臓器交換・オンラインデーティングなどに応用をもつ」とのことでしたがチュートリアルでは腎臓交換の例ばかりだったような．マッチング業者の立場から「確率的にマッチするかどうかがわかるけどカップルが成立したら取り消し不可能(臓器交換しなきゃならない)」という問題設定だと確かにそのままだった．
レコメンデーションなどと組み合わせられるかと思ったけれど確率的にマッチするかどうかというのは少し違うのではないかと考え直した．

1 日目

離散構造処理系 : その概要と最近の研究状況について

ZDD の紹介．数え上げ(複雑な目的関数を取れない)のイメージがあったのである尤度比について枝刈りを行うことで高速化できるという話が面白かった．

グラフ集合を圧縮して活用するためのデータ構造とアルゴリズム

ZDD のテクニックの話だった．

離散構造処理系の機械学習への応用

arm を複数まとめた super arm を考える組み合わせバンディットに活用できるという話が面白かった．
- 話は変わりますが「影響最大化はマーケティングに使える」という枕詞を死ぬほど聞きますが実際にマーケティングに活用した事例はあるのだろうか．

2 日目

公平性に配慮した学習とその理論的課題

「差別」という単語を定義しないまま最初から最後まで話が進んでいたので引っかかる部分が複数あった．おそらく，集団 / 個人公平性が満たされていないことを「差別が発生している」と定義しているのだと思う．
「機械翻訳における差別」という話で「性差の無い言語から英語に翻訳すると『XXはYYである』という文が YY によって XX の he/she が変わるのは差別だ」というエピソードが紹介されていた．この例もよくわからなくてどういう翻訳が出力されたら差別ではないのかがわからない．
「US の全件調査データにおいて女性の収入が低いことはバイアスである」という話があったけれど文字通り全件調査ならバイアスではなくそれが事実なのではないか．データが本当に偏っているのか，調査の過程でバイアスが生じたのか(アメリカ大統領選挙の番狂わせ（前編）〜標本調査における偏り�@｜統計学習の指導のために（先生向け）, ② みたいな話ですね) の例でこれは違うのではないかと思った．
「少数クラスをモデルが無視してしまうので偏った数字が出ることで学習におけるバイアスが発生する」と言われていて，これは学習器が無限に賢くなったら解決される差別なのだと思う．
集団公平性 (group fairness) と個人公平性 (indicidual fairness) というふたつの視点が紹介されていたが「どちらの観点から裁判になることが多いのか」という質問が出ていたのが良かった．
社会正義や公平性を満たすためにデータやモデルを無視しなければならないとしたらそれはもはや学習理論が扱う範疇の話ではなくて質疑でもあったように裁判で決める話なのだろうと思いながら聞いていた．

3 日目

コンピュータビジョンにおける無教師学習の進展とその課題

無教師学習とは何かと思ったら最初から最後まで GAN の話だった．

音声分野における敵対的学習の可能性と展望

JSUT コーパスでもおなじみの高道氏による話．

GAN で高精度になるしもっと発展が見込めるみたいな話だった．
スライド中に「こんなことができるのではないか」と語られていたアイデアがすでに arxiv にあるという話がタイムラインに流れていてそんなペースで論文が出る界隈は死ぬほど大変そうだと思った．

ポスター

去年の東大よりは歩きやすくて聞きやすかった．

D1-05: 巨大ランダム行列を用いた構造の変化点検知
- シンプルな話で面白かったので論文で読みたい．
D1-66: 患者情報の季節性と検索クエリに基づくトレンドを用いたインフルエンザ患者数予測
- 他の人に対して説明しているのを聞いたところ，2 つのデータを分けて推定させたほうが精度が出た，みたいな話が聞こえてよかった．
D1-79: 日時が曖昧に記録されたイベント列の解析
- RBM を時間方向に無限に伸ばすみたいな話だった．最近 accept されたみたいな話だったと思う．
D2-72: 教師付解釈学習
- いい話だった．

2018-11-09

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 はしっかり見分けていて学習がしっかり見分けている．これはベクトルをサンプリングしているからである(と著者は主張している)．多分ですが目的関数を計算する時に矛盾する一点のみではなく矛盾するベクトルかどうかで取り扱っているので後者の方が緩いから，とかそういうことだと思う．

2018-09-20

Graph Convolutional Neural Networks for Web-Scale Recommender Systems (KDD 2018) 読んだ

論文

KDD 2018 | Graph Convolutional Neural Networks for Web-Scale Recommender Systems
著者に Jure Keskovec がいる．
Pinterest における推薦にて node の embedding を graph convolution で学習する推薦手法 PinSage を提案している．タイトルだけ読むとそのように思えるけれど，実際には Graph Convolutional Network で行われるような Graph Fourier変換にもとづく畳み込みを行っていない．この点を誤解しているまたはまともに読んでない人しかいないのではないかと思う (footnote 1 で however, the architecture we employ does not directly approximate a spectral graph convolution と言及もしている)．

PinSage における Graph Convolution

Convolution

今，次のような関数を考える (論文中ではこの操作を Convolution と呼んでいる)．論文中の Algorithm 1 の説明では $h$ と $z$ が未定義の状態で登場していて完全に意味不明なので論文の主張に沿って正しいと思われるコードを書く．

# node u に対する畳込みを得る関数
# z_u  : u の現在の畳み込み表現
# z_neighbors : u の近傍ノードの畳み込み表現の集合
# alpha : 近傍ノードの重み
# Q, q : importance_pooling に渡す前のパラメタ
# W, w : 最後の ReLU に渡す前のパラメタ
def covolve(u, z_u, z_neighbors, alpha):
    n_u = importance_pooling(ReLU(Q * z_neighbors + q), alpha)
    z_u_new = ReLU(W * concat(z_u, n_u) + w)
    return normalize(z_u_new)

# vectors を element-wise に weights で重み付けして平均を取る pooling 関数
def importance_pooling(vectors, weights):
    i, j = vectors.shape
    ret = [ ]
    for dim in j:
        ret[dim] = np.mean(vectors[dim, pos] * weights[pos] for pos in range(i))

    return ret

何をやっているかというと，ある node $u$ に対する embedding をその近傍にある node の embedding をまとめて pooling し，現在の embedding と concat した上で ReLU に通している．これを深さ $K$ まで繰り返し適用する (論文中では $k$ 回目の繰り返しにて得られる embedding を $h^{(k)}$ と表現している)．思ったよりシンプル．

ここだけ読むとシンプルな話でいいわけですが，論文冒頭では「 node $u$ には visual や texual な feature が付与されている」「この手法ではそれら feature を使って embedding を学習する」と書いてある．しかし上記のコードにはそれら feature に対する言及がない．"We start with input node features and then learn neural networks that transform and aggregate features over the graph to compute the node embeddings" と書いてはあるがその後の記述を読むと embedding のことを feature と呼んでいて正直に言って全く理解できない．
id:another16javac さんから「GraphSAGE [1706.02216] Inductive Representation Learning on Large Graphs が参考になる」というコメントをいただき読んだところ $h^{0}$ を特徴量 $x$ で初期化しているのでここで使うという話だった．そしてこの論文もよく読むと algorithm 2 で同様に $h^{0}$ を $x$ で初期化していた．恥ずかしい．

細かいテクニック

Pixie で行ったように $u$ から始まるランダムウォークによる訪問回数が上位の node を近傍として用いる．また，この時の訪問回数を重み $\alpha$ として用いる． Pixie ではこの時のランダムウォークに用いる遷移行列を node の特徴量を謎の関数に通して重み付けしていたが，まさかこれが上記の疑問に相当する?
学習はクエリ $q$ と正例 $i$ のペア $(q, i)$ が与えられていると考え，負例のペアより正例のペアの embedding の内積が大きくなるように学習する．
またこの時，負例は negative sampling するわけですが uniform にやるとほとんど関係ない負例ばかり出てきて関数が収束しない．そこで $q$ に似ているが正例ではない負例を hard negative item として選ぶ．また，学習の際には epoch ごとに hard negative item を段階的に増やす curriculum training を行う．
学習は MapReduce． d2.8xlarge のインスタンスを 378 台並べてクラスタを作る．

Graph の convolve は分かるけどどうやって特徴量を有効活用したのかわからない．

2018-09-01

Sequences of Sets (KDD 2018) 読んだ

論文

KDD 2018 | Sequences of Sets
好きな研究者が何人かいて，タイトルで気になった論文の著者がその人だとちょっとうれしくなる．Cornell University の Jon M. Kleinberg や Google の Ravi Kumar ， Stanford の Jure Leskovec は気になって定期的に著者のページを見に行っている．Facebook の Lars Backstrom は久しく論文を書かなくなってしまったので悲しい．
今回の論文は Ravi Kumar が Co-Author に入っている．

集合 (set) の系列 (sequence) についてモデリングする．論文中では

ある人物が送信したメールそれぞれの宛先を時系列でソートしたもの
Stack exchange において投稿された質問に付与されたタグをユーザごとに集めてソートしたもの
センサーから得られた人の接触データ
共著関係

を対象に分析・観察を行い，集合の系列の推定モデル Correlated Repeated Unions (CRU) model を提案している．

データの観察

集合は繰り返す．多くの集合は系列において繰り返し現れるし，全く同じものだけでなく上位集合 (superset) や部分集合 (subset) も現れる
- 系列を前から見ていった時にある集合 (と完全に同じもの | と全く要素がかぶらない集合 | の部分集合 | 上位集合) ががそれより前に現れた比率を見ると集合が繰り返して現れていることがわかる
集合の要素は相関する．二つ組，三つ組の組み合わせは相関を持って現れる
- 全集合から全ての二つ組，三つ組を数え上げるとそれらがランダムに出現する個数より多い
古いものより新しいものに類似した集合が出現する
- ある集合と，それより k 個前に現れた集合との Jaccard 係数の平均を見ると， k を大きくするほど低下する．つまり近ければ近いほど集合間の類似性は高い

CRU モデル

これらを踏まえて集合系列のモデルを提案する．
しかしここまで読むとこのモデル，系列 $S_1,\cdots,S_n$ が観測されている状態で $S_k$ までを用いて $S_{k+1}$ がどのように生成されるかをモデル化している (機械学習的な外挿を行うモデルではなく，物理のように現象を理解するためのモデルのようなニュアンス)．本来想定していたのは $S_n$ までが与えられた状態で $S_{n+1}$ を推定するモデルだったのでちょっと肩透かし．
パラメータとして長さ $n$ であるいくつ前の集合を重視してサンプリングするかの $w$ と集合内からサンプリングを行うための $p$ を持つ．また， $S_{n+1}$ の要素数も (なぜか) わかっているとする．こういう仮定のおかげで将来予測ができない．
CRU モデルの論文の説明を Python のコードで書いた．大雑把な言い方としては

過去の系列をさかのぼってどの集合から要素をサンプリングするかを選ぶ
選んだ集合から要素をサンプリングする
これが一定の大きさになるまで繰り返す

という動きをする．

# S_i の重み付き抽出に必要
from numpy.random import choice

# 長さ k の 集合の系列 S を受け取って次の繰り返し集合 R を出力するモデル
def CRU(r, w, p, S):
    R = set()
    k = len(S)
    while True:
        if len(R) == r:
            return R

        # S_i を重み w_{k + 1 - i} で抽出
        # w は重みなのでサンプリング用の確率に変換する
        p_s = [w[k + 1 - i] for i in range(k + 1)]
        p_s = [x / sum(p_s) for x in p_s]
        S_i = choice(S, p=p_s)

        # S_i から各要素を確率 p でサンプリング
        T = set()
        for s in S_i:
            if random.random() <= p:
                T.add(s)

        # この時の n は系列の「全長」 (未来の分まで含める)
        if len(R | T) > n:
            while len(R) < n:
                # T から一様に要素をサンプリング
                y = choice(T)
                R.add(y)
                T.remove(y)
        else:
            R = R | T

パラメータ推定

推定したいのはいくつ前の集合を重要視してサンプリングするかのパラメータ $w$ (論文冒頭にて要素内からのサンプリングパラメータ $p$ はグリッドサーチしたと言及がある)．尤度の式を作ることができればパラメータの推定はできるはず．しかし集合が生成される尤度とはどういう形でしょうか．僕はすぐには思い浮かばない．
3.2 を真面目に読んでいないけれど，方針としては出力される $R$ の部分集合すべてについてそれが生成される確率を求めてやればいい，という理解でいる．これ以上はこの論文を再実装したくなった時に読み返す．

2018-08-28

Learning and Transferring IDs Representation in E-commerce (KDD 2018) 読んだ

論文

KDD 2018 | Learning and Transferring IDs Representation in E-commerce
EC サイトにおける商品 (item) の埋め込み (embedding) を学習する．その際，商品につけられたメタデータをまとめて学習する．

基本方針

ユーザの商品閲覧行動にもとづいて skip-gram を学習する．すなわち，窓幅を $C$ として

$\frac{1}{N}\sum_{n=1}^{N}\sum_{-C \leq j \leq C}^{1 \leq n + j \leq N,\ j \neq 0} \log p(\textrm{item}_{n + j} | \textrm{item}_{n})$

を学習する．この時

$p(\textrm{item}_{j} | \textrm{item}_{i}) = \frac{\exp ({e^{\prime}_{j}}^{T} e_i)}{\sum_{d}^D \exp ({e^{\prime}_{d}}^{T} e_i)}$

である． $e^{\prime}\, e$ が $m$ 次元の商品の埋め込みとして得られる．

商品と属性の埋め込み

ここで，商品には様々な属性が付与されていることを考える．論文では例として

ある「商品」(product，例えば iPhone X) は異なる店 (store) にて異なる商品 (item) として扱われている
「商品」にはブランド (brand) が付与されている
「商品」には階層的なカテゴリ構造 (cate-level1, cate-level2, cate-level3) が付与されている

としている．以降， item ID, product ID, store ID, brand ID, cate-lebel1 ID, cate-lebel2 ID, cate-lebel3 ID の 7 種類を考える (これ以上増やすことも可能)．また，これを「属性」と呼ぶことにする．

今， $K$ 種類の属性があり， $\textrm{IDs}(\textrm{item}_i) = [\textrm{id}_1(\textrm{item}_i), \cdots, \textrm{id}_K(\textrm{item}_K)]$ とする．また $\textrm{id}_1$ を item ID とすると，次の式がこの論文の提案手法．

$p(\textrm{IDs}(\textrm{item}_j) | \textrm{IDs}(\textrm{item}_i)) = \sigma (\sum_{k = 1}^K (w_{jk} e^{\prime}_{jk})^T(w_{ik} e_{ik})) \prod_{s=1}^S \sigma (-\sum_{k = 1}^K (w_{sk} e^{\prime}_{sk})^T(w_{ik} e_{ik}))$

$S$ は negative sampling における負例集合であり， $e_{ik}$ は商品 $i$ における属性 $\textrm{ID} k$ ごとの埋め込み．属性ごとに埋め込みの次元長 $m_k$ は変わる (この時点では全ての埋め込みは異なるものとして扱う)．言ってしまえば，商品ごとの全属性の内積の総和を用いて商品の出現確率を計算する． $w_{ik} = \frac{1}{V_{ik}}$ であり $V_{ik}$ は $i$ の属性 $k$ を持つ商品の個数．

更に，商品とその属性との関係も学習する．すなわち

$p(\textrm{item}_i | \textrm{IDs}(\textrm{item}_i)) = \sigma (\sum_{k=2}^K w_{ik} e_{i1}^T M_k e_{ik})$

とする．ここで $M_k$ は商品 $i$ の長さ $m_1$ の埋め込み $e_{i1}$ を各属性 $k$ の長さ $m_k$ 埋め込みに変換するための行列．ここでようやく商品と属性の埋め込みが同じものとして扱えるようになる． $\sum$ のインデックスが $k=2$ から始まっているのが重要．

最終的な目的関数は

$\frac{1}{N}\sum_{n=1}^{N} ( \sum_{-C \leq j \leq C}^{1 \leq n + j \leq N,\ j \neq 0} \log p(\textrm{item}_{n + j} | \textrm{item}_{n}) + \alpha \log p(\textrm{item}_n | \textrm{IDs}(\textrm{item}_n)) - \beta \sum_{k}^K ||M_k||_2)$

とする．[tex\alpha]は商品自身の表現に対する重みのハイパーパラメータ， $\beta$ は $M_k$ に対する L2 正則化のハイパーパラメータ．

ユーザの埋め込み

複雑な方法はあるけれど計算が簡単なので直近 $T$ 個の商品の埋め込みの平均をユーザの埋め込みとする．

応用

類似商品の提示

あるユーザが直近で閲覧したいくつかの商品について埋め込みが類似する商品を列挙すればいい．

未知の商品に対する計算

未知の商品 $i$ があるが属性が付与されているときにその商品の埋め込みが計算できる．

$p(\textrm{item}_i | \textrm{IDs}(\textrm{item}_i)) = \sigma (\sum_{k=2}^K w_{ik} e_{i1}^T M_k e_{ik})$

だったことを思い出すと $\sigma$ は単調増加なので

$p(\textrm{item}_i | \textrm{IDs}(\textrm{item}_i)) \propto \sum_{k=2}^K w_{ik} e_{i1}^T M_k e_{ik} = e_{i1}^T(\sum_{k=2}^K w_{ik} M_k e_{ik})$

となる．目的関数が十分に最適化されていれば $p(\textrm{item}_i | \textrm{IDs}(\textrm{item}_i))$ は 1 と考えられるので式変形をすれば

$e_{i1} \approx \sum_{k=2}^K w_{ik} e_{ik}^T M_k^T$

で値が得られる．

異なるドメインに対する転移

ここの記述が全く理解できていない．

source ドメインで商品の埋め込みを計算してユーザの埋め込みを求める
source ドメインのユーザを埋め込みを用いて k-means でクラスタリングし，そのクラスタで代表的な商品を計算する
target ドメインのユーザを埋め込みにもとづき最も類似するクラスタに割り振り，商品を提示する

という手続きが説明されているが，そもそもユーザの埋め込みが共有できるということは商品の体系も共通していなければならない．揃っているならばまとめて学習すればいい(ドメインの違いは属性として特徴量に持たせればいい)のではないか．論文中では Taobao を source ， Hema を target としているがそもそも EC サイトとしての性質が大きく異なるのに共通で計算できているという話もよくわからない．
「cold-start なユーザに対する推薦」という話だとしても，クラスタにそのユーザを割り振る際に計算するユーザの埋め込みはどのようにして計算できているのか，という話が理解できない(そこが計算できているならばクラスタに割り振る処理は不要ではないか)．

とここまで書いたところで 5.3 にて Since new users have ho historical records に気づくが，やはりどうやって新規ユーザの埋め込みを計算したのかが謎．致命的な何かを読み落としているとしか思えない．