核极限学习机的在线状态预测方法综述

2021-07-08 02:14戴金玲吴明辉李睿峰
兵器装备工程学报 2021年6期
关键词:时变复杂度字典

戴金玲,吴明辉,2,刘 星,李睿峰

(1.海军航空大学, 山东 烟台 264001; 2.杭州声学应用研究所, 浙江 杭州 310000; 3.中国人民解放军92932部队, 广东 湛江 524000)

近几十年来,时间序列预测得到了深入的讨论与研究,并在容错分析、状态预测、状态监测和故障诊断等科学领域中发挥着重要作用[1]。时间序列预测的关键在于建立一个具有相应结构和参数的模型来描述真实系统的动态行为,目前已有大量的研究成果,比如反向传播神经网络(back-propagation neutral network,BP-NN)[2]、支持向量机(support vector machine,SVM)[3]、最小二乘支持向量机(least square SVM,LSSVM)、近端支持向量机(proximal SVM,PSVM)[4]、极限支持向量机(extreme SVM,ESVM)[5]以及极限学习机(ELM)等方法[6-11]。然而,在许多实际应用中,当一个新的数据到达时,以上将新旧数据收集在一起进行再训练、以合并新样本信息的方法不仅会导致额外的存储消耗,同时使学习时间变得越来越长,因此需要在线的、自适应的实时操作。针对这一特点,学者们提出了大量在线顺序学习算法[12-16],其中在线贯序极限学习机(online sequential ELM,OS-ELM)[17]根据其快速的学习速度和出色的泛化能力,能够准确且高效地实现数据样本的在线增量学习[18-20],在众多方法中脱颖而出,并且成为了时间序列预测领域的主流方法。

尽管OS-ELM具有诸多优点,但需要确定隐含层个数的问题依然存在[21],选择隐式映射的核方法则有效地解决了这一问题。相比ELM,KELM不仅避免了维数灾难的问题,还改善了隐藏神经元随机赋值带来的泛化性和稳定性下降,在非线性系统的故障识别和时间序列预测等领域展现了良好的应用价值和发展潜力[22]。因此,基于KELM的在线学习算法逐渐受到了人们的重视与应用。

毫无疑问KELM在线应用的研究是一项非常有意义的工作。自基于核增量的极限学习机(kernel based incremental ELM,KB-IELM)在2014年被提出[23]、将KELM扩展到在线应用中,验证了其优于OS-ELM的性能与速度,OSKELM开始得到不断的关注与研究。近年来的理论研究主要围绕KB-IELM产生的2个问题进行:① 如何抑制模型膨胀;② 如何跟踪系统的动态变化,取得了一批有意义的研究成果[24-52],并且在非平稳时间序列的预测中得到了广泛的应用。本文旨在对这些研究成果进行分归纳、分类、比较与总结:首先简要描述问题和介绍OSKELM的数学模型;针对KELM在线应用中的2个主要问题,对各种改进算法进行分类综述;然后将各改进算法的性能效果进行比较与分析;最后总结展望了该方向的未来发展前景。

1 OSKELM的问题描述与数学模型

1.1 KELM数学模型

KELM是OSKELM的理论基础。假设S={(x1,y1),(x2,y2),…}是一组观测时间序列,xi∈Rd为d维输入向量,yi∈R为对应输出值,将满足等式约束条件的极限学习机优化问题定义为:

(1)

其中,β=[β1,β2,…,βn]T表示连接隐含层与输出层的输出权值;h(xi)=[h1(xi),h2(xi),…,hL(xi)]表示隐层神经元与输入样本的映射关系;yi表示输入样本xi对应的实际输出值;ξi表示样本xi的输出误差值;C表示正则化因子,也称为惩罚因子。

由KKT优化条件,可得式(1)输出权值βn的计算公式如式(2)所示,其中输入样本的映射矩阵为H=[hT(x1),hT(x2),…,hT(xn)]T,yn=[y1,y2,…,yn]。

βn=HT(C-1I+HHT)-1yn

(2)

根据Mercer条件定义核矩阵为Ω=HHT,Ω(i,j)=h(xi)hT(xj)=k(xi,xj)。因此,KELM的输出形式则可以表示为式(3)所示,其中kn=[k(·,x1),k(·,x2),…,k(·,xn)],表示n时刻的核估计向量,θn=(C-1I+HHT)-1yn表示核权重系数。

f(·)=hT(x)βn=h(·)HT(C-1I+HHT)-1yn=

[k(·,x1),k(·,x2),…,k(·,xn)]·

(C-1I+HHT)-1yn=knθn

(3)

1.2 OSKELM

在OSKELM中,令An=C-1I+HHT,则核权重向量为:

(4)

对于n+1时刻的新观测数据(xn+1,yn+1),进一步令

(5)

其中,kn=[k(x1,xn+1),…,k(xn,xn+1)]T,vn=C-1+k(xn+1,xn+1)。根据块矩阵求逆公式,矩阵An+1的逆矩阵可以表示如下形式:

(6)

(7)

由上可见,不同于传统的将新旧样本收集在一起再重新训练,当新样本来临时,KB-IELM方法通过更新矩阵An来吸收新样本信息,更新过程由上一时刻的参数矩阵An与新样本(xn+1,yn+1)来完成,且更新之后将不再需要旧的样本集信息,这种方法极大地降低了计算复杂度,提高了效率。与此同时,由于KB-IELM学习了所有的样本数据,其模型阶数与训练样本数相等,从而产生2个问题:① 算法面临过度拟合的风险;② 计算成本随之超线性增加。为解决该问题,跟踪系统实时动态,放弃冗余信息,选择价值更高的样本去构造并更新模型,成为了新的研究方向。

2 改进的OSKELM算法

在时间序列在线预测的现实应用中,时间序列样本以数据流的形式贯序到达,目标系统的实时动态随着不断改变,这就要求模型在获得新样本信息的同时,及时消除过时或者失效的样本对于系统的影响。在线稀疏化可以有效解决模型膨胀的问题,追踪系统的动态变化。随着研究的深入,KELM模型的稀疏化方法和追踪系统动态方面产生了很多研究成果。本节以KB-IELM为基础,基于在线学习理论,从OSKELM的在线稀疏化与跟踪非线性系统时变动态特征2个角度出发,对改进的OSKELM算法进行总结分析,如图1所示,将改进OSKELM算法归纳为以下几类方法:基于滑动时间窗的OSKELM算法、基于稀疏测度的OSKELM算法、基于参数寻优的OSKELM算法、基于遗忘因子的OSKELM算法、基于多变量的OSKELM算法以及其他方法。

图1 改进的OSKELM算法分类框图

2.1 基于稀疏化方法的OSKELM

目前,已有很多针对OSKELM的稀疏化策略[24-31,42-47],主要分为两类:一是基于滑动时间窗的稀疏化策略;二是基于稀疏测度来量化样本的重要性。二者相同之处是,当滑动时间窗移动或稀疏字典变化时,都会相应的递推更新核权重系数,以得到更好的预测结果。不同点在于,作为传统与直观的方法,滑动时间窗通过[24-27]研究一定数量的最新样本来获取系统的最新性质,并基于此对未来趋势进行预测,其主要流程为:每当一个新样本到达,则删除一个距离最远的旧样本,从而去除旧样本对模型的影响。然而简单粗暴的直接删除旧样本,有可能错误地删除了某些影响较大的样本,因此建立一个固定规模的稀疏字典[28-34,45-47],通过一定的准则判定样本的价值并决定是否吸收,成为了研究稀疏化策略的另一个方向。

2.1.1滑动时间窗

在对系统使用在线时间序列学习算法进行学习的过程中,抛弃那些效果较差或过时的训练样本,不仅可以减小旧样本对模型可能产生的误导作用,还能阻止模型无限膨胀。文献[24]基于传统滑动时间窗,提出了带有遗忘机制的OSKELM算法(online KELM with forgetting mechanism,FOKELM),该方法通过对样本的逐个添加与删除样本来调整输出权值,即依次学习和忘记样本,通过固定规模的时间窗对新样本进行预测,其网络结构的大小是固定的,如图2所示。

图2 滑动时间窗策略示意图

滑动时间窗克服了矩阵展开的问题,在时变系统辨识的稳定性和计算复杂度等方面均优于KB-IELM。同时可见,添加与删除样本的过程依然具有一定的算法复杂度,针对这一点,文献[25]提出了Cholesky因式分解的FOKELM(cholesky factorization based FOKELM,CF-FOKELM),将在线训练过程中涉及矩阵变换的进行Cholesky因子的递推计算,进一步提高了计算效率;文献[26]则将滑动时间窗与小波滤波方法结合,以实现实时煅烧温度的实时滤波与单步预测。显然,通过滑动时间窗内的样本构造字典,模型的复杂度和泛化性能均与时间窗宽度有关。在静态应用学习中,固定时间窗宽度是很好的选择,然而很多情况和应用是快速变化的,对新旧样本一视同仁也是不合理、不准确的,因此文献[27]中提出了一种改进的带遗忘机制的OSKELM,可以根据预测误差自动改变滑动窗口的大小。滑动时间窗宽度的自动确定避免了人为干扰,节省了训练时间,并且具有较好的鲁棒性。

2.1.2稀疏字典

滑动时间窗将窗内的所有样本重要性视为相同,并且将一定时间距离的样本直接舍弃。然而,在时变与非平稳环境中,样本的重要性主要决定于时间序列的内在结构,新样本并不一定对现阶段模型的影响为最大。因此,文献[28]采用了近似线性独立(approximate linear dependency,ALD)准则来作为衡量样本重要性的标准,给定一个固定阈值δ,将新样本在特征空间与稀疏字典的线性范围的距离与该阈值进行比较:

(8)

其中ΩDic是可以有效估计的仅限于字典的核矩阵。距离越大说明新样本与字典成员的相似度越低,那么样本越有价值,即当式(8)成立时,则字典吸收该样本。ALD准则不限定稀疏字典的规模,只要符合条件就吸收样本,因此字典规模与算法复杂度均依赖于阈值的选取。

(9)

(10)

这种无监督的方法,不用预先定义稀疏参数,只需要选择稀疏字典的规模大小,在学习有用信息的同时,保证了模型的简洁。但是显然的,这种方法也额外增加了每个步骤中信息量的计算过程,而快速留一交叉验证(fast leave-one-out cross-validation,FLOO-CV)方法[31-34,45-47],则有效避免了以上两者的短处。FLOO-CV依然以字典成员相似性最小为原则,但新样本加入稀疏字典的条件是预测误差大于字典平均泛化误差。具体流程是,假设n时刻的字典规模为m,FLOO-CV方法根据实时字典计算每个关键点的FLOO-CV误差:

(11)

(12)

若不成立,则字典保持不变。由上可见,该方法一方面无需先验知识、根据系统自适应调整误差阈值,从而决定是否吸收新样本;另一方面没有引入额外的参数计算量,因此得到了广泛的应用。

2.2 基于参数寻优的OSKELM

以上方法虽然有效解决了图1中的第一个问题,但是第二个问题还没有得到彻底的解决。为了能够更好的追踪时变系统动态特征,参数寻优成为了下一步研究的方向。参数寻优可以分为两类,一类是自适应正则化因子,其数值会根据训练步骤而发生实时变化;另一类则是模型参数的优化,主要为正则化因子和核参数的联合优化过程。

2.2.1自适应正则化因子

非平稳时间序列的分布和变化趋势随着时间不断发生变化,要求模型考虑系统建模过程中的经验风险和结构风险。一般OSKELM可以通过正则化来控制结构风险,以平衡经验风险。值得注意的是,时变系统的结构风险也会随着区域的变化而变化,因此采用一个固定的正则化因子不足以充分描述系统的动态特性。为了进一步提高方法的有效性,文献[32-34]提出了一种可以随时变系统变化而自适应变化的正则化因子(adaptive regulation factor,ARF)。

自适应正则化方案主要流程:在OSKELM模型上构造一个新的目标函数,使得每一个训练步骤,为新加入稀疏字典的样本寻找到最优的正则化因子。损失函数是衡量系统结构风险的一个重要指标,因此文献[32-33]将损失函数作为目标函数:

(13)

通过计算损失函数对于正则化因子的梯度,得到受正则化参数影响的2个系数函数,并建立动态学习率来保证算法的稳定性和收敛性,在稳定收敛的前提下,根据系数函数得到新插入样本对应的正则化因子。事实上也证明,采用稀疏字典与自适应正则化因子相结合的OSKELM,比仅采用稀疏字典的方法具有更高的建模精度、更快的收敛速度和更好的稳定性。文献[34]采用了相同的损失函数,但正则化因子的寻优过程采用了天牛须算法,该方法相比计算梯度和动态学习率的寻优过程,显示出更优的性能效果。

2.2.2核参数优化

一般的参数初始化都采用随机赋值、或者经验赋值,然后通过网格搜索法找到效果相对最优的参数值。这种方法不仅耗时耗力,还不能确保所找参数值为最优。基于以上不足,文献[35-44]通过了KELM方法与其他一系列方法相结合来完成正则化因子和核参数的寻优过程。其中,粒子群算法(particle swarm optimization,PSO)是应用最多的一种参数寻优辅助方法[35-36,39];此外,改进的头脑风暴优化方法(improved brain storm optimization,IBSO)[37]、萤火虫算法(firefly algorithm,FA)[38]、重力搜索算法(gravitational search algorithm,GSA)[40]在参数寻优方面也得到了应用。OSKELM的核参数和正则化因子是影响预测性能的2个重要因素,经过了参数优化的模型,在电力预测、交通数据预测、医学诊断等方面[40-44]都得到了广泛的应用和较好的性能。

2.3 基于遗忘因子的OSKELM

总结以上方法的共同点,都将纳入模型的所有有效样本视为相同价值。然而,时变系统的行为常常随着时间变化而改变,新的数据样本相比旧样本应当具有更大价值,对所有样本“权重均衡”的做法显然是不合理的。对于时间越近的样本,有必要在建模时赋予更大的参考价值。遗忘因子[45-47]的引入可以时使字典内时间更近的样本在模型中具有更大的权重,很好的解决了这一问题。

2.3.1遗忘因子

遗忘因子(forgetting factor,FF)的核心思想是根据数据样本到达的时间次序赋予不同的权值,其主要实现过程如下。假设一组如1.1节所示的数据流,则具有遗忘因子的ELM优化问题可定义为[34,45-46]:

(14)

式(14)与式(1)不同之处在于引入了参数为λ的遗忘因子,且0≤λ<1。求解上式可得输出权重为βn=HT(C-1λnB-1+HHT)-1yn,其中B=diag{λn-1,λn-2,…,1}。进一步令An=C-1λnB-1+HHT,则核权重向量可表示为式(4)所示。此时具有遗忘因子的KELM输出形式如式(3)所示。

遗忘因子的引入考虑了各个样本的时间差异性,实现字典中的样本具有不同的权重分布。相比未加入遗忘因子的方法,遗忘因子的应用使得训练时间进一步缩短,预测精度与稳定性也得到了较大的提升。

2.3.2自适应遗忘因子

考虑复杂时变环境下数据流的变化速率可能是不规律的,这种情况下固定的遗忘因子不能确保对时变系统的动态变化有全局自适应性,因此有必要引入自适应的遗忘因子(Adaptive FF,AFF)[47]。当系统变化较快时,预测误差将增大,遗忘因子应相应减小以加速遗忘旧的失效状态并及时跟踪时变系统的最新状态;而当系统变化较慢或趋于平稳时,随着预测误差的降低,遗忘因子应相应增大以提高系统在稳态下的预测精度。AFF的应用过程如下:

定义n时刻的遗忘因子为参数λn, 0<<λn<1,且λn随时间变化进行自适应调整。则融入AFF的KELM可定义为:

(15)

那么输出权重可以表示为β=HT(C-1λnB-1+HHT)- 1yn,其中。进一步令An=C-1λnB-1+HHT,再根据式(4)和式(3)得到核权重向量与输出形式。

根据定义,AFF的取值应与相对误差有关。首先定义一个关于相对误差的中间变量φn:

(16)

其中0<<μ1<1为误差平衡系数,主要用于控制2个值的比重; 0<μ2<<1为误差敏感系数,主要用于控制φn趋近于0的速率,当系统收敛误差较大时,μ2的取值相对较小,反之亦然。同时μ1+μ2<1以确保φn在收敛后期的单调下降特性。

以φn为基础,AFF可按式(17)进行更新计算。其中0.9<<λ+≤1表示AFF的上限,0<<λ-<1表示遗忘因子的下限,取值与具体问题相关,但不宜过小以免产生系统的不稳定。

(17)

实验验证[47]了AFF同时兼具环境在非平稳状态时的快速跟踪能力、和环境在平稳状态下的持续学习能力,相比固定FF,在少量增加计算量的前提下具有更强的系统追踪能力。

2.4 其他方法

2.4.1多变量预测

当预测模型包含多个变量时,可见上述模型均基于变量自身历史时间序列信息进行在线预测。事实上,一个系统的各变量常常相互影响,因此对变量预测不仅要考虑变量本身的历史状态,也要考虑相关变量的状态。由于各个变量时间序列的在线预测所选择的稀疏字典有一定差异,人们常以多变量为输入、某一单变量为输出进行实验[47-50]。

通过设置时间延迟和嵌入维度,将多变量进行相空间重构,可使变量间的时间相关性转换成空间相关性,从而对其中一个单变量进行预测。其实现过程为:假设一个M维多变量时间序列{X1,X2,…,XN},其中Xi=(x1,i,x1,i,…,xM,i),i=1,2,…,N。通过相空间重构可得输入向量:

vn=[x1,n,x1,n-τ1,…,x1,n-(d1-1)τ1,

x2,n,x2,n-τ1,…,x2,n-(d1-1)τ1,…,

xM,n,xM,n-τ1,…,xM,n-(d1-1)τ1]

(18)

其中τi、di分别表示延迟时间和嵌入维度,i=1,…,M,多变量时间序列输出为yn=[y1n,y2n,…,yMn],则维度为i时的预测输出值为yin=xi(n+1)=fi(v(n)),由式(3)可得。确定τi和di后,重构相空间内的输入向量即可用于建模预测。通过多个实例应用可见,相比单变量预测,多变量输入在付出极少时间代价的前提下,的确具有更好的性能效果。

2.4.2组合方法

除了以上的方法,学者们还将OSKELM与一些方法相组合以改进算法的性能,如与支持向量机和小波变换[51]、递归多步算法和漂移检测器机制[52]等,以实现时间序列的预测。这种方法的融合满足了时变系统对某些特定预测任务的需求,有效解决了特定问题,但其一般应用性有待验证。

3 算法比较与分析

在实际的OSKELM改进算法中,为了有效提高图1所示的2种能力,大多数同时应用了稀疏化方法和追踪系统时变状态的方法。根据改进算法追求目标的区别,本节将按分类对各种改进算法进行比较与分析。

1) 从算法复杂度角度,相比滑动时间窗,稀疏字典增加了了决定是否吸收新样本、以及选择所要删除样本索引的步骤,所以具有更高的算法复杂度;稀疏字典中,随着吸收新样本的判定准则提高,复杂度也随之上升,因此固定阈值的 ALD准则复杂度为最低;瞬时信息量和积累一致性由于引入了额外的参数与计算量,其复杂度要高于FLOO-CV方法。在追踪时变系统动态特征的方法中,参数寻优类方法由于引入了额外的计算量,其复杂度大于遗忘因子;其中具有自适应变化功能的因子,算法复杂度也相应更高。

2) 从预测精度角度,滑动时间窗由于流程固定,不能实时根据样本价值吸收新样本,因此预测精度低于稀疏字典;ALD准则根据固定阈值不限制字典大小地吸收了重要样本,因此具有较好的预测效果,但与固定规模的稀疏字典相比时,效果则取决于固定规模的大小。在观察系统动态变化特征方面,遗忘因子拥有比参数寻优更高的追踪能力;不难看出,加入自适应变化的方法也比固定因子精确度更高。

3) 从稳定性的角度,除了ALD准则中具有规模不固定所带来的模型过大风险,滑动时间窗与其他稀疏字典中的样本规模固定,均有较好的稳定性。此外,用于追踪动态特征的自适应因子也在一定程度上提高了系统稳定性。

4) 从应用范围的角度,滑动时间窗与参数寻优方法既适用于单个样本的逐一学习,也可应用于样本块的批量学习,对于时效要求相对较低;而稀疏字典和遗忘因子则更多地应用于单个时间序列的学习,因此更加适用于对时效性要求高的预测问题。

4 结论

非平稳时间序列的在线预测作为一个研究热点,在KELM领域得到了广泛关注和应用。本文以OSKELM为基本算法,针对各种改进的算法,从抑制模型膨胀和追踪系统时变特征2个方面进行了分类和总结,并分别从算法复杂度、精确度、稳定性和应用范围等4个性能效果进行了比较与分析。

OSKELM在稀疏化和追踪系统时变特征方面已经得到了较为全面的研究与改进,分析以上研究成果,还有以下问题值得进一步研究:

1) 算法复杂度分析。在改进的OSKELM算法中,一般的稀疏化方法虽然提高了预测精度,但是都在一定程度上增加了算法复杂度,从而导致预测时间的增长。如何在提高预测性能的前提下控制算法的简洁性是进一步研究的课题。

2) 稳定性分析。在时变环境下,固定遗忘因子的加入显然提高了预测模型追踪时变系统动态性能的能力,而自适应遗忘因子则在固定遗忘因子的基础上进一步提高了模型的全局自适应性,但与此同时算法所需确定的参数也有所增加,这对于稳定性的提高是不利的。因此,寻找一种可以快速确定自适应遗忘因子中参数的方法非常必要。

3) 核函数分析。以上改进的方法中,主要从算法的各个参数寻优出发,参考OSELM的改进算法,算法的改进还可考虑样本加权的角度;此外,所有改进算法中均已设定了核函数,而核函数的种类是较多的,如何选择核函数也具有较大的研究价值。

猜你喜欢
时变复杂度字典
全球大地震破裂空间复杂度特征研究
数字经济对中国出口技术复杂度的影响研究
Kerr-AdS黑洞的复杂度
|直接引语和间接引语|
字典的由来
非线性电动力学黑洞的复杂度
基于马尔可夫时变模型的流量数据挖掘
大头熊的字典
基于时变Copula的股票市场相关性分析
基于时变Copula的股票市场相关性分析