劣モジュラー函数

ウィキペディア

劣モジュラ関数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/14 06:33 UTC 版)

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

定義

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

劣モジュラ性

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

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

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

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

   ロバース拡張

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