最適なブロック構造を学習するブロックスパース正則化：LOP-l2/l1 の紹介

はじめに

スパース正則化をご存知でしょうか？機械学習や信号処理でよく使われる手法ですが，それを発展させた手法としてブロックスパース正則化があります．

普通のスパース正則化では ${\ell }_1$ ノルムを使って「なるべく多くの要素をゼロにする」ことを目指しますが，ブロックスパース正則化では混合 ${\ell }_2/{\ell }_1$ ノルムという少し変わったノルムを使います．これは，現実の信号やデータには「関連する要素がグループになっている」という構造がしばしば見られるためです．

ブロックスパース正則化の利点

この手法の特長は，ブロック構造を適切に設定することで，通常のスパース正則化よりも優れた結果が得られる点です．

具体的には，${\ell }_1$ ノルムは混合 ${\ell }_2/{\ell }_1$ ノルムの特殊なケース（各要素が独立したブロックになっている場合）です．つまり，ブロックスパース正則化の方がより一般的であり，状況に応じてより適切な正則化が可能であると言えます．

ブロックスパース正則化の欠点

ただし，この手法にも課題があります．最大の課題は「適切なブロック構造をどのように決定するか」という点です．

ブロックの分割方法が実際のデータ構造と乖離している場合，期待される性能向上は得られません．特に，事前にブロック構造が分からない場合（これは実際の応用において頻繁に発生する状況ですが），まずデータからブロック構造を推定し，その後で正則化を行う必要があります．これは解決が困難な問題です．

適応的ブロックスパース正則化の必要性

実際の応用における課題

現実の問題を考えてみると，最適なブロック構造が事前に既知であるとは限りません．実際，多くの場合においてその情報は不明です．例えば：

• 自然画像のエッジ成分：写真によってエッジの出現位置は異なります
  
• フェーズドアレイ気象レーダー：観測条件によって周波数パターンが変動します
• 動画像の前景成分：動的物体の形状や位置は時間とともに変化します

このような状況でブロック構造を固定してしまうと，手法の有効性が損なわれる可能性があります．さらに，観測データがノイズなどで汚染されている場合は，ブロック構造の推定がさらに困難になります．

適応的アプローチの重要性

そこで，適応的ブロックスパース正則化が登場します．これは「ブロック構造も同時に学習する」という発想から生まれた手法です．

具体的には，以下の2つのプロセスを同時に最適化します：

1. ブロック構造の推定：データから最適なブロック分割を自動で学習
2. ブロックスパース正則化の実行：学習したブロック構造を使って実際に正則化

従来は「まずブロック構造を決定し，その後正則化を行う」という2段階のアプローチでしたが，適応的手法では両者を同時に最適化します．これにより，相互に影響し合うことなく，より高精度な解の導出が可能となります．

既存手法の限界

このアイデア自体は以前から存在していました．すでに貪欲法やベイズ的手法，Latent Group Lassoといった手法が提案されていました．しかし，これらの手法には共通して以下のような課題がありました：

• 計算量の問題：$\mathcal{O}(N^3)$という計算量は，大規模データに対しては実用的ではありませんでした
• 収束性の問題：非凸最適化であるため，局所最適解に陥るリスクがありました
• スケーラビリティの問題：現実的な時間での解の導出が困難でした

要するに，「理論的には興味深いものの，実用性に課題がある」という状況でした．

そこで登場したのが，LOP-${\ell }_2/{\ell }_1$（Latent Optimally Partitioned ${\ell }_2/{\ell }_1$）という手法です．これは画期的なアプローチでした．

混合${\ell }_2/{\ell }_1$ノルム

混合${\ell }_2/{\ell }_1$ノルムは，LOP-${\ell }_2/{\ell }_1$の数学的基盤をなす重要な概念です．

定義と数学的背景

ブロック構造 ${\mathcal{B}}_1,{\mathcal{B}}_2,\cdots ,{\mathcal{B}}_K$ を持つ信号 $\mathbf{x}$ に対して，混合${\ell }_2/{\ell }_1$ノルムは次のように定義されます：

$$\Vert \mathbf{x}{\Vert }_{2,1}^{({\mathcal{B}}_k{)}_{k=1}^K}=\sum _{k=1}^K\sqrt{|{\mathcal{B}}_k|}\Vert {\mathbf{x}}_{{\mathcal{B}}_k}{\Vert }_2$$

ここで，$|{\mathcal{B}}_k|$ はブロック $k$ の要素数，$\Vert {\mathbf{x}}_{{\mathcal{B}}_k}{\Vert }_2$ はブロック $k$ 内の要素の${\ell }_2$ノルムを表します．

重み $\sqrt{|{\mathcal{B}}_k|}$ の重要性

この定義において特筆すべきは，重み $\sqrt{|{\mathcal{B}}_k|}$ の存在です．この重みは単なる正規化項ではなく，以下の重要な役割を果たします：

1. 大きなブロックへのペナルティ強化：ブロックサイズが大きいほど大きなペナルティを課し，すべての要素を1つの巨大なブロックとして扱う自明な解を防ぎます

2. 適切なブロック分解の促進：ゼロ成分と非ゼロ成分が混在する不適切なブロックよりも，純粋な非ゼロブロックの選択を促進します

${\ell }_1$ノルムとの関係性

混合${\ell }_2/{\ell }_1$ノルムは，ブロック構造の設定によって様々なノルムと等価になります：

• ブロック数 = 1（全要素を1つのブロック）：${\ell }_2$ノルムと等価
• ブロック数 = $N$（各要素が独立のブロック）：${\ell }_1$ノルムと等価

このように，${\ell }_1$ノルム と ${\ell }_2$ノルム は混合${\ell }_2/{\ell }_1$ノルムの特殊なケースとして位置づけられます．

近接写像による挙動の違い

${\ell }_1$ノルムの近接写像がソフト閾値処理であるのに対し，混合${\ell }_2/{\ell }_1$ノルムの近接写像はブロック単位での閾値処理を行います．これにより，ブロック内に非ゼロ成分が含まれていても，ブロック全体の評価に基づいてスパース性を判定するため，より構造的な解が得られます．

LOP-${\ell }_2/{\ell }_1$：最適なブロック構造における混合${\ell }_2/{\ell }_1$ノルム

LOP-${\ell }_2/{\ell }_1$（Latent Optimally Partitioned ${\ell }_2/{\ell }_1$）は，適応的ブロックスパース正則化において極めて重要な手法です．従来手法の限界を克服し，理論的にも実用的にも優れた性能を実現します．

凸緩和によるブロック構造推定のNP困難性解消

組合せ最適化問題の困難性

真のブロック構造推定は本来，NP困難な組合せ最適化問題です．信号の長さが$N$の場合，可能なブロック分割の数は指数的に増加するため，厳密な解を求めることは計算的に不可能でした．

${\ell }_2$ノルムの変分表現の活用

LOP-${\ell }_2/{\ell }_1$の核心は，${\ell }_2$ノルムの変分表現（パースペクティブ関数）を巧みに利用した点にあります：

$$\varphi (x,\tau ):=\{\begin{array}{ll}\frac{|x{|}^2}{2\tau }+\frac{\tau }{2}& \text{if }\tau >0\\ 0& \text{if }x=0\text{ and }\tau =0\\ \infty & \text{otherwise}\end{array}$$

この表現により，最適なブロック構造 $({\mathcal{B}}_k^{\ast }{)}_{k=1}^K$ における混合${\ell }_2/{\ell }_1$ノルムは，以下のように（凸緩和を用いて近似的に）変換できます：

$${\Psi }_{\alpha }(\mathbf{x})=\underset{\mathbf{\sigma }\in {\mathbb{R}}^N}{\min }\sum _{n=1}^N\varphi (x_n,{\sigma }_n)\text{ s.t. }\Vert \mathbf{D}\mathbf{\sigma }{\Vert }_1\le \alpha$$

ここで：

• 制約$\Vert \mathbf{D}\mathbf{\sigma }{\Vert }_1\le \alpha$：潜在変数$\mathbf{\sigma }$の滑らかさを制御し，ブロック境界を検出します
• 微分作用素$\mathbf{D}$：隣接要素間の差分を計算します

微分作用素$\mathbf{D}$は，信号の隣接要素間の差分を計算する行列ですが，グラフ構造に対応する隣接行列を用いることで，より複雑な構造の信号にも対応可能です．

潜在変数$\mathbf{\sigma }$の役割

LOP-${\ell }_2/{\ell }_1$における潜在変数$\mathbf{\sigma }$は，「どこで信号を区切ってブロックを作るか」を柔軟に表現する役割を果たします．
具体的には，$\mathbf{\sigma }$の値が滑らかに変化している区間は同じブロック，急激に変化する箇所がブロックの切れ目（境界）となります．
この$\mathbf{\sigma }$を最適化することで，信号全体を「どこで区切ると最も構造的スパース性が高まるか」を自動的に学習できるのがLOP-${\ell }_2/{\ell }_1$の大きな特徴です．

計算効率の改善

LOP-${\ell }_2/{\ell }_1$は線形拡張ラグランジュ法を用いることで，$\mathcal{O}(N)$ の計算量を実現しています．
これは従来手法の$\mathcal{O}(N^3)$と比較して劇的な改善です．

大域的最適解の保証

凸最適化問題として定式化されたため，以下の重要な保証が得られます：

• 初期値によらない収束：どの初期値から開始しても同一の最適解に到達します
• 大域的最適解の保証：局所解に陥ることなく大域的最適解を発見します
• 収束性の理論的保証：適切なパラメータ設定の下で収束が保証されます

これらの特性は，実用的なアプリケーションにおいて非常に重要です．特に，初期値の選択が結果に影響しないため，ユーザーフレンドリーな設計となっています．

パラメータ$\alpha$による柔軟な制御

パラメータ$\alpha$は，推定されるブロック構造を直感的に制御する役割を担います：

• $\alpha \to 0$：少数の大きなブロック（${\ell }_2$ノルム的挙動）
• $\alpha \to \infty$：多数の小さなブロック（${\ell }_1$ノルム的挙動）
• 適切な$\alpha$：真のブロック構造に最も近い分割を自動的に発見します

適切に設定された$\alpha$により，データの構造に応じた最適なブロック分割が得られます．

既存手法に対する優位性

手法	計算量	凸性	収束保証	実用性
貪欲法	$\mathcal{O}(N^3)$	非凸	なし	低
ベイズ的手法	$\mathcal{O}(N^3)$	非凸	なし	低
Latent Group Lasso	$\mathcal{O}(N^3)$*	凸	あり	中
LOP-${\ell }_2/{\ell }_1$	$\mathcal{O}(N)$ **	凸	あり	高

*候補ブロック構造をすべて用いる場合
**観測行列が単位行列などのスパース行列である場合．それ以外の場合は，増加する場合もあるものの，依然として既存手法よりはるかに効率的です．

このアプローチにより，LOP-${\ell }_2/{\ell }_1$は理論的に優れているだけでなく，実用的な時間で高品質な解を得ることが可能な，極めて実用的な適応的ブロックスパース正則化手法となっています．

まとめ

ブロックスパース正則化は，一見すると複雑に思えるかもしれませんが，本質的には「関連する要素をまとめて考慮する」という，極めて自然な発想から生まれた手法です．

特にLOP-${\ell }_2/{\ell }_1$の登場により，「理論的には優れているものの実用性に課題がある」という従来の問題が一挙に解決されたことは，特筆すべき成果です．

LOP-${\ell }_2/{\ell }_1$の応用研究は，現状圧縮センシングや画像処理などの分野で進められています．

ブロックスパース正則化は，異常検知やニューラルネットワークの軽量化など，これら以外の分野でも有用であることが期待されており，今後の研究においても注目されるテーマです．

もしスパース推定に関わる機会がありましたら，ぜひこのブロックスパース正則化も選択肢の一つとしてご検討ください．データに何らかの構造的特性が見られる場合，本手法は非常に有効なアプローチとなるでしょう．

参考文献

技術的な詳細や実装に関心のある方は，以下の文献を参照してください：

[1] H. Kuroda and D. Kitahara, “Block-sparse recovery with optimal block partition,” IEEE Transactions on Signal Processing, vol. 70, pp. 1506–1520, 2022, doi: 10.1109/TSP.2022.3156283.

[2] T. Furuhashi, H. Hontani and T. Yokota, “Adaptive Block Sparse Regularization Under Arbitrary Linear Transform,” 2024 32nd European Signal Processing Conference (EUSIPCO), Lyon, France, 2024, pp. 2437-2441, doi: 10.23919/EUSIPCO63174.2024.10714986.