劣モジュラ関数

劣モジュラ関数：定義と性質

数学において、劣モジュラ関数 (submodular function) とは、集合の大きさに応じて関数値の増加量が減少していく特別な集合関数です。より厳密には、台集合Ωの冪集合2Ω上の関数f: 2Ω → Rで、以下の劣モジュラ不等式を満たすものを指します。

劣モジュラ性:
任意の集合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)

2. 任意の集合X ⊆ Ω とx₁, x₂ ∈ Ω \ X, x₁ ≠ x₂ に対して、
f(X ∪ {x₁}) + f(X ∪ {x₂}) ≥ f(X ∪ {x₁, x₂}) + f(X)

非負の劣モジュラ関数は劣加法的ですが、劣加法的関数が必ずしも劣モジュラであるとは限りません。

劣モジュラ関数の例

劣モジュラ関数は様々な場面で現れます。以下では、単調性、対称性といった性質に基づいた分類と、具体的な例を示します。Ωを劣モジュラ関数の台集合とします。

単調関数

全てのS ⊆ Tに対してf(S) ≤ f(T)を満たす劣モジュラ関数を単調関数と呼びます。

線形関数: f(S) = Σᵢ∈ₛ wᵢ (∀i, wᵢ ≥ 0 の場合、単調)
バジェット加法型関数: f(S) = min(B, Σᵢ∈ₛ wᵢ) (wᵢ ≥ 0, B ≥ 0)
被覆関数: f(S) = |⋃ᵢ∈ₛ Eᵢ| (EᵢはΩ'の部分集合)
エントロピー関数: SのエントロピーH(S)
マトロイド階数関数: マトロイドの階数関数

非単調関数

単調性を持たない劣モジュラ関数です。

対称な劣モジュラ関数

任意のS ⊆ Ωに対してf(S) = f(Ω - S)を満たす劣モジュラ関数を対称な劣モジュラ関数と呼びます。

カット関数: グラフの頂点集合Ωに対し、SとΩ-Sの間の辺の数(または重み付き辺の重みの和)
相互情報量: 確率変数の集合Ωに対し、f(S) = I(S; Ω - S)

非対称な劣モジュラ関数

単調性も対称性も持たない劣モジュラ関数です。

有向グラフのカット関数: 有向グラフの頂点集合Ωに対して定義されるカット関数

連続関数への拡張

劣モジュラ関数は、ロバース拡張や多重線形拡張によって連続関数に拡張できます。

ロバース拡張

ベクトル x = {x₁, x₂, …, xₙ} (0 ≤ xᵢ ≤ 1) に対し、
fˡ(x) = E[f({i: xᵢ ≥ λ})] (λは[0, 1]上の一様分布)
で定義される関数をロバース拡張と呼びます。これは凸関数になります。

多重線形拡張

(詳細は割愛)

関連概念

L凸関数
k劣モジュラ関数
マトロイド
ポリマトロイド
凸関数
正モジュラ関数
双劣モジュラ関数

参考文献

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

もう一度検索