基于Nystr?m 柯西核共軛梯度算法的混沌時間序列預測*

齊樂天 王世元? 沈明琳 黃剛毅

1) (西南大學電子信息工程學院,重慶 400715)

2) (非線性電路與智能信息處理重慶市重點實驗室,重慶 400715)

混沌時間序列能夠較好反映真實環境的非線性和非平穩性特性,然而具有二階統計特性的核自適應濾波器(kernel adaptive filter,KAF)在處理含噪聲和異常值的混沌時間序列時,其預測性能顯著下降.為提高核自適應濾波器的魯棒性,本文提出了一種用于測量非線性相似度的柯西核損失(Cauchy kernel loss,CKL),并采用半平方(half-quadratic,HQ)方法保證了CKL 的全局凸性.為改善隨機梯度下降法收斂速度較慢且容易陷入局部最優的不足,采用共軛梯度(conjugate gradient,CG)方法優化CKL.進一步,為解決核矩陣網絡增長的問題,采取Nystr?m 稀疏策略近似核矩陣,并利用概率密度秩量化(probability density rank-based quantization,PRQ)提高逼近精度.基于此,本文提出了一種新的基于Nystr?m 和PRQ 的柯西核共軛梯度(Nystr?m Cauchy kernel conjugate gradient with PRQ,NCKCG-PRQ)算法有效實現了混沌時間序列的預測.基于合成和真實兩類混沌時間序列驗證了所提NCKCG-PRQ 算法在穩態性能,魯棒性和計算存儲復雜度上的優勢.

1 引言

混沌現象[1]作為一種類似隨機的無規律行為,是由不附加隨機因素的確定性非線性動力學系統產生.由于現實環境常具有非線性和非平穩性,故混沌系統在很大程度上能夠重構現實世界的非線性系統.然而,混沌系統對初始值的敏感特性使得其長期行為不可精準預測;而混沌吸引子的確定性動力學機制使得混沌時間序列具有較為準確的短期預測性[2].因此,混沌時間序列的有效預測是重構混沌系統的基礎,具有重要的實際意義和挑戰性;精準的預測方法能夠被廣泛應用于保密通信、情感學習、電力系統短期負荷預測、天氣預測[3-4]等領域.然而,在實際應用中,混沌信號常受到不同程度的噪聲干擾,因此如何最大限度地在各類噪聲環境下實現混沌序列的精準預測,已經成為混沌信號處理的研究熱點.混沌時間序列的預測方法可分為全局預測法[5]、局部預測法[6]和自適應預測法[7].其中,全局預測法采用全部樣本數據擬合非線性函數,但當樣本數據量大時運算速度較慢[8-9];局部預測法因僅利用部分數據用于預測,運算速度較快但預測精度較低[10-11].作為一種全局預測法以及局部預測法的擴展,自適應預測法將自適應濾波算法融合于前兩類方法中[12-13].相比于經典的局部預測法和全局預測法,自適應預測法因其參數配置簡單、混沌運動軌跡的自適應跟蹤特性、良好的去噪特性、以及在小數據量前提下仍具備較高的預測精度等諸多優點,已在現實環境中得到廣泛應用[14].因能夠根據混沌序列的變化自動調整模型參數的特性,自適應預測法為混沌時間序列預測提供了一種新的思路,但因采用的自適應濾波算法收斂速度不夠快限制了其在實際應用的實時性.

考慮到現實環境中的數據常具有非線性特征,使得基于線性結構的自適應濾波系統在處理非線性問題時存在局限性.為此,核方法(kernel method)將輸入信號非線性映射到高維再生核希爾伯特空間中,然后在特征空間中執行線性濾波,發展出了核自適應濾波(kernel adaptive filter,KAF),如基于均方誤差(mean square error,MSE)和最小二乘(least squares,LS)準則的核最小均方算法[15]和核遞歸最小二乘算法[16].在自適應濾波算法中,代價函數,權重更新方式和稀疏策略決定了混沌時間序列預測性能.

優化方法是KAF 算法中權向量更新的關鍵.從本質上講,優化方法的選取決定了算法的計算復雜程度和收斂速度.隨機梯度下降(stochastic gradient descent,SGD) [22]法因其簡單,在KAF得到廣泛應用.然而,基于SGD 的濾波算法通常容易陷入局部最優,導致性能下降.作為SGD 方法的延拓,牛頓法和共軛梯度法(conjugate gradient,CG)[23]能更好地求解誤差函數.但是,在牛頓法中需要保證海森矩陣(Hessian matrix)的正定性并計算海森矩陣的逆,這在一定程度上增加了計算復雜度,限制了其實際應用[24].CG 法能夠平衡收斂速度和計算復雜度.與SGD 法相比,CG 法不僅提高了算法收斂速度,并且在計算復雜度較低的情況下取得了與遞歸算法相當的性能[23].但是,相比于牛頓法,CG 法因不需要計算海森矩陣的逆,所以能夠獲得更加穩定的解.

通常,KAF 采用高斯核實現在線學習,即根據每一個新輸入的數據對系統參數進行學習.然而,大規模的數據導致網絡尺寸線性增長,增加了計算量和空間存儲,這對KAF 的在線實際應用提出了巨大挑戰.抑制KAF 網絡增長的方法主要包括量化[25]和稀疏化策略.但是,量化和稀疏化策略均不能預先設定網絡結構大小,用以滿足特定計算和存儲要求.Nystr?m 方法采用近似法重構矩陣[26],將高維度問題轉化為低維度空間,通過固定維網絡結構來逼近KAF 中的核矩陣,并在逼近精度和計算復雜度兩方面實現了平衡.然而,Nystr?m 方法中常采取的抽樣策略是隨機抽樣[27]和k-均值抽樣[28].由于兩種抽樣方法具有對初始樣本選擇的敏感性,所以其逼近精度通常無法達到預期效果.基于此,提出了基于概率密度秩的量化(probability density rank-based quantization,PRQ)[29]采樣方法進一步提高近似精度.

受啟發于半平方(half-quadratic,HQ) [24]方法轉化CKL 后代價函數的全局凸性和魯棒性,本文根據混沌時間序列的短期可預測性,在CG 優化方法上引入了基于PRQ 采樣的Nystr?m 方法,提出了一種新的基于PRQ 采樣的Nystr?m 柯西核共軛梯度 (Cauchy kernel conjugate gradient,CKCG)算法(NCKCG-PRQ).所提的NCKCG-PRQ 算法在預測麥克格拉斯(Mackey-Glass,MG)混沌時間序列和實際電路采集的蔡氏混沌時間序列的兩類實例中,展現了在非高斯噪聲環境下預測性能的強魯棒性、低穩態誤差及低計算復雜度的特點.

2 背景介紹

本節首先介紹柯西核代價函數,接著采用HQ方法將柯西核函數轉化為具有二次型形式的全局凸函數,最后采用Nystr?m 法對矩陣進行有效重構.

2.1 柯西核代價函數

顯然,柯西核函數不是一個全局凸函數.

2.2 半平方法轉化柯西核函數

由于 (3)式的海森矩陣只有在滿足一定條件時才是正定的,因此不能始終保證其全局凸性,這就限制了柯西核函數在解決凸優化問題中的應用.實際上,柯西核函數可以看作一個由具有對數函數形式的柯西函數和指數函數形式的相關熵函數映射而來的復合函數,借助兩次半平方優化法使柯西核函數轉化為全局凸函數.因轉化后的數學表達式為二次型形式,所以能夠有效解決凸優化和共軛梯度優化的問題.

對于應收賬款的估價，一般來說，有三種方法：成本法、市場法和收益法。成本法與市場法不能適應應收賬款的市場需求。對于收益法，一條原理指出：資產的價值等于它將來給所有者帶來的經濟利益的凈現值。而應收賬款作為一種債權，未來會給其所有者帶來經濟利益，故采用收益法。因此，選擇正確的資產估價方法，是應收賬款證券化能否交易成功的關鍵。

此時,(2)式中求解柯西核函數的最優解問題等價于求解如下問題:

其中,viηsiexp(?si)?f(vi) 是關于vi獨立函數.(9)式的求解可以通過交替優化方法實現.借助 (8)式可以解得vi的解析解是vi=?[1+ηsiexp(?si)]?1,其中vi是一個負數.給定vi,(9)式的優化問題等價于如下形式:

不難看出,(11)式是一個全局凸函數且其中包含了共軛梯度優化方法所需要的二次型形式.(11)式中加權最小二乘問題的海森矩陣如下:

由于vi小于0 且ηsi大于0,所以海森矩陣是正定的,保證了全局凸性.(11)式的解可通過半二次方法求解加權最小二乘問題得到.由此可知,半平方法對柯西核函數的轉化打破了海森矩陣中參數δ和η關于誤差e的限制條件,進一步促進了柯西核函數在凸優化問題中的應用.

2.3 Nystr?m 方法

將原始輸入u(i) 映射到再生核希爾伯特空間中,可得輸入φ(u(i)) 的數據矩陣Φ ∈RD×n為

因此,采用Nystr?m 方法生成固定維數為m的特征空間,可有效降低計算和空間復雜度.

3 基于PRQ 采樣的Nystr?m 柯西核共軛梯度

3.1 在線NCKCG 算法

在自適應濾波預測的在線學習中,根據特征空間中變換后的輸入z(uk),將非線性系統表示為

則殘差向量的遞歸形式為:

最后,結合 (20)—(27)式,得到NCKCG 算法.

3.2 概率密度秩的量化采樣

在Nystr?m 稀疏策略[29]中,采樣方法的選取對矩陣近似起著至關重要的作用,將直接影響低秩矩陣的近似精度.直接選取任意m列訓練數據重構的低維矩陣可能在很大程度上不能反映數據集的整體特征,在數據存在有大異常值情況下,隨機采樣方法并不能獲得預期的近似精度.此外,k-均值采樣法采用預先設定的閾值距離來獲取迭代所對應的樣本點,容易選取少數無效的邊界值或離群值,降低了近似精度.為了保證近似精度,采用PRQ的自適應采樣法,選擇信息量更大的列,使得所選數據包含更多的有效信息.PRQ 采樣通過將原始數據替換為對應聚類中的地標點,有效避免了隨機采樣和k-均值采樣均存在的初始點選取問題.

表1 NCKCG-PRQ 算法Table 1.NCKCG-PRQ algorithm.

4 仿真結果及分析

為驗證本文所提NCKCG-PRQ 算法在混沌時間序列預測的有效性,選擇兩類混沌時間序列,即數值仿真的MG 混沌時間序列[34]和由真實蔡氏電路產生的混沌時間序列[31].

4.1 仿真實驗模型

4.1.1 混沌時間序列模型

MG 混沌時間序列因其具有周期性和混沌動力學特性,被廣泛地應用于非線性系統建模.因此,考慮使用這個例子來驗證本文所提出的NCKCGPRQ 算法在非高斯噪聲環境下的優越性.MG 混沌時間序列由下式產生:

式中,時滯參數τ影響了系統的混沌特性.τ大于17 時,系統呈現混沌,且其值越大,混沌程度越高,本文τ設置為30.在采樣周期為6 s 時,對時間序列進行離散化.為實現混沌時間序列的預測,選取之前的7 個樣本點 [st?1,st?2,···,st?7] 預測當前值st.

4.1.2 蔡氏混沌時間序列模型

蔡氏電路可以產生一個現實存在的混沌時間序列.為獲取真實世界的混沌時間序列,建立了如圖1 所示的電路系統.電源模塊將220 V 電壓轉換為12 V 電壓用于蔡氏電路.系統搭建中主要采用LM358 運放,100 nF 和10 nF 各一個以及功率直插電感20 mH,詳細的電路原理圖如圖2 所示.

選取圖2 中電容C2之間的電壓值作為蔡氏混沌時間序列,即圖1 中示波器的綠色波形所示.在此次仿真實驗中,預測C2之間的電壓值并將其標準化為 0—0.1 用以保證實驗預測精度.之前最近的5個電壓值被用作輸入來預測當前的電壓值.

圖1 示波器示意圖Fig.1.Schematic diagram of oscilloscope.

圖2 蔡氏電路原理圖Fig.2.Schematic diagram of the Chua’s circuit.

4.2 噪聲環境

為了驗證算法在非高斯環境下的魯棒性,采用如下的混合高斯噪聲模型,即:

噪聲模型中,qa(i) 是零均值且方差為=0.0016的高斯噪聲;qb(i) 是用于建模脈沖噪聲的α-stable分布[35],其參數為Vα?stable(0.8,0,0.1,0) ;b(i) 是伯努利二項分布發生的概率,P r{b(i)=1}=c且Pr{b(i)=0}=1?c,仿真中選取c=0.1.在仿真實驗中一個包含2000 個樣本點的數據集添加非高斯噪聲后用作訓練,另外干凈的200 個樣本點用作測試,并另選200 個樣本點用于Nystr?m 近似.為了比較預測精度,測試采用如下所示的MSE(單位為dB):

4.3 仿真結果及分析

圖3 所示為不同采樣點個數 對NCKCG-PRQ算法的穩態MSE 值和平均運算時間的影響.從圖3(a)可以看出:1)平均運算時間隨m的增大而延長;2) NCKCG-PRQ 算法濾波精度可以通過增大m的方法在一定程度上提高,當m為80 時,其濾波精度趨于穩定;3)m維數越大,濾波精度越高,但計算時間越長.當m為60 時,運算時間約為1.5 s;而當m為80 時,運算時間約為2.5 s.當m從60 增至80 時,濾波精度提高所帶來的優勢不及運算時間增加帶來的計算負擔.因此,綜合濾波精度和計算時間兩方面,在MG 混沌時間序列仿真中將采樣點設置為60.為公平起見,所有參與比較的稀疏算法的采樣點個數均設置為60.從圖3(b)可以看出,隨著m增大,濾波精度先增大而后減小,但運算時間是一直延長的.在m=13 時,濾波精度達到最高.因此,同時考慮濾波精度和運算時間兩方面,在蔡氏混沌時間序列仿真中最優的采樣點個數為13.故參與比較的稀疏算法采樣點數目也同樣設置為13.

圖3 不同采樣點個數 m 對NCKCG-PRQ 算法的穩態MSE 值和平均運算時間的影響 (a) MG 混沌時間序列;(b) 蔡氏混沌時間序列Fig.3.Influence of different number of sampling points on steady-state MSE value and average operation time of NCKCG-PRQ algorithm:(a) MG chaotic time series;(b)chaotic time series based on Chua’s circuit.

比較算法包含CKCG[30]算法,隨機傅里葉特征柯西共軛梯度(random Fourier features Cauchy conjugate gradient,RFFCCG)[36]算法,Nystr?m核遞歸廣義最大相關熵 (Nystr?m kernel recursive generalized maximum correntropy with PRQ sampling,NKRGMC-PRQ)[29]算法,Nystr?m 核共軛梯度 (Nystr?m kernel conjugate gradient based on k-means sampling,NKCG-KM)[28]算 法.其中,CKCG 算法是采用具有魯棒特性的柯西核函數作為代價函數,通過CG 有效優化該代價函數,但隨著輸入數據的不斷加入,核矩陣規模不斷增大,計算存儲負擔加重.CKCG 算法因其魯棒性強、濾波精度高和運算時間長的特點,是未經過稀疏處理的典型代表.RFFCCG 算法是采用魯棒柯西函數作為代價函數,通過CG 方法優化該代價函數,利用隨機傅里葉特征和均勻隨機數來近似核函數,因此具備低計算復雜度且與傳統核算法相當的性能,是固定維度稀疏算法的代表.NKRGMCPRQ 算法采用信息論學習(information theoretic learning,ITL)準則中廣泛采用的廣義最大相關熵準則作為代價函數,通過經典的遞歸更新方式、基于Nystr?m 低秩近似的核矩陣以及PRQ 采樣方法進一步提高了濾波精度.NKCG-KM 因采用傳統二階誤差準則作為代價函數在非高斯環境下不具備魯棒性.因此,為了全面體現所提NCKCGPRQ 算法的優越性,本文是從代價函數的魯棒性、優化方法、稀疏策略以及采樣方法選擇比較算法.為了體現比較的公平性,對所有參與比較的算法參數進行設置,使其都達到理想的濾波精度.

算法的學習曲線和具體的參數選擇如圖4 所示.其中,σ=0.5 是CKCG 中柯西核代價函數的核帶寬,λ=0.25 是柯西核函數參數;α=2 和σ=0.6 是NKRGMC-PRQ 參數;γ=0.3 為RFFCCG中柯西代價函數參數;λ=0.999 是NKCG-KM 算法遺忘因子;δ=0.5 和η=0.25 是NCKCG-PRQ算法柯西核代價函數參數.

各個算法的平均字典個數大小(即采樣點數目),平均計算時間和穩態MSE 的詳細仿真結果如表2 和表3 所示.從圖4 可以看出,由于脈沖噪聲的存在,NKCG-KM 算法的性能出現發散,由此可知基于二階統計測度的算法在脈沖噪聲下不具備魯棒性.利用柯西損失來懲罰噪聲項,使基于柯西核代價函數的NCKCG-PRQ 算法對非高斯噪聲,特別是重尾噪聲有很好的抑制效果.從表2 和表3可知,與稀疏算法NKRGMC-PRQ 和RFFCCG相比,從穩態MSE 角度比較,所提的NCKCG-PRQ算法具有最好的濾波精度;從運算時間角度比較,所提的NCKCG-PRQ 算法具有最短的運算時間.NCKCG-PRQ 算法在低計算復雜度下最大程度逼近了高計算復雜度CKCG 算法的濾波精度.圖5是顯示了測試集中驗證所提算法的預測結果,其中,縱坐標已作歸一化處理.從圖5 可知,在合成數據的MG 混沌時間序列中所提算法在該仿真實驗中能夠有效地實現混沌序列的預測;在真實采集的蔡氏電路混沌時間序列中,所提算法基本實現了真實值和預測的輸出值的擬合.由此可知,無論是在仿真的MG 混沌時間序列還是真實蔡氏電路產生的混沌時間序列,所提的NCKCG-PRQ 算法在魯棒性,穩態性能和計算復雜度上均具有較大的優勢.

圖4 在脈沖噪聲環境下不同算法的測試MSE 學習曲線 (a) MG 時間序列 ;(b)蔡氏混沌時間序列Fig.4.Testing MSE learning curves of different algorithms in impulsive noise environment:(a) MG chaotic time series;(b) chaotic time series based on Chua’s circuit.

圖5 NCKCG-PRQ 算法對測試數據的最終預測結果 (a) MG 混沌時間序列;(b) 蔡氏混沌時間序列Fig.5.Final predicted results of NCKCG-PRQ algorithm for the test sets:(a) MG chaotic time series;(b) chaotic time series based on Chua’s circuit.

表2 不同算法在MG 混沌時間序列中的仿真結果Table 2.Simulation results of different algorithms in MG chaotic time series.

表3 不同算法在蔡氏電路混沌時間序列中的仿真結果Table 3.Simulation results of different algorithms in chaotic time series based on Chua′s circuit.

5 結論

本文將基于PRQ 采樣的Nystr?m 方法作為稀疏策略應用于核共軛梯度優化法,有效地抑制了核共軛梯度法的核矩陣網絡規模增長.進一步,采用半平方法轉化柯西核函數生成全局凸的魯棒函數作為核共軛梯度法的代價函數,提出了一種新的具有魯棒性的基于PRQ 采樣的NCKCG-PRQ 算法.NCKCG-PRQ 在存儲需求較低的情況下,與沒有采取稀疏策略的CKCG 算法擁有近乎相當的濾波精度.在數值仿真的MG 混沌時間序列和由蔡氏電路真實產生的混沌時間序列的預測中,結果表明在存在脈沖噪聲的情況下,NCKCG-PRQ 與其他固定維度的自適應濾波器相比,具有較低計算復雜度和較高的預測精度,有效證實了所提NCKCG-PRQ 算法在混沌時間序列預測中的性能優勢.