深入理解次模函数（Submodular Function）在机器学习中的应用

可以看到第一个元素增益最大，随后逐渐衰减。这就是次模函数的本质图像。

直观理解：从朋友到物品

为了更好理解，我们可以看几个生活中的例子。

'朋友的价值'

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

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

所以 $f({}) \to f({A})$ 的增量很大，而 $f({A,B,C,D}) \to f({A,B,C,D,E})$ 的增量较小。

物品关系：替代与互补

物品之间可能存在三种关系，对应不同的函数性质：

1. Submodular（替代关系） 例如咖啡和茶，功能类似。同时拥有两者的总价值小于单独价值之和： $$f(coffee, tea) < f(coffee) + f(tea)$$

2. Supermodular（互补关系） 例如咖啡加牛奶，组合效果更好。总价值大于单独价值之和： $$f(coffee, milk) > f(coffee) + f(milk)$$

3. Modular（独立） 例如柠檬和牛奶，互不影响。总价值等于单独价值之和： $$f(A,B) = f(A) + f(B)$$

总结来说，次模函数对应的是边际收益递减，超模函数对应递增，而模块化则是线性的。

经典案例：信息熵

信息论中有一个非常重要的结论：熵（Entropy）是次模函数。

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

常见形式与应用场景

机器学习中常见的次模函数类型包括：

1. Cardinality 上的凹函数

例如 $f(S)=\sqrt{|S|}$。因为根号函数是凹函数，所以随着集合增大，边际增长递减。

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），例如在约束 $|S| \le k$ 下最大化 $f(S)$，使用贪心算法（Greedy algorithm）可以保证达到近似最优解：

$$(1 - 1/e) \approx 0.63$$

这是一个非常强的理论保证，意味着我们不需要遍历所有组合，就能得到一个接近最好的结果。

实际落地：机器学习中的典型应用

论文后半部分重点讨论了其在机器学习中的具体应用：

1. 文本摘要 从 100 句新闻中选 5 句，目标是覆盖尽量多的信息且避免重复。这种目标函数非常适合用次模函数建模。

2. 数据集压缩 例如从 100 万训练样本中选 1 万个代表样本，目标是覆盖整个数据分布。

3. 特征选择 从 1000 个特征中选 50 个，目标是信息最多且冗余最少。

4. 主动学习（Active Learning） 有 100 万未标注数据，选择最有信息的 1000 个去标注，以最小成本最大化模型性能。

结语

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

很多 AI 问题其实都是'从一堆东西里选一个子集'，无论是选数据、选句子还是选特征。如果目标函数是次模的，那么利用贪心算法就能得到接近最优的解。简单来说，次模函数让组合优化变得可解。