>100 Views
March 29, 19
スライド概要
2019/03/29
Deep Learning JP:
http://deeplearning.jp/seminar-2/
DL輪読会資料
1 DEEP LEARNING JP [DL Papers] “Submodular Field Grammars Representation” and “Deep Submodular Functions” Kensuke Wakasugi, Panasonic Corporation. 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 つの不等式は同値である。 1、任意の集合対X,Y ⊆ Ω , X ⊆ Y と任意の x ∊ Ω\Y に対して、 f(X∪{x}) – f(X) ≥ f(Y∪{x}) – f(Y) ←限界効用逓減(diminishing return) 2、集合対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~3式は同値) 1、f(S) + f(T) ≥ f(S ∪ T) + f(S ∩ T) 2、f(X∪{x}) – f(X) ≥ f(Y∪{x}) – f(Y) 3、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.