模式识别第11章独立于算法的机器学习

1、模式识别 独立于算法的机器学习第十一章第十一章 独立于算法的机器学习独立于算法的机器学习模式识别 独立于算法的机器学习11.1 模式识别中的哲学模式识别中的哲学o 这里讨论的是一些独立于具体识别算法的这里讨论的是一些独立于具体识别算法的一般性原理，但可以适用于任何一个特定一般性原理，但可以适用于任何一个特定的识别方法：的识别方法：1. 没有免费午餐定理没有免费午餐定理；2. 丑小鸭定理丑小鸭定理；3. Occam剃刀原理剃刀原理。模式识别 独立于算法的机器学习没有免费的午餐定理没有免费的午餐定理（NFL, No Free Lunch Theorem）o 不存在一个与具体应用无关的，普遍适用的不

2、存在一个与具体应用无关的，普遍适用的“最优分类器最优分类器”；o 学习算法必须要作出一个与问题领域有关的学习算法必须要作出一个与问题领域有关的“假设假设”，分类器必须与问题域相适应。，分类器必须与问题域相适应。模式识别 独立于算法的机器学习丑小鸭定理（丑小鸭定理（Ugly Duckling）o 不存在与问题无关的不存在与问题无关的“最优最优”的特征集合或的特征集合或属性集合；属性集合；o 也同样不存在与问题无关的模式之间的也同样不存在与问题无关的模式之间的“相相似性度量似性度量”。模式识别 独立于算法的机器学习Occam剃刀原理剃刀原理o 设计者不应该选用比设计者不应该选用比“必要必要”更加复

3、杂的分类器，更加复杂的分类器，“必要必要”是由训练数据的拟合情况决定的；是由训练数据的拟合情况决定的；o 在对训练数据分类效果相同时，在对训练数据分类效果相同时，“简单的简单的”分类分类器往往优于器往往优于“复杂的复杂的”分类器；分类器；o 根据根据“没有免费午餐定理没有免费午餐定理”，不能说，不能说“简单的简单的”分类器对分类器对“复杂的复杂的”分类器具有天生的优越性，分类器具有天生的优越性，但在现实世界中遇到的各种问题，这种优越性往但在现实世界中遇到的各种问题，这种优越性往往是存在。往是存在。模式识别 独立于算法的机器学习11.2 分类性能评价方法分类性能评价方法o 使用什么样本测试分类器

4、的性能？使用什么样本测试分类器的性能？o 如何划分样本集如何划分样本集?n 两分法两分法：随机地：随机地将样本集将样本集D划分为划分为不相交的两个集不相交的两个集合合Dl和和Dt，分别用于学习分类器和测试分类器性能。，分别用于学习分类器和测试分类器性能。训练样本集训练样本集(D(Dl l) )测试样本集测试样本集(D(Dt t) )模式识别 独立于算法的机器学习分类性能评价方法分类性能评价方法n 交叉验证交叉验证：将样本集将样本集D随机地划分为互不随机地划分为互不相交的相交的k个个子子集集：1. 使用使用k-1个子集的样本训练一个分类器；个子集的样本训练一个分类器；2. 测试没有参与训练子集的

5、样本测试没有参与训练子集的样本；3. 重复重复k次取平均。次取平均。n 留一法（刀切法）留一法（刀切法）：k = nD D1 1D D2 2D Dk-1k-1D Dk kDlDt模式识别 独立于算法的机器学习分类性能评价方法分类性能评价方法n Bootstrap方法方法（自助法）（自助法）:1. 从样本集从样本集D中有放回地抽取中有放回地抽取n个样本用于训练个样本用于训练；2. 从样本集从样本集D中有放回地抽取中有放回地抽取n个样本用于测试；个样本用于测试；3. 重复重复k次取平均。次取平均。样本集样本集D D样本集样本集D Dl l样本集样本集D Dt t模式识别 独立于算法的机器学习11.

6、3 分类设计的重采样技术分类设计的重采样技术 o 分类器设计的重采样技术也被称为分类器设计的重采样技术也被称为“自适应的自适应的权值重置和组合（权值重置和组合（arcing, adaptive reweighting and combining）；）；o 这类方法的主要思想是利用同一个训练样本集这类方法的主要思想是利用同一个训练样本集合构造多个分类器，然后以某种方式将这些分合构造多个分类器，然后以某种方式将这些分类器组合成一个分类器；类器组合成一个分类器；o 主要方法包括：主要方法包括：bagging算法算法和和boosting算法算法模式识别 独立于算法的机器学习bagging算法算法1.从

7、大小为从大小为n的原始数据集的原始数据集D中独立随机地抽取中独立随机地抽取n个数据个数据(nn)，形成一个自助数据集；，形成一个自助数据集；2.重复上述过程，产生出多个独立的自助数据集；重复上述过程，产生出多个独立的自助数据集；3.利用每个自助数据集训练出一个利用每个自助数据集训练出一个“分量分类分量分类器器”；4.最终的分类结果由这些最终的分类结果由这些“分量分类器分量分类器”各自的各自的判别结果投票决定。判别结果投票决定。模式识别 独立于算法的机器学习boosting算法算法o boosting算法同样是利用训练样本集合构造多算法同样是利用训练样本集合构造多个分量分类器，它只要求这个分量分

8、类器是一个分量分类器，它只要求这个分量分类器是一个弱分类器个弱分类器准确率比平均性能好即可。准确率比平均性能好即可。o 2类问题，类问题，3个分量分类器的训练算法：个分量分类器的训练算法：1.在数量为在数量为n的原始样本集的原始样本集D中随机选取中随机选取n1个样本构成个样本构成D1，利用，利用D1训练出一个分类器训练出一个分类器C1；2.在样本集在样本集D-D1中选择被中选择被C1正确分类和错误分类的样正确分类和错误分类的样本各一半组成样本集本各一半组成样本集D2，用，用D2训练出一个分类器训练出一个分类器C2；3.将样本集将样本集D-D1-D2中所有中所有C1和和C2分类结果不同的样分类结

9、果不同的样本组成样本集本组成样本集D3，训练出一个分类器，训练出一个分类器C3；模式识别 独立于算法的机器学习boosting的分类算法的分类算法o 对新的样本对新的样本x进行分类，如果进行分类，如果C1和和C2判别结果相同，则判别结果相同，则将将x判别为此类别，否则以判别为此类别，否则以C3的结果作为的结果作为x的类别；的类别；原始样本集原始样本集分量分类分量分类器器组合分类组合分类器器模式识别 独立于算法的机器学习AdaBoost方法方法o AdaBoost(adaptive boosting)是是boosting方法的方法的一个重要变形，一般所说的一个重要变形，一般所说的boosting

10、方法均是方法均是指指AdaBoost；o AdaBoost方法中，设计者可以不断地增加分量方法中，设计者可以不断地增加分量分类器，直到达到足够小的错误率为止；分类器，直到达到足够小的错误率为止；o 总体分类结果是由各分量分类器加权平均得到，总体分类结果是由各分量分类器加权平均得到，权重由分量分类器的错误率确定。权重由分量分类器的错误率确定。模式识别 独立于算法的机器学习AdaBoost方法方法1.begin initialize D, kmax, W1(i)1/n, i=1,n；2. k0;3. do kk+14. 训练使用按照训练使用按照Wk(i)采样采样D的弱分类器的弱分类器Ck；5. E

11、k用用Wk(i)采样采样D的样本集测量的样本集测量Ck的训练误差；的训练误差；6. 7. 8. until k=kmax；9. end1ln 12kkkEE 1,kkkkkW ieWiZe正确分类错误分类模式识别 独立于算法的机器学习AdaBoost方法方法o 算法中算法中Wk(i)为每一步迭代中对每个样本的加权，为每一步迭代中对每个样本的加权，Zk是归一化因子，是归一化因子，Ck为第为第k个分量分类器，个分量分类器，k为对为对Ck的加权的加权；o 总体的判别函数由各分量分类器的加权平均得总体的判别函数由各分量分类器的加权平均得到：到：其中其中 为为Ck分类器给出的判别结果。分类器给出的判别结

12、果。 max1kkkkghxx kh x模式识别 独立于算法的机器学习AdaBoost方法的推广能力方法的推广能力o AdaBoost方法实际上是增加了分类器的复杂程度，但方法实际上是增加了分类器的复杂程度，但实践表明此方法出现实践表明此方法出现“过拟合过拟合”的现象极少，这是此方的现象极少，这是此方法最吸引人的地方。法最吸引人的地方。模式识别 独立于算法的机器学习针对特征的针对特征的Boosting算法算法o特征选择特征选择：就是从一组数量为：就是从一组数量为n的特征中选择出的特征中选择出数量为数量为m的最优特征；的最优特征；1. 最优特征组合的评价标准；最优特征组合的评价标准；2. 选择出

13、最优特征组合的算法；选择出最优特征组合的算法；oBoosting可以作为特征选择的方法。可以作为特征选择的方法。模式识别 独立于算法的机器学习AdaBoost特征选择算法特征选择算法oGiven examples (x1,y1), (xn,yn), where yi=0,1for negative and positive examples respectively;oInitialize weights w1,i=1/2m, 1/2l for yi=0,1respectively, where m and l are the number of negatives and positives respectively;oFor t = 1,T:1.Normalize the weights: so that wt is a probability distribution.,1ntitit jjwww模式识别 独立于算法的机器学习AdaBoost特征选择算法特征选择算法2.For each feature, j , train a classifier hj which is restricted to using a single feature. The error is evaluated with respect to wt, 3.Choose the class