前言

次模函数（Submodular Functions）是组合优化和离散数学中的一个重要概念，广泛应用于计算机科学、经济学、系统工程等领域。

例如，在机器学习和数据挖掘中，次模函数用于特征选择、聚类、影响力最大化等问题。具体来讲，选择最能代表数据集的特征子集是一个次模优化问题。次模函数的边际递减性质保证了选择的每个新特征提供的信息量随着已选择特征的增加而递减，帮助避免过拟合。

又如，在图论中，次模函数用于解决最小割、最大流等问题。网络分析中的影响力最大化问题也是一个典型的次模函数应用，如在社交网络中最大化信息传播。

From concavity to submodularity

在了解Submodularity之前，我们先来了解一下什么是Controlcavity(由于各文献对该词翻译不一，一说凹面性，一说凸面性，故不做翻译)。

如上图所示，对于函数$f$，如果$f^{\prime}(\mathbf{x})$是不增的，则$f:\mathbb{R}\to\mathbb{R}$ 是 concave的。

类似的，如上图所示，对任意$i$ ，若$\partial_if(x)=f(x+e_i)-f(x)$是不增的，则$f:{0,1}^n\to\mathbb{R}$是Submodular(次模)的。值得注意的是Submodular function的定义域是离散。

1. 如上图所示$S\subset T,j\notin T$，若$f$满足 $$ f(S \cup \{j\}) - f(S) \geq f(T \cup \{j\}) - f(T) $$ 则称$f$是submodular的。

2. 若$f:2^{[n]}\to\mathbb{R}$满足对任意$S$，$T$满足下式，则$f$是submodular的。 $$ f(S\cup T)+f(S\cap T)\leq f(S)+f(T). $$ 也就是说，对于任何两个嵌套的子集(例如,$A\subset B$), 向A和B中添加同一个新元素，A的增益至少与B的增益一样大。这反映了一种“边际递减”的特性。

次模函数可以用来描述诸如“越多越便宜”或“规模经济”这样的现象。例如，考虑一个购物场景，购买第一个商品可能带来较大的满足感，但随着购买的商品数量增加，每增加一个商品带来的额外满足感会逐渐减少。

Optimization of Submodular Function

对于一个次模函数，如何求它的最大值和最小值？

Lovász extension

前人(Grötschel-Lovász-Schrijver, 1981; Iwata-Fleischer-Fujishige / Schrijver, 2000)利用Lovász扩展可以在多项式时间内解决任何次模函数$f:{0,1}^n\to\mathbb{R}$的最小化问题。

通过Lovász扩展，次模函数( f )可以转化为一个convex function $ f^L $。 $$ f^L(x) = \mathbb{E}_{\lambda\in[0,1]}[f(\{i : x_i > \lambda\})] $$ 转化之后的$f^L$由于在连续的定义域上，因此可以轻松的求出最小值。而$f^L(x) $的最小化值可以转换为$f(S) $的最小化值。

通过这种方式，次模函数的最小化问题转化为convex optimization问题得以解决。

Greedy

回想上文子模函数的定义，在直觉上它与concave functio很相似，但实际上子模函数的最大化是一个典型的NP-hard问题！(实际问题有Max Cut和Max Coverage问题)

类似的，如上图所示，对任意$i$ ，离散导数$\partial_if(x)=f(x+e_i)-f(x)$是不增的，则$f:\{0,1\}^n\to\mathbb{R}$是submodular(次模)的。

有关P, NP, NPC, NP-hard的内容详见 http://www.matrix67.com/blog/archives/105

至此，问题无法解决了吗？其实不然，即使无法完全求出子模函数的最大值，如果可以求出最优解的近似值也是可以接受的。

首先我们对问题进行定义： $$ \max_{S\subseteq\mathcal{V},S\in\mathcal{I}}f(S),S\subset T\Rightarrow f(S)\leq f(T) $$ 其中 $f(\cdot)$ 是定义在数据集 $\nu$ 上的次模函数，$\mathcal{I}$ 是依赖于具体场景的约束(很多时候可能不能选全集)。值得注意的是，这次我们限制了$f$是单调递增的。

对于此问题，可以使用贪心的思想来求解。每次选择一个可以最大化收益的元素加入集合$S$中。即确保元素$i$，使得$ f(S+i)-f(S)$最大，同时确保$S$保持在可行域$\mathcal{I}$中。

Nemhauser, Wolsey, Fisher在1978年的定理指出，如果$f$是单调且次模的，则贪心算法找到的解至少为问题$\max_{S\subseteq\mathcal{V},S\in\mathcal{I}}:|S| ≤ k$最优解的$ (1 - 1/e) $倍。

Nemhauser,Wolsey,Fisher ’78 https://www.cs.toronto.edu/%7Eeidan/papers/submod-max.pdf]

证明见https://zhuanlan.zhihu.com/p/560699106

至此我们对submodular problem的求解有了基础的认识，但是上述方案仍然有几个问题没有解决

• 对于形式化为最大化$f(S)$的问题，当 $f$是单调次模的并且$I$形成一个拟阵时，最优的近似程度是多少。
• 非单调次模函数的优化问题。
• 更一般的约束条件，或者是多种简单约束的组合。

此后又有一些学者提出了基于贪心的Submodular Optimiaztion方法

Multilinear Relaxation

有学者(Calinescu,Chekuri,Pál,V. ’07)尝试用次模函数的多线性松弛(Multilinear Relaxation)将离散优化问题转换成连续优化问题

多线性扩展 $F(x) $是通过以下方式定义的： $$ F(x) = \mathbb{E}[f(\hat{x})] $$ 其中$\hat{x}$ 是通过将每个$x_i$ 以$x_i$ 的概率随机舍入到0或1获得。

Multilinear Relaxation有以下性质：

• $F(x)$既不是全局concave也不是全局convex。
• 对$F$的二阶导数$\frac{\partial^2 F}{\partial x_i^2}$为零
• 如果$\vec{d}$是非负的则$F(x + \lambda \vec{d})$是关于$\lambda$的concave function。

通过将离散问题转化为连续问题，使用连续优化手段来寻找近似解，然后将这些解舍入到最接近的整数解以用于解决离散问题。

Continuous Greedy

求解$F(x)$的最大值$\max{F(x):x\in P)}$，F为单调子模函数的多线性扩展(multilinear extension)。

对于每一个 $x \in P$， $v(x)$为 $$ v(x) = argmax_{v \in P}(v \cdot \nabla F(x)) $$ 定义 $x(t)$：

• $x(0) = 0$
• $\frac{dx}{dt} = v(x)$

其中 $t \in [0, 1]$ 范围内变化，返回 $x(1)$。

在该方法中$x(1) \in P$, $F(x(1))$至少是最优解(OPT)的$(1-\frac1e)$倍。

根据链式法则 $$ \frac{dF}{dt}=\frac{dx}{dt}\cdot\nabla F(x(t))=v(x)\cdot\nabla F(x(t))\geq OPT-F(x(t)). $$ 得 $$ F(x(t))\geq(1-e^{-t})\cdot OPT. $$

Reference:

[1] https://theory.stanford.edu/~jvondrak/data/SIDMA-plenary-talk.pdf

[2] https://zhuanlan.zhihu.com/p/560699106

[3] https://www.cs.toronto.edu/%7Eeidan/papers/submod-max.pdf