分散型オンライン学習

研究 機械学習

ICML2011のOptimal Distributed Online Predictionをざっくりと読んだので，メモ書き．
論文

概要

  • 既存のオンライン学習アルゴリズムをミニバッチに拡張，分散学習を可能にする
    • 勾配ベースのオンライン学習手法は全て拡張可能
    • 勾配ベースのオンライン学習手法 : Dual-Averaging, Mirror descent algorithms (Subgradient method)等
    • Regret Boundは\sqrt{m} (m:データ数)で分散数kに依存せず，凸制約の上では理論上最適解
  • 確率的最適化の文脈から，分散型のアルゴリズムを提案しているとも見ることが可能
  • 実験により，ノードの数の増加に応じて収束速度が向上することが示された

distributed mini-batch framework(DMB)とは？

  • k個の学習器にそれぞれ別のデータを食わせて勾配を計算させる
  • 勾配情報がある程度溜まったら，勾配の平均を取り新しい学習器を生成する
DMBを用いる利点
  • シングルプロセッサでは到底処理不可能な量のストリームデータを扱うことが可能
  • 確率的勾配法ベースのDMBならば，並列性にほぼ線形での速度向上が可能

Regret Bound

E[R(m)] = \sqrt{m}(m:データ数)
証明は，ロングペーパーの方を参照

制約
  • "ある程度"の数bは，データ数mに依存する(但し，bはmより十分に小さければ問題ない)
  • 学習結果のやり取りや勾配平均の計算には遅延が発生するが，データ数mの増大にはスケールしなければ問題ない

その他

  • Master-Worker構成の分散システムにおけるDMBについて議論
    • k個の分散システム全てに同じ処理を指せることは不可能
    • Masterで勾配情報の収集・勾配平均の計算・放送を行い，一方でWorkerはそれぞれ勾配を計算する
    • Masterが死んだ時の処理についてもアレコレ (Fault Torelance)
  • Robust Decentralized Architecture(ADMB)
    • さらにRobustなMaster-Worker構成のDMBアルゴリズムを提案
    • 各ノードは，勾配情報を近隣のノードにのみ送る
    • 各ノードは，自身の勾配情報と近隣ノードの購買情報がある程度集まったら，自身の重みベクトルを更新
    • Regret Boundは係数が2倍に