先验信息优化的S3VM算法模型研究
蒋长鸿1, 范钢龙2,3     
1. 西北工业大学 计算机学院, 陕西 西安 710072;
2. 洛阳师范学院 电子商务学院, 河南 洛阳 471934;
3. 河南省电子商务大数据处理与分析重点实验室, 河南 洛阳 471934
摘要: 在没有充足的标记数据支撑的情况下,传统的半监督学习算法的运算精确性和效率会显著降低。因此,在大数据应用中,面对海量增长的数据和其中所包含的庞杂信息,需要对传统算法进行优化。但相对于数据特征,数据的先验信息是数据集中的一个未被重视的重要组成部分。文中建立了合适的数学模型引入先验信息;针对静态先验信息、动态先验信息2种不同形式先验信息,对传统S3VM算法进行了优化。测试实验验证了模型的效果。
关键词: 半监督学习     支持向量机     先验信息    

随着互联网络基础设施的完善和普及, 以及云计算、大数据处理等技术的日渐成熟, 机器学习算法需要面向的数据规模与日俱增, 对于传统算法的改进迫在眉睫。现有基于支持向量机的半监督学习方法, 大都将分类的关注重点放在数据本身的特征, 过分依赖于标记信息的特征和未标记信息的特征间的近似性估计, 来判断最优分类平面的位置[1]

经研究测试, 常见半监督支持向量机算法, 诸如S3VM[2], TSVM, laplacianS3VM[3]和meanS3VM[4]等, 在数据集中标记样本的个数增大时, 其精度均有明显提升; 而对不同算法所得到的精度提升则大致相同。因此, 可以得出如下结论:半监督支持向量机的算法精度与标记样本在总样本中所占比例呈显著正相关[5]。然而, 现实中的数据集合, 除人为标定提取的特征之外, 还有大量的隐藏信息, 通常会将其视为背景信息而忽略。因此, 本文试图通过数学建模将这些信息加以利用, 对传统的S3VM算法进行优化, 以提高这类算法在面对大量数据时的运行效率。

1 先验信息

先验信息是指在以样本进行试验之前, 已经取得的历史资料和经验。先验信息既与事物自身的客观状态及其状态变化的方式有关, 也与观察者自身的主观因素有关。

通常, 数据的特征是在数据集中受到最多关注的信息。然而在现实中, 在将样本集抽象到数据集时, 人为标定提取的特征只是样本集中所蕴涵信息的很小一部分, 还有大量的信息包含在其中却未被关注。这些未被关注的信息里, 就包含很多数据集的先验信息。

对于任何一个数据集, 其所包含的信息都有庞大的规模。但其中大部分的信息, 或者只与数据集中的部分数据相关, 不能涵盖整体, 或者冗杂而无意义。因而, 我们通常所使用的仅仅是其中极少的一小部分。而在余下的信息中, 其中一部分可以在某些条件下通过人们的主观经验, 抽象为整个数据集的特征信息, 即我们可以关注的先验信息。尽管如此, 数据集中所包含先验信息的数量, 仍然远远多于通常所使用数据特征中所包含的信息数量。

除了与数据集的客观因素有关外, 先验信息也会受到数据集使用者的主观影响。因此, 不一定存在完全的客观依据, 可以部分或完全地基于主观信念的特点。换言之, 对于一个数据集, 依据使用者基于自己使用该数据集的不同目的, 可以得到不同的有意义的先验信息, 而这种先验信息不必完全受限于数据集的客观条件。

这样一个灵活的特点, 使得先验信息可以被灵活地运用到数据集的处理当中。本文的目的, 在于通过数学模型的设计, 明确如何恰当选取先验信息, 并基于半监督支持向量机, 对未标记信息的学习算法进行优化。

1.1 静态先验信息

在对数据集的学习过程中, 除了数据集本身之外, 常常有一些与数据集具体内容无关, 但与数据集如何选取有一定关联的全局信息, 存在于数据集的背景环境之中。由于与数据集的具体内容无关, 所以这些信息不会因为数据集中内容的变换而改变。本文将这些信息称为静态先验信息。

例如, 在道路监控视频中, 如果以道路上的车辆作为目标数据, 则因所关心的目标数据是道路上的车辆, 所以空间位置在道路上的数据点, 才可能是我们关心的目标数据。而每当我们选定一个参考系, 道路的形式一定可以用一组方程确定, 且不会因为其上经过的车辆而改变, 于是道路就可以视为一种静态先验信息。

图 1所示, 道路的范围就是一种静态先验信息, 道路在场景选定后是确定的、不变的。静态先验信息优化, 可以视作一种对部分未标记数据进行快速标记的方式。

图 1 静态先验信息示例
1.2 动态先验信息

静态先验信息是与数据集具体内容无关, 但与数据集如何选取有一定关联的全局信息。由于其本身的特殊性, 已有的数据集有时并不能对寻找静态先验信息提供帮助。静态先验信息与数据集的具体内容无关, 所以它的发现完全依靠对所需处理数据背景信息的获取和整体把握。在不完全利用额外的背景信息的情况下, 已有的数据集具体内容之间的关系, 有可能也作为额外的先验信息进行利用。这种利用已有数据集具体内容推导而得出的先验信息, 本文将其称为动态先验信息。

同样, 以在道路监控视频中的车辆跟踪为例, 以道路上的车辆作为目标数据, 由于所关心的目标数据是道路上的车辆, 所以根据车辆行驶的一般规律, 如果可通过标记信息判断出目标车辆的行进方向, 那么与行进方向相同而不是相反的未标记数据点, 就可能是我们关心的目标数据。每当获得了有限个标记数据, 而它们的内部关系又是可以描述的, 它们就可作为动态先验信息。

图 2所示, 车辆加速度a就是一种动态先验信息, 它可以通过不同帧图像之间的车辆位置差异和帧间隔计算得到。动态先验信息优化, 是一种利用标记数据进行快速标记推广的方式。

图 2 动态先验信息示例
2 先验信息的引入

数据的特征向量是支持向量机算法中的一个重要组成部分, 直接影响着分类超平面位置的确定。将数据的先验信息直接作为其特征向量的一部分, 会使先验信息对分类超平面位置的确定产生不可预知的影响。而将数据的先验信息与其特征向量割裂开来, 则会对算法中数据的组织结构产生影响。因此, 下面构建了一个适当的模型, 将S3VM算法中引入先验信息。

2.1 先验增广向量

考虑机器学习中最根本的问题, 即包含2个类别的线性可分问题。样本集在n维欧式空间中可以实现线性分离, 即等价于空间中存在超平面可将样本集按照不同的标签分隔开来。

设样本集为{(xi, yi)|xiRn; yi∈{-1, +1}, i=1, 2, …, l}, 为了使具有不同标签的样本点被分隔开来且分类模式具有良好的泛化能力, 我们的目的是寻找一个具有最大的分离间隔最优超平面L

由于超平面在n维欧式空间中的数学表达式可写成如下的线性方程

(1)

式中, w为系数向量, xn维变量, <w, x>是向量wx的内积, b为常数。

空间中点到超平面L的距离可表示为

(2)

欲使d(xi, H)最大, 显然应使下式取最小值

(3)

于是, 便得到一个在约束条件下的极值问题:

(4)

式中, n维变量xi, 即是包含样本内元素抽象特征的一个特征向量:

(5)

式中,aij是第i个元素的第j个抽象特征值。

如果每个数据都有m个可以标记的先验信息, 则可以将这些信息抽象集合成如下的一个向量

(6)

联立(5)式和(6)式, 可以构成一个包含了更多信息的增广特征向量:

(7)

根据以上推导过程, 可以得到如下定义2.1。

定义2.1  先验增广向量:先验增广向量xi是利用标记数据在支持向量机下产生的特征向量和数据集的先验信息联合构成的一个包含了更多信息的特殊的特征向量。

至此, 将额外的先验信息整合到了元素的特征向量中。

对于线性方程式(1), 只要将系数向量w推广为

(8)

则(9)式所示的新方程依然成立:

(9)

这也就是说, 利用定义2.1构成的增广特征向量在对方程进行变换后, 仍能满足原来的支持向量机运行条件。

2.2 先验增广向量的S3VM

设半监督支持向量机使用下式所示的数据集

(10)

且根据实际情况, 设其中无标记数据的数量远大于有标记数据的数量, 即lk

则在这种情况下, 半监督支持向量机方法等价于如下的优化问题

(11)

利用先验增广向量, 如算法1所示, 我们可以提高对半监督学习中未标记信息的筛选效率, 从而提高支持向量机学习未标记信息的性能。

算法1  先验增广向量优化算法

1) 提取数据集的特征向量x;

2) 按照(7)式, 利用先验信息构成增广特征向量x′;

3) 通过增广特征向量更新部分标记项yi;

4) 按照(9)式, 求得新的方程〈w′, x′〉+b=0;

5) 代回(11)式求解。

3 S3VM-pri与S3VM-dpri算法 3.1 静态先验优化的标记更新

X={x1, x2, …, xn}(n=l+k)为输入空间, y={1, -1}为标记空间, 则静态先验信息可以抽象为一组方程。以二维空间为例, 由静态先验信息可确定如下式所示的区域

(12)

该区域即为由这组静态先验信息所确定的先验判别区域F(x, y)。先验判别区域F(x, y)可以对每一个独立的数据给出一个反馈信息l={0, 1}(l=0表示不在区域内, 反之则表示在区域内), 如下式所示:

(13)

只要将这个反馈信息l和标记项yi相关联, 则按这个先验判别区域, 就可以构成如下式所示的先验判别条件:

(14)

参考算法1可得出静态先验优化的标记更新算法2。

算法2  静态先验优化的标记更新算法

1) 提取数据集的特征向量x;

2) 提取先验信息方程组fi(x, y)=0, i=1, 2, …, n;

3) 构成增广特征向量x′;

4) 通过先验判别条件更新标记项yi

3.2 静态先验优化算法S3VM-pri

X={x1, x2, …, xn}(n=l+k)为标准S3VM的输入空间, y={1, -1}为标记空间, 则有:

(15)

实际上, 通常假设lk, 则(15)式在形式上与下式等价

(16)

(17)

可将上式拆解为(18)式和(19)式

(18)
(19)

(18)式等价于(20)式

(20)

其中, (20)式是软间隔为ηi的支持向量机的标准形式, 即由(20)式可以求出一组确定的参数(w, b), 从而可得出满足所有标记数据条件的最优超平面。

而(19)式则是利用未标记数据试分类的结果对(20)式的结果再进行进一步调整, 使其更贴近数据整体的结果。

综上所述, (20)式(等价于(18)式)的结果是确定的、准确性高的结果; (19)式的结果是估计的、准确性较低的结果。

(19)式的结果直接权重为, (18)式的结果直接权重为, 但由于lk, 故(19)式的低精度和高运算复杂度的结果更影响(15)式的结果和运算效率。

这时, 可以利用算法2, 使得原数据空间

转化为新数据空间

式中,xp为通过算法2更新标记的数据, k′=k-p

故(15)式可写成

(21)

再令l′=l+p, 将其代入(21)式, 同前述推导, 即有(22)式和(23)式。

(22)
(23)

在这种情况下, (22)式的结果直接权重为, (23)式的结果直接权重为, (22)式高精度结果的直接权重增加了

总结上述推导, 通过构建先验信息判别式对数据集进行优化, 可以将未标记信息中的部分数据与标记信息联合成为新的标记集合, 减少了未标记信息带来的算法迭代次数, 从而提高算法效率。参照算法2, 可以得到算法3。

算法3   S3VM-pri

1) 输入数据集X;

2) 输入静态先验信息构建先验判别方程fi(x, y)=0, i=1, 2, …, n;

3) 将X依照数据标记yi分类;

4) 对未标记数据利用先验判别条件F(x, y)优化;

5) 将更新标记的数据xp与已标记数据xl归并为xl;

6) 将xlxu分别通过SVM和S3VM计算并输出结果(w, b)。

3.3 动态先验优化的标记推广

X={x1, x2, …, xn}(n=l+k)为输入空间, y={1, -1}为标记空间。在已有数据集中, 每若干个相互关联的数据按照一定规律可以描述为一个方程, 这就是一条动态先验信息。以二维空间为例, 若干条动态先验信息可以抽象为如下所示的一组方程

(24)

不同于静态先验信息会利用这组方程生成一个先验判别区域F(x, y), 描述动态先验先验信息的方程组可能并不会形成统一的判别区域, 而是各自反馈各自的判别结果。

即有如下所示的动态先验判别方程组

(25)

式中, αi∈{1, -1}。

假设数据点xk满足(25)式中的第m个方程, 则有yk=lm=αm

若数据点xk满足(25)式中的m个方程, 则有如下所示的判别式

(26)

参考算法1, 可以得出算法4。

算法4  动态先验优化的标记推广算法

1) 提取数据集的特征向量x;

2) 推导先验判别方程组fi(x, y)=0, i=1, 2, …, n;

3) 构成增广特征向量x′;

4) 通过先验判别条件推广标记项yi

3.4 动态先验优化算法S3VM-dpri

动态先验优化的S3VM算法推导过程基本同于3.2节, 故下面直接给出算法5。

算法5   S3VM-dpri

1) 输入数据集X;

2) 将X依照数据标记yi分类;

3) 推导动态先验信息, 构建先验判别方程组fi(x, y)=0, i=1, 2, …, n;

4) 对未标记数据利用先验判别方程组进行优化;

5) 将推广标记的数据xp与已标记数据xl归并为xl;

6) 将xlxu分别通过SVM和S3VM计算并输出结果(w, b)。

3.5 S3VM-pri与S3VM-dpri对比

1) 静态先验优化

考虑(14)式, 静态先验优化所构成的先验判别区域F(x, y)通常对于数据集X的类别判断来说, 是充分条件而不是充要条件, 所以该优化只有更新单一类别标记的能力。

换句话说, 一般情况下先验判别区域F(x, y)对于未标记数据xu, 只能作类似如下的判断:

(1) 不在该区域内的数据点标记一定为-1;

(2) 在该区域内的数据点标记可能为1或-1。

实质上, 静态先验优化的工作重点在于高效清除干扰点。

2) 动态先验优化

考虑(24)式, 由于动态先验优化的判别方程组fi(x, y)=0是分别由标记数据xl推导得出的, 所以其给出的反馈, 对于数据集X的类别判断来说, 是充要条件, 所以该优化可以同时推广所有参与其推导的数据包含的类别标记。

因此, 动态先验优化的效果, 在于通过每类标记数据自身的内在联系, 丰富该类别的数据。

4 实验及结果分析

本文对S3VM-pri和S3VM-dpri测试实验中, 使用了15-Scene、21-LandUse、25-Texture、101-Caltech 4个数据集, 共计10 000个数据, 其中使用的标记数据为400个。实验在Microsoft Visual Studio 2010和Matlab R2015b环境下进行。

在不提供任何先验信息的情况下得到表 1

表 1 无先验信息实验结果
算法准确性/%时间/s
S3VM92.0813.265
S3VM-pri92.0813.386
S3VM-dpri92.0813.281

以S3VM算法的运行结果为基准, 由表 1可以看出, 在不提供先验信息的情况下, 新算法的分类准确性未受影响, 但是它们的运行时间分别增加了0.121 s和0.016 s, 这应该是由于算法前增加的先验筛选器空运行的结果导致的。

为了验证S3VM-pri算法, 对每个数据添加一组额外标记(x, y), 其中x, y∈{1, 2, 3, 4, 5}。令先验判别条件为x>1, 并将2 000个经S3VM分类后标记应为-1的数据添加额外标记(1, y), 其中y∈{1, 2, 3, 4, 5}, 其余数据随机添加额外标记(x, y), 其中x∈{2, 3, 4, 5} y∈{1, 2, 3, 4, 5}。

在对2 000个数据标记合适的静态先验信息的情况下得到表 2

表 2 静态先验信息优化实验结果
算法准确性/%时间/s
S3VM92.0813.265
S3VM-pri92.0812.839

在标记了足量的静态先验信息后, 可以看出S3VM算法并未受到额外标记的影响, 而S3VM-pri算法则在保证准确性的情况下, 将运行时间缩短了0.426 s。

为了验证S3VM-dpri算法, 对每个数据添加一组额外标记(x, y), 其中x, y∈{1, 2, 3, 4, 5}。令先验判别条件为x=yx=y+1, 并将1 000个经S3VM分类后标记应为-1的数据添加额外标记(x, y), 其中x=y; 另外将1 000个经S3VM分类后标记应为1的数据添加额外标记(x, y), 其中x=y+1;其余数据随机添加额外标记(x, y), 其中xyxy+1。

在对2 000个数据标记合适的动态先验信息的情况下得到表 3

表 3 动态先验信息优化实验结果
算法准确性/%时间/s
S3VM92.0813.265
S3VM-dpri90.9412.944

在标记了足量的动态先验信息后, 可以看出S3VM算法并未受到额外标记的影响, 而S3VM-dpri算法准确性下降了1.14%, 运行时间缩短了0.321 s。

按照3.2节中的推导, 理论上算法的运行效率提升应该为0.836 s, 但在实际测试中, 2种算法所提高的运行效率均未达到或接近理论值, 其原因可能在于测试数据规模仍然过小。同时, S3VM-dpri算法的测试中, 出现了分类准确性的微量下降, 这是因为在构建动态先验信息判别方程组的时候产生了预设之外的判别方程。

总之, S3VM-pri和S3VM-dpri 2种算法在保证分类准确性的情况下, 均能提高算法的运行效率, 虽然未能达到或接近理论水平, 但效果仍较为明显。

5 结论

本文根据数据集的结构, 在传统算法中引入了先验信息作为参量, 从理论上证明了当面对大数据时, 先验信息有助于传统算法运算性能的提高。并且通过具体化了静态先验信息和动态先验信息2种可用的先验信息表现形式, 继续通过理论上的推导和分析, 分别利用静态先验信息和动态先验信息, 建立了S3VM-pri和S3VM-dpri 2种不同半监督支持向量机模型, 最终通过理论推导和测试试验, 对这2种算法的有效性和优越性进行了考量。

参考文献
[1] Palaniappan R, Sundaraj K, Sundaraj S. A Comparative Study of the SVM and K-nn Machine Learning Algorithms for the Diagnosis of Respiratory Pathologies Using Pulmonary Acoustic Signals[J]. BMC Bio Information, 2014, 15(1): 1-8.
[2] Guillory A, Bilmes J A. Active Semi-Supervised Learning Using Submodular Functions[C]//Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, 2011:274-282
[3] Gu Y, Feng K. Optimized Laplacian SVM with Distance Metric Learning for Hyperspectral Image Classification[J]. IEEE Journal of Selected Topics in Applied Earth Observations & Remote Sensing, 2013, 6(3): 1109-1117.
[4] Günen M, Alpaydln E. Localized Algorithms for Multiple Kernel Learning[J]. Pattern Recognition, 2013, 46(3): 795-807. DOI:10.1016/j.patcog.2012.09.002
[5] Fujino A, Ueda N, Nagata M. Adaptive Semi-Supervised Learning on Labeled and Unlabeled Data with Different Distributions[J]. Knowledge and Information Systems, 2013, 37(1): 129-154. DOI:10.1007/s10115-012-0576-8
A Novel Algorithm Model Design of S3VM Improved by Prior Information
Jiang Changhong1, Fan Ganglong2,3     
1. School of Computer Science and Engineering, Northwestern Polytechnical University, Xi'an 710072, China;
2. School of Electronic Commerce, Luoyang Normal University, Luoyang 471934, China;
3. Key Lab on E-Commercial Big-Data Processing and Analysis of Henan, Luoyang 471934, China
Abstract: If there is insufficient labeled data to support, the traditional semi-supervised learning algorithm has a significant reduction in computational accuracy and efficiency. Therefore, facing the massive growth of data and the included complex information, traditional algorithms must be improved for the applications of Big-date. The prior information of data, comparing with the data feature, is an important component of the data set that hasn't been focused on. This paper establishes an appropriate mathematical model to introduce the priori information, and designs two models to improve the traditional S3VM algorithm by two different kind of prior information, static priori information and dynamic priori information. The test experiment verifies the effect of the model.
Key words: big data     computational efficiency     MATLAB    
supervised learning     semi-supervised learning     support vector machine     priori information    
西北工业大学主办。
0

文章信息

蒋长鸿, 范钢龙
Jiang Changhong, Fan Ganglong
先验信息优化的S3VM算法模型研究
A Novel Algorithm Model Design of S3VM Improved by Prior Information
西北工业大学学报, 2017, 35(5): 786-792.
Journal of Northwestern Polytechnical University, 2017, 35(5): 786-792.

文章历史

收稿日期: 2017-03-12

相关文章

工作空间