4
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

ラッソ回帰を実装してみよう

Posted at

#まえがき
ラッソ回帰についてまとめます。一応前回までの記事を読んでいる前提で書いています。

ラッソ回帰

ラッソ回帰において最小化する二乗誤差は以下の式で表されます。

E(\mathbf{w}) = ||\mathbf{y} - \mathbf{\tilde{X}\mathbf{w}}||^2 + \lambda ||w ||_1 

ここで$|w|_1$は正則化項で、$|w|_1= \sum ^d _{i=1} |w _{i}|$です。
要するにwの各値の合計。二乗ではなく1乗で合計する。プラマイゼロになっちゃ困るので、それぞれ絶対値をとっています。
#ラッソ回帰を計算する上での致命的な問題
ラッソ回帰を解くためのアルゴリズムはいくつかありますが、今回は座標降下法で計算してみましょう。
簡単に言えば

  • 変数を一つ選んで偏微分係数を0になる値に合わせる。
  • さらにもう一つ変数を選び、偏微分係数が0になる値に合わせる。
  • 同じ工程を全変数に対して行う。

そこまでを一周として、学習が収束するまで何周も繰り返す方法です。

さて、この式の問題点は、今回の$E(w)$は「微分不可能である」という点です。絶対値が入っていると関数が連続にならないためです。ならば場合分けしなければいけない。

数式を書いてみましょう

まず、$w_0$で微分してみましょう。これは絶対値が含まれていないため、普通に偏微分して$w_0$を求めることができます。

\frac{\partial E}{\partial w_0} = -\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})

これが=0になるので、$w_0$について整理して

w_0 = {1\over n}\sum^n _ {i = 1}(y_i - \sum^d _ {j = 1}x_{ij}w_{j})

と求まりました。
$w_1$以降が厄介です。絶対値の微分を確認しましょう。

d^+(|x|) = 1\\
d^-(|x|) =-1

このように0の左側と右側で分かれます。
同様にE(w)を$w_k (k \neq 0)$で微分すると以下のように分かれます。

\frac{\partial E}{\partial w_k} =
\begin{cases}
 -\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik} + \lambda & (w_k > 0)\\
 -\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik} - \lambda
& (w_k < 0)
\end{cases}

どちらも=0として整理すると

w_k = \begin{cases}
{{\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik} - \lambda} \over {\sum^n _{i = 1}x^2_{ik}w_k}} & (w_k > 0)\\
{{\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik} + \lambda} \over {\sum^n _{i = 1}x^2_{ik}w_k}} & (w_k < 0)

\end{cases}

と求まりました。
ただし、これは$w_k$の条件を正しく満たす必要があります。上の式の条件を満たさない場合は$w_k = 0$となります。
書き直してみます。

w_k = \begin{cases}
{{\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik} - \lambda} \over {\sum^n _{i = 1}x^2_{ik}w_k}} & ({\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik}  } > \lambda)\\
0 & (\lambda < {\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik}  } < \lambda)\\
{{\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik} + \lambda} \over {\sum^n _{i = 1}x^2_{ik}w_k}} & (\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik} < - \lambda)

\end{cases}

$w_k = 0$というのは、その要素は計算に含めないほうがいい、という意味です。実際に計算を行うとほとんどの要素が0になったりするので疎行列の扱いを覚えた方がいいようです。
後で計算を楽にするために以下のような工夫をしましょう。

w_k = {{S({\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik}} , \lambda) } \over {\sum^n _{i = 1}x^2_{ik}w_k}}

という関数$S$に置き換えて(ソフト閾値関数といいます)表すと、

{S({\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik}} , \lambda) }\\ = \begin{cases}
{{\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik} - \lambda} } & ({\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik}  } > \lambda)\\
0 & (-\lambda < ({\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik}  } < \lambda )\\
{{\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik} + \lambda} } & (\sum^n_{i=1}(y_i - w_0 - \sum^d_{j = 1}x_{ij}w_{j})x_{ik} < - \lambda)
\end{cases} 

という風に整理できました。このSをsoft_thresholdingという名前で実装します。

実装してみよう

今回サンプルとして扱うデータは以下のサイトから利用します。
https://archive.ics.uci.edu/ml/machine-learning-databases/wine-quality/
ここから winequality-red.csvというファイルをダウンロードして、同じディレクトリに入れました。このデータはワインの各種ステータスとその品質を比較することができます。

まずこのcsvファイルを読み込んでみましょう。
以下のように記述します。

import numpy as np
import csv

Xy = []
with open("winequality-red.csv") as fp:
    for row in csv.reader(fp, delimiter=";"):
        Xy.append(row)
Xy = np.array(Xy[1:], dtype=np.float64)

こういうデータが
rapture_20190313122428.jpg
こういうデータになりました。
rapture_20190313122440.jpg
訓練用のデータとテスト用のデータに分けます。

np.random.seed(0)
np.random.shuffle(Xy)
train_X = Xy[:-1000, :-1] # 1件を除いて訓練用のデータに格納する。
train_y = Xy[:-1000, -1] # 訓練データの品質一覧。
test_X = Xy[-1000, :-1] # テストデータ(1件)のパラメータ。これを使って品質を計算する。
test_y = Xy[-1000, -1] # テストデータの品質(1件)。これを当てられたらOK。

あとは処理を入力します。

def soft_thresholding (x, y):
    return np.sign(x) * max(abs(x) - y, 0)

class Lasso:
    def __init__(self, lambda_, tol = 0.0001, max_iter = 10000):
        self.lambda_ = lambda_
        self.tol = tol
        self.max_iter = max_iter
        self.w_ = None


    def fit(self, X, t):
        n, d = X.shape
        self.w_ = np.zeros(d + 1)
        avgl1 = 0.
        for _ in range(self.max_iter): # max_iter = 10000回繰り返す。
            avgl1_prev = avgl1
            self._update(n, d, X, t)
            avgl1 = np.abs(self.w_).sum() / self.w_.shape[0]
            if abs(avgl1 - avgl1_prev) <= self.tol:
                break # 誤差がtol = 0.0001以下になったら終了。

    def _update(self, n, d, X, t):
        self.w_[0] = (t - np.dot(X, self.w_[1:])).sum() / n
        w0vec = np.ones(n) * self.w_[0]
        for k in range(d):
            ww = self.w_[1:]
            ww[k] = 0
            q = np.dot(t - w0vec - np.dot(X, ww), X[:, k])
            r = np.dot(X[:, k], X[:, k])
            self.w_[k + 1] = soft_thresholding(q / r, self.lambda_)

    def predict(self, X):
        if X.ndim == 1:
            X = X.reshape(1, X.shape[0])
            Xtil = np.c_[np.ones(X.shape[0]), X]
        return np.dot(Xtil, self.w_)

for lambda_ in [1., 0.1, 0.01]: # 三種類のハイパーパラメータを試す。
    model = Lasso(lambda_)
    model.fit(train_X, train_y)
    y = model.predict(test_X)
    print("--- ハイパーパラメータlambda = {} ---".format(lambda_))
    print("係数w:")
    print(model.w_)
    mse = ((y - test_y)**2).mean()
    print("予想値: {}".format(y[0]))
    print("実際の値:{}".format(test_y))
    print("誤差E(w): {:.3f}".format(mse))

出力は以下のようになります。

--- ハイパーパラメータlambda = 1.0 ---
係数w:
[ 5.6360601  0.        -0.         0.         0.        -0.
 -0.        -0.        -0.        -0.         0.         0.       ]
予想値: 5.636060100166945
実際の値:7.0
誤差E(w): 1.860
--- ハイパーパラメータlambda = 0.1 ---
係数w:
[ 6.13255766  0.         -0.75763602  0.27031068  0.         -1.97134698
 -0.         -0.          0.          0.          0.          0.        ]
予想値: 5.844448204297558
実際の値:7.0
誤差E(w): 1.335
--- ハイパーパラメータlambda = 0.01 ---
係数w:
[ 5.76652084 -0.         -1.51392331 -0.03358247  0.         -3.10993286
 -0.         -0.          0.21500579  0.          1.08349525  0.        ]
予想値: 6.165807417800908
実際の値:7.0
誤差E(w): 0.696

このように計算できました。
ハイパーパラメータが高いほど$w_k$が「ないほうがマシ」と判定されて疎行列になっていくこと、逆にハイパーパラメータが低いほど過学習のリスクが高まることがわかります。

まとめ

ラッソ回帰は絶対値が含まれて計算が厄介な数式でしたが、数学の力で特別なライブラリなど使用せずに実装できました。
ハイパーパラメータの設定によって結果が変わるので注意が必要です。

『機械学習のエッセンス』という本を参考にしました。この本ではラッソ回帰のコードには誤植があるので気を付けてください。
前回:多項式回帰、過学習
https://qiita.com/NNNiNiNNN/items/d87990a6eef72a3815a3

4
3
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
4
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?