基于样本的优化

张智杰，孙晓明，张家琳，陈卫

1. 中国科学院计算技术研究所，北京 100086；2. 中国科学院大学，北京 100049；3. 微软亚洲研究院，北京 100080

1 引言

为了解决实际生活中遇到的统筹优化问题，人们通常要建立一个问题模型，并确定模型的参数和优化目标函数，然后设计算法进行求解。然而，在大数据时代，许多应用场景无法提供足够的信息来确定模型参数和目标函数。人们只能通过观察到的历史样本数据来获取模型的信息，并进行优化。在这类场景下，人们通常使用机器学习的方法进行处理：首先近似地学习一个替代的目标函数，然后优化这个替代的函数。尽管这个方法在实际应用中获得了巨大的成功，但是在很多实际问题中，这个方法缺乏理论上的保证。事实上，它可能存在如下两个问题：① 即使针对原函数的优化问题是可求解或者可近似求解的，但是针对替代函数的优化问题也可能是不可近似的，这是因为替代函数可能丢失了一些原函数所具有的良好性质（如次模性）；② 即使替代函数是可近似的，而且从整体上看和原函数很接近，但是它的最优解相较于原函数的最优解也可能是一个很差的近似。这些担忧自然地引出了如下问题：人们是否真的能从一系列样本数据中求解目标函数的优化问题？

1.1 样本优化模型

为了回答基于样本的组合优化是否可能的问题，Balkanski E等人[1]定义了另一种计算模型——样本优化（optimization from samples，OPS）模型。

定义1（OPS模型）给定参数如果存在算法A（不一定是多项式时间的），给定参数并将样本集作为输入，其中，Si独立同分布于D，，算法A返回S∈M，并满足

则称函数类 在分布D下对于约束M是α-可优化的。其中，α被称为近似比，表示算法的解与最优解的比值。算法使用的样本数t被称为算法的采样复杂度。显然，样本分布D会显著影响函数类F在OPS模型下的可优化性。例如，当D总是返回空集作为样本时，不可能对问题得到任何有意义的近似比。因此，人们转而希望在某些“合理的”样本分布下，优化是可能的。此外，对于在查询模型下具有常数近似比的问题，人们通常希望它在OPS模型下也具有常数近似比。对于这类问题，如果存在分布D，当将给定多项式数量的独立同分布于D的样本作为输入时，问题存在常数近似算法，则称它们（在OPS模型下）是可优化的；反之，则称它们是不可优化的。

样本优化模型在目标函数可优化且可学习的情况下最具研究价值。Balcan M F等人[2]首先定义了集合函数的PMAC（probably mostly approximately correct learnability）-可学习性。

定义2（PMAC-可学习性）对于函数类F和参数，如果给定参数并将样本集作为输入，其中，Si独立同分布于D，，存在输出，并满足

如果在每个分布D上都是α-PMAC-可学习的，则称F在分布D上是α-PMAC-可学习的。

由定义2可知，函数类F是α-PMAC-可学习的意味着在大多数输入集合上（相对于分布D而言），存在某种算法学习到的函数值与真实的函数值很接近。并且，人们通常要求这对于任意的分布D均成立。而函数可优化性的定义只要求存在分布D使之成立即可。

最后，覆盖函数和影响力函数是这一领域的重要研究对象，下面介绍它们的定义。给定二部图G=(L,R,E)，其中，L和R分别表示左右两边的点集，E表示点之间的边集。覆盖函数定义为集合S⊆L的邻居的个数，即。而最大覆盖问题要求选取最多k个左边的节点，并最大化它们覆盖的邻居数。换言之，它要求在基数约束下最大化一个覆盖函数，即

影响力函数是覆盖函数在一般有向图上的推广。它被定义在社交网络（有向图）G=(V,E,p)上，其中，V表示点集，E表示边集，p表示概率向量，每条边(u,v)∈E具有概率。每个节点存在激活和未激活两种状态。给定t=0的初始激活节点S0（被称为种子集合），其他节点以如下方式被激活：在时刻t=1,2,3,…，首先令接着，对于每个节点，令表示v的入邻居，每个节点会以概率puv独立地激活节点v。v一旦被激活，就会被加入St中。节点被激活的过程是不可逆的，因此有。一旦没有新的节点被激活，此过程终止。显然，这一过程最多进行n-1步。因此，可以使用来表示激活节点的随机序列。上述传播过程被称为独立级联传播模型。给定S0，定义为最终的激活节点。影响力函数 被定义为，即种子集合S激活的节点数的期望。影响力最大化问题要求选取一个大小不超过k的种子集合，并最大化它激活的期望节点数，即

1.2 不可近似性结果

Balkanski E等人[1]在OPS模型下研究了最大覆盖问题的近似性，即在基数约束下最大化一个覆盖函数。此前，覆盖函数被证明是(1-)-PMAC可学习的[4]。此外，在查询模型下，最大覆盖问题是（1-e-1）-近似[5]的。因此，人们相信若采取“先学习后优化”的策略，最大覆盖问题在OPS模型下是可优化的。然而，令人惊讶的是，Balkanski E等人[1]证明了在OPS模型下，最大覆盖问题实际上是不存在常数近似的。换言之，尽管覆盖函数是可学习的，却不是可优化的。这使基于样本的组合优化问题得到一个否定性的回答。Balkanski E等人[1]的证明中构造了一类PMAC-可学习的覆盖函数，这类函数在绝大多数输入集合上能近似得很好，然而，这些近似良好的集合恰恰不是问题的最优解集，并且最优解与这些集合的函数值有较大差别。这解释了样本优化模型下不可近似性结果的由来。从概念上说，基于“先学习后优化”的思路，原问题通常可以被拆解为采样模型下的学习问题与查询模型下的优化问题。尽管这两个问题都是容易解决的，将它们结合起来却不能解决样本优化问题。这是因为这两个问题的子目标没有完全对应，学习任务的子目标只要求在绝大多数集合上学得好，但这些学得好的集合恰恰是在优化意义上比较差的集合，因此对于原函数的优化没有帮助。

OPS模型十分容易被推广到其他优化问题上，而类似的不可近似性结果也出现在其他多个优化问题中。

众所周知，无约束次模函数①对于，如果有则称函数是次模的。最小化问题可以在多项式时间内精确求解[6]。此外，当假定函数的取值在[0,1]之间时，可以证明以均等的概率返回空集或者全集，就能够得到一个1/2的加性近似[7]。针对这一问题，Balkanski E等人[7]定义了如下OPS模型。

定义3给定参数，如果存在算法A，给定参数并将样本集作为输入，其中，Si独立同分布于，算法A返回，并满足

Balkanski E等人[7]证明了，在OPS模型下存在一类PAC-可学习的取值在[0,1]之间的次模函数，对于任意分布D，将给定多项式数量的独立同分布于D的样本作为输入，这类函数不存在的加性近似。

上述不可近似性结果并不局限于组合优化中。众所周知，凸函数的最小化问题也是多项式时间可解的。针对这一问题，Balkanski E等人[8]定义了如下OPS模型。

定义4给定参数，如果存在算法A，给定参数并将样本集作为输入，其中，xi独立同分布于，算法A返回，并满足

Balkanski E等人[8]证明了，在OPS模型下，存在一类PAC-可学习的凸函数族，对于任意分布D，将给定多项式数量的独立同分布于D的样本作为输入，这类函数不存在(1/2-O(1))的加性近似。这个界是紧的（相当于最优的），这是因为可以证明返回x=(1/2,1/2,…,1/2)就能达到1/2的加性近似。

上述几个结果表明，许多在查询模型下可以优化的问题在采样模型下却是不可优化的，尽管从样本中可以学习到这些问题的目标函数。这说明了函数是可学习的并不意味着它是可优化的。

1.3 算法结果

后续有一系列工作尝试绕开OPS模型下的不可近似性结果[9-13]。这样的尝试大致可以分为3类。

第一类方法假设目标函数f拥有额外的性质。例如，Balkanski E等人[10]考虑了f是曲率为的单调②对于，如果， 则称函数是单调的。次模函数的情况。曲率[14]是衡量单调次模函数线性程度的一个度量。曲率越小，函数越接近线性。例如，线性函数和覆盖函数都满足单调性和次模性，但是线性函数的曲率为0，而覆盖函数的曲率为1。Balkanski E等人[10]证明了，在OPS模型下，当样本分布为约束上的均匀分布时，问题存在近似，并且这个近似比是最优的。线性函数的曲率为0意味着线性函数即使在OPS模型下也是可以精确求解的。而覆盖函数的曲率为1，这个结果和OPS模型下最大覆盖问题的不可近似性并不矛盾。

影响力最大化问题是社交网络研究中的核心问题之一[3]。独立级联传播模型下的影响力函数是单调次模函数的一个重要实例，而覆盖函数又是此影响力函数的特例。因此，影响力函数在OPS模型下也是不可优化的。由于影响力函数被定义在社交网络G=(V,E,p)上，为了绕开OPS模型下的不可近似性结果，Balkanski E等人[9]考虑了带有社区结构的社交网络上的影响力函数。更具体地说，他们假设G是通过随机区块模型（stochastic block model）生成的，因此G可被高概率地划分为若干社区C1,C2,… ,Cℓ，且社区内部的边比较稠密，社区之间的边比较稀疏。他们证明了，对于这样生成的社交网络和约束上的均匀分布，影响力最大化问题存在常数近似算法。

可以发现，上述方法不改变OPS模型本身，但是通常要求目标函数具有良好的性质，因此其适用范围有所限制。

第二类方法弱化了优化目标。Rosenfeld N等人[13]提出了OPS模型的一个变种版本，称之为DOPS（distributional optimization from samples）模型。

定义5（DOPS模型）给定参数如果存在算法A，对于任意分布D，给定独立同分布于D的样本集，参数并将另一批样本集作为输入，其中，Si独立同分布于D，f∈F，，算法A返回并满足

可以发现，在DOPS模型中，不存在约束M，优化目标也不是寻找全局最优解。模型的优化目标是在函数值未知的大小为m的样本集T中寻找函数值最大的样本。因此，优化目标取决于样本分布D。算法可以使用另一批函数值已知的样本集来收集函数f的信息，并最终达成上述目标。需要注意的是，在OPS模型中，要求样本数t关于基集合的大小是多项式的，表示问题规模。因此，作为类比，在DOPS模型中，要求t关于m是多项式的。

Rosenfeld N等人[13]证明了一个集合函数类在DOPS模型下是α-可优化的，当且仅当它是α-PMAC-可学习的。这种解决方式恰恰利用了之前“可学习但不可优化”的矛盾之处。函数可学习说明替代函数在绝大多数地方和目标函数很接近，而这里的绝大多数是相对于分布D而言的。如果分布D较偏离函数最优解，则会导致即使替代函数整体上接近目标函数，在最优解附近可能也会偏离较远，进而使得全局优化目标很难达成。与之相对地，只针对函数值未知的样本定义的优化目标会更容易达成。但是这个解决方式最终达成的优化目标依赖于样本数据的分布，并不符合通常对集合函数的优化问题的要求。人们仍然希望相对合理的分布D能为原目标函数的全局最优解提供一定的理论保证。

第三类方法既不假定目标函数满足额外的性质，也不弱化优化目标，而是假设样本携带额外的结构信息，这样的样本被称为结构化样本。Chen W等人[11]首先研究了这种方法，针对覆盖函数提出了OPS模型的一个变种版本——结构化样本优化（optimization from structured samples，OPSS）模型。

定义6（OPSS模型）给定参数如果存在算法A，给定参数并将样本集作为输入，其中，Si独立同分布于D，为Si在二部图G上的邻居，算法A返回S∈M，并满足

在OPSS模型中，算法不仅知道iS覆盖的邻居数，还知道它具体覆盖了哪些节点，因此掌握了关于函数结构的部分信息。Chen W等人[11]证明了，当分布D满足可行性、多项式大小的采样概率和负相关性这3个条件时，最大覆盖问题在OPSS模型下存在常数近似。因此，通过假设样本是结构化的，所得结果绕过了OPS模型下的不可近似性结果。

这一结果后来被推广到独立级联模型下的影响力函数最大化问题[12]。在OPSS模型下，算法的输入是结构化样本，其中独立同分布于D，给定的产生遵循独立级联模型的传播过程。Chen W等人[12]证明了当分布是乘积分布时，影响力最大化问题存在常数近似。

可以发现，由于不同目标函数的结构各不相同，因此难以定义通用的OPSS模型，需要基于各个函数的结构特点给出具有针对性的定义。本文将着重介绍OPSS模型下的算法结果。

2 OPSS模型

2.1 最大覆盖问题

Chen W等人[11]为OPSS模型下的最大覆盖问题设计了如下算法。

算法1：最大覆盖问题的OPSS算法

令T1=S1

以等概率返回T1和T2中的一个

算法1以相等的概率返回两个可行解T1和T2中的一个，其中T1=S1就是第一个样本，而T2是通过在二部图上运行标准最大覆盖问题的k-近似算法得到的。二部图是原图G的一个近似，它是由样本构造出来的。对于节点uL∈ ，定义它在上的邻居为用来近似它的真实邻居

直观的算法设计如下：如果某个单元素集{u}从分布D中被采样出来，那么算法能完全知晓NG(u)的信息。然而，从D中采样出来的可能是一个大集S，对于节点uS∈ ，NG(u)的信息被隐 藏 在NG(S)中。幸运的是，如果节点同时属于两个样本S1、S2，那么有。因此，算法1使用包含节点的样本的邻居的交集作为节点u的真实邻居的估计，以便尽可能地揭露u的真实邻居的信息。

为了对算法1进行严格的理论分析，需要假定算法在如下假设下运行。

假设1假设2L上的分布D满足如下3个条件。

● 可行性。样本S∼D总是可行的，即

● 多项式大小的采样概率。存在常数c>0，对于每个节点

● 负相关性。对于S∼D，随机变量是负相关的，即

上述3个条件都是非常自然的。特别地，第二个条件意味着L中的所有元素都有足够的概率被采样到。第三个条件直观上意味着u出现在样本中这一事件的发生会减少其他节点出现在样本中的概率。显然，这个条件降低了许多个节点同时出现在样本中的概率，有助于算法1揭示特定节点的邻居的信息。一些典型的分布均满足假设1，例如上的均匀分布 D≤k以及上的均匀分布Dk。基于假设1，可以证明：

定理1对于任意δ∈ ( 0,1)，给定任意标准最大覆盖问题的k-近似算法，令表示算法1返回的解，OPT表示原图G上的最优解。如果分布D满足假设1且样本数其中，c是假设1中的参数，那么

如果只要求常数近似比，则假设1中“可行性”的条件可以被放宽为Chen W等人[11]还证明了如下结论。

● 当样本分布D为均匀分布 D≤k或 Dk时，存在算法能够达到近似比。

● 移除假设1中的任意一个条件，存在满足剩下两个条件的某个分布D，在这一分布下不存在常数近似算法。这意味着为了得到OPSS模型下最大覆盖问题的常数近似算法，假设1的3个条件都是必须满足的。

2.2 影响力最大化问题

Chen W等人[12]采取如下框架求解OPSS模型下的影响力最大化问题：首先学习边的概率，然后在学习到的社交网络上求解影响力最大化问题。其中，学习边概率的任务被称为网络推断（network inference）问题，它的严格定义如下：给定结构化样本，其中独立同分布于D，给定的产生遵循独立级联模型的传播过程，，要求计算一个概率向量，使得

为了求解上述问题，Chen W等人[12]假设产生种子的分布是乘积分布，即对于样本S∼D，事件之间是相互独立的。

在是乘积分布的假设下，Chen W等人[12]提出了一个高效求解网络推断问题的方案。为了描述这一方案，需要定义一些符号。记是激活节点的随机序列。对于节点u，定义，表示u被选为种子的概率。对于节点v∈V，定义，表示v在一个时间步之内被激活的概率。节点v既有可能因为被选为种子而激活，也有可能被种子激活。因此，ap(v)定义中的随机性既来自种子分布D，也来自图G上第一个时间步之内的传播过程。此 外，定 义表示节点u不是种子时相应的条件概率。Chen W等人[12]的关键性观察如下。

引理1给定任意u,v∈V且u≠v，

引理1的证明思路如下：在一个时间步之内，节点v或者被节点u之外的节点激活，或者被节点u激活。由于D是乘积分布，可以得到

重新排列式（10）便可以得到引理1中的结果。

有了引理1后，就可以通过估计qu、ap(v)和来估计puv。

算法2：网络推断算法

对于所有u,v∈V，分别估计和

假设2存在参数和使得

● 对于所有v∈V， ap(v)≤1−α；

在假设2下，可以证明如下定理。

定理2在假设2下，令表示算法2返回的边的概率，表示真实的边概率。给定，如果样本的数量，那么

接着介绍如何利用网络推断算法解决OPSS模型下的影响力最大化问题。Narasimhan H等人[15]证明了如下引理。

引理2给定S⊆V和任意两个概率向量，并满足，用σp表示定义在图G= (V,E,p)上的影响力函数，那么

为了得到一个在任何社交网络上均能运行的OPSS算法，Chen W等人[12]采取了处理最大覆盖问题时所用的技术。具体地说，算法首先对每个节点v∈V估计ap(v)的值，并比较它们与给定阈值的大小。如果ap(v)大于给定阈值，那就意味着节点v以高概率在一步之内被激活，此时，算法将它的所有入边的概率设置为1；如果ap(v)小于此阈值，那么假设2的条件被满足，可以使用网络推断算法估计v的所有入边的概率。经过上述步骤可以得到一张新图。算法在这张新图上运行k-近似的影响力最大化算法，并得到一个解。算法使用第一个样本作为另一个解，最终以等概率返回两个解中的一个。

算法3：影响力最大化问题的OPSS算法

f or 每个v∈Vdo

else

对于所有u,v∈V，分 别 估 计、和

end if

end for

以等概率返回1T和2T中的一个

上述算法与最大覆盖问题的OPSS算法（算法1）的设计思路是一致的。ap(v)接近1意味着节点v以高概率在一步之内被激活，因此网络推断算法的假设不被满足，算法无法学习到节点v的入边概率。幸运的是，这同时意味着任意一个样本都能够以高概率激活节点v。因此算法无须学习节点v的入边概率，而是直接把它们设置为1。这样的设置几乎不改变样本激活节点v的概率。

上述设计使得算法能够处理任意ap(v)，从而移除了假设2中关于ap(v)的条件。而作为代价，算法需要假设样本的期望大小不超过k/2，从而保证采样出来的样本高概率是可行的。因此，算法需要在下面的假设下运行。

假设3存在参数，使得

显然，假设3的两个条件都是针对样本分布的，不针对社交网络。因此，算法3在任何社交网络都可以成功运行。可以证明，算法3是一个常数近似算法。

定理3对于任意，给定任意标准影响力最大化问题的k-近似算法，令表示算法3返回的解表示原图G上的最优解。如果分布D满足假设3且样本数那么

最后，若把假设3中的第一个条件改为“存在常数c>0，使得”，仍然能够通过修改算法得到一个常数近似比。如果，那么可以修改算法得到一个-近似。

3 未来研究方向

样本优化仍然有许多可以进一步研究的方向。

● 针对OPSS模型下的最大覆盖问题和影响力最大化问题，降低现有算法的查询复杂度。此外，目前影响力最大化的OPSS算法假设样本分布是乘积分布。如何突破这样的独立采样假设是一个十分重要的开放问题，一种可能的方法是将文中的方法与极大似然估计方法结合。

● 对更多的目标函数定义适当的结构化样本，并研究它们在OPSS模型下的近似性。一个直接的例子是线性阈值模型下的影响力最大化函数（笔者已经得到了这方面的初步结果）。可以发现，OPSS模型是一个表达能力丰富、能够挖掘函数内在结构性质的模型。因此，在OPSS模型下研究各类优化问题是一个十分有潜力的研究方向。

● 研究更多的方法以绕开标准OPS模型下的不可近似性结果。更多这样的研究一方面有助于人们应对不同的应用场景，另一方面有助于人们理解样本数据与函数可优化性的内在联系。

● 研究从样本中优化凸函数的可能性。目前所有绕开OPS模型不可近似性结果的方法都是针对集合函数而言的。对于实函数，尤其是具有良好优化性质的凸函数，尚没有这方面的研究。考虑到凸函数在连续优化中的重要地位，对它的进一步研究是十分必要的。

4 结束语

本文总结了OPS模型及其变种模型下的不可近似性结果和算法成果，并展望了相关的未来研究方向。OPS模型是数据驱动的优化的重要研究方法之一，值得进行更加深入的研究。