斯坦福大学自然语言处理14章

CFGsandPCFGs(Probabilistic)Context-FreeGrammarsChristopherManningAphrasestructuregrammarSNPVPVPVNPVPVNPPPNPNPNPNPNPPPNPNNPePPPNPpeoplefishtankspeoplefishwithrodsNpeopleNfishNtanksNrodsVpeopleVfishVtanksPwithChristopherManningPhrasestructuregrammars=context-freegrammars(CFGs)•G=(T,N,S,R)•Tisasetofterminalsymbols•Nisasetofnonterminalsymbols•Sisthestartsymbol(S∈N)•Risasetofrules/productionsoftheformX•X∈Nand∈(N∪T)*•AgrammarGgeneratesalanguageL.ChristopherManningPhrasestructuregrammarsinNLP•G=(T,C,N,S,L,R)•Tisasetofterminalsymbols•Cisasetofpreterminalsymbols•Nisasetofnonterminalsymbols•Sisthestartsymbol(S∈N)•Listhelexicon,asetofitemsoftheformXx•X∈Pandx∈T•Risthegrammar,asetofitemsoftheformX•X∈Nand∈(N∪C)*•Byusualconvention,Sisthestartsymbol,butinstatisticalNLP,weusuallyhaveanextranodeatthetop(ROOT,TOP)•Weusuallywriteeforanemptysequence,ratherthannothingChristopherManningAphrasestructuregrammarSNPVPVPVNPVPVNPPPNPNPNPNPNPPPNPNNPePPPNPpeoplefishtankspeoplefishwithrodsNpeopleNfishNtanksNrodsVpeopleVfishVtanksPwithChristopherManningProbabilistic–orstochastic–context-freegrammars(PCFGs)•G=(T,N,S,R,P)•Tisasetofterminalsymbols•Nisasetofnonterminalsymbols•Sisthestartsymbol(S∈N)•Risasetofrules/productionsoftheformX•Pisaprobabilityfunction•P:R[0,1]••AgrammarGgeneratesalanguagemodelL. P(g)=1gÎT*åChristopherManningAPCFGSNPVP1.0VPVNP0.6VPVNPPP0.4NPNPNP0.1NPNPPP0.2NPN0.7PPPNP1.0Npeople0.5Nfish0.2Ntanks0.2Nrods0.1Vpeople0.1Vfish0.6Vtanks0.3Pwith1.0[WithemptyNPremovedsolessambiguous]ChristopherManningTheprobabilityoftreesandstrings•P(t)–Theprobabilityofatreetistheproductoftheprobabilitiesoftherulesusedtogenerateit.•P(s)–TheprobabilityofthestringsisthesumoftheprobabilitiesofthetreeswhichhavethatstringastheiryieldP(s)=ΣjP(s,t)wheretisaparseofs=ΣjP(t)ChristopherManningChristopherManningChristopherManningTreeandStringProbabilities•s=peoplefishtankswithrods•P(t1)=1.0×0.7×0.4×0.5×0.6×0.7×1.0×0.2×1.0×0.7×0.1=0.0008232•P(t2)=1.0×0.7×0.6×0.5×0.6×0.2×0.7×1.0×0.2×1.0×0.7×0.1=0.00024696•P(s)=P(t1)+P(t2)=0.0008232+0.00024696=0.00107016VerbattachNounattachChristopherManningChristopherManningCFGsandPCFGs(Probabilistic)Context-FreeGrammarsGrammarTransformsRestrictingthegrammarformforefficientparsingChristopherManningChomskyNormalForm•AllrulesareoftheformXYZorXw•X,Y,Z∈Nandw∈T•Atransformationtothisformdoesn’tchangetheweakgenerativecapacityofaCFG•Thatis,itrecognizesthesamelanguage•Butmaybewithdifferenttrees•Emptiesandunariesareremovedrecursively•n-aryrulesaredividedbyintroducingnewnonterminals(n2)ChristopherManningAphrasestructuregrammarSNPVPVPVNPVPVNPPPNPNPNPNPNPPPNPNNPePPPNPNpeopleNfishNtanksNrodsVpeopleVfishVtanksPwithChristopherManningChomskyNormalFormstepsSNPVPSVPVPVNPVPVVPVNPPPVPVPPNPNPNPNPNPNPNPPPNPPPNPNPPPNPPPPNpeopleNfishNtanksNrodsVpeopleVfishVtanksPwithChristopherManningChomskyNormalFormstepsSNPVPVPVNPSVNPVPVSVVPVNPPPSVNPPPVPVPPSVPPNPNPNPNPNPNPNPPPNPPPNPNPPPNPPPPNpeopleNfishNtanksNrodsVpeopleVfishVtanksPwithChristopherManningChomskyNormalFormstepsSNPVPVPVNPSVNPVPVVPVNPPPSVNPPPVPVPPSVPPNPNPNPNPNPNPNPPPNPPPNPNPPPNPPPPNpeopleNfishNtanksNrodsVpeopleSpeopleVfishSfishVtanksStanksPwithChristopherManningChomskyNormalFormstepsSNPVPVPVNPSVNPVPVNPPPSVNPPPVPVPPSVPPNPNPNPNPNPNPNPPPNPPPNPNPPPNPPPPNpeopleNfishNtanksNrodsVpeopleSpeopleVPpeopleVfishSfishVPfishVtanksStanksVPtanksPwithChristopherManningChomskyNormalFormstepsSNPVPVPVNPSVNPVPVNPPPSVNPPPVPVPPSVPPNPNPNPNPNPPPNPPNPPPPNPNPpeopleNPfishNPtanksNProdsVpeopleSpeopleVPpeopleVfishSfishVPfishVtanksStanksVPtanksPwithPPwithChristopherManningChomskyNormalFormstepsSNPVPVPVNPSVNPVPV@VP_V@VP_VNPPPSV@S_V@S_VNPPPVPVPPSVPPNPNPNPNPNPPPNPPNPPPPNPNPpeopleNPfishNPtanksNProdsVpeopleSpeopleVPpeopleVfishSfishVPfishVtanksStanksVPtanksPwithPPwithChristopherManningAphrasestructuregrammarSNPVPVPVNPVPVNPPPNPNPNPNPNPPPNPNNPePPPNPNpeopleNfishNtanksNrodsVpeopleVfishVtanksPwithChristopherManningChomskyNormalFormstepsSNPVPVPVNPSVNPVPV@VP_V@VP_VNPPPSV@S_V@S_VNPPPVPVPPSVPPNPNPNPNPNPPPNPPNPPPPNPNPpeopleNPfishNPtanksNProdsVpeopleSpeopleVPpeopleVfishSfishVPfishVtanksStanksVPtanksPwithPPwithChristopherManningChomskyNormalForm•Youshouldthinkofthisasatransformationforefficientparsing•Withsomeextrabook-keepinginsymbolnames,youcanevenreconstructthesametreeswithadetransform•InpracticefullChomskyNormalFormisapain•Reconstructingn-ariesiseasy•Reconstructingunaries/emptiesistrickier•BinarizationiscrucialforcubictimeCFGparsing•Therestisn’tnecessary;itjustmakesthealgorithmscleanerandabitquickerChristopherManningROOTSNPVPNpeopleVNPPPPNProdswithtanksfishNNAnexample:beforebinarization…ChristopherManningPNProdsNwithNPNpeopletanksfishNVPVNPPP@VP_VROOTSAfterbinarization…ChristopherManningTreebank:emptiesandunariesROOTS-HLNNP-SUBJVPVB-NONE-eAtonePTBTreeROOTSNPVPVB-NONE-eAtoneNoFuncTags