【論文読み 001】 TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems (Abadi et al., 2015)
選出理由
kaggle にTPU 使って戦うコンペがあったり、kaggle のカーネル自体に TPU リソースがあったりするので、TPU と相性のいい TensorFlow の考え方を知りたかった。TensorFlow2.0 が出たのに読む必要ある！？と思ったけど、根底の思想に共通部分はあるはずと考え、読むことにした。
概要
Google が TensorFlow を公開するのと同時に出した論文(white paper)。
DistBelief という TensorFlow の前身をベースに、以下の改良を加えて分散機械学習にも対応した計算システムのこと。
(1) あらゆるデバイス(CPU, GPU, etc...)で使用できる(registration mechanism)。本文ではあまり触れられていないが、Heterogeneous とのことなので、デバイスの種類をまたいで学習リソースにすることもできる
(2) dataflow-like model であり、有向グラフで表される
* dataflow: データがどこから渡されて、どのような変化をしどこに行くか、みたいな雰囲気
** 有向グラフ：ノード間に前後関係があり、前のノードは後のノードより先に計算されなければならない
(3) DistBelief より柔軟なプログラミングが可能
(4) TensorFlow の抽象化は、機械学習でも有用だが、それ意外の計算アルゴリズムでも有用であると著者らは考えている
2. Programming Model and Basic Concepts
TensorFlow における重要単語の解説など
(1) Operation (Element-wise...)
- 足し算などの基本操作
(2) Kernel (CPU kernel, GPU kernel)
- デバイス依存のOperation
- ドキュメントには、マルチスレッドCPUカーネル、GPUカーネルがある
(3) Session (グラフの作成)
- 配置アルゴリズム (placement algorithm) によるノードの配置
(4) Variables (変数。グラフの実行を超えて生存するテンソル)
- 例「ネットワークの重み」
3. Implementation
TensorFlow 側からモデルのグラフをどう配置、GPU 上で実行していくかの話
client: session を master に渡す
mater: worker にサブグラフを渡す
worker: デバイスと通信し、デバイス上に配置されたノードを実行
device: CPU/GPU のこと。CPU/GPU 以外も registration mechanism を利用すれば使用可能。tf.device() オブジェクトで割当と開放を管理
local implementation / distributed implementation
- local implementation: client, master, worker が同じ
- distributed implementation: client, master, worker が別々の場合をサポーﾄ
Multi-Device Execution
複数デバイスをまたぐ計算は複雑な問題が２つ発生する。
(1) デバイス配置 (Node-Placement)
(2) デバイス間の通信管理
(1) Node Placement (ノードの配置)
ノードをどのデバイスに配置するか決定する必要がある。これは、グラフをシミュレーションして生成（Greedy Heuristic）。セッションの開始時にグラフに流し込むテンソルの型推定なども行う。
(2) 通信の処理 (Cross-Device Communication)
ノード配置完了後、グラフはデバイスごとにサブグラフに分割される。デバイス間の cross-device edge を除去、送信/受信 ノードに変換
Distributed Execution
グラフの分散実行 worker-worker は、マルチデバイスの実行 device-device に似ている。違うのは、通信プロトコル。TCP / RDMA などのリモート通信プロトコルを使用。
Fault Tolerance
分散実行のバグ検出法
(a) 通信エラー, (b) 定期チェック
通信エラーが検出されると、グラフ全体の実行が中段され、ゼロから再起動される。しかし、Variableノード は Saveノード に接続されており、周期的にバックアップを取っているので、復帰できる。
4. Extensions
「2. Programming Model and Basic Concepts」の掘り下げ
勾配計算
TensorFlow は自動微分を内蔵している。
* 自動微分に関してはまた別の機会に取り上げると思います。
メモリ使用量
自動勾配計算はメモリ使用量の最適化が複雑になりがち。
ヒューリスティックな方法で軽減。
Partial Execution
グラフ全体のサブグラフを実行したいときの機能。sess.run(..., feed_dict={...}) ← この feed を読んで TF 側が partial execution してれる。実行するサブグラフ以外の部分のグラフは実行されない。
Device Constraints
あるノードをどのデバイス上に配置するかを指定できる。デバイスの制約を満たすように、デバイス配置アルゴリズムを変更する。union-find 木を利用。
Control Flow
制御フロー(Control Flow) を導入することで、条件式やループをグラフに実装。* ここらへんも根が深そうなのでいずれ取り上げると思います。
- Arvind
- MIT Tagged-Token machine
あたりをベースに作られているらしい。
Input Operations
TF: feedノード からデータ供給可能
TF以外: 特殊なノードが必要であり、データをファイルから読み込み、そのデータを使用するノードに流し込む必要があり、データ通信に無駄が発生する。（多分 ↓ にまとめた Torch の Dataset クラスのようなもののことを言っているんだと思う。）
Queues
TensorFlow で追加された機能。
データ読み込みの並列化、勾配計算時のバッチ数を増やしたり、RNN などの入力文のデータをグループ化したりするのに使える。
Containers
tf.Graph().container("{container name}")→ 公式Doc: https://www.tensorflow.org/api_docs/python/tf/Graph#container
コンテナ名を指定して、コンテナ内の Variable などにアクセス可能。
リソースの管理ができる。指定しないとデフォルトリソースコンテナに入るらしい（＝無名のコンテナ）
5. Optimizations (Optimizer ではない)
Common Subexpression Elimination
→ 共通部分式除去
共通の計算になる部分を Click[12] の方法で除去する。
https://qiita.com/nuka137/items/1936ad509cd4e68d2fad がわかりやすい。
Controlling Data Communication and Memory Usage
Operation のスケジューリングを行い、データ転送効率化とメモリ消費量を削減できる。(1) 計算の中間結果をメモリに乗せる必要があるが、載せている時間を削減して最大消費メモリを抑える。(2) デバイス間のデータ通信を強調させることでネットワークリソースの競合を減らす。
Asynchronous Kernels
通常のカーネルは同期カーネルだが、非同期カーネルもサポートしている。スレッド数が少ない環境において有効。（Kernel なので CPU/GPU 内での非同期化）
Optimized Libraries for Kernel Implementations
Kernel を実装するため、既存の最適化されたライブラリを使用。
BLAS, cuBLAS, cuda-convnet, cuDNN, Eigen など。
Lossy Compression (非可逆圧縮)
機械学習アルゴリズムは、ノイズや低精度の演算に強い。よって、デバイス間の通信のボトルネック解消のため、32bit の情報を 16bit に落としたあと、受信した別デバイスで 32bit に復元(16bit + 0埋め) することがある。
6. Status and Experience
デバッグが大変だったので、どう解決したかという知見。ここでは Inceptionモデル を TensorFlow に移植し、DistBelief と比較し6倍の実行速度と高いシステムの信頼性を獲得した。
(1) パラメータ数の把握をし、自動型変換のバグ特定
(2) 学習の過程を小さいモデルで確認し、スケールアップしていく
(3) 学習を行ってない段階でバグが発生していないか確認
(4) 単一マシンでの実装 → 分散実装 のような実装順でデバッグ
(5) NaN を検出し除去
(6) ２台以上のマシンで実行し、数値誤差の確認
7. Common Programming Idioms
SGD で並列計算する方法について書かれている。
(1) データパラレル：1,000データ のミニバッチの勾配計算をしたい場合、100データx10レプリカで実行する
(2) モデルパラレル：LSTM の一段目、二段目、三段目をそれぞれ
デバイス 1, 2, 3 で区切る
(3) Pipelining: 一つのデバイス内での並列化。並列性をより高めるために使用
所感
- グラフ配置アルゴリズム Greedy Heuristic がどんな実装か気になる
- 自動微分のメモリ効率アップもヒューリスティックなので気になる
- 9.2 の「EEG」って見たことないんだけど公開されたんだろうか
ーーー
[7] Theano: A CPU and GPU Math Compiler in Python., (Bergstra et al., 2010) [PDF]
■ どんなもの？
- 数式表現のための Pythonコンパイラ
- Numpy のような記法で書ける
- ネイティブコード並の速度が出せる
- 静的に型付けされ、関数型プログラミング的
- 自動微分内蔵。数式を記号的表現で扱える。
■ 先行研究と比べてどこがすごい？
- 高速化: CPU で 1.6~7.5倍、GPUで 6.5~44倍
- CPU では int と float の N次元配列 をサポート
- GPU は float32 のみ対応(？) → Limitationsの項
■ 技術や手法のキモはどこ？
- Python を機械語に変換し効率的な CPU/GPU 計算を行う
- 一時変数の使用を抑え、高メモリ効率
- BLASサブルーチン "gemm"(General Matrix Multiply) / "gemv"(Generalized Matrix-Vector Multiplication) を活用することで高速な Cコード が生成可能
- コンパイル最適化: Canonicalization(TFでも使われてる), Stabilization, Specialization(gemm/gemv), GPU転送変換(GPUで使えるようにした数式), GPU allocation, GPUテンソル, コード生成
■ どうやって有効だと検証した？
- ベンチマークテスト。MLP と CNN をそれぞれ CPU と GPU で、
- CPU: Theano は Numpy より 1.8倍 速い。MATLAB より 1.6倍、Torch より 7.5倍 速い（元より Torch はスピード重視ではないが）
- GPU: Theano は EBLearn より 2.2倍高速、GPU では10.7倍 高速
■ 議論はある？
- 実行速度最適化を重視しているが、コンパイルの過程を最適化してないため、グラフのサイズに応じて線形以上のコンパイル時間がかかる
- Numpy の全機能をカバーしているわけではなく、実際は Scipy の一部の機能をカバーしているだけ
- 複素数のサポートが不十分
- GPU で使えるデータ型が float32 のみ
- sparse vector/expression は利用できない
■ 次に読むべき論文は？
- "Algorithm 679: A set of Level 3 Basic Linear Algebra Subprograms." (BLAS)
[13] Torch: A modular machine learning software library., (Collobert et al., 2002) [PDF]
■ どんなもの？
- C++ 実装の機械学習フレームワーク
- 自動微分は内蔵してない（後に Torch-autograd が公開される）
■ 先行研究と比べてどこがすごい？
- 機械学習アルゴリズムは実装や同じ条件での検証が難しいので BSD フリーライセンスで出して誰でも使えるようにした
- 様々な機械学習アルゴリズム(HMM, SVM, GMM, NNなど)をまとめて使えるようにした
- (今では当たり前だが) 数行で CNN が書ける
■ 技術や手法のキモはどこ？
- modular strategy (DataSet, Machine, Trainer, Measuer) というクラスデザイン
→ モジューラプログラミング: 機能独立, 交換可能
■ どうやって有効だと検証した？
- 当時あった HTK, SVMLight, SVMTorch などは特定の機械学習アルゴリズムしか実装してない
- 正確性、学習速度、メモリ効率
- HTK と Torch の音声認識(Numbers95タスク)では同程度の性能。
- HTK と Torch の SVM 訓練時間は同程度
■ 議論はある？
- 特になし
■ 次に読むべき論文は？
- "Chainer: a Next-Generation Open Source Framework for Deep Learning"
- "PyTorch: An Imperative Style, High-Performance Deep Learning Library"
[14] Large Scale Distributed Deep Networks., (Dean et al., 2012) [PDF]
■ どんなもの？
- 分散機械学習フレームワーク DistBelief。TensorFlow の前身
- DeepLearning の規模を大きくするほど性能が上がることに気づいていたので、デバイス(CPU/GPU)の限界以上の計算力を求めていた
- 分散学習法 Downpour SGD と Sandblaster L-BFGS を開発
- モデルを最大 144分割 し、並列学習させ大幅に高速化可能
■ 先行研究と比べてどこがすごい？
- 数千台のコンピューティングクラスタで学習可（この時代の文献値の30倍規模）
- ImageNet で当時の SoTA
- 中程度のサイズのモデルの学習の高速化 & 大規模モデルを学習可能に
- MapReduce / GraphLab は分散計算技術として存在するが、DNN 系グラフだと計算効率が悪く、DNN に特化した分散計算が必要だった
（MapReduce: 2004年に Google が作った分散コンピューティングプログラムングモデル。GraphLab: C++ で記述されたグラフベースの分散計算フレームワーク）
■ 技術や手法のキモはどこ？
(i) Downpour SGD
- Howglid アルゴリズムの後進
- 非同期型SGD。これによって分散バッチ最適化が可能
- データ並列化し、replica(=複製したモデル) で学習可能
- 学習データをサブセットに分割して、サブセットそれぞれで replica を実行し、パラメータ更新する
- n_fetch: パラメータを更新する回数 / n_push: 勾配を送信する回数
(同期型 SGD だと、n_fetch = n_push = 1)
replica 同士の勾配通信をn_pushごとにすることで通信オーバーヘッド削減
- 同期型 SGD より 非同期の方が故障に強い（1つのマシンに障害が発生しても他の replica が動作するため）
- 確率的要素が増す、学習による勾配計算と更新が微妙にズレる減少が起きるなどの不確定要素が増すが、特に問題ない（根拠はない）
- Optimizer に Adagrad を使うことでロバストになる
(ii) Sandblaster L-BFGS (Broyden-Fletcher-Goldfard-Shanno)
Sandblaster: GoogleBrain 製の分散学習フレームワーク(?, 情報がない)
- L-BFGS: 準ニュートン法
- Sandblaster: (Sandblaster→データを撒き散らすイメージ？)
マシン同士をまたぐノード間では通信が行われ、 Coordinatorプロセス によって保存や操作を分散制御させる (Coordinator は TensorFlow でいうところの Session か？)
- Coordinator がパラメータサーバに対して演算コマンドを発行する。演算の履歴はパラメータサーバに残る。これによって中央サーバに毎回パラメータを送信する必要がなくなり、通信コスト削減ができる
■ どうやって有効だと検証した？
音声認識と画像認識(ImageNet) の性能で評価
音声認識(5層MLP):
- 8台 並列し、2.2倍の速度に。
- 8台 を超えると通信オーバーヘッドが並列の恩恵を超え計算速度低下
画像認識(CNN)
- CNN ではモデル replica をさらにマシンで分割して並列化し、高速化可能
- 最大 71億 パラメータ、81台 並列で 12倍 以上の高速化を実現
- マシンを増やせば増やすほど速度は上がり続けるが、効果は薄くなる
並列化ベンチマーク
(1) 学習時間-精度を並列化しない場合/した場合で比較
SGD < Downpour SGD < Sandblaster L-BFGS < Downpour + Adagrad
という結果
(2) ある精度(ここでは16%)に達成するまでにかかった時間-コア数 の曲線を比較すると、DownpourSGD+Adagrad が一番よい。Sandblater L-BFGS は、30,000コア 以上の並列を実行すると最速を達成する（可能性がある曲線が示唆）
■ 議論はある？
- Adagrad は Downpour SGD のために考えられたものではなく、たまたまうまくいったもの。（じゃあ後発の Adam系 とかは効くのか？）
■ 次に読むべき論文は？
- "A scalable modular convex solver for regularized risk minimization." (分散勾配の計算)
- "Learning multiple layers of features from tiny images."
- "Hogwild! A lock-free approach to parallelizing stochastic gradient descent. "(Hogwild)
- "Adaptive subgradient methods for online learning and stochastic optimization."(Adagrad)
---
この記事は CC-56 の一環です。