周志华 《机器学习》 答案整理

来自于CSDN   四去六进一

第一章:

机器学习(周志华) 参考答案 第一章 绪论

机器学习(周志华西瓜书) 参考答案 总目录


1.表1.1中若只包含编号为1,4的两个样例,试给出相应的版本空间。

假设空间指的是问题所有假设组成的空间,我们可以把学习过程看作是在假设空间中搜索的过程,搜索目标是寻找与训练集“匹配”的假设。

假设数据集有n种属性,第i个属性可能的取值有ti种,加上该属性的泛化取值(*),所以可能的假设有i(ti+1)。再用空集表示没有正例,假设空间中一共i(ti+1)+1种假设。
现实问题中常面临很大的假设空间,我们可以寻找一个与训练集一致的假设集合,称之为版本空间。版本空间从假设空间剔除了与正例不一致和与反例一致的假设,它可以看成是对正例的最大泛化。
版本空间的可以通过搜索假设空间来得到,这样需要遍历完整的假设空间。如果数据集中有正例,则可以先对一个正例进行最大泛化,得到2n个假设,然后再对这些假设进行剔除操作,可以适当精简计算量。
西瓜数据集(精简)

编号 色泽 根蒂 敲声 好瓜
1 青绿 蜷缩 浊响
2 乌黑 稍蜷 沉闷

数据集有3个属性,每个属性2种取值,一共 333+1=28种假设,分别为

  • 1.色泽=青绿 根蒂=蜷缩 敲声=浊响
  • 2.色泽=青绿 根蒂=蜷缩 敲声=沉闷
  • 3.色泽=青绿 根蒂=稍蜷 敲声=浊响
  • 4.色泽=青绿 根蒂=稍蜷 敲声=沉闷
  • 5.色泽=乌黑 根蒂=蜷缩 敲声=浊响
  • 6.色泽=乌黑 根蒂=蜷缩 敲声=沉闷
  • 7.色泽=乌黑 根蒂=稍蜷 敲声=浊响
  • 8.色泽=乌黑 根蒂=稍蜷 敲声=沉闷
  • 9.色泽=青绿 根蒂=蜷缩 敲声=*
  • 10.色泽=青绿 根蒂=稍蜷 敲声=*
  • 11.色泽=乌黑 根蒂=蜷缩 敲声=*
  • 12.色泽=乌黑 根蒂=稍蜷 敲声=*
  • 13.色泽=青绿 根蒂=* 敲声=浊响
  • 14.色泽=青绿 根蒂=* 敲声=沉闷
  • 15.色泽=乌黑 根蒂=* 敲声=浊响
  • 16.色泽=乌黑 根蒂=* 敲声=沉闷
  • 17.色泽=* 根蒂=蜷缩 敲声=浊响
  • 18.色泽=* 根蒂=蜷缩 敲声=沉闷
  • 19.色泽=* 根蒂=稍蜷 敲声=浊响
  • 20.色泽=* 根蒂=稍蜷 敲声=沉闷
  • 21.色泽=青绿 根蒂=* 敲声=*
  • 22.色泽=乌黑 根蒂=* 敲声=*
  • 23.色泽=* 根蒂=蜷缩 敲声=*
  • 24.色泽=* 根蒂=稍蜷 敲声=*
  • 25.色泽=* 根蒂=* 敲声=浊响
  • 26.色泽=* 根蒂=* 敲声=沉闷
  • 27.色泽=* 根蒂=* 敲声=*
  • 28.空集Ø
    编号1的数据可以删除 2810121416182022242628(不包含数据1)
    编号1的数据可以删除 27(包含了数据2)
    所以版本空间为:
  • 1.色泽=青绿 根蒂=蜷缩 敲声=浊响
  • 9.色泽=青绿 根蒂=蜷缩 敲声=*
  • 13.色泽=青绿 根蒂=* 敲声=浊响
  • 17.色泽=* 根蒂=蜷缩 敲声=浊响
  • 21.色泽=青绿 根蒂=* 敲声=*
  • 23.色泽=* 根蒂=蜷缩 敲声=*
  • 25.色泽=* 根蒂=* 敲声=浊响
    一般情况下版本空间是正例的泛化,但由于数据集中只有1个正例,所以在版本空间中依然包含了这个样本的假设(假设1)。

2.与使用单个合取式来进行假设表示相比,使用“析合范式”将使得假设空间具有更强的表示能力。若使用最多包含k个合取式的析合范式来表达1.1的西瓜分类问题的假设空间,试估算有多少种可能的假设。


3.若数据包含噪声,则假设空间中可能不存在与所有训练样本都一致的假设。在此情形下,试设计一种归纳偏好用于假设选择

通常认为两个数据的属性越相近,则更倾向于将他们分为同一类。若相同属性出现了两种不同的分类,则认为它属于与他最临近几个数据的属性。也可以考虑同时去掉所有具有相同属性而不同分类的数据,留下的数据就是没误差的数据,但是可能会丢失部分信息。


4.本章1.4节在论述“没有免费的午餐”定理时,默认使用了“分类错误率”作为性能度量来对分类器进行评估。若换用其他性能度量l,试证明没有免费的午餐”定理仍成立


5.试述机器学习在互联网搜索的哪些环节起什么作用

1.最常见的,消息推送,比如某东经常说某些商品我可能会感兴趣,然而并没有。
2.网站相关度排行,通过点击量,网页内容进行综合分析。
3.图片搜索,现在大部分还是通过标签来搜索,不过基于像素的搜索也总会有的吧。

 

 

第二章

机器学习(周志华) 参考答案 第二章 模型评估与选择

原创 2016年07月29日 16:00:36

机器学习(周志华) 参考答案 第二章 模型评估与选择

机器学习(周志华西瓜书) 参考答案 总目录


1.数据集包含1000个样本,其中500个正例,500个反例,将其划分为包含70%样本的训练集和30%样本的测试集用于留出法评估,试估算共有多少种划分方式。

一个组合问题,从500正反例中分别选出150正反例用于留出法评估,所以可能取法应该是(C150500)2种。


2.数据集包含100个样本,其中正反例各一半,假定学习算法所产生的模型是将新样本预测为训练样本数较多的类别(训练样本数相同时进行随机猜测),试给出用10折交叉验证法和留一法分别对错误率进行评估所得的结果。

10折交叉检验:由于每次训练样本中正反例数目一样,所以讲结果判断为正反例的概率也是一样的,所以错误率的期望是50%。
留一法:如果留下的是正例,训练样本中反例的数目比正例多一个,所以留出的样本会被判断是反例;同理,留出的是反例,则会被判断成正例,所以错误率是100%。


3.若学习器A的F1值比学习器B高,试析A的BEP值是否也比B高。

F1值的大小与BEP值并没有明确的关系。
两个分类器的F1值得大小与他们的BEP值大小并没有明确的关系(没去找)
这道题这里用反推,设计两个BEP值相同的分类器,如果他们的F1值不一样,那么这道题的结论就是否定的
再加点我看了评论后的疑惑:
BEP值就是F1值吗?
BEP值是在P=R时取到的,也就是BEP=P=R。如果在计算F时也要定义P=R,那么F1Fβ将会恒等于BEP,那么P,R,F在这里有什么意义呢?
这里分两种情况:
第一就是我的理解,在计算F1时就是按照分类器真实的分类结果来计算P,R,再根据PR计算F1。当这个分类器正好P=R时,有P=R=BEP=F1。否则BEP的计算不能用当前的PR,而是通过一步一步尝试到查准率=查全率时,P’=R’=BEP。
第二种就是不存在我下面假设的分类器,分类器始终会在P=R的位置进行截断(截断指的是分类器将所有样本按分为正例的可能性排序后,选择某个位置。这个位置前面分类为正,后面分类为负)。但是这个可能吗?这种情况下F1=Fβ=BEP恒成立,分类器的评价本质将会变成了样本的正例可能性排序,而不是最终的样本划分结果。

分类器将所有训练样本按自己认为是正例的概率排序,排在越前面分类器更可能将它判断为正例。按顺序逐个把样本标记为正,当查准率与查全率相等时,BEP=查准率=查全率。当然分类器的真实输出是在这个序列中的选择一个位置,前面的标记为正,后面的标记为负,这时的查准率与查全率用来计算F1值。可以看出有同样的BEP值的两个分类器在不同位置截断可能有不同的F1值,所以F1值高不一定BEP值也高。
比如:

1/+ 2/+ 3/+ 4/+ 5/+ 6/- 7/- 8/- 9/- 10/-
1/+ 2/+ 3/+ 4/+ 6/- 5/- 7/- 8/- 9/- 10/-
1/+ 2/+ 3/+ 4/+ 6/+ 5/- 7/- 8/- 9/- 10/-

第一行是真实的测试样本编号与分类,第二三行是两个分类器对所有样本按为正例可能性的排序,以及判断的结果。显然两个分类器有相同的BEP值,但是他们的F1值一个是0.89,一个是0.8


4.试述真正例率(TPR)、假正例率(FPR)与查准率(P)、查全率(R)之间的联系。

查全率: 真实正例被预测为正例的比例
真正例率: 真实正例被预测为正例的比例
显然查全率与真正例率是相等的。
查准率:预测为正例的实例中真实正例的比例
假正例率: 真实反例被预测为正例的比例
两者并没有直接的数值关系。


5.试证明(2.22)AUC=1lrank

从书34页b图看来,AUC的公式不应该写的这么复杂,后来才发现原来这个图并没有正例反例预测值相等的情况。当出现这种情况时,ROC曲线会呈斜线上升,而不是这种只有水平和垂直两种情况。

由于一开始做题时并没有想过ROC曲线不可以是斜线,所以画了这张图,如果不存在正例反例预测值相等的情况,那么斜线也没必要存在。
但是在维基百科上看到一副图,貌似也存在斜线的ROC,但是不知道含义是否和我这里写的一样。
https://en.wikipedia.org/wiki/Receiver_operating_characteristic
引用一幅有斜线的ROC曲线
这里写图片描述

BEP一样,学习器先将所有测试样本按预测概率排序,越可能是正的排在越前面。然后依次遍历,每扫描到一个位置,里面如果只有正例,则ROC曲线垂直向上,如果只有反例,曲线水平往右,如果既有正例也有反例,则斜向上。如图所示
ROC曲线
由于TPRFPR的分母是常数,所以这里按比例扩大了坐标(分别是真实正例和真实反例的数目倍),可以更好看出曲线走势。

可以看出一共有20个测试样本,10个正,10个反。学习器排序的结果是
+,,(+,+),(+,),(+,),(+,+),(,),(+,+),(,,),+,。其中括号内的样本排在相同的位置。
<(+,+,,)(+,),(+,)是同样的效果>

公式2.21累加了所有不在正例的反例数目,其中同样的位置标记为0.5,在正例前面标记为1。从图中可以看出,折线每次向右(右上)延伸,表示扫描到了反例,折线上方对应的面积,就是该反例后面有多少个正例,每个正例是一个正方形,对应的面积是1。同位置上的正例是个三角形,对应的面积是0.5。计算出总面积后,由于ROC图的坐标是归一化的,所以总面积要除以一开始放大的倍数,也就是m+m


6.试述错误率与ROC曲线之间的关系

ROC曲线每个点对应了一个TPRFPR,此时对应了一个错误率。

学习器会选择错误率最小的位置作为截断点。


7.试证明任意一条ROC曲线都有一条代价曲线与之对应,反之亦然。

由定义可以知道TPRFPR都是由0上升到1,那么FNR则是由1下降到0
每条ROC曲线都会对应一条代价曲线,由于第一条代价线段的是(0,0),(1,1),最后是(0,1)(1,0),
所有代价线段总会有一块公共区域,这个区域就是期望总体代价,而这块区域的边界就是代价曲线,且肯定从(0,0)(1,0)
在有限个样本情况下,ROC是一条折线,此时根据代价曲线无法还原ROC曲线。但若是理论上有无限个样本,ROC是一条连续的折线,代价曲线也是连续的折线,每个点的切线可以求出TPRFNR,从而得到唯一的ROC曲线。


8.Min-Max规范化与z-score规范化如下所示。试析二者的优缺点。

Minmax规范化方法简单,而且保证规范化后所有元素都是正的,每当有新的元素进来,只有在该元素大于最大值或者小于最小值时才要重新计算全部元素。但是若存在一个极大(小)的元素,会导致其他元素变的非常小(大)。
zscore标准化对个别极端元素不敏感,且把所有元素分布在0的周围,一般情况下元素越多,0周围区间会分布大部分的元素,每当有新的元素进来,都要重新计算方差与均值。


9.试述卡方检验过程。

略(……)


10.试述在使用Friedman检验中使用式(2.34)与(2.35)的区别

第三章:

机器学习(周志华) 参考答案 第三章 线性模型

机器学习(周志华西瓜书) 参考答案 总目录


1.试分析在什么情况下,在以下式子中不比考虑偏置项b。

线性模型y=wtx+b,两个实例相减得到yiy0=wt(xix0),以此消除了b。所以可以对训练集每个样本都减去第一个样本,然后对新的样本做线性回归,只需要用模型y=wtx


2.试证明,对于参数w,对率回归(logistics回归)的目标函数(式1)是非凸的,但其对数似然函数(式2)是凸的。

如果一个多元函数是凸的,那么它的Hessian矩阵是半正定的。


3.编程实现对率回归,并给出西瓜数据集3.0α上的结果


4.选择两个UCI数据集,比较10折交叉验证法和留一法所估计出的对率回归的错误率。


5.编程实现线性判别分析,并给出西瓜数据集3.0α上的结果。


6. LDA仅在线性可分数据上能获得理想结果,试设计一个改进方法,使其能较好地用于非线性可分数据。

在当前维度线性不可分,可以使用适当的映射方法,使其在更高一维上可分,典型的方法有KLDA,可以很好的划分数据。


7.令码长为9,类别数为4,试给出海明距离意义下理论最优的EOOC二元码并证明之。

对于ECOC二元码,当码长为2n时,至少可以使2n个类别达到最优间隔,他们的海明距离为2(n1)。比如长度为8时,可以的序列为

1 1 1 1 -1 -1 -1 -1
1 1 -1 -1 1 1 -1 -1
1 -1 1 -1 1 -1 1 -1
-1 -1 -1 -1 1 1 1 1
-1 -1 1 1 -1 -1 1 1
-1 1 -1 1 -1 1 -1 1

其中4,5,6行是对1,2,3行的取反。若分类数为4,一共可能的分类器共有242种(排除了全1和全0),在码长为8的最优分类器后添加一列没有出现过的分类器,就是码长为9的最优分类器。


8.EOOC编码能起到理想纠错作用的重要条件是:在每一位编码上出错的概率相当且独立。试析多分类任务经ECOC编码后产生的二类分类器满足该条件的可能性及由此产生的影响。

理论上的ECOC码能理想纠错的重要条件是每个码位出错的概率相当,因为如果某个码位的错误率很高,会导致这位始终保持相同的结果,不再有分类作用,这就相当于全0或者全 1的分类器,这点和NFL的前提很像。但由于事实的样本并不一定满足这些条件,所以书中提到了有多种问题依赖的ECOC被提出。


9.使用OvR和MvM将多分类任务分解为二分类任务求解时,试述为何无需专门针对类别不平衡性进行处理。

书中提到,对于OvRMvM来说,由于对每个类进行了相同的处理,其拆解出的二分类任务中类别不平衡的影响会相互抵消,因此通常不需要专门处理。以ECOC编码为例,每个生成的二分类器会将所有样本分成较为均衡的二类,使类别不平衡的影响减小。当然拆解后仍然可能出现明显的类别不平衡现象,比如一个超级大类和一群小类。


10.试推出多分类代价敏感学习(仅考虑基于类别的错误分类代价)使用“再缩放”能获得理论最优解的条件。

题目提到仅考虑类别分类的误分类代价,那么就默认正确分类的代价为0。
于是得到分类表,(假设为3类)

0 c12 c13
c21 0 c23
c31 c32 0

 

机器学习(周志华) 参考答案 第四章 决策树

机器学习(周志华西瓜书) 参考答案 总目录


    如果说决策树这章还有什么遗憾,就是实在没找到一个好的树形图生成器,结果只能用Matlab上那么丑的图
  • 1
  • 2

1.试证明对于不含冲突数据(即特征向量完全相同但标记不同)的训练集,必存在与训练集一致(即训练误差为0)的决策树。

因为决策树是通过属性来划分,相同属性的样本最终肯定会进入相同的叶节点。一个叶节点只有一个分类,如果样本属性相同而分类不同,必然产生训练误差。反之,决策树只会在当前样本集合是同一类或者所有属性相同时才会停止划分,最终得到训练误差为0的决策树。


2.试析使用“最小训练误差”作为决策树划分选择的缺陷。

从机器学习最开始就讲起,最小训练误差并不可靠,由于过度学习样本特性最终导致严重的过拟合,而没有泛化能力。


3.试编程实现基于信息熵进行划分选择的决策树算法,并为表4.3中数据生成一棵决策树。


4.试编程实现基于基尼指数进行划分选择的决策树算法,并为表4.2中数据生成预剪枝、后剪枝决策树,并与未剪枝决策树进行比较。


5.试编程实现基于对率回归进行划分选择的决策树算法,并为表4.3中数据生成一棵决策树。


6.试选择4个UCI数据集,对上述3种算法所产生的未剪枝、预剪枝、后剪枝决策树进行实验比较,并进行适当的统计显著性检验。

这里要对上面三种实现的算法进行未剪枝,预剪枝,后剪枝做比较,对率回归划分就算了,都不知道是个什么情况,信息增益和基尼指数的差别并不大,其实就是为了比较未剪枝,预剪枝,后剪枝对测试样本的输出结果。显著性分析,对2种算法,3种剪枝方式的错误数做方差分析,信息增益和基尼指数有显著区别是拒绝的,未剪枝,预剪枝,后剪枝有显著区别是接受的。


7.图4.2是一个递归算法,若面临巨量数据,则决策树的层数会很深,使用递归方法易导致“栈”溢出,试使用“队列”数据结构,以参数maxDepth控制数的最大深度,写出与图4.2等价、但不使用递归的决策树生成算法。

直接用递归会导致大量的临时变量被保存,当层数过深时会导致“栈”溢出。
用队列对决策树进行层次遍历来生成,用Max_Depth来控制树的最大层数。队列中每个元素代表着决策树的每个节点,它必要的属性有:样本集合、剩余属性集合,当前层数指示,父节点序号。队列一开始里面只有一个元素,就是最初初始化,带着所有样本的根节点。然后当队列不为空的时候开始循环,每次取出一个元素,判断是否需要划分,如果不要,就是一个叶节点,出队列就不用管了;如果需要划分,那么找出最好的划分属性,然后划分成n个子区间,依次送入队列,继续循环,直到队列为空。
是否需要划分有3个依据:

  • 当前所有样本属于一类
  • 当前所有样本属性完全相同
  • 达到了Max_Depth的深度

这样就完成了层次遍历(广度优先搜索)对决策树的构建。
显然由于每次出队的元素要先完全划分,那么如果是进行预剪枝算法的决策树,用队列结构是非常方便的。
如果是后剪枝,那必须要等到最终整棵树完全生成,才能进行。


8.试将决策树生成的深度优先搜索过程修改为广度优先搜索,以参数MaxNode控制树的最大结点数,将题4.7中基于队列的决策树算法进行改写。对比题4.7中的算法,试分析哪种方式更易于控制决策树所需储存不超过内存。

队列结构看着不错,但是极端情况下,比如层树很低,但是分叉多,会导致队列内有大量元素。另外不能在决策树生成过程中很好的进行后剪枝,全树生成后再次统计会浪费大量时间。
用栈结构把递归转换为非递归是很好的方法,设置最大节点数MaxNode来保证节点数不会爆炸。栈结构内的元素组成与列队的基本相同:样本集合、剩余属性集合,当前层数指示,父节点序号。初始化也是一样,将一个包含所有样本的集合压入栈中,当栈不为空时,每次拿出栈顶的元素进行操作,如果不可以划分,则不做操作;如果可以划分,则划分出1个子集,先将剩余子集压回栈,再将划分出的子集压回栈。然后再取出一个元素,知道栈内没有元素为止。
是否需要划分有3个依据:

  • 当前所有样本属于一类
  • 当前所有样本属性完全相同
  • 达到了Max_node上限

栈也有他的问题,极端情况下会生成一棵畸形的二叉树,但就算这样内部元素也只是队列结构极端情况的一半。栈可以很好的进行后剪枝操作,当非叶节点所有叶节点生成后可以做后剪枝,由于划分子集的时候就需要计算各个属性样本数,所以这些操作代价并不高。对于一棵完整的树,后剪枝要对所有只拥有叶节点的非叶节点进行遍历,如果某个非叶节点可以剪枝,还需要进一步考虑它的父节点。虽然在某些剪枝需求不大的情况下生成树后剪枝有不错的效果,但是我觉得生成中判断更加方便,而且不需要太多额外的代码。


9.试将4.4.2节对缺失值的处理机制推广到基尼指数的计算中去。

只需要把信息增益的公式换成基尼指数就行,包括扩展到连续参数,缺失参数,都是很直观的方法。


10.从网上下载或自己编程实现任意一种多变量决策树算法,并观察其在西瓜数据集3.0上产生的结果。

机器学习(周志华) 参考答案 第五章 神经网络

机器学习(周志华西瓜书) 参考答案 总目录


    这章就是真正的两句话讲完一个知识点,然后后面还出个题让你编程

神经网络作为一个相当大的,多学科交叉的学科领域,并不是仅仅应用于机器学习。书上3张纸介绍了6种神经网络,都是泛泛几句话介绍。选了几本关于神经网络的书放进某东的购物车,等着下次300-200买起来慢慢研究。

1.试述将线性函数f(x)=wtx用作神经元激活函数的缺陷。

必须要强调的是,神经网络中必须要有非线性的激活函数,无论是在隐层,还是输出层,或者全部都是。如果单用wtx作为激活函数,无论多少层的神经网络会退化成一个线性回归,只不过是把他复杂化了。


2.试述使用图5.2(b)激活函数的神经元与对率回归的联系。

两者都是希望将连续值映射到{0,1}上,但由于阶跃函数不光滑,不连续的性质,所以才选择了sigmoid作为映射函数。不同之处在于激活函数不一定要使用sigmoid,只要是非线性的可导函数都可以使用。


3.对于图5.7中vih,试推导出BP算法中的更新公式。


4.试述学习率的取值对神经网络训练的影响。

如果学习率太低,每次下降的很慢,使得迭代次数非常多。
如果学习率太高,在后面迭代时会出现震荡现在,在最小值附近来回波动。


5.试编程实现标准BP算法与累积BP算法,在西瓜数据集3.0上分别用这个算法训练一个单隐层网络,并进行比较。


6.试设计一个BP改进算法,能通过动态学习率显著提升收敛速度。

这真是一个蛋疼的题,本来以为方法很多,结果没有一个能用的。

固定的学习率要么很慢要么在后期震荡,设计一种自适应的动态学习率算法是有必要的。

  • 对四种参数的最速方向做一位搜索
    这是很直观的一种方法,已知f(x)在x0的导数为d,那么下降方向就是-d。一位搜索就是求试f(x+td)最小的t,也就是当前的学习率。
    然而这方法的t用解析法并不好求,ft(x+td)=0也是无解的。
    使用近似方法尝试了下收敛速度并没有显著提升
  • 对四种参数做牛顿迭代
    虽然不符合题目改学习率的要求,但是牛顿法肯定能大大提高收敛速度,只是没有了学习率这个概念。
    然而Hessian矩阵求的我想吐血,最后也没去继续了。

书中给出了两篇文献供参考

  • Neural Networks: Tricks of the Trade
  • Neural Smithing:Supervised learning in Feedforward Artificial Neural Networks暂时不解这个题,等以后遇到好的方法再来更新。

7.根据式5.18和5.19,试构造一个能解决异或问题的RBF神经网络。


8.从网上下载或自己编程实现一个SOM网络,并观察在西瓜数据集3.0a上产生的结果。

SOM网络书上真的就是草草介绍了下,顺便配了个看不懂的图。我去翻了下《MATLAB神经网络43个案例分析》这本书,里面对SOM讲的还是很明白的,包括原理与训练方法。
简单的说,SOM网络在平面放M*N个神经元(M,N自定义),神经元按8邻接来连接。网络将输入层映射到平面上M*N个神经元上(M,N自定义),每个输入与每个神经元都有一个初始权值,然后计算各个神经元的权值向量与输入向量的距离,选择距离最小的神经元更新他以及他8邻接神经元的权值向量,循环这个过程直到收敛。
如果神经元比样本数多,足够多次迭代后所有样本会映射到了不同的神经元上。
网络生成后就通过输入算出离他最近的神经元,将它标记为该神经元的分类。
matlab中有现成的SOM网络,我就没自己编程了。

clear
simpleclassInputs = xlsread('C:\Users\icefire\Desktop\ml\西瓜3.xlsx', 'sheet1', 'A7:Q8');
net = newsom(simpleclassInputs,[8 8]);  %64个神经元
%迭代次数1000次
net.trainParam.epochs=1000; 
net = train(net,simpleclassInputs);
plotsompos(net,simpleclassInputs);
%获取每个样本映射到哪个神经元
sim(net,simpleclassInputs);

最终得到SOM网络为
SOM网络

64个神经元最终的位置,并可以查看样本映射到了哪个神经元上。


9.试推导用于Elman网络的BP算法。

Elman比正常网络多了个反馈,把前一次的bh作为隐层的输入来调节隐层。
假设用uih来表示反馈输入与隐层连接的参数,由于前一次计算的bh作为常数输入,uijvij的计算方法一样,Δuih=ηehbh,其中e_h书上5.15给出。就是相当于多了几个输入会变的输入层神经元。


10.实现一个卷积神经网络。

CNN作为深度学习一个重要工具,Stanford专门有个CS231n来讲CNN。等我把西瓜书弄完再回头解决这个问题,我感觉一时半会搞不定,还是先把机器学习基础的做完再说。

 

 

机器学习(周志华) 参考答案 第六章 支持向量机

机器学习(周志华西瓜书) 参考答案 总目录


    总的来说支持向量机这章书上讲的比较全面,公式和推到都比较详细,可惜的就是没有具体的SMO算法过程

1.试证明样本空间中任意点x到超平面(w,b)的距离为式(6.2)。

超平面(w,b)的平面法向量为w, 任取平面上一点x0,有wTx0+b=0x到平面的距离就是xx0的距离往w方向的投影,就是|wT(xx0)||w|=|wTx+b||w|


2.使用libsvm,在西瓜数据集3.0α上分别用线性核和高斯核训练一个SVM,并比较其支持向量的差别。

    由于电脑的vs是2015的,而matlab上最高只支持2013来编译libsvm,所以只能在vs上用libsvm了。

训练的结果是线性核与高斯核得到了完全一样的支持向量,由于没去分析libsvm内部是如何计算的,这里只贴结果。
第一列是支持向量的权值,后面则是支持向量对应的属性

ai x1 x2
1 0.697 0.46
1 0.744 0.376
1 0.634 0.264
1 0.608 0.318
1 0.556 0.215
1 0.403 0.237
1 0.481 0.149
1 0.437 0.211
-1 0.666 0.091
-1 0.243 0.267
-1 0.343 0.099
-1 0.639 0.161
-1 0.657 0.198
-1 0.36 0.37
-1 0.593 0.042
-1 0.719 0.103

3.选择两个UCI数据集,分别用线性核和高斯核训练一个SVM,并与BP神经网络和C4.5决策树进行实验比较。

使用的是iris数据集,选取其中分类为1,2的样本,各50个,4属性。
每类选前40个样本训练,后10个样本作为测试
线性核:找出3个支持向量

ai x1 x2 x3 x4
0.04 5.1 3.3 1.7 0.5
0.16 4.8 3.4 1.9 0.2
-0.20 4.9 2.5 4.5 1.7

偏置为1.50709
高斯核:找出9个支持向量

ai x1 x2 x3 x4
0.48 4.4 2.9 1.4 0.2
0.45 4.3 3 1.1 0.1
0.90 5.7 4.4 1.5 0.4
-0.17 6.3 3.3 6 2.5
-0.66 4.9 2.5 4.5 1.7
-0.03 6.5 3.2 5.1 2
-0.40 7.7 2.6 6.9 2.3
-0.15 6 2.2 5 1.5
-0.41 7.9 3.8 6.4 2

偏置为-0.212437
编写一个验证的matlab程序

tmp.xlsx验证数据表格

读取数据
w1 = xlsread('C:\Users\icefire\Desktop\ml\tmp.xlsx', 'sheet1', 'A1:C1');
w2 = xlsread('C:\Users\icefire\Desktop\ml\tmp.xlsx', 'sheet1', 'D1:L1');
x1 = xlsread('C:\Users\icefire\Desktop\ml\tmp.xlsx', 'sheet1', 'A2:C5');
x2 = xlsread('C:\Users\icefire\Desktop\ml\tmp.xlsx', 'sheet1', 'D2:L5');
x = xlsread('C:\Users\icefire\Desktop\ml\tmp.xlsx', 'sheet1', 'A7:T10');

y1=zeros(20,1);
y2=zeros(20,1);
%验证线性核
for i=1:20
    for j=1:3
        y1(i)=y1(i)+w1(j)*(x(:,i)'*x1(:,j));
    end
end

y1=y1+1.50709;
%验证高斯核
for i=1:20
    for j=1:9
        y2(i)=y2(i)+w2(j)*exp(-0.25*(x2(:,j)-x(:,i))'*(x2(:,j)-x(:,i)));
    end
end
y2=y2-0.212437;

得到结果表格如下

y1 y2 y
1.155205016 1.164557907 1
0.997242309 0.780919564 1
1.148298718 1.068992278 1
0.906038093 1.085988234 1
0.842638654 1.042299416 1
1.035492502 1.062906963 1
1.062585631 1.141980465 1
1.09304642 1.100071803 1
1.101546038 1.141056647 1
1.103671899 1.13405161 1
-1.839224592 -1.049900524 0
-1.542242776 -0.95432202 0
-1.471406411 -1.085122464 0
-1.958761346 -1.084832335 0
-1.895362864 -1.029274823 0
-1.608120552 -1.002438466 0
-1.448029593 -1.0262247 0
-1.519044109 -1.03794725 0
-1.658415695 -0.995288562 0
-1.402518712 -1.058306748 0

这里没和神经网络和决策树做对比了,这个数据集的数据线性可分,应该都是0误差。


4.讨论线性判别分析与线性核支持向量机在何种情况下等价。

在线性可分的情况下,LDA求出的wl与线性核支持向量机求出的wswlws=0,即垂直,此时两者是等价的。

当初在做这个题的时候也没细想,就想当然的认为在线性可分时两者求出来的w会垂直,现在看来并不一定。
首先,如果可以使用软间隔的线性SVM,其实线性可分这个条件是不必要的,如果是硬间隔线性SVM,那么线性可分是必要条件。这个题只说了是线性SVM,就没必要关心数据是不是可分,毕竟LDA是都可以处理的。
第二,假如当前样本线性可分,且SVM与LDA求出的结果相互垂直。当SVM的支持向量固定时,再加入新的样本,并不会改变求出的w,但是新加入的样本会改变原类型数据的协方差和均值,从而导致LDA求出的结果发生改变。这个时候两者的w就不垂直了,但是数据依然是可分的。所以我上面说的垂直是有问题的。
我认为这个题的答案应该就是,当线性SVM和LDA求出的w互相垂直时,两者是等价的,SVM这个时候也就比LDA多了个偏移b而已。


5.试述高斯核SVM与RBF神经网络的联系

RBF网络的径向基函数与SVM都可以采用高斯核,也就分别得到了高斯核RBF网络与高斯核SVM。
神经网络是最小化累计误差,将参数作为惩罚项,而SVM相反,主要是最小化参数,将误差作为惩罚项。
在二分类问题中,如果将RBF中隐层数为样本个数,且每个样本中心就是样本参数,得出的RBF网络与核SVM基本等价,非支持向量将得到很小的w.
使用LIBSVM对异或问题训练一个高斯核SVM得到α,修改第5章RBF网络的代码,固定β参数为高斯核SVM的参数,修改每个隐层神经元的中心为各个输入参数,得到结果w,wα各项成正比例。


6.试析SVM对噪声敏感的原因。

SVM的目的是求出与支持向量有最大化距离的直线,以每个样本为圆心,该距离为半径做圆,可以近似认为圆内的点与该样本属于相同分类。如果出现了噪声,那么这个噪声所带来的错误分类也将最大化,所以SVM对噪声是很敏感的。


7.试给出式(6.52)的完整KT条件。

非等式约束写成拉格朗日乘子式,取最优解要满足两个条件

  • 拉格朗日乘子式对所有非拉格朗日参数的一阶偏导为0
  • 非等式约束对应的拉格朗日项,要么非等式的等号成立,要么对应的拉格朗日参数为0

所以得到完整KT条件


8.以西瓜数据集3.0α的“密度”属性为输入,“含糖率”为输出,使用LIBSVM训练一个SVR。

含糖率和密度有什么必然联系吗?训练后得到的支持向量为

αi 密度xi
1 0.697
1 0.744
0.798 0.608
-1 0.666
0.452 0.243
-1 0.245
-0.25 0.343
1 0.36
-1 0.593
-1 0.719

偏置为 0.213589
得到含糖率与密度的关系
假设密度为x


9.试使用和技巧推广对率回归,产生“核对率回归”。


10.设计一个显著减少SVM中支持向量数目而不显著降低泛化性能的方法。
对于线性的SVM,三个属性不完全一样的支持向量就能确定这个SVM,而其他的落在边缘上的点都可以舍弃。
还没太想明白,以后有机会更新。

 

 

 

机器学习(周志华) 参考答案 第七章 贝叶斯分类器

机器学习(周志华西瓜书) 参考答案 总目录


    看了半天依然没看懂如何去优化贝叶斯网,9,10题先空着
  • 1
  • 2

1.试使用极大似然法估算西瓜数据集3.0中前3个属性的类条件概率。


2.试证明:条件独立性假设不成立时,朴素贝叶斯分类器任有可能产生最优分类器。

朴素贝叶斯分类器就是建立在条件独立性假设上的。当有不独立的属性时,假如所有样本不独立的属性取值相同时分类也是相同的,那么此时朴素贝叶斯分类器也将产生最优分类器。


3.试编程实现拉普拉斯修正的朴素贝叶斯分类器,并以西瓜数据集3.0为训练集,并对“测1”样本进行分类。


4.实践中用式(7.15)决定分类类别时,若数据的维度非常高,则连乘的概率结果会非常接近0并导致下溢。试述防止下溢的可能方案。

若连乘的式子太多,导致乘积接近0。由于属性个数是已知的,可以对每个乘式做适当次的开方处理,可以保证结果不会为0。另外也可以对各项取对数,当累加太多时,可能导致和接近负无穷。可以对每个加数除以属性的个数,来防止溢出。


5.试证明:二分类任务中两类数据满足高斯分布且方差相同时,线性判别分析产生最优贝叶斯分类器。


6.试编程实现AODE分类器,并以西瓜数据集3.0为训练集,并对“测1”样本进行分类。


7.给定d个二值属性的分类任务,假设对于任何先验概率的估算需要30个样本。试估计AODE中估算先验概率p(c,xi)所需要的样本数。

显然对于正负样本,各属性对应的取值xi需要出现30次。
最好的情况下,只需要60个样本就能就能估算概率。其中30个xi属性的样本取值为1,30个xi属性的样本取值为0。尽管这不符合实际情况(相同属性取值不同)。
最坏的情况下,要60d个样本才能估算。其中每个样本只有一个属性和测试样本xi相同,其余都是另一个取值。


8.考虑图7.3,证明:在同父结构中,若x1的取值未知,则x3x4不成立。在顺序结构中,yz|x成立,但yz不成立。

 

 

机器学习(周志华) 参考答案 第八章 集成学习

机器学习(周志华西瓜书) 参考答案 总目录


    学了那么多分类器,但真正应用起来都是将这些分类器进行集成学习,达到更好的泛化效果。

1.假设硬币正面朝上的概率为p,反面朝上的概率为1-p。令H(n)代表抛n次硬币所得正面朝上的次数,则最多k次正面朝上的概率为P(H(n)k)=ki=0(ni)pi(1p)ni。对δ>0k=(pδ)ne2δ2n试推导出(8.3)。


3.自己编程实现一个AdaBoost,以不剪枝决策树为基学习器,在西瓜数据集3.0α上训练一个AdaBoost集成,并与图8.4比较。


4.GradientBoosting是一种常用的Boosting算法,是分析其与AdaBoost的异同。

GradientBoosting与AdaBoost相同的地方在于要生成多个分类器以及每个分类器都有一个权值,最后将所有分类器加权累加起来
不同在于:
AdaBoost通过每个分类器的分类结果改变每个样本的权值用于新的分类器和生成权值,但不改变每个样本不会改变。
GradientBoosting将每个分类器对样本的预测值与真实值的差值传入下一个分类器来生成新的分类器和权值(这个差值就是下降方向),而每个样本的权值不变。


5.试编程实现Bagging,以决策树桩为学习器,在西瓜数据集3.0α上训练一个Bagging集成,并与8.6进行比较。


6.试述为什么Bagging难以提升朴素贝叶斯分类器的性能。

Bagging主要是降低分类器的方差,而朴素贝叶斯分类器没有方差可以减小。对全训练样本生成的朴素贝叶斯分类器是最优的分类器,不能用随机抽样来提高泛化性能。


7.试述随即森林为什么比决策树Bagging集成的训练速度快。

随机森林不仅会随机样本,还会在所有样本属性中随机几种出来计算。这样每次生成分类器时都是对部分属性计算最优,速度会比Bagging计算全属性要快。


8.MultiBoosting算法与Iterative Bagging的优缺点。

MultiBoosting由于集合了Bagging,Wagging,AdaBoost,可以有效的降低误差和方差,特别是误差。但是训练成本和预测成本都会显著增加。
Iterative Bagging相比Bagging会降低误差,但是方差上升。由于Bagging本身就是一种降低方差的算法,所以Iterative Bagging相当于Bagging与单分类器的折中。


9.试设计一种可视化多样性度量,并与k-误差图比较。

暂无


10.试设计一种能提升k近邻分类器性能的集成学习算法。

可以使用Bagging来提升k近邻分类器的性能,每次随机抽样出一个子样本,并训练一个k近邻分类器,对测试样本进行分类。最终取最多的一种分类。

 

 

机器学习(周志华) 参考答案 第九章 聚类

机器学习(周志华西瓜书) 参考答案 总目录


    聚类由于不存在客观标准,任何有点道理的角度都能提出新的聚类算法。

这里写图片描述


3.试析k均值算法能否找到最小化(9.24)的最优解。

不能,因为k均值算法只是局部最有的近似算法,只能找到初始化均值附近的局部最优解,无法找到全局最优解。


4.编程实现k均值算法,设置三组不同的k值,三组不同的初始中心点,在西瓜数据集4.0上进行实验,并讨论什么样的初始中心有利于取得好结果。


5.基于DBSCAN的概念定义,若x为核心对象,有x密度可达的所有样本构成的集合X,试证明:X满足连接性和最大性。

由题意显然最大性是满足的。
连接性:假设xi为核心对象,由于xj可以由xi密度可达。则存在核心对象xk,使得xixk密度直达,xkxj密度直达。由于xk是核心对象,则xkxi密度直达。且密度直达是密度可达的子集,所以xkxj密度可达,xkxi密度可达,所以xixj密度相连。


6.试析AGNES算法使用最小距离和最大距离的区别。

最大距离可以认为是所有类别先生成一个能包围所有类内样本的最小圆,然后所有圆同时慢慢扩大相同的半径,哪个类圆能完全包围另一个类则停止,并合并这两个类。由于此时的圆已经包含另一个类的全部样本,所以称为全连接。
最小距离则是扩大时遇到第一个非自己类的点就停止,并合并这两个类。由于此时的圆只包含另一个类的一个点,所以称为单连接。


7.聚类结果中若每个簇都有一个凸包,且凸包不相交,则称为凸聚类。试析本章介绍的哪些聚类方法只能产生凸聚类,哪些能产生非凸聚类。

显然高斯混合聚类是一种可能产生非凸的聚类方式。
高斯混合聚类并不是去最小化类间均方误差,而是通过概率模型来计算每个样本属于每个分类的概率,最后概率最大的。高斯混合概率模型不再单纯与均值相关,而且和方差(协方差)有关,所以不再一定得到凸聚类。
其余如k-means,LVQ,DBSCAN,AGNES都是凸聚类。


8.试设计一个聚类性能度量指标,并与9.2比较。

略。


9.是设计一个能用于混合属性的非度量距离。

混合属性中的连续属性,可以标准的距离为距离参数。
对于非连续属性的距离参数,可以将属性看成是字符串,计算距离时,一对一对比两个字符串各个位置的值相同的次数,并通过计算求出距离。比如两个字符串长度分别为li,l2,一共对比lil2次,相同的字符为k,那么距离参数可以认为是t(1klil2),t为一个合适缩放倍数。
然后通过指数函数将距离参数影射成真正的距离,此时的距离是非度量距离。


10.实现一种能自动确定聚类数的改进k均值算法,编程实现并在西瓜数据集上运行。

 

机器学习(周志华) 参考答案 第十章 降维与度量学习

机器学习(周志华西瓜书) 参考答案 总目录


1.编程实现k邻近分类器,在西瓜数据集3.0α上比较其与决策树分类边界的异同。


2.令err,err分别表示最近邻分类器与贝叶斯最优分类器的期望错误率,试证明:


3.在对高维数据降维前应该先进性“中心化”,常见的方法是将协方差阵XXT转换为


4.在实践中,协方差阵XX^T的特征值分解常由中心化后的样本矩阵X的奇异值分解替代,试讲述原因。

假设样本阵X是k*m矩阵,其中m是样本数,k是维度。
使用协方差阵求特征值分解时,协方差阵与属性的维度成平方比,这需要占用大量的空间。当属性维度与样本数差距巨大时,这种不必要的开销更加明显。
对样本矩阵进行奇异值分解,很明显非0奇异值的个数m’,肯定不会大于样本数和属性维度较小的一个(一般情况k>>m),这样使得求出来的特征向量阵为km(mm),显然当m<<k时,mk的开销会远远小于k2


5.降维中涉及的投影矩阵通常要求是正交的,试述正交非正交投影矩阵用于降维的优缺点。

当特征向量两两正交时,任何两种属性都是相互独立的,其中一个的取值不会影响另一个。但是属性并非全部不相关,比如书上说的,西瓜的体积和重量,显然是正相关的。这时如果两个属性的特征向量不成交会有更好的效果。


6.试使用matlab的PCA函数对人脸数据进行降维,并观察前20个特征向量对应的图像。


7.试述核化线性降维与流型学习之间的联系与优缺点。

非线性核的线性降维与流型学习都属于非线性降维。
核化线性降维有线性降维的优点,比如KPCA与保留了最主要的特征,计算方法简单,使用非线性核可以实现非线性降维。缺点一个是核化后的缺点,复杂度与样本总数成正比,当样本很多时复杂度会很高;另外由于PCA使用的正交空间,如果属性相关性比较大,会出现不好的结果。
流型学习:流形在局部具有欧式空间的性质,能用欧氏距离来进行距离计算。它的优点就是把高维中不能直接计算的距离使用局部距离来累计表示。比如Isomap,它使用测地线距离来表示高维距离。缺点一是如果本的分布不均匀,导致设置的k近邻或e距离近邻中存在短路与断路的存在,不利于计算全局距离。二是并没有特别好的方法去计算新样本的低维坐标。


8.k近邻与e近邻图存在短路和断路问题会给Isomap造成困扰,设计一个来缓解。

短路是由于k与e设置过大造成的,断路是因为k与e太小或者样本分布问题造成的。
比如5个远离其他样本,但他们5个靠的很近,导致5近邻时他们与其他所有样本距离无穷远而导致断路。
这里设计一条规则来解决这个问题:
假设每个点寻找到一个近邻,就连上一条边
那么对每个点遍历寻找近邻的时候,至少要加入一条新的边。
这样可以解决断路问题。至于新增加的边,就是该样本未连边的样本中离它最近的样本。


9.设计一个方法为新样本找到LLE降维后的低维坐标。

如书236的方法,为新样本x寻找它的近邻,设集合为Q
通过最小化平方误差min|xiQwixi|2求出各近邻点的权值。
把求出权值与近邻点在低维坐标线性组合求出新样本的坐标。
z=iQzwizi


10.试述如何确保度量学习产生的距离能满足距离度量四条基本性质。

 

 

机器学习(周志华) 参考答案 第十一章 特征选择与稀疏学习

机器学习(周志华西瓜书) 参考答案 总目录


    压缩感知这个以前别人嘴里很高端的名次,现在终于自己遇到了。
  • 1
  • 2

1.试编程实现Relief算法,并考察其在西瓜数据集3.0上的运行结果。


2.试写出Relief-F的算法描述。

相比Relief增加了多分类的样本所占的比例,很奇怪为什么相同的分类不需要乘上对应的比例。

------------------------------------------------
输入:
    数据集D;

过程:
将数据集连续属性参数用Min-max归一化
计算数据集各样本分类的概率p
计算数据集各样本两两距离dist
for x in D
    根据$dist$找出各分类离$x$最近的样本集合$xmin$
    for xm in xmin
        if(x分类与xm相同)
            for i=1:k
                θ_i=θ_i-diff(x_i,xm_i)^2
            end for
        else
            for i=1:k
                θ_i=θ_i+p_i*diff(x_i,xm_i)^2
            end for         
        end if
    end for
end for

输出:
各属性相关统计量θ
------------------------------------------------

3.Relief算法是分别考察每个属性的重要性,是设计一个能考虑每对属性重要性的改进算法。

由于过滤式的算法都是很老的算法了,并没有去想太多。
一个简单的方法,将单一属性的相关统计量计算出来后,两两相加得到每对属性的相关统计量。不过这样并没有什么用,所有属性还是认为互不相关。


4.试为LVW设计一个改进算法,即便有运行时间限制,该算法也一定能给出解。

LVW结束循环的条件是连续T次随机出来的特征都比当前最优特征集合要差。当T和特征集合A很大时,LVW需要的迭代时间很长。如果有运行时间限制,可以再给定一个结束条件,设最多迭代次数t,当总迭代次数达到t的时候,结束迭代并返回当前最优的特征集合。t的值根据限定的时间来估计。


5.结合图11.2,是举例说明L1正则化在何种情形下不能产生稀疏解。

如图所示,如果平方误差等值线与坐标轴相交前就与L1范数等值线相交了,就无法得到稀疏解。
L1正则化


6.试析岭回归与支持向量机的联系。


7.试述直接求解L0范数正则化会遇到的困难。

由于L0范数不连续,非凸,无法用解析法很好的表示,只能通过遍历来寻求最优解,这导致L0范数的最优化为题是个NP难问题。


8.试给出求解L1范数最小化问题中的闭式解(11.14)的详细推到过程。


9.试述字典学习与压缩感知对稀疏性利用的异同。

字典学习通过学习出的字典使属性适度稀疏,使得文本数据在字频上线性可分,从而提升如SVM获得更好的性能。
压缩感知则是希望原始信号本身虽然不稀疏,但是他内部是高度相关的,这样可以通过x=Ψs,使得s是一个稀疏的向量。此时通过采样信号y来还原s时可以得到足够接近的结果,从而更好的还原原始信号x。


10.试改进(11.15),以学习出具有分组稀疏性的字典。

 

 

机器学习(周志华) 参考答案 第十三章 半监督学习

机器学习(周志华西瓜书) 参考答案 总目录



3.假设数据由混合专家模型生成,即数据是基于k个成分混合的概率密度生成:p(x|θ)=kiαip(x|θi),其中θ为模型参数。假设每个混合成分对应一种类别,但每个类别可能包含多个混合成分。试推导出生成式半监督学习算法。


4.实现TSVM算法,选择两个UCI数据集,将其中30%作为测试样本,10%作为训练样本,60%作为无标记样本,分别训练出利用无标记样本的TSVM和仅利用有标记样本的SVM,并比较其性能。


5.对未标记样本进行标记指派与调整过程中可能出现类别不平衡问题,试给出该问题改进的TSVM算法。


6.TSVM对未标记样本进行标记指派与调整过程涉及很大的计算开销,试设计一个高效的改进算法。

在标记调整过程中,可以考虑每次将最有可能指派错误的样本进行调整,即正负伪标记样本中松弛变量最大且大于1的样本进行标记更改,可以减少迭代的次数。


7.试设计一个能对新样本进行分类图半监督算法。

图半监督算法不会直接对新样本进行分类,可行的办法一是将新样本作为无标记样本再次进行图半监督算法。或者使用已有标记的样本训练一个学习器,再对新样本分类。


8.自训练是一种比较原始的半监督学习方法:它现在有标记的样本上学习,然后在无标记的样本上获得伪标记,再在全部样本上进行重复训练,分析该方差有何缺陷。

由于训练样本远远少于无标记样本,如果将全部无标记样本的伪标记直接作为训练样本,将导致很多样本属于噪声样本,十分影响分类器的准确度。应该进行局部伪标记调整来优化分类器,而不是直接使用全部的伪标记重复训练分类器。


9.给定一个数据集,假设属性集包含两个示图,但事先并不知道哪些属性属于哪个示图,试设计一个算法将两示图分离出来。

根据已有的数据集将属性集分成二个集合,若遍历求最优解是指数级的复杂度。
考虑使用一种局部最优的方法:
设置两个集合,初始时一个集合包含全部属性,另一个为空。
从集合1随机选取一个集合放入集合2。
然后开始迭代:
每轮迭代从集合1选择一个属性放入集合2,使得集合2属性的训练误差减小量与集合1属性的训练误差增加量最小。
当两个属性集合训练结果符合停止标准时,停止迭代。


10.试为图13.7算法第10行写出违约检测算法。

机器学习(周志华) 参考答案 第十四章 概率图模型

原创 2016年12月08日 17:32:36

机器学习(周志华西瓜书) 参考答案 总目录


1.试用盘式记法表示条件随机场和朴素贝叶斯分类器。

条件随机场:
这里写图片描述
这样画的问题在于无法表示N个y之间的关系,到底怎么画我也不知道。

朴素贝叶斯分类器:y依赖于所有的变量x

这里写图片描述


2.证明图模型中的局部马尔可夫性:给定某变量的邻接变量,则该变量条件独立于其他变量。

直接使用全局马尔科夫性:将两个非邻接的变量看成A和C,肯定存在A的所有邻接变量集合的子集B,把A和C分离(否则与条件矛盾),所以A和C独立。


3.证明图模型中的正对马尔科夫性:给定其他所有变量,则两个非邻接变量条件独立。

直接使用全局马尔科夫性:将两个非邻接的变量看成A和C,其他已知的变量为B。显然B把A,C给分离了,所以A和C独立。


4.试述在马尔科夫随机场中为何仅需对极大团定义势函数。

显然极大团的势函数可以看成是所有子团势函数的联合分布,再乘上规范化因子使得ψ(x)是正确的概率。


5.比较条件随机场和对率回归,试析其异同。

这里引用crftut-fnt书里的图
这里写图片描述


6.证明变量消去法的计算复杂度随图模型中极大团的增长而呈指数增长,但随着节点数的增长未必呈指数增长。

 

7.吉布斯采样可以看作MH算法的特例,但吉布斯采样中未使用“拒绝采样”的策略,试述这样做的好处。

MH算法通过拒绝采样最终能生成平稳的马尔科夫链,但是有时因为拒绝概率太大导致状态转移频繁的被拒绝,使得算法效率低下。
吉布斯采样通过每次仅改变一个变量,其他变量保持不变的方法,使得每次改变仅在一个维度,此时接受率为100%,所以不再拒绝,提升了效率。


8.平均场是一种近似推断方法。考虑式(14.32),试析平均场法求解的近似问题与原问题的差异,以及实践中如何选择变量服从的先验分布。

平均场法通过将多元变量z拆分成数个相互独立的多远变量zi,然后单独求出每一个zi最有可能的分布来简化问题。第一个差异是多个变量的独立性假设并不一定存在,所以选择变量时尽可能将相关性较大的划为一组,以此逼近真实解。第二是假设每个zi所服从的先验分布,如果假设不当会造成该方法结果效果很差。所以应该根据当前子变量集合的现有样本数据进行估计,结合可能的专业知识,来得到较好的分布假设。


9.从网上下载或者自己实现LDA,分析《天龙八部》中每10回的话题演变情况。


10.试设计一个无须事先指定话题数目的LDA改进算法。

暂无

 

 

 

机器学习(周志华) 参考答案 第十五章 规则学习

原创 2016年12月17日 16:54:00

机器学习(周志华西瓜书) 参考答案 总目录

http://blog.csdn.net/icefire_tyh/article/details/52064910


    好忙啊好忙啊好忙啊,这章和我的研究方向关系不大,暂时先偷工减料一下下。
  • 1
  • 2

1.对西瓜数据集2.0,允许使用否定形式的文字,试基于自顶向下的策略学出命题规则集。

    1,2题共同的问题是,如果有错误的数据怎么办?没想明白--
  • 1
  • 2

2.对西瓜数据集2.0,在学习过程中通过删除文字,将常量转换为变量来进行规则泛化,试基于自底向上的策略学出命题规则集。


3.从网上下载或自己编程实现RIPPER算法,并在西瓜数据集2.0上学出规则集。

没做,以后如果用到相关领域再回来补全。


4.规则学习也能对数据缺失进行学习,试模仿决策树的缺失值处理方法,基于序贯覆盖在西瓜数据集2.0α上学出命题规则集。

与决策树一样,为每个样例加入权值,缺失处认为是该属性每个取值等比例分配。比如摸个样例一个属性上可以有3种取值,这就相当于有3个样例,每个样例的权值是13。一个方法是利用权值构造新数据集,然后可以直接调用1,2题的代码求解,另一个方法就是重新写一个程序-_-。


5.从网上下载或自己编程实现RIPPER算法,允许使用否定的文字,在西瓜数据集5.0上学出一阶规则集。

请看第3题


6.对西瓜数据集5.0,试利用归纳逻辑学习概念“更坏”。

利用归纳逻辑学习概念“更坏”,并不是太明白怎么做,LGG还是后面的逆归结?
如果说是用一阶规则学习,使用FOIL增益来选择属性,那就比较简单了。

西瓜数据集5.0是根据对西瓜数据集2来的,可以通过对西瓜数据集2来生成5的数字形式。
可以用0,1,2分别代表每个属性对比的程度,比如颜色:0相同,1更深,2更浅。
新数据集仲样例数是西瓜2中正例数与反例数的乘积。

之后就转换成了第一题,只是在选择最佳属性时不再看比例,而是使用FOIL。正反例的判断上改成如果选择的属性取值完全一样,就是整正例,完全相反则是反例,其他的都是未被覆盖的例子。

如果思路没错,代码和题目1的差距并不大,如果思路错了,代码写了也是错的,所以。


7.证明:对于一阶公式r1r2,不存在既能特化为r1r2,也能泛化为他们的LGG的一阶公式r

这题有点像证明:给定两个数x,y,不存在即是x和y的约数,又比他们的最大公约数大的数。看着不是很明显吗,不然还叫什么最大公约数或者最小一般泛化。
证:
假设: r1=rs1rn1; r2=rs2rn2
其中 rsr1r2的相同谓词,rnr1r2的不同谓词
那么显然如果r能特化到r1r2,那么必然能特化到rs,也就是LGG,所以不能泛化到LGG。


8.试生成一个西瓜数据集5.0的LGG集合。

这个题目并没有太看懂,如果仅仅给出两条规则,我知道怎么去求LGG,但是如何去求一个数据集的LGG?
如果是所有规则全部一起去求 ,最终会得到<(),因为不相同的谓词全部扔了。
疑惑


9.一阶原子公式是一种递归定义的公式,形如P(t1,t2,...,tn),其中P是谓词或者函数符号,ti称作“项”,可以使逻辑常量,变量或者其他原子公式。对一阶原子公式Ei的集合S={E1,E2,...,En},设计一个算法求其MGU。

对于所有原子公式,如果相同的字符出现在不同的位置上,这时候很有可能(或者一定?)无法合一。
并没有去多想,按顺序两两合一球出来的应该不是MGU。或者是每次得到一个置换,就将后面所有相同的字符全部置换,不知道这样行不行。


10.对于序贯覆盖的规则学习在学习下一条规则前,会将已被当前规则集覆盖的样例从训练集仲删去。这种贪心策略似的后续学习只关心以往未覆盖的样例,不考虑前后样例的相关性;但该策略是的后续能参考的样例越来越少,试设计一种不删除样例的规则学习算法。

书上介绍的序贯覆盖的规则学习方法,最终球出来的规则都不会覆盖相同的数据集,这导致后续规则参考太少导致太‘特别’。比如一条规则只对应一个样例。
所以要做的就是让生成的规则可以覆盖相同的样例。
自顶向下:书中的方法是:一开始的属性集合为空,然后选择最佳的属性加入集合,加入后覆盖的正样例比例最高,循环操作最后使得覆盖的样例全为正例。记录这条规则,并将这条规则覆盖的正例从数据集删除,再从头开始,直到数据集中只有反例。(参考第一题)

修改:
1.可以参考AdaBoost的方法,为每个数据加入一个权值,初始都为1。
2.每轮规则生成后,被覆盖的样例不再删除,而是将权值除以一个常数,比如3。
3.同样修改属性选择时求正例比例的方法,将权值加入。

只是想象,并没有去操作,不知道行不行。

自底向上:书中的方法是:选择数据集第一条样例的属性,将其放入属性集合,然后依次删除一个属性,使得覆盖的正例最多,同时不能覆盖到反例,直到无论删除哪个属性都无法覆盖新的正例,或者会覆盖反例。记录这条规则,并将这条规则覆盖的正例从数据集删除,再从头开始,直到数据集中只有反例。(参考第二题)

修改:
只需要改一点点,不再删除被当前规则集覆盖的正例,而是每次选择数据集第一个正例属性改成第一个未被规则集覆盖的正例属性,终止条件改为所有正例被当前规则集覆盖。

这两个程序其实根据1,2题代码并不难改,所以就不改了。
(那个太难不想写,这个太简单不想写)

Leave a Reply

Your email address will not be published. Required fields are marked *