【ML Tech RPT. 】第18回構造に関連する機械学習を学ぶ (4)　~格子構造~

f:id:ssatsuki040508:20181210005017p:plain
DSOC研究員の吉村です。最近は朝ごはんを完全ルーティーン化していて、ヨーグルトにフルーツグラノーラを入れたのを毎日食べてます。これを続ける中でわかったことですが、ヨーグルトはプレーンじゃないとフルーツグラノーラに合いません。

さて、今回も構造に関する機械学習の話題について見ていきましょう。今回は格子構造についてです。格子構造自体はグラフ構造の特殊な場合として考えられますが、隣り合う点同士が相互に全て接続されているところが特徴的です。例えば、画像を構成している構造がまさに格子構造ですが、この場合には位置が近いピクセル同士は何らか関係があると考えられるので、そういった情報を用いてタスクを取り扱っていくことになります。他の例としては、機械学習というよりはむしろ離散最適化周りの文脈で、整数格子点上の劣モジュラ関数に関する話題などがあります。

そこで下記では、画像の構造に着目した扱い方と整数格子点上の劣モジュラ関数に関する説明をしていきます。

画像の構造に着目した扱い方

今回は(画像の)セマンティックセグメンテーションについて書いていこうと思います。セマンティックセグメンテーションとは、画像の領域が何を意味するかをピクセル毎にラベル付けするタスクです。深層学習が浸透した現在では、普通 U-NET [*1] などの手法を用いることが多いと思います。これはセマンティックセグメンテーション以外の画像に関する様々な問題設定においても言えることですが、基本的にはフィルタと呼ばれる注目するピクセルとその周囲のピクセルに対して重みをつけて処理すること (いわゆる畳み込み, 英語では Convolution) で、格子情報を利用していると考えられます。畳み込みについては世の中にたくさんのわかりやすい説明があると思いますので、ここでは割愛します。

セマンティックセグメンテーションを実現する方法には、グラフカットを用いるものがあります [*2, *3]。ここでは、簡単のためにセグメンテーションを前景と後景に分割する二値の場合を考えます。さて、グラフカットとは簡単に説明すると、グラフ $G(V, E)$ について、始点ノード $s$ と終点ノード $t$ が与えられているときに、このグラフ $G(V, E)$ をコストに基づいて始点を含むノード集合 $S$ と終点を含むノード集合 $T$ の二つに分割する問題設定です。ここでいう、コストとはノード集合 $S$ とノード集合 $T$ との間のエッジの重みの合計を指します。このコストをうまく設定することでセマンティックセグメンテーションをグラフカットで解くことができます。このコストを最小にするようにグラフカットを求める問題設定を最小カットと呼び、最大費用流問題に帰着させることができます。このことから、最小カットはエッジの重みが全て非負の時には多項式時間で最適解を得ることができます。

グラフカットによるセグメンテーションのアイデアは、このコストを前景らしさのコストと隣接するピクセル間の色差によるコストを組み合わせたもので定義することで、前景と後景を分割するというものです。したがって、実のところグラフカットを用いたアルゴリズムの方は必ずしも対象が格子構造である必要はないです。なぜなら、各ピクセルの前景らしさと、ピクセル間の繋がり情報を扱うことができさえすればこの方法は使えるためです。また、グラフカットによるセグメンテーションはパラメータチューニングが難しいので、うまく機能させるのは難しいようです。

整数格子点上の劣モジュラ関数

こちらは、私もまだ十分に理解が追いついていないのでざっくりとした内容を説明します。一旦「整数格子点上」という部分は置いておいて、劣モジュラ関数 (submodular function) [*4]から説明します。

任意の $X, Y \subseteq V$ に対して、
$f(X) + f(Y) \geq f(X\cup Y) + f(X \cap Y) \tag{1}$ を満たす集合関数 $f:2^V\rightarrow \mathbb{R}$ を劣モジュラ関数と呼ぶ。

集合関数とは集合を入力とする関数のことです。上記の定義だけだとちょっとピンと来ないかもしれないので、もう一つの同値な定義も紹介しておきます。

任意の $X \subseteq Y \subseteq V$ と $e \in V \backslash Y$ に対して、
$f(X \cup \{ e\}) - f(X) \geq f(Y \cup \{e\}) - f(Y) \tag{2}$ を満たす集合関数 $f:2^V\rightarrow \mathbb{R}$ を劣モジュラ関数と呼ぶ。

この定義では、大きい集合にある要素を一つ追加する時よりも、小さい集合にその要素を一つ追加する時の関数の増分の方が常に(等しいか)大きい性質を表しています。これは 限界効用逓減性 と呼ばれる性質です。実世界では、例えば「ものを買う時に既に持っているものを買うよりも持っていないものを買った方が嬉しい」といったような状況を表すときなどに用いられており、他にも、劣モジュラ関数に関連する問題設定としては、文書要約、影響力最大化、センサー配置問題などがあります。

劣モジュラ関数を扱う嬉しさは、本来であればかなり困難である離散最適化のいくつかの問題が効率的に解けるところにあります。例えば、劣モジュラ関数最小化問題 [*5] は、最適解を得るための多項式時間アルゴリズムが作れることが知られています。また、劣モジュラ性に加えて 単調性 ( $f(X)\leq f(Y), (X \subseteq Y)$ ) も併せ持つ、単調劣モジュラ関数の最大化問題については、NP困難であることが知られているものの、(1-1/e)-近似アルゴリズムが作れることがわかっています。

さて、ここからが「整数格子点上」の話です。ちなみにここでの格子は英語では lattice と訳されます。上記の劣モジュラ関数では、各要素を選ぶか選ばないかの場合にしか対応していませんでした。しかし、問題設定によってはそれだけでは不十分な場合があります。代表的なものが最適予算配分問題です。最適予算配分問題は、より多くの人にリーチしたいという目的において、様々な広告媒体にいくらずつ予算を投下するとリーチできる人の数を最大化できるかを明らかにする問題設定です。ここで、どの広告媒体を選ぶか選ばないかだけでなく、選んだものに対していくら予算を投下するかという選択肢も含まれるために元々の劣モジュラ関数では対応できません。そこで、劣モジュラ関数に関する最適化手法を整数格子点上に拡張することで、この最適予算配分問題などを効率的に解くことができます。

まとめ

今回は格子構造に関連する機械学習の話題をまとめました。格子構造は、ほとんどはグラフ構造の特殊な場合として扱われると思います。しかし、整数格子点上の劣モジュラ関数などの、より格子構造としての(というより整数としての)性質に着眼した話題もありますので、そちらも少し紹介しました。次回はグラフに関する話題を書いていく予定ですので、引き続きよろしくお願いします。

▼【ML Tech RPT. 】シリーズ
buildersbox.corp-sansan.com

*1:O. Ronneberger, P. Fischer, and T. Brox, "U-Net: Convolutional Networks for Biomedical Image Segmentation," in 2015, MICCAI.

*2:C. Rother, V. Kolmogorov, and A. Blake, "“GrabCut” — Interactive Foreground Extraction using Iterated Graph Cuts," in 2004, SIGGRAPH.

*3:⽯川博, "グラフカットの理論と応用," in 2008, 画像センシングシンポジウム.

*4:相馬輔, "整数格子点上の劣モジュラ最大化と近似アルゴリズム," in 2018, オペレーションズ・リサーチ.

*5:永野清仁, "機械学習分野における離散最適化手法の応用研究～離散凸最適化を中心に～," in 2012.