Mathematical Applications of Inductive Logic Progr

MathematicalApplicationsofInductiveLogicProgrammingSimonColtonandStephenMuggletonComputationalBioinformaticsLaboratoryDepartmentofComputingImperialCollege180QueensGateLondonSW72AZUnitedKingdomAbstract.TheapplicationofInductiveLogicProgrammingtoscientificdatasetshasbeenhighlysuccessful.Suchapplicationshaveledtobreakthroughsinthedo-mainofinterestandhavedriventhedevelopmentofILPsystems.TheapplicationofAItechniquestomathematicaldiscoverytasks,however,haslargelyinvolvedcom-puteralgebrasystemsandtheoremproversratherthanmachinelearningsystems.WediscussheretheapplicationoftheHRandProgolmachinelearningprogramstodiscoverytasksinmathematics.WhileProgolisanestablishedILPsystem,HRhashistoricallynotbeendescribedasanILPsystem.However,manyapplicationsofHRhaverequiredtheproductionoffirstorderhypothesesgivendataexpressedinaProlog-stylemanner,andthecorefunctionalityofHRcanbeexpressedinILPterminology.In(Colton,2003),wepresentedthefirstpartialdescriptionofHRasanILPsystem,andwebuildonthisworktoprovideafulldescriptionhere.HRperformsanovelILProutinecalledAutomatedTheoryFormation,whichcombinesinductiveanddeductivereasoningtoformclausaltheoriesconsistingofclassificationrulesandassociationrules.HRgeneratesdefinitionsusingasetofproductionrules,interpretsthedefinitionsasclassificationrules,thenusesthesuccesssetsofthedefinitionstoinducehypothesesfromwhichitextractsassociationrules.Itusesthirdpartytheoremproversandmodelgeneratorstocheckwhethertheassociationrulesareentailedbyasetofusersuppliedaxioms.HRhasbeenappliedsuccessfullytoanumberofpredictive,descriptiveandsubgroupdiscoverytasksindomainsofpuremathematics.Wesurveyvariousappli-cationsofHRwhichhaveledtoitproducingnumbertheoryresultsworthyofjournalpublication,graphtheoryresultsrivallingthoseofthehighlysuccessfulGraffitiprogramandalgebraicresultsleadingtonovelclassificationtheorems.TofurtherpromotemathematicsasachallengedomainforILPsystems,wepresentthefirstapplicationofProgoltoanalgebraicdomain–weuseProgoltofindalgebraicpropertiesofquasigroups,semigroupsandmagmas(groupoids)ofvaryingsizeswhichdifferentiatepairsofnon-isomorphicobjects.Thisdevelopmentisparticu-larlyinterestingbecausealgebraicdomainshavebeenanimportantprovinggroundforbothdeductionsystemsandconstraintsolvers.WebelievethatAIprogramswrittenfordiscoverytaskswillneedtosimultaneouslyemployavarietyofreasoningtechniquessuchasinduction,abduction,deduction,calculationandinvention.WearguethatmathematicsisnotonlyachallengingdomainfortheapplicationofILPsystems,butthatmathematicscouldbeagooddomaininwhichtodevelopanewgenerationofsystemswhichintegratevariousreasoningtechniques.c°2006KluwerAcademicPublishers.PrintedintheNetherlands.mlj04.tex;2/03/2006;17:03;p.12ColtonandMuggleton1.IntroductionIfoneweretotakemathematicstextbooksasindicatinghowmathe-maticaltheoriesareconstructed,itwouldappearthattheprocessishighlystructured:definitionsaremade,thenconjecturesinvolvingthedefinitionsarefoundandproved.However,thisbeliesthefactthatmathematicsevolvesinamuchmoreorganicway.Inparticular,itwouldappearthatmathematicsisproducedinanentirelydeductiveway.Whiledeductionandthenotionoftruthsetsmathematicsapartfromothersciences,inductivetechniquesarealsoveryimportantinthedevelopmentofmathematicaltheories.Often,lookingatparticularexamplesorcounterexamplestoatheoremandgeneralisingapropertyfoundforallofthemleadstotheoutlineofaproof.Moreover,manytheorems,includingfamoustheoremssuchasFermat’sLastTheoremandopenquestionssuchasGoldbach’sconjecture(thateveryevennumbergreaterthan2isthesumoftwoprimes),werefoundinduc-tivelybylookingatexamplesandgeneralisingresults.Indeed,somemathematicalgeniusessuchasRamanujanhavemadeentirecareersoutofanabilitytonoticepatternsinmathematicaldata(coupledwithfineanalyticalabilitiestobeabletoprovethatsuchpatternsarenotcoincidences).Theapplicationofmachinelearningtechniquestoscientificdatasetshasbeenhighlysuccessful.InductiveLogicProgramminghasbeenaparticularlyusefulmethodforscientificdiscoveryduetotheeaseofinterpretingthefirstorderhypothesesinthecontextofthedomainofinterest.SuchapplicationshaveledtobreakthroughsinthosedomainsofinterestandhavealsodriventhedevelopmentofILPsystems.TheapplicationofAItechniquestomathematicaldiscoverytasks,however,haslargelyinvolvedcomputeralgebrasystems,theoremproversandad-hocsystemsforgeneratingconceptsandconjectures.Suchad-hocsystemshaveincludedtheAMsystem(Lenat,1982)whichworkedinsettheoryandnumbertheory,theGTsystem(Epstein,1988)whichworkedingraphtheory,theILsystem(SimsandBresina,1989)whichworkedwithnumbertypessuchasConwaynumbers(Conway,1976),andtheGraffitiprogram(Fajtlowicz,1988),whichhasproducedscoresofconjecturesingraphtheorythathavegainedtheattentionofgraphtheoristsworldwide.Generalpurposemachinelearningsystemshaverarelybeenusedfordiscoverytasksinmathematics.WediscussheretheapplicationoftheHR(Colton,2002b)andProgol(Muggleton,1995)machinelearningprogramstodiscoverytasksinmathematics.WeaimtoshowthatmathematicsisachallengingdomainfortheuseoflearningsystemssuchasInductiveLogicProgramming,andwehopetopromotethemlj04.tex;2/03/2006;17:03;p