構造的スパース性正則化

損失関数を持つ線形カーネル正則化経験的リスク最小化問題を考える${\displaystyle V(y_{i},f(x))}$ そして$\displaystyle \ell _{0}}$正則化ペナルティとしての「ノルム」：

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},\langle w,x_{i}\rangle )+\lambda \|w\|_{0},}$

どこ${\displaystyle x,w\in \mathbb {R^{d}} }$、 そして${\displaystyle \|w\|_{0}}$は$\displaystyle \ell _{0}}$ベクトルの非ゼロ要素の数として定義される「ノルム」${\displaystyle w}$。${\displaystyle f(x)=\langle w,x_{i}\rangle }$は疎で あると言われます。${\displaystyle \|w\|_{0}=s<d}$つまり、出力は${\displaystyle Y}$入力変数の小さなサブセットによって記述できる。

より一般的には、辞書を仮定します。${\displaystyle \phi _{j}:X\rightarrow \mathbb {R} }$と${\displaystyle j=1,...,p}$ 目的関数が与えられている${\displaystyle f(x)}$学習問題に関する記述は次のように表すことができます。

${\displaystyle f(x)=\sum _{j=1}^{p}\phi _{j}(x)w_{j}}$、${\displaystyle \forall x\in X}$

の$\displaystyle \ell _{0}}$規範${\displaystyle \|f\|_{0}=\|w\|_{0}}$ 非ゼロ成分の数として${\displaystyle w}$は次のように定義される。

${\displaystyle \|w\|_{0}=|\{j|w_{j}\neq 0,j\in \{1,...,p\}\}|}$、 どこ${\displaystyle |A|}$集合の濃度${\displaystyle A}$。

${\displaystyle f}$は疎であると言われます。${\displaystyle \|f\|_{0}=\|w\|_{0}=s<d}$。

しかし、$\displaystyle \ell _{0}}$正則化のノルムは疎な解を好むが、計算が難しく、さらに凸ではない。疎な解を好む計算上より実行可能なノルムは、$\displaystyle \ell _{1}}$ノルム。これは、より疎な解を依然として優先することが示されており、さらに凸である。^{[ 4 ]}

構造化スパース性正則化は、スパース性正則化の特徴である変数選択問題を拡張し、一般化したものである。^{[ 2 ] [ 3 ]}上記の正則化された経験的リスク最小化問題を、一般的なカーネルとそれに関連する特徴マップを用いて考えてみよう。${\displaystyle \phi _{j}:X\rightarrow \mathbb {R} }$と${\displaystyle j=1,...,p}$。

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},\langle w,\Phi (x_{i})\rangle )+\lambda \|w\|_{0},}$

正則化項${\displaystyle \lambda \|w\|_{0}}$それぞれに罰を与える${\displaystyle w_{j}}$コンポーネントごとに独立して、つまり、アルゴリズムは入力変数を互いに独立して抑制します。

状況によっては、正則化プロセスにさらに構造を持たせたい場合があります。例えば、入力変数をあらかじめ定義されたグループに従って抑制するといったことが可能です。構造化スパース性正則化手法を用いることで、正則化項を定義するノルムに構造を追加し、このような構造を導入することができます。

重複しないグループのケースは、構造的スパース性の最も基本的な例です。この場合、係数ベクトルの事前分割が行われます。${\displaystyle w}$で${\displaystyle G}$重複しないグループを仮定する。${\displaystyle w_{g}}$グループ内の係数のベクトルとする${\displaystyle g}$正則化項とその群ノルムを次のように定義できます。

${\displaystyle \lambda R(w)=\lambda \sum _{g=1}^{G}\|w_{g}\|_{g}}$、

どこ${\displaystyle \|w_{g}\|_{g}}$グループ$\displaystyle \ell _{2}}$規範${\displaystyle \|w_{g}\|_{g}={\sqrt {\sum _{j=1}^{|G_{g}|}(w_{g}^{j})^{2}}}}$、 ${\displaystyle G_{g}}$グループです${\displaystyle g}$、 そして${\displaystyle w_{g}^{j}}$はグループのj 番目の成分です${\displaystyle G_{g}}$。

上記のノルムはグループLassoとも呼ばれます。^{[ 2 ]}この正則化は、個々の係数ではなく、係数グループ全体をゼロに強制します。グループは重複しないため、ゼロでない係数のセットは、ゼロに設定されなかったグループの和集合として得られ、ゼロ係数のセットについてはその逆になります。

重複するグループとは、変数が複数のグループに属することができる構造スパース性のケースである。${\displaystyle g}$このケースは、重複しないグループよりも一般的な変数間の関係を表すことができるため、ツリー構造や他のタイプのグラフなど、興味深い場合が多い。^{[ 3 ] [ 8 ]}

重複するグループスパース性正則化手法には2種類あり、それぞれ異なるタイプの入力変数間の関係をモデル化するために使用されます。

グループラッソを用いた目的関数は、一般的に凸関数である必要があるが必ずしも強凸関数である必要はない誤差関数とグループから構成される。$\displaystyle \ell _{1}}$正則化項。この目的関数の問題点は、凸関数ではあるが必ずしも強凸関数ではないため、一般的に一意解が得られないことである。^{[ 9 ]}

この問題を解決する方法の一例として、2乗を導入することが挙げられます。$\displaystyle \ell _{2}}$重みベクトルのノルムを、追加の正則化項として保持しながら、$\displaystyle \ell _{1}}$グループラッソアプローチからの正則化項。^{[ 9 ]}二乗の係数が $\displaystyle \ell _{2}}$ノルム項はより大きい${\displaystyle 0}$すると、二乗 $\displaystyle \ell _{2}}$ノルム 項が強凸であれば、結果として得られる目的関数も強凸となる。^{[ 9 ]}$\displaystyle \ell _{2}}$係数が十分に小さいが正である場合、結果として得られる目的関数を最小化する重みベクトルは、一般的に、グループを削除することによって得られる目的関数を最小化する重みベクトルに非常に近いものとなる。 $\displaystyle \ell _{2}}$正則化項は元の目的関数から完全に除外されます。後者のシナリオはグループLassoアプローチに対応します。^{[ 9 ]}したがって、このアプローチはスパース性を維持しながら、より単純な最適化を可能にします。^{[ 9 ]}

参照：劣モジュラ集合関数

上記で説明した規範に加えて、構造化スパース性手法で使用される他の規範には、階層規範とグリッド上で定義された規範があります。これらの規範は劣モジュラ関数から生じ、入力変数の構造に関する事前仮定を組み込むことができます。階層規範の文脈では、この構造は変数上の有向非巡回グラフとして表現できますが、グリッドベースの規範の文脈では、構造はグリッドを使用して表現できます。^{[ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ]}

入力変数の最適なサブセットを選択する問題は、ペナルティフレームワークの下で自然に次のように定式化できます。^{[ 4 ]}

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},w,x_{i})+\lambda \|w\|_{0},}$

どこ${\displaystyle \|w\|_{0}}$は$\displaystyle \ell _{0}}$ベクトルの非ゼロ要素の数として定義される「ノルム」${\displaystyle w}$。

この定式化はモデリングの観点からは理にかなっているが、変数のすべての可能な部分集合を評価する網羅的探索に相当するため、計算上は実行不可能である。^{[ 4 ]}

最適化問題を解決するための主なアプローチは、1)統計学における段階的回帰や信号処理におけるマッチング追跡などの貪欲法、および 2) 凸緩和定式化アプローチと近接勾配最適化法の 2 つです。

最良部分集合選択問題の自然な近似は、$\displaystyle \ell _{1}}$ノルム正則化: ^{[ 4 ]}

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},w,x_{i})+\lambda \|w\|_{1}}$

このようなスキームは、ベース追跡またはLassoと呼ばれ、$\displaystyle \ell _{0}}$凸関数で微分不可能な関数の「ノルム」$\displaystyle \ell _{1}}$標準。

近接勾配法（前方後方分割法とも呼ばれる）は、凸関数で微分可能な部分と、凸関数で微分不可能な可能性のある部分を持つ関数を最小化するのに役立つ最適化手法である。

そのため、近接勾配法は、次の形式のスパース性および構造的スパース性正則化問題の解決に役立ちます^{[ 9 ] 。}

${\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},w,x_{i})+R(w)}$

どこ${\displaystyle V(y_{i},w,x_{i})}$は、二次損失のような凸かつ微分可能な損失関数であり、${\displaystyle R(w)}$は、凸で微分不可能な正則化項である。$\displaystyle \ell _{1}}$標準。

構造化スパース性正則化は、多重カーネル学習の文脈で適用できます。^{[ 16 ]}多重カーネル学習とは、事前に定義されたカーネルのセットを使用し、アルゴリズムの一部としてカーネルの最適な線形または非線形の組み合わせを学習する一連の機械学習手法を指します。

上記のアルゴリズムでは、空間全体が一度に考慮され、グループ、つまり部分空間に分割されました。補完的な観点として、異なる空間が結合されて新しい空間が得られる場合を考えてみましょう。この考え方を有限辞書で考えると便利です。線形独立な要素を持つ有限辞書（これらの要素は原子とも呼ばれます）は、線形独立な基底関数の有限集合を指し、それらの線形結合が仮説空間を定義します。有限辞書は、後述するように、特定のカーネルを定義するために使用できます。^{[ 16 ]}この例では、1 つの辞書だけでなく、複数の有限辞書が考慮されると仮定します。

簡略化のため、辞書が2つしかない場合${\displaystyle A=\{a_{j}:X\rightarrow \mathbb {R} ,j=1,...,p\}}$そして${\displaystyle B=\{b_{t}:X\rightarrow \mathbb {R} ,t=1,...,q\}}$どこ${\displaystyle q}$そして${\displaystyle p}$は整数であり、考慮されます。${\displaystyle A}$原子も同様に${\displaystyle B}$は線形独立であると仮定する。${\displaystyle D=\{d_{k}:X\rightarrow \mathbb {R} ,k=1,...,p+q\}=A\cup B}$2つの辞書の和集合とする。関数の線形空間を考える。${\displaystyle H}$次の形式の線形結合で与えられる

${\displaystyle f(x)=\sum _{i=1}^{p+q}{w^{j}d_{j}(x)}=\sum _{j=1}^{p}{w_{A}^{j}a_{j}(x)}+\sum _{t=1}^{q}{w_{B}^{t}b_{t}(x)},x\in X}$

いくつかの係数ベクトルについて$${\displaystyle w_{A}\in \mathbb {R} ^{p},w_{B}\in \mathbb {R} ^{q}}$$、 どこ${\displaystyle w=(w_{A},w_{B})}$原子は${\displaystyle D}$線形独立性を維持する、あるいは同等に、マップ${\displaystyle w=(w_{A},w_{B})\mapsto f}$は1対1です。空間内の関数${\displaystyle H}$は、空間内の 2 つの成分の合計として見なすことができる。${\displaystyle H_{A}}$原子の線形結合 ${\displaystyle A}$そして1つは${\displaystyle H_{B}}$原子の線形結合${\displaystyle B}$。

この空間における規範の選択肢の一つは${\displaystyle ||f||=||w_{A}||+||w_{B}||}$. 今は表示できることに注意してください${\displaystyle H}$関数空間として ${\displaystyle H_{A}}$、 ${\displaystyle H_{B}}$これらは部分空間である。線形独立性の仮定を考慮すると、${\displaystyle H}$識別できる${\displaystyle \mathbb {R} ^{p+q}}$そして${\displaystyle H_{A},H_{B}}$と${\displaystyle \mathbb {R} ^{p},\mathbb {R} ^{q}}$それぞれ。上記の規範は、グループ規範と見なすことができる。 ${\displaystyle H}$部分空間に関連付けられている ${\displaystyle H_{A}}$、 ${\displaystyle H_{B}}$構造的スパース性正則化との関連性を提供する。

ここ、${\displaystyle H_{A}}$、 ${\displaystyle H_{B}}$そして${\displaystyle H}$対応する特徴マップを持つ再生核ヒルベルト空間と見なすことができる${\displaystyle \Phi _{A}:X\rightarrow \mathbb {R} ^{p}}$によって与えられた${\displaystyle \Phi _{A}(x)=(a_{1}(x),...,a_{p}(x))}$、${\displaystyle \Phi _{B}:X\rightarrow \mathbb {R} ^{q}}$によって与えられた${\displaystyle \Phi _{B}(x)=(b_{1}(x),...,b_{q}(x))}$、 そして${\displaystyle \Phi :X\rightarrow \mathbb {R} ^{p+q}}$連結によって与えられる${\displaystyle \Phi _{A},\Phi _{B}}$、 それぞれ。

このシナリオに対する構造化スパース性正則化アプローチでは、グループノルムが考慮する関連変数グループは部分空間に対応します。${\displaystyle H_{A}}$そして${\displaystyle H_{B}}$このアプローチでは、個々の係数だけでなく、これらの部分空間に対応する係数のグループをゼロに設定することを推奨し、スパースな多重カーネル学習を促進します。

上記の推論は、任意の有限個の辞書または特徴マップに直接一般化できる。また、無限次元仮説を誘導する特徴マップにも拡張できる。

空間。^{[ 16 ]}