LoginSignup
0
0

More than 3 years have passed since last update.

@kazuya_minakuchi(Kazuya Minakuchi)

線形回帰・リッジ回帰・ラッソ回帰 -計算方法-

Last updated at Posted at 2020-04-19

線形回帰・リッジ回帰・ラッソ回帰を行う際の計算方法

線形回帰

yを予測するような$f(\mathbf{x})$を↓のように表し、できるだけ正確に予測できるよう$\mathbf{w}^t=(w_0, w_1, w_2, \cdots, w_d)$を求める

f(\mathbf{x}) = w_0 + w_1x_1 + w_2x_2 + \cdots + w_d x_d = w_0 + \sum_{i=1}^{d} w_i x_i = \mathbf{w}^t \mathbf{x}
  • $y$：目的変数。真の値。コレを予測したい。
  • $\mathbf{x}^t = (1, x_1, x_2, \cdots, x_d)$：説明変数。コレを使って$y$を予測したい。(最初の1は説明変数ではない。行列計算するために追加したもの)
    • この場合1つの説明変数はd次元
  • $f(\mathbf{x})$：予測値

↓こういうの
線形回帰.png

直線を引いたときに「予測と真の値の平均二乗誤差」

E = \sum (y - f(x))^2

が最小になるよう、パラメータ(係数)を求める。
ここで、教師データ($\mathbf{x}$、$y$の組み合わせ)がn個あり、

\mathbf{y} = 
\begin{pmatrix}
y_1 \\
y_2 \\
\vdots \\
y_n
\end{pmatrix}

\mathbf{X} = 
\begin{pmatrix}
{x_1}^t \\
{x_2}^t \\
\vdots \\
{x_n}^t
\end{pmatrix}

とすると。$E$は

\begin{align}
E(\mathbf{w}) &= \sum_{i=1}^{n}{(y_i - f(\mathbf{x_i}))^2} \\
&= \sum_{i=1}^{n}{(y_i - \mathbf{w}^t \mathbf{x_i})^2} \\
&= ||\mathbf{y} - \mathbf{X} \mathbf{w}||^2 \\
&= (\mathbf{y} - \mathbf{X} \mathbf{w})^t (\mathbf{y} - \mathbf{X} \mathbf{w}) \\
&= \mathbf{y}^t \mathbf{y} - \mathbf{w}^t \mathbf{X}^t \mathbf{y} - \mathbf{y}^t \mathbf{X} \mathbf{w} + \mathbf{w}^t \mathbf{X}^t \mathbf{X} \mathbf{w} \\
\end{align}

と表せる。コレを最小にするような$\mathbf{w}$は、Eの勾配

\nabla E(\mathbf{w}) = -2 \mathbf{X}^t \mathbf{y} + 2 \mathbf{X}^t \mathbf{X} \mathbf{w}

が0になる$\mathbf{w}$なので

\begin{align}
-2 \mathbf{X}^t \mathbf{y} + 2 \mathbf{X}^t \mathbf{X} \mathbf{w} &= 0 \\
\mathbf{w} &= (\mathbf{X}^t \mathbf{X})^{-1} \mathbf{X}^t \mathbf{y}
\end{align}

となる。

リッジ回帰

「(予測と真の値の平均二乗誤差)+(ハイパーパラメータ)×(パラメータのL2ノルム)」

E(\mathbf{w}) = \sum_{i=1}^{n}{(y_i - f(\mathbf{x_i}))^2} + \lambda \sum_{i=0}^{d} w_i^2

が最小になるよう、パラメータ(係数)を求める(=L2正則化)
このとき

\begin{align}
E(\mathbf{w}) &= ||\mathbf{y} - \mathbf{X} \mathbf{w}||^2 + \lambda ||\mathbf{w}||^2 \\
&= \mathbf{y}^t \mathbf{y} - \mathbf{w}^t \mathbf{X}^t \mathbf{y} - \mathbf{y}^t \mathbf{X} \mathbf{w} + \mathbf{w}^t \mathbf{X}^t \mathbf{X} \mathbf{w} + \lambda ||\mathbf{w}||^2 \\
\end{align}

となり、コレを最小にするような$\mathbf{w}$は、Eの勾配

\nabla E(\mathbf{w}) = -2 \mathbf{X}^t \mathbf{y} + 2 \mathbf{X}^t \mathbf{X} \mathbf{w} + 2 \lambda \mathbf{w}

が0になる$\mathbf{w}$なので

\begin{align}
-2 \mathbf{X}^t \mathbf{y} + 2 \mathbf{X}^t \mathbf{X} \mathbf{w} + 2 \lambda \mathbf{w} &= 0 \\
(\mathbf{X}^t \mathbf{X} + \lambda \mathbf{I}) \mathbf{w} &= \mathbf{X}^t \mathbf{y} \\
\mathbf{w} &= (\mathbf{X}^t \mathbf{X} + \lambda \mathbf{I})^{-1} \mathbf{X}^t \mathbf{y}
\end{align}

となる。

ラッソ回帰

「(予測と真の値の平均二乗誤差)+(ハイパーパラメータ×パラメータのL1ノルム)」が最小になるよう、パラメータ(係数)を求める。=L1正則化

\begin{align}
E(\mathbf{w}) &= \frac{1}{2} \sum_{i=1}^{n}{(y_i - f(\mathbf{x_i}))^2} + \lambda \sum_{i=1}^{d} |w_i| \\
&= \frac{1}{2} \sum_{i=1}^{n}{(y_i - w_0 - \sum_{j=1}^{d} w_j x_{ij})^2} + \lambda \sum_{i=1}^{d} |w_i| \\
&= \frac{1}{2} ||\mathbf{y} - \mathbf{X} \mathbf{w}||^2 + \lambda |\mathbf{w}|_1 \\
&= \mathbf{y}^t \mathbf{y} - \mathbf{w}^t \mathbf{X}^t \mathbf{y} - \mathbf{y}^t \mathbf{X} \mathbf{w} + \mathbf{w}^t \mathbf{X}^t \mathbf{X} \mathbf{w} + \lambda |\mathbf{w}|_1 \\
\end{align}

とおく。ラッソ回帰は$E(\mathbf{w})=0$となる解を手計算で求められないので、数値計算を行う。

数値計算(座標降下法:Coordinate Descent)

  • やりたいこと
    • $E(w_0, w_1, w_2, \cdots, w_d)$を最小にする$w_0, w_1, w_2, \cdots, w_d$を求める
  • 手順
    1. まず$w_0$を求める
    2. 次に、適当に$\mathbf{w}^{(0)} = (w_0, w_1^{(0)}, w_2^{(0)}, \cdots, w_d^{(0)})$の初期値を決める。(上付き文字は繰り返しの回数)
    3. $\mathbf{w}$がほとんど変化しなくなるまで↓を繰り返す。(要するに、$E$が最小になる$w$を一つずつ計算していく)
      1. $\frac{\partial E}{\partial w_1}(w_0, w_1, w_2^{(k)}, w_3^{(k)}, \cdots, w_d^{(k)}) = 0$になる$w_1$を求めて、それを$w_1^{(k+1)}$とする
      2. $\frac{\partial E}{\partial w_2}(w_0, w_1^{(k+1)}, w_2, w_3^{(k)}, \cdots, w_d^{(k)}) = 0$になる$w_2$を求めて、それを$w_2^{(k+1)}$とする
      3. $\cdots$
      4. $\frac{\partial E}{\partial w_d}(w_0, w_1^{(k+1)}, w_2^{(k+1)}, w_3^{(k+1)}, \cdots, w_d) = 0$になる$w_d$を求めて、それを$w_d^{(k+1)}$とする

座標降下法で使う数式

w0

$w_0$の計算方法

E(\mathbf{w}) = \frac{1}{2} \sum_{i=1}^{n}{(y_i - w_0 - \sum_{j=1}^{d} w_j x_{ij})^2} + \lambda \sum_{i=1}^{d} |w_i|

より

\begin{align}
\frac{\partial E}{\partial w_0} &= \frac{1}{2} \sum_{i=1}^{n} 2 (-1) (y_i - w_0 - \sum_{j=1}^{d} w_j x_{ij}) \\
&= - \sum_{i=1}^{n} (y_i - w_0 - \sum_{j=1}^{d} w_j x_{ij}) \\
&= - \sum_{i=1}^{n} (y_i - \sum_{j=1}^{d} w_j x_{ij}) + n w_0 \\
\end{align}

よって

\begin{align}
\frac{\partial E}{\partial w_0} &= - \sum_{i=1}^{n} (y_i - \sum_{j=1}^{d} w_j x_{ij}) + n w_0 = 0 \\
w_0 &= \frac{1}{n} \sum_{i=1}^{n} (y_i - \sum_{j=1}^{d} w_j x_{ij})
\end{align}

w0以外

$w_k (k \neq 0)$の計算方法

E(\mathbf{w}) = \frac{1}{2} \sum_{i=1}^{n}{(y_i - w_0 - \sum_{j=1}^{d} w_j x_{ij})^2} + \lambda \sum_{i=1}^{d} |w_i|

より

\begin{align}
\frac{\partial E}{\partial w_k} &= \frac{1}{2} \sum_{i=1}^{n} 2 (-x_{ik}) (y_i - w_0 - \sum_{j=1}^{d} w_j x_{ij}) + \lambda \frac{\partial |w_k|}{\partial w_k} \\
&= - \sum_{i=1}^{n} (y_i - w_0 - \sum_{j=1}^{d} w_j x_{ij}) x_{ik} + \lambda \frac{\partial |w_k|}{\partial w_k} \\
&= - \sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij} - w_k x_{ik}) x_{ik} + \lambda \frac{\partial |w_k|}{\partial w_k} \\
&= - \sum_{i=1}^{n} \bigl( (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} - w_k {x_{ik}}^2 \bigr) + \lambda \frac{\partial |w_k|}{\partial w_k} \\
&= - \sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} + \sum_{i=1}^{n} w_k {x_{ik}}^2 + \lambda \frac{\partial |w_k|}{\partial w_k} \\
\end{align}

よって$\frac{\partial E}{\partial w_k}=0$となる$w_k$は

\begin{align}
\frac{\partial E}{\partial w_k} &= - \sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} + \sum_{i=1}^{n} w_k {x_{ik}}^2 + \lambda \frac{\partial |w_k|}{\partial w_k} = 0 \\
\sum_{i=1}^{n} {x_{ik}}^2 w_k &=  \sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} - \lambda \frac{\partial |w_k|}{\partial w_k} \\
w_k & = \frac {\sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} - \lambda \frac{\partial |w_k|}{\partial w_k}} {\sum_{i=1}^{n} {x_{ik}}^2} \\
\end{align}

ここで

\frac{\partial |w_k|}{\partial w_k}  = \left\{
\begin{array}{ll}
1 & (w_k > 0) \\
-1 & (w_k < 0)
\end{array}
\right.

を代入すると

w_k = \left\{
\begin{array}{ll}
\dfrac {\sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} - \lambda} {\sum_{i=1}^{n} {x_{ik}}^2} & (w_k > 0) \\
\dfrac {\sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} + \lambda} {\sum_{i=1}^{n} {x_{ik}}^2} & (w_k < 0) \\
\end{array}
\right.

しかし、

\begin{align}
\sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} - \lambda < 0 \\
\sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} + \lambda > 0 \\
\end{align}

すなわち

- \lambda < \sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} < \lambda \\

のとき、「$w_k > 0$となるべきだが、$w_k < 0$」「$w_k < 0$となるべきだが、$w_k > 0$」となってしまうので、このときは$w_k = 0$とする。よって

w_k = \left\{
\begin{array}{ll}
\dfrac {\sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} - \lambda} {\sum_{i=1}^{n} {x_{ik}}^2} & (\lambda \leq \sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik}) \\
0 & (- \lambda < \sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} < \lambda) \\
\dfrac {\sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} + \lambda} {\sum_{i=1}^{n} {x_{ik}}^2} & (\sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} \leq - \lambda) \\
\end{array}
\right.

となる。ここで、

\mathbf{y} = 
\begin{pmatrix}
y_1 \\
\vdots \\
y_n
\end{pmatrix}

\mathbf{I} = 
\begin{pmatrix}
1 \\
\vdots \\
1
\end{pmatrix}

\mathbf{X} = 
\begin{pmatrix}
{x_1}^t \\
{x_2}^t \\
\vdots \\
{x_n}^t
\end{pmatrix}  = 
\begin{pmatrix}
x_{11} & \cdots & x_{1d} \\
\vdots &        & \vdots \\
x_{n1} & \cdots & x_{nd} \\
\end{pmatrix}

\mathbf{x'} = 
\begin{pmatrix}
x_{1k} \\
\vdots \\
x_{nk}
\end{pmatrix}

\mathbf{w_k'} = 
\begin{pmatrix}
w_1 \\
\vdots \\
0 \; (w_k = 0) \\
\vdots \\
w_d
\end{pmatrix}

とおくと、以下の行列計算でも表せる。

w_k = \left\{
\begin{array}{ll}
\dfrac {(\mathbf{y} - \mathbf{I} w_0 - \mathbf{X} \mathbf{w_k'})^t \mathbf{x'} - \lambda} {\mathbf{x'}^t \mathbf{x'}} & (\lambda \leq \sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik}) \\
0 & (- \lambda < \sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} < \lambda) \\
\dfrac {(\mathbf{y} - \mathbf{I} w_0 - \mathbf{X} \mathbf{w_k'})^t \mathbf{x'} + \lambda} {\mathbf{x'}^t \mathbf{x'}} & (\sum_{i=1}^{n} (y_i - w_0 - \sum_{j \neq k} w_j x_{ij}) x_{ik} \leq - \lambda) \\
\end{array}
\right.

図作ったときのコード置き場

参考

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0