CS229 Lesson 11 贝叶斯统计正则化

课程视频地址：http://open.163.com/special/opencourse/machinelearning.html

课程主页：http://cs229.stanford.edu/

更具体的资料链接：https://www.jianshu.com/p/0a6ef31ff77a

笔记参考自中文翻译版：https://github.com/Kivy-CN/Stanford-CS-229-CN

这一讲介绍了贝叶斯统计和正则化。

3 贝叶斯统计和正则化

在这个部分中，我们将讨论另一个对抗过拟合的工具。

​ 在本章开始的时候，我们利用最大似然估计讨论参数拟合，利用如下方式选择参数：

$$\theta_{\text{ML}}=\arg\max_{\theta} \prod_{i=1}^m p(y^{(i)}|x^{(i)};\theta)$$

在随后的讨论中，我们将$\theta$视为一个未知的参数，这种将$\theta$看成恒定但是未知的值是频率学派的观点。而另一种进行参数估计的方法是使用贝叶斯的视角，将$\theta$视为一个未知的随机变量，在这种方法下，我们要给$\theta$一个先验分布$p(\theta)$，用来表达参数的先验信息。给定训练集$\{(x^{(i)},y^{(i)})\}_{i=1}^m​$，当我们需要对一个新的值进行预测的时候，我们可以计算参数的后验分布：

$$\begin{eqnarray*} p(\theta|S) &&=\frac{p(S|\theta)p(\theta)}{p(S)}\\ &&=\frac{( \prod_{i=1}^m p(y^{(i)}|x^{(i)},\theta))p(\theta)} {\int_{\theta}( \prod_{i=1}^m p(y^{(i)}|x^{(i)},\theta))p(\theta) d\theta} \tag 1 \end{eqnarray*}$$

上述等式中，$\prod_{i=1}^m p(y^{(i)}|x^{(i)},\theta)$来自你使用的机器学习模型。

​ 如果有一个新的测试样本$x$，然后要求我们对这个样本进行预测，我们可以用$\theta$的后验分布计算每个分类标签的后验分布：

$$\begin{eqnarray*} p(y|x,S) =\int_{\theta} p(y|x,\theta)p(\theta|S) d\theta \tag 2 \end{eqnarray*}$$

其中$ p(y|x,\theta)$可以利用之前的等式计算出来。因此，如果我们的目标是预测给定$x$，$y$的期望，那么我们将输出

$$\mathbb E[y|x,S] = \int_{y}y p(y|x,S) dy$$

​ 我们叙述的过程可以被认为是在做“完全贝叶斯”预测，其中我们的预测是根据后验分布$p(\theta| S)$计算均值得到的。不幸的是，这种后验分布的计算是非常困难的。这是因为它需要在等式（1）中对（通常是高维的）$θ$进行积分，这通常不能以闭合形式完成。

​ 因此，在实际中我们常用点估计代替$p(y|x,S)$。$\theta$的最大后验估计由如下公式给出：

$$\begin{eqnarray*} \theta_{\text{MAP}}=\arg\max_{\theta} \prod_{i=1}^m p(y^{(i)}|x^{(i)},\theta)p(\theta) \tag 3 \end{eqnarray*}$$

注意到这个公式和最大似然估计的公式基本相同，除了最后增加了先验分布$p(\theta)$。

​ 在实际中，$\theta$先验分布的常见选择是假设$\theta\sim \mathcal N(0,\tau^2 I)$。使用这样的先验分布，拟合出来的参数$\theta_{\text{MAP}}$的范数将比用极大似然估计得到的参数$\theta_{\text{ML}}$小。在实际中，这使得贝叶斯最大后验估计相比于最大似然估计更容易避免过拟合。

4.感知机和大型边界分类器

在学习理论的最后一部分，我们将介绍一种不同的机器学习模型。在之前的内容中，我们考虑的都是批量学习，即给我们训练集去学习，然后在测试集上评估假设$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$没有明确地关系。

定理(Block, 1962, and Novikoff, 1962)

设有一个样本序列$(x^{(1)}, y^{(1)}),(x^{(2)}, y^{(2)})…(x^{(m)}, y^{(m)})$，假设对每个$i$都有$||x^{(i)}|| \le D$，此外存在单位长度的向量$u(||u||_2 =1)$使得对序列中每个样本都有$y^{(i)}.(u^T x^{(i)}) \ge \gamma$，（例如，$u^Tx^{(i)} \ge \gamma$，如果$y^{(i)}=1$，并且$u^Tx^{(i)} \le -\gamma$，如果$y^{(i)}=-1$，因此$u$以至少$\gamma$的距离分开样本数据）。那么感知机算法在序列上给出错误总数最多是$(D/\gamma)^2$

证明：感知机只在犯错误的样本上更新权重。令$\theta^{(k)}$为犯第$k$个错误的时候的权重。则$\theta^{(1)}=\vec 0$（因为权重被初始化为$0$），并且如果第$k$个错误发生在样本$(x^{(i)}, y^{(i)})$上，那么$g((x^{(i)})^T \theta^{(k)})\neq 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)})^Tu \\ &\ge (\theta^{(k)})^Tu + \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)})^Tx^{(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||.||u||\cos \theta \le ||z||.||u||$，其中$\theta$是$z$和$u$的夹角）。上述结果表明

$$k\le (D/\gamma)^2$$

因此，如果感知机犯了第$k$个错误，那么$k\le (D/\gamma)^2$。