HTMLファイルで動作するWord2Vecもどきを作った

# 概要
完全に単一のHTMLファイルで動作するWord2Vecもどき(uni2vec)を作りました。

# やりたかったこと
- ブラウザだけで自然言語処理をしたい。
- サーバサイドでは処理したくない。

# 操作方法
- 以下のファイルを保存します。
https://sites.google.com/site/uni2vec/cab/uni2vec.html
- uni2vec.htmlを開きます。
- src area を指定します。(2017/11/4 新規)
 - 標準では src area に設定された kiwix-serve サーバに Ajax アクセスして学習データを読み込みます。
 - URLを改行区切りで記述すると、 Ajax アクセスして学習データを読み込みます。
 - src area に日本語文字列を記述すると、文字列を学習データとします。
- train で CNN を学習します。
- analogy で CNN をテストし結果を出力します。
- monolog で文字列を順次生成します(独り言です)。
- display で文字特徴ベクトルの配列を表示します。
- output で文字特徴ベクトルを出力します。(2017/11/4 新規)
- load で文字特徴ベクトルを読み込みます。(2017/11/4 新規)

# 機械学習の観点の技術内容
- Muliplied CNNは、Word2Vec と Gated CNN をまとめて一般化したものです。
- 各文字コードについて文字特徴ベクトルをランダムに決めます。(Word2Vecでは単語特徴ベクトルと呼びます)
- 基点文字xの文字特徴ベクトルXと、任意文字yの文字特徴ベクトルYについて、xとyの入力文字列の位置の差を元に関連度t(教師信号)決め、畳み込みカーネルAとします。(ウインドウサイズ範囲内の場合1、範囲外の場合0としています)
- これらと学習率aを組み合わせて差分diffを以下で求めます。(X・YはXとYの内積、activationは活性化関数、gateはゲート関数です)

```math
\text{diff} = a * 1.0 * \text{activation}(t - \text{gate}(X・Y))
```

- 差分の意味は次の通りです。
 - 教師信号で関連があり(t=1)、かつ想起信号で関連が少ない(X・Y≒0)場合、ベクトルXにYの成分を何割か足して関連を高めます。
 - 教師信号で関連がなく(t=0)、かつ想起信号で関連が高い(X・Y≒1)場合、ベクトルXからYの成分を何割か引いて関連を低めます。
- Xに学習結果を反映します。

```math
X = X + \text{diff} * Y
```

- 入力文字列について上記を繰り返して、畳み込みカーネルAについて学習します。
- 畳み込みカーネルB、Cについても学習します。
- 学習後、畳み込みカーネルをA、B、文字x、yの文字特徴ベクトルをそれぞれ$A_X,A_Y,B_X,B_Y$としたとき、関連度r(想起)を以下で計算します。

```math
r = \text{gate}(A_X・A_Y) * \text{gate}(B_X・B_Y)
```

- Word2VecとTweet2Vecは以下のサイトを参照しました。
 - https://code.google.com/p/word2vec/
 - http://qiita.com/Hironsan/items/11b388575a058dc8a46a
 - http://qiita.com/mash0510/items/347964f3eb2e080ea7a4
 - http://qiita.com/moriokumura/items/49fb30e0e88eade91739

- Gated CNNは以下のサイトを参照しました。
 - https://arxiv.org/abs/1612.08083
 - http://qiita.com/Hironsan/items/63d255fd038acbcdf95b
 - http://qiita.com/supersaiakujin/items/3c71c6572dc3036edab1

# WebGLの観点の技術内容
- テクスチャを使用してオフラインレンダリングで計算します。
- テクスチャは正方形であり、かつ縦横のピクセル数が2の累乗である必要があります。
- 頂点シェーダ内において、gl_Position変数に指定するvec4型変数のxy領域の範囲は以下の通りです。

```
   y
 1.0-----
    |   |
    |   |
-1.0-----
 -1.0   1.0 x
```

- なのでソースの以下の箇所は(-1,-1)(1,-1)(-1,1)(1,1)を2次元の頂点とする塗りつぶしの4角形を描画することを意味しています。

```js
gl.bufferData(gl.ARRAY_BUFFER, new Float32Array([-1,-1,  1,-1,  -1,1,  1,1]), gl.STATIC_DRAW);
gl.vertexAttribPointer(location, 2, gl.FLOAT, false, 0, 0);
gl.drawArrays(gl.TRIANGLE_STRIP, 0, 4);
```

- 領域の四隅を塗りつぶしており、領域全体を塗りつぶししてるため、領域の各ピクセルがフラグメントシェーダの処理対象になります。
- フラグメントシェーダ内において、texture2D関数で指定するsampler2D型変数(テクスチャ)のxy領域の範囲は次の通りです。

```
  y
1.0-----
　 |   |
　 |   |
  0-----
   0  1.0 x
```

- またフラグメントシェーダ内において、gl_FragCoord.xy変数で取得できるvec2型変数のxy領域(そしてこれはgl_FragColor変数に指定した色情報が反映される位置)の範囲は以下の通りです。

```
    y
height-----
  　  |   |
　    |   |
     0-----
　    0  width x
```

- なのでソースの以下の箇所は、gl_FragCoord変数(フラグメントシェーダで色情報が反映される位置)から、テクスチャで「そのまま等倍で」取得したい位置の色情報を取得し設定することを意味しています。

```js
gl_FragColor = texture2D(Tex, gl_FragCoord.xy * scale); // scale = 1.0 / width
```

- テクスチャの内容をデフォルトのフレームバッファに出力しなくても、テクスチャを関連付けたフレームバッファをバインドすればreadPixels関数を使用してFLOAT型のデータを直接取得することができます。
- テクスチャにfloat型を使用する場合、gl.TEXTURE_MAG_FILTERとgl.TEXTURE_MIN_FILTERにはgl.NEARESTまたはgl.LINEAR_MIPMAP_NEARESTを指定しなければいけません。(MS Edgeのワーニングメッセージから判明しました。Chromeのメッセージからは分かりませんでした。)

- uni2vecの特徴
 - Word2Vecにおいて、単語特徴ベクトルの演算は、ウインドウ関数をカーネル関数とする畳み込み演算(convolution)です。
 - 座標がインデックス(charCodeに対応している)、値が演算に使用するスカラー値となるようなテクスチャを定義して使用しています。
 - 以下のdiffDotフラグメントシェーダでは、書き込み先フレームバッファの座標がインデックス(gl_FragCoord.xy→idxA)、ワーク入力テクスチャがそれに対応するインデックス(workTexIdx→rgbaIdxB)として、全てのインデックスについて、対応するインデックスとの関係(myFunc：matTexと指定した教師信号→差分)を計算しています。各インデックスに関する差分を一つのフラグメントシェーダで計算させるプログラムにより、GPUによる並列計算を「促す」ことができます。

```js
uniform sampler2D matTex;
uniform sampler2D workTexIdx;
float myFunc(float idxA, float idxB) {
	return (idxB < 0.0) ? 0.0 : (env[OTHER][ALPHA] * activation(
		env[OTHER][TEACHER] - gate(env[FUNCTION][GATE], calcDot(matTex, idx2MatFrag(idxA), idx2MatFrag(idxB)))
	));
}
void main() {
	float idxA = work2Idx(gl_FragCoord.xy);
	vec4 rgbaIdxB = texture2D(workTexIdx, work2Tex(gl_FragCoord.xy));
	gl_FragColor = vec4(
		myFunc(idxA    , rgbaIdxB.r),
		myFunc(idxA+1.0, rgbaIdxB.g),
		myFunc(idxA+2.0, rgbaIdxB.b),
		myFunc(idxA+3.0, rgbaIdxB.a));
}
```

# インターネットの観点の技術内容
- (2017/11/4 新規)
- kiwix-serveについて
 - kiwixをインストールして開くとダウンロード一覧が表示されます。
 - 例としてwikipediaの日本語・文字列のみ(約5GB)のzimファイルをダウンロードします。
  - ダウンロードに失敗するのは、ハードディスクドライブのファイルシステムの制約によるものの可能性が高いです。
  - 過去にフォーマットされたファイルシステムでは、4GBを超える1つのファイルを作成することができないためです。
 - kiwixに同梱されているkiwix-serveを起動します。
  - `kiwix-serve --port=8080 ~/.www.kiwix.org/kiwix/XXX.default/data/content/wikipedia_ja_all_nopix_20XX_XX.zim`
 - uni2vecからkiwix-serveにアクセス先を指定します。
- Cross-Origin Resource Sharing (CORS) について
 - ルーターの内側なら、違うポートでもアドレスでもAjaxでアクセスできる模様。kiwix-serveを、ブラウザと同じセグメントに立てれば良いです。

# JavascriptのTipsのの観点の技術内容
uni2vec で使用したTips技術を紹介します。(2017/11/4 新規)

## fract 関数
小数部分を取得します。glsl 言語の fract 関数と同じように動作します。

```js
function fract(value) {
	return value % 1;
}
```

## createFilter 関数
`addEventLister`関数の引数に指定するリスナーを生成した関数で包む、高階関数を応用した技術です。イベント実行時エラーを捕捉して、出力などを制御する処理を追加するのが簡単になります。

```js
function FormManager(form, destKey) {
	/** @type {function(string)} */
	const bindedSetDest = this.setDest.bind(this);
	/** @type{function(function):function} */
	this._bindedCreateFilter_ = function(listener) {
		return function(arg0, arg1, arg2) {
			try {
				return listener(arg0, arg1, arg2);
			} catch (e) {
				const message = e.message;
				bindedSetDest("\nerror : " + message);
				if (message == null || message.indexOf("please") < 0) {
					throw e;
				}
			}
		};
	};
}
FormManager.prototype.addClick = function(key, listener) {
	this._getElement_(key).addEventListener('click', this._bindedCreateFilter_(listener), false);
};
```

## createOptionFragment 関数
Javascript から Select 部品の選択肢を生成するために、`document.createDocumentFragment`関数を使うと DOM 的に効率的と思います。

```js
FormManager.prototype._createOptionFragment_ = function(nameList, selectValue, valueList) {
	if (selectValue == null) {
		selectValue = 0;
	}
	const fragment = document.createDocumentFragment();
	for (let i=0; i<nameList.length; i++) {
		const name = nameList[i];
		const value = (valueList != null) ? valueList[i] : name;
		const o = new Option(name, value);
		if (name === selectValue || value === selectValue || i === selectValue) {
			o.selected = true;
		}
		fragment.appendChild(o);
	}
	return fragment;
};
FormManager.prototype.createOptions = function(key, nameList, selectValue, valueList) {
	this._getElement_(key).appendChild(this._createOptionFragment_(nameList, selectValue, valueList));
};
```

## Float32Array polyfill
古いブラウザでサポートしていない関数を追加します。

```js
// for example
if (Float32Array.prototype.sort == null) {
	Float32Array.prototype.sort = function(comparator) {
		[].sort.call(this, comparator);
	};
}
```

## mat4 型を16個の数値として扱う
mat4 (4次元の配列)型を利用して、Javascript で事前に計算した16個の数値をまとめて glsl 側に渡すことができます。
mat4 型変数の各要素には const 制約の int 型変数を指定してアクセスすることができるので、可読性も損なわれません。
glsl 言語の実行環境は割り算の計算に負荷がかかると言われているので、それらの計算を Javascript で事前に行うのに使うことができます。

```js
// for example
const int MUL = 0, INV = 1, FUNCTION = 2, OTHER = 3;
const int MATRIX_WIDTH = 0, PIXEL_PER_VEC = 1, VEC_PER_WIDTH = 2, WORK_WIDTH = 3;
uniform mat4 env;
vec2 mat2Tex(vec2 fragCoord) {
	return fragCoord * env[INV][MATRIX_WIDTH];
}
```

## requestAnimationFrame 関数と while ブロック共用
ブラウザでトレーニングの停止機能を実現するには requestAnimationFrame 関数を使えば良いですが、使用頻度が高いとトレーニングの効率が落ちてしまいます。そこで requestAnimationFrame 関数と while ブロックを共用するようにしました。

```js
// for example
this.train = function(yieldCount) {
	let relatedIndex = 0;
	function step() {
		while (true) {
			// train execution
			relatedIndex++;
			if (relatedIndex % yieldCount === 0) {
				break;
			}
		}
		requestAnimationFrame(step);
	}
	step();
}
```

## 配列の値をネタにして別の配列をソートする
オブジェクトの特定の要素をネタにしてオブジェクトの配列をソートする例は他にありますが、ここでは uni2vec で適用した、配列の値をネタにして別の配列をソートするイディオムを紹介します。
idx2WeightArray は、インデックスが idx、値が重みを表している配列(Float32Array)です。重みの大きい順に idx のリストが欲しい場合、次のようにすると idxList に結果が得られます。

```js
// for example
	const idxList = [];
	/** @type {Float32Array} */
	let idx2WeightArray = null;
	function compare(idxA, idxB) {
		const v = idx2WeightArray[idxB] - idx2WeightArray[idxA];
		return (v > 0) ? 1 : (v < 0) ? -1 : 0;
	}
	function sort() {
		const idxLength = idxList.idxLength;
		for (let idx=0; idx<idxLength; idx++) {
			idxList[idx] = idx;
		}
		idxList.sort(compare);
	}
```

- 実装には以下を参照しました。
 - https://wgld.org/d/webgl/w040.html
 - https://turbo.github.io/
 - https://github.com/skeeto/igloojs

# 実装方針
- HTMLで機械学習プログラムを実装するためのリファレンスにしてほしかったため、以下の方針で実装しました。
 1. サードパーティのJavascriptライブラリを使用しないようにしました。
 1. テクスチャ座標、フレームバッファ座標、文字コード間の変換処理を共通関数化しました。
 1. シェーダソースでは、シェーダに負荷がかからないコーディングをしました(剰余に関する計算を小数の定数の掛け算による計算に置き換えた、forループ内の計算を少なくしたなど)。

# WebGLの考察と課題
- ブラウザベースなので、自由にアプリをインストールできない企業の従業員さんが容易にトライできるかもしれません。
- ブラウザベースなので、かつて流行したグリッドコンピューティングまたは分散コンピューティング(遊休PCのCPU時間をください)のGPU版が容易にできるかもしれません。

# 制限
- ライセンスはMITにしています。
- テクスチャの色情報にfloat32型を使用するため、OES_texture_floatをサポートするブラウザに限定しました。
- 現時点はGoogleサイトにhtmlファイルをホストしています(リポジトリで管理していません)。