资源描述：
《02 - A Version Space Approach to Learning Context-free Grammars.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、MachineLearning2:39-74,1987©1987KluwerAcademicPublishers,Boston-ManufacturedinTheNetherlandsAVersionSpaceApproachtoLearningContext-freeGrammarsKURTVANLEHN(VANLEHN@A.PSY.CMU.EDU)WILLIAMBALL(BALL@A.PSY.CMU.EDU)DepartmentofPsychology,Carnegie-MellonUnivers
2、ity,Pittsburgh,PA15218U.S.A.(Received:June17,1986)(Revised:January21,1987)Keywords:Induction,grammaticalinference,versionspace,context-freegrammars,learningfromexamples.Abstract.Inprinciple,theversionspaceapproachcanbeappliedtoanyinductionproblem.Howeve
3、r,insomecasestherepresentationlanguageforgeneralizationsissopowerfulthat(1)someoftheupdatefunctionsfortheversionspacearenoteffectivelycomputable,and(2)theversionspacecontainsinfinitelymanygeneralizations.Theclassofcontext-freegrammarsisasimplerepresenta
4、tionthatexhibitstheseproblems.Thispaperpresentsanalgorithmthatsolvesbothproblemsforthisdomain.Givenasequenceofstrings,thealgorithmincrementallyconstructsadatastructurethathasnearlyallthebeneficialpropertiesofaversionspace.Thealgorithmisfastenoughtosolve
5、smallinductionproblemscompletely,anditservesasaframeworkforbiasesthatpermitthesolutionoflargerproblemsheuristically.Thesamebasicapproachmaybeappliedtorepresentationsthatincludecontext-freegrammarsasspecialcases,suchasAnd-Orgraphs,productionsystems,andHo
6、rnclauses.1.IntroductionTheproblemaddressedherearoseinthecourseofstudyinghowpeoplelearnarithmeticproceduresfromexamples(VanLehn,1983a;VanLehn,1983b).Ourdataallowedustoinferapproximationsoftheproceduresthesubjectshadlearnedandtheexamplestheyreceiveddurin
7、gtraining.Thus,theinputsandoutputstothelearningprocesswereknown,andtheproblemwastodescribethelearningprocessindetail.However,becausethesubjects'learningoccurredintermittentlyoverseveralyears,wewerenotimmediatelyinterestedindevelopingadetailedcognitivesi
8、mulationoftheirlearningprocesses.Evenifsuchasimulationcouldbeconstructed,itmightbesocomplicatedthatitwouldnotshedmuchlightonthebasicprinciplesoflearninginthistaskdomain.Therefore,ourinitialobjectivewastofindprinciplesthatcouldact
