学習のための近接勾配法

近接勾配法に関連する重要な手法の一つに、恒等演算子を2つの近接演算子の和として分解するモロー分解がある。 ^{[ 1 ]}すなわち、${\displaystyle \varphi$ :{\mathcal {X}}\to \mathbb {R} } はベクトル空間上の下半連続凸関数である。$\displaystyle {\mathcal {X}}}$我々は、そのフェンシェル共役を定義する。${\displaystyle \varphi ^{*}:{\mathcal {X}}\to \mathbb {R} }$機能である

${\displaystyle \varphi ^{*}(u):=\sup _{x\in {\mathcal {X}}}\langle x,u\rangle -\varphi (x).}$

モロー分解の一般形は、任意の${\displaystyle x\in {\mathcal {X}}}$そしてどんな${\displaystyle \gamma >0}$それ

${\displaystyle x=\operatorname {prox} _{\gamma \varphi }(x)+\gamma \operatorname {prox} _{\varphi ^{*}/\gamma }(x/\gamma ),}$

そのために${\displaystyle \gamma =1}$意味するところは${\displaystyle x=\operatorname {prox} _{\varphi }(x)+\operatorname {prox} _{\varphi ^{*}}(x)}$^{[ 1 ] [ 3 ]}モロー分解は、ベクトル空間の通常の直交分解の一般化であることがわかります。これは、近接演算子が射影の一般化であるという事実と類似しています。^{[ 1 ]}

状況によっては、共役の近接演算子を計算する方が容易な場合がある。${\displaystyle \varphi ^{*}}$関数の代わりに${\displaystyle \varphi }$したがって、モロー分解を適用できます。これは グループラッソの場合に当てはまります。

簡略化のため、ここでは以下の問題に限定して考察する。${\displaystyle \lambda =1}$問題を解決するために

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

目的関数を2つの部分に分けて考えます。凸で微分可能な項${\displaystyle F(w)={\frac {1}{n}}\sum _{i=1}^{n}(y_{i}-\langle w,x_{i}\rangle )^{2}}$そして凸関数${\displaystyle R(w)=\|w\|_{1}}$。 ご了承ください${\displaystyle R}$厳密には凸関数ではない。

近接演算子を計算してみましょう${\displaystyle R(w)}$まず、近接演算子の別の特徴付けを見つける。${\displaystyle \operatorname {prox} _{R}(x)}$次のように：

${\displaystyle {\begin{aligned}u=\operatorname {prox} _{R}(x)\iff &0\in \partial \left(R(u)+{\frac {1}{2}}\|u-x\|_{2}^{2}\right)\\\iff &0\in \partial R(u)+u-x\\\iff &x-u\in \partial R(u).\end{aligned}}}$

のために${\displaystyle R(w)=\|w\|_{1}}$計算は簡単です${\displaystyle \partial R(w)}$: その${\displaystyle i}$の 番目のエントリ${\displaystyle \partial R(w)}$まさに

${\displaystyle \partial |w_{i}|={\begin{cases}1,&w_{i}>0\\-1,&w_{i}<0\\\left[-1,1\right],&w_{i}=0.\end{cases}}}$

上記の近接演算子の再特性化を使用して、${\displaystyle R(w)=\|w\|_{1}}$そして${\displaystyle \gamma >0}$私たちはそれを持っています${\displaystyle \operatorname {prox} _{\gamma R}(x)}$エントリごとに定義される

${\displaystyle \left(\operatorname {prox} _{\gamma R}(x)\right)_{i}={\begin{cases}x_{i}-\gamma ,&x_{i}>\gamma \\0,&|x_{i}|\leq \gamma \\x_{i}+\gamma ,&x_{i}<-\gamma ,\end{cases}}}$

これはソフト閾値演算子として知られています${\displaystyle S_{\gamma }(x)=\operatorname {prox} _{\gamma \|\cdot \|_{1}}(x)}$[ ^{1 ] [ 6 ]​}

最終的にラッソ問題を解決するために、先に示した不動点方程式を検討します。

${\displaystyle x^{*}=\operatorname {prox} _{\gamma R}\left(x^{*}-\gamma \nabla F(x^{*})\right).}$

近接演算子の形式を明示的に計算したので、標準的な不動点反復手順を定義できます。つまり、初期値を固定します。${\displaystyle w^{0}\in \mathbb {R} ^{d}}$、そして${\displaystyle k=1,2,\ldots }$定義する

${\displaystyle w^{k+1}=S_{\gamma }\left(w^{k}-\gamma \nabla F\left(w^{k}\right)\right).}$

ここで、経験的誤差項と実際のトレードオフに注目してください。${\displaystyle F(w)}$および正規化ペナルティ${\displaystyle R(w)}$この固定点法は、目的関数を構成する 2 つの異なる凸関数の影響を勾配降下ステップに分離しました (${\displaystyle w^{k}-\gamma \nabla F\left(w^{k}\right)}$）とソフト閾値処理ステップ（${\displaystyle S_{\gamma }}$)

この不動点法の収束性は文献^{[ 1 ] [ 6 ]}で十分に研究されており、適切なステップサイズを選択すれば保証される。${\displaystyle \gamma }$損失関数（ここでは二乗損失など）も考慮する必要があります。加速法は1983年にネステロフによって導入され、特定の正則性仮定の下で収束速度を向上させます。${\displaystyle F}$[ ^{7 ]}こうした手法は過去数年間で広く研究されてきた。^{[ 8 ]} 正則化項の一部に対して近接演算子を明示的に計算できない、より一般的な学習問題の^場合${\displaystyle R}$このような固定点スキームは、勾配と近接演算子の両方の近似を使用して実行できます。^{[ 4 ] [ 9 ]}

不動点反復法では

${\displaystyle w^{k+1}=\operatorname {prox} _{\gamma R}\left(w^{k}-\gamma \nabla F\left(w^{k}\right)\right),}$

可変ステップサイズを許容することができる${\displaystyle \gamma _{k}}$定数の代わりに${\displaystyle \gamma }$文献では、数多くの適応ステップサイズスキームが提案されている。 ^{[ 1 ] [ 4 ] [ 11 ] [ 12 ]}これらのスキームの応用例^{[ 2 ] [ 13 ]} は、固定点収束に必要な反復回数を大幅に改善できることを示唆している。

弾性ネット正則化は純粋な${\displaystyle \ell _{1}}$正則化。lasso の問題 (${\displaystyle \ell _{1}}$) 正則化にはペナルティ項が含まれる${\displaystyle R(w)=\|w\|_{1}}$これは厳密には凸関数ではない。したがって、の解は${\displaystyle \min _{w}F(w)+R(w),}$どこ${\displaystyle F}$は経験的な損失関数であり、一意である必要はありません。これは、例えば、厳密に凸な項を追加することで回避されることがよくあります。${\displaystyle \ell _{2}}$ノルム正則化ペナルティ。例えば、次の問題を考えることができる。

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

どこ${\displaystyle x_{i}\in \mathbb {R} ^{d}{\text{ and }}y_{i}\in \mathbb {R} .}$ のために${\displaystyle 0<\mu \leq 1}$罰則${\displaystyle \lambda \left((1-\mu )\|w\|_{1}+\mu \|w\|_{2}^{2}\right)}$は厳密に凸関数となり、したがって最小化問題は一意解を持つようになる。十分に小さい場合、${\displaystyle \mu >0}$追加の罰則${\displaystyle \mu \|w\|_{2}^{2}}$前処理として機能し、解の疎性に悪影響を与えることなく収束を大幅に改善することができます。^{[ 2 ] [ 14 ]}

グループラッソは、特徴が互いに素なブロックにグループ化されている場合のラッソ法の一般化です。^{[ 15 ]}特徴がブロックにグループ化されていると仮定します。${\displaystyle \{w_{1},\ldots ,w_{G}\}}$ここでは、正則化ペナルティとして を採用します。

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

これは、${\displaystyle \ell _{2}}$異なるグループの対応する特徴ベクトルのノルム。上記と同様の近接演算子分析を使用して、このペナルティの近接演算子を計算できます。ラッソペナルティの近接演算子は各個々のコンポーネントに対してソフト閾値処理を行いますが、グループラッソの近接演算子は各グループに対してソフト閾値処理を行います。グループの場合${\displaystyle w_{g}}$近接演算子${\displaystyle \lambda \gamma \left(\sum _{g=1}^{G}\|w_{g}\|_{2}\right)}$は

${\displaystyle {\widetilde {S}}_{\lambda \gamma }(w_{g})={\begin{cases}w_{g}-\lambda \gamma {\frac {w_{g}}{\|w_{g}\|_{2}}},&\|w_{g}\|_{2}>\lambda \gamma \\0,&\|w_{g}\|_{2}\leq \lambda \gamma \end{cases}}}$

どこ${\displaystyle w_{g}}$は${\displaystyle g}$第 1 グループ。

ラッソとは対照的に、グループラッソの近接演算子の導出はモロー分解に依存している。ここで、グループラッソペナルティの共役の近接演算子は、双対ノルムの球への射影となる。^{[ 2 ]}

特徴が互いに素なブロックにグループ化されるグループ ラッソ問題とは対照的に、グループ化された特徴が重複したり、入れ子構造になったりする場合があります。このようなグループ ラッソの一般化は、さまざまな文脈で検討されてきました。^{[ 16 ] [ 17 ] [ 18 ] [ 19 ]}重複するグループの場合、重複を考慮するために潜在変数を導入する潜在グループ ラッソとして知られる一般的なアプローチがあります。 ^{[ 20 ] [ 21 ]}入れ子構造のグループ構造は、階層構造予測と有向非巡回グラフで研究されています。^{[ 18 ]}