[DL輪読会]“Submodular Field Grammars Representation” and “Deep Submodular Functions”

1 DEEP LEARNING JP [DL Papers] “Submodular Field Grammars Representation” and “Deep Submodular Functions” Kensuke Wakasugi, Panasonic Corporation. http://deeplearning.jp/

• http://deeplearning.jp/

発表内容 2 NeurIPS2018にて発表された論文の内， タイトルにSubmodularを含む論文は計13本(うち口頭発表2本) そのうち，以下の2本について紹介します． ■Submodular Field Grammars Representation, Inference, and Application to Image Parsing ■Submodular Maximization via Gradient Ascent The Case of Deep Submodular Functions Wakasugi, Panasonic Corp.

サブモジュラーとは 3 集合関数がサブモジュラー性を有すると，その関数の効率的な最小化/最大化が可能 ■サブモジュラー関数とは(Wikipedia劣モジュラー関数より引用) 台集合 Ω の冪集合 2Ω 上の関数 f: 2Ω →ℝで 次を満たす関数を劣モジュラ関数と呼ぶ。 劣モジュラ性 任意の集合対 S, T ⊆ Ω に対して、f(S) + f(T) ≥ f(S ∪ T) + f(S ∩ T) この不等式を劣モジュラ不等式と呼ぶ。 また、上記の不等式と以下の 2 つの不等式は同値である。 １、任意の集合対X，Y ⊆ Ω ， X ⊆ Y と任意の x ∊ Ω＼Y に対して、 f(X∪{x}) – f(X) ≥ f(Y∪{x}) – f(Y) ←限界効用逓減(diminishing return) ２、集合対X ⊆ Ω と任意の x1，x2 ∊ Ω＼X に対して、 f(X∪{x1}) + f(X∪{x2}) ≥ f(X∪{x1,x2}) + f(X)  実問題に適用する場合は，対象となる問題(一般に非凸)の目的関数がサブモジュラー性を 有する場合，サブモジュラー性を利用した最適化アルゴリズムを用いることができる． 劣モジュラ関数＠Wikipedia：https://ja.wikipedia.org/wiki/%E5%8A%A3%E3%83%A2%E3%82%B8%E3%83%A5%E3%83%A9%E9%96%A2%E6%95%B0 Wakasugi, Panasonic Corp.

サブモジュラー関数の応用 4 最適化が容易な関数に拡張する ■最小化を行う場合(多項式時間で解ける) ロバース拡張： 𝑛 min 𝑛 𝐹(𝑥) → min 𝑛 𝑓(𝑥) 𝑥∈ 0,1 𝑥∈[0,1] 𝑓 𝑥 = 𝛼𝑖 𝐹(𝑆𝑖 ) 𝑖=1 ただし， 𝛼𝑖 と𝑆𝑖 は以下のように定める. 𝑥を大きさ順に並べ替えたとき， 𝑥𝜋1 ≥ 𝑥𝜋2 ≥ ⋯ ≥ 𝑥𝜋𝑛 𝑆𝑖 = 𝑆𝑖−1 ∪ {𝜋𝑖 } 𝛼𝑖 = 𝑥𝜋𝑖 − 𝑥𝜋𝑖−1 ■最大化を行う場合(NP困難 多重線形拡張： → 制約を付け，多項式時間で解けるアルゴリズムが研究されている) max 𝐹(𝑥) → max 𝑛 𝑓(𝑥) 𝑥∈ 0,1 𝑛 𝑥∈[0,1] 𝑓 𝑥 = 𝑥𝑖 𝑆∈2𝑁 𝑖∈𝑆 1 − 𝑥𝑖 𝐹(𝑆) 𝑖∈𝑁∖𝑆  関数の拡張自体は，サブモジュラー性とは無関係．超立方の頂点で関数値が等しい関数になっている  元の集合関数がサブモジュラー性を有する ⇔ 拡張した関数が最適化しやすい Wakasugi, Panasonic Corp.

サブモジュラーの概観 5 • 論文内容の分類  最大化 or 最小化  モノトーン or 非モノトーン  問題設定として， 近似率の改善(最大化の場合)，計算コストの改善，問題設定の拡張，実問題への応用 • 論文を読む時の注意点 – サブモジュラーの表式やノーテーションが揺らぐ（以下1～３式は同値） １、f(S) + f(T) ≥ f(S ∪ T) + f(S ∩ T) ２、f(X∪{x}) – f(X) ≥ f(Y∪{x}) – f(Y) ３、f(X∪{x1}) + f(X∪{x2}) ≥ f(X∪{x1,x2}) + f(X) ちなみに下式は多重線形拡張後の連続変数に対する関数で，これも劣モジュラー関数といわれる F(x)+F(y)≧F(x∨y)+F(x∧y) ，ただし，(x∨y)i =max(xi ,yi ), (x∧y)i =min(xi ,yi ) – 最大化/最小化による課題設定の違いが大きい 最小化：多項式時間で解ける→厳密解の計算コストなどを議論 最大化：NP困難→近似率とその計算コスト，新たな制約を加えた元で高速な求解を実現 Wakasugi, Panasonic Corp.

書誌情報 6 タイトル： Submodular Field Grammars Representation, Inference, and Application to Image Parsing 著者：Abram L. Friesen and Pedro Domingos 所属：University of Washington その他：NIPS，ICMLなどのpaperが多数．最適化の論文が中心だが，DLの論文もある. 現在はDeepMindで働いているらしい. ※別途明示しない限り，P10までの図表などは上記論文から引用 Wakasugi, Panasonic Corp.

背景 7 自然画像の意味理解のために，パースを効率的に行いたい  具体的には，深層学習などによるセグメン テーションに，ラベル間の階層構造や画素値 のマルコフ性を使って，性能向上を図る  しかし，画素値に対するマルコフランダム フィールド(MRF)制約下の事後確率最大化 (MAP)は計算コストが高い．  サブモジュラー性を持ったパースを構築する ことで，効率的なパースを可能に． 引用：Song-Chun Zhu and David Mumford. A stochastic grammar of images. Foundations and Trends in Computer Graphics and Vision, 2(4):259–362, 2006. Wakasugi, Panasonic Corp.

提案手法 8 サブモジュラー性を満たす階層的なパースを定義 MRFにおけるエネルギーの定義： このとき，以下を満たせば，上記エネルギーがサブモジュラー性を有する →ざっくりと・・・ 任意の画素集合p,qに対し，同一ラベルを割り当てたときのpq間エッジのエネルギーは 異なるラベルを割り当てたときのpq間エッジのエネルギーよりも小さい．  画像全体に単一のラベルを割り当てた状態から， 画像分割とラベル割り当てを繰り返す．  S→ABなど，ラベルからラベルへの割り当て関係を 循環しないパースツリーとして事前に定義する． Wakasugi, Panasonic Corp.

パースツリーの推定 9 与えられたGrammarを元に，最適なセグメンテーションを算出  Grammarを元に， 画像全体に単一ラベルを割り当てた状態から， 最適なセグメンテーションを推定していく. Wakasugi, Panasonic Corp.

実験結果 10 提案手法(SFG)により，性能を保持しつつ，実行時間を短縮  パースツリーの分割数，深さ， MRFのパラメータを変えて検証  特に，実行時間が 指数関数的 → 線形に短縮  セグメンテーションの性能も向上 Wakasugi, Panasonic Corp.

書誌情報 11 タイトル： Submodular Maximization via Gradient Ascent: The Case of Deep Submodular Functions 著者：Wenruo Bai, William S Noble, Jeff A. Bilmes 所属：University of Washington その他：リサーチアシスタント. 過去の研究として，以下を挙げている. ・機械学習によるペプチドの同定 ・教師なしマルチラベルセグメンテーション ・サブモジュラー関数の最適化レートの改善 ※別途明示しない限り，P18までの図表などは上記論文から引用 Wakasugi, Panasonic Corp.

背景 12 サブモジュラー性を保持する変換を定義し，学習可能であることが示されている  先行研究(といっても同じ研究グループだが)で， 深層NNに似た構造のサブモジュラー関数が 定義可能であると示されている →NN全体でサブモジュラー性を有する  いくつかのサブモジュラー関数クラスの 上位クラスとなっており，表現能力が高い  この論文では，学習アルゴリズムの提案と， その収束の速さを実証． Wakasugi, Panasonic Corp.

Deep Submodular Functionsの表現能力 13 DSFは特徴選択問題，設備配置問題などの上位クラス 特徴選択問題 設備配置問題 Wakasugi, Panasonic Corp.

DSFの構成 14 深層学習と同じ形式で，サブモジュラー関数を積層  深層学習と同じ形式で表現することで， 深層学習ライブラリで実装可能 →CPU演算よりも高速に求解できる Wakasugi, Panasonic Corp.

収束性の証明 15 単純な連続変数への拡張と多重線形拡張とを比較し，収束性を議論 ・単純な連続変数への拡張 ・多重線形拡張  厳密な値は指数関数的な計算コストのため，通常は近似計算（サンプリング）が必要 Wakasugi, Panasonic Corp.

収束性の証明 16 F(x)は多重線形拡張の厳密な評価値に対して，一定の誤差以下になる  一定の誤差の範囲内の評価値をサンプリングせずに得られる →計算コストが低減できる Wakasugi, Panasonic Corp.

F(x)の最適化 17 Supergradient（=Back Propagation）によって最適化が可能  深層学習のフレームワークがそのまま利用可能 →GPU演算の高速化の恩恵を得られる Wakasugi, Panasonic Corp.

評価実験 18 k>1000において，従来法に比べ実行時間を低減  比較のためCPUで計算しており，GPUを使えばもっと速くなるとのこと. Wakasugi, Panasonic Corp.

まとめ 19 ■Submodular Field Grammars Representation, Inference, and Application to Image Parsing  画像セグメンテーションにおいて，ラベルに関するパースにサブモジュラー性を導入. セグメンテーションの後処理として，MRFによる推定を行い，高速化と性能向上を実現. ■ Submodular Maximization via Gradient Ascent: The Case of Deep Submodular Functions  サブモジュラー関数を深層学習と同じ形式で定義． 関数の表現能力を向上したうえで，計算効率化(収束性の向上，GPUを利用可能に). Wakasugi, Panasonic Corp.