Lasso-Lars その３ | ぽんのブログ

ホームピグアメブロ

芸能人ブログ人気ブログ

ぽんのブログ

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

Lasso-Lars その３

前回、Larsによる解の更新のアウトラインを説明しましたが、今回はもう少し具体的にどうやって修正量（ステップサイズ）を求めるかを説明します。

k 回目のステップで、Lasso推定値が μk、アクティブセットを Ak とすると、Ak に含まれる変数と現在の残差との相関は、前回のブログにも書いたように最大値

$\hat{C}_k=\max_j|c_{kj}|,\quad c_{kj}={\bf x}_j^T\cdot({\bf y}-\boldsymbol{\mu}_k)$
をとります。またこの時、Ak に含まれない変数 xr も上と同じ相関を持ちます。
そこで r もアクティブセットに加え

${\cal A}_{k+1}=\{{\cal A}_k\cup \{r\}\}$

とし、 Ak+1 に含まれる変数の等分角ベクトル uk+1 を求め推定値をその方向に修正します。

式（１）
$\boldsymbol{\mu}_{k+1}=\boldsymbol{\mu}_k+\gamma{\bf u}_{k+1}$

この時、Ak+1 に含まれる変数と現時点の残差 (y - μk+1) との相関は

式（２）
$|{\bf x}_j^T\cdot({\bf y}-\boldsymbol{\mu}_{k+1})|=|{\bf x}_j^T\cdot({\bf y}-\boldsymbol{\mu}_k-\gamma{\bf u}_{k+1})|=\hat{C}_k-\gamma A_{k+1},\quad j\in{\cal A}_{k+1}$

となります。ここで Ak+1 は、前々回のブログで出てきた

$A_{k+1}=({\bf 1}_{k+1}^T\cdot{\bf g}_{k+1}^{-1}\cdot{\bf 1}_{k+1})^{-1/2},\quad {\bf g}_{k+1}={\bf X}_{k+1}^T\cdot{\bf X}_{k+1}$

です。

さらに、今度は Ak+1 に含まれない変数 xs との相関は

式（３）
$c_{k+1\, s}(\gamma)={\bf x}_s^T\cdot({\bf y}-\boldsymbol{\mu}_{k+1})=c_{k s}-\gamma a_{k+1\, s},\quad s\not\in {\cal A}_{k+1}$

となります。ここに a_{ k+1 s} は

$a_{k+1\, s}={\bf x}_s^T\cdot {\bf u}_{k+1}$

また

$c_{k s}={\bf x}_s^T\cdot({\bf y}-\boldsymbol{\mu}_k),\quad s\not\in {\cal A}_{k+1}$

です。

前回のブログのように、式（１）の γ は、推定値を等分角方向に動かし、アクティブセットに含まれない変数との相関が等しくなる最小の値をとります。
式（２）と（３）について

$\hat{C}_k-\gamma A_{k+1}=c_{k+1 s}(\gamma)$

のとき

$\hat{\gamma}=\frac{\hat{C}_k-c_{k s}}{A_{k+1}-a_{k+1\, s}}$

また

$\hat{C}_k-\gamma A_{k+1}=-c_{k+1 s}(\gamma)$

のとき
$\hat{\gamma}=\frac{\hat{C}_k+c_{k s}}{A_{k+1}+a_{k+1\, s}}$

となります。
μ の修正は u の正の方向に沿った（つまりγは正で）、他の変数との相関が等しくなる最小の値なので

$\hat{\gamma}=\min_{s\not\in {\cal A}_{k+1}}^+\left\{\frac{\hat{C}_k-c_{k s}}{A_{k+1}-a_{k+1\, s}},\frac{\hat{C}_k+c_{k s}}{A_{k+1}+a_{k+1\, s}}\right\}$

となります。ここで min^+ は、正の値の最小値、の意味です。
これが推定値の更新のステップサイズで、 Efronさんたちの論文の式（２．１３）になります。