次模函数：离散优化中的边际收益递减
在机器学习与人工智能领域，许多问题本质上是离散优化问题。例如特征选择、数据集采样、主动学习等，其决策变量是集合而非连续值。面对指数级的组合空间，我们需要一种结构化的数学工具来保证高效优化，这就是次模函数（Submodular Function）。
一、核心定义与直觉理解
对于集合函数 $f: 2^V \rightarrow \mathbb{R}$，若对任意子集 $A, B \subseteq V$ 满足以下不等式：
$$ f(A) + f(B) \ge f(A \cup B) + f(A \cap B) $$
则称该函数为次模函数。这被称为次模不等式。
更直观的理解是边际收益递减（Diminishing Returns）。即同一个元素 $e$ 加入较小集合 $A$ 带来的增益，大于或等于加入较大集合 $B$（其中 $A \subseteq B$）的增益：
$$ f(A \cup {e}) - f(A) \ge f(B \cup {e}) - f(B) $$
这意味着随着集合规模的扩大，新增元素的价值会逐渐降低。这种性质类似于连续优化中的凸函数/凹函数结构，但在离散空间中更为复杂且实用。
可视化解释
想象一个价值曲线，横轴是集合大小，纵轴是函数值 $f(S)$。曲线初期增长迅速，随后逐渐平缓。例如从 0 到 1 个元素增益为 1，从 1 到 2 个元素增益降为 0.41，后续依次递减。这正是次模函数的本质图像。
二、典型示例
1. 社交网络中的'朋友价值'
设 $f(S)$ 为朋友集合 $S$ 的价值。当你朋友很少时，新朋友的加入能带来巨大的社交价值；但当你已有大量朋友时，再增加一个朋友的边际贡献就会变小。这符合次模性。
2. 物品间的替代与互补
- 次模（替代关系）：咖啡和茶功能类似，同时拥有的总价值小于单独拥有价值之和（$f(coffee, tea) < f(coffee) + f(tea)$）。
- 超模（互补关系）：咖啡加牛奶效果更好，总价值大于单独价值之和。
- 模函数（独立）：柠檬加牛奶互不影响，总价值等于两者之和。
3. 信息论中的熵
在信息论中，随机变量集合的熵 $H(X_S)$ 是一个经典的次模函数。这源于互信息的非负性，即香农不等式。
三、常见的次模函数类型
在机器学习中，我们常遇到以下几类次模函数：
| 类型 | 数学形式 | 应用场景 |
|---|---|---|
| 基数上的凹函数 | $f(S) = \sqrt{ | S |
| 基于特征的函数 | $f(S) = \sum_i g_i(\sum_{j\in S}w_{ij})$ | NLP、文档摘要，其中 $g_i$ 为凹函数 |
| 设施选址 | $f(S) = \sum_{i\in V}\max_{j\in S} sim(i,j)$ | 数据摘要、聚类、代表性子集选择 |
| 集合覆盖 | $f(S) = | \cup_{i\in S}C_i |
四、为什么它很重要？
次模函数的核心价值在于其优化保证。
