こんにちは。
その1でラッソの概要と大きな特徴であるスパース性を確認しました。
今回からはラッソ実装に向けて数学を頑張りましょう。
Notationのについて
- Obj (objective function)
- OLS (Ordinary least squares) (回帰の残差平方和)
: データ数
: 次元(特徴)
:
番目の特徴
:
番目の観測データ
のうち
に対応するもの
目的関数について
今回、つまりラッソの目的関数は以下の通り
(OLS)の勾配について
上の目的関数は微分できません。なのでひとまず置いておいて
OLSをいつも通り微分して微分を計算します。
後々のため、今回は勾配でなく、での微分を計算します。
簡単のためこれを次のように表します。
L1-normの微分について
-normは微分できないとわかりました。なので
微分できるように、微分という概念を拡張します。そこで出てくるのが
です。wikiのリンク
定義(劣微分)
Convex の点
における劣微分は次の条件を満たす
で定義する。
(簡単のためについてはなし、微分の代わりに勾配という言葉を使っている)
書き換えると
における劣勾配は次の閉区間の集合である。
これが勾配の拡張になっていることは微分可能な点においてその劣勾配が一点集合になることからわかる
実はこれは簡単で、場合分けして綺麗に微分できるところの間を1つの微分の集合と見るのです。
今回のノルム、つまり
を例にとると、
(1)
(2)
そしてこの間の集合を0での微分とするのが劣勾配
(3)
次のはイメージ図
ではこの劣勾配を使って今回の目的関数の第2項を微分してゼロとおきます。
(4)
(5)
ここで先ほどと同様に場合分けを行って
(6)
(7)
そして、
(8)
ですね。文字が多くなってしまったので再確認ですが、目標はを求めることです。上の2つの式は簡単に求まりますが、3つ目の式については閉区間に0が含まれるという条件で考えましょう。なので
(9)
(10)
(11)
なので
(12)
まとめると
(13)
(14)
(15)
となります。ちなみにこの場合分けからSoft thresholding functionという関数が定義されます。
最後に劣微分と一緒にplotを見てみましょう。
微分できなくてよく使う関数をたまたま思い出しました。ニューラルネットワークで使うRELU fucntionですね。
– 活性化関数ReLUとその類似関数
他にも色々あるようです。
色々計算づくしでしたが微分を計算できました。あとは最適化のみですが今までは勾配法を使っていましたが「微分不可能な場合は勾配法は無理」なので他の最適化法が必要です。そこでLassoの問題ではいくつかのメジャーな方法があります。
- Coordinate descent(座標降下法)
- ISTA (メジャライザー最小化)
- FISTA (高速化)
です。もっとも簡単なのは座標降下法です。メジャライザーはテイラー展開を用いて上界を扱うものですがこれらについては次回解説します。
でわ。