机器学习的基本原理

要学习机器学习，首先得想明白机器学习为啥是可信的，下面就介绍几个我个人认为的机器学习的基础原理：

• Hoaffding定理：机器学习泛化误差上界
• bias & variance & error：模型预测误差的成分
• No Free Lunch Theorem：不存在在任何情况下准确性都好的模型

Hoaffding定理

Hoaffding定理是泛化能力的一种解释，现在在这我给出Hoaffding定理的证明和释义。

Jensen不等式

若函数$f(x)$f(x)再$x\in [a,b]$x∈[a,b]上$f^{''}(x)>0$f′′(x)>0，令

$q\in [0,1],F(x)=qf(b)+(1-q)f(a)-f(qb+(1-q)a)$q∈[0,1],F(x)=qf(b)+(1−q)f(a)−f(qb+(1−q)a)

那么

$F(0)=0$F(0)=0

$F(1)=0$F(1)=0

$F^{'}(q)=f(b)-f(a)-(b-a)f^{'}(qb+(1-q)a)=(b-a)(f^{'}(\theta)-f^{'}(qb+(1-q)a))$F′(q)=f(b)−f(a)−(b−a)f′(qb+(1−q)a)=(b−a)(f′(θ)−f′(qb+(1−q)a))

由$f^{&#x27;&#x27;}(x)&gt;0$f′′(x)>0可知$F^{&#x27;}(q)$F′(q)先小于0然后大于0，所以$F(q)&lt;=0$F(q)<=0即函数$x\in [a,b]$x∈[a,b]时$f^{&#x27;&#x27;}(x)&gt;0$f′′(x)>0时，$q\in [0,1],qf(b)+(1-q)f(a)&gt;f(qb+(1-q)a)$q∈[0,1],qf(b)+(1−q)f(a)>f(qb+(1−q)a)

Markov不等式

假设$x$x是大于$0$0的随机变量，则有

$E[x]=\int_0^\infty xp(x)dx&gt;\int_0^\epsilon 0p(x)dx+\int_\epsilon^\infty \epsilon p(x)dx &gt;\epsilon P(x&gt;\epsilon)$E[x]=∫0∞​xp(x)dx>∫0ϵ​0p(x)dx+∫ϵ∞​ϵp(x)dx>ϵP(x>ϵ)

即$P(x&gt;\epsilon)&lt;\frac{E[x]}{\epsilon}$P(x>ϵ)<ϵE[x]​

引理

若$x\in [a,b],E[x]=0,t&gt;0$x∈[a,b],E[x]=0,t>0，那么

$P(x&gt;s)=P(e^{tx}&gt;e^{ts})&lt;\frac{E[e^{tx}]}{e^{st}}$P(x>s)=P(etx>ets)<estE[etx]​

由$e^{tx}$etx为凸函数可知

$e^{tx}&lt;\frac{b-x}{b-a}e^{ta}+\frac{x-a}{b-a}e^{tb}$etx<b−ab−x​eta+b−ax−a​etb

那么

$E[e^{tx}]&lt;\frac{b-E[x]}{b-a}e^{ta}+\frac{E[x]-a}{b-a}e^{tb}$E[etx]<b−ab−E[x]​eta+b−aE[x]−a​etb

令$p=t(b-a),h=\frac{a}{b-a}$p=t(b−a),h=b−aa​，那么有

$\frac{b}{b-a}e^{ta}-\frac{a}{b-a}e^{tb}=e^{ta}[\frac{b}{b-a}-\frac{a}{b-a}e^{t(b-a)}]=e^{ta}[1+\frac{a}{b-a}-\frac{a}{b-a}e^{t(b-a)}]=exp(ph+ln(1+h-he^{p}))$b−ab​eta−b−aa​etb=eta[b−ab​−b−aa​et(b−a)]=eta[1+b−aa​−b−aa​et(b−a)]=exp(ph+ln(1+h−hep))

令$f(p)=ph+ln(1+h-he^{p})$f(p)=ph+ln(1+h−hep)，那么

$f(0)=0$f(0)=0

$f^{&#x27;}(p)=h-\frac{he^{p}}{1+h-he^{p}}$f′(p)=h−1+h−hephep​

$f^{&#x27;}(0)=0$f′(0)=0

$f^{&#x27;&#x27;}(p)=-\frac{he^{p}(1+h-he^{p})+(he^{p})^2}{(1+h-he^{p})^2}=(-\frac{he^p}{1+h-he^{p}})(\frac{1+h}{1+h-he^{p}})$f′′(p)=−(1+h−hep)2hep(1+h−hep)+(hep)2​=(−1+h−hephep​)(1+h−hep1+h​)

$f^{&#x27;&#x27;}(p)=y(1-y)&lt;\frac{1}{4}$f′′(p)=y(1−y)<41​

泰勒展开可得：

$f(p)=f(0)+pf^{&#x27;}(0)+\frac{p^2}{2}f^{&#x27;&#x27;}(\theta)&lt;\frac{p^2}{8}$f(p)=f(0)+pf′(0)+2p2​f′′(θ)<8p2​

则$E[e^{tx}]&lt;exp[\frac{(b-a)^2}{8}t^2]$E[etx]<exp[8(b−a)2​t2]
则$P(x&gt;s)&lt;exp[-st+\frac{(b-a)^2}{8}t^2]$P(x>s)<exp[−st+8(b−a)2​t2]

Hoaffding定理证明

设$r_1，r_2,...,r_n$r1​，r2​,...,rn​为模型的一组误差，为了简便，让他们分布在$[-0.5,0.5]$[−0.5,0.5]，均值为0，令

$\hat r=\frac{\sum_i r_i}{n},r=E[\hat r]$r^=n∑i​ri​​,r=E[r^]

那么

$P(\hat r-r&gt;\epsilon)=e^{-t\epsilon}E[e^{t\sum_ir_i/n}]=e^{-t\epsilon}\prod_i E[e^{tr_i/n}]&lt;exp[-t\epsilon+\frac{t^2}{8n}]$P(r^−r>ϵ)=e−tϵE[et∑i​ri​/n]=e−tϵi∏​E[etri​/n]<exp[−tϵ+8nt2​]

令$t=4n\epsilon$t=4nϵ，可得

$P(x&gt;s)&lt;exp[-2n\epsilon^2]$P(x>s)<exp[−2nϵ2]

那么如果$k$k个模型训练的模型误差都满足$P(r&lt;\hat r+\epsilon)&lt;(1-kP(r-\hat r&gt;\epsilon))$P(r<r^+ϵ)<(1−kP(r−r^>ϵ))（hoeffding不等式的对称性），则

$P(r&lt;\hat r+\epsilon)&lt;(1-k*exp[-2n\epsilon^2])$P(r<r^+ϵ)<(1−k∗exp[−2nϵ2])

令$\delta = k*exp[-2n\epsilon^2]$δ=k∗exp[−2nϵ2]，则模型以$1-\delta$1−δ的概率满足任意训练的模型满足

$r&lt;\hat r+\sqrt{\frac{1}{2n}\ln{\frac{k}{\delta}}}$r<r^+2n1​lnδk​​

这就给了训练出来的模型一个误差上界，若是参数域为无穷，可用VC维来给定上界

个人不喜欢这个解释，不直观，太繁琐，而且是个loose bound，让感觉很难受。

bias & variance & error

机器学习学到的模型预测的结果和真实结果的误差来源于三个地方，也就是bias（偏差），variance（方差），error（噪声），用公式可以表示为：

$E_xL(f(x)+\epsilon,\tilde f(x)+[\hat f(x)-\hat f(x)])=F[\epsilon,f(x)-\hat f(x),\hat f(x))-\tilde f(x)]$Ex​L(f(x)+ϵ,f~​(x)+[f^​(x)−f^​(x)])=F[ϵ,f(x)−f^​(x),f^​(x))−f~​(x)]

$f(x)$f(x)是客观世界的模型，$\epsilon$ϵ是观察噪声或者是样本产生过程中的系统噪声，$\hat f(x)$f^​(x)是当前模型下能够学习到的最好的模型参数下的模型，$\tilde f(x)$f~​(x)是用有限的训练样本实际训练出来的模型，$L$L为损失函数，$E_xL$Ex​L为泛化误差。

我们把$|f(x)-\hat f(x)|$∣f(x)−f^​(x)∣成为bias（偏差），它越大说明本身模型越简单（欠拟合）
$|\hat f(x))-\tilde f(x)|$∣f^​(x))−f~​(x)∣成为variance（方差），它越大说明模型过拟合越严重（把噪声当作是模型的输出进行拟合）。

欠拟合产生的原因是拟合的模型过于简单，无法拟合真正的客观模型。
过拟合产生的原因是数据量太少，无法把模型的参数拟合得很好。

我们在进一步的挖掘一下，过拟合的原因从而更深刻的体会一下正则化的作用。

the amount of parameter vs the amount of data

Chebyshev 不等式 / 大数定理

由Markov不等式$P(x&gt;\epsilon)&lt;\frac{E[x]}{\epsilon}$P(x>ϵ)<ϵE[x]​可得

$P[(\frac{1}{n}\sum_{i=1}^nX-EX)^2&gt;\epsilon]&lt;\frac{E[(\frac{1}{n}\sum_{i=1}^nX-EX)^2]}{\epsilon}=\frac{\sigma^2}{\epsilon n^2}$P[(n1​i=1∑n​X−EX)2>ϵ]<ϵE[(n1​∑i=1n​X−EX)2]​=ϵn2σ2​

数据量和模型参数误差的关系

模型参数可以看成是模型维度的数据统计量（例如模型就是预测值就是直接输出训练集的平均值，那么参数就直接是数据的平均），那么，当参数多了之后，相当于把数据分给不同的参数减少，这可能有点难以理解，可以想象成一个决策树，分支之后每个分支的数据量减少，分支越多，每个分支的数据量就越少。或者还可以换个角度理解，确定A参数之后在确定B参数，B参数的误差会因为A参数的误差而增大。所以参数越多，误差就越大。
正则化为什么可以降低泛化误差呢，因为正则化相当于给参数之间一定的关系，例如$l_1$l1​正则化相当于去掉一些参数，从而使得分配到每个参数上的数据量增多，而$l_2$l2​正则化相当于参数之间共同进退，把异常值的贡献平均分配到各个参数上，因而参数分配数据量就不是数据量除以参数个数了，不同参数之间的相关性使得数据“公用”到各个参数上。

虽然这个解释不是很严谨，但是我个人感觉比较容易理解和直观。

P.S. 我自己自瞎想的，如有错误，还请有缘人指正

No Free Lunch Theorem

若学习算法$L_a$La​在某些问题（数据集）上比学习算法$L_b$Lb​要好，那么必然存在另一些问题（数据集），在这些问题中$L_b$Lb​比$L_a$La​表现更好。
符号说明：

• $\Xi$Ξ:样本空间
• $H$H:假设空间
• $L_a$La​:学习算法
• $P(h|X,L_a)$P(h∣X,La​) : 算法$L_a$La​基于训练数据$X$X产生假设$h$h的概率
• $f$f:代表希望学得的真实目标函数
• ote是off-training error，即训练集外误差
• $E_{ote}(L_a|X,f)=\sum_h\sum_{x\in \Xi-X}P(x)I(h(x)≠f(x))P(h|X,L_a)$Eote​(La​∣X,f)=∑h​∑x∈Ξ−X​P(x)I(h(x)̸​=f(x))P(h∣X,La​)：算法$L_a$La​学得的假设在训练集外的所有样本上的误差的期望（这里的累加可以看作是积分的简化，积分更严谨的感觉；查阅文献后发现，该定理只是定义在有限的搜索空间，对无限搜索空间结论是否成立尚不清楚）

因为是存在性问题，我们就假设真实分布$(x,f(x))$(x,f(x))的$f$f在假设空间内均匀分布，那么
$E_f[E_{ote}(L_a|X,f)]=\sum_f\sum_h\sum_{x\in \Xi-X}P(x)I(h(x)≠f(x))P(h|X,L_a)P(f)$Ef​[Eote​(La​∣X,f)]=f∑​h∑​x∈Ξ−X∑​P(x)I(h(x)̸​=f(x))P(h∣X,La​)P(f)

$=\sum_{x\in \Xi-X}P(x)\sum_hP(h|X,L_a)\sum_fI(h(x)≠f(x))P(f)$=x∈Ξ−X∑​P(x)h∑​P(h∣X,La​)f∑​I(h(x)̸​=f(x))P(f)

$=\sum_{x\in \Xi-X}P(x)\sum_hP(h|X,L_a)\frac{2^{|\Xi|}}{2}$=x∈Ξ−X∑​P(x)h∑​P(h∣X,La​)22∣Ξ∣​

$=\frac{2^{|\Xi|}}{2}\sum_{x\in \Xi-X}P(x)$=22∣Ξ∣​x∈Ξ−X∑​P(x)

结果与算法$L_a$La​无关，说明在$f$f未知的情况下，没有任何一个算法比瞎猜强。

这个定理没啥实用性，但是体现了算法工程师存在的意义。在数据集未知的情况下调大厂的API跟瞎猜一个性质。在脱离实际意义情况下，空泛地谈论哪种算法好毫无意义，要谈论算法优劣必须针对具体学习问题。