20-trees-grammars.pptx
Ling131A
IntroductiontoNLPwithPython
Trees,GrammarsandParsers
MarcVerhagen,Fall2018
Today
• Gradesforassignment3areposted
• Quiz2
• Virtualenvironments
• ConstituentsandTrees
• PennTreebank
• GrammarsandParsing
Quiz2
• AllclassnotesstartingwithWordNet
• NLTKCh3:3.4–3.7
• NLTKCh5:5.1-5.2,5.4-5.7
• NLTKCh6:6.1.1-6.1.5,6.3-6.5
• NLTKCh8:8.1-8.5
• Questions:
– Pythonclass,regularexpressions,WordNet,decision
treesorbayes,taggers,classifiers,vectors,evaluation,
trees,grammars,parsers
VirtualEnvironments
• Dependencyhell
• Thirdpartypackagesinstalledatafewspots
• Butyoucanonlyhaveoneversionofapackage
• Whatiftwoprogramsrequiredifferentversions?
>>> import site
>>> site.getsitepackages()
[‘/usr/local/Cellar/python/3.6.5/Frameworks
/Python.framework/Versions/3.6/lib/python3.6
/site-packages’,
‘/Library/Python/3.6/site-packages’]
>>>
VirtualEnvironments
• CreateanisolatedenvironmentforPython
projects
– eachprojecthasitsowndependencies,regardless
ofwhatdependenciesotherprojectshave
– https://docs.python.org/3/library/venv.html
$ python3 -m venv /virtual-environments/nltk
$ source /virtual-environments/nltk/bin/activate
$ which python
/virtual-environments/nltk/bin/python
BeyondBigrams
• Bigramsworkwellformodelingpartofspeech
tags
• Butnotsomuchforsentences
– “Theworstpartandclumsylookingforwhoever
heardlight.”
– Perfectlyokaywhenseenasasequenceoftags
withinanbigrammodel
• Usingagrammarasamodelisbetterhere
GrammarModel
• Hereisonerulefromagrammar
• IfX1andX2arebothphrasesofgrammatical
categoryC,thenthephrase[X1 and X2]
isalsoofcategoryC
• Thisisviolatedby
[The worst part]NP and [clumsy looking]AP
Constituents
• Agroupofwordsthatformasingleunitina
hierarchicalstructure
• Substitution
– Aconstituentofonetypecantypicallybereplaced
byanotheroneofthesametype
• [Thelittlebear][sleeps]
• [Thebear][sleeps]
• [She][sleeps]
– Themeaningchanges,butthesentenceis
syntacticallyverysimilar
Constituentstructure
Syntacticcategories
Symbol Meaning Example
S sentence themanwalked
NP nounphrase adog
VP verbphrase sawapark
PP prepositionalphrase withatelescope
Det determiner the
N noun dog
V verb walked
P preposition in
Constituentstructure
Constituentstructuretree
PennTreebank
• Phrasestructureannotationinthegenerative
tradition
• ThemostinfluentialtreebankinNLP.
– Googlescholarcitation:6019(Marcusetal1993)
• PTBI(Marcusetal1993)
– Context-freebackbone
– Skeletalstructures
– Limitedemptyelements
– Noargument/adjunctdistinction
PennTreebank
• PTBII(Marcusetal1994)
– Addedfunctiontagstomarkupgrammaticalroles
(thusargument/adjunctdistinction,thoughnot
structurally)
– Enrichedthesetofemptyelements
– Onemillionwordsof1989WallStreetJournal
materialannotatedinTreebank-2style.
– ToolsforprocessingTreebankdata,including“tgrep,”
atree-searchingandmanipulationpackage
• usabilityoftgrepislimited,youmayfindthesoftwaretobe
difficultorimpossibletoport
PennTreebank
• PTBIII
– AddedtheBrowncorpus
• PennTreebankinNLTK
– AfragmentofPennTreebankII
– Youcanexpandthisyourself
– Addedfunctionalityinthenltk.Treeclass
Ambiguity
Ambiguity
Ambiguity
Ambiguity
Treeasamathematicalobject
• Atreeisasetofconnectedlabelednodes,
eachreachablebyauniquepathfroma
distinguishedrootnode.
• Parent,child,siblings
Gettingthetrees
• Treeclasswithinitializationmethods
• Treereader
– turnaparsefromastringrepresentationintoa
treerepresentation
– Shiftreduceparsing
• Aformofautomaticparsing
• turnalistoftokensintoatreerepresentation
ConstructingatreewithNLTK
• nltk.Tree()
– Canbeusedtobuildsmalltrees
>>> t = nltk.Tree(‘S’,
… [nltk.Tree(‘NP’, [‘Fido’]),
…nltk.Tree(‘VP’, [‘barks’])])
>>> t
(S (NP Fido) (VP barks))
>>> t.draw()
ConstructingatreewithNLTK
• nltk.Tree.fromstring()
– Toparsestringsintotrees
– Canbeusedtoreadinmanuallyconstructed
treebanksandturnthetreesintoannltk.Tree
object
– Amorepracticalwayforgettingtrees
nltk.Tree.fromstring()
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
Q:Howdoesthisworkunderthehood?
A:Byusingastack
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
(S(NP(DTthe)(Ncat))(VP(Vsleeps)))
Grammars
• Withregularexpressionswehadaregular
grammar
• Nowwearelookingatthenextlevel:the
contextfreegrammar
– Onecategoryontheleft-hand-sideoftherule
– Oneormorecategoriesontheright-hand-side
– Notallowed
• S–>ε
• NPVP–>DetNVP
Epsilonstandsfortheemptystring
Context-freegrammar
S->NPVP
VP->VNP|VNPPP
PP->PNP
V->“saw”|“ate”|“walked”
NP->“John”|“Mary”|“Bob”|DetN|DetNPP
Det->“a”|“an”|“the”|“my”
N->“man”|“dog”|“cat”|“telescope”|“park”
P->“in”|“on”|“by”|“with”
Recursioninsyntacticstructure
S->NPVP
NP->DetNom|PropN
Nom->AdjNom|N
VP->VAdj|VNP|VS|VNPPP
PP->PNP
PropN->‘Buster’|‘Chatterer’|‘Joe’
Det->‘the’|‘a’
N->‘bear’|‘squirrel’|‘tree’|‘fish’|‘log’Adj->‘angry’|‘frightened’|‘little’|‘tall’
V->‘chased’|‘saw’|‘said’|‘thought’|‘was’|‘put’P->‘on’
ParsingwithCFG
• Aparserprocessesinputsentencesaccording
totheproductionsofagrammar
• Itproducesoneormoreconstituent
structuresthatconformtothegrammar
• Grammar
– adeclarativespecificationofwell-formedness
• Parser
– aproceduralinterpretationofthegrammarthat
searchesthespaceoftreeslicensedbyagrammar
ParsingwithCFG
• Top-downparsing
– Predicts/generatessentencesbystartingatthe
topwiththegoalofcreatingacategoryoftypeS
– Drivenbythegrammar
• Bottom-upparsing
– Buildaparsetreefromthegroundup
– Drivenbytheinputsentence
Recursivedescentparsing
• Top-downparsing
• Recursivelybreaksahigh-levelgoalinto
severallower-levelsubgoals
• Expand,andmatch
• Maintainsalistofnodesinahypothetictree
thatneedstobeexpanded(calledfrontier)
• Useback-trackingifyougetintoadeadend
Thedogseesthecat
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Westartoffwiththestartsymbol
ofthegrammar.Thefrontierof
thetreeisthesetofsymbolsthat
youcanstillexpand,nodesinthe
frontierhavealightgreen
background
Andwehaveourinput
S
the dog thesees cat
S ! NP VP Det ! “the”
NP ! Det N N ! “cat”
VP ! V N ! “dog”
VP ! V NP V ! “sees”
S
NP VP
NDet
the cat
the dog thesees cat
ApplyS!NPVP
ApplyNP!DetN
ApplyDet!“the”
Confirm“the”isininput
ApplyN!“cat”
Wrong:“cat”isnotininput
S ! NP VP Det ! “the”
NP ! Det N N ! “cat”
VP ! V N ! “dog”
VP ! V NP V ! “sees”
Nowwebacktrack.Thatis,weundo
thelaststepandseewhetherthere
wasanalternative,ifnot,wekeep
undoingstepsuntilwedofindan
alternative.Ifwebacktrackallthe
waytoSwithoutfindingalternatives
thentheparserfails.
Weundidstep5fromthelast
slideandthefrontierisnowN
andVP.
Andwehaveanalternativewhich
istouseN!“dog”insteadofN
!“cat”
S
NP VP
NDet
the
the dog thesees cat
S ! NP VP Det ! “the”
NP ! Det N N ! “cat”
VP ! V N ! “dog”
VP ! V NP V ! “sees”
Notethatthisbacktrackingwouldnot
havebeenneedediftheparserhad
justbeenaweelittlebitsmarter,for
examplebygroupingtherulesfor
pre-terminals(N,VandDet)and
peekingaheadattheinput.
S
NP VP
NDet
the dog
the dog thesees cat
V
sees
ApplyN!“dog”
Confirmthat“dog”isintheinput
ApplyVP!V
ApplyV!“sees”
Confirmthat“sees”isintheinput
S ! NP VP Det ! “the”
NP ! Det N N ! “cat”
VP ! V N ! “dog”
VP ! V NP V ! “sees”
Butnowwearestuck.Thereareno
nodesonthefrontieranymore,but
wehavenotcoveredallinput.Sowe
backtrackagain.
S
NP VP
NDet
the dog
the dog thesees cat
Weundidstep3fromthe
previousslideandthefrontieris
nowtheVP.
Andwehaveanalternativewhich
istouseVP!VNPinsteadofVP
”V.
S ! NP VP Det ! “the”
NP ! Det N N ! “cat”
VP ! V N ! “dog”
VP ! V NP V ! “sees”
S
NP VP
NDet
the
the
NP
dog
the dog thesees cat
NDet
V
cat
sees
ApplyVP!VNP
ApplyV–>“Sees”
Checkfor“sees”intheinput
ApplyNP!DetN
ApplyDet!“the”
Checkfor“the”intheinput
ApplyN!“cat”
Checkfor“cat”intheinput
S ! NP VP Det ! “the”
NP ! Det N N ! “cat”
VP ! V N ! “dog”
VP ! V NP V ! “sees”
Andtheparsewassuccessful.
RecursiveDescentParserDemo
import nltk
nltk.app.rdparser_app.app()
Weaknessofrecursivedescentparsing
• Left-recursiveproductionslikeNP!NPPP
leadstoaninfiniteloop
• Theparserwastesalotoftimeconsidering
structuresorwordsthatdonotcorrespondto
theinputstructure
• Backtrackingmaydiscardreusablestructures
Sonobodyusesthis
Bottom-upparsing
• Familyofparsingmethodwheretheprocessis
drivenbytheinputtext
• Generallymoreefficient
Bottom-upparsing
53
S ! NP VP
NP ! det noun
VP ! verb NP
det ! “the”
noun ! “mouse”
noun ! “cheese”
verb ! “ate”
Input:
Themouseatethecheese
Bottom-upparsing
54
S!NPVP
NP!detnoun
VP!verbNP
det!“the”
noun!“mouse”
noun!“cheese”
verb!“ate”
ShiftReduceParser
• Asimplebottom-upparsingstrategy
• Startwiththeinputsentence(alistofwords)
andanemptystack
• Repeatedlypushthenextwordontothestack
• But…ifthetopnitemsonthestackmatchthe
righthand-sideofaCFGrule,thentheyare
poppedoffthestack,andreplacedwiththe
singleitemontheleft-handsideoftherule
ShiftReduceParser
• Shift:pushingtothestack
• Reduce:movingmelementsfromthestack
andreplacethemwithnelements(n≤m)
– Reduceisguidedbyagrammarandcanonlybe
appliedtothetopitemsofthestack(alimitation
ofthestackdatastructure)
ShiftReduceParser
• Theparserfinisheswhenalltheinputis
consumed
– successifthereisasingleSnodeonthestack
– failureifthereismorethanoneitemonthestack
Shift-reduceexample
Grammar:
S !NP VP
NP !Det N
VP !V
VP !V NP
Det !“the”
N !“cat”
N !“dog”
V !“sees”
Input:
“Thedogseesthecat”
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Westartwithanemptystackandthefullinput
sentence.Ouronlyoptionatthestartistoshift,that
is,weaddanelementfromtheremainingtexttothe
stack.Elementsinvolvedinthenextaction(words,
rulesandstackelements)areprintedinblue.
Stack
thedogseesthecat
Remainingtext
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
dogseesthecat
Remainingtext
the
Shifted“the”ontothestack.
Therulewastoshiftunlessyoucouldreduce.Wecan
nowreducebecause“the”onthestackmatchesthe
right-handside(rhs)ofarulesowewilldothat.
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
dogseesthecat
Remainingtext
Reducedbyremoving“the”fromthestackandadding
theminitreeusingtheruleDet!“the”.
Nextup:shift
Det
the
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
seesthecat
Remainingtext
Added“dog”tothestack.
Nextup:reducebecause“dog”isontherhsofarule.
Det
the
dog
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
seesthecat
Remainingtext
Removed“dog”fromthestackandaddedanother
minitree.
Nextup:DetandNaretherhsofarule,sowecando
anotherreduce
NDet
the dog
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
seesthecat
Remainingtext
Twotopelementsofthestackwereremoved,and
onewasadded,drivenbytheruleNP!DetN.
Nextup:shift
NP
NDet
the dog
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
thecat
Remainingtext
Shifted“sees”ontothestack.
Nextup:wecandoanotherreduceandsincewestill
preferthoseovershiftswewillgoahead.
NP
NDet
the dog
sees
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
thecat
Remainingtext
Replaced“sees”onthestackwithaminitree.
Nextup:wecandoanotherreduce.
NP
NDet
the dog
V
sees
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
thecat
Remainingtext
RemovedV(“sees”)fromthestackandreplacedit
withVP(V(“sees”).
Nextup:yetanotherreducethistimedrivenbythe
ruleS!NPVP.
NP
NDet
the dog
V
sees
VP
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
thecat
Remainingtext
Wetooktwoelementsfromthestackandreplacedit
byone.
Nextup:ashift
NP
NDet
the dog
V
sees
VP
S
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
cat
Remainingtext
Weshifted“the”ontothestack.
Nextup:areduce
NP
NDet
the dog
V
sees
VP
S the
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
cat
Remainingtext
Wetook“the”fromthestackandreplaceditbya
minitree.
Nextup:ashift
NP
NDet
the dog
V
sees
VP
S
the
Det
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
cat
Remainingtext
Weadded“cat”tothestack.
Nextup:areduce
NP
NDet
the dog
V
sees
VP
S
the
Det
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
cat
Remainingtext
Weremoved“cat”fromthestackandaddedamini
tree.
Nextup:areduce
NP
NDet
the dog
V
sees
VP
S
the
Det N
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
cat
Remainingtext
Wereplacedtwoelementsfromthestackand
replacedthemwithoneNP.
Nowthereisnothingthatwecando,andeven
thoughweconsumedallinput,theparsefailed
becauseweshouldhaveonlyoneelementonthe
stackattheend.
NP
NDet
the dog
V
sees
VP
S
the
Det N
NP
Shiftorreduce,thatisthequestion
• Whenitispossibletoeithershiftorreduce,
whatshouldtheparserdo?
• Whichreducetouseiftherearemorereduce
options?
• Theanswertothesequestionscanmean
successorfailurefortheparser
74
Shiftorreduce,thatisthequestion
• Possibleanswers:
– Useheuristics
• Reducehaspriorityovershift;
• Usethereducethatcoversthemostitems
– Assigningaprobabilitytoeachaction,andthe
actionwiththehighestprobabilitywins
– Usebacktrackingtotryoutallchoicesifneeded
75
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
thecat
Remainingtext
Hereiswherewetookthewrongturnthelasttime.
Weweregoingtodoareducesincethosewere
favoredovershifts,butwhatifwechangeourrules.
(NotethatthereisasleightofhandheresinceIam
nowchangingtherulesinthemiddleofaparse,bad,
butitisforexplanatorypurposes).
NP
NDet
the dog
V
sees
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
thecat
Remainingtext
Let’ssaywenowusethefollowingheuristics.First,if
available,useareducewithaterminalrule.Second,if
noterminalrulesisavailableuseashift.Third,ifthere
isnoshiftusethereducewiththerulewiththe
longestright-handside.
Sohereweshift.
NP
NDet
the dog
V
sees
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
cat
Remainingtext
Nowwecanuseareducewithaterminalrule.
NP
NDet
the dog
V
sees
the
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack
cat
Remainingtext
Hereweshiftagain.
NP
NDet
the dog
V
sees
Det
the
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack Remainingtext
Andherewereducewithaterminalrule.
NP
NDet
the dog
V
sees
Det
the
cat
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack Remainingtext
Wenowdoareducewiththelongestavailablerule,
whichisNP!DetN.
NP
NDet
the dog
V
sees
Det
the cat
N
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack Remainingtext
Andagain…
NP
NDet
the dog
V
sees Det
the cat
N
NP
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack Remainingtext
Andagain…
NP
NDet
the dog
V
sees Det
the cat
N
NP
VP
S ! NP VP
NP ! Det N
VP ! V
VP ! V NP
Det ! “the”
N ! “cat”
N ! “dog”
V ! “sees”
Stack Remainingtext
Andnowwesucceeded.
NP
NDet
the dog
V
sees Det
the cat
N
NP
VP
S
ShiftReduce:prosandcons
• Ashift-reduceparseronlybuildsstructurethat
correspondstothewordsintheinput
• Generallymoreefficientthantop-down
• Problem:
– Iftheparsertakesthewrongturn,itmaynotfind
aparseevenifthereisone(incompleteness),and
itishardtocomeupwithgoodheuristics.
– Sobacktrackingisneededandexcessiveambiguity
maycausetrouble.
85
Shift-Reduceparserdemo
import nltk
nltk.app.srparser_app.app()
Shiftreduceparsing
ChartParser
• Efficientandcomplete
• AnexampleofDynamicProgrammingas
appliedtoparsing
DynamicProgramming
• Solveaproblembybreakingitintosmallersub
problems
• Tworequirements:
– Optimalsubstructure:optimalsolutioncanbe
createdfromoptionalsolutionsofsubproblems
– Overlappingsubproblems:samesubproblemis
solvedoverandoveragain
• RelatedtoDivideandConquerandRecursion
DynamicProgramming
• Avoidcomputingasubproblemrepeatedlyby
storingtheminalookuptable,thusreducing
waste
• ItisatechniquethatiswidelyusedinNLPto
solveproblemsofthiskind
ChartParsing
• Dynamicprogrammingappliedtosyntactic
parsing
• Aconstituentlikethemousewillbebuiltonly
onceandstoredinatable
• AWell-FormedSubstringTable(WFST)canbe
usedtostoretheintermediateresults
• Thefollowingisanoverlysimpleexampleof
usinganWFST
WFSTExample
Grammar:
S ! NP VP
NP ! Det Nom
Nom ! Adj N
VP ! V NP
Det ! “the”
Adj ! “hungry” | “little”
N ! “bear” | “fish”
V ! “scared”
Input:
“thehungrybearscaredthelittlefish”
WFST
wfst 1 2 3 4 5 6 7
0 Det
1 Adj
2 N
3 V
4 Det
5 Adj
6 N
10 2 3 4 5 6 7
the hungry bear scared the little fish
Initialization
Det Adj N V Det Adj N
start
end
wfst 1 2 3 4 5 6 7
0 Det –
1 Adj Nom
2 N –
3 V –
4 Det –
5 Adj Nom
6 N
10 2 3 4 5 6 7
the hungry bear scared the little fish
Span=2
Det Adj N V Det Adj N
Nom -> Adj N
Nom
Nom
wfst 1 2 3 4 5 6 7
0 Det – NP
1 Adj Nom –
2 N – –
3 V – –
4 Det – NP
5 Adj Nom
6 N
10 2 3 4 5 6 7
the hungry bear scared the little fish
Span=3
Det Adj N V Det Adj N
Nom -> Adj N
NP -> Det Nom
Nom
Nom
NP NP
wfst 1 2 3 4 5 6 7
0 Det – NP –
1 Adj Nom – –
2 N – – –
3 V – – VP
4 Det – NP
5 Adj Nom
6 N
10 2 3 4 5 6 7
the hungry bear scared the little fish
Span=4
Det Adj N V Det Adj N
Nom -> Adj N
NP -> Det Nom
VP -> V NP
Nom
Nom
NP NP
VP
wfst 1 2 3 4 5 6 7
0 Det – NP – –
1 Adj Nom – – –
2 N – – – –
3 V – – VP
4 Det – NP
5 Adj Nom
6 N
10 2 3 4 5 6 7
the hungry bear scared the little fish
Span=5
Det Adj N V Det Adj N
Nom -> Adj N
NP -> Det Nom
VP -> V NP
Nom
Nom
NP NP
VP
wfst 1 2 3 4 5 6 7
0 Det – NP – – –
1 Adj Nom – – – –
2 N – – – –
3 V – – VP
4 Det – NP
5 Adj Nom
6 N
10 2 3 4 5 6 7
the hungry bear scared the little fish
Span=6
Det Adj N V Det Adj N
Nom -> Adj N
NP -> Det Nom
VP -> V NP
Nom
Nom
NP NP
VP
wfst 1 2 3 4 5 6 7
0 Det – NP – – – S
1 Adj Nom – – – –
2 N – – – –
3 V – – VP
4 Det – NP
5 Adj Nom
6 N
10 2 3 4 5 6 7
the hungry bear scared the little fish
Span=7
Det Adj N V Det Adj N
Nom -> Adj N
NP -> Det Nom
VP -> V NP
S -> NP VP
Nom
Nom
NP NP
VP
S
StrengthsandweaknessesofWFST
• Strength:
– Muchmoreefficientthantherecursivedescentparser
– Doesnotgetstuckinthesamewayastheshift-reduce
parser
• Weaknesses
– Checksconstituentsthatarenotlicensedbygrammar,
potentiallywasteful
– Doesnotstorealternativeparseswhenthereis
ambiguity(onlyonecategorypercell)
100
Charts
• Graphstructure
• MoreversatilethanWFSTs
VP!VNP3
Alternativeparses
0 Sheseestheelephantwiththetelescope0 000000
V N
PP
NP
NP2
NP1
NDet
NP3!NPPP
Det
VP!VNP1PP
ChartParsers
• CYKparser
– Cocke-Younger-Kasamialgorithm
– Bottom-up
• Earleyparser
– Top-down
Earleyparser
• Fillthechartinasingleleft-to-rightpassoverthe
input.
• ThechartwillbesizeN+1,whereNisthe
numberofwordsintheinput.
• Chartentriesareassociatedwiththegaps
betweenthewords
– likesliceindexinginPython.
• Foreachpositioninthesentence,thechart
containsasetofedgesrepresentingthepartial
parsetreesgeneratedsofar.
Earleyparser
• Candealwithallcontextfreegrammars
• OperatesinO(n3)
• Operations
– Predict
– Scan
– Complete
0Mary1feeds2the3otter4eos5
Reviews
There are no reviews yet.