Dynamic reconstruction of a chaotic process using regularized RBF networks

Simon Haykin

Communications Research Laboratory

McMaster University

Hamilton, Ontario, Canada L8S 4K1

Abstract

Inthispaperweaddresssomefundamentalissuespertainingtothedynamicreconstructionofachaoticprocess,givenanobservabletimeseriesoftheprocess.Theissuesconsideredare(1)thestabilityofaniteratedpredictionsystembuiltaroundapredictivemodel,and(2)theaccuracyofdynamicreconstruction.Althoughthesetwoissuesaddressdifferentaspectsoftheproblem,inapractical setting they do impinge on each other in a profound way.I.

Introduction

Inthispaperweaddresssomefundamentalissuespertainingtothedynamicreconstructionofachaoticprocess.Theprimarymotivationofdynamicreconstructionistomakephysicalsensefromanexperimentaltimeserieswithoutknowledgeoftheunderlyingphysicsoftheproblem.Tobespecific,consideranunknowndynamicalsystemwhoseevolution(measuredindiscretetime)is described by thestate-space model:

x(n+1)=f(x(n))

y(n)=h(x(n))+w(n)

(1)(2)

wherex(n)isthed-dimensionalstatevectorofthesystematdiscretetimen,f(.)isavector-val-uednonlinearfunctionofitsargument,y(n)istheonlyobservableofthesystem,h(.)isascalar-valuednonlinearfunctionofitsargument,andw(n)isadditivenoise.Equation(1)istheprocess(state)equationofthesystem,andEq.(2)isitsmeasurement(observation)equation.Notethattheprocessequationisnoiseless,butthemeasurementequationisnoisy.Inparticular,thenoisew(n) represents the combined effects of receiver noise and errors due to imprecise measurements.Theobservabletimeseries{y(n)}maybereal-orcomplex-valued.Inanyevent,given{y(n)},howdowereconstructtheunderlyingdynamicsofthechaoticprocessdescribedbyEqs.(1)and(2)?Theanswertothisfundamentalquestionisfoundinageometrictheoremcalledthedelay-embeddingtheoremduetoTakens(1981).ThedynamicreconstructionproceedsbyformulatingtheD-dimensional vector

yR(n)=[y(n),y((n-τ),...,yn–(D-1)τ)]

T

(3)

whereτistheembeddingdelay.Inprinciple,foraninfinitelylongsequenceofinfinitelyprecisedatapointsunperturbedbynoise,thechoiceofembeddingdelayτisnotimportantanddynamic

reconstructionispossibleprovidedthatD>2d+1.Thisconditionisasufficientbutnotnecessarycondition.TheprocedureforfindingasuitableDiscalledembedding.TheminimumintegerDthatachievesdynamicreconstructioniscalledtheembeddingdimension,denotedbyDE.Thedelay-embedding theorem has a powerful implication:

EvolutionoftheobservablepointsyR(n)→yR(n+1)inthereconstructionspacefollowsthatoftheunknowndynamicsx(n)→x(n+1)in the original state space.

Thatis,manyimportantpropertiesoftheunobservablestatevectorx(n)arereproducedwithoutambiguity in the reconstruction space defined byyR(n).II.

Dynamic Reconstruction is an Ill-Posed Inverse Problem

Withthephysicalprocessresponsiblefortheobservabletimeseries{y(n)}viewedlogicallyasadirectproblem,wemayrefertodynamicreconstructionbasedon{y(n)}asinputasaninverseproblem.Moreover,inpracticewehavetodealwithafinitesequenceofnoisydatapointsasdescribedinEqs.(1)and(2).Theinevitablepresenceofadditivenoiseinthemeasurementequation(2),andthefinitelengthof{y(n)}violateHadamard’sconditionsofwellposedness.Accordingly,dynamicreconstructionusingafinitesetofnoisydatapointsisinrealityanill-posed inverse problem.

Howthendowesolvethedynamicreconstructionproblemreliably,givensuchadataset?Theanswertothispracticalquestionhasthreemainparts,assummarizedhere(HaykinandPrincipe,1998):

1.Prefiltering.Tominimizetheeffectsofadditivenoisew(n),theobservabley(n)shouldbefiltered,desirablyusingafinite-impulseresponse(FIR)filter.Carehastobeexercisedinthefilterdesigntoensurethattheunderlyingchaoticdynamicsareleftcompletelyunaltered(Haykin and Puthusserypady, 1997).2.Parameterestimation.TheembeddingdelayτandembeddingdimensionDEmustbechosen

properly.Forreliableestimationofthesetwoparameters,therecommendedproceduresare(Abarbanel et al., 1998):

•

Methodofmutualinformationforestimationτ.Accordingtothismethod,τisdefinedasthetimedelay(i.e.,anintegermultipleofthebasictimeunits)forwhichthemutualinformationbetweeny(n)anditsdelayedversionreachesitsfirstminimum.Typically,thecorrespondingminimumvalueofthemutualinformationissmall,whichindicatesthatsamplesofy(n)spacedbyτtimeunitsapartareessentiallyindependent;andyetitisnonzero, which indicates that the samples so delayed are correlated with each other.ThemethodoffalsenearestneighborsforestimatingDE.Asthenameimplies,falsenearestneighborsonanattractorarethosedatapointsthathavearrivednearoneanotherbyprojectionwhentheattractorisviewedinaspaceofdimensiontoolowtocompletely

•

unfoldit.Accordingtothismethod,DEisdefinedastheminimumdimensionforwhichthepercentageoffalsenearestneighborsisreducedtozeroforthefirsttime.TheembeddingdimensiondEisaglobaldimensionandmaywellbedifferentfromthelocaldimensionoftheunderlyingdynamics.Hence,itistheglobalversionofthemethodthatisusedtoestimateDE.ThelocalversionofthemethoddefinesthenumberoftrueLyapunovexponents,denotedbyDL.WeshouldalwaysfindthatDL3.ApproximationandRegularization.Tomakethedynamicreconstructionproblemwellposed,wehavetoincludesomeformofpriorknowledgeabouttheinput-outputmappingasanessentialrequirement.Inotherwords,someformofconstraintswouldhavetobeimposedonthepredictivemodel.AneffectivewayinwhichthisrequirementcanbesatisfiedistoinvokeTikhonov’sregularizationtheory.Anotherissuethatneedstobeconsideredistheabilityofthepredictivemodeltosolvethedynamicreconstructionproblemwithsufficientaccuracy.Inthiscontext,neuralnetworksofferthemselvesasapossiblecandidateforbuildingthepredictivemodel.Theuniversalapproximationpropertyofamultilayerperceptron,radial-basisfunctionnetworkorsupportvectormachinemeansthatwecantakecareofthereconstructionaccuracybyusingoneortheotherofthesethreestructures.Intheory,allthreestructureslendthemselvestotheuseofregularization.Inpractice,however,itisinradial-basisfunctionnetworksthatwefindregularizationtheoryincludedinamathematicallytractableandexplicitmannerasanintegralpartoftheirdesign(PoggioandGirosi,1990;Yee,1998).Regularizationmanifestsitselfalsointhedesignofsupportvectormachinesbutinanimplicit manner (Smola and Schölkopf, 1998).II.

Two Variants of the Reconstruction Vector

ThereconstructionvectoryR(n)definedinEq.(3)isofdimensionDEassumingthatthedimensionDissetequaltotheembeddingdimensionDE.Thesizeofthedelay-linerequiredtoperformtheembeddingisτDE.But,accordingtoEq.(3),thedelaylineisrequiredtoprovideonlyDEoutputs,whichisthedimensionofthereconstructionspace.Thatis,weuseτequallyspaced taps, representingsparseconnections.

Alternatively,wemaydefinethereconstructionvectoryR(n)asafullm-dimensionalvectorasfollows:

yR(n)=[y(n),y(n-1),…,y(n–m+1)]

wherem is an integer defined by

T

(4)

m≥τDE

(5)

ThissecondformulationofthereconstructionvectoryR(n)suppliesmoreinformationtothepredictivemodelthanthatprovidedbyEq.(3)andmaythereforeyieldamoreaccuratedynamicreconstruction.InMatteraandHaykin(1998),experimentalresultsarepresentedconfirmingthevalidityofthisstatement.However,theimprovementisattainedattheexpenseofincreasedmodel complexity.

ThereconstructionvectoryR(n)definestheinputvectorappliedtothepredictivemodel.Wethushave two ways of formulating the input layer of the predictive model:••

The input layer consists ofDE source nodes in accordance with Eq. (3).The input layer consists ofτDE source nodes in accordance with Eqs. (4) and (5).

Inbothcases,thesizeoftheinputlayerischosentobetheminimumpossibletominimizetheeffects of additive noisew(n).IV.

Stability Considerations

Letℵdenotethepredictivemodeldesignedtosolvethedynamicreconstructionproblem.Totestthedynamicreconstructionperformance,wemayseedthemodelℵwithapointontheattractor,andfeedtheoutputbacktoitsinputasanautonomoussystem,asillustratedinFig.1.Suchanoperationiscallediteratedprediction.Oncetheinitializationiscompleted,theoutputoftheautonomoussystemisarealizationofthedynamicreconstructionprocess.This,ofcourse,presumes that the predictive modelℵ has been designedproperly in the first place.

ExperimentalinvestigationswiththeiteratedpredictionsystemillustratedinFig.1usinganRBFnetwork have revealed the following:

1.Whenthemodelℵsuffersfromunderfitting(i.e.,thesizeofthehiddenlayerisbelowa

criticalvalue,sayh1)orwhenitsuffersfromoverfitting(i.e.,thesizeofthehiddenlayerexceeds another critical value, sayh2), the system fails by breaking into oscillation.2.Whenthesizeofthehiddenlayerliesbetweenthecriticalvaluesh1andh2,theiterated

prediction system of Fig. 1 isstable.Fromtheperspectiveofdynamicreconstruction,itisobviousthatcase1istheonetobeavoided.Asforcase2,wesaythatdynamicreconstructionperformedbytheautonomoussystemofFig.1issuccessfulifcertainconditionsaresatisfied,ensuringthatthepredictivemodelhasindeedlearnedtheunderlyingdynamicsoftheprocess.Foradiscussionofthislatterissue,seeHaykin and Principe (1998).

TheiteratedpredictionsystemdescribedinFig.1isanonlinearfeedbacksystem.Withstabilityfeaturingprominentlyinthestudyoffeedbacksystems,theexperimentalobservationssummarizedunderpoints1and2promptustoraisethefollowingfundamentalquestionsinreverse order to those two points:

Question 1

WhyisasuccessfuldynamicreconstructionrealizedbytheiteratedpredictionsystemofFig.1synonymouswithstabilityofthesystem?Question 2

WhydoestheiteratedpredictionsystemofFig.1usinganunderfittedoroverfittedpredictivemodelℵsufferfrominstability?

Tothebestofthisauthor’sknowledge,thesetwoquestionshavenotbeenaddressedintheliterature; they certainly deserve detailed attention.V.

Multistage Predictive Model

Theoverfittingproblemariseswhenwecontinueincreasingthecomplexityofthepredictiveproblemsoastoimprovethereconstructionaccuracyinaccordancewiththeuniversalapproximationtheorem.Unfortunately,aspointedoutintheprevioussection,overfittingmayleadtoinstabilityoftheiteratedpredictionsystemofFig.1.Thisproblemarisesparticularlywhenwearerequiredtobuildpredictivemodelsforcomplexchaoticprocessesexemplifiedbyseaclutter(i.e.,radarbackscatterfromanoceansurface).Suchaprocessischaracterizedbyacorrelationdimensionlyingbetween4and5andaLyapunovspectrumconsistingof5or6exponents;twooftheexponentsarepositive,oneiszero,andtheremainderarenegative(HaykinandPuthusserypady,1997).Itisindeedthemostcomplexstrangeattractordiscoveredto date.

Howthencanwebuildapredictivemodelforsuchacomplexchaoticprocess,resultinginadynamicreconstructionthatisbothaccurateandstable?OnewayofrealizingthisrequirementistouseamultistagepredictivemodelasdepictedinFig.2.PredictivemodelIoperatesonreconstructionvectoryR(n)deriveddirectlyfromtheexperimentaltimeseriesy(n).SpecialcareistakenindesigningpredictivemodelItoensurestability.HereitisrecognizedthatthereconstructionaccuracyrealizedbypredictivemodelImaynotbeadequate.Thatis,theprediction errore(n+1) produced by model I is significant.

Giventhattheoriginaltimeseriesy(n){}ischaotic,wefindthatthepredictionerrortimeseries{e(n)} is also chaotic, but more complex than {y(n)}. Specifically, we may state the following:•

The correlation dimension of {e(n)} is larger than that of {y(n)}.

•

TheLyapunovspectrumof{e(n)}hasalargernumberofexponents,morepositiveexponents, and bigger first positive exponent than those of {y(n)}.

These statements are all intuitively satisfying.

ProceedinginamannersimilartothatdescribedforpredictivemodelI,wemaydesignpredictivemodelIIdrivenbyreconstructionvectoreR(n+1).Thislattervectorisderivedfromthepredictionerrore(n+1),payingattentiontothechaoticinvariantsoftheprediction-errortimeseries. Here again, special care is taken to ensure stability of predictive model II.

Ifneedbe,wemayaddathirdstagetothestructureofFig.2,andcarryoninthemannerdescribedhereininordertoattainthedesiredreconstructionaccuracyandyetmaintainstability.Indeed,continuinginthemannerdescribedinFig.2,weeventuallyendupwitharesidualthatexhibits the characteristics of noise.

Fordynamicreconstruction,weperformiteratedpredictionaroundtheindividualpredictivemodelsandaddtheirrespectiveoutputstoproduceareconstructionoftheunknownchaoticprocess.

TheimportantpointtonotefromFig.2isthattheindividualpredictivemodelsmaynotbeaccurateenoughactingontheirown,butworkingtogetherinthemannerdescribedinFig.2theyhavethemeanstoprovidethedesireddynamicreconstructionaccuracy.Moreover,theyaredesignedtobeindividuallystable.Thus,thetwoimportantrequirementsofstabilityandaccuracyofreconstructionshould,inprinciple,beattainablewiththismultistagepredictivemodel.References

Abarbanel,H.D.I.,T.N.Frison,andL.Sh.Tsimring,1998.“Obtainingorderinaworldofchaos”,IEEE Signal Processing Magazine, vol. 15, No. 3, pp. 49-65.

Haykin,S.,andJ.Principe,1998.“Makingsenseofacomplexworld”,IEEESignalProcessingMagazine, vol. 15, No. 3, pp. 66-81.

Haykin,S.,andS.Puthusserypady,1997.“Chaoticdynamicsofseaclutter”,CHAOS,vol.7,pp.777-802.

PoggioT.,andF.Girosi,1990,“Networksforapproximationandlearning”,Proc.IEEE,vol.78,pp.1481-1497.

Mattera,D.,andS.Haykin,1998.“SVmachinesfordynamicreconstructionofachoaticsystem”.InB.Schölkopf,C.J.C.Burges,andA.J.Smola,“AdvancesinKernelMethods-Support Vector Learning”, MIT Press, 1998.

Smole,A.J.,andB.Schölkopf,1998.“Fromregularizationoperatorstosupportvectorkernels”,Advances in Neural Information Processing Systems, 1998.

Takens,F.,1981.“Onthenumericaldeterminationofthedimensionofanattractor”.InD.RandandL.S.Young,editors,DynamicalSystemsandTurbulence,Warcick1980LectureNotesinMathematics, vol. 8, pp. 366-381, Springer-Verlag.

Yee,P.1998.“RegularizedRadialBasisFunctionNetworksforProbabilityEstimation,Classification,andTime

Series Prediction”, Ph.D. Thesis, McMaster University, Hamilton, Ontario, Canada.

^y(n-1)PredictionModelℵ.^(n)y

UnitdelayFigure 1: Iterated prediction system

y(n)yR(n) TDL Memory IPredictive Model I^y(n-1)- +Σy(n+1).e(I)(n+1)eRI(n+1) TDL Memory II^(I)(n+2)ee(I)(n+2)Predictive Model II- +Σ.Figure 2: Multistage prediction model (TDL: tapped-delay-line)

eII(n+2)