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

正しさは保証しません。

重回帰

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}))|$ である。