active coevolutionary learning of deterministic finite automata - 2005new

《active coevolutionary learning of deterministic finite automata - 2005new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、JournalofMachineLearningResearch6(2005)1651–1678Submitted8/04;Revised6/05;Published10/05ActiveCoevolutionaryLearningofDeterministicFiniteAutomataJoshBongardJOSH.BONGARD@CORNELL.EDUHodLipsonHOD.LIPSON@CORNELL.EDUComputationalSynthesisLaboratorySibleySchoolofMechanicalandAerospaceEngineeringI

2、thaca,NY14853,USAEditor:StefanWrobelAbstractThispaperdescribesanactivelearningapproachtotheproblemofgrammaticalinference,specif-icallytheinferenceofdeterministicfiniteautomata(DFAs).Werefertothealgorithmastheestimation-explorationalgorithm(EEA).Thisapproachdiffersfrompreviouspassiveandactive

3、learningapproachestogrammaticalinferenceinthattrainingdataisactivelyproposedbytheal-gorithm,ratherthanpassivelyreceivingtrainingdatafromsomeexternalteacher.Hereweshowthatthisalgorithmoutperformsoneversionofthemostpowerfulsetofalgorithmsforgrammaticalinference,evidencedrivenstatemerging(EDSM

4、),onrandomly-generatedDFAs.TheperformanceincreaseisduetothefactthattheEDSMalgorithmonlyworkswellforDFAswithspecificbal-ances(percentageofpositivelabelings),whiletheEEAismoreconsistentoverawiderrangeofbalances.BasedonthisfindingweproposeamoregeneralmethodforgeneratingDFAstobeusedinthedevelopme

5、ntoffuturegrammaticalinferencealgorithms.Keywords:grammaticalinference,evolutionarycomputation,deterministicfiniteautomata,activelearning,systemidentification1.IntroductionGrammaticalinferenceisapopularmachinelearningdomain(refertoCicchelloandKremer,2003,foranoverview):ithaswideapplicabilityi

6、nbothcomputationallinguisticsandrelatedfields,aswellasgivingrisetoahostofbenchmarkproblems(Tomita,1982;Langetal.,1998)andcompe-titions.Grammaticalinferenceisaspecialcaseofthelargerproblemdomainofinductivelearning(BergadanoandGunetti,1995),whichaimstoconstructmodelsofsomeunderlyingsystembased

7、onsetsofpositiveandnegativeclassifications.Inoneclassofgrammaticalinferencemethods,thesystemisconsideredtobesomekindoflanguageorclassifier,andmodelsarerepresentedasdeterministicfiniteautomata(DFA).Boththetargetsystemandmodelstakestringsofsymbolsasinput(sent