中国科学院大学机器学习——boosting.doc

Boosting1. 判断题（1）Boosting和Bagging都是组合多个分类器投票的方法，二者都是根据单个分类器的正确率决定其权重。（2）在Boosting中，当训练误差为0时必须停止迭代，否则会发生过拟合。（3）Boosting和Bagging都可以视为是对训练数据的重采样，但二者的重采样方式不同。（4）在AdaBoost算法中，所有被错分的样本的权重更新比例相同。（T）（5）Boosting的一个优点是不会过拟合。2. Boosting。（20分，每小题10分）考虑如图3所示的训练样本，其中+和O分别表示正样本和负样本。图中还给出了采用AdaBoost算法经过若干次迭代后每个样本的权重。同时图中还给出了3个弱分类器：A、B和C。则图3：训练样本及其权重，A、B和C为3个可能的弱分类器（1） 下次将选择A、B和C等3个弱分类器的哪个弱分类器？为什么？弱分类器B的加权错误率最小。（2） 图中所示权重最可能是上次采用A、B和C哪个弱分类器得到的？为什么？上一轮选择的弱分类器在本轮中的加权错误率为0.5，因此上一轮的分类器是弱分类器C.3Boosting与特征选择考虑一个文本分类问题。每个文档用一些二值特征表示为，其中表示单词j出现在文档i中，否则的话。现采用AdaBoost算法进行分类，其中弱分类器为，其中j为选择的单词索引，为对应的文档标签。即每个弱分类器为每个单词与类别的关系。如有单词”足球”，类别有运动，非运动，则我们有两个弱分类器：l 如果文档中出现单词”足球”，判定该文档为“运动”；l 如果文档中不出现单词”足球”，判定该文档为“运动”；(1) 一共有多少个弱分类器？每个单词对应两个弱分类器，D个单词共有2D个弱分类器。(2) Boosting可以实现特征选择，即运行算法，被选择的特征按其被算法选中的顺序加入最终的模型。有些弱分类器可能会被选择多次吗？可能。Boosting算法是在假定之前的投票权重不变的情况下优化当前的，因此不是对所有的系数一起优化。因此只能通过再重新将弱分类器加入来修正之前的投票权重。(3) 互信息也可以用来特征选择。如果我们对每个特征根据其与标签之间的互信息来排序，那么该排序会比AdaBoost的排序更有信息量吗？不会。AdaBoost是多个弱分类器（特征）的线性组合，新的弱分类器是在考虑之前已有预测的基础上的。而单个特征与标签的互信息只考虑该特征本身的信息，不能发现多个特征队线性预测的交互作用。4. 现采用AdaBoost算法来集成多个弱分类器。图2给出了带标签的数据，其中输入特征为2维，同时还给出了第一个弱分类器。每个弱分类器根据某维特征预测输出。小箭头为决策边界的法线方向。初始时各样本的权重相同。图2: 带标签的数据及第一个弱分类器。箭头方向为决策边界的正方向。(1) 在图2中标出根据第一个弱分类器权重会增大的样本点。错分样本的权重会增加。，权重更新：，错误分类样本的权重：（1个），正确分类样本的权重为：（5个）.(2) 在图中画出下一轮选择的弱分类器。请给出决策边界及其方向。如图。(3) 第二轮弱分类器的系数会比第一次的大吗，即? 是的。因为被第二个弱分类器分错的样本的权重较小（因为被第一个弱分类器分对了）5Boosting考虑下述分类问题。我们打算采用boosting来学习分类器，其中弱分类器为平行两个坐标轴的线性分类器。请给出AdaBoost前3轮迭代的弱分类器、其对应的加权错误率、弱分类器的权重、样本权重的更新。为了统一，第一轮弱分类器选择特征x1，即为竖直线。并请给出每轮结束后的强分类器的训练误差。6AdaBoost的损失函数(1) AdaBoost可视为最小化指数损失函数，其中为类别标签，为弱分类器的权重。证明指数损失是0-1损失函数的上界。证明：(2) 指数损失对outliers敏感。请给出一个简单的解决方案。由于每个被错分的样本的权重会增加，一种忽略outliers的方法是对样本权重设置一个阈值，当样本的权重超过该阈值时，认为样本是outlier，去掉该样本。7下图给出了8个数据点，其中正负样本各4个。图中也给出了AdaBoost第一轮选择的弱分类器h1 （弱分类器为平行坐标轴的直线）。(1) AdaBoost给弱分类器h1的权重1为多少？ (各样本的初始权重相等，即 1/8.)(2) 不管弱分类器是什么类型，AdaBoost的训练误