劣モジュラ関数

数学の分野において劣モジュラ関数 (英: submodular function) とは集合関数の一種で、簡単にいうと、関数に渡される集合に1つ要素が加わった場合に増える関数の値が、もとの集合が大きくなるにつれ小さくなるような関数を指す。集合関数であることを明示して劣モジュラ集合関数ということもある。劣モジュラ関数の概念は一般のベクトル値関数における凸関数の概念と類似した性質を持つため、近似アルゴリズムやゲーム理論、機械学習などの幅広い応用を持つ。

定義

台集合 $Ω$ の冪集合 $2 Ω$ 上の関数 $f : 2 Ω \to R$ で次を満たす関数を劣モジュラ関数と呼ぶ。

劣モジュラ性: 任意の集合対 $S, T \subseteq Ω$ に対して、 $f (S) + f (T) \geq f (S \cup T) + f (S \cap T)$

この不等式を劣モジュラ不等式と呼ぶ。なお、不等号の向きを逆にした不等式を優モジュラ不等式と呼び、それを満たす集合関数を優モジュラ関数と呼ぶ。

また、上記の不等式と以下の 2 つの不等式は同値である。

任意の集合対 $X,Y\subseteq \Omega ,X\subseteq Y$ と任意の $x\in \Omega \backslash Y$ に対して、 $f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)$
任意の集合 $X\subseteq \Omega$ と $x_{1},x_{2}\in \Omega \backslash X,x_{1}\neq x_{2}$ に対して、 $f(X\cup \{x_{1}\})+f(X\cup \{x_{2}\})\geq f(X\cup \{x_{1},x_{2}\})+f(X)$

非負の劣モジュラ関数は劣加法的であるが、劣加法的関数が必ずしも劣モジュラとは限らない。

劣モジュラ関数の例

ここでは劣モジュラ関数の例として、単調関数、非単調関数、対称関数、及び非対称関数について述べる。以下、 $\Omega$ を劣モジュラ関数の台集合とする。

単調関数

劣モジュラ関数　 $f$ が全ての $S\subseteq T$ に対して $f(S)\leq f(T)$ を満たすとき単調と呼ぶ。以下、単調関数の例である。

線形関数: $f(S)=\sum _{i\in S}w_{i}$ という形で表せる全ての集合関数。

この場合、 $\forall i,w_{i}\geq 0$ なら単調。

バジェット加法型関数: $f(S)=\min \left(B,\sum _{i\in S}w_{i}\right)$ という形で表せる関数のうち、 $w_{i}\geq 0,B\geq 0$ を満たす関数。

被覆関数: 集合 $\Omega =\{E_{1},E_{2},\ldots ,E_{n}\}$ が何らかの元集合 $\Omega '$ の部分集合族であるとする。これに対して、 $f(S)=|\bigcup _{E_{i}\in S}E_{i}|$ for $S\subseteq \Omega$ という形で表せる関数。

エントロピー関数 ( $\Omega$ は確率変数の集合)

任意の $S\subseteq \Omega$ に対して、 $S$ のエントロピーを返すような関数 $H(S)$ 。

マトロイド階数関数 ( $\Omega$ はマトロイドの台集合)

マトロイドの階数関数は劣モジュラ関数。

非単調関数

単調関数でない劣モジュラ関数。

対称な劣モジュラ関数

任意の $S\subseteq \Omega$ に対して $f(S)=f(\Omega -S)$ を満たす劣モジュラ関数を対称であるという。以下、対称な劣モジュラ関数の例である。

カット関数 ( $\Omega$ はグラフの頂点集合): 任意の $S\subseteq \Omega$ に対して、 $f(S)$ が、 $e=(u,v),u\in S,v\in \Omega -S$ を満たす辺 $e$ の数を返す関数となるとき $f$ をカット関数と呼ぶ。

上記の条件を満たす辺重みの合計を返すような関数として定義する場合がある。辺重み無しの場合を上記で考える場合、重み 1: 辺が存在する、重み 0: 辺が存在することを表す。

相互情報量 ( $\Omega$ は確率変数の集合): 任意の $S\subseteq \Omega$ に対して、 $f(S)=I(S;\Omega -S)$ ( $I(S;\Omega )$ は相互情報量) となる関数。

非対称な劣モジュラ関数

単調でも対称でもない劣モジュラ関数。以下、非対称な劣モジュラ関数の例である。

有向グラフのカット関数 ( $\Omega$ は有向グラフの頂点集合): この集合 $\Omega$ に対して定義されたカット関数は非対称な劣モジュラ関数である。

出る辺に関するカット関数と、入る辺に関するカット関数は対称でないことからこのことが分かる。

連続関数への拡張

劣モジュラ関数の連続化として、ロバース拡張や多重線形拡張がある。

ロバース拡張

ベクトル $\mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}$ であって、各要素が $0\leq x_{i}\leq 1$ となるものに対し、 $f^{L}(\mathbf {x} )=\mathbb {E} (f(\{i:x_{i}\geq \lambda \}))$ で定義される関数を集合関数 $f$ のロバース拡張 (Lovász extension) という。この関数は閉区間 $[0,1]$ 上の一様分布から $\lambda$ 以上のものを選んだ時の期待値を返すような関数になっており、この関数は凸関数になる。

多重線形拡張

一般化

参考文献

Satoru Fujishige (2005), Submodular Functions and Optimization, Elsevier, ISBN 9780444520869
室田一雄 (2001), 離散凸解析, 共立出版, ISBN 4-320-01690-4
H.Nagamochi and T.Ibaraki (2008), Algorithmic Aspects of Graph Connectivity, Cambridge University Press, ISBN 0-52187864-0
河原吉伸 and 永野清仁 (2015), 劣モジュラ最適化と機械学習, 講談社, ISBN 9784061529090

定義