2017-04-01

任意のバイナリを安全な文字で表す

base64やURIのパーセントエンコーディングなどに共通のアイデアが、「任意のバイナリを安全な文字で表す」ことである。

モチベーション

テキストエディタで画像などのバイナリファイルを開くとひどい表示になる。
これは、テキストエディタがファイルのバイト列を何らかの文字コードで解釈しようとして失敗しているためである。いわゆる文字化けのようなもの。

あらゆるバイト列をascii印字可能文字で表現できれば嬉しいかもしれない。
そうすれば文字化けは起きないし、クリップボードに保存できるし、例えば「HTMLにテキストで画像を埋め込む」という応用などができる。

バイト列とascii印字可能文字の相互変換の方式として様々なものが考えられている。
ここからは、バイト列をascii印字可能文字に変換することを「エンコード」と呼び、バイト列とascii印字可能文字に変換するルールを「エンコード方式」と呼ぶことにする。

冗長度

https://ja.wikipedia.org/wiki/ASCII
asciiの印字可能文字はアルファベット52種、数字10種、記号33種の計95種しかない。これは1バイト(=8ビット)での01の組み合わせ256通りを表現するには不十分である。
なので、1バイトを表現するために、ascii印字可能文字からなる2文字以上の文字列で表現せざるをえない。

一方、asciiコードのテキストファイルを保存すると、1文字が1バイトで保存される。
なので、元のバイト列をそのままファイルに保存するよりも、エンコードして保存するほうがサイズが大きくなる。
冗長度として、(エンコードしたときの文字数)/(元のバイト数)というものを定義できる。
エンコード方式としては、冗長度が小さい方が望ましい。

文字の安全度

個人的な感覚として、ascii印字可能文字の中でも、比較的安全度が高い文字と低い文字がある。(左ほど安全度が高い)
【数字・アルファベット】 > 【-_+.】 > 【!?#$%&@~^*:;=】 > 【()<>[]{}'"`|/,】 > 【\】 > 【半角スペース】

安全度の基準としては「shellのコマンドラインで特殊な意味を持つかどうか」「テキストベースのデータ表現方法(XMLなど)で特別な意味を持つかどうか」くらいの感覚である。

安全度の低い文字はできればエンコードに使いたくない。
例えば、HTMLにテキストで画像を埋め込むときに < > " (半角スペース) があるとエラーが起きそうで嫌である。
エンコード方式としては、安全度の高い文字のみを使う方が望ましい。

エンコード方式例

16進数

代表的なエンコード方式としては16進数がある。
これは0123456789abcdefの16文字を4ビットに割り当て、2文字で1バイトを表す方式で、バイナリとの相性が良い。

例: 38762cf7f55934b34d179ae6a4c80cadccbb7f0a (https://shattered.io/ より)

1バイトを表すのに2文字必要なので、冗長度は2になる。

バイナリとの相性が良いので、バイナリエディタの表示方式としても使われる。
http://forest.watch.impress.co.jp/library/software/binaryeditbz/
sha1のようなハッシュ値でも使われる。
http://ftp.riken.jp/Linux/centos/7/isos/x86_64/sha1sum.txt

2進数・4進数・8進数・32進数

2進数: バイト列をそのまま全て01で表示する方式。
1バイトを表現するのに8文字使うため、冗長度が8と非常に冗長。
デジタルであることを表すかっこいいイメージに使われる。
google:image:digital
あとは学習用くらいだろうか。

4進数: 0123の4文字を2ビットに割り当てる。
冗長度は8/2=4

8進数: 01234567の8文字を3ビットに割り当てる。
冗長度は8/3=2.666..

32進数:123456789abcdefghijklmnopqrstuvの32文字を5ビットに割り当てる。
冗長度は8/5=1.6
ポケモンの個体値で見ることがある。

64進数 (base64)

https://ja.wikipedia.org/wiki/Base64
アルファベット・数字A~Za~z0~9に記号+/を加えた64文字を使って6ビットを表現する。冗長度は8/6=1.333...
また、パディング用の文字として=も使う。

例: メールヘッダ
- Subject: =?ISO-2022-JP?B?GyRCJDMkcyRLJEEkTxsoQg==?=
- 中間の GyRCJDMkcyRLJEEkTxsoQg== の部分はISO-2022-JPの「こんにちは」(16バイト)をbase64 エンコードしている

記号+/を含むのが厄介で、例えばURLに/は使いたくない。
そのような問題を回避するため、記号部分を変更したbase64変種がいくつか提案されている。
例えばURLのためのbase64は、記号に+/ではなく-_を使い、さらにパディングがない。

パーセントエンコーディング

URLにおいてマルチバイト文字や記号を扱うための方法
パーセントエンコーディング - Wikipedia

例(wikipedia「A応P」の記事):
- https://ja.wikipedia.org/wiki/A%E5%BF%9CP
- "%E5%BF%9C"はutf-8の「応」(3バイト)をパーセントエンコーディングしている
- "A"と"P"はエンコードなし

基本は16進数で、%とその後の2文字(0123456789ABCDEFの16種)で1バイトを表す。
ただし、アルファベット・数字・一部のascii記号はエンコードしないまま表示できる。
パーセント(%)自身も%25でエンコードしなければならない。

冗長度は、アルファベットや数字のところでは1、それ以外のところでは3になる。

quoted-printable

https://ja.wikipedia.org/wiki/Quoted-printable
パーセントエンコーディングとほぼ同じ。
=とその後の2文字(0123456789ABCDEFの16種)で1バイトを表す。
ただし、アルファベット・数字・ascii印字可能文字はエンコードしないまま表示できる。
=自身はエンコードしなければならない。

メールで用いられることがある。

unsigned charの配列

0~255の数字の配列として書いてもいいかもしれない。

例:
- "[227,129,147,227,130,147,227,129,171,227,129,161,227,129,175]"
- utf8の「こんにちは」をJSONの数字配列として解釈可能な文字列にしている

冗長度はおよそ3.6

JavascriptのUint8Arrayで読み込める。
https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Uint8Array

用途

これまで書いてきたものも含む。

テキストベースのデータ構造で、エスケープを気にせず扱う

例えばtsvを作成するとき、データにタブ文字や改行があると、単にタブでjoinするだけでは正しいtsvにならず、tsv作成用のライブラリを使って適切にエスケープする必要がある。
読み込むときも同様で、タブでsplitするだけでは駄目で、tsv読み込み用のライブラリを使わなければならない。

「データは全てbase64に変換する」というルールを適用すると、データにタブ文字も改行も入らなくなり、タブでjoin・splitするだけでtsvの作成・読み込みができるようになる。
shellでsort,cutを行うときにも安心して行うことができる。

ただし、変換せずテキストとして読むことは不可能になるし、毎回base64のエンコード・デコードを気にするよりtsvライブラリを使うほうがマシであることが多い。
一応こんな選択肢もあるよ、くらいの認識にしておきたい。

2017-03-18

(自分用メモ) サンプリングのモチベーション

メトロポリス・ヘイスティングス法のようなサンプリングでやりたいことの自分なりの理解。正しさは保証しません。

問題設定

データ・確率モデルは固定
データxが与えられたとき、あるパラメータθの確率(密度) P(θ|x) の値を求めることはできる
θの定義域のありとあらゆる範囲でP(θ|x)を求めるのは計算コスト的に無理
- θが実数なら無限の計算が必要
解析的に積分をするのはたぶん無理

やりたいこと

θの分布のヒストグラムを描く
θがある範囲をとる確率を求める
- 積分の近似計算を行う
- サンプル点を大量にとったとき (ある範囲に入ったサンプル点の数) / (全部のサンプル点の数)でその確率を近似する

例

θを3次元の多項分布(θ1,θ2,θ3) とする。
0≦θ1≦1
0≦θ2≦1
0≦θ3≦1
θ1+θ2+θ3=1

このとき、 0.1≦θ1≦0.3, 0.3≦θ2≦0.5 となる確率を求めたいとする(θ3は自動で決まる)。
サンプリングを行い、十分に多くのサンプル点をとったとすると、θがその範囲に入る確率は
(その範囲に入ったサンプル点の数) / (全部のサンプル点の数)
で近似できる。

方法

適当なパラメータの初期値θcurrentを決める
A. θcurrentからランダムに少し動かしたパラメータθnewをとる
B. P(θcurrent|x)とP(θnew|x)の値を比べて、θcurrentを更新するかどうか決める。更新しない場合Aに戻る。
- P(θnew|x)の方が大きければθcurrentを更新
- P(θnew|x)の方が小さければ、適当な確率でθcurrentを更新。
C. θcurrentを更新: θcurrent←θnew
D. θcurrentをサンプル点として追加
E. Aに戻る
A~Eを繰り返すことで、θの本当の確率分布に近いサンプル点リストがいい感じに得られる

2017-03-10

(自分用メモ) 回帰とニューラルネット

(自分用メモ) 重回帰と勾配降下法 - gneioagineの日記の続き。正しさは保証しません。

勾配降下法では、D個の教師データに対して誤差関数の勾配を求めて重み $\mathbf{w}$ を更新した。
勾配:
$\mathrm{grad}_{\mathbf{w}}(E(\mathbf{w})) = (\frac{\partial E(\mathbf{w})}{\partial w_0},\,\frac{\partial E(\mathbf{w})}{\partial w_1},\,...,\,\frac{\partial E(\mathbf{w})}{\partial w_n})$
勾配の各次元(i):
$\frac{\partial E(\mathbf{w})}{\partial w_i} = 2 \Sigma_{d=1}^{D} x_{i(d)} (\mathbf{w} \cdot \mathbf{x}_{(d)}-y_{(d)})$
重み更新:
$\mathbf{w}_{new} \leftarrow \mathbf{w} - \alpha \mathrm{grad}_{\mathbf{w}}(E(\mathbf{w}))$

D個の教師データを全部読んで勾配を計算→重み更新
D個の教師データを全部読んで勾配を計算→重み更新
...
と繰り返す。

確率的勾配降下法では、1個データ読むごとに勾配を計算して重みを更新する。
1番目の教師データを読んで勾配を計算→重み更新→2番目の教師データを読んで勾配を計算→重み更新→...→D番目の教師データを読んで勾配を計算→重み更新
1番目の教師データを読んで勾配を計算→重み更新→2番目の教師データを読んで勾配を計算→重み更新→...→D番目の教師データを読んで勾配を計算→重み更新
...
という繰り返しになる。
d番目の教師データを読んだ時の勾配の各次元(i):
$\frac{\partial E(\mathbf{w})}{\partial w_i} = 2 (\mathbf{w} \cdot \mathbf{x}_{(d)}-y_{(d)})$
重み更新:
$\mathbf{w}_{new} \leftarrow \mathbf{w} - \alpha \mathrm{grad}_{\mathbf{w}}(E(\mathbf{w}))$

ここでの勾配の逆向きは誤差関数 $E(w_0,w_2,...,w_n) = \Sigma_{d=1}^{D} (\hat{y}_{(d)} - y_{(d)})^2$ を最小化する向きであるとは限らない。
とはいえ実用上ほぼ確実に誤差関数は減ってくれるし、非凸性にもある程度対処できるので、確率的勾配降下法はよく使われる。
以下では確率的勾配降下法を基本的に用いる。

ロジスティック回帰

二値分類問題では、教師データにおいて目的変数yが値が0または1をとる。
この場合、重回帰では都合が悪い。

例えば説明変数xが2次元として、以下のように教師データがあるとする。
$(y=1,\, (x_1,x_2)=(7,-3))$
$(y=1,\, (x_1,x_2)=(-4,15))$
$(y=1,\, (x_1,x_2)=(2,2))$
$(y=0,\, (x_1,x_2)=(2,0))$
$(y=0,\, (x_1,x_2)=(-6,2))$
これを重回帰で最適化してみる。
モデル: $\hat{y} = w_0+w_1x_1+w_2x_2$

最適な重み: $w_0=0.34,w_1=0.097,w_2=0.073$

データy	データx	予測値 $\hat{y}$
1	(7, -3)	$\hat{y} = 0.34+0.0977+0.073(-3)=0.8$
1	(-4, 15)	$\hat{y} = 1.047$
1	(2, 2)	$\hat{y} = 0.68$
0	(3, -1)	$\hat{y} = 0.558$
0	(-6, 2)	$\hat{y} = -0.096$

誤差関数 $E(\mathbf{w}) = 0.4652$
誤差がそれなりに大きいように思えるし、4番目のデータでは $\hat{y}$ は0より1に近くなるのであまり望ましくない。

問題の形式と重回帰モデルの相性が悪く、できれば予測値 $\hat{y}$ は0〜1をとってほしい。
そこで、以下のようなモデルを導入する。
$\hat{y} = \sigma (w_0+w_1x_1+w_2x_2 + ... + w_nx_n) = \sigma (\mathbf{w} \cdot \mathbf{x})$
ただし $\sigma$ はロジスティックシグモイド関数で、以下のように定義される(シグモイド関数とも呼ぶ)。
$\sigma(u) = \frac{1}{1+exp(-u)} = \frac{exp(u)}{exp(u)+1}$

シグモイド関数の性質は下記のようなもので、二値分類と相性が良い。

定義域が(-∞,∞)、値域が(0,1）で単調増加
u=0のとき $\sigma(0) = 0.5$
u<0で急速に0に近づく
u>0で急速に1に近づく

By Chrislb (created by Chrislb) [GFDL (http://www.gnu.org/copyleft/fdl.html) or CC-BY-SA-3.0 (http://creativecommons.org/licenses/by-sa/3.0/)], via Wikimedia Commons

このモデルで適切な重みwを推定するのがロジスティック回帰である。
学習した重みを使って分類する場合、 $\sigma (\mathbf{w} \cdot \mathbf{x}) > 0.5$ (⇒ $(\mathbf{w} \cdot \mathbf{x}) > 0$ )ならラベル1, そうでないならラベル0として分類する。

このモデルで、例えば重み: $w_0=-6,w_1=2,w_2=2$ として先ほどのデータで予測値を出してみる。

データy	データx	予測値 $\hat{y}$
1	(7, -3)	$\hat{y} = \sigma (-6+27+2(-3))=\frac{1}{1+exp(-2)}=0.88$
1	(-4, 15)	$\hat{y} = 0.99999989$
1	(2, 2)	$\hat{y} = 0.88$
0	(3, -1)	$\hat{y} = 0.12$
0	(-6, 2)	$\hat{y} = 0.00000083$

-
誤差がそれなりに小さくなったように思われる。4番目のデータも0に近くなった。
ちなみに、 $w_0=-12,w_1=4,w_2=4$ 、 $w_0=-18,w_1=6,w_2=6$ と $\mathbf{w}$ の要素の比を一定に保ったまま絶対値を大きくしていけば、各データで $\hat{y}$ とyの差を限りなく0に近づけることができる。
この場合、最適な $\mathbf{w}$ の値を一意に定めることは難しい。

ロジスティック回帰では誤差関数は以下の交差エントロピー関数を使うことが多い。
(誤差関数の適切な選び方は「一般化線形モデル」を学べば分かるかもしれない)
$E(\mathbf{w}) = \Sigma_{d=1}^{D} [ -y_{(d)}log(\hat{y}_{(d)}) - (1-y_{(d)})log(1-\hat{y}_{(d)}) ]$
各データについて、

教師データのy=1→ $-log(\hat{y})$ を加える。 $\hat{y}$ が0に近ければ大きく増えて、1に近ければほぼ増えない。
教師データのy=0→ $-log(1-\hat{y})$ を加える。 $\hat{y}$ が1に近ければ大きく増えて、0に近ければほぼ増えない。

回帰に必要な

モデル定義
教師データ
誤差関数の定義

が用意できたので、確率的勾配降下法で最適化していく。

以下では確率的勾配降下法を使うことを前提に、1個のデータについて考える。
$E(\mathbf{w}) = -ylog(\hat{y}) - (1-y)log(1-\hat{y}) = -ylog(\sigma(\mathbf{w} \cdot \mathbf{x})) - (1-y)log(1-\sigma(\mathbf{w} \cdot \mathbf{x}))$
まず、シグモイド関数の微分について以下が成り立つ。
$\frac{\partial \sigma(u)}{\partial u} = \frac{\partial}{\partial u} \frac{1}{1+exp(-u)} = \frac{exp(-u)}{(1+exp(-u))^2} = \sigma(u)(1-\sigma(u))$
これを使うと
$\frac{\partial E(\mathbf{w})}{\partial w_i} = (\hat{y}-y)x_i$
が導ける。

ニューラルネット

重回帰やロジスティック回帰でもうまくいかない回帰問題がある。
例えば説明変数xが2次元として、以下のようにデータがあるとする。
$(y=1,\, (x_1,x_2)=(1,1))$
$(y=1,\, (x_1,x_2)=(-1,-1))$
$(y=0,\, (x_1,x_2)=(-1,1))$
$(y=0,\, (x_1,x_2)=(1,-1))$

これをロジスティック回帰で上手く回帰するには、少なくとも以下の(1)(2)(3)(4)を満たすことが望ましい。
$w_0+w_1+w_2>0$ ... (1)
$w_0-w_1-w_2>0$ ... (2)
$w_0+w_1-w_2<0$ ... (3)
$w_0-w_1+w_2<0$ ... (4)
しかし、(1)(2)(3)(4)を同時に満たすことはないため、ロジスティック回帰ではうまくいかない。
((1)+(2)より $w_0>0$ , (3)+(4)より $w_0<0$ でなければならない)

そこで、天下り的に以下のモデルを導入する。
$u_1=w_0+w_1x_1+w_2x_2$ , $z_1=\sigma(u_1)$
$u_2=w_3+w_4x_1+w_5x_2$ , $z_2=\sigma(u_2)$
$u_3=w_6+w_7z_1+w_8z_2$ , $\hat{y}=\sigma(u_3)$
uやzを除去すると、以下のように表現できる。
$\hat{y} = \sigma( w_6 + w_7 \sigma(w_0+w_1x_1+w_2x_2) + w_8 \sigma(w_3+w_4x_1+w_5x_2) )$
この予測値 $\hat{y}$ も、重回帰やロジスティック回帰と同様重みwと説明変数xの関数である。

重みを天下り的に以下のように設定する。
$w_0=-18$
$w_1=10$
$w_2=10$

$w_3=-18$
$w_4=-10$
$w_5=-10$

$w_6=-5$
$w_7=10$
$w_8=10$
予測値を計算する。

データy	データx	予測値 $\hat{y}$
1	(1,1)	0.98
1	(-1,-1)	0.98
0	(-1,1)	0.0067
0	(1,-1)	0.0067

ということで、いい感じに予測ができる。

このモデルはニューラルネットの非常に簡単な例となっており、図として表すとよく見る感じのものになる。

このニューラルネットの解釈は以下のようになる。

$z_1$ は $x_1+x_2$ が1.8以上ならおよそ1、そうでないならおよそ0
$z_2$ は $x_1+x_2$ が-1.8以下ならおよそ1、そうでないならおよそ0
$\hat{y}$ は $z_1+z_2$ が0.5以上ならおよそ1、そうでないならおよそ0
(ここでは $z_1$ と $z_2$ のどちらかが1に近いならおよそ1と解釈してもよい)
以上より、 $x_1+x_2$ が1.8以上または-1.8以下なら予測値 $\hat{y}$ はおよそ1、そうでないならおよそ0

このように、前段の回帰モデルの出力を後段の回帰モデルの入力にするのがニューラルネットである。

誤差関数としてはロジスティック回帰と同様に交差エントロピー関数が使える。
$E(\mathbf{w}) = \Sigma_{d=1}^{D} [ -y_{(d)}log(\hat{y}_{(d)}) - (1-y_{(d)})log(1-\hat{y}_{(d)}) ]$

誤差逆伝播法

回帰に必要な

モデル定義
教師データ
誤差関数の定義

が用意できたので、いつもどおり確率的勾配降下法で最適化していく。

説明の都合上、先ほどのものよりもう一段増やしたニューラルネットを扱う。
$u_1=w_0+w_1x_1+w_2x_2$ , $z_1=\sigma(u_1)$
$u_2=w_3+w_4x_1+w_5x_2$ , $z_2=\sigma(u_2)$
$u_3=w_6+w_7z_1+w_8z_2$ , $z_3=\sigma(u_3)$
$u_4=w_9+w_{10}z_1+w_{11}z_2$ , $z_4=\sigma(u_4)$
$u_5=w_{12}+w_{13}z_3+w_{14}z_4$ , $\hat{y}=\sigma(u_5)$
$E(\mathbf{w}) = -y_{(d)}log(\hat{y}_{(d)}) - (1-y_{(d)})log(1-\hat{y}_{(d)})$

勾配 $\mathrm{grad}_{\mathbf{w}}(E(\mathbf{w}))$ の計算は力づくでやることも可能ではあるが、直感的には非常に大変そうである。
その勾配の計算に誤差逆伝播法というテクニックを使う。

まずは出力段への重みである $w_{12}$ $w_{13}$ $w_{14}$ で計算すると、ロジスティック回帰と同様に $\frac{\partial E(\mathbf{w})}{\partial w_{14}} = (y-\hat{y})z_{4}$ などとできる。

また、 $\frac{\partial E(\mathbf{w})}{\partial u_5}$ も後で利用するために求める。
$E(\mathbf{w}) = -ylog(\sigma(u_5)) - (1-y)log(1-\sigma(u_5))$ であることから、
$\frac{\partial E(\mathbf{w})}{\partial u_5} = y - \sigma(u_5)$

続いて、前の段への重みである $w_6$ 〜 $w_{11}$ の勾配を求めてみる。
$\frac{\partial E(\mathbf{w})}{\partial w_{11}}$
$\,\,\,\, = \frac{\partial E(\mathbf{w})}{\partial u_5} \frac{\partial u_5}{\partial u_4} \frac{\partial u_4}{\partial w_{11}}$
$\,\,\,\, = (y-\sigma(u_5)) z_2 \frac{\partial u_5}{\partial u_4}$
$\,\,\,\, = (y-\sigma(u_5)) z_2 \frac{\partial u_5}{\partial z_4} \frac{\partial z_4}{\partial u_4}$
$\,\,\,\, = (y-\sigma(u_5)) z_2 w_{14} \sigma(u_4)(1 - \sigma(u_4))$
などとなる。

また、後で必要となるため $\frac{\partial E(\mathbf{w})}{\partial u_3}$ 、 $\frac{\partial E(\mathbf{w})}{\partial u_4}$ も求めておく。
$\frac{\partial E(\mathbf{w})}{\partial u_4} = \frac{\partial E(\mathbf{w})}{\partial u_5} \frac{\partial u_5}{\partial u_4} = (y-\sigma(u_5)) w_{14} \sigma(u_4)(1 - \sigma(u_4))$
(上の $\frac{\partial E(\mathbf{w})}{\partial w_{11}}$ と似たような計算をする)

さらに前の段への重みである $w_0$ 〜 $w_5$ の勾配を求めてみる。
$\frac{\partial E(\mathbf{w})}{\partial w_5} = \frac{\partial E(\mathbf{w})}{\partial u_2} \frac{\partial u_2}{\partial w_5} = x_2 \frac{\partial E(\mathbf{w})}{\partial u_2}$
ここで、 $u_2$ が変化すると $u_3$ $u_4$ が変化することに注意する必要がある。
偏微分の連鎖公式( http://www.math.kobe-u.ac.jp/HOME/higuchi/h18kogi/sect4.pdf )によると、
$\frac{\partial E(\mathbf{w})}{\partial u_2} = \frac{\partial E(\mathbf{w})}{\partial u_3} \frac{\partial u_3}{\partial u_2} + \frac{\partial E(\mathbf{w})}{\partial u_4} \frac{\partial u_4}{\partial u_2}$
のように和の形にする必要がある。
そして、その $\frac{\partial E(\mathbf{w})}{\partial u_3}$ は、 $\frac{\partial E(\mathbf{w})}{\partial u_2}$ と同様に後段の情報を用いて計算ができる。
$\frac{\partial u_3}{\partial u_2}$ は、
$\frac{\partial u_3}{\partial u_2} = \frac{\partial u_3}{\partial z_2} \frac{\partial z_2}{\partial u_2} = w_8 \sigma(u_2)(1-\sigma(u_2))$
などと計算する。

誤差逆伝播法の一般的な方法を述べる。
$\delta_j$ を $\delta_j=\frac{\partial E(\mathbf{w})}{\partial u_j}$ として定義すると、
$\delta_j = \Sigma_{k \in NextLayer} (\delta_k \frac{\partial u_k}{\partial u_j})$
$\,\,\,\, = \Sigma_{k \in NextLayer} (\delta_k w_{jk} \sigma(u_j)(1-\sigma(u_j))$
として計算できる。( $w_{jk}$ は $u_j$ のノードと $u_k$ のノードを接続する重み)
このように、入力層に近い側のデルタは出力層に近い側のデルタに依存する。そのため、デルタは出力層の側から入力層へ向けて順々に計算していく必要がある。これをもって「逆伝播」と呼んでいる。
最初に出力層でデルタを計算するときは、教師データのyの値を用いることができる。

そして重みで誤差関数を偏微分した値は
$\frac{\partial E(\mathbf{w})}{\partial w_{jk}} = \frac{\partial E(\mathbf{w})}{\partial u_k} \frac{\partial u_k}{\partial w_{jk}} = \delta_k z_j$
となる。(ただし入力層ではzはxになる)

2017-03-04

(自分用メモ) 重回帰と勾配降下法

正しさは保証しません。

重回帰

n個の説明変数 $x_1,x_2,...,x_n$ によって目的変数yの予測をしたいとする。
予測モデルとして、 $x_i$ の重み付き線形和を採用してみる。
$\hat{y} = w_0+w_1x_1+w_2x_2 + ... + w_nx_n$
( $\hat{y}$ は目的変数yの予測値。 $w_0$ は説明変数に関わらず一定値のバイアス。)
このとき、適切な重み $w_0,w_1,w_2,...,w_n$ を教師データから推定したい。

教師データは目的変数と説明変数セットの組を複数個集めたものである。D個の教師データがあるとする。
$(y_{(1)}, (x_{1(1)}, x_{2(1)}, ..., x_{n(1)}))$
$(y_{$2$}, (x_{1(2)}, x_{2(2)}, ..., x_{n(2)}))$
...
$(y_{(D)}, (x_{1(D)}, x_{2(D)}, ..., x_{n(D)}))$

例えば説明変数が2個で、下記のように教師データとして4個のデータがあるとする。
$(y=-10,\, (x_1,x_2)=(2,5))$
$(y=-2,\, (x_1,x_2)=(3,3))$
$(y=12,\, (x_1,x_2)=(4,-1))$
$(y=-13,\, (x_1,x_2)=(-2,3))$

適当な重みwの値で予測値を出してみる。

データy	データx	重みA: $w_0=2,w_1=1,w_2=-2$	重みB: $w_0=0.5,w_1=2,w_2=-3$
10	(2, 5)	$\hat{y} = 2 + 12 + (-2)5 = -6$	$\hat{y} = 0.5 + 22 + (-3)5 = -10.5$
-2	(3, 3)	$\hat{y} = -1$	$\hat{y} = -2.5$
12	(4, -1)	$\hat{y} = 8$	$\hat{y} = 11.5$
-13	(-2, 3)	$\hat{y} = -6$	$\hat{y} = -12.5$

モデル: $\hat{y} = w_0+w_1x_1+w_2x_2$

教師データでのyの値と、重みA・重みBでの予測値は以下のようになっており、重みBのほうが良さそうに思える。
重みA: $w_0=2,w_1=1,w_2=-2$
重みB: $w_0=0.5,w_1=2,w_2=-3$

教師データのy	-10	-2	12	-13
重みAでの予測値 $\hat{y}$	-6	-1	8	-6
重みBでの予測値 $\hat{y}$	-10.5	-2.5	11.5	-12.5

実際に重みBの方が良いことを示すため、「良さ」の評価指標が欲しい。
直感的には、教師データでの $y$ と推定値 $\hat{y}$ の差が小さくなる重みが良いと思われる。
そこで誤差関数 $E(w_1,w_2,...,w_n)$ というものを以下のように定義する。
$E(w_0,w_2,...,w_n)$
$\,\,\,\, = \Sigma_{d=1}^{D} (\hat{y}_{(d)} - y_{(d)})^2$
$\,\,\,\, = \Sigma_{d=1}^{D} (w_0+w_1x_{1(d)}+w_2x_{2(d)} + ... + w_nx_{n(d)} - y_{(d)})^2$
(誤差関数の選び方には恣意性がある。差の絶対値の和など、二乗和以外のものもありうる。)
誤差関数の値が小さいほど良い重みであるとみなす。

実際に先ほどの重みで誤差関数の値を求めてみる。

教師データのy	-10	-2	12	-13
重みAでの $\hat{y}$	-6	-1	8	-6
重みBでの $\hat{y}$	-10.5	-2.5	11.5	-12.5

重みAのとき、
$E=(-6-(-10))^2+(-1-(-2))^2+(8-12)^2+(-6-(-13))^2=82$
重みBのとき、
$E=(-10.5-(-10))^2+(-2.5-(-2))^2+(11.5-12)^2+(-12.5-(-13))^2=1.0$
誤差関数の値が小さいので、重みBの方が良いとみなせる。

誤差関数を定義すれば、ありとあらゆるwの組み合わせの中で最も誤差関数の値が小さくなるwを「最適な」wとして定めることができる。
先ほどのデータでは、最適なwの値はおおよそ $w_0=0.22,w_1=2.2,w_2=-2.9$ である。
この重みでのyの予測値は(-9.88, -1.88, 11.92, -12.87)となり、誤差関数の値は
$E=(-9.88-(-10))^2+(-1.88-(-2))^2+(11.92-12)^2+(-12.88-(-13))^2=0.496$
として求められる。

回帰問題を設定する場合、以下が必要となる。

モデル定義(重回帰の場合 $\hat{y} = w_0+w_1x_1+w_2x_2 + ... + w_nx_n$ )
教師データ
誤差関数の定義(差の二乗和 $E(w_0,w_2,...,w_n) = \Sigma_{d=1}^{D} (\hat{y} - y)^2$ など)

これらを最適化ブラックボックスに入力すれば、誤差関数を最小化するいい感じの重みwを出力してくれる。

勾配降下法

ここからはベクトルを導入していくことにする。
$\mathbf{w}=(w_0,\,w_1,\,w_2,\,...,\,w_n)$
$\mathbf{x}=(1,\,x_1,\,x_2,\,...,\,x_n)$
とおくと、内積を用いて以下のように書ける。
$\hat{y} = w_0+w_1x_1+w_2x_2 + ... + w_nx_n$
$\hat{y} = \mathbf{w} \cdot \mathbf{x}$
誤差関数もベクトルを入力にできる。
$E(\mathbf{w})$

最適化ブラックボックスの中身を覗いてみる。やりたいことは、

モデル定義(重回帰の場合 $\hat{y} = \mathbf{w} \cdot \mathbf{x}$ )
教師データ
誤差関数の定義(差の二乗和 $E(\mathbf{w}) = \Sigma_{d=1}^{D} (\hat{y} - y)^2$ など)

が与えられたとき、誤差関数を最小化する $\mathbf{w}$ を求めることである。

$\mathbf{w}$ を少しずつ改善してく方針で考える。
すなわち、十分小さいn+1次元ベクトル $\mathbf{v}$ を用いて
$\mathbf{w}_{new} \leftarrow \mathbf{w} + \mathbf{v}$
$\mathbf{w}_{newnew} \leftarrow \mathbf{w}_{new} + \mathbf{v}_{new}$
と計算することを繰り返して、 $\mathbf{w}$ を改善する。
このとき、誤差関数が小さくなるように、 $E(\mathbf{w}_{new}) < E(\mathbf{w})$ を満たすようにする。

一回の更新において、誤差関数を最も小さくする $\mathbf{v}$ の向きは、誤差関数の勾配 $\mathrm{grad}_{\mathbf{w}}(E(\mathbf{w}))$ の逆向き( $-\mathrm{grad}_{\mathbf{w}}(E(\mathbf{w}))$ と同じ向き)であることが知られている。
ただし、 $\mathrm{grad}_{\mathbf{w}}(E(\mathbf{w}))$ はn+1次元のベクトルで、
$\mathrm{grad}_{\mathbf{w}}(E(\mathbf{w})) = (\frac{\partial E(\mathbf{w})}{\partial w_0},\,\frac{\partial E(\mathbf{w})}{\partial w_1},\,...,\,\frac{\partial E(\mathbf{w})}{\partial w_n})$
である。

重回帰での誤差関数の勾配を求めてみる。まずは3次元、データ2個で考える
$E(\mathbf{w})$
$\,\,\,\, = (w_0+w_1x_{1(1)}+w_2x_{2(1)} + w_3x_{3(1)} - y_{(1)})^2$
$\,\,\,\,\,\,\, + (w_0+w_1x_{1(2)}+w_2x_{2(2)} + w_3x_{3(2)} - y_{(2)})^2$

$w_1$ で偏微分するとき、関係があるのは $w_1$ を含む項だけで、その値は
$(x_{1(1)}^2w_{1}^2+2(w_0+w_2x_{2(1)}+w_3x_{3(1)}-y_{(1)})x_{1(1)}w_1)$
$+ (x_{1(2)}^2w_{1}^2+2(w_0+w_2x_{2(2)}+w_3x_{3(2)}-y_{(2)})x_{1(2)}w_1)$

となる。よって、
$\frac{\partial E(\mathbf{w})}{\partial w_1}$
$\,\,\,=2x_{1(1)}^2w_{1}+2(w_0+w_2x_{2(1)}+w_3x_{3(1)}-y_{(1)})x_{1(1)}$
$\,\,\,\,\,\,\,+2x_{1(2)}^2w_{1}+2(w_0+w_2x_{2(2)}+w_3x_{3(2)}-y_{(2)})x_{1(2)}$
$\,\,\,=2(w_0+w_1x_{1(1)}+w_2x_{2(1)}+w_3x_{3(1)}-y_{(1)})x_{1(1)$
$\,\,\,\,\,\,\,+2(w_0+w_1x_{1(2)}+w_2x_{2(2)}+w_3x_{3(2)}-y_{(2)})x_{1(2)}$
$\,\,\,=2x_{1(1)}(\mathbf{w} \cdot \mathbf{x}_{(1)}-y_{(1)})+2x_{1(2)}(\mathbf{w} \cdot \mathbf{x}_{(2)}-y_{(2)})$

一般に、D個のデータがあるとき、重み $w_i$ での誤差関数の偏微分は以下のようになる。( $x_{0(d)} = 1$ とする)
$\frac{\partial E(\mathbf{w})}{\partial w_i} = 2 \Sigma_{d=1}^{D} x_{i(d)} (\mathbf{w} \cdot \mathbf{x}_{(d)}-y_{(d)})$

これで勾配
$\mathrm{grad}_{\mathbf{w}}(E(\mathbf{w})) = (\frac{\partial E(\mathbf{w})}{\partial w_0},\,\frac{\partial E(\mathbf{w})}{\partial w_1},\,...,\,\frac{\partial E(\mathbf{w})}{\partial w_n})$
が求められる。
あとはこの勾配に適当な縮小の係数αをかけて、(0<α<<1)
$\mathbf{w}_{new} \leftarrow \mathbf{w} - \alpha \mathrm{grad}_{\mathbf{w}}(E(\mathbf{w}))$
とwを少しずつ更新していけば、誤差関数の値が小さいwが得られる。

- - - - -

誤差関数を最も小さくする $\mathbf{v}$ の向きが $-\mathrm{grad}_{\mathbf{w}}(E(\mathbf{w}))$ と同じ向きであることを軽く検証する。
一回の更新において $\mathbf{v}$ の大きさは一定で、向きは自由に変更できるとする。

多変数関数のテーラー展開によると
http://eman-physics.net/math/taylor_multi.html
$E(w_0+v_0, w_1+v_1, ...,w_n+v_n)=$
$\,\,\,\,E(w_0, w_1, ...,w_n)$
$\,\,\,\, + (v_0(\frac{\partial}{\partial w_0})+v_1(\frac{\partial}{\partial w_1})+...+v_n(\frac{\partial}{\partial w_n}))E(w_0, w_1,...,w_n)$
$\,\,\,\, + (1/2)(v_0(\frac{\partial}{\partial w_0})+v_1(\frac{\partial}{\partial w_1})+...+v_n(\frac{\partial}{\partial w_n}))^2E(w_0+\theta v_0, w_1+\theta v_1,...,w_n+\theta v_n)$
らしい。( $0<\theta<1$ )

多変数関数の引数をベクトルとして扱うと、
$E(w_0+v_0, w_1+v_1, ...,w_n+v_n)=E(\mathbf{w}_{new})$
$E(w_0, w_1, ...,w_n)=E(\mathbf{w})$
であることから、
$E(\mathbf{w}_{new}) - E(\mathbf{w}) =$
$\,\,\,\, (v_0(\frac{\partial}{\partial w_0})+v_1(\frac{\partial}{\partial w_1})+...+v_n(\frac{\partial}{\partial w_n}))E(\mathbf{w})$
$\,\,\,\, + (1/2)(v_0(\frac{\partial}{\partial w_0})+v_1(\frac{\partial}{\partial w_1})+...+v_n(\frac{\partial}{\partial w_n}))^2E(w_0+\theta v_0, w_1+\theta v_1,...,w_n+\theta v_n)$

ここで、 $\mathbf{v}$ は十分小さいとしているので、 $\mathbf{v}$ の要素同士の掛け算を含む二次の項は無視してよい。よって、
$E(\mathbf{w}_{new}) - E(\mathbf{w})$
$\,\,\,\, \simeq (v_0(\frac{\partial}{\partial w_0})+v_1(\frac{\partial}{\partial w_1})+...+v_n(\frac{\partial}{\partial w_n}))E(\mathbf{w})$
$\,\,\,\,=(v_0(\frac{\partial E(\mathbf{w}) }{\partial w_0})+v_1(\frac{\partial E(\mathbf{w})}{\partial w_1})+...+v_n(\frac{\partial E(\mathbf{w})}{\partial w_n}))$
$\,\,\,\,=\mathbf{v} \cdot (\frac{\partial E(\mathbf{w})}{\partial w_0},\,\frac{\partial E(\mathbf{w})}{\partial w_1},\,...,\,\frac{\partial E(\mathbf{w})}{\partial w_n})$
$\,\,\,\,=\mathbf{v} \cdot \mathrm{grad}_{\mathbf{w}}(E(\mathbf{w}))$

$\mathbf{v}$ を適切な向きにすることで、 $E(\mathbf{w}_{new}) - E(\mathbf{w})$ を最小にしたい。(絶対値が最大の負の値にする)。
$\mathbf{v} \cdot \mathrm{grad}_{\mathbf{w}}(E(\mathbf{w}))$ の内積を最小化するような $\mathbf{v}$ の向きを求める。
ここで、 $\mathbf{v}$ の大きさは一定だと仮定しており、 $\mathrm{grad}_{\mathbf{w}}(E(\mathbf{w}))$ は $\mathbf{v}$ に依存しない。
2つのベクトルの大きさが一定であるとき、内積が最も小さくなるのはそれらのベクトルが逆向きのときである。
なので、 $\mathbf{v}$ は $-\mathrm{grad}_{\mathbf{w}}(E(\mathbf{w}))$ と同じ向きにすればよい。
そのときコサインが-1で、内積の値は $-|\mathbf{v}||\mathrm{grad}_{\mathbf{w}}(E(\mathbf{w}))|$ である。

2017-02-20

萌え豚の俺に突き刺さった漫画

寄宿学校のジュリエット
 http://www.shonenmagazine.com/bmaga/juliet
正統派で高品質なラブコメ。絵がすごく可愛い。

怪滅王と12人の星の巫女
http://comic-walker.com/contents/detail/KDCW_AM05000036010000_68/
分かりやすい異能バトル+ハーレム。シスターがとてもよい。

うちの娘の為ならば、俺はもしかしたら魔王も倒せるかもしれない。
http://comic-walker.com/contents/detail/KDCW_MF00000025010000_68/
神幼女漫画と一瞬話題になったやつ。ロリの描写が本気。

あやかしこ
http://seiga.nicovideo.jp/comic/22861
ツヤツヤな黒髪ロング好き。

ふつうの恋子ちゃん
http://www.s-manga.net/book/978-4-08-845554-9.html
「ツンデレチョロインな主人公の脳内が読める」という贅沢な体験ができる。表情を変えないまま赤面するのがとてもよい。

愛しの花凛
http://www.dokidokivisual.com/comics/book/index.php?cid=848
絵が可憐すぎる。全力で童貞を殺しにかかっている。

東方鈴奈庵
 http://comic-walker.com/contents/detail/KDCW_KS04000010010000_68/
東方厨だから仕方ない。霊夢のよさに改めて気づいた。

東京★イノセント
http://www.square-enix.co.jp/magazine/tachiyomi/tokyoinnocent/Contents/#
昔好きだったラブコメ。古風で不器用な雪代千歳ちゃんに当時心を奪われた。

2017-02-11

ここ最近で感情を揺さぶられたエモ作品集

おはよう、いばら姫 (少女漫画)
https://www.amazon.co.jp/exec/obidos/ASIN/4063658139/
ほとんど家から出たことのない黒髪ロングのお嬢様に弱い。

月曜日は2限から (少年漫画)
https://www.amazon.co.jp/exec/obidos/ASIN/4091243983/
校則を破ってちょっと悪いことをするドキドキ感に弱い。

青春のアフター (青年漫画)
https://www.amazon.co.jp/exec/obidos/ASIN/4575846627/
思春期の青い思いを大人になっても引きずったままな人に弱い。

コトコノコトノハ (青年漫画)
https://www.amazon.co.jp/exec/obidos/ASIN/425314201X/
何を考えてるのか分からない女の子に振り回されるシチュエーションに弱い。

【Novelsm@ster】渋谷凛「雨に唄えば」 (ビジュアルノベル)
http://www.nicovideo.jp/watch/sm17934547
鬱屈とした子が救済される話に弱い。

お嬢さま三姉妹にぺろぺろされ続けるのをやめたい人生だった (18禁ノベル)
https://www.amazon.co.jp/exec/obidos/ASIN/479640614X/
ただただ主人公とヒロインの心情・関係性にのみスポットを当てた文章に弱い。

下僕の俺が盲目の超わがままお嬢さまの性奴隷な件 (18禁ノベル)
http://novel18.syosetu.com/n7126cq/
まっとうに青春している純愛話に弱い。

- - -

基本的に黒髪ロングとお嬢様に弱い。

2017-02-07

もう「強い能力を持っているが平穏に暮らしたいと思っている女の子が主人公のほのぼの異世界ライフ」であるなろう小説しか読みたくない

(多少ネタバレあり)
タイトルに挙げたジャンルの作品を最近よく読んでいる。試しに読んでいるのをざっと挙げてみる。

タイトル	転生・転移	主人公	能力
http://ncode.syosetu.com/n6475db/	転生	18才学生→10才学生・冒険者	世界最強の古竜のおよそ半分の魔力など
http://ncode.syosetu.com/n1159db/	転生	社会人→18才令嬢・カフェ経営	気難しい幻獣と契約する・悪魔を封印するなど
http://ncode.syosetu.com/n4483dj/	転生	社畜→300才魔女(見た目は17才)	レベルMAX(99)
http://ncode.syosetu.com/n8139dg/	転移	20代社畜→聖女？	聖属性魔法：Lv∞
http://ncode.syosetu.com/n0537cm/	転移	17才学生→冒険者	邪神基準で平均的な能力
http://ncode.syosetu.com/n4185ci/	転移	15才引きこもり→冒険者	強力なクマ装備・クマ魔法・クマ召喚
http://ncode.syosetu.com/n1583dj/	なし(ファンタジー世界)	9才学生	魔法適性9999
http://ncode.syosetu.com/n2532de/	なし(ファンタジー世界)	600年封印されていた魔王	死霊を操り、かつては大陸全土を席巻していた
http://ncode.syosetu.com/n5693dn/	なし(現代)	15才学生・退魔業	超強い式神の力を借りて禍霊退治

異世界じゃないのも混じってるがキニシナイ。
このジャンル、読んでるとすごい癒されて幸せになるのでもっともっと増えてほしい。