机器学习-习题答案.doc_文客久久网wenke99.com

资源描述

1、12.5 （题目略）(a). 第一步：S0 G0 第二步：S1 G1 第三步：S2 G2 第四步：S3 G3 ，,第五步：S4 G4 (b).假设中的每个属性可以取两个值，所以与题目例题一致的假设数目为：（2*2*2*2）*（2*2*2*2） = 256(c). 这个最短序列应该为 8， 256如果只有一个训练样例，则假设空间有 8个假设，我们针对每一个属性来设置训练样例，使每次的假设空间减半。则经过 8 次训练后，可收敛到单个正确的假设。,(d). 若要表达该实例语言上的所有概念，那么我们需要扩大假设空间，使得每个可能的假设都包括在内，这样假设空间就远远大于 256，而且这样没法得到最终的没

2、法收敛，因为对每一个未见过的训练样例，投票没有任何效果，因此也就没有办法对未见样例分类。所以不存在一个最优的查询序列。2.6 完成变型空间表示定理的证明（定理 2.1）定理 2.1：变型空间表示定理领 X 为一任意的实例集合，H 为 X 上定义的布尔假设的集合。令 c：X0,1为 X 上定义的任一目标概念，并令 D 为任一训练样例的集合。对所有的 X，H，c ，D 以及良好定义的 S 和 G： )(|shgSshVS gD 证明：对 VSH，D 中任一 h：当 hS 时，取 sh，则有 hgs 成立当 hS 时，即 (h1H）(hgh1)Consistent(h1,D)若 h1S，显然 hg

3、s 成立；2否则有 (h2H）(h1gh2)Consistent(h2,D)同样或者 h2S，则 hgh1 gs 成立；或者 (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) Consisten

4、t(h3,D)如此下去，必存在一个序列 g=hng gh2gh1gh，故也有 (gG)ggh2.9 （题目略）对每个属性进行如下操作：令 ai=T，遍历样例集，如果样例全部为正例，则向假设中添加 ai=T，否则，令 ai=F，遍历样例集，如果样例全部为正例，则向假设中添加 ai=F,否则，舍弃 ai，不向假设中添加 ai。时间最大复杂度：2*n*样例集大小3.2 15.0log.50log.log)( 2212 ci iipSEntropy01*6241)()( )(|(FT vAValuesvvSEntropySntropySntrpyAGai3.4假设 u1：EnjoySport=Yes

6、) H(U|v2)=(3/4)*0+(1/4)*0=0所以 I(U, V)=H(U)-H(U|V)=H(U) 此时显然信息增益最大，所以 Sky 作为决策树根节点，3又由于对 Sky 取两个值对应的 EnjoySport 值都是确定的，因此可画出决策树为：SkyYes NoSunny Rainy使用变型空间算法得到的变型空间为，决策树对应变型空间为，显然，决策树得到的变型空间更一般。树等价于变型空间中的一个或多个成员。假设 u1：EnjoySport=Yes ， u2：EnjoySport=NoH(U)=-P(u1) log P(u1) P(u2) log P(u2)= -(3/5)log(3

12、) 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=Same v2：Forecast=ChangeH(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.918H(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)=1H(U|V)=P(v1

19、S k yW i n dH u m i d i t yA i r t e m pF o r e c a s tW a t e rs u n n yw a r mn o r m a ls t r o n gW a r mY E SG：Y E S当遇到第二个训练样例时，需要根据前两个样例一般化第一步中决策树作为 S；同样需要根据前两个样例画出最一般的决策树作为 G。困难：注意到由于决策树的假设空间是无偏的，所以如果用候选消除算法来搜索，S 边界中的决策树是将所有正例所在分枝的叶节点判为正例其他均为反例（且将各属性的先后次序改变会得到大量语法不同概念相同的树）。而 G 边界中的决策树则是将反例所在

20、分枝的叶节点判为反例其他均为正例的树。这样，对新的实例将不可能有确定的结论。习题 4.3由题意得知感知器 A 为：1+2*x1+1*x20 ，感知器 B 为：0+2*x1+1*x20 ，由数学知识可知 A 所表示的区域大于 B，并且 B 所表示区域是 A 的一部分，所以显然 A 比 B 更一般。习题 4.961、存在一定的隐藏单元权值，能够对八种输入产生如 0.1，0.2，0.8 的隐藏单元编码。因为 sigmoid 函数是值域在(0,1)区间的递增函数，而输入样本为只有一位为 1 的八位二进制码，显然通过训练可以得到从第一个输入单元到第八个输入单元与隐藏单元的递增的连接权重，从而使隐藏单元对

21、于 10000000，01000000，00000001 八种不同的输入产生递增的 0.1，0.2，0.8 的隐藏单元输出编码。2、不可能存在这样的输出单元权值，能够对以上八种不同的输入进行正确的解码。因为根据目标输出结果，首先考虑第一种输入：10000000，对应 0.1 的隐藏单元编码，隐藏单元与第一个输出单元的权值应为最大，而隐藏单元与其他输出单元的权值相对较小；再考虑第二种输入：01000000，它对应 0.2 的隐藏单元编码，隐藏单元与第二个输出单元的权值应最大，而隐藏单元与其他输出单元的权值相对较小；其他输入情况与此类似。而因为只有一个隐藏单元，它到每个输出单元的权值只有一个，所以

22、这些权值的要求是相互冲突、无法实现的。3、由 2 可知，如果用梯度下降法寻找最优权值，对于不同的输入，权值将会被反复地向不同方向调整，而最终无法收敛，解不存在。习题 6.1解：根据题意有：P(cancer)=0.008, P(cancer)=0.992P( |cancer)=0.98， P( |cancer)=0.02 P( |cancer)=0.03， P( |cancer)=0.97 第一次化验有其极大后验假设为：P( |cancer) P(cancer)0.980.0080.0078P( |cancer)P(cancer)0.030.9920.0298 则第一次化验后确切的后验概率是：P

24、H|，即无先验知识。为了使 FindG 不保证输出 MAP 假设，则应该使假设 P(h)不全相等，即存在先验知识，使得 P(h)不全等于 1/|H|。为了使 FindG 输出的是 ML 假设而不是 MAP 假设，则应该使得每个假设的概率 P(h)不全相等，但对任意一个假设成立的条件下所得到的结果是正类的概率相等，即 P(D|h)相等（对所有的假设，样例为正类和负类的概率均一样）。8.1 给出公式 8.7 的推导过程7解：使用误差准则为如下公式： 231()f(x)(,)2qq qxkEKdx的个近邻（）因为： 3iiEA所以：231(f(x)(,)2q qxkiiEKdx的个近

25、邻（）在整个表达式中 i尽能通过 f()来影响整个网络则上式可转化为3f(x)1f(x)2f(x)(,q qxki i iEKd 的个近邻（）(1)又因为对于f()i除了实例 x 的第 i 个属性值有非零值外其他值都为，则有：f(x)iia代入(1)式有：3f(x)f(x)(,)(q qixki iEKdxa的个近邻（）3(f()(,)(qi qixki daA的个近邻（）习题 8.3决策树学习算法 ID3 的消极版本，我觉得可以借鉴 k-近邻算法思想，先不构造决策树，当有一个新样例时，找到 k 个离新样例最近的样例，按照 ID3 算法，生成决策树，再由此树

26、判别新样例是正例还是反例。优点：可以把决策树建立的过程放到需要预测时再进行，所以初始建立决策树的时间省略了，并且在需要预测时只是选取最近的 k 个建立决策树，所需时间较少。当需要预测样例远小于已有样例时效率比较高。缺点：加大了预测时的时间开销，积极版本只需初始时建立一颗决策树，后面预测只要验证一下即可，但消极版本每次均需重新建立决策树，当需要预测的样例太多时效率十分低下。9.1 8(1) 对 PlayTennis 问题描述：属性集Outlook, Temperature, Humidity, Wind记为：a1,a2,a3,a4目标概念PlayTennis 记为：cOutlook(a1)的值可

27、取：Sunny, Overcast ，Rain Temperature(a2)的值可取：Hot, Mild , CoolHumidity(a3)的值可取：High, NormalWind(a4)的值可取：Weak, Strong PlayTennis(c)的可取值为： Yes,No根据该问题提供的训练样例，则选取其中任意的两个样例，则由两个样例组成的假设为：IF a1= Sunny a2=Hota3=Higha4=Weak THEN c= NoIF a1= Sunny a2=Hota3=Higha4= Strong THEN c= No用二进制位串来表示假设，则有a1 a2 a3 a4 c a

28、1 a2 a3 a4 c100 100 10 10 0 100 100 10 01 0 其中，规则前件有a1 取 100 时，表示 Outlook 取第一个约束即 OutlookSunnya2 取 100 时，表示 Temperatur 取第一个约束即 TemperatureHota3 取 10 时，表示 Humidity 取第一个约束即 HumidityHigha4 取 10 时，表示 Wind 取第一个约束即 WindWeak规则后件 c 取 0 时表示目标值为 No(2)遗传算子如果双亲串是a1 a2 a3 a4 c a1 a2 a3 a4 ch1: 100 100 10 10 0 10

29、0 100 10 01 0a1 a2 a3 a4 c a1 a2 a3 a4 ch2: 010 100 10 10 1 001 010 10 01 1假设为第一个双亲选取的交叉点位置是第 2 和 16 位，如下所示：a1 a2 a3 a4 c a1 a2 a3 a4 ch1: 100 100 10 10 0 100 100 10 01 0那么 d1=2 并且 d2=5 所以允许选取的第二个双亲交叉点的位置有2，5 2，16 13，16,如果选取的是2，16：a1 a2 a3 a4 c a1 a2 a3 a4 ch2: 010 100 10 10 1 001 010 10 01 1那么结果生成的

30、两个后代是：a1 a2 a3 a4 c a1 a2 a3 a4 ch1: 100 100 10 10 1 001 010 10 01 0a1 a2 a3 a4 c a1 a2 a3 a4 ch2: 010 100 10 10 0 100 100 10 01 19.3 9.2.5 节所描述的程序树如下：9EQDUMT NOTCS CSDUMS NOTNN NN交叉算子的操作过程示例如下图：EQDUMT NOTCS CSDUMS NOTNN NNEQDUMT NOTCS CSDUMS NOTNN NNEQDUMT NOTCS CSNOTNNEQDUMT NOTCS CSDUMSNNDUMS NOTNN NN

展开阅读全文