【机器学习基础】PAC学习框架

PAC自学架构

PAC（Probably Approximately Correct）架构借助于样品维数（欲达至近似于截叶须要的样品点数量）和自学演算法的天数内部空间维数（倚赖基本概念类排序则表示的付出）来表述可自学的基本概念类。

PAC自学数学模型

样品： X\mathcal{X}

条码： Y\mathcal{Y} ，该处只探讨二进行分类的情形，Y={0,1}\mathcal{Y}=\{0,1\}

基本概念： X→Y\mathcal{X}\rightarrow\mathcal{Y} ，指两个从X\mathcal{X}到Y\mathcal{Y}的映射

基本概念类：C，可能想要自学的基本概念的集合

分布：D，假设所有样品独立同分布，该分布固定但未知

假设集：H，固定的、所有可能的基本概念组成的集合H，H与C可能一致，也可能不一致（一致是指假设集中包含了待自学的基本概念，我理解为C∈HC\in H ）

泛化误差：

给定两个假设 h∈Hh\in H ，两个目标基本概念 c∈Cc\in C ，以及两个潜在的分布D，则h的泛化误差或风险表述为 R(h)=Prx∼D[h(x)≠c(x)]=Ex∼D⁡[lh[x]≠c[x]]R(h)=\Pr_{x\sim D}[h(x)\not=c(x)]=\mathop{E}_{x\sim D}[l_{h[x]\not=c[x]}] ，因为分布D和目标基本概念c均未知，泛化误差无法直接获得

经验误差：

给定两个假设 h∈Hh\in H ，两个目标基本概念 c∈Cc\in C ，以及两个样品集 S=(x1,…,xm)S=(x_1,\dots,x_m) ，则h的经验误差或经验风险为 R^(h)=1m∑i=1mlh(xi)≠c(xi)\hat{R}(h)=\frac{1}{m}\sum_{i=1}^ml_{h(x_i)\not=c(x_i)}

对于固定的 h∈Hh\in H ，在样品独立同分布的情形下，样品集上经验误差的期望就等于 E[R^(h)]=R(h)E[\hat{R}(h)]= R (h) ，对于样品集S中任意样品x： ES∼Dm⁡[R^(h)]=1m∑i=1mES∼Dm⁡[lh(xi)≠c(xi)]=1m∑i=1mES∼Dm⁡[lh(x)≠c(x)]=Ex∼D⁡[lh(x)≠c(x)]=R(h)\mathop{E}_{S \sim D^m }[ \hat{R}(h) ]= \frac{1}{m} \sum_{i=1}^{m} \mathop{E}_{S \sim D^ m }[l_{h(x_i) \not=c(x_i)}]=\\ \frac{1}{m}\sum_{i=1}^{m} \mathop{E}_{S\sim D^m}[l_{h(x)\not=c(x)}]=\mathop{E}_{x \sim D}[l_{h(x) \not =c(x)}]=R(h)

将对任意元素 x∈Xx\in\mathcal{X}进行则表示的排序维数（如x的维度）上界记为O(n)，将概念c∈Cc\in C 的维数(我理解的是用目标基本概念对两个样品进行排序的维数，如决策树的高度）记为size(c)。

PAC可自学

如果存在两个演算法A以及两个多项式函数 poly(⋅,⋅,⋅,⋅)poly(\cdot ,\cdot,\cdot,\cdot) 使得对于任意 0″>ϵ>0\epsilon>0 以及 0″>δ>0\delta>0 ，对于所有在 X\mathcal{X} 上的分布D以及任意目标基本概念 c∈Cc\in C ，对于满足 m≥poly(1ϵ,1δ,n,size(c))m\ge poly(\frac{1}{\epsilon},\frac{1}{\delta},n,size(c)) 的任意样品规模m均有PrS∼Dm[R(hS)≤ϵ]≥1−δ\Pr_{S\sim D^m}[R(h_S)\le\epsilon]\ge1-\delta成立，那么基本概念类C是PAC可自学的。

高效PAC可自学

若A的运行维数在 poly(1ϵ,1δ,n,size(c))poly(\frac{1}{\epsilon},\frac{1}{\delta},n,size(c)) 内，则基本概念类C是高效PAC可自学的，称演算法A为C的两个PAC自学演算法

一致情形

令A为自学任意目标基本概念 c∈Hc\in H 的演算法并且根据独立同分布样品S返回的是两个一致的假设 hS:R^(hS)=0h_S:\hat{R}(h_S)=0 ，对于任意 0″>ϵ,δ>0\epsilon,\delta>0 ,不等式 Pr[R(hS)≤ϵ]≥1−δ\Pr[R(h_S)\le\epsilon]\ge1-\delta成立的条件是：m≥1ϵ(log|H|+log1δ)m\ge\frac{1}{\epsilon}(log|H|+log\frac{1}{\delta}) （样品维数）

即对于任意 0″>ϵ,δ>0\epsilon,\delta>0 ，以至少 1−δ1-\delta 的概率，有 R(hS)≤1m(log|H|+log1δ)R(h_S)\le\frac{1}{m}(log|H|+log\frac{1}{\delta})(泛化误差界)，泛化误差减少速率为O(1m)O(\frac{1}{m})

证明：

\epsilon]=\Pr[(h_1\in H,\hat{R}(h_1)=0\and R(h_1)>\epsilon)\or (h_2\in H,\hat{R}(h_1=0\And R(h_1)>\epsilon)\or \cdots)\\\le\sum_{h\in H}\Pr[\hat{R}(h)=0 \or R(h)>\epsilon] \le \sum_{h \in H}\Pr[ \hat{R}(h)=0 | R(h)>\epsilon] \le | H |(1- \epsilon)^m”>Pr[∃h∈H:R^(h)=0\andR(h)>ϵ]=Pr[(h1∈H,R^(h1)=0\andR(h1)>ϵ)\or(h2∈H,R^(h1=0&R(h1)>ϵ)\or⋯)≤∑h∈HPr[R^(h)=0\orR(h)>ϵ]≤∑h∈HPr[R^(h)=0|R(h)>ϵ]≤|H|(1−ϵ)m\Pr[\exists h\in H:\hat{R}(h)=0\and R(h)>\epsilon]=\Pr[(h_1\in H,\hat{R}(h_1)=0\and R(h_1)>\epsilon)\or (h_2\in H,\hat{R}(h_1=0\And R(h_1)>\epsilon)\or \cdots)\\\le\sum_{h\in H}\Pr[\hat{R}(h)=0 \or R(h)>\epsilon] \le \sum_{h \in H}\Pr[ \hat{R}(h)=0 | R(h)>\epsilon] \le | H |(1- \epsilon)^m

不一致情形

令H为两个有限的假设集，对于任意 0″>δ>0\delta>0 ，以至少为 1−δ1-\delta 的概率，不等式 ∀h∈H,R(h)≤R^(h)+log|H|+log2δ2m\forall h\in H,R(h) \le \hat{R} (h)+\sqrt{\frac{log|H|+log\frac{2}{\delta}}{2m}}成立，泛化误差减少速率为O(1m)O(\sqrt{\frac{1}{m}})。

证明：

Hoeffding不等式：对于任意假设 h:X→{0,1}h:\mathcal{X}\rightarrow\{0,1\}，固定ε， PrS∼Dm[R^(h)−R(h)≥ϵ2]≤exp⁡(−2mϵ2)PrS∼Dm[R^(h)−R(h)≤−ϵ2]≤exp⁡(−2mϵ2)PrS∼Dm[|R^(h)−R(h)|≥ϵ2]≤2exp⁡(−2mϵ2)\Pr_{S\sim D^m}[\hat{R}(h)-R(h)\ge\epsilon^2]\le\exp(-2m\epsilon^2)\\ \Pr_{S\sim D^m}[\hat{R}(h)-R(h)\le-\epsilon^2]\le\exp(-2m\epsilon^2)\\ \Pr_{S\sim D^m}[|\hat{R}(h)-R(h)|\ge\epsilon^2]\le 2\exp(-2m\epsilon^2)

固定两个单一假设h，则对于任意 0″>δ>0\delta>0 ，以至少 1−δ1-\delta 的概率，不等式 R(h)≤R^(h)+log2δ2mR(h) \le \hat{R} (h)+ \sqrt{ \frac{log \frac{2}{ \delta }}{2m}} 成立

用于每个假设：

\epsilon]=\Pr[(|\hat{R}(h_1)-R(h_1)|>\epsilon)\or \cdots \or (|\hat{R}(h_{|H|})-R(h_{|H|})|>\epsilon)]\\ \le \sum_{h\in H}\Pr[|\hat{R}(h)-R(h)|>\epsilon]\le 2|H|\exp(-2m\epsilon^2)”>Pr[∃h∈H|R^(h)−R(h)|>ϵ]=Pr[(|R^(h1)−R(h1)|>ϵ)\or⋯\or(|R^(h|H|)−R(h|H|)|>ϵ)]≤∑h∈HPr[|R^(h)−R(h)|>ϵ]≤2|H|exp⁡(−2mϵ2)\Pr[\exists h\in H \ \ \ |\hat{R}(h)-R(h)|>\epsilon]=\Pr[(|\hat{R}(h_1)-R(h_1)|>\epsilon)\or \cdots \or (|\hat{R}(h_{|H|})-R(h_{|H|})|>\epsilon)]\\ \le \sum_{h\in H}\Pr[|\hat{R}(h)-R(h)|>\epsilon]\le 2|H|\exp(-2m\epsilon^2)

对于不一致的情形，泛化误差界存在权衡，即减少经验误差与控制假设集的大小。体现了奥卡姆剃刀原则：对于类似的经验误差，更简单的假设集是更好的

随机性情境

自学演算法输出的条码是输入的概率函数，输入对应的条码可能不是唯一的

对于样品 S=((x1,y1),…,(xm,ym))S=((x_1,y_1),\dots,(x_m,y_m)) ，自学要解决的问题是找到两个有较小泛化误差的假设 h∈H:R(h)=Pr(x,y)∼D[h(x)≠y]=E(x,y)∼D⁡[lh(x)≠y]h\in H:R(h)=\Pr_{(x,y)\sim D}[h(x)\not =y]=\mathop{E}_{(x,y)\sim D}[l_{h(x)\not =y}]

不可知PAC自学

如果存在两个演算法A以及两个多项式函数poly(⋅,⋅,⋅,⋅)poly(\cdot ,\cdot,\cdot,\cdot) 使得对于任意 0″>ϵ>0\epsilon>0 以及 0″>δ>0\delta>0 ，对于所有在 X×Y\mathcal{X}\times\mathcal{Y} 上的分布D以及任意目标基本概念 c∈Cc\in C ，对于满足 m≥poly(1ϵ,1δ,n,size(c))m\ge poly(\frac{1}{\epsilon},\frac{1}{\delta},n,size(c)) 的任意样品规模m均有PrS∼Dm[R(hS)−minh∈HR(h)≤ϵ]≥1−δ\Pr_{S\sim D^m}[R(h_S)-\min_{h\in H} R(h)\le\epsilon]\ge1-\delta成立，那么基本概念类C是PAC可自学的。

若A的运行维数在 poly(1ϵ,1δ,n,size(c))poly(\frac{1}{\epsilon},\frac{1}{\delta},n,size(c)) 内，则基本概念类C是高效不可知PAC可自学的，称演算法A为C的两个高效不可知PAC自学演算法

贝叶斯误差和噪声

相应的贝叶斯误差 R∗R^{*}定义为由可测函数类h:X→Yh:\mathcal{X}\rightarrow\mathcal{Y} 产生的误差下界：

R∗=infhhmeasurable⁡R(h)\mathcal{R}^{*}=\mathop{\inf_{h}}_{h \ measurable}R(h) ，两个满足 R(h)=R∗R(h)=R^{*} 的假设h被称为贝叶斯假设或贝叶斯进行分类器，贝叶斯进行分类器可以用条件概率进行表述

∀x∈X,hBayes(x)=arg⁡maxy∈{0,1}Pr[y|x]\forall x\in \mathcal{X},h_{Bayes}(x)=\arg\max_{y\in\{0,1\}} \Pr[y|x]

表述噪声为noise(x)=min{Pr[1|x],Pr[0|x]}noise(x)=\min\{\Pr[1|x],\Pr[0|x]\} ，则平均噪声或称关于分布D的噪声为 E[noise(x)]=R∗E[noise(x)]=R^{*} ，若对于一更样品点 x∈Xx\in \mathcal{X} ，若noise(x)接近1/2，则被称为噪点

估计误差与近似于误差

）R(h)−R∗=(R(h)−R(h∗))+(R(h∗)−R∗）R(h)-R^{*}=(R(h)-R(h^{*}))+(R(h^{*})-R^{*}）

第一项为估计误差（则表示选定的假设与类中最优假设的相近程度），第二项为近似于误差（则表示H与贝叶斯误差的相近程度），h∗h^{*} 称为类中最优假设，是H中误差最小的假设

数学模型选择

R(hSERM)−R(h∗)=R(hSERM)−R^(hSERM)+R^(hSERM)−R(h∗)≤R(hSERM)−R^(hSERM)+R^(h∗)−R(h∗)≤2suph∈H|R(h)−R^(h)|R(h_S^{ERM})-R(h^{*})=R(h_S^{ERM})-\hat{R}(h_S^{ERM})+\hat{R}(h_S^{ERM})-R(h^{*})\\\le R(h_S^{ERM})-\hat{R}(h_S^{ERM})+\hat{R}(h^{*})-R(h^{*})\le2\sup_{h\in H}|R(h)-\hat{R}(h)|

式子右边的上界随|H|增大而增大，R(h∗)R(h^{*}) 随|H|增大而减小

H0⊂H1⊂…Hn…H_0\subset H_1\subset \dots H_n\dots

hSREG=arg⁡minh∈HR^S(h)+λ||h||2h_S^{REG}=\arg\min_{h\in H}\hat{R}_S(h)+\lambda||h||^2

λ为正则因子