糞糞糞ネット弁慶

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

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 すべきではないか

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

声優統計

Shinnosuke Takamichi (高道 慎之介) - jvs_corpus

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

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

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

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 手法
    • 実験の結果， Spy sampling が良いと述べているが Table 4 の要素がどういう理由で bold で記載されているのかが全く説明が無いのですごい
  • section 4 の実験は特に sampling strategy とは関係がない

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 u を得る
    • モデル構造や特徴量について詳細な言及はなし
  • Pin をその画像やテキストにもとづいて topic の集合として表現し，user embedding vector と同じ長さの topic embedding vector t を得る
    • こちらもモデル構造や特徴量について詳細な言及はなし
  • あるユーザ i が興味を持った Pin の topic の embedding を t^{t} とし，興味を持ってない topic の embedding を t^{-} として \frac{1}{k * n} \sum_{i=1}^{n} \sum_{j=1}^{k} \textrm{max}(0, 1 - (u_i \cdot t_{j}^{+} - u_{i} \cdot t_{j}^{-} ) ) という損失関数を最小化する．つまりは興味を持っていないペアの内積より興味を持ったペアの内積を大きくするようにする．
    • ここで学習される埋め込みを求める関数はどのようなものだろうか．実際に使う際には user embedding u を返す関数だけなのでユーザの特徴量表現に行動履歴などが含まれるのだろうか．さすがに属性情報だけではないだろう．よくわからない．

配信対象ユーザの計算

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

  • Locality Sensitive Hashsing を用いてユーザの embedding を [tex:2m] 個の 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 が大きい時は提案手法と教師あり学習の結果とを組み合わせることで教師あり学習単体よりも改善する

ことを示している．

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 件とも比較しないとフェアではないと思う．

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

機械学習のための特徴量エンジニアリング ―その原理とPythonによる実践 (オライリー・ジャパン) 読んだ

www.amazon.co.jp

訳者よりご恵贈いただきました．8年前に kaggle のアカウントを作ったきりの人間であるため，この文章にさほど価値があるとは思えませんが感想を書きたいと思います．

ロジスティック回帰や決定木，ランダムフォレストやニューラルネットワークなどの機械学習アルゴリズムにどのようにデータを入力するか，ただのデータをよりアルゴリズムのパフォーマンスが改善するように加工する作業を「特徴量エンジニアリング」と呼びます．

本書はその特徴量エンジニアリングの基礎である

  • 変数の値をそのまま使うのか，二値化するのか，区分に分けて離散化するのか，対数を取るのか，値を一定の区間に揃えるのか
  • テキストをどのように特徴量にするのか，どう処理すべきか，どう重み付けるのか
  • カテゴリ変数をどのように扱うのか，カテゴリの数が増えた時にどう対処するか
  • 変数の数が多い時にどう減らせば良いのか
  • k-means クラスタリングを用いることで非線形な特徴量抽出が可能になること
  • 画像の特徴量をどう取り出すのか，そして深層学習がどのように特徴量を抽出するのか

といった内容を，「なぜこの加工を行う必要があるのか」「どう嬉しいのか」「どのように問題があるのか」を踏まえながら紹介しています．

また，最後には類似論文の検索アルゴリズムについて，仮説構築，データ加工，実験，仮説の再検証の 4 ステップを繰り返すことでこれまで取り組んできた内容の実践を行っています．

僕が読んでいて面白かったトピックを取り上げます．

  • 5章. カテゴリ変数の取り扱い
    • 僕が日々扱うデータはカテゴリ変数であることがメインであるため，この章は非常に示唆深いものでした． Hasing を用いたカテゴリ変数はどうにも飲み込めていなかったため，本書の説明で理解が明瞭になりました．
    • また，ビンカウンティング (このような呼び方をするのも学びです) についても，次に予測モデルを構築することがあったらぜひ試そうと思えるものでした．
  • 7章. 非線形特徴量の生成 : k-means を使ったスタッキング
    • 「目的変数と説明変数に非線形な関係がある時，または説明変数が非線形な多様体上に分布している時 (余談ですがこの『多様体』という単語の使い方は多様体を専門にしている人にとっては許されるものなのでしょうか) 線形モデルでそれをどのように表現するか」という時の対応策として，説明変数に k-means クラスタリングを適用することにより，非線形特徴量が抽出できることを説明しています．
    • この操作がどの程度効果があるのかは図7-7 を見れば一目瞭然です． k-means によって説明変数が割り振られたクラスタを説明変数に追加することにより，ただのロジスティック回帰がランダムフォレストや SVM などに匹敵する AUC を示しています．
    • すぐにこの操作に飛びつかぬよう，計算量の問題やデータリークが起こることへの言及がなされている点も良いと思います．
  • 9章. バック・トゥ・ザ・「フィーチャー」 : 学術論文レコメンドアルゴリズムの構築
    • 単にこれは僕がステップ・バイ・ステップで作業を進めながら検証を行う様子が好きなのでこの章に言及しました．

おそらく，本書に最も価値があるのは「何気なくやっている操作を言語化・テキスト化した」という点ではないでしょうか． 大体の場合僕たちは何も考えずに対数を取ったり正規化をしたり TF-IDF を計算するわけですが，では「なぜその操作を行うのか」「そのデメリットは何か」を説明しようとした時，たとえば入社一年目の新人に聞かれた時，少し戸惑ってしまうのではないでしょうか (説明が全く無理とは言っていません)． 「Python は書けるし scikit-learn のドキュメントも読めるので予測モデルを作ってみたい」という入社一年目の新人に「一通り抑えてほしい内容が書かれているのでまずは全部読んでくれ」とこの本を渡し，可能であればそれぞれ試してみて精度や計算時間，メモリ使用量がどう変わるかを試してもらうのが良いのではないでしょうか (本書の例でも必ずしも精度がめざましく改善する，つまり，特徴量エンジニアリングがいつでも「銀の弾丸」となるわけではないことが示されており，ここにもリアリティを感じます)．

しかし，わがままを言えば，更に突っ込んで欲しかった話題があります．それは「ニューラルネットワークや勾配ブースティングのような十分複雑なモデルを用いる上で特徴量エンジニアリングはどれだけ貢献するのか，貢献するものとしないものがあるのではないか」というものです．先程述べたような k-means による特徴量変換はロジスティック回帰に投入することで精度の改善を説明していますが，同じ特徴量を Random Forest に投入するとどうなるのでしょうか．さすがに kaggle のような競技プログラミングや実務に寄り過ぎた話題であるため本書の範疇外だとは思いますが．kaggle の kernel を読めという話なのかもしれません．