笔记：http://lib.csdn.net/article/machinelearning/1079
本讲大纲：
1.VC维（VC dimension）
2.模型选择（model selection）
—交叉验证（cross validation）
—特征选择（feature selection）
1. VC维
VC(H)代表可以在任意标签的情况下仍可以被线性分割的最大集合。
在2D情况下，VC(H)=3。
在VC维的定义下，为了证明ＶＣ（Ｈ）至少是ｄ，我们要证明Ｈ能分开至少一个大小为ｄ的集合．
重要定理：
换句话来说，如果猜想有有限的VC维，当ｍ足够大时会有一致收敛性．
推论：
换句话说，用H训练好的训练样本数量和VC维是线性的．结果表明，对大部分的猜想类，VC维（假设合理的参数化）和参数的数量大致也是线性相关的．把这两个放到一起，可以说（对于最小化训练误差的算法来说）需要的训练样本的数量大致和参数的类型是线性的．
VC维到底有什么用？
如果假设空间中的hypothesis数是固定的，经过证明可以得到：
也就是说，H有限且m很大时，真实误差的上界是有限的，也就是说，通过训练，我们可以接近真实误差，从理论上说明机器是有学习能力的。
但是如果H无穷大呢？
因此又证明了如下公式：
这样真是误差就与H无关，而与VC(H)有关了。所以说，VC维是用来证明误差的上界的，知道常用的分类的误差上界，就会对分类器的分类效果有进一步的认识，从而选择最优的分类器。
</br>
2. 模型选择
然而VC维在理论上证明误差上界，可是真实误差有时候和理论上的误差有一定差距，所以常用的模型选择方法有
- CV(Cross-validation) 最常用，且易理解
- AIC(Akaike Information Criterion)
- BIC(Bayesian Information Critrion)
**交叉验证(Cross-validation) **
保留交叉验证
a. 随机把训练集Ｓ分成两个子集，Strain(70%)和Scv(30%).Scv是保留验证集。
b. 用Strain训练每个模型，得到猜想hi.
c. 选择在交叉验证集中有最小错误的猜想。
</br>
交叉验证的缺点是浪费了30%的数据，即使我们最后用整个训练集去训练模型. 在数据充足并且很容易获得的情况下，这是好的，但是如果数据是很稀少的，我们需要采用另外一种方式了.-
k-fold交叉验证
a. 随机把S分成k个子集，每个有m/k个训练样本，为S1,…,Sk;
b. 对每个模型，我们这样评价：
c. 选择具有最低估计泛化误差的模型，并且用整个数据集对模型进行训练，最后输出的猜想就是我们的答案.
一个对fold典型的选择是k=10.
-
留一交叉验证
当数据非常稀有时，极端的选择是把k=m，为了尽可能使留下来的数据少，这种情况下我们会用除了一个之外的数据集进行训练，剩下的用来测试，k个错误的平均值用来作为模型的估计泛化误差.
即使这在边说的是交叉验证用来进行模型选择，但是只有单个模型时也可以用来评价模型的好坏.
特征选择
工程上的方法：
参考：https://www.zhihu.com/question/28641663/answer/41653367
- 计算每一个特征与响应变量的相关性：工程上常用的手段有计算皮尔逊系数和互信息系数，皮尔逊系数只能衡量线性相关性而互信息系数能够很好地度量各种相关性，但是计算相对复杂一些，好在很多toolkit里边都包含了这个工具（如sklearn的MINE），得到相关性之后就可以排序选择特征了；
- 构建单个特征的模型，通过模型的准确性为特征排序，借此来选择特征，另外，记得JMLR'03上有一篇论文介绍了一种基于决策树的特征选择方法，本质上是等价的。当选择到了目标特征之后，再用来训练最终的模型；
- 通过L1正则项来选择特征：L1正则方法具有稀疏解的特性，因此天然具备特征选择的特性，但是要注意，L1没有选到的特征不代表不重要，原因是两个具有高相关性的特征可能只保留了一个，如果要确定哪个特征重要应再通过L2正则方法交叉检验；
- 训练能够对特征打分的预选模型：RandomForest和Logistic Regression等都能对模型的特征打分，通过打分获得相关性后再训练最终模型；
- 通过特征组合后再来选择特征：如对用户id和用户特征最组合来获得较大的特征集再来选择特征，这种做法在推荐系统和广告系统中比较常见，这也是所谓亿级甚至十亿级特征的主要来源，原因是用户数据比较稀疏，组合特征能够同时兼顾全局模型和个性化模型，这个问题有机会可以展开讲。
- 通过深度学习来进行特征选择：目前这种手段正在随着深度学习的流行而成为一种手段，尤其是在计算机视觉领域，原因是深度学习具有自动学习特征的能力，这也是深度学习又叫unsupervised feature learning的原因。从深度学习模型中选择某一神经层的特征后就可以用来进行最终目标模型的训练了。
