PRML学习笔记(七)

第七章 稀疏核机

Posted by Pelhans on November 9, 2018

PRML 和 ESL 的学习基本上是学十得一。稳扎稳打再来一次

稀疏核机

具有稀疏解的基于核的算法对新数据的预测只依赖于在训练数据点的一个子集上计算的核函数。最经典的莫过于SVM(支持向量机),但它不提供后验概率。另一种稀疏核方法被称为相关向量机(RVM),它是基于贝叶斯的方法,提供了后验概率的输出,并且通常能产生比 SVM 更稀疏的解。

7.1 最大边缘分类器

对于二分类问题,线性模型的形式为:

对应于支持向量机的结局方案是:引入边缘(margin)的概念,这个概念被定义为决策边界与任意样本之间的最小距离。原因是同参数$\sigma^{2}$的高斯核的Parsen密度估计对每个类别的输入向量x的分布进行建模,伴随着类别先验,这个分布定义了一个最优的分类错误率的决策边界。在极限$\sigma^{2} \rightarrow 0$的情况下,可以证明最优超平面是有着最大边缘的超平面。这个结果背后的直观含义是,随着$\sigma^{2}$的减小,距离超平面较近的点对超平面的控制能力逐渐大于距离较远的点。在极限情况下,超平面会变得与非支持向量的数据点无关。

最大边缘通过下式得到:

直接求解这个问题很复杂,我们要通过拉格朗日乘数法把它转化为一个更容易求解的等价问题。

首先我们注意到限制条件:

引入拉格朗日乘数$a_{n} \geq 0$,则得到拉格朗日函数:

现在我们要关于w和b的最小化,关于a的最大化,令 $L(w,b,a)$ 关于w和b的导数等于零,我们得到下面两个条件:

使用这两个条件从 $L(w, b, a)$ 中消去 w 和 b,就得到最大化边缘问题的对偶表示,其中我们要关于a的最大化:

限制条件为:

这里,核函数被定义为$k(x, x^{‘}) = \phi(x)^{T}\phi(x^{‘})$。这是一个二次规划问题,我们要在不等式条件下最优化一个a的二次函数。上式就是原问题的对偶问题,它使得模型能够用核函数重新表示,因此最大边缘分类器可以被高效地应用于位数超过数据点个数的特征空间,包括无穷维空间。

上述形式限制的最优化问题满足 Karush-Kuhn-Tucker(KKT) 条件,则下面三个性质要成立:

因此对于每个数据点,要么$a_{n} = 0$ ,要么$t_{n}y(x_{n})=1$,。任何使得$a_{n}=0$的数据点对新数据点的预测没有作用。剩下的数据点被称为支持向量,由于这些向量满足$t_{n}y(x_{n}) = 1 $, 因此它们对应于特征空间中位于最大边缘超平面内的点。这个性质是支持向量机在实际使用中的核心,一旦模型被训练完毕,相当多的数据点都可以被丢弃,只有支持向量被保留。

解决了二次规划的问题,找到了a的值以后,我们就可以确定阈值参数b:

其中$N_{S}$是支持向量的总数。

7.1.1 重叠类分布

到现在位置,我们都假设训练数据点在特征空间$\phi(x)$中是线性可分的,解得的支持向量机在原始输入控件中会对训练数据进行精确地划分。然而在实际中,类条件分布可能会有重叠,这种情况下对训练数据进行精确化粪会导致较差的泛化能力。

因此我们增加一个惩罚项,这个惩罚项随着与决策边界的距离的增大而增大。令这个惩罚项是距离的线性函数分析起来比较方便,因此我们引入松弛变量(slack variable)。每个训练数据点都有一个松弛变量,对于位于正确的边缘边界内部的点或者边界上的点,$\xi_{n} = 0$,对于其他点, $\xi_{n} = |t_{n} - y(x_{n})|$。因此,对于位于决策边界上的点$\xi_{n}=1$,并且通常能产生比$\xi_{n} > 1$ 就是被误分类的点。因此精确分类的限制条件就被替换为:

因此新的最小化目标为:

其中参数C>0控制了松弛变量惩罚与边缘之间的折中。在$C \rightarrow \infty $的行框虾,我们就回到了之前讨论过的用于线性可分数据的支持向量机。

结合上述限制条件,对应有拉格朗日函数:

其中a和$\mu$是拉格朗日乘数。对应的KKT条件为:

现在对w、b和${\xi_{n}}$进行最优化,得到对偶表示:

而后注意到:

这被称为盒限制。这又一次变成二次规划问题。解得b为:

其中M表示满足$0\lt a_{n} \lt C$的数据点的下标的集合。

虽然对新输入的预测只用过支持向量完成,但是在训练阶段(即确定参数a和b的阶段)使用了整个数据集,因此找到一个解决二次规划问题的规划算法很重要。一种最流行的训练SVM的方法被称为顺序最小优化(SMO),这种方法考虑了分块方法的极限情况,每次只考虑两个拉格朗日乘数。这种情况下,子问题可以解析的求解,因此避免了数值二次规划。

7.1.3 多类 SVM

对于多类SVM问题,一种常用的方法是构建K个独立的SVM,其中第k个模型$y_{k}(x)$在训练时,使用来自类别$C_{k}$的数据作为正例,使用来自剩余的K-1个类别的数据作为负例。这被称为”1对剩余”(onr-versus-the-rest)方法。是目前被应用最广泛的方法。

7.1.4 回归问题的 SVM

对于回归问题,我们最小化正则化的误差函数,形式为:

其中$E_{\epsilon}$是一个$\epsilon$不敏感的误差函数。与之前一样,我们通过引入松弛变量的方式,重新表达最优化的问题。

对于每个数据点$x_{n}$,我们现在需要两个松弛变量$\xi_{n} \geq 0$ 和 $\hat{\xi_{n}} \geq 0$,其中 $\xi_{n} \gt 0$ 对应于$t_{n} > y(x_{n}) + \epsilon$的数据点,$\hat{\xi_{n}} \gt 0$对应于 $t_{n} < y(x_{n}) - \epsilon$的数据点。则$\epsilon$位于管道内的条件为:

因此新的误差函数为:

限制条件为:

根据限制条件写出拉格朗日函数并对 $w, b, \xi_{n}, \hat{\xi_{n}} $求导为零,得到对应解。带入拉格朗日函数消除上述变量有:

分析KKT条件,得到盒限制:

因此:

对应的KKT条件为:

因此对预测有效的点是那些$a_{n}$和 $\hat{a}_{n}$不为零的点,因此得到了一个稀疏解。同时我们求得参数b:

7.2 相关向量机

前面说过 SVM 的输出是一个决策结果而不是后验概率,并且 SVM推广到多分类问题有很多问题。有一个复杂度参数 C或者$\nu$、$\epsilon$必须通过诸如交叉验证的方法确定,,预测使用核函数的线性组合表示对额,核函数以训练数据点为中心,并且必须是正定的。相关向量机(RVM)是一个用于回归问题和分类问题的贝叶斯稀疏核方法,它具有SVM的许多特征,同时避免了 SVM的主要局限性。此外,它通常会产生更加稀疏的模型,从而使得在测试集上的速度更快,同事保留了可比的泛化误差。

7.2.1 用于回归的 RVM

用于回归的相关向量机的形式是第三章讨论过的线性模型的额形式,但是先验概率有所不同,从而产生了稀疏解。和之前一样,我们有:

相关向量机是这个模型的一个具体实例,它师徒重现支持向量机的结构。特别地,基函数由核给出,训练集的每个数据点关联着一个核:

y(x)与 SVM 的预测模型具有相同的形式,唯一的差别是系数$a_{n}$被记做$w_{n}$。这里应该强调,后面的分析对于任意的基函数选择都成立。似然函数为:

重点来了,我们引入参数向量w上的先验分布,设为零均值的高斯先验。然而 RVM的关键区别在于我们为每个权参数 $w_{i}$ 都引入了一个单独的超参数$\alpha_{i}$,而不是一个共享的超参数。因此权值先验的形式为:

其中 $\alpha_{i}$ 表示对应参数 $w_{i}$的精度。当我们关于这些超参数最大化模型证据时,大部分都区域无穷,对应的权参数的后验概率分布集中在零附近。与这些参数关联的基函数于是对应于模型的预测没有作用,因此被高效的剪枝掉,从而生成了一个稀疏的模型

具体来说,$\alpha$ 和 $\beta$ 可以通过第二类最大似然法来确定(证据近似)。这种方法中,我们最大化边缘似然函数。边缘似然函数通过对权向量的积分得到:

我们现在的目标是关于超参数 $\alpha$ 和 $\beta$ 的最大化。我们可以通过令求解的边缘似然函数的导数等于零来求,也可以通过EM算法来求。

找到超参后,对于新的输入x,我们可以计算t上的预测分布:

7.2.3 RVM 用于分类

将 RVM推广到分类问题的方法是将权值的ARD先验应用于第四章研究过的概率线性分类模型上。首先,我们初始化超参数$\alpha$。对于给定的$\alpha$值,我们接下来对后验概率建立一个高斯近似,从而得到了对边缘似然的一个近似。这个近似后的边缘似然函数的最大化就引出了对$\alpha$值的重新估计,并且这个过程不断重复,直到收敛。