機械学習における線形回帰モデルの勾配降下法学習
概要1
線形回帰モデルの学習方法の一つである勾配降下法gradient descentを使った方法を紹介する。
説明
データセットを$X = \left\{ \mathbf{x}_{i} \right\}_{i=1}^{N}$、ラベルセットを$Y = \left\{ y_{i} \right\}_{i=1}^{N}$としよう。そして、以下のような線形回帰モデルを仮定する。
$$ \hat{y} = \sum\limits_{j=0}^{n} w_{j}x_{j} = \mathbf{w}^{T} \mathbf{x} $$
この時、$\mathbf{x} = \begin{bmatrix} x_{0} & \dots & x_{n} \end{bmatrix}^{T}$と$\mathbf{w} = \begin{bmatrix} w_{0} & \dots & w_{n} \end{bmatrix}^{T}$である。勾配降下法とは、関数のグラディエントが関数値が最も多く増加する方向を意味することを利用した学習法である。損失関数$J$を以下のようにMSEとする。
$$ J(\mathbf{w}) = \dfrac{1}{2} \sum\limits_{i=1}^{N} (y_{i} - \mathbf{w}^{T}\mathbf{x}_{i})^{2} $$
前に定数$\frac{1}{2}$が付くのは、$J$を微分する時に$2$が飛び出るからであり、これを約分するためである。つまり$J$を最小化することも、$\frac{1}{2}J$を最小化することも同じだ。要するに、与えられた$X$と$Y$に対して、次のような最適解$\mathbf{w}_{\ast}$を見つけることが目標だ。
$$ \mathbf{w}_{\ast} = \argmin\limits_{\mathbf{w}} \left( J(\mathbf{w}) = \dfrac{1}{2} \sum\limits_{i=1}^{N} (y_{i} - \mathbf{w}^{T}\mathbf{x}_{i})^{2} \right) $$
表記法
数学、物理学、工学全般でスカラ関数のグラディエントを次のように表記する。
$$ \nabla J (\mathbf{w}) = \begin{bmatrix} \dfrac{\partial J(\mathbf{w})}{\partial w_{0}} & \dots & \dfrac{\partial J(\mathbf{w})}{\partial w_{n}} \end{bmatrix} $$
機械学習では、次のような表記もよく使われる。
$$ \dfrac{\partial J(\mathbf{w})}{\partial \mathbf{w}} = \begin{bmatrix} \dfrac{\partial J(\mathbf{w})}{\partial w_{0}} & \dots & \dfrac{\partial J(\mathbf{w})}{\partial w_{n}} \end{bmatrix} $$
つまり、$\nabla J = \dfrac{\partial J}{\partial \mathbf{w}}$である。この記事では、グラディエントの表記法として$\nabla J$を使うことにする。
アルゴリズム
グラディエントの性質により、$\nabla J$は$J$が最も大きく増加する方向を指す。その逆に、$-\nabla J$は$J$が減少する方向を指す。私たちの目標は$J$の関数値が減少することであるため、重み$\mathbf{w}$を$-\nabla J$の方向に移動させる。言い換えれば、次のように更新する。
$$ \mathbf{w} - \alpha \nabla J \to \mathbf{w} $$
この時、$\alpha$は学習率learning rateである。実際に$\nabla J$を計算すると次のようになる。$\mathbf{x}_{i} = \begin{bmatrix} x_{i0} & \dots & x_{in} \end{bmatrix}$としよう。$\dfrac{\partial \mathbf{w}^{T}\mathbf{x}_{i}}{\partial w_{j}} = \dfrac{\partial \sum_{k}w_{k}x_{ik}}{\partial w_{j}} = x_{ij}$なので、
$$ \begin{align*} \nabla J &= \begin{bmatrix} \dfrac{1}{2}\sum\limits_{i=1}^{N} \dfrac{\partial}{\partial w_{1}}(y_{i} - \mathbf{w}^{T}\mathbf{x}_{i})^{2} & \cdots & \dfrac{1}{2}\sum\limits_{i=1}^{N} \dfrac{\partial}{\partial w_{n}}(y_{i} - \mathbf{w}^{T}\mathbf{x}_{i})^{2} \end{bmatrix} \\ &= \begin{bmatrix} \sum\limits_{i=1}^{N} (y_{i} - \mathbf{w}^{T}\mathbf{x}_{i})x_{i0} & \cdots & \sum\limits_{i=1}^{N} (y_{i} - \mathbf{w}^{T}\mathbf{x}_{i})x_{in} \end{bmatrix} \\ &= \sum\limits_{i=1}^{N} (y_{i} - \mathbf{w}^{T}\mathbf{x}_{i}) \begin{bmatrix} x_{i0} & \cdots & x_{in} \end{bmatrix} \\ &= \sum\limits_{i=1}^{N} (y_{i} - \mathbf{w}^{T}\mathbf{x}_{i}) \mathbf{x}_{i} \end{align*} $$
したがって、具体的に$\mathbf{w}$を更新する式は次のようになる。
$$ \mathbf{w} - \alpha \sum\limits_{i}(y_{i} - \mathbf{w}^{T}\mathbf{x}_{i}) \mathbf{x}_{i} \to \mathbf{w} $$
これはウィドロー・ホフWidrow-HoffまたはLMSLeast Mean Squareアルゴリズムと呼ばれる。この式で、括弧内は誤差なので、誤差が大きいと$\mathbf{w}$が多く更新され、誤差が小さいと$\mathbf{w}$が少し更新されることがわかる。
更新方法2
重みを更新する方法には大きく分けて二つある。両方の方法は適切な学習率$\alpha$に対して、最適解に収束することが知られている。
バッチ学習
バッチ学習batch learningは、全データセット$X$の誤差に対して、一度に重みを修正することをいう。つまり、上で説明した通りである。
$$ \begin{align*} &\text{Repeat until convergence: }\\ &\quad \mathbf{w} - \alpha \sum\limits_{i}(y_{i} - \mathbf{w}^{T}\mathbf{x}_{i}) \mathbf{x}_{i} \to \mathbf{w} \end{align*} $$
オンライン学習
オンライン学習online learningは、各データ$\mathbf{x}_{i}$の誤差に対して、重みを修正することをいう。
$$ \begin{align*} &\text{Repeat until convergence: } \\ &\quad \text{For } i = 1 \text{ to } N: \\ &\qquad \mathbf{w} - \alpha (y_{i} - \mathbf{w}^{T}\mathbf{x}_{i}) \mathbf{x}_{i} \to \mathbf{w} \end{align*} $$