こんにちは。
前回の最後に、
– Coordinate descent(座標降下法)
– ISTA (メジャライザー最小化)
– FISTA (高速化)
の3つの最適化方法を紹介しました。今回は上の2つを解説します。そして次回実装へうつりましょう。
まずは簡単なLassoからです。
Coordinate descent
いきなり解説に入る前に何ですが、座標降下法ってメチャクチャシンプルなんですよ。
けど全く有名じゃないんですよね。(多分、理由は記事の最後)まあ、アルゴリズムみましょう
目的関数
![Rendered by QuickLaTeX.com f(x) = g(x) + \sum_{i=1}^{n} h_i(x)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-94d6ce01631413ed35d4ed571e1da125_l3.png)
の最適化を考えます。
ここで
![Rendered by QuickLaTeX.com g](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-d208fd391fa57c168dc0f151de829fee_l3.png)
はconvexかつdifferentiabl、
![Rendered by QuickLaTeX.com h_i(x)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-8d46df13c52bac041d1b08b92806bb31_l3.png)
はconvexとします。
(例えばconvexかつundifferentiablな
![Rendered by QuickLaTeX.com f(x)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-a7ee323bc5a3f73ad5e066b13bed5504_l3.png)
を考えた場合、反例があります。詳しくはREADMORE)
![Rendered by QuickLaTeX.com k=1, 2, \cdots](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-d88cfcf9c2c4551399635cc565a7267e_l3.png)
回目の更新を右肩の添え字で表すと、各変数に対して
![Rendered by QuickLaTeX.com \[x_1^{(k)} = \texttt{argmin } f(x_1, x_2^{(k-1)}, x_3^{(k-1)}, \cdots, x_n^{(k-1)})\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-a208013dfcbe0947f48a968c4a613478_l3.png)
![Rendered by QuickLaTeX.com \[x_2^{(k)} = \texttt{argmin } f(x_1^{(k-1)}, x_2, x_3^{(k-1)}, \cdots, x_n^{(k-1)})\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-3d5776006235d456d856ad651ea5b42c_l3.png)
![Rendered by QuickLaTeX.com \[x_3^{(k)} = \texttt{argmin } f(x_1^{(k-1)}, x_2^{(k-1)}, x_3, \cdots, x_n^{(k-1)})\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-7b54b8a1d060aeee6942160fb3e9021a_l3.png)
のように更新するアルゴリズムです。
Pointは1つ、変数を1つずつ更新するんです。その他の変数は定数とみるんです。なので
![](https://research.miidas.jp/wp-content/uploads/2019/02/Screen-Shot-2019-02-24-at-19.59.08.png)
この図の感じですね。しかし次の問題を考えてみましょう
![Rendered by QuickLaTeX.com x \in \mathbb{R}^2](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-2213eb168f32044ef90334df2bf38b14_l3.png)
に対して
![Rendered by QuickLaTeX.com \[\texttt{Minimize } x_1^2 + x_2^2 + 5|x_1 + x_2|\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-6546500fdca81d923c3fff02783e16a9_l3.png)
です。例えば初期値を
![Rendered by QuickLaTeX.com x=(1,-1)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-9678dcbdc2d92bdf5f693ac31281d690_l3.png)
で座標降下法をアプライしてみると
![Rendered by QuickLaTeX.com x_1, x_2](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-62b74729a67aae7b26e639b8d719c6db_l3.png)
のどちらから更新しても
![Rendered by QuickLaTeX.com x=(1,-1)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-9678dcbdc2d92bdf5f693ac31281d690_l3.png)
で停滞することがわかります。しかし
これは明らかに最適解は
![Rendered by QuickLaTeX.com x=(0,0)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-0898652a3ba3650f728158928cbe2c8d_l3.png)
ですよね。こういったことからスパースな問題にはあまり良くないようです。
次にメジャライザーの方を行きましょう。
Iterative Shrinkage Thresholding
ちなみにこのアルゴリズムは初めて聞きました。EMアルゴリズムでも似たことが行われますね。
こちらもアルゴリズムは単純で
テイラー展開を行い、目的関数を置き換えることで最適化問題を解きやすい形にしよう
というものです。
一次元の場合、
![Rendered by QuickLaTeX.com f](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-9c09a708375fde2676da319bcdfe8b24_l3.png)
を
![Rendered by QuickLaTeX.com x=a](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-2b24e8b3f28f048c85d6ea0f32d59fff_l3.png)
周りでのテイラー展開
![Rendered by QuickLaTeX.com \[f(x) \approx f(a) + f^{(1)}(a)(x-a) + \frac{1}{2!} f^{(2)}(a)(x-a)^2 + \frac{1}{3!} f^{(3)}(a)(x-a)^3 + \cdots\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-889a2ae66f0888a1db506e3258d09141_l3.png)
多次元の場合、
![Rendered by QuickLaTeX.com \[f(\vc{x})= f(x_1,x_2, \ldots, x_n)\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-6afc56b7b4c3bcd4c22486bea9206956_l3.png)
![Rendered by QuickLaTeX.com \[f(\bf{x}) \approx f(\bf{a}) + Df(\bf{a}) (\bf{x}-\bf{a}) + \frac{1}{2} (\bf{x}-\bf{a})^T Hf(\bf{a}) (\bf{x}-\bf{a})\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-5cb7c6457dfffaa557194525d8fcc835_l3.png)
下の図がイメージになります。上界というのは「より大きいやつ」という意味です。
![](https://research.miidas.jp/wp-content/uploads/2019/02/Screen-Shot-2019-02-24-at-19.58.01.png)
この図からアルゴリズムがどうやって動いて何で最適化できるのかは直感的にわかったかと思います。
しかし、このメジャライザーが本当に存在するのか?など疑問に思う人がいるでしょう。
では考察しましょう。
まず初期値を
![Rendered by QuickLaTeX.com x^{(t)}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-cc219db918034bd44c33cdc98aa176f5_l3.png)
とします。そして目的関数を
![Rendered by QuickLaTeX.com \mathcal{L}(x)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-482787a2919dd1cd6d1bd4bfa0345ce6_l3.png)
,メジャライザーを
![Rendered by QuickLaTeX.com \mathcal{T}(x)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-f0fa46260dd1d4496906bcfb6b8464cf_l3.png)
とします。
そして、メジャライザーは次のような性質を満たしてほしいです。
–
![Rendered by QuickLaTeX.com \mathcal{L}(x^{(t)}) = \mathcal{T}(x^{(t)})](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-1265249a2dd65111d521c9fc0f8545c0_l3.png)
–
![Rendered by QuickLaTeX.com \forall x\neq x^{(t)}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-1b89007f7b3bf6ce8ab0da9e12c08c1e_l3.png)
に対して
![Rendered by QuickLaTeX.com \mathcal{L}(x) \leq \mathcal{T}(x)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-16eab8925ac18264b669e7ec39451ec9_l3.png)
すると性質から明らかに
![Rendered by QuickLaTeX.com T](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-f9ed275b0bf1633b7ee83b78fcc28273_l3.png)
の最小化が
![Rendered by QuickLaTeX.com L](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-66a9f474fc3c52efdfb0ba6a70199ee8_l3.png)
の最小化に繋がることがわかります。
では実際にそんな都合のいい
![Rendered by QuickLaTeX.com \mathcal{T}(x)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-f0fa46260dd1d4496906bcfb6b8464cf_l3.png)
を探しましょう。の前にちょっと寄り道します。
どんな形のメジャライザーが都合いい?
メジャライザー
![Rendered by QuickLaTeX.com T(x)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-ace58353ecb8a323bad0e9196cd34c9b_l3.png)
を探すといえどこのままでは全くわかりません。
![Rendered by QuickLaTeX.com T(x) = x^2](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-7748a6f2dc1d6d766046c249e61c7a74_l3.png)
にすればいいのか?いや、それもわかりません。なので
都合のいいメジャライザーの形を予想します。
いきなりですが次の最適解
![Rendered by QuickLaTeX.com x](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-ede05c264bba0eda080918aaa09c4658_l3.png)
を考えましょう。次元は1です。(
![Rendered by QuickLaTeX.com \lambda \geq 0](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-21d0afe89f5d1545ccda3d2bd0d8660a_l3.png)
)
![Rendered by QuickLaTeX.com \[\texttt{argmin } \frac{1}{2} (y-x)^2 + \lambda |x|\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-776b0813cf88c9daf963324f9a6cf3bb_l3.png)
前回の記事でやったようにこれは場合分けで簡単にできますね
![Rendered by QuickLaTeX.com \forall x \geq 0](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-dadc54b741048b89b19d165833caac69_l3.png)
に対して
![Rendered by QuickLaTeX.com \[\frac{1}{2} (x^2 - 2xy + y^2 + 2\lambda x) = \frac{1}{2} (x - (y-\lambda))^2 + \texttt{const}\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-e9790eb314fc9683735f08901f8b8bf9_l3.png)
同様にして
![Rendered by QuickLaTeX.com \forall x < 0](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-72082f661a37377b29fa6062c59a6d8f_l3.png)
に対して
![Rendered by QuickLaTeX.com \[\frac{1}{2} (x - (y+\lambda))^2 + \texttt{const}\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-2576ea975b0fc8fc6d3cd88b36562870_l3.png)
では最後に
![Rendered by QuickLaTeX.com y](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-0af556714940c351c933bba8cf840796_l3.png)
の範囲で場合分けすると前回のSoft thresholding functionが出てきましたね。
![Rendered by QuickLaTeX.com \[x = S ( y, \lambda )\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-6d6dbbb30ded7c140e8e15610c006ef1_l3.png)
詳しく復習すると
![Rendered by QuickLaTeX.com y < - \lambda](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-3554b96f70187db3c6599517fe5d09cf_l3.png)
の時
![Rendered by QuickLaTeX.com \[x= y + \lambda\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-42044550dbabed3caf00f4859aa7c22d_l3.png)
![Rendered by QuickLaTeX.com - \lambda \leq y \leq \lambda](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-65752ed8bb7d737961c2a6d2f02827e0_l3.png)
の時
![Rendered by QuickLaTeX.com \[x = 0\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-f4d5e67d4db59ebeb86c661dd9eb518c_l3.png)
![Rendered by QuickLaTeX.com y > \lambda](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-5c6885159634a50128b0ce1b56c14211_l3.png)
の時
![Rendered by QuickLaTeX.com \[x = y - \lambda\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-8624504308b595bb55767e351a3997f4_l3.png)
これが大切です。
つまり平方完成して解が求まりました。
ではLassoの目的を再掲しましょう。
![Rendered by QuickLaTeX.com \[\texttt{argmin } ||y - Xb||_2^2 + \lambda|b|_1^1\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-11ac5cb3484e8c113bc242655dcbba71_l3.png)
今の例と似てますよね。
しかしここままでは平方完成できない
ここで
平方完成できるやつを考えよう!!!
これがほしいメジャライザーを予測するということです。
では元に戻って都合のいい
![Rendered by QuickLaTeX.com \mathcal{T}(x)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-f0fa46260dd1d4496906bcfb6b8464cf_l3.png)
を探しましょう。平方完成できるやるがいいんでしたね。
テイラーの2次近似の形を想像しながら
![Rendered by QuickLaTeX.com \[\mathcal{T}(\mathbf{x}) = \mathcal{L}(\mathbf{x}^{(t)}) + \frac{d\mathcal{L}(\mathbf{x}^{(t)})}{d\mathbf{x}}(\mathbf{x} - \mathbf{x}^{(t)}) + \frac{\rho}{2}\bigl\vert\mathbf{x}-\mathbf{x}^{(t)}\bigr\vert^2\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-a07b78c9f4ce05d391daa76dbd9c394b_l3.png)
という形で考えましょう、(
![Rendered by QuickLaTeX.com \frac{\rho}{2}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-960ff882f2b40412d1266a8350248e66_l3.png)
は計算の都合上のもの)そうすれば
![Rendered by QuickLaTeX.com \[= \frac{\rho}{2} \Bigl\vert \bigl( \mathbf{x}^{(t)} - \frac{1}{\rho} \frac{d\mathcal{L}(\mathbf{x}^{(t)})}{d\mathbf{x}}\bigr) - \mathbf{x} \Bigr\vert^2 + \texttt{const}\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-4061dafe930ed2a3f9ccd4ffc1166c52_l3.png)
とできますね。よって
![Rendered by QuickLaTeX.com \[\text{argmin } \Bigl(\mathcal{T}(\mathbf{x}) + \lambda |\mathbf{x}|\Bigr)\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-53b80f1d717421352503c194ffbd5d76_l3.png)
は
![Rendered by QuickLaTeX.com \[x^{(t+1)} = S \Bigl( \frac{1}{\rho} \frac{d\mathcal{L}(\mathbf{x}^{(t)})}{d\mathbf{x}}, \lambda \Bigr)\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-e602547bc759dea108ac9c9d6eadca64_l3.png)
となります。
実はまだ終わっていない
そうなんです。先ほどメジャライザーを考えたときに
![Rendered by QuickLaTeX.com \rho](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-da039068127cf2ec5fc05123d4d3546f_l3.png)
を使いましたね。
この
![Rendered by QuickLaTeX.com \rho](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-da039068127cf2ec5fc05123d4d3546f_l3.png)
を決める必要があります。メジャライザーの性質(2)から
![Rendered by QuickLaTeX.com \[\mathcal{T}(\mathbf{x}) - \mathcal{L}(\bf{x}) = \frac{1}{2} (\bf{x} - \bf{x}^{(t)})^\top (\rho I - X^TX) (\bf{x} - \bf{x}^{(t)})\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-7ac85ffcc827e9afb4115285109b5c8e_l3.png)
が「0以上」を任意の
![Rendered by QuickLaTeX.com \bf{x}](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-2a364461a90e09df7c9100ce1e738f54_l3.png)
について言える必要があるので
![Rendered by QuickLaTeX.com (\rho I - X^TX)](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-f71907a6914b07c340d6b2b16901e97f_l3.png)
が半正定値
の必要があります。つまり、
![Rendered by QuickLaTeX.com X^TX](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-45ae6e224610b89cbcb8217f0b82df04_l3.png)
の最大の固有値が
![Rendered by QuickLaTeX.com \rho](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-da039068127cf2ec5fc05123d4d3546f_l3.png)
として取りうる最小の値になります。
そこで固有値の大きさを見積れる定理があるのでそれを使いましょう。
–
Gershgorin circle theorem
–
Gershgorin’s Theorem for Estimating Eigenvalues
この定理からmaxをとることで
![Rendered by QuickLaTeX.com \[\texttt{eigenvalue } \le \max_j \sum_i\bigl\vert{\mathrm{X^\top X}}_{ij}\bigr\vert\]](https://research.miidas.jp/wp-content/ql-cache/quicklatex.com-a38448914597dde4939dd76fcbcdf83b_l3.png)
と固有値の大きさが見積もれます。
長かったですがとりあえずLassoはおしまいです。
でわ。
READMORE