十一章

一、子集搜索与评价
特征选择是一个重要的 “数据预处理” （data preprocessing）过程，在现实机器学习任务中在获得数据之后通常先进行特征选择，此后再训练学习器。

我们在现实任务中经常会遇到维数灾难问题，这是由于属性过多而造成的，若能从中选择出重要的特征， 使得后续学习过程仅需在一部分特征上构建模型，则维数灾难问题会大为减轻。
特征选择过程必须确保不丢失重要特征，否则后续学习过程会因为重要信息的缺失而无法获得好的性能。

子集搜索
子集评价
二、过滤式选择
过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。

Relief是一种著名的过滤式 特征选择方法，该方法设计了一个 “相关统计量” 来度量特征的重要性。

Relief是为二分类问题设计的，其扩展变体Relief-F能处理多分类问题。

三、包裹式选择
与过滤式特征选择不考虑后续学斗器不同，包裹式特征选择直接把最终将要使用的学习器的性能作为特征于集的评价准则。换言之，包裹式特征选择的目的就是为给定学习器选择最有利于其性能、 “ 量身定做” 的特征子集 。

LVW是一个典型的包裹式特征选择方法。

四、嵌入式选择与L 1 L_1L 
1
    
 正则化
嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，即在学习器训练过程中自动地进行了特征选择。

L 1 L_1L 
1
    
 范数和L 2 L_2L 
2
    
 范数正则化都有助于降低过拟合风险，但前者还会带来一个额外的好处：它比后者更易于获得 “ 稀疏” （sparse）解，即它求得的ω ωω会有更少的非零分量。

五、稀疏表示与字典学习
不妨把数据集D DD考虑成一个矩阵，其每行对应于一个样本，每列对应于一个特征。特征选择所考虑的问题是特征具有 “稀疏性” ，即矩阵中的许多列与当前学习任务无关，通过特征选择去除这些列，则学习器训练过程仅需在较小的矩阵上进行，学习任务的难度可能有所降低，涉及的计算和存储开销会减少， 学得模型的可解释性也会提高。

为普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表示形式，从而使学习任务得以简化，模型复杂度得以降低，通常称为 “字典学习” 。

六、压缩感知
在现实任务中，我们常希望根据部分信息来恢复全部信息。例如在数据通讯中要将模拟信号转换为数字信号，根据奈奎斯特（Nyquist） 采样定理，令采样频率达到模拟信号最高频率的两倍，则采样后的数字信号就保留了模拟信号的全部信息；换言之 ，由此获得的数字信号能精确重构原模拟信号。

与特征选择、 稀疏表示不同，压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。

感知测量
重构恢复


十二

一、基础知识
计算学习理论（computational learning theory）研究的是关于通过计算来进行学习的理论。

常用的几个不等式：

Jensen不等式
Hoeffding不等式
McDiarmid不等式
二、PAC学习
算学习理论中最基本的是概率近似正确（PAC）学习理论。


在这里插入图片描述
在这里插入图片描述

在这里插入图片描述




三、有限假设空间
可分情形
不可分情形


四、VC维
现实学习任务所面临的通常是无限假设空间，欲对此种情形的可学习性进行研究，需度量假设壁间的复杂度．最常见的办法是考虑假设空间的 “vc维 ” 。

增长函数
对分
打散
五、Rademacher复杂度
Rademacher复杂度（Rademachercomplexity）是另一种刻画假设空间复杂度的途径，与vc维不同的是，它在一定程度上考虑了数据分布。

六、稳定性
算法的 “稳定性” 考察的是算法在输入发生变化时，输出是否会随之发生较大的变化。

通过移除或者替换，来看稳定性。

要注意到稳定性与假设空间并非无关。