木匠手做网站,什么是网络营销含义,合肥公司门户网站制作,新洲建设局网站特征选择和稀疏学习 子集搜索与评价 对象都有很多属性来描述#xff0c;属性也称为特征#xff08;feature#xff09;#xff0c;用于刻画对象的某一个特性。对一个学习任务而言#xff0c;有些属性是关键有用的#xff0c;而有些属性则可能不必要纳入训练数据。对当前学… 特征选择和稀疏学习 子集搜索与评价 对象都有很多属性来描述属性也称为特征feature用于刻画对象的某一个特性。对一个学习任务而言有些属性是关键有用的而有些属性则可能不必要纳入训练数据。对当前学习任务有用的属性称为相关特征relevant feature、无用的属性称为无关特征irrelevantfeature。从给定的特征集合中选择出相关特征子集的过程称为特征选择feature selection。 特征选择时一个数据预处理data preprocessing过程在现实机器学习任务中基于避免维数灾难和降低不相关特征带来的学习难度在获得数据之后往往会先进行特征选择再训练学习器。当然特征选择要确保不丢失重要特征。给定数据集若学习任务不同则相关特征很可能不同因此无关特征是指与当前学习任务无关。若一个属性是从其他属性中推演而出的则成为冗余特征redundant feature。 假定数据中不涉及冗余特征并假定初始的特征集包含了所有的重要信息那么如何进行特征选择呢要从初始的特征集合中选取一个包含了所有重要信息的特征子集若没有任何领域知识作为先验假设那就只有遍历所有子集这计算开销相当大一旦属性稍多就会出现组合爆炸。较为可行的一个做法是先产生一个候选子集然后评价基于评价结果产生下一轮候选子集再评价…如此下去直至无法找到更好的候选子集。这个做法就关系两个很重要的过程如何评价候选子集的优劣又如何根据评价结果遴选下一轮候选子集呢 1子集搜索subsetsearch 给定特征集合{a1,a2,…,ad}可将每个特征看做一个候选子集对这d个候选单特征子集进行评价选出一个最优的然后加入一个特征构成包含两个特征的候选子集…假定在k1轮时最后的候选k1个特征子集不如上一轮的选定集则停止生成候选子集并将上一轮选定的k特征集合作为特征选择结果。上述这种逐渐增加相关特征的策略称为前向forward搜索。如果从完整的特征集合开始每次尝试去掉一个无关特征这样逐渐减少特征的策略称为后向backward搜索。也可将前后和后向搜索结合起来每一轮逐渐增加选定相关特征、同时减少无关特征这样的策略称为双向bidirectional搜索。 上述策略是贪心的因为它们仅仅考虑了使本轮选定集最优如在第三轮假定a5优于a6于是选定集为{a2,a4,a5}然后在第四轮却可能是{a2,a4,a6,a8}优于所有的{a2,a4,a5,ai}。要解决这个问题就只能进行穷举搜索。 2子集评价subsetevaluation 给定数据集D假定D中第i类样本所占的比例为pi(i1,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 iRelief先在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 t0 while tT do 随机产生特征子集A’ d’|A’| E’CrossValidation(Σ(DA’))//在特征子集A’上通过交叉验证估计学习器误差 if (E’E) 或 ((E’E) 与d’d) then //误差小于原来的更新 t0; EE’; dd’; A*A’; else tt1; 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层从而引导后续的突破。
