📂機械学習

머신러닝에서 선형회귀모델의 최소제곱법 학습

概要¹

線形回帰モデルの学習方法の一つである最小二乗法^{least squares}を用いた方法を紹介する。

説明

データ集合を$X = \left\{ \mathbf{x}_{i} \right\}_{i=1}^{N}$、ラベル集合を$Y = \left\{ y_{i} \right\}_{i=1}^{N}$とする。そして次のような線形回帰モデルを仮定しよう。

$$\hat{y} = \sum\limits_{j=0}^{n-1} w_{j}x_{j} = \mathbf{w}^{T} \mathbf{x}$$

このとき$\mathbf{x} = \begin{bmatrix} x_{0} & \dots & x_{n-1} \end{bmatrix}^{T}$、$\mathbf{w} = \begin{bmatrix} w_{0} & \dots & w_{n-1} \end{bmatrix}^{T}$である。最小二乗法とは、モデルの予測値$\hat{y}_{i} = \mathbf{w}^{T} \mathbf{x}_{i}$と実際の正解であるラベル$y_{i}$との誤差の二乗を最小化することによってモデルを学習させる方法だ。すなわち損失関数$J$を次のようにMSEとする。

$$J(\mathbf{w}) = \dfrac{1}{2} \sum\limits_{i=1}^{N} (y_{i} - \mathbf{w}^{T}\mathbf{x}_{i})^{2} = \dfrac{1}{2} \left\| \mathbf{y} - \mathbf{X}\mathbf{w} \right\|^{2}$$

このとき$\mathbf{y} = \begin{bmatrix} y_{1} & \dots & y_{N} \end{bmatrix}^{T}$、$\mathbf{X} = \begin{bmatrix} \mathbf{x}_{1} & \dots & \mathbf{x}_{N} \end{bmatrix}^{T}$である。すると$\mathbf{X}\mathbf{w}$は次のようになる。

$$\mathbf{X}\mathbf{w} = \begin{bmatrix} \mathbf{x}_{1}^{T} \mathbf{w} \\ \vdots \\ \mathbf{x}_{N}^{T} \mathbf{w} \end{bmatrix}$$

先頭の定数$\frac{1}{2}$がつく理由は、$J$を微分する際に$2$が現れるが、これを約分するためだ。どうせ$J$を最小化するのも、$\frac{1}{2}J$を最小化するのも同じだからだ。つまり、目的は与えられた$X$と$Y$について、次のような最小二乗解$\mathbf{w}_{\text{LS}}$を見つけることだ。

$$\mathbf{w}_{\text{LS}} = \argmin\limits_{\mathbf{w}} \left( J(\mathbf{w}) = \dfrac{1}{2} \left\| \mathbf{y} - \mathbf{X}\mathbf{w} \right\|^{2} \right)$$

勾配降下法を用いた学習では反復的な^{iterative approach}アルゴリズムを通じて重みを最適解に収束させるのに対して、ここで紹介する方法は解析的に一発で最適解を見つける方法^{one-shot approach}を紹介する。

学習

場合1: 正確で唯一の解が存在

データの数$N$、重みの次元$n$、および$\mathbf{X}$のランクがすべて等しいとしよう。つまり$\mathbf{X}$がフルランク^{full rank}の場合だ。

$$N = n = \rank (\mathbf{X})$$

上記の状況で、$\mathbf{X}$は$N \times N$の正方行列で、ランクが$N$であるため逆行列を持つ。したがって、連立方程式$\mathbf{y} = \mathbf{X} \mathbf{w}$は次のように唯一の解を持つ。

$$\mathbf{w} = \mathbf{X}^{-1}\mathbf{y}$$

上記のような重み$\mathbf{w}$に対して、損失関数の関数値は$0$である。

$$J(\mathbf{X}^{-1}\mathbf{y}) = \dfrac{1}{2} \left\| \mathbf{y} - \mathbf{X}\mathbf{X}^{-1}\mathbf{y}\right\|^{2} = 0$$

これにより、勾配降下法などを用いずに一発で最適な重みを見つけることができるが、実際の状況ではこのような仮定はほとんど成立しない。つまり理想的な場合と言える。

---

場合2: フルランクと過剰決定

データの数$N$と重みの次元$n$、および$\rank (\mathbf{X})$について次のようにしよう。実際には多くの場合でこの仮定が満たされる。

$$N \gt n = \rank (\mathbf{X})$$

線形システム$\mathbf{X} \mathbf{w} = \mathbf{y}$が過剰決定である場合、最小二乗問題の解が無数に存在する。まず$J$を展開して計算するとベクトルのノルムは、

$$\begin{align*} J(\mathbf{w}) &= \dfrac{1}{2} \left\| \mathbf{y} - \mathbf{X}\mathbf{X}^{-1}\mathbf{y}\right\|^{2} = \dfrac{1}{2} \left( \mathbf{y} - \mathbf{X}\mathbf{w} \right)^{T} \left( \mathbf{y} - \mathbf{X}\mathbf{w} \right) \\ &= \dfrac{1}{2} \left( \mathbf{y}^{T} - \mathbf{w}^{T}\mathbf{X}^{T} \right) \left( \mathbf{y} - \mathbf{X}\mathbf{w} \right) \\ &= \dfrac{1}{2} \left( \mathbf{y}^{T}\mathbf{y} - \mathbf{y}^{T}\mathbf{X}\mathbf{w} - \mathbf{w}^{T}\mathbf{X}^{T}\mathbf{y} + \mathbf{w}^{T}\mathbf{X}^{T}\mathbf{X}\mathbf{w} \right) \end{align*}$$

このとき$\mathbf{w}^{T}\mathbf{X}^{T}\mathbf{y}$はスカラーなので、

$$\mathbf{w}^{T}\mathbf{X}^{T}\mathbf{y} = (\mathbf{w}^{T}\mathbf{X}^{T}\mathbf{y})^{T} = \mathbf{y}^{T}\mathbf{X}\mathbf{w}$$

したがって次を得る。

$$J(\mathbf{w}) = \dfrac{1}{2} \left( \mathbf{y}^{T}\mathbf{y} - 2\mathbf{y}^{T}\mathbf{X}\mathbf{w} + \mathbf{w}^{T}\mathbf{X}^{T}\mathbf{X}\mathbf{w} \right)$$

数学式でベクトルと行列しか見えないが、上の値はスカラーである。混乱しないように注意しよう。この値が最小になるときを見つけるために勾配を計算すると、

$$\begin{align*} \nabla J(\mathbf{w}) = \dfrac{\partial J(\mathbf{w})}{\partial \mathbf{w}} &= \dfrac{1}{2} \dfrac{\partial }{\partial \mathbf{w}}\left( \mathbf{y}^{T}\mathbf{y} - 2\mathbf{y}^{T}\mathbf{X}\mathbf{w} + \mathbf{w}^{T}\mathbf{X}^{T}\mathbf{X}\mathbf{w} \right) \\ &= \dfrac{1}{2} \left( -2\mathbf{X}^{T}\mathbf{y} + 2\mathbf{X}^{T}\mathbf{X}\mathbf{w} \right) \\ &= \mathbf{X}^{T}\mathbf{X}\mathbf{w} - \mathbf{X}^{T}\mathbf{y} \end{align*}$$

微分計算の結果はここを参照しよう。すると次の式を得る。

$$\nabla J = \mathbf{0} \implies \mathbf{X}^{T}\mathbf{X}\mathbf{w} = \mathbf{X}^{T}\mathbf{y}$$

ここで式$\mathbf{X}^{T}\mathbf{X}\mathbf{w} = \mathbf{X}^{T}\mathbf{y}$を正規方程式^{normal equation}と言う。フルランクの場合、この問題は唯一のソリューションを持つ。$\mathbf{X}^{T} \mathbf{X}$は$n\times n$行列で、$\mathbf{X}$と同じランクを持つ。

$$\rank (\mathbf{X}^{T} \mathbf{X}) = n$$

したがって逆行列が存在し、次のような最小二乗解を得る。

$$\mathbf{w} = (\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{X}^{T}\mathbf{y}$$

---

場合3: フルランクと不足決定

データの数$N$と重みの次元$n$、および$\rank (\mathbf{X})$について次のようにしよう。

$$n \gt N = \rank (\mathbf{X})$$

すると連立方程式$\mathbf{X}\mathbf{w} = \mathbf{y}$は不足決定系である。この場合も場合2と同様に唯一の最小二乗解が存在せず、無数にある。解が無数にあるので、その中でもノルムが最小の$\mathbf{w}$を求めることを目標としよう。

$$\argmin\limits_{\mathbf{w}} \dfrac{1}{2} \left\| \mathbf{w} \right\|^{2}$$

この問題の解法をラグランジュ乗数法でアプローチしよう。すると、我々が持っている制約条件$\mathbf{y} - \mathbf{X}\mathbf{w}$に乗数$\boldsymbol{\lambda} = \begin{bmatrix} \lambda_{1} & \dots & \lambda_{N} \end{bmatrix}^{T}$を掛けたものを足して、次のような関数を最小化する問題となる。

$$L(\mathbf{w}, \boldsymbol{\lambda}) = \dfrac{1}{2} \left\| \mathbf{w} \right\|^{2} + \boldsymbol{\lambda}^{T}(\mathbf{y} - \mathbf{X}\mathbf{w})$$

$L$の勾配は次のようになる。微分計算はここを参照しよう。

$$\nabla L = \dfrac{\partial L}{\partial \mathbf{w}} = \mathbf{w} - \mathbf{X}^{T}\boldsymbol{\lambda}$$

したがって微分して$\mathbf{0}$となる重みは$\mathbf{w} = \mathbf{X}^{T}\boldsymbol{\lambda}$である。すると次の式を得る。

$$\mathbf{y} = \mathbf{X}\mathbf{w} = \mathbf{X}\mathbf{X}^{T}\boldsymbol{\lambda}$$

したがって$\boldsymbol{\lambda} = (\mathbf{X}\mathbf{X}^{T})^{-1}\mathbf{y}$であり、我々が求めるソリューションは次のとおりだ。

$$\mathbf{w} = \mathbf{X}^{T}(\mathbf{X}\mathbf{X}^{T})^{-1}\mathbf{y}$$

---

場合4: ランクディフィシェント

ランクディフィシェントであると仮定しよう。

$$\text{overdetermined: }N \gt n \gt \rank(\mathbf{X}) \\ \text{underdetermined: } n \gt N \gt \rank(\mathbf{X})$$

この場合も同様に最小二乗解は唯一でなく無数に存在する。また、$\mathbf{X}$がフルランクでないため、$\mathbf{X}^{T}\mathbf{X}$の逆行列は存在しない。したがって場合2や場合3のようには解けない。