1CS 294-5: StatisticalNatural Language ProcessingDan KleinMF 1-2:30p mSoda Hall 310The Parsing Task Parsing marks how words are syntactically organized Decisions we make here affect how we process the text Big difference between natural languages and programming languages: rampant ambiguitynew art critics write reviews with computersPPNPNPN’NPVPSContext-Free Grammars A context- free grammar is a tuple <N, T, S, R> N : the set of non-terminals Phrasal categories: S, NP, VP, ADJP, etc. Parts-of-speech (pre-terminals): NN, JJ, DT, VB T : the set of terminals (the words) S : the start symbol Often written as ROOT or TOP Not usually the sentence non-terminal S R : the set of rules Of the form X → Y1Y2…Yk, with X, Yi∈ N Examples: S → NP VP, VP → VP CC VP Also called rewrites, productions, or local treesExample CFG Can just write the grammar (rules with non-terminal LHSs) and lexicon (rules with pre-terminal LHSs)ROOT → SS → NP VPVP → VBPVP → VBP NPVP → VP PPPP → IN NPJJ → newNN → artNNS → criticsNNS → reviewsNNS → computersVBP → writeIN → withNP → NNSNP → NNNP → JJ NPNP → NP NNSNP → NP PPGrammar LexiconTop-Down Generation from CFGs A CFG generates a language Fix an order: apply rules to leftmost non-terminal Gives a derivation of a tree using rules of the grammarROOTSNP VPNNS VPcritics VPcritics VBP NPcritics write NPcritics write NNScritics write reviewsROOTSNPVPNNScriticsVBP NPNNSreviewswriteParsing as Search: Top-Down Top-down parsing: starts with the root and tries to generate the inputROOTROOTSROOTSNPVPROOTSNPVPNNSROOTSNPVPNP PPINPUT: critics write reviews2How Top-Down Fails Big problem 1: search isn’t guided by the input Big problem 2: separate ambiguities create redundant workINPUT: critics write reviewsNP VPNP PP VP NP NNS PP VP JJ NP NNS PP VPNP VPnew art critics write reviews with computers[NP] NNS VP[new art] critics VPnew [art critics] VP[JJ NP] VP[new art] critics VBP NP[new art] critics VBP NP PPnew [art critics] VBP NPnew [art critics] VBP NP PPParsing as Search: Bottom-Up Bottom-up parsing: input drives the search (shift-reduce parsing)critics write reviewsROOTSNPVPNNScriticsVBP NPNNSreviewswriteNNS write reviewsNP write reviewsNP VBP NNSNP VBP NPNP VPNP VBP reviewsSROOTHow Bottom-Up Fails Big Problem 1: ambiguities still create redundant work Little Problem: partial analyses which can’t be completednew art critics write reviews with computersNP VBP NP PPNP VBP NPnew art critics write reviews with computers[new art][art critics]NP VBP NP PPNP VP PPNP VBP NPNP VP PPart critics write reviews with art computers[ NP ] [ VP ] computersA Simple Chart Parser Chart parsers are sparse dynamic programs Ingredients: Nodes: positions between words Edges: spans of words with labels, represent the set of trees over those words rooted at x A chart: records which edges we’ve built An agenda: a holding pen for edges (a queue) We’re going to figure out: What edges can we build? All the ways we built them.012 34 5critics write reviews with computersPPWord Edges An edge found for the first time is called discovered. Edges go into the agenda on discovery. To initialize, we discover all word edges.critics write reviews with computerscritics[0,1], write[1,2], reviews[2,3], with[3,4], computers[4,5]012 34 5AGENDACHART [EMPTY]Unary Projection When we pop an word edge off the agenda, we check the lexicon to see what tag edges we can build from itcritics write reviews with computers012 34 5critics write reviews with computerscritics[0,1]write[1,2]NNS[0,1]reviews[2,3] with[3,4] computers[4,5]VBP[1,2] NNS[2,3] IN[3,4] NNS[3,4]3The “Fundamental Rule” When we pop edges off of the agenda: Check for unary projections (NNS → critics, NP → NNS) Combine with edges already in our chart (this is sometimes called the fundamental rule) Enqueue resulting edges (if newly discovered) Record backtraces (called traversals) Stick the popped edge in the chart Queries a chart must support: Is edge X:[i,j] in the chart? What edges with label Y end at position j? What edges with label Z start at position i? Y[i,j] with X → Y forms X[i,j]Y[i,j] and Z[j,k] with X → Y Z form X[i,k]YZXAn Example012 34 5critics write reviews with computersNNSVBP NNS IN NNSNNS[0,1] VBP[1,2] NNS[2,3] IN[3,4] NNS[3,4] NP[0,1] NP[2,3] NP[4,5]NP NPNPVP[1,2] S[0,2]VPPP[3,5]PPVP[1,3]VPROOT[0,2]SROOTSROOTS[0,3] VP[1,5]VPNP[2,5]NPROOT[0,3] S[0,5] ROOT[0,5]SROOTExploiting Substructure Each edge records all the ways it was built (locally) Can recursively extract trees A chart may represent too many parses to enumerate (how many?)01234 5critics write reviews with computersNPPPVPNP6 7new artNPNPVPSJJ NNS VBPOrder Independence A nice property: It doesn’t matter what policy we use to order the agenda (FIFO, LIFO, random). Why? Invariant: before popping an edge: Any edge X[i,j] that can be directly built from chart edges and a single grammar rule is either in the chart or in the agenda. Convince yourselves this invariant holds! This will not be true once we get weighted parsers.Empty Elements Sometimes we want to posit nodes in a parse tree that don’t contain any pronounced words: These are easy to add to our chart parser! For each position i, add the “word” edge ε:[i,i] Add rules like NP →εto the grammar That’s it!01 2 3 4 5Iliketoparseemptiesε εεε ε εNPVPI want John to parse this sentenceI want [ ] to parse this sentence(Speech) Lattices There was nothing magical about words spanning exactly one position. When working with speech, we generally don’t know how many words there are, or where they break. We can represent the possibilities as a lattice and parse these just as easily! (cf. HW 1)Iaweofvaneyessawa‘veanIvan4N-Ary Rules Often we want to write grammar rules likewhich are not binary. We can work with these rules by introducing new intermediate symbols into our grammar: We’ll hear much more about this kind of thing when we talk about grammar representation later in the course.VP → VBD NP PP PPVP[VP → VBD NP •]VBD NPPPPP[VP → VBD NP PP •]Runtime: Theory How long does it take to parse a sentence? Depends on: Sentence length
View Full Document
Unlocking...