ぽんのブログ -23ページ目

ホームピグアメブロ

芸能人ブログ人気ブログ

ぽんのブログ

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

<< 前ページ次ページ >>

Lasso-Lars その７停止条件

前回 Lars の計算方法をまとめましたが、これにはどこで計算を止めるかという停止条件が含まれていません。

Larsでは、アクティブセットに全ての目的変数が含まれた時、観測値 y の推定値 μ は最小二乗解に一致します。なので

「アクティブセットに含まれる変数の数 = 全変数の数」

というのが停止条件の一つになります。

そのほかにも解 βのL1ノルムで停止させることも出来ます。
Lasso解は

$L(\lambda)=\frac{1}{2}|{\bf y}-\boldsymbol{\mu}|^2+\lambda\sum|\boldsymbol{\beta}|$

を最小化するものでしたが、これは

${\rm minimize}\, \frac{1}{2}|{\bf y}-\boldsymbol{\mu}|^2$
${\rm subject\, \, to}\, |\boldsymbol{\beta}|\leq t$

とも書き換えられます。この時βのL1ノルムの閾値 t が λ に対応する事になります。
Larsでは後者を解く事になり、解を更新していくうちβのL1ノルムが設定した閾値 t を超えたら停止する、と言う事をします。

例えば今、k回目のステップで得られた解が

$|\boldsymbol{\beta}^{(k)}|< t$

かつ、k+1回目で

$t\leq|\boldsymbol{\beta}^{(k+1)}|$

となったとします。k+1回目の解を求める為に、推定値を等角ベクトル uA に沿って

$\boldsymbol{\mu}^{(k+1)}=\boldsymbol{\mu}^{(k)}+\gamma{\bf u}_A$

と動かすので β も

式（１）
$\boldsymbol{\beta}^{(k+1)}=\boldsymbol{\beta}^{(k)}+\gamma {\bf S_A}\cdot{\bf w}_A$

と移動します。ここに

${\bf S}_A={\rm diag}({\bf s}_A)$

また sA は

$s_{Aj}={\rm sign}(\beta_j)$

なるβの符号（ = 各変数と残差の相関の符号）を並べたベクトルです。

ここで k ステップ目から k+1 ステップの間で γ は

式（２）
$0\leq \gamma\leq \gamma_{max}$

なる値を取り得ます。ここで

$\gamma_{max}=\min (\hat{\gamma},\widetilde{\gamma})$

です。で、 $|\boldsymbol{\beta}^{(k)}|< t$ 　かつ $t\leq|\boldsymbol{\beta}^{(k+1)}|$ と言う事は

$|\boldsymbol{\beta}|=t$

となるγが式（２）の範囲に居るはずです。これを γ1 とします。

式（３）
$\boldsymbol{\beta}=\boldsymbol{\beta}^{(k)}+\gamma_1{\bf S}_A\cdot{\bf w}_A$

$|\boldsymbol{\beta}|=t$

式（３）の両辺に sA を掛けると

${\bf s}_A^T\cdot\boldsymbol{\beta}=\sum{\rm sign}(\beta_j)\beta_j=|\boldsymbol{\beta}|$

なので

式（４）
$t=t_0+\gamma_1{\bf s}_A^T\cdot{\bf S}_A\cdot{\bf w}_A$

が得られます。ここに

$t_0=|\boldsymbol{\beta}^{(k)}|$

です。

さらに

${\bf w}_A=A_A{\bf g}_A^{-1}\cdot{\bf 1}_A$
$A_A=1/\sqrt{{\bf 1}_A^T\cdot{\bf g}_A^{-1}\cdot{\bf 1}_A}$
${\bf s}_A^T\cdot{\bf S}_A={\bf s}_A^T\cdot{\rm diag}({\bf s}_A)={\bf 1}_A^T$

なので

${\bf s}_A^T\cdot{\bf S}_A\cdot{\bf w}_A=A_A^{-1}$

以上より式（４）から

$\gamma_1=A_A(t-t_0)$

が導かれます。これを改めて式（３）に代入して、求めるべき β は

式（５）
$\boldsymbol{\beta}=\boldsymbol{\beta}^{(k)}+A_A(t-t_0){\bf S}_A\cdot{\bf w}_A$

と得られます（ Efron 論文の（５．１７））。

ここで γ1 は式（２）を満たす、つまり新たに要素が加えられる、或いは除かれる $\gamma_{max}$ より小さいはずなので式（５）の時のアクティブセットは k ステップ目のものと変りません。

<< 前ページ次ページ >>