学习理论

1、基本概念

2、PAC理论

3、VC维

4、极大似然，最大后验概率，贝叶斯估计

5、模型评估与评价指标

6、模型诊断调参

二、PAC理论

​ 概率近似正确（PAC）理论是从概率的角度来衡量模型的正确率，给出了PAC可辨识，样本复杂度界，误差上界。

偏差/方差

​ 偏差和方差是机器学习中很重要的两个概念，在分析模型时对应于欠拟合和过拟合问题。

以回归问题为例，上图中左边为一个线性拟合，可以看出，拟合的程度不够（欠拟合），与真实样本的偏差较大，右边的图类似于插值曲线，基本上每个点都拟合的过好（过拟合），然而我们的训练集只是样本数真实分布的一个子集，并不代表所有的样本（测试集）都能拟合的很好，一般而言，由于右图模型复杂度较高，往往泛化能力不如简单的模型。而中间的图拟合的程度和模型的复杂度都不错，因此，机器学习中更倾向于中间的模型最优。

经验风险最小

经验风险最小一直以来都是我们构建目标函数的一个准则，以二分类为例，经验风险最小就是使得误判的样本数最少，对于数据集：

S={x(i),y(i)},0≤i≤m,y∈{0,1}S=\{x^{(i)},y^{(i)}\},0\leq i \leq m ,y\in \{0,1\} S={x(i),y(i)},0≤i≤m,y∈{0,1}

其中，样本点(x(i),y(i))(x^{(i)},y^{(i)})(x(i),y(i))独立同分布。

假设，我们学习一个模型来进行分类：

hθ(x)=g(θTx)g(z)=I{z≥0},g∈{0,1}h_{\theta}(x)=g(\theta^Tx)\\ g(z)=I\{z\geq 0\},g \in \{0,1\} hθ​(x)=g(θTx)g(z)=I{z≥0},g∈{0,1}

其中hhh是一个线性函数，ggg是一个指示函数，这样我们就有了一个二分类器。

那么，训练误差即为：

ϵ^(hθ)=ϵ^S(hθ)=1m∑i=1mI{hθ(x(i))≠y(i)}\hat{\epsilon}(h_{\theta})=\hat{\epsilon}_{S}(h_{\theta})=\frac{1}{m}\sum_{i=1}^{m}I\{h_{\theta}(x^{(i)})\neq y^{(i)}\} ϵ^(hθ​)=ϵ^S​(hθ​)=m1​i=1∑m​I{hθ​(x(i))̸​=y(i)}

经验风险最小化准则就是最小化训练误差：

θ^=argmin⁡θϵ^S(hθ)\hat{\theta}=arg\min_{\theta}\hat{\epsilon}_{S}(h_{\theta}) θ^=argθmin​ϵ^S​(hθ​)

然而，我们发现如上目标函数非凸，一般无法直接优化，而且这样定义目标函数得到最好的模型在真实数据上并不一定测试误差就最小。为了解决优化的问题，采用对数损失，指数损失，Higne损失，线性损失来代替0​−​10\!-\!10−1损失。

也就是说我们根据最小化经验损失，从hθh_{\theta}hθ​的假设空间HHH中学习我们的目标空间：

h^=argmin⁡h∈Hϵ^(h)\hat{h}=arg\min_{h\in H} \hat{\epsilon}(h) h^=argh∈Hmin​ϵ^(h)

上式，只是我们在训练集上的最小损失，泛化到测试集：

ϵ(h)=Px,y∼D(h(x)≠y)\epsilon(h)=P_{x,y \sim D}(h(x)\neq y) ϵ(h)=Px,y∼D​(h(x)̸​=y)

也就是说ϵ^\hat{\epsilon}ϵ^为训练集上的损失，ϵ\epsilonϵ为泛化到测试集上的损失。当然，我们希望不学习测试数据就能学到测试集上泛化误差最小的h∗h^{*}h∗是最好的（不切实际）。

Hoeffding不等式，联合上界，一致收敛

假设{x(1),x(2),..,x(i),..,x(m)}\{x^{(1)},x^{(2)},..,x^{(i)},..,x^{(m)}\}{x(1),x(2),..,x(i),..,x(m)}独立同分布，服从伯努利分布：

P(x(i)=1)=ϕ,P(x(i)=0)=1−ϕP(x^{(i)}=1)=\phi,P(x^{(i)}=0)=1-\phi P(x(i)=1)=ϕ,P(x(i)=0)=1−ϕ

从伯努利分布角度看，当样本趋于无限大时，所有点的均值为ϕ\phiϕ。从样本统计来看，由于它们之间独立同分布，所以有均值为：

ϕ^=1m∑i=1mx(i)\hat{\phi}=\frac{1}{m}\sum_{i=1}^{m}x^{(i)} ϕ^​=m1​i=1∑m​x(i)

Hoeffding不等式的定义为对任意固定值γ>0\gamma>0γ>0，存在：

P(∣ϕ^−ϕ∣&gt;γ)&lt;2exp(−2γ2m)P(|\hat{\phi}-\phi|&gt;\gamma) &lt;2exp(-2\gamma^{2}m) P(∣ϕ^​−ϕ∣>γ)<2exp(−2γ2m)

该引理表示一个随机变量其偏离期望大于γ\gammaγ的概率有上限。可以从高斯分布出发其到均值距离大于γ\gammaγ的概率有上限（切比雪夫不等式）。 注意，上述不等式是针对一维的情况。

联合上界，假设有n个随机变量{x1,x2,..,xj,..,xn}\{x_{1},x_{2},..,x_{j},..,x_{n}\}{x1​,x2​,..,xj​,..,xn​}，这nnn个随机变量可以相互独立也可以不独立，我们有：

P(x1,x2,..,xn)≤P(x1)+P(x2)+,..,+P(xn)P(x_{1},x_{2},..,x_{n})\leq P(x_{1})+P(x_{2})+,..,+P(x_{n}) P(x1​,x2​,..,xn​)≤P(x1​)+P(x2​)+,..,+P(xn​)

该不等式很容易理解，即所有事件并集发生的概率小于所有事件发生的概率之和，当且仅当nnn个事件互斥，等号成立。现在，我们将∣ϕj^−ϕj∣&gt;γj|\hat{\phi_{j}}-\phi_{j}|&gt;\gamma_{j}∣ϕj​^​−ϕj​∣>γj​ 记为事件xjx_{j}xj​，那么有P(xj)≤2exp(−2γj2m)P(x_{j})\leq 2exp(-2\gamma_{j}^2m)P(xj​)≤2exp(−2γj2​m)，使用联合上界将其推广到nnn维，我们有：

∑j=1nP(∣ϕj^−ϕj∣&gt;γj)≤∑i=1n2exp(−2γj2m)\sum_{j=1}^{n}P(|\hat{\phi_{j}}-\phi_{j}|&gt;\gamma_{j}) \leq\sum_{i=1}^{n}2exp(-2\gamma_{j}^{2}m) j=1∑n​P(∣ϕj​^​−ϕj​∣>γj​)≤i=1∑n​2exp(−2γj2​m)

假设γj\gamma_{j}γj​取统一值γ\gammaγ,那么有：

P(∣ϕ^−ϕ∣&gt;γ)≤2nexp(−2γ2m)P(|\hat{\phi}-\phi|&gt;\gamma) \leq 2n exp(-2\gamma^{2}m) P(∣ϕ^​−ϕ∣>γ)≤2nexp(−2γ2m)

上式的意义在于，说明当样本数目mmm增大时，我们对参数的估计就越逼近真实值。

一致收敛，定义模型的假设空间为:

H={h1,h2,.hk.,hN}H=\{h_{1},h_{2},.h_{k}.,h_{N}\} H={h1​,h2​,.hk​.,hN​}

首先，我们假设对于所有的hhh来说，存在训练误差为ϵ^(hk)=1m∑i=1mI(hk(x(i))≠y(i))\hat{\epsilon}(h_{k})=\frac{1}{m}\sum_{i=1}^{m}I(h_{k}(x^{(i)})\neq y^{(i)})ϵ^(hk​)=m1​∑i=1m​I(hk​(x(i))̸​=y(i))，ϵ\epsilonϵ是定义在测试集上的泛化误差，然后我们证明对于任意一个hkh_{k}hk​泛化误差ϵ\epsilonϵ存在上限。

对于hkh_{k}hk​，泛化误差ϵ(hk)\epsilon(h_{k})ϵ(hk​)是一个以ϵ^(hk)\hat{\epsilon}(h_{k})ϵ^(hk​)为均值服从伯努利分布（分类问题）的随机变量（向量）。由Hoeffding不等式在nnn维的推广，我们有：

P(∀∣ϵ(hk)−ϵ^(hk)∣&gt;γ)≤2Nexp(−2γ2m),k=1,2..NP(\forall|\epsilon(h_{k})-\hat{\epsilon} (h_{k})|&gt;\gamma)\leq 2N exp(-2\gamma^2m) ,k=1,2..N P(∀∣ϵ(hk​)−ϵ^(hk​)∣>γ)≤2Nexp(−2γ2m),k=1,2..N

也就是说对于假设空间中任意一个模型hkh_{k}hk​都满足上式，也就表明不存在一个模型的误差离训练误差的偏差大于一个上限：

P(−∃∣ϵ(hk)−ϵ^(hk)∣&gt;γ)≥1−2Nexp(−2γ2m),k=1,2..NP(∣ϵ(hk)−ϵ^(hk)∣≤γ)≥1−2Nexp(−2γ2m),k=1,2..Np(∣ϵ(hk)−ϵ^(hk)∣≤γ)≥1−σP( -\exists|\epsilon(h_{k})-\hat{\epsilon} (h_{k})|&gt;\gamma)\geq 1-2Nexp(-2\gamma^2m) ,k=1,2..N\\ P( |\epsilon(h_{k})-\hat{\epsilon} (h_{k})|\leq \gamma)\geq 1-2N exp(-2\gamma^2m) ,k=1,2..N\\ p(|\epsilon(h_{k})-\hat{\epsilon} (h_{k})|\leq \gamma) \geq 1-\sigma P(−∃∣ϵ(hk​)−ϵ^(hk​)∣>γ)≥1−2Nexp(−2γ2m),k=1,2..NP(∣ϵ(hk​)−ϵ^(hk​)∣≤γ)≥1−2Nexp(−2γ2m),k=1,2..Np(∣ϵ(hk​)−ϵ^(hk​)∣≤γ)≥1−σ

上式表示，任意一个假设空间下的模型hkh_{k}hk​的泛化误差都存在上界，这个上界就是定义在偏差上的方差内。由此导出PAC可辨识，即从假设空间学习到的模型的误差ϵ^(hi)\hat{\epsilon}(h_{i})ϵ^(hi​)泛化到测试集上的误差ϵ(hi)\epsilon(h_{i})ϵ(hi​)的偏差在γ\gammaγ以内的概率大于1−σ1-\sigma1−σ。

样本复杂度界

​ 由P(∣ϵ(hk)−ϵ^(hk)∣≤γ)≥1−2Nexp(−2γ2m)P( |\epsilon(h_{k})-\hat{\epsilon} (h_{k})|\leq \gamma)\geq 1-2N exp(-2\gamma^2m)P(∣ϵ(hk​)−ϵ^(hk​)∣≤γ)≥1−2Nexp(−2γ2m)，为了保证概率大于1−σ1-\sigma1−σ，我们可以分析出至少需要多少样本：

1−2Nexp(−2γ2m)≥1−σ⇒m≥12γ2log2Nσ⇒γ≥12mlog2Nσ1-2Nexp(-2\gamma^2m)\geq 1-\sigma\\ \Rightarrow m\geq \frac{1}{2\gamma^2}log\frac{2N}{\sigma}\\ \Rightarrow \gamma \geq \sqrt{\frac{1}{2m}log\frac{2N}{\sigma}} 1−2Nexp(−2γ2m)≥1−σ⇒m≥2γ21​logσ2N​⇒γ≥2m1​logσ2N​​

由此，我们我们分析出了模型需要达到一定的准确率，需要的样本数目称为样本复杂度。同时我们分析出了在给定mmm,σ\sigmaσ时，模型hih_{i}hi​的泛化误差与mmm成反比，与nnn成正比，其中mmm为样本数目，nnn表示模型的复杂度。也就是说负杂的模型泛化误差界越大。注意：由于界的条件很宽，所以得出的界具备参考的价值不大，更多时候是直观的理解，需要样本数的大小与复杂度成正比，与误差范围成反比。

误差上界

​ 上面我们分析的是同一个模型h^=hk=argmin⁡h∈Hϵ^(h)\hat{h}=h_{k}=arg\min_{h\in H} \hat{\epsilon}(h)h^=hk​=argminh∈H​ϵ^(h)的训练误差和泛化误差的关系。但是我们更关心的是训练集上最好模型的泛化误差ϵ(h^)\epsilon(\hat{h})ϵ(h^)与测试集上最好模型的泛化误差ϵ(h∗)\epsilon(h^{*})ϵ(h∗)的关系。因为，我们的终极目标是ϵ(h∗)\epsilon(h^{*})ϵ(h∗)，但是ϵ(h∗)\epsilon(h^{*})ϵ(h∗)是永远未知的，我们最优模型还是ϵ(h^)\epsilon(\hat{h})ϵ(h^)，所以我们需要用ϵ(h∗)\epsilon(h^{*})ϵ(h∗)来定义训练最优模型h^\hat{h}h^的上界。

h^=argmin⁡h∈H∼D^min(ϵ^(h))h∗=argmin⁡h∈H∼Dmin(ϵ(h))\hat{h}=arg\min_{h\in H \sim \hat{D}}min(\hat{\epsilon}(h))\\ h^{*}=arg\min_{h\in H \sim D}min(\epsilon(h))\\ h^=argh∈H∼D^min​min(ϵ^(h))h∗=argh∈H∼Dmin​min(ϵ(h))

其中ϵ^(h^)\hat{\epsilon}(\hat{h})ϵ^(h^)表示训练数据集上最好的训练误差，ϵ(h∗)\epsilon(h^{*})ϵ(h∗)表示测试集上最好的泛化误差。

KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ \epsilon(\hat{…

第一个不等式：对于在训练误差最小的假设类h^\hat{h}h^，其泛化误差小于训练误差加γ\gammaγ，由一致收敛定理。

第二个不等式：h^\hat{h}h^为训练集上误差最小的模型，那么必然有ϵ^(h^)≤ϵ^(h∗)\hat{\epsilon}(\hat{h})\leq \hat{\epsilon}(h^{*})ϵ^(h^)≤ϵ^(h∗)。

第三个不等式，对于在测试误差最小的假设类h∗h^{*}h∗，其训练误差小于泛化误差加γ\gammaγ，由一致收敛定理。

所以我们学习的最好模型的误差ϵ^(h^)\hat{\epsilon}(\hat{h})ϵ^(h^)距离我们在测试集上最好模型的误差存在上界：

KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ \epsilon(\hat{…

上式表明，我们学习的目标模型的误差服从一个偏差为ϵ(h∗)\epsilon(h^{*})ϵ(h∗)，方差为212mlog2Nσ2 \sqrt{\frac{1}{2m}log\frac{2N}{\sigma}}22m1​logσ2N​​的分布。当我们采用复杂的假设空间来拟合数据时，偏差也许会小，但是使得第二项大。这就指导了我们在选择模型时既要考虑偏差，也要照顾到方差。一般而言，训练误差与测试误差存在如下趋势：