背景:为什么需要次模函数?
很多机器学习问题本质上其实是离散优化问题。决策变量往往是一个集合,而不是连续变量。
比如特征选择(Feature Selection),我们需要从原始特征中筛选出最相关的子集;或者数据集采样(Dataset Subset Selection),从大规模数据中选取代表性样本。这些问题的组合数量是指数级的。
面对指数级空间,我们需要一种结构,使得优化过程依然高效。
这就是 Submodular Function(次模函数) 登场的原因。它在离散优化中的地位,类似于凸函数(convex function)在连续优化中的地位。
核心定义:边际收益递减
论文给出的正式定义针对集合函数 $f: 2^V \rightarrow R$。对于任意两个集合 $A, B$,满足以下不等式:
这被称为 Submodular Inequality(次模不等式)。
但更直观的理解来自其核心性质:Diminishing Returns(边际收益递减)。
数学表达为:
当 $A \subseteq B$ 时,这意味着同一个元素 $e$ 加入小集合的价值,大于或等于加入大集合的价值。
可视化解释
想象一个价值曲线,横轴是集合大小 $|S|$,纵轴是价值 $f(S)$。

曲线特点是一开始增长很快,后面越来越平缓。具体来看:
| 集合大小变化 | f(S) 变化 | 增长量 |
|---|---|---|
| 0 → 1 | 0 → 1 | +1 |
| 1 → 2 | 1 → 1.41 | +0.41 |
| 2 → 3 | 1.41 → 1.73 | +0.32 |
| ... | ... | 越来越小 |
这正是边际收益递减的体现。再看另一张图,直接展示了每增加一个元素带来的新增价值:



