第八章、第九章：(第六次作业) 第一部分：问题、计算与证明 1．请简述 Adaboost 算法的设计思想。 答：改变训练数据的概率(权重)分布，针对不同的训练数据的分布，调用弱学习算法来学习 多个分类器，并将这些弱分类器组合成一个强分类器，以提高分类性能。 实现： • 改变训练数据的权值或分布：提高被前一轮弱分类器分错的样本的权重，降低已经被正 确分类的样本的权重。 • 将一系列弱分类器组合成一个强分类器：采用加权（多数）表决的方法，加大分类错误 率较小的弱分类器的权重。 2．请从机器学习的角度简述模型选择的基本原则。 答：机器学习的每个模型各有侧重：有的计算复杂度低，有的可更好地应用先验知识，而有 的则具有更好的分类或聚类性能。没有万能的最优模型。对于在训练集上表现同样良好的两 个分类器 (1) 没有免费的午餐定理 (No Free Lunch, NFL) • 学习算法必须要引入一些与问题领域有关的假设，应从特定的实际问题出发，设计其适 用的算法。 • 对于整个函数集(类)而言，不存在与具体应用无关的、万能的最佳算法。 • 所有算法在整个函数集的平均表现度量是一样的。在没有假设的前提下，我们没有理由 偏爱某一学习或分类算法而轻视另一个。 • 各类算法在指标性能提高上各有侧重，要想在某些指标上得到性能的提高，必须在另一 些指标上付出相应的代价。因此,我们需了解所研究对象的本质，如：先验知识 、数据 分布、训练数据量 、代价准则。 (2) 丑小鸭定理 (Ugly Ducking) 一切分类的标准都是主观的。 • 不存在与问题无关的最优的特征属性集合。 • 不存在与问题无关的模式之间的“相似性度量”。 (3) Occam 剃刀原理(Occam’s Razor) 不应该选用比“训练数据拟合情况”更复杂的分类器。训练数据分类的效果相同时，简 单的分类器更优；简单的、参数少的假设更优。 (4) 最小描述长度原理 (Minimum Description Length, MDL) 选择尽可能简单的分类器或模型，使模型的算法复杂度以及与该模型相适应的训练数据 的描述长度之和最小 。常见准则：赤池信息量准则，贝叶斯信息准则，网络信息准则等。 

3． 请简述分类器集成的基本方法。 答： • 目标：集成若干单个分类器，共同完成分类任务，以取得比单个分类器更好的性能。 • 要求：单个分类器的错误率低于 0.5；各分类器的分类效果不尽相同。 • 技术实现： 1 处理训练数据：比如对训练样本进行随机分组，对错分样本进行加权； 2 通过处理特征：比如每次只选择一部分特征来训练分类器； 3 处理类别标号：比如对多类问题 ，采用一对一策略、一对多策略； 4 改进学习方法：比如变更学习参数（如多核学习）、模型结构（如神经网络结构） 等。 • 基本算法： 1 按基本分类器类型: 异态集成：层叠泛化采用多层结构，后一层的输入为前一层学习后的输出结果； 同态集成：基本分类器多采用神经网络、二叉树、K－近邻。 2 按训练数据处理方式： Bagging，Random subspace(随机子空间) ，Boosting/Adaboost，随机森林。 4．请推导出 Hard-Margin SVM 的优化目标。 解： （1）推导方式 1 挑选出离分界面最近的点，计算距离： margin argmin (x)=argmin  d x  D x  D |  x w  d 1 i  +b| 2 w i 最大化两类间隔： argmax margin( b w , w ,b,D)=argmaxargmin b w ,  D x i | i  x w  d 1  +b| 2 i w i 考虑到分界面可能偏移到分类样本的外围，导致无法分类，因此引入约束条件： arg max arg min b w ,  D x i | subject to   x i +b| 2 w i i  x w  d 1 i  : ( D y i x w  i +b) 0  变形： ∵ y i = 1  ，并引入松弛    x i D :| x w  i +b| 1  arg min  D x i | i  x w  d 1 i  +b| 2 w i  arg min  D x i 1 d 1 i   2 w i  1 d 1 i   2 w i 最终 Hard-Margin SVM 的优化目标为： arg min b w ,  d 1 i  2 w i subject to   x i : D y i | （2）推导方式 2 将 margin 看作是两个分界面之间的距离： x w  i +b| 1  

Plus-plane： x w +b=+1 ； Minus-plane： x w  +b= 1  ； 距离： d= 2 ||w || ， 此时目标函数为： maximize 2 w || ||  最终 Hard-Margin SVM 的优化目标为： 1,   for y w x i i T +b 1 y ； 1,   T w x +b 1   i i arg min b w ,  d 1 i  2 w i subject to   x i : D y i | x w  i +b| 1  5． 请解释出 Hinge Loss 在 SVM 中的意义。 解：当样本线性不可分时，引入 soft-margin SVM，即允许错分样本，最小化总的经验风险：  * { w b * , } min ,b  w . . s t y w x  1 j (  c  N 1 j   j   2 i w d 1 i   +b) 1-   j 其中，严格要求 j 大于等于 0 ，因为只针对错分样本参与 松弛，正确样本对应 j 为 0。 Hinge Loss 函数表示为： hinge(  j ) max(1    j ,0) max(1    y w x j ( j +b),0) 此时 SVM 可以通过直接最小化如下损失函数求得最优的分 类超平面： min max(1 w  ,b N i 1   y w x  i i ( +b),0)  w || || 2 第二部分：计算机编程 6． 从 MNIST 数据集中选择两类，对其进行 SVM 分类，可调用现有的 SVM 工具 利用 sklearn 库进行 svm 训练 MNIST 数据集，准确率可以达到 90%以上。 #####代码： from sklearn import svm import numpy as np from tensorflow.examples.tutorials.mnist import input_data mnist = input_data.read_data_sets('MNIST_data', one_hot=False) train_num = 10000 test_num = 1000 

x_train = mnist.train.images y_train = mnist.train.labels x_test = mnist.test.images y_test = mnist.test.labels # 获取一个支持向量机模型 predictor = svm.SVC(gamma='scale', C=1.0, decision_function_shape='ovr', kernel='rbf') # 把数据丢进去 predictor.fit(x_train[:train_num], y_train[:train_num]) # 预测结果 result = predictor.predict(x_test[:test_num]) # 准确率估计 accurancy = np.sum(np.equal(result, y_test[:test_num])) / test_num print(accurancy) 相关函数的解析： • gamma：超平面距离不同类别的最小距离。是一个 float 类型的值，可以自己规定，也可 以用 SVM 自己的值，有两个选择。 1 选择 auto 时，gamma = 1/feature_num ,也就是特征的数目分之 1； 2 选择 scale 时，gamma = 1/(feature_num * X.std()), 特征数目乘样本标准差分之 1. 一 般来说，scael 比 auto 结果准确。 • C：松弛变量的系数。表明该模型对分类错误的容忍程度。 • decision_function_shape： 选择 ovr： one vs rest 将一个类别与其他所有类别进行划分； 选择 ovo： one vs one 两两划分 kernel： 当样本线性可分时，一般选择 linear 线性核函数； 当样本线性不可分时，有很多选择，这里选择 rbf 即径向基函数，又称高斯核函数。 •