一种新的支持向量机半监督增量学习算法外文翻译资料

 2022-12-19 17:41:52

英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

一种新的支持向量机半监督增量学习算法

摘要

半监督学习在数据挖掘应用中尤为重要，因为它可以利用大量的未标记数据来训练高质量的学习模型。半监督支持向量机(S3VM)是一种功能强大的半监督学习模型。然而，S3VM方法计算量大、不具有凸性，严重影响了其在大规模数据中的应用。虽然针对S3VM提出了几种学习算法，但如何扩展S3VM仍然是一个有待解决的问题。为了解决这一难题，本文提出了一种新的基于路径跟踪技术的增量学习算法，该算法在凸差(DC)规划的框架下对S3VM(IL-S3VM)进行扩展。传统的基于DC规划的算法需要多个外循环，不适合增量学习，传统的路径跟踪算法局限于凸问题。我们的基于路径跟踪技术的新的IL-S3VM算法可以直接更新S3VM的解，使其在一个外循环内收敛到局部最小值，从而实现高效的增量学习。更重要的是，我们为我们的算法提供了有限收敛性分析。据我们所知，我们的新IL-S3VM算法是第一个有效的路径跟踪算法用于解决非凸问题(即S3VM)且具有局部最小收敛保证。在多种基准数据集上的实验结果不仅证实了IL-S3VM的有限收敛性，而且与现有的批处理和增量学习算法相比，计算时间大大缩短，同时保持了相似的泛化性能。

  1. 介绍

在真实的数据挖掘应用程序中，标记样本是一项昂贵的任务，因为它通常需要熟练或专业的人工代理。例如，医学图像分析[9]通常需要一个经验丰富的放射科医生来标记大量的医学图像，这是相当昂贵的。然而，很多应用程序都有大量的未标记数据，但是标记样本有限，使得监督学习模型不能达到满意的性能。为了解决这一问题，提出了许多半监督学习方法，包括半监督支持向量机(S3VM)[6]，利用标记和非标记数据来训练高质量的学习模型。

在半监督学习方法中，S3VM是最强大的一种。S3VM的目标是通过最大限度地提高标记和未标记样品的间隔来学习低密度分离器。给定由标记数据集L = {(x1,y1)，···，(xl,yl)}和未标记数据集U = {xl 1，···，xl u}组成的训练数据集，其中xiisin;Rd, yiisin;{ 1，-1}。让f (xi) =lang;w,ϕ(xi)rang; b表示分隔超平面,S3VM[8]解决了以下问题:

(1)

其中ht(·)= max(0, tminus;·)是铰链损耗，ht(|·|)是对称铰链损耗，C和C*是预定义的参数。特别是对于C*=0时，问题(1)退化为标准的凸SVM。对于C* gt; 0时, 问题(1)是非凸的，因为对称的铰链损耗会影响边缘内未标记的数据。本质上，S3VM解决了一个非凸优化问题，它比标准SVM等凸问题的求解更为困难。

S3VM作为一种重要的半监督学习模型，引起了数据挖掘和机器学习领域的广泛关注。为了解决S3VM问题，提出了多种学习算法，主要被分为两大类：凸差(DC)规划算法和梯度算法。具体来说，Fung和Mangasarian[12]、Collobert等人的[8]、Wang等人的[27]基于DC规划，利用CCCP求解S3VM。注意，传统的基于DC规划的算法只能在批处理学习模式下工作，因为这些方法必须通过多个外部循环来更新解决方案，如图1(a)所示。Chapelle和Zien [7]， Chapelle等人[4]和Chapelle[3]采用光滑优化方法逼近原公式(1)，然后采用梯度下降法或牛顿法求解光滑优化问题。由于直接求解问题(1)，CCCP算法是求解S3VM最常用的算法。然而，由于批量学习算法的存在，上述算法都具有较高的计算成本。综上所述，S3VM方法计算量大且不具有凸性，严重阻碍了其在大规模数据中的应用。正如在[6]中指出的，扩展S3VM仍然是一个悬而未决的问题。

增量学习(也称为在线学习)是一种重要的大规模学习方法。已有几种增量学习算法用于求解SVM相关模型，如[16,21,23]。本质上，这些算法通过维护KKT条件[18]，根据跟随算法的路径更新解决方案[17,26]。除了路径跟随算法外，Ertekin等人提出了一种求解非凸问题的在线学习算法。然而，没有理论保证解的收敛性。Emara等人[10]提出了一种基于分支定界技术[5]的增量S3VM算法。然而，[10]方法需要对模型进行多次训练，效率不高。由于路径跟踪技术的高效性和收敛性保证，本文重点研究了路径跟踪技术。

然而，据我们所知，现有的基于路径跟踪技术的增量SVM算法[16,21,23]都局限于凸优化。如前所述，S3VM本质上解决了一个非凸问题。对于非凸问题，满足KKT条件的解只能保证为鞍点，不能保证为局部或全局最小[1]。因此，将现有的路径跟随算法[16,21,23]扩展到非凸问题并保证解是局部或全局的极小值并不是一件简单的事情。

针对上述问题，在DC规划下，提出了一种基于路径跟踪技术的S3VM高效增量学习算法(IL-S3VM)。如前所述，传统的基于DC规划的算法需要多个外循环，不适合增量学习，传统的路径跟随算法仅限于凸问题。我们新的基于路径跟踪技术的IL-S3VM算法可以直接更新S3VM的解，使其在一个外循环内收敛到局部最小值(如图1(b)所示)，从而实现高效的增量学习。更重要的是，我们为IL-S3VM提供了有限收敛分析。在多种基准数据集上的实验结果不仅证实了IL-S3VM的有限收敛性，而且与现有的批处理和增量学习算法相比，计算时间大大缩短，同时保持了相似的泛化性能。

贡献：本文的主要贡献总结如下:

(1)据我们所知，我们的IL-S3VM是第一个基于路径跟踪技术解决非凸问题(即S3VM)且具有局部最小收敛保证的算法。

(2)我们的理论结果表明，在不同的条件下，IL-S3VM的能量函数单调递减甚至递增，突破了传统的凸问题路径跟踪算法的理论结果，即能量函数仅单调递减[14-16]。

组织：本文的其余部分组织如下。第二节给出了S3VM的DC规划。在第三部分，我们提出了我们的IL-S3VM算法。第4节对IL-S3VM进行了分析。第五部分给出了实验结果。最后，在第六部分对全文进行了总结。

  1. S3VM DC形式

我们首先简要回顾了S3VM的DC规划及其算法。在此基础上，给出了由S3VM导出的凸问题对偶公式的KKT条件。

    1. 重温DC规划

如[19]所述，DC规划的一般公式为:

(2)

其中o、v、cj为实值凸函数，dj为仿射函数。对于DC规划问题(2)，CCCP算法[28]是一种广泛使用的寻找局部极小拐点的算法。假设nabla;v (w)的梯度表示是nabla;v (w(l))。CCCP的想法是在一个解决方案的迭代中线性化问题(2)中凹的部分，使得o(w)minus;wTnabla;v(w(l))在w上是凸的。CCCP算法解决了一系列定义的凸规划问题(3)通过线性化凹部分,直到收敛。本文将式(3)称为凸内循环(CIL)问题:

(3)

    1. S3VM的DC规划

为了将S3VM(1)重新表示为DC规划问题(2)，我们将未标记的数据集U加倍，并创建一个人工标记的数据集U= {(xl 1， 1)，···，(xl u， 1) (xl u 1，-1)，···，(xl 2times;u，-1)}。因此，根据式(2)中的DC规划，可以将原S3VM式(1)改写为式(4)。必须指出的是，(4)与[8]中证明的原式(1)是等价的。

为了推导出CIL问题(4),我们计算[w,b]nabla;v (w, b)如下:

因此，我们可以根据公式(3)得到(4)的原始CIL问题。我们直接将对应的对偶CIL问题显示如下[8]:

(6)

H是半正定矩阵，Hj = K (xi, xj) =lang;ϕ(xi),ϕ(xj)rang;，1le;i, jle;l 2times;u, K (xi, xj)是内核函数，和的定义如下:
    1. 对偶CIL问题的KKT条件

根据凸优化理论[1]，对偶CIL问题(6)的求解方法为:

其中b 为拉格朗日乘子。此外，从KKT定理[18]出发，w的一阶导数可得到以下KKT条件:

因此,根据gi在式(11)中的值，我们将扩展训练样本集Lcup;将其划分为集合pi;= (M，E， O)
  1. 新的增量学习算法

在本节中，我们首先介绍了增量S3VM算法的原理(即IL-S3VM)，然后给出了IL-S3VM算法的细节。最后，我们讨论了我们的IL-S3VM和现有的增量SVM算法的区别。

    1. 我们的IL-S3VM的准则

针对S3VM问题，已经提出了多种基于DC框架的算法，但这些算法只能进行批量学习。具体地说,当这些算法应用于解决S3VM，根据之前讨论的CCCP算法,一般单独解决CIL问题和更新mu;，即算法需要多个外循环,直到mu;收敛(见图1 (a))。我们可以对第一个循环使用增量学习算法。然而，对于i gt; 1的第i个循环，只能使用批处理求解器，这对于在线场景是低效的。因此, 设计增量学习算法是非常可取用来同时解决CIL问题和更新mu;(见图1 (b))。注意,尽管[11]的方法被设计来处理在线学习对于一个非凸问题,他们在整个更新过程中固定mu;调整。因此，没有理论保证解收敛到局部极小值。

在本文中,我们将解决CIL问题和更新mu;同时,同时保证解决方案的收敛到局部最小值。S3VM增量学习期间,mu;i可能改变的值从0到C从Clowast;到0导致双重CIL问题(6)的变化

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[19815]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章