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

这正是：边际收益递减（Diminishing Returns）。

这张图更关键，它直接画的是：每增加一个元素，带来的'新增价值'，也就是 $f(S \cup {x}) - f(S)$。

可以看到：

• 第一个元素 → 增益最大（≈1）
• 后面越来越小（0.4 → 0.3 → 0.2 → ...）

这张图就是 Submodular 的本质图像。

三、生活中的例子

'朋友的价值'

设 $f(S)$ 是朋友集合 $S$ 的价值。如果你已经有很多朋友，再增加一个朋友的边际价值会变小；如果朋友很少，新朋友的边际价值更大。这就是典型的边际收益递减。

物品关系

论文还举了咖啡、牛奶、茶的例子来区分不同类型的函数：

• Submodular（替代关系）：如 coffee + tea，功能类似，总价值小于单独价值之和。
• Supermodular（互补关系）：如 coffee + milk，组合更好，总价值大于单独价值之和。
• Modular（独立）：如 lemon + milk，互不影响，线性叠加。

所以：

四、信息论中的经典案例

熵（Entropy）是一个非常重要的结论：Entropy 是 submodular 函数。 设 $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} \text{sim}(i,j)$。含义是每个点找 $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$ 的近似最优解。这是一个非常强的理论保证。

七、机器学习中的应用

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

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

八、总结

次模函数的本质是一种具有'边际收益递减'性质的集合函数，使得许多指数级的离散优化问题可以高效近似求解。它在机器学习中的作用类似于凸函数在连续优化中的作用。

很多 AI 问题都是'从一堆东西里选一个子集'。如果目标函数是次模的，那么用贪心算法就能得到接近最优的解。可以说，次模性让组合优化变得可解。