《重采样技术在高维复杂信号检测中的应用.doc》由会员分享，可在线阅读，更多相关《重采样技术在高维复杂信号检测中的应用.doc（57页珍藏版）》请在三一文库上搜索。
1、重采样技术在高维复杂信号检测中的应用 一、毕业设计（论文）任务课题内容在信号处理领域，高维复杂信号的涌现，对信号处理是一个挑战。高维复杂信号的广泛存在，其检测成为信号处理不得不面对的问题。但是，通过“样本采集”获得的样本集，并应用“重采样技术”，对样本统计模型的真实性进行拟合，大大降低了信号检测的难度。重采样技术(Resampling Methods)是从自然模型多次采样得到样本集，基于此一系列样本集进行学习，并通过集成学习得到自然模型拟合。重采样技术的主要方法是AdaBoost算法，其基本思想是将大量学习能力一般的弱分类器通过一定方法组合起来，构成一个学习能力很强的强分类器。课题任务要求 1
2、. 具有一定的专业知识和实验开发能力，掌握课题相关理论知识和实验技术。2. 要求有一定的文字功能和文档处理能力，撰写合格的毕业设计论文，提供相关实验图表。3. 在学习本课题相关领域知识的基础上，掌握一定的自主学习方法，具备一定创新能力。 课题完成后应提交的资料（或图表、设计图纸）1.毕业论文含：1）中英文摘要2）重采样方法概述3）重采样技术原理4）自适应重采样技术的经典算法5）重采样技术的matlab仿真实验2毕业论文任务书，毕业论文开题报告，毕业论文正文，外文文献原文及翻译主要参考文献与外文翻译文件（由指导教师选定）1 李子清, 张军平. 人脸识别中子空间的统计学习/王珏等主编. 机器学习及
3、其应用. 北京:清华大学出版社, 20062 陈希孺. 数理统计学简史. 长沙：湖南教育出版社, 2002 3 Simon Haykin, McMaster.神经网络与机器学习 加拿大：机械工业出版社, 2009 4 T. G. Dietterich. Machine Learning Research: Four Current Directions AI Magazine. 18 (4), 97-136, 1997.5 Rosset, Zhu and Hastie. Boosting as a Regularized Path to a Maximum Margin Classifier.
4、 Journal of MachineLearning Research 5 (2004) 941973, 2004.6 Newman, D.J. & Hettich, S. & Blake, C.L. & Merz, C.J. (1998). UCI Repository of machine learning databases.同组设计者 无注：1. 此任务书由指导教师填写。如不够填写，可另加页。2. 此任务书最迟必须在毕业设计（论文）开始前一周下达给学生。3. 此任务书可从教务处网页表格下载区下载 重采样技术在高维复杂信号检测中的应用重采样技术在高维复杂信号检测中的应用摘要在信号处理领
5、域，高维复杂信号的涌现对信号处理是一个挑战。高维复杂信号的广泛存在，其检测成为信号处理不得不面对的问题。通过样本采集获得的样本集，并应用重采样技术，对样本统计模型的真实性进行拟合，大大降低了信号检测的难度。重采样技术是从自然模型中多次采样得到样本集，基于此一系列样本集进行学习，并通过集成学习得到自然模型拟合。重采样技术的主要方法是自适应的自助算法，其基本思想是将大量学习能力一般的弱分类器通过一定方法组合起来，构成一个学习能力很强的强分类器。本文从刀切法和自助法阐述了重采样技术的思想来源，详细分析了自适应的自助算法的三种典型算法，并提出了由粗到精的级联分类器以及训练系统的设计的重采样技术实现方法
6、。最后进行了重采样技术基于高维数据的matlab仿真，通过比较分析得出了三种典型算法各自的特点和算法的优劣。关键词：样本集；重采样；分类器；集成学习RE-SAMPLING TECHNIQUE IN HIGH-DIMENSIONAL COMPLEX SIGNAL DETECTIONAbstractThe emergence of high-dimensional complex signals is a challenge for signal processing. Because dimensional complex signal is widespread, the detection
7、of a signal becomes a problem to face. The sample set was obtained by sampling, and apply the re-sampling technique, the authenticity of the sample to fit the statistical model, which greatly reduces the difficulty of signal detection.Re-sampling technique is repeatedly sampled from the natural mode
8、l of the sample set, a series of sample sets based on this study, obtained by integration of the natural learning model fitting. The main re-sampling method is self-adaptive algorithm. the basic idea is to a large number of general learning ability of weak classifiers combined through a certain meth
9、od to form a very strong learning classifier.This article from the jackknife method and self-help law sets forth the ideological source of re-sampling technique, a detailed analysis of three typical algorithms for self-adaptive algorithm algorithm, and made from simple to complex cascade of classifi
10、ers and training system designed to re-sampling technology Methods. Finally, a re-sampling high dimensional data, matlab simulation, through comparative analysis of the three typical algorithms for their own characteristics and merits of the algorithm. Self-adaptive algorithm.Key words: sample set;
11、resampling;classification;ensemble learning 目录1 绪论11.1 课题研究的背景与意义11.2 重采样方法的发展31.3 论文主要内容及章节安排52 重采样技术72.1 重采样方法的理论基础72.2.1 刀切法72.2.1 自助法82.2 重采样方法的自助算法102.2.1 自助重采样方法起源102.2.2 自助重采样算法113 自适应的重采样技术143.1 自适应重采样算法的提出143.2 自适应重采样算法的基本原理153.2.1 分类器的训练153.2.2 弱分类器原理163.2.3 强分类器原理173.3 自适应重采样算法183.4 自适应重采
12、样强分类器算法204 典型的自适应重采样技术实现224.1 Gentle AdaBoost算法224.2 Real AdaBoost算法234.3 Modest AdaBoost算法244.4 重采样技术具体实现274.4.1 重采样技术算法结构274.4.2 重采样技术级联分类器284.4.3 重采样技术训练系统的设计295 重采样技术的matlab仿真实验315.1 实验介绍315.1.1 高维数据315.1.2 matlab工具箱介绍325.2 实验运行结果335.2.1 实验一运行结果335.2.2 实验二运行结果345.3 结果分析与比较35参考文献35致谢36附录37 重采样技术在
13、高维复杂信号检测中的应用1 绪论1.1 课题研究的背景与意义在信息化社会的今天，随着信息技术和互联网技术的发展，现代化的生产和科学研究产生了大量数据和重要信息其中许多数据属于高维数据，如多媒体数据、空间数据、时间序列数据、web数据等，同时现实世界数据库所存储和处理的规模越来越大。这些海量数据中蕴藏着大量有价值的信息，如何高效、准确地使用这些信息就成为当今研究的一项重要课题。由于这些数据兼具数据量超大及数据维数超大的特征，这就使得对它们进行各项操作运算时间过长或者超出了当前普通计算机的运算能力。又因为高维复杂信号存在的普遍性，使得对高维数据提取的研究有着非常重要的意义。但由于维灾的影响，也使得
14、高维数据提取变得异常地困难，必须采用一些特殊的手段进行处理。高维数据提取是基于高维度的一种数据提取，它和传统的数据提取最主要的区别在于它的高维度。目前高维数据提取已成为数据提取的重点和难点。随着技术的进步使得数据收集变得越来越容易，导致数据库规模越来越大、复杂性越来越高，维度（属性）通常可以达到成百上千维，甚至更高。随着数据维数的升高，高维索引结构的性能迅速下降，在低维空间中，我们经常采用欧式距离作为数据之间的相似性度量，但在高维空间中很多情况下这种相似性的概念不复存在，这就给高维数据提取带来了很严峻的考验，一方面引起基于索引结构的数据提取算法的性能下降，另一方面很多基于全空间距离函数的提取方
15、法也会失效。解决的方法可以有以下几种：可以通过降低维数将数据从高维降到低维，然后用低维数据的处理办法进行处理；对算法效率下降问题可以通过设计更为有效的索引结构、采用增量算法及并行算法等来提高算法的性能；对失效的问题通过重新定义使其获得新生。计算机工业以其部件的小型化和价格日趋低廉而有助于我们解决数据量问题。尽管我们总是受限于数学问题，但仍然认识到，多维系统也给了我们新的自由度。这些使得该领域既富于挑战性又无穷乐趣。统计学始于被观测的数据，Wegman把统计描述为一种将原数据转化为信息的方法，以区别于传统统计学的描述-传统统计学是关于收集和分析带随机性误差的数据的科学和艺术。从统计学的发展可以看
16、出数据的采集方式经历了大样本到小样本，再到大样本的过程。在1908年以前统计学的主要用武之地是社会统计(尤其是人口统计)问题，后来加入生物学统计问题。这些问题涉及到的数据一般都是大量的，自然采集的。而所采用的方法，以拉普拉斯中心极限定理为依据，总是归结到正态。到20世纪，受人工控制的试验条件下所得数据的统计分析，日渐引人注意。由于试验数据量一般不大，直接导致了依赖于近似正态分布的传统方法的失效，在这种小样本的研究方向上，Gosset和Fisher发展了确定正态样本统计量的精确分布的理论。无论大样本理论还是小样本理论，它们的共同特点是数据维数一般不大，最多几维，即，自然模型涉及的变量数量很少。然
17、而，现在我们面临自然涌现的数据除了观测的数据数量剧增之外，最大的不同是，数据维数少则几十维，多则上万维。如果再考虑数据性质的复杂性和数据表述的多样性，这不仅对计算机科学是一个挑战性的问题，对统计学同样是一个挑战性的问题。例如，银行的巨额交易数据，电话呼叫记录，文本数据等，数据量达到GB甚至TB级。适合分析和处理在精心设计实验获得独立同分布、同方差和低维数据的传统统计学理论已不能适应，需要新的思考。在统计建模中高维信号数据会遇到两个困难：其一，Bellman的维数灾难现象。维数灾难现象表明，在给定模型精度下的估计模型，需要的样本数量将随着维数的增加指数增长。而与此相关的问题是空间现象，即高维空间
18、的本质上是稀疏空间。一个典型的例子是高斯分布中的3准则：当样本集在二至三维空间时，采用高斯函数，可以证明，90%以上的样本集分布在3范围以内。然而，当维数显著增加时，样本集的分布更多的集中在高斯函数的边界(3以外)而不是中间。这表明在高维样本集中，数据可能大多数分布在超球的外壳，而不是在球的中心。由此产生的困难是，在多元数据分析中缺乏一般性的方法来直接分析高维空间的密度估计和几何性质，因为相对低密度的区域包含了样本集的大部分，反而高密度区域可能完全没有数据存在。其二，不适定问题。我们对自然模型，几乎一无所知，如果使用传统统计学的理论、方法和理念，估计概率密度函数，这一定是一个不适定问题。20世
19、纪初Hadamard在某些情况下求解线性算子方程的问题(寻找满足这一等式的函数)是不确定的。即使方程存在唯一解，如果方程右边有一个微小变动(如用取代，其中任意小)，也会导致解有很大的变化(即可能导致很大)。20世纪后半叶，人们发现根据数据估计密度函数这个统计学中的主要问题是不确定的：使泛函最小化的函数并不能保证在时是方程真实解的一个好的近似。高维空间的数据在拟合模型时的稀疏性，使得所获得的样本集不足以表现自然模型；传统统计学的不适定问题使得我们无法在高维复杂数据的情形下精确估计自然模型。这两个有关高维的、复杂的、自然涌现数据的问题，是重采样技术出现与成长的温床。特别是，当前一些重要的领域，例如
20、，银行交易数据、文本数据、Web数据都是自然涌现的，不但数据量庞大，而且维数很高，并且可能不能简单以一个固定的样本空间进行描述，即，数据不能使用相同维数的向量表述。而重采样技术恰恰为处理这类数据提供了工具，并在理论上给出了统计解释。1.2 重采样方法的发展由于当时海量涌现的高维数据具有天生的稀疏性，因此“获得有代表性的样本”对需要满足同分布条件的各种机器学习研究具有重要的现实意义。重采样方法的出现原本是为了更准确地获得“有代表性的样本”，其思想来源大致有两个方面：其一，试验设计，其二，抽样调查。重采样方法最早可以追溯到上个世纪30年代Fisher提出的配对化检验和Pitman提出的两个独立样本
21、的随机化检验。对两样本情形，试验者从可能不同的自然模型中得到两个样本，希望用统计假设检验来判断两个自然模型是否相同以，决定“两个自然模型相同”这个零假设是否被拒绝。一个直观的方法是将两个样本组合成一个有序的样本，不管每个值是来自哪个自然模型，从小到大给样本赋“秩”，而检验统计量就可能是来自其中一个自然模型观测值的“秩和”。如果这个秩和太小或太大，就意味着来自这个自然模型的值趋向于比来自另一自然模型的值小(或者大，视具体情况而定)。由此可知，如果与一个样本相关的秩趋向于比另一个样本相关的秩大，则“两个自然模型相同”这个零假设可能被拒绝。Fisher用数据本身作为秩来解决配对数据是否来自同一自然模
22、型，描述如下：两个独立的随机样本集分别来自两个自然模型 希望根据样本检验“两个自然模型相同”这个零假设，如果为真，两样本来自同一自然模型。检验统计量是观测值之和：，将混合成一个样本集，从中抽取出个样本，在假设条件下，每一种个样本的组合方式都是等概率的，考虑所有组合的可能性，可得零分布。之后采用标准的假设检验原理构造概率值，做出接受或者拒绝的结论。在随机化检验中采用数据组合的方式构造假设检验的过程，体现出了早期的重采样思想，当两个样本集融合在一起时，除非来自不同自然模型，否则重新采样后的统计指标和原样本统计指标应没有差别。此方法先于计算机发展，所以一般限制在小样本数据上，在样本容量较大的情形下，
23、需要的计算工作量很大，在当时，其应用必然受到限制。几乎是同一时期，抽样调查方面也开始冒出了重采样的萌芽，这种早期的重采样思想是从有限自然模型中无重复采样。在Pearson的统计框架中，针对一个自然模型，其对应着一个庞大的却有限的样本的集合。在理想情况下，科学家会搜集所有的这些样本，并确定其分布参数。如果无法搜集到全部样本，那么就搜集一个很大的并且具有代表性的数据子集。通过大量的且具有代表性的子集计算模型的参数，如果数据具有足够的代表性，被计算出的参数将与自然模型的参数相同。然而Pearson学派的方法存在一个根本性的缺陷，如果所获得的数据被称为“便利样本”，即属于那些最容易得到的数据，这些数据
24、并不能真正代表自然模型。 20世纪30年代的早期，印度发现了一个便利抽样的典型案例，为了估计孟买码头上大批黄麻的价值，需要从每包中抽取一些样品，黄麻的质量由这些样品来确定。抽样是将一把中空的圆形刀片插入包中，再拔出来，刀片中央的空处带出了少量的黄麻，但是由于天气和包装运输的原因，外层黄麻会变质，而由于在中间的黄麻被压紧，并结成一块，导致空心刀片难以插入，这样，所取的样本多是外层已经变质的黄麻，这种“便利样本”就会产生偏差，由此，导致评价整包黄麻质量偏低，实际上整包黄麻的质量要高得多。这个例子说明，收集具有代表性样本对估计模型准确性的重要性。为了收集能够准确估计自然模型的具有代表性的子样本，当时
25、出现了“判断样本”的方法。这个方法是将自然模型划分为几个子模型，每个子模型上都由某些样本来“代表”，这些“代表”的样本组成的集合作为判断样本。但是只有对自然模型有充分了解之后，才能将自然模型划分为一些能用个体样本来代表的子模型，这样判断样本才具有代表性，如果我们对自然模型已经了解的那么清楚，就无需进行抽样。Mahalanobis建议采用随机样本来推断有限自然模型。这种采样得到的样本优于便利样本和判断样本。最初Mahalanobis于1946年在研究作物产量上使用交叉抽样方法，之后McCarthy于1966年将其扩展到抽样调查领域。在抽样调查领域，仅从自然模型随机抽取，得到所有可能样本中的一次采
26、样，并依此来推断自然模型，其推断结果是否准确可靠，无法衡量，通过重复采样法进行抽样得到个子样本集，由于各个子样本集都独立且采样方式相同，若各子样本集的估计结果一致或者比较接近时，推断结果的真实性比较容易让人信服。此时的采样方法是基于从自然模型上重复采样的原则。1969年Hartigan提出了Random Sub-sampling方法，并首次将此方法用在统计量估计中。1.3 论文主要内容及章节安排本文通过现实中高维数据的大量存在，提出了高维数据检测的重采样技术。接着讲述了重采样技术的发展进程，并从刀切法和自助法阐述了其思想来源。提出了实现重采样技术的具体方法自适应的自助算法即AdaBoost算法
27、，详细论述了AdaBoost算法的原理，以及算法的具体流程。接着具体分析了AdaBoost算法的三种典型算法，并提出了由粗到精的级联分类器以及训练系统的设计的重采样技术实现方法。最后用matlab进行了重采样技术高维数据的仿真，通过对比较分析得出了Gentle AdaBoost，Real AdaBoost，Modest AdaBoost这三种算法各自的特点和算法的优劣。本文章节安排如下：第一章：绪论。阐述了本课题研究的背景与意义，提出了高维复杂信号检测的两个基本问题，介绍了重采样方法的发展进程。第二章：重采样技术。介绍了重采样方法的理论基础：刀切法，自助法，并阐述了它们的原理。然后通过提高自助
28、重采样方法起源和算法概述讲述了重采样方法的自助原理。第三章：自适应的重采样技术。提出了自适应的重采样技术Adaboost算法，通过有效地解决了早自助算法在实际运用中的困难引出Adaboost算法，并从分类器的训练，弱分类器原理，强分类器原理详细分析了其原理。最后提出算法具体流程，训练强分类器的算法。第四章：典型的自适应重采样技术实现。通过对Adaboost典型的三种算法：Gentle AdaBoost算法，Real AdaBoost算法，Modest AdaBoost算法的论述，分析了重采样技术具体实现的算法结构，提出由粗到精的级联分类器以及训练系统的设计的重采样技术实现方法。第五章：重采样技
29、术的matlab仿真实验。用matlab进行了重采样技术高维数据的仿真，首先介绍了matlab实验工具箱，然后通过仿真并对实验结果进行了分析。总结了Gentle AdaBoost，Real AdaBoost，Modest AdaBoost这三种算法的误差特点，及通过对比较得出算法的优劣。2 重采样技术重采样技术是从自然模型中多次采样得到样本集，基于此一系列样本集进行学习，并通过集成学习得到自然模型拟合。通过样本采集获得的样本集，并应用重采样技术，对样本统计模型的真实性进行拟合，大大降低了信号检测的难度。目前重采样技术是机器学习中比较热的一个研究方向，获得了越来越广泛的关注。2.1 重采样方法的
30、理论基础2.1.1 刀切法1949年，Quenouille提出了刀切法，这是近代重采样方法的标志，以后，由Quenouille和Tukey不断完善，重采样方法成为统计学的重要方法之一。刀切法的原始动机是降低估计的偏差。常用做法是：每次从样本集中删除一个或者几个样本，剩余的样本成为“刀切”样本，由一系列这样的刀切样本计算统计量的估计值。从这一批估计值，不但可以得到算法的稳定性衡量(方差)，还可以减少算法的偏差。这个方法暗示，刀切法的样本集需要事先给定，即，它的重采样过程是在给定样本集上的采样过程。最简单的一阶刀切法描述如下：假设独立同分布的样本来自一个未知概率模型， 是未知参数，是估计统计量，则
31、的刀切法估计为： (2-1)其中是刀切样本集上的统计量，是把原样本集中第个样本剔除后剩余的个样本组成的集合。 刀切法的最重要的性质是：刀切估计可以将偏差从减少到，并可以修正估计为无偏估计，但是并不能保证减少方差。这个性质描述如下：设为独立同分布样本集，其中为未知参数，统计量为的估计，若其偏差为： (2-2)则的刀切法估计的偏差为虽然刀切法可以降低估计偏差，但当参数不光滑时，刀切法会失效。此处光滑是指样本集上的微小变化，只会引起统计量的微小变化。最简单的不光滑的统计量是中位数，中位数是刻画随机变量分布“中心”的统计量。满足且的实数称为中位数，在样本集上，样本中位数定义为。通俗地说，将一维样本排序
32、，处在最中间位置的那个数据(或最中间两个数据的平均数)即为这组数据的中位数。Efron指出刀切法在估计中位数时会失效，而自助法可以有效地给出中位数的估计。用老鼠数据的例子来说明，9个排好序的样本分别为:10，27，31，40，46，50，52，104，146这个样本集的中位数是46(样本个数是奇数，中位数为最中间位置的样本)。如果改变第四个样本，当增加至并且超过46，中位数才会改变，之前中位数不改变。当样本从46继续增加直至50，中位数和此样本值相同，超过50之后，中位数变为50。使用一阶刀切法估计中位数，先去掉第一个样本，剩余8个样本的中位数是48（46与50的算术平均值），依次去掉相应的第
33、个样本，得到如下中位数估计结果：48，48，48，48，45，43，43，43，43刀切法只得到3个不同的中位数估计，方差较大。而自助法的采样方法使得样本集变化较大，会得到比较敏感的中位数变化。并且，在大样本性质上，中位数的刀切法估计的标准差是不相合的(不能收敛到真实的标准差)。而自助估计是相合的。2.1.2 自助法Efron1979年这篇文章指出了自助法与刀切法的关系。首先，自助法通过经验分布函数构建了自助法世界，将不适定的估计概率分布的问题转化为从给定样本集中重采样。第二，自助法可以解决不光滑参数的问题。遇到不光滑参数估计时，刀切法会失效，而自助法可以有效地给出中位数的估计。第三，将自助法
34、估计用泰勒公式展开，可以得到刀切法是自助法方法的一阶近似。第四，对于线性统计量的估计方差这个问题，刀切法或者自助法会得到同样的结果。但在非线性统计量的方差估计问题上，刀切法严重依赖于统计量线性的拟合程度，所以远不如自助法有效。Efron将刀切法纳入了自助法的体系中，并构建了从真实世界(自然模型)到自助世界的采样过程。这里，自助世界是基于经验分布函数从给定样本集重采样获得。样本集来自一个未知概率模型，是我们关注的未知参数，是估计参数的统计量，它们可以通过传统统计方法(极大似然，MAP等)获得，定义。然而我们不仅关注估计值本身，同时也关注统计量的准确程度，是无偏估计吗？距离真实值的偏差是多少？稳定
35、吗？方差是多少？但是这样的问题往往无法回答，因为我们不了解自然模型本身，我们面对的只有从自然模型中的采样结果样本集。我们可以在给定样本的条件下，构造的估计，然后从分布中重新生成一批随机样本。如果是的一个足够好的估计，那么与的关系会从和的关系中体现出来。自助法定义如下: 样本集来自一个未知概率模型，关注统计量，定义: 是样本集上的经验分布函数，其中每个样本的概率均为。从上次随机采样得到自助样本集为，目的是用自助样本集上的统计量的分布去逼近原样本集上统计量的分布。其中表示自助样本集中样本的个数，表示原始样本集中样本的个数。产生过程如下：从自然模型采样得到样本集，基于此样本集进行学习。如果样本集是对
36、自然模型的独立同分布的采样，那么，在统计上，这样的样本集对自然模型是理想的，它可以很好的拟合自然模型。传统统计学的样本是定义在事先给定的空间上，即，空间维数确定，通常可以理解为欧式空间中的点。对自然模型进行估计，并基于这个估计使用自助法得到自助样本集，可以不受样本空间维数固定的制约，并且可以追加新样本。学习的模型在统计意义下可对自然模型可以解释。重采样的次数是有限的，需要我们设计采样方法使得重采样样本构建的算法具有代表性，虽然自助法本身没有对算法类型做任何限制，但是弱可学习这个条件对于算法建模来说，容易满足，并且能够适用在自助样本集上。从自助法的采样过程来看，弱可学习建立的模型只依赖于部分样本
37、，为了得到自然模型的拟合，需要考虑某种集成方法，将这些自助样本集上的学习算法集群起来。 2.2 重采样方法的自助算法重采样技术实现的主要方法是自助法，自助法是一种有效的分类器组合方法，其通过加权投票来组合多个基分类器进行分类。它可以有效地将精度较低的弱学习算法提升为精度较高的强学习算法。自助法是近年来流行的一种用来提高学习算法精度的方法,作为一种新的集成机器学习方法，它以学习理论为依据，在很多应用领域中都表现出了其优良特性，在实际应用中也有广泛的前景。2.2.1 自助重采样方法起源在机器学习领域中,关键的问题就是如何利用观测数据通过学习得到精确估计。目前,随着计算机硬件技术的迅猛发展,学习准确
38、率比运算速度显得更为重要。但是,在实际应用领域中,构造一个高精度的估计几乎是不可能的。自助法是一种试图提升任意给定学习算法精度的普遍方法。它的思想起源valiant提出的计算学习理论PAC(Probably Approximately Correct)学习模型。PAC是统计机器学习、集成机器学习等方法的理论基础。Kearns和valiant首先提出下面问题:在valiant的PAC模型中，一个性能仅比随机猜测稍好的“弱”学习算法是否能被“提升”为一个具有任意精度的“强”学习算法？1990年SchaPire提出了第一个可证明的多项式时间自助算法，对这个问题做出了肯定的回答。SchaPire证明，
39、如果将多个PAC分类器集成在一起，它将具有PAC强分类器的泛化能力。进而又说明，这类集成后的强分类器具有统计学习理论的基础。之后，Freund设计了一个更加高效的通过重取样或过滤运作的Boost-by-majority算法。这个算法尽管在某种意义上是优化的，但却有一些实践上的缺陷。1995年Rreund与SchaPire提出了自适应的自助算法。这个算法和“Boost-by-majority”算法的效率几乎一样，却可以非常容易的应用到实际问题中去。然后，自助算法经过进一步改进又有了很大的发展，如通过调整权重而运作的一系列算法，解决了早期的自助算法很多实践上的问题。 自助法的主要思想就是通过粗糙的
40、、不太正确的、简单的、单凭经验的初级预测方法，按照一定的规则，最终得出一个复杂的、精确度很高的预测方法。自助法对那些容易错分类的训练实例加强学习，就好像一个人背英语单词一样，首先第一遍背完以后有一些容易记住的单词就记住了，还有一些不容易记住的，则第二遍的时候对那些不容易记住的单词多看几眼，第三遍又对第二遍还一记不住的单词再多看几眼。自助法是近十年来提出的最有效的学习思想之一，是提高预测学习系统能力的有效工具，也是集成学习中最具代表性的方法。2.2.2 自助重采样算法机器学习要解决的问题是如何利用已有的训练样本，自动学习出县有较好预测能力的分类器。例如，我们想得到一个可以自动分别垃圾邮件与非垃圾
41、邮件的分类器。机器学习是用以下步骤来获得这样的分类器的：首先收集大量的垃圾邮件与垃圾邮件的样本，然后把这些具有标定的样本输入到你要使用的学习算法中，我们就可以得到条对垃圾邮件与非垃圾邮件的判别准则。以后再来一封新的邮件，我们就可以用这一准则来判断它是否是垃圾邮件。我们的目标当然是希望这一分类器对新的样本有最准确的预测能力。建立一个预测能力很强的判别准则往往是一件很困难的事情，然而获得些较为粗糙的判别能力较强的准则就容易得多。例如，如果邮件中出现“现在购买”，我们就判定它是垃圾邮件。这样一些准则甚至不能覆盖所有的垃圾邮件，例如邮件中没有出现“现在购买”，也不能判定它就不是垃圾邮件。但是这些粗糙的
42、准则比起随机猜测还是强很多。自助法就是建立在寻找粗糙的弱分类器比寻找很强的分类器要容易得多，这一发现的基础上的。它把许多弱分类器融合在一起，从而获得到一个分类能力很强的判别准则。自助法的思想是一些简单的规则组合起来得到一个整体，使得这个整体的性能要比其中任何一个规则的性能高。假设为一假设集，考虑下面的一个合成的整体假设集，这里的代表整体中每个成员的一个相关系数，和假设都可以在自助过程中通过学习得到。在本节中我们主要关注于两类分类问题。两类分类问题的任务是基于一个观察集合找到一个规则(假设)为实体集分成两类。我们假定每个实体属于一个输入空间X，由规则(假设)输出的空间为Y。那么两类分类问题的任务
43、可以形式化的描述为估计得到一个函数使用服从某一个概率分的随机数据对(输入输出)：使得能够正确的预测来知的。在这种情况下，每个输入的类别标签是由给出的，我们称这类分类器为硬分类器。然而在实际应用过程中很可能会出现这种情况，当训练数据量比较小的情况下，实际错误率可以很低，然而广义错误率却不是很低，这就是所谓的过适应问题。所以小的广义错误率并不能通过简单的减小实际错误率。过适应问题可以通过规则化来解决，规则化通过限制集合F(假设是从这个集合中挑选的)的大小来实现。从直觉上，对于都能描述训练数据的两个假设，简单的和复杂的，通常简单的假设要比复杂的假设更为合适。 自助法会产生一个的复合整体假设，该算法可
44、以保证在某些情况下这个复合整体假设的复杂度并不会很高。既然复杂度不是很高，那么通常情况下就不会出现过适应问题，但是在一些具有噪声的数据中就很有可能会出现过适应的情况，这时候就不可避免的要使用规则化了。自助重采样算法在实际中有着大量而广泛的应用：其一，近年来在很多领域中都采用了自助法，如文本分类、图像分类检索，自然语合理解和语音识别等。其具体做法通常是将自助法与其它方法相结合，如与神经网络、决策树等算法相结合。和其他算法相比较，自助法有很多优点，如速度快、简单、编程容易，在分类的同时能够进行特征选取等等;在弱分类器确定后，除了迭代次数T之外不需要调节其他参数; 自助法不需要弱分类器的先验知识,只
45、要给定足够多的数据，通过寻找比随机稍好的弱分类器，就能够得到一个比较好的最终强分类器，而不是一开始就试图设计一个分类比较精确的算法;同时它还具有理论支持，只要有足够多的数据以及弱分类器就能够达到任意的预测精度。总之，理论上自助法是一种可以集成任何弱分类算法的算法框架，它有比较完整的数学理论基础，而且还有实验表明该算法对少样本、高维数据具有很好的适用性，和其他的分类算法相比，自助法具有适应性强、精度高的优点。 其二，自助法得到的广泛的研究和应用，其研究成果大部分都集中的分类问题上。在这个算法将分类任务划分成多个子分类器，每个子分类器关注于一些较难分类的样本，然后组合这些子分类器的结果形成一个强的
46、分类器。在自助法中，我们是通过调整样本的权重来控制子分类器专注于某些难分类的问题的，较难分类的样本我们则赋予高的权重，反之，则赋予较低的权重。所以，我们需要使用带权重的训练样本，有的学习算法可以直接使用带权重的训练样本，而有的学习算法却无法使用带权重的训练样本。对于可以使用带权重的学习算法，我们可以使用通过重新分配权重来加强的方法。对于那样不能使用带权重的学习算法，我们则采用通过重采样来加强的方法。3 自适应的重采样技术重采样技术有许多不同的变形，其中最为流行的一种是自适应的自助算法即AdaBoost算法。在该算法中，每个样本都被赋予一个权重，代表该样本被当前分类器选入训练集的概率，并根据预测
47、函数的输出与期望输出的差异调整样本权重：如果某个样本点已被正确分类，那么在下一个训练集的构造中，它的权重减小、被选中的概率降低；如果它没有被正确分类，则它的权重增大。通过这种方式，AdaBoost算法使得学习算法集中学习较难判别(富有信息)的样本变得容易判别起来。因此，AdaBoost算法提出后在机器学习领域得到极大的关注。3.1 自适应重采样算法的提出AdaBoost算法是SchaPire和Frcundll在1995年提出的，它有效地解决了早期自助算法在实际运用中的困难，它的最终判别准则的精确度是依赖所有弱学习过程得出的弱假设的，因而更能全面地挖掘弱学习算法的能力，也正是由此原因而得名“Adaptive Boosting”，简称AdaBoost。同时由于其简单的执行和理想的效果，AdaBoost成为人们关注的焦点。一般情况下若无特别说明，我们说自助算法都是指AdaBoost算法。AdaBoost算法是自助算法家族的最具代表性的算法，之后出现的自助算法都是在AdaBoost算法的基础上发展得来的。AdaBoost算法的研究以及应用大多集中于分类问题，同时近年也出现了一些在回归问题上的应用。就其应用AdaBoost系列主要解决了：两类问题、多类单标签问题、多类多标签问题、大