Submodual

子模态定义¶

子模态是集合函数的一种性质。一个集合函数 $f(x)$ 的定义要满足下面这个性质

$\begin{equation}f: 2^{\Omega}\rightarrow \mathbb{R}\end{equation}$

即 $f(x)$ 的定义域为集合 $Ω$ 的任何一个子集，值域为实数集。而这个集合函数如果要满足子模态性质的话，还需要满足下面三个等价条件中的任何一个。

对于任何一个 $X,Y\subset Ω$ 且 $X\subset Y$ ，以及对任何一个 $x\in Ω \\ Y$ ，下面的式子一定成立。
$f(X\cup {x})-f(X)\geq f(Y\cup {x})-f(Y)$
对于任何一个 $X,Y\subset Ω$ ，下面的式子一定成立。
$f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y)$
对于任何一个 $X\subset Ω$ 及 $x_1 ,x_2 \in Ω∖X$ ，下面的式子一定成立,
$f(X\cup {x_1})+f(X\cup {x_2})\geq f(X\cup {x_1,x_2})+f(X)$

读者可以很轻松的验证这几个条件是等价的，这里就不去证明了。

根据这些条件，我们可以得出下面这个结论。设 $f_1 (x),f_2 (x),\cdots,f_k (x)$ 都是有子模态性质的函数， $c_1 ,c_2 ,\cdots,c_k$ 是非负实数，则下面这个函数

$\begin{equation}F(x)=\sum_{i=1}^{k}{c_if_i(x)}\end{equation}$

仍然是子模态的。即多个子模态函数的非负线性组合仍然是子模态函数。这个推论可以很简单的验证出来，这里也就懒得做证明的。

子模态与贪心方法¶

接下来的问题就是，子模态这个函数性质有什么用。简单来说子模态这个函数性质在组合优化中很有用。特别是针对保持|x| 的大小固定，然后去求 $f(x)$ 的最大值这种问题。这个子模态性质可以保证我们在贪心求解这个问题得到的解不会差，事实上贪心解 $f(x)$ 的值不会小于 $(1−1/e )*OPT$ ，其中 $OPT$ 为最优解。在该问题的贪心求解过程中，我们是从 $0$ 开始构建目标集合 $x$ 的。每一步我们将一个新的元素加入到 $x$ 中，迭代 $k$ 步。我们以 $X_i$ 来代表迭代 $i$ 次之后的 $x$ 集合，初始 $x_0 =\emptyset$ 。我们对下一个要加入的节点 $u$ 的选取的贪心规则为

$\begin{equation}u=arg max_{u}{f(X_{i-1}\cup { u})}\end{equation}$

现在我们要证明在此贪心规则下

$\begin{equation}f(x)\geq (1-\frac{1}{e})*OPT\end{equation}$

为此，我们先证明一个引理

$\begin{equation} f(A\cup B)-f(A)\leq \sum_{j=1}^{k}{[f(A\cup {b_j})-f(A)]}\end{equation}$

其中 $B={b_1,\cdots,b_k}$ .此时我们定义 $Bi=b_1,\cdots,b_i$ ，则

$\begin{equation}\begin{split}f(A\cup B)-f(A)&=\sum_{i=1}^{k}{[f(A\cup B_i)-f(A\cup B_{i-1})]}\\&=\sum_{i=1}^{k}{[f(A\cup B_{i-1}\cup {b_i})-f(A\cup B_{i-1})]}\\&\leq\sum_{j=1}^{k}{[f(A\cup {b_j})-f(A)]}\end{split}\end{equation}$

设最优解为 $T={t_1,\cdots,t_k}$ , $\delta_i=f(X_i)-f(X_{i-1})$ ,根据上面这个不等式我们可以推出

$\begin{equation}\begin{split}f(T)&\leq f(X_i\cup T)\\&=f(X_i\cup T)-f(X_i)+f(X_i)\\&\leq\sum_{j=1}^{k}{[f(X_i\cup {t_j})-f(X_i)]}+f(X_i)\\&\leq\sum_{j=1}^{k}{[\delta_{i+1}]}+f(X_i)\\&=f(X_i)+k\delta_{i+1}\end{split}\end{equation}$

综上我们可以得出这个结论

$\begin{equation}\delta_{i+1}\geq \frac{1}{k}[f(T)-f(X_i)]\end{equation}$

所以

$\begin{equation}\begin{split}f(X_{i+1})&=f(X_i)+\delta_{i+1}\\&\geq f(X_i)+\frac{1}{k}[f(T)-f(X_i)]\\&=(1-\frac{1}{k})f(X_i)+\frac{1}{k}f(T)\end{split}\end{equation}$

通过上面的递推式，我们可以给出 $f(X_i)$

$\begin{equation}f(X_i)\geq [1-{(1-\frac{1}{k})}^i]f(T)\end{equation}$

这个是简单的递推数列求通项，这里也就懒得证明了。所以

$\begin{equation}f(X_k)\geq [1-{(1-\frac{1}{k})}^k]f(T)\geq [1-\frac{1}{e}]f(T)\end{equation}$

这就是贪心大法好的证明。

子模态的应用¶

下面我就以影响最大化这个例子来说明这个东西还是有点用的。

影响最大化(influence maXimization)这个问题是定义在一个有向无环图 $G=(V,E)$ 上的。对于这个图的任意一条边 $(v,w)$ ，我们都有这条边的权值 $p_{vw}$ 。 $p_{vw}$ 用来代表 $v$ 对 $w$ 的影响能力，这个影响能力是一个概率，因此 $p _{vw} \in [0,1]$ 。对于边 $(v,w)$ 不存在的时候， $p_{vw}$ 定义为0.

发散网络

这个图类似于一个传播网络，或者感染网络。现在我们来定义影响函数 $f(X)$ ，这是一个集合函数。为了表征这个函数，我们需要定义一个随机过程 $S$ 。初始时刻0，我们给定输入 $P=X_0$ ， $P$ 表示活动集合。在时刻 $t$ ，我们对 $\forall v \in X_t$ 做如下操作： $\forall w\in V/P$ ，我们以概率 $p_{vw}$ 将节点 $w$ 加入到 $X_{t+1}$ 中。此操作完成之后，检查 $X_{t+1}$ 是否为空。如果为空，则返回 $P$ ；否则 $P=P \cup X_{t+1}$ ，然后重复上面的操作。这个模型叫做independent Cascade Model，由Goldenberg, Libai,and Muller提出来的（这个模型是不是跟微博上的转发非常像）。

发散过程

最后我们来表征 $f(X)$ ，就是初始集合 $X$ 该过程 $S$ 下所返回的集合 $P$ 的大小的平均值。

影响最大化问题就是在固定集合 $X$ 大小 $k$ 的情况下，最大化 $f(X)$ 。我们可以证明这个优化问题是NPHard 的。该问题的简化形式为 $p_{vw}$ 都是1，此时该问题不再是一个随机过程。每个初始点 $v$ 的可达集是固定的，我们可以表示为 $R_v$ 。因此，原问题等价于在集合 $R_1 ,\cdots,R_{|v|}$ 中找到 $k$ 个集合，使得

$\begin{equation} arg\max_u{f(S_{i-1}\cup{u})}\end{equation}$

但是，如何证明这个贪心是有效的一个难题，因为这是一个随机过程，每个点的增益在每一个时刻都是一个不同的随机变量，函数表达式也不是一个解析式。

我们现在先从简化问题出发，然后再去求解原问题。而简化问题就是我们之前提到的集合覆盖问题 $f(S)=|\cup i\in S x_i |$ ，这个问题其实是子模态的。证明也很简单，直接对集合进行分割就行了，这里就省去了具体的证明。我们再回归到原问题，在 $t$ 时刻节点 $v$ 引发 $w$ 的概率为 $p_{vw}$ ，这是一个 $01$ 分布。事实上这个结果是 $0$ 还是 $1$ 与时刻 $t$ 是无关的，所以我们可以预先生成好这个随机变量。对所有的边进行提前生成随机变量之后，我们就得到了一个图 $N$ . $N$ 的拓扑结构与原图一致，不同的地方就是 $p_{vw}$ 。

新图1

新图2

新图3

而当 $v$ 引发 $w$ 时， $p_{vw} =1$ ，否则就等于0.在 $N$ 中的影响最大等价于之前讨论的集合覆盖问题。设生成图 $N_i$ 的概率为 $p_i$ ，设 $f_i(X)$ 为在图 $N_i$ 上寻找影响最大的解，则

$\begin{equation}f(X)=\sum_{i=1}{p_if_i(X)}\end{equation}$

可以看出这是多个子模态函数的非负线性组合，因此 $f(X)$ 是子模态的。又根据我们在之前证明贪心法在子模态函数上是可行的，所以贪心法对影响最大问题是可行的。

参考链接¶

http://en.wikipedia.org/wiki/Submodular 维基百科上的介绍
http://www.cs.cornell.edu/home/kleinber/kdd03-inf.pdf 业界大佬kleinberg ，请收下我的膝盖。