对子模函数(submodular function)的一些理解

大家好，欢迎来到IT知识分享网。

1、子模函数是一个集合函数，又减小回转属性（diminishing returns)。子模函数适用于多种应用，包括近似算法，博弈理论，和电网络。

2、标准定义：

如果 $\Omega$ 是一个集合，一个子模函数是一个集合函数， $f : 2^{\Omega }\rightarrow R$ ,（就是 $\Omega$ 的幂集到实数集R的映射），满足下列等式：

（1）对所有 $X,Y\subseteq \Omega$ ,其中 $X\subseteq Y$ ,则对所有 $x\in \Omega \setminus Y$ ,有

$f (X\cup \left \{ x \right \})-f\left ( X \right )\geqslant f(Y\cup \left \{ x \right \})-f\left ( Y \right )$

（2）对所有 $S,T\subseteq \Omega$ 有 $f\left ( S \right )+f\left ( T \right )\geqslant f\left ( S\cup T \right )+f\left ( S\cap T \right )$

（3）对所有 $X\subseteq \Omega ,x_{1},x_{2}\in \Omega$ ，我们有

$f\left ( X\cup \left \{ x_{1} \right \} \right )+f\left ( X\cup \left \{ x_{2} \right \} \right )\geqslant f\left ( X\cup \left \{ x_{1} ,x_{2}\right \} \right )+f\left ( X \right )$

3、边际效用递减定律

（1）对于一个集合函数 $f : 2^{\Omega }\rightarrow R$ ，若 $S\subseteq \Omega$ 。对于定义（1）的理解就是：在S中增加一个元素所增加的收益要小于等于在S的子集中增加一个元素所增加的收益。

（2）submodular functions 也是一类满足边际效益递减的集合函数。边际效应是指在一般情况下在其他投入固定不变时，连续地增加某一投入，所新增的产出或收益反而会逐渐减少。比如吃馒头的满足程度，谈对象的感情程度等等。

（3）经济学角度：把所有商品看成一个集合，随着你所拥有的物品数量的增加，那么你获得剩下物品所得到的满足程度越来越小。

（4）NP-hard：对于子模函数f，如果给定一个限制条件C,找出一个满足条件C的集合S,使得f（S）的值最大。最基本的贪心算法，是每次迭代地在解中加入增加效益最大且满足条件C的元素，在第i次迭代时的解

$S_{i}=S_{i-1}\cup \left \{ argmax_{e} \Delta \left ( e| S_{i-1}\right )\right \}$ ,其中 $\Delta \left ( e|S_{i-1} \right )=f\left (S_{i-1}\cup \left \{ e \right \} \right )-f\left ( S_{i-1} \right )$

4、所谓的集合函数就是定义在一个有限集的幂集（power set），（即它的所有子集的集合）上的函数，每给定一个子集，它返回一个数。

5、如果它还满足若A是B的子集，则有 $f\left ( A \right )\leqslant f(B)$ ,我们则称它是单调的。

6、对于如果一个子模函数f是单调且非负的。即对于任意 $e\notin S,f\left ( S\cup \left \{ e \right \} \right )\geqslant f\left ( S \right )$ 且对于任意

$S\subseteq \Omega$ , $f\left ( S \right )\geqslant 0$ ,那么对于贪心算法找出近似解 $S_{app}$ 相对于最优解 $S_{opt}$ 满足

$f(S_{app})\geqslant \left ( 1-\frac{1}{e} \right )f\left ( S_{opt} \right )$

即从空集开始，每次都选择使得边际收益最大的元素加入集合S，能够达到 $\left ( 1-\frac{1}{e} \right )f\left ( S_{opt} \right )$

7、效用：自动摘要，多文档摘要，特征选择，主动学习，传感器放置，图像收集摘要等等。

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/146265.html

对子模函数(submodular function)的一些理解

相关推荐

发表回复