AdaDeltaを試す - Negative/Positive Thinking

はじめに

勉強会で、学習率を改善(自動調整)する事で学習時間を短縮し、ファンタジスタドールを見る時間を多く確保できる事が示されていた。
AdaGrad等をさらに改良したらしいAdaDeltaがあるようなので、ロジスティック回帰に適用してみた。

AdaDeltaとは

M. D. Zeiler, ADADELTA: AN ADAPTIVE LEARNING RATE METHOD
- http://www.matthewzeiler.com/pubs/googleTR2012/googleTR2012.pdf
学習率を自動調整する方法の一つ
他の関連手法の問題点等を改良
- 過去すべての勾配を考慮→直近の勾配だけを考慮したいので、指数関数的に減衰するように考慮
- グローバルな学習率を指定→second order methodsの特性を持つように、パラメータの変化について直近のパラメータの変化から計算し利用
- RMS(root mean square)の計算→小さい値を加えてから平方根をとる

コード

http://d.hatena.ne.jp/jetbead/20131129/1385658526
上記の学習率を定数ではなくAdaDeltaに置き換える。

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string>
#include <unordered_map>
#include <cmath>


//乱数計算用関数
//xorshift
// 注意: longではなくint(32bit)にすべき
unsigned long xor128(){
  static unsigned long x=123456789, y=362436069, z=521288629, w=88675123;
  unsigned long t;
  t=(x^(x<<11));
  x=y; y=z; z=w;
  return w=(w^(w>>19))^(t^(t>>8));
}
//[0,1)の一様乱数
double frand(){
  return xor128()%10000000000/static_cast<double>(10000000000); 
}


//ロジスティック回帰クラス
class LR_adadelta {
  double rho_, eps_;
  double C_;
  std::unordered_map<std::string,double> weights, eg2, edx2;

  //シグモイド関数
  double sigmoid(double z){
    return 1.0 / ( 1.0 + exp(-z) );
  }

  //σ関数
  double sigma(const std::vector< std::pair<std::string,double> >& x){
    double z = 0;
    for(size_t i=0; i<x.size(); i++){
      z += weights[ x[i].first ] * x[i].second ;
    }
    return sigmoid(z);
  }

  //RMS[x]
  double RMS(double x){
    return sqrt( x + eps_ );
  }

public:
  LR_adadelta(double rho, double eps, double C):
    rho_(rho),eps_(eps),C_(C)
  {}

  //素性の重みをランダム値で初期化
  void setRandWeight(const std::string& feat){
    weights[ feat ] = frand();
  }

  //予測関数
  int predict(const std::vector< std::pair<std::string,double> >& x){
    return sigma(x) > 0.5 ? 1 : 0;
  }
  //確率値の計算
  double prob(const std::vector< std::pair<std::string,double> >& x){
    return sigma(x);
  }
  
  //L2正則化ロジスティック回帰 + AdaDelta
  void trainL2(int t, const std::vector< std::pair<std::string,double> >& x){
    double pred = sigma(x);
    std::unordered_map<std::string,double> xx;
    for(size_t i=0; i<x.size(); i++){
      xx[x[i].first] = x[i].second;
    }

    std::unordered_map<std::string,double>::iterator itr;
    for(itr = weights.begin(); itr != weights.end(); ++itr){
      //Compute Gradient: g_t
      double g = ( (pred-t) * xx[itr->first] + C_ * weights[ itr->first ] );
      //Accumulate Gradient: E[g^2]_t = \rho E[g^2]_{t-1} + (1-\rho) * g^2_t
      eg2[ itr->first ] = rho_ * eg2[ itr->first ] + (1.0 - rho_) * (g * g);
      //Compute Update: \Delta x_t = - (RMS[\Delta x]_{t-1}) / (RMS[g]_t) * g_t
      double deltax = - RMS(edx2[ itr->first ]) / RMS(eg2[ itr->first ]) * g;
      //Accumulate Updates: E[\Delta x^2]_t = \rho E[\Delta x^2]_{t-1} + (1-\rho) * \Delta x^2_t
      edx2[ itr->first ] = rho_ * edx2[ itr->first ] + (1.0 - rho_) * (deltax * deltax);

      //Apply Update: x_{t+1} = x_t + \Delta x_t
      weights[ itr->first ] += deltax;
    }    
  }

  //素性の数
  int weights_num(){
    return weights.size();
  }
  
  //ファイルへ重みを出力
  void save(const std::string& filename){
    std::ofstream ofs(filename);
    std::unordered_map<std::string,double>::iterator itr = weights.begin();
    for(; itr != weights.end(); ++itr){
      ofs << itr->first << " " << itr->second << std::endl;
    }
  }

  //ファイルから重みを入力
  void load(const std::string& filename){
    std::ifstream ifs(filename);
    weights.clear();
    
    std::string name;
    double value;
    while(ifs >> name >> value){
      weights[ name ] = value;
    }
  }
};


int main(){

  //パラメータ
  int iter_num = 1; //学習の反復回数
  double rho = 0.95; //減衰率
  double eps = 0.00001; //小さい定数
  double C = 0.001; //正則化のパラメータ
  std::ifstream trainfile("./a9a"); //学習データファイル
  std::ifstream testfile("./a9a.t"); //評価データファイル

  LR_adadelta lr(rho, eps, C);
  std::vector<int> dat_t;
  std::vector< std::vector< std::pair<std::string,double> > > dat;
  std::string line, feat;

  //学習////////////////////////////////////////////////
  //学習データの読み込み
  while(std::getline(trainfile, line)){
    int t;
    std::stringstream ss(line);
    ss >> t;
    if(t>0) t = 1;
    else t = 0;
    dat_t.push_back(t);
    
    std::vector< std::pair<std::string,double> > v;
    while(ss >> feat){
      std::string::size_type idx = feat.find(":");
      std::string name = feat.substr(0, idx);
      double value = atof(feat.substr(idx+1).c_str());

      v.push_back(std::make_pair(name, value));
      lr.setRandWeight(name); //素性の重みをランダム値で初期化しておく
    }
    dat.push_back(v);
  }
  //学習ループ
  for(int t=0; t<iter_num; t++){
    for(int i=0; i<dat.size(); i++){

      lr.trainL2(dat_t[i], dat[i]);

      //現在の学習データ全部での評価値を表示
      //int cnt = 0, cnt_zero = 0;
      //for(int j=0; j<dat.size(); j++){
      //  if(dat_t[j] == lr.predict(dat[j])) cnt++;
      //}
      //std::cerr << (double)cnt / dat.size() << std::endl;
    }
  }

  //重みデータの出力
  lr.save("weights.txt");



  //予測////////////////////////////////////////////////
  dat_t.clear();
  dat.clear();
  lr.load("weights.txt"); //重みデータの読み込み

  //テストデータの読み込み
  while(std::getline(testfile, line)){
    int t;
    std::stringstream ss(line);
    ss >> t;
    if(t>0) t = 1;
    else t = 0;
    dat_t.push_back(t);
    
    std::vector< std::pair<std::string,double> > v;
    while(ss >> feat){
      std::string::size_type idx = feat.find(":");
      std::string name = feat.substr(0, idx);
      double value = atof(feat.substr(idx+1).c_str());

      v.push_back(std::make_pair(name, value));
    }
    dat.push_back(v);
  }

  //評価
  {
    int cnt = 0, cnt_zero = 0;
    for(int i=0; i<dat.size(); i++){
      //std::cout << dat_t[i] << "\t" << lr.predict(dat[i]) << "\t"; printf("%.8lf\n", lr.prob(dat[i]));

      if(dat_t[i] == lr.predict(dat[i])) cnt++;
    }
    //最終結果の表示
    std::cout << cnt << "/" << dat.size() << "  Acc=" << (double)cnt / dat.size() << std::endl;
  }

  return 0;
}