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 の確率を出す層につなぐ

2019-03-01

機械学習のための特徴量エンジニアリング ―その原理と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 を読めという話なのかもしれません．

2019-01-25

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

論文メモ

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

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

ダウンロードリンク

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

jawiki_n2v.txt.tar.gz : jawiki_n2v.txt.tar.gz は namespace ，ノード名，埋め込みベクトルの値を半角スペースで連結したファイルです
jawiki_n2v.w2v_c_format.tar.gz : jawiki_n2v.w2v_c_format.tar.gz は namespace が 0 のものだけを word2vec C format で記述したファイルです

手法

グラフ埋め込み (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_title が jawiki-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_format は word2vec 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 に所属している同じタイトルが異なるノードとして扱っているためです．

2019-01-18

MovieLens dataset や ImageNet や CaboCha 付属モデルファイルはそのままでは商用利用できない

メモ

タイトルそのままです．
機械学習領域において有名なデータはよくライセンスを確認してみるとそのままでは商用利用ができないことがしばしばあります．
ブログや Qiita に書いたり，大学研究者であれば問題になりにくいとは思いますが，なんらかの企業に所属して研究開発やシステム開発を行っている場合には注意が必要になることがあるかもしれません*1．
色々あってライセンスについて少し調べたのと，ウェブ上での言及を見かけなかったのでここにメモを残します．

MovieLens dataset

MovieLens | GroupLens
MovieLens dataset (以降 MovieLens) は GroupLens によって収集・公開されている映画の評価データです．
このデータはそこそこの量があること，映画という馴染みの深い題材であることから，協調フィルタリングや行列分解を用いた推薦問題を解く際のサンプルデータとして有名です．
MovieLens のライセンスには

The user may not use this information for any commercial or revenue-bearing purposes without first obtaining permission from a faculty member of the GroupLens Research Project at the University of Minnesota.

とあり，許可を取らなければ商用利用できないことがわかります．

ImageNet

ImageNet
ImageNet は画像とタグの集合のペアが大量に入ったデータです．深層学習による画像分類を行う上で定番のデータではないでしょうか．
ライセンスを確認してみると

Researcher shall use the Database only for non-commercial research and educational purposes.

とあります． MovieLens と違って交渉の余地が無さそうです．

CaboCha

CaoboCha: Yet Another Japanese Dependency Structure Analyzer
CaboCha は taku910 氏によって開発・公開がされている係り受け解析を行うためのソフトウェアです．
CaboCha にはモデルファイル (CaboCha が用いている機械学習モデルのパラメータ) が付属されていますが，これは通称毎日新聞コーパスという有償の言語資源を用いて学習が行われています．
そのため，

そのため配布しているモデルをそのままの形で使うことは, 研究目的, 個人利用に限られます. 誤解ないように言っておくと, これは, CaboCha の利用が研究目的に限定されていることを意味しません。 ご自身で用意なさったコーパスを基に, 独自にモデルを学習, 作成した場合は研究目的以外の利用が可能です。

と明記されています．

CaboCha を用いた商用システム開発，たとえば企業のチャットボットが内部で係り受け解析を行うには付属のモデルファイルをそのまま使うことができません．みずから言語資源(日本語文章と，それらに対応する形態素や構文情報など)を整え，モデルを学習する必要があります．自然言語処理には詳しくないのですが京都大学テキストコーパスに類するものを再生産する必要がありそうです．なかなかハードルが高い．

Yelp Dataset

Yelp Captcha
Yelp はレストランや美容院など，さまざまな店舗を対象にしたレビューサイトです．
Yelp dataset では POI (Point Of Interest) へのチェックインやレビュー情報などが含まれています．
こちらも

4. Restrictions You agree that you will not, and will not encourage, assist, or enable others to:
  B. use the Data in connection with any commercial purpose;

とあり，商用目的での利用が不可能です．

そもそもデータの商用利用とはなにか

法律の専門家ではないので何が商用利用で何がそうでないのかがわかっていません．たとえば

ImageNet の画像を加工して商用サイトの素材に用いる
- これはさすがに商用利用に該当しそう
書籍に商用利用不可のデータの一部を掲載する
- 分量と内容が適切であれば著作権法第三十二条に規定された引用の権利の範疇内ではないでしょうか
書籍に商用利用不可のデータを分析した結果を掲載する
- 商用利用に該当するのか？
- MovieLens の分析をやっている本はそこそこあります
  - たとえば集合知プログラミングや仕事ではじめる機械学習など*2
書籍に CaboCha 付属のモデルファイルで係り受け解析した結果を掲載する
- これもさすがに商用利用に該当しそう
アドセンスやアフィリエイトを備えたブログにおいて商用利用不可のデータを分析した結果を掲載する
- 商用利用に該当しそうな気がしますがどうでしょう
- ちなみにこのブログのアマゾンアソシエイトは hatena-blog-22 なのでこれまで一円も儲かったことがない
企業研究者が ImageNet の画像を使って機械学習モデルを構築する
- これは研究活動として認められるのか
- しかし企業研究者は研究を行うことで企業から給与を得ているので商用利用ではないのか
- ImageNet の non-commercial research とはなにか
企業研究者が ImageNet を使って機械学習モデルを構築し，自社の商用システムにデプロイする
- これはさすがに商用利用に該当しそう
大学研究者が ImageNet を使って機械学習モデルを構築し，そのパラメータを公開している場合に，企業研究者がそのパラメータを商用システムに利用する
- reddit でも議論になっています
- Can pre-trained networks be used in commercial applications? : MachineLearning

という話がよくわかっていない．
ソフトウェアのライセンスだと研究者であろうが企業に所属している時点で「商用利用」として扱われている印象があります*3．また，フォントのライセンスであればモリサワのように商業利用の例について明記されていることが多いのでないでしょうか (参考 : 商業利用について | フォント製品 | 製品／ソリューション | 株式会社モリサワ)．

弁護士による進化する機械学習パラダイス～改正著作権法が日本のAI開発をさらに加速する～ | STORIA法律事務所や改正著作権法が日本のAI開発を加速するワケ弁護士が解説 (1/7) - ITmedia NEWS といった記事もありますが，焦点は著作権法であり，商用利用不可としたデータについての利用についての言及はありません．

また，話は少し変わりますが，以前の言語処理学会におけるデータセットと著作権のチュートリアルにて「元の内容が復元できない(たとえば形態素解析済みのもの)であれば著作物に該当しないから公開して構わない」といった話があった，と聞いた記憶があります*4．このあたりもどこかに資料がまとまっていたりしないでしょうか．

わからないことだらけなので有識者の見解が欲しいですし，なんらかの判例があるならば参考にしたいです．

「調べてみました！……いかがでしたか？結論はよくわかりませんでした！」という最悪な大量生成ブログと同じ終わり方になりました．

*1:他の企業がどのように対処しているのかわからないので非常に遠回しな言い方になってしまいました．

*2:Amazon で「集合知プログラミング」を開いたら「お客様は、2008/12/5にこの商品を注文しました。」と出て懐かしい気持ちになりました．10年以上こういうことをやっている．

*3:印象でありソースがあるわけではありません．また，現業においてそのようなソフトウェアと関わりが薄いという理由もあります．

*4:又聞きです．

2019-01-17

Predicting Audio Advertisement Quality (WSDM 2018) 読んだ

論文

[1802.03319] Predicting Audio Advertisement Quality

Spotify や Pandora などの音楽配信サービスにおいて挿入される音声のみの広告の品質を機械学習で推定する．
方針としては，音声から handcrafted な特徴量を抽出し，代理タスクを解く．
論文の著者は Pandora．

どうやって品質を定量化するか

一番いいのは被験者に聴き比べてもらうことですが現実的じゃないので代理のタスクを解く．
Web 広告の文脈では CTR (クリック率) を用いることが多いが，データを見ると音声広告経由でランディングページを開いたものの 90% が 5 秒以内に閉じている．バナーがクリックされた位置のほとんどが「閉じる」ボタンの近くであることも踏まえると，ほとんどが誤クリックであることが推測できる．
そこで，単純な CTR ではなく，ある一定の秒数以上ランディングページを開いていたクリックを表示数で割る Long Click Rate (LCR) を広告ごとに計算する．これがこの論文の新規性の一つ．

予備調査

ユーザがどのような音声広告を好ましいと思うのか調査を行う．5つのカテゴリごとに，LCR の分布の異なる分位点から広告ペアを選び，どちらが優れているか，またその理由は何かをユーザに尋ねるのを繰り返した結果， Audio Aethetic (直訳すると音楽の美しさですがこの指標の例が「BGMや話者の性別，会話，単一話者」などと書いてあってよくわからない) と Clarity of Message (内容が明確であること)，Quality of Sound (BGMと声とのバランスが取れていること)が重要であるとわかった．

なのでここからはそういう特徴量を取ることにする．

特徴量

特徴量は大きく分けて三種類．それぞれの定義は詳細が書かれていないので参照されてる論文を読む必要がある．音声処理についての知識がないのでこれらの特徴量がそれぞれを表現していることがわからないままだった．
これらをすべて合わせると 2440 次元の特徴量ができあがる．

Timbre (音色)
- TFD, MFCC, Delta-MFCC, MSP
Rhythm (リズム)
- TEMPO, TG_LIN, TGR{B, T, H}, BPDIST{B, T, H}, Mellin
Harmony (ハーモニー)
- SIHPCP, MODE, SICH/SICHC/SIKC

予測

タスクとしては広告が good か bad かの二値分類を解く．

モデル

ここからよくわからない記述が出てくる．ベースラインとしては logistic regression や random forest を用いる．
「多重共線性などがあるので PCA や Kernel PCA などの次元削減を行う」という記述があるがここが完全に意味不明．その後 PCA の文字列が出てくることもないし，その後の特徴量解釈が不可能になる．たとえば Figure 5 では L1 logistic regressio でどの特徴量が選ばれたかの議論をしているのでこれを行うためには次元削減をしてはいけない．また，そもそも当初のモチベーションは「handcrafted な特徴量を構築することで音声広告をどのように改善すればいいかを知ること」だったはずなので次元削減したらいくらモデルが interpretable でも意味がなくなる．
何のためにこの記述が存在しているのか全く理解できない．あとやたらと文字数が多い．

また，2440 次元を入力とする多層パーセプトロンだけでなく， Audio Spectrogram を入力とした CNN による推定モデルも提案している．しかし音声を入力とした識別問題に CNN を用いるモデルは Automatic tagging using deep convolutional neural networks (ISMIR 2016) で提案されており，そこまで違いがあるわけではないのでこれ自体に新規性があるとは思えない．
何のためにこの記述が存在しているのかわからない．あとやたらと文字数が多い．

目的変数である good or bad をどう決めるか

この部分がこの論文において一番問題だと考えている．
方針としては LCR を降順にソートし，ある閾値(たとえば top30 と lower 30)を設けて上位と下位をそれぞれ good と bad に割り振ることで目的変数を作る．
ではどうやって閾値を決めたかというと， chose the percentiles whith highest prediction accuracy と言っている．どういうことかというと，異なる閾値で実験を行い，どの値が「もっとも見た目の精度が高いか」で決めている．
そもそも閾値を変えながら精度を比較していることに何の意味もなく (top/lower が変わるのでサンプルサイズも変わる)，どの閾値にすることで見栄えが良くなるかの違いでしかない．これで「提案手法は AUC が 0.79 だった」と言われても「それは最も見た目の精度が良くなる閾値を選んだからだろう」と興ざめしてしまった．
極端な話，どの特徴量がどのように good/bad に寄与しているかを知りたいだけならば閾値は決め打ちし， AUC の見た目の精度に言及せずに選択された特徴量についてのみ議論をすればいいはず．
このような方法で閾値を決める論文をはじめて見たので面食らってしまった．世界は広い．

タイトルで面白いと思い読んだけれど特徴量抽出部分で置き去りにされ，Section 5 で完全に意味がわからなくなった．

2018-11-13

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 ライブラリで行う

糞糞糞ネット弁慶

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