贝叶斯统计和正则化
在这个部分中，我们将讨论另一个对抗过拟合的工具。
在本章开始的时候，我们利用最大似然估计讨论参数拟合，利用如下方式选择参数：
$$ \theta_{\mathrm{ML}} = \arg\max_{\theta} \prod_{i=1}^{m} p(y^{(i)} \mid x^{(i)}; \theta) $$在随后的讨论中，我们将 $\theta$ 视为一个未知的参数，这种将 $\theta$ 看成恒定但是未知的值是频率学派的观点。而另一种进行参数估计的方法是使用贝叶斯的视角，将 $\theta$ 视为一个未知的随机变量，在这种方法下，我们要给 $\theta$ 一个先验分布 $p(\theta)$，用来表达该参数的先验信息。给定训练集 ${(x^{(i)}, y^{(i)})}_{i=1}^{m}$，当我们需要对一个新的值进行预测的时候，我们可以计算参数的后验分布：
$$ p(\theta \mid S)= \frac{p(S \mid \theta)p(\theta)}{p(S)}= \frac{\left(\prod_{i=1}^{m} p(y^{(i)} \mid x^{(i)}, \theta)\right)p(\theta)} {\int_{\theta}\left(\prod_{i=1}^{m} p(y^{(i)} \mid x^{(i)}, \theta)\right)p(\theta)\, d\theta} \tag{1} $$上述等式中，$\prod_{i=1}^{m} p(y^{(i)} \mid x^{(i)}, \theta)$ 来自你使用的机器学习模型。
如果有一个新的测试样本 $x$，然后要求我们对这个样本进行预测，我们可以用 $\theta$ 的后验分布计算每个分类标签的后验分布：
$$ p(y \mid x, S) = \int_{\theta} p(y \mid x, \theta)\, p(\theta \mid S)\, d\theta \tag{2} $$其中 $p(y \mid x, \theta)$ 可以利用之前的等式计算出来。因此，如果我们的目标是预测给定 $x$，$y$ 的期望，那么我们将输出
$$ \mathbb{E}[y \mid x, S] = \int_y y p(y \mid x, S)\, dy $$我们叙述的过程可以被认为是在做“完全贝叶斯”预测，其中我们的预测是根据后验分布 $p(\theta \mid S)$ 计算均值得到的。不幸的是，这种后验分布的计算是非常困难的。这是因为需要在等式（1）中对（通常是高维的）$\theta$ 进行积分，通常不能以闭合形式完成。
因此，在实际中我们常用点估计代替 $p(y \mid x, S)$。$\theta$ 的最大后验估计由下公式给出：
$$ \theta_{\mathrm{MAP}} = \arg\max_{\theta} \prod_{i=1}^{m} p(y^{(i)} \mid x^{(i)}, \theta)\, p(\theta) \tag{3} $$注意到这个公式和最大似然估计的公式基本相同，除了最后增加了先验分布 $p(\theta)$。
在实际中，$\theta$ 先验分布的常见选择是假设 $\theta \sim \mathcal{N}(0, \tau^2 I)$。使用这样的先验分布，拟合出来的参数 $\theta_{\mathrm{MAP}}$ 的范数将比用极大似然估计得到的参数 $\theta_{\mathrm{ML}}$ 小。在实际中，这使得贝叶斯最大后验估计相比较于最大似然估计更容易避免过拟合。
感知机和大型边界分类器
在学习理论的最后一部分，我们将介绍一种不同的机器学习模型。在之前的内容中，我们考虑的都是批量学习，即给我们训练集去学习，然后在测试集上评估假设 $h$。在这一部分中，我们将考虑在线学习，这种算法会在学习的过程中给出预测。
回顾感知机算法，参数为 $\theta \in \mathbb{R}^{n+1}$，根据如下公式预测
$$ h_{\theta}(x) = g(\theta^T x) \tag{1} $$其中
$$ g(z)= \begin{cases}1, & \text{if } z \ge 0 \\-1, & \text{if } z < 0 \end{cases} $$给定一个训练样本 $(x,y)$，感知机学习法则根据如下规则更新参数。如果 $h_{\theta}(x)=y$，那么不更新参数。否则，按如下方式更新参数
$$ \theta := \theta + yx $$这里 $y \in {+1,-1}$。
下面一个定理给出感知机算法的误差上界，注意这个上界和样本序列个数 $m$ 以及数据维度 $n$ 没有明确地关系。
定理
设有一个样本序列 $(x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}) \ldots (x^{(m)}, y^{(m)})$，假设对每个 $i$ 都有 $|x^{(i)}| \le D$，此外存在单位长度的向量 $u$（$|u|_2 = 1$）使得对序列中每个样本都有 $y^{(i)} \cdot (u^T x^{(i)}) \ge \gamma$，（例如，$u^T x^{(i)} \ge \gamma$，如果 $y^{(i)}=1$，并且 $u^T x^{(i)} \le -\gamma$，如果 $y^{(i)}=-1$，因此以至少 $\gamma$ 的距离分开样本数据）。那么感知机算法在序列上给出错误总数最多是 $(D/\gamma)^2$。
证明：感知机只在犯错误的样本上更新权重。令 $\theta^{(k)}$ 为犯第 $k$ 个错误时候的权重。则 $\theta^{(1)}=\vec{0}$（因为权重被初始化为 0），并且如果第 $k$ 个错误发生在样本 $(x^{(i)}, y^{(i)})$ 上，那么 $g((x^{(i)})^T \theta^{(k)}) \ne y^{(i)}$，这意味着
$$ (x^{(i)})^T \theta^{(k)} y^{(i)} \le 0 \tag{2} $$另外根据感知机的学习法则，我们有 $\theta^{(k+1)} = \theta^{(k)} + y^{(i)}x^{(i)}$，所以
$$ \begin{aligned} (\theta^{(k+1)})^T u&= (\theta^{(k)})^T u + y^{(i)}(x^{(i)})^T u \\&\ge (\theta^{(k)})^T u + \gamma \end{aligned} $$利用归纳法可得
$$ (\theta^{(k+1)})^T u \ge k\gamma \tag{3} $$另外，我们有
$$ \begin{aligned} \|\theta^{(k+1)}\|^2&= \|\theta^{(k)} + y^{(i)}x^{(i)}\|^2 \\&= \|\theta^{(k)}\|^2 + \|x^{(i)}\|^2 + 2y^{(i)}(x^{(i)})^T \theta^{(k)} \\&\le \|\theta^{(k)}\|^2 + \|x^{(i)}\|^2 \\&\le \|\theta^{(k)}\|^2 + D^2 \end{aligned} \tag{4} $$其中第一个不等号是因为公式（2），利用归纳法可得
$$ \|\theta^{(k+1)}\|^2 \le kD^2 \tag{5} $$结合（3）和（4）可得
$$ \begin{aligned} \sqrt{k}D&\ge \|\theta^{(k+1)}\| \\&\ge (\theta^{(k+1)})^T u \\&\ge k\gamma \end{aligned} $$第二个不等号是因为 $u$ 是单位向量（并且 $z^T u = |z| \cdot |u| \cos \theta \le |z| \cdot |u|$，其中 $\theta$ 是 $z$ 和 $u$ 的夹角）。上述结果表明
$$ k \le (D/\gamma)^2 $$因此，如果感知机犯了第 $k$ 个错误，那么必有 $k \le (D/\gamma)^2$。