机器学习课后作业
学 院：电子工程学院 专 业：电子与通信工程 姓 名：叶旭庆 学 号：1302121315
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:
(Sunny, Warm, ？, Strong, Warm, Same) v (φ,φ,φ,φ,φ,φ)} G3 = {(Sunny, ?, ?, ?, ?, ?) v (?, Warm, ?, ?, ?, ?), (Sunny, ?, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same), (?, Warm, ?, ?, ?, ?) v (?, ?, ?, ?, ?, Same)} 2
Example 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 {<(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 {<(male brown ? ?), (female black short US)> G3 {<(male ? ? ?), (? ? ? ?)>，,} 第五步：S4 {<(male brown ? ?), (female ? short ?)> G4 {<(male ? ? ?), (? ? ? ?)>}
(b).假设中的每个属性可以取两个值，所以与题目例题一致的假设数目为： （2*2*2*2）*（2*2*2*2） = 256
8(c). 这个最短序列应该为8，2?256
82如果只有一个训练样例，则假设空间有?256个假设，我们针对每一个属性来
设置训练样例，使每次的假设空间减半。则经过8次训练后，可收敛到单个正确的假设。
(d). 若要表达该实例语言上的所有概念，那么我们需要扩大假设空间，使得每个可能的假设都包括在内，这样假设空间就远远大于256，而且这样没法得到最终的没法收敛，因为对每一个未见过的训练样例，投票没有任何效果，因此也就没有办法对未见样例分类。所以不存在一个最优的查询序列。
3.2 考虑下面的训练样例集合：
（a） 请计算这个训练样例集合对于目标函数分类的熵。 （b） 请计算属性a2相对这些训练样例的信息增益。 答：
Entropy(S)???pilog2pi??0.5log20.5?0.5log20.5?1i?1c
Gain(S?A)?Entropy(S)?|Sv|Entropy(Sv)?v?Values(A)|s|?1?4Entropy(ST)?2Entropy(SF)66?1?4*1?2*1?066