劣モジュラ関数とは？ わかりやすく解説

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

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

劣モジュラ性

任意の集合対 S, T ⊆ Ω に対して、f(S) + f(T) ≥ f(S ∪ T) + f(S ∩ T)

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

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

1. 任意の集合対 ${\displaystyle X,Y\subseteq \Omega ,X\subseteq Y}$
   この節の加筆が望まれています。

   ロバース拡張

   ベクトル${\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}}$

   この節の加筆が望まれています。
   • 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