Characterization of the convergence of stationary

arXiv:0802.3235v2[cs.NE]25Feb2008CharacterizationoftheconvergenceofstationaryFokker–PlancklearningArturoBerronesPosgradoenIngenier´ıadeSistemasFacultaddeIngenier´ıaMec´anicayEl´ectricaUniversidadAut´onomadeNuevoLe´onAP126,Cd.Universitaria,SanNicol´asdelosGarza,NL66450,M´exicoarturo@yalma.fime.uanl.mxAbstractTheconvergencepropertiesofthestationaryFokker-Planckalgorithmfortheesti-mationoftheasymptoticdensityofstochasticsearchprocessesisstudied.Theoret-icalandempiricalargumentsforthecharacterizationofconvergenceoftheestima-tioninthecaseofseparableandnonseparablenonlinearoptimizationproblemsaregiven.SomeimplicationsoftheconvergenceofstationaryFokker-Plancklearningfortheinferenceofparametersinartificialneuralnetworkmodelsareoutlined.Keywords:heuristics,optimization,stochasticsearch,statisticalmechanics1IntroductionTheoptimizationofacostfunctionwhichhasanumberoflocalminimaisarelevantsubjectinallfieldsofscienceandengineering.Inparticular,mostofmachinelearningproblemsarestatedlikeoftenlycomplex,optimizationtasks[1].Acommonsetupconsistinthedefinitionofappropriatefamiliesofmodelsthatshouldbeselectedfromdata.Theselectionstepinvolvestheoptimizationofacertaincostorlikelihoodfunction,whichisusuallydefinedonahighdimensionalparameterspace.Inotherapproachestolearning,likeBayesianinference[15,14],theentirelandscapegeneratedbytheoptimizationproblemassociatedwithasetofmodelstogetherwiththedataandthecostfunctionisrelevant.Otherareasinwhichglobaloptimizationplaysaprominentroleincludeoperationsresearch[12],optimaldesigninengineeneredsystems[18]andmanyotherimportantapplications.PreprintsubmittedtoElsevier26February2008Stochasticstrategiesforoptimizationareessentialtomanyoftheheuristictechniquesusedtodealwithcomplex,unstructuredglobaloptimizationprob-lems.Methodslikesimulatedannealing[13,19,9,24]andevolutionarypopula-tionbasedalgorithms[10,7,21,11,24],haveproventobevaluabletools,capa-bleofgivegoodqualitysolutionsatarelativelysmallcomputationaleffort.Inpopulationbasedoptimization,searchspaceisexploredthroughtheevolu-tionoffinitepopulationsofpoints.Thepopulationalternatesperiodsofself–adaptation,inwhichparticularregionsofthesearchspaceareexploredinanintensivemanner,andperiodsofdiversificationinwhichsolutionsincorporatethegainedinformationaboutthegloballandscape.Thereisalargeamountofevidencethatindicatesthatsomeexponentsofpopulationbasedalgorithmsareamongthemostefficientglobaloptimizationtechniquesintermsofcom-putationalcostandreliability.Thesemethods,howeverarepurelyheuristicandconvergencetoglobaloptimaisnotguaranteed.Simulatedannealingontheotherhand,isamethodthatstatisticallyassuresglobaloptimality,butinalimitthatisverydifficulttoacomplishinpractice.Insimulatedanneal-ingasingleparticleexploresthesolutionspacethroughadiffusiveprocess.Inordertoguaranteeglobaloptimality,the“temperature”thatcharacterizethediffusionshouldbeloweredaccordingtoalogarithmicschedule[8].Thisconditionimplyverylongcomputationtimes.Inthiscontributiontheconvergencepropertiesofanestimationprocedureforthestationarydensityofageneralclassofstochasticsearchprocesses,re-centlyintroducedbytheauthor[2],isexplored.Bytheestimationprocedure,promisingregionsofthesearchspacecanbedefinedonaprobabilisticba-sis.Thisinformationcanthenbeusedinconnectionwithalocallyadaptivestochasticordeterministicalgorithm.Preliminaryapplicationsofthisdensityestimationmethodintheimprovementofnonlinearoptimizationalgorithmscanbefoundin[22].Theoreticalaspectsonthefoundationsofthemethod,itslinkstostatisticalmechanicsandpossibleuseofthedensityestimationpro-cedureasageneraldiversificationmechanismarediscussedin[3].Inthenextsectionwegiveabriefaccountofthebasicelementsofourstationarydensityestimationalgorithm.Thereafter,theoreticalandempiricalevidenceontheconvergenceofthedensityestimationisgiven.Besidesglobaloptimization,thedensityestimationapproachmayprovideanoveltechniqueformaximumlikelihoodestimationandBayesianinference.Thispossibility,inthecontextofartificialneuralnetworktraining,isoutlinedinSection4.FinalconclusionsandremarksarepresentedinSection5.22Fokker–PlancklearningofthestationaryprobabilitydensityofastochasticsearchWenowproceedwithabriefaccountofthestationarydensityestimationprocedureonwhichthepresentworkisbased.ConsidertheminimizationofacostfunctionoftheformV(x1,x2,...,xn,...,xN)withasearchspacedefinedoverL1,n≤xn≤L2,n.Astochasticsearchprocessforthisproblemismodeledby˙xn=−∂V∂xn+ε(t),(1)whereε(t)isanadditivenoisewithzeromean.Equation(1),knownasLangevinequationinthestatisticalphysicsliterature[16,25],capturestheessentialpropertiesofageneralstochasticsearch.Inparticular,thegradienttermgivesamechanismforlocaladaptation,whilethenoisetermprovidesabasicdiversi-ficationstrategy.Equation(1)canbeinterpretedasanoverdampednonlineardynamicalsystemcomposedbyNinteractingparticlesinthepresenceofad-ditivewhitenoise.Thestationarydensityestimationisbasedonananalogywiththisphysicalsystem,consideringreflectingboundaryconditions.Itfol-lowsthatthestationaryconditionaldensityforparticlensatisfythelineardifferentialequation,D∂p(xn|{xj6=n=x