Treasure Data Summer Internship 2017 #td_intern

Kento Nozawa
30 September 2017

はじめに

2017年の8月から2ヶ月間 Treasure Data Inc.の高待遇で有名なサマーインターンシップに参加しました (日給2万)．例年はインターン生は3名なのですが，今回は私1人でした．

最終発表のスライド:

実は2年前にも応募していました．

Treasure Data - ソフトウェアエンジニア (Intern) やばい https://t.co/HHjIjyw3fh
— nzw (@nzw0301) May 16, 2015

このあとCTOからリプライがきたので応募しました．

当時は，Treasure Data Summer Intern 2015, myui’s memoにある課題を考えもせず，いきなりコーディングをしてテンパりました．後から成果発表が英語だったと聞いて，行けなくて当然だという気持ちになりましたが，2年もするとなんとかなるようです．

準備

去年までのブログを読みました:

レジュメ

前はJIS規格の履歴書を出したのですが，

当時よりも倍率が高そう（これはそうでもなかったらしい）
成果発表は英語

ということで，D進する予定もあり，英語で書きました．こんな感じです．上の方に数行でどんなことをしたいか (LDAの高速なアルゴリズムをhivemallで実装したい的なこと) を書きました．

面接

今回のコーディング課題が個人的に馴染みがあったので，運もよかったと思います．正しい出力はできましたが，ロジックが美しくなかったので受かったらいいなという印象でしたが，無事通過の連絡をいただきました．

インターン前

メンターのmyuiさんから実装予定のアルゴリズムとJavaの勉強をしておくとスムーズになる旨を伺ったので，パーフェクト Java読んでskip-gram with negative samplingを実装しました．

やったこと

myuiさんとtakutiさんの元でHivemallの機械学習アルゴリズムを実装しました．HivemallはHiveで使える関数の集合（特に機械学習のアルゴリズム）を提供しています．HiveというのはHadoopに格納されているデータをHiveQLというSQLライクな問い合わせ言語を使って操作するものです．

今回は，過去ブログにあるような中間報告などは特になく，適宜メンターと相談して進めていました．最終発表は，↑のスライドを使って英語で発表しました．過去の自分も英語と聞いて後ずさりしてしましたが，とりあえずそれらしい風に話せればなんとかなりました．たぶん．ありがとうDMM英会話．

ちなみになんで英語かというと英語圏のエンジニアがいることが理由なので，場合によっては日本語かもしれません．

FMeasure

HiveのUDFやHivemallのお作法に慣れることを含めて，最初にf1-scoreのを一般化したfmeasureのUDAFを実装しました (PR)．

これが2週間くらいです．

SLIM

確実に成果が見込めるタスクとしてSLIMという行列分解系の推薦アルゴリズムを実装しました．詳しい解説はこちら．これが一番大変でした．

理由としては

行列分解系の実装経験がなかった
反復計算処理
参考にしていた評価方法が謎

です．

予定だと2週間だったのですが，1か月かかりました．

word2vec: Skip-Gram & CBoW with negative sampling

これが挑戦的な課題でした．予定が1か月でしたが，SLIMが長引いたので2週間くらい．とりあえず形にはなったのでよかったです (PR)．

word2vecの分散学習や高速化は，いくつか実装や論文があります．オリジナル実装は，シングルノードのスレッド並列でhogwild!を使っています．Hivemallはマルチノードで動くので，word2vecをマルチノードで学習するのが最終的な課題です．

Spark mllibやdeeplearning4jではグローバルに単語ベクトルを持っており，定期的に分散したノードのもつベクトルと同期させます．これだとノードごとにデータとベクトルをもつ必要があるので，スケールしません．
Network-Efficient Distributed Word2vec Training System for Large Vocabulariesでは，N分割した単語ベクトルをノードが担当することで同期をなくしています．例えば200次元のベクトルを10ノードで扱う場合，最初のノードが0–19, 次のノード20–39という感じです．これだと最大で次元数まで分散可能です．word2vecではnegative samplingは乱数依存なので，異なるノードで同じ負例をサンプルするために，乱数のシード値をノードに送ることで異なるノードでも同じ乱数が使えます．賢い．．．
Parallelizing Word2Vec in Shared and Distributed Memoryでは行列演算にすることで高速化を図っています．オリジナルの実装では，for文使ってベクトルの内積計算をしていますが，blasが使えるなら行列演算のほうが高速です．このため，同じ文脈語（正例）をもつ単語（skip-gramの入力）に対しては同じ負例を使うことで行列積にします．分散学習はspark mllibと似たようなやり方です．
Distributed Negative Sampling for Word Embeddingsが知ってる範囲では最速のアルゴリズムです．この手法では，1単語に対する正例ごとに分散処理します．問題はどのノードに分配するかです．話が前後しますが，オリジナル実装では，語彙数よりもかなり長い配列を用意し，配列の要素の割合がnegative samplingをとってくるnoise distributionと同じ割合になるように要素に負例を格納します．この手法では，まずこの長い配列は使わずにalias methodのテーブルを作ります．このテーブルを分割し，担当するノードに分配しておきます． 1単語に対する正例を1つ決めたら，ノードがもつalias tableの割合と乱数をもとに担当するノードを選択し，単語対をノードに送ります．ノードの内部がもつalias methodのテーブルの一部を使ってnegative samplingします．最後にパラメータサーバに勾配を送ってベクトルの更新をします．

LDAでalias methodを使ってcollapsed Gibbs samplingを高速にする手法を知っていたので，word2vecでも使えそうだと思っていたのですが，最後の手法についてを読んでみるとword2vecにすぐに応用できるということがわかりました（categorical分布からのサンプルになるので当然でした）．

本題です．今回のインターンでは，データ並列でパラメータを共有せずにやってみました．結果からいうとデータ数に対して並列数が上がるとベクトル間のcosine similarityが高くなり，word similarityやanalogyの性能が悪くなります．このあたりはhivemallのパラメータサーバあたりを使って解決を試みることが今後の課題です．

さて工夫したところですが，並列化のために，単語を予め整数値に変換します．この変換された整数値を単語ベクトルの重みの初期化に使う乱数生成器のシードに使うことで異なるノードにおいても全く同じ初期化がされます．これは[Network-Efficient Distributed Word2vec Training System for Large Vocabularies]から着想を得ました．これで精度の劣化 (順位相関係数) を多少防ぐことができました．変換せずに学習できますが，シードが異なると，劣化が激しくなります．

またオリジナルのようにnegative samplingのために語彙数よりも長い配列を使うのは， hivemallの1ノードあたりのメモリを圧迫するので[Distributed Negative Sampling for Word Embeddings]と同じようにalias methodを使いました．Alias methodのためのテーブルを作る関数はUDTFとして作ったので，別用途でも使えます．

これ以外にオリジナル実装と違う点は，

sub-samplingは予め行っておく (本来は学習中に行う)
反復計算は，文書ごとに行う（本来は文書全体）．これをしても性能が落ちなかったので意外でした．オリジナルどおりにやろうとすると予め冗長なテーブルを作るか，一時ファイルにデータを書き出すため，時間がかかります．

全然関係ないですが．参考にしていたspark mllibで複数イテレーションにするとiterationごとに学習率がリセットされます．せっかくなのでPR投げました．

Future work

心残りなことは，以下の通りです．

データ並列で学習したベクトルの品質向上
- e.g. parameter serverを使う
- Learing rateはadagradとかadadeltaのような学習率の更新にデータ数が寄与しない最適化を利用
今回実装した学習アルゴリズムの比較
- 利用するときの指針としてHivemallのアルゴリズム同士や他の実装との比較はとても重要