上QQ阅读APP看书，第一时间看更新

第1章　绪论

式(1.1)

$E_{o%20t%20e}\left(\mathfrak{L}_{a}%20|%20X,%20f\right%29=\sum_{h}%20\sum_{\boldsymbol{x}%20\in\mathcal{X}-X}%20P(\boldsymbol{x}%29%20\mathbb{I}(h(\boldsymbol{x}%29\neq%20f(\boldsymbol{x}%29%29%20P\left(h%20|%20X,%20\mathfrak{L}_{a}\right%29$

参见式 (1.2)

式(1.2）

$\sum_{f} E_{\text {ote }}\left(\mathfrak{L}_{a} \mid X, f\right)=\sum_{f} \sum_{h} \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \mathbb{I}(h(\boldsymbol{x}) \neq f(\boldsymbol{x})) P\left(h \mid X, \mathfrak{L}_{a}\right)$ 　　①

　 $=\sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \sum_{h} P\left(h \mid X, \mathfrak{L}_{a}\right) \sum_{f} \mathbb{I}(h(\boldsymbol{x}) \neq f(\boldsymbol{x}))$ 　　②

　 $=\sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \sum_{h} P\left(h \mid X, \mathfrak{L}_{a}\right) \frac{1}{2} 2^{|\mathcal{X}|}$ 　　③

　 $=\frac{1}{2} 2^{|\mathcal{X}|} \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \sum_{h} P\left(h \mid X, \mathfrak{L}_{a}\right)$ 　　④

　 $=2^{|\mathcal{X}|-1} \sum_{\boldsymbol{x} \in \mathcal{X}-X} P(\boldsymbol{x}) \cdot 1$ 　　⑤

③ $\to$ ⑤显然成立

解析

① $\to$ ②：

$\begin{aligned}&\quad \sum_f\sum_h\sum_{\boldsymbol{x}\in\mathcal{X}-X}P(\boldsymbol{x})\mathbb{I}(h(\boldsymbol{x})\neq f(\boldsymbol{x}))P(h\vert X,\mathfrak{L}_a) \\&=\sum_{\boldsymbol{x}\in\mathcal{X}-X}P(\boldsymbol{x})\sum_f\sum_h\mathbb{I}(h(\boldsymbol{x})\neq f(\boldsymbol{x}))P(h\vert X,\mathfrak{L}_a) \\&=\sum_{\boldsymbol{x}\in\mathcal{X}-X}P(\boldsymbol{x}) \sum_hP(h\vert X,\mathfrak{L}_a)\sum_f\mathbb{I}(h(\boldsymbol{x})\neq f(\boldsymbol{x})) \\\end{aligned}$

② $\to$ ③：首先要知道此时我们假设是任何能将样本映射到{0,1}的函数.存在不止一个时，服从均匀分布，即每个出现的概率相等.例如样本空间只有两个样本时， $\mathcal{X}={\boldsymbol{x}_1,\boldsymbol{x}_2\},\vert\mathcal{X} \vert=2$ .那么所有可能的真实目标函数如下：

$f_1:f_1(\boldsymbol{x}_1)=0,f_1(\boldsymbol{x}_2)=0;\\f_2:f_2(\boldsymbol{x}_1)=0,f_2(\boldsymbol{x}_2)=1;\\f_3:f_3(\boldsymbol{x}_1)=1,f_3(\boldsymbol{x}_2)=0;\\f_4:f_4(\boldsymbol{x}_1)=1,f_4(\boldsymbol{x}_2)=1.$

一共 $2^{\vert \mathcal{X} \vert}=2^2=4$ 个可能的真实目标函数.所以此时通过算法 $\mathfrak{L}_a$ 学习出来的模型 $h(\boldsymbol{x})$ 对每个样本无论预测值为0还是1，都必然有一半的与之预测值相等.例如，现在学出来的模型 $h(\boldsymbol{x})$ 对 $\boldsymbol{x}_1$ 的预测值为1，即 $h(\boldsymbol{x}_1)=1$ ，那么有且只有 f_3 和 f_4 与 $h(\boldsymbol{x})$ 的预测值相等，也就是有且只有一半的与它预测值相等，所以 $\sum_f\mathbb{I}(h(\boldsymbol{x})\neq f(\boldsymbol{x})) = \frac{1}{2}2^{\vert \mathcal{X} \vert}$ .

值得一提的是，在这里我们假设真实的目标函数服从均匀分布，但是实际情形并非如此，通常我们只认为能高度拟合已有样本数据的函数才是真实目标函数，例如，现在已有的样本数据为 ${(\boldsymbol{x}_1,0),(\boldsymbol{x}_2,1)\}$ ，那么此时 f_2 才是我们认为的真实目标函数，由于没有收集到或者压根不存在 ${(\boldsymbol{x}_1,0),(\boldsymbol{x}_2,0)\},\{(\boldsymbol{x}_1,1),(\boldsymbol{x}_2,0)\},\{(\boldsymbol{x}_1,1),(\boldsymbol{x}_2,1)\}$ 这类样本，所以 f_1,f_3,f_4 都不算是真实目标函数.这也就是“西瓜书”式(1.3)下面的第3段中“骑自行车”的例子所想表达的内容.

第1章 绪论

第1章　绪论