Andrew Ng机器学习课程9

首先以一个工匠为例，说明要成为一个出色的工匠，就需要掌握各种工具的使用，才能知道在具体的任务中选择什么工具来做。所以今天要讲的就是机器学习的理论部分。

bias variance trade off，以线性回归为例，underfitting对应high的bias（偏差），overfitting对应high的variance（方差），主要是拟合出了一些奇怪的特性。同样的对于分类问题，复杂的分类边界（decision boundary）也可能出现high variance，而简单的分类边界出现high bias。

training data set：(x(i),y(i))独立同分布，定义了一个简单的训练误差为犯错误的个数所占样本数的比例，叫做经验风险最小化（ERM）。这样的话是一个非凸优化问题，比较困难，通常采用其近似形似进行。利用e^作为对generalization error的估计，我们最关心的还是prediction error，也就是在实际使用中的error，叫做generalization error。跟台大机器学习课程一样，引入了霍弗丁不等式（hoffeding）来说明一个upper bound，独立同分布的变量的观测值的均值估计的量与真实的量之间的差大于某一个值得概率要小于某一个与差值相关的概率，说明一个非常有意义的事情，当观测的样本数量逐渐增加，这个概率的upper bound将指数下降。

ϕ^= 1 m \sum x i

p (| ϕ - ϕ^| > γ) \leq 2 e x p (- 2 γ 2 m)

下面主要说明在何种条件下能够通过training error作为一个generalization error的很好估计，通过hoffeding不等式建立一个upper bound的关系，有利于推出如何的训练条件能够保证是好的估计。最后得到了如下形式的联系：

p (| e (h j) - e^(h j) | > γ) \leq 2 e x p (- 2 γ 2 m)

这是对于一个hypothesis

hj来说的，后面要推广到对于hypothesis set中的k个都成立，然后得到了如下形式的泛化指标：

p (在 h y p o t h e s i s s e t 中 不 存 在 | e (h j) - e^(h j) | > γ) \geq 1 - 2 k \times e x p (- 2 γ 2 m)

上式说明了一个一致性收敛问题，就是说在hypothesis　set中至少以概率为

1−2k×exp(−2γ2m)得到的训练误差的估计

e^(h)与generalization error

e(h)之间的差值在

γ内，这就是uniform convergence 的结果。
后面又引入了sample complexity即样本复杂度bound，说明的是为了达到对误差的一定bound或需要多少训练样本。公式中可以看出，log选项说明对于增加模型复杂度即Hypothesis的数量k，而在保证同样的error bound时，样本数量不用增加太多，因为log是增长速度最慢的一个函数了。

training error会随着hypothesis model complexity的增加而下降，而generalization error随之下降后增加，对应着high bias到high variance，即underfitting到overfitting

2015-9-10 艺少