机器学习(周志华) 参考答案 第十二章 计算理论学习
机器学习(周志华西瓜书) 参考答案 总目录
http://blog.csdn.net/icefire_tyh/article/details/52064910
从三个方面来确定泛化误差的上界，确定学习的可行性。
1.试证明Jensen不等式：对任意凸函数f(x)，有f(E(x))≤E(f(x))。
显然，对任意凸函数f(x)，必然有
取，
所以：
以此类推得：
2.试证明引理12.1。
引理(12.1)若训练集D包含m个从分布Ɗ上独立同分布采样而得的样例，,则对任意
，有
。
已知Hoeffding不等式：若为m个独立的随机变量，且满足
，则对任意
，有
。
将替换为损失函数
，显然
，且独立。
带入Hoeffding不等式得：
其中
所以有：。
3.试证明推论12.1。
推论(12.1)：若训练集D包含m个从分布上独立同分布采样而得的样例，
,则对任意
，式(12.18)以至少
的概率成立。
式(12.18)：
有引理(12.1)可知，成立
即
取，则
所以的概率不小于
整理得：以至少
的概率成立。
4.试证明：空间中线性超平面构成的假设空间的VC维是d+1。
线性空间超平面公式为，超平面将空间分为二块，即二分类。
取空间中不共超平面的d+1个点，为了简化，假设是各坐标轴基向量和原点。
设A是(d+1)*(d+1)矩阵，第一列是b的系数1,第二列起是各个点的坐标。
要证明的是，对于任意的，存在
使得
成立。
由于X是可逆矩阵，可以得使得
成立。所以VC维至少是d+1。
由于R^d空间中的d+2个点必然线性相关，将第d+2个点写成前n+1个点的线性组合：
，
则：
对任意的，取
，得到
恒成立，所以此时
无法被打散。
即VC维小于d+2。
所以空间中线性超平面构成的假设空间的VC维是d+1。
5.试计算决策树桩假设空间的VC维。
如果是非连续属性，通过决策树一次划分无法确定节点个数，可能导致VC维无限大。
仅考虑连续属性单变量的决策树桩。
由于决策树的划分是与坐标轴平行的超平面，显然平面上的2个点是可以被打散的，即VC维大于等于2。
对于平面的3各点，如果其中两个点的连线与一条坐标轴平行，另两个点的连线与另一坐标轴平行。比如(0,0),(0,1),(1,0)三个点，无法通过一个与坐标轴平行的超平面来划分。所以VC维小于3。
所以决策树桩假设空间的VC维是2。
6.决策树分类器的假设空间VC维可以为无穷大。
由于决策树如果不限制伸展，会包含整个假设空间。对任意多的样本，决策树可以使得训练误差为0，所以VC维是无穷大。
7.试证明：最近邻分类器的假设空间VC维为无穷大。
最近邻分类器，也就是1NN，总是会把自己分类成自己的样本分类，所以对任何数目的样本训练误差恒为0。如图所示
8.试证明常数函数c的Rademacher的复杂度为0。
常数函数c的Rademacher的复杂度为
其中是随机变量，以0.5的概率取1，0.5的概率取-1。
所以
9.给定函数空间，试证明Rademacher复杂度
。
当时，
当时，
所以
即：。
10.考虑定理12.8，试讨论通过交叉验证法来估计学习算法泛化能力的合理性。
K折交叉验证，当K=m时，就成了留一法。
由式(12.59)：
取时，可以得到：
以至少
的概率成立，所以留一法有不错的泛化能力。
前提条件是对于损失函数l满足
均匀稳定性，且
应该是
这个量级。
仅拿出一个样本，可以保证很小的。
随着K的减小，训练用的样本会减少，逐渐增大，当
超出
量级时，交叉验证就变得不合理了。
