机器学习习题答案.pdf

1 2.5 （题目略）（题目略） (a). 第一步：S0 G0 第二步：S1 G1 第三步：S2 G2 第四步：S3 G3 ，, 第五步：S4 G4 (b).假设中的每个属性可以取两个值，所以与题目例题一致的假设数目为： （2*2*2*2）*（2*2*2*2） = 256 (c). 这个最短序列应该为 8， 25628 如果只有一个训练样例，则假设空间有 25628 个假设，我们针对每一个属性来设置训练 样例，使每次的假设空间减半。则经过 8 次训练后，可收敛到单个正确的假设。 , , , , , , , , (d). 若要表达该实例语言上的所有概念，那么我们需要扩大假设空间，使得每个可能的假设 都包括在内，这样假设空间就远远大于 256，而且这样没法得到最终的没法收敛，因为对每 一个未见过的训练样例，投票没有任何效果，因此也就没有办法对未见样例分类。所以不存 在一个最优的查询序列。 2.6 完成变型空间表示定理的证明（定理完成变型空间表示定理的证明（定理 2.1） 定理 2.1：变型空间表示定理 领 X 为一任意的实例集合，H 为 X 上定义的布尔假设的集合。 令 c：X0,1为 X 上定义的任一目标概念，并令 D 为任一训练样例的集合。对 所有的 X，H，c，D 以及良好定义的 S 和 G： )()( |shgGgSsHhVS ggHD 证明：对 VSH，D 中任一 h： 当 hS 时，取 sh，则有 hgs 成立 当 hS 时，即(h1H）(hgh1)Consistent(h1,D) 若 h1S，显然 hgs 成立； 2 否则有(h2H）(h1gh2)Consistent(h2,D) 同样或者 h2S，则 hgh1gs 成立；或者(h3H）(h2gh3)Consistent(h3,D) 如此下去，必存在一个序列 hgh1gh2gghnS 故也有(sS)hgs 同理，对 VSH，D 中任一 h： 当 hG 时，取 gh，则有 ggh 成立 当 hG 时，即(h1H）(h1gh)Consistent(h1,D) 若 h1G，显然 ggh 成立； 否则有(h2H）(h2gh1)Consistent(h2,D) 同样或者 h2G，则 g=h2gh1gh 成立；或者(h3H）(h3gh2)Consistent(h3,D) 如此下去，必存在一个序列 g=hng gh2gh1gh，故也有(gG)ggh 2.9 （题目略）（题目略） 对每个属性进行如下操作： 令 ai=T，遍历样例集，如果样例全部为正例，则向假设中添加 ai=T， 否则，令 ai=F，遍历样例集，如果样例全部为正例，则向假设中添加 ai=F, 否则，舍弃 ai，不向假设中添加 ai。 时间最大复杂度：2*n*样例集大小 3.2 15 . 0log5 . 05 . 0log5 . 0log)( 22 1 2 c i ii ppSEntropy 01* 6 2 1* 6 4 1 )( 6 2 )( 6 4 1 )( | | )()( )( FT v AValuesv v SEntropySEntropy SEntropy s S SEntropyASGain 3.4 假设 u1：EnjoySport=Yes ，u2：EnjoySport=No H(U)=-P(u1) log P(u1) P(u2) log P(u2)= -(3/4)log(3/4)-(1/4)log(1/4) 对 Sky 假设 v1：Sky=Sunny v2：Sky=Rainy H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) = -1*log(1)-(0)*log(0)=0 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) = -(0)*log(0)-(1)*log(1)=0 H(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(U|V)=H(U) 此时显然信息增益最大，所以 Sky 作为决策树根节点， 又由于对 Sky 取两个值对应的 EnjoySport 值都是确定的，因此可画出决策树为： 3 Sky YesNo SunnyRainy 使用变型空间算法得到的变型空间为，决策树对应变型空间为 ，显然，决策树得到的变型空间更一般。树等价于变型空间中的一个或多个 成员。 假设 u1：EnjoySport=Yes ，u2：EnjoySport=No H(U)=-P(u1) log P(u1) P(u2) log P(u2)= -(3/5)log(3/5)-(2/5)log(2/5)=0.971 对 Sky 假设 v1：Sky=Sunnyv2：Sky=Rainy H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(3/4)*log(3/4)-(1/4)*log(1/4)=0.811 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) = -(0)*log(0)-(1)*log(1)=0 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(4/5)* 0.811+(1/5)*0=0.6488 I(U, V)=H(U)-H(U|V)=0.971-0.6488=0.3222 对 AirTemp 假设 v1：AirTemp=Warmv2：AirTemp=Cold H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(3/4)*log(3/4)-(1/4)*log(1/4)=0.811 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) = -(0)*log(0)-(1)*log(1)=0 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(4/5)*0.811+(1/5)*0=0.6488 I(U, V)=H(U)-H(U|V)=0.971-0.6488=0.3222 对 Humidity 假设 v1：Humidity=Normalv2：Humidity =High H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(1/2)*log(1/2)-(1/2)*log(1/2)=1 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) =-(2/3)*log(2/3)-(1/3)*log(1/3)=0.918 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(2/5)*1+(3/5)*0.918=0.9508 I(U, V)=H(U)-H(U|V)=0.971-0.9508=0.0202 对 Wind 假设 v1：Wind=Strongv2：Wind =Weak H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(3/4)*log(3/4)-(1/4)*log(1/4)=0.811 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) =-(0)*log(0)-(1)*log(1)=0 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(4/5)*0.811+(1/5)*0=0.6488 I(U, V)=H(U)-H(U|V)=0.971-0.6488=0.3222 对 Water 假设 v1：Water=Warmv2：Water =Cool H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(1/2)*log(1/2)-(1/2)*log(1/2)=1 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) =-(1)*log(1)-(0)*log(0)=0 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(4/5)*1+(1/5)*0=0.8 I(U, V)=H(U)-H(U|V)=0.971-0.8=0.171 对 Forecast 假设 v1：Forecast=Samev2：Forecast=Change H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(2/3)*log(2/3)-(1/3)*log(1/3)=0.918 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) =-(1/2)*log(1/2)-(1/2)*log(1/2)=1 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(3/5)*0.918+(2/5)*1=0.9580 I(U, V)=H(U)-H(U|V)=0.971-0.9580=0.013 从而可画出决策树第一步为： 4 Sky SunnyRainy No 对于 Sky=Sunny 选定后 H(U)=-P(u1) log P(u1) P(u2) log P(u2)= -(3/4)log(3/4)-(1/4)log(1/4)=0.811 对 AirTemp 假设 v1：AirTemp=Warmv2：AirTemp=Cold H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(3/4)*log(3/4)-(1/4)*log(1/4)=0.811 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) = -(0)*log(0)-(0)*log(0)=0 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(4/4)*0.811+(0/4)*0=0.811 I(U, V)=H(U)-H(U|V)=0.811-0.811=0 对 Humidity 假设 v1：Humidity=Normalv2：Humidity =High H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(1/2)*log(1/2)-(1/2)*log(1/2)=1 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) =-(1)*log(1)-(0)*log(0)=0 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(1/2)*1+(1/2)*0 =0.5 I(U, V)=H(U)-H(U|V)=0.811-0.5=0.311 对 Wind 假设 v1：Wind=Strongv2：Wind =Weak H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(1)*log(1)-(0)*log(0)=0 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) =-(0)*log(0)-(1)*log(1)=0 H(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(U|V)=0.811-0=0.811 对 Water 假设 v1：Water=Warmv2：Water =Cool H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(2/3)*log(2/3)-(1/3)*log(1/3)=0.918 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) =-(1)*log(1)-(0)*log(0)=0 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(3/4)*0.918+(1/4)*0=0.6885 I(U, V)=H(U)-H(U|V)=0.811-0.6885=0.1225 对 Forecast 假设 v1：Forecast=Samev2：Forecast=Change H(U|v1)=-P(u1|v1) log P(u1|v1)-P(u2|v1) log P(u2|v1) =-(2/3)*log(2/3)-(1/3)*log(1/3)=0.918 H(U|v2)=-P(u1|v2) log P(u1|v2)-P(u2|v2) log P(u2|v2) =-(1)*log(1)-(0)*log(0)=0 H(U|V)=P(v1) H(U|v1)+P(v2) H(U|v2)=(3/4)*0.918+(1/4)*1=0.6885 I(U, V)=H(U)-H(U|V)=0.811-0.6885=0.1225 从而可画出决策树第二步： Sky SunnyRainy NoWind WeakStrong YesNo 该决策树已全部画出。 5 第一个训练样例后的 S 和 G 集合： S： G： 当遇到第二个训练样例时，需要根据前两个样例一般化第一步中决策树作为 S；同样需要根 据前两个样例画出最一般的决策树作为 G。 困难：注意到由于决策树的假设空间是无偏的，所以如果用候选消除算法来搜索，S 边界中 的决策树是将所有正例所在分枝的叶节点判为正例其他均为反例 （且将各属性的先后次序改 变会得到大量语法不同概念相同的树） 。而 G 边界中的决策树则是将反例所在分枝的叶节点 判为反例其他均为正例的树。这样，对新的实例将不可能有确定的结论。 习题习题 4.3 由题意得知感知器 A 为：1+2*x1+1*x20，感知器 B 为：0+2*x1+1*x20，由数学知识可知 A 所表示的区域大于 B，并且 B 所表示区域是 A 的一部分，所以显然 A 比 B 更一般。 习题习题 4.9 1、存在一定的隐藏单元权值，能够对八种输入产生如 0.1，0.2，0.8 的隐藏单元编码。 6 因为 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(cancer)=0.992 P(|cancer)=0.98，P(|cancer)=0.02 P(|cancer)=0.03，P(|cancer)=0.97 第一次化验有其极大后验假设为： P(|cancer) P(cancer)0.980.0080.0078 P(|cancer)P(cancer)0.030.9920.0298 则第一次化验后确切的后验概率是： P(A)=P(cancer |)0.0078/（0.00780.0298）0.21 P(B)=P(cancer |)0.0298/（0.00780.0298）0.79 因为两次的化验是相互独立的，根据乘法原理有： P(cancer |)P(A)P(A)0.210.210.0441 P(cancer |)P(B)P(B)0.790.790.6241 习题习题 6.3 hMAP=argmaxhH P(h|D)=argmaxhH P(D|h)P(h)/P(D)=argmaxhH P(D|h)P(h) hML=argmaxhH P(D|h) 为了使 FindG 保证输出 MAP 假设，则应该使 P(h)=1/|H|，即无先验知识。 为了使 FindG 不保证输出 MAP 假设，则应该使假设 P(h)不全相等，即存在先验知识，使得 P(h)不全等于 1/|H|。 为了使 FindG 输出的是 ML 假设而不是 MAP 假设，则应该使得每个假设的概率 P(h)不全相 等，但对任意一个假设成立的条件下所得到的结果是正类的概率相等，即 P(D|h)相等（对所 有的假设，样例为正类和负类的概率均一样） 。 8.1 给出公式给出公式 8.7 的推导过程的推导过程 解：使用误差准则为如下公式： 7 2 3 1 ()f(x)f(x)( (, ) 2 q qq x xk E xK d xx 的 个近邻 （） 因为： 3 i i E 所以： 2 3 1 (f(x)f(x)( (, ) 2 q q x xk ii E K d xx 的 个近邻 （） 在整个表达式中 i 尽能通过f(x) 来影响整个网络则上式可转化为 33 f(x)1f(x) 2f(x)f(x)( (, ) 2 f(x) q q x xk iii EE K d xx 的 个近邻 （） (1) 又因为对于 f(x) i 除了实例 x 的第 i 个属性值有非零值外其他值都为，则有： f(x) ( ) i i a x 代入(1)式有： 33 f(x) f(x)f(x)( (, ) ( ) f(x) q qi x xk ii EE K d xx a x 的 个近邻 （） 3 (f(x)f(x)( (, ) ( ) q iqi x xk i E K d xx a x 的 个近邻 （） 习题习题 8.3 决策树学习算法 ID3 的消极版本，我觉得可以借鉴 k-近邻算法思想，先不构造决策树，当 有一个新样例时，找到 k 个离新样例最近的样例，按照 ID3 算法，生成决策树，再由此树 判别新样例是正例还是反例。 优点： 可以把决策树建立的过程放到需要预测时再进行， 所以初始建立决策树的时间省略了， 并且在需要预测时只是选取最近的 k 个建立决策树， 所需时间较少。 当需要预测样例远小于 已有样例时效率比较高。 缺点：加大了预测时的时间开销，积极版本只需初始时建立一颗决策树，后面预测只要验证 一下即可，但消极版本每次均需重新建立决策树，当需要预测的样例太多时效率十分低下。 9.1 (1) 对 PlayTennis 问题描述： 8 属性集Outlook, Temperature, Humidity, Wind记为： a1,a2,a3,a4 目标概念PlayTennis记为： c Outlook(a1)的值可取：Sunny, Overcast，Rain Temperature(a2)的值可取：Hot, Mild , Cool Humidity(a3)的值可取：High, Normal Wind(a4)的值可取：Weak, Strong PlayTennis(c)的可取值为：Yes,No 根据该问题提供的训练样例，则选取其中任意的两个样例，则由两个样例组成的假设为： IF a1= Sunnya2=Hota