上个月参加担任了在宇治举办的京阿尼同人展的工作人员感受到了来场粉丝们的热情也在会场播放的京吹、《声之形》、《平家物语》等动画作品中BGM中回味了曾经看这些动画时的感受。期间还遇到了B站的up主“京阿尼信使”san并现场当了一波翻译主办方还感谢了我能同时提供英语和中文支持哈哈因为来场的粉丝中也有外国人。顺带一提我这个月初才去考了日语N1也算是检验下自己的日语能力了。下面是收到的主办方赠送的礼物科研方面我近期在进行读博第二份工作的证明工作。这篇博客旨在以论文《Exploiting the surrogate gap in online multiclass classification》[1]为主要参考介绍凸代理技术是如何运用于在线学习的代理regret界证明中的整体而言偏向公式细节推导。1 导引凸代理可以为在线学习中regret界的证明提供有力的支持。不仅仅是由于引入了凸代理后可以直接应用在线梯度下降online gradient descent, OGD[2]等在线凸优化算法在凸假设下获得至少为O(√T)的regret界保障而且若能充分利用代理损失函数的特性[1]比如强凸、对数凹exp-concavity[3]、混合能力mixability[4]则可进一步获得诸如O(lnT)的更好的regret界保证。论文《Exploiting the surrogate gap in online multiclass classification》[1][5]就较好地展现了凸代理在在线学习的代理regret界证明中的应用。论文作者证明在充分利用代理损失函数与目标函数间的差距的情况下在完全信息full information的设置下甚至可以达到常数阶的代理regret界。2 利用代理与目标函数间的差距考虑在线多分类场景该场景可能是完全信息full information 的或bandit的完全信息和bandit场景的区别可参见我之前的博客《学习理论在线弃权学习》[6]。设学习过程包括T轮迭代每轮迭代t时环境会暴露特征向量xt∈Rd给学习器假设其对所有T都满足有界条件∥xt∥⩽X。学习器基于xt返回一个随机化的预测值y′t∈Y{1,⋯,K}。在完全信息设置下在学习器做出预测后环境会暴露真实标签yt∈Y{1,⋯,K}给学习器而在bandit设置下环境只会返回学习器是否预测正确也即I[y′t≠yt]。该论文只考虑对抗设置也即意味着不对yt或xt如何生成的做出假设。在完全信息和bandit两种设置中论文都允许学习器使用随机化预测。对于bandit设置而言由于只有当预测正确即y′tyt时才能够获得yt的确切值以对参数进行更新使用随机化预测可以达到 探索exploration 的作用[5][7]。这两种设置下的目标都是去控制学习器在T轮迭代中的期望错误数MTE[T∑t1I[y′t≠yt]]其中期望部分随机性的来源是关于学习器的随机性。而对于这两种设置而言标准实践都是用一个凸代理损失函数ℓt去做为非凸的0-1损失的上界。设这里的凸代理损失ℓt是关于K×d的权重矩阵Wt∈W的线性函数其中W{W:∥W∥⩽D}。其中∥W∥表示矩阵的Frobenius范数。则在T轮迭代后的代理regret可以表示为RTE[T∑t1I[y′t≠yt]−T∑t1ℓt(U)]其中I是示性函数K×d的矩阵U是最佳离线线性预测器。为了优化该代理regret可以将其做进一步分解E[T∑t1I[y′t≠yt]]−E[T∑t1ℓt(U)]E⎡⎢⎢⎢⎢⎢⎣T∑t1I[y′t≠yt]−ℓt(Wt)⩽0T∑t1ℓt(Wt)−ℓt(U)⎤⎥⎥⎥⎥⎥⎦其中ℓt(Wt)是I[y′t≠yt]的凸上界可知项∑Tt1I[y′t≠yt]−ℓt(Wt)⩽0。一种直截的处理方式是直接将这一项放缩掉即得到RT⩽T∑t1ℓt(Wt)−ℓt(U)然后在使用OGD算法的条件下采用标准的在线凸优化证明技术[1][8]得到T∑t1ℓt(Wt)−ℓt(U)⩽∥U∥22ηT∑t1η2∥gt∥2这里η是学习率。假设ft对所有t是ϕ-Liptchitz的意味着梯度满足有界条件∥gt∥⩽ρ并假设W是D-有界的取ηDρ√T可以进一步得到T∑t1ℓt(Wt)−ℓt(U)⩽Dρ√T这是一个O(√T)的界。观察可知这里的√T项主要来自于随着T的增长项∑Tt1η2∥gt∥2而另一项∥U∥22η本身是不随着迭代步数T增长的常数项。根据论文《Exploiting the surrogate gap in online multiclass classification》[1][5]作者的发现代理regret分解产生的∑Tt1I[y′t≠yt]−ℓt(Wt)这一项有充分的利用价值而在某些情况下不应该直接被放缩掉。相反在某些情况下这一项将会负得足够多甚至甚至可以将增长项∑Tt1η2∥gt∥2给抵消掉。若保留这一项则可得到如下所示的代理regret界RTE⎡⎢⎢⎢⎢⎢⎣T∑t1I[y′t≠yt]−ℓt(Wt)T∑t1ℓt(Wt)−ℓt(U)bounded via OGD⎤⎥⎥⎥⎥⎥⎦⩽∥U∥22ηE[T∑t1I[y′t≠yt]−ℓt(Wt)η2∥gt∥2]M其中记项∑Tt1I[y′t≠yt]−ℓt(Wt)∑Tt1η2∥gt∥2为M。若能证明M在特定设置下比如完全信息的设置下⩽0则可达成常数阶的代理regret界。由于论文利用∑Tt1I[y′t≠yt]−ℓt(Wt)这一差距gap的特点本文作者将该方法称为GAPTRON。3 验证代理差距是否可⩽0接下来介绍如何去界定ME[T∑t1I[y′t≠yt]−ℓt(Wt)∥gt∥2]我们先来看论文算法每轮迭代预测的标签值y′t是如何产生的。如果考虑完全信息的设置且不引入随机性的话那么一个合理的选择是使得模型输出score最大的标签y∗targmaxk⟨Wkt,xt⟩但论文的方法不只考虑了完全信息的设置还考虑了bandit的设置。本文的算法在每一轮的预测中引入了随机性而这可以在bandit设置中达到探索的作用。具体而言算法的每一轮得到的标签预测值y′t根据一个概率分布向量p′t采样产生y′t∼p′t而概率分布向量p′t经由一个单位向量ey∗t表示预测分布y∗t索引元素为1而其余为0和一个全1向量表示随机分布的插值产生p′t(1−max{a(Wt,xt),γ})ey∗tmax{a(Wt,xt),γ}1K1其中插值权重max{a(Wt,xt),γ}经由差距映射gap mapa:RK×d×Rd→[0,1]的计算产生根据选用的代理损失函数不同该映射函数也可能不同。参数γ∈[0,1]。在完全信息设置下γ被设置为0但在bandit设置下γ被用于保证每个标签被以至少γK的概率采到这是一个在bandit算法中的常见策略[9]。在这里每个标签被以至少γK的概率采到是重要的因为在bandit设置下论文使用重要性加权importance weighting策略来得到代理损失ℓt的估计形式以及其对应的梯度gt∇ℓt(Wt)因此需要控制这些估计的方差。在完全信息的设置下设a(Wt,xt)0,γ0并将ℓt选择为hinge损失则将得到与经典的感知机perception[10] 算法相似的形式而此算法可以被解释为在hinge损失上的OGD。简记ata(Wt,xt)。这里at的作用为利用代理损失和0-1损失之间的差距这个我们在后面介绍其具体形式的时候会进一步阐述。让我们回到之前所提到的M的具体形式可以继续用at和γ将其展开表示ME[T∑t1I[y′t≠yt]−ℓt(Wt)η2∥gt∥2]E[T∑t1Et[I[y′t≠yt]]−ℓt(Wt)η2∥gt∥2](Et[⋅]表示给定t时给定(y′i)i⩽t−1的条件期望)E[T∑t1(1−max{at,γ})I[y∗t≠yt]max{at,γ}K−1K−ℓt(Wt)η2∥gt∥2]γK−1KTT∑t1E[(1−at)I[y∗t≠yt]atK−1K−ℓt(Wt)η2∥gt∥2]surrogate gap其中最后一个不等式使用了(1−max{at,γ})⩽(1−at)与max{at,γ}atγ。括号括起来的项称为代理差距surrogate gap。在完全信息的设置下设γ0则此时若能证明代理差距在可以调节差距映射at的情况下能被0界定则就能证明常数的代理regret界。下图形象地展示了在K2,γ0η18的设置下通过条件at使得代理差距⩽0的效果设图中绿色的实线表示关于间隔z的光滑hinge损失ℓt(Wt)max{(1−z)2,0}这里z为间隔黑色实线表示关于间隔z的0-1损失I[z⩽0]。首先可以看到光滑hinge损失做为0-1损失的上界是可以将其界定的。然后我们进一步分析其它部分红色实线表示a(W,x)0时0-1损失加上了梯度项的I[z⩽0]η2∥gt∥2其中设当z0时∥gt∥24(1−z)2否则∥gt∥24。可以看到红色实线有部分是在黄线上方的这也就意味着I[z⩽0]η2∥gt∥2减去光滑hinge损失ℓt(Wt)并不一定⩽0也就意味着光滑hinge损失并不能完全将其抵消掉。此时的代理差距体现为图中的红色实线值减去绿色实线值并不一定⩽0。蓝色实线表示a(W,x)(1−|z|)2时的(1−(1−|z|)2)I[z⩽0]12(1−|z|)2η2∥gt∥2可以看到蓝色实线不会到黄线上方去这也就意味着此时光滑hinge损失可以完全将其抵消掉。此时的代理差距体现为图中的蓝色实线值减去绿色实线值满足⩽0。我们还可以发现当a(W,x)0减小学习率η会扩大代理差距被0所界定的范围但只有当η0时代理差距才会处处被0所界定。但如果a(W,x)(1−|z|)2则代理差距对所有z都可以被0所界定了。而对于完全信息的情况这将导致常数阶的代理regret界。4 采用不同代理损失时的代理差距下面以完全信息的设置为例分别在logistic损失和hinge损失的情况下去证明代理差距可以被0界定并给出相应的差距映射at。由于是完全信息在本部分设置γ0。我们先来看logistic损失。4.1 logistic损失logistic损失可定义如下ℓt(W)−log2(σ(W,xt,yt))其中σ(W,x,k)exp(⟨wk,x⟩)∑Kk′1exp(⟨wk′,x⟩)是softmax函数wk为W第k行的向量。注意这里logistic函数是以2为底的我的推测是这是应后面关于代理差距的证明的需要而设置的。对于logistic损失论文使用下列的差距映射a(Wt,xt)1−I[p∗t⩾0.5]p∗t其中p∗tmaxkσ(Wt,xt,k)。这意味着GAPTRON会在p∗t⩽0.5时均匀随机采样一个标签。下列事实在初看时可能是反直觉的当p∗t0.5时不管学习器预测标签是什么0-1损失都能够被logistic损失给界定这是由于当p∈[0,0.5]时−log2(p)⩾1。而这一事实可以被用来证明当p∗t0.5代理差距可以被0界定。下面我们展示在采用logistic损失并设a(Wt,xt)1−I[p∗t⩾0.5]p∗tηln(2)2KX2的情况下代理差距surrogate gapE[(1−at)I[y∗t≠yt]atK−1K−ℓt(Wt)η2∥gt∥2]可以被0界定。我们先求ℓt(Wt)关于Wt的梯度∇Wtℓt(Wt)。由于函数关于矩阵求导等价于关于矩阵的每一个元素求导[11]因此∇Wtℓt(Wt)也是一个和Wt行数和列数相同的K×d矩阵其每个元素为[∇Wtℓt(Wt)]ij∂ℓt(Wt)∂wij。当然逐元素求导可能过于繁杂我们这里将∇Wtℓt(Wt)视为行向量拼成的矩阵其中每个行向量是梯度向量∇wtℓt(Wt)∇Wtℓt(Wt)⎛⎜⎜⎜⎜⎝∇w1ℓt(Wt)∇w2ℓt(Wt)⋮∇wKℓt(Wt)⎞⎟⎟⎟⎟⎠于是我们接着表示∇wkℓt(Wt)∇wkℓt(Wt)∇wk(−log2(σ(Wt,xt,yt)))1ln2∇wk(log(K∑k′1exp(⟨wt,k′,xt⟩))−⟨wt,yt,xt⟩)1ln2(exp(⟨wt,k,xt⟩)xt∑Kk′1exp(⟨wt,k′,xt⟩)−I[ytk]xt)1ln2(σ(Wt,xt,k)−I[ytk])xt因此有∇Wtℓt(Wt)1ln2(~pt−eyt)⊗xt其中~pt(~pt(1),⋯,~pt(k))⊤~pt(k)σ(Wt,xt,k)。式中的⊗为矩阵的Kronecker积[12]这里可以理解为将向量xt乘以~pt−eyt的每一个标量元素然后将所得的结果拼成一个新矩阵。接着我们证明ℓt(W)满足一个重要的性质它是 自界self-bounded[8]的也即意味着该函数的梯度的范数平方可以被函数自身乘一个常数给界定∥∇Wtℓt(Wt)∥2⩽2ln2X2ℓt(Wt)证明如下∥∇Wtℓt(Wt)∥21(ln2)2∥xt∥2(K∑k1(I[ytk]−~pt(k))2)⩽1(ln2)2∥xt∥2(K∑k1|I[ytk]−~pt(k)|)2(a21⋯a2n⩽(|a1|⋯|an|)2)⩽−2ln2∥xt∥2log2(~pt(yt))(Pinsker不等式[13])⩽−2ln2X2log2(~pt(yt))(∥xt∥2⩽X)2ln2X2ℓt(Wt)Pinsker不等式[13]对任意两个在样本空间H上定义的概率分布P1和P2设D(P1∥P2)为它们之间的KL散度∥P1−P2∥1∑a∈H|P1(a)−P2(a)|为它们之间的L1距离则有下列不等式成立D(P1∥P2)⩾12ln2∥P1−P2∥21在上述的证明中将单位向量eyt所对应的分布概率在yt处为1其余处为0做为P1将~pt所对应的分布做为P2即可。有了这个性质可以进一步将代理差距界定如下这里注意ata(Wt,xt)1−I[p∗t⩾0.5]p∗t其中p∗tmaxkσ(Wt,xt,k)surrogate gapE[(1−at)I[y∗t≠yt]atK−1K−ℓt(Wt)η2∥gt∥2](1−at)I[y∗t≠yt]atK−1K−ℓt(Wt)η2∥gt∥2(完全信息设置下ℓt(Wt)和gt不涉及随机选择)⩽(1−at)I[y∗t≠yt]atK−1K−ℓt(Wt)ηln2X2ℓt(Wt)⎧⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎩0K−1Klog2(~pt(yt))−ηln2X2log2(~pt(yt))ifp∗t0.5p∗t(1−p∗t)K−1Klog2(~pt(yt))−ηln2X2log2(~pt(yt))ify∗t≠ytandp∗t⩾0.5(1−p∗t)K−1Klog2(p∗t)−ηln2X2log2(p∗t)ify∗tytandp∗t⩾0.5接着进行分类讨论。(1)p∗t0.5K−1Klog2(~pt(yt))−ηln2X2log2(~pt(yt))⩽−K−1Klog2(~pt(yt))log2(~pt(yt))−ηln2X2log2(~pt(yt))(1⩽−log2(x))1Klog2(~pt(yt))−ηln2X2log2(~pt(yt))⩽0(ηln(2)2KX2ln2KX2)(2)y∗t≠yt且p∗t⩾0.5p∗t(1−p∗t)K−1Klog2(~pt(yt))−ηln2X2log2(~pt(yt))⩽−12log2(1−p∗t)−K−12Klog2(1−p∗t)log2(~pt(yt))−ηln2X2log2(~pt(yt))(x⩽−12log2(1−x)forx∈[0.5,1],1−x⩽−12log2(1−x)forx∈[0.5,1])−12log2⎛⎝K∑k≠y∗t~pt(k)⎞⎠−K−12Klog2⎛⎝K∑k≠y∗t~pt(k)⎞⎠log2(~pt(yt))−ηln2X2log2(~pt(yt))⩽−12log2(~pt(yt))−K−12Klog2(~pt(yt))log2(~pt(yt))−ηln2X2log2(~pt(yt))12Klog2(~pt(yt))−ηln2X2log2(~pt(yt))0(ηln(2)2KX2)(3)y∗tyt且p∗t⩾0.5(1−p∗t)K−1Klog2(p∗t)−ηln2X2log2(p∗t)⩽−K−1Klog2(p∗t)log2(p∗t)−ηln2X2log2(p∗t)(1−x⩽−log2(x))⩽0(ηln(2)2KX2ln2KX2)因此在采用logistic损失并设a(Wt,xt)1−I[p∗t⩾0.5]p∗tηln(2)2KX2的情况下代理差距surrogate gap⩽0得证。于是有RT⩽∥U∥22ηγK−1KTT∑t1E[(1−at)I[y∗t≠yt]atK−1K−ℓt(Wt)η2∥gt∥2]surrogate gap⩽0⩽∥U∥22η(设置γ0)KX2∥U∥2ln2常数阶代理regret界得证。4.2 多类别hinge损失接着我们来看多类别hinge损失的情况。本文使用了Crammer-Singer多分类hinge损失[14]的变体其定义如下ℓt(W)⎧⎪⎨⎪⎩max{1−mt(W,yt),0}ifm∗t⩽βmax{1−mt(W,yt),0}ify∗t≠ytandm∗tβ0ify∗tytandm∗tβ