机器学习习题答案

来源：智榕旅游

2.5（题目略）

(a).第一步：S0{<(QQQQ),(QQQQ)>}G0{<(????),(????)>}第二步：S1{<(malebrowntallUS),(femaleblackshortUS)>G1{<(????),(????)>}第三步：S2{<(malebrown??),(femaleblackshortUS)>G2{<(????),(????)>}第四步：S3{<(malebrown??),(femaleblackshortUS)>G3{<(male???),(????)>，,}第五步：S4{<(malebrown??),(female?short?)>G4{<(male???),(????)>}(b).假设中的每个属性可以取两个值，所以与题目例题一致的假设数目为：（2*2*2*2）*（2*2*2*2）=256(c).这个最短序列应该为8，2256

如果只有一个训练样例，则假设空间有2256个假设，我们针对每一个属性来设置训练样例，使每次的假设空间减半。则经过8次训练后，可收敛到单个正确的假设。,,,,,,,,(d).若要表达该实例语言上的所有概念，那么我们需要扩大假设空间，使得每个可能的假设都包括在内，这样假设空间就远远大于256，而且这样没法得到最终的没法收敛，因为对每一个未见过的训练样例，投票没有任何效果，因此也就没有办法对未见样例分类。所以不存在一个最优的查询序列。882.6完成变型空间表示定理的证明（定理2.1）

定理2.1：变型空间表示定理领X为一任意的实例集合，H为X上定义的布尔假设的集合。令c：X{0,1}为X上定义的任一目标概念，并令D为任一训练样例的集合{}。对所有的X，H，c，D以及良好定义的S和G：VSHD{hH|(sS)(gG)(gghgs}

证明：对VSH，D中任一h：①当h∈S时，取s＝h，则有h≥gs成立②当hS时，即(h1H）[(h>gh1)∧Consistent(h1,D)]若h1S，显然h≥gs成立；1否则有(h2H）[(h1>gh2)∧Consistent(h2,D)]同样或者h2S，则h>gh1≥gs成立；或者(h3H）[(h2>gh3)∧Consistent(h3,D)]如此下去，必存在一个序列h>gh1>gh2>g…>ghnS故也有(sS)h≥gs同理，对VSH，D中任一h：①当hG时，取g＝h，则有g≥gh成立②当hG时，即(h1H）[(h1>gh)∧Consistent(h1,D)]若h1G，显然g≥gh成立；否则有(h2H）[(h2>gh1)∧Consistent(h2,D)]同样或者h2G，则g=h2>gh1≥gh成立；或者(h3H）[(h3>gh2)∧Consistent(h3,D)]如此下去，必存在一个序列g=hn>g…>gh2>gh1>gh，故也有(gG)g≥gh2.9（题目略）

对每个属性进行如下操作：令ai=T，遍历样例集，如果样例全部为正例，则向假设中添加ai=T，否则，令ai=F，遍历样例集，如果样例全部为正例，则向假设中添加ai=F,否则，舍弃ai，不向假设中添加ai。时间最大复杂度：2*n*样例集大小3.2

Entropy(S)pilog2pi0.5log20.50.5log20.51

i1cGain(SA)Entropy(S)

|Sv|

Entropy(Sv)|s|vValues(A)14Entropy(ST)2Entropy(SF)

6614*12*10

663.4

由题意得知感知器A为：1+2*x1+1*x2>0，感知器B为：0+2*x1+1*x2>0，由数学知识可知A所表示的区域大于B，并且B所表示区域是A的一部分，所以显然A比B更一般。习题4.9

1、存在一定的隐藏单元权值，能够对八种输入产生如0.1，0.2，…，0.8的隐藏单元编码。5因为sigmoid函数是值域在(0,1)区间的递增函数，而输入样本为只有一位为1的八位二进制码，显然通过训练可以得到从第一个输入单元到第八个输入单元与隐藏单元的递增的连接权重，从而使隐藏单元对于10000000，01000000，…，00000001八种不同的输入产生递增的0.1，0.2，…，0.8的隐藏单元输出编码。2、不可能存在这样的输出单元权值，能够对以上八种不同的输入进行正确的解码。因为根据目标输出结果，首先考虑第一种输入：10000000，对应0.1的隐藏单元编码，隐藏单元与第一个输出单元的权值应为最大，而隐藏单元与其他输出单元的权值相对较小；再考虑第二种输入：01000000，它对应0.2的隐藏单元编码，隐藏单元与第二个输出单元的权值应最大，而隐藏单元与其他输出单元的权值相对较小；其他输入情况与此类似。而因为只有一个隐藏单元，它到每个输出单元的权值只有一个，所以这些权值的要求是相互冲突、无法实现的。3、由2可知，如果用梯度下降法寻找最优权值，对于不同的输入，权值将会被反复地向不同方向调整，而最终无法收敛，解不存在。习题6.1

解：使用误差准则为如下公式：621

E3(xq)（f(x)f(x)）K(d(xq,x))2xxq的k个近邻

i因为：E3i

所以：2E31

(（f(x)f(x)）K(d(xq,x)))ii2xxq的k个近邻



在整个表达式中i尽能通过f(x)来影响整个网络则上式可转化为



E3Ef(x)1f(x)

32（f(x)f(x)）K(d(xq,x))if(x)i2xxq的k个近邻i

f(x)

i除了实例x的第i个属性值有非零值外其他值都为０，则有：又因为对于f(x)

ai(x)i

E3E3f(x)

（f(x)f(x)）K(d(xq,x))ai(x)ifxxq的k个近邻i(x)代入(1)式有：E3

i(（f(x)f(x)）K(d(xq,x))ai(x))

ixxq的k个近邻



(1)习题8.3

决策树学习算法ID3的消极版本，我觉得可以借鉴k-近邻算法思想，先不构造决策树，当有一个新样例时，找到k个离新样例最近的样例，按照ID3算法，生成决策树，再由此树判别新样例是正例还是反例。优点：可以把决策树建立的过程放到需要预测时再进行，所以初始建立决策树的时间省略了，并且在需要预测时只是选取最近的k个建立决策树，所需时间较少。当需要预测样例远小于已有样例时效率比较高。缺点：加大了预测时的时间开销，积极版本只需初始时建立一颗决策树，后面预测只要验证一下即可，但消极版本每次均需重新建立决策树，当需要预测的样例太多时效率十分低下。9.1

(1)对PlayTennis问题描述：7属性集＝〈Outlook,Temperature,Humidity,Wind〉记为：〈a1,a2,a3,a4〉目标概念＝〈PlayTennis〉记为：〈c〉Outlook(a1)的值可取：Sunny,Overcast，RainTemperature(a2)的值可取：Hot,Mild,CoolHumidity(a3)的值可取：High,NormalWind(a4)的值可取：Weak,StrongPlayTennis(c)的可取值为：Yes,No根据该问题提供的训练样例，则选取其中任意的两个样例，则由两个样例组成的假设为：IFa1=Sunny∧a2=Hot∧a3=High∧a4=WeakTHENc=NoIFa1=Sunny∧a2=Hot∧a3=High∧a4=StrongTHENc=No用二进制位串来表示假设，则有a1a2a3a4ca1a2a3a4c1001001010010010010010其中，规则前件有a1取100时，表示Outlook取第一个约束即Outlook＝Sunnya2取100时，表示Temperatur取第一个约束即Temperature＝Hota3取10时，表示Humidity取第一个约束即Humidity＝Higha4取10时，表示Wind取第一个约束即Wind＝Weak规则后件c取0时表示目标值为No(2)遗传算子如果双亲串是a1a2a3a4ca1a2a3a4ch1:1001001010010010010010a1a2a3a4ca1a2a3a4ch2:0101001010100101010011假设为第一个双亲选取的交叉点位置是第2和16位，如下所示：a1a2a3a4ca1a2a3a4ch1:10[01001010010010]010010那么d1=2并且d2=5所以允许选取的第二个双亲交叉点的位置有〈2，5〉〈2，16〉〈13，16〉,如果选取的是〈2，16〉：a1a2a3a4ca1a2a3a4ch2:01[01001010100101]010011那么结果生成的两个后代是：a1a2a3a4ca1a2a3a4ch1:1001001010100101010010a1a2a3a4ca1a2a3a4ch2:01010010100100100100119.3

9.2.5节所描述的程序树如下：8EQDUMTMSDUNOTNOTCSCSNNNN交叉算子的操作过程示例如下图：EQEQDUMTNOTMSDUNOTMTDUNOTMSDUNOTCSCSNNNNCSCSNNNNEQEQDUMTNOTNOTMTDUNOTMSDUDUMSNOTNNCSCSCSCSNNNNNN9

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

机器学习 习题答案

机器学习习题答案