劣モジュラー集合関数

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

が有限集合である場合、サブモジュラ関数は集合関数であり、 はの冪集合を表し、次の同値条件のいずれかを満たす。^[5]${\displaystyle \オメガ}$${\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }$${\displaystyle 2^{\Omega}}$${\displaystyle \オメガ}$

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)}$

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

集合関数が単調であるとは、任意のに対して が成り立つ場合です。単調なサブモジュラ関数の例には次のものがあります。 ${\displaystyle f}$${\displaystyle T\subseteq S}$${\displaystyle f(T)\leq f(S)}$

線形（モジュラー）関数

形式の関数はすべて線形関数と呼ばれます。さらに、の場合、f は単調です。${\displaystyle f(S)=\sum _{i\in S}w_{i}}$${\displaystyle \forall i,w_{i}\geq 0}$

予算加算関数

それぞれに対しての形の関数は加法予算関数と呼ばれる。^[6]${\displaystyle f(S)=\min \left\{B,~\sum _{i\in S}w_{i}\right\}}$${\displaystyle w_{i}\geq 0}$${\displaystyle B\geq 0}$

カバレッジ機能

を何らかの基底集合の部分集合の集合とします。に対する関数はカバレッジ関数と呼ばれます。 これは、要素に非負の重みを追加することで一般化できます。${\displaystyle \Omega =\{E_{1},E_{2},\ldots ,E_{n}\}}$ ${\displaystyle \Omega '}$${\displaystyle f(S)=\left|\bigcup _{E_{i}\in S}E_{i}\right|}$${\displaystyle S\subseteq \Omega }$

エントロピ

をランダム変数の集合とします。すると、任意の に対して はサブモジュラ関数が成り立ちます。ここで はランダム変数の集合のエントロピーであり、これはシャノンの不等式として知られています。^[7]エントロピー関数のその他の不等式は成り立つことが知られています。エントロピーベクトルを参照してください。${\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle H(S)}$${\displaystyle H(S)}$${\displaystyle S}$

マトロイド ランク関数

をマトロイドが定義される基底集合とする。このときマトロイドのランク関数はサブモジュラ関数である。 ^[8]${\displaystyle \Omega =\{e_{1},e_{2},\dots ,e_{n}\}}$

単調ではないサブモジュラ関数は非単調関数と呼ばれます。

非単調サブモジュラ関数は、任意の に対して が成り立つとき、対称関数と呼ばれます。対称非単調サブモジュラ関数の例には、次のものがあります。 ${\displaystyle f}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)=f(\Omega -S)}$

グラフカット

をグラフの頂点とします。任意の頂点の集合について、およびとなる辺の数を で表します。これは、辺に非負の重みを追加することで一般化できます。${\displaystyle \Omega =\{v_{1},v_{2},\dots ,v_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)}$${\displaystyle e=(u,v)}$${\displaystyle u\in S}$${\displaystyle v\in \Omega -S}$

相互情報

をランダム変数の集合とします。すると、任意の に対して、はサブモジュラ関数であり、 は相互情報量です。${\displaystyle \Omega =\{X_{1},X_{2},\ldots ,X_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)=I(S;\Omega -S)}$${\displaystyle I(S;\Omega -S)}$

対称でない非単調サブモジュラ関数は非対称と呼ばれます。

指示カット

を有向グラフの頂点とします。任意の頂点集合に対して、およびとなる辺の数を で表します。これは、有向辺に非負の重みを追加することで一般化できます。${\displaystyle \Omega =\{v_{1},v_{2},\dots ,v_{n}\}}$${\displaystyle S\subseteq \Omega }$${\displaystyle f(S)}$${\displaystyle e=(u,v)}$${\displaystyle u\in S}$${\displaystyle v\in \Omega -S}$

多くの場合、さまざまなセットの値を表すサブモジュラー セット関数が与えられた場合、分数セットの値を計算する必要があります。たとえば、家 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)}$

サブモジュラ関数の連続拡張には一般的にいくつかの種類があり、以下で説明します。

この拡張は数学者ラスロー・ロヴァースにちなんで名付けられました。^[9]任意のベクトルを考え、各ベクトルが となると、ロヴァース拡張は次のように定義されます。 ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$

${\displaystyle f^{L}(\mathbf {x} )=\mathbb {E} (f(\{i|x_{i}\geq \lambda \}))}$

ここで、期待値は区間 上の一様分布から選択されたものです。ロヴァース拡大は、 がサブモジュラ関数である 場合に限り、凸関数となります。${\displaystyle \lambda }$${\displaystyle [0,1]}$${\displaystyle f}$

各 となる任意のベクトルを考える。このとき多重線型拡張は^{[10] [11]}のように定義される。 ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$${\displaystyle F(\mathbf {x} )=\sum _{S\subseteq \Omega }f(S)\prod _{i\in S}x_{i}\prod _{i\notin S}(1-x_{i})}$

直感的には、x _{i は}アイテムiがセットに選択される確率を表します。すべてのセットSについて、2 つの内積は選択されたセットがまさにS である確率を表します。したがって、合計は、他のアイテムとは無関係に、各アイテムi を確率 xi でランダムに選択することによって形成されるセットのfの期待値を表します。

各 となる任意のベクトルを考えます。凸閉包は として定義されます。 ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$${\displaystyle f^{-}(\mathbf {x} )=\min \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)}$

任意の集合関数の凸閉包は に対して凸である。 ${\displaystyle [0,1]^{n}}$

各 となる任意のベクトルを考えます。このとき、凹閉包は として定義されます。 ${\displaystyle \mathbf {x} =\{x_{1},x_{2},\dots ,x_{n}\}}$${\displaystyle 0\leq x_{i}\leq 1}$${\displaystyle f^{+}(\mathbf {x} )=\max \left(\sum _{S}\alpha _{S}f(S):\sum _{S}\alpha _{S}1_{S}=\mathbf {x} ,\sum _{S}\alpha _{S}=1,\alpha _{S}\geq 0\right)}$

上で議論した拡張に対して、がサブモジュラであることを示すことができる。^[12]${\displaystyle f^{+}(\mathbf {x} )\geq F(\mathbf {x} )\geq f^{-}(\mathbf {x} )=f^{L}(\mathbf {x} )}$${\displaystyle f}$

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})}$

サブモジュラ関数は、凸関数や凹関数と非常によく似た特性を持っています。このため、凸関数や凹関数の最適化に関する最適化問題は、いくつかの制約の下でサブモジュラ関数を最大化または最小化する問題としても説明できます。

サブモジュラ集合関数を最小化する難しさは、問題に課せられる制約によって異なります。

1. 制約のないサブモジュラ関数の最小化問題は、多項式時間で計算可能であり、^{[13] [14]}、さらには強多項式時間で計算可能である。^{[15] [16]グラフの}最小カットを計算することは、この最小化問題の特殊なケースである。
2. 基数下限を持つサブモジュラ関数を最小化する問題はNP困難であり、近似係数には多項式係数の下限がある。^{[17] [18]}

最小化の場合とは異なり、一般的なサブモジュラ関数の最大化は、制約のない設定でもNP 困難です。そのため、この分野の研究のほとんどは、貪欲アルゴリズムや局所探索アルゴリズムなどの多項式時間近似アルゴリズムに関するものです。

1. 非負サブモジュラ関数を最大化する問題は、1/2近似アルゴリズムを許容する。^{[19] [20]}グラフの最大カットを計算することは、この問題の特殊なケースである。
2. 基数制約の下で単調なサブモジュラ関数を最大化する問題は近似アルゴリズムを許容する。^{[21] [22]}最大被覆問題はこの問題の特殊なケースである。${\displaystyle 1-1/e}$
3. マトロイド制約（上記の場合を含む）に従う単調サブモジュラ関数を最大化する問題も近似アルゴリズムが可能である。^{[23] [24] [25]}${\displaystyle 1-1/e}$

これらのアルゴリズムの多くは、半微分ベースのアルゴリズムフレームワーク内で統合することができます。^[18]

サブモジュラ最小化と最大化以外にも、サブモジュラ関数に関連する自然な最適化問題がいくつかあります。

1. ^{2つのサブモジュラ関数[26]}の差を最小化することはNP困難であるだけでなく、近似不可能でもある。^[27]
2. サブモジュラレベルセット制約（サブモジュラ被覆制約またはサブモジュラナップサック制約に従うサブモジュラ最適化とも呼ばれる）に従うサブモジュラ関数の最小化/最大化は、有界近似保証を認める。^[28]
3. 平均福祉を最大化するためにサブモジュラ関数に基づいてデータを分割することは、サブモジュラ福祉問題として知られており、これは有界近似保証も認めます (福祉最大化を参照)。

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

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

• Schrijver、Alexander (2003)、組み合わせ最適化、Springer、ISBN 3-540-44389-4
• リー、ジョン（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/ にはこのテーマに関するさらなる資料が含まれています。