当前位置:首页> AI教程> 机器学习理论导引-笔记目录

机器学习理论导引-笔记目录

释放双眼,带上耳机,听听看~!
这是关于机器学习理论导引的笔记目录,涵盖了预备知识、可学性、复杂度、泛化界、稳定性、一致性、收敛率、遗憾界等内容。

《机器学习理论导引》笔记目录

4.3 分析实例

理论回顾

定理3.6

  Rdmathbb{R}^d 中由非齐次线性超平面构成的假设空间 Hmathcal{H} 的 VC维为 d+1

定理3.7

  若 ∥x∥≤rlVert xrVertle r,D 为大小为 m 的数据集,则超平面族 H={x↦wTx:∥w∥≤Λ}mathcal{H}={xmapsto mathbf{w}^Tmathbf{x}:lVert mathbf{w}rVertleLambda} 的经验 Rademacher复杂度满足

RD^(H)≤r2Λ2mhat{mathcal{R}_D}(mathcal{H})lesqrt{frac{r^2Lambda^2}{m}}

定理3.8

  若 ∥x∥≤rlVert mathbf{x}rVertle r,则超平面族 {x↦sign(wTx):min⁡x⁡∣wTx∣=1∧∥w∥≤Λ}{mathcal{x}mapstotext{sign}(mathbf{w}^Tmathbf{x}):min_mathbf{x}⁡|mathbf{w}^Tmathbf{x}|=1landlVert mathbf{w}rVertleLambda} 的 VC维 d满足

d≤r2Λ2dle r^2Lambda^2

定义 3.3

  函数空间 Fmathcal{F} 关于 𝑍 的经验 Rademacher 复杂度为

定义 3.4

  函数空间 Fmathcal{F} 关于 Zmathcal{Z} 在分布 m 上的 Rademacher 复杂度为

引理 (第一章中的 Hoeffding 不等式)

  若训练集 Dmathcal{D} 包含 m 个从分布 Dmathcal{D} 上独立同分布采样而得的样本,0<ϵ<10<epsilon<1,则对任意 h∈Hhinmathcal{H},有

P(E^(h)−E(h)≥ϵ)≤exp⁡(−2mϵ2)P(E^(h)−E(h)≤−ϵ)≤exp⁡(−2mϵ2)P(∣E^(h)−E(h)∣≥ϵ)≤2exp⁡(−2mϵ2)Pleft(hat{E}(h)-E(h)geepsilonright)leexp{(-2mepsilon^2)}\
Pleft(hat{E}(h)-E(h)le-epsilonright)leexp{(-2mepsilon^2)}\
Pleft(|hat{E}(h)-E(h)|geepsilonright)le2exp{(-2mepsilon^2)}

  学习方法的泛化能力分析往往是通过研究泛化误差的概率上界进行的,具体来说,就是通过比较两种学习方法的泛化误差上界的大小来比较它们的优劣。
  泛化误差上界是样本容量和空间容量的函数,样本容量越大,空间容量越小,泛化误差上界越小。

间隔损失函数

  引入间隔使得泛化误差界与数据分布相关。

定义 4.1

  对任意 ρ>0rho>0ρ−rho− 间隔损失为定义在 z,z′∈Rz,z’inmathbb{R} 上的损失函数 ℓρ:R×R↦R+,ℓρ(z,z′)=Φρ(zz′)ell_rho : mathbb{R} times mathbb{R} mapsto mathbb{R}_+, ell_rho (z, z’) = Phi_rho(zz’),其中

Φρ(x)={0ρ⩽x1−x/ρ0⩽x⩽ρ1x⩽0Phi_rho(x)=begin{cases}
0&rholeqslant x\
1-x/rho&0leqslant xleqslantrho\
1&xleqslant0
end{cases}

机器学习理论导引-笔记目录

  对于集合 D=x1,…,xmD = x_1,ldots, x_m 与假设 hh,经验间隔损失表示为

E^ρ(h)=1m∑i=1mΦρ(yih(xi))widehat{E}_rho(h)=frac{1}{m}sum_{i=1}^mPhi_rho(y_ih(x_i))

  又 Φρ(yih(xi))⩽Iyih(xi)⩽ρPhi_rho (y_ih(x_i)) leqslant mathbb{I}_{y_ih(x_i)leqslantrho},由拉格朗日定理可得

∣Φρ(x1)−Φρ(x2)∣⩽∣Φρ′(ξ)∣∣x1−x2∣lvertPhi_rho(x_1)-Phi_rho(x_2)rvertleqslantlvertPhi^{‘}_{rho}(xi)rvertlvert x_1-x_2rvert

  由间隔损失函数定义可得

∣Φρ′(ξ)∣⩽1ρlvertPhi^{‘}_{rho}(xi)rvertleqslantfrac{1}{rho}

  (补充:对于在实数集的子集的函数 f:D⊆R→Rf : Dsubseteq mathbb{R}rightarrowmathbb{R},若存在常数 KK,使得 ∣f(a)−f(b)∣⩽∣a−b∣,∀a,b∈D|f(a) − f(b)| leqslant |a − b|,forall a, bin D,则称 ff 符合 Lipschitz 条件,对于 ff 最小的常数 KK 称为 ff 的 Lipschitz 常数) 可知 ΦρPhi_{rho} 最多是 1ρfrac{1}{rho}-Lipschitz

Talagrand 收缩引理

引理 4.4 (Talagrand 收缩引理)

Φ:R↦RPhi : mathbb{R} mapsto mathbb{R}ℓρell_{rho}− Lipschitz 函数,则对于任意实值假设空间 Hmathcal{H} 有下式成立:

R^D(Φ∘H)⩽LR^D(H)widehat{mathfrak{R}}_D(Phi circ mathcal{H}) leqslant L hat{mathfrak{R}}_D(mathcal{H})

  说明 Lipschitz 函数与假设空间 Hmathcal{H} 复合后的经验 Rademacher 复杂度可以基于假设空间 Hmathcal{H} 的经验 Rademacher 复杂度表示

证明

  固定样本空间 D=(x1,…,xm)D = (x_1,ldots, x_m),根据定义

ℜS(Φ∘H)=1mE[sup⁡h∈H∑i=1mσi(Φ∘h)(xi)]=1mσσ1,…,σm−1E[Eσm[sup⁡h∈Hum−1(h)+σm(Φ∘h)(xm)]]begin{aligned}
Re_S(Phi circ H) & =frac{1}{m} mathrm{E}left[sup _{h in H} sum_{i=1}^m sigma_i(Phi circ h)left(x_iright)right] \
& =frac{1}{m} sigma_{sigma_1, ldots, sigma_{m-1}}^{mathrm{E}}left[underset{sigma_m}{mathrm{E}}left[sup _{h in H} u_{m-1}(h)+sigma_m(Phi circ h)left(x_mright)right]right]
end{aligned}

  um−1(h)=∑i=1m−1σi(Φ∘h)(xi)u_{m−1}(h) =sum^{m−1}_{i=1} sigma_i(Phicirc h)(x_i) 假设上确界能够达到,令 h1,h2∈Hh_1, h_2in H 满足

um−1(h1)+Φm(h1(xm))=sup⁡h∈Hum−1(h)+Φm(h(xm))um−1(h2)−Φm(h2(xm))=sup⁡h∈Hum−1(h)−Φm(h(xm))begin{aligned}
& u_{m-1}left(h_1right)+Phi_mleft(h_1left(x_mright)right)=sup _{h in H} u_{m-1}(h)+Phi_mleft(hleft(x_mright)right) \
& u_{m-1}left(h_2right)-Phi_mleft(h_2left(x_mright)right)=sup _{h in H} u_{m-1}(h)-Phi_mleft(hleft(x_mright)right)
end{aligned}

  如果上确界达不到,可以考虑接近 ϵepsilon 的上确界,可以得到类似下面的结论。因为 σmsigma_m{−1,+1}{−1, +1} 上的均匀分布,根据期望的定义有

E[sup⁡m∈Hum−1(h)+σm(Φ∘h)(xm)]]=12[um−1(h1)+(Φ∘h1)(xm)]+12[um−1(h2)−(Φ∘h2)(xm)]≤12[um−1(h1)+um−1(h2)+sL(h1(xm)−h2(xm))]=12[um−1(h1)+sLh1(xm)]+12[um−1(h2)−sLh2(xm)]≤12sup⁡h∈H[um−1(h)+sLh(xm)]+12sup⁡h∈H[um−1(h)−sLh(xm)]=Eσm[sup⁡h∈Hum−1(h)+σmLh(xm)]begin{aligned}
& left.mathrm{E}left[sup _{m in H} u_{m-1}(h)+sigma_m(Phi circ h)left(x_mright)right]right] \
& =frac{1}{2}left[u_{m-1}left(h_1right)+left(Phi circ h_1right)left(x_mright)right]+frac{1}{2}left[u_{m-1}left(h_2right)-left(Phi circ h_2right)left(x_mright)right] \
& leq frac{1}{2}left[u_{m-1}left(h_1right)+u_{m-1}left(h_2right)+s Lleft(h_1left(x_mright)-h_2left(x_mright)right)right] \
& =frac{1}{2}left[u_{m-1}left(h_1right)+s L h_1left(x_mright)right]+frac{1}{2}left[u_{m-1}left(h_2right)-s L h_2left(x_mright)right] \
& leq frac{1}{2} sup _{h in H}left[u_{m-1}(h)+s L hleft(x_mright)right]+frac{1}{2} sup _{h in H}left[u_{m-1}(h)-s L hleft(x_mright)right] \
& =underset{sigma_m}{mathrm{E}}left[sup _{h in H} u_{m-1}(h)+sigma_m L hleft(x_mright)right]
end{aligned}

  令 s=sgn(h1(xm)−h2(xm))s =text{sgn} (h_1 (x_m) − h2 (x_m)),对所有其他 i(i≠m)i(ine m) 以相同的方式进行,得证。

二分类 SVM 的泛化误差界

定理 4.8 (关于 Rademacher 复杂度的泛化上界)

  令 Hmathcal{H} 为实值假设空间,给定 ρ>0rho > 0,对于 0<δ<10 < delta < 1h∈Hhinmathcal{H},以至少 1−δ1 − delta 的概率有

E(h)⩽E^ρ(h)+2ρℜm(H)+ln⁡1δ2mE(h)⩽E^ρ(h)+2ρℜ^D(H)+3ln⁡2δ2mbegin{gathered}
E(h) leqslant widehat{E}_rho(h)+frac{2}{rho} Re_m(mathcal{H})+sqrt{frac{ln frac{1}{delta}}{2 m}} \
E(h) leqslant widehat{E}_rho(h)+frac{2}{rho} widehat{Re}_D(mathcal{H})+3 sqrt{frac{ln frac{2}{delta}}{2 m}}
end{gathered}

证明

  构造 H~={z=(x,y)↦yh(x):h∈H}tilde{mathcal{H}} = {z = (x, y)mapsto yh(x) : h in mathcal{H}},考虑值域为 [0,1][0,1] 的假设空间 F={Φρ∘f:f∈H~}mathcal{F} =left{Phi_{rho} circ f : f in tilde{mathcal{H}}right} 由定理 4.4 知,对所有 g∈Fgin mathcal{F},以至少 1−δ1 − delta 的概率有 :

E[g(z)]⩽1m∑i=1mg(zi)+2ℜm(F)+ln⁡1δ2mmathbb{E}[g(z)]leqslantfrac{1}{m}sum_{i=1}^mg(z_i)+2Re_m(mathcal{F})+sqrt{frac{ln frac{1}{delta}}{2 m}}

  因此对于 h∈Hhinmathcal{H},以至少 1−δ1 − delta 的概率有:

E[Φρ(yh(x))]⩽E^ρ(h)+2ℜm(Φρ∘H~)+ln⁡1δ2mmathbb{E}[Phi_{rho}(yh(x))]leqslantwidehat{E}_{rho}(h)+2Re_mleft(Phi_{rho}circtilde{mathcal{H}}right)+sqrt{frac{ln frac{1}{delta}}{2 m}}

  因为对 ∀u∈R,Iu⩽0⩽Φρ(u)forall uinmathbb{R},mathbb{I}_{uleqslant0}leqslantPhi_{rho}(u) 成立,所以

E(h)=E[Iyh(x)⩽0]⩽E[Φρ(yh(x))]E(h)=mathbb{E}left[mathbb{I}_{yh(x)leqslant0}right]leqslantmathbb{E}left[Phi_{rho}(yh(x))right]

  代入可知,以至少 1−δ1 − delta 的概率有:

E(h)⩽E^ρ(h)+2ℜm(Φρ∘H~)+ln⁡1δ2mE(h)leqslantwidehat{E}_{rho}(h)+2Re_mleft(Phi_{rho}circtilde{mathcal{H}}right)+sqrt{frac{ln frac{1}{delta}}{2 m}}

  由于 ΦρPhi_{rho}1ρfrac{1}{rho}-Lipschitz,由引理 4.4 可知

ℜm(Φρ∘H~)⩽1ρℜm(H~)Re_mleft(Phi_{rho}circtilde{mathcal{H}}right)leqslantfrac{1}{rho}Re_m(tilde{mathcal{H}})

  又由 Rademacher 复杂度定义知

ℜm(H~)=1mED,σ[sup⁡h∈H∑i=1mσiyih(xi)]=1mED,σ[sup⁡h∈H∑i=1mσih(xi)]=ℜm(H)begin{aligned}
Re_m(tilde{mathcal{H}})= &frac{1}{m}mathbb{E}_{D,sigma}left[sup_{hinmathcal{H}}sum_{i=1}^msigma_iy_ih(x_i)right]\
= & frac{1}{m}mathbb{E}_{D,sigma}left[sup_{hinmathcal{H}}sum_{i=1}^msigma_ih(x_i)right]\
= & Re_m(mathcal{H})
end{aligned}

  代入得,以至少 1−δ1 − delta 的概率有:

ℜm(Φρ∘H~)⩽1ρℜm(H)⇒E(h)⩽E^ρ(h)+2ℜm(Φρ∘H~)+ln⁡1δ2m⩽E^ρ(h)+2ρℜm(H)+ln⁡1δ2mRe_mleft(Phi_{rho}circtilde{mathcal{H}}right)leqslantfrac{1}{rho}Re_m(mathcal{H})\
Rightarrow{color{blue}E(h)}leqslantwidehat{E}_{rho}(h)+2Re_mleft(Phi_{rho}circtilde{mathcal{H}}right)+sqrt{frac{ln frac{1}{delta}}{2 m}}\{color{blue}leqslantwidehat{E}_rho(h)+frac{2}{rho} Re_m(mathcal{H})+sqrt{frac{ln frac{1}{delta}}{2 m}}}

  得证。由定理 4.4 可知,以至少 1−δ1 − delta 的概率有:

E[g(z)]⩽1m∑i=1mg(zi)+2ℜ^D(F)+3ln⁡2δ2mmathbb{E}[g(z)]leqslantfrac{1}{m}sum_{i=1}^mg(z_i)+2widehat{Re}_D(mathcal{F})+3sqrt{frac{ln frac{2}{delta}}{2 m}}

  同理可证,以至少 1−δ1 − delta 的概率有:

E(h)⩽E^ρ(h)+2ℜ^D(Φρ∘H)+3ln⁡2δ2mE(h) leqslant widehat{E}_rho(h)+2widehat{Re}_Dleft(Phi_{rho}circmathcal{H}right)+3 sqrt{frac{ln frac{2}{delta}}{2 m}}

  对于经验 Rademacher 复杂度,由于 ΦρPhi_{rho}1ρfrac{1}{rho}-Lipschitz,类似地有

R^D(Φρ∘H~)⩽1ρR^D(H~)R^D(H~)=1mEσ[sup⁡h∈H∑i=1mσiyih(xi)]=1mEσ[sup⁡h∈H∑i=1mσih(xi)]=R^D(H)begin{aligned}
& hat{mathfrak{R}}_Dleft(Phi_rho circ tilde{mathcal{H}}right) leqslant frac{1}{rho} widehat{mathfrak{R}}_D(tilde{mathcal{H}}) \
& widehat{mathfrak{R}}_D(tilde{mathcal{H}})=frac{1}{m} mathbb{E}_sigmaleft[sup _{h in mathcal{H}} sum_{i=1}^m sigma_i y_i hleft(boldsymbol{x}_iright)right] \
&=frac{1}{m} mathbb{E}_{boldsymbol{sigma}}left[sup _{h in mathcal{H}} sum_{i=1}^m sigma_i hleft(boldsymbol{x}_iright)right] \
&=hat{mathfrak{R}}_D(mathcal{H})
end{aligned}

  则以至少 1−δ1 − delta 的概率有:

E(h)⩽E^ρ(h)+2ρℜ^D(H)+3ln⁡2δ2mcolor{blue}E(h) leqslant widehat{E}_rho(h)+frac{2}{rho} widehat{Re}_D(mathcal{H})+3 sqrt{frac{ln frac{2}{delta}}{2 m}}

定理 4.9

  令 Hmathcal{H} 为实值假设空间,对于 0<δ<10 < delta < 1h∈Hhinmathcal{H},以及任意 ρ∈(0,1)rhoin(0, 1),以至少 1−δ1-delta 的概率有:

E(h)⩽E^ρ(h)+4ρℜm(H)+ln⁡log⁡22ρm+ln⁡2δ2mE(h)⩽E^ρ(h)+4ρR^D(H)+ln⁡log⁡22ρmm+3ln⁡4δ2mbegin{aligned}
& E(h) leqslant widehat{E}_rho(h)+frac{4}{rho} Re_m(mathcal{H})+sqrt{frac{ln log _2 frac{2}{rho}}{m}}+sqrt{frac{ln frac{2}{delta}}{2 m}} \
& E(h) leqslant widehat{E}_rho(h)+frac{4}{rho} widehat{mathfrak{R}}_D(mathcal{H})+sqrt{frac{ln _{log _2 frac{2}{rho}}^m}{m}}+3 sqrt{frac{ln frac{4}{delta}}{2 m}}
end{aligned}

  由定理 3.7 可知 R^D(H)⩽r2Λ2mwidehat{mathfrak{R}}_D(mathcal{H})leqslantsqrt{frac{r^2Lambda^2}{m}},两边取期望得到,Rm(H)⩽r2Λ2mmathfrak{R}_m(mathcal{H})leqslantsqrt{frac{r^2Lambda^2}{m}}

推论 4.1

  令 H={x↦w⋅x:∣w∣⩽Λ}mathcal{H}={xmapsto w cdot x : lvert wrvertleqslantLambda}∥x∥⩽rlVert xrVert leqslant r,对于 0<δ<10 < delta < 1h∈Hhinmathcal{H} 和固定的 ρ>0rho > 0,以至少 1−δ1-delta 的概率有:

E(h)⩽E^ρ(h)+2r2Λ2/ρ2m+ln⁡1δ2mE(h)leqslantwidehat{E}_{rho}(h)+2sqrt{frac{r^2Lambda^2/rho^2}{m}}+sqrt{frac{ln frac{1}{delta}}{2 m}}

推论 4.2

  令 H={x↦w⋅x:∣w∣⩽Λ}mathcal{H}={xmapsto w cdot x : lvert wrvertleqslantLambda}∥x∥⩽rlVert xrVert leqslant r,对于 0<δ<10 < delta < 1h∈Hhinmathcal{H} 和任意的的 ρ∈(0,1)rhoin(0,1),以至少 1−δ1-delta 的概率有:

E(h)⩽E^ρ(h)+4r2Λ2/ρ2m+ln⁡log⁡22ρm+ln⁡2δ2mE(h)leqslantwidehat{E}_{rho}(h)+4sqrt{frac{r^2Lambda^2/rho^2}{m}}+sqrt{frac{lnlog_2frac{2}{rho}}{m}}+sqrt{frac{ln frac{2}{delta}}{2 m}}

经验风险最小化

定义 4.2

  如果学习算法 Lmathfrak{L} 输出 Hmathcal{H} 中具有最小经验误差的假设 hh,即 E^(h)=min⁡h′∈HE^(h′)hat{E}(h)=min_{h’inmathcal{H}}widehat{E}(h’),则称 Lmathfrak{L} 为满足经验风险最小化原则的算法

  假设 Lmathfrak{L} 为满足经验风险最小化原则的算法,令 gg 表示 Hmathcal{H} 中具有最小泛化误差的假设,即 E(h)=min⁡h′∈HE^(h′)E(h)= min_{h’inmathcal{H}}widehat{E}(h’) 由引理 2.1 可知,

P(∣E^(g)−E(g)∣⩾ϵ2)⩽2exp⁡(−mϵ22)P(lvertwidehat{E}(g)-E(g)rvertgeqslantfrac{epsilon}{2})leqslant2expleft(-frac{mepsilon^2}{2}right)

  由于 δ′=δ2,(ln⁡2/δ′)2m⩽ϵ2delta’=frac{delta}{2},sqrt{frac{(ln2/delta’)}{2m}}leqslantfrac{epsilon}{2},即 2exp⁡(−mϵ22)⩽δ′2expleft(-frac{mepsilon^2}{2}right)leqslantdelta’ 以至少 1−δ21-frac{delta}{2} 的概率有:

E^(g)−ϵ2⩽E(g)⩽E^(g)+ϵ2widehat{E}(g)-frac{epsilon}{2}leqslant E(g)leqslantwidehat{E}(g)+frac{epsilon}{2}

  由定理 4.3 可知,以至少 1−δ21-frac{delta}{2} 的概率有:

∣E(h)−E^(h)∣⩽ϵ2lvert E(h)-widehat{E}(h) rvertleqslantfrac{epsilon}{2}

  即 E(h)⩽E^(h)+ϵ2E(h)leqslantwidehat{E}(h)+frac{epsilon}{2} (根据经验最小化原则,E^(h)⩽E^(g)widehat{E}(h)leqslantwidehat{E}(g)),所以以至少 1−δ1-delta 的概率有:

E(h)−E(g)⩽E^(h)+ϵ2−(E^(g)+ϵ2)=E^(h)−E^(g)+ϵ⩽ϵbegin{aligned}
E(h)-E(g) & leqslant widehat{E}(h)+frac{epsilon}{2}-left(widehat{E}(g)+frac{epsilon}{2}right) \
& =widehat{E}(h)-widehat{E}(g)+epsilon \
& leqslant epsilon
end{aligned}

  所以若学习算法 Lmathfrak{L} 输出 Hmathcal{H} 中具有最小经验误差的假设 hh,其泛化误差
E(h)E(h) 以至少 1−δ1-delta 的概率不大于最小泛化误差 E(h)+ϵE(h) +epsilon

结论

  • 泛化误差边界不取决于维度,而取决于间隔
  • 这需要我们在更高维的特征空间中寻找大间隔的超平面

计算问题

  • 高维特征空间上使用点积是很昂贵的
  • 可以使用核函数来解决

  Orz 快累死了。

本网站的内容主要来自互联网上的各种资源,仅供参考和信息分享之用,不代表本网站拥有相关版权或知识产权。如您认为内容侵犯您的权益,请联系我们,我们将尽快采取行动,包括删除或更正。
AI教程

MegEngine优化器使用指南

2023-12-8 21:16:14

AI教程

大语言模型的红队攻击:新的研究领域

2023-12-8 21:27:14

个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索