糞糞糞ネット弁慶

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

IBIS 2019 行った

第22回情報論的学習理論ワークショップ (IBIS 2019) | 第22回情報論的学習理論ワークショップ, 2019.11.20〜23, ウインクあいちに行った.

  • 昨年の札幌に比べると名古屋は近い
  • いつもの胃ではなく腸の具合が完全に悪くて半分ぐらいまともに発表を聞かずにトイレにいた
    • ウインクあいち2階上のトイレは人も少なくホールの音声も聞こえて快適
    • 抗生物質を処方された時は忘れずに整腸剤も貰わないと本当に駄目だと痛感しました
  • 有料のチュートリアルも聞きたかったのですが朝から握手会があったので断念

11/20

グラフ文法を用いたグラフ生成

  • 「化学構造式のためのハイパーグラフ文法」を発表した(JSAI2018) で予習していた
  • 分子グラフの生成をしたい
  • (ハードな)原子価の制約を必ず満たす分子ハイパーグラフ文法を提案
  • ソフトな制約は VAE で学習する
  • 全てを深層学習でやるのではなく,ハードな制約があるのならばそれはそれで抽出し,そうでない部分を学習する,という話の構造が大好きです
  • always generate valid molecules って響きがかっこいいですね

回帰による再帰ニューラルネットワークからの重み付きオートマトンの抽出

  • 前半をトイレで音だけ聞いていたら話に全くついていけなかった

隣接代数と双対平坦構造を用いた学習

  • はじめに Matrix Balancing という操作が登場する
  • Matrix Balancing できると何が嬉しいのかよくわからないまま話を聞いていたので本当に駄目

招待講演はホテルに戻って腹痛と格闘.

ポスター

  • 1-020: ニュース推薦システムにおける各種埋め込み手法の比較検討
    • 「色々埋め込みを試したけど人気順で推薦するのと対して精度が変わらない,時間と資源を使って深層学習をやる意味は本当にあるのか?」という話が良かった
  • 1-021: 広告種類を考慮した不均衡データからのCTR予測モデルの学習
    • 「とりあえず A/B テストで検証できる」みたいな環境は良い
  • 1-022: 制約付きオンライン凸最適化によるアドネットワークのクリック単価決定
    • 「良いシミュレータを作っておくと様々な戦略を実験できる」という話が良かったので公開して欲しい
  • 1-026: 半教師あり介入効果推定
    • 介入効果推定のブームに乗りたい
  • 1-037: なぜ血液検査値は対数正規分布になるのか
    • タイトルが「なぜなるのか」なのにポスターの冒頭が「対数正規分布になる」なのが良かった
  • 1-045: 購買履歴データに基づくポイントカードユーザのクレジット切り替え行動分析モデル
    • ポイントカードのクレジットカード機能付への切り替えが F-measure 0.9 で予測できたという話
    • 本当なら全員が幸せだけどさすがになにかおかしくないですか,みたいな話をする
  • 1-094: 未知のバイクシェアポート需要予測のためのノンパラメトリックベイズ生成モデル
    • 久しぶりにグラフィカルモデルを見て新鮮な気持ちになる
  • 1-113: 混合エキスパートモデルによる略語や表記揺れに頑健なテキスト名寄せ
    • Mixture of Experts の響きがかっこいいという話と,タスクの絶妙な面倒臭さ・泥臭さの対比が良かった

11/21

サンプリングによるデータ駆動科学

データ駆動科学の立場からみた物質科学と情報科学の接点

  • これまでの研究
    • MD の結果をひたすら見る
    • 分子の向きを少し変えた結果をひたすら見る
  • 計算化学から計算科学へ
  • 計測データを計算データでフィット
  • 第一原理電子状態計算を利用したポテンシャルのフィッティング
    • 原子間に働くポテンシャルのデザインがシミュレーションに重要
    • NN によるポテンシャルモデリングの試みは 95 年ごろから
      • 表面化学反応のシミュレーションは大事だけど面倒
      • 第一世代の問題 : 表面ごとに表現する必要があってだるい,三次元配置を入力にすると精度が出ない
    • アモルファス内のイオン安定配置の全探索も NN ベースでやる
  • スペクトル解析(ピーク位置推定)に EM を使ったり,データが多くてもよく考えると離散値なのでヒストグラムにまとめて sum を取って高速化したり
    • 情報系のテクニックによって成果になる

集団運動におけるデータ駆動科学

  • 集団行動
    • 動物行動,歩行者,子供の遊び,スポーツ
  • 物理学的な動的システムの理解
    • x_{t+1} = f(x_{t})
    • f が既知で解析的に解ける
    • f が既知でも解析的に解けない (歩行者モデル, helbing 2000)
  • 集団運動は階層性.非線形性のある実環境での理解が難しい -> データで推定したい
  • スポーツの戦術分析
  • モデル化と理解のトレードオフ
    • モデル駆動 (方程式ベース)
      • 原理は理解できるが複雑にならない
    • データ駆動 (方程式フリー)
      • 複雑になるが原理は理解できない
    • データ駆動的なモデル化でギャップが埋められるのではないか
  • 「音楽だけ与えると子供は回りだすんですよ」
  • データから特徴抽出したい
  • 集団行動分析は既存研究が少ないので可視化・理論・解釈を工夫
  • 動的モード分解 : クープマン作用素のスペクトル分析
  • 集団行動解析のためのグラフ DMD
    • 問題 1 : モードの可視化解釈が難しい
    • 問題 2 : 個体間に依存関係を持つはずが従来のDMDでは反映できない
    • そこで Graph DMD
    • 集団運動の動的情報抽出,大規模な運動の分類
    • データ駆動的な解釈
  • 良い話だと思うのですが動的モード分解が「行列・テンソル分解の複雑なもの」ぐらいの粒度でしか理解できなかった

ポスター

  • 2-002: Causal Outcome Prediction on Combinatorial Action Spaces
    • 施策 a の組み合わせが膨大な時に全パターンを網羅するのは大変
    • 特徴量 xa との対を受け取って変換し uniform な施策の変換結果となるべく近づけるように学習
    • 既存研究のタイトルを聞き忘れた
  • 2-013: 勾配ブースティング木における木成長時の勾配情報更新による学習加速
    • 本家 xgboost に merge される予定があるのか聞くのを忘れた
  • 2-018: グラフィカルモデルを用いた犯罪発生リスクエリアのスパース性を考慮した相関関係の可視化
    • グラフィカルモデルが bayesian なそれではなくて「グラフィカルな」の意味で使われていて勘違いしたので別の語を使ったほうがいいと思う
  • 2-037: 人間GAN:人間による知覚的識別に基づく敵対的生成ネットワーク
    • 誰しも一度は考えたことがある Discriminator に人間を使う GAN
    • どう backpropagation するのかと思ったら人間への聞き方を工夫すると微分の近似になるというのが良かった
  • 2-047: SGDの挙動解析に基づくデータクレンジング
    • 本当にいい話で良かった
  • 2-056: 早期終了タイミングを予測する:深層学習における確率勾配の分布の変化点検出
    • いい話だった
  • 2-084: 機械は乱数の夢を見るか
    • ポスターの結論が「機械は乱数の夢を見る」だったのが良かった
  • 2-110: 訓練事例が機械学習モデルの予測に与える影響の測り方
    • 人が多くて聞くことができなかった

11/22

「深層学習の理論」はホテルで作業.

機械学習工学」の休憩時間に後ろから大学関係者による「数式が出てこない発表は面白くないなあ!」という大きな声が聞こえて参加者の興味も幅広いものだと思う.無理に聞かずにホテルに戻ればよかったのではないか.

機械学習に対するソフトウェア工学の技術動向

  • ソフトウェア工学
    • 要求工学 : システムの要求を定義・合意・記述しその妥当性確認をする
    • 設計 : 品質を実現する
    • テスティング : 不具合に代表される様々な品質の問題に対応する
  • 従来 : シナリオで書ける
  • 機械学習 : 曖昧な入力と曖昧な実装,曖昧なデータに対する評価
  • どう難しくなってるか?
    • アンケートによると「顧客との意思決定」「テスト・品質の評価・保証」が特に難しい
    • 考え方を変えなければならない
  • 契約・仕様・受け入れの課題
    • 何ができるか具体的には事前に約束できない
      • 作らないとわからない
      • 準委任 (頑張ろう)
      • 後出しで文句言いやすい
    • PoC
      • お試しで終わることが多い
    • 不確かさが多くて納得しにくい
      • どうして?
  • 保守の課題
    • 技術的負債
    • (疑問 : 負債負債というけれど 3-5年後も同じアプリが必要になるのか?)
  • テスト技術の例
    • そもそもこのあたりで「何をテストしたいのか」という明確な定義が無いままに話が進む
      • コーディング?
      • ロジック?
      • パラメタ推定手続き?
      • 推定されたパラメータ? (恐らくこれっぽい)
    • テスト不可能
    • テストでバグを見つけるとは?
    • 単体テスト
      • でかいから無理
    • 要求カバレッジ? 同意クラス?
      • 広すぎる
    • コードカバレッジ?
  • メタモルフィックテスティング
    • 例 : sin(x) と sin(pi-x) が一致することを確認
    • これを繰り返す
    • いろいろな例を作る
  • サーチベースドテスティング
  • システムレベルの要求に基づくテストの例
    • VerifAI (Berkeley)
  • 形式検証技術の適用
  • デバッグ技術の例
    • 分類ミスした事例の特徴量を比較して再選択 -> 能動学習のような話
  • 質疑では「これは一体何をテストしているのか」「感度分析とかありますよね」という話になる

機械学習知財・契約

  • この領域で多くの記事を書いているSTORIA法律事務所による講演
  • 収集
  • 開発
    • 何が知財で守られるのか
  • 展開
  • データの種類 x 取得方法 x 規約
  • データ収集の問題点
    • 医療機関から医療データをもらう
      • 個人情報
      • 三者提供は同意が必要
      • 前向き研究はできるが後ろ向き研究は不可能
      • 委託スキームでやるとか
    • 店頭顔写真リアルタイム分析で情報提供
      • 個人データの第三者提供
      • いちいち同意を取るのか?
      • 複数から委託してデータをマージすると問題になる
    • 自然言語クロール
      • 情報解析のためであれば複製が可能
  • よくある質問
    • ベンダとして事業会社と共同プロジェクトをやりたい
    • ユーザ : 自社で独占したい
    • ベンダ : うちのノウハウが入ってるし横展開したい
    • 知財であるものないものを認識する
  • 展開の重要性
    • 成果物や派生物が思わぬ価値を生むことがある
    • 作って終わり・作業して終わりではない
    • 成果物をどう使うかを最初に定める必要がある
    • 様々なパターンにわけて解説が行われたわけですが,途中からどうにもわからなくなる.「開発ベンダが成果物を横展開したい場合」などはあまり現実的ではないように思う
  • 「存在しない顔を生成する」と謳うベンチャーが昨今多いが,実在の人物 A に似た顔があったとしても A はプライバシーや肖像権を主張できないのか,という質問がしたくて手を挙げるも司会者に無視された

継続的改善をし続けるための機械学習基盤の課題

  • typical steps for machine learning project
  • データが振る舞いを決めるため確率的にエラーを抑えることしかできない
    • AUC/loss が改善しても本当にコンバージョンが改善するのか
    • またそれは別の話ではないのか
  • 確率的な挙動をするため変更の影響範囲を事前に予見できない
  • Same code, CI passed, but prediction fails
    • 大人の声で学習したモデルが若者の間で流行るも精度が劣化
    • 工場の画像検査システムが光の条件が変化して破綻
    • 検索ランキングが新規要素出現で性能が劣化
    • (コンセプトドリフトではないと思う)
    • (そもそも未知の状態をどこまで想定するかでは?)
    • (「猫を電子レンジに入れるな」という但し書きをどこまで機械学習領域で行うのか?)
  • チームをまたいで頑張ろう
  • 後半はツールの紹介が多くてどうにも散漫に感じた

日本におけるデータサイエンスの現状と今後

  • データサイエンティストの必要性
  • ビッグデータとデータサイエンス
    • 進歩してるから頑張ろう
  • DS教育の滋賀大モデル
    • 統計,CS, 実データを用いた演習
  • ビッグデータとデータサイエンスの諸側面
    • 共同研究はうまくいったりいかなかったり
    • 課題駆動型アプローチとデータ駆動型アプローチ
  • 「なぜ日本に統計学部・学科がないのか,その歴史的経緯」「滋賀大学で開講するにあたってどのような苦労があったのか」「今後国策として統計学部・学科を本気で増やそうとしているのか,一過性のブームなのか」という話が聞きたくて手を挙げるも司会者に無視される.次回から質問する時には異常な音や光,悪臭を発する必要があると学びました

Synthesizing Tabular Data using Generative Adversarial Networks (preprint) 読んだ

[1811.11264] Synthesizing Tabular Data using Generative Adversarial Networks]

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 を計算し描画
  • 「真のデータにどれほど近いか」の検証として,学習データとテストデータまたは生成データ全対の距離のヒストグラムを描画

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 は xy の整合性を考慮するのであって x_ix_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 が多すぎる.

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