Submodularity in Machine Learning and Artificial Intelligence
次模函数（submodular function）在机器学习里出现得很频繁，尤其是那些'从一堆东西里选一个子集'的问题。特征选择、数据集子集选择、主动学习、聚类、数据摘要，本质上都带着明显的组合优化味道。变量不是连续数值，而是集合；搜索空间一大，直接穷举就不现实了。次模性提供的，是一种能把这类离散问题变得可处理的结构。
核心目标
很多任务都在做同一件事：在有限预算下，尽量保留信息、减少冗余、控制成本。
- Feature Selection（特征选择）：从原始特征里挑子集，既降维，也减少无关项。
- Dataset Subset Selection（数据集子集选择）：从大数据里抽出代表性样本，训练和存储都更省。
- Active Learning（主动学习）：优先标注最有价值的样本，把标注成本花在刀刃上。
- Clustering（聚类）：按相似性组织数据，尽量让同类更集中。
- Data summarization（数据摘要）：用少量元素覆盖主要信息。
这类问题的共同点是：决策对象是集合，组合数随规模指数增长。若目标函数满足次模性质，很多时候就能借助贪心法得到不错的近似解。这也是它在 AI 里一直有存在感的原因。
什么是次模函数
对集合函数 $f: 2^V \rightarrow \mathbb{R}$，如果对任意集合 $A, B$ 都有
$$f(A) + f(B) \ge f(A \cup B) + f(A \cap B)$$
就称 $f$ 是次模函数。这条不等式就是次模不等式（submodular inequality）。
更常用的理解是边际收益递减。若 $A \subseteq B$，那么对任意元素 $e$：
$$f(A \cup {e}) - f(A) \ge f(B \cup {e}) - f(B)$$
意思很直白：同一个元素加入小集合时，带来的增益通常比加入大集合时更高。集合越大，新增一个元素的'惊喜'越少。
可以把它理解成离散版的凸/凹结构，但这个类比不要抠得太死。它的价值不在于数学外观像谁，而在于优化时能不能用。
| 集合大小 | f(S) | 增长 |
|---|---|---|
| 0 → 1 | 0 → 1 | +1 |
| 1 → 2 | 1 → 1.41 | +0.41 |
| 2 → 3 | 1.41 → 1.73 | +0.32 |
| ... | ... | 越来越小 |
随着集合变大，新增元素带来的边际收益持续下降，这就是次模性最核心的直觉。
几个常见例子
一个很容易理解的说法是'朋友的价值'。
如果你只有几个朋友，新认识一个人可能能补足很多信息；但当你已经有一大群相似的人，再来一个类似的朋友，价值就没那么高了。这个例子不严格，但足够帮助记住'边际收益递减'这个概念。
再看物品组合：
- Submodular（替代关系）：coffee + tea。两者功能相近，组合起来的增益没那么夸张。
- Supermodular（互补关系）：coffee + milk。搭配后效果更好，组合收益高于简单相加。
- Modular（独立）：lemon + milk。彼此基本不影响，直接线性叠加。
| 类型 | 数学性质 |
|---|---|
| Submodular | diminishing returns |
| Supermodular | increasing returns |
| Modular | linear |
这个区分在建模时很有用。不是所有'多加一个元素更好'的问题都适合次模函数；如果元素之间明显是互补的，硬套次模性反而会把结构压坏。
信息论里的例子
熵是一个经典例子。设 $f(S)=H(X_S)$，也就是变量集合 $X_S$ 的熵，它满足次模不等式。背后的原因和互信息非负有关，属于 Shannon inequality 的范畴。
这个例子说明次模性并不只是工程上的经验设计，它在信息论里有很扎实的理论基础。很多摘要、选择和覆盖问题之所以能被次模函数建模，就是因为'信息重叠'天然带来边际收益递减。
常见的次模函数类型
1. concave over cardinality
例如 $f(S)=\sqrt{|S|}$。因为 $\sqrt{x}$ 是凹函数，集合越大，新增一个元素的收益越小。
2. Feature-based function
形式是：
$$f(S)=\sum_i g_i\left(\sum_{j\in S}w_{ij}\right)$$
其中 $g_i$ 是凹函数。这类写法在 NLP 和文档摘要里很常见，通常用来控制覆盖度和多样性之间的平衡。
3. Facility Location（设施选址）
定义为：
$$f(S)=\sum_{i\in V}\max_{j\in S} sim(i,j)$$
它衡量的是集合 $S$ 对全体元素的代表性。哪个子集能最大程度代表整个数据集，常常就会用这个形式去建模。数据摘要、聚类、代表性子集选择里都很常见。
4. Set Cover（集合覆盖）
$$f(S)=|\cup_{i\in S}C_i|$$
意思是集合 $S$ 覆盖了多少元素。覆盖越多越好，但重复覆盖的收益会下降，所以它也自然带有次模结构。文档摘要和传感器放置里经常能看到这类目标。
为什么优化上有价值
对于下面这个问题：
$$\max f(S) \quad \text{s.t. } |S| \le k$$
如果 $f$ 是单调次模函数，贪心算法通常能给出 $1-1/e \approx 0.63$ 的近似保证。
这个结果之所以重要，不是因为 0.63 看起来多漂亮，而是因为它给了你一个很实在的底线：在很多大规模离散选择问题里，不用精确求解，也能拿到一个有理论背书的结果。工程上这比'理论上最优但跑不动'更有意义。
在机器学习里的落点
- 文本摘要：选少量句子，尽量覆盖主题，同时压住重复信息。
- 数据集压缩：从海量样本中挑代表点，保住分布形状。
- 特征选择：少选一些，但别把关键信息丢掉。
- Active Learning：优先选信息量大的样本去标注。
这些任务看起来不一样，建模时却常常共享同一种思路：想办法把'覆盖''代表性''多样性''去冗余'统一到一个目标函数里。次模函数刚好适合干这件事。
结尾
次模函数最有用的地方，不是它定义得多优雅，而是它把一类难啃的离散优化问题接到了可计算的结构上。它描述的是'越选越不值钱'的那部分世界，这恰好覆盖了很多信息选择、摘要和子集选择任务。
把它和连续优化里的凸函数类比是有帮助的，但别把类比看得太重。真正重要的是：当你的问题本身是集合选择，而且存在明显的冗余与覆盖关系时，次模建模往往比硬做精确优化更省事，也更稳。
