子模函数

子模性表达“越晚加入，新增得越少”。当当前集合很小时，新元素可能带来大量未覆盖信息；已有集合越丰富，同一个元素与既有内容重叠越多，边际贡献就越低。它与连续优化中的凹性共享收益递减的图像，但定义发生在集合格上，不能把集合并交不等式直接替换成普通导数条件。

二集合形式突出重叠：分别评估 $A$ 和 $B$ 所得到的总价值，至少覆盖合并后的整体价值与交集的共同价值。边际形式更适合算法，因为它直接比较同一候选元素在不同上下文中的作用。

给定有限宇宙 $U$ 以及每个 $e\in E$ 覆盖的子集 $C_e\subseteq U$，定义

若 $A\subseteq B$，元素 $e$ 在 $B$ 之后能新增覆盖的对象不可能多于在 $A$ 之后，因此覆盖函数单调且子模。无向图的割函数 $f(S)=|\delta (S)|$ 也是子模的，但通常不单调：把顶点移入 $S$ 既可能增加跨割边，也可能把原有跨割边变成内部边。这说明“子模”并不隐含“越多越好”。有限族离散随机变量在联合熵有限时的子集熵理路Shannon 熵Shannon entropy · Information entropy随机变量不确定性的平均信息量，以最优编码所需位数为基本解释。，以及有限拟阵秩，分别从信息重叠与独立性给出另外两类实值子模函数。

互补收益提供真实反例。取 $E=\{a,b\}$，令 $g(S)=1$ 当且仅当 $\{a,b\}\subseteq S$，否则为 $0$。从空集加入 $b$ 的边际收益为 $0$，从 $\{a\}$ 加入却为 $1$，违反边际递减，所以 $g$ 不是子模函数。若 $f$ 子模，则 $-f$ 满足反向不等式，称为超模；这不是把非单调函数误称为超模，而是改变了并交不等式的方向。

非负、单调、归一化的子模函数在基数约束下可以用贪心算法理路贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。逐步选择最大边际元素，并获得经典的 $1-1/e$ 近似保证。保证依赖这些附加条件；对非单调子模目标直接沿用同一证明会失败。

子模函数还统一图割最小化、覆盖选择、传感器布置和信息摘要。拟阵秩页理路拟阵的秩与闭包Matroid rank · Matroid closure · Matroid flat证明有限拟阵秩的子模性及秩公理的逆向重建，由此推出闭包交换，并用同一个四列矩阵计算秩、平坦与依赖证书。证明：整数值、单调、子模以及 $0\le r(S)\le |S|$ 恰好足以恢复拟阵。其关键是每个元素的边际为 $0$ 或 $1$，边际递减再强制独立集增广；一般子模函数没有这种离散限制。优化时必须区分最小化、无约束最大化以及带基数或拟阵约束的最大化，因为它们的可解性与近似界并不相同。

多线性扩张理路子模函数的多线性扩张Submodular multilinear extension · Multilinear extension of a set function用独立随机子集的期望把集合函数扩到单位立方体，推导边际导数与两类方向曲率，并分清同边缘分布、可行性和求值成本。把各元素独立入选的集合值取期望，得到单位立方体上的有限多项式。子模性使混合二阶导数非正，既支持非负方向的凹性，也支持交换方向的凸性；相同边缘但相关的随机子集一般具有不同期望。