基于柔性多面体的最优核极限学习机算法

苏一丹，麻晓璇，覃 华，王保锋

(广西大学 计算机与电子信息学院，广西 南宁 530004)

0 引 言

极限学习机(extreme learning machine, ELM)具有学习速度快、结构简单的特点，但ELM隐藏节点数量的选择以及参数的随机设置造成学习训练方程存在病态问题，影响了它的稳定性。于是出现了核极限学习机(kernel extreme learning machine, KELM)[1]，随着多层特征表示的不断发展，借助核函数的ELM层次化结构也表现出了速度快、易于实现的优势[2]，并已被广泛应用于各个领域，例如，高光谱图像分类[4]、人的行为分析[5]、损伤定位检测[6]、航空发动机故障诊断[7]等场合。多核结构的ELM提高了学习机的泛化能力[3]，其中组合核中通常都包含有高斯核函数(Gaussian kernel function)，其核参数和惩罚参数的设定一般根据经验所定，设置不当会直接影响学习机的分类效果。对KELM参数优化问题，许多学者从多个角度提出了解决思路，何敏等[8]提出采用遗传算法(genetic algorithm, GA)对KELM参数进行优化，Sun Hongchun等[9]提出用粒子群优化算法(particle swarm optimization, PSO)来优化KELM参数。PSO和GA方法是在自然进化基础上模拟个体种群的适应性实现，具有简单易用等优点，属于随机搜索优化算法，但随机搜索优化算法的结果可靠性差，无法得到稳定的解，并且不能很好解决大规模复杂问题。苏一丹等[10]提出的K插值单纯形法来优化KELM参数，该方法的分类精度比传统的KELM平均分类精度提高了41.73%，但其只对核参数进行了一维搜索，惩罚参数的选取依然根据经验来确定，事实上惩罚参数的选取也会对KELM分类器性能和泛化能力产生影响，也需要优化。

柔性多面体搜索算法[11](flexible polyhedron search algorithms, FPSA)近年出现多维非线性问题优化方法，但其初始柔性多面体设置不当会导致多面体寻优搜索收敛速度慢，陷入局部最小值。网格搜索算法(grid search, GS)是一种全局多维搜索方法，对初值不敏感，但全局搜索效率较柔性多面体弱，为此，本文将FPSA和GS相结合，利用两者的优点构造最优化算法优化KELM的核参数和惩罚参数。首先用网格搜索获取参数的初始值作为初始多面体，解决柔性多面体对初始值敏感的问题，然后根据核极限学习机核参数和惩罚参数对分类性能影响程度的不同，给柔性多面体的变形参数中添加参数权重，通过迭代柔性多面体实现核极限学习参数的最优化搜索，再用所获最优参数构造最优化核极限学习机(GSFP-KELM)。最后在UCI数据集上通过与其它同类算法相比较，验证所提算法的可行性。

1 核极限学习机简介

极限学习机是一种单隐藏层前馈神经网络(SLFNs)的学习算法，ELM的分类函数可表示为

f(x)=h(x)β

(1)

式中：h(xi)=[g1(xi),…,gL(xi)] 为特征映射矩阵， g(·) 为激活函数，β=[β1,…,βL]T是连接隐含层和输出层的权重向量。极限学习机的主要训练目标是计算输出权重向量β， 即

β=H-1T

(2)

为提高ELM模型稳定性和泛化能力，优化输出权重矩阵如下

(3)

式中：I是一个N维的单位矩阵，C为惩罚因子。分类函数更新为

(4)

式中：HHT被称为ELM核矩阵，采用满足Mercer’s条件的核函数简化ELM核矩阵的内积计算，即

Ω=HHT;Ωi,j=h(xi)·h(xj)=K(xi,xj)

(5)

则KELM权重矩阵描述如下

(6)

相应的KELM分类函数可使用如下公式计算

(7)

本文KELM选用的核函数为最常用的高斯核函数，其公式描述如下

(8)

式中：σ为高斯核的带宽，也就是核参数。

综上所述，核极限学习机存在两个超参数，即核参数σ和惩罚参数C。σ是控制高斯核函数影响的范围；C是用于调节训练样本满足约束条件的程度。如果两个参数选择不当会影响学习机的分类性能，因此需要提供给KELM一组合适的参数组合。

2 网格搜索优化柔性多面体寻优算法

2.1 网格搜索优化柔性多面体思路

首先要通过网格搜索算法在较大范围内采用大步距进行遍历搜索，为了给柔性多面体提供合适的初始搜索点，本文对核参数σ和惩罚参数C在KELM上的分类性能的影响进行分析。如图1所示，当核参数σ→0时，训练集分类准确率很高，但是构建的分类器对测试样本的分类效果却很差，即产生了过学习状态。随着σ增大，测试精度逐渐提高，但σ超过一定值后训练精度和测试精度都逐渐下降直至趋于常数。惩罚参数C过小时KELM分类精度低，易处于欠学习状态；随着C逐渐增大分类精度逐渐提高并趋于稳定。由此可见，核参数σ与惩罚参数C共同作用影响KELM分类性能，当处于训练误差为0和有足够小的训练误差交界处时测试精度较高。故初始多面体合适的范围设置在存在一定训练误差的位置。先设定目标函数F(σi,Cj)， 即KELM训练误差

(9)

式中：N为训练样本总数，Perror(σi,Cj) 表示在核参数为σi以及惩罚参数为Cj时错误分类的样本数。令允许的训练误差为TolFun， 默认值设定为0.01。选取二维网格中满足F(σi,Cj)>TolFun条件的网格点组合成参数集合G(σi,Cj,F(σi,Cj))。 然后再通过柔性多面体进一步优化。

图1 核参数与惩罚参数在KELM上的影响

从集合G中选取合适的点建立初始多面体。根据Nelder-Mead定理[12]，对于双变量函数问题，需要构建一个3个顶点的多面体，即一个三角形。初始多面体范围设定太大或太小都会导致多面体收敛速度慢和易陷入局部最小值的问题。因此本文针对网格范围来优化初始多面体设定。在集合G中选择目标函数值最小的参数点v1=(σb1,Cb2)， 对应的网格坐标为(b1,b2)。 找到该点的两个参数在网格中前一个点(σb1-1,Cb2)、(σb1,Cb2-1)， 分别以v1为中心点计算出对称顶点v2和v3， 则初始多面体定义为

Sinit=[v1T,v2T,v3T]

(10)

由图1及上述结论来看，分类精度主要受核参数影响，惩罚参数在取一定值后趋于稳定，而通常惩罚参数初始间距较大，如果两个参数按照相同比例反射、扩展、压缩和收缩，惩罚参数会过度增大或者过度减小。本文提出采用惩罚参数与核参数的斜率比作为惩罚参数在柔性多面体变形的权重。取v1顶点在网格中纵轴方向和横轴方向的点，分别拟合成二次曲线，并计算两条曲线在v1顶点上的斜率，分别记为Kσ、KC。 惩罚参数权重计算为

(11)

因此，柔性多面体的变形系数权重记为w=[1wc]T。 根据原始柔性多面体变形公式更新如式(12)

vr=c+w·ρ·(c-vw) (反射Reflection)
ve=c+χ·(vr-c) (扩张Expansion)
voc=c-γ·(vr-c) (外压缩Outer-Contraction)
vic=c+w·γ·(c-vw) (内压缩Inner-Contraction)
vw=vb+w·ο·(vw-vb) (收缩Reduction)

(12)

其中，c是除去最差顶点vw之外剩余顶点的中心点。反射系数ρ、 扩张系数χ、 压缩系数γ、 收缩系数ο在Nelder-Mead中默认值分别为ρ=1，χ=2，γ=0.5，ο=0.5[12]。

依据式(12)进行反射、扩张、压缩操作获取一个更好点vnew来取代最差点vw， 从而构成一个新的多面体，或者通过将最差点vw向最好点vb收缩来形成新的多面体。迭代进行上述操作，以不断逼近最优值，当满足表1终止条件[13]时停止迭代。其中，volume_ratio计算公式描述如式(13)，初值设置为1[14]

(13)

表1 迭代搜索终止条件

2.2 网格搜索柔性多面体算法优化核极限学习机

核极限学习机不需要输入核参数和惩罚参数，参数值在训练过程通过网格搜索优化柔性多面体寻优获取。GSFP-KELM主要通过以下步骤实现：

步骤1 载入训练样本和测试样本；

步骤2 对数据集进行预处理；

步骤3 初始化网格搜索范围与步距，用网格搜索算法构造初始柔性多面体；

步骤4 设计柔性多面体变形系数权值，初始化迭代终止条件；

步骤5 通过柔性多面体迭代优化KELM的核参数与惩罚参数；

步骤6 使用步骤5优化的核参数和惩罚参数计算出KELM的权重矩阵，并对测试样本进行分类，计算出分类准确率。

2.3 时间复杂度分析

网格搜索柔性多面体算法优化核极限学习机执行的时间复杂度为：首先对数据进行预处理，时间复杂度与数据样本大小N成正比，计算时间复杂度是O(N)。 计算训练样本欧式距离的时间复杂度为O(N2)。 目标函数计算时间复杂度为O(N3)。 依次计算网格对应的目标函数值的计算时间复杂度为O(G)*O(N3)， 其中G为网格数。使用柔性多面体搜索最优核参数，计算时间复杂度是O(t)*O(N3)， 其中t为柔性多面体迭代搜索次数。根据返回参数计算权重矩阵的时间复杂度为O(N3)。 计算测试样本类别的计算时间复杂度为O(N3)。 最后计算精度计算时间复杂度为O(N)。 综上复杂度为O(N+N2+N3+GN3+tN3+N3+N3+N)， 由此可知所提算法的计算复杂度为O(N3)。

3 仿真实验与分析

仿真实验在计算机硬件环境为Intel Pentium G640 (2.8 GHz) CPU，内存10 GB。在Windows7 x64平台下用MATLAB R2016a实现所提算法。

3.1 实验用数据集描述

实验总共使用了13个数据集，具体描述见表2。其中表中前12个标准分类数据集来源于UCI和KEEL数据储存库。表中最后1个来源于人工数据集。

表2 数据集

3.2 实验设计

为验证本文算法的可行性，实验结果与近年几种常见智能优化核极限学习机算法相比较：遗传算法核极限学习机(GA-KELM)[8]、粒子群核极限学习机(PSO-KELM)[9]、K插值单纯形核极限学习机(KS-KELM)[10]。使用5-fold交叉验证方式比较4种方法优化的核极限学习机分类性能，并计算5次验证的平均测试精度和标准偏差。将网格搜索中核参数范围设置为 [2-2,2-1,…,28]， 惩罚参数范围设置为 [20,21,…,210]。

3.3 实验结果及分析

4种算法的计算结果见表3，表中 (σ,C) 项表示该算法所获的最优化核参数和惩罚参数；“准确率”项是5-fold交叉验证的平均分类精度与标准偏差。

从表3可以看出，与GA-KELM、PSO-KELM和KS-KELM相比，本文提出的GSFP-KELM在上述数据集上都有非常好的表现。例如，在vehicle、wine、fertility数据集上，其它3种方法所获取的核参数和惩罚参数都偏小，而KS-KELM由于惩罚参数受限制，所训练出来的核参数也相对偏小。此外，GA-KELM和PSO-KELM在对数据集ovlivetti进行训练分类时均能达到100%的准确率，但是在对测试集分类时准确率却很低，明显出现了过拟合现象。而本文提出的GSFP-KELM能得出有效的测试准确度。GSFP-KELM的分类精度较GA-KELM平均提高了13.61%，较PSO-KELM平均提高了7.75%，较KS-KELM平均提高了11.52%。因此，本文提出的用网格搜索柔性多面体算法来优化KELM的最优核参数以及惩罚参数是可行的。

网格搜索优化柔性多面体与传统柔性多面体分别在13个数据集上的运行5-fold交叉验证的平均收敛迭代次数对比如图2所示，以及平均评估目标函数的次数对比如图3所示。在数据集thyroid、seeds、wine和fertility上，传统的柔性多面体平均迭代次数均达到了最高迭代次数，即迭代搜索陷入了局部最小值，产生无效的迭代而无法收敛。如图2可以看出，本文提出的网格搜索优化柔性多面体能有效避免多面体搜索陷入无效迭代过程，并且总体上网格搜索优化柔性多面体收敛速度更快，能更好的逼近目标值。如图2和图3可见，迭代次数与评估次数成正比，每迭代一次将至少进行5次目标函数的计算。传统的柔性多面体则可能进行最多8次目标函数计算，而网格搜索柔性多面体最多进行6次目标函数计算，减少了目标函数的计算次数。在本次实验中，网格搜索柔性多面体比传统柔性多面体平均迭代次数平均减少了8.6次，平均评估次数平均减少了41.1次。因此结合网格搜索的初始多面体能更快的收敛，减少了无效迭代的次数，有效提高了训练效率。

表3 与GA-KELM、PSO-KELM和GS-KELM之间的对比：分类精度与标准偏差

图2 网格搜索优化柔性多面体法收敛迭代次数对比

图3 网格搜索优化柔性多面体法评估次数对比

表4是本文算法与近几年出现的一些极限学习机算法的分类精度比较，分别是基于文化基因算法的极限学习机(M-ELM)[15]、实例克隆极限学习机(IC-ELM)[16]、基于多目标优化的稀疏极限学习机算法(MO-SELM)[17]。相关比较算法的分类精度取自对应的文献，表中的“—”符号表示对比的算法文献中未给出该数据集的结果。从表4可看出，在数据集(segment、vowel、wilt、satellite、letter)上本文算法GSFP-KELM的分类性能均优于其它3种算法。而在数据集iris略低于M-ELM算法，但偏差相对较小，说明了本文提出的网格搜索柔性多面体算法优化的核极限学习机是可行的。

表4 4种极限学习机的分类精度对比

4 结束语

本文提出了一种基于网格搜索柔性多面体算法的自适应核极限学习机方法。首先使用网格搜索算法在全局范围内分析核极限学习机参数集的合适的范围，再通过结合网格优化的多面体对核极限学习机进行局部搜索，将训练的参数集与核极限学习机结合为训练模型。实验与对比结果表明，GSFP-KELM具有很好的分类能力，避免了一定程度的过拟合问题，提高了泛化能力。通过优化的柔性多面体算法较传统的柔性多面体算法收敛速度更快，变换适应能力更强。