自动文摘（Automatic document summarization）方法综述的第一篇文章（一）总结了基于中心的（Centroid-based）方法和基于图的（graph-based）方法，第二篇文章（二）总结了基于最优化的（optimization-based）的方法。这篇博客将依旧整理基于最优化方法选取文本单元的方法，更确切的说，这篇博客将聚焦在次模函数（submodular function）最大化。

Submodularity

次模函数（submodular function）又称“子模函数”或“亚模函数”，次模函数具有次模性（submodularity），它是经济学上边际效益递减（property of diminishing returns）现象的形式化描述。给定一个集合函数$f:2^V ightarrow R$，其将有限集$V$的一个子集$Ssubseteq V$映射为一个实数。如果对于任意$S$，满足：
$f(Scup T)+f(Scap T)leq f(S)+f(T) ag 1$ 则称$f(cdot)$是次模函数。从边际效益递减的角度考虑，次模函数还有一种等价定义：对任意的$Rsubseteq S subseteq V$，并且$sin Vsetminus S$，
$f(Scup {s})-f(S)leq f(Rcup {s})-f(R) ag 2$ 公式（2）指出，当集合越来越大，$s$的“价值”将越来越小，正是边际效益递减的特性。这个现象在自然界普遍存在，例如：香农熵函数就是随机变量集合上的次模函数。当$Ssubseteq T$时有$f(S)leq f(T)$，则称该次模函数是单调的（monotone）。
更进一步，次模性是convexity（凸性）的离散模拟。由于convexity使得连续函数更容易最优化，因而次模性在组合优化中重要作用。当目标函数是次模函数时，许多组合优化问题能够在多项式时间内得到最优解或近似解。次模函数最大化被证明是一个NP-hard问题，幸运的是，存在高效并且解的质量有保证的近似算法。一个流行的结果是：最大化一个单调非负的带基数约束（cardinality constraint，即对子集$S$大小的约束）的次模函数，贪心算法至少能够达到$(1-1/e)f(S_{opt})$的结果，其中$f(S_{opt})$表示问题的最优解，$1-1/e$大约是0.63。
$f(S_{app})geq (1-frac{1}{e})f(S_{opt})$

Lin and Bilmes(2010)

Lin and Bilmes是最早将次模函数引入自动文摘的学者之一，也是对自动文摘次模性研究最深度的学者。在Multi-document summarization via budgeted maximization of submodular functions文章中，作者将自动文摘定义为预算约束（budget constraint，指每个文本单元都有一个budget）下次模函数最大化问题，形式描述如下：
$max_{Ssubseteq V}Big{f(S):sum_{iin S}c_ileq mathcal{B}Big}$ 其中，$V$是文档中所有文本单元（如：句子）的集合，$Ssubseteq V$是抽取的摘要，$c_i$是非负实数，表示选择文本单元$i$的代价，$mathcal{B}$是预算，次模函数$f(cdot)$对摘要的质量进行打分。预算约束（budget constraint）在自动文摘中天然存在，因为文摘通常有长度限制，例如：单词数目，句子数目，摘要bytes大小等。
在定义摘要质量打分函数时，作者首先将整个文档表示成一个带权图$(V,E)$，每条边$e_{i,j}in E$都关联一个非负权重$w_{i,j}$。一个著名的基于图的用来度量$S$与剩余$Vsetminus S$相似度的次模函数是graph-cut函数：
$f_{cut}(S)=sum_{iin Vsetminus S}sum_{jin S}w_{i,j}$ 在多文档摘要中，冗余是一个不能忽略的问题，一份高质量不仅需要信息丰富，而且需要紧凑。作者在这借用了MMR的思想（最大化信息覆盖度同时最小化冗余度），定义了如下目标函数：
$f_{ extbf{MMR}}(S)=sum_{iin Vsetminus S}sum_{jin S}w_{i,j}-lambdasum_{i,jin S:i eq j}w_{i,j},lambdageq0$ 上式中，无论是graph-cut函数还是冗余项都是次模的，所以整个目标函数仍然是次模的，但是不是单调的。接着作者定义了如下改进版贪婪算法：
算法存在两处改进：1）第8、9行，候选摘要$G$和具有最高得分的单文本单元$v^*$进行比较，然后才确定最终摘要$G_f$，这一步保证了当$r=1$时能够达到常数近似因子（constant approximation factor，0.63）；2）作者引入了比例因子（scaling factor）$r$用于调整代价的比率。接着作者分析了算法的性能保证（$1-frac{1} {sqrt e}$），证明部分感兴趣的朋友可以自行查看。

Lin and Bilmes(2011)

在Lin and Bilmes 2011年的文章A Class of Submodular Functions for Document Summarization中，作者设计了一类次模函数用于自动文摘任务。这些函数都由两部分组成，一部分用于鼓励摘要包含更多的信息，另一部分用于鼓励内容的多样性，即低冗余。更为关键的是，这些函数是单调不减的，这意味一个高效可伸缩的贪婪最优化方案具有常数因子最优性保证。

Submodularity in summarization

作者首先分析了自动文摘任务天然存在次模性，摘要可以从两个角度思考：

1. 在knapsack constraint下，最大化目标函数。
   $S^*in argmax_{Ssubseteq V}mathcal{F}(S)quad subject to:sum_{iin S}c_ileq b.$knapsack constraint是基数约束（$c_i=1$