劣モジュラ関数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

定義[編集]

台集合 \Omega の冪集合2^\Omega上の関数 f:2^\Omega \rightarrow \mathbb{R} で 次を満たす関数を劣モジュラ関数と呼ぶ。

任意の集合対 S, T \subseteq \Omega に対して、 f(S) + f(T) \geq f(S \cup T) + f(S \cap T)

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


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

  1. 任意の集合対 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)
  2. 任意の集合 X \subseteq \Omegax_1, x_2 \in \Omega \backslash X に対して、 f(X \cup \{ x_1 \}) + f(X \cup \{ x_2 \}) \geq f(X \cup \{ x_1, x_2 \}) + f(X)

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

劣モジュラ関数の例[編集]

ここでは劣モジュラ関数の例として、単調関数、非単調関数、対称関数、及び非対称関数について述べる。 以下、\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に対して定義されたカット関数は非対称な劣モジュラ関数である。

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

連続関数への拡張[編集]

ロバシュ拡張[編集]

ベクトル \bold{x} = \{ x_1, x_2, \ldots, x_n \} であって、各要素が0 \leq x_i \leq 1となるものに対し、  f^L(\bold{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