机器学习课后作业

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

2、v ( © , © , © , © , © , ©)G0 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 1: <Sunny, Warm, Normal, Strong, Warm, Same, Yes> S1=(Sunny, Warm, Normal, Strong, Warm, Same) v ( G1 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)J/ IJ ) ) )/*，/©,©,©,©,

3、©,©)Example 2: <Sunny, Warm, High, Strong, Warm, Same, Yes> S2= (Sunny, Warm, Normal, Strong, Warm, Same) v (Sunny, Warm, High, Strong, Warm, Same) ， (Sunny, Warm, ？, Strong, Warm, Same) v ( G2 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 3: <Rainy, Cold, High, Strong, Warm, C

4、hange, No>S3=(Sunny, Warm,Normal, Strong, Warm , Same)v (Sunny, Warm,High, Strong, Warm, Same)，©,©,©,©,©,©)(Sunny, Warm, ？, Strong, Warm, Same) v (G3 = (Sunny, ?, ?, ?, ?, ?) v (?, Warm, ?, ?, ?, ?), (Sunny, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same), (?, Warm, ?, ?, ?,

5、?) v (?, ?, ?, ?, ?, Same) 2Example 4: <Sunny, Warm, High, Strong, Cool, Change, Yes>S4= (Sunny, Warm, ?, Strong, ?, ?) v (Sunny, Warm, High, Strong, Warm, Same)，(Sunny, Warm, Normal, Strong, Warm, Same) v (Sunny, Warm, High, Strong, ?, ?) ，(Sunny, Warm, ？, Strong, ？, ？) v ( © , © ,

6、© , © , © , © ) ，(Sunny, Warm, ？ , Strong, Warm , Same)v (Sunny, Warm,High, Strong, Cool, Change)G4 = (Sunny, ?, ?, ?, ?, ?) v (?, Warm, ?, ?, ?, ?), (Sunny, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same), (?, Warm, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same)2.5 请看以下的正例和反例序例，它们描述的概念是 “两个住在同一房间中的

7、 人”。每个训练样例描述了一个有序对， 每个人由其性别、 头发颜色（ black, brown 或bionde）、身高（tall, medium或short）以及国籍（US, French. German, Irish ,In dia n, Chin ese或 P ortuguese）。+ < <male brown tall US>, <female black short US> >+ < <male brown short French>, <female black short US> >- < <fe

8、male brown tall German>, <female black short Indian > >+ < <male brown tall Irish >, <female brown short Irish > >考虑在这些实例上定义的假设空间为：其中所有假设以一对4元组表示，其中每个值约束与 EnjoySport 中的假设表示相似，可以为：特定值、“?”或者“?”。例如，下面的假设：< <male ? Tall ? > <female ? ? French> > 它表示了所有这样的有

9、序对：第一个人为高个男性（国籍和发色任意），第二 个人为法国女性（发色和身高任意）。（a）根据上述提供的训练样例和假设表示，手动执行候选消除算法。特别是要 写出处理了每一个训练样例后变型空间的特殊和一般边界。（b）计算给定的假设空间中有多少假设与下面的正例一致：+ < <male black short Portuguese> <female blonde tall Indian> >（C）如果学习器只有一个训练样例如（b）中所示，现在由学习器提出查询，并由施教者给出其分类。求出一个特定的查询序列，以保证学习器收敛到单个正确的假设，而不论该假设是哪一个（假定

10、目标概念可以使用给定的假设表示语言来描述）。求出最短的查询序列。这一序列的长度与问题（b）的答案有什么关联？（d）注意到这里的假设表示语言不能够表示这些实例上的所有概念（如我们可 定义出一系列的正例和反例，它们并没有相应的可描述假设） 。如果要扩展这一 语言，使其能够表达该实例语言上的所有概念，那么（C）的答案应该如何更改。答： (a). 第一步： S0 <(Q Q Q Q ), (Q Q Q Q)>G0 <(? ? ? ?), (? ? ? ?)>51 <(male brown tall US), (female black short US)>G1 &l

11、t;(? ? ? ?), (? ? ? ?)>52 <(male brown ? ?), (female black short US)>G2 <(? ? ? ?), (? ? ? ?)>53 <(male brown ? ?), (female black short US)>G3 <(male ? ? ?), (? ? ? ?，)><? ? ? ?>,<? ? ? US>54 <(male brown ? ?), (female ? short ?)>G4 <(male ? ? ?), (? ?

12、 ? ?)>第二步：第三步：第四步：第五步：(b) .假设中的每个属性可以取两个值，所以与题目例题一致的假设数目为:( 2*2*2*2 ) * ( 2*2*2*2 ) = 2568(c) . 这个最短序列应该为 8， 282568如果只有一个训练样例，则假设空间有 28 256 个假设，我们针对每一个属性来 设置训练样例， 使每次的假设空间减半。 则经过 8 次训练后，可收敛到单个正确 的假设。<female,blanck,short,Portuguese>,<female,blonde,tall,Indian> <male,brown,short,Port

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

14、,tall,Indian> <male,blanck,short,Portuguese>,<female,blonde,short,Indian> <male,blanck,short,Portuguese>,<female,blonde,tall,US>(d) . 若要表达该实例语言上的所有概念， 那么我们需要扩大假设空间， 使得每个 可能的假设都包括在内，这样假设空间就远远大于 256，而且这样没法得到最终 的没法收敛， 因为对每一个未见过的训练样例， 投票没有任何效果， 因此也就没 有办法对未见样例分类。所以不存在一个最优的查询序列。

15、3.2考虑下面的训练样例集合:分类和1g1+TTr4+TT5-TF4+rrqk-FT6FT请计算这个训练样例集合对于目标函数分类的熵。 请计算属性a2相对这些训练样例的信息增益。答:Entropy (S)Pi log 2 Pii 10.5log2 0.5 0.5log2 0.51Gai n(S A)Entrop y(S)v Values(A) | S |Entropy(Sv)1 46 Entropy(ST)% Entropy®1 46*1 %*1 03.4 ID3仅寻找一个一致的假设，而候选消除算法寻找所有一致的假设。 考虑这两种学习算法间的对应关系。（a）假定给定EnjoySpor

16、t的四个训练样例，画出ID3学习的决策树。其 中EnjoySport目标概念列在第2章的表2-1中。（b ）学习到的决策树和从同样的样例使用变型空间算法得到的变型空 间（见第2章图2-3）间有什么关系？树等价于变型空间的一个成员吗？（C）增加下面的训练样例，计算新的决策树。这一次，显示出增长树的 每一步中每个候选属性的信息增益。1rriirijjHivrA（d）假定我们希望设计一个学习器，它搜索决策树假设空间（类似 ID3） 并寻找与数据一致的所有假设（类似候选消除）。简单地说，我们希望应用候 选消除算法搜索决策树假设空间。写出经过表 2-1的第一个训练样例后的S和G 集合。注意S必须包含与数

17、据一致的最特殊的决策树， 而G必须包含最一般的。 说明遇到第二个训练样例时S和 G集合是如何被改进的（可以去掉描述同一个 概念的语法不同的树）。在把候选消除算法应用到决策树假设空间时，预计会 碰到什么样的困难？答:（a）解：要画决策树，需要计算每个候选属性相对于整个样例集合S的信息增益，然后选择信息增益最高的一个属性作为树节点上第一个被测试的属性。Gai n（S, Sky）= 0.8113Gai n（S, AirTem p）= 0.8113Gai n（S, Humidity）= 0.1226Gai n（S, Win d）=0Gai n（S, Water）= 0.1226Gai n（S, For

18、ecast）= 0.3113（b）（ 1）学习到的决策树只包含一个与训练样例一致的假设，使用变型空间算法得到的变型空间包含了所有与训练样例一致的假设，但变型空间只含各属性合 取式的集合，如果目标函数不在假设空间中，即合取连接词不能表示最小的子式 时，变型空间将会是空的。在本例中，学习到的决策树Sky = Sunny ”与变型空间中的 G集合中的假设vSunny, ?,?,?,?,?> 等价，Air-Temp= Warm”与G中的v?,Warm?> 等价。学习到的决策树是用变型空间算法得到的变型空间是一种包含关系，前者 是后者的子集或者说是后者的一个元素，（2）在此例子中决策树等价于

19、变型空间的一个成员，但是一般情况的决策 树并不一定等价于变型空间中的一个成员，因为决策树的判别有顺序，而假设空间中的元素的各个性质没有顺序（C）Gai n(S, Sky)= 0.3219Gai n(S, AirTem p)= 0.3219Gai n(S, Humidity)= 0.0200Gai n(S, Win d)= 0.3219Gai n(S, Water)= 0.1710Gai n(S, Forecast)= 0.0200显然第一个属性应该选择 Sky AirTe mp Wind 若第一个属性为Sky贝U：Gain(Ssunny, AirTe mp )= 0Gai n(Ssu nny,

20、 Humidity)= 0.3113Gai n(Ssu nny, Wind)= 0.8113 (最大)Gai n(Ssu nny, Water)= 0.1226Gai n(Ssu nny, Forecast)= 0.1226若第一个属性为AirTemp贝U：Gai n(Swarm, Sky)= 0Gai n(Swarm, Humidity)= 0.3113Ga in (Swarm, Win d)= 0.8113 ( 最大)Gai n(Swarm, Water)= 0.1226Gai n(Swarm, Forecast)= 0.1226若第一个属性为Wind贝U：最大）最大）Gai n(Sstr

21、o ny, Sky)= 0.8113 (Gain (Sstro ny, AirTem p)= 0.8113 (Gai n(Sstro ny, Humidity)= 0.1226Gai n(Sstro ny, Water)= 0.1226Gain (Sstro ny, Forecast)= 0.3113Entropy (S) = -(3/5)log(3/5)(2/5)log(2/5)=0.9710所有六个属性的信息增益为：Ga in (S, Sky) = Entropy (S)-4/5*(1/4)log(1/4)(3/4)log(3/4)1/5*log1=0.9710 0.6490=0.3220

22、Ga in (S Air-Temp)= Entropy (S)-4/5*(1/4)log(1/4)(3/4)log(3/4)1/5*log1 =0.9710 0.6490=0.3220Ga in(S, Humidity) = Entropy (S)-2/5*(1/2*log(1/2)*2)3/5*(2/3*log(2/3)13*log(1/3) =0.9710 0.9510=0.0200Gai n (S, Wind) = Entropy (S)-4/5*(1/4*log(1/4)3/4*log(3/4)1/5*log1=0.9710 0.6490=0.3220Gai n (S, Warm) =

23、 Entropy (S)-4/5*(2/4*log(2/4)2/4*log(2/4)1/5*log1=0.9710 0.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.9710 0.9510=0.0200选择Sky, Air-Temp , Wind中的任何一个作为根节点的决策属性即可，这里选择Sky作为根节点的决策属性，建立决策树如下：计算下一步的信息增益如下：Entropy (Su nny) =-(1/4)log(1/4)(3/4)log(3/4) =0.8113Gai n (Su nny Air-Temp) = Entropy (Su nn y)-(1/4*log(1/4)3/4*log(3/4) =0Gai n (Su nny Humidity) = Entropy (S)-2/4*(1/2*log(1/2)*2)2/4*log1=0.8113 0.5000=0