次模函数与机器学习中的离散优化

这个区分在建模时很有用。不是所有'多加一个元素更好'的问题都适合次模函数；如果元素之间明显是互补的，硬套次模性反而会把结构压坏。

信息论里的例子

熵是一个经典例子。设 $f(S)=H(X_S)$，也就是变量集合 $X_S$ 的熵，它满足次模不等式。背后的原因和互信息非负有关，属于 Shannon inequality 的范畴。

这个例子说明次模性并不只是工程上的经验设计，它在信息论里有很扎实的理论基础。很多摘要、选择和覆盖问题之所以能被次模函数建模，就是因为'信息重叠'天然带来边际收益递减。

常见的次模函数类型

1. concave over cardinality

例如 $f(S)=\sqrt{|S|}$。因为 $\sqrt{x}$ 是凹函数，集合越大，新增一个元素的收益越小。

2. Feature-based function

形式是：

$$f(S)=\sum_i g_i\left(\sum_{j\in S}w_{ij}\right)$$

其中 $g_i$ 是凹函数。这类写法在 NLP 和文档摘要里很常见，通常用来控制覆盖度和多样性之间的平衡。

3. Facility Location（设施选址）

定义为：

$$f(S)=\sum_{i\in V}\max_{j\in S} sim(i,j)$$

它衡量的是集合 $S$ 对全体元素的代表性。哪个子集能最大程度代表整个数据集，常常就会用这个形式去建模。数据摘要、聚类、代表性子集选择里都很常见。

4. Set Cover（集合覆盖）

$$f(S)=|\cup_{i\in S}C_i|$$

意思是集合 $S$ 覆盖了多少元素。覆盖越多越好，但重复覆盖的收益会下降，所以它也自然带有次模结构。文档摘要和传感器放置里经常能看到这类目标。

为什么优化上有价值

对于下面这个问题：

$$\max f(S) \quad \text{s.t. } |S| \le k$$

如果 $f$ 是单调次模函数，贪心算法通常能给出 $1-1/e \approx 0.63$ 的近似保证。

这个结果之所以重要，不是因为 0.63 看起来多漂亮，而是因为它给了你一个很实在的底线：在很多大规模离散选择问题里，不用精确求解，也能拿到一个有理论背书的结果。工程上这比'理论上最优但跑不动'更有意义。

在机器学习里的落点

• 文本摘要：选少量句子，尽量覆盖主题，同时压住重复信息。
• 数据集压缩：从海量样本中挑代表点，保住分布形状。
• 特征选择：少选一些，但别把关键信息丢掉。
• Active Learning：优先选信息量大的样本去标注。

这些任务看起来不一样，建模时却常常共享同一种思路：想办法把'覆盖''代表性''多样性''去冗余'统一到一个目标函数里。次模函数刚好适合干这件事。

结尾

次模函数最有用的地方，不是它定义得多优雅，而是它把一类难啃的离散优化问题接到了可计算的结构上。它描述的是'越选越不值钱'的那部分世界，这恰好覆盖了很多信息选择、摘要和子集选择任务。

把它和连续优化里的凸函数类比是有帮助的，但别把类比看得太重。真正重要的是：当你的问题本身是集合选择，而且存在明显的冗余与覆盖关系时，次模建模往往比硬做精确优化更省事，也更稳。