内容来自于《机器学习》
子集搜索与评价
相关特征 无关特征
从给定的特征集合中选择出相关特征子集的过程，成为“特征选择”
特征选择的原因：
- 维数灾难
- 去除不相关特征往往会降低学习任务的难度。
冗余特征 redundant feature，它们所包含的信息能从其他特征中推演出来。
遍历所有可能的自己会导致组合爆炸
候选子集
子集搜索问题：给定特征集合{a1,a2,…,ad}，可以将每个特征看作一个候选子集，对这d个候选单特征子集进行评价，假定{a2}最优，于是将其看作第一轮的选定集；然后在上一轮选定集中加入一个特征，构成包含两个特征的候选子集，选择最优的两特征子集，作为本轮的选定集。如此反复，直到最优的候选k+1特征子集不如上一轮的选定集，则生成候选子集。这样逐渐增加相关特征的策略称为前向搜索。类似的，如果从完整的特征集合开始，每次尝试减少一个无关特征，这样的策略称为后向搜索。将前向与后向搜索集合起来，这样的策略称为双向搜索。
子集评价：
计算属性子集的信息增益，信息增益越大，包含的有助于分类的信息越多。对每个候选特征子集，可以基于训练数据集来计算信息增益，以此作为评价准则。
将特征子集搜索机制与子集评价机制相结合，可以得到特征选择方法。
常见的特征选择方法分为：过滤式filter、包裹式wrapper、嵌入式embedding。
过滤式选择
过滤式方法先对数据集进行特征选择，然后训练学习器，特征选择过程与后续学习器无关。
Relief(relevant features)是一种著名的过滤式特征选择方法，该方法设计了一个相关统计量来度量特征的重要性。该统计量是一个向量，其中每个分类分别对应于一个初始特征，而特征子集的重要性则是由自己种每个特征所对应的相关统计分量之和来决定。于是，最终只需要指定一个阈值，然后选择比阈值大的相关统计分量所对应特征即可。也可指定欲选取的特征个数k，然后选择相关统计量分量最大的k个特征。
显然，如何确定相关统计量，给定训练集{(x1,y1),(x2,y2),…,(xm,ym)}，对每个示例，先在xi的同类样本中寻找最近邻xi,nh，称为猜中近邻（near-hit），再从xi的异类样本中寻找其最近邻xi,nm，称为猜错近邻（near-miss），然后相关统计量对应于属性j的分量：
Relief只需在数据集上采样而不必在整个数据集上估计相关统计量。显然，Relief的时间开销随着采样次数以及原始特征数线性增长，因此是一个运行效率很高的过滤式特征选择算法。
Relief是为二分类问题设计的，其扩展变体Relief-F能处理多分类问题。
包裹式选择
与过滤式的特征选择不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器性能作为特征子集的评价准则。换言之，包裹式特征选择的目的就是为给定学习器选择最有利于其性能、量身定做的特征子集。
从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好，但另一方面，由于在特征选择过程中需多次训练学习器，因此包裹式特征选择的计算开销通常比过滤式特征选择大的多。
LVW（Las Vegas Wrapper）是一个典型的包裹式特征选择方法。在拉斯维加斯方法（Las Vegas method）框架下使用随机策略来进行子集搜索，并以最终分类器的误差为特征子集评价准则。
由于LVW算法中特征子集搜索采用了随机策略，而每次特征子集评价都需训练学习器，计算开销很大，因此算法设置了停止条件控制参数T。然而，整个LVW算法是基于拉斯维加斯方法框架，若初始特征数很多，T设置较大，则算法可能运行很长时间都达不到停止条件。换言之，若有运行时间限制，则有可能给不出解。
嵌入式选择与L1正则化
在过滤式和包裹式特征选择方法中，特征选择过程与学习器训练过程有明显的分别，与此不同，嵌入式特征选择是将特征选择与学习器的训练过程融为一体，两者在同一个优化过程中完成，即在学习器训练过程中自动地进行了特征选择。
L2范数正则化
岭回归（ridge regression）
Lp范数。
L1范数与L2范数正则化都有助于降低过拟合风险，但前者还会带来一个额外的好处，比后者更易于获得稀疏解，即它求得的w会有更少的非零分量。
注意到w取得稀疏解意味着初始的d个特征中仅有对应着w的非零分量的特征才会出现在最终模型中，于是，求解L1范数正则化的结果是得到了仅采用一部分初始特征的模型，换言之，基于L1正则化的学习方法就是一种嵌入式特征选择方法，其特征选择过程与学习器训练过程融为一体，同时完成。
L1正则化问题的求解课使用近端梯度下降（Proximal Dradient Descent,PGD）.
稀疏表示与字典学习
线性支持向量机之所以能在文本数据上有很好的性能，恰是由于文本数据在使用上述字频表示后具有高度的稀疏性，使大多数问题变得线性可分。同时，稀疏样本并不会造成存储上的巨大负责，因为稀疏矩阵已有很多高效的存储方法。
在一般学习任务中并没有字典，需要学习出一个字典，为普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表示形式，从而使学习任务得以简化，模型复杂度得以降低，常称为字典学习（dictionary learning）,亦称为稀疏编码(sparse coding)，这两个称谓稍有差别，字典学习更侧重于学得字典的过程，而稀疏编码更侧重于对样本进行稀疏表达的过程。两者通常在同一个优化求解的过程中完成的。
在字典学习过程中，用户能通过设置词汇量k的大小来控制字典的规模，从而影响到稀疏程度。
压缩感知
压缩感知（compressed sensing）
奈奎斯特（Nyquist）采样定理
压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。通常认为，压缩感知分为“感知测量”和“重构恢复”两个阶段。感知测量关注如何对原始信号进行处理以获得稀疏样本表示，重构恢复关注的是如何基于稀疏性从少量观测中会发原信号。
限定等距性（Restricted Isometry Property,RIP）
矩阵补全（matrix completion）技术