最新要闻

广告

手机

英国房地产因利率上升陷入困境 房价正以2011年来最快速度下跌

英国房地产因利率上升陷入困境 房价正以2011年来最快速度下跌

宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

家电

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

来源:博客园

定义

子模 (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$中原有的规则无关。

关键词: