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

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

这张图直接画的是每增加一个元素带来的'新增价值' f(S ∪ {x}) − f(S)。 可以看到：第一个元素增益最大，后面越来越小。这张图就是 Submodular 的本质图像。

三、论文给出的例子

'朋友的价值'

设：f(S) = 朋友集合 S 的价值。 如果你已经有很多朋友，再增加一个朋友的价值会变小；如果你朋友很少，那么新朋友价值更大。 例如：第 1 个朋友价值 10，第 10 个朋友价值 1。 所以 f({}) → f({A}) 增量很大，f({A,B,C,D}) → f({A,B,C,D,E}) 增量较小。这就是传说中的：边际收益递减。

四、论文里的复杂例子（咖啡、牛奶、茶）

论文用一个比较复杂的例子说明物品之间可能存在三种关系：

1. Submodular（替代关系）

例如：coffee + tea 两者功能类似。 所以：f(coffee, tea) < f(coffee) + f(tea)。因为它们是 substitutes（替代品）。

2. Supermodular（互补关系）

例如：coffee + milk 组合更好。 所以：f(coffee, milk) > f(coffee) + f(milk)。叫：complementarity（互补者）。

3. Modular（独立）

例如：lemon + milk 互不影响。 f(A,B) = f(A) + f(B)。

所以：

五、信息论里的经典例子：Entropy

论文给了一个非常重要的结论：Entropy 是 submodular 函数。

设：f(S) = H(X_S)，即某个变量集合的 entropy。 满足：f(A)+f(B) \ge f(A\cup B)+f(A\cap B)。 原因：互信息非负。这在信息论里叫：Shannon inequality（香农不等式）。

六、常见 Submodular Function 类型

论文列了一些机器学习里常见的：

1. concave over cardinality

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

2. Feature-based function

形式：f(S)=\sum_i g_i(\sum_{j\in S}w_{ij})。其中 g_i 是 concave。 常见于 NLP、document summarization。

3. Facility Location（重要）

定义：f(S)=\sum_{i\in V}\max_{j\in S} sim(i,j)。 含义：每个点 i，找 S 中最像的点。 用于：data summarization、clustering、representative subset。

4. Set Cover

f(S)=|\cup_{i\in S}C_i|。 含义：S 覆盖的元素数量。 常见：document summarization、sensor placement。

七、Submodular 为什么重要

因为它有 优化保证。

对于 Submodular Maximization（子模最大化），例如 max f(S), s.t. |S| ≤ k。 使用 Greedy algorithm（贪心算法） 可以保证：(1 - 1/e) \approx 0.63 近似最优。这是一个 非常强的理论保证。

八、机器学习中的应用

论文后半部分主要讲应用：

1. 文本摘要

从 100 句新闻选 5 句。目标是覆盖尽量多信息，避免重复。这种目标函数很适合 submodular。

2. 数据集压缩

例如：100 万训练样本，选 1 万代表样本。目标：覆盖整个数据分布。

3. 特征选择

例如：1000 个特征，选 50 个。目标：信息最多，冗余最少。

4. Active Learning

有 100 万未标注数据。选择：最有信息的 1000 个去标注。

九、总结

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

它在机器学习中的作用类似于：convex function 在连续优化中的作用。

很多 AI 问题都是'从一堆东西里选一个子集'，例如：选数据、选句子、选特征、选代表点。如果目标函数是 submodular，那么用 greedy 算法就能得到接近最优的解。所以：submodular = 让组合优化变得可解。