机器学习课后作业

1、精品文档机器学习课后作业学 院：电子工程学院专 业：电子与通信工程姓 名：叶旭庆学 号3继续考虑EnjoySport学习任务和2.2节中描述的假设空间H。如果定义一个新 的假设空间H',它包含H中所有假设的成对析取。如H'中一假设为：<?,Cold, High, ?, ?, ?>V<Sunny, ?, High, ?, ?, Sam>试跟踪运行使用该假设空间 H'的候选消除算法，给定的训练样例如表2-1所示（需要分步列出S和G集合）。S0= (K K K (|),(|),(|) v ( K K K K K (|)G0 =

2、 (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 1: <Sunny, Warm, Normal, Strong, Warm, Same, Yes>S1=(Sunny, Warm, Normal, Strong, Warm, Same) v ( 八八九九八小)G1 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 2: <Sunny, Warm, High, Strong, Warm, Same, Yes>S2= (Sunny, Warm, Normal, Strong, Wa

3、rm, Same) v (Sunny, Warm, High, Strong, Warm, Same) ，(Sunny, Warm, ? , Strong, Warm, Same) v (|),(|),(|),(|),(|),(|)G2 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 3: <Rainy, Cold, High, Strong, Warm, Change, No>S3=(Sunny, Warm,Normal, Strong, Warm,Same)v (Sunny, Warm,High, Strong, Warm, S

4、ame)，(Sunny, Warm, ? , Strong, Warm, Same) v (|),(|),(|),(|),(|),(|)G3 = (Sunny, ?, ?, ?, ?, ?) v (?, Warm, ?, ?, ?, ?),(Sunny, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same), (?, Warm, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same) 2Example 4: <Sunny, Warm, High, Strong, Cool, Change, Yes>S4= (Sunny, Warm, ?, S

5、trong, ?, ?) v (Sunny, Warm, High, Strong, Warm, Same)，(Sunny, Warm, Normal, Strong, Warm, Same) v (Sunny, Warm, High,Strong, ?, ?)，(Sunny, Warm, ? , Strong, ? , ?) v ( (|),(|),(|),(|),(|),(|),(Sunny, Warm, ？ , Strong, Warm,Same)v (Sunny, Warm,High, Strong, Cool, Change)G4 = (Sunny, ?, ?, ?, ?, ?) v

6、 (?, Warm, ?, ?, ?, ?),(Sunny, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same), (?, Warm, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same)2.5 请看以下的正例和反例序例，它们描述的概念是“两个住在同一房间中的人 ”。 每个训练样例描述了一个有序对，每个人由其性别、头发颜色 ( black , brown或 blonde)、身高(tall , medium； short )以及国籍(US French, German Irish ,Indian , Chinese 或 Portuguese )。+ &

7、lt; < male brown tall US >, < female black short US > >+ < < male brown short French >, < female black short US > >- < < female brown tall German >, < female black short Indian > >+ < < male brown tall Irish >, < female brown short Irish

8、 > >考虑在这些实例上定义的假设空间为：其中所有假设以一对4元组表示，其中每个值约束与EnjoySport 中的假设表示相似，可以为：特定值、“?”或者“?”。例如，下面的假设：< < male ? Tall ? > < female ? ? French> >它表示了所有这样的有序对：第一个人为高个男性(国籍和发色任意)，第二个人为法国女性(发色和身高任意)。(a)根据上述提供的训练样例和假设表示，手动执行候选消除算法。特别是要 写出处理了每一个训练样例后变型空间的特殊和一般边界。(b)计算给定的假设空间中有多少假设与下面的正例一致：+ &l

9、t; < male black short Portuguese > < female blonde tall Indian > >(c)如果学习器只有一个训练样例如(b)中所示，现在由学习器提出查询，并由施教者给出其分类。求出一个特定的查询序列，以保证学习器收敛到单个正确的假设，而不论该假设是哪一个(假定目标概念可以使用给定的假设表示语言来描述)。求出最短的查询序列。这一序列的长度与问题(b)的答案有什么关联？(d)注意到这里的假设表示语言不能够表示这些实例上的所有概念(如我们可定义出一系列的正例和反例，它们并没有相应的可描述假设)。如果要扩展这一语言， 使其能

10、够表达该实例语言上的所有概念，那么 ( c) 的答案应该如何更改。答： (a). 第一步：S0 <(Q Q Q Q ), (Q Q Q Q)>G0 <(? ? ? ?), (? ? ? ?)>第二步：S1 <(male brown tall US), (female black short US)>G1 <(? ? ? ?), (? ? ? ?)>第三步：S2 <(male brown ? ?), (female black short US)>G2 <(? ? ? ?), (? ? ? ?)>第四步：S3 <(ma

11、le brown ? ?), (female black short US)>G3 <(male ? ? ?), (? ? ? ?)>， <? ? ? ?>,<? ? ? US>第五步：S4 <(male brown ? ?), (female ? short ?)>G4 <(male ? ? ?), (? ? ? ?)>(b) . 假设中的每个属性可以取两个值，所以与题目例题一致的假设数目为：2*2*2*2 ) *( 2*2*2*2 )= 256(c) . 这个最短序列应该为8， 28 256如果只有一个训练样例，则假设空间有

12、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>,

13、<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

14、,US>(d) . 若要表达该实例语言上的所有概念，那么我们需要扩大假设空间，使得每个可能的假设都包括在内，这样假设空间就远远大于256，而且这样没法得到最终的没法收敛，因为对每一个未见过的训练样例，投票没有任何效果，因此也就没有办法对未见样例分类。所以不存在一个最优的查询序列。4欢迎下载 。精品文档3.2考虑下面的训练样例集合:实例分类*71门之1+TTfarTT3-TF4+rF5-FT6-FT(a)请计算这个训练样例集合对于目标函数分类的嫡。 (b)请计算属性a2相对这些训练样例的信息增益。答：cEntropy (S) pi log2 pi0.5log2 0.5 0.5log2 0.

15、5i 1一 一 一 一| S, |一一Gain(S A) Entropy(S)Entropy(Sv)v Values (A) | S |1 /EntropyS) 26 Entropy(SF)1 46*1 26*1 09欢血下载3.4 ID3仅寻找一个一致的假设，而候选消除算法寻找所有一致的假设。 考虑这两种学习算法间的对应关系。(a)假定给定EnjoySport的四个训练样例，画出ID3学习的决策树。其 中EnjoySport目标概念列在第2章的表2-1中。(b)学习到的决策树和从同样的样例使用变型空间算法得到的变型空 问(见第2章图2-3)间有什么关系？树等价于变型空间的一个成员吗？(c)增

16、加下面的训练样例，计算新的决策树。这一次，显示出增长树的 每一步中每个候选属性的信息增益。，而J/m即jG力T£研V 卯 qf/7叫"雅SmifeN0(d)假定我们希望设计一个学习器，它搜索决策树假设空间(类似 ID3) 并寻找与数据一致的所有假设(类似候选消除)。简单地说，我们希望应用候 选消除算法搜索决策树假设空间。写出经过表 2-1的第一个训练样例后的S和G 集合。注意S必须包含与数据一致的最特殊的决策树，而 成须包含最一般的。 说明遇到第二个训练样例时S和G®合是如何被改进的(可以去掉描述同一个概 念的语法不同的树)。在把候选消除算法应用到决策树假设空间时

17、，预计会碰 到什么样的困难？(a)解：要画决策树，需要计算每个候选属性相对于整个样例集合S的信息增益，然后选择信息增益最高的一个属性作为树节点上第一个被测试的属性。Gain(S, Sky尸 0.8113Gain(S, AirTemp尸 0.8113Gain(S, Humidity尸 0.1226Gain(S, Wind)=0Gain(S, Water尸 0.1226Gain(S, Forecast)，0.3113(b) (1)学习到的决策树只包含一个与训练样例一致的假设，使用变型空间算法得到的变型空间包含了所有与训练样例一致的假设，但变型空间只含各属性合 取式的集合，如果目标函数不在假设空间中

18、，即合取连接词不能表示最小的子式 时，变型空间将会是空的。在本例中，学习到的决策树Sky = Sunny ”与变型空间中的 G集合中的假设<Sunny, ?,?,?,?,?> 等价，Air-Temp= Warm”与G的 v?,Warm,?,?,?,?> 等价。学习到的决策树是用变型空间算法得到的变型空间是一种包含关系，前者是后者的子集或者说是后者的一个元素，(2)在此例子中决策树等价于变型空间的一个成员，但是一般情况的决策 树并不一定等价于变型空间中的一个成员，因为决策树的判别有顺序，而假设空间中的元素的各个性质没有顺序(c)Gain(S, Sky尸 0.3219Gain(S

19、, AirTemp尸 0.3219Gain(S, Humidity尸 0.0200Gain(S, Wind尸 0.3219Gain(S, Water尸 0.1710Gain(S, Forecast尸 0.0200显然第一个属性应该选择 Sky AirTemp Wind若第一个属性为Sky则：Gain(Ssunny, AirTemp尸 0Gain(Ssunny, Humidity尸 0.3113Gain(Ssunny, Wind尸 0.8113 ( 最大)Gain(Ssunny, Water)= 0.1226Gain(Ssunny, Forecast尸 0.1226若第一个属性为AirTemp则

20、：Gain(Swarm, Sky)= 0Gain(Swarm, Humidity)= 0.3113Gain(Swarm, Wind)= 0.8113 ( 最大)Gain(Swarm, Water)= 0.1226Gain(Swarm, Forecast尸 0.1226若第一个属性为Wind则：Gain(Sstrony, Sky)= 0.8113 ( 最大)Gain(Sstrony, AirTemp尸 0.8113 ( 最大)Gain(Sstrony, Humidity)= 0.1226Gain(Sstrony, Water)= 0.1226Gain(Sstrony, Forecast)= 0.

21、3113Entropy (S) =-(3/5)log(3/5)(2/5)log(2/5)=0.9710所有六个属性的信息增益为：Gain(S,Sky)=Entropy(S)-4/5*(1/4)log(1/4)(3/4)log(3/4)1/5*log1=0.97100.6490=0.3220Gain(S,Air - Temp=Entropy(S)-4/5*(1/4)log(1/4)(3/4)log(3/4)1/5*log1=0.97100.6490=0.3220Gain(S,Humidity )=Entropy(S)-2/5*(1/2*log(1/2)*2)3/5*(2/3*log(2/3)13

22、*log(1/3)=0.97100.9510=0.0200Gain(S,Wind)=Entropy(S)-4/5*(1/4*log(1/4)3/4*log(3/4)1/5*log1=0.97100.6490=0.3220Gain (S, Warm! = Entropy (S)-4/5*(2/4*log(2/4)2/4*log(2/4)1/5*log1 =0.97100.8000=0.1710EntropyGain(S,Forecast)(S)-2/5*(1/2*log(1/2)*2)3/5*(2/3*log(2/3)1/3*log(1/3)=0.97100.9510=0.0200选择Sky, Air-Temp, Wind中的任何一个作为根节点的决策属性即可，这里选择Sky作为根节点的决策属性，建立决策树如下：R& iny计算下一步的信息增益如下：Entropy (Sunny = -(1/4)log(1/4)(3/4)log(3/4) =0.8113Gain (Sunny Air -Temp = Entropy ( Sunny-(1/4*log(1/4)3/4*log(3/4)=0Gain (Sunny Humidity) = Entropy ( S)-2/4*(1/2*log(1/2)*2)2/4*log1 =0.81130