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として広く使われているらしい.簡単に言えばある画像が適切選ばれたグラフに従って滑らかになるようにするもので,2次計画問題(QP)に使われることが多い.グラフの選び方はopen questionでいろいろなやり方が取られているが,この論文では単純な隣接グラフを使う.ただし,隣接グラフはCNNの出力から計算される点が一つ重要な点で,従来もdeepの枠組みにgraph Laplacian regularizationを取り入れた研究はあるがそれらは固定の関数を使っていてdata-drivenになっていないとのこと.
定式化
ここでは以下のように定式化されるノイズ除去の問題に焦点を絞る.
は元画像またはそのパッチではピクセル数を表す.はノイズ項では観測値.ここで,個のピクセルを頂点とした隣接グラフが与えられたとする.ノードとを結ぶ重み付きのエッジをとすれば,のadjacency matrix は要素がとなる行列になる.するとのdegree matrix は対角要素がとなる対角行列になる.この時のグラフラプラシアン はで計算される半正定値行列となる.
ノイズ除去のためのgraph Laplacian regularization付きのmaximum a posteriori problemは次のように定式化される.
第2項目がgraph Laplacian regularizationの項ではハイパーパラメータ.ここではグラフは真の画像構造を反映したグラフになっている必要がある.従来は観測値やフィルタリング処理を施したからグラフを作る.であることを考えれば,graph Laplacian regularizationはグラフのエッジの値が大きいピクセル同士の値は似た値になるように仕向ける役割をしている.つまり,TVのような上下左右のピクセルで滑らかになるようにではなく,グラフの接続が強いピクセルで滑らかになる様にするため柔軟性が強い正則化になっている.
説明のためmatrix-valued function を定義する.は行がで定義されていて,観測値を個の次元ベクトルにmapする.このはexemplarと呼ばれexemplarを使えばエッジの重みは次の様に計算される.
はの番目の要素を表し,はピクセル間のユークリッド距離で定義される.
Deep graph Laplacian regularization (DeepGLR)
提案手法のDeepGLRは二つのモジュールから構成されていて,一つはグラフを作るgraph construction moduleでもう一つは構成されたグラフを使って問題を解くQP solver.
Graph Laplacian regularization layer
この論文では従来と違い,graph Laplacian regularizationをCNNのモジュールとして組み込む.基本的にはをCNNにしたというもの(これをとする).観測画像をと定義し,観測画像を個のパッチに分割する.一般的にはパッチ毎に処理するが,ここでは全体を入力し,と同じサイズの個のexemplarを出力とする.
Exemplar画像を個のパッチに分割し,パッチごとにグラフを作る.ただし,グラフは前結合ではなく8近傍のみを使って作る.こうすることによってグラフラプラシアンは固定のパターンを持つスパースな行列になる.グラフができたら後はそれをQP solverに渡してノイズ除去された画像を得る.
DeepGLRはグラフの作成とは別にもう二つのCNN(と)を持つ.
1.Generation of () 目的関数の正則化項の重み係数を出力するCNN.
2.Pre-filtering () ノイズ除去手法では一般的に最適化の前にノイズ画像にフィルタリング処理を行うが,それを学習ベースで行うための浅いCNN.
つまるところ画像からグラフを作るためのと,前処理を行うと正則化項の係数を決めるの3つからなる.
実験においてはノイズ除去の手続きを回繰り返す,つまり個のDeepGLRモデルを積み上げて処理を行う.さらに,QP solverで逆問題を解くだけでなく正解の画像を使った次のMSEの最小化する様に学習する.
この最小化に関してはstackされたDeepGLRの最終出力のみに適用される.
Numerical Stability
ここではQP solverの安定性について考える.元々のgraph Laplacian regularization付きの目的関数は本質的には次の線型方程式を解くことになる.
は半正定値行列なためは逆行列が存在するため,というclosed-formな解を持つ.問題としてはの条件数(最小固有値/最大固有値)が大きいときunstableになってしまう.ただし,ここでは次の定理を利用すれば安定した計算をすることができる.
.
ただし,はの最大度数.
証明
の性質からの最小固有値はとなる.Gershgorin circle theoremからの上界が次の様に定まる.の番目のGershgorin discは半径を持ち,disc の中心はとなる.Gershgorin circle theoremから固有ベクトルは全てのGershgorin discのunionに存在するため,となり,が成り立つ.
以上から条件数の最大をとすれば次の関係が導かれる.
よってもしがより大きな値を出力した場合には,出力値をに切ることで安定性を持たせることができる.実験的にはとしたそう.
まとめ
そもそもGraph Laplacian regularizationなるものの存在を知らなかったのでいい勉強になった.途中でてきたGershgorin circleはRNNの初期化に関する論文で前に見たことあったけど完全に忘れていた.