はじめに: 正則化の問題点
「スパース正則化」という言葉,皆さん一度は耳にしたことがあるかもしれませんね.特に機械学習や信号処理の分野で,ノルム(Lasso) や Group Lasso といった手法は,もはや標準的なツールとして広く使われています.これらの手法の根底にあるのは,「できるだけ少ない,選ばれた要素(特徴量やパラメータ)だけで,複雑な現象やデータをうまく表現したい」という,非常に実用的な目的です.
ノルムに代表される多くのスパース正則化手法は,「凸性」 という数学的に扱いやすい性質を持っています.この凸性のおかげで,計算が安定し,最適解を効率的に見つけるための洗練されたアルゴリズムが数多く開発されてきました.これはエンジニアや研究者にとって,非常に大きなメリットです.
しかしながら, 現実世界は必ずしも数学的に都合の良い性質ばかりではありません.実際のデータや,より高度な応用を目指す現場では,ノルムのような「凸」な正則化だけでは,必ずしも十分なレベルのスパース性や,データが持つ本来の構造に寄り添った柔軟な表現力を引き出せないケースが多々あります.「もっと強力に,本当に必要な要素だけを選び出したい」,「データに潜む複雑な構造を,より忠実に捉えたい」——こうした,既存の手法では届きにくいニーズに応えるべく登場したのが,「非凸スパース正則化」 なのです.
非凸正則化は,理論的には,理想的なスパース解(真に非ゼロであるべき要素だけが非ゼロになる解)にノルムよりも「近く」なる可能性を秘めています.しかし,その「非凸性」という性質ゆえに,最適化が難しく,計算上の課題が多いことが長年のボトルネックでした.ですが近年,数理最適化や機械学習アルゴリズムの目覚ましい進展により,この非凸性がもたらす壁を乗り越えるための新しいアプローチが次々と提案され,非凸スパース正則化は実用的な選択肢となりつつあります.
本記事では,この魅力的な「非凸スパース正則化」がなぜ今注目され,どのような理論的な背景を持ち,そして実際にどのような価値をもたらすのかを,背景から丁寧に,そして分かりやすく解説していきます.ノルムの限界を知り,非凸正則化の持つ可能性を感じていただければ嬉しいです.
スパース正則化の基礎とノルムの持つ「壁」
まずは,スパース正則化の基本であるノルムについて改めて見てみましょう.
ノルムとスパース性:なぜLassoは要素をゼロにするのか?
スパース正則化の最も有名な手法は,おそらくノルム正則化でしょう.これは,最小二乗法の目的関数に,パラメータベクトルのノルムに比例する項()を加えることで実現されます.典型的な問題設定は以下のようになります.
ここで,は観測データ,は変換行列(観測行列,基底行列と呼ばれることも),は推定したいスパースなベクトルです.は正則化の強さを調整するハイパーパラメータです.
なぜこのノルム項がスパース性(多くの要素がゼロになる性質)を生み出すのでしょうか?その理由は,ノルムの幾何学的な形状にあります.2次元の場合,ノルムが一定値をとる点の集合(等高線)は,原点を中心としたひし形(ダイヤモンド)になります.一方,最小二乗項の等高線は楕円です.この楕円がノルムのひし形と「初めて」接する点が最適解となることが多いのですが,ひし形は各座標軸上で尖っているため,接点が軸上に位置しやすく,結果としてその軸に対応する要素がゼロになる傾向が生まれるのです.
このノルム正則化(Lasso)は,数学的な「凸最適化」の枠組みで扱うことができます.凸最適化問題は,局所最適解が必ず大域最適解と一致するという素晴らしい性質があり,計算が非常に安定しています.実際,ISTA (Iterative Shrinkage Thresholding Algorithm)やFISTA(Fast ISTA)といった効率的なアルゴリズムによって,大規模な問題でも比較的容易に解くことができます.これがLassoが広く普及した大きな理由の一つです.
ノルムの限界:「縮小バイアス」という落とし穴
ノルムには多くの利点がある一方で,無視できない課題も存在します.その一つが,「縮小バイアス(shrinkage bias)」 と呼ばれる現象です.これは,真の値がゼロでない要素(信号成分など)まで,過度にゼロの方向に「縮小」されてしまう という問題です.
なぜこのようなバイアスが生じるのでしょうか? ノルム正則化の最適化を考える際に重要な役割を果たすのが,「近接写像(Proximal Operator)」 と呼ばれる演算子です.特にノルムに対する近接写像は,「ソフトしきい値関数(Soft Thresholding Operator)」として知られており,以下のようなシンプルな形をしています.
スカラー値 としきい値 に対するソフトしきい値関数は,
と定義されます.この式をよく見てみると,がより小さい場合は強制的にゼロにされます.また,がより大きい場合でも,から一律にが差し引かれてしまいます.
↑ 青線:ソフトしきい値処理を施す前の値. 赤線:ソフトしきい値処理を施した後の値.
つまり,真の値が本来ゼロでない小さな値だったとしても,このソフトしきい値処理を通すとゼロになってしまうか,あるいは真の値よりもだけ小さく評価されてしまうのです.これが「縮小バイアス」の正体です.特に信号処理の分野などでは,信号の小さな成分も重要な情報を含んでいる場合が多く,このような縮小バイアスは,信号の歪みや情報の欠落を引き起こす原因となり得ます.
この縮小バイアス,そしてノルムでは十分に引き出せないより強いスパース性や特定の構造への対応能力の限界が,「非凸スパース正則化」への道を拓きました.
非凸スパース正則化がもたらす可能性と課題
ノルムの課題を克服するために考え出されたのが,非凸な正則化項を導入するというアイデアです.
非凸正則化の基本アイデア:ノルムという理想
理想的なスパース性を実現する正則化項とは何でしょうか?それはおそらく,ベクトルの非ゼロ要素の個数を数える ノルム() でしょう.を最小化するという問題設定は,最も直接的にスパース性を追求します.
しかし,このノルムは,数学的には「ノルム」の定義を満たさないだけでなく,目的関数が連続関数ですらありません.この非連続性・非凸性のため,ノルムを用いた最適化問題は組合せ最適化問題となり,計算が非常に難しくなります(NP困難な場合が多いです).
そこで,「ノルムの持つ理想的なスパース性を持ちながら, ノルムよりは最適化しやすい」という,いわば両者の「いいとこ取り」を目指して提案されたのが,非凸スパース正則化です.これは,ノルムのように連続ではあるものの, ノルムよりもノルムに近い性質を持つ 「非凸」 な関数を正則化項として使う手法全般を指します.
非凸性がもたらすメリットと,それに伴う課題
非凸な正則化関数を用いることの主なメリットは以下の2点です.
- より強いスパース性:ノルムよりも,非ゼロ要素をより積極的にゼロに「押し込む」効果が期待できます.これにより,より少ない変数で表現される,より真に近いスパース解が得られやすくなります.
- 縮小バイアスの低減:ノルムが持つ,真の信号成分を過度に縮小してしまうバイアスを大幅に緩和できます.これにより,ゼロではない重要な要素を,その本来の値に近い形で推定することが可能になります.
これらのメリットは,ノルムの限界を乗り越え,より高精度なモデル構築や信号復元を実現するために非常に魅力的です.
一方で, 非凸性には大きな課題が伴います.それは,最適化問題が非凸になるということです.
- 局所解の問題:非凸関数を持つ目的関数は,複数の「局所最適解」を持つ可能性があります.これは,アルゴリズムがたどり着いた解が,必ずしも最も良い解(大域最適解)であるとは限らないことを意味します.初期値に敏感になったり,解の質が保証されにくくなったりします.
- 計算の難しさ:凸最適化のように汎用的な万能アルゴリズムが存在せず,非凸構造に対応したより高度なアルゴリズムが必要になります.ノルム問題に比べて計算に時間がかかったり,収束が不安定になったりする場合があります.
このように,非凸スパース正則化は「強力だが難しい」という二面性を持っています.しかし,近年のアルゴリズムの進歩により,この難しさを克服し,実用レベルで非凸正則化の恩恵を享受できるようになってきました.
代表的な非凸スパース正則化関数
ここでは,これまで提案されてきた数多くの非凸正則化関数の中から,代表的なものをいくつかご紹介します.これらの関数は,ノルムの性質を何らかの形で「緩和」することで最適化を可能にしています.(TBC: 非凸スパース正則化関数の作図)
ノルム()
最もシンプルな非凸正則化の一つが,ノルムの乗です(厳密には準ノルムと呼びます).
↑ ノルムの等高線(, ).青の点を動かすと の値が変わり,ノルムの等高線が変化する様子がわかります.
これはノルム()やノルム()の一般化と考えられますが,の場合,関数は原点付近で非常に尖った(非凸な)形状をしています.このの値を小さくするほど,関数の形状はノルム(非ゼロなら定数,ゼロならゼロ)に近づき,より強力なスパース性が促進されますが,同時に非凸性も増し,最適化はより難しくなります.
MCP(Minimax Concave Penalty)
MCPは,2010 年に Zhangによって提案された非凸スパース正則化関数です.定義は以下のようになります.
↑ MCP の等高線 .青の点を動かすと の値が変わり,MCPの等高線が変化する様子がわかります.
こちらも,はパラメータです.MCPは,原点付近ではノルムに似た形状を持ちますが,値が大きくなるにつれてペナルティが緩やかになり,ある値()を超えるとペナルティが飽和します. ノルムのように無限にペナルティが増えることを防ぐ ことで,縮小バイアスを抑制しつつ,スパース性を強化する効果があります.
ROWL(Reverse Ordered Weighted Norm)
Reverse Ordered Weighted (ROWL)は,2024 年に Sasaki らによって提案された非凸スパース正則化関数です.
ROWLは,要素の絶対値の「順序」に着目して重みを付ける Ordered Weighted (OWL) を発展させた手法です.OWLは一般的に凸ですが,その拡張であるROWLは非凸となります.
ROWLの正則化項は,以下のようになります.
↑ ROWL の等高線 .青の点を動かすと の値が変わり,ROWLの等高線が変化する様子が見て取れます.
ここでは,ベクトルの各成分の絶対値を大きい順に並べたときの番目の値です.そして,は事前に与えられる重みベクトルです.
ROWLの鍵は,この重みの付け方にあります. 名前の「Reverse」が示唆するように,ROWLでは,絶対値が大きい成分ほど小さな重みを与え,絶対値が小さい成分ほど大きな重みを与えます. 例えば, のような重み付けをすると,最も絶対値が大きい成分 には重みが,2番目に大きい成分 には重みがかけられることになります.絶対値が小さく,順位が低い成分ほど大きな重みがかけられることで,これらの小さな成分をより強くゼロにしようと促す効果が生まれます.
この非凸化の戦略は,ノルムとは異なるアプローチです.ROWLは「値の順位」に基づいてペナルティを変えます.これにより,信号の小さな成分(微細なエッジ)を過度に縮小することなく保持しつつ,ノイズや不要な成分を効果的に除去できるという特徴があります.特に,画像処理などで扱う,テクスチャやエッジのような微細な構造を持つデータに対して有効です.
これらの非凸スパース正則化関数は,それぞれ異なる数学的な性質とデザイン哲学を持っています.ノルムのような凸な手法では捉えきれない,データに潜むより複雑なスパース性や構造を捉えるために,これらの非凸な選択肢が非常に重要になってきています.
Equivalent MCP(EMCP)
さらに,MCPはある意味で最適に重み付けされたノルムと等価です.MCP のこのような捉え方は Equivalent MCP (EMCP) と呼ばれています.
EMCPでは,MCPは以下のような補助変数 を用いた最適化問題の解として表現されます.
この式の意味を考えてみましょう.元の非凸関数 を直接扱う代わりに,より単純な項()と,補助変数 に関する二次関数の和の最小値として表現し直しています.
EMCPの最大の利点は,重み を最適化の一部として扱える点にあります.元の問題は だけの最適化でしたが,EMCPでは と を交互に最適化するアプローチが可能になります.
-
を固定すると, の最適値は解析的に簡単に求まります:
この式は,ソフトしきい値処理と非常によく似た形をしており, の絶対値が大きいときは は小さくなり, の絶対値が小さいときは は大きくなるため,結果として ROWL のように逆順序的な重み付け が行われます.
-
逆に を固定すると, に関する問題は,単純な重み付きノルム最小化問題となり,これも効率的に解くことができます.
この交互最適化のプロセスを通じて,重み はデータに合わせて自動的に調整されていきます.これにより,ヒューリスティックな重み設定に頼ることなく(初期重みと逆学習率の設定は必要ですが),最適なスパース性を引き出すことが可能になるのです.
このように,EMCPはMCPを,より扱いやすい部分問題の連鎖に分解するための強力な枠組みを提供し,MCPの適用範囲と性能を大きく向上させます.
非凸最適化アルゴリズムと計算上の工夫
非凸正則化の最大の課題は,前述したように最適化が難しいことです.しかし,この課題を克服するために,様々な数理最適化アルゴリズムが発展してきました.ここでは,非凸正則化問題を解くために用いられる代表的なアプローチをいくつか簡単にご紹介します.
近接勾配法(Proximal Gradient Methods)
ノルムの最適化で重要な役割を果たした近接勾配法(ISTA: Iterative Shrinkage Thresholding Algorithm)は,非凸関数に対しても適用できます.ここでは近接勾配法自体の詳細なアルゴリズムの説明は省略し,非凸関数に対する近接写像の計算に焦点を当てます.
近接勾配法は,勾配降下と近接写像の計算を組み合わせることで, ノルムのように非平滑な正則化項を持つ問題を効率的に解くことができます.関数の近接写像は一般に以下のように定義されます.
ISTAでは, ノルムの近接写像(ソフトしきい値処理)を用いて,以下のような反復的な更新を行います.
しかし,非凸な関数の場合,この最適化問題の解が一意に定まらなかったり,そもそも計算が非常に難しかったりすることがあります.そのため,非凸正則化を解くための近接勾配法では,非凸関数の近接写像を効率的に計算するための特別な工夫が必要になります.例えば,MCPやROWLのような特定の非凸関数に対しては,その形状を利用した効率的な(閉形式な)近接写像の計算方法が知られています.
その他の手法
他にも,非凸正則化問題を解くための様々なアプローチがあります.
- 差分凸計画(Difference of Convex Functions Programming, DCP):非凸関数を二つの凸関数の差として表現し,それを利用して逐次的に凸問題を解く手法です.
- 交互方向乗数法(ADMM, Alternating Direction Method of Multipliers):非凸正則化項を持つ問題を,複数の凸なサブ問題に分解し,それぞれを交互に最適化する手法です.
- 確率伝搬法 (Approximate Message Passing, AMP):確率モデルを「変数ノード」と「因子ノード」からなるグラフで表現し,ノード間で「メッセージ」と呼ばれる情報をやり取りすることで,事後分布の近似計算を行います(あまり詳しくないので,間違ってたらスイマセン).
これらのアルゴリズムは,非凸性による計算困難性をある程度克服し,実用的な時間で「良い」解(多くの場合,局所最適解)を見つけることを可能にしています.もちろん,大域最適解を見つける保証は一般にはありませんが,多くの応用においては得られた局所解が十分な性能を発揮することが経験的に知られています.さらに,特定条件下(目的関数全体が凸になる場合など)では,局所最適解が大域最適解に近くなることも理論的に示されています.
応用例とノルムとの比較:非凸正則化はどのように役立つのか?
非凸スパース正則化は,その強力なスパース性とバイアス低減効果から,様々な分野でノルムを凌駕する性能を発揮する可能性があります.
非凸スパース正則化の応用例
- 信号復元・画像処理:ノイズが乗った信号から元のスパースな信号を復元したり,画像からエッジのようなスパースな構造を抽出したりするタスクで,ノルムよりもクリアな結果が得られることがあります.圧縮センシングの分野でも重要です.
- 機械学習モデルの特徴選択・圧縮:高次元データの中から,予測に本当に効いている少数の特徴量だけをより正確に選び出したり,ニューラルネットワークのパラメータをスパース化してモデルを圧縮したりする際に,非凸正則化が有効な場合があります.
- 異常検知:異常なパターンを持つデータから,正常なパターンを低周波成分や低ランク成分で近似し,異常な部分をスパースな残差として抽出するタスクで,非凸正則化が有効です.
ここで示した応用例はほんの一部に過ぎませんが,非凸スパース正則化が持つ強力なスパース性とバイアス低減効果が,様々な分野での性能向上に寄与する可能性を示しています.
従来手法(ノルム)との比較
ここでは,ノルムと非凸スパース正則化の一般的な性質を比較してみましょう.
手法 | スパース性(要素をゼロにする強さ) | 縮小バイアス(非ゼロ成分を過度に小さくするか) | 最適化の難易度 | 局所解の可能性 | |
---|---|---|---|---|---|
ノルム | 中 | 大 | 易 | なし(凸問題) | |
ノルム () | 強 | 中 | 難 | あり | |
MCP | 強 | 小 | 難 | あり | |
ROWL | 強 | 小 | 難 | あり |
この表から分かるように,非凸正則化手法は,ノルムに比べて「スパース性が強く,縮小バイアスが小さい」という望ましい性質を持つ反面,「最適化が難しく,局所解に陥る可能性がある」という課題を抱えています.
どの手法を選ぶかは,解決したい問題の性質,データの特性,許容できる計算時間,そして解の精度に対する要求などによって異なります.例えば,とにかく高速に解を得たい場合はノルムが有利ですが,多少計算時間がかかっても,より高精度なスパース解やバイアスの少ない推定値を得たい場合には,非凸正則化が強力な選択肢となります.
私の経験からも,特に信号処理における特定のタイプの信号復元問題に対しては,ノルムでは得られない顕著な性能向上が非凸正則化によって実現できることを確認しています.
まとめ
本記事では,「非凸スパース正則化」という,ノルムの限界を超え,より強力なスパース性と柔軟な表現力を目指す技術について解説しました.
- ノルムは凸性ゆえに扱いやすいですが,縮小バイアスという課題を持ちます.
- 非凸スパース正則化は,ノルム,MCP,ROWLといった多様な関数を用いることで,より強いスパース性とバイアス低減を実現します.
- 非凸性は最適化の難しさを伴いますが,近年の近接勾配法,MM法,座標降下法などのアルゴリズムの発展により,実用的な問題にも適用できるようになってきました.
- 信号処理,画像処理,機械学習 など,幅広い分野での応用が期待されています.
非凸スパース正則化は,まだ発展途上の部分もありますが,その潜在能力は非常に高く,今後ますます重要な技術になっていくと考えられます.特に,大規模データに対する効率的なアルゴリズムの開発や,理論的な性質のさらなる解明,そして様々な応用分野での活用事例の蓄積が進んでいくでしょう.
もし ノルムでの結果に満足できなかったり,より高精度なスパース解を求めているのであれば,「非凸スパース正則化」という選択肢をぜひ検討してみてください.
参考文献
技術的な詳細や実装に関心のある方は,以下の文献を参照してください:
■ 非凸スパース正則化(ノルムやMCP)も含んだスパース正則化のサーベイ論文
[7] Z. Zhang, Y. Xu, J. Yang, X. Li, and D. Zhang, “A Survey of Sparse Representation: Algorithms and Applications,” IEEE Access, vol. 3, pp. 490–530, 2015, doi: 10.1109/ACCESS.2015.2430359.
[8] F. Wen, L. Chu, P. Liu, and R. C. Qiu, “A Survey on Nonconvex Regularization-Based Sparse and Low-Rank Recovery in Signal Processing, Statistics, and Machine Learning,” IEEE Access, vol. 6, pp. 69883–69906, 2018, doi: 10.1109/ACCESS.2018.2880454.
■ Minimax Concave Penalty (MCP) の技術的背景
[2] C.-H. Zhang, “Nearly unbiased variable selection under minimax concave penalty,” The Annals of Statistics, vol. 38, no. 2, pp. 894–942, Apr. 2010, doi: 10.1214/09-AOS729.
↓ MCP を含む目的関数が全体として凸である条件を示した論文
[3] I. Selesnick, “Sparse Regularization via Convex Analysis,” IEEE Transactions on Signal Processing, vol. 65, no. 17, pp. 4481–4494, Sep. 2017, doi: 10.1109/TSP.2017.2711501.
■ Equivalent MCP (EMCP) の技術的背景と異常検知(ロバスト主成分分析)への適用
[4] P. K. Pokala, R. V. Hemadri, and C. S. Seelamantula, “Iteratively Reweighted Minimax-Concave Penalty Minimization for Accurate Low-rank Plus Sparse Matrix Decomposition,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 44, no. 12, pp. 8992–9010, Feb. 2022, doi: 10.1109/TPAMI.2021.3122259.
■ Reverse Ordered Weighted Norm (ROWL) の理論的背景と画像ノイズ除去への応用
[6] T. Sasaki, Y. Bandoh, and M. Kitahara, “Sparse Regularization Based on Reverse Ordered Weighted L1-Norm and Its Application to Edge-Preserving Smoothing,” in Proceedings of International Conference on Acoustics, Speech and Signal Processing, Apr. 2024, pp. 9531–9535. doi: 10.1109/ICASSP48485.2024.10448119.
■ Approximate Message Passing (AMP) による非凸スパース正則化
[5] 坂田綾香 and 小渕智之, “非凸スパース制約最小化による信号復元:非凸性制御によるアルゴリズム軌道の安定化,” 日本統計学会誌, vol. 53, no. 1, pp. 111–137, 2023, doi: 10.11329/jjssj.53.111.