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

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

• 東北大乾研による日本語 Wikipedia エンティティベクトル
• BIZREACH によるHR領域向け単語ベクトル｜株式会社ビズリーチ
• 朝日新聞による朝日新聞単語ベクトル
• BERT with SentencePiece を日本語 Wikipedia で学習してモデルを公開しました – 原理的には可能 – データ分析界隈の人のブログ、もとい雑記帳
• Out-of-the-box - 日本語Wikipediaで学習したdoc2vevモデル

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

ダウンロードリンク

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 に所属している同じタイトルが異なるノードとして扱っているためです．

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:又聞きです．

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 で完全に意味がわからなくなった．

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

IRGAN (SIGIR 2017)→GraphGAN (AAAI 2018)→CFGAN (CIKM 2018) を読んで GAN による購買予測/協調フィルタリングを学ぶ

CFGAN (CIKM 2018) を読もうと思ったら「そもそも発想としては IRGAN (SIGIR 2017) と GraphGAN (AAAI 2018) が先にあって……」と触れられていたので順に読むことにする．
そもそもタイムラインで「CFGAN がはじめて商品推薦に GAN を使っていてすごい」という風潮で取り上げられていて，「2018年まで誰も思いついていないとかまさかそんな馬鹿な話があるわけないだろう」と思ったのがきっかけ．

結論から言うと

• 商品推薦に GAN を用いるのは CFGAN が初出ではなく IRGAN が初出であり， GraphGAN でも実現している
• CFGAN は IRGAN/GraphGAN における「真のデータを Generator がサンプリングしてしまうことで Discriminator が混乱して精度悪化を引き起こす」という問題に対して「離散的に点をサンプリングせずに連続なベクトルのサンプリングを行う」という方式を採用することで精度を改善した

この 2 点．

IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models (SIGIR 2017)

[1705.10513] IRGAN: A Minimax Game for Unifying Generative and Discriminative Information Retrieval Models
SIGIR18 IRGAN Tutorial

概要

GAN で IR (Information Retrieval) を行う．IR は query に対して関連がある document を得るタスク．
読むまで「どのように Generator で document を生成するのだろうか」と思っていたらそういうわけではない．

• Generator : query から document が生成される確率
  • 真の確率 は学習データで与えられているとする (というより関連のある pair が与えられている)
  • を模倣する を学習したい
• Discriminator : query に document が関連がある場合に 1 を返すような識別的な関数 を学習したい
  • 

の 2 つを用意して

を学習する．
の気持ちは

• Discriminator は真に関連がある pair に高いスコアを振り， Generator が提示してくる pair に対して低いスコアを振るように頑張る
• Generator は に対してなるべく関連がありそうな をサンプリングできるように頑張る
  • もう少し丁寧に書くと という感じで を学習する必要がある
• Discriminator および Generator は pair に対するなんらかの特徴ベクトルを受け取るニューラルネットワークで構築する
  • あとで実験を行いますが特に Generator を linear なモデルにすると予測精度が低いままになってしまう．馬鹿な Generator では Discriminator の役に立たない．

という状態．

学習においては Discriminator は普通に勾配を求める． Generator はサンプリングが関係するので policy gradient based reinforcement learning を使う．

自分の解釈

ナイーブに考えると関連がある pair を正例，関連が無い pair を負例として識別的に Discriminator のみを学習すればいいわけですが， query と document それぞれが非常に大量にあり，かつ，関連がある pair が非常に少ない時，まさか全組み合わせを使って負例を作るわけにはいかないし，そもそも「関連がある」わけではないペアがすべて「関連がない」わけではなく， unobserved だけれども 関連する pair も存在している．なので unlabeled なデータを使って Generator で効率的に識別面に近い負例を生成し， Discriminator の学習を補助している，という解釈でいる．

とはいえ Discriminator を Pre-train するという記述があってどうやって負例を作ったのかがわかっていない．実験の項を見ると関連度順に 0, 1, 2 とつけられたラベルと -1 の「関連度無し」というラベルについて 1 と 2 を関連するラベルとして，それ以外を unlabeled として扱っている．そもそもIRにおいて positive だけがある状態で学習する話がわかってない．情報系の素養が何もない．

実験

実験結果を見ると既存の手法を上回る精度を出している．
また，この枠組みは商品推薦にも使うことができる． IR タスクでは特徴ベクトルが与えられる状態でしたが query/document を user/item と読み替えて特徴ベクトルの代わりにそれぞれの latent vector (論文中では user/item matrix に対する matrix factorization) の内積を用いることで同じように実験ができる． Movielens と Netflix で実験して BPR (pairwise な loss を考えるやつ) を上回る精度を出している．よって少なくとも IRGAN によって GAN を用いた商品推薦が実現していることがわかる．

GraphGAN: Graph Representation Learning with Generative Adversarial Nets (AAAI 2018)

[1711.08267] GraphGAN: Graph Representation Learning with Generative Adversarial Nets
今度はグラフに対して GAN を行う．何を生成するかというと

• Generator : vertex ( vertex ) から vertex に対して edge (枝) が存在する確率を返す関数
  • 真の確率 は入力におけるグラフにて vertex ペア 間に edge が存在しているかで表現されている
  • を模倣する を学習したい
• Discriminator : は vertex ペア 間に edge が存在しているかを識別する関数であり，vertex 間に枝があるかを学習させる

といったように

• Generator は edge がありそうな vertex pair を返す
• Discriminator は真に edge が存在する vertex pair かどうかを返す

を繰り返す(馬鹿みたいに考えるとグラフを丸暗記すればいいわけですが後述するように vertex の embedding/latent vector の内積で表現するのでそういうわけにはいかない)．
vertex を query と document として考え， edge を relevant として考えると IRGAN と同じ枠組みであることがわかる．

IRGAN の時と同様に

• Discriminator として を vertex ごとの k 次元の潜在表現pとして学習
• Generator として を vertex ごとの k 次元の潜在表現として学習
  • この時，ナイーブに softmax を取るとグラフ構造を活かすことができないのでグラフ構造を反映して から Breadth First Search で tree を作ってそこにおける path を使って確率を構成する graph softmax を導入する (eq 7が追えてないので詳細は後日ちゃんと読む)
  • さらに からのサンプリングを効率的にするために online sampling strategy を導入する

とする．

実験

実験は link predicton， Node Classification，それと Recommendation をやる．当然 vertex を user と item とみなせば link prediction は recommendation として考えられるため行うことができる．

IRGAN / GraphGAN における素朴な疑問

ここまで IRGAN と GraphGAN を読んできて一点分からないことがある．
Generator は「真にありそうなもの」を提示し， Discriminator はそれを reject しなければならない．もし Generator が「学習データにおいて relevant がある / edge がある」ものを引き当てた場合， Discriminator はそれに対して低いスコアをつけなければならない．
論文中でも「 Generator が真に学習できていたらそれは と区別がつかない」と書かれていてそれが理想なのだろうけど，しかし矛盾する事例を引き当てた場合は無視するのだろうか，もしくはそもそも引き当てることが少ないという前提なのだろうか，いう点が引っかかっていた．

CFGAN: A Generic Collaborative Filtering Framework based on Generative Adversarial Networks (CIKM 2018)

CFGAN: A Generic Collaborative Filtering Framework based on Generative Adversarial Networks

モチベーション

IRGAN と GraphGAN によって GAN による推薦が可能になったとはいえ，これらの手法は「要素を 1 つ離散的にサンプリングしてそれの真偽を問う」という手続きを取っているために問題がある．
なぜなら，真の要素を Generator がサンプリングしてしまった時， Discriminator は矛盾するラベル(同じ要素が true でもあり false でもある)を受け取って学習するために混乱してしまうからだ(思い浮かんだ疑問点で回収されて少しうれしい)．
実際にこれがどの程度起こっているか実験で確かめる．両モデルで推薦タスクを解いてみると epoch を増やすにつれ Generator と Discriminator の精度は上がるが，ある一定の epoch を超えると突如として Discriminator の精度が異常に悪化し始めることがわかる．同時に， Generator が真のデータをサンプリングしてしまう確率が非常に高くなっていることがわかる．これはすなわち

• 学習が進むことで Generator が賢くなって真の分布に近づく
• それによって矛盾したデータを Discriminator が受け取る
• Discriminator が混乱して精度が下がる
• Generator に Discriminator からの信号が伝播しなくなり学習が止まる

という状態に陥っていることがわかる．

CFGAN

著者ら曰く， IRGAN/GraphGAN の問題点は Generator が離散的にサンプリングを行うことであるらしい．
そこで CFGAN では

• Generator はユーザ ごとに
  • の状態ベクトル とランダムノイズ を入力として，商品数 の次元を持つ購買ベクトル を生成する
  • その後 が購買していた商品 の要素 となるマスクベクトル と要素積を取る
    • これは既存の購買予測における「購買していた(学習対象の)要素に絞る」という観点と一致する
• Discriminator は購買ベクトルが真であるか偽であるかを推定する
  • この時，入力には真の購買ベクトル(購買履歴) または Generator が生成した購買ベクトルをマスクしたもの とユーザの状態ベクトル とを連結したものを与える
  • Generator / Discriminator ともに適当なニューラルネットワークで学習する

として Generator を連続的にサンプリングする．
しかし， でマスクを取るならば全てについて となるような購買ベクトルを学習するのがもっとも単純な解であるが，それでは商品間の好みの関係が全く学習されない．
そこで，一部の購買していない商品をサンプリングし，それぞれ について

• zero-reconstruction regularization : として を 0 に近づける項を目的関数に追加して学習させる
• partial-masking : でマスクする時に として購買していない商品についても Discriminator に値を渡すことで学習させる

のという両方の工夫を行う．

実験

実験でSOTAという触れ込みで流れてきたけどこういう比較で SOTA を名乗っていいのかと思うような実験だった．そもそも movielens での現状の SOTA を並べて比較しているサイトがなかったり，皆がそれぞれの基準でデータのフィルタリングを行っているのでまともに比較ができないと思うのですが，140文字未満の論文ツイートだけ読んで論文を理解する人々に言ったところでどうしようもない話だった．
当初の疑問だった「矛盾したラベルはどうなのか」とう話は， CFGAN でも発生はしているがそれでも Discriminator はしっかり見分けていて学習がしっかり見分けている．これはベクトルをサンプリングしているからである(と著者は主張している)．多分ですが目的関数を計算する時に矛盾する一点のみではなく矛盾するベクトルかどうかで取り扱っているので後者の方が緩いから，とかそういうことだと思う．

Graph Convolutional Neural Networks for Web-Scale Recommender Systems (KDD 2018) 読んだ

KDD 2018 | Graph Convolutional Neural Networks for Web-Scale Recommender Systems
著者に Jure Keskovec がいる．
Pinterest における推薦にて node の embedding を graph convolution で学習する推薦手法 PinSage を提案している．タイトルだけ読むとそのように思えるけれど，実際には Graph Convolutional Network で行われるような Graph Fourier変換にもとづく畳み込みを行っていない．この点を誤解しているまたはまともに読んでない人しかいないのではないかと思う (footnote 1 で however, the architecture we employ does not directly approximate a spectral graph convolution と言及もしている)．

PinSage における Graph Convolution

Convolution

今，次のような関数を考える (論文中ではこの操作を Convolution と呼んでいる)．論文中の Algorithm 1 の説明では と が未定義の状態で登場していて完全に意味不明なので論文の主張に沿って正しいと思われるコードを書く．

# node u に対する畳込みを得る関数
# z_u  : u の現在の畳み込み表現
# z_neighbors : u の近傍ノードの畳み込み表現の集合
# alpha : 近傍ノードの重み
# Q, q : importance_pooling に渡す前のパラメタ
# W, w : 最後の ReLU に渡す前のパラメタ
def covolve(u, z_u, z_neighbors, alpha):
    n_u = importance_pooling(ReLU(Q * z_neighbors + q), alpha)
    z_u_new = ReLU(W * concat(z_u, n_u) + w)
    return normalize(z_u_new)

# vectors を element-wise に weights で重み付けして平均を取る pooling 関数
def importance_pooling(vectors, weights):
    i, j = vectors.shape
    ret = [ ]
    for dim in j:
        ret[dim] = np.mean(vectors[dim, pos] * weights[pos] for pos in range(i))

    return ret

何をやっているかというと，ある node に対する embedding をその近傍にある node の embedding をまとめて pooling し，現在の embedding と concat した上で ReLU に通している．これを深さ まで繰り返し適用する (論文中では 回目の繰り返しにて得られる embedding を と表現している)．思ったよりシンプル．

ここだけ読むとシンプルな話でいいわけですが，論文冒頭では「 node には visual や texual な feature が付与されている」「この手法ではそれら feature を使って embedding を学習する」と書いてある．しかし上記のコードにはそれら feature に対する言及がない．"We start with input node features and then learn neural networks that transform and aggregate features over the graph to compute the node embeddings" と書いてはあるがその後の記述を読むと embedding のことを feature と呼んでいて正直に言って全く理解できない．
id:another16javac さんから「GraphSAGE [1706.02216] Inductive Representation Learning on Large Graphs が参考になる」というコメントをいただき読んだところ を特徴量 で初期化しているのでここで使うという話だった．そしてこの論文もよく読むと algorithm 2 で同様に を で初期化していた．恥ずかしい．

細かいテクニック

• Pixie で行ったように から始まるランダムウォークによる訪問回数が上位の node を近傍として用いる．また，この時の訪問回数を重み として用いる． Pixie ではこの時のランダムウォークに用いる遷移行列を node の特徴量を謎の関数に通して重み付けしていたが，まさかこれが上記の疑問に相当する?
• 学習はクエリ と正例 のペア が与えられていると考え，負例のペアより正例のペアの embedding の内積が大きくなるように学習する．
• またこの時，負例は negative sampling するわけですが uniform にやるとほとんど関係ない負例ばかり出てきて関数が収束しない．そこで に似ているが正例ではない負例 を hard negative item として選ぶ．また，学習の際には epoch ごとに hard negative item を段階的に増やす curriculum training を行う．
• 学習は MapReduce． d2.8xlarge のインスタンスを 378 台並べてクラスタを作る．

Graph の convolve は分かるけどどうやって特徴量を有効活用したのかわからない．

Sequences of Sets (KDD 2018) 読んだ

KDD 2018 | Sequences of Sets
好きな研究者が何人かいて，タイトルで気になった論文の著者がその人だとちょっとうれしくなる．Cornell University の Jon M. Kleinberg や Google の Ravi Kumar ， Stanford の Jure Leskovec は気になって定期的に著者のページを見に行っている．Facebook の Lars Backstrom は久しく論文を書かなくなってしまったので悲しい．
今回の論文は Ravi Kumar が Co-Author に入っている．

集合 (set) の系列 (sequence) についてモデリングする．論文中では

• ある人物が送信したメールそれぞれの宛先を時系列でソートしたもの
• Stack exchange において投稿された質問に付与されたタグをユーザごとに集めてソートしたもの
• センサーから得られた人の接触データ
• 共著関係

を対象に分析・観察を行い，集合の系列の推定モデル Correlated Repeated Unions (CRU) model を提案している．

データの観察

• 集合は繰り返す．多くの集合は系列において繰り返し現れるし，全く同じものだけでなく上位集合 (superset) や部分集合 (subset) も現れる
  • 系列を前から見ていった時にある集合 (と完全に同じもの | と全く要素がかぶらない集合 | の部分集合 | 上位集合) ががそれより前に現れた比率を見ると集合が繰り返して現れていることがわかる
• 集合の要素は相関する．二つ組，三つ組の組み合わせは相関を持って現れる
  • 全集合から全ての二つ組，三つ組を数え上げるとそれらがランダムに出現する個数より多い
• 古いものより新しいものに類似した集合が出現する
  • ある集合と，それより k 個前に現れた集合との Jaccard 係数の平均を見ると， k を大きくするほど低下する．つまり近ければ近いほど集合間の類似性は高い

CRU モデル

これらを踏まえて集合系列のモデルを提案する．
しかしここまで読むとこのモデル，系列 が観測されている状態で までを用いて がどのように生成されるかをモデル化している (機械学習的な外挿を行うモデルではなく，物理のように現象を理解するためのモデルのようなニュアンス)．本来想定していたのは までが与えられた状態で を推定するモデルだったのでちょっと肩透かし．
パラメータとして長さ であるいくつ前の集合を重視してサンプリングするかの と集合内からサンプリングを行うための を持つ．また， の要素数も (なぜか) わかっているとする．こういう仮定のおかげで将来予測ができない．
CRU モデルの論文の説明を Python のコードで書いた．大雑把な言い方としては

• 過去の系列をさかのぼってどの集合から要素をサンプリングするかを選ぶ
• 選んだ集合から要素をサンプリングする
• これが一定の大きさになるまで繰り返す

という動きをする．

# S_i の重み付き抽出に必要
from numpy.random import choice

# 長さ k の 集合の系列 S を受け取って次の繰り返し集合 R を出力するモデル
def CRU(r, w, p, S):
    R = set()
    k = len(S)
    while True:
        if len(R) == r:
            return R

        # S_i を重み w_{k + 1 - i} で抽出
        # w は重みなのでサンプリング用の確率に変換する
        p_s = [w[k + 1 - i] for i in range(k + 1)]
        p_s = [x / sum(p_s) for x in p_s]
        S_i = choice(S, p=p_s)

        # S_i から各要素を確率 p でサンプリング
        T = set()
        for s in S_i:
            if random.random() <= p:
                T.add(s)

        # この時の n は系列の「全長」 (未来の分まで含める)
        if len(R | T) > n:
            while len(R) < n:
                # T から一様に要素をサンプリング
                y = choice(T)
                R.add(y)
                T.remove(y)
        else:
            R = R | T

パラメータ推定

推定したいのはいくつ前の集合を重要視してサンプリングするかのパラメータ (論文冒頭にて要素内からのサンプリングパラメータ はグリッドサーチしたと言及がある)．尤度の式を作ることができればパラメータの推定はできるはず．しかし集合が生成される尤度とはどういう形でしょうか．僕はすぐには思い浮かばない．
3.2 を真面目に読んでいないけれど，方針としては出力される の部分集合すべてについてそれが生成される確率を求めてやればいい，という理解でいる．これ以上はこの論文を再実装したくなった時に読み返す．