迭代重加权最小二乘支持向量机快速算法研究

1、第年 迭代重最小二乘支持向量机快速算法研究温郝志峰工业大学计算机学第年 迭代重最小二乘支持向量机快速算法研究温郝志峰工业大学计算机学广州华南理工大学计算机科学与广州中国电互联网与增值业务运营中心广州摘 要 迭代涉及到多次方法是提高最小二乘支持向量机（）稳健性的重要但由最小二和重复训练该方法需要大量运算无法广泛应用。通过数值推导获得了求解迭代重支持向量机的快速算法大幅度减少了其运算复杂度。引入了 种经典的集和实际数据集上进行实验证实了 能获得相当稳健的学习结函数并在多个仿真数据快速算法也确实能够大幅度减少训练时间。实验结果同时表明在快速训练算法的框架下种不同的权重函数可能要求不同的训练时间。支持

2、向量机稳健性异常样本快速算法 的意义下是稳健的。根据这一结论采用 不敏感损失函数损失函数损失函数的支持向量回归算法是相对稳健的而采用误差平方和损失函数的最小二乘支持向量机 引言一种机器学习算法其基础为小样本统计学习理论。该算法具备良好的泛化能力和学习性能已广泛应用于模式分类函数估计以及密度估计等领域。由于引入了结构风险最小化的目标支持向量机算法具备较以往算法更好的推广能力。然而这并不能保证 算法的稳健性。所谓稳健性，是指对于偏离理论假定时的不敏感性。具体来说针对回归问题稳健性就是学习机对于异常样本的不敏感性即学习机的学习效果不会受到训练集中异常样本的影响。 算法对结构风险的控制是通过控制模型的

3、复杂度（）和经验风险损失函数来实现的。其中对稳健性起关键作用的就是 算法的损失函数。经验研究相吻合稳健性条件。这一结论与过去的初期 等人经该算法对异常样本的敏感性因此在年提出 又为 ）来减少异常样本对回归机的负面影响。可以说对进行的思路是正确而有实际意义的。这种思路也正是传统回归中用于解决稳健性问题的经典思路，。此外对于采用其他损失函数 法也有研究者提出了不同的方案譬如 等人 通过的理论研究发现如果 使用 出的鲁棒支持向量回归机算法，以及和 连续的损失函数以及有界的 核则算法在影响函重算法。这类算法都是借鉴传统稳健回归中重到稿日期返修日期本文受国家开放课题基金资助温雯女博士讲师主要研究方向为模

4、式识别机器学习图像处理等， 郝志峰男教授士生导师主要研究方向为数据挖掘机器学习仿生算法等最小二乘 量 赋予一个权重因子，输入样本集可表示成逐步减少异常样本的影响其 优化函数变为 正回归机的估计值。但由于需要进行多次的权重设置和重复学习所耗费的时间也是相当巨大的（， （ 本文以迭代重最小二乘支持向量机式中 由下式决定最小二乘 量 赋予一个权重因子，输入样本集可表示成逐步减少异常样本的影响其 优化函数变为 正回归机的估计值。但由于需要进行多次的权重设置和重复学习所耗费的时间也是相当巨大的（， （ 本文以迭代重最小二乘支持向量机式中 由下式决定研究对象针对重所引起的算法运算量增加首先提出了一种能够根

5、据权重变化求解单 烅，代更新算法而后在该算法的基础上提出并实现了若干种稳健权重设置方案下的快速 学习算法最后从运算时间和求解精度上比对了该算法和经典 以及的性能 的建议取值分别为和这是因为分的假设下绝对值小于的样本出现概率为而绝对值大于的样本出现概率仅为为 的标准偏差的稳健性估计可以由式或式给出最小二乘支持向量机回归算记 ， 其中 为第个样本的输入值为对 应的输出值。对于给定样本集 首先通过一珘将输入值到一个高维为四分位数间距即 将误差值排序后分 别位和位置的两个数据间的差值特征空间在该特征空间中回归函数可以表示成） 有别于传统回归 在最小化经验风险的同时也追求结构风险的最小化即其目标是最小化

6、风险函数：的中位数 即绝对离（ ，（ 要求在训的基础上获得误差的分布信息进而设置权重 ，最后再次训练后的 。因此其运算复杂度相当于训练两次 的计算复杂度 其中损失函数可以有多种表现形式，选择平方和作为损失函数并将不等式约束条件变成等式约束条件。具体 （ （ 注意到不管采用哪种式中 为对应第 个样本的估计误差新训练一次 ，因此将耗费较多的运算时间。针对期望从该优化问题中获取形如）一问从数值计算的角度给出了一种 的快式以对未来的样本进行估计和。但是的具体表速学习算法。为了便于首先将 的对偶问式往往无法知道因此需要采用一定的技巧将问题加以转换改写成如下形式见式利日乘子及矩阵变换方法优化问题可以换成对

7、偶空间中的线性方程组（）的形式 熿燄式中是一个对角矩阵对照 可以发现它模型非常相似唯一的不同之处式中 为样本输出向量 的对偶问题中 在于传统 为核矩阵其中日乘子（ ） （ 这启可以尝试通 的训练结果来快速获得。该线性方程组表方式非常简洁且相对容易求解这也正引起了的 结 果若 记珦，多研究者及实际应用者关注的主要原因。求解式（）后可以获得函数估计式的目的是利用珦，）快速获 ，从而避免 重新求逆。为了清晰描述的算法原理首先引入 公式公式 虽然 具有模型简单求解便捷等优点但由于使用平方和误差作为损失函数异常样本对估计函数的影响将被扩大因此如何控制学习机对异常样本的敏感性便给定一个可逆矩阵列向量假 显

8、得尤为重要。最小二乘支持向量则有以下公式成立是对这一问题的经典尝试 ） 是对每个样本的误差受公式启发可以用一种迭代更新的方法由珦 快速计算获得 。令 为 的计算量其中。因此使用快速求解算法后的运算时间复杂度将大幅度减少为迭代提供了时间上的保证。当然从空间复杂度来看算法 需要其中 是传统在最优超参数下求得的向量和偏置）在每一步迭代中只考虑与矩阵珦 额外的空间用于中间矩阵 ，即它所要求增加的量是一个的对称矩阵在目前硬件的发展水平下这是完全可以接受的。第 行第 列上元素值不一样的对应矩阵即在第次迭代，则考虑：用一种迭代更新的方法由珦 快速计算获得 。令 为 的计算量其中。因此使用快速求解算法后的运算

9、时间复杂度将大幅度减少为迭代提供了时间上的保证。当然从空间复杂度来看算法 需要其中 是传统在最优超参数下求得的向量和偏置）在每一步迭代中只考虑与矩阵珦 额外的空间用于中间矩阵 ，即它所要求增加的量是一个的对称矩阵在目前硬件的发展水平下这是完全可以接受的。第 行第 列上元素值不一样的对应矩阵即在第次迭代，则考虑： 显然当 。是所有训练样本的样本总数时有 图 的快速求解算法流程图式中的第个元素是且（）的第个元素是 则有因此根 。 及其快速算法 公式有在异常样本数目较少的情况下，可以正确地设置样本权重从而较好地消除噪声影响但随着异常样本数量的增加根据一次学习获得的信息进行权重设置其正确性 的第行第列

10、的元素则有即若 逐渐降低。事实上针对这个问题在文献中曾 经提到可以采用多次重复的方法即在每一轮的学习 中根据上一轮训练结果对样本设置权重重新训练并将这种学习过程进行若干次重复从而逐渐纠正有偏差的学习结由于则更新后可以根据式 （ 果。这种方法正是迭代重最小二乘支持向量机计算而得若干关键难点其一 权重的设计和选择其二训练终止条件的确定其三中的元素即对应的和。因此获得 的训练结果之后可以用以下迭代算法快速地求解 算法 的快速求解算法，对偶问题的逆矩保存 中快速训练算法的设计。最后一点恰恰是最的一个问题因为重复训练将导致运算量的大幅度增加也正是因为如此 并不使用重的方案。但是根据前一节所算法，发现大幅

11、度减少一训练的运算时间是有可能的这为多次训练创造了条件。在本小节中将提出实现 的一种完整 法并基于算法提出适用于 快速训练算法采用给定方法对样本进行。其能够根据异常样本数量自适应调整速地获得稳健的学习结果的次数从而较快对于第个样本如果权重则根据式更新矩 的各个元素否则转而执行步骤根据式计算和，输出它们作为的训练结 果。直观地算法的流程如图所示。由于采用式对逆矩阵进行更新针对快速求解算法的复杂度有以下结论显然在 的快速求解算法中对矩阵珟只有当 时才需要进行迭代更新。而在每次更新中将产生复杂度 的计算量。令 代表对应的样本数为了获得 的解总共需要进行复杂度为的计算。由于异常样本的数量通常不会太多因

12、此在合适的权重方案下 首先引 入 权 重 函 数 权重函数以及权重函数。前两种是传统稳健回归中常用的权重函数，最后一种则在经中所用的权重函数事实上权重函数对于第次迭代中的第 个样本种权重函数可以分别用式） 式表示权重函数，权重函数部分样本的权重都将被设置为即的样本数只占少烅部分。而直接求解 至少需要复杂度权重函数果在中中的变 保证了 在以下条件满足时停止迭代如果后两次过程，烅中任何一个样本的权重变化量都不超过阈值 停止迭代由于权重的值域为 可以设置为中的一个较小的数。的实验中通常将设置为。在这种迭在以上 种权重函数中，（） 是第代终止条权重函数果在中中的变 保证了 在以下条件满足时停止迭代如果

13、后两次过程，烅中任何一个样本的权重变化量都不超过阈值 停止迭代由于权重的值域为 可以设置为中的一个较小的数。的实验中通常将设置为。在这种迭在以上 种权重函数中，（） 是第代终止条件下 可以针对每一次学习的结果纠正权重设置并在学习结果无法再改善的时候自动终止重复加权的过程从而保证算法的稳健性。并且在 中次学习后第 个样本对应的误差则由式给出 ）（ 快速训练算法大大减少了迭代从而保证了算法的效率过程中产生的重复计算式中代表第次循环中的误差项的四分位数间距将第次迭代学习获得的误差值 排序后分别位于和位置的两个数据间的差值种权重函数的直观图形如图所示。从图可以看出实验结果与分析为了算法的有效性分别在若

14、干个仿真数据种权重函数的特点都是对位于分布尾部的样本赋予小和实际数据集上进行了测试主要从运算时间和测试精度两权重值因为处于这一位置的样本往往是偏离了正常分布的个方面的算法性能。为了使结果更加客观异常样本。其次根据的观察无论使用上述哪一种权实验中不仅了经回归算法的还加函数随着重复次数的增加异常样本和正常样本的权重入了相同数据集下。所有程序编写了经以及都将逐渐趋向于一个稳定的水平。因此 可以选择在样本权重变化异常微小即小于某个阈值的情况下的终环境下编写和运行其中步骤中直接使用普通的训练方法和加速的即算法 的求解则使用文献中的公开源代码止和重复训练。再者针对耗费运算量过大的情况可以使用前一小节中的结

15、论充分利用算法的迭代更新方法减少运算复杂度加快算法的运算速度即只需要将更新公式修改为如下形式本文使用的版本为 实验中硬件配置条 为的 的内存。所用操作系统首先使用非线性回归中的基准函数函数进行仿 实验。训练样本由两部分一部分是正常样本由式中 代表第后第 个样本对应的权重附加小方差的正态扰动随机产生见式另一部分为异常样本由输出值分布于 的随机均匀分布产生）， ）（ 仿真实验中考虑了个训练样本集样本总数从递增至。每个样本集中正 常样本个数均为 个由式 等间隔采样产生异常样本个数从个递增至个个训练集中的异常样本比例大约从递增至）正态扰动和异常样本均由工具箱随机生成。测试样本集由不加扰动的信号函数产生

16、且设置不同的采样间隔以确保测试样本与训练样本不同。测试样本个数为。各算法测试精度对比如表所列训练时间的相关结果图 种不同的权重函数及权重函数权重函数权重函数以算法 加速如表所列。表的结果显示使用 函数中的任意设置各样本权重初始值 一种 都可以获得远远好 ，并将 对偶问题的逆矩保存 中。选择 度这说明通过重复的方式确实可以大幅最小式中的一个作为权重函数乘支持向量机的稳健性。对于仿真数据集方根据选定的权重函数对样本进行案和 方案都较为出色可以稳定地获 得比。采用算法对 进行快速训练即执行以下步骤好得多的结果。表同时显示， 的测试精度是 种算法中的这与文献中的研究结果相一致因为对于第 个样本如果 模

17、型中的损失函数并不满足稳健性要求而 相对而言更能满足稳健性要求。从训练时间来看更新矩阵 的各个元素并置；否则直接执行步骤速 可以节省大量的训练时间远远少于加速 的方式具备运算如果为真令 ，转而执行步骤；否则执行步骤时间上的可操作性只需要增加较少的训练时间就能 获得较更好的测试精度。此外对于根据式计算和，输出它们作为 的训练结不同的权重函数 所需要的时间也不尽相同表仿真数据集精度对数情况下权重方案需要的训练时间最少所需的时间最多。这是因为在权重方案下多数正常样本能够稳定地被赋予恒定权重每次迭代学习中需要变化更新的只有介于正常和异常之间的少量的样本权重。与此相反权重函数是连续函数在每次学习中都有较

18、多的样本需要变更其权重值从而导致迭代更新的次数增加训练时间也同步增加。 数据集 不同的权重函数 所需要的时间也不尽相同表仿真数据集精度对数情况下权重方案需要的训练时间最少所需的时间最多。这是因为在权重方案下多数正常样本能够稳定地被赋予恒定权重每次迭代学习中需要变化更新的只有介于正常和异常之间的少量的样本权重。与此相反权重函数是连续函数在每次学习中都有较多的样本需要变更其权重值从而导致迭代更新的次数增加训练时间也同步增加。 数据集 为 即平均绝对误差表 仿真数据集训练时间对异常样本个数训练时间秒训练时间秒数据集样本总数迭代次数训练时间秒权重函数未加速算法加速算法 为了进一步验证算法的有效性还选择

19、源自实际问 题的 数据集数据集试。数据集是模拟头部受到撞击后产生的加速度的相关数据共有个样本该数据集输入值的采样并不是等距的且在某些情况下对应的同一个输入值可能有不同的输出值而且输出值具有异方差性。 入特征和个输出特征。数据集是源自生物学研究领域的一个数据集它共包含个样本每个样本有 结束语 为了的稳健性本文对迭代重加数值推导获得了求解的快速算法该算法能输入特征和个输出特征样本集随机分为 等份其中份用于训练份用于测试算法测试精度和训练时幅度减少运算复杂度为迭代重扫除了运算时间上的障分在表和表中。实际数据集上的与仿算法具有远远碍此外还通过实验研究了迭代重中的种常见数据集上的结果具有相似的趋势迭代重函数权重函数函数和 函数优于 的稳健性而且也具有较更好的测试精度。而从训练时间上来看加 速算法大幅度减少了 的运算时间且在 和 的权重方案下加速算法能够在增加不太多训练时间的前提下获得更稳健的测试结果发现无论使用哪种函数 都能获得较为稳健的学习结果。但种权重函数可能会对快速算法的训练时造成一定的影响从研究结果来看迭代的方式确实可以提高最小乘支持向量机的稳健性。虽然该方法主要从改进求解过程的表实际数据集测试精度对角度入手但其本质是改变了损失函数即通过迭代的处 数据集 于 优化目标中的损失函数不再