Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models
新年明けましておめでとうございます。今年初の論文紹介。
大規模なデータセットに対する条件付き最大エントロピーモデルの学習を並列で行う話[1]。
論文概要
条件付き最大エントロピーモデルの学習を並列でおこなうというタスクに関して、標準的な3通りの方法について比較を行った。
そのうちmixture weight methodに関しては収束レートの理論的解析を行っている
また100万件から10億件までのデータセットに対して実験を行った。
条件付き最大エントロピーモデル
条件付き最大エントロピーモデルの詳細に関しては文献[2]などを参考にされたい。
訓練データS={(x_1,y_1) , \dots , (x_m ,y_m)}が与えられたとする。ここでxは入力データ、yはクラスラベルだと思ってもらえればよい。素性ベクトルをとして、
としたとき、解かなければならない問題は
を最小化するwを求めることである。
ここでwを求める標準的なアルゴリズムとしては
w = 0 until convergence F(w)の勾配を求める F(w)の勾配を利用してwを更新 end return w
となる。
並列アルゴリズム
条件付き最大エントロピーモデルを並列に行う方法としてDistributed Gradient, Majority Vote, Mixture Weightの3つを挙げている。
このうちMajority VoteについてはMixture weightの方が実験的によい結果を示していることから、今回の論文紹介では割愛する。
Distributed Gradient
Distributed GradientではF(w)の式からサンプルをS=(S_1,\dots,S_p)とp個のマシンに分割したとき、独立に勾配を計算できることを利用している。アルゴリズムは次のようになる
w = 0
until convergence
各マシンでF_{S_k}(w)の勾配を求める
F_{S_k}(w)を足しあわせてF(w)の勾配を求める
F(w)の勾配を利用してwを更新
各マシン上のwを更新する
end
return wここでF_{S_k}(w)を足しあわせてF(w)の勾配を求めるという部分はMPIなどを用いると容易に実行できる。この方法の問題点としては各ステップにおいてwを更新して各マシンに再配布するということを行うためネットワークの通信量が増加するという点がある。このことはネットワークのレイテンシが大きい時には学習にかかるコストが大きくなる。
Mixture Weight
Mixture Weightではまず各マシンは独立にS_kを使ってw_kを学習する。
各マシンで学習が終了したら
を計算し、識別時に利用する。w_kの係数\mu_kは事前知識によって定まるが、特に事前知識がなければすべて1/pとすればよい。
この場合、ネットワークの利用は最初にデータをばらまくときと、最後に重みを統合するときだけでよく、ネットワーク資源を節約できる。
理論的解析
理論的解析においては各マシンにすべてのデータが同一分布から生成されたという仮定の元で、データを多くしていけばmixture weightも真の解に収束していくことを示している。この辺ちゃんと数式おってないので省略。
