次模函数（Submodular Function）核心概念与机器学习应用

这正是 边际收益递减 的体现。

这张图更关键，它直接画出了每增加一个元素带来的'新增价值' $f(S \cup {x}) - f(S)$。可以看到第一个元素增益最大，随后逐渐衰减。这就是次模函数的本质图像。

经典案例解析

'朋友的价值'

设 $f(S)$ 为朋友集合 $S$ 的价值。如果你已经有很多朋友，再增加一个朋友的价值会变小；反之，如果朋友很少，新朋友的边际价值就更大。

• 第 1 个朋友：价值 10
• 第 10 个朋友：价值 1

所以 $f(\emptyset) \to f({A})$ 的增量很大，而 $f({A,B,C,D}) \to f({A,B,C,D,E})$ 的增量较小。这就是传说中的边际收益递减。

物品关系：咖啡、牛奶与茶

论文用这个例子说明了物品间的三种关系：

1. Submodular（替代关系）：例如咖啡和茶功能类似。$f(\text{coffee}, \text{tea}) < f(\text{coffee}) + f(\text{tea})$。因为它们是替代品，叠加效应减弱。
2. Supermodular（互补关系）：例如咖啡加牛奶。$f(\text{coffee}, \text{milk}) > f(\text{coffee}) + f(\text{milk})$。这叫互补性。
3. Modular（独立）：例如柠檬和牛奶互不影响。$f(A,B) = f(A) + f(B)$。

信息论中的熵

论文给出了一个重要结论：Entropy（熵）是 submodular 函数。

设 $f(S) = H(X_S)$，即某个变量集合的熵。它满足次模不等式，原因在于互信息非负。这在信息论中对应 Shannon Inequality（香农不等式）。

常见的次模函数类型

在机器学习中，我们常遇到以下几类次模函数：

1. Cardinality 上的凹函数

例如 $f(S) = \sqrt{|S|}$。因为 $\sqrt{x}$ 是凹函数，所以边际增长递减。

2. Feature-based Function

形式为 $f(S) = \sum_i g_i(\sum_{j\in S}w_{ij})$，其中 $g_i$ 是凹函数。常见于 NLP 文档摘要任务。

3. Facility Location（设施选址）

定义：$f(S) = \sum_{i\in V}\max_{j\in S} sim(i,j)$。 含义：每个点 $i$，找 $S$ 中最相似的点。用于数据摘要、聚类和代表性子集选择。

4. Set Cover（集合覆盖）

$f(S) = |\cup_{i\in S}C_i|$。含义是 $S$ 覆盖的元素数量。常见于文档摘要和传感器放置。

为什么它很重要？

因为它提供了 优化保证。

对于 Submodular Maximization（次模最大化） 问题，例如： $$\max f(S), \quad \text{s.t. } |S| \le k$$

使用 Greedy Algorithm（贪心算法） 可以保证达到： $$(1 - 1/e) \approx 0.63$$

这是一个 非常强的理论近似最优保证。

机器学习中的应用

论文后半部分重点讨论了实际应用场景：

1. 文本摘要：从 100 句新闻中选 5 句，目标是覆盖尽量多的信息且避免重复。这种目标函数非常适合次模优化。
2. 数据集压缩：例如从 100 万训练样本中选 1 万个代表样本，目标是覆盖整个数据分布。
3. 特征选择：从 1000 个特征中选 50 个，目标是信息最多且冗余最少。
4. 主动学习：面对 100 万未标注数据，选择最有信息的 1000 个去标注。

总结

次模函数的本质是一种具有 '边际收益递减' 性质的集合函数，这使得许多指数级的离散优化问题能够被高效地近似求解。

它在机器学习中的作用，类似于 Convex Function 在连续优化中的地位。很多 AI 问题本质上都是'从一堆东西里选一个子集'，如果目标函数是次模的，那么用贪心算法就能得到接近最优的解。可以说，Submodular = 让组合优化变得可解。