ch11特征选择与稀疏学习-周志华

徐淼第十一章：特征选择与稀疏学习特征特征描述物体的属性特征的分类相关特征:对当前学习任务有用的属性无关特征:与当前学习任务无关的属性冗余特征*:其所包含信息能由其他特征推演出来*为简化讨论，本章暂不涉及冗余特征例子：西瓜的特征西瓜的特征颜色纹理触感根蒂声音相关特征无关特征好瓜坏瓜当前任务：西瓜是否是好瓜特征选择特征选择从给定的特征集合中选出任务相关特征子集必须确保不丢失重要特征原因减轻维度灾难：在少量属性上构建模型降低学习难度：留下关键信息例子：判断是否好瓜时的特征选择西瓜的特征颜色纹理触感根蒂声音相关特征无关特征好瓜坏瓜当前任务：西瓜是否是好瓜特征选择：选择当前任务相关特征特征选择的一般方法遍历所有可能的子集计算上遭遇组合爆炸，不可行可行方法产生初始候选子集评价候选子集的好坏基于评价结果产生下一个候选子集两个关键环节：子集搜索和子集评价子集搜索前向搜索：逐渐增加相关特征后向搜索：从完整的特征集合开始，逐渐减少特征双向搜索：每一轮逐渐增加相关特征，同时减少无关特征用贪心策略选择包含重要信息的特征子集特征集合当前最优子集优于上一轮最优子集？YN前向搜索最优子集初始为空集，特征集合初始时包括所有给定特征结束子集评价特征子集确定了对数据集的一个划分每个划分区域对应着特征子集的某种取值样本标记对应着对数据集的真实划分通过估算这两个划分的差异，就能对特征子集进行评价；与样本标记对应的划分的差异越小，则说明当前特征子集越好用信息熵进行子集评价(A)=(D)¡VXv=1jDvjjDj(Dv)(D)=¡jYjXi=1pklog2pk常见的特征选择方法常见的特征选择方法大致分为如下三类：过滤式包裹式嵌入式将特征子集搜索机制与子集评价机制相结合，即可得到特征选择方法过滤式选择Relief(RelevantFeatures)方法[KiraandRendell,1992]为每个初始特征赋予一个“相关统计量”，度量特征的重要性特征子集的重要性由子集中每个特征所对应的相关统计量之和决定设计一个阈值，然后选择比阈值大的相关统计量分量所对应的特征或者指定欲选取的特征个数，然后选择相关统计量分量最大的指定个数特征如何确定相关统计量？先用特征选择过程过滤原始数据，再用过滤后的特征来训练模型；特征选择过程与后续学习器无关Relief方法中相关统计量的确定Relief方法的多类拓展Relief方法是为二分类问题设计的，其扩展变体Relief-F[Kononenko,1994]能处理多分类问题包裹式选择包裹式特征选择的目的就是为给定学习器选择最有利于其性能、“量身定做”的特征子集包裹式选择方法直接针对给定学习器进行优化，因此从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好包裹式特征选择过程中需多次训练学习器，计算开销通常比过滤式特征选择大得多包裹式选择直接把最终将要使用的学习器的性能作为特征子集的评价准则LVW包裹式特征选择方法基本步骤在循环的每一轮随机产生一个特征子集在随机产生的特征子集上通过交叉验证推断当前特征子集的误差进行多次循环，在多个随机产生的特征子集中选择误差最小的特征子集作为最终解**若有运行时间限制，则该算法有可能给不出解LVW（LasVegasWrapper）[LiuandSetiono,1996]在拉斯维加斯方法框架下使用随机策略来进行子集搜索，并以最终分类器的误差作为特征子集评价准则嵌入式选择嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，在学习器训练过程中自动地进行特征选择岭回归(ridgeregression)[TikhonovandArsenin,1977]易获得稀疏解，是一种嵌入式特征选择方法等值线即取值相同的点的连线minxmXi=1f(x)+¸kxk1近端梯度下降（ProximalGradientDescend，简称PGD）解法[BoydandVandenberghe,2004]L1正则化问题的求解(2)L1正则化问题的求解(3)xk+1;i=8:zi¡¸=Lzi¸=L0jzij·¸=Lzi+¸=Lzi¡¸=L稀疏表示将数据集考虑成一个矩阵，每行对应一个样本，每列对应一个特征矩阵中有很多零元素，且非整行整列出现稀疏表达的优势：文本数据线性可分存储高效能否将稠密表示的数据集转化为“稀疏表示”，使其享受稀疏表达的优势？字典学习为普通稠密表达的样本找到合适的字典，将样本转化为稀疏表示，这一过程称为字典学习字典学习的解法(2)minbi;®ik(X¡Xj6=ibj®j)¡bi®ik2F=minbi;®ikEi¡bi®ik2F为了不破坏的稀疏性，仅保留非零元素，仅保留与非零元素的乘积项®i®i®ibiEi压缩感知数据传输中，能否利用接收到的压缩、丢包后的数字信号，精确重构出原信号？压缩感知(compressivesensing)[Cándesetal.,2006,Donoho,2006]为解决此类问题提供了新的思路.能否利用部分数据恢复全部数据？y=©xy=©x=©ªs=As如傅里叶变换，余弦变换，小波变换等限定等距性(1¡±k)ksk22·kAksk22·(1+±k)ksk22压缩感知的优化目标和解法minsksk0y=Asminsksk1y=As矩阵补全客户对书籍的喜好程度的评分“矩阵补全”技术解决此类问题能否将表中已经通过读者评价得到的数据当作部分信号，基于压缩感知的思想恢复出完整信号从而进行书籍推荐呢？从题材、作者、装帧等角度看（相似题材的书籍有相似的读者），表中反映的信号是稀疏的，能通过类似压缩感知的思想加以处理。矩阵补全的优化问题和解法minXkXk¤Xij=Aij;(i;j)2ÐkXk¤=Pmin(m;n)j=1¾j(X)¾j(X)本章小结