機械学習とかコンピュータビジョンとか

CVやMLに関する勉強のメモ書き。

Deep Graph Laplacian Regularizationを読んだのでメモ

はじめに

Deep Graph Laplacian Regularizationを読んだのでメモ.

気持ち

ノイズ除去等の逆問題は通常不良設定問題であるた、なんらかのpriorを仮定して解く必要がある.よく知られているpriorとしてtotal variation priorやsparsity prior,graph Laplacian regularizerなどがあげられる.最近だとCNNによる力技でかなり精度良く逆問題を解けるようになっている.ただCNNは学習ベースであるためデータセットの収集問題があったり,ハイパーパラメータの調節問題等があって扱いにくい面もある.対してモデルベースなアプローチでは一般的に学習ベースなものよりもロバストであると言われているが,実践的にはパフォーマンスと柔軟性に限界がある.

そこで学習ベースとモデルベースのいいとこ取りをすれば完璧じゃないかというのが話の流れ.そこの橋渡しを行うためにgraph Laplacian regularizerをdeep learningの枠組みに取り入れるというのが論文のコントリビューション.

Graph Laplacian regularization

Graph Laplacian regularizationはその単純さとまずまずの性能からrestoration taskにおいて画像のpriorとして広く使われているらしい.簡単に言えばある画像\mathbf{x}\in\mathbb{R}^mが適切選ばれたグラフ\mathcal{G}に従って滑らかになるようにするもので,2次計画問題(QP)に使われることが多い.グラフの選び方はopen questionでいろいろなやり方が取られているが,この論文では単純な隣接グラフを使う.ただし,隣接グラフはCNNの出力から計算される点が一つ重要な点で,従来もdeepの枠組みにgraph Laplacian regularizationを取り入れた研究はあるがそれらは固定の関数を使っていてdata-drivenになっていないとのこと.

定式化

ここでは以下のように定式化されるノイズ除去の問題に焦点を絞る.

\displaystyle
\mathbf{y}=\mathbf{x}+\mathbf{n}

\mathbf{x}\in\mathbb{R}^mは元画像またはそのパッチでmピクセル数を表す.\mathbf{n}はノイズ項で\mathbf{y}は観測値.ここで,m個のピクセルを頂点とした隣接グラフ\mathcal{G}が与えられたとする.ノードijを結ぶ重み付きのエッジをw_{ij}とすれば,\mathcal{G}のadjacency matrix \mathbf{A}i,j要素がw_{ij}となるm\times m行列になる.すると\mathcal{G}のdegree matrix \mathbf{D}は対角要素が\sum_{j=1}^mw_{ij}となる対角行列になる.この時のグラフラプラシアン \mathbf{L}\mathbf{L}=\mathbf{D}-\mathbf{A}で計算される半正定値行列となる.

ノイズ除去のためのgraph Laplacian regularization付きのmaximum a posteriori problemは次のように定式化される.

\displaystyle
\mathbf{x}^\ast=\mathrm{arg}\min_\mathbf{x}||\mathbf{y}-\mathbf{x}||^2_2+\mu\cdot\mathbf{x}^T\mathbf{L}\mathbf{x}

第2項目がgraph Laplacian regularizationの項で\mu\geq 0はハイパーパラメータ.ここではグラフ\mathcal{G}は真の画像構造を反映したグラフになっている必要がある.従来は観測値\mathbf{y}やフィルタリング処理を施した\mathbf{y}からグラフを作る.\mathbf{L}=\mathbf{D}-\mathbf{A}であることを考えれば,graph Laplacian regularizationはグラフのエッジの値が大きいピクセル同士の値は似た値になるように仕向ける役割をしている.つまり,TVのような上下左右のピクセルで滑らかになるようにではなく,グラフの接続が強いピクセルで滑らかになる様にするため柔軟性が強い正則化になっている.

説明のためmatrix-valued function \mathbf{F}(\mathbf{Y}):\mathbb{R}^m\rightarrow\mathbb{R}^{m\times N}を定義する.\mathbf{F}(\mathbf{y})n行が\mathbf{f}_n\in\mathbb{R}^m,\:1\leq n\leq Nで定義されていて,観測値\mathbf{y}N個のm次元ベクトル\{\mathbf{f}_n\}_{n=1}^Nにmapする.この\mathbf{f}_nはexemplarと呼ばれexemplarを使えばエッジの重みw_{ij}は次の様に計算される.

\displaystyle
w_{ij}=\exp\left(-\frac{\mathrm{dist}(i,j)}{2\epsilon^2}\right) \\ \displaystyle
\mathrm{dist}(i,j)=\sum_{n=1}^N(\mathbf{f}_n(i)-\mathbf{f}_n(j))^2

\mathbf{f}(i)\mathbf{f}_ni番目の要素を表し,\mathrm{dist}(\cdot,\cdot)ピクセルi,j間のユークリッド距離で定義される.

Deep graph Laplacian regularization (DeepGLR)

提案手法のDeepGLRは二つのモジュールから構成されていて,一つはグラフを作るgraph construction moduleでもう一つは構成されたグラフを使って問題を解くQP solver.

Graph Laplacian regularization layer

この論文では従来と違い,graph Laplacian regularizationをCNNのモジュールとして組み込む.基本的には\mathbf{F}をCNNにしたというもの(これを\mathrm{CNN}_\mathbf{F}とする).観測画像を\mathcal{Y}と定義し,観測画像をK個のパッチ\{\mathbf{y}_k\}_{k=1}^Kに分割する.一般的にはパッチ毎に処理するが,ここでは\mathcal{Y}全体を入力し,\mathcal{Y}と同じサイズのN個のexemplar\{\mathcal{F}\}_{n=1}^{N}を出力とする.

Exemplar画像をK個のパッチ\mathbf{f}_n^{(k)}\in\mathrm{R}^m,\:1\leq kale Kに分割し,パッチごとにグラフ\mathcal{k}_kを作る.ただし,グラフは前結合ではなく8近傍のみを使って作る.こうすることによってグラフラプラシアン\mathbf{L}_kは固定のパターンを持つスパースな行列になる.グラフができたら後はそれをQP solverに渡してノイズ除去された画像\mathbf{x}_k^\ast\:(1\leq k\leq K)を得る.

DeepGLRはグラフの作成とは別にもう二つのCNN(\mathrm{CNN}_\mu\mathrm{CNN}_\hat{\mathcal{Y}})を持つ.

1.Generation of \mu (\mathrm{CNN}_\mu) 目的関数の正則化項の重み係数\{\mu_k\}^K_{k=1}を出力するCNN.

2.Pre-filtering (\mathrm{CNN}_\hat{\mathcal{Y}}) ノイズ除去手法では一般的に最適化の前にノイズ画像\mathcal{Y}にフィルタリング処理を行うが,それを学習ベースで行うための浅いCNN.

つまるところ画像からグラフを作るための\mathrm{CNN}_\mathbf{F}と,前処理を行う\mathrm{CNN}_\hat{\mathcal{Y}}正則化項の係数を決める\mathrm{CNN}_\muの3つからなる.

実験においてはノイズ除去の手続きをT回繰り返す,つまりT個のDeepGLRモデルを積み上げて処理を行う.さらに,QP solverで逆問題を解くだけでなく正解の画像を使った次のMSEの最小化する様に学習する.

\displaystyle
L_{\mathrm{res}}\left(\mathcal{X}^{(gt)},\mathcal{X}_T\right)=\frac{1}{HW}\sum_{i=1}^H\sum_{j=1}^W\left(\mathcal{x}^{(gt)}(i,j)-\mathcal{X}_T(i,j)\right)^2

この最小化に関してはstackされたDeepGLRの最終出力のみに適用される.

Numerical Stability

ここではQP solverの安定性について考える.元々のgraph Laplacian regularization付きの目的関数は本質的には次の線型方程式を解くことになる.

\displaystyle
(\mathbf{I}+\mu\mathbf{L})\mathbf{x}^\ast=\mathbf{y}

Lは半正定値行列なため(\mathbf{I}+\mu\mathbf{L})^{-1}逆行列が存在するため,\mathbf{x}^\ast=(\mathbf{I}+\mu\mathbf{L})^{-1}\mathbf{y}というclosed-formな解を持つ.問題としては\mathbf{I}+\mu\mathbf{L}の条件数\kappa(最小固有値/最大固有値)が大きいときunstableになってしまう.ただし,ここでは次の定理を利用すれば安定した計算をすることができる.

\displaystyle
\kappa\leq 1+2\mu d_{\mathrm{max}}

ただし,d_{\mathrm{max}}\mathcal{G}の最大度数.

証明

\mathrm{L}の性質から\mathrm{I}+\mu\mathrm{L}の最小固有値\lambda_{\mathrm{min}}=1となる.Gershgorin circle theoremから\lambda_{\mathrm{max}}の上界が次の様に定まる.\mathrm{L}i番目のGershgorin discは半径r_i=\sum_{j\neq i}|w_{ij}|\leq d_{\mathrm{max}}を持ち,disc iの中心は1+\mu r_iとなる.Gershgorin circle theoremから固有ベクトルは全てのGershgorin discのunionに存在するため,\lambda_{\mathrm{max}}\leq \max_i\{1+2\mu r_i\}となり,\kappa=\lambda_{\mathrm{max}}\leq 1+2\mu d_{\mathrm{max}}が成り立つ.

以上から条件数の最大を\kappa_\max\geq 1+2\mu d_\maxとすれば次の関係が導かれる.

\displaystyle
\mu\leq\frac{\kappa_\max-1}{2d_\max}=\mu_\max

よってもし\mathrm{CNN}_\mu\mu_\maxより大きな値を出力した場合には,出力値を\mu_\maxに切ることで安定性を持たせることができる.実験的には\kappa_\max=250としたそう.

まとめ

そもそもGraph Laplacian regularizationなるものの存在を知らなかったのでいい勉強になった.途中でてきたGershgorin circleはRNNの初期化に関する論文で前に見たことあったけど完全に忘れていた.