劣モジュラ関数

数学の分野において劣モジュラ関数 () とは集合関数の一種で、簡単にいうと、関数に渡される集合に1つ要素が加わった場合に増える関数の値が、もとの集合が大きくなるにつれ小さくなるような関数を指す。集合関数であることを明示して劣モジュラ集合関数ということもある。劣モジュラ関数の概念は一般のベクトル値関数における凸関数の概念と類似した性質を持つため、近似アルゴリズムやゲーム理論、機械学習などの幅広い応用を持つ。
定義.
台集合 の冪集合 上の関数 で
次を満たす関数を劣モジュラ関数と呼ぶ。 
この不等式を劣モジュラ不等式と呼ぶ。劣モジュラ不等式の不等号を逆にした不等式を優モジュラ不等式と呼び、この不等式を満たす集合関数を優モジュラ関数と呼ぶ。
また、上記の不等式と以下の 2 つの不等式は同値である。
非負の劣モジュラ関数は劣加法的であるが、劣加法的関数が必ずしも劣モジュラとは限らない。
劣モジュラ関数の例.
ここでは劣モジュラ関数の例として、単調関数、非単調関数、対称関数、及び非対称関数について述べる。
以下、formula_7 を劣モジュラ関数の台集合とする。
単調関数.
劣モジュラ関数　formula_8 が全ての formula_9 に対して formula_10を満たすとき単調と呼ぶ。
以下、単調関数の例である。
この場合、formula_12なら単調。
任意の formula_20 に対して、formula_21 のエントロピーを返すような関数 formula_22。
マトロイドの階数関数は劣モジュラ関数。
非単調関数.
単調関数でない劣モジュラ関数。
対称な劣モジュラ関数.
任意の formula_18に対して formula_25 を満たす劣モジュラ関数を対称であるという。
以下、対称な劣モジュラ関数の例である。
上記の条件を満たす辺重みの合計を返すような関数として定義する場合がある。
辺重み無しの場合を上記で考える場合、重み 1: 辺が存在する、重み 0: 辺が存在することを表す。
非対称な劣モジュラ関数.
単調でも対称でもない劣モジュラ関数。
以下、非対称な劣モジュラ関数の例である。
出る辺に関するカット関数と、入る辺に関するカット関数は対称でないことからこのことが分かる。
連続関数への拡張.
劣モジュラ関数の連続化として、ロバース拡張や多重線形拡張がある。
ロバース拡張.
ベクトルformula_38 であって、各要素がformula_39となるものに対し、 formula_40 で定義される関数を集合関数formula_8のロバース拡張 (Lovász extension) という。この関数は閉区間formula_42上の一様分布からformula_43以上のものを選んだ時の期待値を返すような関数になっており、この関数は凸関数になる。