スパース辞書学習

辞書${\displaystyle \mathbf {D} }$上記で定義されたものは「不完全」である可能性がある。${\displaystyle n<d}$または「過剰に完了」する場合${\displaystyle n>d}$後者は、疎な辞書学習問題における典型的な仮定である。完全な辞書の場合、表現の観点からは何ら改善が見られないため、考慮しない。

不完全な辞書は、実際の入力データが低次元空間に存在する状況を表します。このケースは、次元削減や、原子を必要とする主成分分析などの手法と密接に関連しています。${\displaystyle d_{1},...,d_{n}}$直交性を持つ。これらの部分空間の選択は効率的な次元削減にとって重要であるが、自明ではない。また、辞書表現に基づく次元削減は、データ分析や分類などの特定のタスクに対応するために拡張できる。ただし、主な欠点は、原子の選択肢が制限されることである。

しかし、過剰完全辞書では、原子が直交している必要はありません（そもそも基底を持つことはないからです）。そのため、より柔軟な辞書とより豊かなデータ表現が可能になります。

信号の疎表現を可能にする過剰完全辞書は、有名な変換行列（ウェーブレット変換、フーリエ変換）を用いることもできますし、与えられた信号を最適に疎表現するように要素を変更するように定式化することもできます。学習済みの辞書は、定義済みの変換行列と比較して、より疎な解を与えることができます。

最適方向法（またはMOD）は、疎な辞書学習問題に取り組むために最初に導入された方法の1つです。^{[ 5 ]}その核心的なアイデアは、表現ベクトルの非ゼロ成分の数が限られているという制約の下で最小化問題を解くことです。

${\displaystyle \min _{\mathbf {D} ,R}\{\|X-\mathbf {D} R\|_{F}^{2}\}\,\,{\text{st}}\,\,\forall i\,\,\|r_{i}\|_{0}\leq T}$

ここ、${\displaystyle F}$はフロベニウスノルムを表します。MODは、マッチング追跡などの方法を使用してスパースコーディングを取得することと、次の問題の解析解を計算することによって辞書を更新することを交互に行います。${\displaystyle \mathbf {D} =XR^{+}}$どこ${\displaystyle R^{+}}$これはムーア・ペンローズ擬似逆行列です。この更新後${\displaystyle \mathbf {D} }$制約条件に適合するように正規化を行い、新たなスパースコーディングを再度取得する。このプロセスを収束するまで（または十分小さな残差になるまで）繰り返す。

MODは低次元入力データに対して非常に効率的な手法であることが証明されている。${\displaystyle X}$収束にはわずかな反復しか必要としない。しかし、行列の逆行列計算は非常に複雑であるため、高次元の場合、擬似逆行列の計算は多くの場合困難である。この欠点が、他の辞書学習手法の開発を促した。

K-SVDは、辞書の要素を一つずつ更新するためにSVDをコアとして実行するアルゴリズムであり、基本的にはK-meansの一般化です。入力データの各要素が${\displaystyle x_{i}}$は、以下の線形結合によって符号化される。${\displaystyle T_{0}}$MODアプローチと全く同じ方法で要素を組み込む：

${\displaystyle \min _{\mathbf {D} ,R}\{\|X-\mathbf {D} R\|_{F}^{2}\}\,\,{\text{st}}\,\,\forall i\,\,\|r_{i}\|_{0}\leq T_{0}}$

このアルゴリズムの本質は、まず辞書を固定し、可能な限り最良のものを見つけることです。${\displaystyle R}$上記の制約の下で（直交マッチング追跡法を用いて）辞書の原子を反復的に更新する${\displaystyle \mathbf {D} }$以下の方法で：

${\displaystyle \|X-\mathbf {D} R\|_{F}^{2}=\left|X-\sum _{i=1}^{K}d_{i}x_{T}^{i}\right|_{F}^{2}=\|E_{k}-d_{k}x_{T}^{k}\|_{F}^{2}}$

アルゴリズムの次のステップには、残差行列のランク1近似が含まれます。${\displaystyle E_{k}}$更新中${\displaystyle d_{k}}$そして疎性を強制する${\displaystyle x_{k}}$アップデート後。このアルゴリズムは辞書学習の標準とみなされており、さまざまなアプリケーションで使用されています。ただし、MODと同様に、比較的低次元の信号にしか有効ではなく、局所最適解に陥る可能性があるという弱点があります。

この問題を解決するために、反復射影を伴う広く用いられている確率的勾配降下法を適用することもできる。^{[ 6 ]}この方法の考え方は、一次確率的勾配を用いて辞書を更新し、それを制約集合に射影することである。${\displaystyle {\mathcal {C}}}$i 番目の反復で発生するステップは、次の式で表されます。

${\displaystyle \mathbf {D} _{i}={\text{proj}}_{\mathcal {C}}\left\{\mathbf {D} _{i-1}-\delta _{i}\nabla _{\mathbf {D} }\sum _{i\in S}\|x_{i}-\mathbf {D} r_{i}\|_{2}^{2}+\lambda \|r_{i}\|_{1}\right\}}$、 どこ${\displaystyle S}$はランダムなサブセットです${\displaystyle \{1...K\}}$そして${\displaystyle \delta _{i}}$勾配ステップです。

双対ラグランジュ問題を解くことに基づくアルゴリズムは、スパース性関数によって生じる複雑さのない辞書を解く効率的な方法を提供する。^{[ 7 ]}次のラグランジュを考える。

${\displaystyle {\mathcal {L}}(\mathbf {D} ,\Lambda )={\text{tr}}\left((X-\mathbf {D} R)^{T}(X-\mathbf {D} R)\right)+\sum _{j=1}^{n}\lambda _{j}\left({\sum _{i=1}^{d}\mathbf {D} _{ij}^{2}-c}\right)}$、 どこ${\displaystyle c}$は原子のノルムに対する制約であり、${\displaystyle \lambda _{i}}$は、対角行列を形成するいわゆる双対変数である。${\displaystyle \Lambda }$。

最小化後、ラグランジュ双対の解析的表現を与えることができる。${\displaystyle \mathbf {D} }$:

${\displaystyle {\mathcal {D}}(\Lambda )=\min _{\mathbf {D} }{\mathcal {L}}(\mathbf {D} ,\Lambda )={\text{tr}}(X^{T}X-XR^{T}(RR^{T}+\Lambda )^{-1}(XR^{T})^{T}-c\Lambda )}$。

双対の値に最適化手法（ニュートン法や共役勾配法など）のいずれかを適用すると、次の値が得られます。${\displaystyle \mathbf {D} }$:

${\displaystyle \mathbf {D} ^{T}=(RR^{T}+\Lambda )^{-1}(XR^{T})^{T}}$

この問題を解くのは、双対変数の数が少ないため、計算負荷はそれほど高くない。${\displaystyle n}$多くの場合、それは主問題の変数の数よりもはるかに少ない。

このアプローチでは、最適化問題は次のように定式化されます。

${\displaystyle \min _{r\in \mathbb {R} ^{n}}\{\,\,\|r\|_{1}\}\,\,{\text{subject to}}\,\,\|X-\mathbf {D} R\|_{F}^{2}<\epsilon }$、 どこ${\displaystyle \epsilon }$これは、再構成LASSOにおける許容誤差です。

それは推定値を見つける${\displaystyle r_{i}}$解ベクトルにおけるL1^ノルム制約の下で最小二乗誤差を最小化することにより、以下のように定式化されます。

${\displaystyle \min _{r\in \mathbb {R} ^{n}}\,\,{\dfrac {1}{2}}\,\,\|X-\mathbf {D} r\|_{F}^{2}+\lambda \,\,\|r\|_{1}}$、 どこ${\displaystyle \lambda >0}$疎性と再構成誤差のトレードオフを制御します。これにより、グローバルな最適解が得られます。^{[ 8 ]}スパースコーディングのためのオンライン辞書学習も参照してください。

パラメトリック学習法は、解析的に構築された辞書と学習によって構築された辞書の両方の利点を取り入れることを目的としています。^{[ 9 ]}これにより、任意のサイズの信号にも適用できる可能性のある、より強力な汎用辞書を構築できます。注目すべきアプローチには、次のものがあります。

• 並進不変辞書。^{[ 10 ]}これらの辞書は、有限サイズの信号パッチ用に構築された辞書から生じる原子の並進によって構成されます。これにより、結果として得られる辞書は、任意のサイズの信号の表現を提供できます。
• マルチスケール辞書。^{[ 11 ]}この方法は、スパース性を向上させるために、異なるスケールの辞書で構成される辞書を構築することに焦点を当てています。
• スパース辞書。^{[ 12 ]}この方法は、スパース表現を提供するだけでなく、式によって強制されるスパース辞書を構築することにも焦点を当てています。${\displaystyle \mathbf {D} =\mathbf {B} \mathbf {A} }$どこ${\displaystyle \mathbf {B} }$高速計算などの望ましい特性を持つ事前定義された分析辞書であり、${\displaystyle \mathbf {A} }$これは疎行列です。このような定式化により、解析辞書の高速な実装と疎行列アプローチの柔軟性を直接組み合わせることが可能になります。

スパース辞書学習の多くの一般的なアプローチは、入力データ全体が${\displaystyle X}$アルゴリズムには、（少なくとも十分な大きさのトレーニングデータセット）が利用可能であることが前提となります。しかし、実際のシナリオでは、入力データのサイズが大きすぎてメモリに収まらない場合があるため、必ずしもそうとは限りません。この前提が成り立たないもう1つのケースは、入力データがストリーム形式で提供される場合です。このようなケースは、オンライン学習の研究分野に見られます。オンライン学習では、基本的に新しいデータポイントに基づいてモデルを繰り返し更新することが求められます。${\displaystyle x}$利用可能になります。

辞書はオンラインで次のように学習できます。^{[ 13 ]}

1. のために${\displaystyle t=1...T:}$
2. 新しいサンプルを描画する${\displaystyle x_{t}}$
3. LARSを使用してスパースコーディングを見つける：${\displaystyle r_{t}={\underset {r\in \mathbb {R} ^{n}}{\text{argmin}}}\left({\frac {1}{2}}\|x_{t}-\mathbf {D} _{t-1}r\|+\lambda \|r\|_{1}\right)}$
4. ブロック座標方式を使用して辞書を更新する：${\displaystyle \mathbf {D} _{t}={\underset {\mathbf {D} \in {\mathcal {C}}}{\text{argmin}}}{\frac {1}{t}}\sum _{i=1}^{t}\left({\frac {1}{2}}\|x_{i}-\mathbf {D} r_{i}\|_{2}^{2}+\lambda \|r_{i}\|_{1}\right)}$

この方法を用いることで、疎表現学習のための新しいデータが利用可能になった際に辞書を段階的に更新することができ、データセット（多くの場合、膨大なサイズになる）を保存するために必要なメモリ量を大幅に削減できます。