机器学习课后作业

机器学习课后作业学 院：电子工程学院专 业：电子与通信工程姓 名：叶旭庆学 号：2.3 继续考虑EnjoySport学习任务和2.2节中描述的假设空间H。如果定义一个新的假设空间H，它包含H中所有假设的成对析取。如H中一假设为： 试跟踪运行使用该假设空间H的候选消除算法，给定的训练样例如表2-1所示（需要分步列出S和G集合）。答：S0= (,) v (,)G0 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 1: S1=(Sunny, Warm, Normal, Strong, Warm, Same) v (,)G1 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 2: S2= (Sunny, Warm, Normal, Strong, Warm, Same) v (Sunny, Warm, High, Strong, Warm, Same)，(Sunny, Warm, ？, Strong, Warm, Same) v (,)G2 = (?, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, ?)Example 3: 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, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same)2Example 4: 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 (,)，(Sunny, Warm, ？, Strong, Warm, Same) v (Sunny, Warm, High, Strong, Cool, Change)G4 = (Sunny, ?, ?, ?, ?, ?) v (?, Warm, ?, ?, ?, ?),(Sunny, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same),(?, Warm, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same)2.5 请看以下的正例和反例序例，它们描述的概念是“两个住在同一房间中的人”。每个训练样例描述了一个有序对，每个人由其性别、头发颜色（black, brown 或blonde）、身高（tall, medium或short）以及国籍（US, French, German, Irish, Indian, Chinese或Portuguese）。+ , + , - , + , 考虑在这些实例上定义的假设空间为：其中所有假设以一对4元组表示，其中每个值约束与EnjoySport 中的假设表示相似，可以为：特定值、“?”或者“”。例如，下面的假设： 它表示了所有这样的有序对：第一个人为高个男性（国籍和发色任意），第二个人为法国女性（发色和身高任意）。（a）根据上述提供的训练样例和假设表示，手动执行候选消除算法。特别是要写出处理了每一个训练样例后变型空间的特殊和一般边界。（b）计算给定的假设空间中有多少假设与下面的正例一致： + （c）如果学习器只有一个训练样例如（b）中所示，现在由学习器提出查询，并由施教者给出其分类。求出一个特定的查询序列，以保证学习器收敛到单个正确的假设，而不论该假设是哪一个（假定目标概念可以使用给定的假设表示语言来描述）。求出最短的查询序列。这一序列的长度与问题（b）的答案有什么关联？ （d）注意到这里的假设表示语言不能够表示这些实例上的所有概念（如我们可定义出一系列的正例和反例，它们并没有相应的可描述假设）。如果要扩展这一语言，使其能够表达该实例语言上的所有概念，那么（c）的答案应该如何更改。答：(a). 第一步：S0 G0 第二步：S1 G1 第三步：S2 G2 第四步：S3 G3 ，,第五步：S4 G4 (b).假设中的每个属性可以取两个值，所以与题目例题一致的假设数目为：（2*2*2*2）*（2*2*2*2） = 256(c). 这个最短序列应该为8，如果只有一个训练样例，则假设空间有个假设，我们针对每一个属性来设置训练样例，使每次的假设空间减半。则经过8次训练后，可收敛到单个正确的假设。,(d). 若要表达该实例语言上的所有概念，那么我们需要扩大假设空间，使得每个可能的假设都包括在内，这样假设空间就远远大于256，而且这样没法得到最终的没法收敛，因为对每一个未见过的训练样例，投票没有任何效果，因此也就没有办法对未见样例分类。所以不存在一个最优的查询序列。3.2 考虑下面的训练样例集合：（a） 请计算这个训练样例集合对于目标函数分类的熵。（b） 请计算属性a2相对这些训练样例的信息增益。答：3.4 ID3仅寻找一个一致的假设，而候选消除算法寻找所有一致的假设。考虑这两种学习算法间的对应关系。（a）假定给定EnjoySport的四个训练样例，画出ID3学习的决策树。其中EnjoySport目标概念列在第2章的表2-1中。（b）学习到的决策树和从同样的样例使用变型空间算法得到的变型空间（见第2章图2-3）间有什么关系？树等价于变型空间的一个成员吗？ （c）增加下面的训练样例，计算新的决策树。这一次，显示出增长树的每一步中每个候选属性的信息增益。（d）假定我们希望设计一个学习器，它搜索决策树假设空间（类似ID3）并寻找与数据一致的所有假设（类似候选消除）。简单地说，我们希望应用候选消除算法搜索决策树假设空间。写出经过表2-1的第一个训练样例后的S和G集合。注意S必须包含与数据一致的最特殊的决策树，而G必须包含最一般的。说明遇到第二个训练样例时S和G集合是如何被改进的（可以去掉描述同一个概念的语法不同的树）。在把候选消除算法应用到决策树假设空间时，预计会碰到什么样的困难？答： （a）解：要画决策树，需要计算每个候选属性相对于整个样例集合S的信息增益，然后选择信息增益最高的一个属性作为树节点上第一个被测试的属性。 Gain(S, Sky)= 0.8113 Gain(S, AirTemp)= 0.8113 Gain(S, Humidity)= 0.1226 Gain(S, Wind)=0 Gain(S, Water)= 0.1226 Gain(S, Forecast)= 0.3113 (b) （1）学习到的决策树只包含一个与训练样例一致的假设，使用变型空间算法得到的变型空间包含了所有与训练样例一致的假设，但变型空间只含各属性合取式的集合，如果目标函数不在假设空间中，即合取连接词不能表示最小的子式时，变型空间将会是空的。 在本例中，学习到的决策树“Sky = Sunny”与变型空间中的G集合中的假设 等价，“Air-Temp= Warm”与G中的等价。 学习到的决策树是用变型空间算法得到的变型空间是一种包含关系，前者是后者的子集或者说是后者的一个元素， （2）在此例子中决策树等价于变型空间的一个成员，但是一般情况的决策树并不一定等价于变型空间中的一个成员，因为决策树的判别有顺序，而假设空间中的元素的各个性质没有顺序 (c) Gain(S, Sky)= 0.3219 Gain(S, AirTemp)= 0.3219 Gain(S, Humidity)= 0.0200 Gain(S, Wind)= 0.3219 Gain(S, Water)= 0.1710 Gain(S, Forecast)= 0.0200 显然第一个属性应该选择 Sky AirTemp Wind 若第一个属性为 Sky 则： Gain(Ssunny, AirTemp)= 0 Gain(Ssunny, Humidity)= 0.3113 Gain(Ssunny, Wind)= 0.8113 (最大) Gain(Ssunny, Water)= 0.1226 Gain(Ssunny, Forecast)= 0.1226 若第一个属性为 AirTemp 则： Gain(Swarm, Sky)= 0 Gain(Swarm, Humidity)= 0.3113 Gain(Swarm, Wind)= 0.8113 (最大) Gain(Swarm, Water)= 0.1226 Gain(Swarm, Forecast)= 0.1226 若第一个属性为 Wind 则： Gain(Sstrony, Sky)= 0.8113 (最大) Gain(Sstrony, AirTemp)= 0.8113 (最大) Gain(Sstrony, Humidity)= 0.1226 Gain(Sstrony, Water)= 0.1226 Gain(Sstrony, Forecast)= 0.3113 Entropy (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.3220 Gain (S, Air-Temp) = Entropy (S)-4/5*(1/4)log(1/4)(3/4)log(3/4)1/5*log1 - =0.97100.6490=0.3220 Gain(S, Humidity) = Entropy (S)-2/5*(1/2*log(1/2)*2)3/5*(2/3*log(2/3)13*log(1/3) - =0.97100.9510=0.0200 Gain (S, Wind) = Entropy (S)-4/5*(1/4*log(1/4)3/4*log(3/4)1/5*log1- =0.97100.6490=0.3220 Gain (S, Warm) = Entropy (S)-4/5*(2/4*log(2/4)2/4*log(2/4)1/5*log1 - =0.97100.8000=0.1710 Gain (S, Forecast) = Entropy (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作为根节点的决策属性，建立决策树如下： 计算下一步的信息增益如下： Entropy (Sunny) =-(1/4)log(1/4)(3/4)log(3/4) =0.8113 Gain (Sunny, Air-Temp) = Entropy (Sunny)-(1/4*log(1/4)3/4*log(3/4)=0 Gain (Sunny, Humidity) = Entropy (S)-2/4*(1/2*log(1/2)*2)2/4*log1- =0.81130.5000=0.3113 Gain (Sunny, Wind) = Entropy (S)-3/4*log1-1/4*log1 =0.8113 Gain (Sunny, Water) = Entropy (S)-3/4*(1/3*log(1/3)2/3*log(3)1/4*log1=0.81130.6887=0.1226 Gain (Sunny, Forecast) = Entropy (S)-3/4*(1/3*log(1/3)2/3*log(3)1/4*log1 - =0.81130.6887=0.1226 由于Gain (Sunny, Wind)最大，选择Wind做为新的叶子节点，建立决策树如下： 至此，已用完所有的训练样例，决策树建立完毕。 （d）经过表2-1的第一个训练样例后的S和G 如下： S1： G1: ? 表示对所有例子都接受为正例 当遇到第二个训练样例：，EnjoySport=YesS2：G2: ? 表示对所有例子都接受为正例在把候选消除算法应用到决策树假设空间时，预计会遇到如下四种困难： （1）在把候选消除算法应用到决策树假设空间时，如