编程语言AI算法
次模函数（Submodular Function）概念与机器学习应用
综述了次模函数（Submodular Function）在机器学习和人工智能中的应用。核心概念是边际收益递减（Diminishing Returns），即集合中新增元素的贡献随集合增大而减小。它被视为离散优化中的凸函数，具有理论上的近似最优保证（如贪心算法可达 1-1/e）。主要应用于特征选择、数据集压缩、文本摘要、主动学习等离散优化问题，帮助在指数级搜索空间中高效求解。
综述了次模函数（Submodular Function）在机器学习和人工智能中的应用。核心概念是边际收益递减（Diminishing Returns），即集合中新增元素的贡献随集合增大而减小。它被视为离散优化中的凸函数，具有理论上的近似最优保证（如贪心算法可达 1-1/e）。主要应用于特征选择、数据集压缩、文本摘要、主动学习等离散优化问题，帮助在指数级搜索空间中高效求解。
本文是一篇综述论文，核心目标是介绍 Submodular functions（次模函数） 以及它们在 机器学习与人工智能中的应用。
作者强调一个重要的观点：很多机器学习问题其实是'离散优化问题'。
例如：
这些问题的共同特点：决策变量是 集合 (set) 而不是连续变量。例如从 1000 个数据里选 100 个，组合数量是指数级的。
因此需要一种结构，使得 指数空间的问题仍然能高效优化。这就是 Submodular Function 的意义。
作者提出一个类比：
| 连续优化 | 离散优化 |
|---|---|
| convex function | submodular function |
可以简单理解为：Submodular ≈ 离散版本的 convex/concave 结构，但其实更复杂。
论文给出的正式定义是：对于集合函数 $f:2^V \rightarrow R$，即输入为集合的子集，输出为一个数值。满足：
$$f(A)+f(B) \ge f(A\cup B)+f(A\cap B)$$
对所有集合 A,B。这叫 Submodular inequality。
论文强调：Submodularity = Diminishing Returns（边际收益递减）。
数学表达：
$$f(A \cup {e}) - f(A) \ge f(B \cup {e}) - f(B)$$
当 $A \subseteq B$ 时。
意思是：同一个元素 e 加入 小集合 的价值 ≥ 加入 大集合 的价值。这就是 submodular 的核心思想。
这张图表示：f(S) 为集合 S 的'价值'，|S| 为集合大小。曲线特点是一开始增长很快，后面越来越平。
| 集合大小 | f(S) | 增长 |
|---|---|---|
| 0 → 1 | 0 → 1 | +1 |
| 1 → 2 | 1 → 1.41 | +0.41 |
| 2 → 3 | 1.41 → 1.73 | +0.32 |
| ... | ... | 越来越小 |
这正是：边际收益递减（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}) 增量较小。这就是传说中的：边际收益递减。
论文用一个比较复杂的例子说明物品之间可能存在三种关系：
例如：coffee + tea 两者功能类似。
所以：f(coffee, tea) < f(coffee) + f(tea)。因为它们是 substitutes（替代品）。
例如：coffee + milk 组合更好。
所以：f(coffee, milk) > f(coffee) + f(milk)。叫：complementarity（互补者）。
例如：lemon + milk 互不影响。
f(A,B) = f(A) + f(B)。
所以：
| 类型 | 数学 |
|---|---|
| Submodular | diminishing returns |
| Supermodular | increasing returns |
| Modular | linear |
论文给了一个非常重要的结论：Entropy 是 submodular 函数。
设：f(S) = H(X_S)，即某个变量集合的 entropy。
满足：f(A)+f(B) \ge f(A\cup B)+f(A\cap B)。
原因：互信息非负。这在信息论里叫：Shannon inequality（香农不等式）。
论文列了一些机器学习里常见的：
例如：f(S)=\sqrt{|S|}。因为 \sqrt{x} 是 concave，所以边际增长递减。
形式：f(S)=\sum_i g_i(\sum_{j\in S}w_{ij})。其中 g_i 是 concave。
常见于 NLP、document summarization。
定义：f(S)=\sum_{i\in V}\max_{j\in S} sim(i,j)。
含义：每个点 i，找 S 中最像的点。
用于：data summarization、clustering、representative subset。
f(S)=|\cup_{i\in S}C_i|。
含义：S 覆盖的元素数量。
常见：document summarization、sensor placement。
因为它有 优化保证。
对于 Submodular Maximization（子模最大化），例如 max f(S), s.t. |S| ≤ k。
使用 Greedy algorithm（贪心算法） 可以保证：(1 - 1/e) \approx 0.63 近似最优。这是一个 非常强的理论保证。
论文后半部分主要讲应用：
从 100 句新闻选 5 句。目标是覆盖尽量多信息，避免重复。这种目标函数很适合 submodular。
例如：100 万训练样本，选 1 万代表样本。目标：覆盖整个数据分布。
例如：1000 个特征，选 50 个。目标：信息最多，冗余最少。
有 100 万未标注数据。选择：最有信息的 1000 个去标注。
Submodular function 的本质：一种具有'边际收益递减'性质的集合函数，使得许多指数级的离散优化问题可以高效近似求解。
它在机器学习中的作用类似于：convex function 在连续优化中的作用。
很多 AI 问题都是'从一堆东西里选一个子集'，例如：选数据、选句子、选特征、选代表点。如果目标函数是 submodular，那么用 greedy 算法就能得到接近最优的解。所以：submodular = 让组合优化变得可解。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
生成新的随机RSA私钥和公钥pem证书。 在线工具，RSA密钥对生成器在线工具，online
基于 Mermaid.js 实时预览流程图、时序图等图表，支持源码编辑与即时渲染。 在线工具，Mermaid 预览与可视化编辑在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online