1.1 表1.1中若只包含编号为1和4的两个样例，试给出相应的版本空间。

假设空间：问题所有可能出现的情况组成的空间。

版本空间：与训练集正例一致的假设空间。

上表有3个属性，每个属性有两个取值。所以上述数据集假设空间大小为$$\begin{gathered} 3 \\ times3 \\ times3+1=28 \end{gathered}$$。

综上所述，问题一的版本空间为：

1. 色泽=“青绿”,根蒂=“蜷缩”,声音=“浊响”
2. 色泽=“青绿”,根蒂=“蜷缩”,声音="*"
3. 色泽=“青绿”,根蒂="*", 声音=“浊响”
4. 色泽=“青绿”,根蒂="*" 声音 ="*"
5. 色泽="*",根蒂=“蜷缩”, 声音="*"
6. 色泽="*", 根蒂 =“蜷缩”,声音=“浊响”
7. 色泽="*", 根蒂 ="*",声音=“浊响”

1.2 与使用单个合取式来进行假设表示相比，使用“析合范式”将使得假设空间具有更强的表示能力。若使用最多包含k个合取式的析合范式来表达1.1的西瓜分类问题的假设空间，试估算有多少种可能的假设。

合取范式 析合范式

表1.1包含3种属性,它的假设空间和大小为 $$\begin{gathered} 3 \\ times4 \\ times4+1=49 \end{gathered}$$。 考虑冗余情况: 具体假设:$$\begin{gathered} 2 \\ times3 \\ times3=18 \end{gathered}$$种; 一个通配符:$$\begin{gathered} 2 \\ times3+3 \\ times3+2 \\ times3=21 \end{gathered}$$种; 两个通配符:$$2+3+3=8$$种； 三个通配符:1种。

不考虑冗余、空集的情况下k最大取值为48，考虑冗余的情况下k最大取值为18.

• k=1时，共48种；
• k=18时，共1种。
• k取中间值，比较复杂，暂时没有想到解法。

1.3 若数据包含噪声，则假设空间中可能不存在与所有训练样本都一致的假设。在此情形下，试设计一种归纳偏好用于假设选择。