p247 - p266
哈哈哈感觉今天看书的状态不错
看来有希望把欠的两天都补上呀
不多说了进入第11章

第11章 特征选择与稀疏学习

11.1 子集搜索与评价

从给定的特征集合中选择相关特征子集的过程，称为“特征选择”。
特征选择是一个重要的数据预处理过程。
能降低“维数灾难”风险，并有降维的效果。

处理高维数据的两大主流技术：“降维”、“特征选择”。

“无关特征”，“冗余特征”？
如果“冗余特征”对应了一个中间过程，那么这个“冗余过程”是有益的。

怎么选特征？
产生一个“候选子集”，评价出好坏，基于评价产生下一个候选子集，再评价，直到收敛。
两个问题：
1）如何获取候选子集？
“子集搜索问题”。前向（非常像决策树）、后向、双向。
贪心策略，并不能全局最优。

2）如何评价好坏？
使用信息增益。
实际上，特征子集对应了一个对数据集D的划分，真实label对应了一个划分。想办法比较这两个划分的差异就能评价好坏。

特征搜索+子集评价：特征选择。
常见分为三类：过滤式、包裹式、嵌入式。

11.2 过滤式选择

过滤式方法先对数据集进行特征选择，再训练学习器。特征选择和学习器无关。

Relief：著名的特征选择方法。
设计了一个“相关统计量”来度量特征的重要性。

对每个样本先选择最近的同类样本，在选择最近的不同类样本。
相关统计量对于每个属性j的计算方法：p250 式11.3

FRelief：对多分类的扩展。

11.3 包裹式选择

包裹式选择考虑学习器，把学习器的性能作为评价指标。
也就是要给学习器选择最有利于其性能，量身定做的特征子集。

开销自然会比过滤式大。

LVW：典型的包裹式选择方法。（拉斯维加斯框架下）
伪码见p251

LVW中特征子集搜索采用了随机策略，每次评价都得重新训练学习器，故计算开销是很大的。
同时，由于是拉斯维加斯框架，故可能给不出解。

11.4 嵌入式选择和L1正则化

嵌入式：学习器训练过程中自动进行了特征选择。

当维数较大样本较少，容易陷入过拟合。
故加入正则项。

而L1范数是比L2更容易得到更稀疏的解的，也就是说w中0更多。也就是选择了特征。
p252 式11.7称为LASSO

从而基于L1正则化的学习方法就是一种嵌入式特征选择方法

L1正则化问题的求解可使用近端梯度下降方法（PGD）。详细原理见p253-254。
PGD可以使LASSO和其他基于L1范数最小化的方法得以快速求解。

11.5 稀疏表示与字典学习