学習のための近似勾配法

学習のための近似勾配法（順方向・逆方向分割法）は、最適化と統計学習理論の研究分野であり、正則化ペナルティが微分可能でない可能性のある凸 正則化問題の一般的なクラスに対するアルゴリズムを研究する。そのような例の一つは、以下の形式の正則化（Lassoとも呼ばれる） である。${\displaystyle \ell _{1}}$

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

近似勾配法は、特定の問題アプリケーションに合わせて調整されたペナルティを用いて、統計学習理論の正則化問題を解決するための一般的なフレームワークを提供します。^{[1] [2]}このようなカスタマイズされたペナルティは、スパース性（ lassoの場合）やグループ構造（ group lassoの場合 ）などの特定の構造を問題の解決に誘導するのに役立ちます。

関連する背景

近似勾配法は、次のよう な凸最適化問題を解くための幅広いシナリオに適用できます。

${\displaystyle \min _{x\in {\mathcal {H}}}F(x)+R(x),}$

ここで、 は凸かつリプシッツ連続勾配で微分可能であり、は凸かつ下側半連続関数であり、微分不可能となる可能性があり、は何らかの集合、典型的にはヒルベルト空間 である。凸かつ微分可能な設定において が最小となるための必要条件は、現在では に置き換えられている。 ${\displaystyle F}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle x}$ ${\displaystyle F(x)+R(x)}$ ${\displaystyle \nabla (F+R)(x)=0}$

${\displaystyle 0\in \partial (F+R)(x),}$

ここで、 は実数値凸関数のサブ微分を表します。 ${\displaystyle \partial \varphi }$ ${\displaystyle \varphi }$

凸関数が与えられたとき、考慮すべき重要な作用素は、その近似作用素であり、これは次のように定義される。 ${\displaystyle \varphi :{\mathcal {H}}\to \mathbb {R} }$ ${\displaystyle \operatorname {prox} _{\varphi }:{\mathcal {H}}\to {\mathcal {H}}}$

${\displaystyle \operatorname {prox} _{\varphi }(u)=\operatorname {arg} \min _{x\in {\mathcal {H}}}\varphi (x)+{\frac {1}{2}}\|u-x\|_{2}^{2},}$

これはノルムの厳密な凸性により明確に定義される。近接作用素は射影の一般化として見ることができる。^{[1] [3] [4]} 近接作用素が重要である理由は、が問題の最小化因子となるのは ${\displaystyle \ell _{2}}$ ${\displaystyle x^{*}}$ ${\displaystyle \min _{x\in {\mathcal {H}}}F(x)+R(x)}$

${\displaystyle x^{*}=\operatorname {prox} _{\gamma R}\left(x^{*}-\gamma \nabla F(x^{*})\right),}$ ここでは任意の正の実数である。^[1]${\displaystyle \gamma >0}$

モロー分解

近接勾配法に関連する重要な手法の一つにモロー分解がある。これは恒等作用素を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 ),}$

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

状況によっては、関数 ではなく共役 の近接演算子を計算する方が簡単な場合があり、その場合はモロー分解を適用できます。これは、 群 lassoの場合に当てはまります。 ${\displaystyle \varphi ^{*}}$ ${\displaystyle \varphi }$

Lasso正規化

二乗損失と正規化ペナルティとしてのノルムを伴う正規化された 経験的リスク最小化問題を考えてみましょう。 ${\displaystyle \ell _{1}}$

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

ここで、正則化問題はラッソ（最小絶対収縮選択演算子）と呼ばれることもある。^[5]このような正則化問題は、疎な解、つまり最小化問題の解が比較的少ない非零成分を持つという点で興味深い。ラッソは、非凸問題の凸緩和と見ることができる。 ${\displaystyle x_{i}\in \mathbb {R} ^{d}{\text{ and }}y_{i}\in \mathbb {R} .}$ ${\displaystyle \ell _{1}}$ ${\displaystyle \ell _{1}}$ ${\displaystyle w}$

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

ここで、は「ノルム」、つまりベクトルの非ゼロ要素の数を表します。スパース解は、学習理論において結果の解釈可能性の観点から特に重要です。スパース解は、少数の重要な因子を特定することができます。^[5]${\displaystyle \|w\|_{0}}$ ${\displaystyle \ell _{0}}$ ${\displaystyle w}$

Lを解く₁近接演算子

簡単のため、ここでは という問題に焦点を絞ります。この問題を解くには ${\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}}}$

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

固定小数点反復スキーム

最終的にラッソ問題を解くために、先に示した固定点方程式を考えます。

${\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).}$

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

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

実用的な考慮事項

過去10年間で凸最適化手法は数多く進歩し、統計学習理論における近似勾配法の応用に影響を与えてきました。本稿では、これらの手法の実用的なアルゴリズム性能を大幅に向上させることができる重要なトピックをいくつか概説します。^{[2] [10]}

適応ステップサイズ

固定小数点反復法では

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

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

弾性ネット（混合ノルム正則化）

弾性ネット正則化は、純粋な正則化の代替手段を提供します。Lasso（）正則化の問題には、厳密に凸ではないペナルティ項 が関係します。したがって、 （ は経験的損失関数）の解は一意である必要はありません。この問題は、ノルム正則化ペナルティなどの厳密に凸な項を追加することで回避されることがよくあります。例えば、以下の問題を考えてみましょう。 ${\displaystyle \ell _{1}}$ ${\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),}$

ここで 、ペナルティ項は厳密に凸となり、したがって最小化問題は唯一の解を許容する。十分に小さい に対して、追加のペナルティ項は前処理として機能し、解のスパース性に悪影響を与えることなく収束性を大幅に改善できることが観察されている。^{[2] [14]}${\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}}$

グループ構造の悪用

近接勾配法は、統計学習理論における幅広い問題に適用可能な一般的な枠組みを提供します。学習における特定の問題では、事前に既知の追加構造を持つデータを扱うことがよくあります。ここ数年、グループ構造に関する情報を取り入れ、様々な用途に適した手法を提供する新たな開発が行われています。ここでは、そのような手法をいくつか概観します。

グループラッソ

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

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

これは、異なるグループに対応する特徴ベクトルのノルムの合計です。上記と同様の近接演算子分析を用いて、このペナルティの近接演算子を計算できます。Lassoペナルティが個々の要素に対してソフト閾値処理を行う近接演算子を持つのに対し、グループLassoの近接演算子は各グループに対してソフト閾値処理を行います。グループに対して、近接演算子は次のように与えられます 。${\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}$

Lassoとは対照的に、グループLassoの近接作用素の導出はモロー分解に依存します。ここで、グループLassoペナルティの共役の近接作用素は、双対ノルムの球面への射影となります。^[2]

その他のグループ構造

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

参照

• 凸解析
• 近位勾配法
• 正規化
• 統計学習理論

参考文献

1. Combettes, Patrick L.; Wajs, Valérie R. (2005). 「近位前方後方分割による信号回復」.マルチスケールモデル. Simul . 4 (4): 1168– 1200. doi :10.1137/050626090. S2CID  15064954.
2. Mosci, S.; Rosasco, L.; Matteo, S.; Verri, A.; Villa, S. (2010). 「近似法による構造化スパース性正則化の解決」.データベースにおける機械学習と知識発見. コンピュータサイエンス講義ノート. 第6322巻. pp.  418– 433. doi : 10.1007/978-3-642-15883-4_27 . ISBN 978-3-642-15882-7。
3. モロー、J.-J. （1962年）。 「凸面の二重構造と、空間のヒルバーティエンに近い点の機能」。Comptes Rendus de l'Académie des Sciences、セリエ A。255 : 2897–2899 . MR  0144188. Zbl  0118.10502.
4. Bauschke, HH, Combettes, PL (2011).ヒルベルト空間における凸解析と単調作用素理論. Springer.
5. Tibshirani, R. (1996). 「Lassoによる回帰収縮と選択」. JR Stat. Soc. Ser. B. 1. 58 (1): 267– 288. doi :10.1111/j.2517-6161.1996.tb02080.x.
6. Daubechies, I.; Defrise, M.; De Mol, C. (2004). 「スパース性制約付き線形逆問題に対する反復閾値化アルゴリズム」. Comm. Pure Appl. Math . 57 (11): 1413– 1457. arXiv : math/0307152 . doi :10.1002/cpa.20042. S2CID  1438417.
7. ネステロフ、ユーリイ (1983). 「収束率を考慮した凸計画問題の解法」.ソビエト数学 - ドクラディ. 27 (2): 372– 376.${\displaystyle O(1/k^{2})}$
8. Nesterov, Yurii (2004).凸最適化入門講義. Kluwer Academic Publisher.
9. ヴィラ、S.サルツォ、S.バルダッサーレ、L.ヴェッリ、A. (2013)。 「高速かつ不正確な前方後方アルゴリズム」。サイアム J.オプティム23 (3): 1607 ～ 1633。CiteSeerX 10.1.1.416.3633。土井：10.1137/110844805。S2CID  11379846。 
10. Bach, F.; Jenatton, R.; Mairal, J.; Obozinski, Gl. (2011). 「スパース性誘導ペナルティを用いた最適化」.機械学習の基礎と動向. 4 (1): 1– 106. arXiv : 1108.0775 . Bibcode :2011arXiv1108.0775B. doi :10.1561/2200000015. S2CID  56356708.
11. Loris, I.; Bertero, M.; De Mol, C.; Zanella, R.; Zanni, L. (2009). 「ステップ長選択規則による -constrained signal recovery のための勾配射影法の高速化」. Applied & Comp. Harmonic Analysis . 27 (2): 247– 254. arXiv : 0902.4424 . doi :10.1016/j.acha.2009.02.003. S2CID  18093882.${\displaystyle \ell _{1}}$
12. Wright, SJ; Nowak, RD; Figueiredo, MAT (2009). 「分離近似によるスパース再構成」. IEEE Trans. Image Process . 57 (7): 2479– 2493. Bibcode :2009ITSP...57.2479W. CiteSeerX 10.1.1.115.9334 . doi :10.1109/TSP.2009.2016892. S2CID  7399917. 
13. Loris, Ignace (2009). 「-ペナルティ付き汎関数の最小化アルゴリズムの性能について」. Inverse Problems . 25 (3) 035008. arXiv : 0710.4082 . Bibcode :2009InvPr..25c5008L. doi :10.1088/0266-5611/25/3/035008. S2CID  14213443.${\displaystyle \ell _{1}}$
14. デ・モル、C.;デ・ヴィート、E.ロザスコ、L. (2009)。 「学習理論におけるエラスティックネット正則化」。J. 複雑さ。25 (2 ) : 201–230.arXiv : 0807.3423 。土井：10.1016/j.jco.2009.01.002。S2CID  7167292。
15. Yuan, M.; Lin, Y. (2006). 「グループ化された変数を用いた回帰分析におけるモデル選択と推定」. JR Stat. Soc. B. 68 ( 1): 49– 67. doi : 10.1111/j.1467-9868.2005.00532.x . S2CID  6162124.
16. Chen, X.; Lin, Q.; Kim, S.; Carbonell, JG; Xing, EP (2012). 「一般構造化スパース回帰における平滑化近似勾配法」. Ann. Appl. Stat . 6 (2): 719– 752. arXiv : 1005.4717 . doi :10.1214/11-AOAS514. S2CID  870800.
17. Mosci, S.; Villa, S.; Verri, A.; Rosasco, L. (2010). 「重複グループを含むグループスパース正則化のためのプライマル-デュアルアルゴリズム」NIPS . 23 : 2604–2612 .
18. Jenatton, R.; Audibert, J.-Y.; Bach, F. (2011). 「スパース性誘導ノルムを用いた構造化変数選択」J. Mach. Learn. Res . 12 : 2777–2824 . arXiv : 0904.3523 . Bibcode :2009arXiv0904.3523J.
19. Zhao, P.; Rocha, G.; Yu, B. (2009). 「グループ化および階層的変数選択における複合絶対ペナルティファミリー」. Ann. Stat . 37 (6A): 3468– 3497. arXiv : 0909.0411 . Bibcode :2009arXiv0909.0411Z. doi :10.1214/07-AOS584. S2CID  9319285.
20. Obozinski, Guillaume; Jacob, Laurent; Vert, Jean-Philippe (2011). 「重複を考慮したグループLasso：潜在的グループLassoアプローチ」arXiv : 1110.0413 [stat.ML].
21. Villa, Silvia; Rosasco, Lorenzo; Mosci, Sofia; Verri, Alessandro (2012). 「潜在グループLassoペナルティのための近似法」arXiv : 1209.0368 [math.OC].