Published on

LARSアルゴリズムでLasso解を求める

Authors

はじめに

LARSを説明した記事のつづきです。

LARSアルゴリズムとLasso解

β^\hat{\boldsymbol{\beta}} をLasso解とすると、非ゼロ要素 β^j\hat{\beta}_j の符号と残差との相関 c^j=xT(y−μ^)\hat{c}_j = \boldsymbol{x}^{\mathsf{T}}\left(\boldsymbol{y} - \hat{\boldsymbol{\mu}}\right) との符号は一致している必要がある。

sign(β^j)=sign(c^j)=sj    ⋯(∗)\text{sign}(\hat{\beta}_j) = \text{sign}(\hat{c}_j) = s_j \ \ \ \ \cdots (*)

しかし、LARSアルゴリズムは (∗)(*) を必ず満たすとは言えない。d^j=sjwAj\hat{d}_j = s_j w_{\mathcal{A}j} とする(wA\boldsymbol{w}_{\mathcal{A}} 等については前回を参照)と βj\beta_j は

βjnew=β^j+γd^j\beta_j^{new} = \hat{\beta}_j + \gamma \hat{d}_j

で更新されるので、βjnew\beta_j^{new} の符号が変わるのは

γj=−β^jd^j\gamma_j = - \frac{\hat{\beta}_j}{\hat{d}_j}

のタイミングで、最初にそのような変化が起こるのは

γ~=min⁡γj>0{γj}\tilde{\gamma}=\min _{\gamma_{j}>0}\left\{\gamma_{j}\right\}

が γ^\hat{\gamma} よりも小さくなるとき。このとき、(∗)(*) を満たせなくなるのでLARSアルゴリズムの解であってもLasso解ではなくなる。

修正版LARS

もし、γ~<γ^\tilde{\gamma} < \hat{\gamma}なら、予測値ベクトル等の更新に γ~\tilde{\gamma} を使い、

μ^new=μ^+γ~uA\hat{\boldsymbol{\mu}}^{new} = \hat{\boldsymbol{\mu}} + \tilde{\gamma} \boldsymbol{u}_{\mathcal{A}}

次のステップで説明変数 j~\tilde{j} を A\mathcal{A} から除いてequiangular vectorを計算、各値を更新すれば良い。こうすることでLasso解を求めることがでる。

Pythonによるフルスクラッチ実装

実装に関しては前回の実装を少しだけ変更すれば良い。Github (minatosato/Lasso)にアップロードしたので参考にしてください。

圧倒的参考資料