ラッソ回帰(L1正則化)

L1正則化

目的関数に正則化項としてL1ノルムを加えたものをL1正則化と言います。ラッソ回帰とも言います。
$w_0$ は正則化から外すことも多い為、今回は外します。
目的関数は以下のようになります。

$\begin{eqnarray} E({\bf w})&=&\frac{1}{2}||{\boldsymbol\Phi}{\bf w}-{\bf t}||^2+\lambda\sum_{i=1}^D|w_i|\tag{1} \end{eqnarray}$

最適化

この目的関数の最適化はL1ノルムがあり、解析的に解くのが難しい為、座標降下法を使って解きます。
座標降下法とは一般に、
ある ${\bf x}\in{\mathbb R}^D$ の関数 $\psi({\bf x})$ を最小化(最大化)したいときに、
$\frac{\partial\psi}{\partial x_1}=0$ を満たす $x_1$ で $x_1$ を更新し、
$\frac{\partial\psi}{\partial x_2}=0$ を満たす $x_2$ で $x_2$ を更新し、という風に繰り返していく方法です。

まず、 $w_0$ の更新式を求めます。
$E({\bf w})$ を $w_0$ についてまとめます。

$\begin{eqnarray} E({\bf w})&=&\frac{1}{2}||{\boldsymbol\Phi}{\bf w}-{\bf t}||^2+\lambda\sum_{i=1}^D|w_i|\\ &=&\frac{1}{2}\sum_{n=1}^N({\boldsymbol\phi}(x_n)^\top{\bf w}-t_n)^2+{\rm const.}\\ &=&\frac{1}{2}\sum_{n=1}^N(w_0+\phi_1(x_n)w_1+\cdots+\phi_D(x_n)w_D-t_n)^2+{\rm const.}\\ &=&\frac{1}{2}\sum_{n=1}^N\left(w_0^2+2w_0\left(\sum_{d=1}^D\phi_d(x_n)w_d-t_n\right)\right)+{\rm const.}\tag{2}\\ \end{eqnarray}$

(2)を $w_0$ で微分して $=0$ とおきます。

$\begin{eqnarray} &&\frac{\partial}{\partial w_0}E({\bf w})=0\\ &&\Leftrightarrow\sum_{n=1}^N\left(w_0+\sum_{d=1}^D\phi_d(x_n)w_d-t_n\right)=0\\ &&\Leftrightarrow Nw_0+\sum_{n=1}^N\left(\sum_{d=1}^D\phi_d(x_n)w_d-t_n\right)=0\\ &&\Leftrightarrow w_0=\frac{1}{N}\sum_{n=1}^N\left(t_n-\sum_{d=1}^D\phi_d(x_n)w_d\right)\tag{3}\ \end{eqnarray}$

次に、 $w_k(k\not=0)$ の更新式を求めます。一旦、 $w_k>0$ とします。この時、 $|w_k|=w_k$ です。
$E({\bf w})$ を $w_k$ についてまとめます。

$\begin{eqnarray} E({\bf w})&=&\frac{1}{2}||{\boldsymbol\Phi}{\bf w}-{\bf t}||^2+\lambda\sum_{i=1}^D|w_i|\\ &=&\frac{1}{2}\sum_{n=1}^N({\boldsymbol\phi}(x_n)^\top{\bf w}-t_n)^2+\lambda w_k+{\rm const.}\\ &=&\frac{1}{2}\sum_{n=1}^N(w_0+\phi_1(x_n)w_1+\cdots+\phi_D(x_n)w_D-t_n)^2+\lambda w_k+{\rm const.}\\ &=&\frac{1}{2}\sum_{n=1}^N\left(\phi_k(x_n)^2w_k^2+2\phi_k(x_n)w_k\left(w_0+\sum_{d\not=k}\phi_d(x_n)w_d-t_n\right)\right)+\lambda w_k+{\rm const.}\tag{4}\\ \end{eqnarray}$

(4)の $\sum_{d\not=k}$ は $\sum_{d=1,d\not=k}^D$ です。
(4)を $w_k$ で微分して $=0$ とおきます。

$\begin{eqnarray} &&\frac{\partial}{\partial w_0}E({\bf w})=0\\ &&\Leftrightarrow\sum_{n=1}^N\left(\phi_k(x_n)^2w_k+\phi_k(x_n)\left(w_0+\sum_{d\not=k}\phi_d(x_n)w_d-t_n\right)\right)+\lambda=0\\ &&\Leftrightarrow \left(\sum_{n=1}^N\phi_k(x_n)^2\right)w_k+\sum_{n=1}^N\phi_k(x_n)\left(w_0+\sum_{d\not=k}\phi_d(x_n)w_d-t_n\right)+\lambda=0\\ &&\Leftrightarrow w_k=\frac{\sum_{n=1}^N\phi_k(x_n)\left(t_n-w_0-\sum_{d\not=k}\phi_d(x_n)w_d\right)-\lambda}{\sum_{n=1}^N\phi_k(x_n)^2}\tag{5}\ \end{eqnarray}$

(5)は $w_k>0$ のときなので、 $w_k^+$ として書き直すと

$\begin{eqnarray} &&w_k^+=\frac{\sum_{n=1}^N\phi_k(x_n)\left(t_n-w_0-\sum_{d\not=k}\phi_d(x_n)w_d\right)-\lambda}{\sum_{n=1}^N\phi_k(x_n)^2}\tag{6}\ \end{eqnarray}$

となります。
同様に $w_k<0$ のとき、 $w_k^-$ とおくと

$\begin{eqnarray} &&w_k^-=\frac{\sum_{n=1}^N\phi_k(x_n)\left(t_n-w_0-\sum_{d\not=k}\phi_d(x_n)w_d\right)+\lambda}{\sum_{n=1}^N\phi_k(x_n)^2}\tag{7}\ \end{eqnarray}$

となります。
$w_k^+$ は $w_k>0$ を、 $w_k^-$ は $w_k<0$ を前提として計算されたものなので、
$w_k^+>0$ ならば、 $w_k^+$ に更新し、 $w_k^-<0$ ならば、 $w_k^-$ に更新します。
また $w_k^+>0$ と $w_k^-<0$ の両方を満たさないときは $w_k$ は更新しません。
まとめると、以下のようになります。
$\sum_{n=1}^N\phi_k(x_n)\left(t_n-w_0-\sum_{d\not=k}\phi_d(x_n)w_d\right)>\lambda$ なら

$\begin{eqnarray} &&w_k=\frac{\sum_{n=1}^N\phi_k(x_n)\left(t_n-w_0-\sum_{d\not=k}\phi_d(x_n)w_d\right)-\lambda}{\sum_{n=1}^N\phi_k(x_n)^2}\tag{8}\ \end{eqnarray}$

$\sum_{n=1}^N\phi_k(x_n)\left(t_n-w_0-\sum_{d\not=k}\phi_d(x_n)w_d\right)<-\lambda$ なら

$\begin{eqnarray} &&w_k=\frac{\sum_{n=1}^N\phi_k(x_n)\left(t_n-w_0-\sum_{d\not=k}\phi_d(x_n)w_d\right)+\lambda}{\sum_{n=1}^N\phi_k(x_n)^2}\tag{9}\ \end{eqnarray}$