log.saiias

あてにならない備忘録

AdaGradとAdaDeltaの収束速度比較

AdaGradとAdaDeltaを実装&収束速度評価を行ってみました.

https://github.com/saiias/Adadelta

詳しいアルゴリズムは論文を参照してください. AdaGradもAdaDeltaのどちらも学習率を自動で調節することによって学習の高速化をすることができる手法です. どちらも実装が簡単で適用範囲が広いです.

AdaGradとAdaDeltaについてざっくり述べると

  • Adagradは過去すべての勾配の2乗和の平方根の逆数を利用
  • AdaDeltaはAdadeltaの改良版で,学習率の初期値が不要で、直近の勾配を重く評価する

などの特徴を持っています.

今回は実装の簡単さからロジスティック回帰+L2正則化の実装と評価を行いました. 実装についてはgithubにのせているのでここでは重みの更新式について記載します.

ロジスティック回帰+L2正則化

w(idx)はidx番目の重み,etaが学習率,label(i)がi行目の正解ラベル,X(i,idx)がi行目,idx番目の特徴量

w(idx) -= eta*((pred - label(i)) * X(i,idx) + C * w(idx));

AdaGard

Eは過去の勾配を2乗和を保存している配列

double grad = (pred - label(i)) * X(i,idx) + C * w(idx);
E(idx) +=grad * grad;
w(idx) -= (eta/sqrt(E(idx)))*grad;

AdaDelta

EはE[grad2]を,EdxはE[\delta x2]を保存している配列

double grad = (pred - label(i)) * X(i,idx) + C * w(idx);
E[idx] = rho * E[idx] + (1.0 - rho) * grad *grad;
double deltax = -(rms(Edx(idx))/rms(E(idx))) * grad;
Edx[idx] = rho * Edx[idx] + (1.0 - rho) * deltax * deltax;
w(idx) += deltax;

実験設定

  • データセット:a9a,a9a.t
  • コストC: 0.01(共通)
  • 学習率eta :0.01(LRとAdaGradの初期値)
  • 減衰率rho: 0.95(AdaDeltaのみ)
  • eps:0.0000001(AdaDeltaのみ)

実験結果

f:id:sa__i:20150103155233p:plain

まとめ

元論文ではMINISTのデータを利用した場合AdaDeltaのほうが収束が早いという結果でしたが今回の実装とデータセットではAdaGradのほうが収束が早いという結果になりました. もしからしたらrhoをepsilonの2変数についてパラメータチューニングをすればAdagradよりも早く収束するのかもしれません. またここには記載しませんでしたがliblinearで試してみたところ32イテレーションぐらいで学習が終わっていたのでAdagradのほうがやや早く収束しているようでした. ただ実装がへぼいので学習時間自体はliblinearのほうが断然早いですが…

参考