スパース構造正則化
最近、スパース正則化に構造的な事前情報を取り入れる事が良く行われています。
例えば、ゲノム解析において類似した性質を持つ遺伝子グループが存在する、画像解析では画像内に同じ色で塗りつぶされた領域が混在する…
このように解析対象が或る種の「構造」を持っていることが既知な場合に、それを事前情報としてスパース正則化に取り入れる、というテーマがこれまで考察されてきました。
その方法として古典的なものの一つにgroup lassoが有ります。これはモデル要素が(既知の遺伝子グループのように)いくつかの群に分けられる事が分かっている場合に、それぞれの群の要素をひとまとめにして正則化を施す、という方法です。しかしこの方法は、どのモデル要素がどの群に属するかが既知でなければ適用できません。
解析対象が、ある種ブロック的な構造を持つことが事前に分かっている（但しそれぞれのブロックのextentは未知）場合によく用いられるのが以下のFused Lassoと呼ばれる正則化法です。
(式1)
これは最適化により最小にすべき目的関数を表します。ここで f(β) は損失関数、βはモデルベクトルです。
この式の第3項のように、Fused lassoでは隣り合うモデル要素同士の差についてL1正則が施されます。L1ノルムをL0ノルムのalternativeと解釈すると、これは「モデル要素の値が急変する（不連続になる）箇所の個数が小さくなる」ような拘束がかけられる事となり、結果得られるモデルはブロック状の構造を持つことが分かります。
Coordinate Descent (Friedman et al.,2007)
このFused Lassoの解法として Friedmanさん達の一連の論文で提案されている Coordinate Descent Algorithm (CDA: 座標降下法)が挙げられます。ちなみにCDAは、有名なglmnetで使われており、その詳細については以前のブログ記事でも取り上げています。なのでここでは詳細は省きますが、要は
「各モデルベクトル要素 毎について目的関数の1次元最適化を延々と繰り返す」
というものです。
例えば、2次元の目的関数(正則化なし)
について考えます。横軸x、縦軸yにとったLの等高線は下図のようになりますが、最適解は(x, y)=(-2.5, 2.5)の赤丸の点です。これを(5.0, -7.5)の青丸を初期値として解く事を考えます。
CDAでは、ある変数、例えば y に着目し、それ以外の変数(x)を固定したLを y の一次関数として最適化 (y = y')、続いて今度は y を y = y'と固定し、L(x, y') を x の変数として最適化…を繰り返します。
上の図の目的関数の場合、y、xについて図の様に一次元の最適化を繰り返す事で最適解に達することが出来ました。
一般に目的関数が狭義凸関数、もしくは凸関数の場合にCDAは最適解に達することが出来ることが保証されています（Tseng, 2000）
ここで次に、以下の正則化項( P(β) )が加わった目的関数を考えます。
ここでλは正則化パラメータです。
もし
f(β) が凸関数
P(β)が分離可能で凸関数
な場合、CDAで最適解に到達することが出来ることが保証されます (Tseng, 2002)。
ここで分離可能(separable)であるとは
の様にP(β)がβの各要素 の各々についてのみの関数 p(βj) の足し合わせで表される事を意味します。
L1正則の場合
なので分離可能、また
の絶対値関数は β=0 で滑らかではないですが凸です。従ってf(β) が凸関数ならCDAでLasso解を得られることが保証されます。
Fused LassoとCDA
しかし式(1)のFused項
については、絶対値関数なので凸ですが、分離可能ではありません。従ってCDAで最適解が得られる保証はありません。
実際、次のような2次元のFused Lassoの場合を考えます。
この目的関数の等高線は
こんな感じになります。先ほどと同じく(x, y) = (5.0, -7.5) をスタートとしてCDAを適用することを考えます。
まずxを固定しyについて最適化すると y=0 が得られます。次に L(x, y=0)をxについて最適化すると x = 0 が得られます。
結局 (x, y) = (0, 0) が得られましたが、これは真の最適解 (x, y) = (-2.5, 2.5) の赤丸の点とは異なったものとなっています。
このように、Fused Lassoの場合（ペナルティが分離可能ではないので）CDAでは最適解とは異なる解でスタックしてしまい、真の解が得られない可能性が指摘されています。
その解決策として Friedman et al. 2007 ではCDAのアルゴリズムにちょっとした変更を加えることを提案しています。が、このブログではそれについての説明は省きます（興味のある方は元論文を参照してください）。
この様に、CDAはglmnetでも使われているとおり優秀なアルゴリズムであることに違いないのですが、構造正則化の場合に必ずしも適用可能とはなりません。
次以降の記事では、Fused Lasso及びGeneralized Lassoと呼ばれる構造正則化問題の解法として提案されているいくつかの方法(FISTA, ADMM)についてまとめてゆきたいと思っています。