【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.基础知识
顾名思义，计算学习理论（computational learning theory）研究的是关于通过“计算”来进行“学习”的理论，即关于机器学习的理论基础，其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。
给定样例集$D=\{ (\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),…,(\mathbf{x}_m,y_m) \},\mathbf{x}_i \in \mathcal{X}$，本章主要讨论二分类问题，若无特别说明，$y_i \in \mathcal{Y} = \{ -1,+1 \}$。假设$\mathcal{X}$中的所有样本服从一个隐含未知的分布$\mathcal{D}$，$D$中所有样本都是独立地从这个分布上采样而得，即独立同分布（independent and identically distributed，简称i.i.d.）样本。
令$h$为从$\mathcal{X}$到$\mathcal{Y}$的一个映射，其泛化误差为：
\[E(h;\mathcal{D})=P_{\mathbf{x}\sim \mathcal{D}}(h(\mathbf{x})\neq y) \tag{1}\]$h$在$D$上的经验误差为：
\[\hat{E}(h;D)=\frac{1}{m}\sum_{i=1}^m \mathbb{I}(h(\mathbf{x}_i)\neq y_i) \tag{2}\]由于$D$是$\mathcal{D}$的独立同分布采样，因此$h$的经验误差的期望等于其泛化误差。在上下文明确时，我们将$E(h;\mathcal{D})$和$\hat{E}(h;D)$分别简记为$E(h)$和$\hat{E}(h)$。令$\epsilon$为$E(h)$的上限，即$E(h) \leqslant \epsilon$；我们通常用$\epsilon$表示预先设定的学得模型所应满足的误差要求，亦称“误差参数”。
本章后面部分将研究经验误差与泛化误差之间的逼近程度。若$h$在数据集$D$上的经验误差为0，则称$h$与$D$一致，否则称其与$D$不一致。对任意两个映射$h_1,h_2 \in \mathcal{X} \to \mathcal{Y}$，可通过其“不合”（disagreement）来度量它们之间的差别：
\[d(h_1,h_2) = P_{\mathbf{x}\sim \mathcal{D}}(h_1(\mathbf{x})\neq h_2 (\mathbf{x}))\tag{3}\]我们会用到几个常用不等式：
👉Jenson不等式：对任意凸函数$f(x)$，有：
\[f(\mathbb{E}(x)) \leqslant \mathbb{E}(f(x)) \tag{4}\]👉Hoeffding不等式：若$x_1,x_2,…,x_m$为$m$个独立随机变量，且满足$0 \leqslant x_i \leqslant 1$，则对任意$\epsilon > 0$，有：
\[P\left( \frac{1}{m}\sum_{i=1}^m x_i - \frac{1}{m}\sum_{i=1}^m \mathbb{E}(x_i) \geqslant \epsilon \right) \leqslant \exp (-2m\epsilon^2) \tag{5}\] \[P\left( \left| \frac{1}{m}\sum_{i=1}^m x_i - \frac{1}{m}\sum_{i=1}^m \mathbb{E}(x_i) \right| \geqslant \epsilon \right) \leqslant 2 \exp (-2m\epsilon^2) \tag{6}\]👉McDiarmid不等式：若$x_1,x_2,…,x_m$为$m$个独立随机变量，且对任意$1 \leqslant i \leqslant m$，函数$f$满足：
\[\sup_{x_1,...,x_m,x'_i} \lvert f(x_1,...,x_m) - f(x_1,...,x_{i-1},x'_i,x_{i+1},...,x_m) \rvert \leqslant c_i\]则对任意$\epsilon > 0$，有：
\[P(f(x_1,...,x_m)-\mathbb{E}(f(x_1,...,x_m)) \geqslant \epsilon) \leqslant \exp \left( \frac{-2\epsilon^2}{\sum_i c_i^2} \right) \tag{7}\] \[P(\lvert f(x_1,...,x_m)-\mathbb{E}(f(x_1,...,x_m)) \rvert \geqslant \epsilon) \leqslant 2 \exp \left( \frac{-2\epsilon^2}{\sum_i c_i^2} \right) \tag{8}\]