NeuralnetworkをJavaScriptで実装した

# はじめに

「[色々な機械学習処理をブラウザ上で試せるサイトを作った](https://qiita.com/norimy/items/669c19ecf2256b3ecae5)」中で実装したモデルの解説の十三回目です。

今回はNeuralnetworkの実装について解説します。
MLP, Autoencoder, GAN, VAE, DQN/DDQNで使っています。

デモは[こちら](https://ai-on-browser.github.io/)から。
実際のコードは[neuralnetwork.js](https://github.com/ai-on-browser/ai-on-browser.github.io/blob/master/model/neuralnetwork.js)にあります。

なお、可視化部分や個別のモデルについては一切触れません。

# 概説

ニューラルネットワークそのものについては調べればすぐに情報が手に入ると思いますので、詳細は割愛します。

また、私は次のような知識の下で作成していますので、参考になるかどうかわかりません。ご注意ください。

- TensorflowやKerasやConvNetJSやNeuralNetworkConsoleといったものの使用感は知っているものの、その内部実装は詳しくない
- Define by runとかDefine and runとか言葉は知っているが、具体的にどんな利点があるのか理解しておらず、どう違うのかもよく分からない
- ニューラルネットワークの数学的知識は多少ある

Neuralnetworkの全体のコードは[ここ](https://github.com/ai-on-browser/ai-on-browser.github.io/blob/master/model/neuralnetwork.js)、Worker用のコードは[ここ](https://github.com/ai-on-browser/ai-on-browser.github.io/blob/master/model/worker/neuralnetwork_worker.js)にあります。
また、行列及びその演算は[ここ](https://github.com/ai-on-browser/ai-on-browser.github.io/blob/master/js/math.js)にあります。

なお、現在は三次元以上のデータに対応していないため、二次元以上のCNNや、RNNは実装することが難しいです。そのうちに対応するかもしれません。

## 計算グラフ

Neuralnetworkは各層をノードとする計算グラフ、つまり有向グラフに帰着できるので、有向グラフ構造を基本として実装します。

有向グラフの実装方法はいくつかありますが、今回はシンプルに各ノードにその親ノードを持つように実装しました。
始点となるノードから順番に処理していったときに、いろいろとやりやすいですし。

※説明にはグラフ理論から「グラフ」「ノード」と呼んでいますが、実装上は機械学習から「ネットワーク（`network`）」「層（`layer`）」を使っています。

## I/F

インタフェースはConvNetJSを参考に、オブジェクトの配列を受け取るようにしました。
各オブジェクトがノードにあたり、それぞれに自分の名前と、親ノードの名前の配列を持つことで、グラフ構造を構築できるようにしました。

また、使いやすくしたり、Conditional GANやVAEやDDQNを扱えるように、

- 親ノードが未指定の場合は直前に定義されたノードのみを親ノードとする
- 出力の指定がない場合は、最後のオブジェクトを出力とする
- 複数の入力を持つことができる
- 途中のノードの出力を複数取得できる
- 定数を使用する場合は、数値をそのまま指定できる
- データを分割した後の一部の取得は、`[]`によるアクセスを文字列として受け取る
- 損失関数は文字列で指定することも、特定のオブジェクトの出力を指定することもできる
- 別のグラフを間に挟むことができる
- 複製できる

などとしています。

例えば、三層のMLPは次のような感じに定義できるようにします。

```JavaScript
[
  { type: 'input' },
  { type: 'full', out_size: 10 },
  { type: 'sigmoid' },
  { type: 'full', out_size: 1 }
]
```

また、Conditional GANは次のように定義できるようにします。

```JavaScript:discriminator
[
  { type: 'input', name: 'dic_in' },
  { type: 'input', name: 'cond', input: [] },
  { type: 'onehot', name: 'cond_oh', input: ['cond'] },
  { type: 'concat', input: ['dic_in', 'cond_oh'] },
  { type: 'full', out_size: 10, activation: 'tanh' },
  { type: 'full', out_size: 10, activation: 'tanh' },
  { type: 'full', out_size: 2 },
  { type: 'softmax' }
]
```

```JavaScript:generator
[
  { type: 'input', name: 'gen_in' },
  { type: 'input', name: 'cond', input: [] },
  { type: 'onehot', name: 'cond_oh', input: ['cond'] },
  { type: 'concat', input: ['gen_in', 'cond_oh'] },
  { type: 'full', out_size: 10, activation: 'tanh' },
  { type: 'full', out_size: 10, activation: 'tanh' },
  { type: 'full', out_size: 2 },
  { type: 'leaky_relu', a: 0.1, name: 'generate' },
  { type: 'include', id: discriminatorId, input_to: 'dic_in', train: false }
]
```
※`discriminatorId`は先に定義したdiscriminatorを一意に特定できる値です

## グラフ

まずグラフ全体をいい感じに管理するクラスを作成します。

コンストラクタでは、学習(`fit`)、順伝播(`calc`)、逆伝播(`grad`)、パラメータ更新(`update`)、複製(`copy`)のそれぞれの処理をやりやすいよう、次の処理を行います。

- 出力が存在しない場合は追加
- 損失関数がコンストラクタで渡された場合はノード化
- 定数のノード化
- 各ノードの親ノード情報の取得

順伝播、逆伝播では、始めに全ノードに対して必要な変数の束縛を行います。そうしてから、どのノードに何を渡すのかを適宜確認しながら、それぞれのノードの処理を実行しています。
今回は親の情報を持っているので、順伝播では自分の「位置」に結果を格納して使用する側でそれらを受け取り、逆伝播では逆に自分を使用するノードの「位置」に渡します。

学習は順伝播、逆伝播、更新の処理を順番に実施するだけです。

コード全体は以下の通りです。

```JavaScript
class NeuralNetwork {
	constructor(layers, loss) {
		this._request_layer = layers;
		this._layers = [];
		if (layers.filter(l => l.type === 'output').length === 0) {
			layers.push({type: 'output'})
		}
		if (loss) {
			layers.push({type: loss})
		}
		const const_numbers = new Set();
		for (const l of layers) {
			if (l.input && Array.isArray(l.input)) {
				for (let i = 0; i < l.input.length; i++) {
					if (typeof l.input[i] === 'number') {
						const_numbers.add(l.input[i]);
						l.input[i] = `__const_number_${l.input[i]}`;
					}
				}
			}
		}
		if (const_numbers.size) {
			layers[0].input = [];
		}
		for (const cn of const_numbers) {
			const cl = new NeuralnetworkLayers.const({value: cn, size: 1, input: []})
			cl.network = this;
			cl.name = `__const_number_${cn}`
			cl.parent = [];
			this._layers.push(cl);
		}
		for (const l of layers) {
			const cl = new NeuralnetworkLayers[l.type](l);
			cl.network = this;
			cl.name = l.name;
			cl.parent = [];
			cl.input = l.input;
			if (l.input) {
				if (typeof l.input === 'string') {
					l.input = [l.input];
				}
				for (const i of l.input) {
					const subscriptRegexp = /\[([0-9]+)\]$/;
					const m = i && i.match(subscriptRegexp);
					const subscript = m ? +m[1] : null;
					const name = m ? i.slice(0, -m[0].length) : i;
					const tl = this._layers.filter(l => name === l.name);
					cl.parent.push({
						layer: tl[0],
						index: this._layers.indexOf(tl[0]),
						subscript: subscript
					});
				}
			} else {
				const pid = this._layers.length - 1;
				if (pid >= 0) {
					cl.parent.push({
						layer: this._layers[pid],
						index: pid,
						subscript: null
					});
				}
			}
			this._layers.push(cl);
		}
	}

	copy() {
		const cp = new NeuralNetwork(this._request_layer);
		for (let i = 0; i < this._layers.length; i++) {
			cp._layers[i].set_params(this._layers[i].get_params());
		}
		return cp;
	}

	calc(x, t, out, options = {}) {
		let data_size = 0
		if (Array.isArray(x)) {
			x = Matrix.fromArray(x);
			data_size = x.rows;
		} else if (!(x instanceof Matrix)) {
			for (const k of Object.keys(x)) {
				x[k] = Matrix.fromArray(x[k]);
				data_size = x[k].rows;
			}
		} else {
			data_size = x.rows;
		}

		for (const l of this._layers) {
			l.bind({input: x, supervisor: t, n: data_size, ...options});
		}
		const o = [];
		const r = {};
		for (let i = 0; i < this._layers.length; i++) {
			const l = this._layers[i];
			o[i] = l.calc(...l.parent.map(p => p.subscript !== null ? o[p.index][p.subscript] : o[p.index]));
			if (out && out.indexOf(l.name) >= 0) {
				r[l.name] = o[i];
				if (Object.keys(r).length === out.length) {
					return r;
				}
			}
			if (!t && l instanceof NeuralnetworkLayers.output) {
				if (out) return r;
				return o[i];
			}
		}
		if (out) return r;
		return o[o.length - 1];
	}

	grad(e) {
		const bi = [];
		let bi_input = null;
		for (let i = 0; i < this._layers.length; bi[i++] = []);
		bi[bi.length - 1] = [new Matrix(1, 1, 1)];
		for (let i = this._layers.length - 1; i >= 0; i--) {
			const l = this._layers[i];
			if (e) {
				if (l instanceof NeuralnetworkLayers.output) {
					bi[i] = [e];
					e = null;
				} else {
					continue;
				}
			}
			if (bi[i].length === 0) continue;
			let bo = l.grad(...bi[i]);
			if (!Array.isArray(bo)) {
				bo = Array(l.parent.length).fill(bo);
			}
			l.parent.forEach((p, k) => {
				if (!bo[k]) return;
				const subidx = p.subscript || 0;
				if (!bi[p.index][subidx]) {
					bi[p.index][subidx] = bo[k].copy();
				} else {
					bi[p.index][subidx].add(bo[k]);
				}
			});
			if (l instanceof NeuralnetworkLayers.input) {
				bi_input = bi[i][0]
			}
		}
		return bi_input;
	}

	update(learning_rate) {
		for (let i = 0; i < this._layers.length; i++) {
			this._layers[i].update(learning_rate);
		}
	}

	fit(x, t, epoch = 1, learning_rate = 0.1, options = {}) {
		if (Array.isArray(x)) {
			x = Matrix.fromArray(x);
		} else if (!(x instanceof Matrix)) {
			for (const k of Object.keys(x)) {
				x[k] = Matrix.fromArray(x[k]);
			}
		}
		t = Matrix.fromArray(t);

		let e;
		while (epoch-- > 0) {
			e = this.calc(x, t, null, options);
			this.grad();
			this.update(learning_rate);
		}
		return e.value;
	}
}
```

## ノード

グラフ構造を考えたときに、出ていく枝へは順伝播、入ってくる枝へは逆伝播することになります。
なので、最低限各ノードには順伝播・逆伝播それぞれの処理を実装する必要があります。
また、ハイパーパラメータ設定、パラメータ更新、状態の保存・読み込みなども行う必要があるので、全てのノードの親クラスとして以下のクラスを用意しました。

```JavaScript
class Layer {
	bind(x) {}

	calc(x) {
		throw new NeuralnetworkException("Not impleneted", this)
	}

	grad(bo) {
		throw new NeuralnetworkException("Not impleneted", this)
	}

	update(rate) {}

	get_params() {
		return null;
	}

	set_params(param) {}
}
```

実装自体は単純です。順伝播`calc`は単純に各ノード毎の処理を行ます。
また逆伝播`grad`はノードの処理を微分した（あるいは微分値の近似）値を引数に乗算します。いわゆる、自動微分ですね。
この二つを満たすことができれば、理論上はあらゆる計算処理を実装できます。

また、コンストラクタで初期パラメータの設定を、`update`でパラメータの更新処理を行います。

なお、学習時の呼び出し順は次のように保証します。

1. bind
2. calc
3. grad
4. update

例えばSigmoidの計算を行うノードは以下のように定義します。

```JavaScript
class SigmoidLayer extends Layer {
	constructor({a = 1}) {
		super();
		this._a = a;
	}

	calc(x) {
		this._o = x.copyMap(v => 1 / (1 + Math.exp(-this._a * v)));
		return this._o;
	}

	grad(bo) {
		const bi = this._o.copyMap(v => v * (1 - v));
		bi.mult(bo);
		return bi;
	}
}
```

また、全結合層は次のようになります。

```JavaScript
class FullyConnected extends Layer {
	constructor({in_size = null, out_size, activation = null, l2_decay = 0, l1_decay = 0}) {
		super();
		this._in_size = in_size;
		this._out_size = out_size;
		this._w = null;
		this._b = Matrix.randn(1, out_size);
		if (activation) {
			this._activation_func = new NeuralnetworkLayers[activation]
		}
		this._l2_decay = l2_decay;
		this._l1_decay = l1_decay;
	}

	calc(x) {
		if (!this._w) {
			this._w = Matrix.randn(x.cols, this._out_size);
		}
		this._i = x;
		this._o = x.dot(this._w);
		this._o.add(this._b);
		if (this._activation_func) {
			return this._activation_func.calc(this._o);
		}
		return this._o;
	}

	grad(bo) {
		this._bo = bo;
		if (this._activation_func) {
			this._bo = this._activation_func.grad(bo);
		}
		this._bi = this._bo.dot(this._w.t);
		return this._bi;
	}

	update(rate) {
		const dw = this._i.tDot(this._bo);
		dw.mult(rate / this._i.rows);
		if (this._l2_decay > 0 || this._l1_decay > 0) {
			for (let i = 0; i < dw.rows; i++) {
				for (let j = 0; j < dw.cols; j++) {
					const v = this._w.at(i, j)
					dw.addAt(i, j, (v * this._l2_decay + Math.sign(v) * this._l1_decay) * rate);
				}
			}
		}
		this._w.sub(dw);
		const db = this._bo.sum(0);
		db.mult(rate / this._i.rows);
		this._b.sub(db);
	}

	get_params() {
		return {
			w: this._w,
			b: this._b
		}
	}

	set_params(param) {
		this._w = param.w.copy();
		this._b = param.b.copy();
	}
}
```

なお実装したノードクラスは連想配列を使用して、[I/F](#if)で示した`type`と対応付けをしておきます。

## Worker

これだけでも動くのですが、さすがにこの処理をメインスレッドで実行するのは気が引けます。
なので、Workerスレッドで実行できるようにするため、次も用意しておきます。

```JavaScript
importScripts('../js/math.js');
importScripts('../js/neuralnetwork.js');

self.model = {};
self.epoch = {};

self.addEventListener('message', function(e) {
	const data = e.data;
	if (data.mode == 'init') {
		const id = Math.random().toString(32).substring(2);
		self.model[id] = new NeuralNetwork(data.layers, data.loss);
		self.epoch[id] = 0;
		self.postMessage(id);
	} else if (data.mode == 'fit') {
		const samples = data.x.length;
		if (samples == 0) {
			self.postMessage(null);
			return;
		}

		const loss = self.model[data.id].fit(data.x, data.y, data.iteration, data.rate, data.options);
		self.epoch[data.id] += data.iteration;
		self.postMessage({
			epoch: self.epoch[data.id],
			loss: loss,
		});
	} else if (data.mode == 'predict') {
		const samples = data.x.length;
		if (samples == 0) {
			self.postMessage([]);
			return;
		}

		const y = self.model[data.id].calc(data.x, null, data.out, data.options);
		if (y instanceof Matrix) {
			self.postMessage(y.toArray());
		} else {
			for (const k of Object.keys(y)) {
				y[k] = y[k].toArray();
			}
			self.postMessage(y);
		}
	} else if (data.mode === 'close') {
		delete self.model[data.id];
	} else if (data.mode === 'copy') {
		const id = Math.random().toString(32).substring(2);
		self.model[id] = self.model[data.id].copy();
		self.epoch[id] = 0;
		self.postMessage(id);
	}
}, false);
```

# 使用しているもの

MLP：[mlp.js](https://github.com/ai-on-browser/ai-on-browser.github.io/blob/master/model/mlp.js)
Autoencoder：[autoencoder.js](https://github.com/ai-on-browser/ai-on-browser.github.io/blob/master/model/autoencoder.js)
GAN/Conditional GAN：[gan.js](https://github.com/ai-on-browser/ai-on-browser.github.io/blob/master/model/gan.js)
VAE/Conditional VAE：[vae.js](https://github.com/ai-on-browser/ai-on-browser.github.io/blob/master/model/vae.js)
DQN/DDQN：[dqn.js](https://github.com/ai-on-browser/ai-on-browser.github.io/blob/master/model/dqn.js)

# おわりに

なぜJSON構造でニューラルネットワークの構造を完全に作る必要があるのか。
JavaScriptにもクラスの概念があるのだから、それで作ればいいじゃん。（つまりKerasみたいな感じです）
など、思うかもしれません。

確かにその通りです。
ですがそもそもこの仕様は、APIによるニューラルネットワークモデル構築の構想を練っていた時期があり、その時のアイディアを基にしています。
なので、少々冗長ですがこういった形にしています。Workerでも実行しやすいですしね。