ABSTRACT

In many practical problems of machine learning, the data has multi-views; multi-views complement each other; and the classification effect is better. This paper mainly studies the semi-supervised method of multi-view dual support vector machine, and divides the data according to different characteristics. Multi-views are used to find two non-parallel hyperplanes for each view, and the model is constructed to solve the dual problem. Experimental results show that the proposed algorithm can reduce the dimension of the data and has good classification accuracy. The support vector machine algorithm shortens the running time, reduces the computational complexity, and predicts better performance.

Keywords:Semi-Supervised Learning, Classification, Support Vector Machines, Multi-View

基于多视图双支持向量机半监督学习机

姚瑞

新疆大学，数学与系统科学学院，新疆 乌鲁木齐

收稿日期：2019年5月9日；录用日期：2019年5月23日；发布日期：2019年5月30日

摘 要

在机器学习的诸多实际问题中，数据有多个视图，多个视图优势互补，分类效果更好。本文主要针对多视图双支持向量机的半监督方法进行了研究，根据不同的特征将数据分成多个视图，分别给每个视图找两个非平行超平面，构建模型，求解对偶问题。实验结果表明，本文的算法可以对数据进行降维，有很好的分类精确度，该算法较双支持向量机算法缩短了运行时间，减少了计算复杂度，预测性能较好。

关键词 :半监督学习，分类问题，支持向量机，多视图

Copyright © 2019 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

多视图学习(MVL)可用于表示多个不同特征的数据集 [1]，不同的特征经常互相补充信息，与传统的单视图学习相反，MVL分别为每个特征视图构造一个学习函数，然后通过利用相同输入数据的冗余视图共同优化学习函数。到目前为止，已经提出了许多MVL算法，可以分为两组：协同训练 [2] 和协同正则化算法 [3]。协同训练算法通过迭代，最大化多个不同视图上的学习函数，以确保在相同数据的一致性。在协同正则化算法中，需要最小化不同视图学习目标函数中的正则项，典型的方法包括稀疏多视图SVMs [4]，multiview Laplacian SVMs [5]，多视图矢量值多重正则化方法 [6]。

半监督学习是一种综合学习方法，它使用少量标记数据来训练初始分类器，并使用大量未标记数据来进一步提高初始分类器的性能，最终实现准确学习。在学习过程中，学习机在训练过程中使用的样本是一个混合样本集，标签样本较少，未标记样本较多。它不仅利用标记样本的优点来精确描述单个样本，而且还可以发现未标记样本在整个样本集中的重要作用 [7]。

支持向量机(SVM)是一种机器学习方法，主要针对小样本分类问题，遵守结构风险极小化原则，获取全局最优解。1982年Vapnik首次提出支持向量机 [8]，他将支持向量机归结为一个二次型方程求解问题。其学习的基本想法是求解能够正确划分训练数据集并且使得几何间隔最大的分离超平面。在近几年的研究中，支持向量机在人脸检测、语音识别、文字识别、手写识别、图像处理等研究方面取得了很多研究成果并受到了许多领域学者的关注。因此，研究也从最初的简单模式发展到各种互补应用。研究人员通过添加函数、变量或系数来对公式进行变形，以生成具有独特优势或一系列应用的新算法，例如：B. Schlkopf等人提出的γ-SVM算法 [9]，主要通过γ参数控制支持向量的个数和误差；Lee等人通过引入光滑函数来近似正类样本标签从而提出一种光滑支持向量机(Smooth SVM, SSVM) [10]，Mangasarian等人提出的一种拉格朗日支持向量机(Lagrangian SVM, LSVM) [11]，Fung等人提出的近似支持向量机(Proximal SVM, PSVM) [12]，以及Lee等人提出的约简支持向量机(Reduced SVM, RSVM)等 [13]。

半监督支持向量机 [14] 是一种能够同时兼顾标签与无标签样本的学习方法，因而半监督支持向量机的学习方法在处理大规模数据识别与分类的过程中处理良好。半监督支持向量机最初应用于文本分类 [15]，研究人员之后提出了用于解决半监督支持向量机目标函数非凸问题的一系列方法，主要的研究方法有：梯度下降法(Gradient descent) [16]；凹凸法(Convex-Concave Procedure) [17]；确定性煺火方法(Deterministic annealing) [18] 等。

本文提出了一种基于多视图的双支持向量机的半监督学习方法，此方法将双支持向量机 [19] 与半监督多视图 [20] 学习相结合。给定训练集，将训练集分成两个视图，分别给视图一和视图二找两个非平行的超平面，构造两个二次规划模型，求解相应对偶问题，每个视图分别得到一个超平面，并可以求出决策函数。事实上，基于多视图双支持向量机半监督学习方法是对数据集进行降维。数据表明，与双支持向量机相比，多视图双支持向量机半监督学习方法训练的耗时更少，缩短了运行时间，减少了计算复杂度，有较高的准确率。

本文结构如下：第2节介绍了支持向量机及半监督多视图学习的基本思想；第3节介绍了基于多视图双支持向量机半监督学习的优化模型推导及算法；第4节对基于多视图双支持向量机半监督学习方法进行人工数据和UCI数据的数值实验，并与其它的分类算法进行比较；第5节给出一些结论及展望。

2. 相关工作

2.1. 支持向量机

对于训练集 $T=\left\{\left(x_1,y_1\right),\left(x_2,y_2\right),\cdots ,\left(x_l,y_l\right)\right\}$ ，其中， $x_i\in R^n$ 是输入的样本点， $y_i\in Y=\left\{-1,1\right\}$ 是输出的标签。线性的标准支持向量机要寻找一个超平面f(x)将两类点分开。

$f\left(x\right)=w^{T}x+b=0,$ (1)

其中， $w\in R^n$ ， $b\in R$ 分别是超平面的法向量和截距。引入松弛变量 $\xi$ ，标准支持向量机的矩阵形式可以表示为：

$\begin{array}{ll}\underset{w,b,\xi }{{\displaystyle \min }}\hfill & \frac{1}{2}{(\Vert Aw+e_{1}b\Vert }^2+c{e}_2^T\xi ,\hfill \\ \text{s}\text{.t}\text{.}\hfill & -\left(Bw+e_{2}b\right)\ge e_2-\xi ,\hfill \\ \hfill & \xi \ge 0,\hfill \end{array}$ (2)

其中， $A\in \left(m\times n\right)$ ， $c\ge 0$ 是惩罚参数， $e_1$ 和 $e_2$ 是相应的维数为的1向量。我们通过求解(2)式的对偶问题可以得到使得 $w$ 和 $b$ ，从而可以得到两个平行的支持超平面 $w^{T}x+b\mathrm{<mo>\; =\; </mo>1}$ 和 $w^{T}x+b\mathrm{<mo>\; =\; </mo>}-1$ 。

2.2. 线性可分的双支持向量机

对于训练集 $T=\left\{\left(x_1,y_1\right),\left(x_2,y_2\right),\cdots ,\left(x_l,y_l\right)\right\}$ ，其中 $x_i\in R^n$ 是输入的样本点， $y_i\in Y=\left\{-1,1\right\}$ 是输出的标签。

双支持向量机 [19] 寻找两个非平行的超平面 $f_1\left(x\right)$ 和 $f_2\left(x\right)$ 使得其中的一个超平面离一类样本点尽可能近，而离另一类样本点尽可能远，反之亦然。

$f_1\left(x\right)=w_1^{T}x+b_1=0,f_2\left(x\right)=w_2^{T}x+b_2=0,$ (3)

其中， $w_1\mathrm{,}{w}_2\in R^n$ 和 $b_1\mathrm{,}{b}_2\in R$ 分别是两个非平行超平面的法向量和截距。引入松弛变量 $\xi$ ，线性双支持向量机的模型为：

$\begin{array}{ll}\text{TWSVMM}1:\underset{w_1,b_1,\xi }{{\displaystyle \min }}\hfill & \frac{1}{2}{(\Vert A{w}_1+e_1{b}_1\Vert }^2+c_1{e}_2^T\xi ,\hfill \\ \text{s}\text{.t}\text{.}\hfill & -\left(B{w}_1+e_2{b}_1\right)\ge e_2-\xi \hfill \\ \hfill & \xi \ge 0,\hfill \end{array}$ (4)

和

$\begin{array}{ll}\text{TWSVMM}2:\underset{w_2,b_2,\xi }{{\displaystyle \min }}\hfill & \frac{1}{2}{(\Vert B{w}_2+e_2{b}_2\Vert }^2+c_2{e}_1^T\xi ,\hfill \\ \text{s}\text{.t}\text{.}\hfill & A{w}_2+e_1{b}_2\ge e_1-\xi ,\hfill \\ \hfill & \xi \ge 0,\hfill \end{array}$ (5)

其中， $A\in \left(m_1\times n\right)$ ， $B\in \left(m_2\times n\right)$ ， $c_1\mathrm{<mo>\; >\; </mo>0,}{c}_2\mathrm{<mo>\; >\; </mo>0}$ 是惩罚参数， $e_1$ 和 $e_2\mathrm{<mo>\; >\; </mo>0}$ 是相应维数的单位向量。

简单的说，双支持向量机是一对二次规划问题，对每个小的二次规划问题构造拉格朗日函数，求解对偶问题，可以得到 $w_1\mathrm{,}{w}_2\mathrm{,}{b}_1\mathrm{,}{b}_2$ ，进而可得到双支持向量机的决策函数：

$f\left(x\right)=\arg \underset{k=1,2}{{\displaystyle \min }}\frac{\left|w_k^{T}x+b_k\right|}{\Vert w_k\Vert },$ (6)

其中， $k=1,2$ 分别对应正负类标签 $\left\{+1,-1\right\}$ 。

2.3. 线性不可分的双支持向量机

显然，并不是所有问题都是线性可分的，对于非线性分划问题，我们可以选择一个适当的内核 $K$ ，用曲面 $g_1\left(x\right)$ 和 $g_2\left(x\right)$ 代替平面 $f_1\left(x\right)$ 和 $f_2\left(x\right)$ 。

$g_1\left(x\right)=K\left(x^T,C^T\right)u_1+b_1=0,g_2\left(x\right)=K\left(x^T,C^T\right)u_2+b_2=0,$ (7)

其中 $C^T={\left[AB\right]}^T$ ，定义 $w_1=C^T{u}_1$ 和 $w_2=C^T{u}_2$ ，根据2.2节可构造优化问题如下：

$\begin{array}{ll}\text{KTWSVM}1:\underset{u_1,b_1,\xi }{{\displaystyle \min }}\hfill & \frac{1}{2}{\left(\Vert K\left(A,C^T\right)u_1+e_1{b}_1\Vert \right)}^2+c_1{e}_2^T\xi ,\hfill \\ \text{s}\text{.t}\text{.}\hfill & -\left[K\left(B,C^T\right)u_1+e_2{b}_1\right]\ge e_2-\xi ,\hfill \\ \hfill & \xi \ge 0,\hfill \end{array}$ (8)

和

$\begin{array}{ll}\text{TWSVM}2:\underset{u_2,b_2,\xi }{{\displaystyle \min }}\hfill & \frac{1}{2}{(\Vert K\left(B,C^T\right)u_2+e_2{b}_2\Vert }^2+c_2{e}_1^T\xi ,\hfill \\ \text{s}\text{.t}\text{.}\hfill & K\left(A,C^T\right)u_2+e_1{b}_2\ge e_1-\xi ,\hfill \\ \hfill & \xi \ge 0,\hfill \end{array}$ (9)

其中 $c_1\mathrm{<mo>\; >\; </mo>0,}{c}_2\mathrm{<mo>\; >\; </mo>0}$ 是惩罚参数， $e_1$ 和 $e_2\mathrm{<mo>\; >\; </mo>0}$ 是相应维数的单位向量。构造拉格朗日函数求解对偶问题，便可得到其决策函数。

2.4. 半监督多视图学习

多视图用于表示数据的不同特征集，本文研究的均为双视图。在多视图学习算法中，给定有标签数据集 ${\left\{\left(x_i\mathrm{,}{y}_i\right)\right\}}_{i\mathrm{<mo>\; =\; </mo>1}}^l$ 和无标签数据 ${\left\{x_i\right\}}_{i\mathrm{<mo>\; =\; </mo>}l+1}^{l+u}$ ，任意一个数据点 $x$ 我们都可以分成两个视图 $x^{\left(1\right)}$ 和 $x^{\left(2\right)}$ ，即 $x=\left(x^{\left(1\right)},x^{\left(2\right)}\right)$ ，其中 $x_i\in R^n$ ， $y_i\in Y=\left\{-1,1\right\}$ ，则目标函数可以表示为 $f=\left(f^{\left(1\right)},f^{\left(2\right)}\right)$ ， $f^{\left(1\right)}$ 和 $f^{\left(2\right)}$ 分别为两个视图下的目标函数。半监督多视图学习方法中，在协同正则化最小二乘方法下的目标函数为：

$\begin{array}{cc}f=\arg \min & {\displaystyle \underset{i=1}{\overset{l}{\sum }}}{\left[y_i-f^{\left(1\right)}\left(x_i^{\left(1\right)}\right)\right]}^2+\mu {\displaystyle \underset{i=1}{\overset{l}{\sum }}}{\left[y_i-f^{\left(2\right)}\left(x_i^{\left(2\right)}\right)\right]}^2+{\gamma }_1{\Vert f^{\left(1\right)}\Vert }^2\\ & +{\gamma }_2{\Vert f^{\left(2\right)}\Vert }^2+\frac{\gamma C}{l+u}{\displaystyle \underset{i=1}{\overset{l+u}{\sum }}}{\left[f^{\left(1\right)}\left(x_i^{\left(1\right)}\right)-f^{\left(2\right)}\left(x_i^{\left(2\right)}\right)\right]}^2,\end{array}$ (10)

其中， $\mu$ 是平衡两个视图的参数， ${\gamma }_1$ ， ${\gamma }_2$ 是正则化参数， $\gamma C$ 是耦合参数，用于调节无标签数据的兼容性。

根据表示定理(10)式可表示为：

$f=\min \left[{\displaystyle \underset{i=1}{\overset{l+u}{\sum }}}{\alpha }_i{K}^{\left(1\right)}\left(x^{\left(1\right)},x_i^{\left(1\right)}\right),{\displaystyle \underset{i=1}{\overset{l+u}{\sum }}}{\beta }_i{K}^{\left(2\right)}\left(x^{\left(2\right)},x_i^{\left(2\right)}\right)\right],i=1,2,\cdots ,l+u$ (11)

其中， $K^{\left(1\right)}$ 和 $K^{\left(2\right)}$ 是核函数。 $\alpha$ 和 $\beta$ 可以通过下列线性方程组求出：

$\begin{array}{l}\left[\frac{1}{l}J{K}_1+{\gamma }_{1}I+\frac{\gamma C}{l+u}{K}_1\right]\alpha -\frac{\gamma C}{l+u}{K}_2\beta =\frac{1}{l}Y],\\ \left[\frac{u}{l}J{K}_2+{\gamma }_{2}I+\frac{\gamma C}{l+u}{K}_2\right]\left[\beta -\frac{\gamma C}{l+u}{K}_1\alpha =\frac{u}{l}Y\right],\end{array}$ (12)

其中， $J$ 和 $Y$ 构成的对角矩阵， $K_1$ 和 $K_2$ 是核函数 $K^{\left(1\right)}$ 和 $K^{\left(2\right)}$ 的格拉姆矩阵。

3. 基于多视图双支持向量机的半监督学习方法

针对分类问题，本文提出了基于多视图双支持向量机的半监督学习方法，此方法将双支持向量机应用到多视图半监督学习中。给定训练集 $T=\left\{\left(x_1,y_1\right),\cdots ,\left(x_l,y_l\right)\right\}\cup \left\{x_{l+1},\cdots ,x_{l+u}\right\}$ ，其中 $x_i\in R^n,i=1,\cdots ,l,l+1,l+u,\mathrm{<mi>\; </mi>}{y}_i\in Y=\left\{-1,1\right\}$ ，需要找到与 ${\left\{x_i\right\}}_{i\mathrm{<mo>\; =\; </mo>}l+1}^{l+u}$ 对应的输出值 $y_u={\left(y_{l+1},\cdots ,y_{l+u}\right)}^T$ 和在多视图双支持向量机中的决策函数：

$\begin{array}{l}f\left(x\right)=\min \left\{f_1\left(x\right),f_2\left(x\right)\right\}\\ =\min \left\{\min \left|w^{\left(1i\right)T}x+b^{\left(1i\right)}\right|,\min \left|w^{\left(2i\right)T}x+b^{\left(2i\right)}\right|\right\},\\ i=1,2,\end{array}$

本文提出的多视图双支持向量机半监督学习方法是将(2.2)节中的矩阵 $A\mathrm{,}B$ 分别从两个视图进行描述，得到线性可分的多视图双支持向量机的半监督学习(MV-TWSVM)的优化模型为：

$\begin{array}{l}\begin{array}{cc}\text{MV-TWSVM}1:& \min \end{array}\frac{1}{2}\left({\Vert A_1{w}^{\left(11\right)}+e_1{b}^{\left(11\right)}\Vert }^2+{\Vert A_2{w}^{\left(12\right)}+e_1{b}^{\left(12\right)}\Vert }^2\right)+c_{11}{e}_2^T{\xi }^{\left(11\right)}+c_{12}{e}_2^T{\xi }^{\left(12\right)}\\ +\frac{1}{2}{\gamma }_1{c}_1{\Vert \left(U_1{w}^{\left(11\right)}+e_3{b}^{\left(11\right)}\right)-\left(U_2{w}^{\left(12\right)}+e_3{b}^{\left(12\right)}\right)\Vert }^2,\\ \text{s}\text{.t}\text{.}-\left(B_1{w}^{\left(11\right)}+e_2{b}^{\left(11\right)}\right)\ge e_2-{\xi }^{\left(11\right)},\\ -\left(B_2{w}^{\left(12\right)}+e_2{b}^{\left(12\right)}\right)\ge e_2-{\xi }^{\left(12\right)},\\ {\xi }^{\left(11\right)}\ge 0,\mathrm{<mi>\; </mi>\; <mi>\; </mi>}{\xi }^{(12)}\ge 0,\end{array}$ (13)

和

$\begin{array}{l}\begin{array}{cc}\text{MV-TWSVM2}:& \min \end{array}\frac{1}{2}\left({\Vert B_1{w}^{\left(21\right)}+e_2{b}^{\left(21\right)}\Vert }^2+{\Vert B_2{w}^{\left(22\right)}+e_2{b}^{\left(22\right)}\Vert }^2\right)+c_{21}{e}_1^T{\xi }^{\left(21\right)}+c_{22}{e}_2^T{\xi }^{\left(22\right)}\\ +\frac{1}{2}{\gamma }_2{c}_2{\Vert \left(U_1{w}^{\left(21\right)}+e_3{b}^{\left(21\right)}\right)-\left(U_2{w}^{\left(22\right)}+e_3{b}^{\left(22\right)}\right)\Vert }^2,\\ \text{s}\text{.t}\text{.}\left(A_1{w}^{\left(21\right)}+e_1{b}^{\left(21\right)}\right)\ge e_1-{\xi }^{\left(21\right)}\mathrm{,}\\ \left(A_2{w}^{\left(22\right)}+e_1{b}^{\left(22\right)}\right)\ge e_1-{\xi }^{\left(22\right)},\\ {\xi }^{\left(21\right)}\ge \mathrm{0,\; <mi>\; </mi>\; <mi>\; </mi>}{\xi }^{\left(22\right)}\ge 0,\end{array}$ (14)

其中， $A_v\in \left(m_1\times n\right)$ 和 $B_v\in \left(m_2\times n\right)$ ， $m_1$ 和 $m_2$ 表示数据点的数量，v表示视图的个数， ${\gamma }_1$ ， ${\gamma }_2$ ， $c_1$ ， $c_2$ 是参数， $e_1$ ， $e_2$ ， $e_3$ 表示相应维数的单位向量 ${\xi }^{\left(1v\right)}$ ， ${\xi }^{\left(2v\right)}$ 是损失项。

对(3.2)式引入拉格朗日乘子并构造拉格朗日函数为：

$\begin{array}{l}L\left(w^{\left(11\right)}\mathrm{,}{w}^{\left(12\right)}\mathrm{,}{b}^{\left(11\right)}\mathrm{,}{b}^{\left(12\right)}\mathrm{,}{\alpha }_{11}\mathrm{,}{\alpha }_{12}\mathrm{,}{\beta }_{11}\mathrm{,}{\beta }_{12}\right)\\ \mathrm{<mo>\; =\; </mo>}\frac{1}{2}{\left(A_1{w}^{\left(11\right)}+e_1{b}^{\left(11\right)}\right)}^T\left(A_1{w}^{\left(11\right)}+e_1{b}^{\left(11\right)}\right)+\frac{1}{2}{\left(A_2{w}^{\left(12\right)}+e_1{b}^{\left(12\right)}\right)}^T\left(A_2{w}^{\left(12\right)}+e_1{b}^{\left(12\right)}\right)\\ +\frac{1}{2}{\left[\left(U_1{w}^{\left(11\right)}+e_3{b}^{\left(11\right)}\right)-\left(U_2{w}^{\left(12\right)}+e_3{b}^{\left(12\right)}\right)\right]}^T\left[\left(U_1{w}^{\left(11\right)}+e_3{b}^{\left(11\right)}\right)-\left(U_2{w}^{\left(12\right)}+e_3{b}^{\left(12\right)}\right)\right]\\ +{\alpha }_{11}^T\left[B_1{w}^{\left(11\right)}+e_2{b}^{\left(11\right)}+e_2-{\xi }^{\left(11\right)}\right]+{\alpha }_{12}^T\left[B_2{w}^{\left(12\right)}+e_2{b}^{\left(12\right)}+e_2-{\xi }^{\left(12\right)}\right]\\ +c_{11}{e}_2^T{\xi }^{\left(11\right)}+c_{12}{e}_2^T{\xi }^{\left(12\right)}-{\beta }_{11}^T{\xi }^{\left(11\right)}-{\beta }_{12}^T{\xi }^{\left(12\right)}\mathrm{,}\end{array}$ (15)

对 $L$ 的分量求导并令其为0得：

${\nabla }_{w^{\left(11\right)}}L:A_1^T\left(A_1{w}^{\left(11\right)}+e_1{b}^{\left(11\right)}\right)+{\gamma }_1{c}_1{U}_1^T\left[\left(U_1{w}^{\left(11\right)}+e_3{b}^{\left(11\right)}\right)-\left(U_2{w}^{\left(12\right)}+e_3{b}^{\left(12\right)}\right)\right]+B_1^T{\alpha }_{11}=0,$ (16)

${\nabla }_{w^{\left(12\right)}}L\mathrm{<mo>\; :\; </mo>}{A}_2^T\left(A_2{w}^{\left(12\right)}+e_1{b}^{\left(11\right)}\right)+{\gamma }_1{c}_1{U}_2^T\left[\left(U_1{w}^{\left(11\right)}+e_3{b}^{\left(11\right)}\right)-\left(U_2{w}^{\left(12\right)}+e_3{b}^{\left(12\right)}\right)\right]+B_2^T{\alpha }_{12}\mathrm{<mo>\; =\; </mo>0,}$ (17)

${\nabla }_{b^{\left(11\right)}}L:e_1^T\left(A_1{w}^{\left(11\right)}+e_1{b}^{\left(11\right)}\right)+{\gamma }_1{c}_1{e}_3^T\left[\left(U_1{w}^{\left(11\right)}+e_3{b}^{\left(11\right)}\right)-\left(U_2{w}^{\left(12\right)}+e_3{b}^{\left(12\right)}\right)\right]+e_2^T{\alpha }_{11}=0,$ (18)

${\nabla }_{b^{\left(12\right)}}L:e_1^T\left(A_2{w}^{\left(12\right)}+e_1{b}^{\left(12\right)}\right)-{\gamma }_1{c}_1{e}_3^T\left[\left(U_1{w}^{\left(11\right)}+e_3{b}^{\left(11\right)}\right)-\left(U_2{w}^{\left(12\right)}+e_3{b}^{\left(12\right)}\right)\right]+e_2^T{\alpha }_{12}=0,$ (19)

${\nabla }_{{\xi }^{\left(11\right)}}L:c_{11}{e}_2^T-{\alpha }_{11}^T-{\beta }_{11}=0,$ (20)

${\nabla }_{{\xi }^{\left(12\right)}}L:c_{12}{e}_2^T-{\alpha }_{12}^T-{\beta }_{12}=0,$ (21)

${\nabla }_{{\alpha }_{11}}L:{\alpha }_{11}^T\left(B_1{w}^{\left(11\right)}+e_2{b}^{\left(11\right)}-{\xi }^{\left(11\right)}\right)=0,$ (22)

${\nabla }_{{\alpha }_{12}}L:{\alpha }_{12}^T\left(B_2{w}^{\left(12\right)}+e_2{b}^{\left(12\right)}-{\xi }^{\left(12\right)}\right)=0,$ (23)

${\nabla }_{{\beta }_{11}}L:{\beta }_{11}^T{\xi }^{\left(11\right)}=0,$ (24)

${\nabla }_{{\beta }_{12}}L:{\beta }_{12}^T{\xi }^{\left(12\right)}=0,$ (25)

$-\left(B_1{w}^{\left(11\right)}+e_2{b}^{\left(11\right)}\right)+{\xi }^{\left(11\right)}\ge e_2,$ (26)

$-\left(B_2{w}^{\left(11\right)}+e_2{b}^{\left(12\right)}\right)+{\xi }^{\left(12\right)}\ge e_2,$ (27)

由(16)和(18)得：

$\left(\left[\begin{array}{c}{A}_1^T\\ e_1^T\end{array}\right]\left[\begin{array}{cc}{A}_1& e_1\end{array}\right]+c_1{\gamma }_1\left[\begin{array}{c}{u}_1^T\\ e_3^T\end{array}\right]\left[\begin{array}{cc}{u}_1& e_3\end{array}\right]\right)\left[\begin{array}{c}{w}^{(11)}\\ b^{(11)}\end{array}\right]-c_1{\gamma }_1\left[\begin{array}{c}{u}_1^T\\ e_3^T\end{array}\right]\left[\begin{array}{cc}{u}_2& e_3\end{array}\right]\left[\begin{array}{c}{w}^{(12)}\\ b^{(12)}\end{array}\right]+{\alpha }_{11}\left[\begin{array}{c}{B}_1^T\\ e_2^T\end{array}\right]{\alpha }_{12}=0,$ (28)

由(17)和(19)得：

$-c_1{\gamma }_1\left[\begin{array}{c}{U}_2^T\\ e_3^T\end{array}\right]\left[\begin{array}{cc}{U}_1& e_3\end{array}\right]\left[\begin{array}{c}{w}^{\left(11\right)}\\ b^{\left(11\right)}\end{array}\right]+\left(\left[\begin{array}{c}{A}_2^T\\ e_1^T\end{array}\right]\left[\begin{array}{cc}{A}_2& e_1\end{array}\right]+c_1{\gamma }_1\left[\begin{array}{c}{U}_2^T\\ e_3^T\end{array}\right]\left[\begin{array}{cc}{U}_2& e_3\end{array}\right]\right)\left[\begin{array}{c}{w}^{\left(12\right)}\\ b^{\left(12\right)}\end{array}\right]+\left[\begin{array}{c}{B}_2^T\\ e_2^T\end{array}\right]{\alpha }_{12}=0,$ (29)

定义

$H_1=\left[A_1{e}_1\right],H_2=\left[A_2{e}_1\right],$

$P_1\mathrm{<mi>\; </mi>}=\left[U_1{e}_3\right],P_2=\left[U_2{e}_3\right],$

$G_1={\left[B_1{e}_2\right]}^T,G_2={\left[B_2{e}_2\right]}^T,$

令

$\begin{array}{l}H=H_1^T{H}_1+c_1{\gamma }_1{P}_1^T{P}_1,F=-c_1{\gamma }_1{P}_1^T{P}_2,\\ P=H_2^T{H}_2+c_1{\gamma }_1{P}_2^T{P}_2,Q=F^{-1}H-P^{-1}{F}^T,\\ u_1={\left[w^{\left(11\right)}{b}^{\left(11\right)}\right]}^T,u_2={\left[w^{\left(12\right)}{b}^{\left(12\right)}\right]}^T,\end{array}$ (30)

由(28)和(29)可到：

$H{u}_1+F{u}_2=-G_1{\alpha }_{11},$ (31)

$F^T{u}_1+P{u}_2=-G_2{\alpha }_{12},$ (32)

由(31)和(32)可解得：

$u_1=-Q^{-1}{F}^{-1}{G}_1{\alpha }_{11}+Q^{-1}{P}^{-1}{G}_2{\alpha }_{12},$ (33)

$u_2=-Q{H}^{-1}{G}_1{\alpha }_{11}+Q{\left(F^T\right)}^{-1}{G}_2{\alpha }_{12},$ (34)

由(33)式(34)式及KKT条件可以得到MV-TWSVM1的对偶问题(DMV-TWSVM1)

$\begin{array}{cc}\max & \frac{1}{2}{\alpha }_1^{T}M{\alpha }_1+e_2^T{\alpha }_1,\\ \text{s}\text{.t}\mathrm{.}& 0\le {\alpha }_1\le c_1\mathrm{,}\end{array}$ (35)

其中

$M=\left(\begin{array}{cc}{M}_1& M_2\\ M_3& M_4\end{array}\right),\mathrm{<mi>\; </mi>}{\alpha }_1=\left(\begin{array}{c}{\alpha }_{11}\\ {\alpha }_{12}\end{array}\right),\mathrm{<mi>\; </mi>}{c}_1=\left(\begin{array}{c}{c}_{11}\\ c_{12}\end{array}\right),$

$M_1=M_{11}^{T}H{M}_{11}+M_{13}^{T}P{M}_{13}-M_{11}^{T}F{M}_{13}-M_{13}^T{F}^T{M}_{11}-2G_1^T{M}_{11},$

$M_2=M_{12}^{T}H{M}_{12}+M_{14}^{T}P{M}_{14}-M_{12}^{T}F{M}_{14}-M_{14}^T{F}^T{M}_{12}-2G_2^T{M}_{12},$

$M_3=-M_{11}^{T}H{M}_{12}-M_{13}^{T}P{M}_{14}+M_{11}^{T}F{M}_{14}+M_{13}^T{F}^T{M}_{12}-2G_1^T{M}_{12},$

$M_4=-M_{12}^{T}H{M}_{11}-M_{14}^{T}P{M}_{13}+M_{12}^{T}F{M}_{13}+M_{14}^T{F}^T{M}_{11}-2G_2^T{M}_{13},$

$M_{11}=Q^{-1}{F}^{-1}{G}_1,M_{12}=Q^{-1}{F}^{-1}{G}_2,$

$M_{13}=Q{H}^{-1}{G}_1,M_{14}=Q{\left(F^T\right)}^{-1}{G}_2,$

同理，对MV-TWSVM2引入拉格朗日乘子并构建拉格朗日函数：

$\left(\left[\begin{array}{c}{B}_1^T\\ e_2^T\end{array}\right]\left[\begin{array}{cc}{B}_1& e_2\end{array}\right]+c_2{\gamma }_2\left[\begin{array}{c}{U}_1^T\\ e_3^T\end{array}\right]\left[\begin{array}{cc}{U}_1& e_3\end{array}\right]\right)\left[\begin{array}{c}{w}^{\left(21\right)}\\ b^{\left(21\right)}\end{array}\right]-c_2{\gamma }_2\left[\begin{array}{c}{U}_1^T\\ e_3^T\end{array}\right]\left[\begin{array}{cc}{U}_2& e_3\end{array}\right]\left[\begin{array}{c}{w}^{\left(22\right)}\\ b^{\left(22\right)}\end{array}\right]+{\alpha }_{21}\left[\begin{array}{c}{A}_1^T\\ e_1^T\end{array}\right]=0,$ (36)

$-c_2{\gamma }_2\left[\begin{array}{c}{U}_2^T\\ e_3^T\end{array}\right]\left[\begin{array}{cc}{U}_1& e_3\end{array}\right]\left[\begin{array}{c}{w}^{\left(21\right)}\\ b^{\left(21\right)}\end{array}\right]+\left(\left[\begin{array}{c}{B}_2^T\\ e_2^T\end{array}\right]\left[\begin{array}{cc}{B}_2& e_2\end{array}\right]+c_2{\gamma }_2\left[\begin{array}{c}{U}_2^T\\ e_3^T\end{array}\right]\left[\begin{array}{cc}{U}_2& e_3\end{array}\right]\right)\left[\begin{array}{c}{w}^{\left(22\right)}\\ b^{\left(22\right)}\end{array}\right]+\left[\begin{array}{c}{A}_2^T\\ e_1^T\end{array}\right]{\alpha }_{22}=0$ (37)

定义

$\begin{array}{l}X=G_1{}^T{G}_1+c_2{\gamma }_2{P}_1^T{P}_1,Y=-c_2{\gamma }_2{P}_1^T{P}_2,\\ R=G_2{}^T{G}_2+c_2{\gamma }_2{P}_2^T{P}_2,S=Y^{-1}X-R^{-1}{Y}^T,\\ v_1={[}^{w^{(21)}},v_2={[}^{w^{(22)}},\end{array}$ (38)

由(36) (37)和(38)可解得：

$v_1=S^{-1}{Y}^{-1}{H}_1{\alpha }_{21}+S^{-1}{R}^{-1}{H}_2{\alpha }_{22},$ (39)

$v_2=S{X}^{-1}{H}_1{\alpha }_{21}+S{\left(Y^T\right)}^{-1}{H}_2{\alpha }_{22},$ (40)

由(39)式(40)式及KKT条件可以得到MV-TWSVM2的对偶问题(DMV-TWSVM2)：

$\begin{array}{cc}\max & \frac{1}{2}{\alpha }_2^{T}N{\alpha }_2+e_1^T{\alpha }_2,\\ \text{s}\text{.t}\mathrm{.}& 0\le {\alpha }_2\le c_2\mathrm{,}\end{array}$ (41)

其中

$N=\left(\begin{array}{cc}{N}_1& N_2\\ N_3& N_4\end{array}\right),{\alpha }_2=\left(\begin{array}{c}{\alpha }_{21}\\ {\alpha }_{22}\end{array}\right),c_2=\left(\begin{array}{c}{c}_{21}\\ c_{22}\end{array}\right),$

$N_1=M_{21}^{T}X{M}_{21}+M_{23}^{T}R{M}_{23}-M_{21}^{T}Y{M}_{23}-M_{23}^T{Y}^T{M}_{21}-2G_1^T{M}_{21},$

$N_2=M_{22}^{T}X{M}_{22}+M_{24}^{T}R{M}_{24}-M_{22}^{T}Y{M}_{24}-M_{24}^T{Y}^T{M}_{22}-2G_2^T{M}_{22},$

$N_3=-M_{21}^{T}X{M}_{22}-M_{23}^{T}R{M}_{24}+M_{21}^{T}Y{M}_{24}+M_{23}^T{Y}^T{M}_{22}-2G_1^T{M}_{22},$

$N_4=-M_{22}^{T}X{M}_{21}-M_{24}^{T}R{M}_{23}+M_{22}^{T}Y{M}_{23}+M_{24}^T{Y}^T{M}_{21}-2G_2^T{M}_{23},$

$M_{21}=S^{-1}{Y}^{-1}{G}_1,M_{22}=S^{-1}{Y}^{-1}{G}_2,$

$M_{23}=S{X}^{-1}{G}_1,M_{24}=S{\left(Y^T\right)}^{-1}{G}_2,$

由上述过程可导出如下算法：

算法3.1：多视图双支持向量机半监督学习方法：

输入：训练集 $T$ ；

输出：决策函数 $f$ ；

1) 输入训练集 $T$ ， ${\gamma }_1\mathrm{,}{\gamma }_2\mathrm{<mo>\; >\; </mo>0}$ ，选择参数 $c_{11}\mathrm{,}{c}_{12}\mathrm{,}{c}_{21}\mathrm{,}{c}_{22}\mathrm{<mo>\; >\; </mo>0}$ ；

2) 计算(35)，(41)得到 ${\alpha }_1$ 和 ${\alpha }_2$ ；

3) 计算(33)，(34)，(39)，(40)得到 $u_1\mathrm{,}{u}_2\mathrm{,}{v}_1\mathrm{,}{v}_2$ ；

4) 由(30)，(38)得到 $\left(w^{\left(11\right)}\mathrm{,}{b}^{\left(11\right)}\right)\mathrm{,}\left(w^{\left(12\right)}\mathrm{,}{b}^{\left(12\right)}\right)\mathrm{,}\left(w^{\left(21\right)}\mathrm{,}{b}^{\left(21\right)}\right)\mathrm{,}\left(w^{\left(22\right)}\mathrm{,}{b}^{\left(22\right)}\right)$ ；

5) 得到决策函数。

$f\left(x\right)=\min \left\{\min \left|w^{\left(1i\right)T}x+b^{\left(1i\right)}\right|,\min \left|w^{\left(2i\right)T}x+b^{\left(2i\right)}\right|\right\},i=1,2.$

4. 数值实验

在本节中，将本文的方法MV-TWSVM与TWSVM进行比较。本文的数值结果是在内存4.00 GB，64位操作的Windows7系统中用软件MATLAB，R2014a运行得到的。

4.1. 人工数据

本节图1中，月牙型数据为视图1，由直线 $y=2x+3$ 和 $y=2x-3$ 生成的样本点加入白噪声得到的数据集为视图2。图中直线是用MV-TWSVM得到的两个视图下的分划线。可以看出分划线很好的表示出了数据的分布，并且有较高的准确率，视图1的准确率达到83.6759%，视图2的准确率达到99.3781%。

图1. 左图是视图1，右图是视图2。图中直线是MV-TWSVM计算人工数据集得到的分划超平面

4.2. UCI数据

在UCI数据上找了Australian，pima，German，spectf，parkinsons，breast六个数据集，表1是数据集的详细信息，其中数据Australian，pima，German选用了该数据的百分之三十进行数值实验。用本文提出的方法对六个数据集计算正确率，并与TWSVM进行比较，如表2。表中加粗的部分正确率较高。

表2是线性的TWSVM，MV-TWSVM对所有数据集计算的正确率，表格分为两部分，第一部分是TWSVM方法，第二部分是本文的方法，其中第一表示TWSVM方法下的正确率，第二列表示在视图1下的正确率，第三列表示在视图2下的正确率，第四列表示原始数据的正确率。奇数行表示将数据集前一半作为视图1，剩余部分作为视图二；偶数行表示将数据集随机分成两部分，一部分作为视图1，另一部分作为视图2。表中可以看出数据spectf，Australian，pima在本文提出的方法下正确率较高。

当我们选择不同比例无标签的数据点时，正确率也会不同，如表3。表3分别取了50%，80%，90%，无标签的数据点，计算正确率和耗时。从表中可以看出，数据集spectf，parkinsons，breast，Pim-a，German，的无标签点增多时，在本文的方法下正确率增大。

此外，本节还对MV-TWSVM与TWSVM进行了时间耗时比较，如图2，数据集仍然是Australian，pima，German，spectf，parkinsons，breast 6个数据集，从图中可以看出，MV-TWSVM比TWSVM耗时少很多，从而说明MV-TWSVM对数据降维事实相符。

表1. 数据集的详细信息

表2. 线性的TWSVM，MV-TWSVM对所有数据集计算的正确率

^*是指用该数据集的33%进行数值实验。黑体表示几个方法中最高的正确率。

表3. MV-TWSVM 对不同比率的无标签的数据集计算的正确率

^*是指用该数据集的33%进行数值实验。黑体表示几个方法中最高的正确率。

图2. 不同的特征下，TWSVM与MV-TWSVM的训练时间之间的比较

5. 结论与展望

本文将双支持向量机应用到多视图半监督学习中，将数据分成两个视图进行描述，降低了数据的维数，减少了计算的复杂度，有效地缩短了运行时间。对于不同的数据，多视图双支持向量机半监督学习方法取得了较好的正确率。

进一步，我们将研究如何选择不同的核函数将线性划分推广到非线性划分。另外，现有的多视图学习方法实际上是双视图，如何推广到更多视图上的研究也是一个需要考虑的问题。

文章引用

姚瑞. 基于多视图双支持向量机半监督学习机
Semi-Supervised Learning Machine Based on Multi-View Twin Support Vector Machine[J]. 运筹与模糊学, 2019, 09(02): 177-188. https://doi.org/10.12677/ORF.2019.92021

参考文献