からっぽのしょこ

読んだら書く!書いたら読む!同じ事は二度調べ(たく)ない

3.1.4.b:ラッソ回帰の導出【PRMLのノート】

はじめに

 『パターン認識と機械学習』の独学時のまとめです。一連の記事は「数式の行間埋め」または「R・Pythonでの実装」からアルゴリズムの理解を補助することを目的としています。本とあわせて読んでください。

 この記事は、3.1.4項「正則化最小二乗法」の内容です。ラッソ回帰(Lasso回帰)を導出します。

【実装編】

www.anarchive-beta.com

www.anarchive-beta.com

【前節の内容】

www.anarchive-beta.com

【他の節一覧】

www.anarchive-beta.com

【この節の内容】

3.1.4 ラッソ回帰の導出

 過学習を防ぐために線形基底関数モデルに正則化項を導入します。線形基底関数モデルについては「3.1.1:最尤推定と最小二乗法【PRMLのノート】 - からっぽのしょこ」を参照してください。

・モデルの設定

 これまでは、二乗和誤差関数$E_D(\mathbf{w})$を最小化(尤度関数を最大化)するパラメータ$\mathbf{w}$を考えました。

$$ E_D(\mathbf{w}) = \frac{1}{2} \sum_{n-1}^N \Bigl\{ t_n - \mathbf{w}^{\top} \boldsymbol{\phi}(\mathbf{x}_n) \Bigr\}^2 \tag{3.26} $$

 ここで、入力変数$\mathbf{X} = \{\mathbf{x}_1, \mathbf{x}_2, \cdots, \mathbf{x}_N\}$、$\mathbf{x}_n = (x_{n,1}, x_{n,2}, \cdots, x_{n,D})^{\top}$、目標値$\mathbf{t} = \{t_1, t_2, \cdots, t_N\}$、基底関数$\boldsymbol{\phi}(\mathbf{x}_n) = (\phi_0(\mathbf{x}_n), \phi_1(\mathbf{x}_n), \cdots, \phi_{M-1}(\mathbf{x}_n))^{\top}$、重みパラメータ$\mathbf{w} = (w_0, w_1, \cdots, w_{M-1})^{\top}$です。ただし、$\phi_0(\mathbf{x}) = 1$とすることで$w_0 = w_0 \phi_0(\mathbf{x})$とし、$w_0$をバイアスと呼びます。
 正則化最小二乗法では、正則化項$E_W(\mathbf{w})$を導入します。

$$ E_W(\mathbf{w}) = \frac{1}{q} \sum_{j=0}^{M-1} |w_j|^q $$

 $|w_j|$は$w_j$の絶対値です。
 二乗和誤差$E_D(\mathbf{w})$に正則化項$E_W(\mathbf{w})$を加えたものを誤差関数$E(\mathbf{w})$とします。

$$ \begin{align} E(\mathbf{w}) &= E_D(\mathbf{w}) + \lambda E_W(\mathbf{w}) \tag{3.24}\\ &= \frac{1}{2} \sum_{n-1}^N \Bigl\{ t_n - \mathbf{w}^{\top} \boldsymbol{\phi}(\mathbf{x}_n) \Bigr\}^2 + \frac{\lambda}{q} \sum_{j=0}^{M-1} |w_j|^q \tag{3.29} \end{align} $$

 ここで、$\lambda$は正則化項の影響を調整する正則化係数です。

 誤差関数に正則化項を含めることで、誤差を小さくしつつパラメータの値も小さくすることが期待できます。

・ラッソ回帰の最尤解の導出

 $q = 1$の場合、正則化項がL1ノルムになります。このとき、ラッソ回帰(Lasso回帰)またはL1正則化と呼びます。L1ノルムについては「【R】Lpノルムの作図【PRMLのノート】 - からっぽのしょこ」を参照してください。

 $q = 1$のとき、正則化項はL1ノルム$\|\mathbf{w}\|_1$になります。

$$ E_W(\mathbf{w}) = \sum_{j=0}^{M-1} |w_j| = \|\mathbf{w}\|_1 $$

 よって、誤差関数は

$$ \begin{align} E_{\mathrm{Lasso}}(\mathbf{w}) &= E_D(\mathbf{w}) + \lambda E_W(\mathbf{w}) \tag{3.24}\\ &= \frac{1}{2} \sum_{n-1}^N \Bigl\{ t_n - \mathbf{w}^{\top} \boldsymbol{\phi}(\mathbf{x}_n) \Bigr\}^2 + \lambda \sum_{j=0}^{M-1} |w_j| \\ &= \frac{1}{2} \sum_{n-1}^N \Bigl\{ t_n - \sum_{j=0}^{M-1} w_j \phi_j(\mathbf{x}_n) \Bigr\}^2 + \lambda \sum_{j=0}^{M-1} |w_j| \tag{1} \end{align} $$

となります。バイアスパラメータ$w_0$を正則化項に含めない場合については、最後に扱います。

 誤差関数(1)を最小化する重みパラメータ$\mathbf{w}_{\mathrm{Lasso}}$(の各項)を求めます。

 $w_k$に関して誤差関数を微分します。

$$ \begin{aligned} \frac{\partial}{\partial w_k} E_{\mathrm{Lasso}}(\mathbf{w}) &= \frac{\partial}{\partial w_k} \Bigl\{ E_D(\mathbf{w}) + \lambda E_W(\mathbf{w}) \Bigr\} \\ &= \frac{\partial}{\partial w_k} E_D(\mathbf{w}) + \lambda \frac{\partial}{\partial w_k} E_W(\mathbf{w}) \end{aligned} $$

 この式を具体的な式に置き替えると次のようになります。

$$ \begin{aligned} \frac{\partial}{\partial w_k} E_{\mathrm{Lasso}}(\mathbf{w}) &= \frac{\partial}{\partial w_k} \left\{ \frac{1}{2} \sum_{n=1}^N \Bigl( t_n - \sum_{j=0}^{M-1} w_j \phi_j(\mathbf{x}_n) \Bigr)^2 + \lambda \sum_{j=0}^{M-1} |w_j| \right\} \\ &= \frac{1}{2} \frac{\partial}{\partial w_k} \left\{ \sum_{n=1}^N \Bigl( t_n - \sum_{j=0}^{M-1} w_j \phi_j(\mathbf{x}_n) \Bigr)^2 \right\} + \lambda \frac{\partial}{\partial w_k} \left\{ \sum_{j=0}^{M-1} |w_j| \right\} \end{aligned} $$

 二乗和誤差関数の微分は、合成関数の微分により

$$ \begin{aligned} \frac{\partial}{\partial w_k} E_D(\mathbf{w}) &= \frac{1}{2} \frac{\partial}{\partial w_k} \left\{ \sum_{n=1}^N \Bigl( t_n - \sum_{j=0}^{M-1} w_j \phi_j(\mathbf{x}_n) \Bigr)^2 \right\} \\ &= \sum_{n=1}^N \Bigl( t_n - \sum_{j=0}^{M-1} w_j \phi_j(\mathbf{x}_n) \Bigr) \frac{\partial}{\partial w_k} \left\{ t_n - \sum_{j=0}^{M-1} w_j \phi_j(\mathbf{x}_n) \right\} \end{aligned} $$

となります。全体を$g(f(x))$、丸括弧を$f(x)$に対応させて、合成関数の微分$\{g(f(x))\}' = g'(f(x)) f'(x)$を行っています。さらに、後の項は

$$ \begin{aligned} \frac{\partial}{\partial w_k} \left\{ t_n - \sum_{j=0}^{M-1} w_j \phi_j(\mathbf{x}_n) \right\} &= \frac{\partial}{\partial w_k} \left\{ t_n - \sum_{j=0}^{M-1} w_j \phi_j(\mathbf{x}_n) \right\} \\ &= \frac{\partial}{\partial w_k} \left\{ t_n - w_k \phi_k(\mathbf{x}_n) - \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \right\} \\ &= \frac{\partial}{\partial w_k} t_n - \frac{\partial}{\partial w_k} w_k \phi_k(\mathbf{x}_n) - \frac{\partial}{\partial w_k} \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \\ &= 0 - \phi_k(\mathbf{x}_n) + 0 \\ &= - \phi_k(\mathbf{x}_n) \end{aligned} $$

$w_k$に関する項のみ残ります。1行目から2行目では、$j = 0, 1, \cdots, M - 1$から$k$番目の項を取り出しています。よって

$$ \frac{\partial}{\partial w_k} E_D(\mathbf{w}) = - \sum_{n=1}^N \left( t_n - \sum_{j=0}^{M-1} w_j \phi_j(\mathbf{x}_n) \right) \phi_k(\mathbf{x}_n) $$

となります。

 正則化項の微分についても

$$ \begin{aligned} \frac{\partial}{\partial w_k} E_W(\mathbf{w}) &= \frac{\partial}{\partial w_k} \left\{ \sum_{j=1}^M |w_j| \right\} \\ &= \frac{\partial}{\partial w_k} \Bigl\{ |w_1| + \cdots + |w_k| + \cdots + |w_M| \Bigr\} \\ &= \frac{\partial}{\partial w_k} |w_1| + \cdots + \frac{\partial}{\partial w_k} |w_k| + \cdots + \frac{\partial}{\partial w_k} |w_M| \\ &= 0 + \cdots + \frac{\partial}{\partial w_k} |w_k| + \cdots + 0 \\ &= \frac{\partial}{\partial w_k} |w_k| \end{aligned} $$

$w_k$に関する項が残ります。
 絶対値について

$$ |w_k| = \begin{cases} w_k &\quad (w_k > 0) \\ - w_k &\quad (w_k < 0) \end{cases} $$

なので、絶対値の微分は

$$ \frac{\partial}{\partial w_k} E_W(\mathbf{w}) = \frac{\partial}{\partial w_k} |w_k| = \begin{cases} 1 &\quad (w_k > 0) \\ [-1, 1] &\quad(w_k = 0) \\ - 1 &\quad (w_k < 0) \end{cases} $$

です。$w_k = 0$のとき、-1から1の値になります。$[-1, 1]$で-1から1を表します。これを劣微分と言います(よく分かってないので解説は省略)。
 グラフで確認しましょう。

・作図コード(クリックで展開)

# 利用するパッケージ
library(tidyverse)
library(gganimate)
# 作図用のデータフレームを作成
df <- tidyr::tibble(
  w = seq(-1, 1, by = 0.001), # x軸の値
  abs_w = abs(w), # 絶対値
  dw = dplyr::if_else(w < 0, true = -1, false = 1) # (雑に)絶対値の微分
)

# 絶対値のグラフを作成
ggplot(df, aes(x = w, y = abs_w)) + 
  geom_line() + 
  labs(title = expression(group("|", w[k], "|")), 
       x = expression(w[k]), y = expression(group("|", w[k], "|")))

# 絶対値の微分のグラフを作成
ggplot(df, aes(x = w, y = dw)) + 
  geom_line() + 
  labs(title = expression(frac(d * group("|", w[k], "|"), d * w[k])), 
       x = expression(w[k]), y = expression(d * w[k]))
# 計算用のデータフレームを作成
df <- tidyr::tibble(
  w = seq(-1, 1, by = 0.01), # x軸の値
  abs_w = abs(w) # 絶対値
)

# 絶対値の接線を計算
anime_df <- tidyr::tibble()
for(tmp_w in seq(- 1, 1, by = 0.01)) { # 接点に利用する値を指定
  if(tmp_w != 0){ # 微分可能な範囲
    # 接線を計算
    tmp_df <- df %>% 
      dplyr::mutate(
        tangent_point_w = tmp_w, # 接点のx軸の値
        tangent_point_y = abs(tmp_w), # 接点のy軸の値
        dw = dplyr::case_when(
          tmp_w > 0 ~ 1, 
          tmp_w < 0 ~ -1
        ), # 絶対値の微分(接線の傾き)
        tangent_line_y = dplyr::case_when(
          tmp_w > 0 ~ w, 
          tmp_w < 0 ~ -w
        ), # 接線のy軸の値
        label = paste0("w=", round(tmp_w, 2), ", dw=", dw) %>% 
          as.factor() # フレーム切替用のラベル
      )
    
    # 結果を結合
    anime_df <- rbind(anime_df, tmp_df)
    
  } else if(tmp_w == 0) { # 劣微分の範囲
    
    # 劣微分の値(傾き)ごとに接線を計算
    for(tmp_dw in seq(-1, 1, by = 0.01)) { # 劣微分に利用する値を指定
      # 接線を計算
      tmp_df <- df %>% 
        dplyr::mutate(
          tangent_point_w = tmp_w, # 接点のx軸の値
          tangent_point_y = abs(tmp_w), # 接点のy軸の値
          dw = tmp_dw, # 絶対値の微分(接線の傾き)
          tangent_line_y = tmp_dw * w, # 接線のy軸の値
          label = paste0("w=", round(tmp_w, 2), ", dw=", round(tmp_dw, 2)) %>% 
            as.factor() # フレーム切替用のラベル
        )
      
      # 結果を結合
      anime_df <- rbind(anime_df, tmp_df)
    }
  }
}

# 接線を作図
anime_graph <- ggplot(anime_df, aes(x = w)) + 
  geom_line(aes(y = abs_w)) + # 絶対値
  geom_point(aes(x = tangent_point_w, y = tangent_point_y), color = "red") + # 接点
  geom_line(aes(y = tangent_line_y), color = "purple", linetype = "dashed") + # 接線
  gganimate::transition_manual(label) + # フレーム
  ylim(c(-0.5, 1)) + # y軸の表示範囲
  labs(title = "Tangent Line", 
       subtitle = paste0("{current_frame}"), 
       x = expression(w[k]), y = expression(group("|", w[k], "|")))

# gif画像に変換
gganimate::animate(anime_graph, nframes = length(unique(anime_df[["label"]])), fps = 25)


f:id:anemptyarchive:20211202034650p:plainf:id:anemptyarchive:20211202034657p:plainf:id:anemptyarchive:20211202082919g:plain
絶対値の微分のグラフ

 左の図は絶対値のグラフです。
 中の図は絶対値の微分のグラフです。$w_k = 0$においてy軸が-1から1になっているのが劣微分に対応しています。
 右の図は絶対値のグラフに対する接線です。$w_k < 0,\ w_k > 0$では接線の傾き(微分)がそれぞれ$- 1,\ 1$で固定で、$w_k = 0$では$[-1, 1]$の範囲で変化するのを確認できます。この値の変化が中の図に対応しています。

 よって、誤差関数の微分は

$$ \begin{aligned} \frac{\partial}{\partial w_k} E_{\mathrm{Lasso}}(\mathbf{w}) &= \frac{\partial}{\partial w_k} E_D(\mathbf{w}) + \lambda \frac{\partial}{\partial w_k} E_W(\mathbf{w}) \\ &= \begin{cases} - \sum_{n=1}^N \Bigl( t_n - \mathbf{w}^{\top} \boldsymbol{\phi}(\mathbf{x}_n) \Bigr) \phi_k(\mathbf{x}_n) + \lambda &\quad (w_k > 0) \\ - \sum_{n=1}^N \Bigl( t_n - \mathbf{w}^{\top} \boldsymbol{\phi}(\mathbf{x}_n) \Bigr) \phi_k(\mathbf{x}_n) + [- \lambda, \lambda] &\quad (w_k = 0) \\ - \sum_{n=1}^N \Bigl( t_n - \mathbf{w}^{\top} \boldsymbol{\phi}(\mathbf{x}_n) \Bigr) \phi_k(\mathbf{x}_n) - \lambda &\quad (w_k < 0) \end{cases} \end{aligned} $$

となり、$w_k$の値によって場合分けして計算する必要があります。

 $w_k$に関する損失関数の微分$\frac{\partial}{\partial w_k} E_{\mathrm{Lasso}}(\mathbf{w})$を0とおき、$w_k$について解きます。

 まずは、$w_k > 0$の場合を考えます。$k$以外の項を右辺に移項し

$$ \begin{aligned} \frac{\partial}{\partial w_k} E_{\mathrm{Lasso}}(\mathbf{w}) = - \sum_{n=1}^N \left( t_n - \sum_{j=0}^{M-1} w_j \phi_j(\mathbf{x}_n) \right) \phi_k(\mathbf{x}_n) + \lambda &= 0 \\ \Rightarrow - \sum_{n=1}^N \left( t_n - w_k \phi_k(\mathbf{x}_n) - \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \right) \phi_k(\mathbf{x}_n) &= - \lambda \\ \Rightarrow w_k \sum_{n=1}^N \phi_k(\mathbf{x}_n)^2 &= \sum_{n=1}^N \left( t_n - \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \right) \phi_k(\mathbf{x}_n) - \lambda \end{aligned} $$

両辺を$\sum_{n=1}^N \phi_k(\mathbf{x}_n)^2$で割ります。

$$ w_k = \frac{ \sum_{n=1}^N \left( t_n - \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \right) \phi_k(\mathbf{x}_n) - \lambda }{ \sum_{n=1}^N \phi_k(\mathbf{x}_n)^2 } \equiv w_k^{(\mathrm{Lasso})} \quad (w_k > 0) \tag{2} $$

 $w_k > 0$における最尤解が得られました。

 この式(2)を条件式に代入すると

$$ \begin{aligned} &w_k > 0 \\ \Rightarrow& \frac{ \sum_{n=1}^N \left( t_n - \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \right) \phi_k(\mathbf{x}_n) - \lambda }{ \sum_{n=1}^N \phi_k(\mathbf{x}_n)^2 } > 0 \\ \Rightarrow& \sum_{n=1}^N \left( t_n - \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \right) \phi_k(\mathbf{x}_n) > \lambda \end{aligned} $$

となります。
 式(2)の分子を見ると、$\sum_{n=1}^N (t_n - \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n)) \phi_k(\mathbf{x}_n)$が$\lambda$より小さいと$w_k$が負の値になり、$w_k > 0$の条件を満たさないことが分かります。この式は、式(2)が成立する条件と言えます。

 $w_k < 0$の場合も同様にして

$$ \begin{align} \frac{\partial}{\partial w_k} E_{\mathrm{Lasso}}(\mathbf{w}) =& - \sum_{n=1}^N \left( t_n - \sum_{j=0}^{M-1} w_j \phi_j(\mathbf{x}_n) \right) \phi_k(\mathbf{x}_n) - \lambda = 0 \\ &\Rightarrow w_k = \frac{ \sum_{n=1}^N \left( t_n - \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \right) \phi_k(\mathbf{x}_n) + \lambda }{ \sum_{n=1}^N \phi_k(\mathbf{x}_n)^2 } \equiv w_k^{(\mathrm{Lasso})} \quad (w_k < 0) \tag{3} \end{align} $$

が得られます。
 また

$$ \begin{aligned} &w_k < 0 \\ \Rightarrow& \sum_{n=1}^N \left( t_n - \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \right) \phi_k(\mathbf{x}_n) < - \lambda \end{aligned} $$

となります。

 $w_k = 0$の場合を考えます。
 式を分かりやすくするために、$w_k$に影響しない項を$S$とおきます。

$$ S = \sum_{n=1}^N \left( t_n - \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \right) \phi_k(\mathbf{x}_n) $$

 $w_k = 0$なので、$w_k$に影響する項は消えてしまいます。

$$ \begin{aligned} \frac{\partial}{\partial w_k} E_{\mathrm{Lasso}}(\mathbf{w}) &= - \sum_{n=1}^N \left( t_n - \sum_{j=0}^{M-1} w_j \phi_j(\mathbf{x}_n) \right) \phi_k(\mathbf{x}_n) + [- \lambda, \lambda] \\ &= w_k \sum_{n=1}^N \phi_k(\mathbf{x}_n)^2 - S + [- \lambda, \lambda] \\ &= [- S - \lambda, - S + \lambda] \quad (w_k = 0) \end{aligned} $$

 これを0とおくと?

$$ \begin{aligned} &- S - \lambda \leq 0 \leq - S + \lambda \\ \Rightarrow& - \lambda \leq S \leq \lambda \end{aligned} $$

となる?これは、式(2)(3)が成り立たない範囲と言えます。
 この条件の下で

$$ w_k^{(\mathrm{Lasso})} = 0 \tag{4} $$

となります。(この部分よく分からない。)

 したがって、式(2)から(4)をまとめると

$$ w_k^{(\mathrm{Lasso})} = \begin{cases} \frac{S - \lambda}{\sum_{n=1}^N \phi_k(\mathbf{x}_n)^2} &\quad (S > \lambda) \\ 0 &\quad (- \lambda \leq S \leq \lambda) \\ \frac{S + \lambda}{\sum_{n=1}^N \phi_k(\mathbf{x}_n)^2} &\quad (S < - \lambda) \\ \end{cases} $$

となります。
 ただし

$$ S = \sum_{n=1}^N \left( t_n - \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \right) \phi_k(\mathbf{x}_n) $$

とおきました。

 グラフで確認しましょう。

f:id:anemptyarchive:20211221210059p:plain
パラメータの値が0になる閾値のグラフ

 平らになっている($w_k = 0$となる)範囲が$- \lambda \leq S \leq \lambda$です。$\lambda$が大きいほど値が0になりやすいのが分かります。また、$S$は観測データの影響を受けるので、観測データによってもグラフの形状が変わります。詳しくは、実装編を参照してください。

・式を整理

 式がごちゃごちゃしているので(またプログラム上で計算しやすくするため)行列の積の形に書き替えてみます。

 式(2)(3)の分子の項を展開します。

$$ \sum_{n=1}^N \left( t_n - \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \right) \phi_k(\mathbf{x}_n) = \sum_{n=1}^N t_n \phi_k(\mathbf{x}_n) - \sum_{n=1}^N \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \phi_k(\mathbf{x}_n) $$

 前の項は、ベクトルの積で表せます。

$$ \begin{aligned} \sum_{n=1}^N t_n \phi_k(\mathbf{x}_n) &= \begin{pmatrix} t_1 & t_2 & \cdots & t_N \end{pmatrix} \begin{pmatrix} \phi_k(\mathbf{x}_1) \\ \phi_k(\mathbf{x}_2) \\ \vdots \\ \phi_k(\mathbf{x}_N) \end{pmatrix} \\ &= \mathsf{t}^{\top} \boldsymbol{\Phi}_k \end{aligned} $$

 後の項は、2つのベクトルと行列の積で表せます。

$$ \begin{aligned} \sum_{n=1}^N \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \phi_k(\mathbf{x}_n) &= \begin{pmatrix} \sum_{j \neq k} w_j \phi_j(\mathbf{x}_1) & \cdots & \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) & \cdots & \sum_{j \neq k} w_j \phi_j(\mathbf{x}_N) \end{pmatrix} \begin{pmatrix} \phi_k(\mathbf{x}_1) \\ \vdots \\ \phi_k(\mathbf{x}_n) \\ \vdots \\ \phi_k(\mathbf{x}_N) \end{pmatrix} \\ &= \begin{pmatrix} w_0 & \cdots & w_{k-1} & 0 & w_{k+1} & \cdots & w_{M-1} \end{pmatrix} \begin{pmatrix} \phi_0(\mathbf{x}_1) & \cdots & \phi_0(\mathbf{x}_n) & \cdots & \phi_0(\mathbf{x}_N) \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ \phi_k(\mathbf{x}_1) & \cdots & \phi_k(\mathbf{x}_n) & \cdots & \phi_k(\mathbf{x}_N) \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ \phi_{M-1}(\mathbf{x}_1) & \cdots & \phi_{M-1}(\mathbf{x}_n) & \cdots & \phi_{M-1}(\mathbf{x}_N) \end{pmatrix} \begin{pmatrix} \phi_k(\mathbf{x}_1) \\ \vdots \\ \phi_k(\mathbf{x}_n) \\ \vdots \\ \phi_k(\mathbf{x}_N) \end{pmatrix} \\ &= \mathbf{w}_{\backslash k}^{\top} \boldsymbol{\Phi}^{\top} \boldsymbol{\Phi}_k \end{aligned} $$

 ただし、$k$番目の要素が0のパラメータを$\mathbf{w}_{\backslash k}$、計画行列$\boldsymbol{\Phi}$の$k$列目を$\boldsymbol{\Phi}_k$とおきました(本当は$k$に関する要素を除くべきですが、0にした方がプログラム上の扱いが楽そうなので)。
 また、分母も内積で表せます。

$$ \begin{aligned} \sum_{n=1}^N \phi_k(\mathbf{x}_n)^2 &= \begin{pmatrix} \phi_k(\mathbf{x}_1) & \phi_k(\mathbf{x}_2) & \cdots & \phi_k(\mathbf{x}_N) \end{pmatrix} \begin{pmatrix} \phi_k(\mathbf{x}_1) \\ \phi_k(\mathbf{x}_2) \\ \vdots \\ \phi_k(\mathbf{x}_N) \end{pmatrix} \\ &= \boldsymbol{\Phi}_k^{\top} \boldsymbol{\Phi}_k \end{aligned} $$

 よって、最尤解の計算式(2)は

$$ \begin{align} w_k^{(\mathrm{Lasso})} &= \frac{ \sum_{n=1}^N \left( t_n - \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \right) \phi_k(\mathbf{x}_n) - \lambda }{ \sum_{n=1}^N \phi_k(\mathbf{x}_n)^2 } \tag{2}\\ &= \frac{ \sum_{n=1}^N t_n \phi_k(\mathbf{x}_n) - \sum_{n=1}^N \sum_{j \neq k} w_j \phi_j(\mathbf{x}_n) \phi_k(\mathbf{x}_n) - \lambda }{ \sum_{n=1}^N \phi_k(\mathbf{x}_n)^2 } \\ &= \frac{ \mathsf{t}^{\top} \boldsymbol{\Phi}_k - \mathbf{w}_{\backslash k}^{\top} \boldsymbol{\Phi}^{\top} \boldsymbol{\Phi}_k - \lambda }{ \boldsymbol{\Phi}_k^{\top} \boldsymbol{\Phi}_k } \\ &= \frac{ \Bigl( \mathsf{t}^{\top} - \mathbf{w}_{\backslash k}^{\top} \boldsymbol{\Phi}^{\top} \Bigr) \boldsymbol{\Phi}_k - \lambda }{ \boldsymbol{\Phi}_k^{\top} \boldsymbol{\Phi}_k } \quad (w_k > 0) \end{align} $$

と書けます。式(3)についても同様です。

・バイアスを正則化項に含めない場合

 バイアス$w_0$を正則化項に含めないことがあるらしい。その場合のバイアスの最尤解$w_0^{(\mathrm{Lasso})}$を考えます。

 $w_0$を含めないので、正則化項は

$$ E_W(\mathbf{w}_{\backslash 0}) = |w_1| + |w_2| + \cdots + |w_{M-1}| = \sum_{j=1}^{M-1} |w_j| $$

となります。$w_0$を除く$M - 1$個のパラメータを$\mathbf{w}_{\backslash 0} = (w_1, w_2, \cdots, w_{M-1})$で表します(が、この表記はもう登場しません)。
 また、定義より$\phi_0(\mathbf{x}_n) = 1$なので、二乗和誤差関数の式を$w_0 = w_0 \phi_0(\mathbf{x}_n)$を取り出して

$$ E_D(\mathbf{w}) = \frac{1}{2} \sum_{n=1}^N \Bigl( t_n - \sum_{j=0}^{M-1} w_j \phi_j(\mathbf{x}_n) \Bigr)^2 = \frac{1}{2} \sum_{n=1}^N \Bigl( t_n - w_0 - \sum_{j=1}^{M-1} w_j \phi_j(\mathbf{x}_n) \Bigr)^2 $$

としておきます。
 よって、誤差関数は

$$ \begin{align} E_{\mathrm{Lasso}}(\mathbf{w}) &= E_D(\mathbf{w}) + E_W(\mathbf{w}_{\backslash 0}) \\ &= \frac{1}{2} \sum_{n=1}^N \Bigl( t_n - w_0 - \sum_{j=1}^{M-1} w_j \phi_j(\mathbf{x}_n) \Bigr)^2 + \lambda \sum_{j=1}^{M-1} |w_j| \tag{5} \end{align} $$

となります。

 $w_0$に関して誤差関数(5)を微分します。

$$ \begin{aligned} \frac{\partial}{\partial w_0} E_{\mathrm{Lasso}}(\mathbf{w}) &= \frac{\partial}{\partial w_0} \left\{ \frac{1}{2} \sum_{n=1}^N \Bigl( t_n - w_0 - \sum_{j=1}^{M-1} w_j \phi_j(\mathbf{x}_n) \Bigr)^2 + \lambda \sum_{j=1}^{M-1} |w_j| \right\} \\ &= \frac{1}{2} \frac{\partial}{\partial w_0} \left\{ \sum_{n=1}^N \Bigl( t_n - w_0 - \sum_{j=1}^{M-1} w_j \phi_j(\mathbf{x}_n) \Bigr)^2 \right\} + \lambda \frac{\partial}{\partial w_0} \left\{ \sum_{j=1}^{M-1} |w_j| \right\} \end{aligned} $$

 正則化項は$w_0$を含まないので微分すると0になり、二乗和誤差関数の微分となります。

$$ \begin{aligned} \frac{\partial}{\partial w_0} E_{\mathrm{Lasso}}(\mathbf{w}) &= \sum_{n=1}^N \left( t_n - w_0 - \sum_{j=1}^{M-1} w_j \phi_j(\mathbf{x}_n) \right) \frac{\partial}{\partial w_0} \left\{ t_n - w_0 - \sum_{j=1}^{M-1} w_j \phi_j(\mathbf{x}_n) \right\} + 0 \\ &= \sum_{n=1}^N \left( t_n - w_0 - \sum_{j=1}^{M-1} w_j \phi_j(\mathbf{x}_n) \right) \left( \frac{\partial}{\partial w_0} t_n - \frac{\partial}{\partial w_0} w_0 - \frac{\partial}{\partial w_0} \sum_{j=1}^{M-1} w_j \phi_j(\mathbf{x}_n) \right) \\ &= \sum_{n=1}^N \left( t_n - w_0 - \sum_{j=1}^{M-1} w_j \phi_j(\mathbf{x}_n) \right) (0 - 1 + 0) \\ &= - \sum_{n=1}^N \left( t_n - w_0 - \sum_{j=1}^{M-1} w_j \phi_j(\mathbf{x}_n) \right) \end{aligned} $$

 先ほど求めた$w_k$に関する二乗和誤差関数の微分における、$k = 0$のときと同じ式になります。

 誤差関数の微分を0とおき、$w_0$について解きます。

$$ \begin{aligned} \frac{\partial}{\partial w_0} E_{\mathrm{Lasso}}(\mathbf{w}) = - \sum_{n=1}^N &\left( t_n - w_0 - \sum_{j=1}^{M-1} w_j \phi_j(\mathbf{x}_n) \right) = 0 \\ \Rightarrow N w_0 &= \sum_{n=1}^N \left( t_n - \sum_{j=1}^{M-1} w_j \phi_j(\mathbf{x}_n) \right) \\ \Rightarrow w_0 &= \frac{1}{N} \sum_{n=1}^N \left( t_n - \sum_{j=1}^{M-1} w_j \phi_j(\mathbf{x}_n) \right) \equiv w_0^{(\mathrm{Lasso})} \end{aligned} $$

 バイアスパラメータの最尤解が得られました。絶対値の微分を含まないため場合分けや劣微分は不要です。$j = 1, \cdots, M - 1$の項については、$w_k^{(\mathrm{Lasso})}$になります。

参考文献

  • C.M.ビショップ著,元田 浩・他訳『パターン認識と機械学習 上下』,丸善出版,2012年.

おわりに

 L2よりL1の方が難しいのね。まだ理解がふわっとしている。劣微分???

 2021年12月1日は、元Juice=Juiceの宮本佳林さんの23歳のお誕生日&ソロデビューシングルの発売日です。シングルの3曲をどうぞ♪♪♪

 おめでとう!そしておめでとう!

 あとこのブログの解説日でもあります。4年目もハロプロ記念日駆動執筆でやっていきます♬

【次節の内容】

www.anarchive-beta.com