【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.包裹式选择
与过滤式特征选择不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。换言之，包裹式特征选择的目的就是为给定学习器选择最有利于其性能、“量身定做”的特征子集。
一般而言，由于包裹式特征选择方法直接针对给定学习器进行优化，因此从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好，但另一方面，由于在特征选择过程中需多次训练学习器，因此包裹式特征选择的计算开销通常比过滤式特征选择大得多。
LVW（Las Vegas Wrapper）是一个典型的包裹式特征选择方法。它在拉斯维加斯方法（Las Vegas method）框架下使用随机策略来进行子集搜索，并以最终分类器的误差为特征子集评价准则。算法描述如图11.1所示。
拉斯维加斯方法和蒙特卡罗方法是两个以著名赌城名字命名的随机化方法，两者的主要区别是：若有时间限制，则拉斯维加斯方法或者给出满足要求的解，或者不给出解，而蒙特卡罗方法一定会给出解，虽然给出的解未必满足要求；若无时间限制，则两者都能给出满足要求的解。
图11.1算法第8行是通过在数据集$D$上，使用交叉验证法来估计学习器$\mathfrak{L}$的误差，注意这个误差是在仅考虑特征子集$A’$时得到的，即特征子集$A’$上的误差，若它比当前特征子集$A$上的误差更小，或误差相当但$A’$中包含的特征数更少，则将$A’$保留下来。
需注意的是，由于LVW算法中特征子集搜索采用了随机策略，而每次特征子集评价都需训练学习器，计算开销很大，因此算法设置了停止条件控制参数$T$。然而，整个LVW算法是基于拉斯维加斯方法框架，若初始特征数很多（即$\lvert A \rvert$很大）、$T$设置较大，则算法可能运行很长时间都达不到停止条件。换言之，若有运行时间限制，则有可能给不出解。
