注：本文为《机器学习》（周志华）第一章的作业笔记。

1.1

表 1.1 的编号为 1, 4 的两个样例：

因为只有两个样本，我们只要能够保证：

$$
s_好 \in S, s_坏 \notin S
$$

1.2

首先我们可以将决策看作一棵树，而每一个取式其实就是一棵子树或者叶子节点。会过来看合取式的析合范式，其实就是在一整棵树中取 $k$ 个互相不包含的子树或者叶子节点。

这里不能直接确定答案，因为题目并没有说决策树能不能给出形如下面的节点：

$$
(色泽\in\{青绿，乌黑\}; 根蒂=*; 敲声=*)
$$

我们先假设题目不允许上述的情况出现，那我们可以断言，包含 $n$ 个并列条件的决策，整棵树的深度为 $n + 1$，因为每一个父子关系其实就是析构 $*$ 和具体内容。

这个问题其实不能简单估算，但是我们可以用树形动态规划来解决。设状态 $f[u][p]$ 代表以节点 $u$ 为根的子决策树有 $p$ 个合取式的析合范式情况数。同时我们注意到书上的旁注：会有冗余的等价情况，那么我们还需要去除这样的等价情况，即在本题中我们需要去除

$$
\bigcup_{v \in u.sons} v = u
$$

的情况。

下面是递推方程：

$$
f[u][p] = \sum_{\sum_{1 \leq i \leq |u.sons|} p_i = p, p_i \geq 0} f[v_i][p_i]
$$

减去冗余情况：

$$
f[u][|u.sons|] := f[u][|u.sons|] - 1
$$

1.3

举例：线性回归。

1.4

$$
E_{ote} (\mathfrak L_a | X, f) = \sum_h \sum_{\boldsymbol x \in \mathcal X - X} P(\boldsymbol x) \ell (h(\boldsymbol x), f(\boldsymbol x)) P(h | X, \mathfrak L_a)
$$

$$
\begin{aligned}
\sum_f E_{ote} &= \sum_f \sum_h \sum_{\boldsymbol x \in \mathcal X - X} P(\boldsymbol x) \ell (h(\boldsymbol x), f(\boldsymbol x)) P(h | X, \mathfrak L_a) \\
&=\sum_{\boldsymbol x \in \mathcal X - X}P(\boldsymbol x)\sum_h P(h | X, \mathfrak L_a) \sum_f \ell (h(\boldsymbol x), f(\boldsymbol x))
\end{aligned}
$$

注意到最后一部分为与 $\mathfrak L$ 无关的常数。不妨设

$$
L = \sum_f \ell (h(\boldsymbol x), f(\boldsymbol x))
$$

故原式等于

$$
L\sum_{\boldsymbol x \in \mathcal X - X}P(\boldsymbol x)\sum_h P(h | X, \mathfrak L_a) = L\sum_{\boldsymbol x \in \mathcal X - X}P(\boldsymbol x) \cdot 1
$$

Q.E.D.

1.5

略。