综述论文：Submodularity In Machine Learning and Artificial Intelligence
本文是一篇关于 Submodular functions（次模函数） 及其在 机器学习与人工智能中应用 的综述。
一、核心目标
许多机器学习问题本质上是 离散优化问题。例如：
- Feature Selection（特征选择）：从原始特征中筛选最相关子集，降低维度并提升性能。
- Dataset Subset Selection（数据集子集选择）：选取代表性子集，降低成本并保持性能。
- Active Learning（主动学习）：主动选择最有价值数据标注，最小化成本最大化性能。
- Clustering（聚类）：根据相似性将未标记数据分组。
- Data summarization（数据摘要）：生成简洁摘要捕捉核心信息。
这些问题的决策变量是 集合 (set) 而非连续变量。组合数量呈指数级增长，因此需要一种结构使得指数空间的问题能高效优化，这就是 Submodular Function 的意义。
类比：Submodular ≈ 离散版本的 convex/concave 结构。
二、什么是 Submodular Function
1. 正式定义
对于集合函数 $f: 2^V \rightarrow \mathbb{R}$，若对所有集合 $A, B$ 满足以下不等式，则称为次模函数：
$$f(A) + f(B) \ge f(A \cup B) + f(A \cap B)$$
这被称为 Submodular inequality（次模不等式）。
2. 直观理解：边际收益递减
论文强调：Submodularity = Diminishing Returns（边际收益递减）。
数学表达为：当 $A \subseteq B$ 时，
$$f(A \cup {e}) - f(A) \ge f(B \cup {e}) - f(B)$$
即：同一个元素 $e$ 加入 小集合 的价值 ≥ 加入 大集合 的价值。
3. 可视化解释
随着集合大小增加，函数值 $f(S)$ 的增长速度逐渐变慢。
| 集合大小 | f(S) | 增长 |
|---|---|---|
| 0 → 1 | 0 → 1 | +1 |
| 1 → 2 | 1 → 1.41 | +0.41 |
| 2 → 3 | 1.41 → 1.73 | +0.32 |
| ... | ... | 越来越小 |
每增加一个元素带来的'新增价值' $f(S \cup {x}) - f(S)$ 随集合增大而减小。
