机器学习-习题答案

#2.5(题目略)(a).第一步：SO{v(QQQQ),(QQQQ)>}G0{<(????),(????)>}第二步：S1{<(malebrowntallUS),(femaleblackshortUS)>G1{<(????),(????)>}第三步：S2{<(malebrown??),(femaleblackshortUS)>G2{<(????),(????)>}第四步：S3{<(malebrown??),(femaleblackshortUS)>G3{<(male???),(????)>，<????>,<???US>}第五步：S4{<(malebrown??),(female?short?)>G4{<(male???),(????)>}(b).假设中的每个属性可以取两个值，所以与题目例题一致的假设数目为:(c).这个最短序列应该为8，28=2562*2*2*2)2*2*2*2)*(2*2*2*2)=256如果只有一个训练样例，则假设空间有28=256个假设，我们针对每一个属性来设置训练样例，使每次的假设空间减半。则经过8次训练后，可收敛到单个正确的假设。<female,blanck,short,Portuguese>,<female,blonde,tall,Indian><male,brown,short,Portuguese>,<female,blonde,tall,Indian><male,blanck,tall,Portuguese>,<female,blonde,tall,Indian><male,blanck,short,US>,<female,blonde,tall,Indian><male,blanck,short,Portuguese>,<male,blonde,tall,Indian><male,blanck,short,Portuguese>,<female,black,tall,Indian><male,blanck,short,Portuguese>,<female,blonde,short,Indian><male,blanck,short,Portuguese>,<female,blonde,tall,US>(d).若要表达该实例语言上的所有概念，那么我们需要扩大假设空间，使得每个可能的假设都包括在内，这样假设空间就远远大于256，而且这样没法得到最终的没法收敛，因为对每一个未见过的训练样例，投票没有任何效果，因此也就没有办法对未见样例分类。所以不存在一个最优的查询序列。2.6完成变型空间表示定理的证明(定理2.1)定理2.1：变型空间表示定理领X为一任意的实例集合，H为X上定义的布尔假设的集合。令c：X｛0,1｝为X上定义的任一目标概念，并令D为任一训练样例的集合｛vx,c(x)>｝。对所有的X，H，c，D以及良好定义的S和G：VS二｛hGH|(3sGS)(3gGG)(g>h>s｝HDgg证明：对VSH,D中任一h：当h^S时，取s=h,则有h三gs成立当h《S时，即(*1gH)[(h>gh1)AConsistent(h1,D)]若h1eS，显然h三gs成立；

否则有(3h2eH)[(hl>gh2)AConsistent(h2,D)]同样或者h2eS，贝9h>gh1三gs成立；或者(mh3wH)[(h2>gh3)AConsistent(h3,D)]如此下去，必存在一个序列h>gh1>gh2>g...>ghnwS故也有(3seS)h^gs同理，对VSH，D中任一h：当heG时，取g=h,则有g三gh成立当h《G时，即QhleH)[(h1>gh)AConsistent(h1,D)]若h1eG，显然g三gh成立；否则有(3h2eH)[(h2>gh1)AConsistent(h2,D)]同样或者h2eG，则g=h2>gh1三gh成立；或者(3h3eH)[(h3>gh2)AConsistent(h3,D)]如此下去，必存在一个序列g=hn>g...>gh2>gh1>gh,故也有(3geG)g^gh2.9(题目略)对每个属性进行如下操作：令ai=T，遍历样例集，如果样例全部为正例，贝9向假设中添加ai=T，否则，令ai=F，遍历样例集，如果样例全部为正例，则向假设中添加ai=F,否则，舍弃ai,不向假设中添加aio时间最大复杂度：2*n*样例集大小3.2Entropy(Entropy(S)=£一plogpi2ii=1=一0・5log0.5一0・5log0.5=122vEntropy(S)Gain(S<A)=Entropy(S)一工vEntropy(S)|s|vveValues(A)=1-46Entropy(S)-26Entropy(S)*1一*1=*1一*1=03.4假设u1：EnjoySport=Yes，u2：EnjoySport=NoH(U)=-P(u1)logP(u1)—P(u2)logP(u2)=-(3/4)log(3/4)-(1/4)log(1/4)对Sky假设v1：Sky=Sunnyv2：Sky=RainyH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-1*log(1)-(0)*log(0)=0H(U|v2)=-P(u1|v2)logP(u1|v2)-P(u2|v2)logP(u2|v2)=-(0)*log(0)-(1)*log(1)=0H(U|V)=P(v1)H(U|v1)+P(v2)H(U|v2)=(3/4)*0+(1/4)*0=0所以I(U,V)=H(U)-H(UIV)=H(U)此时显然信息增益最大，所以Sky作为决策树根节点,又由于对Sky取两个值对应的EnjoySport值都是确定的，因此可画出决策树为：使用变型空间算法得到的变型空间为vsunny,warm,?,srtong,?,?>,决策树对应变型空间为vsunny,?,?,?,?,?>,显然，决策树得到的变型空间更一般。树等价于变型空间中的一个或多个成员。假设u1：EnjoySport=Yes,u2：EnjoySport=NoH(U)=-P(ul)logP(ul)壬(u2)logP(u2)=-(3/5)log(3/5)-(2/5)log(2/5)=0.971①对Sky假设v1：Sky=Sunnyv2：Sky=RainyH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-(3/4)*log(3/4)-(1/4)*log(1/4)=0.811H(U|v2)=-P(u1|v2)logP(u1|v2)-P(u2|v2)logP(u2|v2)=-(0)*log(0)-(1)*log(1)=0H(U|V)=P(v1)H(U|v1)+P(v2)H(U|v2)=(4/5)*0.811+(1/5)*0=0.6488I(U,V)=H(U)-H(U|V)=0.971-0.6488=0.3222对AirTemp假设v1：AirTemp=Warmv2：AirTemp=ColdH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-(3/4)*log(3/4)-(1/4)*log(1/4)=0.811H(U|v2)=-P(u1|v2)logP(u1|v2)-P(u2|v2)logP(u2|v2)=-(0)*log(0)-(1)*log(1)=0H(U|V)=P(v1)H(U|v1)+P(v2)H(U|v2)=(4/5)*0.811+(1/5)*0=0.6488I(U,V)=H(U)-H(U|V)=0.971-0.6488=0.3222对Humidity假设v1：Humidity=Normalv2：Humidity=HighH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-(1/2)*log(1/2)-(1/2)*log(1/2)=1H(U|v2)=-P(u1|v2)logP(u1|v2)-P(u2|v2)logP(u2|v2)=-(2/3)*log(2/3)-(1/3)*log(1/3)=0.918H(U|V)=P(v1)H(U|v1)+P(v2)H(U|v2)=(2/5)*1+(3/5)*0.918=0.9508I(U,V)=H(U)-H(U|V)=0.971-0.9508=0.0202对Wind假设v1：Wind=Strongv2：Wind=WeakH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-(3/4)*log(3/4)-(1/4)*log(1/4)=0.811H(U|v2)=-P(u1|v2)logP(u1|v2)-P(u2|v2)logP(u2|v2)=-(0)*log(0)-(1)*log(1)=0H(U|V)=P(v1)H(U|v1)+P(v2)H(U|v2)=(4/5)*0.811+(1/5)*0=0.6488I(U,V)=H(U)-H(U|V)=0.971-0.6488=0.3222对Water假设v1：Water=Warmv2：Water=CoolH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-(1/2)*log(1/2)-(1/2)*log(1/2)=1H(U|v2)=-P(u1|v2)logP(u1|v2)-P(u2|v2)logP(u2|v2)=-(1)*log(1)-(0)*log(0)=0H(U|V)=P(v1)H(U|v1)+P(v2)H(U|v2)=(4/5)*1+(1/5)*0=0.8I(U,V)=H(U)-H(U|V)=0.971-0.8=0.171对Forecast假设v1：Forecast=Samev2：Forecast=ChangeH(U|v1)=-P(u1|v1)logP(u1|v1)-P(u2|v1)logP(u2|v1)=-(2/3)*log(2/3)-(1/3)*log(1/3)=0.918H(U|v2)=-P(u1|v2)logP(u1|v2)-P(u2|v2)logP(u2|v2)=-(1/2)*log(1/2)-(1/2)*log(1/2)=1H(U|V)=P(v1)H(U|v1)+P(v2)H(U|v2)=(3/5)*0.918+(2/5)*1=0.9580I(U,V)=H(U)-H(U|V)=0.971-0.9580=0.013从而可画出决策树第一步为：对于Sky=Sunny选定后H(U)=-P(ul)logP(ul)-P(u2)logP(u2)=-(3/4)log(3/4)-(l/4)log(l/4)=0.811对AirTemp假设v1：AirTemp=Warmv2：AirTemp=ColdH(U|vl)=-P(ul|vl)logP(ul|vl)-P(u2|vl)logP(u2|vl)=-(3/4)*log(3/4)-(l/4)*log(l/4)=0.8llH(U|v2)=-P(ul|v2)logP(ul|v2)-P(u2|v2)logP(u2|v2)=-(0)*log(0)-(0)*log(0)=0H(U|V)=P(vl)H(U|vl)+P(v2)H(U|v2)=(4/4)*0.8ll+(0/4)*0=0.8llI(U,V)=H(U)-H(U|V)=0.8ll-0.8ll=0对Humidity假设vl：Humidity=Normalv2：Humidity=HighH(U|vl)=-P(ul|vl)logP(ul|vl)-P(u2|vl)logP(u2|vl)=-(l/2)*log(l/2)-(l/2)*log(l/2)=lH(U|v2)=-P(ul|v2)logP(ul|v2)-P(u2|v2)logP(u2|v2)=-(l)*log(l)-(0)*log(0)=0H(U|V)=P(vl)H(U|vl)+P(v2)H(U|v2)=(l/2)*l+(l/2)*0=0.5I(U,V)=H(U)-H(U|V)=0.8ll-0.5=0.3ll对Wind假设vl：Wind=Strongv2：Wind=WeakH(U|vl)=-P(ul|vl)logP(ul|vl)-P(u2|vl)logP(u2|vl)=-(l)*log(l)-(0)*log(0)=0H(U|v2)=-P(ul|v2)logP(ul|v2)-P(u2|v2)logP(u2|v2)=-(0)*log(0)-(l)*log(l)=0H(U|V)=P(vl)H(U|vl)+P(v2)H(U|v2)=(3/4)*0+(l/4)*0=0I(U,V)=H(U)-H(U|V)=0.8ll-0=0.8ll对Water假设vl：Water=Warmv2：Water=CoolH(U|vl)=-P(ul|vl)logP(ul|vl)-P(u2|vl)logP(u2|vl)=-(2/3)*log(2/3)-(l/3)*log(l/3)=0.9l8H(U|v2)=-P(ul|v2)logP(ul|v2)-P(u2|v2)logP(u2|v2)=-(l)*log(l)-(0)*log(0)=0H(U|V)=P(vl)H(U|vl)+P(v2)H(U|v2)=(3/4)*0.9l8+(l/4)*0=0.6885I(U,V)=H(U)-H(U|V)=0.8ll-0.6885=0.l225对Forecast假设vl：Forecast=Samev2：Forecast=ChangeH(U|vl)=-P(ul|vl)logP(ul|vl)-P(u2|vl)logP(u2|vl)=-(2/3)*log(2/3)-(l/3)*log(l/3)=0.9l8H(U|v2)=-P(ul|v2)logP(ul|v2)-P(u2|v2)logP(u2|v2)=-(l)*log(l)-(0)*log(0)=0H(U|V)=P(vl)H(U|vl)+P(v2)H(U|v2)=(3/4)*0.9l8+(l/4)*l=0.6885I(U,V)=H(U)-H(U|V)=0.8ll-0.6885=0.l225从而可画出决策树第二步：

该决策树已全部画出。第一个训练样例后的S和G集合S：当遇到第二个训练样例时，需要根据前两个样例一般化第一步中决策树作为S；同样需要根据前两个样例画出最一般的决策树作为G。困难：注意到由于决策树的假设空间是无偏的，所以如果用候选消除算法来搜索，S边界中的决策树是将所有正例所在分枝的叶节点判为正例其他均为反例（且将各属性的先后次序改变会得到大量语法不同概念相同的树）。而G边界中的决策树则是将反例所在分枝的叶节点判为反例其他均为正例的树。这样，对新的实例将不可能有确定的结论。习题4.3由题意得知感知器A为：l+2*xl+l*x2>0，感知器B为：0+2*xl+l*x2>0,由数学知识可知A所表示的区域大于B,并且B所表示区域是A的一部分，所以显然A比B更一般。习题4.9

1、存在一定的隐藏单元权值，能够对八种输入产生如0.1,0.2,…，0.8的隐藏单元编码。因为sigmoid函数是值域在(0,1)区间的递增函数，而输入样本为只有一位为1的八位二进制码，显然通过训练可以得到从第一个输入单元到第八个输入单元与隐藏单元的递增的连接权重，从而使隐藏单元对于10000000，01000000，…，00000001八种不同的输入产生递增的0.1，0.2，…，0.8的隐藏单元输出编码。2、不可能存在这样的输出单元权值，能够对以上八种不同的输入进行正确的解码。因为根据目标输出结果，首先考虑第一种输入：10000000，对应0.1的隐藏单元编码，隐藏单元与第一个输出单元的权值应为最大，而隐藏单元与其他输出单元的权值相对较小；再考虑第二种输入：01000000，它对应0.2的隐藏单元编码，隐藏单元与第二个输出单元的权值应最大，而隐藏单元与其他输出单元的权值相对较小；其他输入情况与此类似。而因为只有一个隐藏单元，它到每个输出单元的权值只有一个，所以这些权值的要求是相互冲突、无法实现的。3、由2可知，如果用梯度下降法寻找最优权值，对于不同的输入，权值将会被反复地向不同方向调整，而最终无法收敛，解不存在。习题6.1解：根据题意有：P(cancer)=0.008,P(P(cancer)=0.008,P(㊉lcancer)=0.98,P(㊉l―>cancer)=0.03,P(―>cancer)=0.992P(—lcancer)=0.02P(—l―>cancer)=0.97第一次化验有其极大后验假设为：P(㊉Icancer)P(cancer)=0.98X0.008=0.0078P(㊉|「cancer)P(「cancer)=0.03X0.992=0.0298则第一次化验后确切的后验概率是：P(A)=P(cancerI㊉)=0.0078/(0.0078+0.0298)=0.21P(B)=P(-cancerl+)=0.0298/(0.0078+0.0298)=0.79因为两次的化验是相互独立的，根据乘法原理有：P(cancer1+)=P(A)XP(A)=0.21X0.21=0.0441P(-cancerl+)=P(B)XP(B)=0.79X0.79=0.6241习题6.3hMAP=argmaxh^HP(hlD)=argmaxh^HP(Dlh)P(h)/P(D)=argmaxhWHP(Dlh)P(h)hML=argmaxh^HP(Dlh)为了使FindG保证输出MAP假设，则应该使P(h)=1/lHl，即无先验知识。为了使FindG不保证输出MAP假设，则应该使假设P(h)不全相等，即存在先验知识，使得P(h)不全等于1/|Hl。为了使FindG输出的是ML假设而不是MAP假设，则应该使得每个假设的概率P(h)不全相等，但对任意一个假设成立的条件下所得到的结果是正类的概率相等，即P(Dlh)相等(对所有的假设，样例为正类和负类的概率均一样)。8.1给出公式8.7的推导过程解：使用误差准则为如下公式：3q2(f(x)-f(x))K(d(x,x))q因为：SE△①二一q3iS®i务=S®(2(f(X)-f(X))K(d(Xq，X)))所以：iix^x的个近邻在整个表达式中®i尽能通过f(x)来影响整个网络则上式可转化为気ff=-2X21(f(x)-5叫，x))警(1)Sf(x)又因为对于i除了实例x的第i个属性值有非零值外其他值都为0,则有:Sf(x)S①i代入(1)式有：SE__SESf(x)武f)兀_-工(f(x)一f(x))K(d(x,x))a(x)qiSEA®_-qi_-q(-工(f(x)-f(x))K(d(x,x))a(x))S®qiix^x的k个近邻习题8.3决策树学习算法ID3的消极版本，我觉得可以借鉴k-近邻算法思想，先不构造决策树，当有一个新样例时，找到k个离新样例最近的样例，按照ID3算法，生成决策树，再由此树判别新样例是正例还是反例。优点：可以把决策树建立的过程放到需要预测时再进行，所以初始建立决策树的时间省略了，并且在需要预测时只是选取最近的k个建立决策树，所需时间较少。当需要预测样例远小于已有样例时效率比较高。缺点：加大了预测时的时间开销，积极版本只需初始时建立一颗决策树，后面预测只要验证一下即可，但消极版本每次均需重新建立决策树，当需要预测的样例太多时效率十分低下。9.1(1)对PlayTennis问题描述：属性集=〈Outlook,Temperature,Humidity,Wind记为：〈al,a2,a3,a4〉目标概念=〈PlayTennis〉记为