特征选择和稀疏学习
子集搜索与评价
对象都有很多属性来描述，属性也称为特征（feature），用于刻画对象的某一个特性。对一个学习任务而言，有些属性是关键有用的，而有些属性则可能不必要纳入训练数据。对当前学习任务有用的属性称为相关特征（relevant feature）、无用的属性称为无关特征（irrelevantfeature）。从给定的特征集合中选择出相关特征子集的过程，称为特征选择（feature selection）。
特征选择时一个数据预处理（data preprocessing）过程，在现实机器学习任务中，基于避免维数灾难和降低不相关特征带来的学习难度，在获得数据之后往往会先进行特征选择再训练学习器。当然特征选择要确保不丢失重要特征。给定数据集，若学习任务不同，则相关特征很可能不同，因此无关特征是指与当前学习任务无关。若一个属性是从其他属性中推演而出的，则成为冗余特征（redundant feature）。
假定数据中不涉及冗余特征，并假定初始的特征集包含了所有的重要信息，那么如何进行特征选择呢？要从初始的特征集合中选取一个包含了所有重要信息的特征子集，若没有任何领域知识作为先验假设，那就只有遍历所有子集，这计算开销相当大，一旦属性稍多就会出现组合爆炸。较为可行的一个做法是：先产生一个候选子集，然后评价，基于评价结果产生下一轮候选子集，再评价…如此下去，直至无法找到更好的候选子集。这个做法就关系两个很重要的过程：如何评价候选子集的优劣？又如何根据评价结果遴选下一轮候选子集呢？
1）子集搜索（subsetsearch）
给定特征集合{a1,a2,…,ad}，可将每个特征看做一个候选子集，对这d个候选单特征子集进行评价，选出一个最优的，然后加入一个特征，构成包含两个特征的候选子集…假定在k 1轮时，最后的候选（k 1）个特征子集不如上一轮的选定集，则停止生成候选子集，并将上一轮选定的k特征集合作为特征选择结果。上述这种逐渐增加相关特征的策略称为前向（forward）搜索。如果从完整的特征集合开始，每次尝试去掉一个无关特征，这样逐渐减少特征的策略称为后向（backward）搜索。也可将前后和后向搜索结合起来，每一轮逐渐增加选定相关特征、同时减少无关特征，这样的策略称为双向（bidirectional）搜索。
上述策略是贪心的，因为它们仅仅考虑了使本轮选定集最优，如在第三轮假定a5优于a6，于是选定集为{a2,a4,a5}，然后在第四轮却可能是{a2,a4,a6,a8}优于所有的{a2,a4,a5,ai}。要解决这个问题，就只能进行穷举搜索。
2）子集评价（subsetevaluation）
给定数据集D，假定D中第i类样本所占的比例为pi(i=1,2,…,|y|)，假定样本属性均为离散型。对属性子集A，假定根据其取值将D分成了V个子集{D1,D2,…,DV}，每个子集中的样本在A上取值相同，计算属性子集A的信息增益：
信息增益Gain(A)越大，意味着特征子集A包含的欧主语分类的信息越多。如此，对每个候选特征子集，可基于训练数据集D来计算其信息增益，以此作为评价准则。
更一般的，特征子集A实际上确定了对数据集D的一个划分，每个划分区域对应着A上的一个取值，而样本标记信息y则对应对D的真实划分，通过估算这两个划分的差异，就能对A进行评价。与y对应的划分的差异越小，则说明A越好。信息熵仅是判断这个差异的一个途径，其他能判断两个划分差异的机制都能用于特征子集评价。
综上两点，将特征子集搜索机制与子集评价机制结合，就可得到特征选择方法。如将前向搜索与信息熵结合，与决策树相似。事实上，决策树也可用于特征选择，树节点的划分属性所组成的集合就是选择出的特征子集。其他的特征选择方法未必如决策树般特征选择这么明显，不过在本质上都显式或隐式地结合了某种或多种子集搜索机制和子集评价机制。
常见的特征选择方法大致可分三类：过滤式（filter）、包裹式（wrapper）和嵌入式（embedding）。
过滤式选择
过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。先用特征选择过程对初始特征进行过滤，再用过滤后的特征训练模型。Relief是一种著名的过滤式特征选择方法，该方法设计了一个相关统计量来度量特征的重要性。该统计量是一个向量，其每个分量对应于一个初始特征，而特征子集的重要性则是由子集中每个特征所对应的相关统计量分量之和决定。指定一个阈值，选择比阈值大的相关统计量分量所对应的特征即可；也可指定要选择的特征个数k，然后选择相关统计量分量最大的k个特征。
Relief的关键是如何确定相关统计量。给定训练集{(x 1,y 1),(x 2,y 2),…,(x m,y m)}，对每个示例x i，Relief先在x i的同类样本中寻找其最近邻x i,nh，称为猜中近邻（near-hit）；再从x i的异类样本中寻找其最近邻x i,nm，称为猜错近邻（near-miss）；相关统计量对应于属性j的分量为：
包裹式选择
和过滤式特征选择不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器性能作为特征子集的评价准则。换言之，包裹式特征选择的目的就是为给定学习器选择最有利于其性能、量身定做的特征子集。一般而言，包裹式特征选择方法直接针对给定学习器进行优化，从最终学习器性能来说，包裹式特征选择比过滤式特征选择更好，但由于在特征选择过程中要多次训练学习器，其计算开销也比过滤式特征选大很多。
LVW(LasVegas Wrapper)是一个典型的包裹式特征选择方法，它在拉斯维加斯方法框架下随用随机策略进行子集搜索，并以最终分类器的误差为特征子集评价准则。算法描述如下：
输入：数据集D；
特征集A；
学习算法Σ；
停止条件控制参数T。
过程：
E=∞；//初始误差无穷大
D=|A|；
A*=A；
t=0；
while t<T do
随机产生特征子集A’；
d’=|A’|；
E’=CrossValidation(Σ(DA’))；//在特征子集A’上通过交叉验证估计学习器误差
if (E’<E) 或 ((E’=E) 与（d’<d）) then //误差小于原来的，更新
t=0;
E=E’;
d=d’;
A*=A’;
else t=t 1;
end if
end while
输出：特征子集A*
算法中通过在数据集D上使用交叉验证法CrossValidation来估计学习器Σ的误差，这个误差是在仅考虑特征子集A’时得到的，即特征子集A’上的误差，若它比当前特征子集A上的误差更小，或者误差相当但A’中包含的特征数更少，则将A’保留下来。
由于LVW算法中特征子集搜索采用了随机策略，而每次特征子集评价都需训练学习器，计算开销很大，因此算法设置了停止条件控制参数T。然而，整个LVW算法是基于拉斯维加斯方法框架，若初始特征数很多（即|A|很大）、T设置较大，则算法可能运行很长时间都打不到停止条件。就是，若有时间限制，可能无解。
注意：拉斯维加斯方法和蒙特卡罗方法是两个以著名赌城名字命名的随机化方法。两者主要区别是：若有时间限制，则拉斯维加斯方法或者给出满足要求的解，或者不给出解；而蒙特卡罗方法一定会给出解，虽然给出的解未必满足要求。若无时间限制，则两者都能给出满足要求的解。
嵌入式选择与L1正则化
在过滤式和包裹式特征选择方法中，特征选择过程与学习器训练过程有明显的分别；与此不同，嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，即在学习器训练过程中自动地进行了特征选择。
用特征子集评价与学习器训练的前后关系来来说，过滤式是在学习器训练前完成特征子集选择和评价；包裹式是在学习器训练后评价特征子集从而选择特征；嵌入式则是在学习器训练过程中同步评价并选择特征子集。
稀疏表示与字典学习
把数据集D看成一个矩阵，每行对应一个样本，每列对应一个特征。特征选择所考虑的问题是特征具有稀疏性，即矩阵中的许多列与当前学习任务无关，通过特征选择去除这些列，则学习器训练过程仅需在叫小的矩阵上进行，学习任务的难度可能有所降低，设计的计算和存储开销会减少，学得模型的可解释性也会提高。
对于稀疏性，还存在一种情况是：D所对应的矩阵中存在很多零元素，这些零元素不是整行或整列存在。这和直接去掉其中一个或若干个列的稀疏性不一样，直接去除整列，是做了无关性特征剔除，不管样本是否在这个特征上是否为零。这种存在零元素情况的矩阵，在学习任务中有不少，如文档分类任务，将每个文档看做一个样本，每个字或词作为一个特征，字或词在文档中出现的频率或次数作为特征的取值；即D所对应的矩阵，每行是一个文档，每列是一个字或词，行列交汇点就是某个字或词在某文档中出现的频率或次数。《康熙词典》中有47035个汉字，就是矩阵有4万多个列，就算是仅考虑《现代汉语常用字表》中的汉字，矩阵也有3500列。对给定的文档，相当多的字是不会出现在这个文档中，矩阵的每一行有大量的零元素，不同的文档，零元素出现的列也不相同。
如果样本具有这样的稀疏表达形式时，对学习任务来说是有好处的。如线性支持向量机之所以在文档数据上有很好的性能，恰是由于文本数据在使用上述的字频后具有高度稀疏性，使大多数问题变得线性可分。同时，稀疏样本也不会造成存储上的巨大负担，因为稀疏矩阵有很多高效存储方法。
若给定的数据集D是稠密的，即普通非稀疏数据，能否转化为稀疏表示（sparserepresentation）形式，从而享有稀疏性所带来的好处呢？自然这种稀疏表示，是恰当稀疏，而不是过度稀疏。如汉语文档，基于《现代汉语常用字表》得到的可能是恰当稀疏，即其稀疏性足以让学习任务变得简单可行，而基于《康熙词典》则可能是过度稀疏，与前者相比，也许并未给学习任务带来更多好处。
不过，一般的学习任务，如图像分类，并没有《现代汉语常用字表》恰有稀疏表示，需要通过学习一个字典。为普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表示形式，从而使学习任务得以简化，模型复杂度得以降低，称为字典学习（dictionary learning），也称稀疏编码（sparse coding）。实际上，字典学习侧重于学得字典的过程，而稀疏编码则侧重于对样本进行稀疏表达的过程；不过二者在同一优化求解过程中完成，因此不做区分。下面是说明字典学习。
给定数据集{x1,x2,…,x m}，字典学习最简单的形式为：
压缩感知
在现实任务中，常有根据部分信息来恢复全部信息的需求，如在数据通讯中将模拟信号转换为数字信号，根据奈奎斯特（Nyquist）采样定理，令采样频率达到模拟信号最高频率的两倍，则采样后的数字信号就保留了模拟信号的全部信息；换言之，由此获得的数字信号可精确重构原模拟信号。然而，为了便于传输、存储，在实践中人们通常对采样的数字信号进行压缩，这有可能损失一些信息，而在信号传输过程中，由于信道出现丢包等问题，又可能损失部分信息；如此，接收方基于收到的信号，能否精确地重构出原信号呢？压缩感知（compressed sensing）为解决此类问题提供了思路。
与特征选择、稀疏表示不同，压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。通常认为，压缩感知分为感知测量和重构恢复两个阶段。感知测量关注如何对原始信号进行处理以获得稀疏样本表示，涉及傅里叶变换、小波变换以及字典学习、稀疏编码等；重构恢复关注的是如何基于稀疏性从少量观测中恢复原信号，这是压缩感知的精髓。压缩感知的理论比较复杂，文中扼要介绍了限定等距性（Restricted Isometry Property,RIP）。
本章节总的目的是奔着两个目的，一个是减少样本训练的量；一个是减少存储和计算开销；这就提出了三个思路：特征选择、稀疏表示、压缩感知。特征选择有三种方法，过滤式、包裹式、嵌入式，主要思想就是去掉与学习任务无关的属性；稀疏表示，则从样本表示上出发，通过矩阵支持；压缩感知，数据压缩方面研究。要掌握这个章节，还是要掌握矩阵数学基础知识；也明显感觉出，机器学习的数学基础理论在根本上到了可用极致，后面要深入，就要数学突破。或者说，在已知可用的数学理论上，都用上了，后面要突破，有赖于数学基础理论的再突破。
从降维和度量学习开始，介绍算法的基础理论，这个对数学的要求更高了，要做很多课外数学功课来辅助理解，不过仍然感觉不深入，有种浅尝辄止的感觉，没有痛快淋漓的感觉。说白了，还是欠缺数学基础理论的支持，没有这个，机器学习的基础理论就只能肤浅理解，再辅以具体算法模型应用。
实际上，降维和特征选择都是减少冗余样本量保证有效样本量用于训练学习，矩阵在这中间发挥了很大作用。基础矩阵理论的应用是根本。我大致将这分成四个层面：1）数学基础理论研究，如能出泰勒展开式、奇异分解等；2）数学知识应用，如降维和特征选择用到具体的矩阵知识；3）机器学习算法理论研究，这层和第2层紧密相关，就是用数学知识来研究算法基础理论，如能推导范数最小化；4）机器学习具体算法应用，如SVM、决策树等再实际学习任务中的应用。
就目前个人而言，勉强可以在第3层，但要到第2层就已经不太可能，除非重新掌握其完整的数学逻辑。而只有突破第2层，才能到第1层，称为真正的大师。目前应集中第4层，从而引导后续的突破。
