Extracting Rules from a Fuzzy Crisp Recurrent Neu

()ExtractingRulesfromaFuzzy/CrispRecurrentNeuralNetworkusingaSelf-OrganizingMapA.Blanco,M.Delgado,M.C.Pegalajar*DepartamentodeCienciasdelaComputacioneInteligenciaArtificial,E.T.S.I.´Informatica,UniversidaddeGranada,AvenidadeAndalucıa,38,18071´´Granada,SpainAlthoughtheextractionofsymbolicknowledgefromtrainedfeedforwardneuralnet-.workshasbeenwidelystudied,researchinrecurrentneuralnetworksRNNhasbeenmoreneglected,eventhoughitperformsbetterinareassuchascontrol,speechrecognition,timeseriesprediction,etc.Nowadays,asubjectofparticularinterestis.crisprfuzzygrammaticalinference,inwhichtheapplicationoftheseneuralnetworkshasproventobesuitable.Inthispaper,wepresentamethodusingaself-organizingmap.SOMforextractingknowledgefromarecurrentneuralnetworkabletoinfera.crisprfuzzyregularlanguage.Identificationofthislanguageisdoneonlyfroma.crisprfuzzyexamplesetofthelanguage.Q2000JohnWiley&Sons,Inc.1.INTRODUCTION.EventhoughartificialneuralnetworksANNshavedemonstratedtheireffectivenessinmanylearningproblems,understandinghowtheyrepresenttheknowledgethattheycaptureisdifficult.AmethodforproducingasuitablerulebasetodescribeanANNshouldthereforeprovidemorethanjusttheidentifi-cationofasystem.ItshouldalsoofferasimpleexplanationassociatedtotheinternalmechanismofanANN,providinganinterpretationofit.Alearningmethodmustbuildasuitablemodelforanexampleset,buttheresultingmodelmustalsobeeasytounderstand.1]6Inthiswork,wefocusontheknowledgeextractionoftherecurrentneural.7]10networkRNNwhichiscurrentlybeingwidelystudied.Aproblemalsodealt.11,12withhereinisthefuzzyrcrispgrammaticalinference,sinceitisanappro-priatetestforinvestigatingsomeofthefundamentalissuesinRNN,suchastrainingalgorithms,knowledgerepresentationandextraction,etc.RNNswith*Authortowhomallcorrespondenceshouldbeaddressed;e-mail:[e-mail].INTERNATIONALJOURNALOFINTELLIGENTSYSTEMS,VOL.15,595]6212000Q2000JohnWiley&Sons,Inc.BLANCO,DELGADO,ANDPEGALAJAR596time-discreteinputsareabletolearndeterministicfiniteautomatafromexam-ples.IntheirstudyontheseneuralnetworksCleeremansetal.13concludedthatthehiddenunitactivationsrepresentpasthistoriesandthattheactivationclusterscanrepresentthesought-forstatesoftheautomaton.Tostartfromthisassumption,theproblemofextractingtherulesassociatedtothedeterministic.finiteautomatonDFAlearnedfromthetrainingexamplesisreducedtoexploringandanalyzingtheclustersoftheoutputspaceofthehiddenrecurrent.neurons.WehavedevelopedamethodthatdetectstheseclustersDFAstatesandthenextractsthetransitionsbetweenstatesoftheautomatonlearnedbytheRNN..14OurmethodusesKohonen’sself-organizingmapSOMsince,inouropinion,itisespeciallysuitableforthistask.TheSOMtendstoclusterpatternswithsimilarcharacteristics,withincomingpatternsbeingclassifiedbytheunitstheyactivateinthecompetitivelayer.Similaritiesamongpatternsaremappedintoclosenessrelationshipsonthecompetitivelayergrid.Afterthetrainingiscomplete,patternrelationshipsandgroupingsareobservedfromthecompeti-tivelayer.Incertaincasestheavailableexampleshaveanassociateduncertaintyorvagueness,inwhichcasefuzzygrammars,15arebestabletoexpresssuchuncertaintiesandtheneuralnetworksareabletoinferthesegrammars.Toextractthefuzzyautomatonassociatedwiththefuzzyexamples,wehavedevelopedamethodthatalsousestheSOM.Thispaperprovidesabriefintroductiontothegrammaticalinferenceproblem,thearchitectureofsecond-orderrecurrentneuralnetworks,andtheirtraininginSection2.TheextractionalgorithmoftheautomataarediscussedindetailinSection3.InSection4,wefocusonthefuzzygrammaticalinferenceproblemandtheneuralmodelusedtodofuzzygrammaticalinference.TheextractionalgorithmoffuzzyautomatafromthetrainednetworkispresentedinSection5.Finally,someconclusionsareprovided.2.CRISPGRAMMATICALINFERENCEUSINGRECURRENTNEURALNETWORKSThegrammaticalinferenceproblemhasbeenextensivelystudied11,12,16inrecentyearsduetoitsextendedfieldsofapplication:patternrecognition,informationrecovery,designofprogramminglanguages,compilationandtrans-lation,graphiclanguages,man]machinecommunication,etc.Beforedealingwiththegrammaticalinferenceproblemusingneuralnetworks,wewillshowasetofdefinitionsneededtounderstandthesubsequentdevelopmentofthiswork.2.1.Definitions.DEFINITION2.1.1.Aregulargrammar,G,isafour-tupleGsN,T,P,S,whereNisafinitesetofnonterminalsymbols,TisafinitesetofterminalEXTRACTINGRULESFROMARECURRENTNEURALNETWORK597symbols,PisafinitesetofproductionsoftheformAªaBorAªa,whereA,BgNandagT,andSisthestartingsymbol,SgN..DEFINITION2.1.2.AdeterministicfiniteautomatonDFAisastructureMs.Q,S,d,q,F,whereQisafiniteset,elementsofQarecalledstates,Sisa0finiteset,theinputalphabet,d:Q=SªQisthetransitionfunctionrecall.4.thatQ=Sisthesetoforderedpairsq,aNqgQandagS.Intuitively,disafunctionthattellsastatewheretomoveinresponsetoaninput:ifMisin.stateqandseesinputa,itmovestostatedq,a.qgQisthestartingstate0andFisasubsetofQ,elementsofFarecalledacceptorfinalstates.DEFINITION2.1.3.AstringxisacceptedbytheDFAMandhenceisa.memberoftheregularlanguageLMifanacceptingstateisreachedafterstringxhasbeenreadbyM.THEOREM2.1.1.IflanguageLisgeneratedbygrammarGthenther