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

基于遗忘因子的支持向量机的统计特性

摘要

引入遗忘因子可以使得支持向量机自适应地解决时变问题。然而，在早期工作中，即使是对于简单的线性可分离问题，所提出的指数遗忘因子也不能确保平均广义误差的收敛。为了确保收敛性，我们提出一个随时间衰减的阶乘的遗忘因子。我们使用简单的一维问题近似导出阶乘遗忘因子的平均广义误差以及指数遗忘因子的平均广义误差，并通过计算机模拟验证我们的理论。最后，我们证明了我们的理论可以拓展到任意类型的基于遗忘因子的简单线性可分例上。

关键词：SVM；学习曲线，渐进分析

介绍

支持向量机（SVM）是几十年来最成功的学习分类之一(Cristianini amp; Shawe-Taylor, 2000; Schouml;lkopf, Burges amp; Smola,1998; Smola, Bartlett, Schouml;lkopf amp; Schuurmans, 2000; Vapnik, 1995)。一开始，原始的SVM同等地对待所有例子，因此，它不能被应用在时变的环境中。此外，由于训练SVM是二次规划问题（QP），其系数的数目等于被训练的目标数目，所以标准的QP方法对于大数据集合是不可行的。

解决这些困难的方法之一是在线方法，其中一些训练样本被丢弃（Cauwenberghs amp; Poggio,2001;Ikeda amp; Yamasaki,2007;Klinkenberg amp; Joachims, 2000；Takemasa amp; Ikeda, 2011）。在这种方法中，我们可以决定样本的数量（使用启发式），但不能自由设置每个样本的权重。换句话说，样本的权重的值只能假设为零或一。

我们可以通过在自适应滤波器（Haykin, 1996）的RLS算法中引入遗忘因子（Liu, Zhang amp; Zhang, 2003）放松这个限制，其中非整数权重自然地赋给样本，以用于选择滤波器系数。尽管已经提出了用于RLS算法的遗忘因子的许多变体（Montazeri amp; Duhamel, 1995），但是它们基本上使用指数衰减遗忘因子；即每个样本具有作为其权重，其中表示遗忘因子，表示遗忘因子生成时间。我们称之为指数遗忘因子（EFF），并在我们早期的工作中（Funaya，Nomura amp; Ikeda，2009）在一个简单的案例中进行了分析。

最初，我们轻易地选择指数遗忘因子，是因为它通常在信号处理文献中提及。在适应时变问题方面，指数遗忘因子对于简单情况能得到有效的结果，但是渐近平均广义误差（AGE）不会收敛到零。虽然我们可以选择一个EFF，使得平均广义误差任意小，但还是应该更加注重遗忘因子的收敛性。因此，我们为相同的问题引入阶乘遗忘因子（FFF），在考虑与以前工作中相同简单的实例（Funaya et al., 2009）中，随着样本数量增加到无穷大，结果证明其平均泛化误差倾向于零。 本文的概述如下：在第2节中，我们详细阐述了具有遗忘因子（SVM-FF）的SVM，包括EFF和FFF两种情况。在第3节中，介绍了基于具有理想的几何特性的v-SVM算法（Schouml;lkopf，Smola，Williamson amp; Bartlett，2000）来分析的简单问题。第4节中，我们导出算法在渐近状态下的泛化性能。在第5节中，给出了通过计算机模拟的验证。最后，我们在第6节中讨论并提出结论。

具有遗忘因子的SVM

2.1. 指数遗忘因子（EFF）

该SVM最初被用于作为为学习机器输入向量映射到对应的特征矢量，并用最佳超平面确定一个边缘将它们进行分类（ Cortes amp; Vapnik，1995）。然而，我们使用线性内核（具有与输入空间相同的特征空间）和具有均匀超平面的v-SVM（其中标准与边际最大化中的标准略有不同）。这些使得算法的分析称为可能，类似于Ikeda和Aoishi（2005）进行的分析软边际效应的算法。

给定一组数目位N的例子，其中xi是输入，yi是相应的标签，v-SVM具有均匀超平面，被表示为：

(1)

其中，w是超平面的系数向量，是软边缘的松弛变量，C是确定松弛度的常数，(Ikeda amp; Aoishi, 2005; Schouml;lkopf et al., 2000).

在用于自适应滤波器的RLS算法中，每次的平方误差呈指数衰减。也就是说，在第N次的平方误差的和定义为：

(2)

其中表示样本i的误差并且0 lt;lambda;lt;1是一个称为遗忘因子的常数。我们将这个想法引入nu;-SVM并给松弛变量一个指数衰减的权重。然后，具有遗忘因子（SVM-FF）的SVM被表示为:

(3)

1. 的对偶问题很容易求出，

(4)

其中是拉格朗日乘子。

注意：RLS-SVM算法的惩罚函数(Liu et al.,2003)是

(5)

其中包括了平方松弛变量，这导致问题变为线性等式，而不是QP问题。我们的FF也可以以相同的方式映入到原始SVM中。

即使对于线性可分离问题，也不能确保AGE的渐近收敛。为此，我们用阶乘遗忘因子(FFF)替换EFF，1/(N-i 1)，以便于让FF平方和发散，FF的简单和收敛。用在EFF案例中相同的方法，我们可以得出对偶问题：

(6)

3 问题描述

3.1. SVM-FF的几何

在(4)中要最小化的损耗函数是系数向量w的范数。因此，我们考虑约束w时应该适度。包含所有给定点的最小凸集称为点的凸包。条件是任何都是非负的，并且它们的和是一，这导致权重向量w包含于凸包中。附加条件是每个具有上限C/(N-i 1)减少其中w可以存在的面积.我们可以称这个由(4)导出的区域叫缩减凸包。

Bennett 和Bredensteiner (2000)首次指出v-SVM的解和缩减凸包(RCH)之间的关系，当他们考虑不均匀的分离超平面时，出现了两个RCH，正如Fig.2中所示两个RCH是一条线。Ikeda和Aoishi(2005)增加了均匀超平面的假设，并显示 nu;-SVM解是在RCH中最接近原点的点。感谢这个简单的几何图形，在C是任何的上边带的情况下，软边缘参数的影响已定量阐明 ，如(图1)。

在SVM-FF的案例中，任何都有一个不同的上边界。然而，Ikeda和Aoishi(2005)推导AGE的方法也可以用在这种情况下，如下一小节所示。

3.2. 问题制定

现在我们用一个简单的问题分析SVM-FF，这与Ikeda和Aoishi(2005)中描述的几乎相同。我们假设N个输入和类标签，以相等的该路从两个类（一正一负）独立的生成，他们可以通过超平面线性地分离。我们还假设每个类的分布是任意的，除了在分离超平面的附近，两个类均匀且相同地分布。图2示出在原点处可线性分离的一维问题。均匀的重新标记，从几何和数学角度来看是方便的，这被称为“提升”(图3)(Ikeda amp; Aoishi, 2005)。

因为 ，都在正侧（图4）。在硬边缘的情况下形成凸包，而在软边际和遗忘因子的作用下它们形成缩减凸包。如图6的右图中所示，在几何上，这很明显，SVM的泛化误差出现在处，假设泛化误差很小。因此，我们可以通过导出theta;的分布来计算泛化误差。

接下来，我们通过稀疏化来修改问题。由于SVM的解是稀疏的，远离分类超平面的样本不对应具有高概率的解。因此，我们将两个分布映射到均匀分布的半圆中(5)，给出以下修改后的问题：我们假设有N个输入， 独立地均匀地选自，其中是一个m维度单位球体。并且，向量，均匀分布在 ：

(7)

(8)

(9)

在这种情况下，对于新的输入x， 估计 误预测输出的概率，称为广义误差或预测误差，写为theta;/pi;，其中theta;是两者之间的夹角 和 。平均广义误差被定义为：在给定样本中，对于一个新的输入，估计误预测输出的平均概率。在下面的几节中，我们得到一维情况下的SVM的平均广义误差（m = 1）在N→infin;的渐近极限.

在一维空间中，示例的缩小凸包中的最接近原点的点是最靠近水平轴的两个点 和 的中点。如果我们知道 和 的角度分布，我们可以导出自SVM解以来的平均广义误差 写为 。，然后，平均泛化误差写作的平均数。我们可以假设，解遵循相同的分布，因为样本是均匀分布的。因此，我们只考虑因此，我们仅考虑半圆的左半边（图6中的第二象限）。这里，让我们用表示距离左边缘L第i近的样本的角度。表示的拉格朗日乘子，Fiisin;{lambda;Nminus;ti,1/(N minus;ti 1)}表示ti时刻（第i个样本生成的时刻）的遗忘因子。然后，通过求解以下优化问题来获得约束下左半部分中的解：

（10）

（11）

（12）

问题（10）的解可以写为：

（13）

其中n是支持向量的非零的。通过解方程（10）-（12）我们有：

（14）

这个解决方案很容易获得，因为支持向量可以从最小的角度，由于简单问题的一维性质。权重为正的样本称为支持向量（SVs）。

4. SVM-FF的统计特性

4.1. 不同SVM的典型学习曲线

在分析之前，我们先回顾几个SVM学习曲线的典型属性，在原始SVM和v-SVM的情况下，随着样本数量的增加，泛化误差减小，并在无噪声情况下收敛到零。然而，在SVM-FF情况下，这个结果就不这么小了，原因如下两个：（1）由于EFF的影响（假设当N趋于无穷的时候几乎所有的都接近于0），（2）随着N的增加所有的都减小。

因此，繁华无耻不会收敛到0。相反，随着FFF收敛到0，这也就意味着它的学习曲线也在概率上收敛到0。

在图8中，我们可以看到EFF的学习曲线收敛到一个恒定的取决于EFF大小的值，而其他的学习曲线似乎都趋近于0。具有FFF的SVM的学习曲线比具有EFF的SVM的学习曲线慢，但是两个AGE随着样本数量的增加而减小。这个特征是很好的，因为在学习曲线收敛到0的情况下，却没有失去适应时变问题的能力。

我们修改以往的成果，用EFF分析SVM(Funaya et al., 2009)。在这项工作中，我们假设有序的样本的角度之间的具有独立性，其中具有较高指数的角度包含所有具有较小指数的角度。相反，下面的原始工作中，如图7中所示，我们假设没有角度包含其他的角度。这简化了分析，并且产生了更好的结果，特别是在使用FFF的情况下。

首先，我们推导出SV左侧中心的概率分布，，对于任何大小的样本数据N。由于遵循相同的分布，我们可以直接推导出的AGE。由于用于指数和阶乘遗忘因子的平均一般化误差的推导过程是类似的，为了简单起见，我们使用一个把遗忘因子记作的广义公式的方法。注意，，且对立与i。因此，序数最小的角度，记作，是独立与遗忘因子的。两个变量的乘积的期望可以写作：

E[F_ii]=E[F_i]E[_i]. (15)

因此，的期望可以推导为：

(16)

现在，因为相对于整个(16)的第二项本身被认为是很小的，我们可以只用Fi替换第二项的系数。因此，我们有：

(17)

此外，的期望是：

(18)

其方差为：

V[theta;L] (19)

= (20)

= (21)

有了EFF和FFF，所有的SV与pi;相比都非常小，以便于所有的都独立同分布与。的分布可以通过考虑所有落入区域[]的其他样本的概率来获得，记作：

(22)

区分(22)相对与给出分布：

(23)

对于无穷大的N，这与参数的指数分布相同。因此我们有：

(24)

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

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