学习理论：在线弃权学习 _

1 在线弃权学习问题定义设X为输入空间例如Rd的有界子集H为预测器h:X→Yℎ:→的函数类并假设h∈Hℎ∈ 在有标签样本对(x,y)∈X×Y(,)∈×所计算的损失l(y,h(x))(,ℎ())可以定义为0/1损失Ih(x)≠yℎ()≠或一些其它满足Lipschitz性质的变体。 在在线弃权学习中有K个专家expert对应不同的预测器h1(⋅),⋯,hK(⋅)ℎ1(⋅),⋯,ℎ(⋅)可能还会有拒绝器分别对应K个不同的动作类似bandit中arm。依赖于设置K可以为有限或不可数无限的。假设可供选择的专家集合对学习算法是事先已知的。大致地说在线弃权学习的一般流程如下在第t∈[T]∈[]轮时在线算法接收输入xt∈X∈并根据专家1,2,⋯,K1,2,⋯,的输出结果来判定是做预测还是弃权可能是随机抽取一个专家It也可能是多个专家的加权平均若选择弃权则算法弃权并产生一个大小为弃权代价c(xt)∈[0,1]()∈[0,1]的损失否则根据专家1,⋯,K1,⋯,的输出h1(xt),⋯,hK(xt)ℎ1(),⋯,ℎ()的来进行预测可能是随机抽取一个专家It也可能是多个专家的加权平均。然后各个专家计算各自的损失Lt,i,并根据损失更新各个专家的加权参数如果有的话。专家i在有标签样本对z(x,y)∈X×Y(,)∈×上的弃权损失absention loss的典型定义方式为L(hi,z)l(y,hi(x))I选择预测cI选择弃权(ℎ,)(,ℎ())选择预测选择弃权出于简洁我们假设弃权代价c(x)()为一个独立于x的已知常数c∈[0,1]∈[0,1]这个弃权损失与我们在博客《学习理论预测器-拒绝器多分类弃权学习》[3]中所介绍的类似不过这里需要注意的是标签y不一定对所有专家都是可知的标签y可能仅当不弃权时可知[4]也可能仅当弃权的时候可知[8]也可能无论弃权与否都可知[9]。而这也就导致了如上式所示的弃权损失函数并不一定对所有专家都是可观测的。对于前两种情况仅有部分专家可以观测到如上式所示的损失函数我们称其为是部分信息partial information的 而最后一种情况所有专家都可以观测到如上式所示的损失函数我们称其是完全信息full information的。注所谓部分信息设置可以视为介于完全信息和传统bandit之间的一种设置[5][7]。此三者的对比如下完全信息: 每一轮t中学习器可以观测到完整的损失函数Lt(⋅)(⋅)因此可以利用函数的信息比如梯度更新模型。bandit: 每一轮t中学习器通常只能观测到损失函数在所选决策ξIt上的值Lt(ξIt)()不能观测到损失函数在其它决策上的值。部分信息: 每一轮t中学习器可以观测到损失函数在一个决策集合{ξi}{}包括所选决策ξIt在内上的值{Lt(ξi)}i{()}。部分信息设置的在线学习有时也被称为附加信息的banditbandit with side-information。和传统bandit问题相似在线弃权学习也会考虑对抗adversarial和随机stochastic两种设置[5][7]。注传统bandit问题中的对抗和随机设置如下对抗设置每一轮t中学习器选择arm ξIt后一个对手adversary对其行动赋予代价Lt(ξIt)()。学习器可以观察到行动ξIt的代价除此之外什么也得不到。学习器的目标是最小化它的regret。随机设置每一轮t中学习器选择arm ξIt后根据从一个分布中i.i.d采样的损失函数Lt(⋅)(⋅)来计算其代价Lt(ξIt)()。学习器可以观察到行动ξIt的代价除此之外什么也得不到。学习器的目标是最小化它的regret。具体在在线弃权学习中它们的区别在于对抗设置不会对序列zt(xt,yt),t∈[T](,),∈[]做出分布假设而随机设置则会假设zt i.i.d.地采自某个在X×Y×上的分布D。在这两种设置中都可以通过算法A的伪regret RT(A)() 来度量算法A的表现如果在第t轮随机抽取了专家It那么它可以采用如下的方式来定义RT(A)E[T∑t1L(hIt,zt)−infi∈[K]T∑t1L(hi,zt)]()[∑1(ℎ,)−inf∈[]∑1(ℎ,)]其中期望所对应的随机性一是来源于算法所选择的{It}Tt1{}1二是来源于在随机情形下所采样的{zt}Tt1{}1。对于专门设置拒绝器的情况式子中的hItℎ和hℎ可以分别替换为(hIt,rIt)(ℎ,)和(h,r)(ℎ,)。在随机设置下考虑专家集合有限的情况设此时有K个专家则可以将专家 i∈[K]∈[]的期望损失和最优专家的期望损失分别表示为μiEz∼D[L(hi,z)],μ∗mini∈[K]μi∼[(ℎ,)],∗min∈[]其中对于有拒绝器的情况hiℎ可以替换为hℎ。然后可以ΔiΔ表示μi和μ∗∗之间的差距Δiμi−μ∗Δ−∗这一项经常出现在随机设置相关的regret界中。2 仅当不弃权时反馈可知现考虑仅当不弃权时反馈可知的情况其代表性论文为《Online learning with absention》[4]。该论文考虑在线二分类场景设此时的预测器为h:X→Rℎ:→根据其正负号判断0/1类别于是0/1损失可以写为Iyh(x)⩽0ℎ()⩽0。此外论文还另外设置有拒绝器r:X→R:→。设R为弃权函数r:X→R:→的函数类r⩽0⩽0表示对x∈X∈进行弃权或者说拒绝r00表示对x进行预测或者说接受。给定hiℎ一个与之相关的弃权函数ri的自然选择是形如 ri(x)|hi(x)|−θ()|ℎ()|− 的基于置信度的弃权函数其中θ为某个阈值。除此之外也可以考虑更多一般形式的ri。论文算法的基本流程大致如下在第t∈[T]∈[]轮时在线算法接收输入xt∈X∈并选择可能是随机地一个专家It。若rIt(xt)⩽0()⩽0则算法弃权并产生一个大小为弃权代价c∈[0,1]∈[0,1]的损失。否则根据hIt(xt)ℎ()的符号来进行预测并接收真实标签yt∈{±1}∈{±1}来计算损失l(yt,hIt(xt))(,ℎ())。因此(h,r)(ℎ,)在标签对z(x,y)(,)上整个弃权损失L定义为L(h,r)l(y,h(x))Ir(x)0cIr(x)⩽0(ℎ,)(,ℎ())()0()⩽0这里需要注意的是如果学习器在第t轮选择预测也即当rIt(x)0()0时由于标签yt已经暴露给了它它可以观察到每个专家 i∈[K]∈[]的损失L(hi,ri,zt)(ℎ,,)。然而如果它在第t轮选择弃权也即rIt(x)⩽0()⩽0则它将只观测到与在该轮中选择弃权的专家j相关的损失 L(hj,rj,zt)c(ℎ,,)其中j取自满足rj(xt)⩽0()⩽0的j集合。这是因为此时对所有这样的j我们都有L(hj,rj,zt)c(ℎ,,)。这里需要注意的是在这两种情况中学习器都可以观测它自己动作It的损失。这种部分信息的在线学习设置可以用反馈图feedback graph来描述。带反馈图的在线学习是一个囊括了多种在线学习设置的一般性框架在完全信息设置下图是全连接的而在传统bandit设置下顶点通常是只有自环且分离的。设依赖于xt的有向图Gabst(V,Et)abs(,)。这里V{ξ1,⋯,ξK}{1,⋯,}表示图的有限顶点集对应专家组成的有限集。Et表示第t轮时的有向边集合。如果当t轮时算法选择专家i时专家j∈[K]∈[]的损失被观测到则Et中将会存在边ξi→ξj→。因此在仅当不弃权时反馈可知的设置下反馈图是一个带自环的接近全连接的图不过在预测顶点和弃权顶点之间只有从预测顶点到弃权顶点的单向边下图展示了一个当专家数K为5时的一个例子。从上图中可以看到反馈图Gabstabs完全由xt确定这是由于xt确定后则可根据{ri(xt)}{()}决定每个专家i的弃权情况从而确定反馈图。依据《Online learning with absention》[4]这篇论文的作者的观点对于这种设置下的弃权损失L(hi,ri,z)(ℎ,,)难以找到其代理凸上界来使用在线凸优化方法。事实上论文作者更多地是采用离散的视角使用bandit中的许多技术来设计的算法。论文作者讨论了对抗和随机两种设置我们下面以对抗设置为例进行介绍。而对抗设置又可以具体分为有限和无限个专家的场景。我们先讨论有限多个专家的对抗设置。论文作者同时结合了诸如EXP3的标准有限arm的bandit算法和反馈图Gabstabs来为弃权场景设计在线算法并将其称为EXP3-ABSEXP3 with absention[4]。该算法为EXP3的变种其中为了达到对Lt(hi,ri,zt)(ℎ,,)无偏损失估计的重要性采样参数是根据被观测到的专家的损失来计算的而不是根据被选中的专家的损失来计算的。EXP3-ABS算法的大致流程如下对每一轮迭代t∈[T]∈[]:采样专家索引It∼ptwt,i∑wt,j,i∈[K]∼,∑,,∈[]如果rIt(xt)0()0则获得标签yt。对所有i∈[K]∈[]计算ˆLt(hi,ri,zt)Lt(hi,ri,zt)Pt,i(IrIt(xt)⩽0Iri(xt)⩽0IrIt(xt)0)^(ℎ,,)(ℎ,,),(()⩽0()⩽0()0)其中Pt,i⎧⎪⎨⎪⎩1if ri(xt)⩽0∑i:ri(xt)0pt,iif ri(xt)0,{1if ()⩽0∑:()0,if ()0对所有i∈[K]∈[]做如下更新wt1,iwt,iexp(−ηˆLt(hi,ri,zt))1,,exp⁡(−^(ℎ,,))该算法满足下列bound定理 1设EXP3-ABS在K个专家上以学习率η运行于是该算法在T轮后满足下列regret保证RT(EXP3-ABS)⩽(logK)/ηηT(c21)/2(EXP3-ABS)⩽(log⁡)/(21)/2特别地如果EXP3-ABS以η√2logK(c21)T2log⁡(21)运行则有RT(EXP3-ABS)⩽√2(c21)TlogK(EXP3-ABS)⩽2(21)log⁡。这个界对专家个数K的依赖相比标准的EXP3更有优势为√logKlog⁡而不是√K。可以由此联系到使用上下文bandit算法contextual bandit algorithm EXP4达到的界。接下来考虑不可数无限的专家的情况。为了建模这个更一般的框架读者可能想要尝试关注函数hℎ和r的参数化类也即下列线性函数的类E:{(h,r):h(x)w⊤x,r(x)|w⊤x|−θ,w∈Rd,θ0}{(ℎ,):ℎ()⊤,()|⊤|−,∈,0}并引入一些前文提到的弃权损失L(h,r,z)(ℎ,,)的凸代理并在(w,θ)(,)的参数空间中运行在线凸优化算法[3]。不过论文作者认为这并不容易因为这里的代理损失不仅需要确保凸性以及某种形式的校准也需要确保算法能够观测其自身动作的的损失也即反馈图Gabstabs中的自环。论文作者没有通过仅仅求助于凸代理损失来解决这个问题。取而代之地论文作者引入了满足Lipschitz性质而非凸的代理弃权损失。设每轮迭代的专家(h,r)(ℎ,)从值域为E[−1,1]×[−1,1][−1,1]×[−1,1]的连续函数类中采样得到且假设函数hℎ和r关于某个Rd上的合适度量是LE-Lipschitz的这里常数LE决定了函数类E的大小。考虑l(y,h(x))fγ(−yh(x))(,ℎ())(−ℎ())的弃权损失L(h,r,z)(ℎ,,)L(h,r,z)fγ(−yh(x))Ir(x)0c(x)Ir(x)⩽0(ℎ,,)(−ℎ())()0()()⩽0其中fγ是一个做为0-1损失函数的变体的分段函数它在原点斜率为1/2γ1/2其定义如下fγ(a)(γa2γ)I|a|⩽γIa⩾0I|a|γ()(2)||⩽⩾0||其图像如下对于这种不可数无限的情况使用Cesa-Bianchi等人论文[5]的idea作者提出一个在使用弃权设置结构的同时通过有限覆盖来近似动作空间的算法其中用到了经典的“ϵ-网”[10][11]在假设原集合有界的情况下尝试用半径为ϵ的球去覆盖原集合。这里假设除了E之外输出空间X亦有界则存在常数CX00使得对所有0ϵ⩽10⩽1X都能被至多CXϵ−d−个半径为ϵ的球覆盖。类似地存在常数CE00使得对所有0ϵ⩽10⩽1E都能至多被CEϵ−2−2个半径为ϵ的球覆盖。记专家集合E关于常数Cϵ的覆盖为Cϵ。此外作者在保持反馈假设即反馈图Gabstabs不变的条件下定义了做为弃权损失上界的Lipschitz函数~L~。其中一个能够精确解决问题的Lipschitz函数如下~L(h,r,z)⎧⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎨⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎩cif r(x)⩽−γ1(1−cγ)r(x)if r(x)∈(−γ,0)1−(1−fγ(−yh(x))γ)r(x)if r(x)∈[0,γ)fγ(−yh(x))if r(x)⩾γ~(ℎ,,){if ()⩽−1(1−)()if ()∈(−,0)1−(1−(−ℎ()))()if ()∈[0,)(−ℎ())if ()⩾其中γ∈(0,1)∈(0,1)。~L(h,r,z)~(ℎ,,)的图像如下图所示该图的解释给定x和间隔a−yh(x)−ℎ()的值间隔确定后则函数值fγ(a)∈[0,1]()∈[0,1]亦确定描绘目标弃权损失函数L(a,r)(,)蓝色虚线和代理弃权损失函数~L(a,r)~(,)红色实线随rr(x)∈[−1,1]()∈[−1,1]的变化。注意该函数满足反馈假设的要求若rIt(x)⩽0()⩽0则对使得r(xt)⩽0()⩽0的(h,r)∈E(ℎ,)∈算法可以得知~L((h(xt),r(xt)),zt)~((ℎ(),()),)的值独立于yt若rIt(x)0()0则由于yt被观测到算法可以得到~L((h(xt),r(xt)),zt)~((ℎ(),()),)关于所有(h,r)∈E(ℎ,)∈的完全知识。论文作者设计了EXP3-ABS的上下文版本以应用于代理损失序列~L(ξ,zt),t∈[T]~(,),∈[]。该算法用固定半径ϵ的球来自适应地覆盖X每个球对应一个可以运行EXP3-ABS算法的实例。论文作者称这个算法为CONTEXP3-ABS。CONTEXP3-ABS的大致流程如下对每一轮迭代t∈[T]∈[]:接收xt如果xt不属于任何已存在的球则创建以xt为中心的半径为ϵ的新球并分配一个EXP3-ABS的新实例找到离xt最近的现有球中心xs将该球所对应的实例记为“Active EXP3-ABS”使用“Active EXP3-ABS”采样专家(h,r)It∈Eϵ(ℎ,)∈获得关于(h,r)It(ℎ,)的损失反馈并用其来更新“Active EXP3-ABS”的状态。定理 2考虑弃权损失L(h,r,z)fγ(−yh(x))Ir(x)0cIr(x)⩽0(ℎ,,)(−ℎ())()0()⩽0并设(h∗,r∗)argmin(h,r)∈E∑Tt1L(h,r,zt)(ℎ∗,∗)argmin(ℎ,)∈∑1(ℎ,,)其中E{(h,r)}{(ℎ,)}由之前提到过的满足Lipschitz性质的函数对组成。如果CONTEXP3-ABS以参数ϵ≃T−12dγ22d≃−1222和一个合适的学习率运行则它满足以下的regret保证RT(CONTEXP3-ABS)⩽˜O(Td1d2γ−dd2)M∗T(γ)(CONTEXP3-ABS)⩽~(12−2)∗()其中M∗T(γ)∗()是使得|r∗(xt)|⩽γ|∗()|⩽的xt的数量。在上面的叙述中˜O~隐藏了常量与ln(T)ln⁡()因子而≃≃则忽视了诸如LE的常量与各类log因子。3 仅当弃权时反馈可知也有论文假设当学习器选择弃权时反馈可知的比如《Online Selective Classification with Limited Feedback》[6]这篇文章。接下来假设不设置拒绝器而是将标签空间增广为Y∪{⊥}∪{⊥}。设HH为在增广标签空间上定义的预测器h(x):X→Y∪{⊥}h():→∪{⊥}组成的函数类。与之前提到的那篇论文类似该论文也讨论了对抗和随机两种设置。我们下面以随机设置为例进行介绍。专家 hh在有标签样本对z(x,y)∈X×{±1}(,)∈×{±1}上的弃权损失可以定义为L(h,x,y)Ctl(y,h(x))Ih(xt)≠⊥cIh(xt)⊥(h,,)(,h())h()≠⊥h()⊥在此基础上论文提出的Mixed-Loss-Prod算法大致流程如下对每一轮迭代t∈[T]∈[]:采样专家索引It∼ptwt,i∑wt,j,i∈[K]∼,∑,,∈[]采样伯努利变量 Ct∼Bern(p)∼Bern()如果Ct11则直接返回^yt⊥^⊥并获得标签yt反之返回^ythi(xt)∈Y∪{⊥}^h()∈∪{⊥}。对所有i∈[K]∈[], 计算Lt,i{l(yt,^yit)I^yit≠⊥cI^yit⊥if Ct1cI^yit⊥if Otherwise,{(,^)^≠⊥^⊥if 1^⊥if Otherwise对所有i∈[K]∈[], 做如下更新wt1,iwt,i(1−ηL(hi,zt))1,,(1−(h,))论文定义了以下两个指标做为算法性能的度量分别是学习器的犯错数和弃权次数MT:∑t⩽TI^y∉{⊥,yt},AT∑t⩽TI^yt⊥:∑⩽^∉{⊥,},∑⩽^⊥此外论文还定义了最佳事后分类器best-in-hindsight的概念也即需要在不犯错的情况下尽量少弃权f∗∈argminf∈F∑t⩽TI^yt⊥,s.t.∑t⩽TI^y∉{⊥,yt}0∗∈argmin∈∑⩽^⊥,s.t.∑⩽^∉{⊥,}0对于Mixed-Loss-Prod算法有如下定理成立定理 3若Mixed-Loss-Prod算法以η1/21/2λ⩽c⩽运行则满足E[MT]⩽2logKp2λpE[A∗T],E[AT−A∗T]⩽pT2logKλ[]⩽2log⁡2[∗],[−∗]⩽2log⁡4 无论弃权与否反馈都可知也有论文假设无论学习器是否弃权与否反馈都可知的。比如《Fast Rates for Online Prediction with Abstention》[9]这篇文章。现考虑预测器h(x):X→Yh():→组成的函数类。论文提出的算法大致流程如下对每一轮迭代t∈[T]∈[]:对所有专家i∈[K]∈[]计算预测标签^yt,ihi(xt)∈Y^,h()∈对所有专家的预测标签进行加权平均得到一个软概率pt∑i∈[K]wt,iyt,i∑j∈[K]wt,j∑∈[],,∑∈[],计算置信度参数p∗tmax{pt,1−pt}∗max{,1−}用于决定是否弃权设弃权概率αt2(1−p∗t)2(1−∗)^yt{⊥with probability αtIpt⩾12with probability 1−αt^{⊥with probability ⩾12with probability 1−对所有i∈[K]∈[], 计算Lt,il(yt,^yt,i),(,^,)对所有i∈[K]∈[], 做如下更新wt1,iwt,iexp(−ηLt,i)1,,exp⁡(−,)注意由于p∗t⩾12∗⩾12弃权概率α∈[0,1]∈[0,1]。为了从直觉上理解这个规则可以发现当分配给弃权操作一个数值⊥12⊥12时预测结果的期望E[pt]12αt(1−αt)Ipt⩾12(1−p∗t)(2p∗t−1)Ipt⩾12⎧⎪ ⎪⎨⎪ ⎪⎩(1−pt)(2pt−1)if pt⩾12ptif pt12pt[]12(1−)⩾12(1−∗)(2∗−1)⩾12{(1−)(2−1)if ⩾12if 12该算法对应的regret可定义如下RTE[T∑t1ˆLt−infi∈[K]T∑t1Lt,i][∑1^−inf∈[]∑1,]其中ˆLt{l(yt,^yt)if ^yt∈{0,1}cif ^yt⊥^{(,^)if ^∈{0,1}if ^⊥关于该算法的表现有下列结果定理 4假设c1212η⩽2(1−2c)⩽2(1−2)。则上述算法的regret满足RT⩽logKη⩽log⁡特别地该定理只要弃权损失c远离1/21/2我们都可以设置η2(1−2c)2(1−2)且算法可以达到独立于迭代轮数T的regret界。然而当c很接近1/21/2时可能会退回到regret保证为√TlogKlog⁡阶的标准最坏情形。在这种不利情形下这个阶可以通过选择一个保守的η值而轻易达到。下面这个关于定理4的推论总结了算法在不同情况下所能达到的率。推论 1设ηmax{2(1−2c),√8logKT}max{2(1−2),8log⁡}算法的regret满足RT⩽min{logK2(1−2c),√TlogK2}