Inferring subclasses of regular languages faster using RPNI and forbidden configurations.

© Lecture Notes in Artificial Intelligence Vol. 2484. Springer 2002

InferringsubclassesofregularlanguagesfasterusingRPNIandforbiddenconfigurations.∗

A.Cano,J.RuizandP.Garc´ıa.

Depto.deSistemasInform´aticosyComputaci´on.

UniversidadPolit´ecnicadeValencia.Valencia(Spain).

email:{acano,jruiz,pgarcia}@dsic.upv.es

Abstract

Manyvarietiesofregularlanguageshavecharacterizationsintermsofforbidden-patternsoftheiracceptingfiniteautomata.TheuseofpatternswhileinferringlanguagesbelongingtothosefamiliesthroughtheRPNI-Langalgorithmhelptoavoidovergeneralizationinthesamewayasnegativesamplesdo.TheaimofthispaperistodescribeandprovetheconvergenceofamodificationoftheRPNI-Langalgo-rithmthatwecallFCRPNI.PreliminaryexperimentsdoneseemtoshowthattheconvergencewhenweuseFCRPNIforsomesubfami-liesofregularlanguagesisachievedfasterthanwhenweusejusttheRPNIalgorithm.

Keywords:Varietyoflanguages,grammaticalinference,forbiddenconfigura-tions.

1Introduction

Finiteautomataidentificationfrompositiveandnegativesamplesisasolvedprobleminautomatatheory.Ifweexcludethegeneralenumerationalgorithmtherearetwoconstructivealgorithmsthatidentifyanydeterministicfiniteautomatonindeterministicpolynomialtime.

Thefirstone(TBG)isduetoTrakhtenbrotandBarzdin[21]byonehandandGold[10]bytheotherandthesecondisduetoOncinaandGarc´ıa

∗

WorkpartiallysupportedbytheSpanishCICYTundercontractTIC2000-1153

1

(RPNI)[16]andtoLang[14].ThislateralgorithmbehavesbetterthanTBGdoes[7]asitmakesbetteruseoftheinformationcontainedinthedataandthustheconvergenceisachievedmorerapidly.

Evenso,theconvergenceisstillslow,whichrestrictstheuseofthisalgorithminreallearningtasks.Severalapproacheshavebeenproposedaimingtoovercomethisdifficulty.Ifweexcludetheprobabilisticapproaches[20],[3]andweremainintheclassicalmodelofidentificationinthelimit,mostoftheproposalsconsistinthemodificationofRPNI-Langalgorithmbymeansofintroducingheuristicsthatmodifytheorderofmergingstatesfromtheprefixtreeacceptor[11],[15],[5].

Thetheoreticalinterestofthoseapproachesissomehowrelativeastheyusuallydonotguaranteetheidentificationinthelimitandthentheinferredlanguagescannotbecharacterized.

Thesituationtodaywithrespecttotheinferencefrompositiveandneg-ativesamplesissimilartothesituationexistingwiththeinferencefromonlypositivesamplesinthe80’s.Thedistinctionbetweenheuristicandcharac-terizablemethods[1]openednewpossibilitiesofresearch[2],[8],[18]etc.Angluin’sproposalcanbesummarizedasfollows:asthefamilyofregularlanguagesisnotidentifiablewiththeuseofonlypositivesamples,letusfindsubclasseswhichareidentifiableinthiswayandletusproposealgorithmsforthem.

Comingbacktoinferencefromcompletepresentationwecanpostulatethefollowingquestion:ifwerestrictourselvestotheinferenceofsubclassesofregularlanguages,canwespeeduptheconvergencewithoutdroppingtherequisiteofidentification?Thestartingpointofourproposalistoanswerpositivelytothisquestion,itseemsthatifwerestrictthesearchingspace,theidentificationprocesswillneedlessinformationtoconverge.

Researchinlanguagetheoryhasbeenfruitfulinthediscoveryofsub-classesoftheregularlanguagesfamily.Theconceptofvarietyofregularlanguages(alsoknownaspseudovariety),thatis,aclassofregularlanguagesclosedunderbooleanoperations,inversemorphismsandquotients,anditsonetoonecorrespondencewiththealgebraicconceptofpseudovarietyofsemigroups(monoids)[6]canbeusefulingrammaticalinference.

Thereexistmanyvarietiesoflanguageswhicharedecidable,meaningthatgivenaDFAthatrecognizesalanguage,itsmembershiptoacertainvarietycanbedecided.Amongthedecidablevarietieswehavethewellknownfam-iliesoffiniteandcofinitelanguages,definite,reversedefiniteandgeneralizeddefinitelanguages,locallytestableandpiecewisetestablelanguages,starfreelanguages,(see[6]or[17])etc.Notethatneitherofthosefamiliesareidenti-fiablefromonlypositivesamples.Whithoutconsideringnowfactsaboutthecomplexityofthealgorithmsforeachparticularsituation,thedecidability

2

ofthosefamiliespermitasimplemodificationoftheRPNI-Langalgorithm:eachtimethatthisalgorithmtriesamerge,besidestheusualconsiderationswehavetomakesurethattheresultingautomaton(thelanguage)canstillbelongtothevarietytowhichwehaverestrictedtheinference.

Theworkwepresentherewantstobethebeginningofaresearchinordertostudytheinfluencethatrestrictionsinthelearningdomainmayhaveinregularlanguageinferencefrompositiveandnegativedata.Wehavepaidnoattentiontotothetimecomplexityoftheproposedmethod.Itisobviousthatthiscomplexitywilldependonthevarietyunderstudyand,infact,therewillbevarietiesforwhichthismethodcouldnotbeappliedforcomplexityreasons.Wedescribethemethodandproveitconverges.Theexperimentalresultsareverylimitedandtheyarerestrictedtotwoexamplesofvarieties,thefamiliesofstar-freeandpiecewisetestablelanguages.

2Definitionsandnotation.

Inthissectionwewilldescribesomefactsaboutsemigroupsandformallanguagesinordertomakethenotationunderstandabletothereader.Forfurtherdetailsaboutthedefinitions,thereaderisreferredto[12](formallanguages)andto[6]and[17](varietiesoffinitesemigroups).

2.1Automata,languagesandsemigroups

ThroughoutthispaperΣwilldenoteafinitealphabetandΣ∗willbethefreemonoidgeneratedbyΣwithconcatenationastheinternallawandλasneutralelement.AlanguageLoverΣisasubsetofΣ∗.TheelementsofLarecalledwords.Givenx∈Σ∗,ifx=uvwithu,v∈Σ∗,thenu(resp.v)iscalledprefix(resp.suffix)ofx.

Adeterministicfiniteautomaton(DFA)isaquintupleA=(Q,Σ,·,q0,F)whereQisafinitesetofstates,Σisafinitealphabet,q0∈Qistheinitialstate,F⊆Qisthesetoffinalstatesand·isapartialfunctionthatmapsQ×ΣinQ,whichcanbeeasilyextendedtowords.AwordxisacceptedbyanautomatonAifq0·x∈F.ThesetofwordsacceptedbyAisdenotedbyL(A).

GivenanautomatonA,∀a∈Σ,wecandefinethefunctionaA:Q→QasqaA=q·a,∀q∈Q.Forx∈Σ∗,thefunctionxA:Q→Qisdefinedinductively:λAistheidentityonQand(xa)A=xAaA,∀a∈Σ.Clearly,∀x,y∈Σ∗,(xy)A=(x)A(y)A.Theset{aA:a∈Σ}isdenotedbyMA.Thesetoffunctions{xA:x∈Σ+}isafinitesemigroupundertheoperationofcompositionoffunctions,andisdenotedasSAandcalledsemigroupofA.

3

AMooremachineisa6-tupleM=(Q,Σ,Γ,·,q0,Φ),whereΣ(resp.Γ)istheinput(resp.output)alphabet,·isapartialfunctionthatmapsQ×ΣinQandΦisafunctionthatmapsQinΓcalledoutputfunction.ThebehaviorofMisgivenbythepartialfunctiontM:Σ∗→ΓdefinedastM(x)=Φ(q0·x)

atq0·xisdefined.foreveryx∈Σ∗suchth

GiventwofinitesetsofwordsD+andD−,wedefinethe(D+,D−)-prefixMooremachine(PTM(D+,D−))astheMooremachinehavingΓ={0,1,↑},Q=Pr(D+∪D−),q0=λandu·a=uaifu,ua∈Qanda∈Σ.Foreverystateu,thevalueoftheoutputfunctionassociatedtouis1,0or↑(undefined)dependingwhetherubelongstoD+,toD−ortothecomplementarysetofD+∪D−.

AMooremachineM=(Q,Σ,{0,1,↑},δ,q0,Φ)isconsistentwith(D+,D−)if∀x∈D+wehaveΦ(q0·x)=1and∀x∈D−wehaveΦ(q0·x)=0.

2.2Varietiesoffinitesemigroupsandlanguages

Afinitesemigroup(resp.monoid)isacoupleformedfromafinitesetandaninternalassociativeoperation(resp.thathasaneutralelement).

ForeveryL⊆Σ∗,thecongruence∼Ldefinedasx∼Ly⇔(∀u,v∈Σ∗,uxv∈L⇔uyv∈L),iscalledthesyntacticcongruenceofLanditisthecoarsestcongruencethatsaturatesL.Σ∗/∼LiscalledthesyntacticmonoidofLandisdenotedasS(L).Themorphismϕ:Σ∗→S(L),thatmapseachwordtoitsequivalenceclassmodulo∼LiscalledthesyntacticmorphismofL.

Avarietyoffinitemonoids(alsodenotedaspseudovariety)isaclassoffinitemonoidsclosedundermorphicimages,submonoidsandfinitedirectproducts.

Avarietyofrecognizablelanguagesisaclassoflanguagesclosedunderfiniteunionandintersection,complement,inversemorphismsandrightandleftquotients.Eilenberg[6]provedthatvarietiesoffinitemonoidsandva-rietiesoflanguagesareinone-to-onecorrespondence.IfVisavarietyofsemigroups,wedenoteasLV(Σ∗)thevarietyoflanguagesoverΣwhosesyntacticsemigroupslieinV.

Someinstancesofthiscorrespondencethatwillbeusedthroughoutthispaperaretherelationsbetween:

•Thevarietyoflocallytestablelanguagesandthevarietyoflocallyidem-potentandcommutativesemigroups.

•ThevarietyofpiecewisetestablelanguagesandthevarietyofJ-trivialsemigroups.

4

•Thevarietyofstar-freelanguagesandthevarietyofaperiodicsemi-groups.

2.3Forbiddenconfigurations

GivenanautomatonA=(Q,Σ,·,q0,F),thesetofallpathsinAdefinesaninfinitelabelledgraphG(A)wherethesetofverticesisQandthesetofedgesis{(q,w,q·w):q∈Q,w∈Σ+}.AlabelledsubgraphPofG(A)issaidtobeaconfiguration,orapattern,presentinA.

Theforbidden-patterncharacterizationshavebeendevelopedinthestudyoftherelationsbetweenlogicandformallanguages.Theyareresultsofthefollowingtype:”AlanguageLbelongstoaclassCifandonlyiftheacceptingfiniteautomatondoesnothavesubgraphPinitstransitiongraph”.Usually,forbidden-patterncharacterizationsimplythedecidabilityofthecharacterizedclass,sinceweonlyhavetotestwhethertheforbidden-patternoccursinanautomaton.

Formanyvarietiesofregularlanguagestheforbidden-patterncharacter-izationiswellknown,butforothersthequestionremainsopen,forexampleitcanbeshownthatthesemigroupofa(minimal)deterministicautomatonAisidempotentifandonlyifthereexistnoconfigurationofAoftheformdepictedinfigure1,wherex∈Σ+andp=q.

rxpxqFigure1:Forbiddenconfigurationforanautomatonwhosesemigroupisidempotent

Forbidden-patterncharacterizationforseveralvarietiesoflanguagescanbefoundin[4],[9]and[19].

3AdescriptionoftheFCRPNIalgorithm

WesupposethatthereaderisfamiliarwithRPNI-Langalgorithm[16],[14].TheversionweusepresentsDFAsasMooremachineswithoutputbelongingtotheset{0,1,↑}.AnywordxsuchthatΦ(q0·x)=0(resp.1)(resp.↑)isconsiderednegative(resp.positive)(resp.notdefined).TheonlychangesthatouralgorithmmakeswithrespecttoRPNI-Langalgorithmisthatbe-forewedefinitivelymergetwostates,wetestiftheresultingautomatoncan

5

stillbelongtotheconsideredvariety.Thisisdonebylookingforpossiblefor-biddenconfigurationsinthestablepartoftheautomaton.Inthesequel,themodificationweproposewillbedenotedasFCRPNI(ForbiddenPatternsRPNI).

MergingtwostatesinRPNI-Langalgorithmpossiblymakessomeotherstatestobemergedinordertoguaranteethedeterminismoftheautomaton.Thenthisautomatonistestedforconsistencywiththedata(astatecannotbepositiveandnegative)andifitisnotconsistentwehavetoundothemerging.

Besidesthattest,FCRPNIhastoestablishthatthecurrentautomatoncanstillbelongtothevarietytobelearned.Thisisdonebytestingwhethertheforbidden-patternsoccurintheconsolidatedpartoftheautomaton.ThefollowingexampleillustratesthediferencesbetweenRPNI-LangandFCRPNIalgorithms,werestrictourselvestothevarietyofstar-freelan-guages.Werecallthatalanguageisstar-freeifandonlyiftheminimalautomatonthatrecognizesitispermutation-free1.

Example1LetL=aa∗(whichisstar-free)andletD+={a,aaa}andD−={λ}.TheprefixtreeacceptorisrepresentedinFigure2

0q0a1q1aq2a1q3Figure2:PrefixMooremachineforthesampleD+={a,aaa}andD−={λ}.RPNI-Langtriestomergeq0andq1buttheconsistencytestfails.Inthefollowingstepittriestomergeq0andq2whichimpliesthemergingofq1andq3.TheresultisdepictedinFigure3.

a0q0a1q1Figure3:DFAoutputbyRPNIalgorithmoninputofD+={a,aaa}andD−={λ}.

AseverystateintheprefixMooremachinehasbeenconsidered,thealgo-rithmfinishes.Weseethattheinputwasnotenoughtolearnaa∗.

AnautomatonhasapermutationifthereexistsasubsetP⊆QandawordxsuchthatP·x=P,whereP·x=∪p∈Pp·x

1

6

FCRPNIwiththerestrictiontostar-freelanguagesproccedsinthesamewaybutastheautomatondepictedinFigure3failsinthetestofforbiddenpatternsforstar-freelanguages,itcannotmergestatesq0andq2.Thefol-lowingstepistotrytomergeq1andq2whichimpliesthemergingofq1andq3.Thefinalresultistheautomatonrepresentedinfigure4.

aa0q01q1Figure4:DFAoutputbyFCRPNIalgorithmoninputofD+={a,aaa}andD−={λ}.

3.1ConvergenceofFCRPNIalgorithm.

Fact.LetL∈LV(Σ∗)bethetargetlanguageandletD+∪D−acom-pletesamplefortheinferenceoflanguageLusingRPNI-Langalgorithm.Ateverystepthisalgorithmoutputsafiniteautomatonwithnoforbiddenconfigurationsasthoseforbiddenpatternsmayonlyappearinconsolidatedpartoftheautomatonandthatsubautomatonremainsstableduringtherestoftheprocess.

Proposition2FCRPNIalgorithmidentifiesanyvarietyLV(Σ∗)fromacompletepresentationinthelimit.

Proof.LetL∈LV(Σ∗)bethetargetlanguage.IfthesamplesusedforinferencecontainacharacteristicsampleofLfortheRPNI-Langalgorithm,noforbiddenconfigurationcanappearinthestablepartoftheautomatonduringtheprocessofinference,andFCRPNIalgorithmbehavesinthesamewayasRPNI-Langalgorithmdoesandthus,itidentifiesthelanguageL.Proposition3LetL∈LV(Σ∗)bethetargetlanguageandletD+∪D−anarbitrarysamplesuchthatwhenitisusedasinputfortheRPNI-Langalgorithm,itoutputsthecanonicalacceptorforL.ThenFCRPNIalgorithmoutputsthesameautomaton.

Proof.ItisobviousthatifRPNI-LangalgorithmentersinaforbiddenconfigurationitwillnotidentifylanguageL.

Propositions2and3showintheorythatifwerestricttheidentificationtovarietiesofregularlanguages,FCRPNIalgorithmworkssomehowbetter

7

thanRPNI-Langdoes.Itisclearthattherearesituationsinwhichtheformerconvergeswhereasthelaterdoesnot(seeexample1).Thecostisthatwehavetocheckforforbiddenconfigurations,soonlyacompletesetofexperimentswillallowustoquantifythedifferences.

4Experimentalresults.

WehavedonesomesmallexperimentsinordertocomparethebehaviorofRPNIandFCRPNIfortwovarietiesofformallanguages,thevarietyofpiecewisetestablelanguagesandthevarietyofstar-freelanguages.Descriptionoftheexperiments:•Weworkwithminimalautomatahaving5states,thealphabetisΣ={a,b}.Eachofthemrecognizeseitherapiecewisetestablelanguageorastar-freeone.Weobtainthembeginningwithlargerautomata,wethenminimizethemanddiscardtheautomatawhichdonothavetherequiredsize.Afterwardswecalculatethetransformationsemigroupofeachautomatonanddiscardtheonesthatdoesnotbelongtotherequiredclass.

•Forthelearningprocessweuserandomlygeneratedstringsoflengthlessthanorequalto10overΣ.Thenumberofthemisshowninthetablesthatdescribetheresultsoftheexperiments.

•Thecomparisonoftheobtainedautomataisdoneusingallthewordsoflengthlessthanorequalto15notusedinthelearningprocess.•Wehavedone200experimentsforeachdifferenttypesoflanguages.Table1(resp.Table2)showthemeanoftheerrorrate(percentageofwordsnotcorrectlyclassified)intermsofthenumberofwordsusedinthelearningprocesswhenRPNI-LangandFCRPNIareusedforinferenceofpiecewisetestable(resp.star-free)languages.NumberofsamplesusedforinferenceerrorrateofRPNI-LangerrorrateofFCRPNI2040608010012,123,422,000,930,779,732,570,620,260,11Table1:MeanoftheerrorratewhenofRPNIandFCRPNIareusedfortheinferenceofpiecewisetestablelanguagesintermsofthenumberofwordsusedinthelearningprocess

8

NumberofsamplesusedforinferenceerrorrateofRPNI-LangerrorrateofFCRPNI204060801008,101,630,750,280,247,111,230,380,130,12Table2:MeanoftheerrorratewhenofRPNIandFCRPNIareusedfortheinferenceofstar-freelanguagesintermsofthenumberofwordsusedinthelearningprocess

5Conclusionsandfuturework.

WehavedescribedFCRPNI,amodificationofRPNI-Langalgorithmaim-ingtoshowhowtherestrictionofthelearningdomaintocertainwellcharac-terizedsubclassesofthefamilyregularlanguagesaffectstotheconvergence.WehaveprovedthatifRPNI-Langalgorithmhasbeengivenenoughsamplestoconverge,sodoesFCRPNI.Then,thislateralgorithmconvergesfasterthantheformeroneatthecostof:

•Restrictthedomainoftheinferenceprocess.

•Theadditionalcostofhavingtodotheforbidden-patterntests.Wehavedonesomepreliminaryexperimentsfortwovarietiesoflan-guages,theaperiodicandthepiecewisetestable.AlthoughtheerrorratesforFCRPNIarebetterinbothcases,asthesizeoftheautomatawehaveusedisverysmall,wecannotbeconclusiveabouthowmuchbettertheyare.Asfutureworkweshouldmakeefficientalgorithmsforsomeofthevari-etiesforwhichitispossibleandweshouldmakeacompleteexperimentationtomeasurehowbothalgorithmsbehave.

References

[1]Angluin,D.InductiveInferenceofFormalLanguagesfromPositiveData.Inform

andControl,pp.117-135(1980).

[2]Angluin,D.InferenceofReversibleLanguages.JournaloftheACM,Vol29-3.pp.

741-765(1982).

[3]Carrasco,R.andOncina,J.LearningStochasticRegularGrammarsbymeansofa

StateMergingMethod.InGrammaticalInferenceandApplications.R.CarrascoandJ.Oncina(Eds.).LNAI862.Springer-Verlag,pp.139-152(1994).

[4]Cohen,J.PerrinD.andPinJ-E.Ontheexpressivepoweroftemporallogic.Journal

ofcomputerandSystemSciences46,pp271-294(1993).

9

[5]Coste,F.andNicolasJ.HowconsideringIncompatibleStateMergingsMayReduce

theDFAinductionSearchTree.InGrammaticalInference.V.HonavarandG.Slutzki(Eds.)LNAI1433.Springer-Verlag,pp199-210(1998).

[6]Eilenberg,S.Automata,LanguagesandMachines,VolAandB(AcademicPress,

1976)

[7]Garc´ıa,P.Cano,A.andRuiz,J.Acomparativestudyoftwoalgorithmsforautomata

identification.InGrammaticalInference:AlgorithmsandApplications.A.L.Oliveira

(Ed.)LNAI1.Springer-Verlag,pp.115-126(2000).

[8]Garc´ıaP.andVidalE.Inferenceofk-TestablelanguagesintheStricSenseandAp-plicationstoSyntacticPatternRecognition.IEEETransactionsonPatternAnalysis

andMachineIntelligence12/9,pp920-925(1990).

[9]Glaβer,C.Forbidden-PatternsandWordExtensionsforConcatenationHierarchies.

Phdissertation,W¨urzburgUniversity,Germany,2001.

[10]Gold,M.ComplexityofAutomatonIdentificationfromGivenData.Information

andControl37,pp302-320(1978).

[11]delaHiguera,C.Oncina,J.andVidal,E.Datadependantvsdataindependant

algorithms.InGrammaticalInference:LearningSyntaxfromSentences.L.MicletandC.delaHiguera(Eds.).LNAI1147.Springer-Verlag,pp.313-325(1996).

[12]Hopcroft,J.andUllman,J.IntroductiontoAutomataTheory,LanguagesandCom-putation.Addison-Wesley(1979).

[13]Juill´e,H.andPollackJ.AStochasticSearchApproachtoGrammarInduction.

InGrammaticalInference.V.HonavarandG.Slutzki(Eds.)LNAI1433.Springer-Verlag,pp126-137(1998).

[14]Lang,K.J.RandomDFA’scanbeApproximatelyLearnedfromSparseUniform

Examples.InProceedingsoftheFifthAnnualACMWorkshoponComputational

LearningTheory,pp45-52.(1992).

[15]Lang,K.J.,PearlmutterB.A.andPriceR.A.ResultsontheAbbadingoOneDFA

LearningCompetitionandaNewEvidence-DrivenStateMergingAlgorithm.InGrammaticalInference.V.HonavarandG.Slutzki(Eds.)LNAI1433.Springer-Verlag,pp1-12(1998).

[16]Oncina,J.andGarc´ıa,P.InferringRegularLanguagesinPolynomialUpdatedTime.

InPatternRecognitionandImageAnalysys.P´erezdelaBlanca,Sanfeli´uandVidal

(Eds.)WorldScientific.(1992).

10

[17]Pin,J.Varietiesofformallanguages.Plenum.(1986).

[18]Ruiz,J.andGarc´ıa,P.Learningk-piecewisetestablelanguagesfrompositivedata.

InGrammaticalInference:LearningSyntaxfromSentences.L.MicletandC.dela

Higuera(Eds.).LNAI1147.Springer-Verlag,pp.203-210(1996).

[19]Schmitz,H.TheForbidden-PatternapproachtoConcatenationHierarchies.Phdis-sertation,W¨urzburgUniversity,Germany,2001.

[20]Stolcke,A.andOmohundro,S.InducingProbabilisticGrammarsbyBayesianModel

Merging.InGrammaticalInferenceandApplications.R.CarrascoandJ.Oncina(Eds.).LNAI862.Springer-Verlag,pp.106-118(1994).

[21]TrakhtenbrotB.andBarzdinYa.FiniteAutomata:BehaviorandSynthesis.North

HollandPublishingCompany.(1973).

[22]Vidal,E.andLlorens,S.UsingKnowledgetoimproveN-GramLanguageModelling

throughtheMGGIMethodology.InGrammaticalInference:LearningSyntaxfromSentences.L.MicletandC.delaHiguera(Eds.).LNAI1147.Springer-Verlag,pp.179-190(1996).

11