网易《机器学习》第11课--学习理论03

网易机器学习 机器学习理论

---

回顾我们一开始学习的线性回归当中，我们求解具体参数的时候使用的是极大似然估计(MLE)方法，即：

$$\begin{equation} \theta_{MLE} = \operatorname*{argmax}_{\theta} \prod_{i=1}^m P(y^{(i)} | x^{(i)};\theta) \end{equation}$$
在上式中，我们认为$\theta$是一个固定的未知值或向量，通过极大似然估计可以得到$\theta$的值。这是频率学派的观点，该学派认为参数是固定的，使用统计学习方法可以估计出这些值。
在统计学中，还有另一个学派：贝叶斯学派。与频率学派的观点不同，该学派认为参数$\theta$是一个随机变量，服从某一先验分布，即$\theta \sim P(\theta)$。其中$P(\theta)$表示先验概率。

假设训练集为$S = \{x^{(i)},y^{(i)}\},i=1,...,m$。后验概率的求解方法如下：

$$\begin{equation} 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 (\prod_{i=1}^m P(y^{(i)} | x^{(i)},\theta))P(\theta) d\theta} \end{equation}$$
注意到公式（2）与公式（1）中条件概率的差别，公式（2）中$P(y^{(i)} | x^{(i)},\theta)$中$x^{(i)}$与$\theta$逗号相隔，表示$\theta$是随机变量；公式（1）中$P(y^{(i)} | x^{(i)}；\theta)$中$x^{(i)}$与$\theta$分号相隔，表示$\theta$为固定值。

在公式（2）中，$P(y^{(i)} | x^{(i)},\theta)$的表达式形式取决于问题所用的模型。比如，你使用贝叶斯Logistic回归模型，则$P(y^{(i)} | x^{(i)},\theta) = h_{\theta}(x^{(i)})^{y^{(i)}}(1-h_{\theta}(x^{(i)}))^{1-y^{(i)}}$，其中$h_{\theta}(x^{(i)}) = \frac{1}{1 + exp(-\theta^Tx^{(i)})}$。

在对新样本$x_{new}$进行预测时，使用如下公式计算各个$y$值的概率：

$$\begin{equation} P(y|x_{new},S) = \int P(y|x_{new},\theta)P(\theta|S)d\theta \end{equation}$$
由（3）式可知，每个$y$值对应的概率都可求得，那么可求得期望（最终预测函数）为：
$$\begin{equation} E[y|x_{new},S] = \int yP(y|x_{new},S) dy \end{equation}$$
但是，利用公式（3）（4）的方法求解时，由于$\theta$的积分使得计算量变得很大，当$\theta$是高维向量时，往往是一个NP难问题。所以在实际应用中，往往通过最大化后验概率得到参数$\theta$的估计值，然后将$\theta$代入到模型中直接预测。该方法称为极大后验概率（Maximum A Posteriori，MAP）方法，计算公式如下：
$$\begin{equation} \theta_{MAP} = \operatorname*{argmax}_{\theta} \prod_{i=1}^m P(y^{(i)} | x^{(i)}，\theta)P(\theta) \end{equation}$$
比较$\theta_{MLE}$和$\theta_{MAP}$，可知道差别仅仅在于$\theta_{MAP}$末尾添加了先验概率$P(\theta)$而已。

在实际应用中，普遍选择正态分布作为$\theta$的先验概率，即$\theta \sim \mathcal{N}(0,\tau^2I)$。实践表明，采用MAP方法得到的参数比使用MLE方法得到的参数更加不容易过拟合，即降低了过拟合的概率。
在之前的笔记中，已经分析了在线性回归模型中平方Loss与极大似然估计MLE的关系，那么MAP方法与此相对应的Loss函数该如何解释呢？

$$\begin{equation} min \sum_{i=1}\|y^{(i)} - \theta^Tx^{(i)}\|^2~~~(MLE)\\ min \sum_{i=1}\|y^{(i)} - \theta^Tx^{(i)}\|^2+\tau\|\theta\|^2~~~(MAP) \end{equation}$$
我们看到MAP方法需要优化的Loss函数目标和MLE相比多了一个$\tau\|\theta\|^2$。$\tau\|\theta\|^2$被称为正则项。正则项在很多地方使用，如改进SVM算法中的惩罚项。

在线学习

之前学的算法都是批处理算法，即在训练集上得到模型后，再去对测试集或者训练集本身进行评测，得到训练误差或测试误差。而在线学习并不是这样，而是首先有一个初始的分类器，当第一个样本到来时，对该样本进行预测，得到预测结果，然后利用该样本的信息对分类器进行更新；然后第二个样本到来时做同样的操作，以此类推。这样，我们就对m个样本都有一个预测值，只不过它们都是在训练过程中得到的。对这些预测值进行统计，就得到了在线训练误差。这就是过程上在线学习和批处理学习的不同之处。

对于感知器算法来说，如果正负样本线性可分，那么其在线学习算法也是收敛的。

感知器在线学习收敛性证明

为证明方便，我们使用标签$y \in \{-1,1\}$，其假设函数为：

$$h_{\theta}(x) = g(\theta^Tx) = \left\{ \begin{array}{l} 1, ~~~\theta^Tx \geq 0 \\ -1, \theta^Tx \leq 0 \end{array}\right.$$
感知器算法参数更新法则：当一个新样本$(x,y)$到来时，若$h_{\theta}(x) = y$，则参数不变，否则更新法则为：$\theta := \theta+yx$。

下面证明感知器算法在线学习收敛（在正负样本线性可分的条件下）。
首先，解释何为正负样本线性可分。设样本用$\{x^{(i)},y^{(i)}\},i=1,...,m$ 来表示，假设对所有先行样本，均有二范数$\|x^{(i)}\|_2 \leq D$。线性可分的意义即为存在一个单位向量$u(\|u\|=1)$，对所有样本，均存在如下公式：

$$y^{(i)}·(u^Tx^{(i)}) \geq \gamma$$
上式的解析为：当$y^{(i)}=1,(u^Tx^{(i)}) \geq \gamma$；当$y^{(i)}=-1,(u^Tx^{(i)}) \leq -\gamma$；因此，单位向量$u$至少以间隔$\gamma$将正负样本分离。

在这样的前提下，可证明如下收敛定理：

$$感知器算法在该正负样本线性可分的样本集上被错分的样本数k \leq (D/\gamma)^2$$
证：感知器算法只有在错误分类时才会更新参数，令$\theta^{(1)}=\vec 0$，令$\theta^{(k)}$表示第$k$此错分时的参数，假设第$k$次错分发生在样本$(x^{(i)},y^{(i)})$上，则有 $g((x^{(i)})^T\theta^{(k)}) \neq y^{(i)}$，意味着：
$$(x^{(i)})^T\theta^{(k)}·y^{(i)} \leq 0$$
另外，由$\theta^{(k+1)} = \theta^{(k)}+y^{(i)}x^{(i)}$，有：
$$(\theta^{(k+1)})^T u = (\theta^{(k)})^T u + y^{(i)}(x^{(i)})^T u \geq (\theta^{(k)})^T u + \gamma$$
根据递推法则，可得：
$$(\theta^{(k+1)})^T u \geq k \gamma$$
类似的，我们可得到：
$$\|\theta^{(k+1)}\|^2 = \|\theta^{(k)}+y^{(i)}x^{(i)}\|^2=\|\theta^{(k)}\|^2 +\|x^{(i)}\|^2 +2y^{(i)}(x^{(i)})^T \theta^{(k)}\\ \leq \|\theta^{(k)}\|^2 +\|x^{(i)}\|^2 \leq\|\theta^{(k)}\|^2 +D^2$$
也由递推法则可得：
$$\|\theta^{(k+1)}\|^2 \leq kD^2$$
将上面得到的两个式子放在一起，有：
$$\sqrt{k}D \geq \|\theta^{(k+1)}\| \geq (\theta^{(k+1)})^Tu \geq k\gamma$$
第二个不等式来自于基本事实：$u$是单位向量（$z^Tu = \|z\|\|u\|cos\phi \leq \|z\|\|u\|$,其中$\phi$是$u、z$之间的夹角）。
因此，可得：
$$k \leq (D/\gamma)^2$$
得证。

机器学习算法应用建议

机器学习中有很多算法，那么在实际问题中该如何使用这些算法呢？同样的算法对同一个问题，不同的人做出的结果可能截然相反的。当算法遇到瓶颈时该朝什么样的方向来对算法加以改进？相应的建议就是为了解决这一类问题。这些建议是针对实际应用机器学习算法应用到实际问题上的，对研究新的算法并没有太大帮助。
该部分分为三个主要内容：

• 调试ML算法时如何进行诊断？
• 误差分析和销蚀分析。
• 如何在一个ML问题上开始研究？

在对具体的内容分析之前，先介绍一个很有用的建议：避免过早优化。
在我们进行项目开发或课题研究时，往往会遇到一些问题，在没有弄清楚问题之前，即没有明确的证据说明问题确实出自某个原因之前，我们往往想当然的认为对自己认为出问题的地方进行改进或优化，运气好时能够解决问题，运气不好时则会浪费大量时间。此外，在项目开发时，过早的优化代码段（虽然代码段并不是瓶颈）。虽然该段代码被优化得很快，但对系统性能的提高的作用确实微乎其微，可以说是浪费了时间。而对研究来说，过早地去做一些不能解决问题的事情，浪费的时间可能会更多。因此我们必须找到能够判断问题关键所在的办法，这就引出了一下内容：

ML算法诊断

设想垃圾邮件过滤问题，目前的研究现状如下：
——>在5000个特征中选择了100个特征；
——>使用贝叶斯Logistic回归模型算法，用态度下降优化目标函数；
——>目前的误差率为20%。
显然，20%的误差率难以接受，那么可能的解决办法如下：

1. 更多的数据：数据量变多往往有助于模型变好；
2. 更少的特征；
3. 更多的特征；
4. 选择更好的特征；
5. 梯度下降法多迭代几次：解决算法没有收敛的问题；
6. 尝试牛顿方法：牛顿方法更容易收敛；
7. 调整目标函数中$\gamma$的值；
8. 使用SVM算法（一般不建议随意更换算法）；

可能的办法数以百计，但我们暂时只列出这么多吧。对于上述8种改进方法，如果一一尝试的话会非常耗时。比如，第1种收集更多数据会达到好效果（通常是这样），但是对于某些实际应用来说，收集数据是非常耗时的事情。盲目行动的效果并不好

面对以上8种方法，我们如何选择呢？拼rp?当然不是。如果我们能够找到几种标准，排除上面的绝大多数，只留下一两种，那么成功的概率会高很多。

方差/偏差分析
第一个标准就是判断问题是出在高偏差还是高方差上。一般说来，高方差针对的是过拟合问题，即训练误差很小但生成误差很大。而高偏差针对的是模型本身不合适的情况，如特征数目过少等问题，表现即是训练误差和生成误差都很大。

由左上图可看到，在高偏差下，训练误差和生成误差都会大于预期的性能。这个时候，增加样本的数目是不可能解决问题的，可以看到Test Error和Train Error到最后已不再随着样本数m的增大而变化。
由右上图可以看到，在高方差下，可以比较训练误差和测试误差，如果它们之间相差很大，那么通过增加样本数目使得系统的过拟合程度减小，提高性能。（看Test Error和Train Error的差距来判断高方差or高偏差）

根据上面的分析，我们就可以对8条办法的前四条进行分类了：更多的数据、更少的特征解决的是高方差的问题；更多的特征和更好的特征可以增加模型的复杂度，提高模型在数据中的拟合程度，因而对应解决高偏差问题。

是否收敛于目标函数是否正确的判断
考虑下面的情景，仍然是针对垃圾邮件分类问题：
——>使用贝叶斯Logistic回归模型(BLR)可以达到正常邮件上2%的错误率，垃圾邮件上2%的错误率；
——>使用SVM模型可以达到正常邮件上0.01%的错误率，垃圾邮件上10%的错误率；

对于BLR来说，正常邮件上2%的错误率是不能容忍的，因为一般人一般情况下不愿意错过朋友发来的邮件或重要邮件。显然，此时SVM比BLR要好。
此时我们会有两个可能的分析：
a.贝叶斯Logistic回归模型是否收敛？
b.贝叶斯Logistic回归模型的目标函数是否选对？

这两者情况都有可能造成结果中SVM由于BLR。即如果BLR没有收敛，而SVM收敛，那么SVM效果更好；如果模型的目标函数没有找对，那么在当前的目标函数上，BLR可能逊于SVM，但BLR在正确的目标函数上却能达到更好的效果，这也是有可能的。

对于上面SVM优于BLR的问题，我们根据实际情况找到实际的需要优化的函数：

$$\alpha(\theta) = \frac{1}{m}\sum_{i=1}^m w^{(i)} \mathbf{1}(y^{(i)} =h_{\theta}(x^{(i)}))$$
加入$w^{(i)}$的原因：通过对正常样本和垃圾样本的错误的惩罚进行加权，我们可以更好地将目标锁定在提高垃圾邮件识别率的同时更好地保护正常邮件不被错判。
根据假设可知：$\alpha(\theta_{SVM}) > \alpha(\theta_{BLR})$。
现在，我们可以判断在BLR的目标函数（即似然函数$J$）上$\theta_{SVM}$与$\theta_{BLR}$的表现，来判断到底发生了了什么问题。可能的情形如下：
(1) $\alpha(\theta_{SVM}) > \alpha(\theta_{BLR})$ 、 $J(\theta_{SVM}) > J(\theta_{BLR})$
这就表明BLR的算法收敛程度还不够，还需要继续迭代。原因是这样：参数$\theta_{BLR}$的目标就是为了让$J(\theta)$实现最大化，但现在$J(\theta_{SVM}) > J(\theta_{BLR})$则表明$\theta_{BLR}$并没有实现最大化。

(1) $\alpha(\theta_{SVM}) > \alpha(\theta_{BLR})$ 、 $J(\theta_{SVM}) < J(\theta_{BLR})$
这就表明BLR的目标函数有待改进，选得不够好。原因是这样：一个不能使得$J(\theta)$实现最大化的参数$J(\theta_{SVM})$取得的效果竟然好过使得使得$J(\theta)$最大的那个$\theta_{BLR}$，那就肯定出问题了。表明$J(\theta)$的形式需要改变。

因此，我们就可以对8种解决方案中的后4种做出分类了。算法迭代次数增加与尝试牛顿方法是为了收敛性更好。调整$\gamma$与使用SVM则是改进了目标函数。

如何开始ML问题的解决

在ML上开始研究一般有两种做法：
第一种是仔细构造法。对问题进行深入的分析，提取正确的特征，收集需要的数据，设计正确的算法结构，这样往往能够一次就得到较好的具有可拓展性的算法。
第二种是创建-修改法。这种做法一般是先创建一个较差的系统，然后利用上面的诊断法对系统进行修改，从而得到较好的系统。这种做法比较广泛应用，因为互联网上的成功产品，往往不是最好的，而是最早的。

如果在ML上开始做解决方案的话，一个较好的建议是先对数据进行分析，比如为什么数据中的这些属性值是负的。当找出数据中的规律或者数据中的错误的时候，往往会发现系统性能差不是需要更复杂的算法，而是更加强大的预处理。
在做研究的过程中，要把注意力集中在关键问题上，不要轻易的相信某些结论对算法有用而花大量的时间在那些理论上。Ng谈到自己的经验时，说道花在设计、诊断上的时间通常都很有价值；一般来说，三分之一或者一般的时间花在诊断和设计上都是可以接受的。