CSCI 5832 Natural Language Processing Jim Martin Lecture 13 01 14 19 1 Today 2 28 Finish Grammars Treebanks Parsing 2 01 14 19 Grammars Before you can parse you need a grammar So where do grammars come from Grammar Engineering Lovingly hand crafted decades long efforts by humans to write grammars typically in some particular grammar formalism of interest to the linguists developing the grammar TreeBanks Semi automatically generated sets of parse trees for the sentences in some corpus Typically in a generic lowest common denominator formalism of no particular interest to any modern linguist 3 01 14 19 TreeBank Grammars Reading off the grammar The grammar is the set of rules local subtrees that occur in the annotated corpus They tend to avoid recursion and elegance and parsimony Ie they tend to the flat and redundant Penn TreeBank III has about 17500 grammar rules under this definition 01 14 19 4 TreeBanks 5 01 14 19 TreeBanks 6 01 14 19 Sample Rules 7 01 14 19 Example 8 01 14 19 TreeBanks TreeBanks provide a grammar of a sort As we ll see they also provide the training data for various ML approaches to parsing But they can also provide useful data for more purely linguistic pursuits You might have a theory about whether or not something can happen in particular language Or a theory about the contexts in which something can happen TreeBanks can give you the means to explore those theories If you can formulate the questions in the right way and get the data you need 9 01 14 19 Tgrep You might for example like to grep through a file filled with trees 10 01 14 19 TreeBanks Finally you should have noted a bit of a circular argument here Treebanks provide a grammar because we can read the rules of the grammar out of the treebank But how did the trees get in there in the first place There must have been a grammar theory in there someplace 11 01 14 19 TreeBanks Typically not all of the sentences are hand annotated by humans They re automatically parsed and then hand corrected 12 01 14 19 Parsing Parsing with CFGs refers to the task of assigning correct trees to input strings Correct here means a tree that covers all and only the elements of the input and has an S at the top It doesn t actually mean that the system can select the correct tree from among all the possible trees 13 01 14 19 Parsing As with everything of interest parsing involves a search which involves the making of choices We ll start with some basic meaning bad methods before moving on to the one or two that you need to know 14 01 14 19 For Now Assume You have all the words already in some buffer The input isn t POS tagged We won t worry about morphological analysis All the words are known 15 01 14 19 Top Down Parsing Since we re trying to find trees rooted with an S Sentences start with the rules that give us an S Then work your way down from there to the words 16 01 14 19 Top Down Space 17 01 14 19 Bottom Up Parsing Of course we also want trees that cover the input words So start with trees that link up with the words in the right way Then work your way up from there 18 01 14 19 Bottom Up Space 19 01 14 19 Bottom Up Space 20 01 14 19 Control Of course in both cases we left out how to keep track of the search space and how to make choices Which node to try to expand next Which grammar rule to use to expand a node 21 01 14 19 Top Down and Bottom Up Top down Only searches for trees that can be answers i e S s But also suggests trees that are not consistent with any of the words Bottom up Only forms trees consistent with the words But suggest trees that make no sense globally 22 01 14 19 Problems Even with the best filtering backtracking methods are doomed if they don t address certain problems Ambiguity Shared subproblems 23 01 14 19 Ambiguity 24 01 14 19 Shared Sub Problems No matter what kind of search top down or bottom up or mixed that we choose We don t want to unnecessarily redo work we ve already done 25 01 14 19 Shared Sub Problems Consider A flight from Indianapolis to Houston on TWA 26 01 14 19 Shared Sub Problems Assume a top down parse making bad initial choices on the Nominal rule In particular Nominal Nominal Noun Nominal Nominal PP 27 01 14 19 Shared Sub Problems 28 01 14 19 Shared Sub Problems 29 01 14 19 Shared Sub Problems 30 01 14 19 Shared Sub Problems 31 01 14 19 Break Next quiz will be pushed back Readings for this section will be from Chapters 12 13 14 32 01 14 19 Parsing We re going to cover from Chapter 13 CKY today Earley Thursday Both are dynamic programming solutions that run in O n 3 time CKY is bottom up Earley is top down 33 01 14 19 Sample Grammar 34 01 14 19 Dynamic Programming DP methods fill tables with partial results and Do not do too much avoidable repeated work Solve exponential problems in polynomial time sort of Efficiently store ambiguous structures with shared sub parts 35 01 14 19 CKY Parsing First we ll limit our grammar to epsilonfree binary rules more later Consider the rule A BC If there is an A in the input then there must be a B followed by a C in the input If the A spans from i to j in the input then there must be some k st i k j Ie The B splits from the C someplace 36 01 14 19 CKY So let s build a table so that an A spanning from i to j in the input is placed in cell i j in the table So a non terminal spanning an entire string will sit in cell 0 n If we build the table bottom up we ll know that the parts of the A must go from i to k and from k to j 37 01 14 19 CKY Meaning that for a rule like A B C we should look for a B in i k and a C in k j In other words if we think there might be an A spanning i j in the input AND A B C is a rule in the grammar THEN There must be a B in i k and a C in k j for some i k j 38 01 14 19 CKY So to fill the table loop over the cell i j values in some systematic way What constraint should we put on that For each cell loop over the appropriate k values to search for things to add 39 01 14 19 CKY Table 40 …
View Full Document
Unlocking...