糞糞糞ネット弁慶

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

プロ話者 (声優・俳優など) 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 件とも比較しないとフェアではないと思う.

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 を読めという話なのかもしれません.

300 万ノード 1 億エッジからなる日本語版 Wikipedia のリンク構造から学習した見出し語の node2vec (分散表現) を公開しました

タイトルの通りです.Wikipedia 本文を用いた埋め込みは

がありますが,リンク情報を用いた埋め込みは見かけなかったので公開します.このデータが誰かの何かの役に立てば幸いです.

ダウンロードリンク

2 種類のファイルを用意しました.

手法

グラフ埋め込み (Graph Embedding) はノードとエッジからなるグラフデータを入力とし,ノードごとの埋め込み表現 (分散表現, Embedding) を得る手法です.グラフからなんらかの手法でサンプリングを行うことで,順序のあるノードの系列を複数生成し,これを文とみなした上で Skip-Gram with Negative-Sampling を用いてノードに対する分散表現を計算する,というのが現状の僕の理解です.一昨年から自分の中で注目している分野です.

今回は Jure らによって提案された node2vec (node2vec: Scalable Feature Learning for Networks, KDD 2016) を使います.node2vec の説明は元論文を読むか, nzw さんによる node2vec: Scalable Feature Learning for Networks を参照してください.

データ

2019 年 1 月 21 日時点における日本語版 Wikipedia のリンク構造を用います.Wikimedia Downloads に公開されている

  • jawiki-latest-pagelinks.sql.gz : リンク構造が格納されたファイル
  • jawiki-latest-page.sql.gz : ページ ID とそのタイトルが格納されたファイル

の二つを用いることで,日本語版 Wikipedia に存在するすべてのリンク関係のうち,リンク先のページにタイトルが振られているものを全て残しています.

細かい話をすると,jawiki-latest-pagelinks.sql.gz におけるリンク構造は「ページ ID (from_id と呼びましょう)」から「ページタイトル (to_title と呼びましょう)」への形式で記述されているため,to_title に対応するページ ID を jawiki-latest-page.sql.gz から見つけなければなりません.しかし,これらのファイルには

  • from_id に対応するタイトルが jawiki-latest-page.sql.gz に存在しない
  • to_titlejawiki-latest-page.sql.gz に存在しない

といったよくわからない状態が発生します.前者については from_id を新たなタイトルとして扱い,後者についてはそのエッジおよびノードを削除しました.

結果的に,ノード数 3,361,556 件 (ユニークタイトル数 2,953,052 件)*1,エッジ数 118,369,335 本の重み無し有向グラフを構築しました.

構築においては MySQL のダンプファイルを一度データベースにインポートするのではなく, jamesmishra/mysqldump-to-csv: A quickly-hacked-together Python script to turn mysqldump files to CSV files. Optimized for Wikipedia database dumps. を用いて(一部改変して) TSV ファイルに変換しました.これは便利.また作業の都合上,"!'\ といった記号を全てタイトルから削除しています.

計算

実装は Jure らによる実装 (snap-stanford/snap: Stanford Network Analysis Platform (SNAP) is a general purpose network analysis and graph mining library.) を用いました.

計算環境は Google Compute Engine を用いました.特に今回の計算は,

  • コア数が増えれば増えるほど計算が早くなる実装である
  • メモリを非常に消費する (450GB 程度)

といったことから vCPU x 96 / メモリ 624 GB という高スペックなマシン (n1-highmem-96) を使用しました.このマシンは 1 時間あたりの費用が $3.979 と比較的高額ですが,これまで利用していなかった $300 のクレジットがあったので 10 時間ほどかかりましたがどうにか自腹を切らずに済みました.ありがとう Google

デフォルトのパラメータではなぜかすべての値が -nan になってしまうため,# of negative sampling を 4 に,SGD の初期学習率を 0.01 としました (snap-adv/word2vec.h にハードコードされています.引数で変更できるようにしてほしい.).その他のパラメータは node2vec の実装のデフォルト値を設定しています.

得られた埋め込みはどうか

では,得られた埋め込みを使ってみましょう.

jawiki_n2v.w2v_c_formatword2vec C format で記載しているのでそのまま gensim で読み込むことができます.

>>> import gensim
>>> model = gensim.models.KeyedVectors.load_word2vec_format("./jawiki_n2v.w2v_c_format")
>>> model.most_similar("大久保瑠美", topn=3)
[('高橋李依', 0.9941796064376831), ('阿澄佳奈', 0.99155592918396), ('斉藤壮馬', 0.9913237690925598)]
>>> model.most_similar("乃木坂46", topn=3)
[('欅坂46', 0.9911350607872009), ('生駒里奈', 0.9882588386535645), ('シュートサイン', 0.9879196882247925)]
>>> model.most_similar("新宿駅", topn=3)
[('池袋駅', 0.9909403324127197), ('渋谷駅', 0.9906771779060364), ('上野駅', 0.989866316318512)]
>>> model.most_similar("アボカド", topn=3)
[('デヒドロアスコルビン酸', 0.9737377166748047), ('ビタミンB2', 0.9736371636390686), ('ルテイン', 0.9733775854110718)]
>>> model.most_similar("バナナ", topn=3)
[('キャッサバ', 0.9832699298858643), ('ヤムイモ', 0.9814094305038452), ('パパイア', 0.9809246063232422)]

なんとなく本文から学習された埋め込みと違う結果になっていることがわかります. 特に「バナナ」では果物ではなく,「主食」という意味合いでキャッサバやヤムイモが類似していることがわかります.面白いですね.

*1:なぜユニークカウントをしているかというと,異なる namespace に所属している同じタイトルが異なるノードとして扱っているためです.