机器学习课后习题答案(周志华)

第二章 模型评估与选择1.数据集包含1000 个样本，其中500 个正例， 500 个反例，将其划分为包含70%样本的训练集和 30% 样本的测试集用于留出法评估，试估算共有多少种划分方式。一个组合问题，从500500 正反例中分别选出150150 正反例用于留出法评估，所以可能取法应该是 (?500150)2。2.数据集包含100 个样本， 其中正反例各一半，假定学习算法所产生的模型是将新样本预测为训练样本数较多的类别（训练样本数相同时进行随机猜测），试给出用10 折交叉验证法和留一法分别对错误率进行评估所得的结果。10 折交叉检验：由于每次训练样本中正反例数目一样，所以讲结果判断为正反例的概率也是一样的，所以错误率的期望是5050%。留一法： 如果留下的是正例，训练样本中反例的数目比正例多一个，所以留出的样本会被判断是反例；同理，留出的是反例，则会被判断成正例，所以错误率是100% 。3.若学习器A 的 F1 值比学习器B 高，试析A 的 BEP 值是否也比B 高。4.试述真正例率（TPR） 、假正例率（FPR）与查准率（P） 、查全率（ R）之间的联系。查全率 : 真实正例被预测为正例的比例真正例率 : 真实正例被预测为正例的比例显然查全率与真正例率是相等的。查准率 :预测为正例的实例中真实正例的比例假正例率 : 真实反例被预测为正例的比例两者并没有直接的数值关系。9.试述卡方检验过程。第三章 线性模型2.试证明，对于参数w，对率回归（ logistics回归）的目标函数（式1）是非凸的，但其对数似然函数（式2）是凸的。如果一个多元函数是凸的，那么它的Hessian 矩阵是半正定的。3.编程实现对率回归，并给出西瓜数据集3.0 上的结果http:/ 数据集，比较10 折交叉验证法和留一法所估计出的对率回归的错误率。http:/ 上的结果。http:/ LDA 仅在线性可分数据上能获得理想结果，试设计一个改进方法，使其能较好地用于非线性可分数据。在当前维度线性不可分，可以使用适当的映射方法，使其在更高一维上可分，典型的方法有KLDA，可以很好的划分数据。9.使用 OvR 和 MvM将多分类任务分解为二分类任务求解时，试述为何无需专门针对类别不平衡性进行处理。书中提到，对于OvROvR，MvMMvM来说，由于对每个类进行了相同的处理，其拆解出的二分类任务中类别不平衡的影响会相互抵消，因此通常不需要专门处理。以ECOCECOC 编码为例，每个生成的二分类器会将所有样本分成较为均衡的二类，使类别不平衡的影响减小。当然拆解后仍然可能出现明显的类别不平衡现象，比如一个超级大类和一群小类。第四章 决策树4.1.试证明对于不含冲突数据（即特征向量完全相同但标记不同）的训练集，必存在与训练集一致（即训练误差为0）的决策树。因为决策树是通过属性来划分，相同属性的样本最终肯定会进入相同的叶节点。一个叶节点只有一个分类， 如果样本属性相同而分类不同，必然产生训练误差。反之，决策树只会在当前样本集合是同一类或者所有属性相同时才会停止划分，最终得到训练误差为0 的决策树。4.2.试析使用“最小训练误差”作为决策树划分选择的缺陷。从机器学习最开始就讲起，最小训练误差并不可靠，由于过度学习样本特性最终导致严重的过拟合，而没有泛化能力。4.3.试编程实现基于信息熵进行划分选择的决策树算法，并为表 4.3 中数据生成一棵决策树。http:/ ID3 算法4.4.试编程实现基于基尼指数进行划分选择的决策树算法，并为表4.2 中数据生成预剪枝、后剪枝决策树，并与未剪枝决策树进行比较。http:/ CART 算法4.5.试编程实现基于对率回归进行划分选择的决策树算法，并为表4.3 中数据生成一棵决策树。http:/ 的多变量决策树 模型，这里我们将每个非叶节点作为一个对率回归分类器，输出为”是”、”否”两类，形成形如二叉树的决策树。4.6.试选择 4 个 UCI 数据集，对上述3 种算法所产生的未剪枝、预剪枝、后剪枝决策树进行实验比较，并进行适当的统计显著性检验。答案一简要的分析一下：ID3 算法基于信息熵增益，CART 算法则采用了基尼系数。两种划分属性选择均是基于数据纯度的角度， 方法差距应该不大（CART 可能要好一点） 。而对率回归进行划分选择，以斜划分的方式，实现了多变量参与划分，其模型决策边界更光滑。相比于决策树的生成算法，剪枝操作更影响模型性能。答案二这里要对上面三种实现的算法进行未剪枝，预剪枝，后剪枝做比较，对率回归划分就算了，都不知道是个什么情况，信息增益和基尼指数的差别并不大，其实就是为了比较未剪枝，预剪枝，后剪枝对测试样本的输出结果。显著性分析，对2 种算法， 3 种剪枝方式的错误数做方差分析， 信息增益和基尼指数有显著区别是拒绝的，未剪枝，预剪枝，后剪枝有显著区别是接受的。4.7.图 4.2 是一个递归算法，若面临巨量数据，则决策树的层数会很深，使用递归方法易导致“栈”溢出，试使用“队列”数据结构，以参数 maxDepth控制数的最大深度，写出与图4.2等价、但不使用递归的决策树生成算法。答案一直接用递归会导致大量的临时变量被保存，当层数过深时会导致“栈”溢出。用队列对决策树进行层次遍历来生成，用Max_Depth 来控制树的最大层数。队列中每个元素代表着决策树的每个节点，它必要的属性有：样本集合、剩余属性集合，当前层数指示，父节点序号。队列一开始里面只有一个元素，就是最初初始化，带着所有样本的根节点。然后当队列不为空的时候开始循环，每次取出一个元素，判断是否需要划分，如果不要， 就是一个叶节点，出队列就不用管了；如果需要划分，那么找出最好的划分属性，然后划分成n个子区间，依次送入队列，继续循环，直到队列为空。是否需要划分有3 个依据 : 当前所有样本属于一类当前所有样本属性完全相同达到了 Max_Depth 的深度这样就完成了层次遍历(广度优先搜索 )对决策树的构建。显然由于每次出队的元素要先完全划分，那么如果是进行预剪枝算法的决策树，用队列结构是非常方便的。如果是后剪枝，那必须要等到最终整棵树完全生成，才能进行。答案二首先做一些分析：从数据结构算法的角度来看，生成一棵树常用递归和迭代两种模式。采用递归时， 由于在递归时要存储程序入口出口指针和大量临时变量等，会涉及到不断的压栈与出栈，当递归层次加深，压栈多于出栈，内存消耗扩大。这里要采用队列数据结构来生成决策树，虽然避免了递归操作产生的内存消耗，但需要更大的额外存储空间。用 MaxDepth 来控制树的深度，即深度优先（Depth Fisrt ）的形式，一般来说，使用递归实现相对容易，当然也可以用非递归来实现。4.8.试将决策树生成的深度优先搜索过程修改为广度优先搜索，以参数MaxNode控制树的最大结点数，将题4.7 中基于队列的决策树算法进行改写。对比题4.7 中的算法，试分析哪种方式更易于控制决策树所需储存不超过内存。本题实际上是BFS与 DFS的比较：对于深度优先搜索，每深入一层需要存储上一层节点的信息以方便回溯遍历（其存储的是一条路径）；对于广度优先搜索，每深入一层需要存储当前层兄弟节点信息以实现遍历（其存储的是每层信息，存储量会大一些）；两种方法各自有防止队列过大化的阈值（即 MaxDepth 和 MaxNode ） ，所以两种方法均可将内存消耗控制在一定范围之内。当数据属性相对较多， 属性不同取值相对较少时，树会比较宽， 此时深度优先所需内存较小，反之宽度优先较小。4.9.试将 4.4.2 节对缺失值的处理机制推广到基尼指数的计算中去。只需要把信息增益的公式换成基尼指数就行，包括扩展到连续参数，缺失参数， 都是很直观的方法。4.10.从网上下载或自己编程实现任意一种多变量决策树算法，并观察其在西瓜数据集3.0 上产生的结果。http:/ 神经网络第六章 支持向量机第七章 贝叶斯分类器4.试为 LVW 设计一个改进算法，即便有运行时间限制，该算法也一定能给出解。LVW 结束循环的条件是连续T 次随机出来的特征都比当前最优特征集合要差。当T 和特征集合 A 很大时， LVW 需要的迭代时间很长。如果有运行时间限制，可以再给定一个结束条件，设最多迭代次数t， 当总迭代次数达到t 的时候， 结束迭代并返回当前最优的特征集合。t 的值根据限定的时间来估计。5.结合图 11.2，是举例说明L1 正则化在何种情形下不能产生稀疏解。如果平方误差等值线与坐标轴相交前就与L1L1 范数等值线相交了，就无法得到稀疏解。6.试析岭回归与支持向量机的联系。7.试述直接求解L0L0 范数正则化会遇到的困难。由于 L0L0 范数不连续，非凸，无法用解析法很好的表示，只能通过遍历来寻求最优解，这导致 L0L0 范数的最优化为题是个NP 难问题。8.试给出求解L1L1 范数最小化问题中的闭式解(11.14) 的详细推到过程。9.试述字典学习与压缩感知对稀疏性利用的异同。字典学习通过学习出的字典使属性适度稀疏，使得文本数据在字频上线性可分，从而提升如SVM 获得更好的性能。压缩感知则是希望原始信号本身虽然不稀疏，但是他内部是高度相关的，这样可以通过x=s,使得 s 是一个稀疏的向量。此时通过采样信号y 来还原 s 时可以得到足够接近的结果，从而更好的还原原始信号x。10.试改进 (11.15) ，以学习出具有分组稀疏性的字典。5.试计算决策树桩假设空间的VC 维。如果是非连续属性，通过决策树一次划分无法确定节点个数，可能导致VC 维无限大。仅考虑连续属性单变量的决策树桩。由于决策树的划分是与坐标轴平行的超平面，显然平面上的2 个点是可以被打散的，即VC维大于等于2。对于平面的3 各点，如果其中两个点的连线与一条坐标轴平行，另两个点的连线与另一坐标轴平行。比如 (0,0),(0,1),(1,0)三个点，无法通过一个与坐标轴平行的超平面来划分。所以VC维小于 3。所以决策树桩假设空间的VC 维是 2。6.决策树分类器的假设空间VC 维可以为无穷大。由于决策树如果不限制伸展，会包含整个假设空间。对任意多的样本，决策树可以使得训练误差为 0，所以 VC 维是无穷大。7.试证明：最近邻分类器的假设空间VC 维为无穷大。8.试证明常数函数c 的 Rademacher的复杂度为0。2.试基于朴素贝叶斯模型推导出生成式半监督学习算法。朴素贝叶斯模型假设样本所有属性相互独立。参数表示：?a 表示属性集合?x 样本属性?y 表示有标记样本的分类?c 表示样本的生成伪分类初始化：根据训练样本计算出最初的，并对无标记样本生成最初的伪标记。使用 EM 算法来求解伪标记：E步：使用拉普拉斯平滑标记对已经有标记的样本进行属性类概率估计，求出。M 步：使用当前的对无标记样本集合重新进行分类，获得新的伪标记。直到无标记样本的伪标记不再变化。6.TSVM 对未标记样本进行标记指派与调整过程涉及很大的计算开销，试设计一个高效的改进算法。在标记调整过程中，可以考虑每次将最有可能指派错误的样本进行调整，即正负伪标记样本中松弛变量最大且大于1 的样本进行标记更改，可以减少迭代的次数。7.试设计一个能对新样本进行分类图半监督算法。图半监督算法不会直接对新样本进行分类，可行的办法一是将新样本作为无标记样本再次进行图半监督算法。或者使用已有标记的样本训练一个学习器，再对新样本分类。8.自训练是一种比较原始的半监督学习方法：它现在有标记的样本上学习，然后在无标记的样本上获得伪标记，再在全部样本上进行重复训练，分析该方差有何缺陷。由于训练样本远远少于无标记样本，如果将全部无标记样本的伪标记直接作为训练样本，将导致很多样本属于噪声样本，十分影响分类器的准确度。应该进行局部伪标记调整来优化分类器，而不是直接使用全部的伪标记重复训练分类器。9.给定一个数据集，假设属性集包含两个示图，但事先并不知道哪些属性属于哪个示图，试设计一个算法将两示图分离出来。根据已有的数据集将属性集分成二个集合，若遍历求最优解是指数级的复杂度。考虑使用一种局部最优的方法：设