こんにちは。
前回の最後に、
– Coordinate descent(座標降下法)
– ISTA (メジャライザー最小化)
– FISTA (高速化)
の3つの最適化方法を紹介しました。今回は上の2つを解説します。そして次回実装へうつりましょう。
まずは簡単なLassoからです。
Coordinate descent
いきなり解説に入る前に何ですが、座標降下法ってメチャクチャシンプルなんですよ。
けど全く有名じゃないんですよね。(多分、理由は記事の最後)まあ、アルゴリズムみましょう
目的関数の最適化を考えます。
ここではconvexかつdifferentiabl、
はconvexとします。
(例えばconvexかつundifferentiablなを考えた場合、反例があります。詳しくはREADMORE)
回目の更新を右肩の添え字で表すと、各変数に対して
のように更新するアルゴリズムです。
Pointは1つ、変数を1つずつ更新するんです。その他の変数は定数とみるんです。なので
この図の感じですね。しかし次の問題を考えてみましょうに対して
です。例えば初期値をで座標降下法をアプライしてみると
のどちらから更新しても
で停滞することがわかります。しかし
これは明らかに最適解はですよね。こういったことからスパースな問題にはあまり良くないようです。
次にメジャライザーの方を行きましょう。
Iterative Shrinkage Thresholding
ちなみにこのアルゴリズムは初めて聞きました。EMアルゴリズムでも似たことが行われますね。
こちらもアルゴリズムは単純で
というものです。
一次元の場合、を
周りでのテイラー展開
多次元の場合、
下の図がイメージになります。上界というのは「より大きいやつ」という意味です。
この図からアルゴリズムがどうやって動いて何で最適化できるのかは直感的にわかったかと思います。
しかし、このメジャライザーが本当に存在するのか?など疑問に思う人がいるでしょう。
では考察しましょう。
まず初期値をとします。そして目的関数を
,メジャライザーを
とします。
そして、メジャライザーは次のような性質を満たしてほしいです。
–
– に対して
すると性質から明らかにの最小化が
の最小化に繋がることがわかります。
では実際にそんな都合のいいを探しましょう。の前にちょっと寄り道します。
どんな形のメジャライザーが都合いい?
メジャライザーを探すといえどこのままでは全くわかりません。
にすればいいのか?いや、それもわかりません。なので
いきなりですが次の最適解を考えましょう。次元は1です。(
)
前回の記事でやったようにこれは場合分けで簡単にできますね
に対して
同様にしてに対して
では最後にの範囲で場合分けすると前回のSoft thresholding functionが出てきましたね。
詳しく復習すると
の時
の時
の時
これが大切です。
ではLassoの目的を再掲しましょう。
今の例と似てますよね。
ここで
これがほしいメジャライザーを予測するということです。
では元に戻って都合のいいを探しましょう。平方完成できるやるがいいんでしたね。
テイラーの2次近似の形を想像しながら
という形で考えましょう、(は計算の都合上のもの)そうすれば
とできますね。よって
は
となります。
そうなんです。先ほどメジャライザーを考えたときにを使いましたね。
このを決める必要があります。メジャライザーの性質(2)から
が「0以上」を任意のについて言える必要があるので

の必要があります。つまり、の最大の固有値が
として取りうる最小の値になります。
そこで固有値の大きさを見積れる定理があるのでそれを使いましょう。
– Gershgorin circle theorem
– Gershgorin’s Theorem for Estimating Eigenvalues
この定理からmaxをとることで
と固有値の大きさが見積もれます。
長かったですがとりあえずLassoはおしまいです。
でわ。