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

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

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

关系类型：替代、互补与独立

物品之间可能存在三种关系：

1. Submodular（替代关系） 例如：Coffee + Tea。两者功能类似，存在替代效应。 $$f(\text{coffee}, \text{tea}) < f(\text{coffee}) + f(\text{tea})$$

2. Supermodular（互补关系） 例如：Coffee + Milk。组合起来更好。 $$f(\text{coffee}, \text{milk}) > f(\text{coffee}) + f(\text{milk})$$

3. Modular（独立） 例如：Lemon + Milk。互不影响。 $$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.} \quad |S| \le k$$

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

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

实战场景

论文后半部分主要探讨了具体应用：

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

结语

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

它在机器学习中的作用类似于 Convex Function 在连续优化中的作用。很多 AI 问题都是'从一堆东西里选一个子集'，如果目标函数是 Submodular，那么用 Greedy 算法就能得到接近最优的解。所以，Submodular 是让组合优化变得可解的关键工具之一。