The dissertationofAndreas Stolckeis approved: Chair Date Date Date Date UniversityofCaliforniaat Berkeley 1994 BayesianLearningofProbabilisticLanguageModels Copyright c 1994 (cid:13) by AndreasStolcke BayesianLearningofProbabilisticLanguageModels by AndreasStolcke Abstract The generaltopicofthisthesisistheprobabilisticmodelingoflanguage, inparticularnaturallanguage. In probabilisticlanguagemodeling,onecharacterizes thestringsofphonemes, words,etc. ofacertaindomain in terms of a probability distributionover all possible strings within the domain. Probabilistic language modelinghas been appliedtoawiderangeofproblemsinrecent years, fromthetraditionaluses inspeech recognitiontomorerecentapplicationsinbiologicalsequencemodeling. Themaincontributionofthisthesisisaparticularapproachtothelearningproblemforprobabilistic languagemodels,knownasBayesianmodelmerging. Thisapproachcanbecharacterizeasfollows. Models are built either in batch mode or incrementally from samples, by incorporating individual (cid:15) samplesintoaworkingmodel Auniform,smallnumberofsimpleoperatorsworkstograduallytransformaninstance-basedmodelto (cid:15) ageneralizedmodelthatabstractsfromthedata. Instance-basedpartsofamodelcancoexistwithgeneralizedones,dependingonthedegreeofsimilarity (cid:15) amongtheobservedsamples,allowingthemodeltoadapttonon-uniformcoverageofthesamplespace. The generalizationprocess isdriven and controlledbya uniform, probabilisticmetric: the Bayesian (cid:15) posteriorprobabilityofamodel,integratingbothcriteriaofgoodness-of-fitwithrespecttothedataand anotionofmodelsimplicity(‘Occam’sRazor’). The Bayesianmodelmergingframeworkisinstantiatedforthreedifferentclasses ofprobabilistic models: Hidden Markov Models (HMMs), stochastic context-free grammars (SCFGs), and simple proba- bilisticattribute grammars (PAGs). Along with the theoretical background, various applications and case studies are presented, includingthe induction of multiple-pronunciationword models for speech recogni- tion (with HMMs), data-driven learning of syntactic structures (with SCFGs), and the learning of simple sentence-meaningassociationsfromexamples(withPAGs). Apartfromlanguagelearningissues,anumberofrelatedcomputationalproblemsinvolvingproba- bilisticcontext-freegrammarsarediscussed. AversionofEarley’sparserispresentedthatsolvesthestandard problemsassociatedwithSCFGsefficiently,includingthecomputationofsentenceprobabilitiesandsentence prefixprobabilities,findingmostlikelyparses,andtheestimationofgrammarparameters. Finally, we describe an algorithmthat computes -gram statisticsfrom a given SCFG, based on n solvinglinearsystemsderivedfromthegrammar. Thismethodcanbeaneffectivetooltotransformpartof 2 theprobabilisticknowledgefromastructuredlanguagemodelintoanunstructuredlow-levelformforusein applicationssuchasspeechdecoding. Weshowhowthisproblemisjustaninstanceofalargerclassofrelated ones(suchasaveragesentencelengthorderivationentropy)thatareallsolvablewiththesamecomputational technique. Anintroductorychapter triestopresentaunifiedviewofthevariousmodeltypesandalgorithms foundintheliterature,aswellasissuesofmodellearningandestimation. Prof.JeromeA.Feldman,DissertationChair i Acknowledgments Life and work in Berkeley and at ICSI for me are marked by a wonderful wealth of friends, colleagues, collaborators, and acquaintances. It will be hard to do justice to the many ways in which the people below, and probably some I will forget to mention, have enriched the years at this extraordinary place—butIwilltry. JerryFeldman, advisorwhopatientlyguideshisstudentsbylettingthem wanderabouttheirown ways—atrueDoktorvater. Steve Omohundro, collaborator and friend, an endless source of ideas, insight, and above all, enthusiasm. Myextendedacademicsupportgroup,whotaughtmemostofwhatIknowandmadeBerkeleythe placetobe(inapproximateorderofappearance): JohnCanny,BobWilensky,StuartRussell,GeorgeLakoff, ChuckFillmore,LotfiZadeh,JitendraMalik,JohnOusterhout,andDavidCuller. PeterCheeseman andWrayBuntine,whointroducedmetothepowersofBayes’Ruleatjustthe rightmomentandhavebeenawillingsourceofadviceeversince—maytheirbookbeontheshelvessoon. NelsonMorgan, whoadoptedmeintohisgroup,andcontinuestobe avaluablesourceofadvice abouttherealdata,andRAP. SubutaiAhmad, DekaiWu, Terry RegierandBen Gomes, officemates, friendsand collaborators: thanksformakingthesesuchfunyears. The ICSI AI and realization groups, Bertrand Irissou, Brian Kingsbury, Chris Bregler, Chuck Wooters, Dan Jurafsky, DavidBailey, DavidStoutamire, Eric Fosler, GaryTajchman, Herve´ Bourlard,Jeff Bilmes, Joachim Diederich, Jonathan Segal, Krste Asanovic, Lokendra Shastri, Nikki Mirghafori, Srini Narayanan, Steve Greenberg, Susan Weber, and Yochai Konig. Apart from being an utterly fun crowd, severalofthemdidmuchoftheworkthatwascrucialinobtainingresults. All of the ICSI staff, past and present, who have developed perfection in providing unobtrusive supportandafternoonteaandcookies. SpecialthanksgotoAlixCollisonforfriendshipandhelpinfeeling, quiteliterally,athome. TherestoftheBerkeleyAIandCogscicrowd,AdeleGoldberg,FrancescaBarrientos,JaneEdwards, MartiHearst, MikeBraverman, MikeSchiff,NJ, andPeterNorvig—nevershortofadvice, encouragement, goodhumor,rhythm,andbluenotes. KathrynCrabtree, whohas been indispensableinsteeringme(as wellas everyoneelse)through, andwherepossibleclearofthethicketofUniversityregulationsandrequirements. My former academic advisors at Munich, Erwin Kloeck, ChristianFreksa, Wilfried Brauer, and TheoVennemann,whoinmanywayslaidthefoundationsforthepresentworkandencouragedmetotrymy luckinBerkeley. FernandoPereira,whoIfirstranintoontheInternet,andwhohassincemadehimselfindispensable withvaluableinsightsandbibliographicreferences. Our‘Foster’parents,BillandDonna,andeverybodyatWCPC,whomade usfeelsowelcome in theverybeginningandthereafter. DavidBlake,BerkeleystudentparexcellenceandimportantsourceofinformationaboutAmerican andBerkeleyculture. ii Myparents, whosesupport,encouragement andunderstandingIcouldalwayscounton,and who (astheysay)madeitallpossible. Susanne,PatrickandOliver,whomadeeverythingbearable,eventhoughitwasn’talwaysforthem. Thesepagesarededicatedtoyou. iii Contents ListofFigures vii ListofTables viii 1 Introduction 1 1.1 Overview 1 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1.2 StructuralLearningofProbabilisticGrammars 2 : : : : : : : : : : : : : : : : : : : : : : : : 1.2.1 Probabilisticfinite-statemodels 3 : : : : : : : : : : : : : : : : : : : : : : : : : : : 1.2.2 TheMiniatureLanguageLearning( )Task 3 0 L : : : : : : : : : : : : : : : : : : : : 1.3 Miscellaneoustopics 6 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1.4 BibliographicalNote 6 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 Foundations 7 2.1 Preliminaries 7 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.2 ProbabilisticLanguageModels 7 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.2.1 Interpretationofprobabilities 8 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.2.2 Anexample: -grammodels 8 n : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.2.3 Probabilisticgrammarsasrandomstringgenerators 9 : : : : : : : : : : : : : : : : : 2.2.4 Multinomialdistributions 9 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.2.5 Parameterestimation 10 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.2.6 Likelihoodandcross-entropy 11 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.3 Grammarswithhiddenvariables 12 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.3.1 Mixturegrammars 13 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.3.2 Expectation-Maximization 13 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.3.3 ViterbiderivationsandapproximateEM 14 : : : : : : : : : : : : : : : : : : : : : : : 2.3.4 HiddenMarkovModels 15 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.3.5 StochasticContext-freeGrammars 16 : : : : : : : : : : : : : : : : : : : : : : : : : : 2.4 LevelsofLearningandModelMerging 17 : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.4.1 Beyondparameterestimation 17 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.4.2 Modelmerging 17 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.4.3 Acurve-fittingexample 18 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.4.4 Knowingwhentostop 18 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.5 BayesianModelInference 20 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.5.1 Theneedforinductivebias 20 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.5.2 Posteriorprobabilities 21 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.5.3 BayesianModelMerging 21 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.5.4 MinimumDescriptionLength 22 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.5.5 Structurevs.parameterpriors 23 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2.5.6 DescriptionLengthpriors 24 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : CONTENTS iv 2.5.7 Posteriorsforgrammarstructures 26 : : : : : : : : : : : : : : : : : : : : : : : : : : 3 HiddenMarkovModels 27 3.1 IntroductionandOverview 27 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.2 HiddenMarkovModels 28 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.2.1 Definitions 28 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.2.2 HMMestimation 29 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.2.3 Viterbiapproximation 30 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.3 HMMMerging 31 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.3.1 Likelihood-basedHMMmerging 31 : : : : : : : : : : : : : : : : : : : : : : : : : : 3.3.2 Anexample 32 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.3.3 PriorsforHiddenMarkovModels 34 : : : : : : : : : : : : : : : : : : : : : : : : : : 3.3.4 WhyaresmallerHMMspreferred? 37 : : : : : : : : : : : : : : : : : : : : : : : : : 3.3.5 Thealgorithm 39 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.4 ImplementationIssues 40 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.4.1 Efficientsampleincorporation 40 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.4.2 Computingcandidatemerges 41 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.4.3 ModelevaluationusingViterbipaths 41 : : : : : : : : : : : : : : : : : : : : : : : : 3.4.4 Globalpriorweighting 45 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.4.5 Searchissues 45 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.5 RelatedWork 46 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.5.1 Non-probabilisticfinite-statemodels 47 : : : : : : : : : : : : : : : : : : : : : : : : : 3.5.2 Bayesianapproaches 47 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.5.3 Statesplittingalgorithms 47 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.5.4 Otherprobabilisticapproaches 48 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.6 Evaluation 49 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.6.1 Casestudiesoffinite-statelanguageinduction 49 : : : : : : : : : : : : : : : : : : : : 3.6.2 Phoneticwordmodelsfromlabeledspeech 63 : : : : : : : : : : : : : : : : : : : : : 3.6.3 Multiplepronunciationwordmodelsforspeechrecognition 72 : : : : : : : : : : : : : 3.7 ConclusionsandFurtherResearch 74 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 StochasticContext-freeGrammars 75 4.1 IntroductionandOverview 75 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.2 StochasticContext-freeGrammars 76 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.2.1 Definitions 76 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.2.2 SCFGestimation 78 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.2.3 Viterbiparses 79 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.3 SCFGMerging 79 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.3.1 Sampleincorporationandmergingoperators 79 : : : : : : : : : : : : : : : : : : : : : 4.3.2 Anexample 83 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.3.3 Bracketedsamples 85 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.3.4 SCFGpriors 86 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.3.5 Searchstrategies 88 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.3.6 Miscellaneous 90 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.4 RelatedWork 91 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.4.1 Bayesiangrammarlearningbyenumeration 91 : : : : : : : : : : : : : : : : : : : : : 4.4.2 Mergingandchunkingbasedapproaches 91 : : : : : : : : : : : : : : : : : : : : : : 4.4.3 Cook’sGrammaticalInferencebyHillClimbing 92 : : : : : : : : : : : : : : : : : : : 4.5 Evaluation 93 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.5.1 Formallanguagebenchmarks 93 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.5.2 Naturallanguagesyntax 96 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4.5.3 Sampleordering 101 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : CONTENTS v 4.5.4 SummaryandDiscussion 103 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5 ProbabilisticAttributeGrammars 104 5.1 Introduction 104 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5.2 ProbabilisticAttributeGrammars 104 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5.2.1 Definitions 105 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5.2.2 Anexample 107 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5.2.3 PAGestimation 108 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5.3 PAGMerging 109 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5.3.1 Sampleincorporation 109 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5.3.2 Nonterminalmergingandchunking 110 : : : : : : : : : : : : : : : : : : : : : : : : : 5.3.3 Featureoperators 111 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5.3.4 Efficientsearchforfeatureoperations 112 : : : : : : : : : : : : : : : : : : : : : : : : 5.3.5 PAGPriors 114 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5.4 Experiments 115 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5.4.1 examples 115 0 L : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5.4.2 Syntacticconstraintsimposedbyattributes 116 : : : : : : : : : : : : : : : : : : : : : 5.5 LimitationsandExtensions 118 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5.5.1 Moreexpressivefeatureconstraints 118 : : : : : : : : : : : : : : : : : : : : : : : : : 5.5.2 Hierarchicalfeatures 119 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5.5.3 Trade-offsbetweencontext-freeandfeaturedescriptions 120 : : : : : : : : : : : : : : 5.6 Summary 120 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6 EfficientparsingwithStochasticContext-freeGrammars 122 6.1 Introduction 122 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.2 Overview 124 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.3 EarleyParsing 124 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.4 ProbabilisticEarleyParsing 127 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.4.1 Stochasticcontext-freegrammars 127 : : : : : : : : : : : : : : : : : : : : : : : : : : 6.4.2 Earleypathsandtheirprobabilities 129 : : : : : : : : : : : : : : : : : : : : : : : : : : 6.4.3 Forwardandinnerprobabilities 131 : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.4.4 Computingforwardandinnerprobabilities 133 : : : : : : : : : : : : : : : : : : : : : 6.4.5 Copingwithrecursion 134 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.4.6 Anexample 139 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.4.7 Nullproductions 139 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.4.8 Existenceof and 143 6.4.9 ComplexityiRssLues RU : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 145 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.4.10 Summary 147 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.5 Extensions 147 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.5.1 Viterbiparses 147 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.5.2 Ruleprobabilityestimation 149 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.5.3 Parsingbracketedinputs 152 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.5.4 Robustparsing 154 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.6 ImplementationIssues 158 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.6.1 Prediction 158 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.6.2 Completion 158 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.6.3 Efficientparsingwithlargesparsegrammars 159 : : : : : : : : : : : : : : : : : : : : : 6.7 Discussion 160 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.7.1 Relationtofinite-statemodels 160 : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.7.2 Onlinepruning 161 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.7.3 RelationtoprobabilisticLRparsing 161 : : : : : : : : : : : : : : : : : : : : : : : : : 6.7.4 Otherrelatedwork 163 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : CONTENTS vi 6.7.5 AsimpletypologyofSCFGalgorithms 164 : : : : : : : : : : : : : : : : : : : : : : : 6.8 Summary 165 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 6.9 Appendix: LRitemprobabilitiesasconditionalforwardprobabilities 165 : : : : : : : : : : : : 7 -gramsfromStochasticContext-freeGrammars 168 N 7.1 Introduction 168 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7.2 BackgroundandMotivation 169 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7.3 TheAlgorithm 171 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7.3.1 NormalformforSCFGs 171 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7.3.2 Probabilitiesfromexpectations 171 : : : : : : : : : : : : : : : : : : : : : : : : : : : 7.3.3 Computingexpectations 172 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7.3.4 Computingprefixandsuffixprobabilities 173 : : : : : : : : : : : : : : : : : : : : : : 7.3.5 -gramscontainingstringboundaries 174 N : : : : : : : : : : : : : : : : : : : : : : : : 7.4 EfficiencyandComplexityIssues 174 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7.5 ConsistencyofSCFGs 175 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7.6 Experiments 176 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7.7 Summary 178 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7.8 Appendix: RelatedProblems 179 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7.8.1 Expectedstringlength 179 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7.8.2 Derivationentropy 179 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7.8.3 Expectednumberofnonterminaloccurrences 180 : : : : : : : : : : : : : : : : : : : : 7.8.4 Othergrammartypes 180 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8 Futuredirections 181 8.1 Formalcharacterizationoflearningdynamics 181 : : : : : : : : : : : : : : : : : : : : : : : : 8.2 Noisysamples 182 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8.3 Moreinformativesearchheuristicsandbiases 182 : : : : : : : : : : : : : : : : : : : : : : : : 8.4 Inductionbymodelspecialization 182 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8.5 Newapplications 183 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8.6 Newtypesofprobabilisticmodels 183 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : Bibliography 184