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

ホームピグアメブロ

芸能人ブログ人気ブログ

ぽんのブログ

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

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

LassoLars その１４ larsen アルゴリズムの詳細

Elatsic netではL2正則化項が、単位行列を E として

$P_2(\boldsymbol{\beta},\lambda_2)=\lambda_2\boldsymbol{\beta}^T\mathbf{E}^T\mathbf{E}\boldsymbol{\beta}$

という形をしていました。この E を任意の線形オペレータ J に置き換えた場合を考えます。
従って求める β は

$\mathop\textrm{arg min}\limits_{\beta} ||{\bf y}-\bf{X}\boldsymbol{\beta}||^2+\lambda_2\boldsymbol{\beta}^T{\bf J}^T{\bf J}\boldsymbol{\beta}$
$\textrm{subject to}\sum_j|\beta_j|<t$
となります。ここに

$[p_J,p]=\mathrm{dim}({\bf J})$

即ち J の行数を p_J とします。

これは

${\bf b}=\zeta\left( \begin{array}{c} {\bf y}\\ {\bf 0} \end{array} \right ),\quad {\bf Z}=\zeta\left( \begin{array}{c} {\bf X}\\ {\bf \sqrt{\lambda_2}{\bf J}} \end{array} \right )$

として

$\mathop\textrm{arg min}\limits_\beta ||{\bf b}-{\bf Z}\boldsymbol{\beta}||^2,$
$\textrm{subject to}\sum_j|\beta_j|<t$
なる β を求める事になります。

１．等角ベクトル (equiangular vector) u
LARS-ENアルゴリズムでは、イテレーション毎に解 β は修正方向 w に対し

式（１）
$\boldsymbol{\beta}'=\boldsymbol{\beta}+\gamma{\bf w}$

と更新されます。ここに γ は修正量を表します。よって b の推定値 ν は

$\boldsymbol{\nu}'={\bf Z}\boldsymbol{\beta}+\gamma{\bf Z}{\bf w} =\boldsymbol{\nu}+\gamma{\bf Z}{\bf w}$

と更新されます。従って等角ベクトルは n + p_J 次元のベクトル

${\bf u}={\bf Z}{\bf w}$

となります。

ところで式（１）の β は、アクティブセット A に含まれる要素しか変化しません。
なぜならアクティブセットに含まれない β の要素は

$\beta_{j\in A_c}=0$

だからです。なので w も

$w_j=\left\{ \begin{array}{cl} w_j & (j\in A)\\ 0 & (j \not\in A) \end{array} \right.$

となります。以後この　w　の非ゼロ部分を w_A と書きます。
w_A は

${\bf w}_A'=({\bf Z}_A^T{\bf Z}_A)^{-1}{\bf s}_A,\quad {\bf w}_A={\bf w}_A'/\sqrt{{\bf s}_A^T{\bf w}_A'}$

で求められます。ここに Z_A はmatlab風に書くと Z(:, A) です。また

${\bf s}_A=\mathrm{sign}({\bf c}_A)$

また c_A は後に出てくる残差と目的変数の相関（内積）です。

すると u は

式（２）
${\bf u}={\bf Z}_A{\bf w}_A(+{\bf Z}_{A_c}{\bf w}_{A_c}=0)= \zeta\left( \begin{array}{c} {\bf X}_A\\ \sqrt{\lambda_2}{\bf J}_A \end{array} \right){\bf w}_A$

なる n + p_J 次元ベクトルとなります。

２．解及び b の推定値 ν の更新
u により b の推定値 ν は

$\boldsymbol{\nu}'=\boldsymbol{\nu}+\gamma{\bf u} =\left( \begin{matrix} \boldsymbol{\mu}'\\ \zeta\sqrt{\lambda_2}{\bf J}\boldsymbol{\beta}' \end{matrix} \right)$

と更新されます。ここに

$\boldsymbol{\mu}'=\boldsymbol{\mu}+\gamma\zeta{\bf X}_A{\bf w}_A$

は y の推定値です。

３．ステップサイズの更新
ステップサイズ γ の計算には

${\bf a}={\bf Z}^T{\bf u}$

が必要になりますが、これは式（２）から

${\bf a}=\zeta^2({\bf X}^T{\bf X}_A+\lambda_2{\bf J}^T{\bf J}_A){\bf w}_A$

で計算できます。
因みに γ の計算には a(Ac) しか参照されないので J = E （elastic net）の場合には

${\bf a}=\zeta^2{\bf X}^T{\bf X}_A{\bf w}_A$

だけ計算しておけば足ります（逆に J != E なら（J によっては）後ろの部分も計算しなければなりません）。

４． Cholesky 分解の更新
γ の更新結果からアクティブセット A も更新されます。 w_A を求める際の

${\bf (Z}_A^T{\bf Z}_A)^{-1}$

の計算にCholesky分解を用いている場合、cholinsert / delete アルゴリズムを用いる事で計算の大幅な効率化が図れます。

今 j を新たにアクティブセットに加えるものとします。
この時

${\bf Z}_{A+j}=({\bf Z}_A, {\bf z}^T_j) =\zeta\left( \begin{matrix} {\bf X}_A & {\bf x}^T_j\\ \sqrt{\lambda_2}{\bf J}_A & \sqrt{\lambda_2}{\bf J}_j \end{matrix} \right)$
なので

${\bf Z}_{A+j}^T{\bf Z}_{A+j} =\zeta^2\left( \begin{matrix} {\bf X}_A^T{\bf X}_A+\lambda{\bf J}_A^T{\bf J}_A & {\bf X}_A^T{\bf x}^T_j+\lambda{\bf J}_A^T{\bf J}_j\\ {\bf x}_j{\bf X}_A+\lambda{\bf J}_j^T{\bf J}_A & {\bf x}_j{\bf x}^T_j+\lambda{\bf J}_j^T{\bf J}_j \end{matrix} \right)$

つまりベクトル

${\bf t}=\zeta^2\left( \begin{matrix} {\bf X}_A^T{\bf x}^T_j+\lambda{\bf J}_A^T{\bf J}_j\\ {\bf x}_j{\bf x}^T_j+\lambda{\bf J}_j^T{\bf J}_j \end{matrix} \right)$

を cholinsert すれば良い事となります。

また要素を除く場合は普通に choldelete すれば良いです。

５．Correlation の計算
b とその推定値 ν との残差 r = b - ν と説明変数との相関 c は

${\bf c}={\bf Z}^T({\bf b}-\boldsymbol{\nu})=\zeta({\bf X}^T\, \sqrt{\lambda_2}{\bf J}^T) \left( \begin{matrix} {\bf y}-\boldsymbol{\mu}\\ {\bf 0}-\zeta\sqrt{\lambda_2}{\bf J}\boldsymbol{\beta} \end{matrix} \right)$
即ち

${\bf c}=\zeta{\bf X}^T({\bf y}-\boldsymbol{\mu})-\zeta^2\lambda_2{\bf J}^T{\bf J}\boldsymbol{\beta}$

で計算できます。

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