ISTA: 反復ソフトスレショールディングアルゴリズム
アルゴリズム
$$ \argmin_{\beta} \left( {{ 1 } \over { 2 }} \left\| Y - X \beta \right\|_{2}^{2} + \lambda \left\| \beta \right\|_{1} \right) $$
上のような BPDN、あるいはラッソ回帰問題 を解く方法として、次の更新則を ISTAIterative Soft Thresholding Algorithm と呼ぶ。 $$ \beta^{(k+1)} = S_{\lambda} \left( \beta^{(k)} - \alpha X^{T} \left( X \beta^{(k)} - Y \right) \right) $$ ここで $\alpha$ はステップサイズstep size であり、ベクトル化されたvectorized ソフトスレッショルディング $S_{\lambda} : \mathbb{R}^{n} \to \mathbb{R}^{n}$ はベクトルの各成分に対して ソフトスレッショルディング $\eta_{S} \left( x ; \lambda \right)$ を適用する関数である。
説明
ISTA は プラクシマル・グラディエント・メソッド の一種で、行列代数的に容易に解ける 最小二乗法 と異なり、解を 零ベクトル の近傍で見つけたい場合に使える。
$\lambda$ が 定数 として与えられているとき、ラッソ回帰の 目的関数 $L$ を上のように表す。一般にラッソ回帰の最適解は 閉形式closed form を持たないが、 $X$ の全てのカラムが互いに 直交 すると仮定すれば、$\hat{\beta} = \argmin_{\beta} L \left( \beta \right)$ の $k$ 番目の成分 $\left( \hat{\beta} \right)_{k}$ は次のようになる。 $$ \begin{align*} \left( \hat{\beta} \right)_{k} =& {{ 1 } \over { \left( X^{T} X \right)_{kk} }} \eta_{\lambda} \left( X^{T} Y \right)_{k} \\ = & {{ 1 } \over { \left( X^{T} X \right)_{kk} }} \begin{cases} \left( X^{T} Y \right)_{k} + \lambda & , \text{if } \left( X^{T} Y \right)_{k} < - \lambda \\ 0 & , \text{if } \left( X^{T} Y \right)_{k} \in [-\lambda, \lambda] \\ \left( X^{T} Y \right)_{k} - \lambda & , \text{if } \left( X^{T} Y \right)_{k} > \lambda \end{cases} \end{align*} $$
実際、BPDN において 計画行列 が フルランク のとき、ラッソ回帰の最適解は上のように表せるし、そうでなくてもラッソ回帰を実行する手法が ISTA である。こうした理論的背景を数式的に理解することは非常に重要で、これを理解することなしに発展した FISTA を知ることはできないためだ。
導出
$S_{\lambda}$ はそれ自体が解を零ベクトルの近傍へ移す関数であり、プラクシマル演算子 を反映しているとみなせるので、BPDN では平方項である $L = \left\| Y - X \beta \right\|_{2}^{2} / 2$ に注意すればよい。
残差二乗和の勾配: $$ f \left( \mathbf{s} \right) := \left( \mathbf{y} - X \mathbf{s} \right)^{T} R \left( \mathbf{y} - X \mathbf{s} \right) $$ $\mathbf{s}$ に依存しないベクトル $\mathbf{y} \in \mathbb{R}^{n}$ と行列 $X \in \mathbb{R}^{n \times p}$、$R \in \mathbb{R}^{n \times n}$ に対して次が成り立つ。 $$ {{ \partial f \left( \mathbf{s} \right) } \over { \partial \mathbf{s} }} = - X^{T} \left( R + R^{T} \right) \left( \mathbf{y} - X \mathbf{s} \right) $$
$R = I$ の場合に上の公式を適用すると $$ \begin{align*} & {{ \partial } \over { \partial \beta }} L \\ =& {{ 1 } \over { 2 }} {{ \partial } \over { \partial \beta }} \left\| Y - X \beta \right\|_{2}^{2} \\ =& {{ \partial } \over { \partial \beta }} {{ 1 } \over { 2 }} \left( Y - X \beta \right)^{T} \left( Y - X \beta \right) \\ =& - {{ 1 } \over { 2 }} X^{T} \left( I + I^{T} \right) \left( Y - X \beta \right) \\ =& X^{T} \left( X \beta - Y \right) \end{align*} $$ であり、これ自体が 勾配 だから 勾配降下法 に当てはめると $$ \beta^{(k+1)} = \beta^{(k)} - \alpha \nabla L $$ となり、ここにベクトル化されたソフトスレッショルディングを適用すれば ISTA の更新則になる。
■