Coordinate descent for lasso 1. Gauss-Seidel法

ここまで、lassoを解くためのアルゴリズムとして LARS、LARS-EN を扱ってきましたが、この他に挙げられるlasso解法の代表的なアルゴリズムの一つに coordinate descent とよばれるものがあります。
今回はこちらのアルゴリズムについて書きたいと思います。

参考文献としては Friedman et al., 2011 が挙げられるでしょうか。

さて、この coordinate descent アルゴリズムですが、有名な glmnet でも使われているそうです。
基本的な考え方は Gauss-Seidel法という連立方程式の解法と同じだそうです。

今、線形方程式

${\bf y}={\bf X}\boldsymbol{\beta}$

を考え、以下の目的関数を最小にする解を求めるものとします。

$L(\boldsymbol{\beta})=||{\bf y}-{\bf X}\boldsymbol{\beta}||^2$

Gauss-Seidel法では β の各要素を、勾配を使って一つづつ更新してゆきます。
今着目する $\beta_j$ についての目的関数の勾配

$\frac{\partial L}{\partial \beta_j}=-{\bf x}_j^T({\bf y}-{\bf X}\boldsymbol{\beta})$
についての極値で　 $\beta_j$ を更新します。つまり

$\frac{\partial L}{\partial \beta_j}=-{\bf x}_j^T({\bf y}-{\bf X}\boldsymbol{\beta}^{(j)}-{\bf x}_j\beta_j)=0$

から

式（１）
$\beta_j=\frac{{\bf x}_j^T({\bf y}-{\bf X}\boldsymbol{\beta}^{(j)})}{{\bf x}_j^T{\bf x}_j}$

とします。ここで

$\boldsymbol{\beta}^{(j)}=(\beta_1,\cdots,\beta_{j-1},0,\beta_{j+1}\cdots)$

で、β から β_j を除いたものです。

式（１）はつまり、着目する解以外を固定した場合の目的関数の勾配で解を更新する、即ち着目する解以外を固定したときの目的関数の断面（プロファイル）の極小値で解を置き換える事になります。

Gauss-Seidel法では、全ての j について式（１）で更新し、これを解が収束するまで続けます。

さて、次に以下の L2 正則化問題を考えます。

${\bf b}={\bf Z}\boldsymbol{\beta},\quad {\bf b}=\begin{pmatrix} {\bf y}\\ {\bf 0} \end{pmatrix},\quad {\bf Z}=\begin{pmatrix} {\bf X}\\ \sqrt{\lambda_2}{\bf E} \end{pmatrix}$

この場合も式（１）と同様、β_j は

$\beta_j=\frac{{\bf z}_j^T({\bf b}-{\bf Z}\boldsymbol{\beta}^{(j)})}{{\bf z}_j^T{\bf z}_j}$

で更新されます。 x_j が規格化されていれば z_j^T z_j = 1+λ2 なので

式（２）
$\beta_j=\frac{{\bf z}_j^T({\bf b}-{\bf Z}\boldsymbol{\beta}^{(j)})}{1+\lambda_2}$

となります。式（２）をさらに書き下すと

$\beta_j=\frac{{\bf x}_j^T{\bf y}-{\bf x}_j^T{\bf X}\boldsymbol{\beta}^{(j)}-\lambda_2{\bf e}_j{\bf E}\boldsymbol{\beta}^{(j)}(=0)}{1+\lambda_2} =\frac{{\bf x}_j^T({\bf y}-{\bf X}\boldsymbol{\beta}^{(j)})}{1+\lambda_2}$

となります。

ぽんのブログ

自分用の備忘録ブログです。書いてある内容、とくにソースは、後で自分で要点が分かるよう、かなり簡略化してます（というか、いい加減）。あまり信用しないように（汗

Coordinate descent for lasso 1. Gauss-Seidel法