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

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