GAN を使って表形式のデータを生成する論文は既に読んだわけですが，その発展形．著者らによる実装も公開されており(DAI-Lab/TGAN: Generative adversarial training for synthesizing tabular data)，実装を試した人もいる(テーブルデータ向けのGAN（TGAN）で、titanicのデータを増やす - u++の備忘録)．

前述した tableGAN との違いは CNN を用いずに LSTM を用いていること，交差エントロピーを用いるのではなく KL divergence を使って周辺分布を学習していることの二点．

データ変換

データが $n_{c}$ 個の連続値の変数 $c_{i}$ と $n_{d}$ 個の離散値の変数 $d_{i}$ で構成されているとし，各行の各列についてそれぞれが連続値の変数なのか，離散値の変数なのかを区別して話を進める．

連続値の変数について

多くの場合連続値の変数は多峰 (multimodal) である．なのでそのまま表現せず，次のような手続きを踏む．

$(-1, 1)$ に変換する
それぞれの変数について混合数 $m$ のGMM (Gaussian Mixture Model) を学習し，平均 $\tau_{i}^{(1)},\tau_{i}^{(2)},\cdots,\tau_{i}^{(m)}$ および標準偏差 $\sigma_{i}^{(1)},\sigma_{i}^{(2)},\cdots,\sigma_{i}^{(m)}$ を得る
$i$ 番目の変数の $j$ 列目の値 $c_{i, j}$ が GMM の各要素から得られる確率 $u_{i, j}^{(1)},\cdots,u_{i, j}^{(m)}$ を得る
$c_{i, j}$ を $v_{i, j} = (c_{i, j} - \tau_{i}^{k}) / 2\sigma_{i}^(k)$ とする．この時 $k=\textrm{argmax}_{k} u_{i, j}^{k}$ である．その後 $v_{i, j}$ を $[-0.99, 0.99$ ] に clip する

一言で言えば連続値の変数を $m$ 個の正規分布でクラスタリングし，一番当てはまりが良い分布に関する情報を持つ．論文では $m=5$ とし，もし単峰の変数だったとしても $m-1$ 個の正規分布に対する重みがゼロになるから構わないとしている．この手続きの結果，連続値の変数 $c_{i, j}$ を $u_{i, j}^{(1)},\cdots,u_{i, j}^{(m)}$ と $v_{i, j}$ の $m+1$ 次元で表現する．

離散値の変数について

$i$ 列目の離散値の全要素を $D_{i}$ として離散値 $d_{i, j}$ を one-hot encoding して $\mathbf{b}_{i, j}$ とする
$\mathbf{b}_{i, j}$ の各次元 $\mathbf{b}_{i, j}^{(k)}$ に $\textrm{Uniform}(0, 0.2)$ なノイズを加える
$\mathbf{b}_{i, j}$ を確率に正規化する

これら二種類の処理により， $n_{c} + n_{d}$ 次元のデータは $n_{c}(m + 1) + \sum_{i=1}^{n_{d}} |D_{i}|$ 次元に変換される．

また，これから説明する GAN は上記の $v_{1:n_{c},j},\, u_{1:n_{c},j}^{1:m},\, \mathbf{d}_{1:n_{d},j}$ を生成するわけですが，本来の値に戻すには次のように変換すればいい．

連続値 $c_{i, j} = 2v_{i, j}\sigma_{i}^{(k)} + \tau_{i}^{(k)},\ k = \textrm{argmax}_{k} u_{i, j}^(k)$
離散値 $d_{i, j} = \textrm{argmax}_{k} \mathbf{d}_{i, j}^{(k)}$

生成

Generator には LSTM を使う．LSTM を使う理由は we use LSTM with attention in order to generate data column by column. としか書かれていないが，気持ちを汲み取ると各変数間の相関などを陽に考慮したいからだと思う． LSTM の出力を $h_{t}$ として hidden vector $f_{t}=\textrm{tanh}(W_{h}h_{t})$ を求め，更に $\textrm{tanh}(W_{t}f_{t})$ として各変数を出力する．その後， $t+1$ ステップの LSTM に $f_{t}$ を渡す．連続値の場合は $v_{i}$ を得，次に $u_{i}$ を得る．また，離散値の場合は $t+1$ ステップにはそのまま渡さずに $f_{t}' = E_{i}[\textrm{argmax}_{k} \textrm{d}_i$ ] として渡す( $E_{i}$ は $|D_{i}| \times n_f$ 次元の embedding)．

Discriminator には mini-batch discrimination vector 入りの MLP を用いる(Generator が LSTM なのだから Discriminator も LSTM で良かったのではないか)．

通常の GAN の損失関数に加え， Generator 側の損失関数について連続値変数 $u$ に関する KL divergence $\sum_{i=1}^{n_c} \textrm{KL}(u_i', u_i)$ と離散値の変数そのものの KL divergence $\sum_{i=1}^{n_d}\textrm{KL}(\mathbf{d}_i', \mathbf{d}_i)$ を追加することで学習が安定するらしい．

実験

評価は三種類．

学習を生成したデータ，予測対象を元データとした時にどの程度精度を保つことができるかの Machine learning efficacy
- 前回の論文で model compatibility と呼んでいたもの
「変数間の相関が保存されているか」の検証として，連続変数を離散化して変数間の normalized mutual information を計算し描画
「真のデータにどれほど近いか」の検証として，学習データとテストデータまたは生成データ全対の距離のヒストグラムを描画

2019-08-25

Data Synthesis based on Generative Adversarial Networks (VLDB 2018) 読んだ

論文

[1806.03384] Data Synthesis based on Generative Adversarial Networks

匿名化については micro aggregation (各行を集約することで架空の行を生成すること) や post-randomization (ノイズを載せる) などがあるわけですが， GAN でデータを生成すれば完全な匿名化 (Generator があまりに賢くなりすぎて元データと全く同じものを生成しない限り) が実現できる，というアイデアにもとづく論文．

匿名化および GAN による生成の対象は Kaggler では「テーブルデータ」と呼ばれる 1 行 1 データ．つまりネットワークは表形式のデータの各行を生成する．同様の GAN には後発の TGAN ([1811.11264] Synthesizing Tabular Data using Generative Adversarial Networks) が存在し，実装も公開されている．後者では LSTM を用いたより複雑なネットワークを提案しているが，特に匿名化については言及していない．

実験結果について理解できない記述が多い．査読者はちゃんと読んだのか疑問に思う．もしくは匿名化に関して知見や興味のある査読者がいなかったのではないかと思う．

以下の問題意識が念頭にある
- 生成したデータにおいて平均や分散といった統計量を保存したい
- 変数間の整合性を保ちたい．たとえば身長 170cm なのに体重 30kg のデータが生成されると困る (十分に Generator が賢ければ避けられるのではないか)
- membership attack に備えたい (とはいえモデル中で陽に備えるわけではない)
生成対象の各行は 0 埋めした状態で正方形に形を変え，画像として扱う．いってしまえば MNIST の学習のような問題に落とす
提案手法である table-GAN を次の 3 モジュールで構築する
- Discriminator D : データの真偽を判定する
- Generator G : 偽のデータを生成する
- Classifier C : データの一部を label として (たとえば年収が平均値以上か否かの二値変数)，真のデータで学習して偽のデータを判定させる．これによって変数間の整合性が保たれる (と著者らは主張しているが， classifier は x と y の整合性を考慮するのであって x_i と x_j の整合性が保たれるわけではないのでは?)
損失関数を次の 3 項で構成する
- original loss : 本来の GAN の損失関数である D と G の間で発生する損失
- information loss : Discriminator D に真偽それぞれのデータを通して得られる最終層の dense vector の平均および分散の L2 norm．ここが一致していると平均および分散が保存されている (らしい．特定の minibatch における平均と分散を保存するのは難しいように思える)．ここで hinge loss を導入して生成されるデータの品質 (どの程度真のデータに近づけるか，あるいはプライバシーを保護するか) をコントロールする
- classification loss : Classifier C の損失
GAN に対する membership attack について考える．攻撃者が Generator G にのみアクセスできる状況において，当該 GAN を学習したデータに特定のデータが含まれているか否かの推定を以下の手続きで行う
- G から大量のデータを生成する
- その一部を使って複数の GAN を学習する
- それぞれの GAN の Discriminator D に対して
  - 学習に使った生成データ x を通して D(x), in というデータを得る
  - 学習に使ってない生成データ x を通して D(x), out というデータを得る
    - 論文ではこの負例側を元の GAN の学習に使っていないデータを用いており (In our case, we use the test set prepared for the model compatibility test.) ，実際の検証としては不適切である (攻撃者が元の GAN の学習データを知っているという状況がおかしい)．
- 上記データを全て結合して in/out を学習することで membership attack を実現する
  - GAN の GAN の精度はどのようなものでしょうか
いくつかの方法で検証を行う
- 実データと生成データの累積分布を見る
- 実データと生成データそれぞれで構築した学習器での回帰および分類の精度を検証する (model compatibility の検証)．これは「もし生成したデータが十分リアルならば，生成データで学習したモデルで元データの予測もうまくいくはず」という過程にもとづいている
  - 上記 2 項目については散布図を示すのみであり，「見ればわかるだろう」と言わんばかりに定量的にどの程度優れているか全く言及していない．確かに見ればわかりますがこんな雰囲気だけの結果でいいのか．
- 元のデータに対してある匿名化されたレコード r とのユークリッド距離が最も近いレコードを検索し，その時のユークリッド距離を DCR (distance to the closest record) と呼ぶ．DCR = 0.0 の場合元レコードと完全に一致しているので leak である，としている (この leak の定義がまず受け入れがたい．Quasi Identifier がわからなければそれ以外の値がどうなろうとどうでもいい話ではないか)．各種匿名化手法について複数のレコードについて DCR を計算し，その平均と標準偏差を確認する
  - 反対に言えば， DCR が小さければ小さいほど真のデータに近いことを意味している?
  - と思ったが It is preferred that the average distance is large and the standard devision is small と書かれており，標準偏差が小さい方が嬉しいことはわかる (むらなく一定の品質で匿名化できていることを意味する) が平均距離が大きいほうが良い理由がわからない．DCR はデータの確からしさとプライバシー保護とのトレードオフなので一概に preferred とは言えないのではないか?
  - Table 5 を見る限り low-privacy な table-GAN が high-privay な table-GAN より DCR の平均値が小さい．それはそう
- そもそもベースラインに設定している匿名化ツール ARX に関する記述が理解できないし，ベースラインとしてアンフェアな使い方をしているのではないか
  - 「ARX は micro aggregation するが sensitive attribute を変化させない．よって sensitive attribute に絞って最近傍探索を行うと DCR の平均と分散が 0 になる」と言及されている (そもそもの話として各データは職業や年齢，郵便番号といったそれらの列の値の組合せによって個人を特定しうる Quasi Identifier と，給料や疾病の状態 (十分 Quasi Identifier ではないか?) といったそれ以外の情報の列である sensitive attribute のふたつから構成されている)．
  - しかし，ツールの理念として Quasi Identifier のみを匿名化するのならば sensitive attribute がいくら leak しても困らないはずであるし (そもそもそれを leak と呼ぶのか?)，その時に DCR が完全に一致することは統計量が保存されているわけであり非常に望ましい性質ではないか
  - もし sensitive attribute が真に sensitive であり， leak して困るのならば sensitive attribute も含めた全ての列を Quasi Identifier とみなして k-anonymity を満たすように aggregate すべきではないか

2019-08-18

プロ話者 (声優・俳優など) 100 名から得られたコーパスである JVS (Japanese versatile speech) corpus が東大の高道助教によって公開されました

声優統計

音声合成研究のために，コーパスをリリースしました．100名のプロ話者（声優・俳優）× 100発話(パラレル)を含んでいます．今すぐダウンロードできます！！https://t.co/FJXrl3owrX https://t.co/qGuUCSqIyA
— Shinnosuke Takamichi (高道慎之介) (@forthshinji) August 17, 2019

Shinnosuke Takamichi (高道慎之介) - jvs_corpus

このブログを読んでいる人間は全員知っているとは思いますが，東京大学の高道助教によって JVS (Japanese versatile speech) corpus が公開されました．

JVS corpus は 100名のプロ話者から得られた様々な音声が含まれていますが，特に "parallel100" ... 話者間で共通する読み上げ音声 100 発話 は声優統計コーパスバランス文を読み上げたものです．ありがとうございます．多種多様な「遺灰のほとんどは、スウェーデン西海岸の、ブーヒュースレーン地方の小島にある漁村、フヤルバッカ周辺の海に、散骨された。」を聞くことができて幸せです．

こんなことになるなら声優統計コーパスの原稿を無理やりにでも英語にして arXiv にアップロードすべきだった．今からでも間に合うかもしれない．これまで仕事で書いてきたスクリプトや作った予測モデルよりこの音素バランス文の方が数倍社会に貢献しているのではないかと思います．

2019-08-08

Comprehensive Audience Expansion based on End-to-End Neural Prediction (SIGIR eCOM 2019) 読んだ

論文

Comprehensive Audience Expansion based on End-to-End Neural Prediction (pdf)

もうひとつオーディエンス拡張の論文．特にモデルが目新しいわけでもなく，実験もよくわからない (Table 3 は何を行っているのか意味不明) だけど気になったところを書く．

オーディエンス拡張は広告を配信したい人から「この人たちに類似したユーザに広告を配信したい」という seed となるユーザ S を受け取り，全ユーザ U の中から S に類似したユーザを探す作業である．Finding Users Who Act Alike (KDD 2019)では教師なしの手法で取り組んだわけですがこの論文では seed を正例，U - S からランダムにサンプリングしたものを負例として教師あり学習で解くアプローチにもとづいている．

負例をどの程度サンプリングすべきか
- 詳細が不明な実験の結果 (Table 3 がどのように得られたのかの説明が全く無いのですごい)，負例は正例の2倍程度が良い，と述べている
PU-Learning の枠組みとして捉えられるのではないか
- Positive (seed) と Unlabeled (U - S) として考えることで，ランダムなサンプリングよりもかしこく負例を得る
- 論文中で実験を行っているのは次の 3 手法
  - Partially Supervised Classification of Text Documents (ICML 2002) における Spy sampling
  - Pre-Train sampling (参考文献不明)
  - Bootstrap sampling (subset をサンプリングしながらモデルを学習・予測して負例をサンプリング)
- 実験の結果， Spy sampling が良いと述べているが Table 4 の要素がどういう理由で bold で記載されているのかが全く説明が無いのですごい
section 4 の実験は特に sampling strategy とは関係がない

2019-08-05

Finding Users Who Act Alike: Transfer Learning for Expanding Advertiser Audiences (KDD 2019) 読んだ

論文

Finding Users Who Act Alike: Transfer Learning for Expanding Advertiser Audiences

Pinterest におけるオーディエンス拡張を説明した論文．オーディエンス拡張の論文はあまり見かけないので良かった．

オーディエンス拡張 (あるいは look-alike) は広告を配信したい人から「こういう人に配信したい」というユーザのリスト (seed) を受け取り，それらに類似したユーザに対して広告を配信するメニュー．

一般的には seed ユーザを正例， seed ではないユーザをランダムにサンプリングしたものを負例として教師あり学習を行うらしい．しかしこの方法には

seed ごと (異なる広告配信ごと) にモデルを学習しなければならずコストが高い
seed のサンプルサイズが小さい場合に十分な精度が出ない

という問題がある．

提案手法

提案手法では

seed に依存せず，使い回すことができるユーザの埋め込みを学習する
その埋め込みにもとづいて近傍探索を行うことで配信対象のユーザを得る

という二段階の手続きを行う．

埋め込みの学習

埋め込みは次の手続きによって構築する．ちなみに，埋め込みはユーザごとに計算するのではなく，「ユーザの特徴量を受け取って埋め込みを得る関数」を学習する．これにより，未知のユーザに対しても埋め込みを得ることができる．

ユーザに関する特徴量をいくつかの pooling や layer に通すことで user embedding vector を得る
- モデル構造や特徴量について詳細な言及はなし
Pin をその画像やテキストにもとづいて topic の集合として表現し，user embedding vector と同じ長さの topic embedding vector を得る
- こちらもモデル構造や特徴量について詳細な言及はなし
あるユーザが興味を持った Pin の topic の embedding をとし，興味を持ってない topic の embedding をとしてという損失関数を最小化する．つまりは興味を持っていないペアの内積より興味を持ったペアの内積を大きくするようにする．
- ここで学習される埋め込みを求める関数はどのようなものだろうか．実際に使う際には user embedding $u$ を返す関数だけなのでユーザの特徴量表現に行動履歴などが含まれるのだろうか．さすがに属性情報だけではないだろう．よくわからない．

配信対象ユーザの計算

埋め込みにもとづいて seed に類似するユーザを計算すれば終わり．ですが，たとえば seed に多様性がある場合，ナイーブに seed の embedding の平均を使って検索してしまうとどの seed にも似ていないユーザばかりが得られてしまう (どれぐらい差があるのかの offline での検証などは無し)．そこで，

Locality Sensitive Hashsing を用いてユーザの embedding を [tex:2^m] 個の Region に分割する
seed を各 Region に割り当て， Region $r_i$ に含まれる seed の数を $c_{s, r_i}$ とする
全ユーザが各 Region にいくつ存在するかを数え $c_{b, i}$ とする
density score $d_{s}(r_i) = \frac{c_{s, r_i} + \alpha}{c_{b, i} + \beta}$ とする
これを m 回繰り返し $m 2^{n}$ 個の density score を得る
Region r に含まれるユーザのスコアを $\frac{1}{m}\sum d_{s}(r)$ とする

とする．

実験の結果は

seed が小さい時にはこの方法が有効
seed が大きい時は提案手法と教師あり学習の結果とを組み合わせることで教師あり学習単体よりも改善する

ことを示している．

2019-07-12

Personalized Purchase Prediction of Market Baskets with Wasserstein-Based Sequence Matching (KDD 2019) 読んだ

論文

Personalized Purchase Prediction of Market Baskets with Wasserstein-Based Sequence Matching

KDD 2019 の Accepted papers が出たのでひとまずタイトル一覧に目を通し， arXiv などに既にあるものから読んでいこうと思います．しかしあまりにも Graph Convolutional Network が多すぎる．

ユーザ $c$ が $k$ 回目の購買 $b_c^{k}$ において複数の商品を購入している (この時，各購買を basket と呼びます) 状況において， $m_c$ 個の購買の系列を学習データとして $m_c + 1$ 回目において購入される商品 $b_{c}^{m_c + 1}$ の exact set の予測に取り組んでいる．

わざわざ exact set と強調した理由ですが，これまでの next basket recommendation，たとえば

では「 $m_c+1$ の購買においてどの商品を買いそうか」を推定・予測していました．すなわち，これら既存研究におけるモデルの出力は各商品が購買される確率です．が，本研究では basket の中身を直接出力します．「 $m_c+1$ 回目の購買において商品 A は 0.3， B は 0.21， C は 0.17 の確率で購入される」ではなく，「basket $b^{m_c + 1}_{c}$ は A と D と J である」を予測結果として出力する．

しかし，このタスクはただ難しくなっただけのように見え，実際これが解けるとどう嬉しいのかがよくわかりません (著者らも明確に述べていないように見える)．クーポン配信などを考えた場合には商品の購買確率が出る方が嬉しいように思います．複数の商品をすることでまとめ買いなどの効果がある，ということなのでしょうか．

手法

一言でまとめると，あるユーザ $c$ の過去の全 basket から構成される系列 $B_c$ について最も類似した basket の部分系列 $B_i[i_s:i_e]$ を検索し，その部分系列のひとつ先 $B_i [i_{e + 1} ]$ を予測対象である $b^{m_c + 1}_c$ として出力します．そのために

商品の集合である basket のペアについて類似度を計算する
- それぞれの商品をある次元に埋め込む
- 埋め込みの集合で表現された basket 対について Wasserstein Distance を計算する
$B_c$ に最も類似した部分系列を高速に計算する

という作業を行う必要がある．

商品の埋め込み

埋め込みは

$\sum_{p \in b^{i}_c} \sum_{q \in b^{i}_c,p \neq q} \log Pr(p|q)$

$Pr(p|q) = \frac{\exp(u^{T}_p v_q)}{\sum_r \exp(u^{T}_p v_r)}$

と同一 basket 内で同時に購買された全ペアについて計算する．これだけなら追試ができそう．

Wasserstein Distance の計算

Wasserstein Distance を計算する．

部分系列の高速な検索

類似度の計算には Dynamic Time Warping を使うが，ナイーブにやるとクエリであるセッションの系列長を $n$ ，部分系列の検索対象であるセッションの系列長を $m$ とすると $O(nm^{2})$ かかる．全ユーザが $k$ なのでこれでは重くて困る．しかし Stream Monitoring under the Time Warping Distance (ICDM 2007) を使うと $O((n+1)m)$ に落ちるので嬉しい(らしい)．この論文誰かに解説して欲しい．

実験

Instacart dataset と Ta Feng Grocery Dataset を用いた実験を実施．比較手法があまりにシンプルで悲しくなる．アソシエーションルール以外には「全体の人気順に上位 $n_c$ 個」「ユーザごとの人気順に上位 $n_c$ 個」という手法 ( $n_c$ は $c$ の最後の購買において買った商品数) を採用しているわけですが，既存の商品ごとに計算する session-based な手法の結果の上位 $n_c$ 件とも比較しないとフェアではないと思う．

2019-05-08

Personalized Top-N Sequential Recommendation via Convolutional Sequence Embedding (WSDM 2018) 読んだ

論文

Personalized Top-N Sequential Recommendation via Convolutional Sequence Embedding (pdf)

A Simple Convolutional Generative Network for Next Item Recommendation (WSDM 2019) を読もうとしたところ引用されていたのでまずはこちらから読む．WSDM 2019 の方は dilated 1d conv + residual unit という感じで WaveNet に非常によく似た形なのであまり読むモチベーションが上がらない．余談ですがこの構造を "A Simple but Hard-to-Beat Baseline" と名付ける著者らが理解できません．

問題はユーザ $u$ における閲覧などによって得られる $t -1$ 個の item の系列 $S_1^{u}, S_2^{u}, \cdots$ を入力として $S^{u}_{t}$ 以降の item を予測する，というものです．

Marcov Chain や FPMC (昔読みましたね) といった既存手法では $t$ より前の item から個別に将来のどのアイテムがどれだけ発生しやすいかをモデルする point-level な推定を行っていた．しかし系列の傾向を捉えるには union-level なモデル化が必要．また， point-level な推定では skip (陽に隣り合っているわけではないが関係するもの) が考慮できない(これを association rule で示している図が面白いのだけれど説明が少なすぎるので理解が正しいのかがわからない．)．のでモデルに組み込んでいく．

手法

ConvolutionAl Sequence Embedding Recommendation (Caser) を提案している．ある user の長さ $L$ の系列を入力として $T$ 個 item を予測するモデルを考えて $L+T$ の窓をずらしながら学習していく．

方針としては

$L$ 個の item について，それぞれに $d$ 次元の embedding を lookup することで $L \times d$ の matrix を得る．これを image と見なして操作していく．
この image に二種類の filter を適用し，次の操作を行う
- 高さで幅の複数行を移動しながら系列性を抽出する holizontal convolutional filter
  - 高さ $1 \leq h \leq L$ なるフィルタを使い， activation function に通すことで $L - h + 1$ 個の値が得られます．その後，max pooling を行うことで 1 つのフィルタにつき値を 1 つ得る．
  - これを $h$ を変えた $n$ 個のフィルタを用意し，操作することで $n$ 次元の値を得る．これを $\mathbf{o}$ とする．
- 高さで幅 1 の各列を移動しながら抽出する vertical convolutional filter
  - こちらは $\tilde{n}$ 個のフィルタを準備し $d$ 列分抽出を行うので結果 $d\tilde{n}$ 次元の値を得る．これを $\tilde{\mathbf{o}}$ とする．
$\mathbf{o}$ と $\tilde{\mathbf{o}}$ を連結したものを FC 層に通し，更に user ごとの embedding を lookup し連結して最後に item の確率を出す層につなぐ