劣モジュラ集合関数

数学において、劣モジュラ集合関数（劣モジュラ関数とも呼ばれる）は、入力の集合と出力の関係を非公式に記述する集合関数であり、ある入力をさらに追加すると、追加される利益が減少する（収穫逓減）という性質を持つ。この自然な収穫逓減の性質により、近似アルゴリズム、ゲーム理論（ユーザーの好みをモデル化する関数として）、電気ネットワークなど、多くのアプリケーションに適している。最近では、劣モジュラ関数は、機械学習や人工知能におけるいくつかの現実世界の問題、例えば自動要約、複数文書要約、特徴選択、アクティブラーニング、センサー配置、画像コレクション要約など、多くの分野で有用であることがわかっている。^{[ 1 ] [ 2 ] [ 3 ] [ 4 ]}

もし${\displaystyle \Omega }$は有限集合であり、劣モジュラ関数は集合関数である。${\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }$、 どこ$2Ω$の冪集合を表す${\displaystyle \Omega }$これは、以下の同等の条件のいずれかを満たす。^{[ 5 ]}

1. すべての${\displaystyle X,Y\subseteq \Omega }$と${\displaystyle X\subseteq Y}$そしてすべての${\displaystyle x\in \Omega \setminus Y}$私たちはそれを持っています${\displaystyle f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)}$。
2. すべての${\displaystyle S,T\subseteq \Omega }$私たちはそれを持っています${\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)}$。
3. すべての${\displaystyle X\subseteq \Omega }$そして${\displaystyle x_{1},x_{2}\in \Omega \backslash X}$そのため${\displaystyle x_{1}\neq x_{2}}$私たちはそれを持っています${\displaystyle f(X\cup \{x_{1}\})+f(X\cup \{x_{2}\})\geq f(X\cup \{x_{1},x_{2}\})+f(X)}$または同等に、$\displaystyle f(X\cup \{x_{1}\})-f(X)\geq f(X\cup \{x_{1},x_{2}\})-f(X\cup \{x_{2}\})}$。

非負劣モジュラ関数は劣加法関数でもあるが、劣加法関数は劣モジュラ関数である必要はない。${\displaystyle \Omega }$が有限であると仮定されない場合、上記の条件は同等ではない。特に、関数 ${\displaystyle f}$定義される${\displaystyle f(S)=1}$もし${\displaystyle S}$有限であり${\displaystyle f(S)=0}$もし${\displaystyle S}$無限大は上記の最初の条件を満たしますが、2番目の条件は、${\displaystyle S}$そして${\displaystyle T}$これらは有限個の共通部分を持つ無限集合である。

多くの場合、さまざまな集合の値を記述する劣モジュラ集合関数が与えられたとき、部分集合の値を計算する必要が生じます。例えば、家Aと家Bを受け取る場合の値がVであることがわかっている場合、家Aの40%と家Bの60%を受け取る場合の値を知りたいとします。この目的のために、劣モジュラ集合関数の連続的な拡張が必要となります。

形式的には、集合関数${\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }$と${\displaystyle |\Omega |=n}$関数として表現できる${\displaystyle \{0,1\}^{n}}$それぞれを関連付けることで${\displaystyle S\subseteq \Omega }$バイナリベクトル付き${\displaystyle x^{S}\in \{0,1\}^{n}}$そのため${\displaystyle x_{i}^{S}=1}$いつ${\displaystyle i\in S}$、 そして${\displaystyle x_{i}^{S}=0}$そうでなければ。${\displaystyle f}$連続関数である${\displaystyle F:[0,1]^{n}\rightarrow \mathbb {R} }$、その値に一致する${\displaystyle f}$の上${\displaystyle x\in \{0,1\}^{n}}$つまり${\displaystyle F(x^{S})=f(S)}$。

劣モジュラ関数の連続拡張にはいくつかの種類があり、一般的に用いられています。それらについては以下に説明します。

1. 劣モジュラ関数のクラスは、非負の線形結合に関して閉じている。任意の劣モジュラ関数を考える。${\displaystyle f_{1},f_{2},\ldots ,f_{k}}$および非負の数${\displaystyle \alpha _{1},\alpha _{2},\ldots ,\alpha _{k}}$すると関数${\displaystyle g}$定義される${\displaystyle g(S)=\sum _{i=1}^{k}\alpha _{i}f_{i}(S)}$劣モジュラである。
2. 任意の劣モジュラ関数に対して${\displaystyle f}$、定義される関数${\displaystyle g(S)=f(\Omega \setminus S)}$劣モジュラである。
3. 機能${\displaystyle g(S)=\min(f(S),c)}$、 どこ${\displaystyle c}$は実数であり、 のとき劣モジュラである。${\displaystyle f}$単調劣モジュラである。より一般的には、${\displaystyle g(S)=h(f(S))}$は、任意の非減少凹関数に対して劣モジュラである。${\displaystyle h}$。
4. 集合がランダムなプロセスであることを考えてみましょう${\displaystyle T}$各要素で選択されます${\displaystyle \Omega }$含まれる${\displaystyle T}$確率で独立に${\displaystyle p}$すると、次の不等式が成り立つ。${\displaystyle \mathbb {E} [f(T)]\geq pf(\Omega )+(1-p)f(\varnothing )}$どこ${\displaystyle \varnothing }$は空集合です。より一般的には、集合が次のランダムプロセスであることを考えます。${\displaystyle S}$は次のように構築されます。${\displaystyle 1\leq i\leq l,A_{i}\subseteq \Omega }$構築する${\displaystyle S_{i}}$各要素を含めることで${\displaystyle A_{i}}$独立して${\displaystyle S_{i}}$確率で${\displaystyle p_{i}}$さらに、${\displaystyle S=\cup _{i=1}^{l}S_{i}}$すると、次の不等式が成り立つ。${\displaystyle \mathbb {E} [f(S)]\geq \sum _{R\subseteq [l]}\Pi _{i\in R}p_{i}\Pi _{i\notin R}(1-p_{i})f(\cup _{i\in R}A_{i})}$。

劣モジュラ関数は、凸関数や凹関数と非常によく似た性質を持っています。そのため、凸関数や凹関数を最適化する問題は、何らかの制約条件の下で劣モジュラ関数を最大化または最小化する問題として記述することもできます。

劣モジュラ関数は、経済学、ゲーム理論、機械学習、コンピュータビジョン^{[ 4 ] [ 29 ]}、および一般的な人工知能^{[ 30 ]}など、現実世界のさまざまなアプリケーションで自然に現れます。収穫逓減の性質により、劣モジュラ関数は、購入するアイテムが増えるにつれて割引が大きくなることが多いため、アイテムのコストを自然にモデル化します。劣モジュラ関数は、最小化問題に現れる場合、複雑性、類似性、協力の概念をモデル化します。一方、最大化問題では、多様性、情報、カバレッジの概念をモデル化します。

• 超モジュロ関数
• マトロイド、ポリマトロイド
• 分割不可能な財に対する効用関数

• Schrijver、Alexander (2003)、組み合わせ最適化、Springer、ISBN 3-540-44389-4
• Lee, Jon (2004), 『組合せ最適化入門』、ケンブリッジ大学出版局、ISBN 0-521-01012-8
• 藤重悟（2005）『劣モジュラ関数と最適化』エルゼビア、ISBN 0-444-52086-4
• ナラヤナン、H. (1997)、劣モジュラ関数と電気回路、エルゼビア、ISBN 0-444-82523-1
• オクスリー、ジェームズ・G. (1992)、マトロイド理論、オックスフォード・サイエンス・パブリケーションズ、オックスフォード：オックスフォード大学出版局、ISBN 0-19-853563-5、Zbl 0784.05002 

• http://www.cs.berkeley.edu/~stefje/references.html にはより詳細な参考文献リストがあります。
• http://submodularity.org/ には、このテーマに関するさらなる資料が掲載されています。