JavaScript で実装してみる Deep Learning

// ユーティリティー関数
var DNNUtil = function() {
};

// ユーティリティー関数定義
DNNUtil.prototype = {
 
  // 正規乱数
  rnorm: function(mean, sd) {
    var x = Math.random();
    var y = Math.random();
    var ret = mean + sd * Math.sqrt(-2 * Math.log(x)) * Math.cos(2 * Math.PI * y);
    return ret;
  },

  randomChoice: function (ary, count) {
    // 配列のサイズが指定サイズ以下ならそのまま返します。
    if (ary.length <= count) {
      return ary;
    }

    // 新しい配列
    var newAry = [];
    // 使用済みインデックス
    var used = {};

    // 新しい配列が規定の数になるまでループします。
    while (true) {
      // 乱数
      var r = Math.floor(Math.random() * ary.length);
      // 既に使われている場合はスキップ
      if ((r in used)) {
        continue;
      }
      newAry.push(ary[r]);
      // 規定の数になったら break
      if (newAry.length == count) {
        break;
      }
      used[r] = 1;
    }
    return newAry;
  },

  getMeanAndSD: function(dataSet) {
    // 合計の計算
    var sum = [];
    for (var i = 0; i < dataSet.length; i++) {
      var items = dataSet[i]['data'];
      for (var j = 0; j < items.length; j++) {
        if (sum[j] === undefined) {
          sum[j] = 0;
        }
        sum[j] += items[j];
      }
    }
  
    // 平均
    var means = [];
    for (var k = 0; k < sum.length; k++) {
      means[k] = sum[k] / dataSet.length;
    }

    // 差の2乗の合計
    var squaredSum = [];
    for (var l = 0; l < dataSet.length; l++) {
      var items2 = dataSet[l]['data'];
      for (var m = 0; m < items2.length; m++) {
        if (squaredSum[m] === undefined) {
          squaredSum[m] = 0;
        }
        squaredSum[m] += Math.pow((items2[m] - means[m]), 2);
      }
    }

    // 標準偏差
    var sds = [];
    for (var p = 0; p < dataSet.length; p++) {
      var items3 = dataSet[p]['data'];
      for (var q = 0; q < items3.length; q++) {
        var sd = Math.sqrt(squaredSum[q] / dataSet.length);
        sds[q] = sd;
      }
    }
    return {means: means, sds: sds};
  },

 normalize: function(dataAry, mean, sd) {
    var newAry = [];
    for (var i = 0; i < dataAry.length; i++) {
      newAry.push((dataAry[i] - mean[i]) / sd[i]);
    }
    return newAry;
  }
};

var UnitType = {
  INPUT: 0,
  HIDDEN: 1,
  BIAS: 2,
  OUTPUT: 3
};

// ユニットクラス
var Unit = function(unitType) {

  // ユニットタイプ
  this.unitType = unitType;

  // ユニット自体に左右の結合オブジェクトへの参照を持たせることで lookup を容易にしています。
  // 結合オブジェクト（左側）
  this.leftConnections = [];
  // 結合オブジェクト（右側）
  this.rightConnections = [];
  // 入力値 全結合層の場合は前の層の全ユニットからの出力の合計とバイアスの合計です。
  // 今回はバイアスユニットの出力と重みも加算されます。
  this.inputValue = 0;

  // 出力値（バイアスの出力は1固定になります。）
  this.outputValue = 0;
  if (unitType === UnitType.BIAS) {
    this.outputValue = 1;
  }

  // デルタ
  // 誤差逆伝播法で重要な要素になります。ユニットオブジェクトに持たせます。
  this.delta = 0;
};

// ユニットクラス定義
Unit.prototype = {

  // ユニットタイプの取得
  getUnitType: function(unitType) {
    return this.unitType;
  },

  // 結合オブジェクト（左側）の配列を設定
  setLeftConnections: function(connections) {
    // 中間層と出力層のみ
    if (this.unitType !== UnitType.HIDDEN &&
        this.unitType !== UnitType.OUTPUT) {
      throw new Error('Invalid unit type');
    }
    this.leftConnections = connections;
  },

  // 結合オブジェクト（右側）の配列を設定
  setRightConnections: function(connections) {
    // 入力層と中間層とバイアスのみ
    if (this.unitType !== UnitType.INPUT &&
        this.unitType !== UnitType.HIDDEN &&
        this.unitType !== UnitType.BIAS) {
      throw new Error('Invalid unit type');
    }
    this.rightConnections = connections;
  },

  // 結合オブジェクト（左側）の配列を取得
  getLeftConnections: function() {
    // 中間層と出力層のみ
    if (this.unitType !== UnitType.HIDDEN &&
        this.unitType !== UnitType.OUTPUT) {
      throw new Error('Invalid unit type');
    }
    return this.leftConnections;
  },

  // 結合オブジェクト（右側）の配列を取得
  getRightConnections: function() {
    // 入力層と中間層とバイアスのみ
    if (this.unitType !== UnitType.INPUT &&
        this.unitType !== UnitType.HIDDEN &&
        this.unitType !== UnitType.BIAS) {
      throw new Error('Invalid unit type');
    }
    return this.rightConnections;
  },

  // 入力値を設定
  setInput: function(value) {
    // 入力層と中間層と出力層のみ
    if (this.unitType !== UnitType.INPUT &&
        this.unitType !== UnitType.HIDDEN &&
        this.unitType !== UnitType.OUTPUT) {
      throw new Error('Invalid unit type');
    }
    this.inputValue = value;
  },

  // 入力値を取得
  getInput: function() {
    // 入力層と中間層と出力層のみ
    if (this.unitType !== UnitType.INPUT &&
        this.unitType !== UnitType.HIDDEN &&
        this.unitType !== UnitType.OUTPUT) {
      throw new Error('Invalid unit type');
    }
    return this.inputValue;
  },

  // 出力値を設定
  setOutput: function(value) {
    this.outputValue = value;
  },

  // 出力値を取得
  getOutput: function() {
    return this.outputValue;
  },

  // デルタを設定
  setDelta: function(delta) {
    // 中間層と出力層のみ
    if (this.unitType !== UnitType.HIDDEN &&
        this.unitType !== UnitType.OUTPUT) {
      throw new Error('Invalid unit type');
    }
    this.delta = delta;
  },

  // デルタを取得
  getDelta: function() {
    // 中間層と出力層のみ
    if (this.unitType !== UnitType.HIDDEN &&
        this.unitType !== UnitType.OUTPUT) {
      throw new Error('Invalid unit type');
    }
    return this.delta;
  }
};

var Connection = function() {
  // ユニット（左側）
  this.leftUnit = {};
  // ユニット（右側）
  this.rightUnit = {};

  // 重み
  this.weight = 1;

  // 重みの差分(一時保存用)
  this.weightDiff = 0;
};

// コネクションクラス定義
Connection.prototype = {

  // ユニット（左側）の設定
  setLeftUnit: function(unit) {
    this.leftUnit = unit;
  },

  // ユニット（右側）の設定
  setRightUnit: function(unit) {
    this.rightUnit = unit;
  },

  // ユニット（左側）の取得
  getLeftUnit: function() {
    return this.leftUnit;
  },

  // ユニット（右側）の取得
  getRightUnit: function() {
    return this.rightUnit;
  },

  // 重みの設定
  setWeight: function(weight) {
    this.weight = weight;
  },

  // 重みの取得
  getWeight: function() {
    return this.weight;
  },

  // 重みの差分の設定
  setWeightDiff: function(diff) {
    this.weightDiff = diff;
  },

  // 重みの差分の取得
  getWeightDiff: function() {
    return this.weightDiff;
  }
};

// パラメータは下記のような形式で渡します。
// {numOfUnits:[], weights:[[],...], means:[], sds:[]}
// なお、weights、means、sds は任意です。
var DNN = function(param) {
  // パラメータチェック
  if (param === null || param === undefined) {
    throw new Error("Null parameter.");
  }
  if ('numOfUnits' in param === false) {
    throw new Error("numOfUnits must be specified.");
  }
  if (param['numOfUnits'].length <= 2) {
    throw new Error("At least 1 hidden units must be specified.");
  }

  // デフォルトの重み
  this.DEFAULT_WEIGHT = 0;
  
  // ユニット数
  this.numOfUnits = param['numOfUnits'];

  // 学習係数(Default)
  this.learningCoefficient = 0.01;
  
  // ミニバッチサイズ
  this.miniBatchSize = 10;

  // 接続オブジェクト
  this.connections = {};

  // ユニットオブジェクト
  this.units = {};

  // 入力値の平均
  this.inputMeans = [];
  if ('means' in param) {
    this.inputMeans = param['means'];
  }

  // 入力値の標準偏差
  this.inputSDs = [];
  if ('sds' in param) {
    this.inputSDs = param['sds'];
  }

  ////// 各種初期化プロセス
  // 全ての層をまとめたもの
  var layersArray = [];

  // 入力層の初期化（バイアスユニットを先頭に持ってきます）
  var inputUnitArray = [];
  inputUnitArray.push(new Unit(UnitType.BIAS)); // BIAS
  for (var i = 0; i < this.numOfUnits[0]; i++) {
    inputUnitArray.push(new Unit(UnitType.INPUT));
  }
  layersArray.push(inputUnitArray);
    
  // 中間層の初期化（バイアスユニットを先頭に持ってきます）
  for (var j = 1; j < this.numOfUnits.length - 1; j++) {
    var hiddenUnitArray = [];
    hiddenUnitArray.push(new Unit(UnitType.BIAS)); // BIAS
    for (var k = 0; k < this.numOfUnits[j]; k++) {
      hiddenUnitArray.push(new Unit(UnitType.HIDDEN));
    }
    layersArray.push(hiddenUnitArray);
  }

  // 出力層の初期化
  var outputUnitArray = [];
  for (var l = 0; l < this.numOfUnits[this.numOfUnits.length - 1]; l++) {
    outputUnitArray.push(new Unit(UnitType.OUTPUT));
  }
  layersArray.push(outputUnitArray);

  // ユニットオブジェクト
  this.units = layersArray;

  // Util
  var dnnUtil = new DNNUtil();

  // コネクションの生成
  var allConnectionArray = [];

  // 層の数 - 1 のコネクション「層」が必要
  for (var m = 0; m < this.numOfUnits.length - 1; m++) {

    // 現在のコネクション層
    var connectionArray = [];

    // 現在のコネクション層の左側のユニットをループ
    for (var n = 0; n < this.units[m].length; n++) {

      // 左のユニット毎にそのユニットの右に出ているコネクション
      var connArray = [];

      // 左ユニット
      var leftUnit = this.units[m][n];

      // 右隣のユニットをループ
      for (var p = 0; p < this.units[m + 1].length; p++) {

        var rightUnit = this.units[m + 1][p];

        // 右隣のバイアスユニットは除く
        if (rightUnit.getUnitType() !== UnitType.BIAS) {

          var conn = new Connection();

          // 現在のコネクション層の右側のユニットをセット
          conn.setRightUnit(rightUnit);

          // 現在のコネクション層の左側のユニットをセット
          conn.setLeftUnit(leftUnit);

          // 重みの設定
          if (leftUnit.getUnitType() === UnitType.BIAS) {
            // 左のユニットがバイアスユニットの場合
            conn.setWeight(this.DEFAULT_WEIGHT);
          } else {
            // 左のユニットがバイアスユニットでない場合
            conn.setWeight(this.DEFAULT_WEIGHT + dnnUtil.rnorm(0, 1));
          }
          connArray.push(conn);

          // 右ユニットの左側コネクションに追加
          var connTmpArray = rightUnit.getLeftConnections();
          connTmpArray.push(conn);
          rightUnit.setLeftConnections(connTmpArray);
        }
      }

      // 現在のコネクション層に追加
      connectionArray.push(connArray);

      // 左ユニットの右側結合にセット
      leftUnit.setRightConnections(connArray);
    }

    // 全てのコネクションに追加
    allConnectionArray.push(connectionArray);
  }

  // 全てのコネクション
  this.connections = allConnectionArray;

  // weightsが指定されている場合
  if ('weights' in param) {

    // 重みのみの配列から重みを対応するconnectionにそれぞれ設定する
    for (var s = 0; s < this.connections.length; s++) {
      for (var t = 0; t < this.connections[s].length; t++) {
        for (var u = 0; u < this.connections[s][t].length; u++) {
          this.connections[s][t][u].setWeight(param['weights'][s][t][u]);
        }
      }
    }
  }
};

// DNNメインクラス定義
DNN.prototype = {

  // 学習係数の設定
  setLearningCoefficient: function(coefficient) {
    this.learningCoefficient = coefficient;
  },

  // ミニバッチサイズの設定
  setMiniBatchSize: function(size) {
    this.miniBatchSize = size;
  },

  /**
   * モデルの取得
   * 各層のユニット数と重みを返す
   * {
   *   numOfUnits:[入力層のユニット数,中間層1のユニット数,...,出力層のユニット数],
   *   weights:[[重み,...],[..],...],
   *   means:[入力値1の平均,入力値2の平均,...],
   *   sds:[入力値1の標準偏差,入力値2の標準偏差,...],
   * }
   */
  getModel: function() {
    var weights = [];
    for (var i = 0; i < this.connections.length; i++) {
      var weightsSub = [];
      for (var j = 0; j < this.connections[i].length; j++) {
        var weightsSubSub = [];
        for (var k = 0; k < this.connections[i][j].length; k++) {
          weightsSubSub.push(this.connections[i][j][k].getWeight());
        }
        weightsSub.push(weightsSubSub);
      }
      weights.push(weightsSub);
    }
    return {numOfUnits:this.numOfUnits,
            weights:weights,
            means:this.inputMeans,
            sds:this.inputSDs};
  },

  /**
   * 学習
   * @param data [{data:[a_1,a_2,...,a_n], expected:c}],[...],...
   * @return
   */
  train: function(dataSet) {
    // データセットの平均と標準偏差を取得
    var dnnUtil = new DNNUtil();
    var msd = dnnUtil.getMeanAndSD(dataSet);
    this.inputMeans = msd['means'];
    this.inputSDs = msd['sds'];

    // ミニバッチ用データ選択
    var data = dnnUtil.randomChoice(dataSet, this.miniBatchSize);

    // {クラス,データ}のペアを繰り返し処理
    for (var n = 0; n < data.length; n++) {

      // 判定処理を実行して各層の入力、出力を確定させる
      this.predict(data[n]['data']);

      // 誤差逆伝播（まず重みの差分を計算、あとでまとめて更新する）
      // 出力層から順に
      // 入力層は除く
      for (var k = this.numOfUnits.length - 1; k > 0; k--) {
        for (var l = 0; l < this.units[k].length; l++) {

          // ユニット
          var unit = this.units[k][l];

          // デルタ
          var delta = 0;

          // 出力層か中間層のユニットの場合（バイアスは除く）
          if (unit.getUnitType() === UnitType.OUTPUT || unit.getUnitType() === UnitType.HIDDEN) {

            // 出力層のユニットの場合
            if (unit.getUnitType() === UnitType.OUTPUT) {

              // 出力層のデルタは y - d
              delta = unit.getOutput();

              // 期待されるクラスの場合は-1する（出力層のデルタはy - dなので）
              if (data[n]['expected'] == l) {
                delta -= 1;
              }

            // 中間層のユニット（バイアスは除外）
            } else {

              // 入力値
              var inputValue = unit.getInput();

              // 上位層のユニットを右側結合を通じてループ
              var rightConns = unit.getRightConnections();
              for (var m = 0; m < rightConns.length; m++) {

                // デルタ * 重み * 正規化線形関数の1階微分
                delta += rightConns[m].getRightUnit().getDelta() *
                         rightConns[m].getWeight() *
                         ((inputValue < 0) ? 0 : 1);
              }
            }

            // デルタをセット
            unit.setDelta(delta);

            // 重みの差分を前回の逆伝播の結果に追加（左側結合の全て）
            var conns = unit.getLeftConnections();
            for (var p = 0; p < conns.length; p++) {
              var diff = conns[p].getWeightDiff(); 

              // デルタ * 左側ユニットの出力
              diff += delta * conns[p].getLeftUnit().getOutput();
              conns[p].setWeightDiff(diff);
            }
          }
        }
      }

      // 誤差逆伝播（重みの更新）
      // connectionに重みの差分がセットされているのでそれらを順次適用する
      for (var q = 0; q < this.connections.length; q++) {
        for (var r = 0; r < this.connections[q].length; r++) {
          for (var s = 0; s < this.connections[q][r].length; s++) {

            var conn = this.connections[q][r][s];
            var weight = conn.getWeight();
            weight -= this.learningCoefficient * conn.getWeightDiff();

            // 新しい重みをセット
            conn.setWeight(weight);

            // 重みの差分をクリア
            conn.setWeightDiff(0);
          }
        }
      }
    }
  },

  /**
   * テスト
   * @param data [{data:[a_1,a_2,...,a_n], expected:c}],[...],...
   * @return 誤差関数の値
   */
  test: function(dataSet) {
    // 誤差
    var e = 0;
    // ミニバッチ用データ選択
    var dnnUtil = new DNNUtil();
    var data = dnnUtil.randomChoice(dataSet, this.miniBatchSize);

    // {クラス,データ}のペアを繰り返し処理
    for (var n = 0; n < data.length; n++) {

      // 判定処理を実行して各層の入力、出力を確定させる
      this.predict(data[n]['data']);

      // 出力層
      var outputUnits = this.units[this.numOfUnits.length - 1];

      // 出力層の出力の合計
      var sum = 0;

      // 誤差関数の計算
      for (var i = 0; i < outputUnits.length; i++) {

        // クラスが一致した場合のみ出力の対数値を加算（クラスが一致しない場合は0をかけるので）
        if (data[n]['expected'] == i) {
          sum += Math.log(outputUnits[i].getOutput());
        }
      }

      // 符号を反転して加算
      e += -1 * sum;
    }

    // eの平均値を返す
    var avg_e = e / data.length;

    return avg_e;
  },

  /**
   * 判定
   * @param data [a_1,a_2,...,a_n]
   * @return best: 最も値の高かった出力層のユニットのインデックス
   *                result: 最も値の高かった出力層のユニットの値
   */
  predict: function(dataSet) {

    // ソフトマックス関数の計算用
    var denom = 0;
    var denomArray = [];

    // データセットを正規化する
    var dnnUtil = new DNNUtil();
    var data = dnnUtil.normalize(dataSet, this.inputMeans, this.inputSDs);

    // バイアスを除く入力層のユニット全部
    // 現在の層のユニット全部
    var g = 0;
    for (var h = 0; h < this.units[0].length; h++) {
      if (this.units[0][h].getUnitType() != UnitType.BIAS) {

        // 入力層は入力値=出力値
        this.units[0][h].setInput(data[g]);
        this.units[0][h].setOutput(data[g]);
        g++;
      }
    }

    // 入力層以降から繰り返し
    for (var i = 1; i < this.units.length; i++) {

      // 現在の層のユニット全部
      for (var j = 0; j < this.units[i].length; j++) {
        var unit = this.units[i][j];

        // 中間層と出力層の場合(バイアスの出力は常に1なので処理しない)
        if (unit.getUnitType() === UnitType.HIDDEN ||
            unit.getUnitType() === UnitType.OUTPUT) {

          // 左側ユニットの出力*重みの合計
          var sum = 0;

          // 左結合
          var connArray = unit.getLeftConnections();
          for (var k = 0; k < connArray.length; k++) {
            var conn = connArray[k];

            // 左側ユニットの出力 * 左側結合の重みを加算
            sum += conn.getLeftUnit().getOutput() * conn.getWeight();
          }
          unit.setInput(sum);

          // 出力層の場合はソフトマックス関数計算用変数をセット
          if (unit.getUnitType() === UnitType.OUTPUT) {
            var ex = Math.exp(unit.getInput());
            denom += ex;
            denomArray.push(ex);

          // 中間層の場合は正規化線形関数
          } else {
            if (unit.getInput() < 0) {
              unit.setOutput(0);
            } else {
              unit.setOutput(unit.getInput());
            }
          }
        }
      }
    }

    // ソフトマックス関数計算用変数からOUTPUTユニットの最終結果を計算
    var result = [];
    var outputUnits = this.units[this.numOfUnits.length - 1];
    for (var p = 0; p < denomArray.length; p++) {
      var res = denomArray[p] / denom;
      result.push(res);
      // outputに出力値をセットする。学習時の誤差関数に出力が必要になる
      outputUnits[p].setOutput(res);
    }

    // 最も確率の高い結果を調べる
    var best = -1;
    var idx = -1;
    for (var q = 0; q < result.length; q++) {
      if (best < result[q]) {
        best = result[q];
        idx = q;
      }
    }

    return {best:idx, result:result};
  }
}; 

module.exports.DNN = DNN;

// パラメータのチェック
if (process.argv.length !== 3) {
  console.log("Usage: node cross_validation.js <training data file>");
  process.exit();
}
// ファイルシステムオブジェクト
var fs = require('fs');
var dataFile = process.argv[2];
// DNN.js の読み込み
var DNN = require('./DNN.js');

// 下記のネットワーク構成とします。
// 入力層: 4 ユニット
// 中間層: 4, 4 ユニット
// 出力層: 3 ユニット
var dnn = new DNN.DNN({numOfUnits:[4, 4, 4, 3]});

// 学習係数の設定
dnn.setLearningCoefficient(0.001);
// 学習データを読み込みます。
var data = fs.readFileSync(dataFile, 'utf-8');
 
// 改行で split します。データセットの取得先によって変わるかも。
var lines = data.split("\r\n");
// 10-fold cross validation を行います。
// 1 分割あたりのデータ数を計算
var size = Math.floor(lines.length / 10);

// 全てのデータセット
var allDataSets = [];
var i = 0;
 
// 精度計算用
var accuracySum = 0;
// ループ
while (1) {
  // データセット
  var dataSets = [];
 
  // 1 分割あたりのデータ数までを dataSets にセットします。
  for (var j = 0; j < size; j++) {
    if (i > lines.length - 1) {
      break;
    }
    var ary = lines[i].split("\t");
    dataSets.push(ary);
    i++;
  }
 
  // 全データセットに配列として追加します。
  allDataSets.push(dataSets);
 
  // 10 データセットになったら break
  if (allDataSets.length == 10) {
    break;
  } 
}
 
// 全データセット分ループ
for (var i = 0; i < allDataSets.length; i++) {
 
  // 学習データとテストデータ
  var trainData = [];
  var testData = [];
 
  // 再度全データセット分ループ
  for (var j = 0; j < allDataSets.length; j++) {
    // データセットをループ
    for (var k = 0; k < allDataSets[j].length; k++) {
      // テストデータを保存
      if (i == j) {
        testData.push(allDataSets[j][k]);
      // 学習データを保存
      } else {
        trainData.push(allDataSets[j][k]);
      }
    }
  }
 
  // 誤差関数の出力が規定の値未満になるまで最大 10000 回ループします。
  for (var l = 0; l < 10000; l++) {
 
    // DNN.js に渡すデータ
    var inputData = [];
    for (var m = 0; m < trainData.length; m++) {
      // ラベル部分を除外したもの
      var dataPart = [];
      for (var n = 1; n < trainData[m].length; n++) {
        dataPart.push(Number(trainData[m][n]));
      } 
      // DNN.js に渡すデータに追加
      inputData.push({expected:Number(trainData[m][0]), data:dataPart}); 
    }
 
    // 学習処理
    dnn.train(inputData);
 
    // 1 学習後のネットワークに対して入力データによる誤差関数の値を取得
    var result = dnn.test(inputData);
 
    // 誤差関数の値が 0.01 未満であれば break
    if (result < 0.01) {
      break;
    }
  }
 
  // 正解数
  var corrects = 0;
 
  // テストデータをループしてテスト
  for (var o = 0; o < testData.length; o++) {
 
    // ラベル以外の部分
    var dataPart = [];
    for (var p = 1; p < testData[o].length; p++) {
      dataPart.push(Number(testData[o][p]));
    }
 
    // 判定
    var result = dnn.predict(dataPart);
 
    // best には最も値の高かったラベルが入っています。
    if (result['best'] == Number(testData[o][0])) {
      corrects++;
    }
  }
 
  // 1 回のループ（学習と判定）における精度の平均値を加算
  accuracySum += 100 * corrects / testData.length;
}
 
// 全ループによる精度の平均値を出力
console.log("accuracy: " + (accuracySum / allDataSets.length) + "%"); 

$ ../../github/libsvm/svm-train -c 8192 -g 3.0517578125e-05 -v 10 -q train_data_fisher_libsvm.txt
Cross Validation Accuracy = 97.3333%

$ ../../github/libsvm/svm-train -v 10 -q train_data_fisher_libsvm.txt
Cross Validation Accuracy = 82.6667%

$ node cross_validation.js train_data_fisher.txt 
accuracy: 97.33333333333333%