首页 科技正文

大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读

admin 科技 2021-09-12 272 2

摘要

本文提出了一种用于训练支持向量机的新算法:序列最小优化算法(SMO)。训练支持向量机需要解决非常大的二次计划(QP)优化问题。SMO 将这个大的 QP 问题分解为一系列最小的 QP 问题。这些小的 QP 问题可以通过剖析来解决,从而避免了将耗时的数值 QP 优化用作内部循环。SMO 所需的内存量与训练集巨细成线性关系,这使 SMO 可以处置非常大的训练集。由于避免了矩阵盘算,因此对于种种测试问题,SMO 随训练集巨细在线性和二次方之间缩放,而尺度分块 SVM 算法随训练集巨细在线性和三次方之间缩放。SMO 的盘算时间主要由 SVM 评估决议,因此 SMO 对于线性 SVM 和希罕数据集最快。在现实天下的希罕数据集上,SMO 的速率可以比分块算法快 1000 倍以上。

研究靠山

在已往的几年中,学界对支持向量机(SVM)的研究兴趣激增,因其在诸如手写字符识别、面部检测、行人检测和文本分类等许多问题上均具有优越的泛化性能。然而,现有的 SVM 训练算法速率慢、内存开销大,且实现过于庞大和难题,这使得 SVM 的使用仍然仅限于一小部门研究人员。因此,为了提高 SVM 的实用性,亟需一种更好的训练算法。

问题形貌

SVM 的训练本质上是求解一个二次计划(QP)问题,其拉格朗日对偶表示如下:

当知足如下 KKT 条件时,该 QP 问题得以解决:

其中,\(\vec x_i\) 是第 i 个训练样本,\(y_i\) 是第 i 个训练样本的真实标签,\(u_i\) 是第 i 个训练样本的输出,\(α_i\) 第 i 个训练样本对应的拉格朗日乘数,\(C\) 是责罚参数。

上式中的二次形式涉及一个矩阵,该矩阵的元素数目即是训练样本数目的平方。一旦样本数目稍大,该矩阵将难以存入内存,因而通过尺度的 QP 手艺无法轻松解决由 SVM 引出的 QP 问题。

本文所讨论的内容即,作者所提出的训练算法是若何解决上述问题的。

研究现状

Vapnik[2] 形貌了一种“分块”解决 SVM QP 的方式,将整个 QP 问题分解为多个 QP 子问题,其最终目的是识别所有非零拉格朗日乘数并抛弃所有零拉格朗日乘数。每个 QP 子问题都使用先前子问题的效果初始化。在最后一步,已经确定了整个非零拉格朗日乘数集,从而解决了整个 QP 问题。

分块处置将矩阵的巨细从训练样本数的平方,削减到约莫为非零拉格朗日乘数的数目的平方。然而,分块算法仍然不能解决大规模的训练问题,由于纵然这个缩小的矩阵也无法放入内存中。

1997年,Osuna 等人[3] 从理论上证实,大的 QP 问题可以分解为一系列较小的 QP 子问题。基于此,论文建议在每一步中添加一个样本,然后去除一个样本,这样每个 QP 子问题将保持一个恒定巨细的矩阵,从而允许对随便巨细的数据集举行训练。但显然这是低效的,由于它使用整个数值 QP 优化步骤来仅仅使一个训练样本遵守 KKT 条件。

更主要的是,所有这些方式都需要数值 QP 解算器,而众所周知,数值 QP 存在精度问题。

解决方式

作者在论文中提出的序列最小优化算法(SMO)是一种简朴快速求解 SVM 引出的 QP 问题的方式,它将整个 QP 问题分解为多个 QP 子问题,通过 Osuna[3] 的定理保证收敛。

创新点与优势

不像以往的算法,SMO 在每一步仅选择两个拉格朗日乘数举行团结优化。其优势在于,两个拉格朗日乘数的优化可以通过剖析方式完成,避免了数值 QP 优化,盘算更快、更准确。此外,由于 SMO 完全不需要分外的矩阵存储,纵然大规模的训练问题也可以在个人电脑的内存中运行。下图直观地说明晰 SMO 与以往算法的区别。

图中,每种算法均展示了三个训练轮次。水平细线代表训练集,粗块代表本轮中被优化的拉格朗日乘数。对于分块算法,每轮添加牢固数目的样本,而为零的拉格朗日乘数被抛弃。因此,每轮的训练样本数目趋于增添。对于Osuna的算法,每轮都市优化牢固数目的样本,由于添加和删除的样本数目相同。对于SMO,每轮都仅对两个样本举行剖析优化,因此每轮都非常快。

实现历程

SMO 由两个部门组成:一种求解两个拉格朗日乘数的剖析方式,以及一种选摘要优化的乘数的启发式方式。

求解两个拉格朗日乘数的剖析方式

为了求解两个拉格朗日乘数,SMO 首先盘算这些乘数的约束,然后求解约束最小值。如下图所示,有界约束使拉格朗日乘数位于一个框内,而线性相等约束使拉格朗日乘数位于对角线上。 因此,目的函数的约束最小值必须位于对角线段上。

大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第1张

在实现上,假设当前为第 \(k\) 轮,使用剖析法盘算乘数 \(α_1^{(k)}\)\(α_2^{(k)}\) 的最优解并更新至 \(α_1^{(k+1)}\)\(α_2^{(k+1)}\)\(\vec α\) 中的其他乘数稳定,获得 \(\vec α^{(k+1)}\),然后更新阈值 \(b^{(k+1)}\) 以及误差 $E_i^{(k+1)} $。详细盘算历程如下:

  1. 盘算 \(α_2^{(k+1)}\) 的取值局限 \([L, H]\),其中

    大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第2张
  2. 求得最优解\(α_1^{(k+1)}\)\(α_2^{(k+1)}\)\(b^{(k+1)}\)

    大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第3张

    连系 \(α_2^{(k+1)}\) 的取值局限,可得

    大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第4张

    \(α_2^{(k+1)}\) 可求得 \(α_1^{(k+1)}\)

    大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第5张

    之后更新阈值 \(b\)

    大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第6张
  3. 更新 \(E_i\) 的值

    大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第7张

选摘要优化的乘数的启发式方式

第一个乘数的选择称为外循环。首先遍历整个样本集,选择违反 KKT 条件的 \(α_i\) 作为第一个乘数,遍历完整个样本集后,遍历非界限样本集 \(0<α_i<C\) 中违反 KKT 条件的 \(α_i\) 作为第一个乘数。遍历完非界限样本集后,再次回到遍历整个样本集中寻找,即在整个样本集与非界限样本集上往返切换。直到遍历整个样本集后,没有违反 KKT 条件的 \(α_i\),则退出。

第二个乘数的选择称为内循环。选择的依据是最大化团结优化历程中接纳的步长,而 SMO 通过 \(|E_1−E_2|\) 来近似步长,为此需要为训练集中的每个非界限样本保留一个缓存的误差值 \(E_i\)

实验评估

作者对比尺度分块 SVM 学习算法,对 SMO 算法举行了一系列基准测试。

实验平台

两种算法都以 C++ 编写,使用 Microsoft 的 Visual C++ 5.0 编译器,且都在运行 Windows NT 4 的 266 MHz Pentium II 处置器上运行。

实验设置

如 Burges[4] 的建议,分块算法使用投影共轭梯度算法[5]作为 QP 解算器,并使用启发式方式来设置住手阈值[1]。为了确保分块算法和 SMO 算法到达相同的精度,若是输出与其准确值相差 \(10^{-3}\) 以上,则两种算法都市将该样本标识为违反 KKT 条件。

实验方式

作者在收入展望义务、网页分类义务和两个差别的人工数据集上对 SMO 算法举行了测试,研究算法的时间性能以及数据希罕性对运算速率的影响。以下表中列出的所有时间均以 CPU 秒为单元。

收入展望

用于测试 SMO 速率的第一个数据集是 UCI 的 *** 家庭普查数据集,共有 32562 个样本,包罗 14 个属性。SVM 的义务是展望该家庭的收入是否跨越 50,000 美元。针对该问题训练了两种差别的 SVM:线性 SVM 和方差为 10 的高斯SVM。

下表显示了在 *** 数据集上,使用 SMO 算法和分块算法训练线性 SVM 的时间。

大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第8张

通过拟合训练时间与训练集巨细的对数-对数图,得出 SMO 的训练时间规模为 ~\(N^{1.9}\),而分块算法为 ~\(N^{3.1}\)。因此,SMO将对于该问题的履历缩放比例优化了至少一个数目级。

使用 SMO 算法和分块算法训练高斯 SVM 的时间如下表所示:

大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第9张

SMO 算法对于非线性 SVM 比线性 SVM 慢,这是由于时间开销主要由 SVM 的评估决议。这里,SMO 的训练时间规模为 ~\(N^{2.1}\),而分块算法为 ~\(N^{2.9}\)。同样,SMO 比分块算法约莫快一个数目级。

网页分类

SMO 的第二项测试是对网页举行分类。训练集包罗 49749 个网页,从每个网页中提取了 300 个希罕的二进制关键字属性。在此问题上尝试了两种差别的 SVM:线性 SVM 和方差为 10 的高斯 SVM。

使用 SMO 算法和分块算法训练线性 SVM 的时间如下表所示:

大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第10张

对于该数据集上的线性 SVM,SMO 的训练时间规模为 ~\(N^{1.6}\),而分块算法为 ~\(N^{2.5}\)。该实验是 SMO 在盘算时间上优于分块算法的另一个例子。

使用 SMO 算法和分块算法训练高斯 SVM 的时间如下表所示:

大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第11张

对于该数据集上的非线性 SVM,SMO 的训练时间规模为 ~\(N^{1.7}\),而分块算法为 ~\(N^{2.0}\)。在这种情形下,SMO 比分块算法快 2~6 倍。

线性可分数据集

作者还在人工天生的数据集上对 SMO 举行了测试,以探索 SMO 在极端情形下的性能。

第一个人工数据集是完全线性可分离的数据集,输入数据是随机二进制 300 维向量。这里用线性 SVM 拟合此数据集。

使用 SMO 算法和分块算法训练线性 SVM 的时间如下表所示:

大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第12张

SMO 的训练时间规模为 ~\(N\),较分块算法的 ~\(N^{1.2}\) 稍好。

此外,还可以在此简朴数据集上丈量行使希罕点积而获得的SMO算法和分块算法的加速。相同的数据集在使用和不使用希罕点乘积代码的情形下都举行了测试。

希罕/非希罕实验的效果如下表所示:

大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第13张

对于 SMO,使用希罕数据结构将代码的速率提高了 10 倍以上,这表明 SVM 的评估时间完全决议了 SMO 的盘算时间。希罕点积代码仅将分块算法的速率提高了约莫 1.1 倍,这表明数值 QP 步骤的评估在分块盘算中占主导地位。

噪声数据集

第二个人工数据集由随机的 300 维二进制输入点和随机输出标签天生。SVM 拟合的是纯噪声。

将 SMO 和分块算法应用于线性 SVM 的效果如下所示:

大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第14张

SMO 的盘算时间规模为 ~\(N^{1.8}\),而分块算法为 ~\(N^{3.2}\)。该效果显示,当大多数支持向量都处于界限时,SMO 显示出色。因此,为了确定由希罕点积代码引起的速率增添,在没有使用希罕点乘积代码的情形下测试了 SMO 和分块算法:

大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第15张

在线性 SVM 情形下,希罕点积代码将 SMO 的速率提高了约莫 6 倍,而分块算法的速率提升很小。在该实验中,纵然对于非希罕数据,SMO 也比分块更快。

同样地,作者也使用了方差为 10 的高斯 SVM 对第二个人工数据集举行了测试,实验效果显示在以下两个表格中:

大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第16张

大发888客户端:Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines 论文研读 第17张

对于拟合纯噪声的高斯 SVM,SMO 的盘算时间规模为 ~\(N^{2.2}\),而分块算法为 ~\(N^{3.4}\)。纵然应用于非希罕数据,SMO 的总运行时间仍然优于分块算法。对于非线性情形,输入数据的希罕性使 SMO 的速率提高了约莫 4 倍,这表明对于非线性 SVM,点积速率仍占 SMO 盘算时间的主导地位。

实验结论

  • SMO 在多种差别的数据集上都比分块算法更快。
  • SMO 在有许多拉格朗日乘数处于界限上的 SVM 上显示出色。
  • SMO 对于线性 SVM 显示优越,由于 SMO 的盘算时间主要由 SVM 评估决议。
  • SMO 对于具有希罕输入的 SVM 显示出色(纵然是非线性 SVM),由于其可以削减核函数的盘算时间,从而直接加速了 SMO。
  • SMO 在大规模问题上显示优越,由于对于文中所有的测试问题,其盘算时间随训练集巨细的缩放规模都优于分块算法。

不足之处

S.S. Keerthi 等人[6]指出,由于 SMO 的盘算方式以及仅维护和更新一个阈值 \(β\) 的特点,在某些情形下可能会举行不必要的第二个拉格朗日乘数的搜索,从而导致 SMO 的效率低下。

左琳[7]也指出,SMO 实际上是在循环迭代上追求快速算法。因此若是没有一个好的选择迭代计谋,SMO 算法就存在盲目性,可能泛起某些到达最优值的样本却不知足 KKT 条件的情形,好比过分选择的消耗,影响了算法的执行效率。

参考文献

  1. J. Platt, “Sequential minimal optimization: A fast algorithm for training support vector machines,” Microsoft, Res. Tech. Rep. MSR-TR-98-14, 1998.
  2. Vapnik, V., Estimation of Dependences Based on Empirical Data, Springer-Verlag, (1982).
  3. Osuna, E., Freund, R., Girosi, F., "Improved Training Algorithm for Support Vector Machines," Proc. IEEE NNSP ’97, (1997).
  4. Burges, Christopher JC. "A tutorial on support vector machines for pattern recognition." Data mining and knowledge discovery 2.2 (1998): 121-167.
  5. Gill, P. E., Murray, W., Wright, M. H., Practical Optimization, Academic Press, (1981).
  6. Keerthi, S. Sathiya, et al. "Improvements to Platt's SMO algorithm for SVM classifier design." Neural computation 13.3 (2001): 637-649.
  7. 左琳. "序列最小优化事情集选择算法的改善." 电子科技大学学报 42.3 (2013): 448-451.
,

AllbetAPP下载

欢迎进入AllbetAPP下载(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

版权声明

本文仅代表作者观点,
不代表本站Allbet欧博官网的立场。
本文系作者授权发表,未经许可,不得转载。

评论

精彩评论
  • 2021-09-12 00:01:32

    USDT跑分www.Uotc.vip)是使用TRC-20协议的Usdt官方交易所,开放USDT帐号注册、usdt小额交易、usdt线下现金交易、usdt实名不实名交易、usdt场外担保交易的平台。免费提供场外usdt承兑、低价usdt渠道、Usdt提币免手续费、Usdt交易免手续费。U担保开放usdt otc API接口、支付回调等接口。

    懒人宅家看文,安逸~