采用置信度加权学习的相关向量机分类算法

许庆晗, 金立左, 费树岷

(东南大学 自动化学院，江苏 南京，210096)

摘 要：

VM)是一种通过贝叶斯推断在核空间建立稀疏线性模型的机器学习方法。在求解分类问题时，为了避免不可分或误标记训练样本对RVM分类精度的影响，提出一种训练方法。在训练得到RVM模型后，用置信度加权(Confidence weighted)算法重新对权值进行学习。CW算法通过计算当前样本对已有模型的置信度，判断是否用当前样本更新权值。利用这一特性在训练时只挑选部分训练集用于训练。结果表明：本算法保持了RVM的稀疏性，其分类能力比标准RVM的有所提高。

关键词：

相关向量机；在线学习；置信度加权算法；

中图分类号：  TP319          文献标志码：A         文章编号：1672-7207(2011)S1-0600-05

Relevance vector machine classification method with confidence-weighted learning

XU Qing-han, JIN Li-zuo, FEI Shu-min

(School of Automation, Southeast University, Nanjing 210096, China)

Abstact: Relevance vector machine(RVM) is a machine learning algorithm in order to find sparse linear model in kernel space via bayessian method. To improve the accuracy of classification, an apdative RVM+CW method using online linear classifier was proposed. After training a RVM model, a confidence-weighted(CW) classifier was trained with training set in the kernel space defined by learned relevance vectors. In this method only part of the training samples is used. The results demonstrate the improvement on classification capability and the same sparsity as RVM.

Key words: relevance vetor machine; online learning; confidence-weighted learning

在机器学习领域，以支持向量机(SVM)为代表的核方法具有重要影响^[1]，近年来，另一种基于稀疏贝叶斯学习的核方法——相关向量机(RVM)^[2]因其稀疏性日益为人所重视。RVM通过核函数将样本集变换至核空间，随后通过求解最大后验概率(Maximum a posteriori, MAP)得到核空间(Kernel space)线性模型。为了改进RVM，多数研究者关注于改进“特征提取”部分，即核函数的选择与参数学习问题：如多核学习(Multiple kernel learning)如自适应RVM^[3]等。这些方法通过学习得到对分类更有效的核函数，但计算量增长也十分可观。而RVM中权值和超参数的求取主要是Tipping等^[4-5]给出的2种求解最大后验概率的方法重新进行学习：第1种用Hessian阵的二阶技术^[4]，第2种利用变分贝叶斯法，通过EM算法迭代求解^[5]。根据文献[5]中的结果，2种不同方法得到的RVM性能几乎没有差别，只是变分贝叶斯法计算量稍大。

本文作者希望在训练时能采用某种方法，降低混叠样本的影响，进而提高分类性能。因为在实际使用RVM时发现，对于分类问题，在存在混叠、不可分的数据集上，各次交叉验证时的分类误差、相关向量RV数量均有较大差别。这暗示某些“误标记”或混叠的训练样本的出现可能影响了学习效果。因此，本文作者提出一种训练方法：在RVM训练结束后保持相关向量(Relevance vector, RV)不变，但在训练集上采CW (Confidence-weighted)在线学习算法^[6]对每个相关向量对应的权值重新进行学习。CW算法是一种在线线性分类算法，已成功应用于自然语言理解、URL欺骗分析等大规模、高维的机器学习问题^[7]。CW算法特点是对与当前模型有明显差异的样本十分敏感，利用这一特性，可以避免用导致分类能力下降的样本对模型进行更新。实验表明，该RVM+CW算法在基准数据集上的分类能力比标准RVM有了一定提高。

1  RVM与CW的权值求解比较

1.1  RVM中的权值求解

在求解线性表示时为了得到稀疏解，通常采用求解时加入(L1范数)约束的方法，如著名的LASSO。但RVM没有采用这一思路，而是采用贝叶斯推断的方式。通过假设概率模型获得稀疏性。

首先，对权值w的每一维假设其服从正态分布：

             (1)

随后，假设α服从gamma分布：

             (2)

对α_m假设gamma分布的目的是为了使权值w_m的边缘分布服从t分布：

         (3)

由概率论知识可知，此时。t分布比正态分布在均值处有更大的概率密度，而RVM中w的均值假定为0，因此导致最终求解得的权值中大多数的w_m趋于0。相比于基于正态分布假设的最小二乘解，w显著稀疏。而通过改变超参数a, b改变权值的分布，可以控制稀疏程度。

随后，RVM通过后验概率建立类标记与权值之间的联系：

  (4)

式中：C为常数；t为数据集类标记，；为预测结果，A为与权值元同阶的对角阵，对角元值为α_m。

最后采用二阶技术近似求解w的极大似然估计。相应的梯度向量和Hessian阵为

      (5)

       (6)

式中：B是N×N对角阵，对角元，。解得：

,     (7)

从数值计算的角度，Hessian阵为在目标函数的极值点附近的二阶逼近，而从贝叶斯推断的角度看式(5)~(7)，可以看作是在极大似然估计极值点w*处用一个高斯分布N(w*, ) 对似然函数的近似。此法优点是计算简便，但当真实分布非高斯、在极值点w*处非对称时，求解得到的近似分布只在极值点附近较准确，而其余位置误差较大。图2(b)给出了基准数据集(Banana)上求解出的相关向量构成的核空间中的样本分布情况，可以明显看出呈现非对称、非高斯特性。这种情况下，理论上采用变分贝叶斯方法可取得更好效果。变分贝叶斯法通过分布分解(Factorized distribution)用参数模型(通常为指数族分布)，对高斯分布中的w和参数假设服从含有超参数的共轭先验密度，并用期望最大化(EM)算法求解参数。但实际使用时，通常很难得到先验知识，因此，通常只使用无信息先验(Noninformation prior)，这种情况下，对分类问题的性能改进不大^[5]。

1.2  CW算法的权值求解

CW算法同样假设权值w服从高斯分布N(μ, ) ，用表示每个权值w_m的置信度。优化的目标函数为权值的真实分布N(μ, )与第t个训练样本到达时的分布N(μ_t, ) 之间的kullback-Leibler分解：

使：                (8)

为标准正态分布的累积分布函数。式(8)为把输出标准化到标准正态分布，当发生误分类或虽然正确分类，但输出幅值低于置信度水平η时，更新模型。更新方式如下：

          (9)

式中：α_t，f，μ_t在文献[8]中定义。CW算法对方差较大的特征，更显著地更新其权值，且通过引入置信度门限η使得当x_t能够以概率η被正确分类的时候，尽量少地更新模型。

2  RVM+CW算法

比较式(7)和(9)，可以得到RVM与CW最终求解出的权值w均为一个多元高斯分布，且在训练时都通过一组参数控制权值w每一维w_m的更新：RVM中为超参数α和先验概率p(α) ；而CW算法中扮演这一角色的是置信度和门限η。CW算法除了计算简便外，对与模型有明显差异的样本十分敏感，当这样的样本到来后，将显著更新模型。因此希望利用CW算法这一特性，识别出那些导致模型分类能力变差样本并拒绝更新，从而提高分类能力。

本文作者提出一种简便的RVM+CW算法。首先训练经典的RVM，随后在特征空间用CW对权值w重新进行在线学习。为了避免那些“混叠”样本对训练的干扰，训练时保存每个训练样本到达后更新的权值μ_t，_t和相应的训练误差e_t，最终输出e_t最小的权值。具体流程见算法1。

在核空间使用CW算法进行为在线学习过程中，随着训练样本到达，在训练集上将误差波动情况进行分类，最终输出的是具有最小训练误差的模型，图1所示为训练结果。由图1可知，只使用了约一半的样本。

表1   RVM+CW算法

Table 1  RVM+CW algorithm

图1 在核空间使用CW算法进行在线学习的训练结果(图卷标出最小训练误差(UCI banana数据集))

Fig.1 Online learning results in kernel space using CW (Minimum of training error (UCI banana dataset) is denoted with circle)

3  结果与分析

通过实验比较该RVM+CW算法与标准RVM以及SVM的分类能力。RVM和SVM均采用高斯核。RVM采用Tipping提供的matlab代码；SVM采用LIBSVM，参数C的值和核宽度σ采用对数尺度上的线性搜索。实验数据集来自UCI数据库，数据集描述见表2。

表2  实验用基准数据集

Table 2  Benchmark datasets used in experiments

图2所示为在Banana数据集上标准RVM与该RVM+CW的分类对比。当σ=0.85时，RVM+CW的误分率10.33%，而标准RVM的误分率是11.37%。表2所列为经过5折交叉验证的分类结果。在分类精度上RVM+CW在大多数数据集上比RVM有一定提高。虽然其分类精度仍比SVM的略低，但在模型稀疏性上， RVM及RVM+CW的RV的数量明显更少，而SVM的SV数量与训练样本数N成近似线性关系。

图2 核宽度σ=0.85时Banana数据集分类结果对比

Fig.2  Comparison results on banana dataset at gaussian basis width σ=0.85

实验发现本算法的一个不足之处是对核函数选取比标准RVM更加敏感。以Banana数据集为例，当将核宽度从σ=0.85改变为σ=2.5(见图3)后，标准RVM的误分率只从11.37%升高到12.33%，而本算法的误分率则从10.33%升高到38.10%，分类失败。这意味着训练RVM+CW时需要比标准RVM花费更多时间选择核函数，如何改善这一问题是将来的改进方向。

表3  分类结果对比

Table 3  Comparison of classification results

图3  RVM+CW分类失败(Banana数据集,核宽度σ=2.5)

Fig.3 Failure case of RVM+CW(Banana dataset, Gaussian basis width σ=2.5).

4  结论

通常训练样本越多，得到的模型泛化能力越强。但如果引入混叠严重的数据或误标记数据，则会影响模型的泛化能力。本文提出利用CW算法对RVM权值重新进行在线学习，避免了混叠样本对训练过程的干扰，在保持RVM稀疏性的前提下提高了分类能力，且由于在线学习算法的简便性，没有明显增加计算量。

参考文献：

[1] Bishop C M. Pattern recognition and machine learning [M]. New York: Springer, 2006: 325-344.

[2] Tipping M E. Sparse bayesian learning and the relevance vector machine [J]. Journal of Machine Learning Research, 2001, 1: 211-244.

[3] Tzikas D, Likas A, Galatsanos N. Sparse bayesian modeling with adaptive kernel learning [J]. IEEE Transactions on Neural Networks, 2009, 20(6): 926-937.

[4] Tipping M E., Faul A. Fast marginal likelihood maximisation for sparse bayesian models [C]//Proceedings of the Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics, Key West, FL, F, 2003: 3-6.

[5] Bishop C M, Tipping M E. Variational relevance vector machines [C]//Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann Publishers Inc, 2000: 46-53.

[6] Dredze M, Crammer K, Pereira F. Confidence-weighted linear classification [C]//Proceedings of the Proceedings of the 25th Annual International Conference on Machine Learning (ICML 2008), Helsinki, Finland: ACM, 2008: 264-271.

[7] Ma J, Saul L K, Savage S, et al. Identifying suspicious URLs: An application of large-scale online learning [C]//Proceedings of the Proceedings of the 26th International Conference on Machine Learning, Montreal: ACM, 2009: 681-688.

[8] Crammer K, Dredze M, Pereira F. Exact convex confidence-weighted learning [C]//Proceedings of the Advances in Neural Information Processing Systems, 21(NIPS 21). Vanconver BC, Canada: MIT Press, 2009: 345-352.

(编辑 龙怀中)

收稿日期：2011-04-15；修回日期：2011-06-15

通信作者：金立左(1972-)，男，江苏盐城人，博士, 副教授，从事机器视觉研究；电话：025-83795152；E-mail：jinlizuo@gmail.com

摘要：相关向量机(RVM)是一种通过贝叶斯推断在核空间建立稀疏线性模型的机器学习方法。在求解分类问题时，为了避免不可分或误标记训练样本对RVM分类精度的影响，提出一种训练方法。在训练得到RVM模型后，用置信度加权(Confidence weighted)算法重新对权值进行学习。CW算法通过计算当前样本对已有模型的置信度，判断是否用当前样本更新权值。利用这一特性在训练时只挑选部分训练集用于训练。结果表明：本算法保持了RVM的稀疏性，其分类能力比标准RVM的有所提高。