《机器学习理论导引》笔记目录
0 感言
没什么太多感言了,拔刀吧!(orange 主题感觉非常鲜明,最近又把替代函数剩下部分补全了,学习笔记下也应该很快就能发布了)
6.1 基本概念
一些标记
X样本空间, X⊆RdY标签空间, Y={−1,+1}DX×Y 上的联合概率分布DXX 的边缘概率分布η(x)条件概率 P(y=+1∣x)h:X→Y分类器begin{aligned}
mathcal{X}qquad & text{样本空间, }mathcal{X}subseteqmathbb{R}^d\
mathcal{Y}qquad& text{标签空间, }mathcal{Y}={-1,+1}\
mathcal{D}qquad &mathcal{X}timesmathcal{Y} text{ 上的联合概率分布}\
mathcal{D}_{mathcal{X}}qquad &mathcal{X}text{ 的边缘概率分布}\
eta(boldsymbol{x})qquad & text{条件概率 }P(y=+1|boldsymbol{x})\
boldsymbol{h}:mathcal{X}rightarrowmathcal{Y}qquad & text{分类器}\
end{aligned}
泛化风险
- 泛化风险 : 分类器在分布 Dmathcal{D} 上的分类错误率
R(h)=P(x,y)∼D(h(x)≠y)=E(x,y)∼D[I(h(x)≠y)]=Ex∼Dx[η(x)I(h(x)≠+1)+(1−η(x))I(h(x)≠−1)]=Ex∼Dx[η(x)I(h(x)=−1)+(1−η(x))I(h(x)=+1)]begin{aligned}
R(h) & =P_{(x, y) sim mathcal{D}}(h(x) neq y)=E_{(x, y) sim mathcal{D}}[mathbb{I}(h(x) neq y)] \
& =E_{x sim D_x}[eta(x) mathbb{I}(h(x) neq+1)+(1-eta(x)) mathbb{I}(h(x) neq-1)] \
& =E_{x sim D_x}[eta(x) mathbb{I}(h(x)=-1)+(1-eta(x)) mathbb{I}(h(x)=+1)]
end{aligned}
Bayes 分类器
- 贝叶斯最优分类器 h∗boldsymbol{h}^* : 在分布 Dmathcal{D} 上取得最小错误率的分类器 (简称贝叶斯分类器)
h∗=argminhR(h)boldsymbol{h}^*=argmin_{h} R(h)
Bayes 风险
- 贝叶斯风险 R∗R^* : 贝叶斯分类器的泛化风险
R∗=R(h∗)=minh{R(h)}=Ex∼DX[minh(x){η(x)I(h(x)=−1)+(1−η(x))I(h(x)=+1)}]begin{aligned}
R^* & =Rleft(h^*right) \
& =min _h{R(h)} \
& =mathbb{E}_{boldsymbol{x} sim mathcal{D}_{mathcal{X}}}left[min _{h(boldsymbol{x})}{eta(boldsymbol{x}) mathbb{I}(h(boldsymbol{x})=-1)+(1-eta(boldsymbol{x})) mathbb{I}(h(boldsymbol{x})=+1)}right]
end{aligned}
- 若分布 Dmathcal{D} 已知 (即 η(x)eta(boldsymbol{x}) 已知),则可以直接根据分布给出贝叶斯分类器和贝叶斯风险:
η(x)⩾1−η(x)eta(boldsymbol{x})geqslant1-eta(boldsymbol{x}) | η(x)<1−η(x)eta(boldsymbol{x})<1-eta(boldsymbol{x}) | |
---|---|---|
η(x)eta(boldsymbol{x}) | ⩾12geqslantfrac{1}{2} | <12<frac{1}{2} |
h∗(x)h^*(boldsymbol{x}) | +1+1 | −1-1 |
R∗R^* | 1−η(x)1-eta(boldsymbol{x}) | η(x)eta(boldsymbol{x}) |
- 因此,
h∗(x)=2I(η(x⩾12))−1R∗=R(h∗)=Ex∼Dx[min{η(x),1−η(x)}]h^*(boldsymbol{x})=2mathbb{I}(eta(boldsymbol{x}geqslantfrac{1}{2}))-1\
R^*=R(h^*)=mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{x}}}[min{eta(boldsymbol{x}),1-eta(boldsymbol{x})}]
引理 6.1 (贝叶斯最优分类器 h∗boldsymbol{h}^* 和一般的分类器 hboldsymbol{h} 的关系)
∀h:X→Yforall h:mathcal{X}rightarrowmathcal{Y} 和贝叶斯最优分类器 h∗h^*,满足
R(h)−R∗=Ex∼DX[∣1−2η(x)∣I(h(x)≠h∗(x)]R(h)-R^*=mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}left[lvert1-2eta(x)rvertmathbb{I}(h(x)ne h^*(x)right]
证明
对任意样本 x∈Xxinmathcal{X},令
Δ(x)=η(x)I(h(x)=−1)+(1−η(x))I(h(x)=+1)−η(x)I(h∗(x)=−1)−(1−η(x))I(h∗(x)=+1)begin{aligned}
Delta(x)&=eta(x)mathbb{I}(h(x)=-1)+(1-eta(x))mathbb{I}(h(x)=+1)\
&-eta(x)mathbb{I}(h^*(x)=-1)-(1-eta(x))mathbb{I}(h^*(x)=+1)
end{aligned}
然后有
R(h)−R∗=Ex∼DX[η(x)I(h(x)=−1)+(1−η(x))I(h(x)=+1)]−Ex∼DX[η(x)I(h∗(x)=−1)+(1−η(x))I(h∗(x)=+1)]=Ex∼DX[Δ(x)]begin{aligned}
R(h)-R^* & =mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}left[eta(x)mathbb{I}(h(x)=-1)+(1-eta(x))mathbb{I}(h(x)=+1)right]\
&-mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}left[eta(x)mathbb{I}(h^*(x)=-1)+(1-eta(x))mathbb{I}(h^*(x)=+1)right]\
&=mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}left[Delta(x)right]
end{aligned}
- 若 η(x)>12eta(x)>frac{1}{2} 时,则 h∗(x)=+1h^*(x)=+1,于是当 h(x)=−1h(x)=-1 时,Δ(x)=2η(x)−1Delta(x)=2eta(x)-1,当 h(x)=+1h(x)=+1 时,Δ(x)=0Delta(x)=0,因此 Δ(x)=I(h(x)≠h∗(x))∣1−2η(x)∣Delta(x)=mathbb{I}(h(x)ne h^*(x))lvert1-2eta(x)rvert
- 同理可证当 η(x)⩽12eta(x)leqslantfrac{1}{2} 时成立,引理得证。
若数据分布 Dmathcal{D} 未知,常见的方法是通过训练集 Dmmathcal{D}_m 估计条件概率,然后构建分类器
h(x)=2I(η^(x)⩾12)−1h(x)=2mathbb{I}left(hat{eta}(x)geqslantfrac{1}{2}right)-1
这种基于条件概率估计的分类方法被称为插入 (plug-in) 法。
引理 6.2
对插入法的分类器 h(x)h(x) 有
R(h)−R∗⩽2Ex∼DX[∣η(x)−η^(x)∣]⩽2Ex∼DX[∣η(x)−η^(x)∣2]R(h)-R^*leqslant2mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}left[lverteta(x)-hat{eta}(x)rvertright]leqslant2sqrt{mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}left[lverteta(x)-hat{eta}(x)rvert^2right]}
证明
根据引理 6.1 可知 R(h)−R∗=Ex∼DX[∣1−2η(x)∣I(h(x)≠h∗(x)]R(h)-R^*=mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}left[lvert1-2eta(x)rvertmathbb{I}(h(x)ne h^*(x)right],根据 h∗(x)=2I(η(x)⩾12)−1h^*(x)=2mathbb{I}(eta(x)geqslantfrac{1}{2})-1 和 h(x)=2I(η^(x)⩾12)−1h(x)=2mathbb{I}(hat{eta}(x)geqslantfrac{1}{2})-1
当 I(h(x)≠h∗(x)mathbb{I}(h(x)ne h^*(x) 时有 I(η^(X)⩾12)≠I(η(x)⩾12)mathbb{I}(hat{eta}(X)geqslantfrac{1}{2})nemathbb{I}(eta(x)geqslantfrac{1}{2})
-
若 η^(x)⩾12hat{eta}(x)geqslantfrac{1}{2} 且 η(x)<12eta(x)<frac{1}{2},则 ∣1−2η(x)∣=2∣12−η(x)∣⩽2∣η^(x)−η(x)∣lvert1-2eta(x)rvert=2lvertfrac{1}{2}-eta(x)rvertleqslant2lverthat{eta}(x)-eta(x)rvert
-
若 η^(x)<12hat{eta}(x)<frac{1}{2} 且 η(x)⩾12eta(x)geqslantfrac{1}{2},则 ∣1−2η(x)∣=2∣12−η(x)∣⩽2∣η^(x)−η(x)∣lvert1-2eta(x)rvert=2lvertfrac{1}{2}-eta(x)rvertleqslant2lverthat{eta}(x)-eta(x)rvert
由此可得 R(h)−R∗⩽2Ex∼DX[∣η(x)−η^(x)∣]R(h)-R^*leqslant2mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}left[lverteta(x)-hat{eta}(x)rvertright],再利用 Jensen 不等式,可得 R(h)−Ex∼DX[∣η(x)−η^(x)∣]⩽Ex∼DX[∣η(x)−η^(x)∣2]R(h)-mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}left[lverteta(x)-hat{eta}(x)rvertright]leqslantsqrt{mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}left[lverteta(x)-hat{eta}(x)rvert^2right]},引理得证。
学习算法 Lmathfrak{L} 基于训练集 DmD_m 学习得到分类器 LDmmathfrak{L}_{D_m},随着训练集规模 mm 的增加,可以得到一系列分类器 LD1,LD2,…,LDm,…mathfrak{L}_{D_1},mathfrak{L}_{D_2},ldots,mathfrak{L}_{D_m},ldots
定义 6.1 一致性 (consistency)
当 m→∞mrightarrowinfty,若学习算法 Lmathfrak{L} 满足 EDm∼Dm[R(LDm)]→R(h∗)mathbb{E}_{D_msimmathcal{D}^m}left[R(mathfrak{L}_{D_m})right]rightarrow R(h^*),则称学习算法 Lmathfrak{L} 是一致的。
直观来说,一致性反映了在训练数据足够多的情形下,算法 Lmathfrak{L} 能否学习得到贝叶斯最优分类器;在理论上,一致性刻画了学习算法 Lmathfrak{L} 在无限多数据情形下学习的性能极限。
6.2 替代函数
对二分类问题,常见的方法是学习一个实值函数 f:X→Rf:mathcal{X}rightarrowmathbb{R},然后根据实值函数输出函数得到分类器
h(x)={+1f(x)⩾0−1f(x)<0h(x)=begin{cases}
+1 & f(x)geqslant0\
-1 & f(x)<0
end{cases}
实值函数 ff 在分布 Dmathcal{D} 上的泛化风险为
R(f)=E(x,y)∼D[I(yf(x))]=E(x,y)∼DX[η(x)I(f(x)⩽0)+(1−η(x))I(f(x)⩾0)]begin{aligned}
R(f)=&mathbb{E}_{(boldsymbol{x},boldsymbol{y})simmathcal{D}}left[mathbb{I}(boldsymbol{y}f(boldsymbol{x}))right]\
=&mathbb{E}_{(boldsymbol{x},boldsymbol{y})simmathcal{D}_{mathcal{X}}}left[eta(boldsymbol{x})mathbb{I}(f(boldsymbol{x})leqslant0)+(1-eta(boldsymbol{x}))mathbb{I}(f(boldsymbol{x})geqslant0)right]\
end{aligned}
考虑到 Bayes 风险和 Bayes 实值函数
R∗=R(h∗)=Ex∼DX[min{η(x),1−η(x)}]f∗∈F∗={f:当η(x)=12 时,f(x) 可以是任意的实数η(x)≠12 时,f(x)(η(x)−12>0)}R^*=R(h^*)=mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}[min{eta(boldsymbol{x}),1-eta(boldsymbol{x})}]\
begin{aligned}
f^*inmathcal{F}^*={f:text{当}& eta(x)=frac{1}{2}text{ 时,}f(x)text{ 可以是任意的实数}\
& eta(x)nefrac{1}{2}text{ 时,}f(x)left(eta(x)-frac{1}{2}>0right)}
end{aligned}
给定训练集 Dm={(x1,y1),(x2,y2),…,(xm,ym)}D_m={(x_1,y_1),(x_2,y_2),ldots,(x_m,y_m)} 和实值函数 ff,函数 ff 在训练集 DmD_m 上的分类错误率为
1m∑i=1mI(yif(xi)⩽0)frac{1}{m}sum_{i=1}^mmathbb{I}(y_if(x_i)leqslant0)
其本质上是泛化风险 R(f)R(f) 的一种无偏估计,I(yif(xi)⩽0)mathbb{I}(y_if(x_i)leqslant0) 是非凸不连续的,因此直接优化上式是 NP 难问题。因此在现实算法设计中可以对 I(yif(xi)⩽0)mathbb{I}(y_if(x_i)leqslant0) 进行凸放松,用一个具有良好数学性质的凸函数 ϕ:R↦Rphi:mathbb{R}mapstomathbb{R} 进行替代。考虑一般的替代函数
ℓ(f(x),y)=ϕ(yf(x))ell(f(boldsymbol{x}),boldsymbol{y})=phi(boldsymbol{y}f(boldsymbol{x}))
其中 ϕphi 是连续的凸函数或光滑的连续函数。替代函数本质上也是损失函数,这里使用 “替代” 主要针对 0/10/1 目标函数进行连续凸放松的替代。
机器学习中常用的替代函数
- 平方函数 ϕ(t)=(1−t)2phi(t)=(1-t)^2
- Hinge 函数 ϕ(t)=max(0,t−1)phi(t)=max(0,t-1)
- 指数函数 ϕ(t)=e−tphi(t)=e^{-t}
- 对率函数 ϕ(t)=ln(1+e−t)phi(t)=ln(1+e^{-t})
常见的替代函数如下图所示
替代泛化风险 (surrogate generalization risk)
- 替代泛化风险 : 给定替代函数 ϕphi,它在数据分布 Dmathcal{D} 上的泛化风险,定义为
Rϕ(f)=E(x,y)∼D[ϕ(yf(x))]R_{phi}(f)=mathbb{E}_{(boldsymbol{x},boldsymbol{y})simmathcal{D}}left[phi(boldsymbol{y}f(boldsymbol{x}))right]
- 最优替代泛化风险 :
Rϕ∗=min(Rϕ(f))R_{phi}^*=minleft(R_{phi}(f)right)
- 替代经验风险 (surrogate empirical risk),它是替代泛化风险 Rϕ(f)R_{phi}(f) 在训练集上的无偏估计
1m∑i=1mϕ(yif(xi))frac{1}{m}sum_{i=1}^mphi(y_if(x_i))
定义 6.2 替代函数一致性
随着训练数据规模 m→∞mrightarrowinfty,通过优化替代经验风险得到一系列输出函数 f^1,f^2,…,f^m,…hat{f}_1,hat{f}_2,ldots,hat{f}_m,ldots 若 Rϕ(f^m)→Rϕ∗R_{phi}(hat{f}_m)rightarrow R_{phi}^* 时有 R(f^m)→R∗R(hat{f}_m)rightarrow R^* 成立,则称替代函数 ϕphi 对原目标函数具有一致性,简称替代函数一致性
下面研究满足什么性质的替代函数,才具有对原 0/10/1 目标函数的一致性,根据替代泛化风险和最优替代泛化风险的定义,我们有
Rϕ(f)=Ex∼DX[η(x)ϕ(f(x))+(1−η(x))ϕ(−f(x))]Rϕ∗=Ex∼DX[minf(x)∈R(η(x)ϕ(f(x))+(1−η(x))ϕ(−f(x)))]begin{aligned}
R_{phi}(f)&=mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}left[eta(x)phi(f(x))+(1-eta(x))phi(-f(x))right]\
R_{phi}^*&=mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}left[min_{f(x)inmathbb{R}}left(eta(x)phi(f(x))+(1-eta(x))phi(-f(x))right)right]
end{aligned}
从而得到替代函数的最优实值输出函数 fϕ∗(x)f_{phi}^*(x) 为
fϕ∗(x)∈argminf(x)∈R(η(x)ϕ(f(x))+(1−η(x))ϕ(−f(x)))f_phi^*(boldsymbol{x}) in arg min _{f(boldsymbol{x}) in mathbb{R}}(eta(boldsymbol{x}) phi(f(boldsymbol{x}))+(1-eta(boldsymbol{x})) phi(-f(boldsymbol{x})))
定理 6.1 替代函数一致性的充分条件
对替代函数 ϕphi,若最优实值输出函数满足 fϕ∗∈F∗f_{phi}^*inmathcal{F}^*,且存在常数 c>0c>0 和 s⩾1sgeqslant1 使
∣η(x)−12∣S⩽cS(ϕ(0)−η(x)ϕ(fϕ∗(x))−(1−η(x))ϕ(−fϕ∗(x)))leftlverteta(x)-frac{1}{2}rightrvert^{mathcal{S}}leqslant c^{mathcal{S}}left(phi(0)-eta(x) phileft(f_phi^*(x)right)-(1-eta(x)) phileft(-f_phi^*(x)right)right)
证明
回顾一致性的定义,我们发现当 R(f^m)→R∗R(hat{f}_m)rightarrow R^* 与 Rϕ(f^m)→Rϕ∗R_{phi}(hat{f}_m)rightarrow R^*_{phi} 时,替代函数满足一致性要求。
故证明分为以下三点
- 计算 R(f^m)→R∗R(hat{f}_m)rightarrow R^*
- 计算 Rϕ(f^m)→Rϕ∗R_{phi}(hat{f}_m)rightarrow R^*_{phi}
- 将 R(f^m)→R∗R(hat{f}_m)rightarrow R^* 与 Rϕ(f^m)→Rϕ∗R_{phi}(hat{f}_m)rightarrow R^*_{phi} 相结合
下面沿着思路划分开始证明
1. 计算 R(f^m)→R∗R(hat{f}_m)rightarrow R^*
回顾
R(f)=E(x,y)∼DX[η(x)I(f(x)⩽0)+(1−η(x))I(f(x)⩾0)]R∗=Ex∼DX[min{η(x),1−η(x)}]R(f)
=mathbb{E}_{(boldsymbol{x},boldsymbol{y})simmathcal{D}_{mathcal{X}}}left[eta(boldsymbol{x})mathbb{I}(f(boldsymbol{x})leqslant0)+(1-eta(boldsymbol{x}))mathbb{I}(f(boldsymbol{x})geqslant0)right]\
R^*=mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}[min{eta(boldsymbol{x}),1-eta(boldsymbol{x})}]
所以
R(f)−R∗=E(x,y)∼DX[η(x)I(f(x)⩽0)+(1−η(x))I(f(x)⩾0)]−Ex∼DX[min{η(x),1−η(x)}]=Ex∼DX[Δ1(x)]begin{aligned}
R(f)-R^*&=mathbb{E}_{(boldsymbol{x},boldsymbol{y})simmathcal{D}_{mathcal{X}}}left[eta(boldsymbol{x})mathbb{I}(f(boldsymbol{x})leqslant0)+(1-eta(boldsymbol{x}))mathbb{I}(f(boldsymbol{x})geqslant0)right]\
&qquad-mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}[min{eta(boldsymbol{x}),1-eta(boldsymbol{x})}]\
&=mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}left[Delta_1(x)right]\
end{aligned}
其中
Δ1(x)=η(x)I(f(x)⩽0)+(1−η(x))I(f(x)⩾0)−min{η(x),1−η(x)}Delta_1(x)=eta(x)mathbb{I}(f(x)leqslant0)+(1-eta(x))mathbb{I}(f(x)geqslant0)-min{eta(x),1-eta(x)}
- 根据 η(x)−12eta(x)-frac{1}{2} 和 f(x)f(x) 的不同取值,分五种情况讨论 Δ1(x)Delta_1(x) :
- η(x)>12eta(x)>frac{1}{2}且 f(x)>0f(x)>0 时,有 Δ1(x)=0Delta_1(x)=0
- η(x)>12eta(x)>frac{1}{2}且 f(x)⩽0f(x)leqslant0 时,有 Δ1(x)=2η(x)−1Delta_1(x)=2eta(x)-1
- η(x)<12eta(x)<frac{1}{2}且 f(x)⩾0f(x)geqslant0 时,有 Δ1(x)=1−2η(x)Delta_1(x)=1-2eta(x)
- η(x)<12eta(x)<frac{1}{2}且 f(x)<0f(x)<0 时,有 Δ1(x)=0Delta_1(x)=0
- η(x)=12eta(x)=frac{1}{2},Δ1(x)=0Delta_1(x)=0
所以有
Δ1(x)=2I(η(x)−12)f(x)≤0)∣η(x)−12∣R(f)−R∗=2E(η(x)−12)f(x)≤0[∣η(x)−12∣]begin{aligned}
& left.Delta_1(boldsymbol{x})=2 mathbb{I}(eta(boldsymbol{x})-frac{1}{2}) f(boldsymbol{x}) leq 0right)|eta(boldsymbol{x})-frac{1}{2}| \
& R(f)-R^*=2 mathbb{E}_{(eta(boldsymbol{x})-frac{1}{2}) f(boldsymbol{x}) leq 0}[|eta(boldsymbol{x})-frac{1}{2}|]
end{aligned}
根据 Jensen 不等式 (E[X])⩽E[XS]S(mathbb{E}[X])leqslantsqrt[mathcal{S}]{mathbb{E}[X^{mathcal{S}}]},有
R(f)−R∗⩽2E(η(x)−12)f(x)≤0[∣η(x)−12∣S]SR(f)-R^*leqslant2sqrt[mathcal{S}]{mathbb{E}_{(eta(boldsymbol{x})-frac{1}{2}) f(boldsymbol{x}) leq 0}[|eta(boldsymbol{x})-frac{1}{2}|^{mathcal{S}}]}
定义
Δ2(x)=η(x)ϕ(f(x))+(1−η(x))ϕ(−f(x))Δ3(x)=η(x)ϕ(fϕ∗(x))+(1−η(x))ϕ(−fϕ∗(x))begin{gathered}
Delta_2(boldsymbol{x})=eta(boldsymbol{x}) phi(f(boldsymbol{x}))+(1-eta(boldsymbol{x})) phi(-f(boldsymbol{x})) \
Delta_3(boldsymbol{x})=eta(boldsymbol{x}) phileft(f_phi^*(boldsymbol{x})right)+(1-eta(boldsymbol{x})) phileft(-f_phi^*(boldsymbol{x})right)
end{gathered}
在充分条件下,
R(f)−R∗⩽2cE(η(x)−12)f(x)≤0[ϕ(0)−Δ3(x)]SR(f)-R^*leqslant2csqrt[mathcal{S}]{mathbb{E}_{(eta(boldsymbol{x})-frac{1}{2}) f(boldsymbol{x}) leq 0}[phi(0)-Delta_3(boldsymbol{x})]}
2. 计算 Rϕ(f^m)→Rϕ∗R_{phi}(hat{f}_m)rightarrow R^*_{phi}
回顾
Rϕ(f)=E(x,y)∼D[ϕ(yf(x)]=Ex∼DX[η(x)ϕ(f(x))+(1−η(x))ϕ(−f(x))]Rϕ∗=Ex∼DX[minf(x)∈R(η(x)ϕ(f(x))+(1−η(x))ϕ(−f(x)))]begin{aligned}
R_{phi}(f)&=mathbb{E}_{(boldsymbol{x},boldsymbol{y})simmathcal{D}}left[phi(yf(x)right]\
&=mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}left[eta(x)phi(f(x))+(1-eta(x))phi(-f(x))right]\
R_{phi}^*&=mathbb{E}_{boldsymbol{x}simmathcal{D}_{mathcal{X}}}left[min_{f(x)inmathbb{R}}left(eta(x)phi(f(x))+(1-eta(x))phi(-f(x))right)right]
end{aligned}
所以
Rϕ(f)−Rϕ∗=Ex∼DX[Δ2(x)−Δ3(x)]⩾E(η(x)−12)f(x)≤0[Δ2(x)−Δ3(x)]begin{aligned}
R_{phi}(f)-R_{phi}^*&=mathbb{E}_{xsimmathcal{D}_{mathcal{X}}}[Delta_2(x)-Delta_3(x)]\
&geqslantmathbb{E}_{(eta(boldsymbol{x})-frac{1}{2}) f(boldsymbol{x}) leq 0}[Delta_2(x)-Delta_3(x)]
end{aligned}
这里 Δ3(x)Delta_3(x) 正好包含在充分条件中。
3. 将 R(f^m)→R∗R(hat{f}_m)rightarrow R^* 与 Rϕ(f^m)→Rϕ∗R_{phi}(hat{f}_m)rightarrow R^*_{phi} 相结合
R(f)−R∗⩽2cE(η(x)−0.5)f(x)≤0[ϕ(0)−Δ3(x)]S⋯⩽2cE(η(x)−0.5)f(x)≤0[Δ2(x)−Δ3(x)]S⩽2cSRϕ(f)−Rϕ∗Sbegin{aligned}
R(f)-R^* leqslant & 2 c sqrt[mathcal{S}]{mathbb{E}_{(eta(boldsymbol{x})-0.5) f(boldsymbol{x}) leq 0}left[phi(0)-Delta_3(boldsymbol{x})right]} \
& cdots \
leqslant & 2 c sqrt[mathcal{S}]{mathbb{E}_{(eta(boldsymbol{x})-0.5) f(boldsymbol{x}) leq 0}left[Delta_2(boldsymbol{x})-Delta_3(boldsymbol{x})right]} \
leqslant & 2 c^mathcal{S} sqrt[mathcal{S}]{R_phi(f)-R_phi^*}
end{aligned}
下面即证明 ϕ(0)⩽Δ2(x)phi(0)leqslantDelta_2(x),令 Γ(t)=η(x)ϕ(t)+(1−η(x))ϕ(−t)Gamma(t)=eta(boldsymbol{x}) phi(t)+(1-eta(boldsymbol{x})) phi(-t) 现在 Γ(f(x))=Δ2(x)Gamma(f(x))=Delta_2(x) 和 Γ(0)=ϕ(0)Gamma(0)=phi(0),根据凸函数的性质可知,当 ϕ(t)phi(t) 是凸函数时 Γ(t)Gamma(t) 也是凸函数,以及当 0∈[a,b]0in[a,b] 时有 Γ(0)⩽max{Γ(a),Γ(b)}Gamma(0)leqslantmax{Gamma(a),Gamma(b)}。下面分三种情况讨论 :
-
若 η(x)>12eta(x)>frac{1}{2},则 fϕ∗(x)>0f^*_{phi}(x)>0,由 (η(x)−12)f(x)⩽0left(eta(x)-frac{1}{2}right)f(x)leqslant0 可知 f(x)⩽0f(x)leqslant0,故 ϕ(0)=Γ(0)⩽max{Γ(f(x)),Γ(fϕ∗(x))}phi(0)=Gamma(0)leqslantmax{Gamma(f(x)),Gamma(f_{phi}^∗(x))},又因为 Γ(f(x))⩾Γ(fϕ∗(x))Gamma(f(x))geqslantGamma(f_{phi}^∗(x)),于是 ϕ0⩽Γ(f(x))=Δ2(x)phi_0leqslantGamma(f(x))=Delta_2(x)
-
若 η(x)<12eta(x)<frac{1}{2},同理有 fϕ∗(x)<0,f(x)⩾0f^*_{phi}(x)<0,f(x)geqslant0,以 ϕ(0)=Γ(0)⩽max{Γ(f(x)),Γ(fϕ∗(x))}=Γ(f(x))=Δ2(x)phi(0)=Gamma(0)leqslantmax{Gamma(f(x)),Gamma(f_{phi}^∗(x))}=Gamma(f(x))=Delta_2(x)
-
若 η(x)=12eta(x)=frac{1}{2},对凸函数 ϕphi 有 ϕ(0)⩽ϕ(f(x))2+ϕ(−f(x))2=Δ2(x)phi(0)leqslantfrac{phi(f(x))}{2}+frac{phi(-f(x))}{2}=Delta_2(x)
证毕。
支持向量机 (support vector machine, SVM)
支持向量机 (support vector machine, SVM) 的替代函数是 hinge 函数
ϕ(t)=max(0,t−1)phi(t)=max(0,t-1)
在这个实例中,我们希望证明 hinge 函数的一致性。
引理 6.3
优化 hinge 函数 ϕ(t)=max(0,1−t)phi(t)=max(0,1-t) 得到输出函数
fϕ∗(x)={sign(2η(x)−1)η(x)≠1/2∀c∈[−1,1]η(x)=1/2f_phi^*(x)= begin{cases}operatorname{sign}(2 eta(x)-1) & eta(x) neq 1 / 2 \ forall c in[-1,1] & eta(x)=1 / 2end{cases}
是最优实值输出函数,其对应的最优替代泛化风险为 Rϕ∗=2Ex∼DX[min(η(x),1−η(x))]R_{phi}^*=2mathbb{E}_{x sim mathcal{D}_{mathcal{X}}}[minleft(eta(x),1-eta(x)right)]。
证明
将 hinge 函数 ϕ(t)=max(0,1−t)phi(t)=max(0,1-t) ,代入可得
Rϕ(f)=E(x,y)∼D[ϕ(yf(x))]=Ex∼DX[η(x)ϕ(f(x))+(1−η(x))ϕ(−f(x))]=Ex∼DX[η(x)max(0,1−f(x))+(1−η(x))max(0,1+f(x))]begin{aligned}
R_phi(f) & =mathbb{E}_{(boldsymbol{x}, y) sim mathcal{D}}[phi(y f(boldsymbol{x}))] \
& =mathbb{E}_{boldsymbol{x} sim mathcal{D}_{mathcal{X}}}[eta(boldsymbol{x}) phi(f(boldsymbol{x}))+(1-eta(boldsymbol{x})) phi(-f(boldsymbol{x}))] \
& =mathbb{E}_{boldsymbol{x} sim mathcal{D}_{mathcal{X}}}[eta(boldsymbol{x}) max (0,1-f(boldsymbol{x}))+(1-eta(boldsymbol{x})) max (0,1+f(boldsymbol{x}))]
end{aligned}
令 α=f(x)alpha=f(boldsymbol{x}),则有
fϕ∗(x)∈argminα∈R(η(x)max(0,1−α)+(1−η(x))max(0,1+α))=argminα∈Rg(α)g(α)={η(x)(1−α)α⩽11+α(1−2η(x))α∈[−1,+1](1−η(x))(1+α)α⩾1f_phi^*(boldsymbol{x}) in arg min _{alpha in mathbb{R}}(eta(boldsymbol{x}) max (0,1-alpha)+(1-eta(boldsymbol{x})) max (0,1+alpha))\=arg min _{alpha in mathbb{R}} g(alpha)\
g(alpha)=begin{cases}
eta(boldsymbol{x})(1-alpha)&alphaleqslant1\
1+alpha(1-2eta(boldsymbol{x}))&alphain[-1,+1]\
(1-eta(boldsymbol{x}))(1+alpha)&alphageqslant1
end{cases}
根据 fϕ∗(x)=arg minα∈Rg(α)f_{phi}^*(x)=argmin_{alphainmathbb{R}}g(alpha)
fϕ∗(x)={1η(x)>12∀c∈[−1,1]η(x)=12−1η(x)<12f_{phi}^*(x)=begin{cases}
1&eta(x)>frac{1}{2}\
forall cin[-1,1]&eta(x)=frac{1}{2}\
-1&eta(x)<frac{1}{2}\
end{cases}
将函数 fϕ∗(x)f_{phi}^*(x) 代入替代泛化风险可得
Rϕ∗=Rϕ(fϕ∗(x))=2Ex∼DX[min(η(x),1−η(x))]R_{phi}^*=R_{phi}left(f_{phi}^*(x)right)=2mathbb{E}_{x sim mathcal{D}_{mathcal{X}}}[minleft(eta(x),1-eta(x)right)]
引理得证
定理 6.2
hinge 函数 ϕ(t)=max(0,1−t)phi(t)=max(0,1-t) 针对原 0/10/1 目标函数具有替代一致性。
证明
根据引理 6.3 可知优化 hinge 函数 ϕ(t)=max(0,1−t)phi(t)= max(0,1-t) 所得的最优实值输出函数 fϕ∗(x)={sign(2η(x)−1)η(x)≠1/2∀c∈[−1,1]η(x)=1/2f_phi^*(x)= begin{cases}operatorname{sign}(2 eta(x)-1) & eta(x) neq 1 / 2 \ forall c in[-1,1] & eta(x)=1 / 2end{cases},显然 fϕ∗(x)∈F∗f_phi^*(x)inmathcal{F}^*。
给定样本 x∈Xxinmathcal{X},我们有
- 当 η(x)>12eta(x)>frac{1}{2} 时,fϕ∗(x)=1f_phi^*(x)=1,ϕ(0)−η(x)ϕ(fϕ∗(x))−(1−η(x))ϕ(−fϕ∗(x))=2∣η(x)−12∣phi(0)-eta(x)phileft(f_phi^*(x)right)-(1-eta(x))phileft(-f_phi^*(x)right)=2leftlverteta(x)-frac{1}{2}rightrvert
- 当 η(x)<12eta(x)<frac{1}{2} 时,fϕ∗(x)=−1f_phi^*(x)=-1,ϕ(0)−η(x)ϕ(fϕ∗(x))−(1−η(x))ϕ(−fϕ∗(x))=2∣η(x)−12∣phi(0)-eta(x)phileft(f_phi^*(x)right)-(1-eta(x))phileft(-f_phi^*(x)right)=2leftlverteta(x)-frac{1}{2}rightrvert
- 当 η(x)=12eta(x)=frac{1}{2} 时,fϕ∗(x)∈[−1,+1]f_phi^*(x)in[-1,+1],ϕ(0)−η(x)ϕ(fϕ∗(x))−(1−η(x))ϕ(−fϕ∗(x))=2∣η(x)−12∣phi(0)-eta(x)phileft(f_phi^*(x)right)-(1-eta(x))phileft(-f_phi^*(x)right)=2leftlverteta(x)-frac{1}{2}rightrvert
取 c=12,s=1c=frac{1}{2},s=1,由定理 6.1 可知 hinge 函数针对原 0/10/1 函数具有替代一致性,定理得证。
支持向量机常用的另一种替代函数是平方 hinge 函数:
ϕ(t)=(max(0,1−t))2phi(t)=(max(0,1-t))^2
定理 6.3
证明平方 hinge 函数的一致性。
证明
当 fϕ∗∈F∗f^*_{phi}inmathcal{F}^* 且 ∃ c>0,s⩾1exists c>0,sgeqslant1 使得
∣η(x)−12∣s≤cs[ϕ(0)−η(x)ϕ(fϕ∗(x))−(1−η(x))ϕ(−fϕ∗(x))]left|eta(boldsymbol{x})-frac{1}{2}right|^s leq c^sleft[phi(0)-eta(boldsymbol{x}) phileft(f_phi^*(boldsymbol{x})right)-(1-eta(boldsymbol{x})) phileft(-f_phi^*(boldsymbol{x})right)right]
则替代函数 ϕphi 是一致的。我们同时有 fϕ∗(x)=2η(x)−1,ϕ(fϕ∗(x))=(1−fϕ∗(x))2f^*_{phi}(x)=2eta(x)-1,phi(f^*_{phi}(x))=(1-f^*_{phi}(x))^2,将 fϕ∗(x)f^*_{phi}(x) 代入可得
[ϕ(0)−η(x)ϕ(fϕ∗(x))−(1−η(x))ϕ(−fϕ∗(x))]=1−4η(x)(1−η(x))=4∣η(x)−12∣2left[phi(0)-eta(boldsymbol{x}) phileft(f_phi^*(boldsymbol{x})right)-(1-eta(boldsymbol{x})) phileft(-f_phi^*(boldsymbol{x})right)right]\
=1-4eta(boldsymbol{x})(1-eta(boldsymbol{x}))=4leftlverteta(boldsymbol{x})-frac{1}{2}rightrvert^2
让 c=12,s=2c=frac{1}{2},s=2,即可得证