习题

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

1.2 与使用单个合取式来进行假设表示相比，使用“析合范式”将使得假设空间具有更强的表示能力。例如

析合范式即多个合取式的析取。

提示：注意冗余情况，如（A=ɑ）∨（A=*）与（A=*）等价。

会把“（色泽=青绿）∧（根蒂=蜷缩）∧（敲声=清脆）”以及“（色泽=乌黑）∧（根蒂=硬挺）∧（敲声=沉闷）”都分类为“好瓜”。若使用最多包含k个合取式的析合范式来表达表1.1西瓜分类问题的假设空间，试估算共有多少种可能的假设。

即不存在训练错误为0的假设。

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

1.4* 本章1.4节在论述“没有免费的午餐”定理时，默认使用了“分类错误率”作为性能度量来对分类器进行评估。若换用其他性能度量，则式（1.1）将改为

试证明“没有免费的午餐定理”仍成立。

1.5 试述机器学习能在互联网搜索的哪些环节起什么作用。