基于稳定性分析的非凸损失函数在线点对学习的遗憾界

郎璇聪 李春生,2 刘 勇 王 梅,2

1 （东北石油大学计算机与信息技术学院 黑龙江大庆 163318）

2 （黑龙江省石油大数据与智能分析重点实验室（东北石油大学） 黑龙江大庆 163318）

3 （中国人民大学高瓴人工智能学院 北京 100872）

4 （大数据管理与分析方法研究北京市重点实验室（中国人民大学） 北京 100071）（xuancongl@163.com）

点对学习（pairwise learning）在数据挖掘和机器学习中占有很重要的地位.在数据挖掘方面，主要的应用场景有运营式传统行业、互联网领域、物联网领域等[1]；在机器学习方面，包括排序[2-5]、接收机操作特性曲线的面积计算[6]、度量学习[7]等.

关于在线点对学习泛化性的研究，Wang 等人[8]建立的损失函数是一致有界条件下的泛化分析，给出遗憾界O(T-1).Ying 等人[9-10]基于非正则的再生核希尔伯特空间（reproducing kernel Hilbert space, RKHS）的在线点对学习算法，在损失函数没有强凸性和有界性的假设条件下，得到遗憾界O(T-1/3logT).Chen等人[11]假设迭代序列满足更紧的一致约束，给出遗憾界O(T-1/2)，同时提高了算法最后一次迭代的收敛率.Guo等人[12]基于正则的RKHS，对于特定的铰链损失函数有O(T-1/4logT1/2)收敛率.Wang等人[13]分析了具有多项式衰减步长和多个正则化参数的在线点对学习算法最后一次迭代的收敛性，给出遗憾界O(T-2/3).文献[14]提出了基于分而治之策略的多正则化项的分布式在线点对学习的误差分析.

作为用来分析泛化性的重要工具之一，稳定性分析已经被广泛应用于单点学习算法的泛化边界研究[15-16].但是，除了Shen 等人[17]和Lei 等人[18]的工作以外，关于点对学习的稳定性研究较少.Shen 等人[17]建立了随机梯度下降（stochastic gradient descent, SGD）在凸和强凸损失函数中的稳定性结果，从而给出了泛化边界，并权衡了SGD 下的泛化误差和优化误差，Lei 等人[18]提供了一个更细化的稳定性分析，并将泛化边界改进为O(γlogn).

以上所述都是假设损失函数是强凸或一般凸，缺乏对非凸损失函数的在线点对学习的理论分析.针对这一问题，本文基于稳定性分析，提出了非凸损失函数的在线点对学习的遗憾界.本文包含2 点贡献：1）提出了可以扩展到非凸损失函数的广义在线点对学习框架；2）建立了该框架下稳定性和遗憾界之间的关系，并给出了该框架的遗憾界及理论分析.

1 广义在线点对学习框架

1.1 广义在线点对学习

传统的机器学习与在线学习模式不同，传统的机器学习中，一次性地取全部训练样本进行学习，样本分为训练样本和测试样本.而在线学习没有训练样本和测试样本的区分，学习者（learner）实时获取样本，每获取到1 个实例，就调整1 次假设.

假设一个样本空间Z=X×Y，其中X⊂Rd是一个输入空间，Y⊂R是 一个输出空间，x∈X和y∈Y分别是输入和输出.在线点对学习的学习过程迭代T轮，学习者每轮接收2 个实例 (xt,yt),(x′t,y′t)，并进行预测，然后接收标签，再依损失函数 ℓt∈L遭受的损失更新假设wt+1∈W.

广义在线点对学习表示为

显而易见，与在线点对学习模型相比，广义在线点对学习是一个更鲁棒、更广义的框架.该框架中包含一个 σ 项 ， σ 项 是一个从e xp(η) （参数为η 的指数分布）采样的随机噪声.引入随机噪声项 σ避免过拟合，从而提高在线点对学习的泛化能力.因此，广义在线点对学习是鲁棒的在线点对学习，是一个更广义的在线框架.FTRL（follow the regularized leader）是一种广泛用于凸假设的非常有效的算法[19].事实上，当广义在线点对学习中的随机噪声为 µw时，FTRL 即为广义在线点对学习的一个特例：

1.2 离线神谕模型

直觉上，度量在线学习质量的方式是学习者遭受的损失函数的累计加和，学习者的目标是使累计损失尽可能的小，这也是一般学习模式性能度量的方式.但是，在线学习中的数据通常是对抗性生成的，对手知道学习者的所有信息，包括学习者给出的预测函数和损失函数等.因此，对手总是会给出与学习者预测值相反的标签，使得学习者的预测总是错误的，并遭受最大的损失.在这种对抗环境中，累计损失的度量方式难以奏效，为了解决这个问题，引入了专家（expert）这一概念.专家就是一个映射集合h:X→Y，对输入x∈X给出预测h(x)，与学习者不同的是，专家是固定的，学习者会随着时间根据损失进行更新，而专家给出的预测不会受到对手影响.采用专家的损失作为参考，矫正学习者的预测，学习者在专家中选择的时候，只需要选择对输入实例的累计损失函数值最小的专家，即最优专家.有了专家的参与，在线学习性能度量方式就是学习者遭受的损失与最优专家的损失之差的累计加和，以此避免对手的干扰.

有专家建议的在线点对学习是学习者和对手之间的重复游戏，其特征是学习者可以从含有N个专家的有限集合H中进行选择，对手从一组决策集合Y中选择，还有一个损失函数 ℓt∈L.首先，在游戏开始前，对手从Y中选择一个任意的决策序列y1,y2,…，在游戏的每一轮t=1,2,…，学习者必须选择（可能是随机的）一个专家ht∈H，然后对手揭示其决策yt∈Y，学习者遭受损失.学习者每接收到一对实例z,z′∈Z后的目标是使学习者遭受的损失与最优假设w*∈W的损失之间的累积差尽可能的小，因此，遗憾界是衡量在线点对学习性能的标准，对于算法 A定义为

基于神谕的学习模型可称之为“可优化的专家”，该模型本质上是经典的在线学习模型，即学习者通过专家的建议和一个离线神谕进行预测.在“可优化的专家”模型中，假设最初学习者对损失函数 ℓ是未知的，并允许学习者通过神谕来获取ℓ.离线神谕模型是通过学习者提交一系列的损失函数，返回使得累积损失最小的假设.定义1 给出离线神谕模型的一种近似神谕模型定义.

定义1.[20]一个离线神谕模型，其输入是一个损失函数 ℓ :W→R和 一个d维向量σ ， 输出是一个w→ℓ(w,z,z′)-〈σ,w〉的 近似最小值.若它返回的w*∈W满足

则称其为“ (α,β)-近似神谕”.

为 方 便 起 见，将 一 个 “ ( α,β)-近 似 神 谕” 记 为ORALα,β(ℓ-〈σ,·〉).使用近似神谕是因为我们不可能知道一个假设是全局最小值还是仅为一个鞍点.ORAL可以输出一个w而不需要保证其最优性.在大多数情况下，w实际上只是近似最优.离线神谕模型（返回w*∈arg minℓ(w) ） 与 (α,β)-近似神谕模型的区别在于，近似神谕模型有一个关于变量 α ， β， σ的扰动项.在指定变量 α 和 β的大小时可以获得更好的遗憾界.近似神谕模型关于在线单点学习的应用包括的实例有：当Query-GAN算法采用近似神谕时，对于非凸损失函数以T-1/2的 速度收敛[21]，累积遗憾）；FTRL 和FTL（follow the leader）算法采用近似神谕时，对于半凸损失函数可以达到T-1的遗憾界[22]， α=T-1/2.在上述应用中， β=0 ，只有 α被用作近似神谕的参数.

2 非凸广义在线点对学习的稳定性分析

2.1 非凸广义在线点对学习算法

非凸广义在线点对学习算法的原理是迭代T轮，每轮产生一个随机向量 σ（该向量服从关于参数 η的指数分布），并获得一个假设w，该假设来自于 (α,β)-近似离线神谕模型，然后，学习者会遭受相应损失并调整假设.算法1 给出当学习者可以访问 (α,β)-近似离线神谕的非凸广义在线点对学习的算法.

算法1.非凸的广义在线点对学习算法.

输入：参数η，近似神谕ORALα,β；

输出：w*∈W.

①fort=1,2,…,Tdo

③ 学习者在时刻t的假设：

⑤ 学习者遭受损失ℓt；

⑥ end for

与在线点对学习相比，广义在线点对学习中包含一个 σ项，是一个具有更强鲁棒性、更广义的算法.一些在线学习算法，如在线镜像下降（online mirror descent，OMD）[23]、 在线梯度下降（online gradient decent ，OGD）[24]、FTL、FTRL 等，通常需要在凸甚至强凸的条件下实现收敛.文献[20]通过损失函数的随机扰动来保证遗憾消失，这种随机扰动具有与FTRL 和OMD 中使用的显式正则项类似的作用，将广义在线单点学习算法扩展到非凸设置中，然而缺少关于非凸在线点对学习的内容.针对这一问题，本文将单点学习扩展到点对设置中，通过稳定性分析将在线点对中的点对耦合进行解耦，从形式上把具有耦合的点对通过稳定性分析变换成2 步假设之间的差，从而实现单点到点对学习的推广.

2.2 稳定性分析

算法稳定性是机器学习理论分析中一个重要的概念.稳定性可以衡量一个学习算法的输出对训练数据集微小变化的敏感性.对于批量学习假设中独立同分布的样本，稳定性是可学习性的一个关键特性.类似地，对于在线学习的可学习性，稳定性条件也是同样有效的.一种特别常用的稳定性度量方式是一致稳定性，已经被广泛应用到在线点对学习中，除此以外，还有由定义2 给出的平均稳定性.下文中用aTb或 〈a,b〉表 示a和b之 间 的 欧 几 里 得 点 积.用‖·‖表示2 范 数， ‖·‖p来 表 示 一 个 特 定 的 ℓp范 数.若|f(x)-f(y)|≤G‖x-y‖,∀x,y∈C ，则称f:C →R是关于‖·‖ 范 数G-Lipschitz 连续的.

定义2.[18,25]假设学习者遭受的损失序列是GLipschitz 连续的.若 ∃ γ ＞0使得

则称算法 A 是 γ-平均稳定的.

显然，平均稳定性比一致稳定性（||ℓt(wt,z,z′)-ℓt+1(wt+1,z,z′)||≤Gγ）更弱，因为前者要求的条件仅仅是wt的期望值和平均值满足不等式（1）.本文主要研究平均稳定性，所有定理采用的也是平均稳定性，以此放松理论分析中的假设条件.

稳定性分析首先将广义在线点对学习的期望遗憾与平均稳定性建立联系.如定理1 所示，构建了广义在线点对学习的期望遗憾与平均稳定性的相关性.

定理1.假设D为决策集W⊆Rd的界，学习者遭受的损失满足 ℓ1范 数的G-Lipschitz 连续性.则广义在线点对学习的遗憾上界可以表示为

本文研究“遗忘的对手”设定，因此只需使用单一的随机向量 σ，而不是在每次迭代中生成一个新的随机向量.wt(σ)为非凸广义在线点对学习基于随机扰动 σ ，在第t次迭代时的假设.

对于任意w*∈W，都有

令γ(σ)=α+β‖σ‖1.由归纳法证明

步骤T= 1：由于w2是 ℓ1(w,z,z′)-〈σ,w〉的近似最小化，因此

式（3）中最后一个不等式对任何w*∈W均成立.即

归纳步骤：假设归纳对所有T≤T0-1成立，下面证明它对T0也成立.

其中①处是由于归纳对任何T≤T0-1都成立，而②处是由于wT0+1的近似最优化.

由上述结果，得到非凸的广义在线点对学习的期望遗憾上界：

由指数分布的属性E[σi]=得证.证毕.

定理1 表明期望遗憾与平均稳定性相关.式（2）中的稳定性即为定义2 中的平均稳定性.定理1 的证明是受文献[26]的启发，证明了当平均稳定性的上界可得时，遗憾也可以实现收敛.因此，定理2 将着重于研究稳定项E[‖wt-wt+1‖1]的上界.

定理2.wt(σ) 为 广义在线点对学习在第t次迭代时的假设，其中， σ为随机扰动.ei表 示第i个标准基向量，wt,i表 示wt在i坐标上的假设.对于任意c＞0，都有单调性成立：

其中①处是由于wt(σ′)的近似最优化.结合式（4）中的第1 项和最后1 项，得

定理2 证明了包含随机扰动项 σ的广义在线点对学习的稳定性.通过观察扰动向量的变化对广义在线点对学习的输出产生的影响，表明了其在一维情况下的单调性，由于在线学习中稳定性是指相邻2 次迭代得到的假设之间的距离，因此，定理2 得到的即为一维情况下的稳定性.

定理3.wt(σ)为 广义在线点对学习在第t次迭代时的假设，其中 σ为随机扰动.ei表 示第i个标准基向量，wt,i表示wt在i坐标上的假设.假设‖wt(σ)-wt+1(σ)‖1≤有单调性成立：

其 中①处 是 由 于 ℓt(·)的Lipschitz 连 续 性，②处 是 由于‖wt(σ)-wt+1(σ)‖1上 的 假 设.由wt+1(σ′)的 近 似 最 优化，得

其中①处是由于wt+1(σ)的近似最优化.结合式（5）和式（6），得

同理

从定理2 中的单调性，得

结合上述不等式（7）～（10）得证.证毕.

定理3 证明了d维情况下广义在线点对学习的稳定性.虽然d维相较于一维的单调性证明会更具挑战性，但可以通过分别改变扰动项的每个坐标来有效地将分析减少到一维.同理，定理2 由单调性表明在线点对学习的稳定性可得d维情况下的稳定性.

3 非凸广义在线点对学习的遗憾界

利用定理1 所给出的非凸的广义在线点对学习稳定性分析，对其遗憾界进行研究.由于定理2 和定理3 分别给出了一维和高维情况稳定性E[‖wt-wt+1‖1]的界，结合定理2 和定理3 引导定理4，对定理4 进行讨论.

定理4.假设D为 决策集W⊆Rd的界.学习者遭受的损失满足 ℓ1范 数的G-Lipschitz 连续性.学习者可访问 ( α,β) -近似神谕.对于任意 η，广义在线点对学习的假设都满足遗憾界：

证明.使用与定理2 和定理3 中相同的符号定义，E[‖wt(σ)-wt+1(σ)‖1]也记作

因此，由E[||wt,i(σ)-wt+1,i(σ)||],∀i∈[d]的界，可得E[‖wt(σ)-wt+1(σ)‖1]的 界.对 于 任 意 的i∈[d]，定 义E-i[||wt,i(σ)-wt+1,i(σ)||]为

其中σj是 σ第j个坐标值.

令wmax,i(σ)=max(wt,i(σ),wt+1,i(σ)).类 似 地，令

定义

对式（12）中的T1,T2求取下界：

由于第i个坐标的域位于某个长度为D的 区间内，并且由于T1和E-i[wmax,i(σ)]是这个区间的点，它们的差值被D所 界限.所以T1的 下界为E-i[wmax,i(σ)]-D.将T2重新定义为：

改变积分中的1 个变量，令 σi=σ′i+100Gd且σ′=(σ1,σ2,…,σi-1,σ′i,σi+1,…)是 将在第i个 坐标的 σ替换为得到的向量，得

则T2=exp(-100ηGd)E-i[wmin,i(σ+100Gdei)].将T1,T2的下界代入式（12）中，可得

则E-i[wmin,i(σ)]下界：

其中式（13）中第1 个不等式来自于定理2 和定理3，第2 个 不 等 式 来 自 于 εc的 定 义.由P-i(ε)≤1，可 得

其中①处是由于.得exp(w)≥1+w

将式（15）代入到式（11）中，可得稳定性界：

将式（16）代入式（2）中，得证.证毕.

Table 1 Comparison of Online Pairwise Learning Regret Bounds表1 在线点对学习遗憾界对比

由表1 可知，本文对具有非凸损失函数的广义在线点对学习得到了O(T-1/2)的遗憾界优于已有的遗憾界.

4 结束语

本文通过引入随机噪声提出了广义在线点对学习框架.基于文献[26]提出的近似神谕的近似最优假设，提出了非凸广义在线点对学习算法.进一步，对广义在线点对学习进行泛化性研究，通过稳定性分析，得到广义在线点对学习的遗憾界O(T-1/2).

基于在线梯度下降算法，可进一步研究具有非凸损失函数的在线点对学习的遗憾界.此外，本文中的遗憾界和平均稳定性结果是建立在期望意义下的，而如何得到高概率的界也是未来可进行的工作.

作者贡献声明：郎璇聪负责研究方案的设计、证明推导，以及论文的撰写和修改；李春生指导论文撰写与修改；刘勇提出论文研究思路、设计研究方案；王梅指导论文结构设计.