劣モジュラ関数(submodular function)とは、有限集合 $E$ の部分集合全体の上の実数値関数 $f$ で、すべての $S,T\subset E$ について $f(S)+f(T)\ge f(S\cup T)+f(S\cap T)$ をみたすもの、言い換えると要素を 1 つ加えたときの増分が集合が大きいほど小さくなるもののことである。マトロイドの階数関数、グラフのカットの容量、被覆の大きさ、エントロピーが例である。$f(\emptyset)=0$ のとき、要素を並べた順に増分を割り当てた貪欲ベクトルが基多面体の頂点のすべてで、係数の降順に並べた貪欲ベクトルが一次関数を最大にする(Edmonds)。最小値は多項式時間で求まるが、最大値を求める問題は一般に NP 困難である。
劣モジュラ関数(submodular function)とは、有限集合 $E$ の部分集合全体の上で定義された実数値関数 $f$ で、すべての $S,T\subset E$ について
$$
f(S)+f(T)\ge f(S\cup T)+f(S\cap T)
$$
をみたすもののことである。言い換えると、要素を 1 つ加えたときの増え方が、すでに持っている集合が大きいほど小さくなる関数である(prop-sm-equiv)。マトロイドの階数関数、グラフのカットの容量、集合の族の被覆の大きさ、確率変数の組のエントロピーなど、組合せ論と最適化の多くの量がこの性質をもつ。
劣モジュラ関数は、連続の最適化での凸関数に似た役割を果たす(GLS88 第 10 章の序、p. 304)。その代表が Edmonds の貪欲法の定理(thm-sm-greedy)である。$f$ から定まる多面体の上で一次関数を最大化する問題は、$E$ の要素を目的関数の係数の大きい順に並べ、順に $f$ の増分を割り当てるだけで解ける。この定理は Lovász拡張 が凸関数になることの基礎であり、劣モジュラ関数の最小値が多項式時間で求まることにつながる。一方、最大値を求める問題は、最大カット問題 を含むので一般には NP 困難である。
この記事では、定義の言い換え、例と構成法、多面体と貪欲法の定理とその完全な証明、最小化と最大化についての既知の結果をまとめ、仮定を外したときの反例を挙げる。
$E$ を有限集合とし、$n:=\lvert E\rvert$ とする。$E$ の部分集合全体を $2^E$ と書く。$f\colon2^E\to\mathbb R$ と $S\subset E$、$e\in E\setminus S$ について、増分 を $\Delta_f(e\mid S):=f(S\cup\{e\})-f(S)$ とおく。$S\cup\{e\}$ を $S+e$ と略す。
$f\colon2^E\to\mathbb R$ が 劣モジュラ であるとは、すべての $S,T\subset E$ について
$$
f(S)+f(T)\ge f(S\cup T)+f(S\cap T)
$$
が成り立つことをいう。不等号が逆向きのとき 優モジュラ、等号のとき モジュラ であるという。$S\subset T$ なら $f(S)\le f(T)$ のとき、$f$ は 単調 であるという。
$f$ が優モジュラであることは $-f$ が劣モジュラであることと同じなので、以下では劣モジュラ関数だけを扱う。
$f\colon2^E\to\mathbb R$ について、次の 3 条件は同値である。
(a) $f$ は劣モジュラである。
(b)(収穫逓減)$S\subset T\subset E$、$e\in E\setminus T$ なら $\Delta_f(e\mid S)\ge\Delta_f(e\mid T)$。
(c)(局所形)$S\subset E$ と相異なる $a,b\in E\setminus S$ について $f(S+a)+f(S+b)\ge f(S+a+b)+f(S)$。
(a) ⇒ (c):(a) を $S+a$ と $S+b$ に当てる。和集合は $S+a+b$、共通部分は $S$ である。
(c) ⇒ (b):$T\setminus S=\{t_1,\dots,t_k\}$ とし、$S_j:=S\cup\{t_1,\dots,t_j\}$ とおく。(c) を $S_{j-1}$ と $a=e$、$b=t_j$ に当てると $\Delta_f(e\mid S_{j-1})\ge\Delta_f(e\mid S_j)$ である。$j=1,\dots,k$ についてつなげると $\Delta_f(e\mid S)\ge\Delta_f(e\mid T)$ を得る($k=0$ なら等号)。
(b) ⇒ (a):$T\setminus S=\{t_1,\dots,t_k\}$ とし、$U_j:=\{t_1,\dots,t_{j-1}\}$ とおく。$(S\cap T)\cup U_j\subset S\cup U_j$ で、$t_j$ はどちらにも属さないので、(b) から $\Delta_f(t_j\mid S\cup U_j)\le\Delta_f(t_j\mid(S\cap T)\cup U_j)$ である。$j$ について足すと、両辺が差の和になって
$$
f(S\cup T)-f(S)\le f\bigl((S\cap T)\cup(T\setminus S)\bigr)-f(S\cap T)=f(T)-f(S\cap T)
$$
となり、これは (a) である。$\square$
(b) は「すでに多く持っているほど、1 つ足したときの増え方は小さい」と読める。この形は 貪欲法 の定義「単調性と劣モジュラ性」で使われている。(c) は、$f$ が劣モジュラかどうかを、$n$ 個の要素の組と集合 $S$ についての有限個の不等式で確かめられることを示す。
モジュラ関数は次の形のものに限る。$f$ がモジュラなら、$e\notin S$ について $S$ と $\{e\}$ に等式を当てて $f(S+e)=f(S)+f(\{e\})-f(\emptyset)$ となり、帰納法で
$$
f(S)=f(\emptyset)+\sum_{e\in S}\bigl(f(\{e\})-f(\emptyset)\bigr)
$$
を得る。逆にこの形の関数はモジュラである。ベクトル $x\in\mathbb R^E$ と $A\subset E$ について $x(A):=\sum_{e\in A}x(e)$ と書くと、$f(\emptyset)=0$ のモジュラ関数は $A\mapsto x(A)$ の形の関数のことである。
5 を確かめる。$S,T\subset\{1,\dots,n\}$ について $A:=X_{S\setminus T}$、$B:=X_{S\cap T}$、$C:=X_{T\setminus S}$ とおくと、示すべき不等式は $H(A,B,C)+H(B)\le H(A,B)+H(B,C)$ である。エントロピー の定理「連鎖律と劣加法性」の連鎖律により、これは $H(C\mid A,B)\le H(C\mid B)$ と同値である。$B$ の各値 $b$ で条件をつけた分布に同じ定理の 3(条件をつけるとエントロピーは増えない)を当てて $b$ の確率で平均すれば、この不等式を得る。単調性は、$S\subset T$ について連鎖律から $H(X_T)=H(X_S)+H(X_{T\setminus S}\mid X_S)$ で、条件付きエントロピーが $0$ 以上であることから従う。
劣モジュラ関数から新しい劣モジュラ関数を作る操作をまとめる。
$f,g\colon2^E\to\mathbb R$ を劣モジュラとする。
(1) $\alpha,\beta\ge0$ と $x\in\mathbb R^E$、$a\in\mathbb R$ について、$\alpha f+\beta g$ と $S\mapsto f(S)-x(S)+a$ は劣モジュラである。
(2) $A\subset E$ について、$2^A$ への制限 $f|_{2^A}$ と、$E\setminus A$ の上の関数 $f_A(S):=f(S\cup A)-f(A)$ は劣モジュラである。
(3) $\bar f(S):=f(E\setminus S)$ は劣モジュラである。
$f\colon2^E\to\mathbb R$ を $f(\emptyset)=0$ をみたす関数とする(主に $f$ が劣モジュラのときに使う)。
$$
EP_f:=\{x\in\mathbb R^E\mid\text{すべての }A\subset E\text{ で }x(A)\le f(A)\},\qquad P_f:=EP_f\cap\mathbb R^E_{\ge0}
$$
をそれぞれ $f$ の 拡張ポリマトロイド、ポリマトロイド といい(GLS88 (10.1.3)・(10.1.4)、p. 306)、
$$
B(f):=\{x\in EP_f\mid x(E)=f(E)\}
$$
を 基多面体 という。
呼び名は文献によって揃っていない(GLS88 p. 304)。$f$ がマトロイドの階数関数なら、$P_f$ は独立集合の指示ベクトルの凸包である(Rado–Edmondsの定理 の定理「マトロイド多面体の頂点」)。
$E$ の要素の並べ方 $\sigma=(e_1,\dots,e_n)$ ごとに、$S_i:=\{e_1,\dots,e_i\}$($S_0:=\emptyset$)とおき、ベクトル $x^\sigma\in\mathbb R^E$ を
$$
x^\sigma(e_i):=f(S_i)-f(S_{i-1})\qquad(i=1,\dots,n)
$$
で定める。これを $\sigma$ についての 貪欲ベクトル と呼ぶ。定義から $x^\sigma(S_i)=f(S_i)$($i=0,\dots,n$)である。
$f\colon2^E\to\mathbb R$ を $f(\emptyset)=0$ をみたす関数とする。
(1) $f$ が劣モジュラであることと、すべての並べ方 $\sigma$ で $x^\sigma\in EP_f$ であることは同値である。このとき $x^\sigma\in B(f)$ である。
以下 $f$ を劣モジュラとする。$c\in\mathbb R^E$ と、$c(e_1)\ge c(e_2)\ge\cdots\ge c(e_n)$ となる並べ方 $\sigma=(e_1,\dots,e_n)$ をとる。
(2) $x^\sigma$ は $B(f)$ の上で $x\mapsto c\cdot x$ の最大値をとり、最大値は
$$
c\cdot x^\sigma=\sum_{i=1}^{n-1}\bigl(c(e_i)-c(e_{i+1})\bigr)f(S_i)+c(e_n)f(E)
$$
である。さらに $c\ge0$ なら、$x^\sigma$ は $EP_f$ の上でも $c\cdot x$ の最大値をとる。
(3) $B(f)$ は貪欲ベクトル全体の凸包であり、$B(f)$ の頂点は貪欲ベクトルとちょうど一致する。とくに $f$ が整数値なら、$B(f)$ の頂点はすべて整数ベクトルである。
$c\ge0$ のとき貪欲ベクトルが $EP_f$ の上で $c\cdot x$ を最大にする頂点であることは Edmonds による(Edm70。GLS88 Theorem (10.1.6) と (10.1.7)・(10.1.8)、pp. 306–307)。GLS88 Theorem (10.1.6) はさらに強く、空でない下に閉じた多面体の上で、$0$ 以上のどの $c$ についても貪欲法が最適解を出すのは拡張ポリマトロイドのときに限ることを述べている。
(1) 劣モジュラなら $x^\sigma\in EP_f$。 $A\subset E$ を任意にとる。$e_i\in A$ なら $(A\cap S_{i-1})+e_i=A\cap S_i$ であり、$A\cap S_{i-1}\subset S_{i-1}$、$e_i\notin S_{i-1}$ なので、prop-sm-equiv (b) から
$$
x^\sigma(e_i)=\Delta_f(e_i\mid S_{i-1})\le\Delta_f(e_i\mid A\cap S_{i-1})=f(A\cap S_i)-f(A\cap S_{i-1})
$$
である。$e_i\notin A$ なら $A\cap S_i=A\cap S_{i-1}$ で右辺の差は $0$ である。よって
$$
x^\sigma(A)=\sum_{e_i\in A}x^\sigma(e_i)\le\sum_{i=1}^n\bigl(f(A\cap S_i)-f(A\cap S_{i-1})\bigr)=f(A)-f(\emptyset)=f(A)
$$
である。$x^\sigma(E)=f(E)$ なので $x^\sigma\in B(f)$ でもある。
(1) $x^\sigma\in EP_f$ なら劣モジュラ。 $S,T\subset E$ をとり、$S\cap T$ の要素、$S\setminus T$ の要素、$T\setminus S$ の要素、残りの要素の順に並べた $\sigma$ を考える。$S\cap T$、$S$、$S\cup T$ はどれも $\sigma$ の始めの部分なので、$x^\sigma$ のそれらの上の和は $f$ の値に等しい。よって
$$
x^\sigma(T)=x^\sigma(S\cap T)+x^\sigma(T\setminus S)=f(S\cap T)+\bigl(f(S\cup T)-f(S)\bigr)
$$
であり、$x^\sigma\in EP_f$ から $x^\sigma(T)\le f(T)$ なので、移項すれば劣モジュラ性の不等式を得る。
(2)。 $c_i:=c(e_i)$ と書く。任意の $x\in\mathbb R^E$ について、和の順序を入れ替えると
$$
c\cdot x=\sum_{i=1}^nc_i\bigl(x(S_i)-x(S_{i-1})\bigr)=\sum_{i=1}^{n-1}(c_i-c_{i+1})\,x(S_i)+c_n\,x(E)
$$
である。$x\in B(f)$ なら $x(S_i)\le f(S_i)$、$x(E)=f(E)$ で、$c_i-c_{i+1}\ge0$ なので、$c\cdot x\le\sum_{i=1}^{n-1}(c_i-c_{i+1})f(S_i)+c_nf(E)$ である。右辺は $x^\sigma$ での値に等しく($x^\sigma(S_i)=f(S_i)$)、(1) により $x^\sigma\in B(f)$ なので、これが最大値である。$c\ge0$ なら $c_n\ge0$ なので、$x\in EP_f$ について $c_nx(E)\le c_nf(E)$ となり、同じ議論が $EP_f$ の上で成り立つ。
(3)。 貪欲ベクトルは有限個なので、その凸包 $Q$ はコンパクトな凸集合で、$B(f)$ は凸なので (1) から $Q\subset B(f)$ である。$y\in B(f)\setminus Q$ があったとすると、凸集合の分離により $c\cdot y>\max_{q\in Q}c\cdot q$ となる $c\in\mathbb R^E$ がある。$c$ に合わせて並べた $\sigma$ について、(2) から $c\cdot y\le c\cdot x^\sigma\le\max_Qc\cdot q$ となり、矛盾する。よって $B(f)=Q$ である。有限個の点の凸包の頂点はそれらの点のどれかなので、$B(f)$ の頂点は貪欲ベクトルである。逆に、$c_1>c_2>\cdots>c_n$ と狭義に減少する $c$ をとると、$x\in B(f)$ が最大値をとるのは (2) の不等式がすべて等号のとき、すなわち $x(S_i)=f(S_i)$($i=1,\dots,n$)のときで、これは $x=x^\sigma$ を意味する。よって $x^\sigma$ は $B(f)$ 上で $c\cdot x$ の最大値をただ 1 点でとり、頂点である。整数値の $f$ では $x^\sigma$ は整数ベクトルである。$\square$
最小値をとる集合の全体は、和と共通部分で閉じている。
$f$ を劣モジュラとし、$\mu:=\min_{S\subset E}f(S)$ とする。$f(S)=f(T)=\mu$ なら $f(S\cup T)=f(S\cap T)=\mu$ である。とくに、最小値をとる集合のうち包含について最小のものと最大のものがただ 1 つずつある。
$2\mu=f(S)+f(T)\ge f(S\cup T)+f(S\cap T)\ge2\mu$ なので、すべて等号である。最小値をとる集合全体の共通部分と和集合は、この性質を有限回使えば最小値をとる。$\square$
$f$ の値を返す手続き(オラクル)だけが与えられたとき、$2^n$ 個の集合をすべて調べずに最小値を求められるかが問題になる。
有理数値の劣モジュラ関数 $f$ がオラクルで与えられるとき、$f$ を最小にする集合は、$n$ と値の符号化の長さについての多項式時間で求まる。
これは Grötschel・Lovász・Schrijver が楕円体法を使って示した(GLS88 (10.2.7)・(10.2.8)、pp. 310–311。GN23 pp. 42–43)。方針は、Lovász拡張 が劣モジュラ関数について凸関数になり、$f$ の最小値が Lovász拡張の単位立方体の上の最小値に等しいことを使って、凸関数の最小化に帰着することである(楕円体法)。楕円体法を使わない強多項式時間の組合せ的な算法は、Schrijver(Sch00)と、岩田覚(Satoru Iwata)・Fleischer・藤重悟(Satoru Fujishige)(IFF01)が与えた(GN23 p. 43)。この記事では算法の詳細には立ち入らない。最小値の公式と最小化への帰着の証明は Lovász拡張 にある。
最大値を求める問題は難しい。無向グラフのカットの容量(ex-sm-examples の 4)は劣モジュラで、その最大値を求める問題は 最大カット問題 であり、その定理「重みつき最大カット問題の NP 完全性」により NP 困難である(GLS88 p. 311)。一方、単調な劣モジュラ関数を $k$ 個以下の集合の上で最大化する問題では、増分が最大の要素を順に選ぶ貪欲法が最適値の $1-(1-1/k)^k$ 倍以上を保証する(貪欲法 の定理「増分最大の貪欲法の保証」)。
Edmonds は、$f,g$ が同じ $E$ の上の整数値の劣モジュラ関数なら、$P_f\cap P_g$ と $EP_f\cap EP_g$ の頂点はすべて整数ベクトルであることを示した(Edm70。GLS88 Theorem (10.1.13)、p. 308)。この定理は マトロイド交差定理 を含む。thm-sm-greedy (3) は $f$ が 1 つの場合の整数性で、2 つの共通部分の整数性はより深い結果である。3 つの多面体の共通部分では、関数が整数値でも整数でない頂点が現れうる(GLS88 p. 310)。
$E=\{a,b\}$ の上の関数を、値の組 $\bigl(f(\emptyset),f(\{a\}),f(\{b\}),f(E)\bigr)$ で書く。
| 外した仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 劣モジュラ(thm-sm-greedy (2)) | $(0,0,0,1)$ | $x^\sigma$ が $B(f)$ 上の最大値をとること($B(f)=\emptyset$) |
| $f(\emptyset)=0$(thm-sm-greedy (1)) | $(-1,0,0,0)$(劣モジュラ) | $x^\sigma\in B(f)$ |
| 並べ方が $c$ の降順(thm-sm-greedy (2)) | $(0,1,1,1)$、$c=(1,0)$、$\sigma=(b,a)$ | $x^\sigma$ が $B(f)$ 上の最大値をとること |
| $c\ge0$(thm-sm-greedy (2) の後半) | $E=\{a\}$、$f\equiv0$、$c=-1$ | $x^\sigma$ が $EP_f$ 上の最大値をとること |
| 劣モジュラ(prop-sm-minimizers) | $(1,0,0,1)$ | 最小値をとる集合の和と共通部分が最小値をとること |
1 行目:$f(\{a\})+f(\{b\})=0< 1=f(E)+f(\emptyset)$ で劣モジュラでない。$x\in B(f)$ なら $x(a)\le0$、$x(b)\le0$、$x(a)+x(b)=1$ となるが、これは両立しないので $B(f)=\emptyset$ で、最大値をとる点はない。実際 $\sigma=(a,b)$ の $x^\sigma=(0,1)$ は $x^\sigma(b)=1>0=f(\{b\})$ で $EP_f$ に入らない。
2 行目:空でない $S,T$ が交わらないとき $f(S)+f(T)=0\ge-1=f(S\cup T)+f(\emptyset)$、ほかの組では両辺が等しいので劣モジュラである。$EP_f$ の条件で $A=\emptyset$ とすると $0\le-1$ となるので $EP_f=\emptyset$ で、$x^\sigma$ は $B(f)$ に入らない。
3 行目:$f(S)=\min\{\lvert S\rvert,1\}$($\lvert S\rvert\ge1$ で $1$)は劣モジュラである。$\sigma=(b,a)$ では $x^\sigma(b)=1$、$x^\sigma(a)=0$ で $c\cdot x^\sigma=0$ だが、$x=(1,0)$($x(a)=1$)は $B(f)$ に属して $c\cdot x=1$ である。
4 行目:$EP_f=\{x\mid x(a)\le0\}$ で、$c\cdot x=-x(a)$ は $EP_f$ 上でいくらでも大きくなるので最大値がなく、$x^\sigma=0$ は最大値をとらない。$B(f)=\{0\}$ の上では最大値 $0$ をとるので、成り立たないのは $EP_f$ の上の主張だけである。
5 行目:$f(\{a\})+f(\{b\})=0< 2$ で劣モジュラでない。最小値 $0$ は $\{a\}$ と $\{b\}$ でとるが、和 $E$ と共通部分 $\emptyset$ での値は $1$ である。
劣モジュラ関数は、マトロイド(Rado 1942、Ingleton 1959)と束(Dilworth 1944)に関連して最初に調べられ、最適化での重要性は Rado(1957)と Edmonds(1970)によって明らかにされた。Edmonds はポリマトロイドの概念を導入し、基本的な定理を証明した(GLS88 p. 304)。劣モジュラ関数と凸関数を結ぶ Lovász拡張は Lovász による(Lov83。GN23 p. 42)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する