子/次模 (Submodular)、超模 (Supermodular)和模(Modular)函数

2023-07-08 14:15:17 来源：博客园

定义

子模 (Submodular)、超模 (Supermodular)和模(Modular)函数是组合优化中用到的函数概念。函数定义域为某个有限集$\Omega$的幂集$2^\Omega$，值域通常为$R$，即$f:2^\Omega\to R$。

子模函数：对于集合$A\subseteq B\subset \Omega$，元素$e\in \Omega-B$，子模函数$f(X)$满足

$f(A\cup\{e\})-f(A)\geq f(B\cup\{e\})-f(B)$

(资料图片仅供参考)

直观上看，随着集合$X$元素的增加，$f(X)$值的变化量不变或降低。或者说函数$f(X)$的边际效应逐渐降低。

超模函数：对于集合$A\subseteq B\subset \Omega$，元素$e\in \Omega-B$，超模函数$f(X)$满足

$f(A\cup\{e\})-f(A)\leq f(B\cup\{e\})-f(B)$

直观上看，随着集合$X$元素的增加，$f(X)$值的变化量不变或增加。或者说函数$f(X)$的边际效应逐渐增加。此外，对于超模函数$f(X)$，可以证明$-f(X)$为子模函数。

模函数：对于集合$A\subseteq B\subset \Omega$，元素$e\in \Omega-B$，模函数$f(X)$满足

$f(A\cup\{e\})-f(A)=f(B\cup\{e\})-f(B)$

直观上看，在集合$X$加入元素时，$f(X)$值的变化量与集合中原有的元素无关，而仅与新加入的元素相关，从而有上面的等号。根据定义可以看出，模函数既是超模函数，又是子模函数。

应用

使用规则集举个例子，规则集$S\subseteq \Omega$中包含一系列的规则$R_i$，即$S=\{R_i\}_{i=1}^m, R_i\in \Omega$。每个规则都可以判断样本$x$是否满足该规则，如果规则集中有一个规则满足该样本，则说该规则集满足该样本。对于包含$n$个样本的数据集$X=\{x_i\}_{i=1}^n$，定义$X_{S}$为满足规则集$S$的样本的集合。

则我们可以发现子模函数：

$\displaystyle f(S)=|X_S|$

这是因为，当我们不断向$S$中加入新的规则时，$S$能满足的样本数量逐渐趋向$n$而饱和，函数收益递减。

还可以发现模函数：

$\displaystyle g(S)=\sum\limits_{R_i\in S} |X_{\{R_i\}}|$

这是因为，当我们不断向$S$中加入新的规则时，上式总是把新规则所满足的样本数量增加到函数值中，而与$S$中原有的规则无关。

关键词：