Programming and Logic Grammars

Page1AFlexibleKnowledgeDiscoverySystemUsingGeneticProgrammingandLogicGrammarsManLeungWongDepartmentofCo[e-mail]2AFlexibleKnowledgeDiscoverySystemusingGeneticProgrammingandLogicGrammarsAbstractAsthecomputingworldmovesfromtheinformationageintotheknowledge-baseage,itisbeneficialtoinduceknowledgefromtheinformationsuperhighwayformedfromtheInternetandintranet.Knowledgediscoveryindatabasesisdefinedasthenon-trivialprocessofidentifyingvalid,novel,potentiallyuseful,andultimatelyunderstandablepatternsindatastoredindatabases.Theknowledgeacquiredcanbeexpressedindifferentknowledgerepresentationssuchascomputerprograms,first-orderlogicalrelations,orFuzzyPetriNets(FPNs).Inthispaper,wepresentaflexibleknowledgediscoverysystemcalledLOGENPRO(TheLOgicgrammarbasedGENeticPROgrammingsystem)thatappliesgeneticprogrammingandlogicgrammarstolearnknowledgeinvariousknowledgerepresentationformalisms.Thesystemisalsopowerfulenoughtorepresentcontext-sensitiveinformationanddomain-dependentknowledge.AnexperimentisperformedtodemonstratethatLOGENPROcandiscoverknowledgerepresentedinFPNsthatsupportfuzzyandapproximatereasoning.ToevaluatetheperformanceofLOGENPROinproducinggoodFPNs,theclassificationaccuracyofthefuzzyPetrinetinducedbyLOGENPROandthatofthedecisiontreegeneratedbyC4.5arecompared.Moreover,theperformanceofLOGENPROininducinglogicprogramsfromnoisyexamplesisevaluated.AdetailedcomparisontoFOIL,asystemthatinduceslogicprograms,hasbeenconducted.TheseexperimentsdemonstratethatLOGENPROisapromisingalternativetootherknowledgediscoverysystemsandsometimesissuperiorforhandlingnoisyandinexactdata.Area:KnowledgeDiscoveryinDatabases,GeneticProgramming,LogicGrammars,FuzzyPetriNets1.IntroductionAsthecomputingworldmovesfromtheinformationageintotheknowledge-baseage,itisbeneficialtoinduceknowledgefromtheinformationsuperhighwayformedfromtheInternetandintranet.Knowledgediscoveryfromvariousdatasourcesofthenewinformationinfrastructureisconcernedwiththenon-trivialextractionofimplicit,previouslyunknown,andpotentiallyusefulinformationfromthem(Fayyadetal.1996,Frawleyetal.1991,Piatetsky-ShapiroandFrawley1991).TheknowledgeacquiredcanbeexpressedindifferentknowledgePage3representationformalismssuchascomputerprograms,first-orderlogicalrelations,decisiontrees,decisionlists,productionrules,orPetrinets.DzeroskiandLavrachaveshowedthatInductiveLogicProgramming(ILP)canbeusedtoinduceknowledgerepresentedasfirst-orderlogicalrelations(DzeroskiandLavrac1993,Dzeroski1996).ResearchinILPcanbeclassifiedintoempiricalandinteractiveILP(LavracandDzeroski1994,DeRaedt1992)andseveralempiricalILPsystems,suchasCIGOL(MuggletonandBuntine1988),GOLEM(MuggletonandFeng1990),FOIL(Quinlan1990;1991),andFOCL(PazzaniandKibler1992,Pazzanietal.1991),havebeendevelopedrecently.Forexample,FOILcanefficientlylearnfunction-freeHornclauses.Itusesatop-down,divideandconquerapproachguidedbyinformation-basedheuristicstoproduceaconceptdescriptionthatcoversallpositiveexamplesandexcludesallnegativeexamples.FOCLextendsFOILbyintegratinginductiveandanalyticlearninginauniformframeworkandbyallowingdifferentformsofbackgroundknowledgetobeusedingeneratingfunction-freeHornclauses.AnotherapproachofknowledgediscoveryisGeneticProgramming(GP)thatextendstraditionalGeneticAlgorithms(Holland1975,Goldberg1989,Davis1987;1991)toinduceautomaticallyS-expressionsinLisp(Koza1992;1994,Kozaetal.1999,Kinnear1994).Koza(1992)demonstratedthatdecisiontreescanberepresentedasS-expressionsinLisp.Inotherwords,GPcanbeusedtodiscoverknowledgefromdatabases.Theproblemofdiscoveringknowledgefromdatabasescanbereformulatedasasearchforahighlyfitprograminthespaceofallpossibleprograms(Mitchell1982).ThesearchspaceofILPisdeterminedbythesyntaxoflogicprogramandthebackgroundknowledge.InGP,thisspaceisdeterminedbythesyntaxofS-expressioninLispandthesetsofterminalsandfunctions.Thus,thesearchspaceisfixedoncetheseelementsaredecided.Inthispaper,wepresentaflexibleknowledgediscoverysystem(LOGENPRO),ageneralizationandextensionofGLPS(WongandLeung1995),thatcombineILPandGPtoinduceknowledgefromdatabases.LOGENPRO(TheLOgicgrammarbasedGENeticPROgrammingsystem)isbasedonaformalismoflogicgrammarsanditcanspecifythesearchspacedeclaratively.Thesystemispowerfulenoughtorepresentcontext-sensitiveinformationanddomain-dependentknowledgeusedtoacceleratethelearningofknowledge.LOGENPROisalsoveryflexibleandtheknowledgeacquiredcanberepresentedindifferentknowledgerepresentationssuchascomputerprograms,fuzzyPetrinets,first-orderlogicalrelations,and/orfuzzyrelations(Wong1998,WongandLeung2000).Page4ThenextsectionpresentstheformalismoflogicgrammarsandthedetailsofLOGENPRO.Petrinets,adirectedbipartitegraphwithahighdegreeofstructuralparallelismandpipelining,isanidealknowledgerepresentation(Peterson1981).However,Petrinetscannotrepresentimprecise(fuzzy),incomplete,anduncertaininformation.Consequently,Chenetal.(1990)proposedtheFuzzyPetriNets(FPNs)formalismthatprovidesaneffectiveandefficientreasoningproceduretodeduceinformationfrominexactknowledge.Inse