CSCI 5832 Natural Language Processing Jim Martin Lecture 12 2 28 08 1 Today 2 26 Syntax Context Free Grammars Review Quiz More grammars 2 2 28 08 Syntax By syntax or grammar I mean the kind of implicit knowledge of your native language that you had mastered by the time you were 2 or 3 years old without explicit instruction Not the kind of stuff you were later taught in school 3 2 28 08 1 Syntax Why should you care Grammar checkers Question answering Information extraction Machine translation 4 2 28 08 Context Free Grammars Capture constituency and ordering Ordering is easy What are the rules that govern the ordering of words and bigger units in the language What s constituency How words group into units and how the various kinds of units behave wrt one another 5 2 28 08 CFG Examples S NP VP NP Det NOMINAL NOMINAL Noun VP Verb Det a Noun flight Verb left 6 2 28 08 2 CFGs S NP VP This says that there are units called S NP and VP in this language That an S consists of an NP followed immediately by a VP Doesn t say that that s the only kind of S Nor does it say that this is the only place that NPs and VPs occur 7 2 28 08 Generativity As with FSAs and FSTs you can view these rules as either analysis or synthesis machines Generate strings in the language Reject strings not in the language Impose structures trees on strings in the language 8 2 28 08 Derivations A derivation is a sequence of rules applied to a string that accounts for that string Covers all the elements in the string Covers only the elements in the string 9 2 28 08 3 Derivations as Trees 10 2 28 08 Parsing Parsing is the process of taking a string and a grammar and returning a many parse tree s for that string It is completely analogous to running a finite state transducer with a tape It s just more powerful Remember this means that there are languages we can capture with CFGs that we can t capture with finite state methods 11 2 28 08 Other Options Regular languages expressions Too weak Context sensitive or Turing equiv Too powerful maybe 12 2 28 08 4 Context The notion of context in CFGs has nothing to do with the ordinary meaning of the word context in language All it really means is that the non terminal on the lefthand side of a rule is out there all by itself free of context A B C Means that I can rewrite an A as a B followed by a C regardless of the context in which A is found Or when I see a B followed by a C I can infer an A regardless of the surrounding context 13 2 28 08 Key Constituents English Sentences Noun phrases Verb phrases Prepositional phrases 14 2 28 08 Sentence Types Declaratives A plane left S NP VP Imperatives Leave S VP Yes No Questions Did the plane leave S Aux NP VP WH Questions When did the plane leave S WH Aux NP VP 15 2 28 08 5 Recursion We ll have to deal with rules such as the following where the non terminal on the left also appears somewhere on the right directly Nominal Nominal PP flight to Boston VP VP PP departed Miami at noon 16 2 28 08 Recursion Of course this is what makes syntax interesting flights from Denver Flights from Denver to Miami Flights from Denver to Miami in February Flights from Denver to Miami in February on a Friday Flights from Denver to Miami in February on a Friday under 300 Flights from Denver to Miami in February on a Friday under 300 with lunch 17 2 28 08 Recursion Of course this is what makes syntax interesting flights from Denver Flights from Denver to Miami Flights from Denver to Miami in February Flights from Denver to Miami in February on a Friday Etc 18 2 28 08 6 The Point If you have a rule like VP V NP It only cares that the thing after the verb is an NP It doesn t have to know about the internal affairs of that NP 19 2 28 08 The Point 20 2 28 08 Conjunctive Constructions S S and S John went to NY and Mary followed him NP NP and NP VP VP and VP In fact the right rule for English is X X and X 21 2 28 08 7 Break Quiz 1 2 3 4 5 29 slides True slides slides 22 2 28 08 2 Rules Verb PresPart Verb ing lexical ie ing y ing surface TIE PP TIE ing tying 2 28 08 23 4a One fish One fish two fish red fish blue fish 2 28 08 One Two Red Blue Fish One 0 0 0 0 1 Two 0 0 0 0 1 Red 0 0 0 0 1 Blue 0 0 0 0 1 Fish 0 1 1 1 0 24 8 4b One fish One fish two fish red fish blue fish 2 28 08 One Two Red Blue Fish One 1 1 1 1 2 Two 1 1 1 1 2 Red 1 1 1 1 2 Blue 1 1 1 1 2 Fish 1 2 2 2 1 25 4b P fish red Count red fish Count red 2 6 1 3 P fish fish Count fish fish Count fish 1 9 26 2 28 08 4c Would trigrams help No Think in terms of the two cases here There are fish and there are adjs P fish ADJ 1 P ADJ fish 1 A trigram model P fish fish ADJ 1 P ADJ adj fish 1 But maybe 27 2 28 08 9 5 Need 1 Transition table 2 Observation table 3 Start table 28 2 28 08 5a Transition table JJ NN ORD JJ 0 4 0 NN 4 0 1 ORD 0 2 0 29 2 28 08 5a Observation table s One Fish Two Red Blue Black JJ 0 0 0 1 2 1 NN 0 6 0 0 0 0 ORD 1 0 1 0 0 0 30 2 28 08 10 5a Start table Pi START JJ NN ORD 0 0 1 31 2 28 08 5b Two fish blue fish ORD NN JJ NN P ORD START P NN ORD P JJ NN P NN JJ P Two ORD P Fish NN P Blue JJ P Fish NN 32 2 28 08 5b START JJ JJ JJ JJ NN NN NN NN ORD ORD ORD ORD Two fish blue fish 33 2 28 08 11 Problems Agreement Subcategorization Movement for want of a better term 34 2 28 08 Agreement This dog Those dogs This dogs Those dog This dog eats Those dogs eat This dog eat Those dogs eats 35 2 28 08 Agreement In English subjects and verbs have to agree in person and number Determiners and nouns have to agree in number Many languages …
View Full Document
Unlocking...