半监督直推式支持向量机在个性化推荐研究中的应用

(1)直推式支持向量机算法

直推式支持向量机(Transductive Support Vector Machine，TSVM)是基于低密度分割假设的最大间隔分类方法。与传统的支持向量机非常类似，其寻找具有最大间隔的分类超平面作为最优分类超平面，同时考虑无标签数据和有标签数据来训练分类模型。TSVM算法的详细概念可以参考文献［162］。

假设一组独立同分布的有标签样本：

以及无标签样本：

在一般情况下，TSVM的学习过程可以认为是求解下面最优化问题的过程：

其中，C1和C2由用户设定，用于控制对错分样本的惩罚。C2为训练过程中无标签数据的“影响因子”；C2ξj被称为第j个无标签样本在目标函数中的“影响项”。

TSVM的训练过程如下所述。

步骤一：设置参数C1与C2，采用归纳学习方式训练有标签的样本，并得到一个初始分类器。设定无标记样本中正类样本的估计个数N。

步骤二：利用初始分类器对所有无标签样本计算其决策函数值。将决策函数值比较大的前N个无标签样本标记为正类样本，并且把剩下的无标签样本标记为负类样本。设定Ctemp为一个临时影响因子。(www.xing528.com)

步骤三：在标记的所有样本上重新训练SVM模型。对于新产生的分类器，根据使目标函数(6.3)下降尽可能大的原则，交换每一对样本的标签，直到没有满足交换条件的样本，否则重复该过程。

步骤四：对Ctemp的值进行均匀增大，并返回步骤三。当Ctemp≥C2时，算法终止，返回所有未标记样本的标签。

(2)直推式支持向量机分析

TSVM能得到比传统归纳式学习更好的性能，但也存在一些缺点。例如目标函数是非凸的二次规划问题(称为“非凸”问题)，导致了求解的难度；参数N必须预先设定(称为“预设N”问题)；并且也没有结论得出对无标签数据利用得越多，那么对提升分类器的性能就越有效。事实上，因为标签由分类器产生，可能将错误的标签数据加入训练样本中，错误的标签对分类器性能的影响很大(称为“无标签数据利用”问题)。

对于“非凸”问题，在过去十几年，学者们采用了很多方法试图解决这个关键问题。Chapelle等［163］提出结合平滑损失函数的半监督分类，并采用梯度下降的方法在低密度区域中寻找决策分类面，然而这样的近似方法不能满足精度的需求［164］。Chapelle等［165］提出了另外一种方法称为分支定界法，来寻找精确的、全局最优解。但是，因为这种方法涉及大规模计算，所以它只适合小规模样本问题。为了处理大规模数据问题，文献［60］提出了大规模TSVM，也是第一次将高度可扩展的算法应用到TSVM中，被称为改进的TSVM“凹-凸”算法。

对于预设N问题，一些TSVM改进版被提出［166，167］。其中，文献［166］提出的改进版被称为PTSVM。该算法根据最大化决策函数值的绝对值，同时标记一个正类样本和一个负类样本。虽然该方法提升了TSVM的性能，但是该方法只适合小规模的无标记样本集。因为对于大规模的无标记样本集，需要频繁的标记和交换标签，将导致算法复杂度急剧升高。文献［167］为了解决遥感问题，通过对无标记样本进行加权并加入时间戳，提出了一种新的TSVM。

为了解决无标签样本利用问题，周志华等［168］指出利用无标记数据可能使得分类器的性能下降，并且与只采用有标签的数据相比，泛化能力更糟。他们提出了S3VM-us方法，该方法采用启发式聚类来选择无标记样本从而降低分类器性能下降的可能性。Settles［169］在文献中表明，主动学习和半监督学习是从相反的方面来解决无标记样本利用问题。半监督学习是从它所知道的无标记的样本信息来解决标记问题；而主动学习从另外一方面来解决。主动学习是通过一定的策略选择信息量最大的样本进行查询，并提交给领域专家进行标注。主动学习的目标是获得尽可能小并且对分类器提升最大的样本集，从而降低获得样本的代价。因此，结合主动学习与半监督学习可以更好地对无标记样本进行利用。